3 Improved upper bounds on the depth

This chapter proves the paper’s main results: the inductive machinery of the classes \(\mathcal{T}_{a,b}\) (Claims 5–7), Theorem 1 (\(\mathrm{MAX}_{3^n+2}\) with \(n+1\) hidden layers) and Theorem 2 (all CPWL functions on \(\mathbb {R}^n\) with \(\lceil \log _3(n-1)\rceil + 1\) hidden layers).

Definition 45 The function \(T_{a,b}\)

Let \(a, b \ge 0\) with \(a + b \ge 1\). Define \(T_{a,b} \colon \mathbb {R}^{4a+b} \to \mathbb {R}\) as the maximum of \(a\) block terms of the form \(\max (\cdot ,\cdot ) + \max (\cdot ,\cdot )\) and \(b\) extra arguments:

\[ T_{a,b}(x) = \max \bigl( \max (x_1, x_2) + \max (x_3, x_4),\ \dots , \max (x_{4a-3}, x_{4a-2}) + \max (x_{4a-1}, x_{4a}), x_{4a+1}, \dots , x_{4a+b}\bigr). \]

Definition 46 The vector space \(\mathcal{T}_{a,b}^{(d)}\)

Let \(a, b \ge 0\) with \(a + b \ge 1\) and let \(d \ge 1\). Define \(\mathcal{T}_{a,b}^{(d)}\) as the linear span of the functions \(T_{a,b} \circ L\) where \(L \colon \mathbb {R}^d \to \mathbb {R}^{4a+b}\) ranges over all linear maps. (The paper works with the square case \(d = 4a+b\) and passes to other \(d\) by “ignoring coordinates”; the formulation with an arbitrary source dimension makes those steps literal inclusions.)

Lemma 47 \(T_{0,b}\) is the maximum function

For every \(b \ge 1\) we have \(T_{0,b} = \mathrm{MAX}_b\).

Proof ▶

With \(a = 0\) there are no block terms, and the definition reads \(T_{0,b}(x) = \max (x_1, \dots , x_b)\).

Lemma 48 Splitting off four extra arguments

Let \(a, b \ge 0\) with \(a + b \ge 1\) and put \(i = 4a + b\). For all \(x \in \mathbb {R}^{i+4}\),

\[ T_{a,b+4}(x) = \max \bigl(x_{i+1},\ x_{i+2},\ x_{i+3},\ x_{i+4}, T_{a,b}(x_1, \dots , x_i)\bigr). \]

Proof ▶

Both sides are the maximum of the same \(a\) block terms and the same \(b + 4\) extra arguments; only the grouping under the associative and commutative operation \(\max \) differs.

Lemma 49 \(\mathcal{T}\) is closed under linear precomposition

Let \(f \in \mathcal{T}_{a,b}^{(d)}\) and let \(L \colon \mathbb {R}^{d'} \to \mathbb {R}^{d}\) be linear. Then \(f \circ L \in \mathcal{T}_{a,b}^{(d')}\).

Proof ▶

Write \(f = \sum _j c_j\, T_{a,b} \circ L_j\). Then \(f \circ L = \sum _j c_j\, T_{a,b} \circ (L_j \circ L)\), and each \(L_j \circ L\) is linear.

Lemma 50 Adding an extra argument

Let \(a \ge 0\), \(b \ge 1\), \(d \ge 1\). Then \(\mathcal{T}_{a,b}^{(d)} \subseteq \mathcal{T}_{a,b+1}^{(d)}\).

Proof ▶

It suffices to treat a generator \(T_{a,b} \circ L\). Define \(L' \colon \mathbb {R}^d \to \mathbb {R}^{4a+b+1}\) to agree with \(L\) on the first \(4a + b\) output coordinates and to copy output coordinate \(4a + 1\) (the first extra argument, which exists since \(b \ge 1\)) into output coordinate \(4a + b + 1\). A maximum is unchanged when one of its entries is repeated, so \(T_{a,b+1} \circ L' = T_{a,b} \circ L\).

Lemma 51 Absorbing two extras into a block

Let \(a \ge 0\), \(b \ge 2\), \(d \ge 1\). Then \(\mathcal{T}_{a,b}^{(d)} \subseteq \mathcal{T}_{a+1,b-2}^{(d)}\).

Proof ▶

