3 The Improved Logarithmic Upper Bound
For nonnegative integers \(a,b\), define \(T_{a,b}:\mathbb {R}^{4a+b}\to \mathbb {R}\) by
Thus \(T_{0,b}=\operatorname {MAX}_b\).
Let \(\mathcal{T}_{a,b}\) be the vector space spanned by all functions of the form \(T_{a,b}\circ L\), where \(L:\mathbb {R}^{4a+b}\to \mathbb {R}^{4a+b}\) is linear.
If \(i=4a+b\), then \(T_{a,b+4}\) can be written as
The first \(4a\) coordinates of \(T_{a,b+4}\) form the same \(a\) paired-sum blocks as in \(T_{a,b}\). The next \(b\) coordinates are the extra arguments of \(T_{a,b}\). The final four coordinates are exactly \(x_{i+1},x_{i+2},x_{i+3},x_{i+4}\). Taking the maximum over the union of these entries is therefore the displayed expression.
In the proof of Claim 5, the four terms corresponding to \(P_1,P_2,P_3,P_4\) lie in \(\mathcal{T}_{a+1,b+1}\).
The term corresponding to \(P_1\) is
Pulling out the factor \(2\) rewrites it as
This is a scalar multiple of \(T_{a+1,b+1}\circ L\) for a linear map \(L\): the new paired-sum block is the pair of binary maxima displayed above, and the extra coordinate is \((x_{i+1}+x_{i+2})/2\), while the old \(T_{a,b}\) block is passed through linearly. Hence it lies in \(\mathcal{T}_{a+1,b+1}\). The same argument with indices permuted proves the assertion for \(P_2,P_3,P_4\).
In the proof of Claim 5, the term corresponding to \(Q\) lies in \(\mathcal{T}_{a,b+2}\), and the terms corresponding to \(R_{13},R_{14},R_{23},R_{24}\) lie in \(\mathcal{T}_{a,b+3}\).
The \(Q\) term is
so it is a scalar multiple of an element of \(\mathcal{T}_{a,b+2}\) after a linear change of coordinates. The \(R_{13}\) term is
so it lies in \(\mathcal{T}_{a,b+3}\). The formulas for \(R_{14},R_{23},R_{24}\) only replace the first displayed average by the corresponding pair average, so the same argument applies.
For all \(a,b\), one has \(\mathcal{T}_{a,b+2}\subseteq \mathcal{T}_{a,b+3}\subseteq \mathcal{T}_{a+1,b+1}\) after ignoring unused last coordinates.
The inclusion \(\mathcal{T}_{a,b+2}\subseteq \mathcal{T}_{a,b+3}\) is obtained by adding one dummy extra coordinate that is never selected. For the second inclusion, use
Thus two extra arguments may be encoded as one paired-sum block, with remaining coordinates passed through and any unused coordinates fixed to zero by the linear map. Since \(\mathcal{T}_{a,b}\) is closed under linear changes of coordinates and finite linear combinations by definition, the inclusions follow.
Viewing \(T_{a,b+4}\) as a function on \(\mathbb {R}^{4a+b+5}\) that ignores the last coordinate, one has \(T_{a,b+4}\in \mathcal{T}_{a+1,b+1}\).
By Lemma 33, \(T_{a,b+4}\) is the maximum of the five quantities \(x_{i+1},x_{i+2},x_{i+3},x_{i+4},T_{a,b}\). Apply the identity \(\operatorname {MAX}_5=M\) from Lemma 29 to these five inputs. The four resulting \(P\) terms lie in \(\mathcal{T}_{a+1,b+1}\) by Lemma 34. The \(Q\) term lies in \(\mathcal{T}_{a,b+2}\) and the four \(R\) terms lie in \(\mathcal{T}_{a,b+3}\) by Lemma 35; Lemma 36 embeds both spaces into \(\mathcal{T}_{a+1,b+1}\). Since \(\mathcal{T}_{a+1,b+1}\) is a vector space, the signed half-sum \(M\) also lies in it. Therefore \(T_{a,b+4}\in \mathcal{T}_{a+1,b+1}\).
If \(T_{3^n-1,2}\) can be computed in depth \(k\), then \(T_{0,3^n+2}\) can also be computed in depth \(k\).
Claim 5 gives inclusions
Starting from \((a,b)=(0,3^n-2)\) and applying this inclusion \(3^n-1\) times gives
Therefore any depth-\(k\) network for \(T_{3^n-1,2}\) yields one for the member \(T_{0,3^n+2}\) of the smaller class.
If \(T_{0,3^{n-1}+2}\) can be computed in depth \(k-1\), then \(T_{3^{n-1},2}\) can be computed in depth \(k\).
In the first hidden layer, compute each of the \(3^{n-1}\) quantities
for \(j=0,\ldots ,3^{n-1}-1\), using Lemma 9 for the two binary maxima and an affine sum. Keep the two extra inputs as affine coordinates. The remaining task is exactly to apply \(T_{0,3^{n-1}+2}\) to the \(3^{n-1}\) computed paired-sum quantities and the two extra inputs. By hypothesis this costs \(k-1\) further hidden layers, so the total depth is \(k\).
For every \(n\ge 1\), \(\operatorname {MAX}_{3^n+2}\in \operatorname {ReLU}_{3^n+2,n+1}\).
The proof is by induction on \(n\). For \(n=1\), the statement is exactly the two-hidden-layer upper bound for \(\operatorname {MAX}_5\) from Proposition 30. For the induction step, assume \(T_{0,3^{n-1}+2}=\operatorname {MAX}_{3^{n-1}+2}\) can be computed with \(n\) hidden layers. By Claim 7, \(T_{3^{n-1},2}\) can be computed with \(n+1\) hidden layers. By Claim 6, \(T_{0,3^n+2}=\operatorname {MAX}_{3^n+2}\) can then also be computed with \(n+1\) hidden layers. This proves the induction.
For every \(m\ge 4\), \(\operatorname {MAX}_m\) can be computed with \(\lceil \log _3(m-2)\rceil +1\) hidden layers.
Let \(r=\lceil \log _3(m-2)\rceil \), so \(m\le 3^r+2\). Apply Theorem 40 to compute \(\operatorname {MAX}_{3^r+2}\) with \(r+1\) hidden layers, and feed the first \(m\) inputs together with \(3^r+2-m\) duplicate copies of one existing input, for instance \(x_1\). Duplicating an input does not change the maximum of the original \(m\) inputs. Thus \(\operatorname {MAX}_m\) has the claimed depth.
For \(n\ge 3\),
The inclusion \(\operatorname {ReLU}_{n,\lceil \log _3(n-1)\rceil +1}\subseteq \operatorname {CPWL}_n\) is Lemma 6. For the reverse inclusion, take \(f\in \operatorname {CPWL}_n\) and write it by Theorem 11 as a signed sum of \(\operatorname {MAX}_{n+1}\) applied to affine maps. Since \(n\ge 3\), one has \(n+1\ge 4\), so Corollary 41 computes each \(\operatorname {MAX}_{n+1}\) term with \(\lceil \log _3((n+1)-2)\rceil +1=\lceil \log _3(n-1)\rceil +1\) hidden layers. Parallelizing the finitely many terms and taking the final signed affine sum preserves this depth. Hence \(f\) lies in the stated ReLU class.
The inductive constructions in Claims 5 and 7 use only linear coefficients obtained by repeated halving and affine copying. Therefore all weights in the resulting networks are fractions whose denominators are powers of two. In particular, they are decimal fractions.
The only nonintegral coefficients introduced in Claim 5 are the displayed factors \(1/2\) used to express pair sums and scaled binary maxima. Claim 7 introduces no new denominators beyond those already used to compute binary maxima and affine sums. Inducting through Theorem 40 shows that every denominator is a power of two. Such rationals have finite decimal expansions after multiplying numerator and denominator by a suitable power of five.
For ReLU networks whose weights are decimal fractions, the maximum function \(\operatorname {MAX}_m\) requires at least \(\lceil \log _3 m\rceil \) hidden layers.
For decimal-fraction ReLU networks, the construction of Corollary 41 is within at most one hidden layer of the lower bound of Averkov–Hojny–Merkert.
Corollary 41 computes \(\operatorname {MAX}_m\) using \(\lceil \log _3(m-2)\rceil +1\) layers and Remark 43 places the weights in the decimal-fraction model. Lemma 44 gives the lower bound \(\lceil \log _3 m\rceil \). Since \(\lceil \log _3(m-2)\rceil \le \lceil \log _3 m\rceil \), the difference between the upper and lower bounds is at most one layer.