# Online Lewis Weight Sampling

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 17 Jul 2022.

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

- [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)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [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)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [The Adversarial Robustness of Sampling](https://mlsanity.com/paper/1906.11327/) (2019)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Majorizing Measures, Sequential Complexities, and Online Learning](https://mlsanity.com/paper/2102.01729/) (2021)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Dimensionality Reduction for Tukey Regression](https://mlsanity.com/paper/1905.05376/) (2019)
- [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)
- [Improved Iteration Complexities for Overconstrained p-Norm Regression](https://mlsanity.com/paper/2111.01848/) (2021)
- [Online Active Regression](https://mlsanity.com/paper/2207.05945/) (2022)
- [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)
- [Tight Bounds for ℓp Oblivious Subspace Embeddings](https://mlsanity.com/paper/1801.04414/) (2018)
- [Tight Bounds for the Subspace Sketch Problem with Applications](https://mlsanity.com/paper/1904.05543/) (2019)
- [Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches](https://mlsanity.com/paper/2110.15533/) (2021)
- [Nearly Linear Row Sampling Algorithm for Quantile Regression](https://mlsanity.com/paper/2006.08397/) (2020)

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

- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models](https://mlsanity.com/paper/2405.14121/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)
- [Accurate Coresets for Latent Variable Models and Regularized Regression](https://mlsanity.com/paper/2412.20189/) (2024)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)
- [The Space Complexity of Approximating Logistic Loss](https://mlsanity.com/paper/2412.02639/) (2024)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)

## Abstract (arXiv)

The seminal work of Cohen and Peng introduced Lewis weight sampling to the theoretical computer science community, yielding fast row sampling algorithms for approximating d-dimensional subspaces of ℓp up to (1+ε) error. Several works have extended this important primitive to other settings, including the online coreset and sliding window models. However, these results are only for p∈1,2, and results for p=1 require a suboptimal tilde O(d2/ε2) samples. In this work, we design the first nearly optimal ℓp subspace embeddings for all p∈(0,∞) in the online coreset and sliding window models. In both models, our algorithms store tilde O(d1lor(p/2)/ε2) rows. This answers a substantial generalization of the main open question of [BDMMUWZ2020], and gives the first results for all pnotin1,2. Towards our result, we give the first analysis of "one-shot'' Lewis weight sampling of sampling rows proportionally to their Lewis weights, with sample complexity tilde O(dp/2/ε2) for p>2. Previously, this scheme was only known to have sample complexity tilde O(dp/2/ε5), whereas tilde O(dp/2/ε2) is known if a more sophisticated recursive sampling is used. The recursive sampling cannot be implemented online, thus necessitating an analysis of one-shot Lewis weight sampling. Our analysis uses a novel connection to online numerical linear algebra. As an application, we obtain the first one-pass streaming coreset algorithms for (1+ε) approximation of important generalized linear models, such as logistic regression and p-probit regression. Our upper bounds are parameterized by a complexity parameter μ introduced by [MSSW2018], and we show the first lower bounds showing that a linear dependence on μ is necessary.