mlsanityData to 7 Oct 2026

Training Neural Networks is NP-Hard in Fixed Dimension

arXiv 2303.17045 ↗First posted 29 Mar 2023cs.CC cs.DS cs.LGcited by 23

Not on the map. Why?

Abstract (arXiv)

We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times in recent years, several questions are still open. We answer questions by Arora et al. [ICLR '18] and Khalife and Basu [IPCO '22] showing that both problems are NP-hard for two dimensions, which excludes any polynomial-time algorithm for constant dimension. We also answer a question by Froese et al. [JAIR '22] proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training error. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 12 of its 23 references that are in the map. First posted on arXiv 29 Mar 2023.

Builds on

12 of 23 references.

References · 12

  1. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  2. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 96
  3. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 55
  4. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  5. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  6. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  7. 2018Complexity of Training ReLU Neural Networkcited by 23
  8. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  9. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  10. 2021On minimal representations of shallow ReLU networkscited by 13
  11. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  12. 2021ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computationcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 7; 2026: 12.

23 papers.

Sort:

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  3. 2025Enabling Local Neural Operators to perform Equation-Free System-Level Analysiscited by 10
  4. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  5. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  6. 2025Parameterized Hardness of Zonotope Containment and Neural Network Verificationcited by 4
  7. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2
  8. 2024Complexity of Injectivity and Verification of ReLU Neural Networkscited by 2
  9. 2026New Complexity-Theoretic Frontiers of Tractability for Neural Network Trainingcited by 2
  10. 2025Equation-Free Coarse Control of Distributed Parameter Systems via Local Neural Operatorscited by 1
  11. 2026NanoQuant: Efficient Sub-1-Bit Quantization of Large Language Modelscited by 1
  12. 2026Online Realizable Regression and Applications for ReLU Networkscited by 1
11 more
  1. 2026Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspectivecited by 1
  2. 2025Invariant Manifolds of Discrete-time Dynamical Systems with Nonlinear Exosystems via Hybrid Physics-Informed Neural Networkscited by 0
  3. 2025Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regressioncited by 0
  4. 2026Knowledge-Informed Kernel State Reconstruction from Heterogeneous Partial Observationscited by 0
  5. 2026Why ReLU? A Bit-Model Dichotomy for Deep Network Trainingcited by 0
  6. 2026Stability and Bifurcation Analysis of Nonlinear PDEs via Random Projection-based PINNs: A Krylov-Arnoldi Approachcited by 0
  7. 2026Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functionscited by 0
  8. 2026Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Lossescited by 0
  9. 2026How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?cited by 0
  10. 2026Parameterized Complexity of Lp-Lipschitz Constants for Input Convex Neural Networks and Lp-Norm Maximization over Zonotopescited by 0
  11. 2026Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensionscited by 0