# On Coresets for Logistic Regression

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

## Key facts

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

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

- [Deep Learning on a Data Diet: Finding Important Examples Early in Training](https://mlsanity.com/paper/2107.07075/) (2021)
- [From Quantity to Quality: Boosting LLM Performance with Self-Guided Data Selection for Instruction Tuning](https://mlsanity.com/paper/2308.12032/) (2023)
- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [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)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning](https://mlsanity.com/paper/2305.18424/) (2023)
- [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)
- [NLU on Data Diets: Dynamic Data Subset Selection for NLP Classification Tasks](https://mlsanity.com/paper/2306.03208/) (2023)
- [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)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Data pruning and neural scaling laws: fundamental limitations of score-based algorithms](https://mlsanity.com/paper/2302.06960/) (2023)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [Federated Wasserstein Distance](https://mlsanity.com/paper/2310.01973/) (2023)
- [A Novel Sequential Coreset Method for Gradient Descent Algorithms](https://mlsanity.com/paper/2112.02504/) (2021)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [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)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)

## Abstract (arXiv)

Coresets are one of the central methods to facilitate the analysis of large data sets. We continue a recent line of research applying the theory of coresets to logistic regression. First, we show a negative result, namely, that no strongly sublinear sized coresets exist for logistic regression. To deal with intractable worst-case instances we introduce a complexity measure μ(X), which quantifies the hardness of compressing a data set for logistic regression. μ(X) has an intuitive statistical interpretation that may be of independent interest. For data sets with bounded μ(X)-complexity, we show that a novel sensitivity sampling scheme produces the first provably sublinear (1±varepsilon)-coreset. We illustrate the performance of our method by comparing to uniform sampling as well as to state of the art methods in the area. The experiments are conducted on real world benchmark data for logistic regression.