# Coresets for Classification -- Simplified and Strengthened

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 8 Jun 2021.

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

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Data-Independent Neural Pruning via Coresets](https://mlsanity.com/paper/1907.04018/) (2019)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Optimal Subsampling for Large Sample Logistic Regression](https://mlsanity.com/paper/1702.01166/) (2017)
- [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)
- [Subspace Embedding and Linear Regression with Orlicz Norm](https://mlsanity.com/paper/1806.06430/) (2018)
- [On Coresets for Support Vector Machines](https://mlsanity.com/paper/2002.06469/) (2020)
- [Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more](https://mlsanity.com/paper/1802.07382/) (2018)
- [Dimensionality Reduction for Tukey Regression](https://mlsanity.com/paper/1905.05376/) (2019)
- [ℓp Row Sampling by Lewis Weights](https://mlsanity.com/paper/1412.0588/) (2014)
- [On Coresets for Regularized Loss Minimization](https://mlsanity.com/paper/1905.10845/) (2019)
- [Communication Complexity (for Algorithm Designers)](https://mlsanity.com/paper/1509.06257/) (2015)
- [Subspace Embeddings Under Nonlinear Transformations](https://mlsanity.com/paper/2010.02264/) (2020)

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

- [How to Train Data-Efficient LLMs](https://mlsanity.com/paper/2402.09668/) (2024)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)
- [A Coreset Learning Reality Check](https://mlsanity.com/paper/2301.06163/) (2023)
- [Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning](https://mlsanity.com/paper/2407.06120/) (2024)
- [Leveraging Importance Weights in Subset Selection](https://mlsanity.com/paper/2301.12052/) (2023)
- [Feature Space Sketching for Logistic Regression](https://mlsanity.com/paper/2303.14284/) (2023)
- [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)
- [Simple Weak Coresets for Non-Decomposable Classification Measures](https://mlsanity.com/paper/2312.09885/) (2023)
- [A Provably Accurate Randomized Sampling Algorithm for Logistic Regression](https://mlsanity.com/paper/2402.16326/) (2024)
- [Accurate Coresets for Latent Variable Models and Regularized Regression](https://mlsanity.com/paper/2412.20189/) (2024)
- [Efficient NTK using Dimensionality Reduction](https://mlsanity.com/paper/2210.04807/) (2022)
- [Improved Coresets for Euclidean k-Means](https://mlsanity.com/paper/2211.08184/) (2022)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [The Space Complexity of Approximating Logistic Loss](https://mlsanity.com/paper/2412.02639/) (2024)
- [Near-Polynomially Competitive Active Logistic Regression](https://mlsanity.com/paper/2503.05981/) (2025)
- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)
- [Monotone Classification with Relative Approximations](https://mlsanity.com/paper/2506.10775/) (2025)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)

## Abstract (arXiv)

We give relative error coresets for training linear classifiers with a broad class of loss functions, including the logistic loss and hinge loss. Our construction achieves (1± ε) relative error with tilde O(d · μy(X)2/ε2) points, where μy(X) is a natural complexity measure of the data matrix X ∈ ℝn × d and label vector y ∈ -1,1n, introduced in by Munteanu et al. 2018. Our result is based on subsampling data points with probabilities proportional to their ℓ1 Lewis weights. It significantly improves on existing theoretical bounds and performs well in practice, outperforming uniform subsampling along with other importance sampling methods. Our sampling distribution does not depend on the labels, so can be used for active learning. It also does not depend on the specific loss function, so a single coreset can be used in multiple training scenarios.