# Coresets for Near-Convex Functions

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

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

- [InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning](https://mlsanity.com/paper/2303.04947/) (2023)
- [Dataset Distillation with Convexified Implicit Gradients](https://mlsanity.com/paper/2302.06755/) (2023)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Dataset Distillation by Automatic Training Trajectories](https://mlsanity.com/paper/2407.14245/) (2024)
- [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)
- [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)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond](https://mlsanity.com/paper/2402.17327/) (2024)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [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)
- [GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning](https://mlsanity.com/paper/2410.13761/) (2024)
- [A Novel Sequential Coreset Method for Gradient Descent Algorithms](https://mlsanity.com/paper/2112.02504/) (2021)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [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)
- [Coresets for Wasserstein Distributionally Robust Optimization Problems](https://mlsanity.com/paper/2210.04260/) (2022)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Exploration](https://mlsanity.com/paper/2312.13385/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [Subsampling Graphs with GNN Performance Guarantees](https://mlsanity.com/paper/2502.16703/) (2025)
- [On the Size and Approximation Error of Distilled Sets](https://mlsanity.com/paper/2305.14113/) (2023)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Provable Pruning for Efficient 3D Gaussian Splatting via Coresets](https://mlsanity.com/paper/2607.02721/) (2026)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Accurate Coresets for Latent Variable Models and Regularized Regression](https://mlsanity.com/paper/2412.20189/) (2024)
- [Distributionally Robust Coreset Selection under Covariate Shift](https://mlsanity.com/paper/2501.14253/) (2025)

## Abstract (arXiv)

Coreset is usually a small weighted subset of n input points in ℝd, that provably approximates their loss function for a given set of queries (models, classifiers, etc.). Coresets become increasingly common in machine learning since existing heuristics or inefficient algorithms may be improved by running them possibly many times on the small coreset that can be maintained for streaming distributed data. Coresets can be obtained by sensitivity (importance) sampling, where its size is proportional to the total sum of sensitivities. Unfortunately, computing the sensitivity of each point is problem dependent and may be harder to compute than the original optimization problem at hand. We suggest a generic framework for computing sensitivities (and thus coresets) for wide family of loss functions which we call near-convex functions. This is by suggesting the f-SVD factorization that generalizes the SVD factorization of matrices to functions. Example applications include coresets that are either new or significantly improves previous results, such as SVM, Logistic regression, M-estimators, and ℓz-regression. Experimental results and open source are also provided.