On the Hardness of Learning One Hidden Layer Neural Networks
Not on the map. Why?
Abstract (arXiv)
In this work, we consider the problem of learning one hidden layer ReLU neural networks with inputs from ℝd. We show that this learning problem is hard under standard cryptographic assumptions even when: (1) the size of the neural network is polynomial in d, (2) its input distribution is a standard Gaussian, and (3) the noise is Gaussian and polynomially small in d. Our hardness result is based on the hardness of the Continuous Learning with Errors (CLWE) problem, and in particular, is based on the largely believed worst-case hardness of approximately solving the shortest vector problem up to a multiplicative polynomial factor.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 21 of its 29 references that are in the map. First posted on arXiv 4 Oct 2024.
Builds on
21 of 29 references.
References · 21
- 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
- 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
- 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
- 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
- 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
- 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
- 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
- 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
- 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
- 2020Continuous LWEcited by 37
- 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
- 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
9 more
- 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
- 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
- 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
- 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
- 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
- 2020Indistinguishability Obfuscation from Well-Founded Assumptionscited by 12
- 2024Robustly Learning Single-Index Models via Alignment Sharpnesscited by 11
- 2018High Dimensional Linear Regression using Lattice Basis Reductioncited by 5
- 2019Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detectioncited by 5
Built on by
Citing papers per year: 2024: 1.
1 paper.