# A Provably Accurate Randomized Sampling Algorithm for Logistic Regression

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 47 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 19 of 19)

- [Deep Anomaly Detection with Outlier Exposure](https://mlsanity.com/paper/1812.04606/) (2018)
- [Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibration](https://mlsanity.com/paper/1910.12656/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Optimal Subsampling for Large Sample Logistic Regression](https://mlsanity.com/paper/1702.01166/) (2017)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Lectures on Randomized Numerical Linear Algebra](https://mlsanity.com/paper/1712.08880/) (2017)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Logistic Regression for Massive Data with Rare Events](https://mlsanity.com/paper/2006.00683/) (2020)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [More Efficient Estimation for Logistic Regression with Optimal Subsample](https://mlsanity.com/paper/1802.02698/) (2018)
- [Single-Label Multi-Class Image Classification by Deep Logistic Regression](https://mlsanity.com/paper/1811.08400/) (2018)
- [Nonuniform Negative Sampling and Log Odds Correction with Rare Events Data](https://mlsanity.com/paper/2110.13048/) (2021)
- [Feature Space Sketching for Logistic Regression](https://mlsanity.com/paper/2303.14284/) (2023)
- [Randomized Iterative Algorithms for Fisher Discriminant Analysis](https://mlsanity.com/paper/1809.03045/) (2018)
- [Faster Randomized Interior Point Methods for Tall/Wide Linear Programs](https://mlsanity.com/paper/2209.08722/) (2022)
- [On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming](https://mlsanity.com/paper/2202.01756/) (2022)

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

- [Near-Polynomially Competitive Active Logistic Regression](https://mlsanity.com/paper/2503.05981/) (2025)

## Abstract (arXiv)

In statistics and machine learning, logistic regression is a widely-used supervised learning technique primarily employed for binary classification tasks. When the number of observations greatly exceeds the number of predictor variables, we present a simple, randomized sampling-based algorithm for logistic regression problem that guarantees high-quality approximations to both the estimated probabilities and the overall discrepancy of the model. Our analysis builds upon two simple structural conditions that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized numerical linear algebra. We analyze the properties of estimated probabilities of logistic regression when leverage scores are used to sample observations, and prove that accurate approximations can be achieved with a sample whose size is much smaller than the total number of observations. To further validate our theoretical findings, we conduct comprehensive empirical evaluations. Overall, our work sheds light on the potential of using randomized sampling approaches to efficiently approximate the estimated probabilities in logistic regression, offering a practical and computationally efficient solution for large-scale datasets.