Research map / Learning theory and algorithms / Sample complexity
Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
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 that pure ℓp sensitivity sampling needs Ω(d^{2-p/2}) samples for ℓp subspace embeddings, and that augmenting ℓp sensitivities with ℓ2 sensitivities and uniform weights yields optimal Õ(ε^-2 d) sampling for p in [1,2], extended to logistic regression with Õ(ε^-2 μ d).
Problem
Sensitivity sampling for ℓp subspace embeddings (p in [1,2]) and logistic regression typically needs more samples than the optimal linear dependence on d; it was open whether ℓp sensitivity sampling can reach Õ(ε^-2(S+d)).
Approach
Augment ℓp sensitivity sampling probabilities with ℓ2 leverage scores and a uniform 1/n term, and keep sampling weights separate (not folded into the data) so that ℓ2 and ℓp subspace embedding guarantees hold simultaneously; generalize the chaining/Gaussian process analysis to weighted norms; use a p-ReLU decomposition of the logistic loss to obtain μd dependence.
Key results
- Proves an Ω(d^{2-p/2}/(log d)^{p/2}) lower bound for pure ℓp leverage score sampling to form an ℓp subspace embedding.
- Shows ℓ2-augmented ℓp sensitivity sampling achieves Õ(ε^-2(S^{(p)}+d)) = Õ(ε^-2 d) sample size for all p in [1,2], matching Lewis-weight bounds up to polylog factors.
- Gives an Õ(ε^-2 μ d) sensitivity sampling bound for logistic regression, improving the previous Õ(ε^-2 μ^2 d).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| augment ℓp sensitivities with ℓ2 sensitivities and a uniform term | ℓp sensitivity sampling · ℓp subspace embeddings, p ∈ [1,2] | sample complexity: \tilde O(\varepsilon^{-2}(\mathfrak S^{(p)} + d)) vs. \tilde O(\varepsilon^{-2}\mathfrak S^{2/p}) | Helped |
| augment ℓ1 sensitivities with ℓ2 sensitivities and a uniform term | Sensitivity sampling for logistic regression · Logistic regression | sample complexity: \tilde O(\varepsilon^{-2}\mu d) vs. \tilde O(\varepsilon^{-2}\mu^2 d) | Helped |
| sample according to pure ℓp leverage scores rather than augmenting them with ℓ2 sensitivities | ℓp sensitivity sampling · ℓp subspace embeddings, p ∈ [1,2] | sample complexity lower bound: \tilde\Omega(d^{2-p/2}) | Hurt |
Surprising findings
- Pure ℓp sensitivity sampling is provably suboptimal (off by d^{1-p/2}) even though the total sensitivity bound is tight, so the probabilities must be changed.
- Uniform sampling augmentation does not help against the lower bound.
Limitations
- Result only for p in [1,2]; the p>2 case gives no improvement over prior bounds.
- Assumes access to exact ℓp and ℓ2 sensitivity scores without giving approximation algorithms.
- Results are worst-case theoretical bounds, not validated empirically in the excerpt.
Experimental setup
Metrics: sample size complexity (theoretical) relative approximation error
Baselines: plain sensitivity sampling Lewis weight sampling Mutually-augmented sensitivity bound of prior work (S^{2/p}) Sd^{1-p/2} sensitivity bound previous logistic regression Lewis weight bound O(μ^2 d)
Builds on: sensitivity sampling Lewis weights Dudley chaining bound Dual Sudakov minoration
Closest papers by meaning
- Robust Statistical Estimators with Bounded Empirical Sensitivity (NeurIPS 2026 · similarity 0.85)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.85)
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.84)
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.84)
- Minimum Norm Interpolation Meets The Local Theory of Banach Spaces (ICML 2024 · similarity 0.84)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.84)
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.