High Probability Frequency Moment Sketches

We consider the problem of sketching the $p$-th frequency moment of a vector, $p>2$, with multiplicative error at most $1\pm ε$ and \emph{with high confidence} $1-δ$. Despite the long sequence of work on this problem, tight bounds on this quantity are only known for constant $δ$. While one can obtain an upper bound with error probability $δ$ by repeating a sketching algorithm with constant error probability $O(\log(1/δ))$ 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 $Θ(n^{1-2/p} \log(1/δ) + n^{1-2/p} \log^{2/p} (1/δ) \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 $δ$ is obtained by repeating the optimal algorithm for constant error probability $O(\log(1/δ))$ times and taking the median output. We also obtain a matching lower bound for this problem, up to constant factors.