Dependencies

Uniform output-layer regularity. The output-layer class \(H \subseteq \mathbb R^{\mathcal X}\) has finite uniform covering numbers \(N(H, \| \cdot \| _\infty , u) {\lt} \infty \) for all \(u {\gt} 0\), and there are constants \(B_H, L_H\) with \(\| h\| _\infty \le B_H\) and \(|h(x) - h(x')| \le L_H d(x,x')\) for all \(h \in H\).

Sample output-layer regularity. For a sample \(S\) and a hidden class \(F\), the output-layer class \(H \subseteq \mathbb R^{\mathcal X}\) has finite uniform pushed-forward covering numbers \(N_{S,F}(H, u) {\lt} \infty \) for all \(u {\gt} 0\), and there are constants \(B_H\), \(L_H\) such that every \(h \in H\) satisfies \(|h(x)| \le B_H\) and \(|h(x) - h(x')| \le L_H d(x, x')\) for all \(x, x' \in \mathcal R_S(F)\) (boundedness and the Lipschitz estimate are only required on the points reached by the sample; compare ass:ent-readout, where both hold on all of \(\mathcal X\) and \(H\) is covered in the sup norm).

Uniform transition covering. The hidden-layer class \(F \subseteq \mathcal X^{\mathcal X}\) has finite uniform covering numbers \(N(F, d_\infty , v) {\lt} \infty \) for all \(v {\gt} 0\).

Sample transition covering. The hidden-layer class \(F \subseteq \mathcal X^{\mathcal X}\) has finite covering numbers in the empirical metric: \(N^{\mathrm{ext}}(F, d_S, v) {\lt} \infty \) for all \(v {\gt} 0\).

Output-layer realization of hidden geometry. For a sample \(S\), an output-layer class \(H\), a hidden class \(B_k\) and constants \(\kappa , R_{\mathrm{out}}\): there is, for each \(g \in B_k\), an output layer \(h_g \in H\) such that the map \(\Psi _k(g) = h_g \circ g\) satisfies \(\| \Psi _k(g) - \Psi _k(g')\| _S \ge \kappa \, d_S(g,g')\) for \(g, g' \in B_k\) and \(\| \Psi _k(g)\| _{S,\infty } \le R_{\mathrm{out}}\) for \(g \in B_k\).

Sub-Gaussian output-layer increments. Let \(\mathfrak F\) be a hidden-layer class and \(A_H, L\) constants. For all \(f, g \in \mathfrak F\) and \(t {\gt} 0\),

where \(\mathbb P_\sigma \) is the uniform distribution on \(\{ \pm 1\} ^n\); and when \(d_S(f,g) = 0\) the requirement is \(Z_f = Z_g\) (for every \(\sigma \)), which is the limiting interpretation of the display (in Lean the display with \(d_S(f,g)=0\) reads \(\ldots \le 2\exp (0)\), hence the separate conjunct).

(E1: free semigroup with one-point uniform separation.) Let \(F = \{ f_1, \dots , f_r\} \), \(r \ge 2\), and suppose there are a base point \(x_* \in \mathcal X\) and \(\delta {\gt} 0\) such that for every \(k\) and all distinct words \(u \ne v \in [r]^k\),

Then for every \(k\) and every \(\varepsilon {\lt} \delta /2\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\). (The paper’s hypothesis (1), that \(u \mapsto f_u\) is injective on \([r]^k\), follows from the separation hypothesis since \(\delta {\gt} 0\), so it is omitted; the hypothesis \(r \ge 2\) is not used in the proof.)

(E1’: equal-length coding.) Let \(F = \{ f_1, \dots , f_r\} \), \(r \ge 2\), and suppose there are \(x_* \in \mathcal X\) and \(\delta {\gt} 0\) with \(d(f_u(x_*), f_v(x_*)) \ge \delta \) for all distinct \(u, v \in [r]^k\) and all \(k\). Then \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\) for all \(k\) and all \(\varepsilon {\lt} \delta /2\). (This generalizes the paper, which assumes in addition that the generators are isometries, that \(d_\infty \) is finite on \(\langle F\rangle \) and that \(u \mapsto f_u\) is injective on \([r]^k\): none of these is needed for the lower bound, which follows from ‘cond:e1-free-iso‘ in one line; the isometry hypothesis only serves, in the paper, to make the covering numbers meaningful.)

(E2: ping–pong coding.) Let \(F = \{ f_1, \dots , f_r\} \), \(r \ge 2\), and suppose there are sets \(V_i \subseteq U_i \subseteq \mathcal X\), anchors \(a_1, \dots , a_r \in \mathcal X\), a marker \(q \in \mathcal X\) and a constant \(\alpha {\gt} 0\) such that, with \(A = \{ a_1, \dots , a_r\} \) and \(Q = \{ q\} \cup \bigcup _j V_j\):

1. (disjoint chambers) \(U_i \cap U_j = \emptyset \) for \(i \ne j\);

2. (coding cores) \(Q \subseteq f_i(V_i)\) for every \(i\);

3. (reset) \(f_i(x) = a_i\) for \(x \notin U_i\), and \(f_i(A) \subseteq A\);

4. (marker separation) \(d(q, a_i) \ge \alpha \) for every \(i\).

Then (a) \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\) for every \(k\) and every \(\varepsilon {\lt} \alpha /2\), and (b) \(u \mapsto f_u\) is injective on \([r]^k\) for every \(k\). (This generalizes the paper, which assumes in (1) a uniform separation \(d(U_i, U_j) \ge \Delta {\gt} 0\) and additionally \(V_i \ne \emptyset \): the proof uses of (1) only the disjointness of the chambers, and \(V_i \ne \emptyset \) follows from (2) since \(q \in f_i(V_i)\); the hypothesis \(r \ge 2\) is not used.)

(E3: memory-preserving expansion grows super- or double-exponentially.) Let \(E\) be a normed space, \(G \subseteq E\), \(\lambda {\gt} 1\), \(X = E^{\mathbb N}\) with the bounded sup metric, \(F = \{ r, A\} \cup \{ g_u : u \in G\} \) and \(W_k = \{ w_u : u \in G^k\} \subseteq B(2k+1, F)\). Then (i) each \(w_u\) is the constant map with value \((\lambda u_{k-1}, \dots , \lambda ^k u_0, 0, \dots )\) (‘cond:e3-i‘), (ii) \(d_\infty (w_u, w_v) = \max _{j{\lt}k} \min \{ 1, \lambda ^{j+1}\| u_{k-1-j} - v_{k-1-j}\| \} \) (‘cond:e3-ii‘), and (iii) for every \(0 {\lt} \varepsilon {\lt} 1/2\),

Consequently \(N^{\mathrm{ext}}(B(2k+1,F), d_\infty , \varepsilon ) \ge N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon )\).

(E3 (i).) For every \(x \in X\), \(w_u(x) = (\lambda u_{k-1}, \lambda ^2 u_{k-2}, \dots , \lambda ^k u_0, 0, 0, \dots )\): coordinate \(j {\lt} k\) of \(w_u(x)\) is \(\lambda ^{j+1} u_{k-1-j}\) and the coordinates \(j \ge k\) vanish. In particular \(w_u\) is a constant map.

(E3 (ii).) For \(u, v \in E^k\), \(d_\infty (w_u, w_v) = \max _{0 \le j {\lt} k} \min \{ 1, \lambda ^{j+1} \| u_{k-1-j} - v_{k-1-j}\| _E\} \) (the paper’s \(\max _{1 \le j \le k} \min \{ 1, \lambda ^{k-j+1}\| u_j - v_j\| \} \) after reindexing).

(E3 (iii), lower bound.) For every \(0 \le \varepsilon {\lt} 1/2\) (and \(\lambda \ne 0\)),

(E3 (iii), upper bound.) For every \(\varepsilon \ge 0\) (and \(\lambda \ne 0\)),

(P1: equicontinuous semigroup on a compact domain saturates, hypothesis 1.) Assume \(\mathcal X\) is compact and the semigroup \(\langle F \rangle \) is precompact (totally bounded) in \(d_\infty \). Then, with \(G := \overline{\langle F\rangle }^{d_\infty }\), for all \(\varepsilon {\gt} 0\) and all \(k\),

hence no dependence on \(k\). (Compactness of \(\mathcal X\) is not needed for this hypothesis.)

(P1, hypothesis 2a.) Assume \(\mathcal X\) is compact and the semigroup \(\langle F \rangle \) is equicontinuous. Then for all \(\varepsilon {\gt} 0\) and all \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon ) {\lt} \infty \).

(P1, hypothesis 2b.) Assume \(\mathcal X\) is compact and the semigroup \(\langle F \rangle \) is uniformly Lipschitz: every \(g \in \langle F \rangle \) is \(K\)-Lipschitz for a common \(K\). Then for all \(\varepsilon {\gt} 0\) and all \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon ) {\lt} \infty \).

(P1, hypothesis 2c.) Assume \(\mathcal X\) is compact and the generators are non-expanding: \(\mathrm{lip}\, F \le 1\). Then for all \(\varepsilon {\gt} 0\) and all \(k\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(\overline{\langle F\rangle }, d_\infty , \varepsilon ) {\lt} \infty \).

(P1’: contraction to a compact invariant set.) Assume

1. (uniform contraction) every \(f \in F\) is \(c\)-Lipschitz with \(0 {\lt} c {\lt} 1\);

2. (invariant set) there is a nonempty \(F\)-invariant set \(A \subseteq \mathcal X\) (\(f(A) \subseteq A\) for all \(f \in F\));

3. (bounded absorbing set) there are \(L \in \mathbb N\) and a bounded set \(K \subseteq \mathcal X\) with \(f(\mathcal X) \subseteq K\) for every word \(f \in F^L\) of length \(L\).

Then for every \(\varepsilon {\gt} 0\), with \(m(\varepsilon ) := L + \lceil \log _{1/c}(2\, \mathrm{diam}(K)/\varepsilon ) \rceil \), for every \(k \ge 0\),

In particular the right-hand side is independent of \(k\). (This generalizes the paper, which assumes \(A\) compact, \(K\) compact and \(k \ge m(\varepsilon )\): the proof uses of \(A\) only that it is nonempty and invariant, of \(K\) only its boundedness, and the bound holds for every \(k\). The right-hand side is finite whenever each \(N^{\mathrm{ext}}(F^l, d_\infty , \varepsilon )\), \(l {\lt} m(\varepsilon )\), is finite, which the paper does not assume.)

(P2: nilpotent control grows polynomially.) Let \((H, d_H)\) be a group with a pseudo-emetric, identity \(e\), and assume the length \(g \mapsto d_H(e,g)\) is subadditive: \(d_H(e,gh) \le d_H(e,g) + d_H(e,h)\). Assume its balls have polynomial entropy of degree \(D \ge 0\): there is \(1 \le C_H {\lt} \infty \) such that for all \(R \ge 0\) and \(\delta {\gt} 0\),

Suppose \(H\) acts on \(\mathcal X\) through a homomorphism \(\alpha : H \to \mathcal X^{\mathcal X}\), that there is a bounded set \(S \subseteq H\) (\(d_H(e,s) \le R_S\) for \(s \in S\)) with \(F \subseteq \alpha (S)\), and that the orbit map is Lipschitz in the uniform metric: \(d_\infty (\alpha (g), \alpha (h)) \le L_\alpha d_H(g,h)\) with \(0 {\lt} L_\alpha {\lt} \infty \). Then with

one has, for every \(\varepsilon {\gt} 0\) and every \(k \ge 0\),

(In Lean the ball-entropy hypothesis and the conclusion are stated in \([0,\infty ]\) as \(N \le \operatorname {ofReal}(\cdots )\), which in particular asserts finiteness; the bound holds for \(k = 0\) as well.)

On a bounded state space, \(d(x,y) \le D_{\mathcal X}\) for all \(x, y \in \mathcal X\), every pair of self-maps satisfies \(d_\infty (f,g) \le D_{\mathcal X}\); in particular \(\mathrm{diam}_\infty B(k,F) \le \mathrm{diam}(\mathcal X)\) for every \(k\).

(Real-valued form of P2.) Under the hypotheses of ‘cond:p2-nilp‘, for every \(\varepsilon {\gt} 0\) and \(k \ge 0\), \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le C_H \max (1, R_S L_\alpha )^D (1 + k/\varepsilon )^D\) as real numbers (the covering number being finite).

(Saturation for compact equicontinuous semigroups.) Let \((\mathcal X, d)\) be compact and \(F \subseteq \mathcal X^{\mathcal X}\). If the generated semigroup \(\langle F \rangle \) is equicontinuous, then for every \(\varepsilon {\gt} 0\) and every \(k\)

In particular the covering number of the word ball does not grow with the depth \(k\).

