For the empirical feature, \(F_\rho (i)=F_\rho (x_i)\): the realization is the vector \(F_\rho |_x=(F_\rho (x_i))_i\in {\mathbb R}^N\).

\(L_N(\rho )=\frac1{2N}\sum _i(F_\rho (x_i)-y_i)^2 =\tfrac 12\| F_\rho |_x-y\| _N^2\) is the population risk of the empirical feature for the uniform measure on \(\{ 1,\dots ,N\} \) and the target \(y\).

\({\mathcal F}_N(\rho )=L_N(\rho )+\beta \operatorname {KL}(\rho \| \mu _U)\) is the free energy of the empirical feature for the uniform measure on \(\{ 1,\dots ,N\} \) and the target \(y\).

For \(r\in {\mathbb R}^N\) the analysis map of the empirical feature is \((S^*r)(z)=\frac1N\sum _i\varphi _z(x_i)r_i=(S_N^*r)(z)\).

For \(\nu \in {\mathcal P}(Z)\) and \(h\in {\mathbb R}^N\) the kernel operator of the empirical feature is \(K_{N,\nu }\): \((K_\nu h)_i=\int \varphi _z(x_i)\langle \Phi _z,h\rangle _N\, \nu (\, \mathrm dz)\).

For \(\lambda {\gt}0\) and \(\nu \in {\mathcal P}(Z)\), \(K_{N,\nu }+\lambda \) is injective (hence bijective) on \({\mathbb R}^N\), since \(K_{N,\nu }\) is positive semidefinite for \(\langle \cdot ,\cdot \rangle _N\).

Let \(s\) be measurable with \(|s|\le C\), \(\rho _s=\hat\mu _{W_s}\) as in Lemma 218, \(B_C:=\frac C\lambda +\sqrt{\frac{2\beta }{\pi \lambda }}\) and \(T\ge C/\lambda \). Then \(\int _{\{ |a|{\gt}T\} }|a|\, \mathrm d\rho _s\le B_C\exp \bigl(-\frac\lambda {2\beta }(T-\frac C\lambda )^2\bigr)\). (Conditionally on \(z\), \(a\sim {\mathcal N}(-s(z)/\lambda ,\beta /\lambda )\) with \(|s(z)/\lambda |\le C/\lambda \); apply Lemma 908 with \(m_0=C/\lambda \), \(v=\beta /\lambda \) and integrate over \(\nu _{\rho _s}\).)

The minimizer \(\rho _N^*\) of \({\mathcal F}_N\) on \({\mathcal D}\) is the minimizer of the free energy of the empirical feature \((z,i)\mapsto \varphi _z(x_i)\) for the uniform measure on \(\{ 1,\dots ,N\} \) and the target \(y\in {\mathbb R}^N=L^2(\text{uniform})\); all of Lemma ?? and Theorem ?? apply to it.

With \(r_N^*:=F_{\rho _N^*}|_x-y\) and \(g_N:=S_N^*r_N^*\), \(\rho _N^*=\hat\mu _{W_N^*}\) relative to \(\mu _U\) with \(W_N^*(\theta )=a\, g_N(z)\), i.e. \(\rho _N^*(\, \mathrm d\theta )\propto e^{-a g_N(z)/\beta }\mu _U(\, \mathrm d\theta )\).

Let \(r_N^*:=F_{\rho _N^*}|_x-y\in {\mathbb R}^N\), \(g_N:=S_N^*r_N^*\) and \(\nu _N^*:=\nu _{\rho _N^*}\). Then \(\rho _N^*(\, \mathrm da\, \mathrm dz) =\nu _N^*(\, \mathrm dz)\, {\mathcal N}\bigl(-g_N(z)/\lambda ,\beta /\lambda \bigr)(\, \mathrm da)\).

\(\nu _N^*(\, \mathrm dz) \propto \exp \bigl(\frac{g_N(z)^2}{2\lambda \beta }\bigr)\nu _0(\, \mathrm dz)\) (with \(\nu _0\propto e^{-V/\beta }\, \mathrm dz\) this is \(\nu _N^*(\, \mathrm dz) \propto \exp \bigl(\frac{g_N(z)^2}{2\lambda \beta }-\frac{V(z)}\beta \bigr)\, \mathrm dz\)).

\(m_{\rho _N^*}(z)=-g_N(z)/\lambda \) for \(\nu _N^*\)-a.e. \(z\).

With \(K:=K_{N,\nu _N^*}\),

and \(K+\lambda \) is injective on \({\mathbb R}^N\), so that \(r_N^*=-\lambda (K+\lambda )^{-1}y\) and \(F_{\rho _N^*}|_x=K(K+\lambda )^{-1}y\).

If \(|y_i|\le {Y_{\max }}\) for all \(i\), then deterministically \(\| r_N^*\| _N\le \| y\| _N\le {Y_{\max }}\), \(\sup _z|g_N(z)|\le {Y_{\max }}\) and \(|m_{\rho _N^*}(z)|\le {Y_{\max }}/\lambda \) for \(\nu _N^*\)-a.e. \(z\).

If \(|y_i|\le {Y_{\max }}\) for all \(i\), then deterministically \(\int |a|\, \mathrm d\rho _N^*\le B:=\frac{{Y_{\max }}}\lambda +\sqrt{\frac{2\beta }{\pi \lambda }}\) and \(\int a^2\, \mathrm d\rho _N^*\le \frac{{Y_{\max }}^2}{\lambda ^2}+\frac\beta \lambda \).

