2 Computing the Maximum of Five Inputs

Definition 15 Auxiliary term \(P_1\)

For \(x\in \mathbb {R}^5\), define

\[ P_1(x)= \max \big(\max (2x_5,x_1+x_2),\max (x_1,x_3)+\max (x_1,x_4)\big). \]

Equivalently,

\[ P_1(x)=\max (2x_5,x_1+x_2,2x_1,x_1+x_3,x_1+x_4,x_3+x_4). \]

Definition 16 Auxiliary term \(P_2\)

For \(x\in \mathbb {R}^5\), define

\[ P_2(x)= \max \big(\max (2x_5,x_1+x_2),\max (x_2,x_3)+\max (x_2,x_4)\big), \]

equivalently

\[ P_2(x)=\max (2x_5,x_1+x_2,2x_2,x_2+x_3,x_2+x_4,x_3+x_4). \]

Definition 17 Auxiliary term \(P_3\)

For \(x\in \mathbb {R}^5\), define

\[ P_3(x)= \max \big(\max (2x_5,x_3+x_4),\max (x_3,x_1)+\max (x_3,x_2)\big), \]

equivalently

\[ P_3(x)=\max (2x_5,x_3+x_4,2x_3,x_3+x_1,x_3+x_2,x_1+x_2). \]

Definition 18 Auxiliary term \(P_4\)

For \(x\in \mathbb {R}^5\), define

\[ P_4(x)= \max \big(\max (2x_5,x_3+x_4),\max (x_4,x_1)+\max (x_4,x_2)\big), \]

equivalently

\[ P_4(x)=\max (2x_5,x_3+x_4,2x_4,x_4+x_1,x_4+x_2,x_1+x_2). \]

Definition 19 Auxiliary term \(Q\)

For \(x\in \mathbb {R}^5\), define

\[ Q(x)=\max \big(2x_5,\max (x_1+x_2,x_3+x_4)\big) =\max (2x_5,x_1+x_2,x_3+x_4). \]

Definition 20 Auxiliary term \(R_{13}\)

For \(x\in \mathbb {R}^5\), define

\[ R_{13}(x)= \max \big(\max (2x_5,x_1+x_3),\max (x_1+x_2,x_3+x_4)\big). \]

Thus \(R_{13}(x)=\max (2x_5,x_1+x_3,x_1+x_2,x_3+x_4)\).

Definition 21 Auxiliary term \(R_{14}\)

For \(x\in \mathbb {R}^5\), define

\[ R_{14}(x)= \max \big(\max (2x_5,x_1+x_4),\max (x_1+x_2,x_3+x_4)\big). \]

Thus \(R_{14}(x)=\max (2x_5,x_1+x_4,x_1+x_2,x_3+x_4)\).

Definition 22 Auxiliary term \(R_{23}\)

For \(x\in \mathbb {R}^5\), define

\[ R_{23}(x)= \max \big(\max (2x_5,x_2+x_3),\max (x_1+x_2,x_3+x_4)\big). \]

Thus \(R_{23}(x)=\max (2x_5,x_2+x_3,x_1+x_2,x_3+x_4)\).

Definition 23 Auxiliary term \(R_{24}\)

For \(x\in \mathbb {R}^5\), define

\[ R_{24}(x)= \max \big(\max (2x_5,x_2+x_4),\max (x_1+x_2,x_3+x_4)\big). \]

Thus \(R_{24}(x)=\max (2x_5,x_2+x_4,x_1+x_2,x_3+x_4)\).

Definition 24 The two-layer candidate \(M\)

Define \(M:\mathbb {R}^5\to \mathbb {R}\) by

\[ M(x)=\frac12\big(P_1(x)+P_2(x)+P_3(x)+P_4(x)+Q(x) -R_{13}(x)-R_{14}(x)-R_{23}(x)-R_{24}(x)\big). \]

Lemma 25 Two-hidden-layer realizability of the nine terms

Each of \(P_1,P_2,P_3,P_4,Q,R_{13},R_{14},R_{23},R_{24}\) can be computed by a ReLU network with two hidden layers.

Proof ▶

Every displayed term is obtained from affine functions by first computing a finite list of binary maxima and then taking one final binary maximum between affine combinations of the first-layer quantities. For example, \(P_1\) first computes \(\max (2x_5,x_1+x_2)\), \(\max (x_1,x_3)\), and \(\max (x_1,x_4)\), and then computes the maximum of the first quantity and the sum of the latter two. The other eight terms have the same form, with some summands omitted. By Lemma 9, each binary maximum costs one hidden layer, and affine sums are handled by affine maps between layers. Hence each term has depth two.

Lemma 26 Symmetries of \(M\)