(Internal version of ‘cor:aa-semigroup-saturation‘.) Under the same hypotheses, for every \(\varepsilon {\gt} 0\) and every \(k\), \(N\bigl(B(k,F), d_\infty , \varepsilon \bigr) \le N\bigl(\overline{\langle F\rangle }^{d_\infty }, d_\infty , \varepsilon /2\bigr) {\lt} \infty \) (internal covering numbers are not monotone in the set, whence the loss of a factor \(2\) in the radius).

(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})\).

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}\).

(Double-exponential regime.) Assume there are \(p, c_-, c_+, \delta _0 {\gt} 0\) with \(c_- \delta ^{-p} \le \log M(G, \delta )\) and \(\log N^{\mathrm{ext}}(G, \delta ) \le c_+ \delta ^{-p}\) for all \(0 {\lt} \delta {\lt} \delta _0\), and that \(N^{\mathrm{ext}}(G, \delta ) {\lt} \infty \) for all \(\delta {\gt} 0\). Then for every fixed \(\varepsilon \) with \(0 {\lt} \varepsilon {\lt} 1/2\) and \(\varepsilon {\lt} \lambda \delta _0/2\) there are \(C_1, C_2 {\gt} 0\) and \(k_0\) such that \(C_1 \lambda ^{pk} \le \log N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon ) \le C_2 \lambda ^{pk}\) for all \(k \ge k_0\).

(Profiles from the envelope, ‘cor:envelope-profiles‘.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, \(\overline D {\gt} 0\), \(k \ge 1\) and \(D_k(S) \le \overline D\).

1. (Parametric layers.) If \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le p\log (C/\varepsilon )\) for all \(0 {\lt} \varepsilon \le C\), with \(p \ge 0\) and \(C \ge \overline D\), then for \(0 {\lt} \varepsilon \le \overline D\), \(\log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le \log (k+1) + kp[\log (C/\varepsilon ) + \log S_k(\Lambda )]\), and \(\mathsf V_k(S) \le \overline D\bigl(\sqrt{\log (k+1)} + \sqrt{kp\log k} + k\sqrt{p\log \Lambda _+} + \sqrt{kp}\, (\sqrt{\log (2C/\overline D)} + \sqrt\pi /2)\bigr)\).

2. (Nonparametric layers.) If \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le c\, \varepsilon ^{-q}\) for all \(\varepsilon {\gt} 0\), with \(c \ge 0\) and \(0 {\lt} q {\lt} 2\), then for \(\varepsilon {\gt} 0\), \(\log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \le \log (k+1) + kc\, S_k(\Lambda )^q\varepsilon ^{-q}\), and \(\mathsf V_k(S) \le \overline D\sqrt{\log (k+1)} + \sqrt{kc}\, (2S_k(\Lambda ))^{q/2}\, \overline D^{\, 1-q/2}/(1-q/2)\).

See ‘cor:envelope-profiles-a‘ and ‘cor:envelope-profiles-b‘ for the factors \(2\).

(Profiles from the envelope: parametric layers, ‘cor:envelope-profiles‘(a).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, let \(\overline D {\gt} 0\), \(C \ge \overline D\), \(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 (C/\varepsilon )\) for all \(0 {\lt} \varepsilon \le C\). If \(D_k(S) \le \overline D\) then, for \(k \ge 1\), with \(\Lambda _+ := \max \{ 1,\Lambda \} \),

(The paper has \(C\) in place of \(2C\): 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‘.)

(Parametric layers, entropy form of ‘cor:envelope-profiles‘(a).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le p\log (C/\varepsilon )\) for all \(0 {\lt} \varepsilon \le C\), with \(p \ge 0\). Then for \(k \ge 1\) and \(0 {\lt} \varepsilon \le C\),

(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\).)

(Profiles from the envelope: nonparametric layers, ‘cor:envelope-profiles‘(b).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, let \(\overline D {\gt} 0\), \(c \ge 0\), \(0 {\lt} q {\lt} 2\), and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le c\, \varepsilon ^{-q}\) for all \(\varepsilon {\gt} 0\). If \(D_k(S) \le \overline D\) then, for \(k \ge 1\),

(The paper has \(S_k(\Lambda )^{q/2}\) in place of \((2S_k(\Lambda ))^{q/2}\): the factor \(2\) is the price of comparing the internal covering number in \(d_S\) with the external one in \(d_\infty \).)

(Nonparametric layers, entropy form of ‘cor:envelope-profiles‘(b).) Let every \(f \in F\) be \(\Lambda \)-Lipschitz and suppose \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) {\lt} \infty \) and \(\log N^{\mathrm{ext}}(F, d_\infty , \varepsilon ) \le c\, \varepsilon ^{-q}\) for all \(\varepsilon {\gt} 0\), with \(c \ge 0\). Then for \(k \ge 1\) and \(\varepsilon {\gt} 0\),

(Finite-dimensional feature map.) Let \(\mathcal H = \mathbb R^m\) and \(\Phi : \mathcal X \to \mathbb R^m\). If for each \(j\) the feature matrix \(\Phi _j = (\Phi (f_j(x_i)))_{i \in [n]} \in \mathbb R^{m \times n}\) has full column rank, quantified as \(\sigma _{\min }(\Phi _j)^2 = \lambda _{\min }(\Phi _j^\top \Phi _j) \ge \lambda _{\min ,j} {\gt} 0\), i.e. \(c^\top \Phi _j^\top \Phi _j c \ge \lambda _{\min ,j} \| c\| _2^2\), then ‘prop:linear-interpolation‘ applies with \(\Lambda _j = \lambda _{\min ,j}^{-1/2} = \sigma _{\min }(\Phi _j)^{-1}\). (This is ‘cor:rkhs-readout‘ for \(\mathcal H = \mathbb R^m\), since \(\Phi _j^\top \Phi _j\) is the Gram matrix.)

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

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\).

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

(Bounded codes.) In ‘prop:linear-interpolation‘, for \(R_{\mathrm{out}}\)-bounded codes it suffices to take \(R_H \ge \sqrt n\, R_{\mathrm{out}} \max _j \Lambda _j\) (with \(\Lambda _j \ge 0\)), which is independent of the number \(M\) of maps.

(Readout realization from interpolation.) Under the hypotheses of ‘prop:linear-interpolation‘, if moreover \(\kappa \, d_S(f_j, f_\ell ) \le \rho \) for all \(j \ne \ell \), then the readout-realization assumption holds for \(H_{R_H}(\Phi )\) on \(B_k = \{ f_1, \dots , f_M\} \) with constants \(\kappa \) and \(R_{\mathrm{out}}\).

Matching depth dependence (i). There is a universal constant \(c {\gt} 0\) such that under Assumption ass:readout-realization-main for \(B_k\) (constants \(\kappa , R_{\mathrm{out}}\)), the boundedness hypothesis of thm:sudakov-type and \(\varepsilon _0 {\gt} 0\): if \(M(B_k, d_S, 2\varepsilon _0) \ge e^{\alpha k}\) for some \(\alpha {\gt} 0\), then \(\hat{\mathfrak R}_S(\mathcal H_k) \ge c\, \kappa \varepsilon _0 \sqrt{\alpha k / n}\) whenever \(n \ge R_{\mathrm{out}}^2 \alpha k / (\kappa ^2 \varepsilon _0^2)\).

Matching depth dependence (ii). There is a universal constant \(c {\gt} 0\) such that under Assumption ass:readout-realization-main for \(B_k\) (constants \(\kappa , R_{\mathrm{out}}\)), the boundedness hypothesis of thm:sudakov-type, \(k \ge 1\) and \(\varepsilon _0 {\gt} 0\): if \(M(B_k, d_S, 2\varepsilon _0) \ge k^{\beta }\) for some \(\beta {\gt} 0\), then \(\hat{\mathfrak R}_S(\mathcal H_k) \ge c\, \kappa \varepsilon _0 \sqrt{\beta \log k / n}\) whenever \(n \ge R_{\mathrm{out}}^2 \beta \log k / (\kappa ^2 \varepsilon _0^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}\).

(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}\).

(Finite hidden-layer classes; table row “E1’, E2 with \(|F| = r\)”.) If \(F\) is finite with \(|F| = r \ge 2\) and the state metric is bounded, \(d(x,y) \le D_{\mathcal X}\) (\(D_{\mathcal X} \ge 0\)), then \(|B(k,F)| \le r^{k+1}\), hence \(N(B(k,F), d_S, \varepsilon ) \le r^{k+1}\) for every \(\varepsilon {\gt} 0\), and

for every \(k\): profile (iii), \(\mathrm{var}(k,n) = O(\sqrt{k/n})\).

(P1 \(\Rightarrow \) saturation; table row “P1 (compact, equicontinuous)”.) Let \(\mathcal X\) be compact and the semigroup \(\langle F\rangle \) equicontinuous. With \(N_\infty (\varepsilon ) := N^{\mathrm{ext}}\bigl(\overline{\langle F\rangle }, d_\infty , \varepsilon /2\bigr)\) and \(\mathsf V_\infty := \int _0^{\mathrm{diam}(\mathcal X)} \sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) (assumed interval-integrable), \(D_k(S) \le \mathrm{diam}(\mathcal X)\) and \(\mathsf V_k(S) \le \mathsf V_\infty \) for all \(k\): profile (i), \(\mathsf V_k = O(1)\), \(\mathrm{var}(k,n) = O(n^{-1/2})\).

(P1 with non-expanding generators.) Let \(\mathcal X\) be compact and every \(f \in F\) be \(1\)-Lipschitz. Then the conclusion of ‘cor:profile-p1‘ holds.

(P1 \(\Rightarrow \) saturation; general form.) Let the state metric be bounded, \(d(x,y) \le D_{\mathcal X}\) (\(D_{\mathcal X} \ge 0\)), and let the semigroup \(\langle F\rangle \) be totally bounded in \(d_\infty \) (‘cond:p1‘). Put \(N_\infty (\varepsilon ) := N^{\mathrm{ext}}\bigl(\overline{\langle F\rangle }, d_\infty , \varepsilon /2\bigr)\) (finite for \(\varepsilon {\gt} 0\); the factor \(\tfrac 12\) comes from comparing internal with external covers) and assume \(\mathsf V_\infty := \int _0^{D_{\mathcal X}} \sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) (interval-integrability of the majorant). Then for every \(k\) and every sample \(S\), \(\mathsf V_k(S) \le \mathsf V_\infty \): profile (i), \(\mathrm{var}(k,n) = O(n^{-1/2})\).

(P2 on a bounded state space; table row “P2, compact \(\mathcal X\)”.) Under the hypotheses of ‘cond:p2-nilp‘, if moreover \(d(x,y) \le D_{\mathcal X}\) for all \(x, y\) (\(D_{\mathcal X} {\gt} 0\)), then \(D_k(S) \le D_{\mathcal X}\) and for every \(k \ge 1\)

with \(C_0 = 2^D C_H\max (1, R_SL_\alpha )^D\): profile (ii), \(\mathrm{var}(k,n) = O(\sqrt{D\log k/n})\).

(P2 on a general state space; table row “P2, non-compact \(\mathcal X\)”.) Under the hypotheses of ‘cond:p2-nilp‘ with \(R_S {\gt} 0\), \(D_k(S) \le 2L_\alpha R_S k\) and for every \(k \ge 1\)

with \(C_0 = 2^D C_H\max (1, R_SL_\alpha )^D\): profile (iv), \(\mathrm{var}(k,n) = O(k\sqrt{D/n})\).

The sup-norm theorem from the sample theorem. Under the sup-norm Assumptions ass:ent-readout and ass:ent-transition with \(L_H {\gt} 0\), \(B_H {\gt} 0\), if \(x \mapsto \mathcal E_H(x/4) + \mathcal E_F(x/(8L_H))\) is integrable on \([0, B_H/2]\), then for every sample \(S\) of size \(n \ge 1\),

This is thm:rad.decomp.ent.ent with the scale \(x/(8L_H)\) in place of \(x/(4L_H)\) for \(F\) (the price of the internal cover of \(F\) in the sample version), obtained from thm:rad.decomp.ent.ent-sample-foml: the sup-norm assumptions imply the sample assumptions, and \(\mathcal E_{H,S} \le \mathcal E_H\), \(\mathcal E_{F,S} \le \mathcal E_F\) pointwise at positive scales.

