2 The maximum of five numbers with two hidden layers

This chapter contains the paper’s key finite-dimensional identity (Claim 4): an explicit function \(M\), built from nine two-hidden-layer terms, equals \(\mathrm{MAX}_5\). This disproves the depth conjecture of Hertrich, Basu, Di Summa, and Skutella already for five inputs.

Definition 18 The term \(P_1\)

Define \(P_1 \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 19 The term \(P_2\)

Define \(P_2 \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 20 The term \(P_3\)

Define \(P_3 \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 21 The term \(P_4\)

Define \(P_4 \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 22 The term \(Q\)

Define \(Q \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 23 The term \(R_{13}\)

Define \(R_{13} \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 24 The term \(R_{14}\)

Define \(R_{14} \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 25 The term \(R_{23}\)

Define \(R_{23} \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 26 The term \(R_{24}\)

Define \(R_{24} \colon \mathbb {R}^5 \to \mathbb {R}\) by

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

Definition 27 The function \(M\)

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

\[ M(x) = \tfrac 12\bigl(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)\bigr). \]

Lemma 28 Distributing sums over maxima

For all real numbers \(a, b, c, d\),

\[ \max (a, b) + \max (c, d) = \max (a + c,\ a + d,\ b + c,\ b + d). \]

Proof ▶

Each of the four sums on the right is at most the left-hand side, so the right-hand side is at most the left-hand side. Conversely, \(\max (a,b) = a\) or \(b\) and \(\max (c,d) = c\) or \(d\), so the left-hand side equals one of the four sums.

Lemma 29 Flattened form of \(P_1\)

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

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

Proof ▶

By Lemma 28, \(\max (x_1,x_3) + \max (x_1,x_4) = \max (2x_1,\ x_1{+}x_4,\ x_3{+}x_1,\ x_3{+}x_4)\); combining with \(\max (2x_5, x_1{+}x_2)\) under the outer maximum and using associativity of \(\max \) gives the claim.

Lemma 30 Flattened form of \(P_2\)

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

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

Proof ▶

As for Lemma 29, expanding \(\max (x_2,x_3) + \max (x_2,x_4)\) with Lemma 28.

Lemma 31 Flattened form of \(P_3\)

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

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

Proof ▶

As for Lemma 29, expanding \(\max (x_3,x_1) + \max (x_3,x_2)\) with Lemma 28.

Lemma 32 Flattened form of \(P_4\)

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

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

Proof ▶

As for Lemma 29, expanding \(\max (x_4,x_1) + \max (x_4,x_2)\) with Lemma 28.

Lemma 33 Two-layer shape lemma

Let \(d \ge 1\) and let \(g_1, \dots , g_6 \colon \mathbb {R}^d \to \mathbb {R}\) be affine. Then the function

\[ x \mapsto \max \bigl(\max (g_1(x), g_2(x)), \max (g_3(x), g_4(x)) + \max (g_5(x), g_6(x))\bigr) \]

lies in \(\mathrm{ReLU}_{d,2}\).

Proof ▶

By Lemma 12 and Lemma 10, each of \(u = \max (g_1, g_2)\), \(\max (g_3, g_4)\) and \(\max (g_5, g_6)\) lies in \(\mathrm{ReLU}_{d,1}\), and by Lemma 9 so does \(v = \max (g_3,g_4) + \max (g_5,g_6)\). Finally \(\max (u, v) = \mathrm{MAX}_2(u, v)\) lies in \(\mathrm{ReLU}_{d,2}\) by Lemma 11 applied with \(\mathrm{MAX}_2 \in \mathrm{ReLU}_{2,1}\).

Lemma 34 Maxima of up to four affine functions

Let \(d \ge 1\), let \(1 \le r \le 4\) and let \(g_1, \dots , g_r \colon \mathbb {R}^d \to \mathbb {R}\) be affine. Then \(x \mapsto \max (g_1(x), \dots , g_r(x))\) lies in \(\mathrm{ReLU}_{d,2}\).

Proof ▶

By Lemma 13, \(\mathrm{MAX}_4 \in \mathrm{ReLU}_{4,2}\). Precompose (Lemma 10) with the affine map \(x \mapsto (g_1(x), \dots , g_r(x), g_r(x), \dots , g_r(x))\) that pads by repeating \(g_r\). For \(r \le 2\) one may alternatively use Lemmas 12 and 8.

Lemma 35 \(M\) has a two-hidden-layer network

\(M \in \mathrm{ReLU}_{5,2}\).

Proof ▶

Each of \(P_1, P_2, P_3, P_4\) is of the shape of Lemma 33 with affine arguments (\(g_1 = 2x_5\), etc.), hence lies in \(\mathrm{ReLU}_{5,2}\). Each of \(Q, R_{13}, R_{14}, R_{23}, R_{24}\) is a maximum of at most four affine functions, hence lies in \(\mathrm{ReLU}_{5,2}\) by Lemma 34. By Lemma 9 the linear combination \(M\) of these nine functions lies in \(\mathrm{ReLU}_{5,2}\).

Lemma 36 Symmetry of \(M\) under swapping \(x_1\) and \(x_2\)

For all \(x \in \mathbb {R}^5\), \(M(x_2, x_1, x_3, x_4, x_5) = M(x_1, x_2, x_3, x_4, x_5)\).

Proof ▶

Substituting \((x_2, x_1, x_3, x_4, x_5)\) into the defining formulas interchanges \(P_1 \leftrightarrow P_2\), \(R_{13} \leftrightarrow R_{23}\) and \(R_{14} \leftrightarrow R_{24}\), and fixes \(P_3\), \(P_4\) and \(Q\) (their formulas involve \(x_1, x_2\) only through \(x_1 + x_2\) or through \(\max (x_\cdot , x_1) + \max (x_\cdot , x_2)\), both symmetric). The defining combination of \(M\) is invariant under these exchanges.

Lemma 37 Symmetry of \(M\) under swapping \(x_3\) and \(x_4\)

For all \(x \in \mathbb {R}^5\), \(M(x_1, x_2, x_4, x_3, x_5) = M(x_1, x_2, x_3, x_4, x_5)\).

Proof ▶

The substitution interchanges \(P_3 \leftrightarrow P_4\), \(R_{13} \leftrightarrow R_{14}\) and \(R_{23} \leftrightarrow R_{24}\), and fixes \(P_1\), \(P_2\) and \(Q\), exactly as in Lemma 36. The combination defining \(M\) is invariant.

Lemma 38 Symmetry of \(M\) under swapping the pairs

For all \(x \in \mathbb {R}^5\), \(M(x_3, x_4, x_1, x_2, x_5) = M(x_1, x_2, x_3, x_4, x_5)\).

Proof ▶

Substituting \((x_3, x_4, x_1, x_2, x_5)\) interchanges \(P_1 \leftrightarrow P_3\), \(P_2 \leftrightarrow P_4\) and \(R_{14} \leftrightarrow R_{23}\), and fixes \(Q\), \(R_{13}\) and \(R_{24}\) (for instance \(R_{13}\) becomes \(\max (2x_5, x_3{+}x_1, x_3{+}x_4, x_1{+}x_2) = R_{13}(x)\)). The combination defining \(M\) is invariant.

Lemma 39 Value of \(M\) when \(x_5\) is maximal

Let \(x \in \mathbb {R}^5\) with \(x_5 \ge x_i\) for \(i = 1, \dots , 4\). Then \(M(x) = x_5\).

Proof ▶

Every entry of each of the nine flattened maxima is of the form \(x_i + x_j\) with \(i, j \in \{ 1, \dots , 5\} \) (reading \(2x_i\) as \(x_i + x_i\)), hence is at most \(2x_5\); since \(2x_5\) itself appears in each list, all nine terms equal \(2x_5\). Therefore \(M(x) = \tfrac 12\, (5 \cdot 2x_5 - 4 \cdot 2x_5) = x_5\).

Lemma 40 Value of \(M\) when \(x_1\) is maximal

Let \(x \in \mathbb {R}^5\) with \(x_1 \ge x_i\) for \(i = 2, \dots , 5\). Then \(M(x) = x_1\).

Proof ▶

Since \(x_1\) dominates every coordinate, every entry of the flattened list of \(P_1\) is at most \(2x_1\), and \(2x_1\) occurs in the list, so \(P_1(x) = 2x_1\). In the list for \(P_2\), the entries \(2x_2\) and \(x_2 + x_4\) are dominated by \(x_1 + x_2\); deleting them gives \(P_2(x) = \max (2x_5, x_1{+}x_2, x_2{+}x_3, x_3{+}x_4) = R_{23}(x)\). In the list for \(P_3\), the entries \(2x_3\) and \(x_3 + x_2\) are dominated by \(x_3 + x_1\) and \(x_1 + x_2\) respectively, so \(P_3(x) = \max (2x_5, x_3{+}x_4, x_3{+}x_1, x_1{+}x_2) = R_{13}(x)\). Symmetrically, in the list for \(P_4\) the entries \(2x_4\) and \(x_4 + x_2\) are dominated, so \(P_4(x) = \max (2x_5, x_3{+}x_4, x_4{+}x_1, x_1{+}x_2) = R_{14}(x)\). Finally, in \(R_{24}\) the entry \(x_2 + x_4\) is dominated by \(x_1 + x_2\), so \(R_{24}(x) = \max (2x_5, x_1{+}x_2, x_3{+}x_4) = Q(x)\). Substituting into the definition of \(M\), all terms cancel except \(\tfrac 12 P_1(x)\), so \(M(x) = \tfrac 12 \cdot 2x_1 = x_1\).

Theorem 41 Claim 4: \(\mathrm{MAX}_5 = M\)

For all \(x \in \mathbb {R}^5\) we have \(\mathrm{MAX}_5(x) = M(x)\).

Proof ▶

Let \(x \in \mathbb {R}^5\) and distinguish which coordinate attains the maximum. If \(x_5\) is maximal, Lemma 39 gives \(M(x) = x_5 = \mathrm{MAX}_5(x)\). If \(x_1\) is maximal, Lemma 40 applies directly. If \(x_2\) is maximal, apply Lemma 40 to \(y = (x_2, x_1, x_3, x_4, x_5)\) and use Lemma 36: \(M(x) = M(y) = y_1 = x_2\). If \(x_3\) is maximal, apply Lemma 40 to \(y = (x_3, x_4, x_1, x_2, x_5)\) and use Lemma 38. If \(x_4\) is maximal, apply Lemma 40 to \(y = (x_4, x_3, x_1, x_2, x_5)\) and use Lemmas 38 and 36. In every case \(M(x) = \mathrm{MAX}_5(x)\).

Proposition 42 \(\mathrm{MAX}_5\) with two hidden layers

\(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\).

Proof ▶

By Theorem 41, \(\mathrm{MAX}_5 = M\), and by Lemma 35, \(M \in \mathrm{ReLU}_{5,2}\).

Proposition 43 Proposition 3: the depth of \(\mathrm{MAX}_5\) is exactly two

The minimum number of hidden layers needed to compute \(\mathrm{MAX}_5\) is exactly two: \(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\) and \(\mathrm{MAX}_5 \notin \mathrm{ReLU}_{5,1}\).

Proof ▶

Membership in \(\mathrm{ReLU}_{5,2}\) is Proposition 42. If we had \(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,1}\), then Lemma 14 would give \(\mathrm{MAX}_3 \in \mathrm{ReLU}_{3,1}\), contradicting Lemma 17.

Corollary 44 Five-ary trees: \(\mathrm{MAX}_n\) in \(2\lceil \log _5 n\rceil \) layers

For every \(n \ge 1\) we have \(\mathrm{MAX}_n \in \mathrm{ReLU}_{n,\, 2\lceil \log _5 n \rceil }\).

Proof ▶

We show \(\mathrm{MAX}_{5^k} \in \mathrm{ReLU}_{5^k, 2k}\) by induction on \(k \ge 0\); the claim follows by Lemma 14 with \(k = \lceil \log _5 n\rceil \). For \(k = 0\) the identity is affine. For the step, split the \(5^k\) inputs into five blocks of size \(5^{k-1}\) and write \(\mathrm{MAX}_{5^k}\) as \(\mathrm{MAX}_5\) applied to the five block maxima. Each block maximum lies in \(\mathrm{ReLU}_{5^k, 2k-2}\) by induction and Lemma 10; composing with \(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\) (Proposition 42) via Lemma 11 adds two hidden layers.