# Learning Deep ReLU Networks Is Fixed-Parameter Tractable

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2020.

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

- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis](https://mlsanity.com/paper/2206.12802/) (2022)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [DeepMed: Semiparametric Causal Mediation Analysis with Debiased Deep Learning](https://mlsanity.com/paper/2210.04389/) (2022)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [Efficiently Learning Any One Hidden Layer ReLU Network From Queries](https://mlsanity.com/paper/2111.04727/) (2021)
- [Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs](https://mlsanity.com/paper/2201.07206/) (2022)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Gradient dynamics for low-rank fine-tuning beyond kernels](https://mlsanity.com/paper/2411.15385/) (2024)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Operator theory, kernels, and Feedforward Neural Networks](https://mlsanity.com/paper/2301.01327/) (2023)
- [Most Neural Networks Are Almost Learnable](https://mlsanity.com/paper/2305.16508/) (2023)
- [Tight Certified Robustness via Min-Max Representations of ReLU Neural Networks](https://mlsanity.com/paper/2310.04916/) (2023)
- [On the Hardness of Learning One Hidden Layer Neural Networks](https://mlsanity.com/paper/2410.03477/) (2024)

## Abstract (arXiv)

We consider the problem of learning an unknown ReLU network with respect to Gaussian inputs and obtain the first nontrivial results for networks of depth more than two. We give an algorithm whose running time is a fixed polynomial in the ambient dimension and some (exponentially large) function of only the network's parameters. Our bounds depend on the number of hidden units, depth, spectral norm of the weight matrices, and Lipschitz constant of the overall network (we show that some dependence on the Lipschitz constant is necessary). We also give a bound that is doubly exponential in the size of the network but is independent of spectral norm. These results provably cannot be obtained using gradient-based methods and give the first example of a class of efficiently learnable neural networks that gradient descent will fail to learn. In contrast, prior work for learning networks of depth three or higher requires exponential time in the ambient dimension, even when the above parameters are bounded by a constant. Additionally, all prior work for the depth-two case requires well-conditioned weights and/or positive coefficients to obtain efficient run-times. Our algorithm does not require these assumptions. Our main technical tool is a type of filtered PCA that can be used to iteratively recover an approximate basis for the subspace spanned by the hidden units in the first layer. Our analysis leverages new structural results on lattice polynomials from tropical geometry.