(RKHS / kernel output layer.) Let \(\Phi : \mathcal X \to \mathcal H\) be a feature map (e.g. the canonical feature map of a positive definite kernel \(K\), so that \(\langle \Phi (a), \Phi (a')\rangle = K(a, a')\)) and fix \(f_1, \dots , f_M\) and a sample \(S\). Suppose that for each \(j\) the Gram matrix \(G_j = (\langle \Phi (f_j(x_i)), \Phi (f_j(x_{i'})) \rangle )_{i,i'}\) satisfies \(c^\top G_j c \ge \lambda _{\min ,j} \| c\| _2^2\) with \(\lambda _{\min ,j} {\gt} 0\). Then ‘prop:linear-interpolation‘ applies with \(\Lambda _j = \lambda _{\min ,j}^{-1/2}\): for all codes \(u^{(j)}\) with \(\lambda _{\min ,j}^{-1/2} \| u^{(j)}\| _2 \le R_H\), \(\rho \)-separated and \(R_{\mathrm{out}}\)-bounded, there are \(h_j \in H_{R_H}(\Phi )\) with \(h_j(f_j(x_i)) = u^{(j)}_i\), \(\| h_j \circ f_j - h_\ell \circ f_\ell \| _S \ge \rho \) (\(j \ne \ell \)) and \(\| h_j \circ f_j\| _{S,\infty } \le R_{\mathrm{out}}\).

Rates under fixed-scale packing lower bounds (exponential). There is a universal constant \(c {\gt} 0\) such that under Assumption ass:readout-realization-main for \(B_k\): if \(M(B_k, d_S, 2\varepsilon _0) \ge e^{\alpha k}\) for some \(\varepsilon _0, \alpha {\gt} 0\), then

Rates under fixed-scale packing lower bounds (polynomial). There is a universal constant \(c {\gt} 0\) such that under Assumption ass:readout-realization-main for \(B_k\): if \(k \ge 1\) and \(M(B_k, d_S, 2\varepsilon _0) \ge k^{\beta }\) for some \(\varepsilon _0, \beta {\gt} 0\), then

Conditional Sudakov-type lower bound for a bounded hypothesis class. Under the hypotheses of thm:sudakov-type, the boundedness hypothesis holds as soon as \(\mathcal H_k\) is uniformly bounded on the sample, \(|g(x_i)| \le C\) for all \(g \in \mathcal H_k\) and \(i \le n\); hence the same lower bound.

(Super-exponential regime.) Assume there are \(c_-, c_+, \delta _0 {\gt} 0\) with \(c_- \log (1/\delta ) \le \log M(G, \delta )\) and \(\log N^{\mathrm{ext}}(G, \delta ) \le c_+ \log (1/\delta )\) for all \(0 {\lt} \delta {\lt} \delta _0\), and that \(N^{\mathrm{ext}}(G, \delta ) {\lt} \infty \) for all \(\delta {\gt} 0\) (automatic for compact \(G\)). Then for every fixed \(\varepsilon \) with \(0 {\lt} \varepsilon {\lt} 1/2\) and \(\varepsilon {\lt} \lambda \delta _0/2\) there are \(C_1, C_2 {\gt} 0\) and \(k_0\) such that \(C_1 k^2 \le \log N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon ) \le C_2 k^2\) for all \(k \ge k_0\). (The smallness condition \(\varepsilon {\lt} \lambda \delta _0/2\) makes every radius \(2\varepsilon /\lambda ^{j+1} \le 2\varepsilon /\lambda \) fall below \(\delta _0\); it cannot be replaced by "large \(k\)" since the \(j = 0\) radius does not shrink with \(k\).)

EL regime, upper bound: \(\mathsf{gen}({k^{\ast }},n) = O(\sqrt{\log \log n/n})\).

EP regime, upper bound: \(\mathsf{gen}({k^{\ast }},n) = O(n^{-1/2}(\log n)^{\gamma /2})\).

PL regime, upper bound: \(\mathsf{gen}({k^{\ast }},n) = O(\sqrt{\log n/n})\).

(Plugging a profile into the decomposition.) Under the hypotheses of ‘thm:hidden-decomp-depth‘ (including the integrability of the entropy integrand), if \(\mathsf V_k(S) \le B\) then \(\hat{\mathfrak R}_S(\mathcal H_k) \le \hat{\mathfrak R}_S(H) + \frac{12A_HL}{\sqrt n}\, B\). The statements about \(\mathrm{var}(k,n)\) in ‘prop:profiles‘ follow by multiplying the profile bounds with \(12A_HL/\sqrt n\).

(Estimation term for finite hidden-layer classes.) Under the hypotheses of ‘cor:profile-finite‘ and ‘thm:hidden-decomp-depth‘, \(\hat{\mathfrak R}_S(\mathcal H_k) \le \hat{\mathfrak R}_S(H) + \frac{12A_HL}{\sqrt n}\, D_{\mathcal X}\sqrt{(k+1)\log r}\) for every \(k\): \(\mathrm{var}(k,n) = O(\sqrt{k/n})\).

(Estimation term under P1.) Let \(\mathcal X\) be compact, the semigroup \(\langle F\rangle \) equicontinuous, and \(\mathsf V_\infty \) as in ‘cor:profile-p1‘. Under the hypotheses of ‘thm:hidden-decomp-depth‘, \(\hat{\mathfrak R}_S(\mathcal H_k) \le \hat{\mathfrak R}_S(H) + \frac{12A_HL}{\sqrt n} \mathsf V_\infty \) for every \(k\): \(\mathrm{var}(k,n) = O(n^{-1/2})\) uniformly in the depth.

(Estimation term under P2, bounded state space.) Under the hypotheses of ‘cor:profile-p2-compact‘ and ‘thm:hidden-decomp-depth‘, for \(k \ge 1\), \(\hat{\mathfrak R}_S(\mathcal H_k) \le \hat{\mathfrak R}_S(H) + \frac{12A_HL}{\sqrt n}\Bigl( D_{\mathcal X}\sqrt D\bigl(\sqrt{\log (1 + k/D_{\mathcal X})} + \tfrac {\sqrt\pi }{2}\bigr) + D_{\mathcal X}\sqrt{\log C_0}\Bigr)\): \(\mathrm{var}(k,n) = O(\sqrt{D\log k/n})\).

(Estimation term under P2, general state space.) Under the hypotheses of ‘cor:profile-p2-noncompact‘ and ‘thm:hidden-decomp-depth‘, for \(k \ge 1\), \(\hat{\mathfrak R}_S(\mathcal H_k) \le \hat{\mathfrak R}_S(H) + \frac{12A_HL}{\sqrt n}\, 2L_\alpha R_Sk\Bigl(\sqrt D\bigl(\sqrt{\log (1 + 1/(2L_\alpha R_S))} + \tfrac {\sqrt\pi }{2}\bigr) + \sqrt{\log C_0}\Bigr)\): \(\mathrm{var}(k,n) = O(k\sqrt{D/n})\).

Exponentially decaying approximation error: \(\mathsf{bias}(k) = e^{-\alpha k}\), \(\alpha {\gt} 0\).

Polynomially decaying approximation error: \(\mathsf{bias}(k) = k^{-\beta }\), \(\beta {\gt} 0\).

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.)

For \(H \subseteq \mathbb R^{\mathcal X}\) and \(F \subseteq \mathcal X^{\mathcal X}\), \(H \circ F = \{ h \circ f : h \in H,\ f \in F\} \).

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)\)).

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

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

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

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

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 constant sequence \(\bar a = (a, a, \dots )\).

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).

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

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

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)\).

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

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

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).

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.

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

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)\).

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})\).

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\).

The uniform distance on \(\mathcal X^{\mathcal X}\) is \(d_\infty (f,g) = \sup _{x \in \mathcal X} d(f(x), g(x)) \in [0,\infty ]\).

The real-valued uniform distance \(d_\infty (f,g)\), with the convention that it is \(0\) when \(d_\infty (f,g) = \infty \).

For a sample \(S = (x_1,\dots ,x_n)\) the empirical distance is \(d_S(f,g) = \bigl(\frac1n \sum _{i=1}^n d(f(x_i), g(x_i))^2\bigr)^{1/2}\).

The empirical diameter of a class \(F\) is \(\mathrm{diam}_S(F) = \sup _{f, g \in F} d_S(f,g)\).

The expander \(A(x_0, x_1, \dots ) = (\lambda x_0, \lambda x_1, \dots )\).

The hidden-layer class \(F = \{ r, A\} \cup \{ g_u : u \in G\} \).

The reset map \(r(x) = 0\).

The bounded sup metric on \(X = E^{\mathbb N}\): \(d_X(x,y) = \sup _{j} \min \{ 1, \| x_j - y_j\| _E\} \). It is a pseudo-emetric (indeed a metric with values in \([0,1]\)).

The memory state space \(X = E^{\mathbb N}\) (the paper’s \(\ell _\infty (E)\); we allow all sequences since the bounded metric below is finite anyway).

For \(u = (u_0, \dots , u_{k-1}) \in E^k\) the word \(w_u = A \circ g_{u_{k-1}} \circ A \circ g_{u_{k-2}} \circ \cdots \circ A \circ g_{u_0} \circ r\) (so \(u_0\) is written first and \(u_{k-1}\) last). In Lean it is defined by recursion on \(k\): \(w_{()} = r\) and \(w_{(u, a)} = A \circ g_a \circ w_u\).

\(W_k = \{ w_u : u \in G^k\} \).

The writer \(g_u(x_0, x_1, \dots ) = (u, x_0, x_1, \dots )\).

The pseudometric space \((\mathbb R^{\mathcal X}, \| \cdot \| _S)\) of real-valued functions equipped with the empirical \(L^2\) distance \(\| u - v\| _S = \bigl(\frac1n \sum _i |u(x_i) - v(x_i)|^2\bigr)^{1/2}\) of the sample \(S\) (a type synonym of \(\mathbb R^{\mathcal X}\)).

\(\| \cdot \| _S\) is a pseudometric on \(\mathbb R^{\mathcal X}\). In Lean this is FoML’s ‘empiricalPMet S‘ (whose distance is FoML’s ‘empiricalDist S‘).

\(f\) is an \(\eta \)-empirical minimizer over \(\mathcal H\) if \(f \in \mathcal H\) and \(\hat L[f] \le \inf _{g \in \mathcal H} \hat L[g] + \eta \).

For real-valued \(u, v\) the empirical \(L^2\) distance is \(\| u - v\| _S = \bigl(\frac1n \sum _{i=1}^n |u(x_i) - v(x_i)|^2\bigr)^{1/2}\).

The empirical Rademacher complexity of \(G \subseteq \mathbb R^{\mathcal X}\) on the sample \(S = (x_1,\dots ,x_n)\) is \(\hat{\mathfrak R}_S(G) = \mathbb E_\sigma \sup _{g \in G} \frac1n \sum _{i=1}^n \sigma _i g(x_i) = 2^{-n} \sum _{\sigma \in \{ \pm 1\} ^n} \sup _{g \in G} \frac1n \sum _{i=1}^n \sigma _i g(x_i)\) (no absolute value). In Lean this is FoML’s ‘empiricalRademacherComplexity_without_abs‘ for the class indexed by \(G\) itself.

The empirical risk on a sample \(D = ((x_1,y_1),\dots ,(x_n,y_n))\) is \(\hat L[f] = \frac1n \sum _{i=1}^n \ell (f(x_i), y_i)\).

The pseudometric space \((\mathcal X^{\mathcal X}, d_S)\) of self-maps equipped with the empirical distance of the sample \(S\) (a type synonym of \(\mathcal X^{\mathcal X}\)).

\(d_S\) is a pseudometric on \(\mathcal X^{\mathcal X}\).

The empirical sup norm \(\| u\| _{S,\infty } = \max _{i \le n} |u(x_i)|\) (equal to \(0\) when \(n = 0\)).

The root entropy of the output-layer class at scale \(u\): \(\mathcal E_H(u) = \sqrt{\log N^{\mathrm{ext}}(H, \| \cdot \| _\infty , u)}\) (with \(u \mapsto \max (u, 0)\) and \(\log \infty = \log 0 = 0\) in Lean).

The root entropy of the output-layer class at scale \(u\) on the sample: \(\mathcal E_{H,S}(u) = \sqrt{\log N_{S,F}(H, u)}\) (with \(u \mapsto \max (u,0)\) and \(\log \infty = \log 0 = 0\) in Lean).

The root entropy of the hidden class at scale \(v\): \(\mathcal E_F(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_\infty , v)}\).

The root entropy of the hidden class at scale \(v\) on the sample: \(\mathcal E_{F,S}(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_S, v)}\).

The entropy integral of \(A\) up to scale \(D\) is \(\mathsf V(D, A) = \int _0^{D} \sqrt{\log N(A, \varepsilon )}\, d\varepsilon \). In the paper, \(\mathsf V_k(S) = \int _0^{D_k(S)} \sqrt{\log N(B(k,F), d_S, \varepsilon )}\, d\varepsilon \) with \(D_k(S) = \operatorname {diam}_S B(k,F)\) is \(\mathsf V(\operatorname {diam}_S B(k,F), B(k,F))\) for the empirical pseudometric \(d_S\).

For a layerwise Lipschitz constant \(\Lambda \ge 0\) and \(m \ge 0\), the geometric sum \(S_m(\Lambda ) := \sum _{i=0}^{m-1} \Lambda ^i\) (so \(S_0 = 0\), \(S_1 = 1\)) of ‘prop:implementation‘(b); it is the amplification factor of the covering envelope ‘prop:envelope‘.

The implementation error of an implementation map \(\iota \) on a class \(\mathcal H\) is \(\varepsilon _{\mathrm{imp}} = \sup _{f \in \mathcal H} \| f - \iota f\| _\infty \).

