# Efficient List-Decodable Regression using Batches

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 84 references that are in the map.
- First posted on arXiv 23 Nov 2022.

## Builds on (most cited first, 30 of 54)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [Robust Meta-learning for Mixed Linear Regression with Small Batches](https://mlsanity.com/paper/2006.09702/) (2020)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Learning Mixtures of Linear Regressions with Nearly Optimal Complexity](https://mlsanity.com/paper/1802.07895/) (2018)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)

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

- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm](https://mlsanity.com/paper/2305.00966/) (2023)
- [Batch List-Decodable Linear Regression via Higher Moments](https://mlsanity.com/paper/2503.09802/) (2025)
- [List-Decodable Regression via Expander Sketching](https://mlsanity.com/paper/2511.22524/) (2025)

## Abstract (arXiv)

We begin the study of list-decodable linear regression using batches. In this setting only an α ∈ (0,1] fraction of the batches are genuine. Each genuine batch contains ≥ n i.i.d. samples from a common unknown distribution and the remaining batches may contain arbitrary or even adversarial samples. We derive a polynomial time algorithm that for any n≥ tilde Omega(1/α) returns a list of size mathcal O(1/α2) such that one of the items in the list is close to the true regression parameter. The algorithm requires only tildeO(d/α2) genuine batches and works under fairly general assumptions on the distribution. The results demonstrate the utility of batch structure, which allows for the first polynomial time algorithm for list-decodable regression, which may be impossible for the non-batch setting, as suggested by a recent SQ lower bound citediakonikolas2021statistical for the non-batch setting.