# Most Neural Networks Are Almost Learnable

arXiv: https://arxiv.org/abs/2305.16508 · HTML: https://mlsanity.com/paper/2305.16508/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Limitations of Lazy Training of Two-layers Neural Networks](https://mlsanity.com/paper/1906.08899/) (2019)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Learning One-hidden-layer ReLU Networks via Gradient Descent](https://mlsanity.com/paper/1806.07808/) (2018)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Learning Deep ReLU Networks Is Fixed-Parameter Tractable](https://mlsanity.com/paper/2009.13512/) (2020)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Learning Two-layer Neural Networks with Symmetric Inputs](https://mlsanity.com/paper/1810.06793/) (2018)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds](https://mlsanity.com/paper/1805.02677/) (2018)
- [ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time](https://mlsanity.com/paper/1510.03528/) (2015)
- [A Deep Conditioning Treatment of Neural Networks](https://mlsanity.com/paper/2002.01523/) (2020)
- [Hardness of Learning Neural Networks with Natural Weights](https://mlsanity.com/paper/2006.03177/) (2020)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [On the Learnability of Deep Random Networks](https://mlsanity.com/paper/1904.03866/) (2019)

## Built on by (most cited first, 2 of 2)

- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)

## 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.