# Sharper Bounds for ℓp Sensitivity Sampling

arXiv: https://arxiv.org/abs/2306.00732 · HTML: https://mlsanity.com/paper/2306.00732/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 1 Jun 2023.

## Builds on (most cited first, 21 of 21)

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Biased Importance Sampling for Deep Neural Network Training](https://mlsanity.com/paper/1706.00043/) (2017)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [Fast Regression for Structured Inputs](https://mlsanity.com/paper/2203.07557/) (2022)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression](https://mlsanity.com/paper/1907.07167/) (2019)
- [Improved Iteration Complexities for Overconstrained p-Norm Regression](https://mlsanity.com/paper/2111.01848/) (2021)
- [Computing Lewis Weights to High Precision](https://mlsanity.com/paper/2110.15563/) (2021)
- [High-Dimensional Geometric Streaming in Polynomial Space](https://mlsanity.com/paper/2204.03790/) (2022)
- [Iterative Refinement for ℓp-norm Regression](https://mlsanity.com/paper/1901.06764/) (2019)
- [Faster p-norm minimizing flows, via smoothed q-norm problems](https://mlsanity.com/paper/1910.10571/) (2019)
- [Faster p-Norm Regression Using Sparsity](https://mlsanity.com/paper/2109.11537/) (2021)

## Abstract (arXiv)

In large scale machine learning, random sampling is a popular way to approximate datasets by a small representative subset of examples. In particular, sensitivity sampling is an intensely studied technique which provides provable guarantees on the quality of approximation, while reducing the number of examples to the product of the VC dimension d and the total sensitivity mathfrak S in remarkably general settings. However, guarantees going beyond this general bound of mathfrak S d are known in perhaps only one setting, for ℓ2 subspace embeddings, despite intense study of sensitivity sampling in prior work. In this work, we show the first bounds for sensitivity sampling for ℓp subspace embeddings for p > 2 that improve over the general mathfrak S d bound, achieving a bound of roughly mathfrak S2-2/p for 2<p<∞. Furthermore, our techniques yield further new results in the study of sampling algorithms, showing that the root leverage score sampling algorithm achieves a bound of roughly d for 1≤ p<2, and that a combination of leverage score and sensitivity sampling achieves an improved bound of roughly d2/pmathfrak S2-4/p for 2<p<∞. Our sensitivity sampling results yield the best known sample complexity for a wide class of structured matrices that have small ℓp sensitivity.