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

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

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

\(\varepsilon \mapsto \sqrt{\log N(A, \varepsilon ^+)}\) is a measurable function on \(\mathbb R\) (it is the composition of the antitone map \(\varepsilon \mapsto N(A,\varepsilon ^+)\) with measurable maps).

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

If \(\sqrt{\log N(A,\varepsilon )} \le g(\varepsilon )\) on \((0, D]\) for an interval-integrable \(g\) on \([0,D]\), then \(\varepsilon \mapsto \sqrt{\log N(A,\varepsilon )}\) is interval-integrable on \([0,D]\).

For \(0 {\lt} a \le D\) with \(N(A, a) {\lt} \infty \), \(\varepsilon \mapsto \sqrt{\log N(A,\varepsilon )}\) is interval-integrable on \([a, D]\) (it is antitone and bounded there).

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

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

(Saturation.) Let \(A_k\) be sets with diameters \(0 \le D_k \le \overline D\) and \(N(A_k, \varepsilon ) \le N_\infty (\varepsilon )\) for all \(k\) and \(\varepsilon \), with \(N_\infty (\varepsilon ) {\lt} \infty \) for \(\varepsilon {\gt} 0\) and \(\mathsf V_\infty := \int _0^{\overline D} \sqrt{\log N_\infty (\varepsilon )}\, d\varepsilon {\lt} \infty \) (the integrand is interval-integrable). Then \(\mathsf V(D_k, A_k) \le \mathsf V_\infty \) for all \(k\).

If \(N(A, \varepsilon ) \le C_0 (1 + k/\varepsilon )^{D}\) for \(\varepsilon {\gt} 0\), with \(C_0 \ge 1\), \(D \ge 0\), then for \(0 {\lt} \varepsilon \le \overline D\), \(\sqrt{\log N(A,\varepsilon )} \le \sqrt{\log C_0} + \sqrt{D}\sqrt{\log (1 + k/\overline D)} + \sqrt{D}\sqrt{\log (\overline D/\varepsilon )}\).

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

(Polynomial growth, bounded diameter.) If \(0 \le D_k \le \overline D\), \(\overline D {\gt} 0\), and \(N(A_k, \varepsilon ) \le C_0 (1 + k/\varepsilon )^{D}\) for all \(k \ge 1\) and \(\varepsilon {\gt} 0\) (with \(C_0 \ge 1\), \(D \ge 0\)), then for \(k \ge 1\)

(Polynomial growth, linearly growing diameter.) If \(0 \le D_k \le D_1 k\) with \(D_1 {\gt} 0\), and \(N(A_k, \varepsilon ) \le C_0 (1 + k/\varepsilon )^{D}\) for all \(k \ge 1\) and \(\varepsilon {\gt} 0\) (with \(C_0 \ge 1\), \(D \ge 0\)), then for \(k \ge 1\)

(Exponential growth, bounded diameter.) If \(0 \le D_k \le \overline D\) and \(\log N(A_k, \varepsilon ) \le \alpha k + \psi (\varepsilon )\) for all \(k\) and \(\varepsilon {\gt} 0\), with \(\Psi := \int _0^{\overline D} \sqrt{\psi (\varepsilon )}\, d\varepsilon {\lt} \infty \) (i.e. \(\sqrt\psi \) is interval-integrable on \([0,\overline D]\)), then \(\mathsf V(D_k, A_k) \le \overline D\sqrt{\alpha k} + \Psi = O(\sqrt k)\).

(Finite classes.) If \(|A_k| \le r^{k+1}\) and \(0 \le D_k \le \overline D\), then \(N(A_k, \varepsilon ) \le r^{k+1}\) at every scale and \(\mathsf V(D_k, A_k) \le \overline D\sqrt{(k+1)\log r}\).

Since \(d_S \le d_\infty \), the identity map \((\mathcal X^{\mathcal X}, d_\infty ) \to (\mathcal X^{\mathcal X}, d_S)\) is \(1\)-Lipschitz.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 \(\varepsilon \mapsto \sqrt{\log N(A,\varepsilon )}\) is interval-integrable on \([0, D]\).

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

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

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

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

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