# Discrepancy, Coresets, and Sketches in Machine Learning

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2019.

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

- [How to Train Data-Efficient LLMs](https://mlsanity.com/paper/2402.09668/) (2024)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Learnware: Small Models Do Big](https://mlsanity.com/paper/2210.03647/) (2022)
- [FisherSFT: Data-Efficient Supervised Fine-Tuning of Language Models Using Information Gain](https://mlsanity.com/paper/2505.14826/) (2025)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Sample Constrained Treatment Effect Estimation](https://mlsanity.com/paper/2210.06594/) (2022)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [Diving into Unified Data-Model Sparsity for Class-Imbalanced Graph Representation Learning](https://mlsanity.com/paper/2210.00162/) (2022)
- [Leveraging Importance Weights in Subset Selection](https://mlsanity.com/paper/2301.12052/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [Farzi Data: Autoregressive Data Distillation](https://mlsanity.com/paper/2310.09983/) (2023)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [Sketching Multidimensional Time Series for Fast Discord Mining](https://mlsanity.com/paper/2311.03393/) (2023)
- [Stronger Coreset Bounds for Kernel Density Estimators via Chaining](https://mlsanity.com/paper/2310.08548/) (2023)
- [Solving the Cold Start Problem on One's Own as an End User via Preference Transfer](https://mlsanity.com/paper/2502.12398/) (2025)
- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)
- [Density Sketches for Sampling and Estimation](https://mlsanity.com/paper/2102.12301/) (2021)
- [Dimension-Independent Kernel ε-Covers](https://mlsanity.com/paper/2306.16516/) (2023)
- [Evaluation and Incident Prevention in an Enterprise AI Assistant](https://mlsanity.com/paper/2504.13924/) (2025)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

This paper defines the notion of class discrepancy for families of functions. It shows that low discrepancy classes admit small offline and streaming coresets. We provide general techniques for bounding the class discrepancy of machine learning problems. As corollaries of the general technique we bound the discrepancy (and therefore coreset complexity) of logistic regression, sigmoid activation loss, matrix covariance, kernel density and any analytic function of the dot product or the squared distance. Our results prove the existence of epsilon-approximation O(sqrt{d}/epsilon) sized coresets for the above problems. This resolves the long-standing open problem regarding the coreset complexity of Gaussian kernel density estimation. We provide two more related but independent results. First, an exponential improvement of the widely used merge-and-reduce trick which gives improved streaming sketches for any low discrepancy problem. Second, an extremely simple deterministic algorithm for finding low discrepancy sequences (and therefore coresets) for any positive semi-definite kernel. This paper establishes some explicit connections between class discrepancy, coreset complexity, learnability, and streaming algorithms.