# Complexity of Training ReLU Neural Network

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2018.

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

- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [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)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Limits of Transformer Language Models on Learning to Compose Algorithms](https://mlsanity.com/paper/2402.05785/) (2024)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions](https://mlsanity.com/paper/2305.11833/) (2023)
- [Multi-Spatio-temporal Fusion Graph Recurrent Network for Traffic forecasting](https://mlsanity.com/paper/2205.01480/) (2022)
- [Towards Theoretical Analysis of Transformation Complexity of ReLU DNNs](https://mlsanity.com/paper/2205.01940/) (2022)
- [Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes](https://mlsanity.com/paper/2311.10972/) (2023)
- [Generative Feature Training of Thin 2-Layer Networks](https://mlsanity.com/paper/2411.06848/) (2024)
- [New Complexity-Theoretic Frontiers of Tractability for Neural Network Training](https://mlsanity.com/paper/2607.20811/) (2026)
- [Tight Mixed-Integer Optimization Formulations for Prescriptive Trees](https://mlsanity.com/paper/2302.14744/) (2023)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Training Neural Networks is existsmathbb R-complete](https://mlsanity.com/paper/2102.09798/) (2021)
- [Review of AlexNet for Medical Image Classification](https://mlsanity.com/paper/2311.08655/) (2023)
- [Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Network](https://mlsanity.com/paper/2508.17783/) (2025)
- [Why ReLU? A Bit-Model Dichotomy for Deep Network Training](https://mlsanity.com/paper/2602.19017/) (2026)
- [Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions](https://mlsanity.com/paper/2609.27932/) (2026)

## Abstract (arXiv)

In this paper, we explore some basic questions on the complexity of training neural networks with ReLU activation function. We show that it is NP-hard to train a two-hidden layer feedforward ReLU neural network. If dimension of the input data and the network topology is fixed, then we show that there exists a polynomial time algorithm for the same training problem. We also show that if sufficient over-parameterization is provided in the first hidden layer of ReLU neural network, then there is a polynomial time algorithm which finds weights such that output of the over-parameterized ReLU neural network matches with the output of the given data.