Timezone: »
Spotlight
Fully Understanding The Hashing Trick
Casper B. Freksen · Lior Kamma · Kasper Green Larsen
Feature hashing, also known as {\em the hashing trick}, introduced by Weinberger et al. (2009), is one of the key techniques used in scalingup machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix $A : \mathbb{R}^n \to \mathbb{R}^m$ (where $m \ll n$) in order to reduce the dimension of the data from $n$ to $m$ while approximately preserving the Euclidean norm. Every column of $A$ contains exactly one nonzero entry, equals to either $1$ or $1$.
Weinberger et al. showed tail bounds on $\Ax\_2^2$. Specifically they showed that for every $\varepsilon, \delta$, if $\x\_{\infty} / \x\_2$ is sufficiently small, and $m$ is sufficiently large, then
\begin{equation*}\Pr[ \;  \;\Ax\_2^2  \x\_2^2\;  < \varepsilon \x\_2^2 \;] \ge 1  \delta \;.\end{equation*}
These bounds were later extended by Dasgupta et al. (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters $\x\_{\infty} / \x\_2, m, \varepsilon, \delta$ remained an open question.
We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants "hiding" in the asymptotic notation are, in fact, very close to $1$, thus further illustrating the tightness of the presented bounds in practice.
Author Information
Casper B. Freksen (Aarhus University)
Lior Kamma (Aarhus University)
Kasper Green Larsen (Aarhus University, MADALGO)
Related Events (a corresponding poster, oral, or spotlight)

2018 Poster: Fully Understanding The Hashing Trick »
Thu. Dec 6th through Fri the 7th Room Room 210 #90
More from the Same Authors

2022 Poster: Improved Coresets for Euclidean $k$Means »
Vincent CohenAddad · Kasper Green Larsen · David Saulpic · Chris Schwiegelshohn · Omar Ali SheikhOmar 
2022 Poster: Optimal Weak to Strong Learning »
Kasper Green Larsen · Martin Ritzert 
2020 Poster: Margins are Insufficient for Explaining Gradient Boosting »
Allan Grønlund · Lior Kamma · Kasper Green Larsen 
2019 Poster: MarginBased Generalization Lower Bounds for Boosted Classifiers »
Allan Grønlund · Lior Kamma · Kasper Green Larsen · Alexander Mathiasen · Jelani Nelson