7 Worked examples (Appendices J–M)
7.1 Shared glue for the worked examples (regimes)
\(L[f] \ge 0\) since the loss is nonnegative.
(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
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\).
For \(h = \langle w, \Phi (\cdot )\rangle \in H_R(\Phi )\), \(|h(x)| \le R\, \| \Phi (x)\| \).
If \(\Phi \) is \(L_\Phi \)-Lipschitz and \(R \ge 0\) then every \(h \in H_R(\Phi )\) is \(R L_\Phi \)-Lipschitz.
For \(R {\gt} 0\), \(H_R(\Phi ) = H_1(R\, \Phi )\): the radius can be absorbed into the feature map.
(‘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\).
\(H_R(\Phi ) = H_1(R\Phi )\) and \(R\Phi \) is \(RL_\Phi \)-Lipschitz.
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.
(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\),
(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.)
If \(F\) is finite then every word ball \(B(k,F)\) is finite.
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.
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\).
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\).
A finite hidden-layer class has a countable uniformly dense subset (itself).
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 )\)).
(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)\).
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‘).
Every element of the uniform closure of a class of measurable functions is measurable (a uniform limit of measurable functions is a pointwise limit).
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)\):
(All regime propositions below are stated in terms of this quantity, so that the constants of ‘thm:bv‘ enter in one place only.)
\(B \mapsto \mathrm{dev}_{\ell ,n,\delta }(B)\) is nondecreasing when \(\beta _\ell \ge 0\).
(‘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
‘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)\).
(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 \).
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 \).
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)]\).
(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)\).
\(k \log (1/\theta ) \ge \tfrac 12\log n = \log \sqrt n\), so \((1/\theta )^k \ge \sqrt n\).
(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}\).
7.2 Implementation with controlled uniform error (Appendix J, prop:implementation; proof in J.3)
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)\)).
\(f_{[]} = \mathrm{id}\).
\(f_{f :: u} = f \circ f_u\).
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\).
\(\tilde f_{[]} = \mathrm{id}\).
\(\tilde f_{f :: u} = \tilde f \circ \tilde f_u\).
If all layers of \(u\) lie in \(F\) and \(|u| \le k\) then \(f_u \in B(k,F)\).
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)\).
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\).
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\),
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\).
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
(Stated for an arbitrary \(\iota \) with this property; such an \(\iota \) exists by ‘lem:impl-map-exists‘.)
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\).
Combine ‘lem:impl-map-exists‘ and ‘prop:implementation-b‘.
If \(0 \le \Lambda \le 1\) then \(\sum _{i{\lt}k} \Lambda ^i \le k\).
If \(0 \le \Lambda {\lt} 1\) then \(\sum _{i{\lt}k} \Lambda ^i \le 1/(1-\Lambda )\).
\(\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 \).
‘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 )\).
‘prop:implementation-b‘ and \(\sum _{i{\lt}k} \Lambda ^i \le 1/(1-\Lambda )\).
\(\mathrm{relu}(t) = \max \{ 0, t\} \).
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.
\(t = \mathrm{relu}(t) - \mathrm{relu}(-t)\).
(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}\),
i.e. \(x \mapsto Ax + b\) is one ReLU layer of width \(2d\).
\(\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\).
The parameters \((W_2, W_1, b)\) of a ReLU layer of width \(2d\) on \(\mathbb R^d\).
The ReLU layer of width \(2d\) with parameters \((W_2, W_1, b)\).
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\).
Induction on \(u\), replacing each affine layer by the ReLU layer of ‘lem:affine-eq-relu‘.
The identity implementation map has zero implementation error: \(\varepsilon _{\mathrm{imp}} = 0\) for \(\iota = \mathrm{id}\) on any class.
(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\).
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‘.
(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.)
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)
Packing numbers are monotone in the set: \(A \subseteq B\) implies \(M(A, \varepsilon ) \le M(B, \varepsilon )\).
(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\).
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))\).
(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.
Every separated subset is finite (its finite subsets have bounded cardinality) and its cardinality is bounded by ‘lem:relu-volumetric-finset‘.
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).
(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 \} \),
(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\).)
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\).
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\} \).
\(\mathrm{relu}(z)_i = \max \{ z_i, 0\} \).
\(\mathrm{relu}\) is \(1\)-Lipschitz for the Euclidean norm, since \(|\max \{ a,0\} - \max \{ b,0\} | \le |a - b|\) coordinatewise.
\(\mathrm{relu}(0) = 0\).
\(\| \mathrm{relu}(z)\| \le \| z\| \).
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.
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\).
The admissible parameters: \(\| W\| _{\rm op}, \| V\| _{\rm op} \le \beta _W\), \(\| b\| , \| c\| \le \beta \) and \(\mathrm{lip}(f_\vartheta ) \le \Lambda \).
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.
\(F_\Lambda \ne \emptyset \): the zero parameters give the constant map \(x \mapsto \Pi _K(0)\).
The admissible parameters lie in the sup-norm ball of radius \(\max \{ \beta _W, \beta \} \).
(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
(Only these three parameter bounds are used, as in the paper’s 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.
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‘).
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.)
\(L_F \ge 1\) when \(R_K \ge 0\).
\(\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 }\).
The parameter space has dimension \(p = 2mw + w + m\), \(m = \dim E\).
(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‘.
(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 )\).
(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 '\),
(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).
If \(K\) is bounded then so is the state space \(K\) (as a metric space in its own right).
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).
(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‘.
For \(N \ge 1\) in \(\mathbb N \cup \{ \infty \} \), \(\sum _{l{\lt}m} N^l \le m N^m\).
\(N^{\mathrm{ext}}(F_\Lambda , d_\infty , \varepsilon ) \ge 1\) (the class is nonempty).
(‘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\),
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\).)
‘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‘).
\(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 \).
‘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‘).
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 \} \),
(‘cor:envelope-profiles-a-one-add‘ with ‘lem:relu-layer-covering‘).
(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‘,
(‘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\),
(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‘.
(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 \).
(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})\).
(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‘.
The clipping \(\Pi _{[0,1]}(x) = \max \{ 0, \min \{ 1, x\} \} \), a \(1\)-Lipschitz retraction of \(\mathbb R\) onto \([0,1]\).
\(\Pi _{[0,1]}(x) = x\) for \(x \in [0,1]\).
\(\Pi _{[0,1]}\) is a \(1\)-Lipschitz retraction onto \([0,1]\) (‘def:ode-projection‘).
\(x \mapsto ax + b\) is \(L\)-Lipschitz on \(\mathbb R\) when \(|a| \le L\).
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]\).
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]\).
\(g_0\) maps \([0,1]\) into \([0,1]\).
\(g_1\) maps \([0,1]\) into \([0,1]\).
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\)).
On \([0,1]\), \(g_1(x) = \max \{ \min \{ 5/8, -20x + 125/8\} , \min \{ \tfrac {16}{3}x - \tfrac {25}{6}, -12x + 101/8\} \} \).
\(g_0\) is \(20\)-Lipschitz on \([0,1]\) (max–min of \(20\)-Lipschitz affine maps).
\(g_1\) is \(20\)-Lipschitz on \([0,1]\).
\(g_0\) as a self-map of the state space \([0,1]\).
\(g_1\) as a self-map of the state space \([0,1]\).
\(g_0 : [0,1] \to [0,1]\) is \(20\)-Lipschitz.
\(g_1 : [0,1] \to [0,1]\) is \(20\)-Lipschitz.
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‘.
Input weights of the expand-and-reset blocks at width \(4 + w'\): \(u = (1,1,1,1,0,\dots ,0)\).
Thresholds of \(g_0\): \(t = (0, \eta , 1/4 - \eta , 1/4, 0, \dots , 0)\).
Output weights of \(g_0\) (the slope increments at the breakpoints): \(v = (-12, 52/3, -76/3, 20, 0, \dots , 0)\).
Thresholds of \(g_1\): \(t = (3/4, 3/4 + \eta , 1 - \eta , 0, 0, \dots , 0)\).
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\)).
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\).
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\).
The unit sum of \(g_0\) at width \(4 + w'\) (the padding units vanish).
The unit sum of \(g_1\) at width \(4 + w'\).
(\(g_0\) is a ReLU block of width \(4 + w'\).) With the clipping \(\Pi _{[0,1]}\), \(f_{\vartheta _0} = g_0\) on \([0,1]\).
(\(g_1\) is a ReLU block of width \(4 + w'\).) \(f_{\vartheta _1} = g_1\) on \([0,1]\).
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\).
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\).
The two generators \(f = (g_0, g_1)\).
The chambers \(U_0 = [0, 1/4]\), \(U_1 = [3/4, 1]\).
The coding cores \(V_0 = [\eta , 1/4 - \eta ]\), \(V_1 = [3/4 + \eta , 1 - \eta ]\).
The anchors \(a_0 = 3/8\), \(a_1 = 5/8\).
The marker \(q = 1/2\).
\(V_i \subseteq U_i\).
(Disjoint chambers.) \(U_0 \cap U_1 = \emptyset \).
(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]\).
The anchors lie outside both chambers.
\(g_i(A) \subseteq A\) for \(A = \{ a_0, a_1\} \) (each anchor is reset to \(a_i\)).
(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\).
(Marker separation.) \(d(q, a_i) = 1/8\) for \(i = 0, 1\).
(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.
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.
(‘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
(The paper states \(w \ge 5\); the two maps have three interior breakpoints each, so width \(4\) suffices.)
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 Chain-of-thought style symbolic computation (Appendix L)
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).
For \(x \ne y\) the first mismatch index is \(n(x,y) := \min \{ j \ge 0 : x_j \ne y_j\} \).
\(x_{n(x,y)} \ne y_{n(x,y)}\).
\(L \le n(x,y)\) if and only if \(x_j = y_j\) for all \(j {\lt} L\).
\(x_j = y_j\) for all \(j {\lt} n(x,y)\).
\(n(x,y) = n(y,x)\).
Both indices are characterized by the same prefix-agreement property.
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)\).
\(0 {\lt} \theta \) (as a real number).
\(\theta {\lt} 1\) (as a real number).
For \(x \ne y\), \(d_\theta (x,y) = \theta ^{n(x,y)}\).
\(d_\theta (x,y) = d_\theta (y,x)\).
(Prefix characterization.) \(d_\theta (x,y) \le \theta ^L\) if and only if \(x_j = y_j\) for all \(j {\lt} L\).
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.
\(d_\theta (x,y) \ge 0\).
\(d_\theta (x,y) \le 1\): the scratchpad space has diameter at most \(1\).
The case \(L = 0\) of the prefix characterization.
(Ultrametric inequality.) \(d_\theta (x,z) \le \max \{ d_\theta (x,y), d_\theta (y,z)\} \).
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\).
\((\mathcal A^{\mathbb N}, d_\theta )\) is a metric space (indeed an ultrametric space).
On \(\mathcal A^{\mathbb N}\) the distance is \(d_\theta \).
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\).
\(d_\theta (x,y) \le 1\), i.e. \(\mathrm{diam}(\mathcal A^{\mathbb N}) \le 1\).
\(d_\theta (x,y) \le 1\) as an extended distance.
If \(x_0 \ne y_0\) then \(d_\theta (x,y) = 1\).
\(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}\).
\(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)}\).
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.)
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\).
A write step prepends a symbol: \(g_a(x) := (a, x_0, x_1, \dots )\) for \(a \in \mathcal A\).
The append-only step family \(F_{\rm w} := \{ g_a : a \in \mathcal A\} \).
\(g_a(x)_0 = a\).
\(g_a(x)_{i+1} = x_i\).
\(a \mapsto g_a\) is injective, so \(|F_{\rm w}| = |\mathcal A| = m\).
\(F_{\rm w}\) is finite.
\(|F_{\rm w}| = m = |\mathcal A|\).
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\).
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).
(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\).
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 \).
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)\).
The resolution length \(\ell (\varepsilon ) := \lceil \log (1/\varepsilon )/\log (1/\theta ) \rceil \) (a natural number; \(0\) for \(\varepsilon \ge 1\)).
\(\log (1/\theta ) {\gt} 0\).
\(\theta ^{\ell (\varepsilon )} \le \varepsilon \) for every \(\varepsilon {\gt} 0\).
\(\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 )}\).
For \(0 {\lt} \varepsilon \le 1\), \(\ell (\varepsilon ) \le \log (1/\varepsilon )/\log (1/\theta ) + 1\).
\(\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.
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\),
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})\)).
‘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\).
\(\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\),
(Case (i) of ‘prop:profiles‘: the entropy integral does not depend on the depth \(k\).)
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‘).
The alphabet \(\mathcal A = [r] \cup \{ \bullet \} \) with \(r\) active symbols and one padding symbol \(\bullet \).
The shift \(\sigma (x) = (x_1, x_2, \dots )\).
The constant sequence \(\bar a = (a, a, \dots )\).
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\).
The branching step family \(F_{\rm b} := \{ f_a : a \in [r]\} \).
\(\sigma (g_a(y)) = y\).
\(\sigma (\bar a) = \bar a\).
If \(x_0 \ne a\) then \(f_a(x) = \bar a\).
If \(x_0 = a\) then \(f_a(x) = \sigma (x)\).
\(f_a(\bar a) = \bar a\) and \(f_a(\bar b) = \bar a\) for \(b \ne a\): the anchors are mapped to anchors.
\(a \mapsto f_a\) is injective, so \(|F_{\rm b}| = r\).
\(f_a(\bar a) = \bar a\) while \(f_b(\bar a) = \bar b\).
\(|F_{\rm b}| = r\).
(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\).
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\),
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}\).
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\)).
‘prop:profiles-finite‘ with \(|B(k,F_{\rm b})| \le r^{k+1}\) and \(D_k(S) \le 1\).
\(f_{u \cdot v} = f_v \circ f_u\) (the first letter acts first).
Every \(g \in B(k, \{ f_1, \dots , f_r\} )\) is \(f_u\) for a word \(u \in [r]^{\le k}\).
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).
\(\sigma ^j(x) = (x_{i+j})_{i \ge 0}\).
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.
(Closed form, success.) If \(x \in [u]\) then \(f_u(x) = \sigma ^{|u|}(x)\).
(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.
(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}\),
(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\).
(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\).
(Programs are close to constants on the sample.) For every program \(u\) (with last letter \(u_j\), or any \(b\) if \(u\) is empty),
since \(f_u = \bar u_j\) off \([u]\) and \(\mathrm{diam}(\mathcal A^{\mathbb N}) = 1\).
If \(\# \{ i : X_i \in [u]\} \le \varepsilon ^2 n\) then \(d_S(f_u, \bar u_j) \le \varepsilon \).
(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\)),
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\).
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.
\(1 + r + \sum _{j=1}^k\min \{ r^j, n, \lfloor \varepsilon ^{-2}\rfloor \} \le 1 + r + k\min \{ n, \lfloor \varepsilon ^{-2}\rfloor \} \).
(Root-logarithmic empirical entropy integral for branching steps.) For every sample \(S\) and every \(k\),
(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}\)).
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]\)),
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.
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})\).
\(\| \Phi _L(x)\| = 1\) (in particular \(\| \Phi _L\| \le 1\)).
If \(x, y\) agree on the first \(L\) symbols then \(\Phi _L(x) = \Phi _L(y)\).
Distinct one-hot vectors are at Euclidean distance \(\sqrt2\): \(\| e_u - e_v\| = \sqrt2\) for \(u \ne v\).
\(\| 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)\).)
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}\).
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)\).
\(\mathsf V_\infty (m,\theta ) \ge 0\).
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.
(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.
Every element of the target class \(\mathcal C\) is measurable (a uniform limit of continuous functions).
\(\mathcal C \ne \emptyset \) (it contains the zero readout) when \(R \ge 0\).
(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\).
(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).
(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\)).
(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\),
(‘thm:hidden-decomp-depth‘ with \(A\_ H = 1\), ‘lem:cot-append-profile‘ and ‘lem:cot-readout-rademacher‘).
(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 }\),
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‘.
(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
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\).)
(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}\).
(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
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})\).
7.5 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‘).
‘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).
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.)
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\).
Since \(\Pi _K\) is \(1\)-Lipschitz, \(\| T_s(x) - T_s(y)\| \le \| (x - y) + h\, (s(x) - s(y))\| \).
A step of size \(0\) is the identity: \(T_{s,0} = \mathrm{id}\).
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\)
(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.)
(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)\).
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.
\(\| (x-y) + h(s(x)-s(y))\| \le \| x-y\| + h\Lambda _s\| x-y\| \).
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\).
Every \(T \in F_{\rm fp}\) is non-expanding: \(\mathrm{lip}\, F_{\rm fp} \le 1 - h\mu \le 1\).
(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 \).
‘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‘),
(In Lean the absorbing set is \(K\) itself, with \(L = 0\).)
‘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‘).
The non-expanding semigroup is equicontinuous, hence totally bounded in \(d_\infty \) (‘thm:caa‘); apply ‘lem:ode-profile-saturation-generic‘.
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)\).
The Euler layer class \(F_T := \{ T_{s,h,\tau } : s \in \mathcal S_T,\ h \in [0,h_0],\ \tau \in [0,T]\} \).
Each Euler layer with \(h \ge 0\) and \(\Lambda _s\)-Lipschitz drift \(s(\cdot ,\tau )\) is \((1 + h\Lambda _s)\)-Lipschitz.
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)\).
(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.
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.
All schemes: \(\bigcup _k B_T(k)\).
\(B_T(k) \subseteq B_T(k+1)\): the scheme classes are nested.
\(B_T(k) \subseteq B(k, F_T)\).
Every scheme in \(\bigcup _k B_T(k)\) is \(e^{\Lambda _s T}\)-Lipschitz on \(K\).
‘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
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‘).
‘lem:ode-profile-saturation-generic‘ with \(G = \bigcup _k B_T(k)\).
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\).
\(\mathrm{id}_K\) is \(1\)-Lipschitz and continuous.
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).
Under the step-size condition \(0 {\lt} h \le 2/(\mu +\Lambda )\) with \(0 {\lt} \mu \le \Lambda \), \(0 \le 1 - h\mu \).
Every element of \(\langle F_{\rm fp}\rangle \) is \(1\)-Lipschitz, hence continuous.
For compact \(K\), \(\langle F_{\rm fp}\rangle \) is totally bounded in \(d_\infty \) (Arzelà–Ascoli for the non-expanding semigroup).
(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\),
(‘cor:var-profiles-p1‘ with \(A\_ H = 1\), \(L = R\), and ‘lem:linear-readouts-rademacher‘).
Every element of \(H_R \circ B(k, F_{\rm fp})\) is Borel measurable.
Every element of the target class \(\mathcal C\) is measurable.
\(\mathcal C \ne \emptyset \) for \(R \ge 0\).
(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 }\),
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‘.
(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
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.
(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}\).
(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 \),
with probability at least \(1 - \delta \): the balanced value is of order \(n^{-1/2}\).
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)\).
(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
(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.)
(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
(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}\).)
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)\).
(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)\).
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 \).
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\),
(‘thm:hidden-decomp‘ on the scheme class, ‘lem:ode-saturation-profile‘ and ‘lem:linear-readouts-rademacher‘).
Every scheme in \(\bigcup _k B_T(k)\) is Lipschitz, hence continuous.
Every element of \(H_R \circ B_T(k)\) is Borel measurable.
(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
by ‘lem:ode-euler-error‘, ‘lem:ode-scheme-eq-euler‘ and ‘lem:approx-transfer‘.
(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
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.
(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}\).
(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 \)),
with probability at least \(1 - \delta \): the balanced value is of order \(n^{-1/2}\).
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}\).
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\).
\(\| \cdot \| _\infty \) is a pseudo-emetric on the restricted drifts (Mathlib’s instance on the uniform function space).
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.
\(\| s - s'\| _\infty = \sup _{x \in K,\ \tau \in [0,T]} \| s(x,\tau ) - s'(x,\tau )\| \) (as an extended distance).
\(\| s(x,\tau ) - s'(x,\tau )\| \le \| s - s'\| _\infty \) for \(x \in K\) and \(\tau \in [0,T]\).
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.
(Two drifts.) Since \(\Pi _K\) is \(1\)-Lipschitz, \(\| T_{s}(x) - T_{s'}(y)\| \le \| (x - y) + h\, (s(x) - s'(y))\| \).
(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\),
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}\).
A scheme all of whose steps have size \(0\) is the identity.
With horizon \(T = 0\) every equal-step scheme is the identity.
(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\).
‘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\),
(Only the Lipschitz constant of \(s\) is used; \(s'\) may be any drift.)
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)\).
\(E_T(k) \subseteq \{ \mathrm{id}\} \cup \bigcup _{m=1}^k \{ \Phi _{s,m} : s \in \mathcal S_T\} \).
(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\),
(the radius is \(\varepsilon /(Te^{\Lambda _sT})\), equal to \(0\) when \(T = 0\)).
Subadditivity over the union \(\{ \mathrm{id}\} \cup \bigcup _{m=1}^k\{ \Phi _{s,m}\} \) and ‘lem:ode-equal-scheme-image-covering‘ for each \(m\).
The equal-step scheme classes are nested: \(E_T(k) \subseteq E_T(k+1)\).
\(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).
(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\),
and consequently, for every \(k \ge 0\) and \(\varepsilon \ge 0\),
The entropy-integral consequence is ‘lem:ode-scheme-entropy-profile‘.
(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)\),
(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‘.)
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\).