Again treat a generator \(T_{a,b} \circ L\), and note \(\max (u,v) = \max (u,v) + \max (0,0)\). Define \(L' \colon \mathbb {R}^d \to \mathbb {R}^{4(a+1)+(b-2)}\) as follows: the first \(4a\) output coordinates (the old blocks) and the extra output coordinates \(4(a+1)+1, \dots , 4(a+1)+(b-2)\) agree with the corresponding outputs of \(L\) (the first \(b-2\) old extras); the new block inputs \(4a+1, \dots , 4a+4\) are set to \((u, v, 0, 0)\), where \(u, v\) are the last two extra outputs of \(L\) and \(0\) denotes the zero functional. The new block contributes \(\max (u,v) + \max (0,0) = \max (u,v)\) to the outer maximum, and \(\max \) over a list containing \(\max (u,v)\) equals \(\max \) over the list containing \(u\) and \(v\) separately. Hence \(T_{a+1,b-2} \circ L' = T_{a,b} \circ L\).

Lemma 52 The substituted \(P\)-terms

Let \(a, b \ge 0\) with \(a + b \ge 1\), put \(i = 4a+b\), and let \(S \colon \mathbb {R}^{i+4} \to \mathbb {R}^5\) be given by \(S(x) = (x_{i+1}, x_{i+2}, x_{i+3}, x_{i+4}, T_{a,b}(x_1, \dots , x_i))\). Then \(P_j \circ S \in \mathcal{T}_{a+1,b+1}^{(i+4)}\) for each \(j \in \{ 1, 2, 3, 4\} \).

Proof ▶

Consider \(j = 1\); the other cases are identical up to renaming the four coordinates \(x_{i+1}, \dots , x_{i+4}\). Pulling out a factor \(2\),

\[ (P_1 \circ S)(x) = 2 \max \Bigl( T_{a,b}(x_1,\dots ,x_i), \tfrac {x_{i+1}+x_{i+2}}{2}, \max \bigl(\tfrac {x_{i+1}}{2}, \tfrac {x_{i+3}}{2}\bigr) + \max \bigl(\tfrac {x_{i+1}}{2}, \tfrac {x_{i+4}}{2}\bigr)\Bigr). \]

Expanding \(T_{a,b}\), the outer maximum ranges over the \(a\) old block terms, the \(b\) old extra arguments, the new extra argument \(\tfrac {x_{i+1}+x_{i+2}}{2}\), and the new block term \(\max (\tfrac {x_{i+1}}{2}, \tfrac {x_{i+3}}{2}) + \max (\tfrac {x_{i+1}}{2}, \tfrac {x_{i+4}}{2})\). All entries are linear in \(x\), so this is exactly \(2\, (T_{a+1,b+1} \circ L)\) for the linear map \(L \colon \mathbb {R}^{i+4} \to \mathbb {R}^{4(a+1)+(b+1)}\) feeding the old block inputs, the new block inputs \((\tfrac {x_{i+1}}{2}, \tfrac {x_{i+3}}{2}, \tfrac {x_{i+1}}{2}, \tfrac {x_{i+4}}{2})\), the old extras, and the new extra \(\tfrac {x_{i+1}+x_{i+2}}{2}\). Since \(\mathcal{T}_{a+1,b+1}^{(i+4)}\) is a linear span, the factor \(2\) is harmless.

Lemma 53 The substituted \(Q\)-term

In the setting of Lemma 52, \(Q \circ S \in \mathcal{T}_{a,b+2}^{(i+4)}\).

Proof ▶

As before,

\[ (Q \circ S)(x) = 2\max \Bigl( T_{a,b}(x_1,\dots ,x_i), \tfrac {x_{i+1}+x_{i+2}}{2},\ \tfrac {x_{i+3}+x_{i+4}}{2}\Bigr) = 2\, (T_{a,b+2} \circ L)(x) \]

for the linear map \(L\) feeding the old blocks, the old extras, and the two new extras \(\tfrac {x_{i+1}+x_{i+2}}{2}\) and \(\tfrac {x_{i+3}+x_{i+4}}{2}\).

Lemma 54 The substituted \(R\)-terms

In the setting of Lemma 52, \(R_{13} \circ S,\ R_{14} \circ S,\ R_{23} \circ S,\ R_{24} \circ S \in \mathcal{T}_{a,b+3}^{(i+4)}\).

Proof ▶

For \(R_{13}\) (the other three cases only rename coordinates),

\[ (R_{13} \circ S)(x) = 2\max \Bigl( T_{a,b}(x_1,\dots ,x_i), \tfrac {x_{i+1}+x_{i+3}}{2}, \tfrac {x_{i+1}+x_{i+2}}{2}, \tfrac {x_{i+3}+x_{i+4}}{2}\Bigr), \]

which equals \(2\, (T_{a,b+3} \circ L)\) for the linear map \(L\) feeding the old blocks, the old extras, and the three displayed new extras.

Theorem 55 Claim 5: absorbing four extras into one block

Let \(a, b \ge 0\) with \(a + b \ge 1\) and put \(i = 4a+b\). Then \(T_{a,b+4} \in \mathcal{T}_{a+1,b+1}^{(i+4)}\).

Proof ▶

