The maximum of five numbers with two hidden ReLU layers (Bakaev–Brunck–Hertrich–Stade–Yehudayoff) #
A ReLU network with two hidden layers computes max(x₁,…,x₅) exactly: max(x₁,…,x₅) = M(x), where
M is half of an explicit signed sum of nine nested maxima (Bakaev, Brunck, Hertrich, Stade and
Yehudayoff, arXiv:2505.14338, Claim 4 and Proposition 3). This refutes for n = 5 the conjecture of
Hertrich, Basu, Di Summa and Skutella that the maximum of n numbers needs ⌈log₂ n⌉ hidden layers
(here 3). Rep n k is the class of functions ℝⁿ → ℝ computed with k hidden layers; it is closed
under affine combinations, and max f g = f + ReLU(g − f) raises the depth by one.
Main results #
ReLUDepth.max_eq_M: Claim 4: max of five numbers = MReLUDepth.max5_two_hidden_layers: MAX5 is computed with two hidden ReLU layers
References #
- E. Bakaev, F. Brunck, C. Hertrich, J. Stade, A. Yehudayoff, «Better neural network expressivity: subdividing the simplex», arXiv:2505.14338 v3 (2026), ec. (2), Claim 4, Prop. 3.
Functions ℝⁿ → ℝ computable by a ReLU network with k hidden layers.
Equations
Instances For
The function M of equation (2): half of P₁+P₂+P₃+P₄+Q−R₁₃−R₁₄−R₂₃−R₂₄, each term written as in the paper
(nested maxima, the form a two-hidden-layer network computes).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Case analysis: which coordinate is maximal (the paper reduces the four cases to one by symmetry).