The model error (approximation term) of \(\mathcal H\) relative to a target class \(\mathcal C\) is \(\varepsilon _{\mathrm{model}} = \inf _{f \in \mathcal H} L[f] - \inf _{c \in \mathcal C} L[c]\).

For probes \(P = (p_j)_{j \in J}\) (\(J\) finite) the evaluation map is \(\mathrm{ev}_P : (\mathcal X^{\mathcal X}, d_\infty ) \to (\mathcal X^J, d_{\max })\), \(\mathrm{ev}_P(f) = (f(p_j))_{j \in J}\), where \(\mathcal X^J\) carries the sup-metric.

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\).

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).

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.)

The depth-dependent part of the excess-risk bound of theorem 98: \(\mathsf{gen}(k,n) = \mathsf{bias}(k) + \mathsf{var}(k,n)\).

For a Hilbert space \(\mathcal H\) and a feature map \(\Phi : \mathcal X \to \mathcal H\), the norm-bounded linear output-layer class is \(H_\Phi = \{ x \mapsto \langle w, \Phi (x)\rangle : \| w\| \le 1\} \).

The depth-\(k\) hypothesis class is \(\mathcal H_k = H \circ B(k,F)\).

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\).

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\).

EL balancing depth (leading terms): \({k^{\ast }}= \frac{1}{2\alpha }(\log n - \log \log \log n)\).

EP balancing depth (leading terms): \({k^{\ast }}= \frac{1}{2\alpha }(\log n - \gamma \log \log n)\).

PL balancing depth \({k^{\ast }}= \bigl(2\beta n/\log (2\beta n)\bigr)^{1/(2\beta )}\), the leading term of \(\exp \bigl(W(2\beta n)/(2\beta )\bigr)\) (Lambert \(W\), \(W(x) \sim \log x\)).

PP balancing depth \({k^{\ast }}= n^{1/(2\beta +\gamma )}\).

For a real Hilbert space \(\mathcal H\), a feature map \(\Phi : \mathcal X \to \mathcal H\) and a radius \(R_H \ge 0\), the norm-bounded linear output-layer class is

A loss is a function \(\ell : \mathbb R \times \mathcal Y \to [0, b]\) which is \(\beta _\ell \)-Lipschitz in its first argument: \(|\ell (a, y) - \ell (a', y)| \le \beta _\ell |a - a'|\).

The metric entropy of \(A\) at scale \(\varepsilon \) is \(\log N(A, \varepsilon )\), where \(N(A,\varepsilon )\) is the (internal) covering number of \(A\) by closed \(\varepsilon \)-balls (with the convention \(\log \infty = \log 0 = 0\) in Lean).

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 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}\).

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 Euler layer class \(F_T := \{ T_{s,h,\tau } : s \in \mathcal S_T,\ h \in [0,h_0],\ \tau \in [0,T]\} \).

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)\).

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 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).

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\).

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\).

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 restriction of a drift \(s : K \times \mathbb R \to \mathbb R^d\) to \(K \times [0,T]\), viewed in the sup-norm space.

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}\)).

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.

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.

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

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 \).

For a sample \(S = (x_1,\dots ,x_n)\), an output-layer class \(H\) and a hidden map \(f\), the hidden-indexed process is \(Z_f(\sigma ) = \sup _{h \in H} \frac1n \sum _{i=1}^n \sigma _i h(f(x_i))\), \(\sigma \in \{ \pm 1\} ^n\).

The memory length of P1’: \(m(\varepsilon ) := L + \bigl\lceil \log _{1/c}\bigl(2\, \mathrm{diam}(K)/\varepsilon \bigr) \bigr\rceil \) (a natural number; the ceiling of a non-positive real is \(0\)).

For a monoid homomorphism \(\alpha : H \to \mathcal X^{\mathcal X}\) (i.e. \(\alpha (gh) = \alpha (g) \circ \alpha (h)\) and \(\alpha (e) = \mathrm{id}\)), the orbit map is \(g \mapsto \alpha (g) \in \mathcal X^{\mathcal X}\).

The uniform pushed-forward covering number of the output-layer class: \(N_{S,F}(H, u) = \sup _{f \in F} N^{\mathrm{ext}}(H, \| \cdot \| _{f \circ S}, u)\), the largest external covering number of \(H\) in the empirical metric of a pushed-forward sample \(f \circ S = (f(x_1), \dots , f(x_n))\), \(f \in F\). (Any uniform bound \(N^{\mathrm{ext}}(H, \| \cdot \| _{f \circ S}, u) \le \bar N(u)\) for all \(f \in F\) dominates it.)

The (population) Rademacher complexity is \(\mathfrak R_n(G) = \mathbb E_{S \sim P^{\otimes n}} \hat{\mathfrak R}_S(G)\). In Lean we take FoML’s ‘rademacherComplexity‘, i.e. the expectation over \(S \sim P^{\otimes n}\) of the absolute version \(\mathbb E_\sigma \sup _{g \in G} \bigl|\frac1n \sum _i \sigma _i g(x_i)\bigr| \ge \hat{\mathfrak R}_S(G)\); this is the quantity for which FoML’s deviation bounds are stated, and it dominates the paper’s \(\mathfrak R_n(G)\).

EL balanced rate \(\sqrt{\log \log n / n}\).

EP balanced rate \(n^{-1/2}(\log n)^{\gamma /2}\).

PL balanced rate \(\sqrt{\log n/n}\).

The set of points reached by the sample through the hidden class: \(\mathcal R_S(F) = \{ f(x_i) : f \in F,\ 1 \le i \le n\} \subseteq \mathcal X\).

The reachable sample set of a hidden class \(B_k\) on the sample \(S = (x_1, \dots , x_n)\) is \(U_{k,S} = \{ f(x_i) : f \in B_k,\ i \in [n]\} \).

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

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 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 \} \).

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

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

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

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.)

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

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 two generators \(f = (g_0, g_1)\).

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

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\) as a self-map of the state space \([0,1]\).

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

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

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

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.

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

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 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 admissible parameters: \(\| W\| _{\rm op}, \| V\| _{\rm op} \le \beta _W\), \(\| b\| , \| c\| \le \beta \) and \(\mathrm{lip}(f_\vartheta ) \le \Lambda \).

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

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)\)).

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

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

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\).

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

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\} \).

The (population) risk under a distribution \(P\) on \(\mathcal X \times \mathcal Y\) is \(L[f] = \mathbb E_{(X,Y) \sim P}\, \ell (f(X), Y)\).

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)]\).

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 semigroup (monoid) generated by \(F\) is \(\langle F\rangle = \bigcup _{k \ge 0} B(k,F)\).

A class \(\mathcal H \subseteq \mathbb R^{\mathcal X}\) is (sup-norm) separable if it has a countable subset \(\mathcal D \subseteq \mathcal H\) which is dense for the uniform norm: for every \(f \in \mathcal H\) and \(\varepsilon {\gt} 0\) there is \(g \in \mathcal D\) with \(\sup _x |f(x) - g(x)| \le \varepsilon \).

The (identity) map \(\mathbb R^{\mathcal X} \to (\mathbb R^{\mathcal X}, \| \cdot \| _S)\) viewing a real-valued function as a point of the pseudometric space.

The identity map \((\mathcal X^{\mathcal X}, d_\infty ) \to (\mathcal X^{\mathcal X}, d_S)\).

The (identity) map \(\mathbb R^{\mathcal X} \to (\mathbb R^{\mathcal X}, \| \cdot \| _\infty )\) viewing a real-valued function as a point of the pseudo-emetric space.

The (identity) map \(\mathcal X^{\mathcal X} \to (\mathcal X^{\mathcal X}, d_\infty )\) viewing a self-map as a point of the pseudo-emetric space.

The pseudo-emetric space \((\mathbb R^{\mathcal X}, \| \cdot \| _\infty )\) of real-valued functions with the uniform distance \(\| u - v\| _\infty = \sup _x |u(x) - v(x)| \in [0,\infty ]\) (a type synonym of \(\mathbb R^{\mathcal X}\); in Lean Mathlib’s ‘X →ᵤ ℝ‘).

\(\| \cdot \| _\infty \) is a pseudo-emetric on \(\mathbb R^{\mathcal X}\).

The pseudo-emetric space \((\mathcal X^{\mathcal X}, d_\infty )\) of self-maps equipped with the uniform distance (a type synonym of \(\mathcal X^{\mathcal X}\); in Lean it is Mathlib’s ‘X →ᵤ X‘, the function space with the uniform structure).

If \(\mathcal X\) is complete then \((\mathcal X^{\mathcal X}, d_\infty )\) is complete (uniform limits of Cauchy sequences). This is Mathlib’s instance on ‘X →ᵤ X‘.

\(d_\infty \) is a pseudo-emetric on \(\mathcal X^{\mathcal X}\) (it may take the value \(\infty \)). This is Mathlib’s instance on ‘X →ᵤ X‘.

The depth-dependent part of the estimation term is

with \(D_k(S) = \mathrm{diam}_S B(k,F)\).

Root-logarithmic estimation profile: \(\mathsf{var}(k,n) = \sqrt{\log k / n}\) (??(i)–(ii)).

Root-polynomial estimation profile: \(\mathsf{var}(k,n) = \sqrt{k^{\gamma } / n}\), \(\gamma {\gt} 0\) (??(iii)–(iv)).

Let \(F \subseteq \mathcal X^{\mathcal X}\) be a hidden-layer class. The depth-\(k\) hidden class is the word ball \(B(k,F) = \{ f_m \circ \cdots \circ f_1 : 0 \le m \le k,\ f_i \in F\} \), with \(B(0,F) = \{ \mathrm{id}\} \). It is defined recursively by \(B(k+1,F) = B(k,F) \cup F \circ B(k,F)\).

For a finite family \(f = (f_1, \dots , f_r)\) of self-maps and a word \(u = (i_1, \dots , i_k) \in [r]^k\), the associated map is \(f_u = f_{i_k} \circ \cdots \circ f_{i_1}\) (the first letter acts first); \(f_{\emptyset } = \mathrm{id}\). In Lean: ‘wordOf f [] = id‘ and ‘wordOf f (i :: u) = wordOf f u ∘ f i‘.

The words of length exactly \(m\): \(F^m = \{ f_m \circ \cdots \circ f_1 : f_i \in F\} \), with \(F^0 = \{ \mathrm{id}\} \) and \(F^{m+1} = F \circ F^m\).

(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}\),

(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\).

