CountSketches, Feature Hashing and the Median of Three

Kasper Green Larsen, Rasmus Pagh, Jakub Tetek

Overview

This paper provides a new theoretical analysis of the classic CountSketch algorithm, proving that using just three rows (the "median of three") dramatically improves estimation accuracy compared to a single row. It demonstrates that this simple architectural change reduces variance by a factor proportional to the sketch size, finally offering a theoretical explanation for why practitioners have long favored using a small, constant number of rows.

The Problem with Standard Theory

CountSketch is a fundamental tool in data streaming and machine learning, used to estimate the frequency of items or the inner product of high-dimensional vectors using minimal memory. Standard theory suggests that to achieve high-confidence estimates, the number of rows must scale logarithmically with the desired failure probability.

However, in real-world applications, engineers often use just 3 or 5 rows. Previous theoretical analyses only predicted a constant-factor improvement for these small settings, failing to explain the massive performance gains observed in practice. This paper addresses that gap, showing that the "median of three" isn't just a minor tweak—it fundamentally changes how the error scales.

Methodology: Moments of the Median

The authors introduce a novel analysis technique focused on the moments of the median. Instead of the typical approach using concentration inequalities (like Chernoff bounds), they prove a general theorem relating the higher-order moments of the median of several independent estimates to the lower-order moments of a single estimate.

Specifically, they analyze CountSketch with $t=2$ (which corresponds to $2t-1 = 3$ rows). By applying their new moment bounds, they demonstrate that the variance of the "median of three" estimator is bounded by $O(\min\{\|v\|_1^2/s^2, \|v\|_2^2/s\})$, where $s$ is the number of columns. This is a significant improvement over the standard $O(\|v\|_2^2/s)$ bound for a single row.

Datasets Evaluated

The researchers evaluated their findings on both synthetic and real-world datasets:

  • Kosarak: An anonymized click-stream dataset from a Hungarian news portal.
  • Sentiment140: A collection of 1.6 million tweets used for sentiment analysis.
  • Zipfian: Synthetic data following power-law distributions, common in natural language and network traffic.
  • News20: A collection of newsgroup documents, used specifically to test inner product estimation.
  • Disjoint 64 non-zeros: A synthetic benchmark for inner product estimation where vectors have no overlapping entries.

Key Insights

  • The $1/s^2$ Scaling: The most surprising finding is that moving from one row to three rows changes the variance scaling from $1/s$ to $1/s^2$ in terms of the $\ell_1$ norm. This means as memory (columns) increases, the error drops much faster than previously thought.
  • Universal Median Property: The authors discovered a general mathematical property: the $tq$-th moment of the median of $2t-1$ variables is bounded by the $q$-th moment of a single variable, raised to the $t$-th power. This insight is broadly applicable beyond just sketching algorithms.
  • Feature Hashing Benefits: Since a single-row CountSketch is identical to the popular "feature hashing" scheme used in machine learning, this work implies that using a "median of three" feature hashing approach can drastically reduce noise in ML pipelines for a negligible increase in computation.

Empirical Results

The empirical results strongly support the new theory. The variance for the median of three ($t=2$) drops much more sharply than the single-row version ($t=1$) as the sketch size increases.

Variance plots for CountSketch with t=1 and t=2. The first plot shows polynomial decrease on a log-log scale, while the third plot highlights the 1/s² behavior for t=2.

Quantitatively, the researchers found:

  • On the Kosarak dataset, using 3 rows instead of 1 reduced variance by a factor of 88x for the same total memory.
  • On Zipfian data with high skew, the reduction was as high as 173.9x.
  • The theoretical $O(1/s^2)$ behavior was clearly visible in experiments once the number of columns $s$ was sufficiently large.

Limitations and Future Work

  • Differentiability: One major hurdle for deep learning applications is that the median is not a continuously differentiable operation. This makes it difficult to use "median of three" CountSketches directly in neural network architectures where backpropagation is required. Finding a differentiable approximation of the median could be a fruitful area for future research.
  • Inner Product Thresholds: For inner product estimation, the $1/s^2$ benefit only becomes dominant when the number of columns $s$ is quite large relative to the vectors' $\ell_2$ norms. In some low-memory regimes, the improvement might be less pronounced than in frequency estimation.

Summary updated

Abstract

In this paper, we revisit the classic CountSketch method, which is a sparse, random projection that transforms a (high-dimensional) Euclidean vector $v$ to a vector of dimension $(2t-1) s$, where $t, s > 0$ are integer parameters. It is known that even for $t=1$, a CountSketch allows estimating coordinates of $v$ with variance bounded by $\|v\|_2^2/s$. For $t > 1$, the estimator takes the median of $2t-1$ independent estimates, and the probability that the estimate is off by more than $2 \|v\|_2/\sqrt{s}$ is exponentially small in $t$. This suggests choosing $t$ to be logarithmic in a desired inverse failure probability. However, implementations of CountSketch often use a small, constant $t$. Previous work only predicts a constant factor improvement in this setting. Our main contribution is a new analysis of Count-Sketch, showing an improvement in variance to $O(\min\{\|v\|_1^2/s^2,\|v\|_2^2/s\})$ when $t > 1$. That is, the variance decreases proportionally to $s^{-2}$, asymptotically for large enough $s$. We also study the variance in the setting where an inner product is to be estimated from two CountSketches. This finding suggests that the Feature Hashing method, which is essentially identical to CountSketch but does not make use of the median estimator, can be made more reliable at a small cost in settings where using a median estimator is possible. We confirm our theoretical findings in experiments and thereby help justify why a small constant number of estimates often suffice in practice. Our improved variance bounds are based on new general theorems about the variance and higher moments of the median of i.i.d. random variables that may be of independent interest.
BibTeX
@inproceedings{larsen2021countsketches,
  author = {Kasper Green Larsen and Rasmus Pagh and Jakub Tetek},
  title = {{CountSketches, Feature Hashing and the Median of Three}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=r-0tOmJsUa},
}
Figure