mlsanityData to 7 Oct 2026

Statistical Query Lower Bounds for List-Decodable Linear Regression

arXiv 2106.09689 ↗First posted 17 Jun 2021cs.DS cs.LG math.STcited by 25

Not on the map. Why?

Abstract (arXiv)

We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set T of labeled examples (x, y) ∈ ℝd × ℝ and a parameter 0< α <1/2 such that an α-fraction of the points in T are i.i.d. samples from a linear regression model with Gaussian covariates, and the remaining (1-α)-fraction of the points are drawn from an arbitrary noise distribution. The goal is to output a small list of hypothesis vectors such that at least one of them is close to the target regression vector. Our main result is a Statistical Query (SQ) lower bound of dpoly(1/α) for this problem. Our SQ lower bound qualitatively matches the performance of previously developed algorithms, providing evidence that current upper bounds for this task are nearly best possible.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 28 of its 70 references that are in the map. First posted on arXiv 17 Jun 2021.

Builds on

28 of 70 references.

References · 28

  1. 2018Spectral Signatures in Backdoor Attackscited by 457
  2. 2017Certified Defenses for Data Poisoning Attackscited by 288
  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 123
  6. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  7. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  8. 2016Learning from Untrusted Datacited by 90
  9. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  10. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  11. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  12. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
16 more
  1. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  2. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  3. 2019List-Decodable Linear Regressioncited by 42
  4. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  5. 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
  6. 2019List Decodable Learning via Sum of Squarescited by 37
  7. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  8. 2019EM Converges for a Mixture of Many Linear Regressionscited by 27
  9. 2016A General Characterization of the Statistical Query Complexitycited by 26
  10. 2019Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Momentscited by 26
  11. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  12. 2020List Decodable Mean Estimation in Nearly Linear Timecited by 20
  13. 2020List-Decodable Mean Estimation via Iterative Multi-Filteringcited by 18
  14. 2020List-Decodable Mean Estimation in Nearly-PCA Timecited by 17
  15. 2016Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Predictioncited by 15
  16. 2020List Decodable Subspace Recoverycited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 3; 2024: 7; 2025: 5; 2026: 2.

25 papers.

Sort:

  1. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  2. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  3. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  4. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  5. 2022List-Decodable Sparse Mean Estimationcited by 11
  6. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  7. 2022List-Decodable Covariance Estimationcited by 8
  8. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  9. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  10. 2022Efficient List-Decodable Regression using Batchescited by 5
  11. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4
  12. 2023Linear Regression using Heterogeneous Data Batchescited by 3
13 more
  1. 2024Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensingcited by 2
  2. 2021Conditional Linear Regression for Heterogeneous Covariancescited by 1
  3. 2023A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Normcited by 1
  4. 2024Robust Mixture Learning when Outliers Overwhelm Small Groupscited by 1
  5. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 1
  6. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  7. 2024Sample-Efficient Linear Regression with Self-Selection Biascited by 0
  8. 2025Batch List-Decodable Linear Regression via Higher Momentscited by 0
  9. 2025Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contaminationcited by 0
  10. 2025High-Accuracy List-Decodable Mean Estimationcited by 0
  11. 2025List-Decodable Regression via Expander Sketchingcited by 0
  12. 2026Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barrierscited by 0
  13. 2026A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspacescited by 0