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

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

## Key facts

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

## Builds on (most cited first, 30 of 31)

- [Mixed Precision Training](https://mlsanity.com/paper/1710.03740/) (2017)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [LLM-QAT: Data-Free Quantization Aware Training for Large Language Models](https://mlsanity.com/paper/2305.17888/) (2023)
- [Model compression via distillation and quantization](https://mlsanity.com/paper/1802.05668/) (2018)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [A Study of BFLOAT16 for Deep Learning Training](https://mlsanity.com/paper/1905.12322/) (2019)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Overcoming Oscillations in Quantization-Aware Training](https://mlsanity.com/paper/2203.11086/) (2022)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Degree-Quant: Quantization-Aware Training for Graph Neural Networks](https://mlsanity.com/paper/2008.05000/) (2020)
- [On the Computational Efficiency of Training Neural Networks](https://mlsanity.com/paper/1410.1141/) (2014)
- [A Comprehensive Survey on Model Quantization for Deep Neural Networks in Image Classification](https://mlsanity.com/paper/2205.07877/) (2022)
- [Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions](https://mlsanity.com/paper/2006.15459/) (2020)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (2020)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Optimal Clipping and Magnitude-aware Differentiation for Improved Quantization-aware Training](https://mlsanity.com/paper/2206.06501/) (2022)
- [Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs](https://mlsanity.com/paper/2110.05518/) (2021)
- [Complexity of Training ReLU Neural Network](https://mlsanity.com/paper/1809.10787/) (2018)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning](https://mlsanity.com/paper/2001.04413/) (2020)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time](https://mlsanity.com/paper/2101.02429/) (2021)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [Multi-output Polynomial Networks and Factorization Machines](https://mlsanity.com/paper/1705.07603/) (2017)
- [Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions](https://mlsanity.com/paper/2305.11833/) (2023)
- [The Existential Theory of the Reals as a Complexity Class: A Compendium](https://mlsanity.com/paper/2407.18006/) (2024)

## 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.