(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

Balancing principle. Let \(S \subseteq \mathbb R\) be a set of depths on which \(\mathsf{bias}\ge 0\) is nonincreasing and \(\mathsf{var}(\cdot ,n) \ge 0\) is nondecreasing. If \(k_0 \in S\) balances the two terms, \(\mathsf{bias}(k_0) = \mathsf{var}(k_0,n)\), then \(\mathsf{gen}(k,n) \ge \mathsf{bias}(k_0)\) for every \(k \in S\), while \(\mathsf{gen}(k_0,n) = 2\mathsf{bias}(k_0)\); hence \(k_0\) minimizes the bound over \(S\) up to the factor \(2\).

If \(\mathsf{bias}\ge 0\) and \(\mathsf{var}(\cdot ,n) \ge 0\) on a set \(S\) of depths, then \(\mathsf{gen}(k,n) \ge \max \{ \mathsf{bias}(k), \mathsf{var}(k,n)\} \) for every \(k \in S\).

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

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.

For \(\alpha {\gt} 0\), \(k \mapsto e^{-\alpha k}\) is nonincreasing.

For \(\alpha {\gt} 0\) and \(n {\gt} e\), \(e^{-\alpha {k^{\ast }}} = \sqrt{\log \log n/n}\) exactly.

For \(\alpha {\gt} 0\) and \(n {\gt} 1\), \(e^{-\alpha {k^{\ast }}} = n^{-1/2}(\log n)^{\gamma /2}\) exactly.

For \(\beta {\gt} 0\), \(k \mapsto k^{-\beta }\) is nonincreasing on \((0,\infty )\).

For \(\beta {\gt} 0\), \(n {\gt} 0\) and \(L = \log (2\beta n) {\gt} 0\): \({k^{\ast }}^{-\beta } = \sqrt{L/(2\beta n)}\).

For \(\beta ,\gamma {\gt} 0\) and \(n {\gt} 0\), \(\mathsf{bias}({k^{\ast }}) = {k^{\ast }}^{-\beta } = n^{-\beta /(2\beta +\gamma )}\).

Deterministic excess-risk bound. Fix a sample \(\mathcal D\) and suppose \(|L[f] - \hat L[f]| \le \Delta _0\) for every \(f \in \mathcal H\). If \(d_T(\iota f, f) \le \varepsilon _{\mathrm{imp}}\) and \(|L[\iota f] - L[f]| \le \beta _L\, d_T(\iota f, f)\) for all \(f \in \mathcal H\) (\(\beta _L \ge 0\)), then every \(\eta \)-empirical minimizer \(\hat f \in \mathcal H\) satisfies, with \(\hat h = \iota (\hat f)\), \(L[\hat h] - \inf _{\mathcal C} L \le \beta _L \varepsilon _{\mathrm{imp}} + \varepsilon _{\mathrm{model}} + \eta + 2\Delta _0\).

Deterministic gap bound. Fix a sample \(\mathcal D\) and suppose \(|L[f] - \hat L[f]| \le \Delta _0\) for every \(f \in \mathcal H\). Under the implementation hypotheses (\(d_T(\iota f, f) \le \varepsilon _{\mathrm{imp}}\), \(|L[\iota f] - L[f]| \le \beta _L d_T(\iota f,f)\), \(|\hat L[\iota f] - \hat L[f]| \le \beta _{\hat L} d_T(\iota f, f)\)), every \(f \in \mathcal H\) satisfies \(L[\iota f] - \hat L[\iota f] \le (\beta _L + \beta _{\hat L}) \varepsilon _{\mathrm{imp}} + \Delta _0\).

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

The one-sided empirical Rademacher complexity of the class \(\{ (x,y) \mapsto f(x) : f \in \mathcal H\} \) on the labelled sample \(\mathcal D\) equals \(\hat{\mathfrak R}_S(\mathcal H)\) on the inputs \(S = (x_1,\dots ,x_n)\).

One-sided Rademacher complexity of the loss class. Let \(\mathcal H \ne \emptyset \) be pointwise bounded and \(\ell : \mathbb R \times \mathcal Y \to \mathbb R\) be \(\beta _\ell \)-Lipschitz in its first argument (\(\beta _\ell \ge 0\)). Then on every sample \(\mathcal D = ((x_i,y_i))_i\) with \(S = (x_i)_i\),

where \(\hat{\mathfrak R}\) is the one-sided (no absolute value) empirical Rademacher complexity. Proof: the one-sided contraction lem:contraction-without-abs applied to \(\psi (z,u) = \pm \ell (u,y)\), which is \(\beta _\ell \)-Lipschitz in \(u\) (no vanishing condition at \(u = 0\) is needed).

Uniform deviation for a sup-separable Lipschitz-loss class. Let \(n \ge 1\), \(\mathcal H\) be a sup-norm separable, pointwise bounded class of measurable functions, \(\ell : \mathbb R \times \mathcal Y \to [0,b]\) measurable and \(\beta _\ell \)-Lipschitz in its first argument (\(b {\gt} 0\), \(\beta _\ell \ge 0\)), \(\delta \in (0,1)\). Then with probability at least \(1 - \delta \) over \(\mathcal D \sim P^{\otimes n}\),

Proof: apply the two-sided bound lem:two-sided-tail-empirical (one-sided symmetrization for \(\ell \circ \mathcal H\) and \(-\ell \circ \mathcal H\)) with \(C(\mathcal D) = \beta _\ell \hat{\mathfrak R}_S(\mathcal H)\) from lem:bv-loss-rademacher and \(\varepsilon = b\sqrt{2\log (4/\delta )/n}\), so that \(4\exp (-n\varepsilon ^2/(2b^2)) = \delta \); the topology on \(\mathcal H\) is the uniform-convergence topology, which is separable and first countable by lem:sup-dense-separableSpace, and evaluations are continuous.

(Consequence of ‘thm:caa‘.) If \(\mathcal X\) is compact and \(H \subseteq \mathcal X^{\mathcal X}\) is equicontinuous, then the closure of \(H\) in \((\mathcal X^{\mathcal X}, d_\infty )\) is compact.

If \(|u_i| \le R_{\mathrm{out}}\) for all \(i \in [n]\) then \(\| u\| _2 \le \sqrt n\, R_{\mathrm{out}}\).

\(H \circ F = \emptyset \) iff \(H = \emptyset \) or \(F = \emptyset \).

If \(F \subseteq F'\) then \(H \circ F \subseteq H \circ F'\).

\(H \circ \{ \mathrm{id}\} = H\).

Composition of covers. Let every \(h \in H\) be \(L_H\)-Lipschitz, let \(C_H\) be an \(r_1\)-cover of \(H\) for \(\| \cdot \| _\infty \) and \(C_F\) an \(r_2\)-cover of \(F\) for \(d_\infty \) (centres anywhere). Then \(\{ h_a \circ f_b : h_a \in C_H, f_b \in C_F\} \) is an \((r_1 + L_H r_2)\)-cover of \(H \circ F\) for \(\| \cdot \| _\infty \): \(|h(f(x)) - h_a(f_b(x))| \le |h(f(x)) - h(f_b(x))| + |h(f_b(x)) - h_a(f_b(x))| \le L_H d_\infty (f, f_b) + \| h - h_a\| _\infty \).

Composition of covers on the sample. Let every \(h \in H\) be \(L_H\)-Lipschitz on \(\mathcal R_S(F)\), let \(C_F \subseteq F\) be an \(r_2\)-cover of \(F\) for \(d_S\) with centres in \(F\), and for every \(f_b \in C_F\) let \(C_H(f_b)\) be an \(r_1\)-cover of \(H\) for \(\| \cdot \| _{f_b \circ S}\) (centres anywhere). Then \(\{ h_a \circ f_b : f_b \in C_F,\ h_a \in C_H(f_b)\} \) is an \((r_1 + L_H r_2)\)-cover of \(H \circ F\) for \(\| \cdot \| _S\): \(\| h \circ f - h_a \circ f_b\| _S \le \| h \circ f - h \circ f_b\| _S + \| h \circ f_b - h_a \circ f_b\| _S \le L_H d_S(f, f_b) + \| h - h_a\| _{f_b \circ S}\), where the first estimate uses the Lipschitz property of \(h\) at the reachable points \(f(x_i), f_b(x_i)\) (this is where \(f_b \in F\) is needed).

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\).

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.

(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)\).

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

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

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

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

If \(f \in B(k,F)\) and \(g \in B(l,F)\) then \(g \circ f \in B(l+k,F)\).

If \(w \in F^m\) and \(g \in F\) then \(w \circ g \in F^{m+1}\): the words of length \(m\) are also closed under right composition with generators.

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

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

(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}\).

(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‘.

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

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

(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.

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\).

(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 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})\)).

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

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\).

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

(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\).)

(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\).

(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‘).

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

(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}\).

(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\).

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\)).

(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\).

(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.

(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}\)).

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

(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\).

(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.

(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).

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.)

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

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

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

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

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\).

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

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

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

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

\(n(x,y) = n(y,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\).

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

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

(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\).

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

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

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

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\).

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

(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)\).)

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

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

(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\)).

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

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

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

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

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

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

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

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

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

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

(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\).

(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\).

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\).

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

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

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

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

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

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

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

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.

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 \).

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 )\)).

The bridge used by all profiles: for every \(A \subseteq \mathcal X^{\mathcal X}\) and \(\varepsilon \ge 0\), \(N(A, d_S, \varepsilon ) \le N^{\mathrm{ext}}(A, d_\infty , \varepsilon /2)\) (internal covering number on the left, external on the right; the factor \(2\) is the price of comparing internal with external covers).

For every \(A \subseteq \mathcal X^{\mathcal X}\) and \(\varepsilon \ge 0\), \(N^{\mathrm{ext}}(A, d_S, \varepsilon ) \le N^{\mathrm{ext}}(A, d_\infty , \varepsilon )\): covering numbers in the empirical metric are dominated by those in the uniform metric, so all hypotheses may be verified in \(d_\infty \).

\(N(A, d_S, \varepsilon ) \le N(A, d_\infty , \varepsilon )\) (internal covering numbers).

If \(N^{\mathrm{ext}}(A, d_\infty , \varepsilon /2) \le b\) with \(b \ge 0\), then \(N(A, d_S, \varepsilon ) \le b\) as real numbers (the covering number being finite).

On \((\mathbb R^{\mathcal X}, \| \cdot \| _S)\) the distance is \(\| u - v\| _S\).

On \((\mathbb R^{\mathcal X}, \| \cdot \| _S)\) the distance is FoML’s ‘empiricalDist S‘.

On \((\mathcal X^{\mathcal X}, d_S)\) the distance is \(d_S\).

If \(d_\infty (f,g) {\lt} \infty \) then \(d(f(x), g(x)) \le d_\infty (f,g)\) as real numbers.

The empirical distance is dominated by the uniform distance: \(d_S(f,g) \le d_\infty (f,g)\) for every sample \(S\).

(Probe construction for E2.) Under the hypotheses of ‘cond:e2-pingpong‘, for every word \(u\) there is a point \(x_u \in Q = \{ q\} \cup \bigcup _j V_j\) with \(f_u(x_u) = q\) and \(f_v(x_u) \in A = \{ a_1, \dots , a_r\} \) for every word \(v \ne u\) of the same length.

\(N^{\mathrm{ext}}(W_k, d_\infty , \varepsilon ) \le N^{\mathrm{ext}}(B(2k+1,F), d_\infty , \varepsilon )\) (monotonicity of the external covering number under \(W_k \subseteq B(2k+1,F)\)).

\(d_X(x,y) = \sup _j \min \{ 1, \| x_j - y_j\| _E\} \).

\(d_X(x,y) \le 1\).

The same identity for the extended distance of \((\mathcal X^{\mathcal X}, d_\infty )\).

\(A(x)_j = \lambda x_j\).

For \(q {\gt} 1\) and \(k \ge 1\): \(q^k \le \sum _{j{\lt}k} q^{j+1} \le \frac{q}{q-1} q^k\).

If \(f : \mathbb N \to [0,\infty ]\) vanishes on \(j \ge k\) then \(\sup _{j \in \mathbb N} f(j) = \max _{j {\lt} k} f(j)\).

If \(G \ne \emptyset \) and all \(N^{\mathrm{ext}}(G, \varepsilon /\lambda ^{j+1})\) are finite, then \(\log N^{\mathrm{ext}}(W_k, \varepsilon ) \le \sum _{j{\lt}k} \log N^{\mathrm{ext}}(G, \varepsilon /\lambda ^{j+1})\).

(Upper bound in sum form.) Suppose \(N^{\mathrm{ext}}(G,\delta ) {\lt} \infty \) for all \(\delta {\gt} 0\), \(G \ne \emptyset \), and \(\log N^{\mathrm{ext}}(G, \delta ) \le \varphi (\delta )\) for \(0 {\lt} \delta {\lt} \delta _0\). If \(0 {\lt} \varepsilon {\lt} \lambda \delta _0\) then \(\log N^{\mathrm{ext}}(W_k, \varepsilon ) \le \sum _{j{\lt}k} \varphi (\varepsilon /\lambda ^{j+1})\) for every \(k\).

For finite nonzero \(n_i \in \mathbb N \cup \{ \infty \} \), \(\log \prod _i n_i = \sum _i \log n_i\) (with the coercion to \([0,\infty ]\) and ‘toReal‘).

If \(N^{\mathrm{ext}}(G,\delta ) {\lt} \infty \) for all \(\delta {\gt} 0\) then \(N^{\mathrm{ext}}(W_k, \varepsilon ) {\lt} \infty \) for all \(\varepsilon {\gt} 0\).

If \(a \le b + c\) in \([0,\infty ]\) then \(\min \{ 1,a\} \le \min \{ 1,b\} + \min \{ 1,c\} \).

If \(c_- \log (1/\delta ) \le \log M(G, \delta )\) for all small \(\delta {\gt} 0\) with \(c_- {\gt} 0\), then \(G \ne \emptyset \).

If \(c_- \delta ^{-p} \le \log M(G, \delta )\) for all small \(\delta {\gt} 0\) with \(c_- {\gt} 0\), then \(G \ne \emptyset \).

(Product packing.) Let \(2\varepsilon {\lt} 1\), \(\lambda \ne 0\), and let \(P_j \subseteq G\) be \(2\varepsilon /\lambda ^{j+1}\)-separated (\(0 \le j {\lt} k\)). Then \(\prod _j |P_j| \le M(W_k, d_\infty , 2\varepsilon )\).

If \(0 \le a {\lt} \lambda \delta _0\) and \(\lambda {\gt} 1\) then \(a/\lambda ^{j+1} {\lt} \delta _0\) for every \(j\).

\(r(x)_j = 0\).

\(X = E^{\mathbb N}\) is nonempty (it contains \(0\)).

(Lower bound in sum form.) Suppose \(N^{\mathrm{ext}}(G,\delta ) {\lt} \infty \) for all \(\delta {\gt} 0\), \(G \ne \emptyset \), and \(\varphi (\delta ) \le \log M(G, \delta )\) for \(0 {\lt} \delta {\lt} \delta _0\). If \(0 {\lt} \varepsilon {\lt} 1/2\) and \(2\varepsilon {\lt} \lambda \delta _0\) then \(\sum _{j{\lt}k} \varphi (2\varepsilon /\lambda ^{j+1}) \le \log N^{\mathrm{ext}}(W_k, \varepsilon )\) for every \(k\).

