Chapter 4: Oracle PAC-Bayes Bounds

Theorem 4.1.1 (Fubini's Theorem) If $\mathcal{X}_1$ and $\mathcal{X}_2$ are $\sigma$-finite measurable spaces and $f:\mathcal{X}_1\times\mathcal{X}_2$ is measurable and $$\int_{\mathcal{X}_1\times\mathcal{X}_2}\vert f(x_1,x_2)\vert d(x_1,x_2)<\infty,$$ then $$\int_{\mathcal{X}_1}\left(\int_{\mathcal{X}_2}f(x_1,x_2)dx_2\right)dx_1=\int_{\mathcal{X}_2}\left(\int_{\mathcal{X}_1}f(x_1,x_2)dx_2\right)dx_1=\int_{\mathcal{X}_1\times\mathcal{X}_2}f(x_1,x_2)d(x_1,x_2).$$

We proceed from Corollary 3.9 to deduce that $$\begin{align*}\mathbb{E}_{S\sim\mathcal{D}^m}\left(R\left(\hat{\rho}_{\lambda}\right)\right)&\leq\mathbb{E}_{S\sim\mathcal{D}^m}\left(\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\hat{R}(\rho)+\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)}{\lambda}\right)\right)\\&\leq\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\rho)+\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)}{\lambda}\right)\right)\\&=\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\rho)\right)+\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)}{\lambda}\right)\\&=\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\mathbb{E}_{\mathbf{w}\sim\rho}\left(\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\mathbf{w})\right)\right)\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)}{\lambda}\right)\end{align*}$$ where Fubini's theorem has been applied in the last inequality. Recalling that $\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\mathbf{w})\right)=R(\mathbf{w})$ completes the proof of the theorem. $\square$

Recall the proof of Theorem 3.4 and the subsequent application to the Gibbs posterior that yielded Corollary 3.6. $$\mathbb{P}_{S\sim\mathcal{D}^m}\left(R(\hat{\rho}_{\lambda})\leq\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\hat{R}(\rho)+\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)+\log\left(\frac{1}{\delta}\right)}{\lambda}\right)\right)\geq1-\delta.$$ In the proof we utilized the result of Theorem 2.1. The inequality of Theorem 2.1 can be reversed by replacing the $U_i$ by $-U_i$ in its proof. Applying the reverse inequality of Theorem 2.1 in the proof of Theorem 3.4 gives the updated corollary $$\mathbb{P}_{S\sim\mathcal{D}^m}\left(\hat{R}(\rho)\leq R(\rho)+\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)+\log\left(\frac{1}{\delta}\right)}{\lambda}\right)\geq1-\delta.$$ Which holds for all $\rho\in\mathcal{M}(\mathcal{W})$. Applying a union bound on Corollary 3.6 and the updated result above gives $$\mathbb{P}_{S\sim\mathcal{D}^m}\begin{pmatrix}R(\hat{\rho}_{\lambda})\leq\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\hat{R}(\rho)+\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)+\log\left(\frac{1}{\delta}\right)}{\lambda}\right),\\\hat{R}(\rho)\leq R(\rho)+\frac{\lambda C^2}{8m}+\frac{\mathrm{KL}(\rho,\pi)+\log\left(\frac{1}{\delta}\right)}{\lambda}\end{pmatrix}\geq1-2\delta,$$ which holds for all $\rho\in\mathcal{M}(\mathcal{W})$. Using the upper bound on $\hat{R}(\rho)$ from the second event on the first event gives $$\mathbb{P}_{S\sim\mathcal{D}^m}\left(R(\hat{\rho}_{\lambda})\leq\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\hat{R}(\rho)+\frac{\lambda C^2}{4m}+\frac{2\left(\mathrm{KL}(\rho,\pi)+\log\left(\frac{1}{\delta}\right)\right)}{\lambda}\right)\right)\geq1-2\delta.$$ We can simply replace the $\delta$ with $\frac{\delta}{2}$ to complete the proof. $\square$

Lemma 4.4.1 Let $g$ denote the Bernstein function defined by $$g(x)=\begin{cases}1&x=0\\\frac{e^x-1-x}{x^2}&x\neq0.\end{cases}$$ Let $U_1,\dots,U_n$ be $\mathrm{i.i.d}$ random variables such that $\mathbb{E}(U_i)$ is finite and $U_i-\mathbb{E}(U_i)\leq C$ almost surely for some $C\in\mathbb{R}$. Then, $$\mathbb{E}\left(\exp\left(t\sum_{i=1}^n\left(U_i-\mathbb{E}(U_i)\right)\right)\right)\leq\exp\left(g(Ct)nt^2\mathrm{Var}(U_i)\right).$$

