Introduction: The Illusion of Infinite Precision
Standard theoretical analyses of neural networks often rely on the "Real-RAM" model of computation, assuming computers can store and manipulate real numbers with infinite precision. Under this idealized framework, training even a simple neural network is known to be $\exists \mathbb{R}$-complete—a complexity class believed to be strictly harder than NP.
However, this algebraic assumption diverges sharply from the reality of digital computation. Modern hardware, such as GPUs and CPUs, relies on finite-precision arithmetic (e.g., Float32 or BFloat16). To bridge this gap, researchers introduce the ERM-bit model, which restricts network parameters and inputs to rational numbers with polynomially bounded bit-lengths.
By analyzing Empirical Risk Minimization (ERM) through this realistic lens, the authors uncover a fundamental "complexity dichotomy" in deep learning. Their findings provide rigorous theoretical justification for a long-standing empirical trend: why the industry has overwhelmingly converged on piecewise-linear activations like ReLU over smooth polynomial alternatives.
The ERM-bit Model and Theoretical Methodology
To understand how activation functions impact computational hardness under finite precision, the authors employ tools from complexity theory, mapping neural network training onto known intractable problems.
Their methodology hinges on several key theoretical constructs:
- The ERM-bit Framework: A realistic computational model where weights, biases, and inputs are rational numbers. Their bit-lengths are constrained to grow at most polynomially with the problem size.
- Arithmetic Simulation: The authors prove a "multiplication gadget" lemma, demonstrating that any non-linear polynomial activation (degree 2 or higher) can simulate addition, subtraction, and multiplication gates.
- Reduction from Straight Line Programs (SLPs): By reducing problems involving SLPs—sequences of arithmetic operations used to represent massive numbers—to neural network training, they establish a baseline for computational hardness.
- Synthetic Mathematical Datasets: Because this is a theoretical work, the authors do not rely on empirical benchmarks like ImageNet. Instead, they construct synthetic (input, label) pairs designed to force the network's weights to represent specific arithmetic circuits, making the loss dependent on solving hard numerical problems.
The Complexity Dichotomy: Polynomials vs. ReLU
The core contribution of this paper is revealing how the choice of activation function fundamentally alters the tractability of network training when accounting for finite precision.
The "Non-Benign" Gradient Explosion of Polynomials
In standard practice, "exploding gradients" are viewed as a numerical stability nuisance. However, in the bit-model, they represent a deep computational trap. With polynomial activations, bit-lengths grow multiplicatively with network depth. This explosion of "information density" means the gradient doesn't just become large in magnitude; its internal bit-pattern becomes a computationally intractable puzzle.
For deep networks using any polynomial activation with rational coefficients and a degree of at least 2, deciding ERM-bit is #P-hard. Furthermore, determining the sign of a single partial derivative is unlikely to be in BPP, and computing a specific bit in the gradient is #P-hard.
The Tractability of Piecewise-Linear Activations
In stark contrast, piecewise-linear functions like ReLU act as "adders" for bit-complexity. Precision requirements grow only additively (linearly) with depth. This keeps the precision requirements manageable and ensures that standard backpropagation runs in polynomial time.
For ReLU networks, the ERM-bit problem is NP-complete. While still hard in the worst case, a ReLU network's performance can be verified in polynomial time (placing it in NP), whereas verifying a polynomial network is likely impossible for a standard computer.
Summary of Complexity Results
| Setting | Real-valued ERM (Infinite Precision) | ERM-bit (Finite Precision) |
|---|---|---|
| Deep (Polynomial $\sigma$) | $\notin$ NP (Harder) | #P-hard |
| Deep (ReLU/PWL $\sigma$) | $\notin$ NP (Harder) | NP-complete |
| Backprop (Polynomial $\sigma$) | In P | $\notin$ BPP (Intractable) |
| Backprop (ReLU/PWL $\sigma$) | In P | In P (Efficient) |
Note: The paper also highlights a PAC Learning gap, showing that in the bit-model, the number of samples needed to learn a simple class can scale with the precision $q$, whereas in the Real-RAM model, it might appear to be a constant $O(1)$.
Limitations and Future Directions
While this work provides a robust theoretical foundation for the superiority of ReLU in finite-precision environments, it leaves several avenues open for future exploration:
- Smooth Non-Polynomials: The current techniques specifically target polynomials. Functions like Sigmoid or Tanh are often approximated by polynomials via Taylor expansion, but the paper does not formally classify the complexity of exact transcendental functions.
- High-Dimensionality: Some hardness results rely on networks with large input/output dimensions. The authors suggest that adding regularization might allow these results to hold for constant-dimensional inputs, which remains an open question.
- Floating-Point Nuance: The ERM-bit model uses exact rational arithmetic. While a massive step closer to reality than Real-RAM, it does not perfectly capture the specific rounding behaviors and idiosyncrasies of IEEE 754 floating-point standards used in modern hardware.
Ultimately, this research demonstrates that finite-precision constraints are not merely implementation details to be engineered away, but fundamental determinants of neural network learnability.
Summary updated