If \(|y_i|\le {Y_{\max }}\) for all \(i\) and \(T\ge {Y_{\max }}/\lambda \), then deterministically \(\int _{\{ |a|{\gt}T\} }|a|\, \mathrm d\rho _N^* \le B\exp \bigl(-\frac\lambda {2\beta }(T-\frac{{Y_{\max }}}\lambda )^2\bigr)\), \(B=\frac{{Y_{\max }}}\lambda +\sqrt{\frac{2\beta }{\pi \lambda }}\).

If \(\| f\| _{L^2(P_X)}\le {Y_{\max }}\) then, with \(g^*:=S^*r^*\) as in Theorem ??, \(\| r^*\| _{L^2(P_X)}\le \| f\| _{L^2(P_X)}\le {Y_{\max }}\), \(\sup _z|g^*(z)|\le {Y_{\max }}\) and \(|m_{\rho ^*}(z)|\le {Y_{\max }}/\lambda \) for \(\nu ^*\)-a.e. \(z\).

If \(\| f\| _{L^2(P_X)}\le {Y_{\max }}\) then \(\int |a|\, \mathrm d\rho ^*\le B=\frac{{Y_{\max }}}\lambda +\sqrt{\frac{2\beta }{\pi \lambda }}\) and \(\int a^2\, \mathrm d\rho ^*\le \frac{{Y_{\max }}^2}{\lambda ^2}+\frac\beta \lambda \).

If \(\| f\| _{L^2(P_X)}\le {Y_{\max }}\) and \(T\ge {Y_{\max }}/\lambda \), then \(\int _{\{ |a|{\gt}T\} }|a|\, \mathrm d\rho ^* \le B\exp \bigl(-\frac\lambda {2\beta }(T-\frac{{Y_{\max }}}\lambda )^2\bigr)\).

Let \(f\) be a regression function of \(Q\) with \(|f|\le C\), \(|Y|\le {Y_{\max }}\) a.s., and \(\rho \) with \(\int |a|\, \mathrm d\rho {\lt}\infty \). Then \(\tilde L(\rho )=L(\rho )+\tfrac 12\, {\mathbb E}(Y-f(X))^2=L(\rho )+\tfrac 12\, {\mathbb E}\, \mathrm{Var}(Y\mid X)\), since \({\mathbb E}[(F_\rho (X)-f(X))(f(X)-Y)]=0\) by the tower property.

