Generalization error bounds for deep models

7 Worked examples (Appendices J–M)

7.1 Shared glue for the worked examples (regimes)

Theorem 419
✓
#

\(L[f] \ge 0\) since the loss is nonnegative.

Proof ▶

(Approximation transfer, ‘eq:approx-transfer‘.) Let \(\ell \) be \(\beta _\ell \)-Lipschitz in its first argument, \(\mathcal H\) and \(\mathcal C \ne \emptyset \) classes of measurable functions, and \(B \in \mathbb R\). If every \(c \in \mathcal C\) is uniformly approximable from \(\mathcal H\) within \(B + \varepsilon \) for every \(\varepsilon {\gt} 0\) (in particular if \(\sup _{c \in \mathcal C}\inf _{f \in \mathcal H} \| f - c\| _\infty \le B\)), then

\[ \varepsilon _{\mathrm{model}} = \inf _{\mathcal H} L - \inf _{\mathcal C} L \le \beta _\ell \, B . \]
Proof ▶

For \(c \in \mathcal C\) and \(\varepsilon {\gt} 0\) pick \(f \in \mathcal H\) with \(\| f - c\| _\infty \le B + \varepsilon \); then \(\inf _{\mathcal H} L \le L[f] \le L[c] + \beta _\ell (B + \varepsilon )\) by ‘lem:risk-lipschitz‘. Let \(\varepsilon \to 0\) and take the infimum over \(c\).

Theorem 421
✓

For \(h = \langle w, \Phi (\cdot )\rangle \in H_R(\Phi )\), \(|h(x)| \le R\, \| \Phi (x)\| \).

Proof ▶
Theorem 422
✓

If \(\Phi \) is \(L_\Phi \)-Lipschitz and \(R \ge 0\) then every \(h \in H_R(\Phi )\) is \(R L_\Phi \)-Lipschitz.

Proof ▶

For \(R {\gt} 0\), \(H_R(\Phi ) = H_1(R\, \Phi )\): the radius can be absorbed into the feature map.

Proof ▶

(‘prop:hilbert-sg‘ for the radius-\(R\) class.) If \(\Phi \) is \(L_\Phi \)-Lipschitz and \(R {\gt} 0\), then \(H_R(\Phi )\) satisfies the sub-Gaussian increment condition ‘ass:sg-increment-main‘ with \(A_H = 1\) and \(L = R L_\Phi \), for every hidden-layer class \(\mathfrak F\).

Proof ▶

\(H_R(\Phi ) = H_1(R\Phi )\) and \(R\Phi \) is \(RL_\Phi \)-Lipschitz.

Theorem 425
✓

If \(|g(x)| \le C\) for all \(g \in G\) and \(x\) (\(C \ge 0\)), then the Rademacher averages \(\{ \frac1n\sum _i \sigma _i g(x_i) : g \in G\} \) are bounded above by \(C\), for every sample and sign pattern.

Proof ▶

(Rademacher complexity of the linear readout class.) If \(\| \Phi (x)\| \le M\) for all \(x\) (\(R, M \ge 0\)), then for every sample \(S\) of size \(n\),

\[ \hat{\mathfrak R}_S(H_R(\Phi )) \le \frac{R\, M}{\sqrt n} . \]

(Proof: \(\hat{\mathfrak R}_S(H_R(\Phi )) \le R\, \mathbb E_\sigma \| n^{-1}\sum _i\sigma _i \Phi (x_i)\| \le R\sqrt{\sum _i\| \Phi (x_i)\| ^2}/n \le RM/\sqrt n\), via FoML’s hilbertPredictor_empiricalRademacherComplexity_le.)

Proof ▶
Theorem 427
✓
#

If \(F\) is finite then every word ball \(B(k,F)\) is finite.

Proof ▶

If \(\Phi \) is continuous and every \(f \in \mathfrak F\) is continuous, then every element of \(H_R(\Phi ) \circ \mathfrak F\) is (Borel) measurable.

Proof ▶

If \(\| \Phi \| \le M\) and \(R \ge 0\) then \(|g(x)| \le RM\) for every \(g \in H_R(\Phi ) \circ \mathfrak F\) and every \(x\).

Proof ▶
Definition 430
✓
#

A hidden-layer class \(\mathfrak F\) has a countable uniformly dense subset if there is a countable \(D \subseteq \mathfrak F\) such that every \(f \in \mathfrak F\) is within uniform distance \(\varepsilon \) of some \(g \in D\), for every \(\varepsilon {\gt} 0\).

Theorem 431
✓

A finite hidden-layer class has a countable uniformly dense subset (itself).

Proof ▶

A hidden-layer class which is totally bounded in \(d_\infty \) has a countable uniformly dense subset (it is separable in the pseudo-metrizable space \((\mathcal X^{\mathcal X}, d_\infty )\)).

Proof ▶

(Sup-norm separability of \(H_R(\Phi ) \circ \mathfrak F\).) Let \(\mathcal H\) be a separable real inner product space, \(\Phi : \mathcal X \to \mathcal H\) be \(L_\Phi \)-Lipschitz with \(\| \Phi \| \le M\), \(R \ge 0\), and let \(\mathfrak F\) have a countable uniformly dense subset. Then \(H_R(\Phi ) \circ \mathfrak F\) is sup-norm separable: the countable set \(\{ \langle w, \Phi (g(\cdot ))\rangle : w \in W,\ g \in D\} \), with \(W\) a countable dense subset of the ball of radius \(R\), is uniformly dense, since \(|\langle w, \Phi (f x)\rangle - \langle w', \Phi (g x)\rangle | \le \| w - w'\| M + R L_\Phi \, d(f x, g x)\).

Proof ▶

A class which is totally bounded in \(d_\infty \) is totally bounded in \(d_S\) for every sample \(S\) (the identity is \(1\)-Lipschitz, ‘lem:to-emp-space-lipschitz‘).

Proof ▶
Theorem 435
✓

Every element of the uniform closure of a class of measurable functions is measurable (a uniform limit of measurable functions is a pointwise limit).

Proof ▶
Definition 436
✓
#

The estimation-plus-deviation term of ‘thm:bv‘ (with the constants of ‘thm:bv-general‘), as a function of an upper bound \(B\) for \(\hat{\mathfrak R}_S(\mathcal H)\):

\[ \mathrm{dev}_{\ell ,n,\delta }(B) := 4\beta _\ell B + 6\, b\sqrt{\tfrac {2\log (4/\delta )}{n}} . \]

(All regime propositions below are stated in terms of this quantity, so that the constants of ‘thm:bv‘ enter in one place only.)

Theorem 437
✓
#

\(B \mapsto \mathrm{dev}_{\ell ,n,\delta }(B)\) is nondecreasing when \(\beta _\ell \ge 0\).

Proof ▶

(‘thm:bv‘ with \(\iota = \mathrm{id}\) and explicit bounds.) Let \(\mathcal H\) be a sup-norm separable, pointwise bounded class of measurable functions, \(\mathcal C \ne \emptyset \) a class of measurable benchmarks, \(\ell \) measurable, bounded by \(b {\gt} 0\) and \(\beta _\ell \)-Lipschitz, \(n \ge 1\), \(\eta \ge 0\), \(\delta \in (0,1)\). Suppose \(\hat{\mathfrak R}_S(\mathcal H) \le B\) for every sample \(S\) of size \(n\) and \(\varepsilon _{\mathrm{model}} \le \mathrm{bias}\). Then with probability at least \(1 - \delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(\eta \)-empirical minimizer \(\hat f \in \mathcal H\) satisfies

\[ L[\hat f] - \inf _{\mathcal C} L \le \mathrm{bias} + \eta + \mathrm{dev}_{\ell ,n,\delta }(B) = \mathrm{bias} + \eta + 4\beta _\ell B + 6\, b\sqrt{\tfrac {2\log (4/\delta )}{n}} . \]
Proof ▶

‘thm:bv-general‘ with \(\iota = \mathrm{id}\), \(d_T = 0\), \(\varepsilon _{\mathrm{imp}} = 0\), then monotonicity of the bad event.

(Truncation, Sec. ‘sec:examples-regime‘.) Let every \(h \in H\) be \(L_H\)-Lipschitz, every \(f \in F\) be \(c\)-Lipschitz, and \(d(x,y) \le D_{\mathcal X}\) on \(\mathcal X\). Then every \(g = h \circ w \in H \circ \langle F\rangle \) is within uniform distance \(L_H c^k D_{\mathcal X}\) of \(\mathcal H_k = H \circ B(k,F)\): if \(w = w_2 \circ w_1\) with \(|w_2| = k\) then \(|h(w_2(w_1 x)) - h(w_2 x)| \le L_H c^k d(w_1 x, x)\).

Proof ▶

(Truncation for the uniform closure.) Under the hypotheses of ‘lem:truncation-bias-exact‘, every \(g\) in the uniform closure \(\overline{H \circ \langle F\rangle }^{\, d_\infty }\) satisfies, for every \(\varepsilon {\gt} 0\), \(\inf _{f \in \mathcal H_k}\| f - g\| _\infty \le L_H c^k D_{\mathcal X} + \varepsilon \).

Proof ▶
Definition 441
✓

The depth-independent entropy integral of ‘cor:profile-p1‘: \(\mathsf V_\infty (F) := \int _0^{\mathrm{diam}(\mathcal X)} \sqrt{\log N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon /2)}\, d\varepsilon \).

Definition 442
✓

The paper’s condition \(\mathsf V_\infty (F) {\lt} \infty \): the majorant \(\varepsilon \mapsto \sqrt{\log N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon /2)}\) is interval-integrable on \([0, \mathrm{diam}(\mathcal X)]\).

Theorem 443
✓

(EL balance with saturated variance.) For \(0 {\lt} \theta {\lt} 1\) and \(n \ge 1\), the depth \(k := \lceil \log n / (2\log (1/\theta ))\rceil \) satisfies \(\theta ^k \le n^{-1/2}\): the bias \(\theta ^k\) is balanced against the saturated variance \(n^{-1/2}\), and \(k = \frac{\log n}{2\log (1/\theta )} + O(1)\).

Proof ▶

\(k \log (1/\theta ) \ge \tfrac 12\log n = \log \sqrt n\), so \((1/\theta )^k \ge \sqrt n\).

Theorem 444
✓
#

(PL balance with saturated variance, \(p = 1\).) For \(n \ge 1\) the depth \(k := \lceil \sqrt n\rceil \ge 1\) satisfies \(1/k \le n^{-1/2}\): the bias \(k^{-1}\) is balanced against the saturated variance \(n^{-1/2}\), and \(k \asymp n^{1/2}\).

Proof ▶

7.2 Implementation with controlled uniform error (Appendix J, prop:implementation; proof in J.3)

Definition 445
✓
#

For a list of layers \(u = [f_m, \dots , f_1]\) (an explicit representation of a word) the composed map is \(f_u = f_m \circ \cdots \circ f_1\), with \(f_{[]} = \mathrm{id}\). In Lean: ‘compList [] = id‘ and ‘compList (f :: u) = f ∘ compList u‘ (the head of the list acts last, matching the recursion \(B(k+1,F) = B(k,F) \cup F \circ B(k,F)\)).

Theorem 446
✓
#

\(f_{[]} = \mathrm{id}\).

Proof ▶
Theorem 447
✓
#

\(f_{f :: u} = f \circ f_u\).

Proof ▶
Definition 448
✓
#

Given an implementation \(f \mapsto \tilde f\) of the layers, the implemented word of a representation \(u = [f_m, \dots , f_1]\) is \(\tilde f_u = \tilde f_m \circ \cdots \circ \tilde f_1\).

Theorem 449
✓
#

\(\tilde f_{[]} = \mathrm{id}\).

Proof ▶
Theorem 450
✓
#

\(\tilde f_{f :: u} = \tilde f \circ \tilde f_u\).

Proof ▶
Theorem 451
✓

If all layers of \(u\) lie in \(F\) and \(|u| \le k\) then \(f_u \in B(k,F)\).

Proof ▶

Induction on \(u\): \(\mathrm{id} \in B(k,F)\), and \(f \circ f_u \in B(k'+1,F)\) when \(f \in F\) and \(f_u \in B(k',F)\).

Theorem 452
✓

Every \(g \in B(k,F)\) has a representation \(g = f_m \circ \cdots \circ f_1\) with \(f_i \in F\) and \(m \le k\), i.e. \(g = f_u\) for a list \(u\) of elements of \(F\) with \(|u| \le k\).

Proof ▶

Induction on \(k\) along the recursion \(B(k+1,F) = B(k,F) \cup F \circ B(k,F)\).