Now fix $\mathbf{w}\in\mathcal{W}$ and apply Lemma 4.4.1 to $U_i=l_i(\mathbf{w}^*)-l_i(\mathbf{w})$ (where we inherit the notation of the proof of Theorem 2.1). Note that $\mathbb{E}(U_i)=R(\mathbf{w}^*)-R(\mathbf{w})$ and therefore, $$\mathbb{E}_{S\sim\mathcal{D}^m}\left(\exp\left(tm\left(R(\mathbf{w})-R(\mathbf{w}^*)-\hat{R}(\mathbf{w})+\hat{R}(\mathbf{w})\right)\right)\right)\leq\exp\left(g(Ct)mt^2\mathrm{Var}_{S\sim\mathcal{D}^m}(U_i)\right).$$ Observe that $$\begin{align*}\mathrm{Var}(U_i)&\leq\mathbb{E}_{S\sim\mathcal{D}^m}\left(U_i^2\right)\\&=\mathbb{E}_{S\sim\mathcal{D}^m}\left(l_i(\mathbf{w}^*)-l_i(\mathbf{w})\right)\\&\leq K(R(\mathbf{w})-R(\mathbf{w}^*)).\end{align*}$$ Therefore, with $\lambda=tn$ we get that $$\mathbb{E}_{S\sim\mathcal{D}^m}\left(\exp\left(\lambda\left(R(\mathbf{w})-R(\mathbf{w}^*)-\hat{R}(\mathbf{w})+\hat{R}(\mathbf{w}^*)\right)\right)\right)\leq\exp\left(g\left(\frac{\lambda C}{m}\right)\frac{\lambda^2}{m}K\left(R(\mathbf{w})-R(\mathbf{w}^*)\right)\right)$$ which upon rearrangement gives $$\mathbb{E}_{S\sim\mathcal{D}^m}\left(\exp\left(\lambda\left(1-Kg\left(\frac{\lambda C}{m}\right)\frac{\lambda}{m}\right)\left(R(\mathbf{w})-R(\mathbf{w}^*)\right)-\hat{R}(\mathbf{w})-\hat{R}(\mathbf{w}^*)\right)\right)\leq1.$$ Now integrate with respect to $\pi$ and apply Fubini's theorem along with Lemma 3.4.3 from the proof of Theorem 3.4 to get $$\mathbb{E}_{S\sim\mathcal{D}^m}\left(\exp\left(\lambda\sup_{\rho\in\mathcal{M}(\mathcal{W})}\left(\left(1-Kg\left(\frac{\lambda C}{m}\right)\frac{\lambda}{m}\right)\left(R(\rho)-R(\mathbf{w}^*)\right)-\hat{R}(\rho)-\hat{R}(\mathbf{w}^*)-\mathrm{KL}(\rho,\pi)\right)\right)\right)\leq1.$$ In particular, this holds for $\rho-\hat{\rho}_{\lambda}$, and we can apply Jensen's inequality and re-arrange to yield $$\left(1-Kg\left(\frac{\lambda C}{m}\right)\right)\left(\mathbb{E}_{S\sim\mathcal{D}^m}\left(R(\hat{\rho}_{\lambda})-R(\mathbf{w}^*)\right)\right)\leq\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\rho)-\hat{R}(\mathbf{w})+\frac{\mathrm{KL}(\hat{\rho}_{\lambda},\pi)}{\lambda}\right).$$ From now on $\lambda$ will be such that $1-Kg\left(\frac{\lambda C}{m}\right)\frac{\lambda}{m}>0$, thus $$\mathbb{E}_{S\sim\mathcal{D}^m}\left(R(\hat{\rho}_{\lambda})\right)-R(\mathbf{w}^*)\leq\frac{\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\hat{\rho}_{\lambda})-\hat{R}(\mathbf{w}^*)+\frac{\mathrm{KL}(\hat{\rho}_{\lambda},\pi)}{\lambda}\right)}{1-Kg\left(\frac{\lambda C}{m}\right)\frac{\lambda}{m}}.$$ As with $\lambda=\frac{m}{\max(2K,C)}$ it follows that $$Kg\left(\frac{\lambda C}{m}\right)\frac{\lambda}{m}\leq\frac{1}{2}$$ and so we have $$\mathbb{E}_{S\sim\mathcal{D}^m}\left(R(\hat{\rho}_{\lambda})\right)-R(\mathbf{w}^*)\leq 2\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\hat{\rho}_{\lambda})-\hat{R}(\mathbf{w}^*)+\frac{\mathrm{KL}(\hat{\rho}_{\lambda},\pi)}{\lambda}\right).$$ As $\hat{\rho}_{\lambda}$ minimizes the quantity on the right hand side in expectation we can re-write this as $$\begin{align*}\mathbb{E}_{S\sim\mathcal{D}^m}(R(\hat{\rho}_{\lambda}))&\leq2\mathbb{E}_{S\sim\mathcal{D}^m}\left(\inf_{\rho\in\mathcal{M}(\mathcal{W})}\left(\hat{R}(\mathbf{w})-\hat{R}(\mathbf{w}^*)+\frac{\max(2K,C)\mathrm{KL}(\rho,\pi)}{m}\right)\right)\\&\leq2\inf_{\rho\in\mathcal{M}(\mathcal{W})}\mathbb{E}_{S\sim\mathcal{D}^m}\left(\hat{R}(\mathbf{w})-\hat{R}(\mathbf{w}^*)+\frac{\max(2K,C)\mathrm{KL}(\rho,\pi)}{m}\right)\\&=2\inf_{\rho\in\mathcal{M}(\mathcal{W})}\mathbb{E}_{S\sim\mathcal{D}^m}\left(R(\mathbf{w})-R(\mathbf{w}^*)+\frac{\max(2K,C)\mathrm{KL}(\rho,\pi)}{m}\right),\end{align*}$$ which completes the proof.$\square$

