mlsanityData to 7 Oct 2026

Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models

arXiv 2206.04589 ↗First posted 9 Jun 2022cs.DS cs.LG math.STcited by 4

Not on the map. Why?

Abstract (arXiv)

We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions. In particular, we show that no efficient SQ algorithm with access to an ε-corrupted binary product distribution can learn its mean within ℓ2-error o(ε √log(1/ε)). Similarly, we show that no efficient SQ algorithm with access to an ε-corrupted ferromagnetic high-temperature Ising model can learn the model to total variation distance o(ε log(1/ε)). Our SQ lower bounds match the error guarantees of known algorithms for these problems, providing evidence that current upper bounds for these tasks are best possible. At the technical level, we develop a generic SQ lower bound for discrete high-dimensional distributions starting from low dimensional moment matching constructions that we believe will find other applications. Additionally, we introduce new ideas to analyze these moment-matching constructions for discrete univariate distributions.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 22 of its 41 references that are in the map. First posted on arXiv 9 Jun 2022.

Builds on

22 of 41 references.

References · 22

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  4. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  5. 2018Adversarial examples from computational constraintscited by 79
  6. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  7. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  8. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  9. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  10. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  11. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  12. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
10 more
  1. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  2. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  3. 2016A General Characterization of the Statistical Query Complexitycited by 26
  4. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  5. 2014Approximate resilience, monotonicity, and the complexity of agnostic learningcited by 16
  6. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  7. 2017Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methodscited by 8
  8. 2018Non-Gaussian Component Analysis using Entropy Methodscited by 8
  9. 2017Concentration of Multilinear Functions of the Ising Model with Applications to Network Datacited by 5
  10. 2020Learning Ising models from one or multiple samplescited by 3

Built on by

Cited by year (2026 to 7 Oct)

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

4 papers.

  1. 2022SQ Lower Bounds for Learning Single Neurons with Massart Noisecited by 5
  2. 2026Unlearnable phases of mattercited by 2
  3. 2024Distribution Learning Meets Graph Structure Samplingcited by 1
  4. 2026A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspacescited by 0