2 Setting
2.1 Word balls and the semigroup generated by the hidden layers
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)\).
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\).
The semigroup (monoid) generated by \(F\) is \(\langle F\rangle = \bigcup _{k \ge 0} B(k,F)\).
\(B(0,F) = \{ \mathrm{id}\} \).
\(B(k+1,F) = B(k,F) \cup \{ g \circ f : g \in F,\ f \in B(k,F)\} \).
\(\mathrm{id} \in B(k,F)\) for every \(k\).
Induction on \(k\): \(\mathrm{id} \in B(0,F)\) and \(B(k,F) \subseteq B(k+1,F)\).
The word balls are increasing: \(B(k,F) \subseteq B(k+1,F)\), hence \(B(k,F) \subseteq B(l,F)\) for \(k \le l\).
If \(g \in F\) and \(f \in B(k,F)\) then \(g \circ f \in B(k+1,F)\).
\(B(k,F) \subseteq \langle F \rangle \) for every \(k\).
If \(F \subseteq G\) then \(B(k,F) \subseteq B(k,G)\).
Induction on \(k\), using that \(\circ \)-images are monotone in both arguments.
If \(f \in B(k,F)\) and \(g \in B(l,F)\) then \(g \circ f \in B(l+k,F)\).
Induction on \(l\) (the length of the word \(g\)). If \(g = \mathrm{id}\) this is \(f \in B(k,F)\); if \(g = a \circ b\) with \(a \in F\), \(b \in B(l,F)\) then \(g \circ f = a \circ (b \circ f)\) with \(b \circ f \in B(l+k,F)\) by induction.
\(B(k+1,F) = B(k,F) \cup F^{k+1}\): the word ball of radius \(k+1\) is the word ball of radius \(k\) together with the words of length exactly \(k+1\).
Induction on \(k\): \(F \circ B(k+1,F) = F \circ B(k,F) \cup F \circ F^{k+1}\) and \(F \circ B(k,F) \subseteq B(k+1,F)\).
\(|F^m| \le |F|^m\) (as extended natural numbers).
Induction on \(k\): \(F^{k+1}\) is the image of \(F \times F^k\) under composition.
\(|B(k,F)| \le \sum _{m=0}^{k} |F|^m\) (as extended natural numbers).
Induction on \(k\) using \(B(k+1,F) = B(k,F) \cup F^{k+1}\) and \(|F^{k+1}| \le |F|^{k+1}\).
If \(F\) is finite with \(|F| = r \ge 2\) then \(|B(k,F)| \le \sum _{m=0}^k r^m \le r^{k+1}\).
Combine the previous bound with the geometric sum estimate \(\sum _{m \le k} r^m = (r^{k+1}-1)/(r-1) {\lt} r^{k+1}\) for \(r \ge 2\).
2.2 Uniform and empirical metrics
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 \).
\(d(f(x), g(x)) \le d_\infty (f,g)\) for every \(x\).
Right composition is \(1\)-Lipschitz for \(d_\infty \): \(d_\infty (a \circ f, b \circ f) \le d_\infty (a, b)\).
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)\).
Pointwise, \(d(f(a(x)), f(b(x))) \le K d(a(x), b(x)) \le K d_\infty (a,b)\).
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).
\(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 (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.
Viewing \(f\) in \((\mathcal X^{\mathcal X}, d_\infty )\) does not change its values.
On \((\mathcal X^{\mathcal X}, d_\infty )\) the extended distance is \(d_\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}\).
\(d(f(x), g(x)) \le d_\infty (f,g)\) for \(f, g \in (\mathcal X^{\mathcal X}, d_\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}\).
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 sup norm \(\| u\| _{S,\infty } = \max _{i \le n} |u(x_i)|\) (equal to \(0\) when \(n = 0\)).
The empirical diameter of a class \(F\) is \(\mathrm{diam}_S(F) = \sup _{f, g \in F} d_S(f,g)\).
\(d_S(f,f) = 0\).
\(d_S(f,g) = d_S(g,f)\).
\(d_S(f,g) \ge 0\).
Minkowski’s inequality for the Euclidean norm on \(\mathbb R^n\): \(\bigl(\sum _i (u_i + v_i)^2\bigr)^{1/2} \le \bigl(\sum _i u_i^2\bigr)^{1/2} + \bigl(\sum _i v_i^2\bigr)^{1/2}\).
This is the triangle inequality in the Euclidean space \(\ell ^2(\{ 1,\dots ,n\} )\).
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}\).
Pointwise \(d(f(x_i), h(x_i)) \le d(f(x_i), g(x_i)) + d(g(x_i), h(x_i))\), then apply Minkowski’s inequality to the vectors of pointwise distances.
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}\).
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\).
If \(d_\infty (f,g) = \infty \) there is nothing to prove. Otherwise each term satisfies \(d(f(x_i), g(x_i))^2 \le d_\infty (f,g)^2\), so the average is at most \(d_\infty (f,g)^2\) and we take square roots.
2.3 Covering and packing numbers
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).
2.4 Hypothesis classes and implementation error
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\} \).
The depth-\(k\) hypothesis class is \(\mathcal H_k = H \circ B(k,F)\).
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 \).
If \(F \subseteq F'\) then \(H \circ F \subseteq H \circ F'\).
\(H \circ \{ \mathrm{id}\} = H\).
\(\mathcal H_0 = H \circ \{ \mathrm{id}\} = H\).
The hypothesis classes are increasing in depth: \(\mathcal H_k \subseteq \mathcal H_{k+1}\).
2.5 Loss, risk, and empirical minimizers
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 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 (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)\).
\(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 \).
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]\).
2.6 Rademacher complexity
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 (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)\).
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)\).
Compare the suprema termwise for each sign pattern \(\sigma \): every element of \(G_1\) is an element of \(G_2\).
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|\).
2.7 The entropy integral
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\).
2.8 Assumptions and auxiliary definitions of the main theorems
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 \).
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\).
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).
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\} \).
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\).
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}\).
On \((\mathbb R^{\mathcal X}, \| \cdot \| _\infty )\) the extended distance is \(\sup _x \mathrm{edist}(u(x), v(x))\).
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\).
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\).
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.
\(\mathrm{edist}(u, v) = \sup _x \mathrm{edist}(u(x), v(x))\) in \((\mathbb R^{\mathcal X}, \| \cdot \| _\infty )\).
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 hidden class at scale \(v\): \(\mathcal E_F(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_\infty , v)}\).
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‘).
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.
On \((\mathbb R^{\mathcal X}, \| \cdot \| _S)\) the distance is FoML’s ‘empiricalDist S‘.
On \((\mathbb R^{\mathcal X}, \| \cdot \| _S)\) the distance is \(\| u - v\| _S\).
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\).
\(f(x_i) \in \mathcal R_S(F)\) for \(f \in F\).
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.)
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).
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\).
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\) on the sample: \(\mathcal E_{F,S}(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_S, v)}\).
The identity map \((\mathcal X^{\mathcal X}, d_\infty ) \to (\mathcal X^{\mathcal X}, d_S)\).
The depth-dependent part of the estimation term is
with \(D_k(S) = \mathrm{diam}_S B(k,F)\).