mlsanityData to 7 Oct 2026

Training Fully Connected Neural Networks is existsℝ-Complete

arXiv 2204.01368 ↗First posted 4 Apr 2022cs.CC cs.LG cs.NEcited by 15

Not on the map. Why?

Abstract (arXiv)

We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalRiskMinimization. Our main result is that the associated decision problem is existsℝ-complete, that is, polynomial-time equivalent to determining whether a multivariate polynomial with integer coefficients has any real roots. Furthermore, we prove that algebraic numbers of arbitrarily large degree are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReLU neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021]. A consequence of this is that a combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] is impossible for networks with more than one output dimension, unless mathsfNP=existsℝ.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 58 of its 127 references that are in the map. First posted on arXiv 4 Apr 2022.

Builds on

58 of 127 references.

References · 58

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  4. 2016Error bounds for approximations with deep ReLU networkscited by 567
  5. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  6. 2018Regularisation of Neural Networks by Enforcing Lipschitz Continuitycited by 311
  7. 2016On the Expressive Power of Deep Neural Networkscited by 302
  8. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  9. 2016Benefits of depth in neural networkscited by 248
  10. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  11. 2019Complexity of Linear Regions in Deep Networkscited by 166
  12. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
38 more
  1. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  2. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 120
  3. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
  4. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  5. 2018Tropical Geometry of Deep Neural Networkscited by 92
  6. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  7. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  8. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  9. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  10. 2021The Modern Mathematics of Deep Learningcited by 63
  11. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  12. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
  13. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 55
  14. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  15. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
  16. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  17. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  18. 2020Approximation Schemes for ReLU Regressioncited by 34
  19. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  20. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  21. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  22. 2018Complexity of Training ReLU Neural Networkcited by 23
  23. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  24. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  25. 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 20
  26. 2018Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regionscited by 17
  27. 2020Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Sizecited by 16
  28. 2018Principled Deep Neural Network Training through Linear Programmingcited by 13
  29. 2021On minimal representations of shallow ReLU networkscited by 13
  30. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  31. 2021ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computationcited by 11
  32. 2019Smoothing the gap between NP and ERcited by 10
  33. 2020Graph Drawing via Gradient Descent, (GD)2cited by 5
  34. 2021On Classifying Continuous Constraint Satisfaction Problemscited by 5
  35. 2021The Complexity of the Hausdorff Distancecited by 5
  36. 2016Intersection Graphs of Rays and Grounded Segmentscited by 4
  37. 2018The Complexity of Drawing a Graph in a Polygonal Regioncited by 4
  38. 2019A Universality Theorem for Nested Polytopescited by 4

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 3; 2025: 3; 2026: 4.

15 papers.

Sort:

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  3. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  4. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  5. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  6. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  7. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  8. 2023Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functionscited by 3
  9. 2024Graph Neural Networks and Arithmetic Circuitscited by 3
  10. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2
  11. 2026New Complexity-Theoretic Frontiers of Tractability for Neural Network Trainingcited by 2
  12. 2024On the Complexity of Identification in Linear Structural Causal Modelscited by 1
3 more
  1. 2026Why ReLU? A Bit-Model Dichotomy for Deep Network Trainingcited by 0
  2. 2026How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?cited by 0
  3. 2026Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensionscited by 0