mlsanityData to 7 Oct 2026

Why ReLU? A Bit-Model Dichotomy for Deep Network Training

arXiv 2602.19017 ↗First posted 22 Feb 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Theoretical analyses of Empirical Risk Minimization (ERM) are standardly framed within the Real-RAM model of computation. In this setting, training even simple neural networks is known to be exists ℝ-complete -- a complexity class believed to be harder than NP, that characterizes the difficulty of solving systems of polynomial inequalities over the real numbers. However, this algebraic framework diverges from the reality of digital computation with finite-precision hardware. In this work, we analyze the theoretical complexity of ERM under a realistic bit-level model (mathsfERMbit), where network parameters and inputs are constrained to be rational numbers with polynomially bounded bit-lengths. Under this model, we reveal a sharp dichotomy in tractability governed by the network's activation function. We prove that for deep networks with em any polynomial activations with rational coefficients and degree at least 2, the bit-complexity of training is severe: deciding mathsfERMbit is #P-Hard, hence believed to be strictly harder than NP-complete problems. Furthermore, we show that determining the sign of a single partial derivative of the empirical loss function is intractable (unlikely in BPP), and deciding a specific bit in the gradient is #P-Hard. This provides a complexity-theoretic perspective for the phenomenon of exploding and vanishing gradients. In contrast, we show that for piecewise-linear activations such as ReLU, the precision requirements remain manageable: mathsfERMbit is contained within NP (specifically NP-complete), and standard backpropagation runs in polynomial time. Our results demonstrate that finite-precision constraints are not merely implementation details but fundamental determinants of learnability.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 31 of its 62 references that are in the map. First posted on arXiv 22 Feb 2026.

Builds on

31 of 62 references.

References · 31

  1. 2017Mixed Precision Trainingcited by 1,135
  2. 2016XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networkscited by 829
  3. 2015BinaryConnect: Training Deep Neural Networks with binary weights during propagationscited by 571
  4. 2023LLM-QAT: Data-Free Quantization Aware Training for Large Language Modelscited by 320
  5. 2018Model compression via distillation and quantizationcited by 287
  6. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  7. 2019A Study of BFLOAT16 for Deep Learning Trainingcited by 227
  8. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  9. 2022Overcoming Oscillations in Quantization-Aware Trainingcited by 116
  10. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  11. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 96
  12. 2020Degree-Quant: Quantization-Aware Training for Graph Neural Networkscited by 93
19 more
  1. 2014On the Computational Efficiency of Training Neural Networkscited by 71
  2. 2022A Comprehensive Survey on Model Quantization for Deep Neural Networks in Image Classificationcited by 64
  3. 2020Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functionscited by 50
  4. 2020Convex Geometry and Duality of Over-parameterized Neural Networkscited by 49
  5. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  6. 2022Optimal Clipping and Magnitude-aware Differentiation for Improved Quantization-aware Trainingcited by 26
  7. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  8. 2018Complexity of Training ReLU Neural Networkcited by 23
  9. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  10. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  11. 2020Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learningcited by 18
  12. 2017On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networkscited by 16
  13. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  14. 2021Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Timecited by 14
  15. 2021Neural networks with linear threshold activations: structure and algorithmscited by 12
  16. 2017Multi-output Polynomial Networks and Factorization Machinescited by 8
  17. 2024The Existential Theory of the Reals as a Complexity Class: A Compendiumcited by 4
  18. 2023Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functionscited by 3
  19. 2024On the Hardness of Training Deep Neural Networks Discretelycited by 2

Built on by

Not cited yet.