12 Material for FoML
General lemmas on Rademacher complexities that belong upstream in FoML (lean-rademacher, ToFoML/): the one-sided contraction principle for an arbitrary class (from FoML’s finite-class theorem), McDiarmid’s inequality in the bounded-difference form, and the one-sided symmetrization and tail bounds for separable classes over an arbitrary index type, which relax FoML’s countability (or topological separability) requirement.
Let \(F=\{ F_i:i\in \iota \} \) be a nonempty class of functions on \({\mathcal X}\) with \(|F_i(S_k)|\le M\) on the sample \(S_1,\dots ,S_N\), and let \(\psi _x\colon {\mathbb R}\to {\mathbb R}\) be \(L\)-Lipschitz for every \(x\) (\(L\ge 0\)). Then, in the one-sided convention, \({\widehat{\mathfrak R}}_N(\{ \psi \circ F_i\} )\le L\, {\widehat{\mathfrak R}}_N(F)\), where \((\psi \circ F_i)(x)=\psi _x(F_i(x))\). This extends FoML’s finite-class contraction principle (‘empiricalRademacherComplexity_without_abs_contraction_finite‘) to an arbitrary index set: for every sign vector \(\sigma \) pick a near-maximizer \(i_\sigma \) of \(\sum _k\sigma _k\psi _{S_k}(F_i(S_k))\); the finite subclass \(\{ F_{i_\sigma }\} _\sigma \) realizes the left-hand side up to \(\varepsilon \) and its right-hand side is dominated by that of \(F\).
Near-maximizers: for every ‘σ‘ an index ‘iσ‘ with ‘⨆ i, A σ i ≤ A σ (iσ) + ε‘.
FoML’s finite-class contraction on the finite subclass ‘H‘.
Let \(G\) be a measurable function of \(N\) i.i.d. samples \(\omega _1,\dots , \omega _N\sim \mu \) such that replacing any single \(\omega _k\) changes \(G\) by at most \(c{\gt}0\). Then for every \(\varepsilon \ge 0\), \({\mathbb P}\bigl(G-{\mathbb E}G\ge \varepsilon \bigr)\le \exp \bigl(-2\varepsilon ^2/(Nc^2)\bigr)\) and \({\mathbb P}\bigl(G-{\mathbb E}G\le -\varepsilon \bigr)\le \exp \bigl(-2\varepsilon ^2/(Nc^2)\bigr)\) (FoML’s ‘mcdiarmid_inequality_pos_iid_of_const‘ with \(t=1/(Nc^2)\)).
A class \(F=\{ f_i:i\in \iota \} \) of real functions on \({\mathcal X}\) is separable if there is a countable \(D\subseteq \iota \) such that every \(f_i\) is the pointwise limit of a sequence \((f_{u_n})_n\) with \(u_n\in D\). Countable classes are separable, and so are classes with \(\iota \) a separable first countable topological space and \(i\mapsto f_i(x)\) continuous for every \(x\).
Let \(F=\{ f_i\} \) be a class with a pointwise dense sequence \((f_{e_n})_n\) and let \(\Phi \colon \iota \to {\mathbb R}\) be such that \(\Phi (u_n)\to \Phi (i)\) whenever \(f_{u_n}\to f_i\) pointwise. Then \(\sup _{i\in \iota }\Phi (i)=\sup _n\Phi (e_n)\) (with the convention that both sides are \(0\) if \(\Phi \) is unbounded). In particular the empirical Rademacher complexities and the uniform deviations of a bounded separable class are those of the countable subclass \(\{ f_{e_n}\} \).
Let \(F=\{ f_i:i\in \iota \} \) be a nonempty separable class of measurable functions on \(\mathcal Z\) with \(|f_i|\le b\), let \(\mu \in {\mathcal P}(\mathcal Z)\), \(N\ge 1\), and let \(\omega _1,\dots ,\omega _N\sim \mu \) be i.i.d. Then, in the one-sided convention,
This is the one-sided form of FoML’s symmetrization (‘expectation_le_rademacher‘, from ‘symmetrization_equation‘) with the countability of the class relaxed to separability: all suprema are computed on a pointwise dense sequence.
Under the hypotheses of Lemma 802 with \(b{\gt}0\), for every \(\varepsilon \ge 0\),
and the same for \(\sup _i(\frac1N\sum _kf_i(\omega _k)-\mu (f_i))\). The one-sided deviation is measurable (as a supremum over the dense sequence) and has bounded differences \(2b/N\), so McDiarmid’s inequality (Lemma 799) applies.
Let \(F=\{ f_i:i\in \iota \} \) be a nonempty separable class of measurable functions on \({\mathcal X}\) with \(|f_i|\le b\), \(b{\gt}0\), let \(X\colon \Omega \to {\mathcal X}\) be measurable, \(\mu \in {\mathcal P}(\Omega )\) and \(\omega _1,\dots ,\omega _n\sim \mu \) i.i.d. Then for every \(\varepsilon \ge 0\),
This is FoML’s ‘uniform_deviation_tail_bound_separable_of_pos‘ with its topological hypotheses replaced by the separability of the class.
A class \(F=\{ F_i:i\in \iota \} \) of real functions on \({\mathcal X}\) pseudo-shatters the points \((x_1,t_1),\dots ,(x_n,t_n)\in {\mathcal X}\times {\mathbb R}\) if for every \(T\subseteq [n]\) there is \(i\) with \(t_k\le F_i(x_k)\iff k\in T\) for all \(k\).
The pseudo-dimension of \(F\) is at most \(d\), \(\operatorname {Pdim}(F)\le d\), if \(F\) pseudo-shatters no family of \(n{\gt}d\) points.
Let \(g\colon {\mathbb R}\to {\mathbb R}\) be such that for every \(t\in {\mathbb R}\) the level set \(\{ u:t\le g(u)\} \) is of the form \(\{ u:s\le u\} \), or \({\mathbb R}\), or \(\emptyset \) (e.g. \(g=\tanh \), with \(s=\operatorname {artanh}t\) for \(|t|{\lt}1\)). If \(\operatorname {Pdim}(F)\le d\) then \(\operatorname {Pdim}(g\circ F)\le d\), where \(g\circ F=\{ g\circ F_i:i\in \iota \} \).
If \((x_k,t_k)_{k\le n}\) are pseudo-shattered by \(g\circ F\), no level set \(\{ u:t_k\le g(u)\} \) is trivial (the patterns \(T=\emptyset \) and \(T=[n]\) would be unrealizable), so \(t_k\le g(u)\iff s_k\le u\) for some \(s_k\), and \((x_k,s_k)_{k\le n}\) are pseudo-shattered by \(F\); hence \(n\le d\).
The affine class on \(E\) is \(\mathcal A:=\{ x\mapsto \langle w,x\rangle -b:(w,b)\in E\times {\mathbb R}\} \).
The \(\tanh \) ridge class on \(E\) is \(\Phi :=\{ x\mapsto \tanh (\langle w,x\rangle -b):(w,b)\in E\times {\mathbb R}\} \).
\(\operatorname {Pdim}(\mathcal A)\le \dim E+1\).
The pseudo-dimension of the class \(\Phi =\{ x\mapsto \tanh (\langle w,x\rangle -b) :(w,b)\in E\times {\mathbb R}\} \) of \(\tanh \) ridge functions on a \(d\)-dimensional inner product space \(E\) is at most \(d+1\).
Let \(F\) be a class with \(|F_i(S_k)|\le 1\) on the sample \(S_1,\dots ,S_N\) and \(\operatorname {Pdim}(F)\le d\). For every \({\varepsilon }{\gt}0\) the \(L_2(P_N)\) covering number of \(F\) on the sample satisfies \(\mathcal N({\varepsilon },F,L_2(P_N))\le \bigl(N(\lfloor 2/{\varepsilon }\rfloor +1)+1\bigr)^d\); in particular \(\mathcal N({\varepsilon },F,L_2(P_N))\le (4N/{\varepsilon })^d\) for \(0{\lt}{\varepsilon }\le 1\), \(N\ge 1\).
Round the values to the grid \(-1+j{\varepsilon }\), \(0\le j\le M:=\lfloor 2/{\varepsilon }\rfloor \). Two functions with the same level sets \(A_i=\{ (k,j):-1+j{\varepsilon }\le F_i(S_k)\} \) differ by less than \({\varepsilon }\) in every coordinate, so one representative per realized level set is an \({\varepsilon }\)-cover. A set of pairs \((k,j)\) shattered by \(\{ A_i\} \) is a family of points \((S_k,-1+j{\varepsilon })\) pseudo-shattered by \(F\), so the VC dimension of \(\{ A_i\} \) is at most \(d\), and the Sauer–Shelah–Perles lemma gives \(|\{ A_i\} |\le \sum _{k\le d}\binom {N(M+1)}{k}\le (N(M+1)+1)^d\).
Let \(F\), \(G\) be classes with \(|F_i(S_k)|,|G_j(S_k)|\le 1\) on the sample. Then \(\mathcal N({\varepsilon },F\cdot G,L_2(P_N))\le \mathcal N({\varepsilon }/2,F,L_2(P_N))\, \mathcal N({\varepsilon }/2,G,L_2(P_N))\), where \(F\cdot G=\{ F_iG_j\} \).
\(|F_iG_j-F_{i'}G_{j'}|\le |F_i-F_{i'}|\, |G_j|+|F_{i'}|\, |G_j-G_{j'}| \le |F_i-F_{i'}|+|G_j-G_{j'}|\) pointwise, hence \(\| F_iG_j-F_{i'}G_{j'}\| _{L_2(P_N)}\le \| F_i-F_{i'}\| _{L_2(P_N)}+\| G_j-G_{j'}\| _{L_2(P_N)}\), and the products of the centers of \({\varepsilon }/2\)-covers form an \({\varepsilon }\)-cover.
Let \(F\) be a class with \(|F_i(S_k)|\le 1\) on the sample and suppose \(\mathcal N(x,F,L_2(P_N))\le (A/x)^d\) for \(0{\lt}x\le 1/2\), with \(d\ge 1\), \(A{\gt}0\). Then for every \(0{\lt}\alpha {\lt}1/2\), \({\widehat{\mathfrak R}}_N(F)\le 4\alpha +\frac6{\sqrt N}\sqrt{d\log (2A/\alpha )}\) (absolute convention).
Dudley’s entropy integral in FoML’s form, \({\widehat{\mathfrak R}}_N(F)\le 4\alpha +\frac{12}{\sqrt N}\int _\alpha ^{1/2} \sqrt{\log \mathcal N(x,F\cup -F,L_2(P_N))}\, \mathrm dx\), with \(\mathcal N(x,F\cup -F)\le 2\mathcal N(x,F)\le 2(A/\alpha )^d\le (2A/\alpha )^d\) on \([\alpha ,1/2]\) and \(\int _\alpha ^{1/2}\, \mathrm dx\le 1/2\).
Let \(F\) be a class with \(|F_i(S_k)|\le 1\) on the sample \(S_1,\dots ,S_N\) (\(N\ge 1\)) and \(\operatorname {Pdim}(F)\le d\), \(d\ge 1\). Then \({\widehat{\mathfrak R}}_N(F)\le 18\sqrt{d\log (N+1)/N}\).
Let \(F\), \(G\) be classes with \(|F_i(S_k)|,|G_j(S_k)|\le 1\) on the sample (\(N\ge 1\)) and \(\operatorname {Pdim}(F),\operatorname {Pdim}(G)\le d\), \(d\ge 1\). Then \({\widehat{\mathfrak R}}_N(F\cdot G)\le 26\sqrt{d\log (N+1)/N}\).
Lemma 813 and Lemma 812 give \(\mathcal N(x,F\cdot G,L_2(P_N))\le (8N/x)^{2d}\); Lemma 814 with \(\alpha =1/(4\sqrt N)\) and \(16N/\alpha =64N\sqrt N\le (N+1)^8\) gives \({\widehat{\mathfrak R}}_N(F\cdot G)\le \bigl(1+6\sqrt{16d\log (N+1)}\bigr)/\sqrt N =\bigl(1+24\sqrt{d\log (N+1)}\bigr)/\sqrt N\).
Let \(F\) be a class with \(|F_i(S_k)|\le 1\) on the sample and suppose \(\mathcal N(x,F,L_2(P_N))\le (A/x)^d\) for \(0{\lt}x\le 1/2\), with \(d\ge 1\) and \(2A\ge 1\). Then for every \(0{\lt}\alpha {\lt}1/2\), \({\widehat{\mathfrak R}}_N(F)\le 4\alpha +\frac{12}{\sqrt N}\sqrt d\Bigl(\tfrac 12\sqrt{\log (2A)}+\sqrt2\Bigr)\) (absolute convention).
As in Lemma 814, but the integrand is bounded pointwise: \(\log \mathcal N(x,F\cup -F)\le d\log (2A/x)=d(\log 2A+\log (1/x))\), \(\sqrt{\log (1/x)}\le \sqrt{1/x}\) (from \(\log y\le y-1\)), and \(\int _\alpha ^{1/2}x^{-1/2}\, \mathrm dx=2\sqrt{1/2}-2\sqrt\alpha \le \sqrt2\).
Let \(F\) be a class with \(|F_i(S_k)|\le 1\) on the sample (\(N\ge 1\)) and suppose \(\mathcal N(x,F,L_2(P_N))\le (A/x)^d\) for \(0{\lt}x\le 1/2\), with \(d\ge 1\) and \(2A\ge 1\). Then \({\widehat{\mathfrak R}}_N(F)\le \bigl(1+6\sqrt{\log (2A)}+12\sqrt2\bigr)\sqrt{d/N}\).
Lemma 817 with \(\alpha =1/(4\sqrt N)\) and \(\sqrt d\ge 1\).
A finite subset \(t\) of a pseudometric space is \({\varepsilon }\)-separated if \(d(a,b)\ge {\varepsilon }\) for all distinct \(a,b\in t\).
Let \(A\) be a totally bounded subset of a pseudometric space and \({\varepsilon }{\gt}0\). If every \({\varepsilon }\)-separated finite subset of \(A\) has at most \(B\) elements, then \(\mathcal N({\varepsilon },A)\le B\).
Take an \({\varepsilon }\)-separated subset \(t\subseteq A\) of maximal cardinality \(n_0\le B\). If some \(q\in A\) had \(d(q,y)\ge {\varepsilon }\) for all \(y\in t\), then \(t\cup \{ q\} \) would be \({\varepsilon }\)-separated with \(n_0+1\) elements. Hence \(A\subseteq \bigcup _{y\in t}B(y,{\varepsilon })\) and \(\mathcal N({\varepsilon },A)\le |t|\le B\).
Let \(\alpha \) be a nonempty finite set, \(P\) a finite index set and \(B_q\subseteq \alpha \) with \(|B_q|\le (1-p)|\alpha |\) for \(q\in P\). If \(|P|(1-p)^n{\lt}1\), there is \(K\colon [n]\to \alpha \) such that for every \(q\in P\) some \(K_k\) lies outside \(B_q\).
Double counting: \(\sum _K|\{ q\in P:K([n])\subseteq B_q\} | =\sum _{q\in P}|B_q|^n\le |P|(1-p)^n|\alpha |^n{\lt}|\alpha |^n\), so some \(K\) has no such \(q\).
Let \(|f(S_k)|,|g(S_k)|\le 1\) for all \(k\) and \(\| f-g\| _{L_2(P_N)}\ge {\varepsilon }\), \(N\ge 1\). Then \(|\{ k:|f(S_k)-g(S_k)|{\lt}{\varepsilon }/2\} |\le (1-{\varepsilon }^2/8)N\).
\({\varepsilon }^2N\le \sum _k(f(S_k)-g(S_k))^2\le 4\, |\{ k:|f-g|\ge {\varepsilon }/2\} | +\tfrac {{\varepsilon }^2}4|\{ k:|f-g|{\lt}{\varepsilon }/2\} |\), so the good coordinates number at least \(\tfrac 3{16}{\varepsilon }^2N\ge {\varepsilon }^2N/8\).
For \(1\le d\le n\), \(\sum _{k\le d}\binom nk\le (en/d)^d\).
Let \(F\) be a class with \(|F_i(S_k)|\le 1\) on the sample \(S_1,\dots ,S_N\) and \(\operatorname {Pdim}(F)\le d\), \(d\ge 1\), and let \(0{\lt}{\varepsilon }\le 1\). Every \({\varepsilon }\)-separated finite subset of \(F\) in \(L_2(P_N)\) has at most \((8/{\varepsilon })^{6d}\) elements.
Let \(t\) be \({\varepsilon }\)-separated with \(m=|t|\ge 1\) (for \(N=0\) all distances vanish and \(m\le 1\)). Put \(p={\varepsilon }^2/8\), \(n=\lfloor 2\log m/p\rfloor +d+1\), \(M=\lfloor 4/{\varepsilon }\rfloor \). By Lemma 822 each pair of distinct elements of \(t\) is \({\varepsilon }/2\)-apart on all but at most \((1-p)N\) coordinates, and \(m^2(1-p)^n\le e^{2\log m-pn}{\lt}1\), so Lemma 821 gives \(K\colon [n]\to [N]\) with every pair \({\varepsilon }/2\)-apart at some \(S_{K_k}\). Two such functions have distinct level sets on the grid \(-1+j{\varepsilon }/2\), \(0\le j\le M\), over the \(n\) points \(S_{K_k}\); the level-set family has VC dimension at most \(d\), so \(m\le \sum _{k\le d}\binom {n(M+1)}k\le (en(M+1)/d)^d\) (Lemma 823). With \(r=m^{1/(2d)}\), \(\log m=2d\log r\le 2dr\), hence \(n\le 34dr/{\varepsilon }^2\), \(M+1\le 5/{\varepsilon }\) and \(m\le (170e/{\varepsilon }^3)^dr^d=(170e/{\varepsilon }^3)^d\sqrt m\); thus \(m\le (170e/{\varepsilon }^3)^{2d}\le (8/{\varepsilon })^{6d}\).
Let \(F\) be a class with \(|F_i(S_k)|\le 1\) on the sample \(S_1,\dots ,S_N\) and \(\operatorname {Pdim}(F)\le d\), \(d\ge 1\). Then for every \(0{\lt}{\varepsilon }\le 1\), \(\mathcal N({\varepsilon },F,L_2(P_N))\le (8/{\varepsilon })^{6d}\), with no dependence on \(N\) or on the sample (Haussler’s bound; the sharp form is \(e(d+1)(2e/{\varepsilon })^d\) in \(L_1(P_N)\)).