mlsanityData to 7 Oct 2026

Statistical-Query Lower Bounds via Functional Gradients

arXiv 2006.15812 ↗First posted 29 Jun 2020cs.LG cs.DS stat.MLcited by 50

Not on the map. Why?

Abstract (arXiv)

We give the first statistical-query lower bounds for agnostically learning any non-polynomial activation with respect to Gaussian marginals (e.g., ReLU, sigmoid, sign). For the specific problem of ReLU regression (equivalently, agnostically learning a ReLU), we show that any statistical-query algorithm with tolerance n-(1/ε)b must use at least 2nc ε queries for some constant b, c > 0, where n is the dimension and ε is the accuracy parameter. Our results rule out general (as opposed to correlational) SQ learning algorithms, which is unusual for real-valued learning problems. Our techniques involve a gradient boosting procedure for "amplifying" recent lower bounds due to Diakonikolas et al. (COLT 2020) and Goel et al. (ICML 2020) on the SQ dimension of functions computed by two-layer neural networks. The crucial new ingredient is the use of a nonstandard convex functional during the boosting procedure. This also yields a best-possible reduction between two commonly studied models of learning: agnostic learning and probabilistic concepts.

Key facts. Cited by 50 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 8; 2023: 12; 2024: 12; 2025: 5; 2026: 5.

50 papers.

Sort:

  1. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  2. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  3. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  4. 2022Testing distributional assumptions of learning algorithmscited by 30
  5. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  6. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  7. 2022A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexitycited by 27
  8. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  9. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  10. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  11. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  12. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
38 more
  1. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  2. 2023An Efficient Tester-Learner for Halfspacescited by 18
  3. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  4. 2023Statistical Indistinguishability of Learning Algorithmscited by 17
  5. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  6. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  7. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  8. 2024Replicable Learning of Large-Margin Halfspacescited by 12
  9. 2021ReLU Regression with Massart Noisecited by 10
  10. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  11. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  12. 2024Model Stealing for Any Low-Rank Language Modelcited by 9
  13. 2024On the Computational Landscape of Replicable Learningcited by 7
  14. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  15. 2024Learning Neural Networks with Sparse Activationscited by 6
  16. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  17. 2022Learning ReLU networks to high uniform accuracy is intractablecited by 5
  18. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  19. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  20. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  21. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  22. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
  23. 2022Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designscited by 2
  24. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  25. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  26. 2025Learning and Testing Convex Functionscited by 2
  27. 2021Learning stochastic decision treescited by 1
  28. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  29. 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
  30. 2024Reliable Learning of Halfspaces under Gaussian Marginalscited by 1
  31. 2025Provably Extracting the Features from a General Superpositioncited by 1
  32. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1
  33. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  34. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  35. 2026Robust Learning of a Group DRO Neuroncited by 0
  36. 2026A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspacescited by 0
  37. 2026Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginalscited by 0
  38. 2026Efficient Robust Learning at the Information-Theoretic Limitcited by 0