mlsanityData to 7 Oct 2026

Complexity of Training ReLU Neural Network

arXiv 1809.10787 ↗First posted 27 Sep 2018cs.CC cs.LGcited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 3; 2023: 7; 2024: 3; 2025: 1; 2026: 4.

23 papers.

Sort:

  1. 2021Theory of overparametrization in quantum neural networkscited by 100
  2. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 55
  3. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  4. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  5. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  6. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  7. 2024Limits of Transformer Language Models on Learning to Compose Algorithmscited by 13
  8. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  9. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  10. 2023The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Modelscited by 7
  11. 2023Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functionscited by 3
  12. 2022Multi-Spatio-temporal Fusion Graph Recurrent Network for Traffic forecastingcited by 2
11 more
  1. 2022Towards Theoretical Analysis of Transformation Complexity of ReLU DNNscited by 2
  2. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2
  3. 2024Generative Feature Training of Thin 2-Layer Networkscited by 2
  4. 2026New Complexity-Theoretic Frontiers of Tractability for Neural Network Trainingcited by 2
  5. 2023Tight Mixed-Integer Optimization Formulations for Prescriptive Treescited by 1
  6. 2026Online Realizable Regression and Applications for ReLU Networkscited by 1
  7. 2021Training Neural Networks is existsmathbb R-completecited by 0
  8. 2023Review of AlexNet for Medical Image Classificationcited by 0
  9. 2025Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Networkcited by 0
  10. 2026Why ReLU? A Bit-Model Dichotomy for Deep Network Trainingcited by 0
  11. 2026Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensionscited by 0