For the proof we define the following notation, $$\mathrm{kl}_{\gamma}(q,p)=\gamma q-\log\left(1-p+pe^{\gamma}\right),$$ for $p,q\in[0,1]$ and $\gamma\in\mathbb{R}$. One can show that $$\mathrm{kl}(q,p)=\sup_{\gamma}\left(\mathrm{kl}_{\gamma}(q,p)\right).$$

Lemma 4.5.1 For $\lambda>\frac{1}{2}$, if $\mathrm{kl}_{-\frac{1}{\gamma}}(q,p)\leq c$ then $$p\leq\frac{1}{1-\frac{1}{2\lambda}}(q+\lambda c).$$

Lemma 4.5.2 Let $x_1,\dots,x_n$ be realizations of a random variable $X$ with range $[0,1]$ and mean $\mu$. Let $\hat{\mu}=\frac{1}{n}\sum_{i=1}^nx_i$. Then for any fixed $\gamma$ we have that $$\mathbb{E}\left(\exp\left(n\mathrm{kl}_{\gamma}(\hat{\mu},\mu)\right)\right)\leq1.$$

Lemma 4.5.3 For probability distributions defined on the sample space $\mathcal{X}$ and a measurable function $f$ we have that $$\mathbb{E}_{x\in Q}(f(x))\leq\mathrm{KL}(Q,P)+\log\left(\mathbb{E}_{x\in P}\left(\exp(f(x))\right)\right).$$

We can use similar reasoning to that given in the proof of Theorem 3.12 to conclude from Lemma 4.5.2 that $$\mathbb{E}_{S\sim\mathcal{D}^m}\left(\exp\left(m\mathrm{kl}_{\gamma}\left(\hat{R}(\mathbf{w}),R(\mathbf{w})\right)\right)\right)\leq1$$ for fixed $\mathbf{w}\in\mathcal{W}$. Now we can take expectations over $\pi$ on both sides an apply Fubini's theorem to deduce that $$\begin{align*}1&\geq\mathbb{E}_{\mathbf{w}\sim\pi}\left(\mathbb{E}_{S\sim\mathcal{D}^m}\left(\exp\left(m\mathrm{kl}_{\gamma}\left(\hat{R}(\mathbf{w}),R(\mathbf{w})\right)\right)\right)\right)\\&\geq\mathbb{E}_{S\sim\mathcal{D}^m}\left(\mathbb{E}_{\mathbf{w}\sim\pi}\left(\exp\left(m\mathrm{kl}_{\gamma}\left(\hat{R}(\mathbf{w}),R(\mathbf{w})\right)\right)\right)\right).\end{align*}$$ To which we can apply Markov's inequality to get that $$\mathbb{P}_{S\sim\mathcal{D}^m}\left(\mathbb{E}_{\mathbf{w}\sim\pi}\left(\exp\left(m\mathrm{kl}_{\gamma}\left(\hat{R}(\mathbf{w}),R(\mathbf{w})\right)\right)\right)\leq\frac{1}{\delta}\right)\geq1-\delta.$$ Letting $f(\mathbf{w})=m\mathrm{kl}_{\gamma}\left(\hat{R}(\mathbf{w}),R(\mathbf{w})\right)$ in Lemma 4.5.3 and using the above result we get that $$\mathbb{P}_{S\sim\mathcal{D}^m}\left(\mathbb{E}_{\mathbf{w}\sim\rho}\left(m\mathrm{kl}_{\gamma}\left(\hat{R}(\mathbf{w}),R(\mathbf{w})\right)\right)\leq\mathrm{KL}(\rho,\pi)+\log\left(\frac{1}{\delta}\right)\right)\geq1-\delta.$$ By the convexity of $\mathrm{kl}_{\gamma}$ we get that $$\mathbb{P}_{S\sim\mathcal{D}^m}\left(m\mathrm{kl}_{\gamma}\left(\hat{R}(\mathbf{w}),R(\mathbf{w})\right)\leq\mathrm{KL}(\rho,\pi)+\log\left(\frac{1}{\delta}\right)\right)\geq1-\delta.$$ Therefore, by re-arranging and applying Lemma 4.5.1 the proof of the theorem is complete. $\square$.

This is the result of the previous Theorem 4.5 with $\lambda=\frac{1}{2(1-\beta)}$ and $C=1$.