If \(G \ne \emptyset \), \(\varepsilon {\lt} 1/2\), all \(M(G, 2\varepsilon /\lambda ^{j+1})\) and \(N^{\mathrm{ext}}(W_k, \varepsilon )\) are finite, then \(\sum _{j{\lt}k} \log M(G, 2\varepsilon /\lambda ^{j+1}) \le \log N^{\mathrm{ext}}(W_k, \varepsilon )\).

\(\sum _{j{\lt}k} \log \bigl(\lambda ^{j+1}/a\bigr) = \frac{k(k+1)}{2}\log \lambda - k \log a\) for \(a, \lambda {\gt} 0\).

\(\sum _{j{\lt}k} (a/\lambda ^{j+1})^{-p} = a^{-p} \sum _{j{\lt}k} (\lambda ^p)^{j+1}\) for \(a, \lambda {\gt} 0\).

\(w_u \in B(2k+1, F)\) for every \(u \in G^k\).

\(w_u\) is constant: \(w_u(x) = w_u(y)\) for all \(x, y\).

For \(\lambda \ne 0\) the map \(u \mapsto w_u\) is injective on \(E^k\).

\(w_u = A \circ g_{u_k} \circ w_{u|_{k}}\) for \(u \in E^{k+1}\).

\(w_{()} = r\).

\(W_k \subseteq B(2k+1, F)\).

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

\(g_u(x)_0 = u\).

\(d(f(x), g(x)) \le d_\infty (f,g)\) for \(f, g \in (\mathcal X^{\mathcal X}, d_\infty )\).

\(d(f(x), g(x)) \le d_\infty (f,g)\) for every \(x\).

\(\mathrm{edist}(u, v) = \sup _x \mathrm{edist}(u(x), v(x))\) in \((\mathbb R^{\mathcal X}, \| \cdot \| _\infty )\).

\(d_\infty \) is the distance of \((\mathcal X^{\mathcal X}, d_\infty )\): \(\mathrm{edist}(f, g) = d_\infty (f,g)\) for \(f, g \in \mathcal X^{\mathcal X}\).

On \((\mathbb R^{\mathcal X}, \| \cdot \| _\infty )\) the extended distance is \(\sup _x \mathrm{edist}(u(x), v(x))\).

On \((\mathcal X^{\mathcal X}, d_\infty )\) the extended distance is \(d_\infty \).

(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)\).

For every sample \(S\) (\(n \ge 1\)) and \(r \ge 0\), \(N^{\mathrm{ext}}(G, \| \cdot \| _S, r) \le N^{\mathrm{ext}}(G, \| \cdot \| _\infty , r)\): a sup-norm cover is an empirical cover, since \(\| u - v\| _S \le \| u - v\| _\infty \).

For every sample \(S\) and \(r \ge 0\), \(N^{\mathrm{ext}}(F, d_S, r) \le N^{\mathrm{ext}}(F, d_\infty , r)\), since \(d_S \le d_\infty \) (lem:dS-le-dinf).

If \(|h(f(x_i)) - h(g(x_i))| \le c\, d(f(x_i), g(x_i))\) for every \(i\) (\(c \ge 0\)), then \(\| h \circ f - h \circ g\| _S \le c\, d_S(f, g)\).

\(\| u \circ f - v \circ f\| _S = \| u - v\| _{f \circ S}\): the empirical norm of a composition is the empirical norm on the pushed-forward sample \(f \circ S = (f(x_1), \dots , f(x_n))\).

For a single hidden map \(f_0\) with bounded Rademacher averages, \(\hat{\mathfrak R}_S(H \circ \{ f_0\} ) = \mathbb E_\sigma Z_{f_0}(\sigma )\).

\(\hat{\mathfrak R}_S(\emptyset ) = 0\) (the supremum over the empty class is \(0\) by convention).

If \(|g(x_i)| \le C\) for all \(g \in G\) and \(i \le n\), then the one-sided empirical Rademacher complexity is dominated by the absolute one: \(\hat{\mathfrak R}_S(G) \le \mathbb E_\sigma \sup _{g \in G} \bigl|\frac1n \sum _i \sigma _i g(x_i)\bigr|\).

If \(G_1 \subseteq G_2\), \(G_1 \ne \emptyset \) and the Rademacher averages \(\{ \frac1n\sum _i \sigma _i g(x_i) : g \in G_2\} \) are bounded above for every sign pattern \(\sigma \), then \(\hat{\mathfrak R}_S(G_1) \le \hat{\mathfrak R}_S(G_2)\).

If \(G \ne \emptyset \) and for every sign pattern \(\sigma \) the Rademacher averages \(\{ \frac1n\sum _i \sigma _i g(x_i) : g \in G\} \) are bounded above, then \(\hat{\mathfrak R}_S(G) \ge 0\).

If \(\ell \) is \(\beta _\ell \)-Lipschitz in its first argument (with \(\beta _\ell \ge 0\)) and \(\sup _x |f(x) - g(x)| \le c\) with \(c \ge 0\), then \(|\hat L[f] - \hat L[g]| \le \beta _\ell c\) for every sample.

On a bounded state space, \(d(x,y) \le D_{\mathcal X}\) for all \(x, y\) (\(D_{\mathcal X} \ge 0\)), every class satisfies \(\mathrm{diam}_S(A) \le D_{\mathcal X}\); in particular \(D_k(S) \le \mathrm{diam}(\mathcal X)\) for all \(k\).

On a compact state space, \(D_k(S) \le \mathrm{diam}(\mathcal X)\) for every class \(A\) and every sample \(S\).

(Diameter envelopes transfer from \(d_\infty \) to \(d_S\).) If \(d_\infty (f,g) \le D\) for all \(f, g \in A\), with \(D \ge 0\), then \(\mathrm{diam}_S(A) \le D\) for every sample \(S\).

If \(d_\infty (f,g) \le \overline D {\lt} \infty \) for all \(f, g \in A\) then \(\mathrm{diam}_S(A) \le \overline D\).

\(\mathrm{diam}_S(A) \ge 0\).

(Diameter envelope under P2, non-compact case.) Under the hypotheses of ‘lem:p2-diameter‘, \(D_k(S) = \mathrm{diam}_S B(k,F) \le 2 L_\alpha R_S k\) for every sample \(S\).

\(d_S(f,g) = d_S(g,f)\).

If \(d_S(f,g) = 0\) then \(d(f(x_i), g(x_i)) = 0\) for every \(i \le n\).

If \(d(f(x_i), g(x_i)) \le D\) for every sample point, with \(D \ge 0\), then \(d_S(f,g) \le D\).

\(d_S(f,g) \ge 0\).

\(d_S(f,f) = 0\).

The empirical distance satisfies the triangle inequality: \(d_S(f,h) \le d_S(f,g) + d_S(g,h)\). Hence \(d_S\) is a pseudometric on \(\mathcal X^{\mathcal X}\).

FoML’s empirical distance is dominated by the uniform distance: \(\| u - v\| _S \le \| u - v\| _\infty \) whenever the latter is finite (\(n \ge 1\)).

In \(\mathbb N \cup \{ \infty \} \), a finite product of suprema over nonempty index types is the supremum of the products: \(\prod _{i \in s} \sup _{a \in A_i} g_i(a) = \sup _{x \in \prod _i A_i} \prod _{i \in s} g_i(x_i)\).

Composition covering lemma. If every \(h \in H\) is \(L_H\)-Lipschitz then for every \(\varepsilon \ge 0\),

(For \(L_H = 0\) the second radius is \(0\) by the convention \(x/0 = 0\), and the inequality still holds.)

For \(L_H\)-Lipschitz \(H\) and radii \(r_1, r_2 \ge 0\), \(N^{\mathrm{ext}}(H \circ F, \| \cdot \| _\infty , r_1 + L_H r_2) \le N^{\mathrm{ext}}(H, \| \cdot \| _\infty , r_1) \cdot N^{\mathrm{ext}}(F, d_\infty , r_2)\).

Composition covering lemma on the sample. If every \(h \in H\) is \(L_H\)-Lipschitz on \(\mathcal R_S(F)\) then for every \(\varepsilon \ge 0\),

(For \(L_H = 0\) the second radius is \(0\) by the convention \(x/0 = 0\).) Compared with the sup-norm lemma lem:ent-composition-covering, the radius of \(F\) is \(\varepsilon /(4L_H)\) instead of \(\varepsilon /(2L_H)\): the cover of \(F\) must have its centres in \(F\), and \(N(F, d_S, 2r) \le N^{\mathrm{ext}}(F, d_S, r)\).

For \(H\) \(L_H\)-Lipschitz on \(\mathcal R_S(F)\) and radii \(r_1, r_2 \ge 0\), \(N^{\mathrm{ext}}(H \circ F, \| \cdot \| _S, r_1 + L_H r_2) \le N_{S,F}(H, r_1) \cdot N(F, d_S, r_2)\), where \(N(F, d_S, \cdot )\) is the internal covering number (centres in \(F\)). Proof: choose a minimal internal cover \(C_F\) of \(F\) and, for each \(f_b \in C_F\), a minimal external cover of \(H\) for \(\| \cdot \| _{f_b \circ S}\); apply lem:comp-cover-sample and count.

Entropy of the composition class. Let every \(h \in H\) be \(L_H\)-Lipschitz with \(L_H {\gt} 0\), and let \(\varepsilon \in \mathbb R\) be such that \(N^{\mathrm{ext}}(H, \| \cdot \| _\infty , \varepsilon /2)\) and \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon /(2L_H))\) are finite. Then

Entropy of the composition class on the sample. Let every \(h \in H\) be \(L_H\)-Lipschitz on \(\mathcal R_S(F)\) with \(L_H {\gt} 0\), and let \(\varepsilon \in \mathbb R\) be such that \(N_{S,F}(H, \varepsilon /2)\) and \(N^{\mathrm{ext}}(F, d_S, \varepsilon /(4L_H))\) are finite. Then

Assumption ass:ent-readout implies ass:ent-readout-sample for every sample \(S\) (\(n \ge 1\)) and every hidden class \(F\).

Assumption ass:ent-transition implies ass:ent-transition-sample for every sample \(S\).

If \(F \ne \emptyset \) has finite \(d_\infty \) covering numbers at every positive scale, then \(v \mapsto \mathcal E_F(v)\) is antitone on \((0, \infty )\).

\(\mathcal E_F(v) \ge 0\).

If \(F \ne \emptyset \) has finite \(d_S\) covering numbers at every positive scale, then \(v \mapsto \mathcal E_{F,S}(v)\) is antitone on \((0, \infty )\).

\(\mathcal E_{F,S}(v) \ge 0\).

If \(H \ne \emptyset \) has finite uniform covering numbers at every positive scale, then \(u \mapsto \mathcal E_H(u)\) is antitone on \((0, \infty )\).

\(\mathcal E_H(u) \ge 0\).

If \(H, F \ne \emptyset \) and \(N_{S,F}(H, u) {\lt} \infty \) for every \(u {\gt} 0\), then \(u \mapsto \mathcal E_{H,S}(u)\) is antitone on \((0, \infty )\).

\(\mathcal E_{H,S}(u) \ge 0\).

If \(\sqrt{\log N(A,\varepsilon )} \le g(\varepsilon )\) on \((0, D]\) for an interval-integrable \(g\) on \([0, D]\), then \(\mathsf V(D, A) \le \int _0^D g\).

Combined comparison: if \(0 \le D \le \overline D\) and \(\sqrt{\log N(A,\varepsilon )} \le g(\varepsilon )\) on \((0, \overline D]\) for an interval-integrable \(g\) on \([0, \overline D]\), then \(\mathsf V(D, A) \le \int _0^{\overline D} g\).

(Polynomial growth, bounded diameter; single-set form.) If \(0 \le D \le \overline D\), \(\overline D {\gt} 0\), \(C_0 \ge 1\), \(D \ge 0\) (the exponent) and \(N(A, \varepsilon ) \le C_0 (1 + k/\varepsilon )^{D}\) for all \(\varepsilon {\gt} 0\), then \(\mathsf V(D, A) \le \overline D\sqrt{D}\bigl(\sqrt{\log (1 + k/\overline D)} + \tfrac {\sqrt\pi }{2}\bigr) + \overline D\sqrt{\log C_0}\).

