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

Ilan Doron-Arad; Elchanan Mossel

cs.LGFeb 22, 2026

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

Authors: Ilan Doron-Arad, Elchanan Mossel

Organizations: MIT, Cambridge, MA, USA

Abstract

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, 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 ( $\mathsf{ERM}_{\text{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 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 $\mathsf{ERM}_{\text{bit}}$ 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: $\mathsf{ERM}_{\text{bit}}$ 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.

Figures & tables

Figure 1: Illustration of Depth-dependent gradient growth for polynomial vs. ReLU activations. We plot

\log_{10}\|\nabla_{W_{1}}L\|_{2}

versus depth for randomly initialized MLPs with

\sigma(x)=x^{2}

or ReLU, where in both cases weights are scaled by a factor of 3 on every layer. Gradients increase with depth for both activations, but much faster for the polynomial one, qualitatively reflecting our bit-complexity separation. This experiment is illustrative rather than a formal bound.

Setting	Real-valued ERM	$\mathsf{ERM}_{\text{bit}}$
Shallow ERM	$\notin\textnormal{NP}^{\ast\ast}$	NP-complete
Deep ERM, poly $\sigma$	$\cdot$	$\notin\textnormal{NP}^{\ast}$
Deep ERM, pw-linear $\sigma$	$\notin\textnormal{NP}^{\ast\ast}$	NP-complete
Backprop-Sign, poly $\sigma$	in P	$\notin\textnormal{BPP}^{\ast\ast\ast}$
Backprop / sign, pw-linear $\sigma$	$\cdot$	in P

Table 1: Main complexity comparisons between the classical real-valued ERM formulation and the bit-bounded

\mathsf{ERM}_{\text{bit}}

formulation. “poly

\sigma

” / “pw-linear

\sigma

” denote fixed polynomial / piecewise-linear (ReLU-type) activations; The entry

\notin\textnormal{NP}^{\ast\ast}

indicates hardness via the existential theory of the reals (

\exists\mathbb{R}

), so NP membership is unknown and believed unlikely for real-valued ERM. The entry marked ∗ assumes that the polynomial hierarchy (PH) does not collapse

\textnormal{PH}\not\subseteq\Delta^{P}_{2}

, and ∗∗∗ assume the constructive univariate radical conjecture and

\textnormal{NP}\not\subseteq\textnormal{BPP}

Panel of Figure 2 — Figure 2: Proof roadmap: SLP based hardness is embedded into deep networks via a fixed polynomial activation $\sigma$ , yielding conditional lower bounds for $\mathsf{ERM}_{\text{bit}}$ and Backprop-Sign; piecewise-linear activations admit NP verification and polynomial-time exact backprop in the bit model.

Panel of Figure 3 — Figure 3: Multiplication gadget using a fixed polynomial activation $\sigma\in\mathbb{Q}[T]$ . For each integer shift $j=0,\dots,{\mu}$ , the network forms three affine combinations $x+y+j$ , $x+j$ , and $y+j$ , applies $\sigma$ , and then takes a fixed linear combination with coefficients $\lambda_{j}\in\mathbb{Q}$ (indicated by the “linear combination” node).

Empirical Risk Minimization

Empirical risk minimization (ERM) fits predictors by minimizing average loss on observed data, balancing data fit, generalization, and computation.

See all 44 papers

Jul 23, 2026

New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of

1

, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

Cornelius Brand, Robert Ganian, Mathis Rocton

Algorithms & Complexity Group Vienna University of Technology Favoritenstraße 9-11, 1040 Vienna, Austria

ReLU Neural Networks Neural Network Optimization Deep Linear Networks

Ask PDF

Aug 24, 2026

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all

k\geq2

, we construct a globally

[0,1]

-valued,

1

-Lipschitz function realized by a depth-

(k+1)

network of width

\mathcal{O}(d^4)

, whereas any depth-

k

network with unrestricted weights and width at most

\frac{2^d}{2d(k-1)}

has squared

L_2

error at least

1/24

under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least

3

. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case

k=2

gives a compactly supported separation between depths

3

and

2

with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally

[0,1]

-valued and

\mathcal{O}(\sqrt d)

-Lipschitz and maps the unit hypercube onto

[0,1]

. It is computed by a polynomial-width depth-

4

network, whereas any depth-

3

network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.

Itay Safran

Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev

Shallow Neural Networks ReLU Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Ask PDF

Feb 12, 2026

Rational Neural Networks have Expressivity Advantages

We study neural networks with trainable low-degree rational activation functions and show that they are more expressive and parameter-efficient than modern piecewise-linear and smooth activations such as ELU, LeakyReLU, LogSigmoid, PReLU, ReLU, SELU, CELU, Sigmoid, SiLU, Mish, Softplus, Tanh, Softmin, Softmax, and LogSoftmax. For an error target of

\varepsilon>0

, we establish approximation-theoretic separations: Any network built from standard fixed activations can be uniformly approximated on compact domains by a rational-activation network with only

\mathrm{poly}(\log\log(1/\varepsilon))

overhead in size, while the converse provably requires

Ω(\log(1/\varepsilon))

parameters in the worst case. This exponential gap persists at the level of full networks and extends to gated activations and transformer-style nonlinearities. In practice, rational activations integrate seamlessly into standard architectures and training pipelines, allowing rationals to match or outperform fixed activations under identical architectures and optimizers.

Maosen Tang, Alex Townsend

Center for Applied Mathematics, Cornell University, United States · Department of Mathematics, Cornell University, United States

Neural Network Activation Functions Neural Network Approximation Theory Neural Network Expressivity

Ask PDF

Abstract

Empirical Risk Minimization

Explore similar work

New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

Every Layer Counts: An Exponential L2L_2L2​ Depth Hierarchy for ReLU Networks

Rational Neural Networks have Expressivity Advantages

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks