mlsanityData to 7 Oct 2026

Most Neural Networks Are Almost Learnable

arXiv 2305.16508 ↗First posted 25 May 2023cs.LG stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

We present a PTAS for learning random constant-depth networks. We show that for any fixed ε>0 and depth i, there is a poly-time algorithm that for any distribution on √d · mathbbSd-1 learns random Xavier networks of depth i, up to an additive error of ε. The algorithm runs in time and sample complexity of (bard)^poly(ε-1), where bar d is the size of the network. For some cases of sigmoid and ReLU-like activations the bound can be improved to (bard)^polylog(ε-1), resulting in a quasi-poly-time algorithm for learning constant depth random networks.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 28 of its 35 references that are in the map. First posted on arXiv 25 May 2023.

Builds on

28 of 35 references.

References · 28

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  2. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  3. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  4. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  5. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  6. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  7. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  8. 2020Learning Parities with Neural Networkscited by 77
  9. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  10. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  11. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  12. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
16 more
  1. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  2. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  3. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  4. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  5. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  6. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  7. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  8. 2014Complexity theoretic limitations on learning DNF'scited by 21
  9. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  10. 2015ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Timecited by 16
  11. 2020A Deep Conditioning Treatment of Neural Networkscited by 15
  12. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
  13. 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
  14. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  15. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  16. 2019On the Learnability of Deep Random Networkscited by 4

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024On the hardness of learning under symmetriescited by 13
  2. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11