# Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2018.

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

- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (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)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Data subsampling for Poisson regression with pth-root-link](https://mlsanity.com/paper/2410.22872/) (2024)
- [Distributionally Robust Coreset Selection under Covariate Shift](https://mlsanity.com/paper/2501.14253/) (2025)
- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)
- [Monotone Classification with Relative Approximations](https://mlsanity.com/paper/2506.10775/) (2025)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)

## Abstract (arXiv)

Coreset (or core-set) is a small weighted subset Q of an input set P with respect to a given monotonic function f:ℝ→ℝ that provably approximates its fitting loss sump∈ Pf(p· x) to any given x∈ℝd. Using Q we can obtain approximation of x^* that minimizes this loss, by running existing optimization algorithms on Q. In this work we provide: (i) A lower bound which proves that there are sets with no coresets smaller than n=|P| for general monotonic loss functions. (ii) A proof that, under a natural assumption that holds e.g. for logistic regression and the sigmoid activation functions, a small coreset exists for any input P. (iii) A generic coreset construction algorithm that computes such a small coreset Q in O(nd+nlog n) time, and (iv) Experimental results which demonstrate that our coresets are effective and are much smaller in practice than predicted in theory.