mlsanityData to 7 Oct 2026

Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks

arXiv 2202.05258 ↗First posted 10 Feb 2022cs.LG cs.CC stat.MLcited by 27

Not on the map. Why?

Abstract (arXiv)

We give superpolynomial statistical query (SQ) lower bounds for learning two-hidden-layer ReLU networks with respect to Gaussian inputs in the standard (noise-free) model. No general SQ lower bounds were known for learning ReLU networks of any depth in this setting: previous SQ lower bounds held only for adversarial noise models (agnostic learning) or restricted models such as correlational SQ. Prior work hinted at the impossibility of our result: Vempala and Wilmes showed that general SQ lower bounds cannot apply to any real-valued family of functions that satisfies a simple non-degeneracy condition. To circumvent their result, we refine a lifting procedure due to Daniely and Vardi that reduces Boolean PAC learning problems to Gaussian ones. We show how to extend their technique to other learning models and, in many well-studied cases, obtain a more efficient reduction. As such, we also prove new cryptographic hardness results for PAC learning two-hidden-layer ReLU networks, as well as new lower bounds for learning constant-depth ReLU networks from label queries.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 41 of its 86 references that are in the map. First posted on arXiv 10 Feb 2022.

Builds on

41 of 86 references.

References · 41

  1. 2016Practical Black-Box Attacks against Machine Learningcited by 893
  2. 2016Stealing Machine Learning Models via Prediction APIscited by 602
  3. 2019High Accuracy and High Fidelity Extraction of Neural Networkscited by 208
  4. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  5. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  6. 2018Model Reconstruction from Model Explanationscited by 84
  7. 2019Reverse-Engineering Deep ReLU Networkscited by 81
  8. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  9. 2014On the Computational Efficiency of Training Neural Networkscited by 71
  10. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  11. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  12. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
29 more
  1. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  2. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  3. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  4. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  5. 2020Continuous LWEcited by 37
  6. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  7. 2020Approximation Schemes for ReLU Regressioncited by 34
  8. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  9. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  10. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  11. 2016Distribution-Specific Hardness of Learning Neural Networkscited by 27
  12. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  13. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  14. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  15. 2014Complexity theoretic limitations on learning DNF'scited by 21
  16. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  17. 2020Statistical Queries and Statistical Algorithms: Foundations and Applicationscited by 21
  18. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  19. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  20. 2017On the Complexity of Learning Neural Networkscited by 17
  21. 2013From average case complexity to improper learning complexitycited by 16
  22. 2020A Deep Conditioning Treatment of Neural Networkscited by 15
  23. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
  24. 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
  25. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  26. 2021An Exact Poly-Time Membership-Queries Algorithm for Extraction a three-Layer ReLU Networkcited by 11
  27. 2021Size and Depth Separation in Approximating Benign Functions with Neural Networkscited by 7
  28. 2020Span Recovery for Deep Neural Networks with Applications to Input Obfuscationcited by 4
  29. 2016Optimal Key Consensus in Presence of Noisecited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 6; 2024: 11; 2025: 2; 2026: 2.

27 papers.

Sort:

By area:

  1. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  2. 2023Looped Transformers are Better at Learning Learning Algorithmscited by 135
  3. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  4. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  5. 2024Provably learning a multi-head attention layercited by 21
  6. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  7. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  8. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  9. 2024On the hardness of learning under symmetriescited by 13
  10. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  11. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  12. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
15 more
  1. 2024Learning Neural Networks with Sparse Activationscited by 6
  2. 2022Learning ReLU networks to high uniform accuracy is intractablecited by 5
  3. 2022Magnitude and Angle Dynamics in Training Single ReLU Neuronscited by 5
  4. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  5. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 5
  6. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  7. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  8. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  9. 2023Most Neural Networks Are Almost Learnablecited by 2
  10. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2
  11. 2025Learning and Testing Convex Functionscited by 2
  12. 2024On the Hardness of Learning One Hidden Layer Neural Networkscited by 1
  13. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 1
  14. 2024Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantizationcited by 0
  15. 2024Sequencing the Neurome: Towards Scalable Exact Parameter Reconstruction of Black-Box Neural Networkscited by 0