(Telescoping error propagation.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz and let \(\tilde f\) satisfy \(d_\infty (f, \tilde f) \le \delta \) for \(f \in F\), where \(\delta \ge 0\). Then for every representation \(u = [f_m, \dots , f_1]\) of layers in \(F\) and every \(x\),

\[ d\bigl(f_m \circ \cdots \circ f_1(x),\ \tilde f_m \circ \cdots \circ \tilde f_1(x)\bigr) \le \delta \sum _{i=0}^{m-1} \Lambda ^i . \]
Proof ▶

Induction on \(u\). For \(u = f :: u'\) write \(y = f_{u'}(x)\), \(\tilde y = \tilde f_{u'}(x)\); then \(d(f(y), \tilde f(\tilde y)) \le d(f(y), f(\tilde y)) + d(f(\tilde y), \tilde f(\tilde y)) \le \Lambda \, d(y, \tilde y) + \delta \le \Lambda \delta \sum _{i{\lt}m} \Lambda ^i + \delta = \delta \sum _{i{\lt}m+1} \Lambda ^i\).

(Existence of the layerwise implementation map.) Given implementations \(f \mapsto \tilde f\) of the transitions and \(h \mapsto \tilde h\) of the output layers, there is a map \(\iota : \mathbb R^{\mathcal X} \to \mathbb R^{\mathcal X}\) such that every \(g \in \mathcal H_k\) has a representation \(g = h \circ f_m \circ \cdots \circ f_1\) with \(h \in H\), \(f_i \in F\), \(m \le k\) and \(\iota (g) = \tilde h \circ \tilde f_m \circ \cdots \circ \tilde f_1\).

Proof ▶

For each \(g \in \mathcal H_k\) choose (by the axiom of choice) a representation, using ‘lem:exists-comp-list-of-mem-wordball‘; outside \(\mathcal H_k\) the value of \(\iota \) is irrelevant.

(Layerwise implementation.) Let \(F \subseteq \mathcal X^{\mathcal X}\) with \(\mathrm{lip}(f) \le \Lambda \) for all \(f \in F\), and \(H \subseteq \mathbb R^{\mathcal X}\) with \(\mathrm{lip}(h) \le L_H\) for all \(h \in H\). Suppose every \(f \in F\) is assigned an implemented map \(\tilde f\) with \(d_\infty (f, \tilde f) \le \delta \) (\(\delta \ge 0\)) and every \(h \in H\) an implemented \(\tilde h\) with \(\| h - \tilde h\| _\infty \le \delta _H\). Let \(\iota \) be an implementation map that sends each \(g \in \mathcal H_k\), for one representation \(g = h \circ f_m \circ \cdots \circ f_1\) with \(m \le k\), to \(\tilde h \circ \tilde f_m \circ \cdots \circ \tilde f_1\). Then

\[ \varepsilon _{\mathrm{imp}}(k) \le \delta _H + L_H\, \delta \sum _{i=0}^{k-1} \Lambda ^i . \]

(Stated for an arbitrary \(\iota \) with this property; such an \(\iota \) exists by ‘lem:impl-map-exists‘.)

Proof ▶

Fix \(g = h \circ f_u \in \mathcal H_k\) and \(x\); put \(T_0 = f_u(x)\), \(T_m = \tilde f_u(x)\). By ‘lem:impl-word-error‘, \(d(T_0, T_m) \le \delta \sum _{i{\lt}m} \Lambda ^i \le \delta \sum _{i{\lt}k} \Lambda ^i\) (as \(\Lambda \ge 0\) and \(m \le k\)). Then \(|h(T_0) - \tilde h(T_m)| \le |h(T_0) - h(T_m)| + |h(T_m) - \tilde h(T_m)| \le L_H\, d(T_0, T_m) + \delta _H\); take suprema over \(x\) and \(g\).

Under the hypotheses of ‘prop:implementation-b‘ there exists an implementation map \(\iota \) with \(\varepsilon _{\mathrm{imp}}(k) \le \delta _H + L_H\, \delta \sum _{i{\lt}k} \Lambda ^i\).

Proof ▶

Combine ‘lem:impl-map-exists‘ and ‘prop:implementation-b‘.

Theorem 457
✓
#

If \(0 \le \Lambda \le 1\) then \(\sum _{i{\lt}k} \Lambda ^i \le k\).

Proof ▶
Theorem 458
✓
#

If \(0 \le \Lambda {\lt} 1\) then \(\sum _{i{\lt}k} \Lambda ^i \le 1/(1-\Lambda )\).

Proof ▶

\(\sum _{i{\lt}k} \Lambda ^i = (1 - \Lambda ^k)/(1 - \Lambda ) \le 1/(1-\Lambda )\).

(Non-expanding transitions.) If moreover \(\Lambda \le 1\), then \(\varepsilon _{\mathrm{imp}}(k) \le \delta _H + L_H\, k\, \delta \).

Proof ▶

‘prop:implementation-b‘ and \(\sum _{i{\lt}k} \Lambda ^i \le k\).

(Contractive transitions.) If moreover \(\Lambda {\lt} 1\), then \(\varepsilon _{\mathrm{imp}}(k) \le \delta _H + L_H\, \delta / (1 - \Lambda )\).

Proof ▶

‘prop:implementation-b‘ and \(\sum _{i{\lt}k} \Lambda ^i \le 1/(1-\Lambda )\).

Definition 461
✓
#

\(\mathrm{relu}(t) = \max \{ 0, t\} \).

Definition 462
✓
#

A one-hidden-layer ReLU layer on \(\mathbb R^d\) with hidden index set \(m\) (width \(|m|\)) is \(x \mapsto W_2\, \mathrm{relu}(W_1 x) + b\), with \(W_1 \in \mathbb R^{m \times d}\), \(W_2 \in \mathbb R^{d \times m}\), \(b \in \mathbb R^d\) and \(\mathrm{relu}\) applied coordinatewise.

Theorem 463
✓
#

\(t = \mathrm{relu}(t) - \mathrm{relu}(-t)\).

Proof ▶

(Exact realization of an affine map.) For \(A \in \mathbb R^{d \times d}\) and \(b \in \mathbb R^d\), with \(W_1 = [I_d; -I_d] \in \mathbb R^{2d \times d}\) and \(W_2 = [A, -A] \in \mathbb R^{d \times 2d}\),

\[ W_2\, \mathrm{relu}(W_1 x) + b = A x + b \qquad (x \in \mathbb R^d), \]

i.e. \(x \mapsto Ax + b\) is one ReLU layer of width \(2d\).

Proof ▶

\(\mathrm{relu}(W_1 x) = (\mathrm{relu}(x), \mathrm{relu}(-x))\) and \([A,-A](v_1, v_2) = A(v_1 - v_2)\); conclude with \(\mathrm{relu}(t) - \mathrm{relu}(-t) = t\).

Definition 465
✓
#

The parameters \((W_2, W_1, b)\) of a ReLU layer of width \(2d\) on \(\mathbb R^d\).

Definition 466
✓
#

The ReLU layer of width \(2d\) with parameters \((W_2, W_1, b)\).

Definition 467
✓

A map \(g : \mathbb R^d \to \mathbb R^d\) is a ReLU network of depth \(\le k\) and width \(2d\) if it is a composition of at most \(k\) ReLU layers of width \(2d\).

If every layer of the representation \(u\) is affine, then \(f_u\) is a composition of \(|u|\) ReLU layers of width \(2d\).

Proof ▶

Induction on \(u\), replacing each affine layer by the ReLU layer of ‘lem:affine-eq-relu‘.

Theorem 469
✓
#

The identity implementation map has zero implementation error: \(\varepsilon _{\mathrm{imp}} = 0\) for \(\iota = \mathrm{id}\) on any class.

Proof ▶

(Exact implementation of affine transitions.) Let \(\mathcal X = \mathbb R^d\) and let every \(f \in F\) be affine, \(f(x) = Ax + b\). Then every element of \(B(k,F)\) is a ReLU network of depth \(\le k\) and width \(2d\), and with the identity implementation map \(\iota = \mathrm{id}\) (the abstract class \(\mathcal H_k\) is itself the implemented class) one has \(\varepsilon _{\mathrm{imp}}(k) = 0\).

Proof ▶

Take a representation of \(g \in B(k,F)\) (‘lem:exists-comp-list-of-mem-wordball‘) and apply ‘lem:comp-list-affine-eq-relu-net‘; the second claim is ‘lem:impl-error-id‘.

Theorem 471
✓
#

(Net-based implementation.) Let \(\mathcal H \subseteq \mathbb R^{\mathcal X}\) be totally bounded in the uniform norm and let \(\mathcal A \subseteq \mathbb R^{\mathcal X}\) be uniformly dense on \(\mathcal H\) (for every \(g \in \mathcal H\) and \(\eta {\gt} 0\) there is \(a \in \mathcal A\) with \(\| g - a\| _\infty \le \eta \)). Then for every \(\varepsilon {\gt} 0\) there exist a finite class \(\mathcal H_{\mathrm{imp}}^\varepsilon \subseteq \mathcal A\) with \(|\mathcal H_{\mathrm{imp}}^\varepsilon | \le N(\mathcal H, \| \cdot \| _\infty , \varepsilon /2)\) and an implementation map \(\iota : \mathcal H \to \mathcal H_{\mathrm{imp}}^\varepsilon \) with \(\sup _{g \in \mathcal H} \| g - \iota (g)\| _\infty \le \varepsilon \). (The paper’s compact domain \(K\) and the continuity of the functions are only used to guarantee total boundedness and density, which are the hypotheses here.)

Proof ▶

Let \(C \subseteq \mathcal H\) be a minimal internal \(\varepsilon /2\)-net (finite by total boundedness). For each \(c \in C\) choose \(a_c \in \mathcal A\) with \(\| c - a_c\| _\infty \le \varepsilon /2\), set \(\mathcal H_{\mathrm{imp}} = \{ a_c : c \in C\} \) and \(\iota (g) = a_{c(g)}\) where \(c(g) \in C\) satisfies \(\| g - c(g)\| _\infty \le \varepsilon /2\). Then \(\| g - \iota (g)\| _\infty \le \varepsilon /2 + \varepsilon /2\).

7.3 Deep ReLU networks (Appendix K, lem:relu-layer-covering, prop:relu-regimes)

Theorem 472
✓
#

Packing numbers are monotone in the set: \(A \subseteq B\) implies \(M(A, \varepsilon ) \le M(B, \varepsilon )\).

Proof ▶
Theorem 473
✓

(Volumetric bound, finite sets.) Let \(E\) be a real normed space of dimension \(q\), \(\rho \ge 0\), \(\delta {\gt} 0\). If \(s \subseteq \overline B(x, \rho )\) is a finite \(\delta \)-separated set (distinct points at distance \({\gt} \delta \)) then \(|s| \le (1 + 2\rho /\delta )^q\): the open balls \(B(y, \delta /2)\), \(y \in s\), are pairwise disjoint and contained in \(B(x, \rho + \delta /2)\), and Haar measure scales like \(r^q\).

Proof ▶

The balls \(B(y, \delta /2)\), \(y \in s\), are pairwise disjoint.

Each of them lies in \(B(x, \rho + \delta /2)\).

Comparing measures: \(|s| \cdot (\delta /2)^q \mu (B(0,1)) \le (\rho + \delta /2)^q \mu (B(0,1))\).

Theorem 474
✓
#

(Volumetric bound.) In a real normed space \(E\) of dimension \(q\), for \(\rho \ge 0\) and \(\delta {\gt} 0\), the packing number of the closed ball satisfies \(M(\overline B(x, \rho ), \delta ) \le \lfloor (1 + 2\rho /\delta )^q \rfloor \); in particular a \(\delta \)-cover of the ball of size at most \((1 + 2\rho /\delta )^q\) exists.

Proof ▶

Every separated subset is finite (its finite subsets have bounded cardinality) and its cardinality is bounded by ‘lem:relu-volumetric-finset‘.

Theorem 475
✓

If \(\varphi \) is \(L\)-Lipschitz on \(A\) then \(N^{\mathrm{ext}}(\varphi (A), L\varepsilon ) \le N(A, \varepsilon )\) (internal covering number of \(A\) on the right, since the centres must lie in \(A\) where \(\varphi \) is controlled).

Proof ▶

(Parametric layers, ‘cor:envelope-profiles‘(a) for the hypothesis \(\log N(F, \varepsilon ) \le p\log (1 + C/\varepsilon )\).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, let \(\overline D {\gt} 0\), \(C \ge 0\), \(p \ge 0\), and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le p\log (1 + C/\varepsilon )\) for all \(\varepsilon {\gt} 0\). If \(D_k(S) \le \overline D\) then, for \(k \ge 1\), with \(\Lambda _+ := \max \{ 1,\Lambda \} \),

\[ \mathsf V_k(S) \le \overline D\Bigl(\sqrt{\log (k+1)} + \sqrt{kp\log k} + k\sqrt{p\log \Lambda _+} + \sqrt{kp}\bigl(\sqrt{\log (1 + 2C/\overline D)} + \tfrac {\sqrt\pi }{2}\bigr)\Bigr). \]

(Same proof as ‘cor:envelope-profiles-a‘, with \(1 + 2CS_k/\varepsilon \le (1 + 2C/\overline D)\, S_k\, \overline D/\varepsilon \) for \(\varepsilon \le \overline D\).)

Proof ▶

Pointwise, for \(0 {\lt} \varepsilon \le \overline D\): \(\log N(B(k,F), d_S, \varepsilon ) \le \log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon /2) \le \log (k+1) + kp\log (1 + 2CS_k/\varepsilon )\), and \(1 + 2CS_k/\varepsilon \le (1 + 2C/\overline D) S_k \overline D/\varepsilon \) with \(\log S_k \le \log k + k\log \Lambda _+\); take square roots termwise and integrate, using \(\int _0^{\overline D}\sqrt{\log (\overline D/\varepsilon )} \, d\varepsilon = \tfrac {\sqrt\pi }{2}\overline D\).

Definition 477
✓
#

The ReLU nonlinearity acting coordinatewise on \(\mathbb R^w\) (the scalar ‘relu‘ of ‘LeanDeepgen.Examples.Implementation‘ in every coordinate): \(\mathrm{relu}(z)_i = \max \{ z_i, 0\} \).

Theorem 478
✓
#

\(\mathrm{relu}(z)_i = \max \{ z_i, 0\} \).

Proof ▶
Theorem 479
✓
#

\(\mathrm{relu}\) is \(1\)-Lipschitz for the Euclidean norm, since \(|\max \{ a,0\} - \max \{ b,0\} | \le |a - b|\) coordinatewise.

Proof ▶
Theorem 480
✓
#

\(\mathrm{relu}(0) = 0\).

Proof ▶
Theorem 481
✓

\(\| \mathrm{relu}(z)\| \le \| z\| \).

Proof ▶
Definition 482
✓
#

The parameter space of a ReLU block of width \(w\) on \(\mathbb R^m\) (\(=E\)): \(\vartheta = (W, b, V, c) \in (\mathbb R^m \to \mathbb R^w) \times \mathbb R^w \times (\mathbb R^w \to \mathbb R^m) \times \mathbb R^m\), with the operator norm on the linear maps and the sup (product) norm on the tuple.

Definition 483
✓

The ReLU block with parameters \(\vartheta = (W,b,V,c)\) on the state space \(K\): \(f_\vartheta (x) = \Pi _K\bigl(V\, \mathrm{relu}(Wx + b) + c\bigr)\), a self-map of \(K\).

Definition 484
✓

The admissible parameters: \(\| W\| _{\rm op}, \| V\| _{\rm op} \le \beta _W\), \(\| b\| , \| c\| \le \beta \) and \(\mathrm{lip}(f_\vartheta ) \le \Lambda \).

Definition 485
✓

The hidden-layer class of ReLU blocks of width \(w\), \(F_\Lambda = \{ f_\vartheta : \| W\| _{\rm op}, \| V\| _{\rm op} \le \beta _W,\ \| b\| , \| c\| \le \beta ,\ \mathrm{lip}(f_\vartheta ) \le \Lambda \} \).

Every \(f \in F_\Lambda \) is \(\Lambda \)-Lipschitz.

Proof ▶

\(F_\Lambda \ne \emptyset \): the zero parameters give the constant map \(x \mapsto \Pi _K(0)\).

Proof ▶

The admissible parameters lie in the sup-norm ball of radius \(\max \{ \beta _W, \beta \} \).

Proof ▶

(Parameter-Lipschitz estimate.) Let \(\| x\| \le R_K\) on \(K\), \(\| V\| _{\rm op} \le \beta _W\), \(\| W'\| _{\rm op} \le \beta _W\) and \(\| b'\| \le \beta \). Then

\[ d_\infty (f_\vartheta , f_{\vartheta '}) \le \beta _W R_K\| W - W'\| _{\rm op} + \beta _W\| b - b'\| + (\beta _W R_K + \beta )\| V - V'\| _{\rm op} + \| c - c'\| . \]

(Only these three parameter bounds are used, as in the paper’s proof.)

Proof ▶

For \(x \in K\) write \(z = \mathrm{relu}(Wx+b)\), \(z' = \mathrm{relu}(W'x+b')\); then \(\| z - z'\| \le R_K\| W - W'\| + \| b - b'\| \), \(\| z'\| \le \beta _W R_K + \beta \) and \(\| Vz + c - V'z' - c'\| \le \| V\| \| z - z'\| + \| V - V'\| \| z'\| + \| c - c'\| \); apply the \(1\)-Lipschitz retraction.

Definition 490
✓
#

The parameter-Lipschitz constant of \(\vartheta \mapsto f_\vartheta \) on \(F_\Lambda \) for the sup norm on parameters: \(L_F := 2\beta _W R_K + \beta _W + \beta + 1\) (the sum of the four coefficients of ‘lem:relu-layer-covering-a‘).

Definition 491
✓
#

The covering constant of one ReLU block: \(C_F := 2 L_F \max \{ \beta _W, \beta \} = 2(2\beta _W R_K + \beta _W + \beta + 1) \max \{ \beta _W,\beta \} \). (The paper’s \(C_F = 8\sqrt{\max \{ m,w\} }\max \{ \beta _W,1\} \max \{ \beta _W R_K + \beta , \beta _W, 1\} \) has the same shape; the factor \(\sqrt{\max \{ m,w\} }\) comes from bounding the operator norm by the Frobenius norm, which the volumetric argument in the operator norm avoids.)

Theorem 492
✓
#

\(L_F \ge 1\) when \(R_K \ge 0\).

Proof ▶

\(\vartheta \mapsto f_\vartheta \) is \(L_F\)-Lipschitz on the admissible parameter set, from \((\mathrm{parameters}, \| \cdot \| _{\sup })\) to \((\mathcal X^{\mathcal X}, d_\infty )\): each of the four differences in ‘lem:relu-layer-covering-a‘ is at most \(\| \vartheta - \vartheta '\| _{\sup }\).

Proof ▶
Theorem 494
✓
#

The parameter space has dimension \(p = 2mw + w + m\), \(m = \dim E\).

Proof ▶

(Covering bound, cardinality form.) Let \(\| x\| \le R_K\) on \(K\) with \(R_K \ge 0\) and \(p = 2mw + w + m\). For every \(\varepsilon {\gt} 0\), \(N^{\mathrm{ext}}(F_\Lambda , d_\infty , \varepsilon ) \le (1 + C_F/\varepsilon )^p\) with \(C_F = 2(2\beta _W R_K + \beta _W + \beta + 1)\max \{ \beta _W, \beta \} \): \(N^{\mathrm{ext}}(F_\Lambda , \varepsilon ) \le N(P, \varepsilon /L_F) \le M(P, \varepsilon /L_F) \le M(\overline B(0, \max \{ \beta _W,\beta \} ), \varepsilon /L_F) \le (1 + 2L_F\max \{ \beta _W,\beta \} /\varepsilon )^p\) by ‘lem:relu-lipschitz-on-image‘, ‘lem:packing-covering‘ and ‘lem:relu-volumetric‘.

Proof ▶

(Covering bound, entropy form.) Under the hypotheses of ‘lem:relu-layer-covering-b‘, for every \(\varepsilon {\gt} 0\), \(N^{\mathrm{ext}}(F_\Lambda , d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F_\Lambda , d_\infty , \varepsilon ) \le p\log (1 + C_F/\varepsilon )\).

Proof ▶

(Covering numbers of one ReLU block.) Let \(K \subseteq \mathbb R^m\) with \(\| x\| \le R_K\) on \(K\) (\(R_K \ge 0\)), let \(\Pi _K\) be a \(1\)-Lipschitz retraction onto \(K\), and let \(F_\Lambda \) be the class of ReLU blocks of width \(w\) with \(p = 2mw + w + m\) parameters. (a) For admissible \(\vartheta , \vartheta '\),

\[ d_\infty (f_\vartheta , f_{\vartheta '}) \le \beta _W R_K\| W - W'\| _{\rm op} + \beta _W\| b - b'\| + (\beta _W R_K + \beta )\| V - V'\| _{\rm op} + \| c - c'\| ; \]

(b) for every \(\varepsilon {\gt} 0\), \(N^{\mathrm{ext}}(F_\Lambda , d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F_\Lambda , d_\infty , \varepsilon ) \le p\log (1 + C_F/\varepsilon )\) with \(C_F = 2(2\beta _W R_K + \beta _W + \beta + 1)\max \{ \beta _W, \beta \} \) (‘def:relu-cover-const‘; the paper’s constant has the same shape, see there).

Proof ▶
Theorem 498
✓
#

If \(K\) is bounded then so is the state space \(K\) (as a metric space in its own right).

Proof ▶
Theorem 499
✓

A bounded set \(K\) of a finite-dimensional space has finite covering numbers: \(N^{\mathrm{ext}}(K, \varepsilon ) {\lt} \infty \) for \(\varepsilon {\gt} 0\) (external covering number of the state space \(K\) by points of \(K\); \(K\) is totally bounded since its closure is compact).

Proof ▶

(Telescoping estimate for contractive layers.) If every \(f \in F\) is \(\Lambda \)-Lipschitz with \(\Lambda {\lt} 1\) then \(N^{\mathrm{ext}}(F^l, d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(F, d_\infty , (1 - \Lambda )\varepsilon )^l\), since \(S_l(\Lambda ) = \sum _{i{\lt}l}\Lambda ^i \le 1/(1-\Lambda )\) in ‘lem:envelope-words‘.

Proof ▶
Theorem 501
✓
#

For \(N \ge 1\) in \(\mathbb N \cup \{ \infty \} \), \(\sum _{l{\lt}m} N^l \le m N^m\).

Proof ▶

\(N^{\mathrm{ext}}(F_\Lambda , d_\infty , \varepsilon ) \ge 1\) (the class is nonempty).

Proof ▶

(‘prop:relu-regimes‘(i): contractive layers, \(\Lambda {\lt} 1\).) Let \(K \ne \emptyset \) be bounded with \(\| x\| \le R_K\) on \(K\), and \(0 {\lt} \Lambda {\lt} 1\). Then ‘cond:p1-ucont‘ applies with the invariant set \(K\) itself (\(L = 0\), absorbing set \(K\)), and with \(m(\varepsilon ) = \lceil \log (2D_K/\varepsilon )/\log (1/\Lambda )\rceil \) (\(D_K = \mathrm{diam}\, K\)), for every \(\varepsilon {\gt} 0\) and every \(k\),

\[ N^{\mathrm{ext}}(B(k,F_\Lambda ), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(K, \varepsilon /2) + m(\varepsilon )\, N^{\mathrm{ext}}(F_\Lambda , d_\infty , (1-\Lambda )\varepsilon )^{m(\varepsilon )} {\lt} \infty , \]

which does not depend on \(k\); in particular \(\sup _k N^{\mathrm{ext}}(B(k,F_\Lambda ), d_\infty , \varepsilon ) {\lt} \infty \). (The paper’s \(k \ge m(\varepsilon )\) is not needed, cf. ‘cond:p1-ucont‘; the right-hand side is finite by ‘lem:relu-layer-covering‘ and the total boundedness of \(K\).)

Proof ▶

‘cond:p1-ucont‘ with \(c = \Lambda \), \(A = K\), \(L = 0\) and the bounded absorbing set \(K\); the short words are bounded by ‘lem:relu-words-covering-contractive‘ and ‘lem:relu-sum-pow-le‘; finiteness from ‘lem:relu-covering-univ-ne-top‘ and ‘lem:relu-layer-covering-log‘.

The \(k\)-independent majorant of case (i) at the scale of the empirical metric: \(N_\infty (\varepsilon ) := N^{\mathrm{ext}}(K, \varepsilon /4) + m(\varepsilon /2)\, N^{\mathrm{ext}}(F_\Lambda , d_\infty , (1-\Lambda )\varepsilon /2)^{m(\varepsilon /2)}\) (the factor \(2\) from \(N(A, d_S, \varepsilon ) \le N^{\mathrm{ext}}(A, d_\infty , \varepsilon /2)\)).

(Case (i), saturated profile: \(\mathsf V_k(S) = O(1)\).) Under the hypotheses of ‘prop:relu-regimes-i‘, if \(\varepsilon \mapsto \sqrt{\log N_\infty (\varepsilon )}\) is interval-integrable on \([0, D_K]\) then \(\mathsf V_k(S) \le \mathsf V_\infty := \int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon \) for all \(k\) and all samples \(S\) (case (i) of ‘prop:profiles‘).

Proof ▶

\(N(B(k,F), d_S, \varepsilon ) \le N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon /2) \le N_\infty (\varepsilon )\) by ‘prop:relu-regimes-i‘, and \(D_k(S) \le D_K\).

(‘prop:relu-regimes‘(ii): non-expanding layers, \(\Lambda \le 1\).) If \(K\) is compact and \(\Lambda \le 1\) then ‘cond:p1‘ (2c, non-expanding generators on a compact state space) applies: for every \(\varepsilon {\gt} 0\) and every \(k\), \(N^{\mathrm{ext}}(B(k,F_\Lambda ), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F_\Lambda \rangle }, d_\infty , \varepsilon ) {\lt} \infty \); in particular \(\sup _k N^{\mathrm{ext}}(B(k,F_\Lambda ), d_\infty , \varepsilon ) {\lt} \infty \).

Proof ▶

‘cond:p1-2c‘ on the compact state space \(K\).

(Case (ii), saturated profile: \(\mathsf V_k(S) = O(1)\).) Under the hypotheses of ‘prop:relu-regimes-ii‘, with \(N_\infty (\varepsilon ) := N(\overline{\langle F_\Lambda \rangle }, d_\infty , \varepsilon /2) {\lt} \infty \): if \(\int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) then \(\mathsf V_k(S) \le \int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon \) for all \(k\) and all samples \(S\) (case (i) of ‘prop:profiles‘, as in ‘lem:fp-profile‘).

Proof ▶

The non-expanding semigroup is equicontinuous, hence totally bounded in \(d_\infty \) (‘thm:caa‘); apply ‘lem:ode-profile-saturation-generic‘.

(Envelope profile of the ReLU class, all \(\Lambda \).) Let \(K\) be bounded with \(\| x\| \le R_K\) on \(K\), \(D_K \le \overline D\), \(\overline D {\gt} 0\), \(p = 2mw + w + m\) and \(C_F\) as in ‘lem:relu-layer-covering‘. Then for \(k \ge 1\) and every sample \(S\), with \(\Lambda _+ = \max \{ 1, \Lambda \} \),

\[ \mathsf V_k(S) \le \overline D\Bigl(\sqrt{\log (k+1)} + \sqrt{kp\log k} + k\sqrt{p\log \Lambda _+} + \sqrt{kp}\bigl(\sqrt{\log (1 + 2C_F/\overline D)} + \tfrac {\sqrt\pi }{2}\bigr)\Bigr) \]

(‘cor:envelope-profiles-a-one-add‘ with ‘lem:relu-layer-covering‘).

Proof ▶

(Case (ii), explicit envelope: \(\mathsf V_k(S) = O(\sqrt{kp\log k})\).) For \(\Lambda \le 1\), under the hypotheses of ‘lem:relu-envelope-profile‘,

\[ \mathsf V_k(S) \le \overline D\Bigl(\sqrt{\log (k+1)} + \sqrt{kp\log k} + \sqrt{kp}\bigl(\sqrt{\log (1 + 2C_F/\overline D)} + \tfrac {\sqrt\pi }{2}\bigr)\Bigr) . \]
Proof ▶

(‘prop:relu-regimes‘(iii), upper bound: expanding layers, \(\Lambda {\gt} 1\): \(\mathsf V_k(S) = O(k\sqrt{p\log \Lambda })\).) Under the hypotheses of ‘lem:relu-envelope-profile‘, for \(\Lambda {\gt} 1\),

\[ \mathsf V_k(S) \le \overline D\Bigl(\sqrt{\log (k+1)} + \sqrt{kp\log k} + k\sqrt{p\log \Lambda } + \sqrt{kp}\bigl(\sqrt{\log (1 + 2C_F/\overline D)} + \tfrac {\sqrt\pi }{2}\bigr)\Bigr) . \]
Proof ▶

(Depth profiles of ReLU networks by Lipschitz constant, upper bounds.) Let \(K \ne \emptyset \) be bounded with \(\| x\| \le R_K\) on \(K\) (\(R_K \ge 0\)), \(F = F_\Lambda \), \(p = 2mw + w + m\) and \(C_F\) as in ‘lem:relu-layer-covering‘.

  1. (Contractive, \(0 {\lt} \Lambda {\lt} 1\).) For every \(\varepsilon {\gt} 0\) and \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(K, \varepsilon /2) + m(\varepsilon ) N^{\mathrm{ext}}(F, d_\infty , (1-\Lambda )\varepsilon )^{m(\varepsilon )} {\lt} \infty \) with \(m(\varepsilon ) = \lceil \log (2D_K/\varepsilon )/\log (1/\Lambda )\rceil \), so \(\sup _k N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) {\lt} \infty \).

  2. (Non-expanding, \(\Lambda \le 1\).) If \(K\) is compact then for every \(\varepsilon {\gt} 0\) and \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon ) {\lt} \infty \); and for \(D_K \le \overline D\), \(\overline D {\gt} 0\), \(k \ge 1\), the envelope gives \(\mathsf V_k(S) \le \overline D(\sqrt{\log (k+1)} + \sqrt{kp\log k} + \sqrt{kp}(\sqrt{\log (1 + 2C_F/\overline D)} + \sqrt\pi /2)) = O(\sqrt{kp\log k})\).

  3. (Expanding, \(\Lambda {\gt} 1\).) For \(D_K \le \overline D\), \(\overline D {\gt} 0\), \(k \ge 1\), \(\mathsf V_k(S) \le \overline D(\sqrt{\log (k+1)} + \sqrt{kp\log k} + k\sqrt{p\log \Lambda } + \sqrt{kp}(\sqrt{\log (1 + 2C_F/\overline D)} + \sqrt\pi /2)) = O(k\sqrt{p\log \Lambda })\).

The lower bound of (iii) is ‘prop:relu-regimes-iii-lower‘; the saturated profiles \(\mathsf V_k(S) = O(1)\) of (i) and (ii) are ‘prop:relu-regimes-i-profile‘ and ‘prop:relu-regimes-ii-profile‘.

Proof ▶
Definition 512
✓
#

The clipping \(\Pi _{[0,1]}(x) = \max \{ 0, \min \{ 1, x\} \} \), a \(1\)-Lipschitz retraction of \(\mathbb R\) onto \([0,1]\).

Theorem 513
✓
#

\(\Pi _{[0,1]}(x) = x\) for \(x \in [0,1]\).

Proof ▶
Theorem 514
✓

\(\Pi _{[0,1]}\) is a \(1\)-Lipschitz retraction onto \([0,1]\) (‘def:ode-projection‘).

Proof ▶
Theorem 515
✓
#

\(x \mapsto ax + b\) is \(L\)-Lipschitz on \(\mathbb R\) when \(|a| \le L\).

Proof ▶
Definition 516
✓
#

The first expand-and-reset map of the computed illustration (‘sec:relu-computed‘), \(\eta = 1/32\): the piecewise-linear map with breakpoints \((0, 3/8), (\eta , 0), (1/4 - \eta , 1), (1/4, 3/8), (1, 3/8)\), i.e. \(g_0(x) = 3/8 - 12x\) on \([0, \eta ]\), \(= \tfrac {16}{3}(x - \eta )\) on \([\eta , 1/4 - \eta ]\), \(= 1 - 20(x - 1/4 + \eta )\) on \([1/4 - \eta , 1/4]\) and \(= 3/8\) on \([1/4, 1]\).

Definition 517
✓
#

The second expand-and-reset map, with breakpoints \((0, 5/8), (3/4, 5/8), (3/4 + \eta , 0), (1 - \eta , 1), (1, 5/8)\), i.e. \(g_1(x) = 5/8\) on \([0, 3/4]\), \(= 5/8 - 20(x - 3/4)\) on \([3/4, 3/4 + \eta ]\), \(= \tfrac {16}{3}(x - 3/4 - \eta )\) on \([3/4 + \eta , 1 - \eta ]\) and \(= 1 - 12(x - 1 + \eta )\) on \([1 - \eta , 1]\).

Theorem 518
✓
#

\(g_0\) maps \([0,1]\) into \([0,1]\).

Proof ▶
Theorem 519
✓
#

\(g_1\) maps \([0,1]\) into \([0,1]\).

Proof ▶
Theorem 520
✓
#

On \([0,1]\), \(g_0(x) = \max \{ -12x + 3/8, \min \{ \tfrac {16}{3}x - \tfrac 16, \max \{ 3/8, -20x + 43/8\} \} \} \) (a max–min of affine maps of slopes \(\le 20\)).

Proof ▶
Theorem 521
✓
#

On \([0,1]\), \(g_1(x) = \max \{ \min \{ 5/8, -20x + 125/8\} , \min \{ \tfrac {16}{3}x - \tfrac {25}{6}, -12x + 101/8\} \} \).

Proof ▶

\(g_0\) is \(20\)-Lipschitz on \([0,1]\) (max–min of \(20\)-Lipschitz affine maps).

Proof ▶

\(g_1\) is \(20\)-Lipschitz on \([0,1]\).

Proof ▶
Definition 524
✓
#

\(g_0\) as a self-map of the state space \([0,1]\).

Definition 525
✓
#

\(g_1\) as a self-map of the state space \([0,1]\).

\(g_0 : [0,1] \to [0,1]\) is \(20\)-Lipschitz.

Proof ▶

\(g_1 : [0,1] \to [0,1]\) is \(20\)-Lipschitz.

Proof ▶
Definition 528
✓
#

The parameters of a one-dimensional ReLU block with \(w\) units of input weights \(u_i\), thresholds \(t_i\), output weights \(v_i\) and bias \(c\): \(W = (u_i)_i\), \(b = (-t_i)_i\), \(V = (v_i)_i\) (as a row), so that \(V\, \mathrm{relu}(Wx + b) + c = \sum _i v_i\, \mathrm{relu}(u_i x - t_i) + c\).

\(f_\vartheta (x) = \Pi _K\bigl(\sum _i v_i\max \{ u_ix - t_i, 0\} + c\bigr)\) for the parameters ‘def:relu-unit-param‘.

Proof ▶
Definition 530
✓
#

Input weights of the expand-and-reset blocks at width \(4 + w'\): \(u = (1,1,1,1,0,\dots ,0)\).

Definition 531
✓
#

Thresholds of \(g_0\): \(t = (0, \eta , 1/4 - \eta , 1/4, 0, \dots , 0)\).

Definition 532
✓
#

Output weights of \(g_0\) (the slope increments at the breakpoints): \(v = (-12, 52/3, -76/3, 20, 0, \dots , 0)\).

Definition 533
✓
#

Thresholds of \(g_1\): \(t = (3/4, 3/4 + \eta , 1 - \eta , 0, 0, \dots , 0)\).

Definition 534
✓
#

Output weights of \(g_1\): \(v = (-20, 76/3, -52/3, 0, 0, \dots , 0)\).

The ReLU parameters of \(g_0\) (bias \(c = 3/8\)).

The ReLU parameters of \(g_1\) (bias \(c = 5/8\)).

Theorem 537
✓
#

On \([0,1]\), \(g_0(x) = -12\, \mathrm{relu}(x) + \tfrac {52}{3}\mathrm{relu}(x - \eta ) - \tfrac {76}{3}\mathrm{relu}(x - 1/4 + \eta ) + 20\, \mathrm{relu}(x - 1/4) + 3/8\).

Proof ▶
Theorem 538
✓
#

On \([0,1]\), \(g_1(x) = -20\, \mathrm{relu}(x - 3/4) + \tfrac {76}{3} \mathrm{relu}(x - 3/4 - \eta ) - \tfrac {52}{3}\mathrm{relu}(x - 1 + \eta ) + 5/8\).

Proof ▶
Theorem 539
✓

The unit sum of \(g_0\) at width \(4 + w'\) (the padding units vanish).

Proof ▶
Theorem 540
✓

The unit sum of \(g_1\) at width \(4 + w'\).

Proof ▶

(\(g_0\) is a ReLU block of width \(4 + w'\).) With the clipping \(\Pi _{[0,1]}\), \(f_{\vartheta _0} = g_0\) on \([0,1]\).

Proof ▶
Proof ▶

Weight norms of the representation of \(g_0\): \(\| W\| _{\rm op} = \| u\| = 2\), \(\| b\| = \| t\| \le 2\), \(\| V\| _{\rm op} = \| v\| \le 41\), \(\| c\| = 3/8 \le 2\).

Proof ▶

Weight norms of the representation of \(g_1\): \(\| W\| _{\rm op} = 2\), \(\| b\| \le 2\), \(\| V\| _{\rm op} \le 41\), \(\| c\| = 5/8 \le 2\).

Proof ▶
Definition 545
✓
#

The two generators \(f = (g_0, g_1)\).

Definition 546
✓
#

The chambers \(U_0 = [0, 1/4]\), \(U_1 = [3/4, 1]\).

Definition 547
✓
#

The coding cores \(V_0 = [\eta , 1/4 - \eta ]\), \(V_1 = [3/4 + \eta , 1 - \eta ]\).

Definition 548
✓
#

The anchors \(a_0 = 3/8\), \(a_1 = 5/8\).

Definition 549
✓
#

The marker \(q = 1/2\).

Theorem 550
✓

\(V_i \subseteq U_i\).

Proof ▶
Theorem 551
✓
#

(Disjoint chambers.) \(U_0 \cap U_1 = \emptyset \).

Proof ▶

(Reset.) \(g_i(x) = a_i\) for \(x \notin U_i\): \(g_0 = 3/8\) outside \([0,1/4]\) and \(g_1 = 5/8\) outside \([3/4, 1]\).

Proof ▶
Theorem 553
✓

The anchors lie outside both chambers.

Proof ▶
Theorem 554
✓

\(g_i(A) \subseteq A\) for \(A = \{ a_0, a_1\} \) (each anchor is reset to \(a_i\)).

Proof ▶

(Coding cores.) \(g_i(V_i) = [0,1] \supseteq \{ q\} \cup V_0 \cup V_1\): for \(y \in [0,1]\), \(x = \eta + \tfrac {3}{16}y \in V_0\) has \(g_0(x) = y\), and \(x = 3/4 + \eta + \tfrac {3}{16}y \in V_1\) has \(g_1(x) = y\).

Proof ▶
Theorem 556
✓

(Marker separation.) \(d(q, a_i) = 1/8\) for \(i = 0, 1\).

Proof ▶

(The expand-and-reset maps satisfy ‘cond:e2-pingpong‘.) With the chambers, cores, anchors and marker above and separation \(\alpha = 1/8\): \(N^{\mathrm{ext}}(B(k, \{ g_0, g_1\} ), d_\infty , \varepsilon ) \ge 2^k\) for all \(k\) and \(2\varepsilon {\lt} 1/8\), and the words of each length are pairwise distinct.

Proof ▶

For \(\beta _W \ge 41\), \(\beta \ge 2\), \(\Lambda \ge 20\) and width \(4 + w'\), \(g_0, g_1 \in F_\Lambda \) on \(K = [0,1]\) with the clipping retraction.

Proof ▶

(‘prop:relu-regimes‘(iii), lower bound.) For \(m = 1\), \(K = [0,1]\) with the clipping retraction, width \(w \ge 4\), \(\Lambda \ge 20\), and \(\beta _W \ge 41\), \(\beta \ge 2\) (at least the weight norms of the representations of the two expand-and-reset maps), the class \(F_\Lambda \) contains \(g_0, g_1\), which satisfy ‘cond:e2-pingpong‘ with two generators and separation \(1/8\); hence

\[ N^{\mathrm{ext}}(B(k, F_\Lambda ), d_\infty , \varepsilon ) \ge 2^k \quad \text{for all } k \text{ and all } \varepsilon {\lt} 1/16 . \]

(The paper states \(w \ge 5\); the two maps have three interior breakpoints each, so width \(4\) suffices.)

Proof ▶

Write \(w = 4 + w'\); ‘lem:relu-er-pingpong‘ gives the bound for \(\{ g_0, g_1\} \), and \(B(k, \{ g_0,g_1\} ) \subseteq B(k, F_\Lambda )\) by ‘lem:relu-er-mem-class‘.

7.4 Deep ReLU networks: Rademacher complexity of a shattered sample (Appendix K, lem:shatter-rademacher)

Theorem 560
✓

(A shattered sample has Rademacher complexity at least half the margin, general form.) Let \(S = (x_1, \dots , x_n)\) with \(n \ge 1\), \(G \subseteq \mathbb R^{\mathcal X}\) and \(a_0 \le a_1\). Suppose that \(G\) realizes every two-valued labeling of the sample: for every \(c \in \{ 0,1\} ^n\) there is \(g \in G\) with \(g(x_i) = a_{c_i}\) for all \(i\). Suppose moreover that for every sign pattern \(\sigma \) the Rademacher averages \(\{ \frac1n \sum _i \sigma _i g(x_i) : g \in G\} \) are bounded above (as in lem:emp-rademacher-mono). Then

\[ \hat{\mathfrak R}_S(G) \ge \frac{a_1 - a_0}{2}. \]

(This is lem:shatter-rademacher with the boundedness of \(G\) on the sample replaced by the weaker hypothesis on the Rademacher averages; the hypothesis \(a_0 \le a_1\) is not used in the proof.)

Proof ▶

Step 1. For a sign pattern \(\sigma \) let \(\psi (\sigma ) := \frac1n \sum _i \sigma _i a_{c_i}\) with \(c_i = 1\) exactly when \(\sigma _i = 1\). The labeling \(c\) is realized by some \(g \in G\), so \(\psi (\sigma ) \le \sup _{g \in G} \frac1n \sum _i \sigma _i g(x_i)\).

Step 2. \(\psi (\sigma ) + \psi (-\sigma ) = a_1 - a_0\): the \(i\)-th terms add up to \(a_1 - a_0\) for either value of \(\sigma _i\).

Step 3. Reindexing by \(\sigma \mapsto -\sigma \), \(2 \sum _\sigma \psi (\sigma ) = \sum _\sigma (\psi (\sigma ) + \psi (-\sigma )) = 2^n (a_1 - a_0)\).

Step 4. Average the inequality of Step 1 over the sign patterns.

Theorem 561
✓

(Rademacher complexity of a shattered sample.) Let \(G\) be a class of real-valued functions that is bounded on the sample \(S = (x_1, \dots , x_n)\), \(n \ge 1\) (there is \(C\) with \(|g(x_i)| \le C\) for all \(g \in G\) and \(i \le n\)), and let \(a_0 \le a_1\). If for every \(c \in \{ 0,1\} ^n\) there is \(g \in G\) with \(g(x_i) = a_{c_i}\) for all \(i\), then

\[ \hat{\mathfrak R}_S(G) \ge \frac{a_1 - a_0}{2}. \]

(The boundedness on the sample gives the hypothesis of lem:shatter-rademacher-general that the Rademacher averages are bounded above.)

Proof ▶

(Shattered sample, composite class.) Let \(H \subseteq \mathbb R^{\mathcal X}\) be an output-layer class, \(B \subseteq \mathcal X^{\mathcal X}\) a hidden class, \(h \in H\) and \(a_0 \le a_1\). If for every labeling \(c \in \{ 0,1\} ^n\) there is \(f \in B\) with \(h(f(x_i)) = a_{c_i}\) for all \(i\), and \(|g(x_i)| \le C\) for all \(g \in H \circ B\) and \(i \le n\), then \(\hat{\mathfrak R}_S(H \circ B) \ge (a_1 - a_0)/2\).

Proof ▶

Apply lem:shatter-rademacher to \(G = H \circ B\) with the functions \(h \circ f\).

7.5 Deep ReLU networks: sort–hold blocks separated on a sample (Appendix K, lem:relu-sort-hold)

Definition 563
✓
#

The first expand–sort–hold map, \(f_0(x) = 2\, \mathrm{relu}(x) - 2\, \mathrm{relu}(x - \tfrac 38) + \mathrm{relu}(x - \tfrac 34)\).

Definition 564
✓
#

The second expand–sort–hold map, \(f_1(x) = 2\, \mathrm{relu}(x) + 2\, \mathrm{relu}(x - \tfrac 14) - 4\, \mathrm{relu}(x - \tfrac 38) - 2\, \mathrm{relu}(x - \tfrac 58) + 3\, \mathrm{relu}(x - \tfrac 34)\).

Theorem 565
✓
#

For \(x \ge 0\) (in particular on \([0,1]\)): \(f_0(x) = 2x\) on \([0, \tfrac 38]\), \(= \tfrac 34\) on \([\tfrac 38, \tfrac 34]\), and \(= x\) for \(x \ge \tfrac 34\).

Proof ▶
Theorem 566
✓
#

For \(x \ge 0\) (in particular on \([0,1]\)): \(f_1(x) = 2x\) on \([0, \tfrac 14]\), \(= 4x - \tfrac 12\) on \([\tfrac 14, \tfrac 38]\), \(= 1\) on \([\tfrac 38, \tfrac 58]\), \(= \tfrac 94 - 2x\) on \([\tfrac 58, \tfrac 34]\), and \(= x\) for \(x \ge \tfrac 34\).

Proof ▶
Theorem 567
✓
#

\(f_0\) maps \([0,1]\) into \([0,1]\).

Proof ▶
Theorem 568
✓
#

\(f_1\) maps \([0,1]\) into \([0,1]\).

Proof ▶
Theorem 569
✓

\(|f_0(x) - f_0(y)| \le 2|x - y|\) for \(x, y \ge 0\) (the slopes of \(f_0\) are \(2, 0, 1\)).

Proof ▶

Case analysis on the linear pieces containing \(x\) and \(y\); every case is a linear inequality.

Theorem 570
✓

\(|f_1(x) - f_1(y)| \le 4|x - y|\) for \(x, y \ge 0\) (the slopes of \(f_1\) are \(2, 4, 0, -2, 1\)).

Proof ▶

Case analysis on the linear pieces containing \(x\) and \(y\); every case is a linear inequality.

Definition 571
✓
#

\(f_0\) as a self-map of the state space \([0,1]\).

Definition 572
✓
#

\(f_1\) as a self-map of the state space \([0,1]\).

Theorem 573
✓

\(f_0 : [0,1] \to [0,1]\) is \(2\)-Lipschitz.

Proof ▶
Theorem 574
✓

\(f_1 : [0,1] \to [0,1]\) is \(4\)-Lipschitz.

Proof ▶
Definition 575
✓
#

Input weights of both expand–sort–hold blocks at width \(5 + w'\): the vector \(u = (1,1,1,1,1,0,\dots ,0)\).

Definition 576
✓
#

Thresholds of both blocks: \(t = (0, \tfrac 14, \tfrac 38, \tfrac 58, \tfrac 34, 0, \dots , 0)\).

Definition 577
✓
#

Output weights of \(f_0\): \(v = (2, 0, -2, 0, 1, 0, \dots , 0)\).

Definition 578
✓
#

Output weights of \(f_1\): \(v = (2, 2, -4, -2, 3, 0, \dots , 0)\).

The ReLU parameters of \(f_0\) at width \(5 + w'\) (bias \(c = 0\)).

The ReLU parameters of \(f_1\) at width \(5 + w'\) (bias \(c = 0\)).

The unit sum of \(f_0\) at width \(5 + w'\) (the units with zero output weight and the padding units vanish).

Proof ▶

The unit sum of \(f_1\) at width \(5 + w'\).

Proof ▶

(\(f_0\) is a ReLU block of width \(5 + w'\).) With the clipping \(\Pi _{[0,1]}\), thresholds \(0, \tfrac 14, \tfrac 38, \tfrac 58, \tfrac 34\), output weights \((2, 0, -2, 0, 1)\) and \(c = 0\): \(f_{\vartheta _0} = f_0\) on \([0,1]\).

Proof ▶

(\(f_1\) is a ReLU block of width \(5 + w'\).) With the clipping \(\Pi _{[0,1]}\), thresholds \(0, \tfrac 14, \tfrac 38, \tfrac 58, \tfrac 34\), output weights \((2, 2, -4, -2, 3)\) and \(c = 0\): \(f_{\vartheta _1} = f_1\) on \([0,1]\).

Proof ▶

Weight norms of the representation of \(f_0\): \(\| W\| _{\rm op} = \| u\| = \sqrt5 \le 7\), \(\| b\| = \| t\| = \sqrt{74}/8 \le 2\), \(\| V\| _{\rm op} = \| v\| = 3 \le 7\), \(\| c\| = 0 \le 2\).

Proof ▶

Weight norms of the representation of \(f_1\): \(\| W\| _{\rm op} = \sqrt5 \le 7\), \(\| b\| = \sqrt{74}/8 \le 2\), \(\| V\| _{\rm op} = \| v\| = \sqrt{37} \le 7\), \(\| c\| = 0 \le 2\).

Proof ▶
Definition 587
✓
#

The two generators \(f = (f_0, f_1)\), as self-maps of \([0,1]\).

(‘lem:relu-sort-hold‘(i), width \(5 + w'\).) For \(\beta _W \ge 7\), \(\beta \ge 2\), \(\Lambda \ge 4\) and width \(5 + w'\), \(f_0, f_1 \in F_\Lambda \) on \(K = [0,1]\) with the clipping retraction.

Proof ▶

(‘lem:relu-sort-hold‘(i).) For every width \(w \ge 5\), \(\beta _W \ge 7\), \(\beta \ge 2\) and \(\Lambda \ge 4\), \(f_0, f_1 \in F_\Lambda \) on \(K = [0,1]\) with the clipping retraction.

Proof ▶
Definition 590
✓
#

The two levels \(a_0 = \tfrac 34\), \(a_1 = 1\).

(Expansion zone.) \(f_i(x) = 2x\) for \(x \in [0, \tfrac 14]\), \(i = 0, 1\).

Proof ▶

(Gate.) \(f_i(\tfrac 12) = a_i\), \(i = 0, 1\): \(f_0(\tfrac 12) = \tfrac 34\) and \(f_1(\tfrac 12) = 1\).

Proof ▶

(Hold zone.) Both maps fix both levels: \(f_i(a_s) = a_s\) for \(i, s \in \{ 0, 1\} \).

Proof ▶
Definition 594
✓
#

The sample points \(x_j = 2^{-(j+1)} \in [0,1]\), \(j \ge 0\).

Theorem 595
✓
#

\(x_j = (1/2)^{j+1}\) as a real number.

Proof ▶
Definition 596
✓
#

For a word \(u = (u_0, \dots , u_{k-1}) \in \{ 0,1\} ^k\), the composition \(f_u = f_{u_{k-1}} \circ \cdots \circ f_{u_0}\) (the letter \(u_0\) acts first; ‘def:word-of‘ for the list \((u_0, \dots , u_{k-1})\)).

\(f_u \in B(k, \{ f_0, f_1\} )\) for every word \(u \in \{ 0,1\} ^k\).

Proof ▶

\(f_{(u_0, u_1, \dots , u_k)} = f_{(u_1, \dots , u_k)} \circ f_{u_0}\).

Proof ▶

Every composition fixes both levels: \(f_u(a_s) = a_s\).

Proof ▶

The set \(\{ a_s\} \) is invariant under both generators (‘lem:relu-sort-hold-hold‘), hence under every word (‘lem:wordof-mem-of-invariant‘).

(‘lem:relu-sort-hold‘(ii): the composition writes the word on the sample.) For every word \(u \in \{ 0,1\} ^k\) and every \(j {\lt} k\), \(f_u(x_j) = a_{u_j}\), where \(x_j = 2^{-(j+1)}\).

Proof ▶

Induction on \(k\), peeling off the first letter: \(f_u = f_{u'} \circ f_{u_0}\) with \(u' = (u_1, \dots , u_{k-1})\). If \(j = 0\) then \(f_{u_0}(x_0) = f_{u_0}(\tfrac 12) = a_{u_0}\) (gate), which every later layer fixes (hold). If \(j \ge 1\) then \(x_j \le \tfrac 14\), so \(f_{u_0}(x_j) = 2x_j = x_{j-1}\) (expansion), and \(f_{u'}(x_{j-1}) = a_{u'_{j-1}} = a_{u_j}\) by induction.

(‘lem:relu-sort-hold‘(iii): separation on the sample.) On the sample \(S = (x_0, \dots , x_{k-1})\), for all words \(u, v \in \{ 0,1\} ^k\),

\[ d_S(f_u, f_v)^2 = \frac1{16}\, \frac{\# \{ j : u_j \ne v_j\} }{k} . \]
Proof ▶

By (ii), \(d(f_u(x_j), f_v(x_j)) = |a_{u_j} - a_{v_j}|\), which is \(\tfrac 14\) if \(u_j \ne v_j\) and \(0\) otherwise.

Let \(F\) be any hidden-layer class on \([0,1]\) that contains \(f_0\) and \(f_1\), \(H_R = \{ x \mapsto w\, x : |w| \le R\} \) with \(R \ge 0\), \(k \ge 1\) and \(S = (x_0, \dots , x_{k-1})\). Then \(\hat{\mathfrak R}_S(H_R \circ B(k, F)) \ge R/8\).

Proof ▶

The functions \(x \mapsto R f_u(x)\), \(u \in \{ 0,1\} ^k\), belong to \(H_R \circ B(k,F)\) and realize every labeling of the sample with the two values \(R a_0 = \tfrac 34 R\) and \(R a_1 = R\) (by (ii)); all functions of the class are bounded by \(R\) on \([0,1]\). Apply ‘lem:shatter-rademacher-comp‘: the lower bound is \((R - \tfrac 34 R)/2 = R/8\).

(‘lem:relu-sort-hold‘(iii): Rademacher lower bound for the two-map class.) For the linear output layers \(H_R = \{ x \mapsto w\, x : |w| \le R\} \), \(R \ge 0\), every \(k \ge 1\) and the sample \(S = (x_0, \dots , x_{k-1})\),

\[ \hat{\mathfrak R}_S\bigl(H_R \circ B(k, \{ f_0, f_1\} )\bigr) \ge \frac R8 . \]
Proof ▶

(‘lem:relu-sort-hold‘(iii): Rademacher lower bound for \(F_\Lambda \).) For \(K = [0,1]\) with the clipping retraction, width \(w \ge 5\), \(\beta _W \ge 7\), \(\beta \ge 2\), \(\Lambda \ge 4\), the linear output layers \(H_R = \{ x \mapsto w\, x : |w| \le R\} \), \(R \ge 0\), every \(k \ge 1\) and the sample \(S = (x_0, \dots , x_{k-1})\),

\[ \hat{\mathfrak R}_S\bigl(H_R \circ B(k, F_\Lambda )\bigr) \ge \frac R8 . \]
Proof ▶

(Expand–sort–hold ReLU blocks: separation on the sample.) Let \(K = [0,1]\) with the clipping retraction, \(a_0 = \tfrac 34\), \(a_1 = 1\), and

\[ f_0(x) = 2\, \mathrm{relu}(x) - 2\, \mathrm{relu}(x - \tfrac 38) + \mathrm{relu}(x - \tfrac 34), \]
\[ f_1(x) = 2\, \mathrm{relu}(x) + 2\, \mathrm{relu}(x - \tfrac 14) - 4\, \mathrm{relu}(x - \tfrac 38) - 2\, \mathrm{relu}(x - \tfrac 58) + 3\, \mathrm{relu}(x - \tfrac 34) . \]

On \([0,1]\): \(f_0(x) = 2x\) on \([0, \tfrac 38]\), \(= \tfrac 34\) on \([\tfrac 38, \tfrac 34]\), \(= x\) on \([\tfrac 34, 1]\); \(f_1(x) = 2x\) on \([0, \tfrac 14]\), \(= 4x - \tfrac 12\) on \([\tfrac 14, \tfrac 38]\), \(= 1\) on \([\tfrac 38, \tfrac 58]\), \(= \tfrac 94 - 2x\) on \([\tfrac 58, \tfrac 34]\), \(= x\) on \([\tfrac 34, 1]\). Both map \([0,1]\) into itself.

  1. (Membership.) \(f_0\) is \(2\)-Lipschitz, \(f_1\) is \(4\)-Lipschitz, and both are ReLU blocks of width \(5\), of the form \(x \mapsto \Pi _K(V\, \mathrm{relu}(Wx + b) + c)\) (thresholds \(0, \tfrac 14, \tfrac 38, \tfrac 58, \tfrac 34\); output weights \((2, 0, -2, 0, 1)\) and \((2, 2, -4, -2, 3)\); \(c = 0\)). Hence \(f_0, f_1 \in F_\Lambda \) for every width \(w \ge 5\), \(\beta _W \ge 7\), \(\beta \ge 2\), \(\Lambda \ge 4\).

  2. (The composition writes the word on the sample.) For \(k \ge 1\) let \(x_j := 2^{-(j+1)}\), \(j = 0, \dots , k-1\). For every word \(u = (u_0, \dots , u_{k-1}) \in \{ 0,1\} ^k\) and \(f_u := f_{u_{k-1}} \circ \cdots \circ f_{u_0} \in B(k, \{ f_0, f_1\} )\) (so \(u_0\) is applied first), \(f_u(x_j) = a_{u_j}\) for all \(j\).

  3. (Separation and lower bound on the sample.) On the sample \(S = (x_0, \dots , x_{k-1})\): \(d_S(f_u, f_v)^2 = \tfrac 1{16}\, \# \{ j : u_j \ne v_j\} /k\). For the linear output layers \(H_R = \{ x \mapsto w\, x : |w| \le R\} \), \(R \ge 0\), and every \(k \ge 1\),

    \[ \hat{\mathfrak R}_S\bigl(H_R \circ B(k, \{ f_0, f_1\} )\bigr) \ge \frac R8 , \]

    and the same bound holds for \(H_R \circ B(k, F_\Lambda )\) for the parameter ranges in (i).

The Lean statement lists, in this order: the two formulas for \(f_0\) and for \(f_1\) on \([0,1]\); (i); (ii); the two claims of (iii).

Proof ▶

7.6 Deep ReLU networks: load–count–sort blocks shatter a sample (Appendix K, prop:relu-shatter)

Definition 606
✓
#

The linear map \(\mathbb R^2 \to \mathbb R^w\) with columns \(\alpha , \gamma \in \mathbb R^w\): \((z, y) \mapsto z\, \alpha + y\, \gamma \), i.e. the matrix with rows \((\alpha _i, \gamma _i)\).

Theorem 607
✓
#

\((W x)_i = \alpha _i x_0 + \gamma _i x_1\) for the map ‘def:relu-shatter-col-map‘.

Proof ▶
Definition 608
✓
#

The linear map \(\mathbb R^w \to \mathbb R^2\) with rows \(u, v \in \mathbb R^w\): \(r \mapsto (\langle u, r\rangle , \langle v, r\rangle )\).

Theorem 609
✓
#

\((V r)_0 = \sum _i u_i r_i\) for the map ‘def:relu-shatter-row-map‘.

Proof ▶
Theorem 610
✓
#

\((V r)_1 = \sum _i v_i r_i\) for the map ‘def:relu-shatter-row-map‘.

Proof ▶
Theorem 611
✓
#

(Operator norm bounded by the Frobenius norm.) If \(\sum _i \alpha _i^2 + \sum _i \gamma _i^2 \le C^2\) with \(C \ge 0\) then the map ‘def:relu-shatter-col-map‘ has \(\| W\| _{\rm op} \le C\): by the Cauchy–Schwarz inequality, \(\| x_0\alpha + x_1\gamma \| \le |x_0|\| \alpha \| + |x_1|\| \gamma \| \le \sqrt{\| \alpha \| ^2 + \| \gamma \| ^2}\, \| x\| \).

Proof ▶
Theorem 612
✓
#

(Operator norm bounded by the Frobenius norm.) If \(\sum _i u_i^2 + \sum _i v_i^2 \le C^2\) with \(C \ge 0\) then the map ‘def:relu-shatter-row-map‘ has \(\| V\| _{\rm op} \le C\): \(\| V r\| ^2 = \langle u, r\rangle ^2 + \langle v, r\rangle ^2 \le (\| u\| ^2 + \| v\| ^2)\| r\| ^2\).

Proof ▶
Definition 613
✓

The parameters of a ReLU block of width \(w\) on \(\mathbb R^2\) with input weights \((\alpha _i, \gamma _i)\), thresholds \(t_i\), output weights \(u_i\) (first coordinate) and \(v_i\) (second coordinate), and \(c = 0\): \(W\) is ‘def:relu-shatter-col-map‘, \(b = (-t_i)_i\), \(V\) is ‘def:relu-shatter-row-map‘, so that \(V\, \mathrm{relu}(Wx + b) = \bigl(\sum _i u_i\, \mathrm{relu}(\alpha _i z + \gamma _i y - t_i), \sum _i v_i\, \mathrm{relu}(\alpha _i z + \gamma _i y - t_i)\bigr)\) for \(x = (z, y)\).

For the parameters ‘def:relu-shatter-plane-param‘ and \(x = (z, y) \in K\), \(f_\vartheta (x) = \Pi _K\bigl(\sum _i u_i \max \{ \alpha _i z + \gamma _i y - t_i, 0\} , \sum _i v_i \max \{ \alpha _i z + \gamma _i y - t_i, 0\} \bigr)\).

Proof ▶

A ReLU block \(f_\vartheta (x) = \Pi _K(V\, \mathrm{relu}(Wx + b) + c)\) is \(\| V\| _{\rm op}\| W\| _{\rm op}\)-Lipschitz: it is the composition of the \(1\)-Lipschitz maps \(\Pi _K\) and \(\mathrm{relu}\) with the affine maps \(x \mapsto Wx + b\) and \(r \mapsto Vr + c\).

Proof ▶
Definition 616
✓
#

The coordinatewise clipping of \(\mathbb R^2\) to the unit square: \(\Pi _K(z, y) = (\mathrm{clip}(z), \mathrm{clip}(y))\) with \(\mathrm{clip}(a) = \max \{ 0, \min \{ 1, a\} \} \) (‘def:relu-clip-unit‘).

Theorem 617
✓

\(\Pi _K(x)_i = \mathrm{clip}(x_i)\).

Proof ▶
Definition 618
✓
#

The state space \(K = [0,1]^2 \subseteq \mathbb R^2\). A state is written \((z, y)\): the track \(z\) is coordinate \(0\) and the register \(y\) is coordinate \(1\).

\(\Pi _K\) is a \(1\)-Lipschitz retraction of \(\mathbb R^2\) (Euclidean norm) onto \(K = [0,1]^2\) (‘def:ode-projection‘): it maps into \(K\), is the identity on \(K\), and \(|\mathrm{clip}(a) - \mathrm{clip}(b)| \le |a - b|\) coordinatewise.

Proof ▶
Theorem 620
✓

\(\| x\| \le \sqrt2\) for \(x \in K = [0,1]^2\).

Proof ▶
Definition 621
✓
#

The track map \(P(z) = 2\, \mathrm{relu}(z) - 4\, \mathrm{relu}(z - \tfrac 3{16}) + 4\, \mathrm{relu}(z - \tfrac 14) - \tfrac 52\, \mathrm{relu}(z - \tfrac 12) + \tfrac 32\, \mathrm{relu}(z - \tfrac 34)\).

Definition 622
✓
#

The loading window \(\psi (z) = 32\, \mathrm{relu}(z - \tfrac 3{32}) - 32\, \mathrm{relu}(z - \tfrac 18) - 16\, \mathrm{relu}(z - \tfrac 3{16}) + 16\, \mathrm{relu}(z - \tfrac 14)\).

Definition 623
✓
#

The sorting term \(s(z, y) = \mathrm{relu}\bigl(2(z - \tfrac 12) + \tfrac 14(y - \tfrac 14)\bigr) - \mathrm{relu}\bigl(2(z - \tfrac 12) + \tfrac 14(y - \tfrac 34)\bigr)\).

Definition 624
✓
#

The shift of the register: \(E(y) = \mathrm{clip}\bigl(4\, \mathrm{relu}(y) - 8\, \mathrm{relu}(y - \tfrac 12)\bigr)\) (the tent map on \([0,1]\)).

Definition 625
✓

The track coordinate of one layer: \((z, y) \mapsto \mathrm{clip}\bigl(P(z) + s(z, y)\bigr)\).

Definition 626
✓

The register coordinate of one layer with parameter \(\theta \): \((z, y) \mapsto \mathrm{clip}\bigl(4\, \mathrm{relu}(y) - 8\, \mathrm{relu}(y - \tfrac 12) + \theta \, \psi (z)\bigr)\).

Theorem 627
✓
#

(Fact 1.) \(P(z) = 2z\) for \(z \in [0, \tfrac 3{16}]\).

Proof ▶
Theorem 628
✓
#

(Facts 2 and 3.) \(P(z) = 2z - \tfrac 14\) for \(z \in [\tfrac 14, \tfrac 12]\); in particular \(P(\tfrac 12) = \tfrac 34\).

Proof ▶
Theorem 629
✓
#

(Fact 4.) \(P(z) = z - \tfrac 18\) for \(z \ge \tfrac 34\).

Proof ▶
Theorem 630
✓
#

(Facts 1 and 2.) \(s(z, y) = 0\) for \(z \le \tfrac 38\) and \(y \le 1\).

Proof ▶
Theorem 631
✓
#

(Fact 3.) \(s(\tfrac 12, y) = 0\) for \(y \le \tfrac 14\).

Proof ▶
Theorem 632
✓
#

(Fact 3.) \(s(\tfrac 12, y) = \tfrac 18\) for \(y \ge \tfrac 34\).

Proof ▶
Theorem 633
✓
#

(Fact 4.) \(s(z, y) = \tfrac 18\) for \(z \ge \tfrac 34\) and \(y \ge 0\).

Proof ▶
Theorem 634
✓
#

(Fact 5.) \(\psi (z) = 0\) for \(z \le \tfrac 3{32}\).

Proof ▶
Theorem 635
✓
#

(Fact 5.) \(\psi (z) = 1\) for \(z \in [\tfrac 18, \tfrac 3{16}]\).

Proof ▶
Theorem 636
✓
#

(Fact 5.) \(\psi (z) = 0\) for \(z \ge \tfrac 14\).

Proof ▶
Theorem 637
✓

(Fact 6.) \(E(u/4) = u\) for \(u \in [0,1]\).

Proof ▶
Theorem 638
✓

(Fact 6.) \(E(0) = 0\).

Proof ▶
Theorem 639
✓

(Fact 6.) \(E(1 - u/4) = u\) for \(u \in [0,1]\).

Proof ▶

(Wait and load, track.) For \(z \in [0, \tfrac 3{16}]\) and \(y \le 1\) the new track is \(\mathrm{clip}(P(z) + s(z, y)) = 2z\).

Proof ▶

(Wait, register.) For \(z \le \tfrac 3{32}\) and \(y = 0\) the new register is \(0\), for every \(\theta \).

Proof ▶

(Load, register.) For \(z \in [\tfrac 18, \tfrac 3{16}]\), \(y = 0\) and \(\theta \in [0, \tfrac 14]\) the new register is \(\theta \).

Proof ▶

(Count, track.) For \(z \in [\tfrac 14, \tfrac 38]\) and \(y \le 1\) the new track is \(2z - \tfrac 14\).

Proof ▶

(Count, register.) For \(z \ge \tfrac 14\) the new register is \(E(y)\), for every \(\theta \).

Proof ▶

(Sort.) For \(z = \tfrac 12\) and \(y \le \tfrac 14\) the new track is \(\tfrac 34\).

Proof ▶

(Sort.) For \(z = \tfrac 12\) and \(y \ge \tfrac 34\) the new track is \(\tfrac 78\).

Proof ▶

(Hold.) For \(z \in [\tfrac 34, 1]\) and \(y \ge 0\) the new track is \(z\); in particular the values \(\tfrac 34\) and \(\tfrac 78\) are kept by every layer.

Proof ▶
Definition 648
✓
#

Input weights of the \(11 + w'\) units on the track \(z\): \(\alpha = (1,1,1,1,1,1,1;\ 0,0;\ 2,2;\ 0,\dots ,0)\) (seven track units, two register units, two sort units, \(w'\) zero units).

Definition 649
✓
#

Input weights of the units on the register \(y\): \(\gamma = (0,0,0,0,0,0,0;\ 1,1;\ \tfrac 14,\tfrac 14;\ 0,\dots ,0)\).

Definition 650
✓
#

Thresholds of the units (\(b = -t\)): \(t = (0, \tfrac 3{32}, \tfrac 18, \tfrac 3{16}, \tfrac 14, \tfrac 12, \tfrac 34;\ 0, \tfrac 12; \tfrac {17}{16}, \tfrac {19}{16};\ 0,\dots ,0)\).

Definition 651
✓
#

Output weights for the track coordinate: \(v^z = (2, 0, 0, -4, 4, -\tfrac 52, \tfrac 32;\ 0, 0;\ 1, -1;\ 0,\dots ,0)\).

Definition 652
✓
#

Output weights for the register coordinate, the only weights that depend on \(\theta \): \(v^y_\theta = (0, 32\theta , -32\theta , -16\theta , 16\theta , 0, 0;\ 4, -8; 0, 0;\ 0,\dots ,0)\).

The parameters \(\vartheta _\theta = (W, b, V_\theta , 0)\) of the block \(f_\theta \) at width \(11 + w'\) (‘def:relu-shatter-plane-param‘ with the weights ‘def:relu-shatter-in-z‘, ‘def:relu-shatter-in-y‘, ‘def:relu-shatter-threshold‘, ‘def:relu-shatter-out-z‘, ‘def:relu-shatter-out-y‘). Only \(V_\theta \) depends on \(\theta \).

The unit sum of the track coordinate at width \(11 + w'\) (the padding units vanish): \(\sum _i v^z_i\, \mathrm{relu}(\alpha _i z + \gamma _i y - t_i) = P(z) + s(z, y)\).

Proof ▶

The unit sum of the register coordinate at width \(11 + w'\): \(\sum _i v^y_{\theta ,i}\, \mathrm{relu}(\alpha _i z + \gamma _i y - t_i) = 4\, \mathrm{relu}(y) - 8\, \mathrm{relu}(y - \tfrac 12) + \theta \, \psi (z)\).

Proof ▶

The hidden layer with parameter \(\theta \) on the state space \(K = [0,1]^2\):

\[ f_\theta (z, y) = \Bigl(\mathrm{clip}\bigl(P(z) + s(z, y)\bigr), \mathrm{clip}\bigl(4\, \mathrm{relu}(y) - 8\, \mathrm{relu}(y - \tfrac 12) + \theta \, \psi (z)\bigr)\Bigr). \]
Theorem 657
✓

The track coordinate of \(f_\theta (z, y)\) is \(\mathrm{clip}(P(z) + s(z, y))\).

Proof ▶
Theorem 658
✓

The register coordinate of \(f_\theta (z, y)\) is \(\mathrm{clip}(4\, \mathrm{relu}(y) - 8\, \mathrm{relu}(y - \tfrac 12) + \theta \, \psi (z))\).

Proof ▶

(\(f_\theta \) is a ReLU block of width \(11 + w'\).) With the clipping \(\Pi _K\) of the unit square and the parameters ‘def:relu-shatter-param‘, \(f_{\vartheta _\theta } = f_\theta \) on \(K\): the closed form of the block in terms of \(P\), \(\psi \), \(s\) and \(\mathrm{clip}\).

Proof ▶

(Closed form of the ReLU block, track.) For \(x = (z, y) \in K\), the first coordinate of \(\Pi _K(V_\theta \, \mathrm{relu}(Wx + b))\) is \(\mathrm{clip}\bigl(P(z) + s(z, y)\bigr)\).

Proof ▶

(Closed form of the ReLU block, register.) For \(x = (z, y) \in K\), the second coordinate of \(\Pi _K(V_\theta \, \mathrm{relu}(Wx + b))\) is \(\mathrm{clip}\bigl(4\, \mathrm{relu}(y) - 8\, \mathrm{relu}(y - \tfrac 12) + \theta \, \psi (z)\bigr)\).

Proof ▶

Weight norms of the representation of \(f_\theta \), \(\theta \in [0, \tfrac 14]\): \(\| W\| _{\rm op} \le \sqrt{15 + 17/8} \le 5\) (rows \((1,0)\) seven times, \((0,1)\) twice, \((2, \tfrac 14)\) twice), \(\| b\| \le 2\) (\(\| b\| ^2 = 3813/1024\)), \(\| V_\theta \| _{\rm op} \le \sqrt{\| v^z\| ^2 + \| v^y_\theta \| ^2} = \sqrt{46.5 + 2560\theta ^2 + 80} \le 17\), and \(c = 0\).

Proof ▶

(\(f_\theta \in F_\Lambda \) at width \(11 + w'\).) For \(\theta \in [0, \tfrac 14]\), \(\beta _W \ge 17\), \(\beta \ge 2\) and \(\Lambda \ge 85\), the block \(f_\theta \) belongs to the class \(F_\Lambda \) of ReLU blocks of width \(11 + w'\) on \(K = [0,1]^2\) with the clipping retraction: the weight norms are bounded by ‘lem:relu-shatter-param-norms‘ and the block is \(\| V_\theta \| \| W\| \le 17 \cdot 5 = 85\) Lipschitz by ‘lem:relu-shatter-block-lipschitz‘.

Proof ▶

(‘prop:relu-shatter‘(i), membership.) Every \(f_\theta \), \(\theta \in [0, \tfrac 14]\), is a ReLU block of width \(11\) (‘lem:relu-shatter-block-relu‘) and belongs to \(F_\Lambda \) for every width \(w \ge 11\), \(\beta _W \ge 17\), \(\beta \ge 2\) and \(\Lambda \ge 85\) (pad the representation of ‘lem:relu-shatter-block-mem‘ with \(w - 11\) zero units).

Proof ▶
Definition 665
✓
#

The two inverse branches of the shift \(E\): \(S_0(u) = u/4\) and \(S_1(u) = 1 - u/4\).

Theorem 666
✓
#

\(S_a\) maps \([0,1]\) into \([0,1]\).

Proof ▶

\(E(S_a(u)) = u\) for \(u \in [0,1]\) and \(a \in \{ 0, 1\} \) (Fact 6).

Proof ▶
Definition 668
✓
#

The code of a finite word \(c = (c_1, \dots , c_B) \in \{ 0,1\} ^B\): \(\mathrm{code}(c) = S_{c_1}(S_{c_2}(\cdots S_{c_B}(0)))\), defined by recursion on the word: \(\mathrm{code}(\emptyset ) = 0\) and \(\mathrm{code}(c_1, c_2, \dots ) = S_{c_1}(\mathrm{code}(c_2, \dots ))\).

Theorem 669
✓
#

\(\mathrm{code}(c) \in [0,1]\).

Proof ▶

The shift drops letters: \(E^j(\mathrm{code}(c_1, \dots , c_B)) = \mathrm{code}(c_{j+1}, \dots , c_B)\) for every \(j \ge 0\) (the empty word, of code \(0\), for \(j \ge B\)).

Proof ▶
Definition 671
✓
#

The parameter that stores the word \(c\): \(\theta (c) = \mathrm{code}(c)/4 \in [0, \tfrac 14]\).

Theorem 672
✓

\(\theta (c) \in [0, \tfrac 14]\).

Proof ▶

\(E(\theta (c)) = \mathrm{code}(c)\).

Proof ▶

(Reading the \(b\)-th letter.) For a word \(c = (c_1, \dots , c_B)\) and \(1 \le b \le B\), \(E^{b}(\theta (c)) = \mathrm{code}(c_b, \dots , c_B) = S_{c_b}(\mathrm{code}(c_{b+1}, \dots , c_B))\), which lies in \([0, \tfrac 14]\) if \(c_b = 0\) and in \([\tfrac 34, 1]\) if \(c_b = 1\). (In Lean the letters are indexed from \(0\): \(E^{b+1}(\theta (c)) = S_{c[b]}(\mathrm{code}(\mathrm{drop}_{b+1} c))\).)

Proof ▶
Definition 675
✓
#

The two sinks of the track: \(a_0 = \tfrac 34\) and \(a_1 = \tfrac 78\).

(Wait phase.) Let \((z_s, y_s)_{s \ge 0}\) be an orbit of the layers, \(z_{s+1} = \mathrm{clip}(P(z_s) + s(z_s, y_s))\), \(y_{s+1} = \mathrm{clip}(4\, \mathrm{relu}(y_s) - 8\, \mathrm{relu}(y_s - \tfrac 12) + \theta _s\psi (z_s))\), started at \(z_0 = a\, 2^{-t}\), \(y_0 = 0\) with \(a \in [0, \tfrac 3{16}]\). Then \(z_s = a\, 2^{-(t-s)}\) and \(y_s = 0\) for all \(s \le t\) (the track doubles and the register stays empty, for arbitrary \(\theta _s\)).

Proof ▶

(Count phase.) Let \((z_s, y_s)\) be an orbit of the layers with \(y_s \le 1\) for all \(s\), and suppose \(z_{s_0} = \tfrac 14 + \tfrac 14 2^{-b}\). Then for \(0 \le j \le b\), \(z_{s_0+j} = \tfrac 14 + \tfrac 14 2^{-(b-j)}\) and \(y_{s_0+j} = E^j(y_{s_0})\), for arbitrary \(\theta _s\).

Proof ▶
Theorem 678
✓

(Hold phase.) Let \((z_s, y_s)\) be an orbit of the layers with \(y_s \ge 0\) for all \(s\). If \(z_{s_0} \in [\tfrac 34, 1]\) then \(z_s = z_{s_0}\) for all \(s \ge s_0\).

Proof ▶

(Orbit of a sample point: wait, load, count.) Let \(\theta _s \in [0, \tfrac 14]\) for all \(s\) and let \((z_s, y_s)_{s \ge 0}\) be the orbit of the layers \(f_{\theta _0}, f_{\theta _1}, \dots \) (layer \(s\) maps \((z_s, y_s)\) to \((z_{s+1}, y_{s+1})\), with \(y_s \le 1\)) started at \(z_0 = \tfrac 18(1 + 2^{-(b+1)})\, 2^{-t}\), \(y_0 = 0\). Then, for arbitrary \(\theta _s\):

  1. (wait) the state is \((\tfrac 18(1 + 2^{-(b+1)})2^{-(t-s)}, 0)\) after \(s \le t\) layers;

  2. (load) it is \((\tfrac 14(1 + 2^{-(b+1)}), \theta _t)\) after \(t+1\) layers;

  3. (count) it is \((\tfrac 14 + \tfrac 14 2^{-(b+1-j)}, E^j(\theta _t))\) after \(t+1+j\) layers, \(0 \le j \le b+1\);

  4. in particular it is \((\tfrac 12, E^{b+1}(\theta _t))\) after \(t+b+2\) layers.

(Indices are \(0\)-based; in the paper’s \(1\)-based indices \(t' = t+1\), \(b' = b+1\) these are the states after \(s \le t'-1\), \(t'\), \(t'+j\) and \(t'+b'\) layers.)

Proof ▶

Wait: after \(t\) layers the state is \((\tfrac 18(1 + 2^{-(b+1)}), 0)\), with track in \((\tfrac 18, \tfrac 3{16}]\) (‘lem:relu-shatter-orbit-wait‘).

Load: layer \(t\) writes \(\theta _t\) into the register and doubles the track.

Count: ‘lem:relu-shatter-orbit-count‘ started at depth \(t+1\).

(Orbit of a sample point: sort and hold.) In the situation of ‘lem:relu-shatter-orbit-states‘ (with \(y_s \in [0,1]\)), for every depth \(N \ge t + b + 3\) the track is \(z_N = \tfrac 34\) if \(E^{b+1}(\theta _t) \le \tfrac 14\) and \(z_N = \tfrac 78\) if \(E^{b+1}(\theta _t) \ge \tfrac 34\): layer \(t+b+2\) sorts the state \((\tfrac 12, E^{b+1}(\theta _t))\) and all later layers hold the track.

Proof ▶

(Orbit of a sample point, code form.) In the situation of ‘lem:relu-shatter-orbit-sink‘, if \(E^{b+1}(\theta _t) = S_a(u)\) with \(u \in [0,1]\) and \(a \in \{ 0,1\} \), then the track is \(z_N = a_a\) (that is \(\tfrac 34\) for \(a = 0\) and \(\tfrac 78\) for \(a = 1\)) for every \(N \ge t + b + 3\), since \(S_0(u) \le \tfrac 14\) and \(S_1(u) \ge \tfrac 34\). In the paper’s \(1\)-based indices \(t' = t+1\), \(b' = b+1\) this is depth \(N \ge t' + b' + 1\).

Proof ▶
Definition 682
✓
#

The composition of the first \(s\) layers of the sequence \(f_{\theta _0}, f_{\theta _1}, \dots \) (layer \(0\) applied first): \(g_0 = \mathrm{id}\), \(g_{s+1} = f_{\theta _s} \circ g_s\).

If every layer \(f_{\theta _s}\) belongs to a hidden-layer class \(F\) then \(f_{\theta _{s-1}} \circ \cdots \circ f_{\theta _0} \in B(s, F)\).

Proof ▶
Theorem 684
✓
#

\(\tfrac 18(1 + 2^{-(b+1)})\, 2^{-t} \in [0,1]\).

Proof ▶
Definition 685
✓
#

The sample points: for \(t, b \ge 1\), \(x_{t,b} = \bigl(\tfrac 18(1 + 2^{-b})\, 2^{-(t-1)},\ 0\bigr) \in K\). In Lean the indices are \(0\)-based: ‘shatterPoint t b‘ \(= (\tfrac 18(1 + 2^{-(b+1)})\, 2^{-t}, 0)\) is the paper’s \(x_{t+1,b+1}\).

(Orbit of \(x_{t,b}\) under the network: wait, load, count.) Let \(\theta _s \in [0, \tfrac 14]\) for all \(s\) and write \((z_s, y_s) := (f_{\theta _{s-1}} \circ \cdots \circ f_{\theta _0})(x_{t+1,b+1})\) for the state after \(s\) layers. Then \((z_s, y_s) = (\tfrac 18(1 + 2^{-(b+1)})2^{-(t-s)}, 0)\) for \(s \le t\); \((z_{t+1}, y_{t+1}) = (\tfrac 14(1 + 2^{-(b+1)}), \theta _t)\); \((z_{t+1+j}, y_{t+1+j}) = (\tfrac 14 + \tfrac 14 2^{-(b+1-j)}, E^j(\theta _t))\) for \(0 \le j \le b+1\); in particular \((z_{t+b+2}, y_{t+b+2}) = (\tfrac 12, E^{b+1}(\theta _t))\) (‘lem:relu-shatter-orbit-states‘ applied to the two coordinates of the states).

Proof ▶

(Orbit of \(x_{t,b}\) under the network.) Let \(\theta _s \in [0, \tfrac 14]\) for all \(s\). If \(E^{b+1}(\theta _t) = S_a(u)\) with \(u \in [0,1]\) and \(a \in \{ 0, 1\} \), then for every depth \(N \ge t + b + 3\) the first coordinate of \((f_{\theta _{N-1}} \circ \cdots \circ f_{\theta _0})(x_{t+1,b+1})\) is \(a_a\) (‘lem:relu-shatter-orbit‘ applied to the two coordinates of the states).

Proof ▶
Definition 688
✓
#

The parameters of the shattering network for a labeling \(c \in \{ 0,1\} ^{k_1 \times B}\): \(\theta _t := \theta (c_{t,1}, \dots , c_{t,B})\) for \(t \le k_1\) and \(\theta _s := 0\) for \(s {\gt} k_1\). (In Lean the layers are indexed from \(0\): \(\theta _s = \theta (c_{s,\cdot })\) for \(s {\lt} k_1\) and \(\theta _s = 0\) for \(s \ge k_1\).)

Theorem 689
✓

\(\theta _s \in [0, \tfrac 14]\) for every layer \(s\).

Proof ▶
Theorem 690
✓

\(\theta _t = \theta (c_{t,1}, \dots , c_{t,B})\) for \(t \le k_1\).

Proof ▶

(The explicit network realizes the labeling.) Let \(c \in \{ 0,1\} ^{k_1 \times B}\) and \(\theta _s\) as in ‘def:relu-shatter-theta-seq‘. For \(t \le k_1\), \(b \le B\) and every depth \(N \ge t + b + 1\) (in particular for \(N = k_1 + B + 1\)), the first coordinate of \((f_{\theta _N} \circ \cdots \circ f_{\theta _1})(x_{t,b})\) equals \(a_{c_{t,b}}\): by ‘lem:relu-shatter-shift-iterate-theta‘, \(E^{b}(\theta _t) = S_{c_{t,b}}(\mathrm{code}( c_{t,b+1}, \dots , c_{t,B}))\), and ‘lem:relu-shatter-net-sink‘ applies. (In Lean, with \(0\)-based \(t, b\): \(N \ge t + b + 3\).)

Proof ▶

(‘prop:relu-shatter‘(ii) for every class containing the blocks \(f_\theta \): depth \(k_1 + B + 1\) realizes every labeling of \(k_1 B\) points.) Let \(F\) be a hidden-layer class on \(K = [0,1]^2\) with \(f_\theta \in F\) for all \(\theta \in [0, \tfrac 14]\) (a one-parameter family suffices). Let \(k_1, B \ge 0\) and \(c \in \{ 0,1\} ^{k_1 \times B}\), and put \(\theta _t := \theta (c_{t,1}, \dots , c_{t,B})\) for \(t \le k_1\) and \(\theta _s := 0\) for \(k_1 {\lt} s \le k_1 + B + 1\). Then \(g := f_{\theta _{k_1+B+1}} \circ \cdots \circ f_{\theta _1} \in B(k_1 + B + 1, F)\) satisfies: the first coordinate of \(g(x_{t,b})\) equals \(a_{c_{t,b}}\) for all \(t \le k_1\), \(b \le B\), where \(a_0 = \tfrac 34\) and \(a_1 = \tfrac 78\).

Proof ▶

Take \(g\) = the composition of the first \(k_1 + B + 1\) layers with the parameters ‘def:relu-shatter-theta-seq‘. All parameters lie in \([0, \tfrac 14]\), so every layer is in \(F\) and \(g \in B(k_1 + B + 1, F)\) (‘lem:relu-shatter-net-mem‘); the labels are given by ‘lem:relu-shatter-net-labels‘, since \(k_1 + B + 1 \ge t + b + 1\).

(‘prop:relu-shatter‘(ii), shattering.) Let \(k_1, B \ge 0\), \(a_0 := \tfrac 34\), \(a_1 := \tfrac 78\) and \(x_{t,b} := (\tfrac 18(1 + 2^{-b})\, 2^{-(t-1)}, 0)\), \(1 \le t \le k_1\), \(1 \le b \le B\). For every \(c \in \{ 0,1\} ^{k_1 \times B}\) there are \(\theta _1, \dots , \theta _{k_1+B+1} \in [0, \tfrac 14]\) such that the first coordinate of \(f_{\theta _{k_1+B+1}} \circ \cdots \circ f_{\theta _1}(x_{t,b})\) equals \(a_{c_{t,b}}\) for all \(t\) and \(b\); namely \(\theta _t = \tfrac 14 S_{c_{t,1}} \circ \cdots \circ S_{c_{t,B}}(0)\) for \(t \le k_1\) and \(\theta _s = 0\) for \(s {\gt} k_1\) (‘lem:relu-shatter-net-labels‘).

Proof ▶

(Depth \(k_1 + B + 1\) realizes every labeling of \(k_1 B\) points; ‘prop:relu-shatter‘(ii) in terms of the depth-\((k_1 + B + 1)\) hidden class.) Let \(K = [0,1]^2\) with the clipping retraction, \(w \ge 11\), \(\beta _W \ge 17\), \(\beta \ge 2\), \(\Lambda \ge 85\) and \(F_\Lambda \) the class of ReLU blocks of width \(w\). Let \(k_1, B \ge 0\) and \(c \in \{ 0,1\} ^{k_1 \times B}\). Put \(\theta _t := \theta (c_{t,1}, \dots , c_{t,B})\) for \(t \le k_1\) and \(\theta _s := 0\) for \(k_1 {\lt} s \le k_1 + B + 1\). Then \(g := f_{\theta _{k_1+B+1}} \circ \cdots \circ f_{\theta _1} \in B(k_1 + B + 1, F_\Lambda )\) satisfies: the first coordinate of \(g(x_{t,b})\) equals \(a_{c_{t,b}}\) for all \(t \le k_1\), \(b \le B\), where \(a_0 = \tfrac 34\) and \(a_1 = \tfrac 78\).

Proof ▶

‘prop:relu-shatter-labels-of-subset‘ with \(F = F_\Lambda \), which contains every \(f_\theta \), \(\theta \in [0, \tfrac 14]\) (‘prop:relu-shatter-i‘).

Definition 695
✓
#

The sample \(S = (x_{t,b})_{t \le k_1,\, b \le B}\) of \(n = k_1 B\) points, indexed through the bijection \(\{ 1,\dots ,k_1\} \times \{ 1,\dots ,B\} \cong \{ 1,\dots ,k_1 B\} \).

(‘prop:relu-shatter‘(iii) for every class containing the blocks \(f_\theta \): Rademacher lower bound.) Let \(F\) be a hidden-layer class on \(K = [0,1]^2\) with \(f_\theta \in F\) for all \(\theta \in [0, \tfrac 14]\). Let \(k_1, B \ge 1\), \(k \ge k_1 + B + 1\), \(R \ge 0\), \(H_R = \{ x \mapsto \langle u, x\rangle : \| u\| \le R\} \) and \(S = (x_{t,b})_{t,b}\) the sample of \(n = k_1 B\) points. Then

\[ \hat{\mathfrak R}_S\bigl(H_R \circ B(k, F)\bigr) \ge \frac{R}{16}. \]
Proof ▶

Step 1. The output layer \(h(x) = \langle R e_0, x\rangle = R\, x_0\) (\(e_0\) the first basis vector) belongs to \(H_R\).

Step 2. Every labeling \(c \in \{ 0,1\} ^n\) of the sample is realized at the levels \(a_0 = \tfrac 34 R\), \(a_1 = \tfrac 78 R\) by \(h \circ g\) with \(g \in B(k_1 + B + 1, F) \subseteq B(k, F)\) (‘prop:relu-shatter-labels-of-subset‘).

Step 3. Every function of \(H_R \circ B(k, F)\) is bounded by \(R\sqrt2\) on \(K\) (Cauchy–Schwarz and \(\| x\| \le \sqrt2\) on \(K\)), so ‘lem:shatter-rademacher-comp‘ gives \(\hat{\mathfrak R}_S \ge (\tfrac 78 R - \tfrac 34 R)/2 = R/16\).

(‘prop:relu-shatter‘(iii), lower bound on the sample: deep ReLU networks shatter \(k_1 B\) points at depth \(k_1 + B + 1\).) Let \(K = [0,1]^2\) with the clipping retraction \(\Pi _K\), \(w \ge 11\), \(\beta _W \ge 17\), \(\beta \ge 2\), \(\Lambda \ge 85\) and \(F_\Lambda \) the class of ReLU blocks \(x \mapsto \Pi _K(V\, \mathrm{relu}(Wx + b) + c)\) of width \(w\) with \(\| W\| _{\rm op}, \| V\| _{\rm op} \le \beta _W\), \(\| b\| , \| c\| \le \beta \) and Lipschitz constant at most \(\Lambda \). Let \(k_1, B \ge 1\) and \(x_{t,b} = (\tfrac 18(1 + 2^{-b})2^{-(t-1)}, 0)\), \(t \le k_1\), \(b \le B\). For every \(c \in \{ 0,1\} ^{k_1 \times B}\) there is \(g \in B(k_1 + B + 1, F_\Lambda )\) such that the first coordinate (the track) of \(g(x_{t,b})\) equals \(a_{c_{t,b}}\) for all \(t, b\), with \(a_0 = \tfrac 34\), \(a_1 = \tfrac 78\) (‘prop:relu-shatter-labels‘). Consequently, for every \(k \ge k_1 + B + 1\), the linear output layers \(H_R = \{ x \mapsto \langle u, x\rangle : \| u\| \le R\} \), \(R \ge 0\), and the sample \(S = (x_{t,b})_{t,b}\) of \(n = k_1 B\) points,

\[ \hat{\mathfrak R}_S\bigl(H_R \circ B(k, F_\Lambda )\bigr) \ge \frac{R}{16}. \]
Proof ▶

‘prop:relu-shatter-iii-of-subset‘ with \(F = F_\Lambda \), which contains every \(f_\theta \), \(\theta \in [0, \tfrac 14]\) (‘prop:relu-shatter-i‘): the labelings are realized by ‘prop:relu-shatter-labels‘, and ‘lem:shatter-rademacher-comp‘ with the output layer \(x \mapsto R\, x_0\) gives \((\tfrac 78 R - \tfrac 34 R)/2 = R/16\).

(Load–count–sort blocks.) Let \(K = [0,1]^2\) with the coordinatewise clipping retraction, and write a state as \((z, y)\). For \(\theta \in [0, \tfrac 14]\) let (‘def:relu-shatter-block‘)

\[ f_\theta (z, y) := \Bigl(\mathrm{clip}\bigl(P(z) + s(z, y)\bigr), \mathrm{clip}\bigl(4\, \mathrm{relu}(y) - 8\, \mathrm{relu}(y - \tfrac 12) + \theta \, \psi (z)\bigr)\Bigr), \]

where \(\mathrm{clip} = \Pi _{[0,1]}\) and (‘def:relu-shatter-P‘, ‘def:relu-shatter-psi‘, ‘def:relu-shatter-sort‘)

\[ P(z) := 2\, \mathrm{relu}(z) - 4\, \mathrm{relu}(z - \tfrac 3{16}) + 4\, \mathrm{relu}(z - \tfrac 14) - \tfrac 52\, \mathrm{relu}(z - \tfrac 12) + \tfrac 32\, \mathrm{relu}(z - \tfrac 34), \]
\[ \psi (z) := 32\, \mathrm{relu}(z - \tfrac 3{32}) - 32\, \mathrm{relu}(z - \tfrac 18) - 16\, \mathrm{relu}(z - \tfrac 3{16}) + 16\, \mathrm{relu}(z - \tfrac 14), \]
\[ s(z, y) := \mathrm{relu}\bigl(2(z - \tfrac 12) + \tfrac 14(y - \tfrac 14)\bigr) - \mathrm{relu}\bigl(2(z - \tfrac 12) + \tfrac 14(y - \tfrac 34)\bigr). \]
  1. (Membership.) Every \(f_\theta \), \(\theta \in [0, \tfrac 14]\), is a ReLU block of width \(11\) (with the parameters ‘def:relu-shatter-param‘) and belongs to \(F_\Lambda \) for every width \(w \ge 11\), \(\beta _W \ge 17\), \(\beta \ge 2\) and \(\Lambda \ge 85\).

  2. (Shattering.) Let \(k_1, B \ge 1\), \(a_0 := \tfrac 34\), \(a_1 := \tfrac 78\) and \(x_{t,b} := (\tfrac 18(1 + 2^{-b})\, 2^{-(t-1)}, 0)\), \(1 \le t \le k_1\), \(1 \le b \le B\). For every \(c \in \{ 0,1\} ^{k_1 \times B}\) there are \(\theta _1, \dots , \theta _{k_1+B+1} \in [0, \tfrac 14]\) such that the first coordinate of \(f_{\theta _{k_1+B+1}} \circ \cdots \circ f_{\theta _1}(x_{t,b})\) equals \(a_{c_{t,b}}\) for all \(t\) and \(b\).

  3. (Lower bound on the sample.) Let \(k \ge k_1 + B + 1\), let \(S\) be the sample of the \(n = k_1 B\) points \(x_{t,b}\) and \(H = \{ x \mapsto \langle u, x\rangle : \| u\| \le R\} \) with \(R \ge 0\). Then, for \(F_\Lambda \) as in (i),

    \[ \hat{\mathfrak R}_S\bigl(H \circ B(k, F_\Lambda )\bigr) \ge \frac{R}{16}. \]

The Lean statement is the conjunction of (i), (ii) and (iii) for \(w\), \(\beta _W\), \(\beta \), \(\Lambda \) in the ranges of (i); the three parts are ‘prop:relu-shatter-i‘, ‘prop:relu-shatter-ii‘ and ‘prop:relu-shatter-iii‘. In Lean, (ii) is stated for all \(k_1, B \ge 0\) and (iii) for \(k_1, B \ge 1\).

Proof ▶

If every \(f \in F\) is \(\Lambda \)-Lipschitz and \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) for all \(\varepsilon {\gt} 0\), then for \(k \ge 1\) the depth-\(k\) hidden class \(B(k,F)\) is totally bounded in \(d_S\), for every sample \(S\): by the envelope (‘lem:envelope-ne-top‘), \(N^{\mathrm{ext}}(B(k,F), d_S, \varepsilon ) \le N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) {\lt} \infty \).

Proof ▶

(Pointwise majorant of the entropy integrand under the envelope.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, \(\overline D {\gt} 0\), \(C \ge 0\), \(p \ge 0\), and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le p\log (1 + C/\varepsilon )\) for all \(\varepsilon {\gt} 0\). Then for \(k \ge 1\), every sample \(S\) and \(0 {\lt} \varepsilon \le \overline D\),

\[ \sqrt{\log N(B(k,F), d_S, \varepsilon )} \le \sqrt{\log (k+1) + kp\bigl(\log (1 + 2C/\overline D) + \log S_k(\Lambda )\bigr)} + \sqrt{kp}\, \sqrt{\log (\overline D/\varepsilon )} , \]

with \(S_k(\Lambda ) = \sum _{i{\lt}k}\Lambda ^i\) (the pointwise step of ‘cor:envelope-profiles-a-one-add‘).

Proof ▶

\(\log N(B(k,F), d_S, \varepsilon ) \le \log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon /2) \le \log (k+1) + kp\log (1 + 2CS_k/\varepsilon )\) and \(1 + 2CS_k/\varepsilon \le (1 + 2C/\overline D)\, S_k\, \overline D/\varepsilon \) for \(\varepsilon \le \overline D\); then \(\sqrt{a + b} \le \sqrt a + \sqrt b\).

(Integrability under the envelope.) Under the hypotheses of ‘lem:envelope-one-add-majorant‘, if \(D_k(S) \le \overline D\) then the entropy integrand \(\varepsilon \mapsto \sqrt{\log N(B(k,F), d_S, \varepsilon )}\) is interval-integrable on \([0, D_k(S)]\): the hypothesis of ‘thm:hidden-decomp-depth‘ is automatic for parametric Lipschitz layers (the majorant is a constant plus a multiple of \(\sqrt{\log (\overline D/\varepsilon )}\), which is integrable on \([0, \overline D]\)).

Proof ▶

(Entropy-integral lower bound from shattering.) In the situation of ‘prop:relu-shatter‘ (\(K = [0,1]^2\), \(w \ge 11\), \(\beta _W \ge 17\), \(\beta \ge 2\), \(\Lambda \ge 85\), \(k_1, B \ge 1\), \(k \ge k_1 + B + 1\), sample \(S = (x_{t,b})\) of \(n = k_1 B\) points),

\[ \mathsf V_k(S) = \int _0^{D_k(S)} \sqrt{\log N(B(k, F_\Lambda ), d_S, \varepsilon )}\, d\varepsilon \ \ge \ \frac{\sqrt n}{192} - \frac{\sqrt2}{12} . \]

Proof: with \(R = 1\), ‘prop:relu-shatter‘(iii) gives \(\hat{\mathfrak R}_S(H_1 \circ B(k, F_\Lambda )) \ge \tfrac 1{16}\); the hidden–output decomposition ‘thm:hidden-decomp-depth‘ with \(A_H = 1\), \(L = 1\) (‘prop:hilbert-sg‘) gives \(\hat{\mathfrak R}_S(H_1 \circ B(k, F_\Lambda )) \le \hat{\mathfrak R}_S(H_1) + \tfrac {12}{\sqrt n}\mathsf V_k(S)\), and \(\hat{\mathfrak R}_S(H_1) \le \sqrt2/\sqrt n\) (‘lem:linear-readouts-rademacher‘, \(\| x\| \le \sqrt2\) on \(K\)). The total boundedness and integrability hypotheses of the decomposition hold by the covering bound ‘lem:relu-layer-covering‘ and the envelope (‘lem:envelope-wordball-totally-bounded‘, ‘lem:envelope-one-add-integrable‘).

Proof ▶

Step 1. Lower bound: ‘prop:relu-shatter-iii‘ with \(R = 1\).

Step 2. The hypotheses of the hidden–output decomposition for \(F_\Lambda \): Lipschitz layers, finite covering numbers with \(\log N \le p\log (1 + C_F/\varepsilon )\) (‘lem:relu-layer-covering-log‘ with \(R_K = \sqrt2\)), \(D_k(S) \le 2\sqrt2\), total boundedness and integrability.

Step 3. Upper bound: ‘thm:hidden-decomp-depth‘ for \(H_1\) (\(A_H = 1\), \(L = 1\)) and \(\hat{\mathfrak R}_S(H_1) \le \sqrt2/\sqrt n\).

Step 4. Combine: \(\tfrac 1{16} \le \tfrac {\sqrt2}{\sqrt n} + \tfrac {12}{\sqrt n} \mathsf V_k(S)\), and multiply by \(\sqrt n/12\).

(The linear order of the layerwise bound is attained by ReLU blocks.) In the situation of ‘prop:relu-shatter‘, let \(k \ge 0\) and \(k_1 = B = \lfloor (k-1)/2 \rfloor \), so that the sample \(S = (x_{t,b})\) has \(n = \lfloor (k-1)/2 \rfloor ^2\) points and \(k_1 + B + 1 \le k\). Then

\[ \mathsf V_k(S) \ge \frac{1}{192}\Bigl\lfloor \frac{k-1}{2} \Bigr\rfloor - \frac{\sqrt2}{12}, \]

which is linear in \(k\), as is the upper bound \(O(k\sqrt{p\log \Lambda })\) of ‘prop:relu-regimes‘(iii). (For \(k \le 2\) the sample is empty and the right-hand side is negative.)

Proof ▶

For \(k \le 2\): \(\lfloor (k-1)/2 \rfloor = 0\) and \(\mathsf V_k(S) \ge 0\).

For \(k \ge 3\): ‘prop:relu-shatter-entropy‘ with \(k_1 = B = \lfloor (k-1)/2 \rfloor \ge 1\) and \(\sqrt n = \lfloor (k-1)/2 \rfloor \).

7.7 Deep ReLU networks: the expand-and-reset maps on a sample (Appendix K, lem:relu-reset-sample)

Theorem 704
✓

(Disjoint success sets carry at most the whole sample.) Let \((C_u)_u\) be subsets of \(\mathcal X\) indexed by words \(u \in [r]^{*}\) such that the sets \(C_u\), \(|u| = j\), are pairwise disjoint for every \(j\). For every sample \(S = (X_1, \dots , X_n)\) and every \(j \ge 0\), \(\sum _{|u| = j} \# \{ i : X_i \in C_u\} \le n\), i.e. \(\sum _{|u| = j} \hat P_n(C_u) \le 1\): each \(X_i\) lies in at most one set \(C_u\) with \(|u| = j\).

Proof ▶

Exchange the two sums: for each \(i\), at most one word \(u\) of length \(j\) has \(X_i \in C_u\), because the sets \(C_u\), \(|u| = j\), are pairwise disjoint.

Theorem 705
✓

(Words are close to constants on the sample.) Let \(\mathrm{diam}(\mathcal X) \le 1\) and suppose that every nonempty word \(f_u = f_{u_j} \circ \cdots \circ f_{u_1}\) equals the constant \(c_{u_j}\) of its last letter off a set \(C_u\). Then, for every sample \(S\) and every nonempty word \(u\),

\[ d_S(f_u, c_{u_j})^2 = \frac1n\sum _{i : X_i \in C_u} d(f_u(X_i), c_{u_j})^2 \le \hat P_n(C_u) = \frac1n\# \{ i : X_i \in C_u\} . \]
Proof ▶

The \(i\)-th term \(d(f_u(X_i), c_{u_j})^2\) is at most \(1\) if \(X_i \in C_u\) (the diameter is at most \(1\)) and vanishes otherwise (\(f_u = c_{u_j}\) off \(C_u\)).

In the setting of ‘lem:reset-words-sq-empdist-le‘, if \(\# \{ i : X_i \in C_u\} \le \varepsilon ^2 n\) then \(d_S(f_u, c_{u_j}) \le \varepsilon \).

Proof ▶

(Empirical saturation of words that are constant off disjoint success sets.) Let \((\mathcal X, d)\) have diameter at most \(1\), let \(f = (f_1, \dots , f_r)\) be self-maps of \(\mathcal X\), \(c_1, \dots , c_r \in \mathcal X\), and let \((C_u)_u\) be subsets of \(\mathcal X\) indexed by words such that (a) (constant off the success set) for every nonempty word \(u = (u_1, \dots , u_j)\), \(f_u(x) = c_{u_j}\) for all \(x \notin C_u\), and (b) (disjoint success sets) for every \(j\) the sets \(C_u\), \(|u| = j\), are pairwise disjoint. Then for every sample \(S = (X_1, \dots , X_n)\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\),

\[ N^{\mathrm{ext}}\bigl(B(k,\{ f_1, \dots , f_r\} ), d_S, \varepsilon \bigr) \le 1 + r + \sum _{j=1}^{k}\min \bigl\{ r^j,\ n,\ \lfloor \varepsilon ^{-2}\rfloor \bigr\} . \]

Centres: the identity, the \(r\) constant maps \(c_a\), and for each \(1 \le j \le k\) the words \(u\) of length \(j\) with \(\hat P_n(C_u) {\gt} \varepsilon ^2\) (fewer than \(\varepsilon ^{-2}\) of them, at most \(n\), at most \(r^j\)); every other word of length \(j\) is within \(d_S\)-distance \(\varepsilon \) of the constant map \(c_{u_j}\).

Proof ▶

The heavy words of length \(j\): those with \(\# \{ i : X_i \in C_u\} {\gt} \varepsilon ^2 n\).

Counting the heavy words: at most \(r^j\), at most \(n\), at most \(\lfloor \varepsilon ^{-2}\rfloor \) (the success sets of length \(j\) are disjoint).

The cover: a word is its own centre if it is heavy, and is within \(\varepsilon \) of the constant of its last letter otherwise (‘lem:reset-words-empdist-le‘).

(Root-logarithmic empirical entropy integral.) In the setting of ‘lem:reset-words-covering‘, for every sample \(S\) and every \(k\),

\[ \mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log (1+r)} + \sqrt{2\log 2} + \sqrt{\pi /2} . \]

(The additive constant \(\sqrt{2\log 2}\) is the price of comparing the internal covering number in \(d_S\), which defines \(\mathsf V_k(S)\), with the external one at half the scale: \(N(B, d_S, \varepsilon ) \le N^{\mathrm{ext}}(B, d_S, \varepsilon /2) \le 1 + r + 4k\varepsilon ^{-2}\).)

Proof ▶

For \(0 {\lt} \varepsilon \le 1\): \(N(B, d_S, \varepsilon ) \le N^{\mathrm{ext}}(B, d_S, \varepsilon /2) \le 1 + r + k\lfloor 4\varepsilon ^{-2}\rfloor \le (1+r)(k+1)(2/\varepsilon )^2\), so \(\sqrt{\log N} \le \sqrt{\log (k+1)} + \sqrt{\log (1+r)} + \sqrt{2\log 2} + \sqrt2\sqrt{\log (1/\varepsilon )}\); integrate over \((0,1]\) (recall \(D_k(S) \le 1\)) with \(\int _0^1\sqrt{\log (1/\varepsilon )}\, d\varepsilon = \sqrt\pi /2\).

(Empirical saturation, abstract form of ‘lem:cot-branch-sample‘ and ‘lem:relu-reset-sample‘(ii).) Let \((\mathcal X, d)\) have diameter at most \(1\), let \(f = (f_1, \dots , f_r)\) be self-maps of \(\mathcal X\), \(c_1, \dots , c_r \in \mathcal X\), and let \((C_u)_u\) be subsets of \(\mathcal X\) indexed by words such that (a) every nonempty word \(f_u\) equals the constant \(c_{u_j}\) of its last letter off \(C_u\), and (b) the sets \(C_u\) of words of the same length are pairwise disjoint. Then for every sample \(S = (X_1,\dots ,X_n)\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\),

\[ N^{\mathrm{ext}}\bigl(B(k,\{ f_1,\dots ,f_r\} ), d_S, \varepsilon \bigr) \le 1 + r + \sum _{j=1}^{k}\min \{ r^j, n, \lfloor \varepsilon ^{-2}\rfloor \} \le 1 + r + k\min \{ n, \lfloor \varepsilon ^{-2}\rfloor \} , \]

and consequently \(\mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log (1+r)} + \sqrt{2\log 2} + \sqrt{\pi /2}\), for every sample and without any assumption on the input distribution.

Proof ▶
Definition 710
✓
#

The success set of a word \(u = (u_1, \dots , u_j)\) for maps \(f = (f_1, \dots , f_r)\) and chambers \(U_1, \dots , U_r \subseteq \mathcal X\): the set \(C_u\) of inputs whose trajectory stays in the chambers, \(x \in U_{u_1}\), \(f_{u_1}(x) \in U_{u_2}\), …, \(f_{u_{j-1}} \circ \cdots \circ f_{u_1}(x) \in U_{u_j}\). In Lean it is defined by recursion on \(u\): \(C_{\emptyset } = \mathcal X\) and \(C_{(i, u)} = U_i \cap f_i^{-1}(C_u)\).

Theorem 711
✓
#

\(C_{\emptyset } = \mathcal X\).

Proof ▶
Theorem 712
✓
#

\(C_{(i, u)} = U_i \cap f_i^{-1}(C_u)\).

Proof ▶
Theorem 713
✓

(The recursive definition is the trajectory description.) \(x \in C_u\) if and only if \(f_{u_m} \circ \cdots \circ f_{u_1}(x) \in U_{u_{m+1}}\) for every \(0 \le m {\lt} |u|\).

Proof ▶

Induction on \(u\). For \(u = (i, u')\) the condition at \(m = 0\) is \(x \in U_i\) and the conditions at \(m + 1\) are those of \(u'\) at the point \(f_i(x)\).

Theorem 714
✓

If \(f_i(a_j) = a_i\) for all \(i, j\) then, on an anchor, \(f_u(a_b) = a_{u_j}\) where \(u_j\) is the last letter of \(u\) (and \(a_b\) if \(u\) is empty).

Proof ▶

Induction on \(u\): the first letter \(i\) sends \(a_b\) to \(a_i\).

(Closed form, failure.) Suppose \(f_i(x) = a_i\) for \(x \notin U_i\) and \(f_i(a_j) = a_i\) for all \(i, j\). If \(x \notin C_u\) then \(f_u(x) = a_{u_j}\), the anchor of the last letter of \(u\): a trajectory that leaves a chamber is reset to an anchor, and each later map sends an anchor to its own anchor.

Proof ▶

Induction on \(u = (i, u')\). If \(x \in U_i\) then \(f_i(x) \notin C_{u'}\) and the induction hypothesis applies at \(f_i(x)\); otherwise \(f_i(x) = a_i\) (reset) and ‘lem:reset-wordof-anchor‘ applies.

Theorem 716
✓

(Property (a): words are constant off their success sets.) Suppose \(f_i(x) = a_i\) for \(x \notin U_i\) and \(f_i(a_j) = a_i\) for all \(i, j\). For a nonempty word \(u = (u_1, \dots , u_j)\) and \(x \notin C_u\), \(f_u(x) = a_{u_j}\).

Proof ▶
Theorem 717
✓
#

If the chambers are pairwise disjoint, words of the same length with a common successful input coincide: if \(x \in C_u \cap C_v\) and \(|u| = |v|\) then \(u = v\).

Proof ▶

Induction on the common length. The first letters agree because \(x \in U_{u_1} \cap U_{v_1}\) and distinct chambers are disjoint; the tails agree by the induction hypothesis at \(f_{u_1}(x)\).

Theorem 718
✓

(Property (b): disjoint success sets.) If the chambers are pairwise disjoint then, for every \(j\), the success sets \(C_u\), \(|u| = j\), are pairwise disjoint.

Proof ▶

(Empirical saturation of ping–pong families with reset.) Let \((\mathcal X, d)\) have diameter at most \(1\) and let \(f = (f_1, \dots , f_r)\) be self-maps with chambers \(U_i \subseteq \mathcal X\) and anchors \(a_i \in \mathcal X\) such that (1) \(U_i \cap U_j = \emptyset \) for \(i \ne j\), (2) \(f_i(x) = a_i\) for \(x \notin U_i\), and (3) \(f_i(a_j) = a_i\) for all \(i, j\) (e.g. the anchors lie outside all chambers). Then for every sample \(S = (X_1,\dots ,X_n)\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\),

\[ N^{\mathrm{ext}}\bigl(B(k,\{ f_1,\dots ,f_r\} ), d_S, \varepsilon \bigr) \le 1 + r + \sum _{j=1}^{k}\min \{ r^j, n, \lfloor \varepsilon ^{-2}\rfloor \} \le 1 + r + k\min \{ n, \lfloor \varepsilon ^{-2}\rfloor \} , \]

and \(\mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log (1+r)} + \sqrt{2\log 2} + \sqrt{\pi /2}\). (Conditions (1) and (2) are those of ‘cond:e2-pingpong‘; (3) strengthens its anchor invariance \(f_i(A) \subseteq A\).)

Proof ▶
Theorem 720
✓
#

The state space \([0,1]\) has diameter \(1\): \(|x - y| \le 1\) for \(x, y \in [0,1]\).

Proof ▶
Theorem 721
✓

\(g_i(a_j) = a_i\) for all \(i, j \in \{ 0, 1\} \): the anchors lie outside both chambers (‘lem:relu-er-anchor-not-mem‘), and each map sends every point outside its chamber to its own anchor (‘lem:relu-er-reset‘).

Proof ▶
Definition 722
✓

The success set \(C_u\) of a word \(u = (u_1, \dots , u_j)\) in the two expand-and-reset maps: the set of inputs \(x \in [0,1]\) whose trajectory stays in the chambers, \(x \in U_{u_1}\), \(g_{u_1}(x) \in U_{u_2}\), …, \(g_{u_{j-1}} \circ \cdots \circ g_{u_1}(x) \in U_{u_j}\) (‘def:reset-success-set‘ for the generators ‘def:relu-er-generators‘ and the chambers ‘def:relu-er-chambers‘).

\(x \in C_u\) if and only if \(g_{u_m} \circ \cdots \circ g_{u_1}(x) \in U_{u_{m+1}}\) for every \(0 \le m {\lt} |u|\).

Proof ▶

(‘lem:relu-reset-sample‘(i), closed form of the words off their success sets.) For a nonempty word \(u = (u_1, \dots , u_j)\), \(g_u := g_{u_j} \circ \cdots \circ g_{u_1}\) and \(x \notin C_u\),

\[ g_u(x) = a_{u_j} : \]

a trajectory that leaves a chamber is reset to an anchor, the anchors lie outside both chambers, and each map sends every point outside its chamber, in particular both anchors, to its own anchor.

Proof ▶

(‘lem:relu-reset-sample‘(i), disjoint success sets.) For every \(j\) the sets \(C_u\), \(|u| = j\), are pairwise disjoint (the chambers \([0,1/4]\) and \([3/4,1]\) are disjoint).

Proof ▶

(Empirical saturation of the expand-and-reset maps.) For every sample \(S = (X_1, \dots , X_n)\) in \([0,1]\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\),

\[ N^{\mathrm{ext}}\bigl(B(k,\{ g_0,g_1\} ), d_S, \varepsilon \bigr) \le 1 + 2 + \sum _{j=1}^{k}\min \bigl\{ 2^j,\ n,\ \lfloor \varepsilon ^{-2}\rfloor \bigr\} . \]

Centres: the identity, the two constant maps \(a_0, a_1\), and for each \(1 \le j \le k\) the words \(u\) of length \(j\) with \(\hat P_n(C_u) {\gt} \varepsilon ^2\); every other word of length \(j\) is within \(d_S\)-distance \(\varepsilon \) of the constant map \(a_{u_j}\) (‘lem:reset-words-covering‘ with ‘eq:relu-reset-closed-form‘ and ‘lem:relu-reset-disjoint‘).

Proof ▶

(Root-logarithmic empirical entropy integral of the expand-and-reset maps.) For every sample \(S\) in \([0,1]\) and every \(k\),

\[ \mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log 3} + \sqrt{2\log 2} + \sqrt{\pi /2} \]

(‘lem:reset-words-profile‘ with \(r = 2\)).

Proof ▶

(‘lem:relu-reset-sample‘(ii), entropy on a sample: empirical saturation of the expand-and-reset maps.) Let \(g_0, g_1\) be the two expand-and-reset maps of \([0,1]\) (‘def:relu-er-generators‘), with chambers \(U_0 = [0,1/4]\), \(U_1 = [3/4,1]\) and anchors \(a_0 = 3/8\), \(a_1 = 5/8\). For a word \(u = (u_1, \dots , u_j)\), \(j \ge 1\), let \(g_u = g_{u_j} \circ \cdots \circ g_{u_1}\) and let \(C_u\) be the set of inputs whose trajectory stays in the chambers (‘def:relu-reset-success-set‘). Then \(g_u(x) = a_{u_j}\) for every \(x \notin C_u\) (‘eq:relu-reset-closed-form‘) and the sets \(C_u\), \(|u| = j\), are pairwise disjoint (‘lem:relu-reset-disjoint‘). Consequently, for every sample \(S = (X_1,\dots ,X_n)\) in \([0,1]\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\),

\[ N^{\mathrm{ext}}\bigl(B(k,\{ g_0,g_1\} ), d_S, \varepsilon \bigr) \le 1 + 2 + \sum _{j=1}^{k}\min \{ 2^j, n, \lfloor \varepsilon ^{-2}\rfloor \} \le 3 + k\min \{ n, \lfloor \varepsilon ^{-2}\rfloor \} , \]

and \(\mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log 3} + \sqrt{2\log 2} + \sqrt{\pi /2}\), for every sample and without any assumption on the input distribution, although \(N^{\mathrm{ext}}(B(k,\{ g_0,g_1\} ), d_\infty , \varepsilon ) \ge 2^k\) for \(\varepsilon {\lt} 1/16\) (‘lem:relu-er-pingpong‘).

Proof ▶

(Expand-and-reset maps on a sample.) Let \(g_0, g_1\) be the two expand-and-reset maps of \([0,1]\) (‘def:relu-er-generators‘; the paper writes \(e_0, e_1\)), with chambers \(U_0 = [0, \tfrac 14]\), \(U_1 = [\tfrac 34, 1]\) and anchors \(a_0 = \tfrac 38\), \(a_1 = \tfrac 58\). For a word \(u = (u_1, \dots , u_j)\) with \(j \ge 1\), let \(g_u := g_{u_j} \circ \cdots \circ g_{u_1}\), and let \(C_u\) be the set of inputs \(x \in [0,1]\) such that \(g_{u_{i-1}} \circ \cdots \circ g_{u_1}(x) \in U_{u_i}\) for every \(i \le j\) (‘def:relu-reset-success-set‘, ‘lem:relu-reset-success-set-iff‘).

  1. (Closed form.) \(g_u(x) = a_{u_j}\) for every \(x \notin C_u\), and the sets \(C_u\) of the words of a fixed length are pairwise disjoint.

  2. (Entropy on a sample.) For every sample \(S\) of \(n\) points of \([0,1]\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\),

    \[ N^{\mathrm{ext}}\bigl(B(k,\{ g_0,g_1\} ), d_S, \varepsilon \bigr) \le 3 + \sum _{j=1}^{k}\min \bigl\{ 2^j,\ n,\ \lfloor \varepsilon ^{-2}\rfloor \bigr\} \le 3 + k\min \{ n, \lfloor \varepsilon ^{-2}\rfloor \} , \]

    and \(\mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log 3} + \sqrt{2\log 2} + \sqrt{\pi /2}\).

The Lean statement is the conjunction of (i) (‘eq:relu-reset-closed-form‘ and ‘lem:relu-reset-disjoint‘) and (ii) (‘lem:relu-reset-sample-ii‘).

Proof ▶

7.8 Chain-of-thought style symbolic computation (Appendix L)

Definition 730
✓
#

The scratchpad space is \(\mathcal X = \mathcal A^{\mathbb N} = \{ x = (x_0, x_1, \dots ) : x_j \in \mathcal A\} \), the space of infinite symbol sequences over the alphabet \(\mathcal A\) (a type synonym of \(\mathbb N \to \mathcal A\) carrying the parameter \(\theta \) of the metric below).

Definition 731
✓
#

For \(x \ne y\) the first mismatch index is \(n(x,y) := \min \{ j \ge 0 : x_j \ne y_j\} \).

Theorem 732
✓

\(x_{n(x,y)} \ne y_{n(x,y)}\).

Proof ▶
Theorem 733
✓

\(L \le n(x,y)\) if and only if \(x_j = y_j\) for all \(j {\lt} L\).

Proof ▶
Theorem 734
✓

\(x_j = y_j\) for all \(j {\lt} n(x,y)\).

Proof ▶
Theorem 735
✓

\(n(x,y) = n(y,x)\).

Proof ▶

Both indices are characterized by the same prefix-agreement property.

Definition 736
✓
#

The ultrametric on \(\mathcal A^{\mathbb N}\): \(d_\theta (x,y) = \theta ^{n(x,y)}\) for \(x \ne y\) and \(d_\theta (x,x) = 0\), for a fixed \(\theta \in (0,1)\).

Theorem 737
✓
#

\(0 {\lt} \theta \) (as a real number).

Proof ▶
Theorem 738
✓
#

\(\theta {\lt} 1\) (as a real number).

Proof ▶
Theorem 739
✓

For \(x \ne y\), \(d_\theta (x,y) = \theta ^{n(x,y)}\).

Proof ▶

\(d_\theta (x,y) = d_\theta (y,x)\).

Proof ▶

(Prefix characterization.) \(d_\theta (x,y) \le \theta ^L\) if and only if \(x_j = y_j\) for all \(j {\lt} L\).

Proof ▶

If \(x = y\) both sides hold. Otherwise \(\theta ^{n(x,y)} \le \theta ^L \iff L \le n(x,y)\) since \(0 {\lt} \theta {\lt} 1\), and \(L \le n(x,y)\) is the prefix-agreement property.

Theorem 742
✓

\(d_\theta (x,y) \ge 0\).

Proof ▶
Theorem 743
✓

\(d_\theta (x,y) \le 1\): the scratchpad space has diameter at most \(1\).

Proof ▶

The case \(L = 0\) of the prefix characterization.

(Ultrametric inequality.) \(d_\theta (x,z) \le \max \{ d_\theta (x,y), d_\theta (y,z)\} \).

Proof ▶

If \(x = y\) or \(y = z\) this is trivial. Otherwise let \(L = \min \{ n(x,y), n(y,z)\} \); then \(x, y\) and \(y, z\) agree on the first \(L\) symbols, hence so do \(x, z\), so \(d_\theta (x,z) \le \theta ^L = \max \{ \theta ^{n(x,y)}, \theta ^{n(y,z)}\} \).

\(d_\theta (x,y) = 0\) implies \(x = y\).

Proof ▶

\((\mathcal A^{\mathbb N}, d_\theta )\) is a metric space (indeed an ultrametric space).

Theorem 747
✓

On \(\mathcal A^{\mathbb N}\) the distance is \(d_\theta \).

Proof ▶
Theorem 748
✓

Two sequences are within distance \(\theta ^L\) if and only if they agree in the first \(L\) symbols: \(d_\theta (x,y) \le \theta ^L \iff \forall j {\lt} L,\ x_j = y_j\).

Proof ▶
Theorem 749
✓

\(d_\theta (x,y) \le 1\), i.e. \(\mathrm{diam}(\mathcal A^{\mathbb N}) \le 1\).

Proof ▶
Theorem 750
✓

\(d_\theta (x,y) \le 1\) as an extended distance.

Proof ▶

If \(x_0 \ne y_0\) then \(d_\theta (x,y) = 1\).

Proof ▶

\(x \ne y\) and \(n(x,y) = 0\).

If \(x\) and \(y\) do not agree on the first \(L\) symbols then \(d_\theta (x,y) \ge \theta ^{L-1}\).

Proof ▶

\(x \ne y\) and \(n(x,y) {\lt} L\), so \(n(x,y) \le L - 1\) and \(\theta ^{L-1} \le \theta ^{n(x,y)}\).

Definition 753
✓
#

The identity map \(\mathcal A^{\mathbb N} \to (\mathcal A^{\mathbb N}, d_\theta )\) from the product of the discrete spaces.

For a finite alphabet, \((\mathcal A^{\mathbb N}, d_\theta )\) is compact. (The identity from the product of discrete spaces is continuous, since a \(d_\theta \)-ball is a cylinder set.)

Proof ▶

Equip \(\mathcal A\) with the discrete topology; \(\mathcal A^{\mathbb N}\) with the product topology is compact (Tychonoff). The identity map to \((\mathcal A^{\mathbb N}, d_\theta )\) is continuous: given \(\varepsilon {\gt} 0\) pick \(L\) with \(\theta ^L {\lt} \varepsilon \); the cylinder \(\{ y : y_j = x_j,\ j {\lt} L\} \) is a product neighbourhood of \(x\) contained in the \(\varepsilon \)-ball. The continuous image of a compact space is compact.

Since \(\mathrm{diam}(\mathcal A^{\mathbb N}) \le 1\) and \(d_S \le d_\infty \), the empirical diameter of any class of self-maps of \(\mathcal A^{\mathbb N}\) is at most \(1\): \(D_k(S) \le 1\).

Proof ▶
Definition 756
✓
#

A write step prepends a symbol: \(g_a(x) := (a, x_0, x_1, \dots )\) for \(a \in \mathcal A\).

Definition 757
✓
#

The append-only step family \(F_{\rm w} := \{ g_a : a \in \mathcal A\} \).

Theorem 758
✓

\(g_a(x)_0 = a\).

Proof ▶
Theorem 759
✓

\(g_a(x)_{i+1} = x_i\).

Proof ▶
Theorem 760
✓

\(a \mapsto g_a\) is injective, so \(|F_{\rm w}| = |\mathcal A| = m\).

Proof ▶
Theorem 761
✓

\(F_{\rm w}\) is finite.

Proof ▶

\(|F_{\rm w}| = m = |\mathcal A|\).

Proof ▶

Each write step is \(\theta \)-Lipschitz: \(d_\theta (g_a(x), g_a(y)) \le \theta \, d_\theta (x,y)\) (in fact with equality). Hence \(F_{\rm w}\) is a contractive hidden-layer class with \(\mathrm{lip}(g_a) = \theta {\lt} 1\).

Proof ▶

If \(x = y\) there is nothing to prove. Otherwise \(g_a(x)\) and \(g_a(y)\) agree on the first \(n(x,y) + 1\) symbols, so \(d_\theta (g_a(x), g_a(y)) \le \theta ^{n(x,y)+1} = \theta \, d_\theta (x,y)\).

Each write step is non-expanding (\(1\)-Lipschitz).

Proof ▶

(Saturation via P1.) For a finite alphabet and every \(\varepsilon {\gt} 0\), \(N^{\mathrm{ext}}(B(k,F_{\rm w}), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F_{\rm w}\rangle }, d_\infty , \varepsilon ) {\lt} \infty \) uniformly in \(k\).

Proof ▶

A word of \(\ell \) write steps determines the first \(\ell \) symbols of its output independently of the input: for \(w \in F_{\rm w}^{\ell }\) and all \(x, y\), \(w(x)_j = w(y)_j\) for \(j {\lt} \ell \).

Proof ▶

Induction on \(\ell \): for \(w = g_a \circ w'\), the symbol \(0\) is \(a\) for both inputs and the symbols \(1, \dots , \ell \) are the first \(\ell - 1\) symbols of \(w'(x)\), \(w'(y)\).

Definition 767
✓
#

The resolution length \(\ell (\varepsilon ) := \lceil \log (1/\varepsilon )/\log (1/\theta ) \rceil \) (a natural number; \(0\) for \(\varepsilon \ge 1\)).

Theorem 768
✓
#

\(\log (1/\theta ) {\gt} 0\).

Proof ▶
Theorem 769
✓

\(\theta ^{\ell (\varepsilon )} \le \varepsilon \) for every \(\varepsilon {\gt} 0\).

Proof ▶

\(\ell (\varepsilon ) \ge \log (1/\varepsilon )/\log (1/\theta )\), so \(\log (1/\varepsilon ) \le \log ((1/\theta )^{\ell (\varepsilon )})\) and \(1/\varepsilon \le 1/\theta ^{\ell (\varepsilon )}\).

Theorem 770
✓
#

For \(0 {\lt} \varepsilon \le 1\), \(\ell (\varepsilon ) \le \log (1/\varepsilon )/\log (1/\theta ) + 1\).

Proof ▶

\(\lceil a \rceil {\lt} a + 1\) for \(a \ge 0\); here \(a \ge 0\) since \(\varepsilon \le 1\).

(The short words cover the word ball.) For every \(\varepsilon {\gt} 0\) and \(k\), the word ball \(B(\min \{ k, \ell (\varepsilon )\} , F_{\rm w}) \subseteq B(k, F_{\rm w})\) is an \(\varepsilon \)-cover of \(B(k,F_{\rm w})\) in \(d_\infty \): a word \(g_u\) with \(|u| {\gt} \ell \) is within \(\theta ^{\ell } \le \varepsilon \) of the word \(g_{u'}\) formed by its last \(\ell \) letters.

Proof ▶

Let \(f \in F_{\rm w}^l\) with \(l \le k\). If \(l \le \ell (\varepsilon )\) then \(f\) itself lies in the cover. Otherwise factor \(f = w_2 \circ w_1\) with \(w_2 \in F_{\rm w}^{\ell (\varepsilon )}\) (the last \(\ell (\varepsilon )\) letters); \(w_2(w_1(x))\) and \(w_2(x)\) agree on the first \(\ell (\varepsilon )\) symbols, so \(d_\infty (f, w_2) \le \theta ^{\ell (\varepsilon )} \le \varepsilon \).

(Saturation for append-only steps.) Let \(|\mathcal A| = m \ge 2\). For \(\varepsilon {\gt} 0\) let \(\ell (\varepsilon ) := \lceil \log (1/\varepsilon )/\log (1/\theta )\rceil \). Then for all \(k \ge 0\),

\[ N^{\mathrm{ext}}\bigl(B(k,F_{\rm w}), d_\infty , \varepsilon \bigr) \le m^{\min \{ k,\ell (\varepsilon )\} +1} . \]
Proof ▶

The cover of ‘lem:cot-append-cover‘ has at most \(\sum _{j \le \min \{ k,\ell (\varepsilon )\} } m^j \le m^{\min \{ k,\ell (\varepsilon )\} +1}\) elements (‘lem:wordball-card‘).

The same bound for the internal covering number in \(d_\infty \) and in \(d_S\): \(N(B(k,F_{\rm w}), d_S, \varepsilon ) \le N(B(k,F_{\rm w}), d_\infty , \varepsilon ) \le m^{\min \{ k,\ell (\varepsilon )\} +1}\) (the cover consists of elements of \(B(k,F_{\rm w})\)).

Proof ▶

‘lem:covering-empSpace-le-unifMaps-internal‘, then the internal cover \(B(\min \{ k,\ell (\varepsilon )\} , F_{\rm w}) \subseteq B(k,F_{\rm w})\).

For \(0 {\lt} \varepsilon \le 1\) and \(m \ge 2\), \(\sqrt{\log N(B(k,F_{\rm w}), d_S, \varepsilon )} \le \sqrt{\log m}\Bigl(\frac{\sqrt{\log (1/\varepsilon )}}{\sqrt{\log (1/\theta )}} + \sqrt2\Bigr)\), using \(\ell (\varepsilon ) + 1 \le \log (1/\varepsilon )/\log (1/\theta ) + 2\) and \(\sqrt{a+b} \le \sqrt a + \sqrt b\).

Proof ▶

\(\log N \le (\ell (\varepsilon )+1)\log m \le (\log (1/\varepsilon )/\log (1/\theta ) + 2)\log m\); take square roots.

(Saturated variance profile for append-only steps.) Let \(|\mathcal A| = m \ge 2\). For every sample \(S\) and every \(k \ge 0\),

\[ \mathsf V_k(S) = \int _0^{D_k(S)} \sqrt{\log N(B(k,F_{\rm w}), d_S, \varepsilon )}\, d\varepsilon \le \sqrt{\log m}\Bigl(\frac{\sqrt\pi }{2\sqrt{\log (1/\theta )}} + \sqrt2\Bigr) =: \mathsf V_\infty . \]

(Case (i) of ‘prop:profiles‘: the entropy integral does not depend on the depth \(k\).)

Proof ▶

Since \(D_k(S) \le 1\), dominate the integrand on \((0,1]\) by ‘lem:cot-append-entropy-pointwise‘ and use \(\int _0^1 \sqrt{\log (1/\varepsilon )}\, d\varepsilon = \sqrt\pi /2\) (‘lem:log-split‘).

Definition 776
✓
#

The alphabet \(\mathcal A = [r] \cup \{ \bullet \} \) with \(r\) active symbols and one padding symbol \(\bullet \).

Definition 777
✓
#

The shift \(\sigma (x) = (x_1, x_2, \dots )\).

Definition 778
✓
#

The constant sequence \(\bar a = (a, a, \dots )\).

Definition 779
✓

A guarded step \(f_a\), \(a \in [r]\), reads the current symbol: if it equals \(a\) the step consumes it, \(f_a(x) = \sigma (x)\); otherwise it resets to the constant error state \(\bar a\).

Definition 780
✓

The branching step family \(F_{\rm b} := \{ f_a : a \in [r]\} \).

Theorem 781
✓

\(\sigma (g_a(y)) = y\).

Proof ▶
Theorem 782
✓

\(\sigma (\bar a) = \bar a\).

Proof ▶

If \(x_0 \ne a\) then \(f_a(x) = \bar a\).

Proof ▶

If \(x_0 = a\) then \(f_a(x) = \sigma (x)\).

Proof ▶

\(f_a(\bar a) = \bar a\) and \(f_a(\bar b) = \bar a\) for \(b \ne a\): the anchors are mapped to anchors.

Proof ▶

\(a \mapsto f_a\) is injective, so \(|F_{\rm b}| = r\).

Proof ▶

\(f_a(\bar a) = \bar a\) while \(f_b(\bar a) = \bar b\).

\(|F_{\rm b}| = r\).

Proof ▶

(The branching family is a ping–pong family, ‘ex:e2-pingpong-subshift‘.) With chambers \(U_a = V_a = \{ x : x_0 = a\} \), anchors \(\bar a\), marker \(\bar\bullet \) and \(\alpha = 1\), \(F_{\rm b}\) satisfies the hypotheses of ‘cond:e2-pingpong‘ (the chambers are disjoint; they are in fact \(1\)-separated, which the paper’s form of E2 requires). Consequently, for \(r \ge 2\), \(N^{\mathrm{ext}}(B(k,F_{\rm b}), d_\infty , \varepsilon ) \ge r^k\) for every \(k\) and every \(\varepsilon {\lt} 1/2\), and \(u \mapsto f_u\) is injective on \([r]^k\).

Proof ▶

Verify the four ping–pong conditions: (1) sequences in different chambers differ at index \(0\), so the chambers are disjoint; (2) \(y = f_a(g_a(y))\) with \(g_a(y) \in V_a\); (3) the reset is the definition of \(f_a\) off \(U_a\), and anchors go to anchors (‘lem:cot-guarded-const‘); (4) \(\bar\bullet _0 = \bullet \ne a = \bar a_0\), so \(d(\bar\bullet , \bar a) = 1\).

(Exponential growth for branching steps.) For \(r \ge 2\), every \(k \ge 0\) and every \(\varepsilon {\lt} 1/2\),

\[ r^k \le N^{\mathrm{ext}}\bigl(B(k,F_{\rm b}), d_\infty , \varepsilon \bigr) \le r^{k+1} . \]

The lower bound is the ping–pong bound ‘cond:e2-pingpong‘; the upper bound holds because \(F_{\rm b}\) is finite, so \(|B(k,F_{\rm b})| \le \sum _{j \le k} r^j \le r^{k+1}\).

Proof ▶

For \(r \ge 2\), every sample \(S\) and every \(k\), \(\mathsf V_k(S) \le \sqrt{(k+1)\log r}\) (case (iii) of ‘prop:profiles‘, with \(\overline D = \mathrm{diam}(\mathcal A^{\mathbb N}) = 1\)).

Proof ▶

‘prop:profiles-finite‘ with \(|B(k,F_{\rm b})| \le r^{k+1}\) and \(D_k(S) \le 1\).

Theorem 791
✓
#

\(f_{u \cdot v} = f_v \circ f_u\) (the first letter acts first).

Proof ▶

Every \(g \in B(k, \{ f_1, \dots , f_r\} )\) is \(f_u\) for a word \(u \in [r]^{\le k}\).

Proof ▶
Definition 793
✓

The success cylinder of a program \(u = (u_1, \dots , u_j)\): the set \([u]\) of inputs whose first \(j\) symbols are \(u_1, \dots , u_j\). In Lean, membership is defined by recursion on \(u\): \(x \in [\, ]\) always, and \(x \in [a :: u]\) iff \(x_0 = a\) and \(\sigma (x) \in [u]\).

Membership in a cylinder is decidable (it is a finite conjunction of symbol comparisons).

Theorem 795
✓

\(\sigma ^j(x) = (x_{i+j})_{i \ge 0}\).

Proof ▶

On a constant state, \(f_u(\bar b) = \bar u_j\) where \(u_j\) is the last letter of \(u\) (and \(\bar b\) if \(u\) is empty): each guard either keeps the constant state or replaces it by its own.

Proof ▶

(Closed form, success.) If \(x \in [u]\) then \(f_u(x) = \sigma ^{|u|}(x)\).

Proof ▶

(Closed form, failure.) If \(x \notin [u]\) then \(f_u(x) = \bar u_j\), the constant state of the last letter of \(u\): once a guard fails the scratchpad is the constant state of the failed symbol, and each later guard either keeps it or replaces it by its own constant state.

Proof ▶

(Closed form of the programs.) For a nonempty program \(u = (u_1, \dots , u_j)\) and \(f_u := f_{u_j} \circ \cdots \circ f_{u_1}\),

\[ f_u(x) = \sigma ^{j}(x)\ \text{ if } x \in [u], \qquad f_u(x) = \bar u_j\ \text{ otherwise}. \]
Proof ▶

(Disjointness of the cylinders.) Programs of the same length with a common successful input coincide: if \(x \in [u] \cap [v]\) and \(|u| = |v|\) then \(u = v\).

Proof ▶

(The cylinders of length \(j\) are pairwise disjoint.) For every sample \(S = (X_1, \dots , X_n)\) and \(j \ge 0\), \(\sum _{|u| = j} \# \{ i : X_i \in [u]\} \le n\), i.e. \(\sum _{|u|=j}\hat P_n([u]) \le 1\): each \(X_i\) lies in at most one cylinder of length \(j\).

Proof ▶

(Programs are close to constants on the sample.) For every program \(u\) (with last letter \(u_j\), or any \(b\) if \(u\) is empty),

\[ d_S(f_u, \bar u_j)^2 = \frac1n\sum _{i : X_i \in [u]} d_\theta (\sigma ^j(X_i), \bar u_j)^2 \le \hat P_n([u]) = \frac1n\# \{ i : X_i \in [u]\} , \]

since \(f_u = \bar u_j\) off \([u]\) and \(\mathrm{diam}(\mathcal A^{\mathbb N}) = 1\).

Proof ▶

If \(\# \{ i : X_i \in [u]\} \le \varepsilon ^2 n\) then \(d_S(f_u, \bar u_j) \le \varepsilon \).

Proof ▶

(Empirical saturation for branching steps.) For every sample \(S = (X_1, \dots , X_n)\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\) (the paper states \(\varepsilon \in (0,1]\); the bound holds for all \(\varepsilon {\gt} 0\)),

\[ N^{\mathrm{ext}}\bigl(B(k,F_{\rm b}), d_S, \varepsilon \bigr) \le 1 + r + \sum _{j=1}^{k}\min \bigl\{ r^j,\ n,\ \lfloor \varepsilon ^{-2}\rfloor \bigr\} . \]

Centres: the identity, the \(r\) constant maps \(\bar a\), and for each \(1 \le j \le k\) the programs \(u\) of length \(j\) with \(\hat P_n([u]) {\gt} \varepsilon ^2\) (fewer than \(\varepsilon ^{-2}\) of them, at most \(n\), at most \(r^j\)); every other program of length \(j\) is within \(d_S\)-distance \(\varepsilon \) of the constant map \(\bar u_j\).

Proof ▶

The heavy programs of length \(j\).

Counting the heavy programs: at most \(r^j\), at most \(n\), at most \(\lfloor \varepsilon ^{-2}\rfloor \).

The cover.

Theorem 805
✓
#

\(1 + r + \sum _{j=1}^k\min \{ r^j, n, \lfloor \varepsilon ^{-2}\rfloor \} \le 1 + r + k\min \{ n, \lfloor \varepsilon ^{-2}\rfloor \} \).

Proof ▶

(Root-logarithmic empirical entropy integral for branching steps.) For every sample \(S\) and every \(k\),

\[ \mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log (1+r)} + \sqrt{2\log 2} + \sqrt{\pi /2} \]

(the paper’s bound without the term \(\sqrt{2\log 2}\): this additive constant is the price of comparing the internal covering number in \(d_S\), which defines \(\mathsf V_k(S)\), with the external one at half the scale, \(N(B, d_S, \varepsilon ) \le N^{\mathrm{ext}}(B, d_S, \varepsilon /2) \le 1 + r + 4k\varepsilon ^{-2}\)).

Proof ▶

For \(0 {\lt} \varepsilon \le 1\): \(N(B, d_S, \varepsilon ) \le N^{\mathrm{ext}}(B, d_S, \varepsilon /2) \le 1 + r + k\lfloor 4\varepsilon ^{-2}\rfloor \le (1+r)(k+1)(2/\varepsilon )^2\), so \(\sqrt{\log N} \le \sqrt{\log (k+1)} + \sqrt{\log (1+r)} + \sqrt{2\log 2} + \sqrt2\sqrt{\log (1/\varepsilon )}\); integrate over \((0,1]\) (recall \(D_k(S) \le 1\)) with \(\int _0^1\sqrt{\log (1/\varepsilon )}\, d\varepsilon = \sqrt\pi /2\).

(Empirical saturation for branching steps, ‘lem:cot-branch-sample‘.) For every sample \(S = (X_1,\dots ,X_n)\), every \(k \ge 0\) and every \(\varepsilon {\gt} 0\) (the paper states \(\varepsilon \in (0,1]\)),

\[ N^{\mathrm{ext}}\bigl(B(k,F_{\rm b}), d_S, \varepsilon \bigr) \le 1 + r + \sum _{j=1}^{k}\min \{ r^j, n, \lfloor \varepsilon ^{-2}\rfloor \} \le 1 + r + k\min \{ n, \lfloor \varepsilon ^{-2}\rfloor \} , \]

and consequently \(\mathsf V_k(S) \le \sqrt{\log (k+1)} + \sqrt{\log (1+r)} + \sqrt{2\log 2} + \sqrt{\pi /2}\), the root-logarithmic profile, for every sample and without any assumption on the input distribution.

Proof ▶
Definition 808
✓
#

For \(L \ge 1\) the window feature map \(\Phi _L : \mathcal A^{\mathbb N} \to \mathbb R^{\mathcal A^L}\) is the one-hot encoding of the window \((x_0, \dots , x_{L-1})\).

Theorem 809
✓

\(\| \Phi _L(x)\| = 1\) (in particular \(\| \Phi _L\| \le 1\)).

Proof ▶
Theorem 810
✓

If \(x, y\) agree on the first \(L\) symbols then \(\Phi _L(x) = \Phi _L(y)\).

Proof ▶
Theorem 811
✓
#

Distinct one-hot vectors are at Euclidean distance \(\sqrt2\): \(\| e_u - e_v\| = \sqrt2\) for \(u \ne v\).

Proof ▶

\(\| e_u - e_v\| ^2 = \| e_u\| ^2 - 2\langle e_u, e_v\rangle + \| e_v\| ^2 = 1 - 0 + 1\).

(Window output features.) \(\Phi _L\) is \(\sqrt2\, \theta ^{1-L}\)-Lipschitz with respect to \(d_\theta \), and \(\| \Phi _L\| \le 1\). (If \(d_\theta (x,y) \le \theta ^L\) the first \(L\) symbols agree and \(\Phi _L(x) = \Phi _L(y)\); otherwise \(d_\theta (x,y) \ge \theta ^{L-1}\) and \(\| \Phi _L(x) - \Phi _L(y)\| = \sqrt2 \le \sqrt2\, \theta ^{1-L} d_\theta (x,y)\).)

Proof ▶

Case analysis on whether the windows agree.

Consequently (via ‘prop:hilbert-sg‘) the sub-Gaussian increment condition holds for the linear readout class \(H_L = \{ x \mapsto \langle w, \Phi _L(x)\rangle : \| w\| \le 1\} \) and every hidden-layer class on \(\mathcal A^{\mathbb N}\), with \(A_H = 1\) and \(L = \sqrt2\, \theta ^{1-L}\).

Proof ▶
Definition 814
✓
#

The depth-independent entropy integral of ‘lem:cot-append-profile‘: \(\mathsf V_\infty (m,\theta ) := \sqrt{\log m}\Bigl(\frac{\sqrt\pi }{2\sqrt{\log (1/\theta )}} + \sqrt2\Bigr)\).

Theorem 815
✓
#

\(\mathsf V_\infty (m,\theta ) \ge 0\).

Proof ▶

The teacher–student target class of arbitrarily long programs read out linearly: \(\mathcal C := \overline{H_R(\Phi ) \circ \langle F_{\rm w}\rangle }^{\, d_\infty }\), the uniform closure of the readouts of all finite compositions of write steps.

Every element of \(B(k, F_{\rm w})\) and of \(\langle F_{\rm w}\rangle \) is \(1\)-Lipschitz, hence continuous.

Proof ▶

(Measurability.) For a continuous feature map \(\Phi \) (with the Borel \(\sigma \)-algebra on \(\mathcal A^{\mathbb N}\)), every element of \(\mathcal H_k = H_R(\Phi ) \circ B(k, F_{\rm w})\) is measurable.

Proof ▶

Every element of the target class \(\mathcal C\) is measurable (a uniform limit of continuous functions).

Proof ▶

\(\mathcal C \ne \emptyset \) (it contains the zero readout) when \(R \ge 0\).

Proof ▶

(Pointwise boundedness.) If \(\| \Phi \| \le M_\Phi \) and \(R \ge 0\) then \(|g(x)| \le R M_\Phi \) for every \(g \in \mathcal H_k\).

Proof ▶

(Sup-norm separability.) For a separable feature space, a Lipschitz feature map \(\Phi \) with \(\| \Phi \| \le M_\Phi \) and \(R \ge 0\), the class \(\mathcal H_k = H_R(\Phi ) \circ B(k, F_{\rm w})\) is sup-norm separable (\(B(k,F_{\rm w})\) is finite and the ball of radius \(R\) has a countable dense subset).

Proof ▶

(Rademacher complexity of the readout class, ‘lem:cot-output‘.) If \(\| \Phi \| \le M_\Phi \) then \(\hat{\mathfrak R}_S(H_R(\Phi )) \le R M_\Phi /\sqrt n\) for every sample \(S\) (for the window features, \(M_\Phi = 1\)).

Proof ▶

(Estimation term for append-only steps.) Let \(|\mathcal A| = m \ge 2\), \(\Phi \) be \(L_\Phi \)-Lipschitz with \(\| \Phi \| \le M_\Phi \) and \(R {\gt} 0\). Then for every sample \(S\) of size \(n \ge 1\) and every depth \(k\),

\[ \hat{\mathfrak R}_S(\mathcal H_k) \le \frac{R M_\Phi }{\sqrt n} + \frac{12 \cdot 1 \cdot R L_\Phi }{\sqrt n}\, \mathsf V_\infty (m,\theta ) \]

(‘thm:hidden-decomp-depth‘ with \(A\_ H = 1\), ‘lem:cot-append-profile‘ and ‘lem:cot-readout-rademacher‘).

Proof ▶

(Bias for append-only steps.) Let \(\Phi \) be \(L_\Phi \)-Lipschitz and \(R \ge 0\). Against the teacher–student class \(\mathcal C = \overline{H_R(\Phi ) \circ \langle F_{\rm w}\rangle }^{\, d_\infty }\),

\[ \mathrm{bias}(k) = \varepsilon _{\mathrm{model}}(k) \le \beta _\ell \, R L_\Phi \, \theta ^k : \]

for a teacher \(c = h_w \circ g_u \circ g_v\) with \(|u| = k\), \(|c(x) - h_w(g_u(x))| \le R L_\Phi \, d_\theta (g_u(g_v x), g_u x) \le R L_\Phi \theta ^k\) since \(\mathrm{lip}(g_u) = \theta ^k\) and \(\mathrm{diam} = 1\), and the same bound holds on the uniform closure; conclude with ‘lem:approx-transfer‘.

Proof ▶

(Append-only scratchpad, rigorous form.) Let \(|\mathcal A| = m \ge 2\), let \(\Phi : \mathcal A^{\mathbb N} \to \mathcal H\) be an \(L_\Phi \)-Lipschitz feature map into a separable Hilbert space with \(\| \Phi \| \le M_\Phi \) (e.g. the window features \(\Phi _L\)), \(R {\gt} 0\), \(H = H_R(\Phi )\), \(F = F_{\rm w}\), and let the target class be \(\mathcal C = \overline{H \circ \langle F_{\rm w}\rangle }^{\, d_\infty }\). For a measurable loss \(\ell : \mathbb R \times \mathcal Y \to [0,b]\), \(\beta _\ell \)-Lipschitz in its first argument, \(n \ge 1\), \(\eta \ge 0\) and \(\delta \in (0,1)\): with probability at least \(1 - \delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(\eta \)-empirical minimizer \(\hat h \in \mathcal H_k = H \circ B(k, F_{\rm w})\) satisfies

\[ L[\hat h] - \inf _{\mathcal C} L \le \beta _\ell R L_\Phi \, \theta ^k + \eta + \mathrm{dev}_{\ell ,n,\delta }\Bigl(\frac{R M_\Phi }{\sqrt n} + \frac{12 R L_\Phi }{\sqrt n} \mathsf V_\infty (m,\theta )\Bigr), \]

where \(\mathrm{dev}_{\ell ,n,\delta }(B) = 4\beta _\ell B + 6b\sqrt{2\log (4/\delta )/n}\) is the estimation-plus-deviation term of ‘thm:bv‘ (‘def:bv-dev‘). This is the EL regime with \(\alpha = \log (1/\theta )\) and saturated variance. (The implementation map is the identity, \(\varepsilon _{\mathrm{imp}} = 0\).)

Proof ▶
Theorem 827
✓
#

(EL balancing with saturated variance.) For \(n \ge 1\) the depth \(k^\ast := \lceil \log n / (2\log (1/\theta ))\rceil = \frac{\log n}{2\log (1/\theta )} + O(1)\) satisfies \(\theta ^{k^\ast } \le n^{-1/2}\), so the bias term matches the saturated variance \(n^{-1/2}\).

Proof ▶

(Balanced value \(O(n^{-1/2})\).) Under the hypotheses of ‘prop:cot-append‘, at the depth \(k^\ast = \lceil \log n / (2\log (1/\theta ))\rceil \) the bound reads

\[ L[\hat h] - \inf _{\mathcal C} L \le \frac{\beta _\ell R L_\Phi }{\sqrt n} + \eta + \mathrm{dev}_{\ell ,n,\delta }\Bigl(\frac{R M_\Phi + 12 R L_\Phi \mathsf V_\infty (m,\theta )}{\sqrt n}\Bigr) \]

with probability at least \(1 - \delta \): every term is of order \(n^{-1/2}\) (up to the \(\sqrt{\log (1/\delta )}\) factor of the deviation term), so the balanced value is \(O(n^{-1/2})\).

Proof ▶

7.9 Unrolled fixed-point iterations and ODE solvers (Appendix M)

(Saturated profile from total boundedness.) Let \(\mathcal X\) be compact, let \(G \subseteq \mathcal X^{\mathcal X}\) be totally bounded in \(d_\infty \) and \(A_k \subseteq G\) for all \(k\). With \(N_\infty (\varepsilon ) := N(\overline G, d_\infty , \varepsilon /2) {\lt} \infty \) and \(\overline D := \mathrm{diam}(\mathcal X)\), if \(\int _0^{\overline D}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) then \(\mathsf V(\mathrm{diam}_S(A_k), A_k) \le \int _0^{\overline D} \sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon \) for every sample \(S\) and every \(k\) (case (i) of ‘prop:profiles‘).

Proof ▶

‘prop:profiles-i‘ with \(N(A_k, d_S, \varepsilon ) \le N(A_k, d_\infty , \varepsilon ) \le N(\overline G, d_\infty , \varepsilon /2)\) (‘lem:covering-empSpace-le-unifMaps-internal‘ and Mathlib’s ‘coveringNumber_subset_le‘), which is finite since \(\overline G\) is totally bounded, and \(D_k(S) \le \mathrm{diam}(\mathcal X)\).

(Integrability of the entropy integrand from total boundedness.) Under the hypotheses of ‘lem:ode-profile-saturation-generic‘, the entropy integrand \(\varepsilon \mapsto \sqrt{\log N(A_k, d_S, \varepsilon )}\) is interval-integrable on \([0, \mathrm{diam}_S(A_k)]\) (it is dominated by the integrable majorant).

Proof ▶
Definition 831
✓
#

A map \(\Pi _K : \mathbb R^d \to \mathbb R^d\) is a (Euclidean) projection onto \(K\) if \(\Pi _K(x) \in K\) for all \(x\), \(\Pi _K(x) = x\) for \(x \in K\), and \(\Pi _K\) is \(1\)-Lipschitz. (For a nonempty closed convex \(K\) the nearest-point map has these properties; Mathlib provides only the existence of nearest points, so we take the projection and its properties as hypotheses.)

Definition 832
✓
#

The projected step of size \(h\) along a vector field \(s : K \to \mathbb R^d\): \(T_s(x) := \Pi _K\bigl(x + h\, s(x)\bigr)\), a self-map of \(K\).

Theorem 833
✓

Since \(\Pi _K\) is \(1\)-Lipschitz, \(\| T_s(x) - T_s(y)\| \le \| (x - y) + h\, (s(x) - s(y))\| \).

Proof ▶
Theorem 834
✓

A step of size \(0\) is the identity: \(T_{s,0} = \mathrm{id}\).

Proof ▶
Definition 835
✓
#

A vector field \(s : K \to \mathbb R^d\) is \(\mu \)-strongly monotone and \(\Lambda \)-co-coercive (the properties of \(s = \nabla \phi \) for \(\phi \) \(\mu \)-strongly concave and \(\Lambda \)-smooth) if for all \(x, y \in K\)

\[ \langle x - y, s(x) - s(y)\rangle \le -\mu \| x-y\| ^2, \qquad \langle x - y, s(x) - s(y)\rangle \le -\frac{\mu \Lambda }{\mu +\Lambda }\| x-y\| ^2 - \frac{1}{\mu +\Lambda }\| s(x)-s(y)\| ^2 . \]

(The first is the gradient characterization of strong concavity; the second is the standard consequence of strong concavity and smoothness. We take both as the definition.)

Theorem 836
✓

(Contraction of projected gradient steps.) Let \(0 {\lt} \mu \le \Lambda \), let \(s\) be \(\mu \)-strongly monotone and \(\Lambda \)-co-coercive, and let \(0 {\lt} h \le 2/(\mu +\Lambda )\). Then \(T_s = \Pi _K(\cdot + h s(\cdot ))\) is \(\lambda \)-Lipschitz on \(K\) with \(\lambda := 1 - h\mu \in [0,1)\).

Proof ▶

Write \(u = x - y\), \(v = s(x) - s(y)\), \(a = \| u\| \), \(b = \| v\| \). Strong monotonicity and Cauchy–Schwarz give \(\mu a \le b\). Then \(\| u + hv\| ^2 = a^2 + 2h\langle u,v\rangle + h^2 b^2 \le a^2\bigl(1 - \tfrac {2h\mu \Lambda }{\mu +\Lambda }\bigr) + \bigl(h^2 - \tfrac {2h}{\mu +\Lambda }\bigr) b^2\) and, since \(h^2 - 2h/(\mu +\Lambda ) \le 0\) and \(b^2 \ge \mu ^2 a^2\), this is at most \(a^2\bigl(1 - \tfrac {2h\mu \Lambda }{\mu +\Lambda }\bigr) + \bigl(h^2 - \tfrac {2h}{\mu +\Lambda }\bigr)\mu ^2 a^2 = (1 - h\mu )^2 a^2\). Finally \(\Pi _K\) is \(1\)-Lipschitz.

(Stability of one step.) If \(s\) is \(\Lambda _s\)-Lipschitz and \(h \ge 0\) then \(x \mapsto \Pi _K(x + h s(x))\) is \((1 + h\Lambda _s)\)-Lipschitz.

Proof ▶

\(\| (x-y) + h(s(x)-s(y))\| \le \| x-y\| + h\Lambda _s\| x-y\| \).

Definition 838
✓
#

The fixed-point refinement class \(F_{\rm fp} := \{ T_s : x \mapsto \Pi _K(x + h s(x)) : s \in \mathcal S\} \) for a class \(\mathcal S\) of vector fields on \(K\) and a fixed step size \(h\).

Every \(T \in F_{\rm fp}\) is \((1 - h\mu )\)-Lipschitz, under the hypotheses of ‘lem:fp-contraction‘ for every \(s \in \mathcal S\).

Proof ▶

Every \(T \in F_{\rm fp}\) is non-expanding: \(\mathrm{lip}\, F_{\rm fp} \le 1 - h\mu \le 1\).

Proof ▶

(Saturation for fixed-point refinement, ‘cond:p1‘.) If \(K\) is compact then for every \(\varepsilon {\gt} 0\) and every \(k\), \(N^{\mathrm{ext}}(B(k,F_{\rm fp}), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F_{\rm fp}\rangle }, d_\infty , \varepsilon ) {\lt} \infty \); in particular \(\sup _k N^{\mathrm{ext}}(B(k,F_{\rm fp}), d_\infty , \varepsilon ) {\lt} \infty \).

Proof ▶

‘cond:p1-2c‘ on the compact state space \(K\) with non-expanding generators.

(Explicit entropy bound via ‘cond:p1-ucont‘.) Assume moreover \(h\mu {\lt} 1\) and \(K \ne \emptyset \), and let \(\lambda = 1 - h\mu \), \(m(\varepsilon ) = \lceil \log _{1/\lambda }(2 D_K/\varepsilon )\rceil \) with \(D_K = \mathrm{diam}(K)\). Then for every \(\varepsilon {\gt} 0\) and every \(k\) (generalizing the paper, which assumes \(k \ge m(\varepsilon )\); see ‘cond:p1-ucont‘),

\[ N^{\mathrm{ext}}(B(k,F_{\rm fp}), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(K, \varepsilon /2) + \sum _{j {\lt} m(\varepsilon )} N^{\mathrm{ext}}(F_{\rm fp}^{\, j}, d_\infty , \varepsilon ) . \]

(In Lean the absorbing set is \(K\) itself, with \(L = 0\).)

Proof ▶

‘cond:p1-ucont‘ with \(c = 1 - h\mu \in (0,1)\), invariant set \(A = K\) and bounded absorbing set \(K\) (words of length \(L = 0\)).

(Saturated variance profile for fixed-point refinement.) Under the hypotheses of ‘lem:fp-saturation‘, with \(N_\infty (\varepsilon ) := N(\overline{\langle F_{\rm fp}\rangle }, d_\infty , \varepsilon /2) {\lt} \infty \) and \(D_K = \mathrm{diam}(K)\): if \(\int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) then \(\mathsf V_k(S) \le \mathsf V_\infty := \int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon \) for all \(k\) and all samples \(S\) (case (i) of ‘prop:profiles‘).

Proof ▶

The non-expanding semigroup is equicontinuous, hence totally bounded in \(d_\infty \) (‘thm:caa‘); apply ‘lem:ode-profile-saturation-generic‘.

Definition 844
✓
#

An explicit Euler layer of step size \(h\) at time stamp \(\tau \) for a time-dependent vector field \(s : K \times [0,T] \to \mathbb R^d\): \(T_{s,h,\tau }(x) := \Pi _K\bigl(x + h\, s(x,\tau )\bigr)\).

Definition 845
✓
#

The Euler layer class \(F_T := \{ T_{s,h,\tau } : s \in \mathcal S_T,\ h \in [0,h_0],\ \tau \in [0,T]\} \).

Theorem 846
✓

Each Euler layer with \(h \ge 0\) and \(\Lambda _s\)-Lipschitz drift \(s(\cdot ,\tau )\) is \((1 + h\Lambda _s)\)-Lipschitz.

Proof ▶
Definition 847
✓
#

A scheme of \(n\) steps with a single drift \(s\), step sizes \(h = (h_0, \dots , h_{n-1})\) and time stamps \(\tau = (\tau _0, \dots , \tau _{n-1})\) is the composition \(T_{s,h_{n-1},\tau _{n-1}} \circ \cdots \circ T_{s,h_0,\tau _0}\) (the empty scheme is \(\mathrm{id}\)).

A scheme of \(n\) steps with drift \(s \in \mathcal S_T\), step sizes in \([0,h_0]\) and time stamps in \([0,T]\) belongs to \(B(n, F_T)\).

Proof ▶

(Stability of schemes.) If \(s(\cdot ,\tau )\) is \(\Lambda _s\)-Lipschitz for every \(\tau \) and \(h_i \ge 0\), then the scheme with steps \(h_0, \dots , h_{n-1}\) is \(\prod _i(1 + h_i\Lambda _s) \le \exp (\Lambda _s\sum _i h_i)\)-Lipschitz.

Proof ▶
Definition 850
✓
#

The class \(B_T(k)\) of schemes of at most \(k\) steps with a single drift \(s \in \mathcal S_T\), step sizes \(h_i \in [0,h_0]\), time stamps \(\tau _i \in [0,T]\) and total time \(\sum _i h_i \le T\) (it contains \(\mathrm{id}\), the empty scheme). The consistency condition \(\tau _i = \sum _{j{\lt}i}h_j\) of the paper is dropped; the bounds below hold for this larger class.

Definition 851
✓
#

All schemes: \(\bigcup _k B_T(k)\).

Theorem 852
✓

\(B_T(k) \subseteq B_T(k+1)\): the scheme classes are nested.

Proof ▶

\(B_T(k) \subseteq B(k, F_T)\).

Proof ▶

Every scheme in \(\bigcup _k B_T(k)\) is \(e^{\Lambda _s T}\)-Lipschitz on \(K\).

Proof ▶

‘lem:ode-scheme-lipschitz‘ and \(\sum _i h_i \le T\).

(Stability and saturation.) Let \(K\) be compact and let every drift \(s \in \mathcal S_T\) be \(\Lambda _s\)-Lipschitz in \(x\). Every scheme in \(\bigcup _k B_T(k)\) is \(e^{\Lambda _sT}\)-Lipschitz on \(K\). Consequently \(\bigcup _k B_T(k)\) is equicontinuous on the compact set \(K\), hence totally bounded in \(d_\infty \) (‘thm:caa‘), and

\[ \sup _k N^{\mathrm{ext}}\bigl(B_T(k), d_\infty , \varepsilon \bigr) \le N^{\mathrm{ext}}\Bigl(\bigcup _k B_T(k), d_\infty , \varepsilon \Bigr) =: N_\infty (\varepsilon ) {\lt} \infty \quad (\varepsilon {\gt} 0). \]
Proof ▶

A uniformly Lipschitz family is (uniformly) equicontinuous; Arzelà–Ascoli (‘thm:caa-of-equicontinuous‘) gives total boundedness in \(d_\infty \), monotonicity of the external covering number and ‘lem:aa-external-covering-ne-top‘ the rest.

(Saturated variance profile for Euler schemes.) Under the hypotheses of ‘lem:ode-saturation‘, with \(N_\infty (\varepsilon ) := N(\overline{\bigcup _k B_T(k)}, d_\infty , \varepsilon /2) {\lt} \infty \) and \(D_K = \mathrm{diam}(K)\): if \(\int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) then \(\mathsf V_k(S) \le \mathsf V_\infty := \int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon \) for all \(k\) and all samples \(S\) (case (i) of ‘prop:profiles‘).

Proof ▶

‘lem:ode-profile-saturation-generic‘ with \(G = \bigcup _k B_T(k)\).

Definition 857
✓
#

The identity feature map \(K \hookrightarrow \mathbb R^d\), so that \(H_R = \{ x \mapsto \langle w, x\rangle : \| w\| \le R\} \) is the linear readout class \(H_R(\Phi )\) with \(\Phi = \mathrm{id}_K\).

Theorem 858
✓

\(\mathrm{id}_K\) is \(1\)-Lipschitz and continuous.

Proof ▶

The teacher–student target class of the fixed-point example: \(\mathcal C := \overline{H_R \circ \langle F_{\rm fp}\rangle }^{\, d_\infty }\), which contains the readouts \(x \mapsto \langle w, x^\ast _s\rangle \) of the fixed points (limits of the refinement).

Theorem 860
✓
#

Under the step-size condition \(0 {\lt} h \le 2/(\mu +\Lambda )\) with \(0 {\lt} \mu \le \Lambda \), \(0 \le 1 - h\mu \).

Proof ▶

Every element of \(\langle F_{\rm fp}\rangle \) is \(1\)-Lipschitz, hence continuous.

Proof ▶

For compact \(K\), \(\langle F_{\rm fp}\rangle \) is totally bounded in \(d_\infty \) (Arzelà–Ascoli for the non-expanding semigroup).

Proof ▶

(Estimation term for fixed-point refinement.) Let \(K\) be compact with \(\| x\| \le M_K\) on \(K\), \(R {\gt} 0\), and assume \(\mathsf V_\infty (F_{\rm fp}) {\lt} \infty \) (‘def:sat-integrable‘). Then for every sample \(S\) of size \(n \ge 1\) and every depth \(k\),

\[ \hat{\mathfrak R}_S(H_R \circ B(k, F_{\rm fp})) \le \frac{R M_K}{\sqrt n} + \frac{12 \cdot 1 \cdot R}{\sqrt n}\, \mathsf V_\infty (F_{\rm fp}) \]

(‘cor:var-profiles-p1‘ with \(A\_ H = 1\), \(L = R\), and ‘lem:linear-readouts-rademacher‘).

Proof ▶

Every element of \(H_R \circ B(k, F_{\rm fp})\) is Borel measurable.

Proof ▶

Every element of the target class \(\mathcal C\) is measurable.

Proof ▶

\(\mathcal C \ne \emptyset \) for \(R \ge 0\).

Proof ▶

(Bias for fixed-point refinement.) Let \(K\) be compact with \(D_K = \mathrm{diam}(K)\) and \(R \ge 0\). Against the teacher–student class \(\mathcal C = \overline{H_R \circ \langle F_{\rm fp}\rangle }^{\, d_\infty }\),

\[ \mathrm{bias}(k) = \varepsilon _{\mathrm{model}}(k) \le \beta _\ell \, R\, D_K\, (1 - h\mu )^k \]

by the truncation argument ‘lem:truncation-bias‘ (\(\mathrm{lip}(h) \le R\), \(\mathrm{lip}(u) \le (1-h\mu )^k\) for \(u \in F_{\rm fp}^{\, k}\)) and ‘lem:approx-transfer‘.

Proof ▶

(Fixed-point refinement, rigorous form.) Let \(K \subseteq \mathbb R^d\) (a separable Hilbert space) be compact with \(\| x\| \le M_K\) on \(K\) and \(D_K = \mathrm{diam}(K)\), let \(F_{\rm fp}\) be the projected gradient steps of ‘lem:fp-contraction‘ with \(0 {\lt} h \le 2/(\mu +\Lambda )\), \(H = H_R\) (\(R {\gt} 0\)), and let the target class be \(\mathcal C = \overline{H_R \circ \langle F_{\rm fp}\rangle }^{\, d_\infty }\). Assume \(\mathsf V_\infty (F_{\rm fp}) {\lt} \infty \). For a measurable loss \(\ell : \mathbb R \times \mathcal Y \to [0,b]\), \(\beta _\ell \)-Lipschitz in its first argument, \(n \ge 1\), \(\eta \ge 0\), \(\delta \in (0,1)\): with probability at least \(1 - \delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(\eta \)-empirical minimizer \(\hat h \in H_R \circ B(k, F_{\rm fp})\) satisfies

\[ L[\hat h] - \inf _{\mathcal C} L \le \beta _\ell R D_K (1 - h\mu )^k + \eta + \mathrm{dev}_{\ell ,n,\delta }\Bigl(\frac{R M_K}{\sqrt n} + \frac{12 R}{\sqrt n}\, \mathsf V_\infty (F_{\rm fp})\Bigr), \]

with \(\mathrm{dev}_{\ell ,n,\delta }(B) = 4\beta _\ell B + 6b\sqrt{2\log (4/\delta )/n}\) (‘def:bv-dev‘): the EL regime with \(\alpha = \log (1/(1-h\mu )) \ge h\mu \) and saturated variance.

Proof ▶
Theorem 869
✓
#

(EL balancing for fixed-point refinement.) If \(h\mu {\lt} 1\) and \(n \ge 1\), the depth \(k^\ast := \lceil \log n / (2\log (1/(1-h\mu )))\rceil = \frac{\log n}{2\log (1/(1-h\mu ))} + O(1) \le \frac{\log n}{2h\mu } + O(1)\) satisfies \((1 - h\mu )^{k^\ast } \le n^{-1/2}\).

Proof ▶

(Balanced value \(O(n^{-1/2})\).) Under the hypotheses of ‘prop:ode-fixedpoint‘ with \(h\mu {\lt} 1\), at the depth \(k^\ast = \lceil \log n / (2\log (1/(1-h\mu )))\rceil \),

\[ L[\hat h] - \inf _{\mathcal C} L \le \frac{\beta _\ell R D_K}{\sqrt n} + \eta + \mathrm{dev}_{\ell ,n,\delta }\Bigl(\frac{R M_K + 12 R\, \mathsf V_\infty (F_{\rm fp})}{\sqrt n}\Bigr) \]

with probability at least \(1 - \delta \): the balanced value is of order \(n^{-1/2}\).

Proof ▶
Definition 871
✓
#

The explicit Euler iterates on the ambient space with constant step \(h\) from time \(0\): \(y_0 = x\), \(y_{i+1} = y_i + h\, s(y_i, i h)\).

Theorem 872
✓
#

(One-step consistency of the Euler scheme.) Let \(s\) be \(\Lambda _s\)-Lipschitz in \(x\), \(\Lambda _\tau \)-Lipschitz in \(\tau \) and bounded by \(M_s\), and let \(x\) solve \(\dot x(t) = s(x(t), t)\) on \([t_0, t_0 + h]\) (\(h \ge 0\)). Then

\[ \| x(t_0 + h) - x(t_0) - h\, s(x(t_0), t_0)\| \le \frac{(\Lambda _s M_s + \Lambda _\tau )\, h^2}{2} . \]

(The function \(g(t) = x(t) - x(t_0) - (t - t_0) s(x(t_0),t_0)\) has \(\| g'(t)\| \le \Lambda _s\| x(t) - x(t_0)\| + \Lambda _\tau (t - t_0) \le (\Lambda _s M_s + \Lambda _\tau )(t - t_0)\), and the mean value inequality with the quadratic boundary \(B(t) = (\Lambda _s M_s + \Lambda _\tau )(t-t_0)^2/2\) gives the claim.)

Proof ▶
Theorem 873
✓

(Global error of the explicit Euler scheme.) Let \(s\) be \(\Lambda _s\)-Lipschitz in \(x\), \(\Lambda _\tau \)-Lipschitz in \(\tau \) and bounded by \(M_s\), let \(x\) solve \(\dot x(t) = s(x(t),t)\) on \([0,T]\) (\(T \ge 0\)), and let \(y_0, \dots , y_k\) be the Euler iterates with \(k \ge 1\) equal steps \(h = T/k\) started at \(y_0 = x(0)\). Then

\[ \| x(T) - y_k\| \le C_E\, \frac{T^2}{k}, \qquad C_E := \frac{(\Lambda _s M_s + \Lambda _\tau )\, e^{\Lambda _s T}}{2} . \]

(Discrete Grönwall: \(e_{i+1} \le (1 + h\Lambda _s) e_i + c h^2/2\) with \(c = \Lambda _s M_s + \Lambda _\tau \), hence \(e_k \le \frac{c h^2}{2}\sum _{j{\lt}k}(1+h\Lambda _s)^j \le \frac{c h^2}{2}\, k\, e^{\Lambda _s T}\).)

Proof ▶
Definition 874
✓
#

The equal-step scheme with \(k\) Euler steps of size \(h = T/k\) and time stamps \(\tau _i = i h\): \(T_{s,h,\tau _{k-1}} \circ \cdots \circ T_{s,h,\tau _0}\).

For \(s \in \mathcal S_T\), \(T \ge 0\), \(k \ge 1\) and \(T/k \le h_0\), the equal-step scheme with \(k\) steps belongs to \(B_T(k)\).

Proof ▶

(Inactive projection.) Let \(\tilde s : \mathbb R^d \times \mathbb R \to \mathbb R^d\) extend the drift \(s\) from \(K\), and suppose \(K\) is invariant under the Euler steps, \(x + h\, s(x,\tau ) \in K\) for \(x \in K\). Then the projection is inactive and the scheme with \(k\) equal steps of size \(h\) coincides with the Euler iterates: \(T_{s,h,(k-1)h} \circ \cdots \circ T_{s,h,0}(x_0) = y_k(x_0)\).

Proof ▶
Definition 877
✓

The depth-independent entropy integral of ‘lem:ode-saturation-profile‘: \(\mathsf V_\infty := \int _0^{D_K}\sqrt{\log N(\overline{\bigcup _k B_T(k)}, d_\infty , \varepsilon /2)}\, d\varepsilon \).

Definition 878
✓

The paper’s condition \(\int _0^{D_K}\sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) for the scheme classes: the majorant is interval-integrable.

(Estimation term for fixed-horizon schemes.) Let \(K\) be compact with \(\| x\| \le M_K\) on \(K\), every drift in \(\mathcal S_T \ne \emptyset \) be \(\Lambda _s\)-Lipschitz in \(x\), \(T \ge 0\), \(R {\gt} 0\), and assume the entropy condition of ‘lem:ode-saturation-profile‘. Then for every sample \(S\) of size \(n \ge 1\) and every \(k\),

\[ \hat{\mathfrak R}_S(H_R \circ B_T(k)) \le \frac{R M_K}{\sqrt n} + \frac{12 \cdot 1 \cdot R}{\sqrt n}\, \mathsf V_\infty \]

(‘thm:hidden-decomp‘ on the scheme class, ‘lem:ode-saturation-profile‘ and ‘lem:linear-readouts-rademacher‘).

Proof ▶

Every scheme in \(\bigcup _k B_T(k)\) is Lipschitz, hence continuous.

Proof ▶

Every element of \(H_R \circ B_T(k)\) is Borel measurable.

Proof ▶

(Bias for fixed-horizon integration.) Let the target class be the readouts of the endpoint map of the exact flow of \(s^\ast \in \mathcal S_T\): \(\mathcal C = \{ x_0 \mapsto \langle w, \Phi _T(x_0)\rangle : \| w\| \le R\} \), where for every \(x_0 \in K\) the flow \(\Phi _T(x_0) = x(T)\) is given by a solution of \(\dot x = \tilde s(x, t)\), \(x(0) = x_0\), for an extension \(\tilde s\) of \(s^\ast \) which is \(\Lambda _s\)-Lipschitz in \(x\), \(\Lambda _\tau \)-Lipschitz in \(\tau \) and bounded by \(M_s\). Assume the projection is inactive along the Euler steps of size \(T/k\) (\(K\) is invariant), \(k \ge 1\) and \(T/k \le h_0\). Then

\[ \mathrm{bias}(k) = \varepsilon _{\mathrm{model}}(k) \le \beta _\ell \, R\, C_E\, \frac{T^2}{k}, \qquad C_E = \frac{(\Lambda _s M_s + \Lambda _\tau )e^{\Lambda _s T}}{2}, \]

by ‘lem:ode-euler-error‘, ‘lem:ode-scheme-eq-euler‘ and ‘lem:approx-transfer‘.

Proof ▶

(Fixed-horizon integration, rigorous form, \(p = 1\).) Let \(K \subseteq \mathbb R^d\) (a separable Hilbert space) be compact with \(\| x\| \le M_K\) on \(K\), let every drift in \(\mathcal S_T\) be \(\Lambda _s\)-Lipschitz in \(x\), \(H = H_R\) (\(R {\gt} 0\)), and let the target class be the flow readouts \(\mathcal C = \{ \langle w, \Phi _T(\cdot )\rangle : \| w\| \le R\} \) of a teacher \(s^\ast \in \mathcal S_T\) as in ‘lem:ode-horizon-bias‘ (projection inactive, \(k \ge 1\), \(T/k \le h_0\)). Assume the entropy condition \(\mathsf V_\infty {\lt} \infty \) of ‘lem:ode-saturation-profile‘. For a measurable loss \(\ell : \mathbb R \times \mathcal Y \to [0,b]\), \(\beta _\ell \)-Lipschitz in its first argument, \(n \ge 1\), \(\eta \ge 0\), \(\delta \in (0,1)\): with probability at least \(1 - \delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(\eta \)-empirical minimizer \(\hat h \in H_R \circ B_T(k)\) satisfies

\[ L[\hat h] - \inf _{\mathcal C} L \le \beta _\ell R C_E\, \frac{T^2}{k} + \eta + \mathrm{dev}_{\ell ,n,\delta }\Bigl(\frac{R M_K}{\sqrt n} + \frac{12 R}{\sqrt n}\, \mathsf V_\infty \Bigr), \]

with \(C_E = (\Lambda _s M_s + \Lambda _\tau )e^{\Lambda _s T}/2\) and \(\mathrm{dev}_{\ell ,n,\delta }(B) = 4\beta _\ell B + 6b\sqrt{2\log (4/\delta )/n}\) (‘def:bv-dev‘): the PL regime with \(\beta = p = 1\) and saturated variance.

Proof ▶
Theorem 884
✓
#

(PL balancing with saturated variance, \(p = 1\).) For \(n \ge 1\) the depth \(k^\ast := \lceil \sqrt n\rceil \ge 1\) satisfies \(1/k^\ast \le n^{-1/2}\), so \(k^\ast \asymp n^{1/2} = n^{1/(2p)}\) balances the bias \(k^{-1}\) against the saturated variance \(n^{-1/2}\).

Proof ▶

(Balanced value \(O(n^{-1/2})\).) Under the hypotheses of ‘prop:ode-horizon‘ with \(k^\ast = \lceil \sqrt n\rceil \) (and \(T/k^\ast \le h_0\), projection inactive at step size \(T/k^\ast \)),

\[ L[\hat h] - \inf _{\mathcal C} L \le \frac{\beta _\ell R C_E T^2}{\sqrt n} + \eta + \mathrm{dev}_{\ell ,n,\delta }\Bigl(\frac{R M_K + 12 R\, \mathsf V_\infty }{\sqrt n}\Bigr) \]

with probability at least \(1 - \delta \): the balanced value is of order \(n^{-1/2}\).

Proof ▶
Definition 886
✓

The class of equal-step schemes of at most \(k\) steps, \(E_T(k) := \{ \Phi _{s,m} : s \in \mathcal S_T,\ 0 \le m \le k\} \), where \(\Phi _{s,m} = T_{s,T/m,\tau _m} \circ \cdots \circ T_{s,T/m,\tau _1}\) with \(\tau _i = (i-1)T/m\) is the \(m\)-step equal-step Euler scheme and \(\Phi _{s,0} = \mathrm{id}\).

Definition 887
✓
#

The space of drifts restricted to \(K \times [0,T]\) with the sup-norm (pseudo-e)metric \(\| s - s'\| _\infty := \sup _{x \in K,\ \tau \in [0,T]}\| s(x,\tau ) - s'(x,\tau )\| \); in Lean it is Mathlib’s \((K \times [0,T]) \to _{\mathrm u} E\).

Definition 888
✓

\(\| \cdot \| _\infty \) is a pseudo-emetric on the restricted drifts (Mathlib’s instance on the uniform function space).

Definition 889
✓
#

The restriction of a drift \(s : K \times \mathbb R \to \mathbb R^d\) to \(K \times [0,T]\), viewed in the sup-norm space.

Theorem 890
✓

\(\| s - s'\| _\infty = \sup _{x \in K,\ \tau \in [0,T]} \| s(x,\tau ) - s'(x,\tau )\| \) (as an extended distance).

Proof ▶

\(\| s(x,\tau ) - s'(x,\tau )\| \le \| s - s'\| _\infty \) for \(x \in K\) and \(\tau \in [0,T]\).

Proof ▶
Definition 892
✓
#

The extension of a restricted drift \(c : K \times [0,T] \to \mathbb R^d\) to \(K \times \mathbb R\) by \(0\) outside \([0,T]\) (used to lift the centres of a cover of \(\mathcal S_T\) to drifts).

Restricting the extension gives back the restricted drift.

Proof ▶
Theorem 894
✓

(Two drifts.) Since \(\Pi _K\) is \(1\)-Lipschitz, \(\| T_{s}(x) - T_{s'}(y)\| \le \| (x - y) + h\, (s(x) - s'(y))\| \).

Proof ▶

(Stability with respect to the drift; discrete Grönwall.) Let \(s(\cdot ,\tau )\) be \(\Lambda _s\)-Lipschitz for every \(\tau \), let \(h_i \ge 0\), and suppose \(\| s(x,\tau _i) - s'(x,\tau _i)\| \le \delta \) for all \(x \in K\) and all stamps \(\tau _i\) used by the scheme. Then for every \(x\),

\[ \bigl\| y_n - y_n'\bigr\| \le \delta \, \Bigl(\sum _i h_i\Bigr) \exp \Bigl(\Lambda _s\sum _i h_i\Bigr), \]

where \(y_n, y_n'\) are the schemes of \(s\) and \(s'\) with the same steps and stamps started at \(x\). Indeed \(\| y_{i} - y_{i}'\| \le (1 + h_i\Lambda _s)\| y_{i-1} - y_{i-1}'\| + h_i\delta \) and \(1 + h\Lambda _s \le e^{h\Lambda _s}\).

Proof ▶

A scheme all of whose steps have size \(0\) is the identity.

Proof ▶

With horizon \(T = 0\) every equal-step scheme is the identity.

Proof ▶

(Pointwise stability of equal-step schemes.) If \(s(\cdot ,\tau )\) is \(\Lambda _s\)-Lipschitz for every \(\tau \), \(T \ge 0\), and \(\| s(x,\tau ) - s'(x,\tau )\| \le \delta \) for all \(x \in K\), \(\tau \in [0,T]\), then \(\| \Phi _{s,m}(x) - \Phi _{s',m}(x)\| \le Te^{\Lambda _sT}\delta \) for all \(m \ge 0\) and \(x\).

Proof ▶

‘lem:ode-scheme-dist‘ with \(h_i = T/m\), \(\sum _i h_i = T\) and stamps \(\tau _i = (i-1)T/m \in [0,T]\).

(Stability of equal-step schemes in \(d_\infty \).) If \(s(\cdot ,\tau )\) is \(\Lambda _s\)-Lipschitz for every \(\tau \) and \(T \ge 0\), then for every drift \(s'\) and every \(m \ge 0\),

\[ d_\infty (\Phi _{s,m}, \Phi _{s',m}) \le Te^{\Lambda _sT}\, \| s - s'\| _\infty , \qquad \| s - s'\| _\infty = \sup _{x \in K,\ \tau \in [0,T]}\| s(x,\tau ) - s'(x,\tau )\| . \]

(Only the Lipschitz constant of \(s\) is used; \(s'\) may be any drift.)

Proof ▶

If \(\| s - s'\| _\infty = \infty \) the bound is trivial unless \(T = 0\), when both schemes are the identity; otherwise apply ‘lem:ode-equal-scheme-dist‘ with \(\delta = \| s - s'\| _\infty \) and take the supremum over \(x\).

(Covering the \(m\)-step schemes.) Under the hypotheses of ‘lem:ode-equal-scheme-uniformdist‘ for every \(s \in \mathcal S_T\), the image of an \(\varepsilon e^{-\Lambda _sT}/T\)-cover of \(\mathcal S_T\) (in \(\| \cdot \| _\infty \) on \(K \times [0,T]\), centres extended by \(0\) outside \([0,T]\)) under \(s \mapsto \Phi _{s,m}\) is an \(\varepsilon \)-cover of \(\{ \Phi _{s,m} : s \in \mathcal S_T\} \); hence \(N^{\mathrm{ext}}(\{ \Phi _{s,m} : s \in \mathcal S_T\} , d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\mathcal S_T, \| \cdot \| _\infty , \varepsilon e^{-\Lambda _sT}/T)\).

Proof ▶

\(E_T(k) \subseteq \{ \mathrm{id}\} \cup \bigcup _{m=1}^k \{ \Phi _{s,m} : s \in \mathcal S_T\} \).

Proof ▶

(Covering bound for equal-step schemes.) If every drift \(s \in \mathcal S_T\) is \(\Lambda _s\)-Lipschitz in \(x\) and \(T \ge 0\), then for every \(k \ge 0\) and \(\varepsilon \ge 0\),

\[ N^{\mathrm{ext}}\bigl(E_T(k), d_\infty , \varepsilon \bigr) \le 1 + k\, N^{\mathrm{ext}}\bigl(\mathcal S_T, \| \cdot \| _\infty , \varepsilon e^{-\Lambda _sT}/T\bigr) \]

(the radius is \(\varepsilon /(Te^{\Lambda _sT})\), equal to \(0\) when \(T = 0\)).

Proof ▶

Subadditivity over the union \(\{ \mathrm{id}\} \cup \bigcup _{m=1}^k\{ \Phi _{s,m}\} \) and ‘lem:ode-equal-scheme-image-covering‘ for each \(m\).

Theorem 903
✓

The equal-step scheme classes are nested: \(E_T(k) \subseteq E_T(k+1)\).

Proof ▶

\(E_T(k) \subseteq B_T(k)\) when \(0 \le T \le h_0\) (the equal steps \(T/m\), \(1 \le m \le k\), are admissible).

Proof ▶

(Explicit entropy of equal-step schemes.) Let every drift \(s \in \mathcal S_T\) be \(\Lambda _s\)-Lipschitz in \(x\) and \(T \ge 0\). Then for all \(s, s' \in \mathcal S_T\) and \(m \ge 0\),

\[ d_\infty (\Phi _{s,m}, \Phi _{s',m}) \le Te^{\Lambda _sT}\, \| s - s'\| _\infty , \qquad \| s - s'\| _\infty := \sup _{x \in K,\ \tau \in [0,T]}\| s(x,\tau ) - s'(x,\tau )\| , \]

and consequently, for every \(k \ge 0\) and \(\varepsilon \ge 0\),

\[ N^{\mathrm{ext}}\bigl(E_T(k), d_\infty , \varepsilon \bigr) \le 1 + k\, N^{\mathrm{ext}}\bigl(\mathcal S_T, \| \cdot \| _\infty , \varepsilon e^{-\Lambda _sT}/T\bigr) . \]

The entropy-integral consequence is ‘lem:ode-scheme-entropy-profile‘.

Proof ▶

(Entropy integral of equal-step schemes.) Let \(K\) be compact, every drift \(s \in \mathcal S_T\) be \(\Lambda _s\)-Lipschitz in \(x\), \(T {\gt} 0\), and suppose \(N^{\mathrm{ext}}(\mathcal S_T, \| \cdot \| _\infty , \rho ) {\lt} \infty \) for all \(\rho {\gt} 0\) and that \(\varepsilon \mapsto \sqrt{\log N^{\mathrm{ext}}(\mathcal S_T, \| \cdot \| _\infty , \varepsilon e^{-\Lambda _sT}/(2T))}\) is integrable on \([0, D_K]\), \(D_K = \mathrm{diam}(K)\). Then for every sample \(S\) and every \(k\), for the class \(E_T(k)\),

\[ \mathsf V_k(S) \le D_K\sqrt{\log (k+1)} + \int _0^{D_K}\sqrt{\log N^{\mathrm{ext}}\bigl( \mathcal S_T, \| \cdot \| _\infty , \varepsilon e^{-\Lambda _sT}/(2T)\bigr)}\, d\varepsilon . \]

(The paper has \(\varepsilon e^{-\Lambda _sT}/T\): the factor \(2\) is the price of comparing the internal covering number in \(d_S\) defining \(\mathsf V_k(S)\) with the external one in \(d_\infty \), ‘lem:covering-empSpace-le-external-unifMaps‘.)

Proof ▶

Pointwise, \(\log N(E_T(k), d_S, \varepsilon ) \le \log N^{\mathrm{ext}}(E_T(k), d_\infty , \varepsilon /2) \le \log (1 + kN) \le \log (k+1) + \log N\) with \(N = N^{\mathrm{ext}}(\mathcal S_T, \varepsilon e^{-\Lambda _sT}/(2T))\); take square roots termwise and integrate over \((0, D_K]\), using \(D_k(S) \le D_K\).