Shallower ReLU Network Representations via Exact Linear Algebra

Abstract

We prove that the maximum of $n$ real numbers is exactly representable by a ReLU network with two hidden layers for every $n\le 10$. The constructions are obtained by reducing the problem to exact rational linear algebra: after a symmetry reduction, the necessary cancellations are encoded in finite linear systems over $\mathbb{Q}$, which we solve and verify computationally. The representation of ${\max }_{10}$ has a structured first hidden layer consisting only of pairwise maxima, a feature that allows it to be recursively substituted into larger networks. We use this to show that for every $n>10$, the maximum ${\max }_n$ can be exactly represented with $\lceil {\log }_5(n/2)\rceil +1<{\log }_5(n)+1.5694$ hidden layers. Via the generalized hinging-hyperplane representation [Wang, Sun, IEEE Trans. Inf. Theory 2005], the same depth bound holds for all continuous piecewise-linear functions on ${\mathbb{R}}^d$, with $d+1$ in place of $n$. In particular, every continuous piecewise-linear function on ${\mathbb{R}}^d$ for $d\le 9$ admits a two-hidden-layer ReLU representation. Our results improve on [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. In that work, the authors established a two-hidden-layer representation for ${\max }_5$ and an upper bound of $\lceil {\log }_3(n-2)\rceil +1$ hidden layers for ${\max }_n$.