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

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 \mathbb{R}$-complete - a complexity class believed to be harder than NP, characterizing 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 (ERM-bit), 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 activation function: for deep networks with any polynomial activation with rational coefficients and degree at least $2$, deciding ERM-bit is #P-hard, determining the sign of a single partial derivative is unlikely to be in BPP, and deciding a specific bit in the gradient is #P-hard. In contrast, for piecewise-linear activations such as ReLU, precision requirements remain manageable: ERM-bit is in NP, indeed NP-complete, and standard backpropagation runs in polynomial time, showing that finite-precision constraints are not merely implementation details but fundamental determinants of learnability.

Many theoretical results about neural-network training assume an idealized world where computers can store real numbers with infinite precision. This makes the mathematics cleaner, but it does not match real training systems, where every number is stored using only finitely many bits. We study how this finite-precision constraint changes the computational difficulty of training neural networks. Our main finding is that the answer depends sharply on the activation function, the rule that determines how each neuron transforms its input. For networks with polynomial activations of degree at least two, finite-precision training remains computationally intractable: even deciding whether good parameters exist, or extracting certain information from the training gradients, can encode extremely hard counting problems. By contrast, for piecewise-linear activations such as ReLU, finite precision behaves much more benignly: the relevant numbers can be represented with only polynomially many bits, and standard procedures such as backpropagation can be carried out efficiently. This shows that the numerical model is not just an implementation detail. It can change the complexity landscape of neural-network training and separate activation functions that look similar in idealized mathematical models but behave very differently on real computers.