Under the hypotheses of Lemma 288, for \(\rho ,\rho '\) with integrable amplitude, \(\tilde L(\rho )-\tilde L(\rho ')=L(\rho )-L(\rho ')\).

Let \(f\) be a regression function of \(Q\) with \(|f|\le C\), \(|Y|\le {Y_{\max }}\) a.s., \(P_X\) the first marginal of \(Q\), and \(\rho ^*\) the minimizer of \({\mathcal F}\) on \({\mathcal D}\) (for the target \(f\in L^2(P_X)\)). Then for every \(\rho \in {\mathcal D}\), \(\operatorname {KL}(\rho \| \rho ^*){\lt}\infty \) and

(Lemma 212 and Lemma 288: \(\tilde{{\mathcal F}}-{\mathcal F}\) is the constant \(\tfrac 12{\mathbb E}(Y-f(X))^2\).)

Let \(\rho _N^*\) be the minimizer of \({\mathcal F}_N\) on \({\mathcal D}\) for the sample \((x_i,y_i)_{i=1}^N\). Then for every \(\rho \in {\mathcal D}\), \(\operatorname {KL}(\rho \| \rho _N^*){\lt}\infty \) and

(Lemma 212 for the empirical feature, through the dictionary of Lemma 61.)

For a sample \(\omega =(x_i,y_i)_{i=1}^N\) and the minimizer \(\rho _N^*\) of \({\mathcal F}_N\) on \({\mathcal D}\), every \(\rho \in {\mathcal D}\) satisfies \({\mathcal F}_N(\rho )-{\mathcal F}_N(\rho _N^*)=\tfrac 12\| F_\rho |_x-F_{\rho _N^*}|_x\| ^2_N +\beta \, \operatorname {KL}(\rho \| \rho _N^*)\).

For \(\rho \in {\mathcal P}_B\) and every \(x\in {\mathcal X}\), \(|F_\rho (x)|\le B\).

For \(|a|\le B\) and \(z\in Z\), \(\delta _{(a,z)}\in {\mathcal P}_B\).

Let \(B\ge 0\), \(x_1,\dots ,x_N\in {\mathcal X}\) and \(\sigma \in \{ \pm 1\} ^N\), and let \(\psi _\sigma (z):=\frac1N\sum _i\sigma _i\varphi _z(x_i)\). Then \(\sup _{\rho \in {\mathcal P}_B}\frac1N\sum _i\sigma _iF_\rho (x_i)=B\sup _{z\in Z}|\psi _\sigma (z)|\) (and the same with \(\bigl|\frac1N\sum _i\sigma _iF_\rho (x_i)\bigr|\) on the left).

Let \(B\ge 0\) and \(x_1,\dots ,x_N\in {\mathcal X}\). Then, in the one-sided convention of the paper, \({\widehat{\mathfrak R}}_N({\mathcal{H}}_B)=B\, {\widehat{\mathfrak R}}_N(\Phi )\) for \({\mathcal{H}}_B=\{ F_\rho :\rho \in {\mathcal P}_B\} \), where \({\widehat{\mathfrak R}}_N(\Phi )={\mathbb E}_\sigma \sup _z|\psi _\sigma (z)|\) is ‘featureRademacher‘.

Under the hypotheses of Lemma 296, also in the absolute convention \({\widehat{\mathfrak R}}_N({\mathcal{H}}_B)=B\, {\widehat{\mathfrak R}}_N(\Phi )\).

If for every \(z\in Z\) there is \(z'\in Z\) with \(\varphi _{z'}=-\varphi _z\) (for \(\tanh \), \(z'=-z\)), then \({\widehat{\mathfrak R}}_N(\Phi )\) coincides with the one-sided complexity \({\mathbb E}_\sigma \sup _z\frac1N\sum _i\sigma _i\varphi _z(x_i)\) of the paper.

\({\mathcal P}_B^0\) is countable.

Let \(Z\) be first countable, \(Z_0\subseteq Z\) dense, \(\varphi \) continuous in \(z\), \(Q\in {\mathcal P}({\mathcal X}\times {\mathbb R})\), \(B\ge 0\) and \(x_1,\dots ,x_N\in {\mathcal X}\). For every \(\rho \in {\mathcal P}_B\) and \(\varepsilon {\gt}0\) there is \(\rho '\in {\mathcal P}_B^0\) with \(\int |F_\rho -F_{\rho '}|\, \mathrm dQ\le \varepsilon \) and \(|F_\rho (x_k)-F_{\rho '}(x_k)|\le \varepsilon \) for all \(k\). The proof samples \(M\) particles from \(\rho \) reweighted by \(|a|\) (Monte Carlo, expected squared error \(\le B^2/M\)), then moves the atoms into \(Z_0\) and the amplitude into \({\mathbb Q}\).

Let \(Z\) be separable and first countable, \(\varphi \) continuous in \(z\), \(Q\in {\mathcal P}({\mathcal X}\times {\mathbb R})\) with \(|Y|\le {Y_{\max }}\) a.s., \(B\ge 0\), \({Y_{\max }}\ge 0\) and \(N\ge 1\). Then \({\mathbb E}\, G_\pm \le 2B(B+{Y_{\max }})\, {\mathfrak R}_N(\Phi )\).

Let \(Z\) be separable and first countable, \(\varphi \) continuous in \(z\), \(Q\in {\mathcal P}({\mathcal X}\times {\mathbb R})\) with \(|Y|\le {Y_{\max }}\) a.s., \(B{\gt}0\), \({Y_{\max }}\ge 0\) and \(N\ge 1\). Let \(G:=\sup _{\rho \in {\mathcal P}_B}|L_N(\rho )-\tilde L(\rho )|\). Then for every \(\delta \in (0,1)\), with probability at least \(1-\delta \) over the i.i.d. sample of size \(N\) from \(Q\),

The proof is symmetrization (one-sided), the contraction principle, the identity \({\widehat{\mathfrak R}}_N({\mathcal{H}}_B)=B{\widehat{\mathfrak R}}_N(\Phi )\), McDiarmid’s inequality for \(G_\pm \) with bounded differences \((B+{Y_{\max }})^2/(2N)\) and a union bound; the suprema over \({\mathcal P}_B\) are computed on the countable dense subclass \({\mathcal P}_B^0\).

Assume (A3) and an i.i.d. sample of size \(N\ge 1\) (only the \(x_i\) are used). For every \(\delta _2\in (0,1)\), with probability at least \(1-\delta _2\), \(H_N\le 2\, {\mathfrak R}_N(\Psi )+\sqrt{2\log (2/\delta _2)/N}\). (FoML’s bound has the sharper radius \(\sqrt{2\log (1/\delta _2)/N}\), obtained without a union bound.)

For \(|e|\le E_*\) and every sample \((x_i,y_i)_{i=1}^N\), \({\widehat{\mathfrak R}}_N(\{ \varphi _ze\} )\le E_*\, {\widehat{\mathfrak R}}_N(\Phi )\), by the contraction lemma with the \(E_*\)-Lipschitz maps \(t\mapsto e(x_i,y_i)t\).

Assume (A3), an i.i.d. sample of size \(N\ge 1\) and a measurable \(e\colon {\mathcal X}\times {\mathbb R}\to {\mathbb R}\) with \(|e|\le E_*\), \(E_*{\gt}0\) (in the paper \(e(x,y)=y-f(x)\)). For every \(\delta _1\in (0,1)\), with probability at least \(1-\delta _1\), \(G_N\le 2E_*\, {\mathfrak R}_N(\Phi )+E_*\sqrt{2\log (2/\delta _1)/N}\).

Under the hypotheses of Lemma 305, with \(e(x,y)=y-f(x)\) for a measurable \(f\) and \(|Y-f(X)|\le E_*\) almost surely, the same bound holds for \(G_N=\sup _z|(P_N-P)(\varphi _ze)|\).

For every \(m\), \(\mathrm{HC}(m,8,6)\) holds: for every \(N\), every \(x_1,\dots ,x_N\in {\mathbb R}^m\) and every \(0{\lt}{\varepsilon }\le 1/2\), \(\mathcal N({\varepsilon },\Phi ,L_2(P_N))\le (8/{\varepsilon })^{6(m+1)}\).

For every \(m\), \(N\) and every \(x_1,\dots ,x_N\in {\mathbb R}^m\), \({\widehat{\mathfrak R}}_N(\Phi )\le 18\sqrt{(m+1)\log (N+1)/N}\).

Assume (A3). For every \(N\) and every \(x_1,\dots ,x_N\), \({\widehat{\mathfrak R}}_N(\Psi )\le 26\sqrt{(m+1)\log (N+1)/N}\).

Assume \(\mathrm{HC}(m,A,c)\) for all \(m\), with \(2A\ge 1\), \(c\ge 1\). Then for every \(m\), \(N\) and \(x_1,\dots ,x_N\in {\mathbb R}^m\), \({\widehat{\mathfrak R}}_N(\Phi )\le \bigl(1+6\sqrt{\log (2A)}+12\sqrt2\bigr)\sqrt c\, \sqrt{(m+1)/N}\), i.e. Lemma 314(b) with \(C_{\mathrm P}=(1+6\sqrt{\log (2A)}+12\sqrt2)\sqrt c\).

Assume \(\mathrm{HC}(m,A,c)\) for all \(m\), with \(2A\ge 1\), \(c\ge 1\). Then for every \(m\), \(N\) and \(x_1,\dots ,x_N\in {\mathbb R}^m\), \({\widehat{\mathfrak R}}_N(\Psi )\le \bigl(1+6\sqrt{\log (4A)}+12\sqrt2\bigr)\sqrt{2c}\, \sqrt{(m+1)/N}\).

For every \(m\), \(N\) and \(x_1,\dots ,x_N\in {\mathbb R}^m\), \({\widehat{\mathfrak R}}_N(\Phi )\le \bigl(1+6\sqrt{\log 16}+12\sqrt2\bigr)\sqrt6\, \sqrt{(m+1)/N}\); numerically the constant is at most \(69\).

For every \(m\), \(N\) and \(x_1,\dots ,x_N\in {\mathbb R}^m\), \({\widehat{\mathfrak R}}_N(\Psi )\le \bigl(1+6\sqrt{\log 32}+12\sqrt2\bigr)\sqrt{12}\, \sqrt{(m+1)/N}\); numerically the constant is at most \(101\).

(a) The pseudo-dimension of the class \(\Phi =\{ \varphi _z:z\in Z\} \) of \(\tanh \) ridge functions \(x\mapsto \tanh (w^\top x-b)\), \((w,b)\in {\mathbb R}^m\times {\mathbb R}\), is at most \(m+1\). (b) There is an absolute constant \(C_{\mathrm P}\) such that for every \(N\) and every \(x_1,\dots ,x_N\), \({\widehat{\mathfrak R}}_N(\Phi )\le C_{\mathrm P}\sqrt{(m+1)/N}\), hence \({\mathfrak R}_N(\Phi )\le C_{\mathrm P}\sqrt{(m+1)/N}\). A crude evaluation through Haussler’s covering bound and Dudley’s entropy integral gives \(C_{\mathrm P}\le 43\).

Assume (A3). For every \(N\) and every \(x_1,\dots ,x_N\), \({\widehat{\mathfrak R}}_N(\Psi )\le C'_{\mathrm P}\sqrt{(m+1)/N}\) with \(C'_{\mathrm P}:=\min \{ 4C_{\mathrm P},63\} \).

Under Lemma 314, for every \(Q\in {\mathcal P}({\mathcal X}\times {\mathbb R})\), \({\mathfrak R}_N(\Phi )\le C_{\mathrm P}\sqrt{(m+1)/N}\).

Under Lemma 315, for every \(Q\in {\mathcal P}({\mathcal X}\times {\mathbb R})\), \({\mathfrak R}_N(\Psi )\le C'_{\mathrm P}\sqrt{(m+1)/N}\).

For every \(Q\in {\mathcal P}({\mathcal X}\times {\mathbb R})\), \({\mathfrak R}_N(\Phi )\le 18\sqrt{(m+1)\log (N+1)/N}\).

For every \(Q\in {\mathcal P}({\mathcal X}\times {\mathbb R})\), \({\mathfrak R}_N(\Psi )\le 26\sqrt{(m+1)\log (N+1)/N}\).

\(\rho ^*\in {\mathcal P}_B\) (Lemma ??(c)).

If \(|y_i|\le {Y_{\max }}\) for all \(i\) then \(\rho _N^*(\omega )\in {\mathcal P}_B\) (Lemma ??(c)).

Under the hypotheses of Lemma 302, for every \(\delta \in (0,1)\), \({\mathbb P}(E_\delta )\ge 1-\delta \).

On a sample with \(|y_i|\le {Y_{\max }}\), \(\tilde{{\mathcal F}}(\rho _N^*)-\tilde{{\mathcal F}}(\rho ^*) =[\tilde L(\rho _N^*)-L_N(\rho _N^*)]+[{\mathcal F}_N(\rho _N^*)-{\mathcal F}_N(\rho ^*)] +[L_N(\rho ^*)-\tilde L(\rho ^*)]\le G_++G_-\), since the middle term is \(\le 0\) by minimality of \(\rho _N^*\) and \(\rho _N^*,\rho ^*\in {\mathcal P}_B\).

On a sample with \(|y_i|\le {Y_{\max }}\), \({\mathcal F}_N(\rho ^*)-{\mathcal F}_N(\rho _N^*) =[L_N(\rho ^*)-\tilde L(\rho ^*)]+[\tilde{{\mathcal F}}(\rho ^*)-\tilde{{\mathcal F}}(\rho _N^*)] +[\tilde L(\rho _N^*)-L_N(\rho _N^*)]\le G_++G_-\), since the middle term is \(\le 0\) by minimality of \(\rho ^*\).

On the event \(E_\delta \) of Lemma 302,

On the event \(E_\delta \),

On the event \(E_\delta \), \(\beta \, \operatorname {KL}(\rho _N^*\| \rho ^*)\le \Delta _N(\delta )\) and \(\beta \, \operatorname {KL}(\rho ^*\| \rho _N^*)\le \Delta _N(\delta )\).

Assume the setting of Section ?? (\(|Y|\le {Y_{\max }}\), i.i.d. sample, \(\lambda ,\beta {\gt}0\), \(Z\) separable and first countable, \(\varphi \) continuous in \(z\)) and Lemma ?? for \(L\) and \(L_N\). Let \(B\) be as in 82 and \(\Delta _N(\delta )\) as in 83. For every \(\delta \in (0,1)\), with probability at least \(1-\delta \) over the sample, the following hold simultaneously:

If \({\mathfrak R}_N(\Phi )\le C_{\mathrm P}\sqrt{(m+1)/N}\) (Lemma 314) then \(\Delta _N(\delta )\le D(\delta )/\sqrt N\) with \(D(\delta )\) as in 84.

In the setting of Theorem 328, let \({\varepsilon }{\gt}0\), \(\delta \in (0,1)\), \({\mathfrak R}_N(\Phi )\le C_{\mathrm P}\sqrt{(m+1)/N}\) and \(N_0({\varepsilon },\delta )\) as in 85. If \(N\ge N_0({\varepsilon },\delta )\) then on \(E_\delta \) (probability at least \(1-\delta \)), \(\operatorname {KL}(\rho _N^*\| \rho ^*)\le {\varepsilon }\) and \(\operatorname {KL}(\rho ^*\| \rho _N^*)\le {\varepsilon }\).

On \(E_\delta \), \(\tilde{{\mathcal F}}(\rho _N^*)-\tilde{{\mathcal F}}(\rho ^*)\le \Delta _N(\delta )\) and \({\mathcal F}_N(\rho ^*)-{\mathcal F}_N(\rho _N^*)\le \Delta _N(\delta )\).

On \(E_\delta \), \(\| F_{\rho _N^*}-F_{\rho ^*}\| _{L^2(P_X)}\le \sqrt{2\Delta _N(\delta )}\) and \(\| F_{\rho _N^*}|_x-F_{\rho ^*}|_x\| _N\le \sqrt{2\Delta _N(\delta )}\).

On \(E_\delta \), \(|\tilde L(\rho _N^*)-\tilde L(\rho ^*)|=|L(\rho _N^*)-L(\rho ^*)| \le \Delta _N(\delta )+{Y_{\max }}\sqrt{2\Delta _N(\delta )}\).

\((S^*r^*)(z)={\mathbb E}[\varphi _z(X)(F_{\rho ^*}(X)-f(X))] ={\mathbb E}[\varphi _z(X)(F_{\rho ^*}(X)-Y)]\) by the tower property.

On \(E_{\delta /2}\) (in particular on \(E'_\delta \)), with \(\Delta _N:=\Delta _N(\delta /2)\), \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \sqrt{\Delta _N/(2\beta )}\) and \(\| \nu _N^*-\nu ^*\| _{\mathrm{TV}}\le \sqrt{\Delta _N/(2\beta )}\) (Pinsker’s inequality and ??; the total variation of the marginals is at most that of the joint laws).

On a sample with \(|y_i|\le {Y_{\max }}\), for every \(z\in Z\),

hence \(|g_N(z)-g^*(z)|\le \| F_{\rho _N^*}|_x-F_{\rho ^*}|_x\| _N+G_N(\omega )\).

On \(E'_\delta \), with \(\Delta _N:=\Delta _N(\delta /2)\) and \(\Delta '_N\) as in 86,

where \(R^N_{\lambda ,\nu _N^*}y=-g_N/\lambda =m_{\rho _N^*}\) (\(\nu _N^*\)-a.e.) and \(R_{\lambda ,\nu ^*}f=-g^*/\lambda =m_{\rho ^*}\) (\(\nu ^*\)-a.e.).

On \(E'_\delta \),

Under the hypotheses of Theorem 328, \({\mathbb P}(E'_\delta )\ge 1-\delta \): apply Theorem 328 with \(\delta /2\) and Lemma 305 with \(\delta /2\) to the class \(\{ \varphi _ze\} \), \(|\varphi _ze|\le B+{Y_{\max }}\), and take the intersection.

On \(E'_\delta \),

with \(\| \mu \| _{\mathrm{TV}}=\tfrac 12|\mu |(Z)\).

By Lemma 314, \(\Delta _N\le D(\delta /2)/\sqrt N\) and \(\Delta _N'\le D'(\delta )/\sqrt N\), so that on \(E'_\delta \), \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \sqrt{D(\delta /2)/(2\beta \sqrt N)}\) and \(\sup _z|(R^N_{\lambda ,\nu _N^*}y)(z)-(R_{\lambda ,\nu ^*}f)(z)| \le \frac1\lambda \bigl[\sqrt{2D(\delta /2)/\sqrt N}+D'(\delta )/\sqrt N\bigr]\): for fixed \((\lambda ,\beta ,\delta ,m,{Y_{\max }})\), (b) is \(O(N^{-1/4})\) and (a), (c), (d) are \(O(\beta ^{-1/2}N^{-1/4})\).

In the setting of Theorem 328 let \(\delta \in (0,1)\), \(\Delta _N:=\Delta _N(\delta /2)\) and \(\Delta '_N\) as in 86. With probability at least \(1-\delta \) the following hold simultaneously: (a) \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \sqrt{\Delta _N/(2\beta )}\) and \(\| \nu _N^*-\nu ^*\| _{\mathrm{TV}}\le \sqrt{\Delta _N/(2\beta )}\); (b) \(\sup _z|g_N(z)-g^*(z)|\le \sqrt{2\Delta _N}+\Delta '_N\), i.e. \(\sup _z|(R^N_{\lambda ,\nu _N^*}y)(z)-(R_{\lambda ,\nu ^*}f)(z)| \le \frac1\lambda [\sqrt{2\Delta _N}+\Delta '_N]\); (c) \(\sup _x|F_{\rho _N^*}(x)-F_{\rho ^*}(x)|\le \frac1\lambda [\sqrt{2\Delta _N}+\Delta '_N] +\frac{2{Y_{\max }}}\lambda \sqrt{\Delta _N/(2\beta )}\); (d) \(\| \Pi \rho _N^*-\Pi \rho ^*\| _{\mathrm{TV}}\le \frac1{2\lambda }[\sqrt{2\Delta _N}+\Delta '_N] +\frac{{Y_{\max }}}\lambda \sqrt{\Delta _N/(2\beta )}\).

For \(m_i\in L^1(\nu _i)\), \(m_1\nu _1-m_2\nu _2=\psi \, (\nu _1+\nu _2)\) with \(\psi \) the mixed density.

For \(g m_i\in L^1(\nu _i)\), \(\int m_1g\, \mathrm d\nu _1-\int m_2g\, \mathrm d\nu _2=\int \psi g\, \mathrm d(\nu _1+\nu _2)\).

For bounded measurable \(m_1,m_2\), \(|m_1\nu _1-m_2\nu _2|(\alpha )=\int |\psi |\, \mathrm d(\nu _1+\nu _2)\).

For bounded measurable \(m_1,m_2\) with \(|m_2|\le M\), \(\int |\psi |\, \mathrm d(\nu _1+\nu _2)\le \int |m_1-m_2|\, \mathrm d\nu _1+2M\| \nu _1-\nu _2\| _{\mathrm{TV}}\), from \(|w_1m_1-w_2m_2|\le w_1|m_1-m_2|+|w_1-w_2||m_2|\).

If \(\| f\| _{L^2(P_X)}\le {Y_{\max }}\) then \(\sup _z|m^*(z)|\le M_*={Y_{\max }}/\lambda \).

\(F_{\rho ^*}(x)=\int _Zm^*(z)\varphi _z(x)\, \nu ^*(\, \mathrm dz)\) for every \(x\).

If \(|Y|\le {Y_{\max }}\) a.s. and \(\| f\| \le {Y_{\max }}\), then \(|e|\le E_*=M_*+{Y_{\max }}\) a.s.

If \(|y_i|\le {Y_{\max }}\) for all \(i\) then \(\sup _z|m_N(z)|\le {Y_{\max }}/\lambda \).

\(F_{\rho _N^*}(x)=\int _Zm_N(z)\varphi _z(x)\, \nu _N^*(\, \mathrm dz)\) for every \(x\).

\(\Pi \rho _N^*=m_N\, \nu _N^*\).

\(h(x)=\int _Z\varphi _z(x)\, \Pi \varsigma (\, \mathrm dz) =\int _Z\psi (z)\varphi _z(x)\, \mu (\, \mathrm dz)\) for every \(x\), where \(\Pi \varsigma =m_N\nu _N^*-m^*\nu ^*=\psi \mu \).

\(D_\varsigma =|\Pi \varsigma |(Z)=\int _Z|\psi |\, \mathrm d\mu \).

Let \(\Psi =\{ \Psi _i:i\in I\} \) be a class of measurable functions on \({\mathcal X}\times {\mathbb R}\) bounded by one, \(\kappa \) a finite measure on \(I\), \(c\in L^1(\kappa )\) and \(e\in L^1(P)\). Then, with \(H(p):=\int _Ic(i)\Psi _i(p)\, \kappa (\, \mathrm di)\), \((P_N-P)[He]=\int _Ic(i)\, (P_N-P)(\Psi _ie)\, \kappa (\, \mathrm di)\) (Fubini, since \(\iint |c(i)\Psi _i(p)e(p)|\, \kappa (\, \mathrm di)P(\, \mathrm dp) \le \| c\| _{L^1(\kappa )}\| e\| _{L^1(P)}{\lt}\infty \)).

Under the hypotheses of Lemma 355, \(|(P_N-P)[He]|\le \| c\| _{L^1(\kappa )}\sup _{i\in I}|(P_N-P)(\Psi _ie)|\).

Under the assumptions of Theorem 328, for every realization of the sample, deterministically,

(Add the two quadratic expansions of Lemma ??; the entropy terms \(\beta \operatorname {KL}(\cdot \| \mu _U)\) cancel, and \(\ell _{F_{\rho _N^*}}-\ell _{F_{\rho ^*}}=he+\frac12h^2\).)

\(\tfrac 12\| h\| _N^2+\tfrac 12\| h\| ^2+\beta {\mathcal{K}}_N =-(P_N-P)[he]-\tfrac 12(P_N-P)[h^2]\), since \(\ell _{F_{\rho _N^*}}-\ell _{F_{\rho ^*}}=\frac12(h+e)^2-\frac12e^2=he+\frac12h^2\).

For each direction separately, \(\tfrac 12\| h\| _N^2+\beta \operatorname {KL}(\rho ^*\| \rho _N^*)\le -(P_N-P)[he+\tfrac 12h^2]\) and \(\tfrac 12\| h\| ^2+\beta \operatorname {KL}(\rho _N^*\| \rho ^*)\le -(P_N-P)[he+\tfrac 12h^2]\) (drop one of the two nonnegative expansions).

\((P_N-P)[he]=\int _Z[(P_N-P)(\varphi _ze)]\, \Pi \varsigma (\, \mathrm dz)\) and \(|(P_N-P)[he]|\le D_\varsigma G_N\).

\((P_N-P)[h^2]=\iint _{Z\times Z}[(P_N-P)(\varphi _z\varphi _{z'})]\, \Pi \varsigma (\, \mathrm dz)\Pi \varsigma (\, \mathrm dz')\) and \(|(P_N-P)[h^2]|\le D_\varsigma ^2H_N\).

Deterministically, \(\tfrac 12\| h\| _N^2+\tfrac 12\| h\| ^2+\beta {\mathcal{K}}_N \le D_\varsigma G_N+\tfrac 12D_\varsigma ^2H_N\).

\(g^*(z)=\langle \varphi _z,F_{\rho ^*}-f\rangle _{L^2(P_X)} ={\mathbb E}[\varphi _z(X)(F_{\rho ^*}(X)-Y)]=P(\varphi _ze)\), since \({\mathbb E}[(Y-f(X))\varphi _z(X)]=0\).

For every \(z\), \(\lambda (m_N-m^*)(z)=-P_N(\varphi _zh)-(P_N-P)(\varphi _ze)\).

\(\sup _z|m_N(z)-m^*(z)|\le \frac1\lambda \bigl[\| h\| _N+G_N\bigr]\), because \(|P_N(\varphi _zh)|\le \| \Phi _z\| _N\| h\| _N\le \| h\| _N\).

Under Theorem ??(c) and Lemma ??(a), if \(\sup _z|m^*(z)|\le M_1\) then, deterministically, \(D_\varsigma \le \frac1\lambda \bigl[\| h\| _N+G_N\bigr]+M_1\sqrt{{\mathcal{K}}_N}\) (Lemma 367 with \(M_*\) replaced by \(M_1\); the same proof).

Under Theorem ??(c), (d) and Lemma ??(a), deterministically,

(\(\Pi \rho _N^*-\Pi \rho ^*=(m_N-m^*)\nu _N^*+m^*(\nu _N^*-\nu ^*)\), subadditivity of the total variation, \(|\nu _N^*-\nu ^*|(Z)=2\| \nu _N^*-\nu ^*\| _{\mathrm{TV}}\le 2\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \sqrt{{\mathcal{K}}_N}\) by Lemma 852.)

Let \(u,u_P,v,D,G,H\ge 0\) and \(c\ge 1\) with \(c^2H\le \frac18\), \(\frac12u^2+\frac12u_P^2+v^2\le DG+\frac12D^2H\) and \(D\le c(u+v+G)\). Then \(u+v\le 9cG\), \(u_P\le 6cG\) and \(D\le 10c^2G\). (With \(s=u+v\): \(\frac14s^2\le \frac12u^2+v^2\), \(D^2H\le \frac18(s+G)^2\), hence \(s^2\le 8cGs+9cG^2\) and \(s\le 9cG\).)

Assume the setting of Theorem 370 and \(\sup _z|m^*(z)|\le M_1\); put \(c_1(M_1):=\max \{ 1,1/\lambda ,M_1/\sqrt\beta \} \). For any upper bounds \(\eta '\ge G_N\), \(\eta ''\ge H_N\) with \(c_1(M_1)^2\eta ''\le \frac18\): \(\| h\| _N+\sqrt{\beta {\mathcal{K}}_N}\le 9c_1(M_1)\eta '\), \(\| h\| \le 6c_1(M_1)\eta '\), \(D_\varsigma \le 10c_1(M_1)^2\eta '\), \({\mathcal{K}}_N\le \frac{81c_1(M_1)^2}\beta \eta '{}^2\) and \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \frac{9c_1(M_1)}{2\sqrt\beta }\eta '\) (the proof of Theorem 370 with Lemma 366).

Assume the setting of Theorem 328. Put \(c_1:=\max \{ 1,1/\lambda ,M_*/\sqrt\beta \} \) and \(N_B(\delta ):=\lceil 64c_1^4D''(\delta )^2\rceil \) (\(\Leftrightarrow c_1^2\eta _N''\le \frac18\)). Let \(\delta \in (0,1)\) and \(N\ge N_B(\delta )\). On the event \(\Omega _\delta \) the following hold simultaneously.

1. \(\| h\| _N+\sqrt{\beta {\mathcal{K}}_N}\le 9c_1\eta _N'\), \(\| h\| _{L^2(P_X)}\le 6c_1\eta _N'\), \(D_\varsigma \le 10c_1^2\eta _N'\).

2. \({\mathcal{K}}_N\le \frac{81c_1^2}\beta \eta _N'{}^2\) and \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \frac{9c_1}{2\sqrt\beta }\eta _N'\).

(In Lean the statement is deterministic: for any upper bounds \(\eta '\ge G_N\), \(\eta ''\ge H_N\) with \(c_1^2\eta ''\le \frac18\).)

Assume the setting of Theorem 369. For any upper bounds \(\eta '\ge G_N\), \(\eta ''\ge H_N\) with \(c_1(M_1)^2\eta ''\le \frac18\): \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}},\| \nu _N^*-\nu ^*\| _{\mathrm{TV}}\le \frac{9c_1(M_1)}{2\sqrt\beta }\eta '\), \(\sup _z|m_N-m^*|\le \frac1\lambda [\| h\| _N+\eta ']\le \frac{10c_1(M_1)}\lambda \eta '\), \(\sup _x|h|\le D_\varsigma \le 10c_1(M_1)^2\eta '\) and \(\| \Pi \rho _N^*-\Pi \rho ^*\| _{\mathrm{TV}}=\frac12D_\varsigma \le 5c_1(M_1)^2\eta '\).

Assume the setting of Theorem 370, \(\delta \in (0,1)\) and \(N\ge N_B(\delta )\). On the event \(\Omega _\delta \) the following hold simultaneously.

1. \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \frac{9c_1}{2\sqrt\beta }\eta _N'\) and \(\| \nu _N^*-\nu ^*\| _{\mathrm{TV}}\le \frac{9c_1}{2\sqrt\beta }\eta _N'\).

2. \(\sup _z|(R^N_{\lambda ,\nu _N^*}y)(z)-(R_{\lambda ,\nu ^*}f)(z)|=\sup _z|m_N(z)-m^*(z)| \le \frac1\lambda [\| h\| _N+\eta _N']\le \frac{10c_1}\lambda \eta _N'\).

3. \(\sup _x|F_{\rho _N^*}(x)-F_{\rho ^*}(x)|\le D_\varsigma \le 10c_1^2\eta _N'\), since \(|h(x)|=|\int \varphi _z(x)\, \mathrm d\Pi \varsigma |\le D_\varsigma \).

4. \(\| \Pi \rho _N^*-\Pi \rho ^*\| _{\mathrm{TV}}=\frac12D_\varsigma \le 5c_1^2\eta _N'\).

Fix \(\delta \in (0,1)\) and apply Lemma 305 with \(\delta _1=\delta /2\) and Lemma 303 with \(\delta _2=\delta /2\): with \(\eta _N'=2E_*{\mathfrak R}_N(\Phi )+E_*\sqrt{2\log (4/\delta )/N}\) and \(\eta _N''=2{\mathfrak R}_N(\Psi )+\sqrt{2\log (4/\delta )/N}\), \({\mathbb P}(\Omega _\delta )={\mathbb P}(\{ G_N\le \eta _N'\} \cap \{ H_N\le \eta _N''\} )\ge 1-\delta \).

If \(|e|\le E\) \(Q\)-a.s. for some \(E{\gt}0\), then with \(\eta _N'=2E{\mathfrak R}_N(\Phi )+E\sqrt{2\log (4/\delta )/N}\) and \(\eta _N''=2{\mathfrak R}_N(\Psi )+\sqrt{2\log (4/\delta )/N}\), \({\mathbb P}(\{ G_N\le \eta _N'\} \cap \{ H_N\le \eta _N''\} )\ge 1-\delta \) (Lemmas 305 and 303 at level \(\delta /2\) each, and a union bound).

If \(|Y|\le {Y_{\max }}\) a.s. and \(\sup _z|m^*(z)|\le M_1\), then \(|e|\le M_1+{Y_{\max }}\) a.s. (\(|F_{\rho ^*}|=|S_{\nu ^*}m^*|\le M_1\)).

If \(\sup _z|m^*(z)|\le M_1\), then with \(E_*:=M_1+{Y_{\max }}\) in \(\eta _N'\), \({\mathbb P}(\Omega _\delta )\ge 1-\delta \) (Lemma 374 with Lemma 375).

If \({\mathfrak R}_N(\Phi )\le C_{\mathrm P}\sqrt{(m+1)/N}\) then \(\eta _N'\le E_*D'(\delta )/\sqrt N\), \(D'(\delta )=2C_{\mathrm P}\sqrt{m+1}+\sqrt{2\log (4/\delta )}\).

If \({\mathfrak R}_N(\Psi )\le C'_{\mathrm P}\sqrt{(m+1)/N}\) then \(\eta _N''\le D''(\delta )/\sqrt N\), \(D''(\delta )=2C'_{\mathrm P}\sqrt{m+1}+\sqrt{2\log (4/\delta )}\).

For \(c\ge 0\) and \(D''\ge 0\), \(N\ge 64c^4D''{}^2\) implies \(c^2D''/\sqrt N\le \frac18\); this is the condition \(N\ge N_B(\delta )=\lceil 64c_1^4D''(\delta )^2\rceil \) of Theorem 370.

Assume the setting of Theorem 369, the complexity bounds \({\mathfrak R}_N(\Phi )\le C_{\mathrm P}\sqrt{(m+1)/N}\), \({\mathfrak R}_N(\Psi )\le C'_{\mathrm P}\sqrt{(m+1)/N}\) and \(N\ge 64c_1(M_1)^4D''(\delta )^2\). On the event \(\Omega _\delta \) (with \(E:=M_1+{Y_{\max }}\) in \(\eta '_N\)), with \(D'(\delta )=2C_{\mathrm P}\sqrt{m+1}+\sqrt{2\log (4/\delta )}\): \({\mathcal{K}}_N\le \frac{121c_1(M_1)^2E^2D'(\delta )^2}{\beta N}\), \(\| h\| _N,\| h\| \le \frac{11c_1(M_1)ED'(\delta )}{\sqrt N}\), \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \frac{11c_1(M_1)ED'(\delta )}{2\sqrt{\beta N}}\), \(\sup _z|m_N-m^*|\le \frac{12c_1(M_1)ED'(\delta )}{\lambda \sqrt N}\) and \(\sup _x|F_{\rho _N^*}-F_{\rho ^*}|\le \frac{12c_1(M_1)^2ED'(\delta )}{\sqrt N}\).

On \(\Omega _\delta \), for \(N\ge N_B(\delta )\) and under Lemmas 314 and 315: with \(D'(\delta )=2C_{\mathrm P}\sqrt{m+1}+\sqrt{2\log (4/\delta )}\), \({\mathcal{K}}_N\le \frac{121c_1^2E_*^2D'(\delta )^2}{\beta N}=O(1/N)\), \(\| h\| _N,\| h\| \le \frac{11c_1E_*D'(\delta )}{\sqrt N}\), \(\| \rho _N^*-\rho ^*\| _{\mathrm{TV}}\le \frac{11c_1E_*D'(\delta )}{2\sqrt{\beta N}}\), \(\sup _z|m_N-m^*|\le \frac{12c_1E_*D'(\delta )}{\lambda \sqrt N}\) and \(\sup _x|F_{\rho _N^*}-F_{\rho ^*}|\le \frac{12c_1^2E_*D'(\delta )}{\sqrt N}\), all of order \(N^{-1/2}\) with no logarithm.