  We consider the problem of sketching the $p$-th frequency moment of a vector,
$p>2$, with multiplicative error at most $1\pm \epsilon$ and \emph{with high
confidence} $1-\delta$. Despite the long sequence of work on this problem,
tight bounds on this quantity are only known for constant $\delta$. While one
can obtain an upper bound with error probability $\delta$ by repeating a
sketching algorithm with constant error probability $O(\log(1/\delta))$ times
in parallel, and taking the median of the outputs, we show this is a suboptimal
algorithm! Namely, we show optimal upper and lower bounds of $\Theta(n^{1-2/p}
\log(1/\delta) + n^{1-2/p} \log^{2/p} (1/\delta) \log n)$ on the sketching
dimension, for any constant approximation. Our result should be contrasted with
results for estimating frequency moments for $1 \leq p \leq 2$, for which we
show the optimal algorithm for general $\delta$ is obtained by repeating the
optimal algorithm for constant error probability $O(\log(1/\delta))$ times and
taking the median output. We also obtain a matching lower bound for this
problem, up to constant factors.
