# High Probability Frequency Moment Sketches

arXiv: https://arxiv.org/abs/1805.10885 · HTML: https://mlsanity.com/paper/1805.10885/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2018.

## Built on by (most cited first, 2 of 2)

- [Improving textitTug-of-War sketch using Control-Variates method](https://mlsanity.com/paper/2203.02432/) (2022)
- [Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms](https://mlsanity.com/paper/2408.08494/) (2024)

## Abstract (arXiv)

We consider the problem of sketching the p-th frequency moment of a vector, p>2, with multiplicative error at most 1± ε and 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 Theta(n1-2/p log(1/δ) + n1-2/p log2/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 ≤ p ≤ 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.