Research map / Learning theory and algorithms / Sample complexity
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows the birthday-paradox folklore map (O(s^2) dims) is essentially optimal for average-case norm preservation of sparse vectors under linear and smooth maps, and gives a non-linear max-pooling hashing embedding for non-negative sparse vectors with O(s log(n s)/eps^2) dimensions for any l_p.
Problem
Dimensionality reduction for s-sparse vectors in l_p norms beyond worst-case: whether the birthday-paradox O(s^2) bound is optimal under average-case guarantees, and whether non-negativity enables smaller non-linear embeddings especially for l_infinity.
Approach
Proves Omega(s^2) lower bounds for linear and smooth (twice-differentiable) maps preserving norms of 99% of sparse vectors, and for non-negative sparse vectors replaces the linear hashing sum with a max-pooling hash that is non-expanding, enabling non-linear embeddings of size O(s log(n)/eps^2) for all l_p and exact l_infinity embedding in O(s log n) dimensions.
Key results
- Linear maps preserving l_p norms of 99% of s-sparse vectors require m >= s^2/1000 dimensions (even p), and the lower bound extends to twice-differentiable maps and encoder-decoder schemes for l_2.
- Non-negative sparse max-pooling embedding achieves O(s log(ns)/eps^2) dimensions for all p >= 1 with non-linear map, versus prior (s^2/eps^2)(p log n)^{O(p)} linear bounds.
- Exact l_infinity dimensionality reduction for non-negative sparse vectors into O(s log n) dimensions, shown tight up to constants via lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a non-linear max-pooling embedding instead of a linear embedding | Non-negative s-sparse vectors · Pairwise [?2;2~p distances, p ≥ 1 | embedding dimension: O\left( \frac{s \log(n)}{\varepsilon^2} \right) vs. \frac{s^2}{\eps^2} \cdot (p \log(n))^{O(p)} | Helped |
| Use the non-linear embedding for non-negative vectors | Non-negative s-sparse vectors · Pairwise [?2;2~∞ distances | embedding dimension: O(s \log(n)) | Helped |
| Require a linear map rather than a non-linear map (ablation) | Non-negative 10-sparse vectors in R^d · [?2;2~∞ norm | embedding dimension: \Omega(d) | Hurt |
| Require twice differentiability (ablation) | Non-negative 10-sparse vectors in R^d · [?2;2~∞ norm | embedding dimension: \Omega(d) | Hurt |
| Drop the non-negativity assumption (ablation) | Sparse-vector [?2;2~∞ embedding · Pairwise distances | embedding dimension: \Omega(d) | Hurt |
| Require preservation of sums with approximation factor strictly below 2 (ablation) | Non-negative sparse-vector embedding · Sums in [?2;2~∞ norm | embedding dimension: m \ge d | Hurt |
Surprising findings
- Arbitrary (non-smooth) decoders allow O(s log d) dimensions via compressed sensing, so smoothness of encoder/decoder forces Omega(s^2), a sharp separation.
- Linear maps provably fail for non-negative sparse l_infinity embedding (Omega(d) lower bound), so non-linearity is necessary.
Limitations
- Average-case lower bounds apply only to a constant fraction of vectors and to linear or smooth maps; arbitrary maps are not covered.
- Non-negativity is required for the upper bound; general sparse vectors suffer Omega(d) for l_infinity with non-expanding maps.
- The eps dependence of the non-negative upper bound is not shown to be tight.
Experimental setup
Metrics: norm preservation probability distortion
Baselines: birthday paradox map RIP matrices linear sparse JL maps
Builds on: Johnson-Lindenstrauss lemma restricted isometry property birthday paradox hashing
Closest papers by meaning
- Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.92)
- Minimum Norm Interpolation Meets The Local Theory of Banach Spaces (ICML 2024 · similarity 0.86)
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.85)
- Enhancing Sufficient Dimension Reduction via Hellinger Correlation (ICML 2024 · similarity 0.85)
- Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees (ICML 2025 · similarity 0.85)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.