# No Dimensional Sampling Coresets for Classification

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

## Key facts

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

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

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [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)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Data-Independent Neural Pruning via Coresets](https://mlsanity.com/paper/1907.04018/) (2019)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [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)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [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)
- [Improved Coresets for Kernel Density Estimates](https://mlsanity.com/paper/1710.04325/) (2017)
- [Optimal Coreset for Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2007.08031/) (2020)
- [Improved Algorithms for Time Decay Streams](https://mlsanity.com/paper/1907.07574/) (2019)
- [A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations](https://mlsanity.com/paper/2401.02562/) (2024)
- [Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs](https://mlsanity.com/paper/1711.03076/) (2017)
- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Geometric Inference on Kernel Density Estimates](https://mlsanity.com/paper/1307.7760/) (2013)

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

- [Distributionally Robust Coreset Selection under Covariate Shift](https://mlsanity.com/paper/2501.14253/) (2025)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Monotone Classification with Relative Approximations](https://mlsanity.com/paper/2506.10775/) (2025)
- [Dimension Reduction for Curves: Simplified and Generalized](https://mlsanity.com/paper/2607.03112/) (2026)

## 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.