Let \(S(x) = (x_{i+1}, x_{i+2}, x_{i+3}, x_{i+4}, T_{a,b}(x_1, \dots , x_i))\) as in Lemma 52. By Lemma 48 and Theorem 41,

\[ T_{a,b+4} = \mathrm{MAX}_5 \circ S = M \circ S = \tfrac 12\bigl( \textstyle \sum _{j=1}^4 P_j \circ S + Q \circ S - R_{13} \circ S - R_{14} \circ S - R_{23} \circ S - R_{24} \circ S \bigr). \]

By Lemma 52 the four \(P\)-terms lie in \(\mathcal{T}_{a+1,b+1}^{(i+4)}\). By Lemma 53 and two applications of the inclusions of Lemmas 50 and 51,

\[ Q \circ S \in \mathcal{T}_{a,b+2}^{(i+4)} \subseteq \mathcal{T}_{a,b+3}^{(i+4)} \subseteq \mathcal{T}_{a+1,b+1}^{(i+4)}, \]

and by Lemma 54 likewise \(R_{13}\circ S, \dots , R_{24}\circ S \in \mathcal{T}_{a,b+3}^{(i+4)} \subseteq \mathcal{T}_{a+1,b+1}^{(i+4)}\). Since \(\mathcal{T}_{a+1,b+1}^{(i+4)}\) is a vector space, the linear combination \(T_{a,b+4}\) lies in it.

Lemma 56 Step inclusion of the spaces

Let \(a, b \ge 0\) with \(a + b \ge 1\) and let \(d \ge 1\). Then \(\mathcal{T}_{a,b+4}^{(d)} \subseteq \mathcal{T}_{a+1,b+1}^{(d)}\).

Proof ▶

A generator of \(\mathcal{T}_{a,b+4}^{(d)}\) has the form \(T_{a,b+4} \circ L\) with \(L\) linear. By Theorem 55, \(T_{a,b+4} \in \mathcal{T}_{a+1,b+1}^{(4a+b+4)}\), so by Lemma 49, \(T_{a,b+4} \circ L \in \mathcal{T}_{a+1,b+1}^{(d)}\). Spans of subsets of a vector space respect inclusion, so the claim follows.

Lemma 57 Claim 6: iterating the step

For every \(n \ge 1\) and every \(d \ge 1\),

\[ \mathcal{T}_{0,3^n+2}^{(d)} \subseteq \mathcal{T}_{1,3^n-3+2}^{(d)} \subseteq \mathcal{T}_{2,3^n-6+2}^{(d)} \subseteq \cdots \subseteq \mathcal{T}_{3^{n-1},2}^{(d)}. \]

Proof ▶

For \(0 \le j \le 3^{n-1} - 1\) apply Lemma 56 with \(a = j\) and \(b = 3^n - 3j - 2 \ge 1\): it gives \(\mathcal{T}_{j,\, 3^n - 3j + 2}^{(d)} \subseteq \mathcal{T}_{j+1,\, 3^n - 3(j+1) + 2}^{(d)}\). Chaining these \(3^{n-1}\) inclusions from \(j = 0\) to \(j = 3^{n-1}-1\) yields the claim.

Lemma 58 Depth transfers from \(T_{a,b}\) to \(\mathcal{T}_{a,b}\)

Let \(a, b \ge 0\) with \(a + b \ge 1\), and let \(k \ge 0\), \(d \ge 1\). If \(T_{a,b} \in \mathrm{ReLU}_{4a+b,\, k}\) then \(\mathcal{T}_{a,b}^{(d)} \subseteq \mathrm{ReLU}_{d,k}\).

Proof ▶

Each generator \(T_{a,b} \circ L\) lies in \(\mathrm{ReLU}_{d,k}\) by Lemma 10, and \(\mathrm{ReLU}_{d,k}\) is closed under linear combinations by Lemma 9, so it contains the span.

Lemma 59 Claim 7: computing the blocks in one extra layer

Let \(a \ge 1\), \(b \ge 0\) and \(k \ge 0\). If \(T_{0,a+b} \in \mathrm{ReLU}_{a+b,\, k}\) then \(T_{a,b} \in \mathrm{ReLU}_{4a+b,\, k+1}\).

Proof ▶

