# New Frameworks for Offline and Streaming Coreset Constructions

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2016.

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

- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)
- [DataS^3: Dataset Subset Selection for Specialization](https://mlsanity.com/paper/2504.16277/) (2025)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [Performance analysis of coreset selection for quantum implementation of K-Means clustering algorithm](https://mlsanity.com/paper/2206.07852/) (2022)
- [A Coreset Learning Reality Check](https://mlsanity.com/paper/2301.06163/) (2023)
- [On the Size and Approximation Error of Distilled Sets](https://mlsanity.com/paper/2305.14113/) (2023)
- [A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering](https://mlsanity.com/paper/2102.04050/) (2021)
- [A Batch-to-Online Transformation under Random-Order Model](https://mlsanity.com/paper/2306.07163/) (2023)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Efficient Test-Time Finetuning of LLMs via Convex Reconstruction and Gradient Caching](https://mlsanity.com/paper/2605.30337/) (2026)
- [Provable Pruning for Efficient 3D Gaussian Splatting via Coresets](https://mlsanity.com/paper/2607.02721/) (2026)
- [Simple Weak Coresets for Non-Decomposable Classification Measures](https://mlsanity.com/paper/2312.09885/) (2023)
- [Data subsampling for Poisson regression with pth-root-link](https://mlsanity.com/paper/2410.22872/) (2024)
- [Communication-efficient k-Means for Edge-based Machine Learning](https://mlsanity.com/paper/2102.04282/) (2021)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)
- [On the Interplay of Subset Selection and Informed Graph Neural Networks](https://mlsanity.com/paper/2306.10066/) (2023)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)

## Abstract (arXiv)

A coreset for a set of points is a small subset of weighted points that approximately preserves important properties of the original set. Specifically, if P is a set of points, Q is a set of queries, and f:P× Q→ℝ is a cost function, then a set Ssubseteq P with weights w:P→[0,∞) is an ε-coreset for some parameter ε>0 if sums∈ Sw(s)f(s,q) is a (1+ε) multiplicative approximation to sump∈ Pf(p,q) for all q∈ Q. Coresets are used to solve fundamental problems in machine learning under various big data models of computation. Many of the suggested coresets in the recent decade used, or could have used a general framework for constructing coresets whose size depends quadratically on what is known as total sensitivity t. In this paper we improve this bound from O(t2) to O(tlog t). Thus our results imply more space efficient solutions to a number of problems, including projective clustering, k-line clustering, and subspace approximation. Moreover, we generalize the notion of sensitivity sampling for sup-sampling that supports non-multiplicative approximations, negative cost functions and more. The main technical result is a generic reduction to the sample complexity of learning a class of functions with bounded VC dimension. We show that obtaining an (nu,α)-sample for this class of functions with appropriate parameters nu and α suffices to achieve space efficient ε-coresets. Our result implies more efficient coreset constructions for a number of interesting problems in machine learning; we show applications to k-median/k-means, k-line clustering, j-subspace approximation, and the integer (j,k)-projective clustering problem.