Fully Understanding The Hashing Trick
summary
Gives a tight characterization of when feature hashing preserves L2 norms: if M is at or below the Johnson–Lindenstrauss dimension it fails, if M is much larger it succeeds, and the intermediate regime is precisely pinned down by the ratio nu = ||x||_infty / ||x||_2 (threshold scales like epsilon^{2/3} up to log factors). Proof uses higher moment bounds on the norm error, moment-to-concentration tools (Markov, Paley–Zygmund), combinatorial counting via Eulerian multigraph encoding, and shows tightness; connects to CountSketch equivalence.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:41Classification and Recommendation
- 1:32Feature Vectors
- 2:21Dimensionality Reduction
- 3:49Johnson–Lindenstrauss Lemma JL'84
- 5:21Feature Hashing Weinberger et al.
- 10:51Tight Bounds - Formal Problem
- 17:45Tight Bounds on Higher Moments of X
- 22:33Counting Edge-Labeled Eulerian Graphs
- 24:14Encoding Graphs
related talks
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
37mMin-Wise Hashing for Large-Scale Regression and Classification
42mDimensionality Reduction Via Sparse Matrices
01h 34mAlgorithmic High-Dimensional Geometry I
01h 03mHigh Dimensional Geometry and Concentration II
01h 02mImportance Sampling in High Dimensions via Hashing
39mProbabilistic Hashing Methods for Succinct Data Representations and Applications
01h 34mAlgorithmic High-Dimensional Geometry II