# Training Neural Networks is NP-Hard in Fixed Dimension

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

## Key facts

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

## Builds on (most cited first, 12 of 12)

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Complexity of Training ReLU Neural Network](https://mlsanity.com/paper/1809.10787/) (2018)
- [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)
- [On minimal representations of shallow ReLU networks](https://mlsanity.com/paper/2108.05643/) (2021)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)

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

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Enabling Local Neural Operators to perform Equation-Free System-Level Analysis](https://mlsanity.com/paper/2505.02308/) (2025)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Parameterized Hardness of Zonotope Containment and Neural Network Verification](https://mlsanity.com/paper/2509.22849/) (2025)
- [Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes](https://mlsanity.com/paper/2311.10972/) (2023)
- [Complexity of Injectivity and Verification of ReLU Neural Networks](https://mlsanity.com/paper/2405.19805/) (2024)
- [New Complexity-Theoretic Frontiers of Tractability for Neural Network Training](https://mlsanity.com/paper/2607.20811/) (2026)
- [Equation-Free Coarse Control of Distributed Parameter Systems via Local Neural Operators](https://mlsanity.com/paper/2509.23975/) (2025)
- [NanoQuant: Efficient Sub-1-Bit Quantization of Large Language Models](https://mlsanity.com/paper/2602.06694/) (2026)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)
- [Invariant Manifolds of Discrete-time Dynamical Systems with Nonlinear Exosystems via Hybrid Physics-Informed Neural Networks](https://mlsanity.com/paper/2506.13950/) (2025)
- [Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression](https://mlsanity.com/paper/2508.20616/) (2025)
- [Knowledge-Informed Kernel State Reconstruction from Heterogeneous Partial Observations](https://mlsanity.com/paper/2601.22328/) (2026)
- [Why ReLU? A Bit-Model Dichotomy for Deep Network Training](https://mlsanity.com/paper/2602.19017/) (2026)
- [Stability and Bifurcation Analysis of Nonlinear PDEs via Random Projection-based PINNs: A Krylov-Arnoldi Approach](https://mlsanity.com/paper/2603.21568/) (2026)
- [Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions](https://mlsanity.com/paper/2605.06959/) (2026)
- [Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses](https://mlsanity.com/paper/2605.10219/) (2026)
- [How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?](https://mlsanity.com/paper/2606.01107/) (2026)
- [Parameterized Complexity of Lp-Lipschitz Constants for Input Convex Neural Networks and Lp-Norm Maximization over Zonotopes](https://mlsanity.com/paper/2608.24865/) (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)

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.