\(\mathsf V(D, A) \le \mathsf V(D', A)\) for \(0 \le D \le D'\), provided the integrand is interval-integrable on \([0, D']\) (the integrand is nonnegative).

\(\mathsf V(D, A) \ge 0\) for \(D \ge 0\).

Almost-everywhere comparison of the entropy integrands. Let \(H \ne \emptyset \), \(F \ne \emptyset \) satisfy Assumptions ass:ent-readout, ass:ent-transition with \(L_H {\gt} 0\), \(n \ge 1\), and let \(N_S(x)\) be FoML’s open-ball covering number of \(H \circ F\) for \(\| \cdot \| _S\). Then for every \(\varepsilon {\gt} 0\) and Lebesgue-a.e. \(x {\gt} \varepsilon \),

Proof: for every \(y {\lt} x\), \(N_S(x) \le N^{\mathrm{ext}}(H \circ F, \| \cdot \| _\infty , y/2) \le N^{\mathrm{ext}}(H, y/4) N^{\mathrm{ext}}(F, y/(4L_H))\); the right-hand side \(\psi (y) = \mathcal E_H(y/4) + \mathcal E_F(y/(4L_H))\) is antitone in \(y\), hence continuous outside a countable set, and letting \(y \uparrow x\) at a continuity point gives the claim.

Almost-everywhere comparison of the entropy integrands on the sample. Let \(H, F \ne \emptyset \) satisfy ass:ent-readout-sample and ass:ent-transition-sample with \(L_H {\gt} 0\), and let \(N_S(x)\) be FoML’s open-ball covering number of \(H \circ F\) for \(\| \cdot \| _S\). Then for every \(\varepsilon {\gt} 0\) and Lebesgue-a.e. \(x {\gt} \varepsilon \),

Proof: for every \(y {\lt} x\), \(N_S(x) \le N^{\mathrm{ext}}(H \circ F, \| \cdot \| _S, y/2) \le N_{S,F}(H, y/4)\, N^{\mathrm{ext}}(F, d_S, y/(8L_H))\); the right-hand side is antitone in \(y\), hence continuous outside a countable set, and we let \(y \uparrow x\) at a continuity point.

(Simplified envelope.) If every \(f \in F\) is \(\Lambda \)-Lipschitz then for every \(k \ge 0\) and \(\varepsilon \ge 0\),

If all layers of \(u\) lie in \(F\) then \(f_u \in F^{|u|}\).

Every \(g \in F^m\) is \(f_u\) for a list \(u\) of elements of \(F\) with \(|u| = m\).

As a real number, \(S_m(\Lambda ) = \sum _{i{\lt}m} \Lambda ^i\).

With \(\Lambda _+ := \max \{ 1, \Lambda \} \), \(S_k(\Lambda ) \le k\, \Lambda _+^k\) (since \(\Lambda ^i \le \Lambda _+^k\) for \(i {\lt} k\)).

\(m \mapsto S_m(\Lambda )\) is nondecreasing.

\(S_1(\Lambda ) = 1\).

\(S_m(\Lambda ) \ge 1\) for \(m \ge 1\).

\(S_m(\Lambda ) {\gt} 0\) for \(m \ge 1\).

\(S_{m+1}(\Lambda ) = 1 + \Lambda \, S_m(\Lambda )\).

\(S_0(\Lambda ) = 0\).

(Logarithmic form of the envelope.) If every \(f \in F\) is \(\Lambda \)-Lipschitz, \(k \ge 1\) and \(N := N^{\mathrm{ext}}(F, \varepsilon /S_k(\Lambda )) {\lt} \infty \), then \(\log N^{\mathrm{ext}}(B(k,F), \varepsilon ) \le \log (k+1) + k\log N\) (using \(1 + kN^k \le (k+1)N^k\) for \(N \ge 1\); for \(N = 0\) both sides are \(\ge 0 = \log 1\)).

(Transfer to the empirical metric.) If every \(f \in F\) is \(\Lambda \)-Lipschitz and \(N^{\mathrm{ext}}(F, d_\infty , \varepsilon /(2S_k(\Lambda ))) {\lt} \infty \), then \(\log N(B(k,F), d_S, \varepsilon ) \le \log N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon /2)\) for every sample \(S\) (‘lem:covering-empSpace-le-external-unifMaps‘).

If \(N^{\mathrm{ext}}(F, \varepsilon /S_k(\Lambda )) {\lt} \infty \) then \(N^{\mathrm{ext}}(B(k,F), \varepsilon ) {\lt} \infty \).

(First inequality of ‘prop:envelope‘.) If every \(f \in F\) is \(\Lambda \)-Lipschitz then for every \(k \ge 0\) and \(\varepsilon \ge 0\),

(Second inequality of ‘prop:envelope‘.) For every \(k \ge 0\) and \(\varepsilon \ge 0\),

because \(S_m(\Lambda ) \le S_k(\Lambda )\) for \(m \le k\), covering numbers are nonincreasing in the radius, and \(N^m \le N^k\) for \(N \ge 1\) (or \(N = 0\), \(m, k \ge 1\)).

(Uniform form of the telescoping estimate ‘lem:impl-word-error‘.) If every \(f \in F\) is \(\Lambda \)-Lipschitz and \(d_\infty (f, \tilde f) \le \delta \) for \(f \in F\), then \(d_\infty (f_u, \tilde f_u) \le \delta \sum _{i{\lt}|u|} \Lambda ^i\) for every list \(u\) of layers in \(F\).

\(B(k, \emptyset ) = \{ \mathrm{id}\} \).

(Covering the words of length \(m\).) If every \(f \in F\) is \(\Lambda \)-Lipschitz then for every \(\varepsilon \ge 0\) and \(m \ge 0\),

The \(M^m\) compositions \(c_{i_m} \circ \cdots \circ c_{i_1}\) of the centres of an \(\varepsilon /S_m(\Lambda )\)-cover \(\{ c_1, \dots , c_M\} \) of \(F\) form an \(\varepsilon \)-cover of \(F^m\) by the telescoping estimate.

The evaluation map \(\mathrm{ev}_P\) is \(1\)-Lipschitz from \(d_\infty \) to the sup-metric on \(\mathcal X^J\).

For \(\alpha {\gt} 0\), eventually in \(n\): \(\sqrt{\log \log n/n} \le \mathsf{gen}({k^{\ast }},n) \le \bigl(1 + \sqrt{1 + |\log (2\alpha )|}\bigr)\sqrt{\log \log n/n}\).

For \(\alpha ,\gamma {\gt} 0\), eventually in \(n\): \(n^{-1/2}(\log n)^{\gamma /2} \le \mathsf{gen}({k^{\ast }},n) \le \bigl(1 + \sqrt{(2\alpha )^{-\gamma }}\bigr)\, n^{-1/2}(\log n)^{\gamma /2}\).

For every \(c {\gt} 0\), \(\log x \le c\, x\) for all sufficiently large \(x\).

For every \(c {\gt} 0\), \(\log \log n \le c \log n\) for all sufficiently large \(n\).

For \(\beta {\gt} 0\), eventually in \(n\): \(\sqrt{1/(4\beta )}\sqrt{\log n/n} \le \mathsf{gen}({k^{\ast }},n) \le 2\sqrt{(1 + |\log 2\beta |)/(2\beta )}\, \sqrt{\log n/n}\).

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\).

(Integrability for finite hidden-layer classes.) If \(F\) is finite with \(|F| = r \ge 2\) and \(d(x,y) \le D_{\mathcal X}\), then the entropy integrand of \(B(k,F)\) is bounded by the constant \(\sqrt{(k+1)\log r}\), hence interval-integrable on \([0, D_k(S)]\).

For \(\kappa , \varepsilon _0, R_{\mathrm{out}} {\gt} 0\), \(n \ge 1\) and \(q \ge 0\), the first branch of the minimum is the smaller one as soon as \(n \ge R_{\mathrm{out}}^2 q / (\kappa ^2 \varepsilon _0^2)\): \(\kappa \varepsilon _0 \sqrt{q/n} \le \kappa ^2 \varepsilon _0^2 / R_{\mathrm{out}}\).

FoML covering numbers versus empirical external covering numbers. Let \(G \subseteq \mathbb R^{\mathcal X}\) be nonempty and totally bounded for \(\| \cdot \| _S\), and let \(0 \le 2r {\lt} x\). Then FoML’s open-ball covering number of \(G\) for \(\| \cdot \| _S\) satisfies \(N^{\mathrm{open}}_S(G, x) \le N(G, \| \cdot \| _S, 2r) \le N^{\mathrm{ext}}(G, \| \cdot \| _S, r)\) (the two metrics coincide; the factor \(2\) is the price of the internal cover).

FoML covering numbers versus uniform external covering numbers. Let \(G \subseteq \mathbb R^{\mathcal X}\) be nonempty and totally bounded for \(\| \cdot \| _S\), and let \(0 \le 2r {\lt} x\). Then FoML’s open-ball covering number of \(G\) for \(\| \cdot \| _S\) satisfies \(N^{\mathrm{open}}_S(G, x) \le N(G, \| \cdot \| _\infty , 2r) \le N^{\mathrm{ext}}(G, \| \cdot \| _\infty , r)\) (internal closed \(2r\)-balls for the sup norm with centres in \(G\) are contained in open \(x\)-balls for \(\| \cdot \| _S\)).

(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}\).

(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‘.

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

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 element of \(H_R \circ B(k, F_{\rm fp})\) is Borel measurable.

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

(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)\).

(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\).)

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

(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‘).

(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 \).

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

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

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

(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‘).

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 )\).

(Right inverse from a well-conditioned Gram matrix.) Let \(\varphi _1, \dots , \varphi _n \in \mathcal H\) and suppose the Gram matrix \(G = (\langle \varphi _i, \varphi _{i'} \rangle )_{i,i'}\) satisfies \(c^\top G c \ge \lambda _{\min } \| c\| _2^2\) for all \(c \in \mathbb R^n\), with \(\lambda _{\min } {\gt} 0\). Then for every \(c \in \mathbb R^n\) there is \(w \in \mathcal H\) with \(\langle w, \varphi _i\rangle = c_i\) for all \(i\) and \(\| w\| \le \lambda _{\min }^{-1/2} \| c\| _2\).

(Restatement of ‘thm:hidden-decomp-depth‘.) Under the hypotheses of ‘thm:hidden-decomp-depth‘ (including the integrability of the entropy integrand of \(B(k,F_0)\) on \([0, D_k(S)]\)), \(\hat{\mathfrak R}_S(\mathcal H_k) \le \hat{\mathfrak R}_S(H) + \mathrm{var}(k,n)\).

The hypothesis classes are increasing in depth: \(\mathcal H_k \subseteq \mathcal H_{k+1}\).

\(\mathcal H_0 = H \circ \{ \mathrm{id}\} = H\).

\(\mathrm{id} \in B(k,F)\) for every \(k\).

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

If \(\varepsilon _{\mathrm{imp}} = \sup _{f \in \mathcal H} \| f - \iota f\| _\infty \le \varepsilon \) with \(\varepsilon \ge 0\), then \(|\iota f(x) - f(x)| \le \varepsilon \) for all \(f \in \mathcal H\), \(x \in \mathcal X\).

(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\).

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

(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\),

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

\(\frac1n \sum _k \sigma _k \langle w, u_k\rangle = \bigl\langle w, \frac1n \sum _k \sigma _k u_k \bigr\rangle \).

A set \(C\) is an \(\varepsilon \)-cover of \(A\) for \(\| \cdot \| _S\) iff every \(u \in A\) has some \(c \in C\) with \(\| u - c\| _S \le \varepsilon \).

A set \(C\) is an \(\varepsilon \)-cover of \(A\) for \(d_S\) iff every \(f \in A\) has some \(c \in C\) with \(d_S(f, c) \le \varepsilon \).

FoML’s ‘EmpiricalFunctionSpace‘ of a class \(G\) (metric \(\| \cdot \| _S\)) embeds isometrically into \((\mathbb R^{\mathcal X}, \| \cdot \| _S)\) by evaluating the index.

If \(0 \le g\) eventually, \(c {\gt} 0\), and \(g \le f \le c\, g\) eventually, then \(f = \Theta (g)\).

For \(\alpha {\gt} 0\) and \(\log n \ge e\): \(0 {\lt} {k^{\ast }}\le \log n/(2\alpha )\) and \(\log {k^{\ast }}\le \log \log n + |\log (2\alpha )|\).

For \(\alpha , \gamma {\gt} 0\) and \(\log n \ge 1\), \({k^{\ast }}\le \log n/(2\alpha )\).

Left composition with a \(K\)-Lipschitz map \(f\) is \(K\)-Lipschitz for \(d_\infty \): \(d_\infty (f \circ a, f \circ b) \le K\, d_\infty (a, b)\).

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

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

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

(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.)

(‘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\).

If \(\varphi \) is Lipschitz into a metric space and \(d_S(f,g) = 0\), then \(\varphi (f(x_i)) = \varphi (g(x_i))\) for every \(i \le n\).

If \(c \le a\, b\) in \(\mathbb N \cup \{ \infty \} \) with \(a, b {\lt} \infty \), then \(\log c \le \log a + \log b\) (with \(\log 0 = 0\); all three logarithms are \(\ge 0\)).

For \(\beta {\gt} 0\), \(n {\gt} 0\) and \(L = \log (2\beta n) {\gt} 0\): \(\log {k^{\ast }}= (L - \log L)/(2\beta )\).

\(\log x {\lt} x\) for \(x {\gt} 0\).

For natural numbers \(k, N\): \(\log (1 + kN) \le \log (k+1) + \log N\) (with \(\log 0 = 0\)): \(1 + kN \le (k+1)N\) when \(N \ge 1\), and \(\log 1 = 0\) when \(N = 0\).

For \(\overline D {\gt} 0\), \(k \ge 0\) and \(0 {\lt} \varepsilon \le \overline D\), \(\log \bigl(1 + \tfrac {k}{\varepsilon }\bigr) \le \log \bigl(1 + \tfrac {k}{\overline D}\bigr) + \log \tfrac {\overline D}{\varepsilon }\).

If \(A \le 1 + kN\) in \(\mathbb N \cup \{ \infty \} \) with \(N {\lt} \infty \), then \(\log A \le \log (k+1) + \log N\) (as real numbers, with \(\log \infty = \log 0 = 0\)).

For \(\beta {\gt} 0\) and \(\log n \ge \max \{ 1, 2|\log 2\beta |\} \): \(\tfrac 12\log n \le \log (2\beta n) \le (1 + |\log 2\beta |)\log n\).

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

\(f(x_i) \in \mathcal R_S(F)\) for \(f \in F\).

\(f \in B(k,F)\) if and only if \(f \in F^l\) for some \(l \le k\).

If \(g \in F\) and \(f \in B(k,F)\) then \(g \circ f \in B(k+1,F)\).

The metric entropy is antitone in the scale: if \(\varepsilon \le \delta \) and \(N(A,\varepsilon ) {\lt} \infty \) then \(\log N(A,\delta ) \le \log N(A,\varepsilon )\).

\(\log N(A,\varepsilon ) \ge 0\) for every \(A\) and \(\varepsilon \).

\(n\, d_S(f,g)^2 = \sum _{i=1}^n d(f(x_i), g(x_i))^2\).

(Modulus extraction on compact domains.) Let \((\mathcal X,d)\) be compact and \(H \subseteq \mathcal X^{\mathcal X}\) equicontinuous. Then \(H\) admits a common monotone modulus of continuity \(\omega \) with \(\omega (r) \to 0\) as \(r \downarrow 0\) and \(d(f(x), f(y)) \le \omega (d(x,y))\) for all \(f \in H\), \(x, y \in \mathcal X\). In particular ‘thm:maa‘ applies.

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

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

(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\)).

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).

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

