# On the Hardness of Learning One Hidden Layer Neural Networks

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

## Key facts

- Cited by 1 papers 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 (most cited first, 21 of 21)

- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [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)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)
- [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)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Indistinguishability Obfuscation from Well-Founded Assumptions](https://mlsanity.com/paper/2008.09317/) (2020)
- [Robustly Learning Single-Index Models via Alignment Sharpness](https://mlsanity.com/paper/2402.17756/) (2024)
- [High Dimensional Linear Regression using Lattice Basis Reduction](https://mlsanity.com/paper/1803.06716/) (2018)
- [Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection](https://mlsanity.com/paper/1910.10890/) (2019)

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

- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)

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