mlsanityData to 7 Oct 2026

Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent

arXiv 2006.12011 ↗First posted 22 Jun 2020cs.LG cs.DS stat.MLcited by 57

Not on the map. Why?

Abstract (arXiv)

We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent. We show that any classifier trained using gradient descent with respect to square-loss will fail to achieve small test error in polynomial time given access to samples labeled by a one-layer neural network. For classification, we give a stronger result, namely that any statistical query (SQ) algorithm (including gradient descent) will fail to achieve small test error in polynomial time. Prior work held only for gradient descent run with small batch sizes, required sharp activations, and applied to specific classes of queries. Our lower bounds hold for broad classes of activations including ReLU and sigmoid. The core of our result relies on a novel construction of a simple family of neural networks that are exactly orthogonal with respect to all spherically symmetric distributions.

Key facts. Cited by 57 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: 13; 2022: 10; 2023: 10; 2024: 15; 2025: 6; 2026: 3.

57 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. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  4. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  5. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  6. 2021Early-stopped neural networks are consistentcited by 34
  7. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited 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. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  11. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  12. 2023Implicit regularization of deep residual networks towards neural ODEscited by 20
38 more
  1. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  2. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  3. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  4. 2023On Single Index Models beyond Gaussian Datacited 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. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  8. 2024On the hardness of learning under symmetriescited by 13
  9. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  10. 2022DeepMed: Semiparametric Causal Mediation Analysis with Debiased Deep Learningcited by 10
  11. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  12. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  13. 2024Model Stealing for Any Low-Rank Language Modelcited by 9
  14. 2021On the Hardness of PAC-learning Stabilizer States with Noisecited by 8
  15. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  16. 2023A faster and simpler algorithm for learning shallow networkscited 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. 2023Feature Adaptation for Sparse Linear Regressioncited by 6
  20. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  21. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  22. 2022Learning ReLU networks to high uniform accuracy is intractablecited by 5
  23. 2022Global Convergence of SGD On Two Layer Neural Netscited by 5
  24. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  25. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  26. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 5
  27. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  28. 2024How Does Gradient Descent Learn Features -- A Local Analysis for Regularized Two-Layer Neural Networkscited by 4
  29. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  30. 2021Achieving Small Test Error in Mildly Overparameterized Neural Networkscited by 3
  31. 2023Global Convergence of SGD For Logistic Loss on Two Layer Neural Netscited by 3
  32. 2024Cryptographic Hardness of Score Estimationcited by 3
  33. 2025Quantum advantage for learning shallow neural networks with natural data distributionscited by 3
  34. 2022Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designscited by 2
  35. 2022Is Stochastic Gradient Descent Near Optimal?cited by 2
  36. 2023Most Neural Networks Are Almost Learnablecited by 2
  37. 2025On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approachcited by 2
  38. 2025Learning and Testing Convex Functionscited by 2

50 most cited of 57 All 57 (JSON)