By definition, \(T_{a,b}(x) = T_{0,a+b}(g_1(x), \dots , g_a(x), x_{4a+1}, \dots , x_{4a+b})\), where \(g_m(x) = \max (x_{4m-3}, x_{4m-2}) + \max (x_{4m-1}, x_{4m})\). Each \(g_m\) lies in \(\mathrm{ReLU}_{4a+b,\, 1}\) by Lemma 12, Lemma 10 and Lemma 9; each coordinate function \(x \mapsto x_{4a+j}\) lies in \(\mathrm{ReLU}_{4a+b,\, 1}\) as well (it is affine, and affine functions belong to every class \(\mathrm{ReLU}_{\cdot ,\, k'}\)). Composing with \(T_{0,a+b} \in \mathrm{ReLU}_{a+b,\, k}\) via Lemma 11 gives \(T_{a,b} \in \mathrm{ReLU}_{4a+b,\, k+1}\).

Theorem 60 Theorem 1: \(\mathrm{MAX}_{3^n+2}\) with \(n+1\) hidden layers

For every \(n \ge 1\) we have \(\mathrm{MAX}_{3^n+2} \in \mathrm{ReLU}_{3^n+2,\, n+1}\).

Proof ▶

Induction on \(n\). The base case \(n = 1\) is \(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\) (Proposition 42). For the induction step let \(n \ge 2\) and assume \(\mathrm{MAX}_{3^{n-1}+2} \in \mathrm{ReLU}_{3^{n-1}+2,\, n}\). By Lemma 47 this says \(T_{0,3^{n-1}+2} \in \mathrm{ReLU}_{3^{n-1}+2,\, n}\), so Lemma 59 (with \(a = 3^{n-1}\), \(b = 2\)) gives \(T_{3^{n-1},2} \in \mathrm{ReLU}_{4\cdot 3^{n-1}+2,\, n+1}\). Set \(d = 3^n + 2\). By Lemma 58, \(\mathcal{T}_{3^{n-1},2}^{(d)} \subseteq \mathrm{ReLU}_{d,\, n+1}\). Since \(T_{0,3^n+2} \in \mathcal{T}_{0,3^n+2}^{(d)}\) (take \(L\) the identity), Lemma 57 gives \(T_{0,3^n+2} \in \mathcal{T}_{3^{n-1},2}^{(d)}\), and therefore \(\mathrm{MAX}_{3^n+2} = T_{0,3^n+2} \in \mathrm{ReLU}_{3^n+2,\, n+1}\) by Lemma 47.

Corollary 61 Depth \(\lceil \log _3(n-2)\rceil + 1\) for \(\mathrm{MAX}_n\)

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

Proof ▶

Let \(m = \lceil \log _3(n-2)\rceil \); since \(n \ge 4\) we have \(n - 2 \ge 2\) and hence \(m \ge 1\), and \(3^m \ge n - 2\), i.e. \(3^m + 2 \ge n\). By Theorem 60, \(\mathrm{MAX}_{3^m+2} \in \mathrm{ReLU}_{3^m+2,\, m+1}\), and Lemma 14 restricts to \(n\) arguments.

Theorem 62 Theorem 2: depth of all CPWL functions

For every \(n \ge 3\) we have

\[ \mathrm{CPWL}_n = \mathrm{ReLU}_{n,\, \lceil \log _3(n-1)\rceil + 1}. \]

Proof ▶

The inclusion \(\supseteq \) is Lemma 6. For \(\subseteq \), let \(f \in \mathrm{CPWL}_n\) and write \(f = \sum _i \sigma _i\, \mathrm{MAX}_{n+1} \circ A_i\) as in Theorem 15. Since \(n + 1 \ge 4\), Corollary 61 gives \(\mathrm{MAX}_{n+1} \in \mathrm{ReLU}_{n+1,\, \lceil \log _3(n-1)\rceil + 1}\). By Lemma 10 and Lemma 9, \(f\) lies in \(\mathrm{ReLU}_{n,\, \lceil \log _3(n-1)\rceil + 1}\).

Proposition 63 Remark 1: dyadic weights suffice

For every \(n \ge 1\) there is a ReLU network with \(n + 1\) hidden layers computing \(\mathrm{MAX}_{3^n+2}\) all of whose weights and biases lie in \(\mathbb {Z}[\tfrac 12]\), the ring of binary fractions. (In particular the construction of Theorem 60 falls into the decimal-fraction setting of the \(\lceil \log _3 n\rceil \) lower bound of Averkov, Hojny, and Merkert.)

Proof ▶

We inspect the construction proving Theorem 60. All gadgets used there have weights in \(\{ 0, \pm 1, \pm \tfrac 12\} \subseteq \mathbb {Z}[\tfrac 12]\) and zero biases: the \(\mathrm{MAX}_2\) gadget of Lemma 12 uses weights \(\pm 1\); the nine terms of \(M\) use integer coefficients and the outer combination of \(M\) uses \(\pm \tfrac 12\); the rearrangements in the proofs of Claims 5–7 introduce only coefficients \(0\), \(\pm 1\) and \(\pm \tfrac 12\) (the halvings). The closure operations (parallel stacking, and merging adjacent affine maps in compositions) combine weights by addition and multiplication, and \(\mathbb {Z}[\tfrac 12]\) is a ring, so all weights and biases of the resulting network remain binary fractions.