The expression \(M\) is invariant under swapping indices \(1\) and \(2\), under swapping indices \(3\) and \(4\), and under simultaneously swapping the pair \((1,2)\) with the pair \((3,4)\).

Proof ▶

Under \(1\leftrightarrow 2\), the terms \(P_1\) and \(P_2\) are exchanged, \(R_{13}\) and \(R_{23}\) are exchanged, and \(R_{14}\) and \(R_{24}\) are exchanged; \(P_3\), \(P_4\), and \(Q\) remain fixed. Under \(3\leftrightarrow 4\), the terms \(P_3\) and \(P_4\) are exchanged, \(R_{13}\) and \(R_{14}\) are exchanged, and \(R_{23}\) and \(R_{24}\) are exchanged; the other terms remain fixed. Under \((1,2)\leftrightarrow (3,4)\), the terms \(P_1\) and \(P_3\) are exchanged, \(P_2\) and \(P_4\) are exchanged, and \(R_{14}\) and \(R_{23}\) are exchanged; the remaining terms are fixed. Since \(M\) is the same signed half-sum of the resulting multiset of terms, \(M\) is invariant under all three operations.

Lemma 27 The case where \(x_5\) is largest

If \(x_5=\operatorname {MAX}_5(x)\), then \(M(x)=x_5\).

Proof ▶

If \(x_5\) is the largest coordinate, then for every pair \(i,j\) one has \(x_i+x_j\le 2x_5\). Inspecting the displayed maxima in the definitions of \(P_1,P_2,P_3,P_4,Q,R_{13},R_{14},R_{23},R_{24}\), each of the nine terms is therefore equal to \(2x_5\). Substitution in Definition 24 gives

\[ M(x)=\frac12(5\cdot 2x_5-4\cdot 2x_5)=x_5. \]

Lemma 28 The normalized case where \(x_1\) is largest

If \(x_1=\operatorname {MAX}_5(x)\), then \(M(x)=x_1\).

Proof ▶

Since \(x_1\) is largest, \(2x_1\) dominates all entries in \(P_1\), so \(P_1(x)=2x_1\). Also \(x_1+x_2\ge 2x_2\) and \(x_1+x_2\ge x_2+x_4\), hence

\[ P_2(x)=\max (2x_5,x_1+x_2,x_2+x_3,x_3+x_4)=R_{23}(x). \]

Similarly, \(x_1+x_3\ge 2x_3\) and \(x_1+x_3\ge x_2+x_3\), so

\[ P_3(x)=\max (2x_5,x_3+x_4,x_1+x_3,x_1+x_2)=R_{13}(x). \]

Likewise \(x_1+x_4\ge 2x_4\) and \(x_1+x_4\ge x_2+x_4\), giving

\[ P_4(x)=\max (2x_5,x_3+x_4,x_1+x_4,x_1+x_2)=R_{14}(x). \]

Finally \(x_1+x_2\ge x_2+x_4\), so

\[ R_{24}(x)=\max (2x_5,x_1+x_2,x_3+x_4)=Q(x). \]

In the signed half-sum defining \(M\), the equal pairs \(P_2=R_{23}\), \(P_3=R_{13}\), \(P_4=R_{14}\), and \(Q=R_{24}\) cancel. Therefore \(M(x)=\frac12P_1(x)=x_1\).

Lemma 29 Claim 4: identity \(\operatorname {MAX}_5=M\)

For every \(x\in \mathbb {R}^5\), \(\operatorname {MAX}_5(x)=M(x)\).

Proof ▶

If \(x_5\) is a largest coordinate, Lemma 27 applies. Otherwise some coordinate among \(x_1,x_2,x_3,x_4\) is largest. By the symmetries of Lemma 26, the four cases with a largest coordinate in \(\{ 1,2,3,4\} \) reduce to the case \(x_1=\operatorname {MAX}_5(x)\), which is Lemma 28. Hence \(M\) agrees with \(\operatorname {MAX}_5\) on all inputs.

Proposition 30 Proposition 3: exact depth of \(\operatorname {MAX}_5\)

The minimum number of hidden layers needed to compute \(\operatorname {MAX}_5\) is exactly two.

Proof ▶

The upper bound follows because each of the nine terms in Definition 24 is computable with two hidden layers by Lemma 25, and \(M\) is an affine combination of those terms. By Lemma 29, this computes \(\operatorname {MAX}_5\). For the lower bound, if \(\operatorname {MAX}_5\) had a one-hidden-layer representation, then restricting to the affine subspace \((x_1,x_2,x_3,x_4,x_5)=(y_1,y_2,y_3,c,c)\) with \(c\) smaller than all relevant \(y_i\) on each translated test region would give a one-hidden-layer representation of \(\operatorname {MAX}_3\). This contradicts Lemma 14. Therefore one hidden layer does not suffice, while two do.