mlsanityData to 14 Oct 2026

Efficient List-Decodable Regression using Batches

arXiv 2211.12743 ↗First posted 23 Nov 2022cs.LG cs.IT math.ITcited by 5

Not on the map. Why?

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.

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

54 of 84 references.

References · 54

  1. 2021A Field Guide to Federated Optimizationcited by 315
  2. 2017Certified Defenses for Data Poisoning Attackscited by 303
  3. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  4. 2016Agnostic Estimation of Mean and Covariancecited by 131
  5. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 125
  6. 2016Learning from Untrusted Datacited by 90
  7. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  8. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  9. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  10. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  11. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  12. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
38 more
  1. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
  2. 2020Meta-learning for mixed linear regressioncited by 44
  3. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  4. 2019List-Decodable Linear Regressioncited by 42
  5. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  6. 2020Robust Meta-learning for Mixed Linear Regression with Small Batchescited by 41
  7. 2015Robust Regression via Hard Thresholdingcited by 39
  8. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  9. 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
  10. 2019List Decodable Learning via Sum of Squarescited by 37
  11. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  12. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  13. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 32
  14. 2019Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimatorcited by 31
  15. 2018High Dimensional Robust Sparse Regressioncited by 29
  16. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  17. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  18. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  19. 2016Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimizationcited by 26
  20. 2019Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Momentscited by 26
  21. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  22. 2019Adaptive Hard Thresholding for Near-optimal Consistent Robust Regressioncited by 23
  23. 2013Spectral Experts for Estimating Mixtures of Linear Regressionscited by 22
  24. 2017Robust Regression via Mutivariate Regression Depthcited by 20
  25. 2020List Decodable Mean Estimation in Nearly Linear Timecited by 20
  26. 2020List-Decodable Mean Estimation via Iterative Multi-Filteringcited by 18
  27. 2020List-Decodable Mean Estimation in Nearly-PCA Timecited by 17
  28. 2016Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Predictioncited by 15
  29. 2020Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problemscited by 15
  30. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  31. 2022Learning Mixtures of Linear Dynamical Systemscited by 15
  32. 2017Learning Discrete Distributions from Untrusted Batchescited by 14
  33. 2020On the Sample Complexity of Adversarial Multi-Source PAC Learningcited by 11
  34. 2019Optimal Robust Learning of Discrete Distributions from Batchescited by 10
  35. 2022On Learning Mixture of Linear Regressions in the Non-Realizable Settingcited by 10
  36. 2020Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Timecited by 9
  37. 2020Learning Structured Distributions From Untrusted Batches: Faster and Simplercited by 8
  38. 2020A General Method for Robust Learning from Batchescited by 8

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 2.

5 papers.

  1. 2023Linear Regression using Heterogeneous Data Batchescited by 3
  2. 2024Collaborative Learning with Different Labeling Functionscited by 2
  3. 2023A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Normcited by 1
  4. 2025Batch List-Decodable Linear Regression via Higher Momentscited by 0
  5. 2025List-Decodable Regression via Expander Sketchingcited by 0