# The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 18 May 2021.

## 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)
- [On Loss Functions for Deep Neural Networks in Classification](https://mlsanity.com/paper/1702.05659/) (2017)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)
- [Learning Deep ReLU Networks Is Fixed-Parameter Tractable](https://mlsanity.com/paper/2009.13512/) (2020)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [Complexity of Training ReLU Neural Network](https://mlsanity.com/paper/1809.10787/) (2018)
- [Refined Complexity of PCA with Outliers](https://mlsanity.com/paper/1905.04124/) (2019)
- [Fixed Parameter Complexity and Approximability of Norm Maximization](https://mlsanity.com/paper/1307.6414/) (2013)
- [Concave losses for robust dictionary learning](https://mlsanity.com/paper/1711.00659/) (2017)

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

- [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)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks](https://mlsanity.com/paper/2110.09548/) (2021)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (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)
- [A Combinatorial Perspective on the Optimization of Shallow ReLU Networks](https://mlsanity.com/paper/2210.00176/) (2022)
- [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)
- [Generalizability of Memorization Neural Networks](https://mlsanity.com/paper/2411.00372/) (2024)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Deep-ICE: the first globally optimal algorithm for minimizing 0-1 loss in two-layer ReLU and maxout networks](https://mlsanity.com/paper/2505.05740/) (2025)
- [Why ReLU? A Bit-Model Dichotomy for Deep Network Training](https://mlsanity.com/paper/2602.19017/) (2026)
- [Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses](https://mlsanity.com/paper/2605.10219/) (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)

Understanding the computational complexity of training simple neural networks with rectified linear units (ReLUs) has recently been a subject of intensive research. Closing gaps and complementing results from the literature, we present several results on the parameterized complexity of training two-layer ReLU networks with respect to various loss functions. After a brief discussion of other parameters, we focus on analyzing the influence of the dimension d of the training data on the computational complexity. We provide running time lower bounds in terms of W[1]-hardness for parameter d and prove that known brute-force strategies are essentially optimal (assuming the Exponential Time Hypothesis). In comparison with previous work, our results hold for a broad(er) range of loss functions, including ℓp-loss for all p∈[0,∞]. In particular, we extend a known polynomial-time algorithm for constant d and convex loss functions to a more general class of loss functions, matching our running time lower bounds also in these cases.