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

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.

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

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.

General bias–variance decomposition (excess risk). Let \(\mathcal H\) be a sup-norm separable, pointwise bounded class of measurable functions \(\mathcal X \to \mathbb R\), \(\mathcal C\) a nonempty class of measurable benchmark functions, and \(\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\)). Let \(\iota \) be an implementation map, \(d_T\) a nonnegative function (pseudo-metric) and assume, for constants \(\beta _L, \beta _{\hat L} \ge 0\) and \(\varepsilon _{\mathrm{imp}} \ge 0\) (any upper bound for \(\sup _{f\in \mathcal H} d_T(\iota f, f)\)), that for every \(f \in \mathcal H\): \(d_T(\iota f, f) \le \varepsilon _{\mathrm{imp}}\), \(|L[\iota f] - L[f]| \le \beta _L d_T(\iota f, f)\) and \(|\hat L[\iota f] - \hat L[f]| \le \beta _{\hat L} d_T(\iota f, f)\) for every sample. Let \(n \ge 1\), \(\eta \ge 0\) and \(\delta \in (0,1)\). Then with probability at least \(1 - \delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(\eta \)-empirical minimizer \(\hat f \in \mathcal H\) satisfies, with \(\hat h := \iota (\hat f)\),

The Rademacher constant \(4\beta _\ell \) is the paper’s; the deviation constant is explicit (\(C b\sqrt{\log (1/\delta )/n}\) in the paper, with unspecified universal \(C\), becomes \(6b\sqrt{2\log (4/\delta )/n}\), from lem:bv-uniform-deviation-onesided). The pointwise boundedness of \(\mathcal H\) makes \(\hat{\mathfrak R}_S(\mathcal H)\) a genuine supremum.

General bias–variance decomposition (generalization gap). Under the hypotheses of thm:bv-general, with probability at least \(1-\delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(f \in \mathcal H\) (in particular every \(\eta \)-empirical minimizer \(\hat f\)) satisfies, with \(h := \iota (f)\),

(The paper states this for the \(\eta \)-empirical minimizer only, with \(2\beta _\ell \hat{\mathfrak R}_S(\mathcal H) + Cb\sqrt{\log (1/\delta )/n}\); its proof gives it for every \(f \in \mathcal H\), which is what we state. The deviation constant is explicit, see thm:bv-general.)

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

Implementation-free bias–variance decomposition. Fix \(k \ge 0\), \(\eta \ge 0\), \(n \ge 1\). Assume \(\mathcal H_k = H \circ B(k,F)\) consists of measurable functions, is sup-norm separable and pointwise bounded, \(\mathcal C\) is a nonempty class of measurable benchmarks, the loss \(\ell : \mathbb R \times \mathcal Y \to [0,b]\) is measurable and \(\beta _\ell \)-Lipschitz in its first argument (\(b {\gt} 0\), \(\beta _\ell \ge 0\)), the implementation map \(\iota \) produces measurable functions, and \(\varepsilon _{\mathrm{imp}}(k) = \sup _{f \in \mathcal H_k} \| f - \iota f\| _\infty \le \varepsilon _{\mathrm{imp}}\) for a real \(\varepsilon _{\mathrm{imp}} \ge 0\). Then for every \(\delta \in (0,1)\), with probability at least \(1-\delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(\eta \)-empirical minimizer \(\hat f \in \mathcal H_k\) satisfies, with \(\hat h := \iota (\hat f)\),

This is thm:bv-general with \(d_T(f,g) = \| f - g\| _\infty \) and \(\beta _L = \beta _{\hat L} = \beta _\ell \) (the loss is \(\beta _\ell \)-Lipschitz); the Rademacher constant \(4\beta _\ell \) is the paper’s and the deviation constant is explicit (as in thm:bv-general); \(\mathcal H_k\) is assumed pointwise bounded.

Implementation-free generalization gap. Under the hypotheses of thm:bv, with probability at least \(1-\delta \) over \(\mathcal D \sim P^{\otimes n}\), every \(f \in \mathcal H_k\) (in particular every \(\eta \)-empirical minimizer) satisfies, with \(h := \iota (f)\),

(The Rademacher constant \(2\beta _\ell \) is the paper’s; the deviation constant is explicit, as in thm:bv-general-gap.)

Let \(F \ne \emptyset \) and fix a sign pattern \(\sigma \). If for every \(f \in F\) the Rademacher averages \(\{ \frac1n\sum _i \sigma _i h(f(x_i)) : h \in H\} \) are bounded above, and \(f \mapsto Z_f(\sigma )\) is bounded above on \(F\), then \(\sup _{u \in H \circ F} \frac1n \sum _i \sigma _i u(x_i) = \sup _{f \in F} Z_f(\sigma )\).

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

Hidden–output decomposition under a sub-Gaussian increment condition. Let \(n \ge 1\), let \(F \subseteq \mathcal X^{\mathcal X}\) be totally bounded in \(d_S\), let \(f_0 \in F\) be an arbitrary anchor, and suppose Assumption ass:sg-increment-main holds on \(\mathfrak F \supseteq F\) with constants \(A_H, L {\gt} 0\). (We also assume that the suprema defining \(Z_f(\sigma )\), \(f \in F\), are finite, i.e. the Rademacher averages over \(H\) are bounded above; this is implicit in the paper.) Then

where \(\hat{\mathfrak R}_S(H \circ \{ f_0\} ) = \mathbb E_\sigma Z_{f_0}(\sigma )\) (lem:emp-rademacher-comp-singleton). This generalizes the paper, which assumes \(\mathrm{id} \in F\) and anchors at \(f_0 = \mathrm{id}\), giving \(\hat{\mathfrak R}_S(H)\) on the right-hand side (thm:hidden-decomp-id); the anchor is arbitrary because the Dudley bound thm:dudley-subgaussian-finite-space is anchored at any point. We assume in addition that the entropy integrand \(\varepsilon \mapsto \sqrt{\log N(F,d_S,\varepsilon )}\) is integrable on \([0,\mathrm{diam}_S(F)]\); the paper’s bound is trivially true with right-hand side \(+\infty \) otherwise, whereas Lean’s Bochner integral of a non-integrable function is \(0\).

Hidden–output decomposition, anchored at the identity (the paper’s form). Under the hypotheses of thm:hidden-decomp with \(\mathrm{id} \in F\),

Proof: thm:hidden-decomp with \(f_0 = \mathrm{id}\) and \(H \circ \{ \mathrm{id}\} = H\).

If Assumption ass:sg-increment-main holds on the semigroup \(\langle F_0 \rangle \) with constants \((A_H, L)\), then for every depth \(k \ge 0\) with \(B(k,F_0)\) totally bounded in \(d_S\),

with the same constants \(A_H, L\) (assuming, as in thm:hidden-decomp, that the entropy integrand of \(B(k,F_0)\) is integrable on \([0, \mathrm{diam}_S(B(k,F_0))]\)).

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

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

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

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 \(\varphi \) is \(L\)-Lipschitz then \(\sum _{i=1}^n d(\varphi (f(x_i)), \varphi (g(x_i)))^2 \le L^2\, n\, d_S(f,g)^2\).

A counting fraction on \(\{ \pm 1\} ^n\) is at most \(1\): \(\# \{ \sigma : p(\sigma )\} /2^n \le 1\).

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

Hilbert output layers satisfy the increment condition, given the vector Hoeffding inequality. Let \(\mathcal H\) be a real inner product space and \(\Phi : \mathcal X \to \mathcal H\) be \(L\)-Lipschitz. Assume the Rademacher tail bound lem:rademacher-hilbert-tail holds in \(\mathcal H\) for samples of size \(n\): \(\mathbb P_\sigma (\| \sum _i \sigma _i v_i\| {\gt} t) \le 2\exp (-t^2/(2\sum _i\| v_i\| ^2))\). Then Assumption ass:sg-increment-main holds for \(H = H_\Phi \) with \(A_H = 1\) and the same \(L\), for every hidden-layer class \(\mathfrak F\). Proof: \(|Z_f - Z_g| \le \sup _{\| w\| \le 1} |\langle w, \frac1n\sum _i \sigma _i v_i\rangle | = \| \frac1n \sum _i \sigma _i v_i\| \) with \(v_i = \Phi (f(x_i)) - \Phi (g(x_i))\), and \(\sum _i \| v_i\| ^2 \le L^2 n d_S(f,g)^2\).

Hilbert output layers satisfy the increment condition. Let \(\mathcal H\) be a real Hilbert space and \(\Phi : \mathcal X \to \mathcal H\) be \(L\)-Lipschitz. Then Assumption ass:sg-increment-main holds for \(H = H_\Phi \) with \(A_H = 1\) (and the same \(L\)), for every hidden-layer class \(\mathfrak F\).

One-dimensional Hilbert output layers. Let \(\Phi : \mathcal X \to \mathbb R\) be \(L\)-Lipschitz and \(H_\Phi = \{ x \mapsto w\, \Phi (x) : |w| \le 1\} \). Then Assumption ass:sg-increment-main holds for \(H_\Phi \) with \(A_H = 1\) and the same \(L\) (this is prop:hilbert-sg for \(\mathcal H = \mathbb R\), fully proved from the real Hoeffding inequality).

Finite Lipschitz scalar output layers. Let \(H = \{ h_1, \dots , h_m\} \) be a finite class of real-valued functions on \(\mathcal X\), each \(L\)-Lipschitz. Then Assumption ass:sg-increment-main holds with \(A_H = (1 + \log m / \log 2)^{1/2}\), for every hidden-layer class \(\mathfrak F\).

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

Conditional Sudakov-type lower bound. There is a universal constant \(c {\gt} 0\) such that the following holds. Let \((\mathcal X, d)\) be a pseudometric space, \(S = (x_1,\dots ,x_n)\) a sample with \(n \ge 1\), \(H\) an output-layer class, \(B \subseteq \mathcal X^{\mathcal X}\) an arbitrary hidden class, and suppose Assumption ass:readout-realization-main holds for \(B\) with constants \(\kappa , R_{\mathrm{out}} {\gt} 0\). Then for every \(\varepsilon {\gt} 0\),

equivalently the bound with \(\sup _{\varepsilon {\gt} 0}\) on the right. (In Lean \(\log M\) is read as \(0\) when \(M = \infty \), which only weakens the inequality.) This generalizes the paper, which states the bound for the word ball \(B = B(k,F)\) (thm:sudakov-type-wordball); the word-ball structure is not used in the proof, and \(B = \emptyset \) is allowed (both sides are then \(0\)). In Lean we add the hypothesis that, for every sign pattern, the Rademacher averages over \(H \circ B\) are bounded above (equivalently, that the supremum defining \(\hat{\mathfrak R}_S(H \circ B)\) is finite); without it the Lean statement is false because an unbounded supremum evaluates to \(0\). The proof is complete modulo the Bernoulli–Sudakov minoration thm:bernoulli-sudakov. Proof: take a maximal \(2\varepsilon \)-packing \(g_1, \dots , g_M\) of \(B\) for \(d_S\) (\(M = M(B, d_S, 2\varepsilon )\); if \(M = \infty \) the right-hand side is \(0\) in Lean and the claim is lem:emp-rademacher-nonneg); the transported vectors \(u_j = (h_{g_j}(g_j(x_i)))_i\) are \(2\kappa \varepsilon \)-separated in \(\| \cdot \| _S\) and bounded by \(R_{\mathrm{out}}\), so thm:bernoulli-sudakov gives \(\mathbb E_\sigma \max _j \frac1n\sum _i \sigma _i u_{j,i} \ge c\min \{ 2\kappa \varepsilon \sqrt{\log M/n}, 4\kappa ^2\varepsilon ^2/R_{\mathrm{out}}\} \), and the left-hand side is at most \(\hat{\mathfrak R}_S(H \circ B)\) since \(\{ h_{g_j} \circ g_j\} \subseteq H \circ B\).

Conditional Sudakov-type lower bound for word balls (the paper’s form). There is a universal constant \(c {\gt} 0\) such that, for \(F\) a hidden-layer class, \(k \ge 0\) and Assumption ass:readout-realization-main for \(B_k = B(k,F)\) with constants \(\kappa , R_{\mathrm{out}} {\gt} 0\) (and the boundedness hypothesis of thm:sudakov-type), for every \(\varepsilon {\gt} 0\),

Proof: thm:sudakov-type with \(B = B(k,F)\), since \(\mathcal H_k = H \circ B(k,F)\).

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.

(Substitution step.) There is a universal constant \(c {\gt} 0\) such that under Assumption ass:readout-realization-main for \(B_k\) and the boundedness hypothesis of thm:sudakov-type, for every \(\varepsilon _0 {\gt} 0\) and every \(q \ge 0\) with \(q \le \log M(B_k, d_S, 2\varepsilon _0)\), \(\hat{\mathfrak R}_S(\mathcal H_k) \ge c \min \{ \kappa \varepsilon _0 \sqrt{q/n}, \kappa ^2 \varepsilon _0^2 / 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

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

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

(Global scalar observable.) Fix a sample \(S = (x_i)_{i=1}^n\), a hidden class \(B_k\) and \(U_{k,S} = \{ f(x_i) : f \in B_k, i \in [n]\} \). Let \(\Phi : \mathcal X \to \mathcal H\) and assume there are \(u \in \mathcal H\) with \(\| u\| \le R_H\) and constants \(\kappa , R_\Phi {\gt} 0\) such that

Then the readout-realization assumption holds for \(H_{R_H}(\Phi )\) on \(B_k\) with constants \(\kappa \) and \(R_{\mathrm{out}} = R_H R_\Phi \), with the single choice \(h_f = h_u = \langle u, \Phi (\cdot )\rangle \) for all \(f \in B_k\): \(\| h_u \circ f - h_u \circ g\| _S \ge \kappa \, d_S(f,g)\) and \(\| h_u \circ f\| _{S,\infty } \le R_H R_\Phi \) for \(f, g \in B_k\).

(Map-dependent finite-set interpolation criterion for linear heads.) Fix \(f_1, \dots , f_M \in B_k\) and a sample \(S = (x_i)_{i=1}^n\), and let \(\Phi : \mathcal X \to \mathcal H\). Assume that for each \(j\) the evaluation operator \(T_j : w \mapsto (\langle w, \Phi (f_j(x_i))\rangle )_{i \in [n]}\) admits a right inverse of norm \(\le \Lambda _j\): for every \(c \in \mathbb R^n\) there is \(w \in \mathcal H\) with \(\| w\| \le \Lambda _j \| c\| _2\) and \(\langle w, \Phi (f_j(x_i))\rangle = c_i\) for all \(i\). Then for every family of code vectors \(u^{(1)}, \dots , u^{(M)} \in \mathbb R^n\) with \(\Lambda _j \| u^{(j)}\| _2 \le R_H\) there are output layers \(h_j \in H_{R_H}(\Phi )\) with \(h_j(f_j(x_i)) = u^{(j)}_i\). Consequently, if \(\bigl(\frac1n \sum _i |u^{(j)}_i - u^{(\ell )}_i|^2\bigr)^{1/2} \ge \rho \) for \(j \ne \ell \) then \(\| h_j \circ f_j - h_\ell \circ f_\ell \| _S \ge \rho \) for \(j \ne \ell \), and if \(\max _{j,i} |u^{(j)}_i| \le R_{\mathrm{out}}\) (with \(R_{\mathrm{out}} \ge 0\)) then \(\| h_j \circ f_j\| _{S,\infty } \le R_{\mathrm{out}}\).

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

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

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

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

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

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

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

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

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

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

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

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

If \(G \subseteq \mathbb R^{\mathcal X}\) is nonempty with finite uniform covering numbers \(N^{\mathrm{ext}}(G, \| \cdot \| _\infty , r) {\lt} \infty \) for all \(r {\gt} 0\), then \(G\) is totally bounded for the empirical pseudometric \(\| \cdot \| _S\) (FoML’s ‘EmpiricalFunctionSpace‘), \(n \ge 1\).

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

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

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

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

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.

Deterministic entropy decomposition (FoML form). Under Assumptions ass:ent-readout and ass:ent-transition with \(L_H {\gt} 0\), for every sample \(S\) of size \(n \ge 1\) and every \(0 {\lt} \varepsilon {\lt} B_H/2\),

where \(\mathcal E_H(u) = \sqrt{\log N^{\mathrm{ext}}(H, \| \cdot \| _\infty , u)}\) and \(\mathcal E_F(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_\infty , v)}\) (external covering numbers by closed balls). Proof: FoML’s Dudley integral for the class \(H \circ F\) with the empirical pseudometric \(\| \cdot \| _S\) (dudley_entropy_integral’), whose internal open-ball covering number at scale \(x\) is at most \(N^{\mathrm{ext}}(H \circ F, \| \cdot \| _\infty , y/2)\) for every \(y {\lt} x\) (lem:foml-covering-le-external-unifFun, losing a factor \(2\) in the radius when passing from external to internal covers), followed by the composition covering lemma lem:ent-composition-entropy at scale \(y/2\) and the limit \(y \uparrow x\) almost everywhere (lem:entropy-integrand-ae). Compared with the paper’s statement (quoted in thm:rad.decomp.ent.ent), the scales \(x/2\), \(x/(2L_H)\) are replaced by \(x/4\), \(x/(4L_H)\) (the paper implicitly uses covers with centres in the class, while the assumptions here are stated with external covering numbers), the integration range is \([\varepsilon , B_H/2]\) instead of \([0, 2B_H]\), and there is the additive term \(4\varepsilon \) from FoML’s Dudley bound.

Deterministic entropy decomposition. The paper states: under Assumptions ass:ent-readout and ass:ent-transition, for every sample \(S = (x_1,\dots ,x_n)\) with \(n \ge 1\),

The formalized statement is: under Assumptions ass:ent-readout and ass:ent-transition with \(L_H {\gt} 0\) and \(B_H {\gt} 0\), if the entropy integrand \(x \mapsto \mathcal E_H(x/4) + \mathcal E_F(x/(4L_H))\) is integrable on \([0, B_H/2]\), then for every sample \(S\) of size \(n \ge 1\),

where \(\mathcal E_H(u) = \sqrt{\log N^{\mathrm{ext}}(H, \| \cdot \| _\infty , u)}\) and \(\mathcal E_F(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_\infty , v)}\) are the root entropies for the external covering numbers by closed balls of the assumptions.

Deviations from the paper. (i) We assume in addition that the entropy integrand is integrable on \([0, B_H/2]\); the paper’s bound is trivially true with right-hand side \(+\infty \) otherwise (e.g. Lipschitz classes on a two-dimensional domain), whereas Lean’s Bochner integral of a non-integrable function is \(0\), so the statement without this hypothesis is false as transcribed. (ii) FoML’s Dudley integral (dudley_entropy_integral’) uses internal open-ball covers, and converting the external closed-ball covering numbers of the assumptions costs a factor \(2\) in the radius (lem:foml-covering-le-external-unifFun), so the scales are \(x/4\) and \(x/(4L_H)\) on \([0, B_H/2]\) instead of \(\varepsilon /2\), \(\varepsilon /(2L_H)\) on \([0, 2B_H]\). Up to these constant rescalings the statement is the paper’s.

Proof: let \(\varepsilon \to 0\) in thm:rad.decomp.ent.ent-foml, using the integrability hypothesis to compare the integrals over \([\varepsilon , B_H/2]\) and \([0, B_H/2]\).

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

If \(G \subseteq \mathbb R^{\mathcal X}\) has finite empirical covering numbers \(N^{\mathrm{ext}}(G, \| \cdot \| _S, r) {\lt} \infty \) for all \(r {\gt} 0\), then \(G\) is totally bounded for \(\| \cdot \| _S\) (FoML’s ‘EmpiricalFunctionSpace‘).

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

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.

Deterministic entropy decomposition on the sample (FoML form). Under Assumptions ass:ent-readout-sample and ass:ent-transition-sample with \(L_H {\gt} 0\), for every sample \(S\) of size \(n \ge 1\) and every \(0 {\lt} \varepsilon {\lt} B_H/2\),

where \(\mathcal E_{H,S}(u) = \sqrt{\log N_{S,F}(H, u)}\) and \(\mathcal E_{F,S}(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_S, v)}\). Proof: FoML’s Dudley integral for \(H \circ F\) with the pseudometric \(\| \cdot \| _S\) (dudley_entropy_integral’); its internal open-ball covering number at scale \(x\) is at most \(N^{\mathrm{ext}}(H \circ F, \| \cdot \| _S, y/2)\) for every \(y {\lt} x\) (lem:foml-covering-le-external-empFun), then the composition covering lemma on the sample lem:ent-composition-entropy-sample at scale \(y/2\) and the limit \(y \uparrow x\) almost everywhere (lem:entropy-integrand-ae-sample).

Deterministic entropy decomposition on the sample. Let \(S\) be a sample of size \(n \ge 1\), and suppose ass:ent-readout-sample and ass:ent-transition-sample hold with \(L_H {\gt} 0\), \(B_H {\gt} 0\). If the entropy integrand \(x \mapsto \mathcal E_{H,S}(x/4) + \mathcal E_{F,S}(x/(8L_H))\) is integrable on \([0, B_H/2]\), then

where \(\mathcal E_{H,S}(u) = \sqrt{\log N_{S,F}(H, u)}\) with \(N_{S,F}(H, u) = \sup _{f \in F} N^{\mathrm{ext}}(H, \| \cdot \| _{f \circ S}, u)\), and \(\mathcal E_{F,S}(v) = \sqrt{\log N^{\mathrm{ext}}(F, d_S, v)}\).

Comparison with the paper (thm:rad.decomp.ent.ent, Appendix D). The paper assumes \(H\) uniformly \(L_H\)-Lipschitz and bounded on \(\mathcal X\) and covered in the sup norm, and \(F\) covered in \(d_\infty \); its proof passes from \(\| \cdot \| _S\) to \(\| \cdot \| _\infty \) at the very first step. Here (W8 of the plan) every hypothesis is on the sample only: \(H\) is bounded and \(L_H\)-Lipschitz on the reachable points \(\mathcal R_S(F) = \{ f(x_i)\} \), \(F\) is covered in \(d_S\), and \(H\) is covered in the empirical metrics \(\| \cdot \| _{f \circ S}\) of the pushed-forward samples, uniformly in \(f \in F\) (this is the honest sample analogue of the sup norm cover: in the composition estimate the output layer is evaluated at \(f_b(x_i)\), not at \(x_i\), so a cover of \(H\) for \(\| \cdot \| _S\) alone would not suffice). The sup-norm assumptions imply the sample assumptions for every \(S\) (cor:rad.decomp.ent.ent-of-sample). The scales are \(x/4\), \(x/(8L_H)\) on \([0, B_H/2]\) in place of the paper’s \(\varepsilon /2\), \(\varepsilon /(2L_H)\) on \([0, 2B_H]\): one factor \(2\) comes from FoML’s internal open-ball covers (as in thm:rad.decomp.ent.ent) and, for \(F\) only, a second factor \(2\) from the fact that the cover of \(F\) must have its centres in \(F\) (so that the pushed-forward samples \(f_b \circ S\) are admissible), see lem:ent-composition-covering-sample. As in the sup-norm theorem, integrability of the integrand is an additional hypothesis.

Proof: let \(\varepsilon \to 0\) in thm:rad.decomp.ent.ent-sample-foml.

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

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

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 \(a \le b {\lt} \infty \) in \(\mathbb N \cup \{ \infty \} \) then \(\sqrt{\log a} \le \sqrt{\log b}\) (with \(\log 0 = 0\)).

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.