# Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 43 references that are in the map.
- First posted on arXiv 1 Jun 2024.

## 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)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more](https://mlsanity.com/paper/1802.07382/) (2018)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [New Subset Selection Algorithms for Low Rank Approximation: Offline and Online](https://mlsanity.com/paper/2304.09217/) (2023)
- [Non-Adaptive Adaptive Sampling on Turnstile Streams](https://mlsanity.com/paper/2004.10969/) (2020)
- [ℓp Row Sampling by Lewis Weights](https://mlsanity.com/paper/1412.0588/) (2014)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Tight Bounds for the Subspace Sketch Problem with Applications](https://mlsanity.com/paper/1904.05543/) (2019)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)
- [Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds](https://mlsanity.com/paper/2405.01339/) (2024)
- [Sparsifying sums of norms](https://mlsanity.com/paper/2305.09049/) (2023)
- [Tight Bounds for Volumetric Spanners and Applications](https://mlsanity.com/paper/2310.00175/) (2023)

## Built on by (most cited first, 3 of 3)

- [Data subsampling for Poisson regression with pth-root-link](https://mlsanity.com/paper/2410.22872/) (2024)
- [The Space Complexity of Approximating Logistic Loss](https://mlsanity.com/paper/2412.02639/) (2024)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)

## Abstract (arXiv)

Data subsampling is one of the most natural methods to approximate a massively large data set by a small representative proxy. In particular, sensitivity sampling received a lot of attention, which samples points proportional to an individual importance measure called sensitivity. This framework reduces in very general settings the size of data to roughly the VC dimension d times the total sensitivity mathfrak S while providing strong (1±varepsilon) guarantees on the quality of approximation. The recent work of Woodruff & Yasuda (2023c) improved substantially over the general tilde O(varepsilon-2mathfrak Sd) bound for the important problem of ℓp subspace embeddings to tilde O(varepsilon-2mathfrak S2/p) for p∈[1,2]. Their result was subsumed by an earlier tilde O(varepsilon-2mathfrak Sd1-p/2) bound which was implicitly given in the work of Chen & Derezinski (2021). We show that their result is tight when sampling according to plain ℓp sensitivities. We observe that by augmenting the ℓp sensitivities by ℓ2 sensitivities, we obtain better bounds improving over the aforementioned results to optimal linear tilde O(varepsilon-2(mathfrak S+d)) = tilde O(varepsilon-2d) sampling complexity for all p ∈ [1,2]. In particular, this resolves an open question of Woodruff & Yasuda (2023c) in the affirmative for p ∈ [1,2] and brings sensitivity subsampling into the regime that was previously only known to be possible using Lewis weights (Cohen & Peng, 2015). As an application of our main result, we also obtain an tilde O(varepsilon-2μ d) sensitivity sampling bound for logistic regression, where μ is a natural complexity measure for this problem. This improves over the previous tilde O(varepsilon-2μ2 d) bound of Mai et al. (2021) which was based on Lewis weights subsampling.