# Computing Approximate ℓp Sensitivities

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 39 of its 81 references that are in the map.
- First posted on arXiv 7 Nov 2023.

## Builds on (most cited first, 30 of 39)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Prioritized Training on Points that are Learnable, Worth Learning, and Not Yet Learnt](https://mlsanity.com/paper/2206.07137/) (2022)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Provable Filter Pruning for Efficient Neural Networks](https://mlsanity.com/paper/1911.07412/) (2019)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Biased Importance Sampling for Deep Neural Network Training](https://mlsanity.com/paper/1706.00043/) (2017)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [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)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Data-Independent Structured Pruning of Neural Networks via Coresets](https://mlsanity.com/paper/2008.08316/) (2020)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data](https://mlsanity.com/paper/1710.10364/) (2017)
- [Solving Linear Programs with Sqrt(rank) Linear System Solves](https://mlsanity.com/paper/1910.08033/) (2019)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures](https://mlsanity.com/paper/1508.05243/) (2015)
- [Dimensionality Reduction for Tukey Regression](https://mlsanity.com/paper/1905.05376/) (2019)
- [Tight Sensitivity Bounds For Smaller Coresets](https://mlsanity.com/paper/1907.01433/) (2019)

## Abstract (arXiv)

Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering provable guarantees on the quality of the approximation after removing low-sensitivity datapoints via subsampling. However, fast algorithms for approximating ℓp sensitivities, which we show is equivalent to approximate ℓp regression, are known for only the ℓ2 setting, in which they are termed leverage scores. In this work, we provide efficient algorithms for approximating ℓp sensitivities and related summary statistics of a given matrix. In particular, for a given n × d matrix, we compute α-approximation to its ℓ1 sensitivities at the cost of O(n/α) sensitivity computations. For estimating the total ℓp sensitivity (i.e. the sum of ℓp sensitivities), we provide an algorithm based on importance sampling of ℓp Lewis weights, which computes a constant factor approximation to the total sensitivity at the cost of roughly O(√d) sensitivity computations. Furthermore, we estimate the maximum ℓ1 sensitivity, up to a √d factor, using O(d) sensitivity computations. We generalize all these results to ℓp norms for p > 1. Lastly, we experimentally show that for a wide class of matrices in real-world datasets, the total sensitivity can be quickly approximated and is significantly smaller than the theoretical prediction, demonstrating that real-world datasets have low intrinsic effective dimensionality.