mlsanityData to 7 Oct 2026

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks

arXiv 2006.12476 ↗First posted 22 Jun 2020cs.LG cs.DS math.STcited by 49

Not on the map. Why?

Abstract (arXiv)

We study the problem of PAC learning one-hidden-layer ReLU networks with k hidden units on ℝd under Gaussian marginals in the presence of additive label noise. For the case of positive coefficients, we give the first polynomial-time algorithm for this learning problem for k up to tildeO(√log d). Previously, no polynomial time algorithm was known, even for k=3. This answers an open question posed by~citeKliv17. Importantly, our algorithm does not require any assumptions about the rank of the weight matrix and its complexity is independent of its condition number. On the negative side, for the more general task of PAC learning one-hidden-layer ReLU networks with arbitrary real coefficients, we prove a Statistical Query lower bound of dOmega(k). Thus, we provide a separation between the two classes in terms of efficient learnability. Our upper and lower bounds are general, extending to broader families of activation functions.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 10; 2023: 9; 2024: 12; 2025: 5; 2026: 1.

49 papers.

Sort:

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  3. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  4. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  5. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  6. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  7. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  8. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  9. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  10. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  11. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  12. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
37 more
  1. 2024Provably learning a multi-head attention layercited by 21
  2. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  3. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  4. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  5. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  6. 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
  7. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  8. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  9. 2022Learning a Single Neuron for Non-monotonic Activation Functionscited by 13
  10. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  11. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  12. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  13. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  14. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 8
  15. 2023A faster and simpler algorithm for learning shallow networkscited by 7
  16. 2023Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Productscited by 7
  17. 2021Efficiently Learning Any One Hidden Layer ReLU Network From Queriescited by 6
  18. 2022An Information-Theoretic Framework for Supervised Learningcited by 6
  19. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  20. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  21. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  22. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  23. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 5
  24. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4
  25. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  26. 2023SQ Lower Bounds for Learning Mixtures of Linear Classifierscited by 4
  27. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  28. 2024Cryptographic Hardness of Score Estimationcited by 3
  29. 2022Is Stochastic Gradient Descent Near Optimal?cited by 2
  30. 2023Most Neural Networks Are Almost Learnablecited by 2
  31. 2025Learning and Testing Convex Functionscited by 2
  32. 2024On the Hardness of Learning One Hidden Layer Neural Networkscited by 1
  33. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 1
  34. 2025Provably Extracting the Features from a General Superpositioncited by 1
  35. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 1
  36. 2021Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networkscited by 0
  37. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0