mlsanityData to 7 Oct 2026

Coresets for Classification -- Simplified and Strengthened

arXiv 2106.04254 ↗First posted 8 Jun 2021cs.LG cs.DScited by 28

Not on the map. Why?

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.

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

Builds on

22 of 36 references.

References · 22

  1. 2017Compressed Sensing using Generative Modelscited by 337
  2. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  3. 2016Coresets for Scalable Bayesian Logistic Regressioncited by 79
  4. 2017Practical Coreset Constructions for Machine Learningcited by 75
  5. 2018On Coresets for Logistic Regressioncited by 65
  6. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  7. 2020Coresets for Near-Convex Functionscited by 38
  8. 2019Data-Independent Neural Pruning via Coresetscited by 35
  9. 2014Uniform Sampling for Matrix Approximationcited by 31
  10. 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
  11. 2019Discrepancy, Coresets, and Sketches in Machine Learningcited by 30
  12. 2017Optimal Subsampling for Large Sample Logistic Regressioncited by 28
10 more
  1. 2021Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergencecited by 24
  2. 2018Near Optimal Linear Algebra in the Online and Sliding Window Modelscited by 19
  3. 2018Subspace Embedding and Linear Regression with Orlicz Normcited by 19
  4. 2020On Coresets for Support Vector Machinescited by 19
  5. 2018Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and morecited by 14
  6. 2019Dimensionality Reduction for Tukey Regressioncited by 12
  7. 2014ℓp Row Sampling by Lewis Weightscited by 8
  8. 2019On Coresets for Regularized Loss Minimizationcited by 6
  9. 2015Communication Complexity (for Algorithm Designers)cited by 5
  10. 2020Subspace Embeddings Under Nonlinear Transformationscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 7; 2024: 9; 2025: 3; 2026: 2.

28 papers.

Sort:

  1. 2024How to Train Data-Efficient LLMscited by 91
  2. 2022Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptionscited by 20
  3. 2022Online Lewis Weight Samplingcited by 15
  4. 2022Active Learning for Single Neuron Models with Lipschitz Non-Linearitiescited by 12
  5. 2022p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresetscited by 11
  6. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  7. 2022An Empirical Evaluation of k-Means Coresetscited by 7
  8. 2023Optimal Sketching Bounds for Sparse Linear Regressioncited by 6
  9. 2023Improved Active Learning via Dependent Leverage Score Samplingcited by 6
  10. 2024Scalable Learning of Item Response Theory Modelscited by 6
  11. 2024Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuningcited by 5
  12. 2023A Coreset Learning Reality Checkcited by 4
16 more
  1. 2023Leveraging Importance Weights in Subset Selectioncited by 4
  2. 2023Feature Space Sketching for Logistic Regressioncited by 4
  3. 2024Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentationcited by 3
  4. 2024Turnstile ℓp leverage score sampling with applicationscited by 3
  5. 2023Simple Weak Coresets for Non-Decomposable Classification Measurescited by 1
  6. 2024A Provably Accurate Randomized Sampling Algorithm for Logistic Regressioncited by 1
  7. 2024Accurate Coresets for Latent Variable Models and Regularized Regressioncited by 1
  8. 2022Efficient NTK using Dimensionality Reductioncited by 0
  9. 2022Improved Coresets for Euclidean k-Meanscited by 0
  10. 2023Computing Approximate ℓp Sensitivitiescited by 0
  11. 2024The Space Complexity of Approximating Logistic Losscited by 0
  12. 2025Near-Polynomially Competitive Active Logistic Regressioncited by 0
  13. 2025Importance Sampling for Nonlinear Modelscited by 0
  14. 2025Monotone Classification with Relative Approximationscited by 0
  15. 2026Deterministic Coreset for Lp Subspacecited by 0
  16. 2026Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Samplingcited by 0