mlsanityData to 7 Oct 2026

No Dimensional Sampling Coresets for Classification

arXiv 2402.05280 ↗First posted 7 Feb 2024cs.LG cs.CGcited by 4

Not on the map. Why?

Abstract (arXiv)

We refine and generalize what is known about coresets for classification problems via the sensitivity sampling framework. Such coresets seek the smallest possible subsets of input data, so one can optimize a loss function on the coreset and ensure approximation guarantees with respect to the original data. Our analysis provides the first no dimensional coresets, so the size does not depend on the dimension. Moreover, our results are general, apply for distributional input and can use iid samples, so provide sample complexity bounds, and work for a variety of loss functions. A key tool we develop is a Radamacher complexity version of the main sensitivity sampling approach, which can be of independent interest.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 22 of its 64 references that are in the map. First posted on arXiv 7 Feb 2024.

Builds on

22 of 64 references.

References · 22

  1. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  2. 2017Practical Coreset Constructions for Machine Learningcited by 75
  3. 2018On Coresets for Logistic Regressioncited by 65
  4. 2016Coresets and Sketchescited by 63
  5. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  6. 2019Data-Independent Neural Pruning via Coresetscited by 35
  7. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
  8. 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
  9. 2019Discrepancy, Coresets, and Sketches in Machine Learningcited by 30
  10. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  11. 2015Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filteringcited by 22
  12. 2018varepsilon-Coresets for Clustering (with Outliers) in Doubling Metricscited by 19
10 more
  1. 2021Oblivious sketching for logistic regressioncited by 18
  2. 2018Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and morecited by 14
  3. 2019Dimensionality Reduction for Tukey Regressioncited by 12
  4. 2017Improved Coresets for Kernel Density Estimatescited by 8
  5. 2020Optimal Coreset for Gaussian Kernel Density Estimationcited by 6
  6. 2019Improved Algorithms for Time Decay Streamscited by 5
  7. 2024A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluationscited by 5
  8. 2017Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphscited by 4
  9. 2021Approximate Maximum Halfspace Discrepancycited by 3
  10. 2013Geometric Inference on Kernel Density Estimatescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Distributionally Robust Coreset Selection under Covariate Shiftcited by 1
  2. 2026Hardness of High-Dimensional Linear Classificationcited by 1
  3. 2025Monotone Classification with Relative Approximationscited by 0
  4. 2026Dimension Reduction for Curves: Simplified and Generalizedcited by 0