(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\).

(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)\).

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)\).

(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.)

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

(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}\).)

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

(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.)

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

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

(Two drifts.) 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}\).

(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}\).

(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‘.

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

(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‘).

(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).

(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.

(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‘).

Restricting the extension gives back the restricted drift.

(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

(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‘).

\(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 Lipschitz, hence continuous.

(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}\).

(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‘.)

(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)\).

(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.

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)\).

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

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

If \(N {\lt} \infty \) then \(1 + kN {\lt} \infty \) (in \(\mathbb N \cup \{ \infty \} \)).

If \(h(f(x_i)) = h(g(x_i))\) for all \(h \in H\) and \(i \le n\), then \(Z_f(\sigma ) = Z_g(\sigma )\) for every \(\sigma \).

(Integrability under P1.) Under the hypotheses of ‘cor:profile-p1-totallyBounded‘ (in particular the interval-integrability of the majorant \(\sqrt{\log N_\infty }\) on \([0, D_{\mathcal X}]\)), the entropy integrand \(\varepsilon \mapsto \sqrt{\log N(B(k,F), d_S, \varepsilon )}\) is interval-integrable on \([0, D_k(S)]\) for every \(k\): the hypothesis of ‘thm:hidden-decomp-depth‘ is automatic.

(Long words are almost constant.) Under the hypotheses of ‘cond:p1-ucont‘, for every word \(w \in F^l\) with \(l \ge m(\varepsilon )\) and all \(x, y \in \mathcal X\),

In particular \(d_\infty (w, \mathrm{const}_{w(a_0)}) \le \varepsilon /2\) for every \(a_0\).

(Long words.) Under the hypotheses of ‘cond:p1-ucont‘, the set of all words of length \(\ge m(\varepsilon )\) satisfies

Indeed each such word \(w\) is \(\varepsilon /2\)-close to the constant map \(\mathrm{const}_{w(a_0)}\) with \(w(a_0) \in A\), so the constant maps at the points of an \(\varepsilon /2\)-net of \(A\) form an \(\varepsilon \)-cover.

If \(0 {\lt} c {\lt} 1\), \(\varepsilon {\gt} 0\) and \(m(\varepsilon ) \le n + L\) then \(c^n \, \mathrm{diam}(K) \le \varepsilon /2\).

(Short words; subadditivity over finitely many sets.) For a finite family \((A_i)_{i \in s}\), \(N^{\mathrm{ext}}\bigl(\bigcup _{i \in s} A_i, \varepsilon \bigr) \le \sum _{i \in s} N^{\mathrm{ext}}(A_i, \varepsilon )\). Applied to \(A_l = F^l\), \(l {\lt} m(\varepsilon )\), this covers the short words.

\(C_0 = 2^D C_H \max (1, R_S L_\alpha )^D \ge 1\).

(Diameter envelope.) Under the hypotheses of ‘lem:p2-wordball-subset-ball‘ and with the orbit map \(L_\alpha \)-Lipschitz, for all \(f, g \in B(k,F)\),

i.e. \(\mathrm{diam}_\infty B(k,F) \le 2L_\alpha R_S k\) (and a fortiori \(D_k(S) \le 2 L_\alpha R_S k\) for every sample \(S\)).

(P2 in the empirical metric.) Under the hypotheses of ‘cond:p2-nilp‘, for every \(k\) and \(\varepsilon {\gt} 0\),

as real numbers. (The factor \(2^D\) comes from \(N(\cdot , d_S, \varepsilon ) \le N^{\mathrm{ext}}(\cdot , d_\infty , \varepsilon /2)\) and \(1 + 2k/\varepsilon \le 2(1 + k/\varepsilon )\).)

(Integrability under P2.) Under the hypotheses of ‘cond:p2-nilp‘, if \(D_k(S) \le \overline D\) with \(\overline D {\gt} 0\), then the entropy integrand of \(B(k,F)\) is interval-integrable on \([0, D_k(S)]\) (it is dominated by \(\sqrt{\log C_0} + \sqrt D\sqrt{\log (1 + k/\overline D)} + \sqrt D\sqrt{\log (\overline D/\varepsilon )}\), ‘lem:sqrt-metric-entropy-le-of-poly‘).

\(\alpha (gh) = \alpha (g) \circ \alpha (h)\).

\(\alpha (e) = \mathrm{id}\).

For \(\varepsilon , L_\alpha {\gt} 0\), \(R_S \ge 0\), \(k \ge 0\) and \(D \ge 0\),

If the orbit map is \(L_\alpha \)-Lipschitz, \(d_\infty (\alpha (g), \alpha (h)) \le L_\alpha d_H(g,h)\), then for every \(B \subseteq H\) and \(\delta \ge 0\),

Under the hypotheses of ‘lem:p2-wordball-subset-ball‘ and ‘lem:p2-transfer‘, for every \(k\) and \(\delta \ge 0\),

Let \(\alpha : H \to \mathcal X^{\mathcal X}\) be a homomorphism, assume the length \(g \mapsto d_H(e,g)\) is subadditive, \(d_H(e, gh) \le d_H(e,g) + d_H(e,h)\), and let \(S \subseteq H\) satisfy \(d_H(e,s) \le R_S\) for all \(s \in S\) and \(F \subseteq \alpha (S)\). Then for every \(k\),

\(M(A, d_S, \varepsilon ) \le M(A, d_\infty , \varepsilon )\) (packing numbers).

(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}\).

Let \(f = (f_1,\dots ,f_r)\) and let \(P\) be a finite family of probes such that the evaluations \(\mathrm{ev}_P(f_u)\), \(u \in [r]^k\), are pairwise at sup-distance \(\ge \delta {\gt} 0\). Then \(N^{\mathrm{ext}}(B(k,F), d_\infty , \varepsilon ) \ge r^k\) for every \(\varepsilon \) with \(2\varepsilon {\lt} \delta \).

(Probes and packing.) Let \(A \subseteq (\mathcal X^{\mathcal X}, d_\infty )\), let \(P\) be a finite family of probes and let \(T \subseteq \mathrm{ev}_P(A)\) be \(\delta \)-separated: \(d_{\max }(y,z) \ge \delta \) for all distinct \(y, z \in T\). Then for every \(\varepsilon \) with \(2\varepsilon {\lt} \delta \), \(|T| \le N^{\mathrm{ext}}(A, d_\infty , \varepsilon )\).

(Indexed form of ‘lem:probes-packing‘.) Let \((g_i)_{i \in I}\) be a family of maps in \(A \subseteq (\mathcal X^{\mathcal X}, d_\infty )\) and \(P\) a finite family of probes such that \(d_{\max }(\mathrm{ev}_P(g_i), \mathrm{ev}_P(g_j)) \ge \delta {\gt} 0\) for all \(i \ne j\). Then \(|I| \le N^{\mathrm{ext}}(A, d_\infty , \varepsilon )\) whenever \(2\varepsilon {\lt} \delta \).

Under the hypotheses of the previous lemma, also \(|T| \le N(A, d_\infty , \varepsilon )\) (internal covering number).

\(N_{S,F}(H, r) \le N^{\mathrm{ext}}(H, \| \cdot \| _\infty , r)\) for every sample \(S\) (\(n \ge 1\)): the sup-norm covering number dominates the covering numbers on all pushed-forward samples.

\(u \mapsto N_{S,F}(H, u)\) is antitone.

\(N^{\mathrm{ext}}(H, \| \cdot \| _{f \circ S}, u) \le N_{S,F}(H, u)\) for \(f \in F\).

\(N_{S,F}(H, u) {\gt} 0\) when \(H, F \ne \emptyset \).

\(n^{-1/2}(\log n)^{\gamma /2} \ge 0\) for \(n \ge 1\).

For \(n {\gt} 1\), \(\sqrt{\log n/n} = n^{-1/2}(\log n)^{1/2}\).

(Reachable radius.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, \(x_0 \in \mathcal X\), \(R \ge 0\), and suppose \(d(f(x_0), x_0) \le c\) for all \(f \in F\) (with \(c \ge 0\)). Then every \(g \in B(k,F)\) maps the ball \(B(x_0,R)\) into \(B\bigl(x_0, \Lambda ^kR + c\, S_k(\Lambda )\bigr)\) when \(\Lambda \ge 1\), and into \(B\bigl(x_0, R + c\, S_k(\Lambda )\bigr)\) when \(\Lambda \le 1\). Consequently, if \(S \subset B(x_0,R)\), then \(D_k(S) \le 2\bigl(\Lambda _+^kR + c\, S_k(\Lambda )\bigr)\) with \(\Lambda _+ = \max \{ 1,\Lambda \} \): bounded in \(k\) if \(\Lambda {\lt} 1\), at most linear if \(\Lambda = 1\), and at most exponential if \(\Lambda {\gt} 1\).

(Reachable radius, \(\Lambda \le 1\).) Under the hypotheses of ‘lem:reachable-radius-core‘, if \(\Lambda \le 1\) then every \(g \in B(k,F)\) maps \(B(x_0,R)\) into \(B\bigl(x_0, R + c\, S_k(\Lambda )\bigr)\).

(Reachable radius, unified form.) Let every \(f \in F\) be \(\Lambda \)-Lipschitz, \(x_0 \in \mathcal X\), \(c \ge 0\) with \(d(f(x_0), x_0) \le c\) for all \(f \in F\), and \(R \ge 0\). Then every \(g \in B(k,F)\) maps \(B(x_0, R)\) into \(B\bigl(x_0, \Lambda _+^kR + c\, S_k(\Lambda )\bigr)\), \(\Lambda _+ := \max \{ 1,\Lambda \} \): for \(d(x,x_0) \le \rho \), \(d(f(x), x_0) \le d(f(x), f(x_0)) + d(f(x_0), x_0) \le \Lambda \rho + c\); iterate.

(Diameter of the reachable states.) Under the hypotheses of ‘lem:reachable-radius-core‘, if the sample lies in \(B(x_0, R)\) then \(D_k(S) \le 2\bigl(\Lambda _+^kR + c\, S_k(\Lambda )\bigr)\): bounded in \(k\) if \(\Lambda {\lt} 1\), at most linear if \(\Lambda = 1\), at most exponential if \(\Lambda {\gt} 1\).

(Reachable radius, \(\Lambda \ge 1\).) Under the hypotheses of ‘lem:reachable-radius-core‘, if \(\Lambda \ge 1\) then every \(g \in B(k,F)\) maps \(B(x_0,R)\) into \(B\bigl(x_0, \Lambda ^kR + c\, S_k(\Lambda )\bigr)\).

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

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

(\(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]\).

\(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‘.

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

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

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

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

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

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

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).