mlsanityData to 14 Oct 2026

The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

arXiv 2105.08675 ↗First posted 18 May 2021cs.LG cs.CC cs.DScited by 22

Not on the map. Why?

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.

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

12 of 33 references.

References · 12

  1. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  2. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 98
  3. 2017On Loss Functions for Deep Neural Networks in Classificationcited by 68
  4. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  5. 2020Approximation Schemes for ReLU Regressioncited by 34
  6. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  7. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  8. 2018Robust Fitting in Computer Vision: Easy or Hard?cited by 25
  9. 2018Complexity of Training ReLU Neural Networkcited by 23
  10. 2019Refined Complexity of PCA with Outlierscited by 7
  11. 2013Fixed Parameter Complexity and Approximability of Norm Maximizationcited by 2
  12. 2017Concave losses for robust dictionary learningcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 2; 2023: 3; 2024: 3; 2025: 5; 2026: 6.

22 papers.

Sort:

  1. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  2. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  3. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
  4. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  5. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  6. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  7. 2021Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscited by 14
  8. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  9. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  10. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  11. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  12. 2025Parameterized Hardness of Zonotope Containment and Neural Network Verificationcited by 5
10 more
  1. 2022A Combinatorial Perspective on the Optimization of Shallow ReLU Networkscited by 3
  2. 2024Complexity of Injectivity and Verification of ReLU Neural Networkscited by 2
  3. 2026New Complexity-Theoretic Frontiers of Tractability for Neural Network Trainingcited by 2
  4. 2024Generalizability of Memorization Neural Networkscited by 1
  5. 2026Online Realizable Regression and Applications for ReLU Networkscited by 1
  6. 2025Deep-ICE: the first globally optimal algorithm for minimizing 0-1 loss in two-layer ReLU and maxout networkscited by 0
  7. 2026Why ReLU? A Bit-Model Dichotomy for Deep Network Trainingcited by 0
  8. 2026Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Lossescited by 0
  9. 2026Parameterized Complexity of Lp-Lipschitz Constants for Input Convex Neural Networks and Lp-Norm Maximization over Zonotopescited by 0
  10. 2026Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensionscited by 0