Research map / Learning theory and algorithms / Prediction and decision losses
A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a leverage-score sampling-and-rescaling algorithm for logistic regression that provably approximates the full-data MLE's estimated probabilities and misclassification discrepancy with O(d/ε²) sampled rows.
Problem
Logistic regression on tall data (n ≫ d) is expensive, and obtaining labels for all observations may be costly; the paper asks whether a subsampled MLE can accurately approximate the full-data estimated probabilities and with what sample size.
Approach
Reduces the accuracy analysis to two structural conditions on a sampling sketch S satisfied by randomized matrix multiplication; with leverage-score sampling, the subsampled MLE's estimated probabilities satisfy a bound relative to the full-data residual norm, with sample size O(d/ε²) independent of the complexity measure μ_y(X).
Key results
- Leverage-score sampling of O(d/ε²) rows gives a theoretical bound ||p(β̂)-p(β*)||₂ ≤ ε||y-p(β*)||₂, improving sample complexity over prior coreset bounds that scale with μ_y(X)².
- On the cardiovascular dataset, leverage-score sampling (red) consistently outperforms L2S and uniform sampling in relative error of estimated probabilities; on the other two datasets, all three methods have very close errors, with uniform and L2S marginally better in general.
- Misclassification rates of leverage-score sampling are lower than or very close to the full-data model for moderate sample sizes on two datasets; the authors describe the empirical evidence as preliminary proof-of-concept.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use row leverage-score sampling instead of L2S or uniform sampling | Sketched logistic regression · Cardiovascular disease | relative error of estimated probabilities | Helped |
| Use row leverage-score sampling instead of L2S or uniform sampling | Sketched logistic regression · Bank customer churn prediction | relative error of estimated probabilities | Mixed |
| Use row leverage-score sampling instead of L2S or uniform sampling | Sketched logistic regression · Default of credit card clients | relative error of estimated probabilities | Mixed |
| Increase the sample size | Sketched logistic regression with leverage-score, L2S, or uniform sampling · All three real-world datasets | relative error of estimated probabilities | Helped |
| Use leverage-score sampling instead of uniform sampling | Sketched logistic regression · Cardiovascular disease | misclassification rate | Helped |
| Use leverage-score sampling instead of L2S | Sketched logistic regression · Cardiovascular disease | misclassification rate | Hurt |
| Use leverage-score sampling instead of L2S or uniform sampling | Sketched logistic regression · Default of credit card clients | misclassification rate | Mixed |
| Use leverage-score sampling, L2S, or uniform sampling with increasing sample sizes | Sketched logistic regression · Bank customer churn prediction | misclassification rate | Helped |
| Use leverage-score sampling instead of uniform sampling | Sketched logistic regression · All three real-world datasets | relative error of subsampled negative log-likelihood | Helped |
| Use leverage-score sampling instead of L2S at larger sample sizes | Sketched logistic regression · All three real-world datasets | relative error of subsampled negative log-likelihood | Helped |
| Use leverage-score sampling instead of L2S or uniform sampling | Sketched logistic regression · Cardiovascular disease | relative error of full-data negative log-likelihood | Helped |
| Use leverage-score sampling instead of L2S | Sketched logistic regression · Bank customer churn prediction and Default of credit card clients | relative error of full-data negative log-likelihood | Mixed |
Surprising findings
- On two of three datasets, uniform sampling and L2S slightly outperform leverage-score sampling in estimated-probability error, despite the theoretical advantage of leverage scores.
Limitations
- Experiments are described by the authors as preliminary proof-of-concept, with only three tabular datasets.
- Theory treats IRLS solver as a black box; errors from the solver are not analyzed.
- Analysis is restricted to the n ≫ d regime; the high-dimensional n ≪ d case is not covered.
Experimental setup
Datasets: Cardiovascular disease dataset (70,000x12) Bank customer churn prediction dataset (10,000x10) Default of credit card clients dataset (30,000x24)
Benchmarks: Cardiovascular disease dataset Bank customer churn prediction dataset Default of credit card clients dataset
Metrics: relative error of estimated probabilities misclassification rate relative error of full-data negative log-likelihood relative error of subsampled negative log-likelihood
Baselines: uniform sampling L2S full-data logistic regression
Builds on: IRLS randomized matrix multiplication L2S (Mai et al. 2021) leverage score sampling
Closest papers by meaning
- The Impact of Regularization on High-dimensional Logistic Regression (NeurIPS 2019 · similarity 0.87)
- A Conditional Randomization Test for Sparse Logistic Regression in High-Dimension (NeurIPS 2022 · similarity 0.87)
- Understanding Randomization in Greedy Model Search (NeurIPS 2026 · similarity 0.86)
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.85)
- One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently (NeurIPS 2024 · similarity 0.85)
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.