%% This LaTeX-file was created by <jl> Tue Apr 23 13:54:31 2002
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[landscape,dvips]{slides}
\usepackage[T1]{fontenc}
\pagestyle{empty}
\usepackage{color}
\usepackage{graphics}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newcounter{slidetype}
\setcounter{slidetype}{0}
\newif\ifLyXsNoCenter
\LyXsNoCenterfalse
\newcommand{\noslidecentering}{
   \LyXsNoCentertrue%
}
\newcommand{\slidecentering}{
   \LyXsNoCenterfalse%
}
\newcommand{\lyxendslide}[1]{
   \ifLyXsNoCenter%
        \vfill%
   \fi%
   \ifcase \value{slidetype}%
        \or % no action for 0
        \end{slide} \or%
        \end{overlay} \or%
        \end{note}%
   \fi%
   \setcounter{slidetype}{0}
	\visible
}
\AtEndDocument{\lyxendslide{.}}
\newcommand{\lyxnewslide}[1]{
   \lyxendslide{.}
   \setcounter{slidetype}{1}
   \begin{slide}
}
\newcommand{\lyxnewoverlay}[1]{
   \lyxendslide{.}
   \setcounter{slidetype}{2}
   \begin{overlay}
}
\newcommand{\lyxinvisible}[1]{
   \invisible
}

\makeatother

\begin{document}


\lyxnewslide{sdf}

{\par\centering A primer for PAC-Bayes\par}

{\par\centering John Langford\par}


\lyxnewslide{afaf}

\begin{enumerate}
\item \textcolor{green}{Occam's Razor bound}
\item PAC-Bayes bound
\item Proof
\item Bits-Back
\end{enumerate}

\lyxnewslide{afaf}

{\par\centering The Model\par}

\( X \) = (arbitrary) input space

\( Y\in \{0,1\} \) = prediction space

Assume: Examples \( (X,Y) \) are drawn independently from distribution \( D \)


\lyxnewslide{aldd}

{\par\centering Terminology\par}

\begin{itemize}
\item Samples = \( S \)
\item Learning algorithm \( A:\, \, S\rightarrow h \)
\item True Error rate \( e_{D}(h)=\Pr _{D}(h(x)\neq y) \)
\item Empirical Error rate \( \hat{e}_{S}(h)=\Pr _{S}(h(x)\neq y) \)\vspace{0.3cm}

\end{itemize}

\lyxnewslide{faf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{thesis/training_set.eps}} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

{\par\centering ``Occam's Razor'' bound (BEHW87)\par}

Theorem:
\[
\forall P(h)\, \, \Pr _{S\sim D^{m}}\left( \exists h\in H:\, \, e_{D}(h)>\bar{e}(h,\hat{e}_{S}(h),P(h)\delta )\right) \leq \delta \]
where \( \bar{e}(h,\frac{k}{m},\delta )=\max \{p|\textrm{Bin}_{p,m}(\frac{k}{m})\geq \delta \} \)

Proof: by nonuniform bound


\lyxnewslide{afaf}

{\par\centering Another Representation\par}

{\par\centering \( \hat{e}(h_{1}) \)------\( e(h_{1}) \)\par}

{\par\centering \( \hat{e}(h_{2}) \)------\( e(h_{2}) \)\par}

{\par\centering \( \hat{e}(h_{3}) \)---------\( e(h_{3}) \)\par}

{\par\centering \( \hat{e}(h_{4}) \)---------\( e(h_{4}) \)\par}

{\par\centering \( \hat{e}(h_{5}) \)-----------\( e(h_{5}) \)\par}


\lyxnewslide{afaf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{thesis/thesis-paper/test_vs_micro.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{adf}

Corollary:
\[
\forall P(h)\,\,\,\Pr _{S\sim D^{m}}\left( \textrm{KL}(\hat{e}_{S}(h)||e_{D}(h))\geq \frac{\ln \frac{1}{P(h)}+\ln \frac{1}{\delta }}{m}\right) \leq \delta \]


Corollary:
\[
\forall P(h)\,\,\,\Pr _{S\sim D^{m}}\left( e_{D}(h)\geq \hat{e}_{S}(h)+\sqrt{\frac{\ln \frac{1}{P(h)}+\ln \frac{1}{\delta }}{2m}}\right) \leq \delta \]



\lyxnewslide{afaf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{thesis/thesis-paper/bound_plot.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{afaf}

\begin{enumerate}
\item \textcolor{red}{Occam's Razor bound}
\item \textcolor{green}{PAC-Bayes bound}
\item Proof
\item Bits-Back
\end{enumerate}

\lyxnewslide{afa}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{thesis/pac-bayes.eps}} \par}
\vspace{0.3cm}


\lyxnewslide{afa}

{\par\centering PAC-Bayes Terminology\par}

\begin{enumerate}
\item \( \hat{e}_{Q,S}=E_{h\sim Q}\hat{e}_{S}(h) \) = expected training error over
\( Q \).
\item \( e_{Q,D}=E_{h\sim Q}e_{D}(h) \) = expected true error over \( Q \).
\item \( \textrm{KL}(Q||P)=E_{h\sim Q}\ln \frac{Q(h)}{P(h)} \)
\item \( \textrm{KL}(\hat{e}_{Q,S}||e_{Q,D})=\hat{e}_{Q,S}\ln \frac{\hat{e}_{Q,S}}{e_{Q,D}}+(1-\hat{e}_{Q,S})\ln \frac{1-\hat{e}_{Q,S}}{1-e_{Q,D}} \)
\end{enumerate}

\lyxnewslide{afaf}

{\par\centering PAC-Bayes bound (McAllester99, me00, Seeger02)\par}

Theorem:
\[
\forall P(h)\, \, \Pr _{S\sim D^{m}}\left( \exists Q\sim h:\, \, \textrm{KL}(\hat{e}_{Q,S}||e_{Q,D})>\frac{\textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \leq \delta \]


Proof: later


\lyxnewslide{afa}

{\par\centering Stochastic Neural Network\par}

\begin{enumerate}
\item Pick a Neural Network
\item For every weight, \( w \)

\begin{enumerate}
\item Find sensitivity, \( s(w) \)
\end{enumerate}
\item Perturb weights by gaussian \( N\left( w,\frac{1}{s(w)}\right)  \)
\end{enumerate}

\lyxnewslide{afaf}

{\par\centering PAC-Bayes for SNN (Rich \& I, NIPS 2001)\par}

let \( n \) = number of weights

\begin{enumerate}
\item Pick Prior = \( N(0,\alpha )^{n} \) 

\begin{itemize}
\item actually, a mixture.
\end{itemize}
\item Pick Posterior = \( N\left( w,\frac{1}{s(w)}\right)  \)
\item Monte carlo estimate and bound \( \hat{e}_{Q,S} \)
\end{enumerate}

\lyxnewslide{afaf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{g.100.full.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{afaf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{g.100.partial.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{afaf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{g.5000.partial.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{afaf}

\begin{enumerate}
\item \textcolor{red}{Occam's Razor bound}
\item \textcolor{red}{PAC-Bayes bound}
\item \textcolor{green}{Proof}
\item Bits-Back
\end{enumerate}

\lyxnewslide{fafa}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \)


\lyxinvisible{}

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)

Proof: Let \( f(h)=m\textrm{KL}(\hat{e}(h)||e(h)) \) 

\( \Rightarrow mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))} \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( \textrm{KL}(E_{h\sim Q}\hat{e}(h)||E_{h\sim Q}e(h))\leq \frac{\textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta  \)
(jensen)


\lyxnewoverlay{df}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \)

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)


\lyxinvisible{}

Proof: Let \( f(h)=m\textrm{KL}(\hat{e}(h)||e(h)) \) 

\( \Rightarrow mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))} \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( \textrm{KL}(E_{h\sim Q}\hat{e}(h)||E_{h\sim Q}e(h))\leq \frac{\textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta  \)
(jensen)


\lyxnewoverlay{df}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \)

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)

Proof: Let \( f(h)=m\textrm{KL}(\hat{e}(h)||e(h)) \) 

\( \Rightarrow mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))} \) 


\lyxinvisible{}

\( \Rightarrow \Pr _{S\sim D^{m}}\left( mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( \textrm{KL}(E_{h\sim Q}\hat{e}(h)||E_{h\sim Q}e(h))\leq \frac{\textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta  \)
(jensen)


\lyxnewoverlay{df}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \)

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)

Proof: Let \( f(h)=m\textrm{KL}(\hat{e}(h)||e(h)) \) 

\( \Rightarrow mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))} \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }\right) \geq 1-\delta  \) 


\lyxinvisible{}

\( \Rightarrow \Pr _{S\sim D^{m}}\left( \textrm{KL}(E_{h\sim Q}\hat{e}(h)||E_{h\sim Q}e(h))\leq \frac{\textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta  \)
(jensen)


\lyxnewoverlay{df}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \)

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)

Proof: Let \( f(h)=m\textrm{KL}(\hat{e}(h)||e(h)) \) 

\( \Rightarrow mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))} \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( mE_{h\sim Q}\textrm{KL}(\hat{e}(h)||e(h))\leq \textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

\( \Rightarrow \Pr _{S\sim D^{m}}\left( \textrm{KL}(E_{h\sim Q}\hat{e}(h)||E_{h\sim Q}e(h))\leq \frac{\textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta  \)
(jensen)


\lyxnewslide{faf}


\lyxnewoverlay{afaf}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \) 


\lyxinvisible{}

Proof: \( \Pr _{\textrm{error}}(S)=p^{\#heads}(1-p)^{\#tails} \)

\( =p^{\hat{p}m}(1-p)^{(1-\hat{p})m} \)

\( =e^{\log p^{\hat{p}m}+\log (1-p)^{(1-\hat{p})m}} \)

\( =e^{-m(\hat{p}\log \frac{1}{p}-(1-\hat{p})\log \frac{1}{1-p})} \)

\( =e^{m(-(\hat{p}\log \frac{\hat{p}}{p}-(1-\hat{p})\log \frac{1-\hat{p}}{1-p})-(\hat{p}\log \frac{1}{\hat{p}}-(1-\hat{p})\log \frac{1}{1-\hat{p}}))} \)

\( =e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))} \)


\lyxnewoverlay{afaf}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

Proof: \( \Pr _{\textrm{error}}(S)=p^{\#heads}(1-p)^{\#tails} \)


\lyxinvisible{}

\( =p^{\hat{p}m}(1-p)^{(1-\hat{p})m} \)

\( =e^{\log p^{\hat{p}m}+\log (1-p)^{(1-\hat{p})m}} \)

\( =e^{-m(\hat{p}\log \frac{1}{p}-(1-\hat{p})\log \frac{1}{1-p})} \)

\( =e^{m(-(\hat{p}\log \frac{\hat{p}}{p}-(1-\hat{p})\log \frac{1-\hat{p}}{1-p})-(\hat{p}\log \frac{1}{\hat{p}}-(1-\hat{p})\log \frac{1}{1-\hat{p}}))} \)

\( =e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))} \)


\lyxnewoverlay{afaf}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

Proof: \( \Pr _{\textrm{error}}(S)=p^{\#heads}(1-p)^{\#tails} \)

\( =p^{\hat{p}m}(1-p)^{(1-\hat{p})m} \)


\lyxinvisible{}

\( =e^{\log p^{\hat{p}m}+\log (1-p)^{(1-\hat{p})m}} \)

\( =e^{-m(\hat{p}\log \frac{1}{p}-(1-\hat{p})\log \frac{1}{1-p})} \)

\( =e^{m(-(\hat{p}\log \frac{\hat{p}}{p}-(1-\hat{p})\log \frac{1-\hat{p}}{1-p})-(\hat{p}\log \frac{1}{\hat{p}}-(1-\hat{p})\log \frac{1}{1-\hat{p}}))} \)

\( =e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))} \)


\lyxnewoverlay{afaf}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

Proof: \( \Pr _{\textrm{error}}(S)=p^{\#heads}(1-p)^{\#tails} \)

\( =p^{\hat{p}m}(1-p)^{(1-\hat{p})m} \)

\( =e^{\log p^{\hat{p}m}+\log (1-p)^{(1-\hat{p})m}} \)


\lyxinvisible{}

\( =e^{-m(\hat{p}\log \frac{1}{p}-(1-\hat{p})\log \frac{1}{1-p})} \)

\( =e^{m(-(\hat{p}\log \frac{\hat{p}}{p}-(1-\hat{p})\log \frac{1-\hat{p}}{1-p})-(\hat{p}\log \frac{1}{\hat{p}}-(1-\hat{p})\log \frac{1}{1-\hat{p}}))} \)

\( =e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))} \)


\lyxnewoverlay{afaf}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

Proof: \( \Pr _{\textrm{error}}(S)=p^{\#heads}(1-p)^{\#tails} \)

\( =p^{\hat{p}m}(1-p)^{(1-\hat{p})m} \)

\( =e^{\log p^{\hat{p}m}+\log (1-p)^{(1-\hat{p})m}} \)

\( =e^{-m(\hat{p}\log \frac{1}{p}-(1-\hat{p})\log \frac{1}{1-p})} \)


\lyxinvisible{}

\( =e^{m(-(\hat{p}\log \frac{\hat{p}}{p}-(1-\hat{p})\log \frac{1-\hat{p}}{1-p})-(\hat{p}\log \frac{1}{\hat{p}}-(1-\hat{p})\log \frac{1}{1-\hat{p}}))} \)

\( =e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))} \)


\lyxnewoverlay{afaf}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

Proof: \( \Pr _{\textrm{error}}(S)=p^{\#heads}(1-p)^{\#tails} \)

\( =p^{\hat{p}m}(1-p)^{(1-\hat{p})m} \)

\( =e^{\log p^{\hat{p}m}+\log (1-p)^{(1-\hat{p})m}} \)

\( =e^{-m(\hat{p}\log \frac{1}{p}-(1-\hat{p})\log \frac{1}{1-p})} \)

\( =e^{m(-(\hat{p}\log \frac{\hat{p}}{p}-(1-\hat{p})\log \frac{1-\hat{p}}{1-p})-(\hat{p}\log \frac{1}{\hat{p}}-(1-\hat{p})\log \frac{1}{1-\hat{p}}))} \)


\lyxinvisible{}

\( =e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))} \)


\lyxnewoverlay{afaf}

Lemma: \( \forall P\,\,\Pr _{S\sim D^{m}}\left( E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta }\right) \geq 1-\delta  \) 

Proof: \( \Pr _{\textrm{error}}(S)=p^{\#heads}(1-p)^{\#tails} \)

\( =p^{\hat{p}m}(1-p)^{(1-\hat{p})m} \)

\( =e^{\log p^{\hat{p}m}+\log (1-p)^{(1-\hat{p})m}} \)

\( =e^{-m(\hat{p}\log \frac{1}{p}-(1-\hat{p})\log \frac{1}{1-p})} \)

\( =e^{m(-(\hat{p}\log \frac{\hat{p}}{p}-(1-\hat{p})\log \frac{1-\hat{p}}{1-p})-(\hat{p}\log \frac{1}{\hat{p}}-(1-\hat{p})\log \frac{1}{1-\hat{p}}))} \)

\( =e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))} \)


\lyxnewslide{afaf}


\lyxnewoverlay{df}

\( E_{S}e^{m\textrm{KL}(\hat{p}||p)}\leq \sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}\Pr (S)|\{S:\hat{p}\}| \)


\lyxinvisible{}

\( =\sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))}e^{m\textrm{H}(\hat{p})} \)

\( =\sum _{\hat{p}}1 \)

\( =m+1 \)

\( \Rightarrow E_{S}E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq m+1 \)

\( \Rightarrow \forall P\,\,\Pr _{S}(E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta })\leq \delta  \)
(markov)


\lyxnewoverlay{df}

\( E_{S}e^{m\textrm{KL}(\hat{p}||p)}\leq \sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}\Pr (S)|\{S:\hat{p}\}| \)

\( =\sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))}e^{m\textrm{H}(\hat{p})} \)


\lyxinvisible{}

\( =\sum _{\hat{p}}1 \)

\( =m+1 \)

\( \Rightarrow E_{S}E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq m+1 \)

\( \Rightarrow \forall P\,\,\Pr _{S}(E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta })\leq \delta  \)
(markov)


\lyxnewoverlay{df}

\( E_{S}e^{m\textrm{KL}(\hat{p}||p)}\leq \sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}\Pr (S)|\{S:\hat{p}\}| \)

\( =\sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))}e^{m\textrm{H}(\hat{p})} \)

\( =\sum _{\hat{p}}1 \)


\lyxinvisible{}

\( =m+1 \)

\( \Rightarrow E_{S}E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq m+1 \)

\( \Rightarrow \forall P\,\,\Pr _{S}(E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta })\leq \delta  \)
(markov)


\lyxnewoverlay{df}

\( E_{S}e^{m\textrm{KL}(\hat{p}||p)}\leq \sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}\Pr (S)|\{S:\hat{p}\}| \)

\( =\sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))}e^{m\textrm{H}(\hat{p})} \)

\( =\sum _{\hat{p}}1 \)

\( =m+1 \)


\lyxinvisible{}

\( \Rightarrow E_{S}E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq m+1 \)

\( \Rightarrow \forall P\,\,\Pr _{S}(E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta })\leq \delta  \)
(markov)


\lyxnewoverlay{df}

\( E_{S}e^{m\textrm{KL}(\hat{p}||p)}\leq \sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}\Pr (S)|\{S:\hat{p}\}| \)

\( =\sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))}e^{m\textrm{H}(\hat{p})} \)

\( =\sum _{\hat{p}}1 \)

\( =m+1 \)

\( \Rightarrow E_{S}E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq m+1 \)


\lyxinvisible{}

\( \Rightarrow \forall P\,\,\Pr _{S}(E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta })\leq \delta  \)
(markov)


\lyxnewoverlay{df}

\( E_{S}e^{m\textrm{KL}(\hat{p}||p)}\leq \sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}\Pr (S)|\{S:\hat{p}\}| \)

\( =\sum _{\hat{p}}e^{m\textrm{KL}(\hat{p}||p)}e^{m(-\textrm{KL}(\hat{p}||p)-\textrm{H}(\hat{p}))}e^{m\textrm{H}(\hat{p})} \)

\( =\sum _{\hat{p}}1 \)

\( =m+1 \)

\( \Rightarrow E_{S}E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq m+1 \)

\( \Rightarrow \forall P\,\,\Pr _{S}(E_{h\sim P}e^{m\textrm{KL}(\hat{e}(h)||e(h))}\leq \frac{m+1}{\delta })\geq 1-\delta  \)
(markov)


\lyxnewslide{afaf}


\lyxnewoverlay{df}

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)


\lyxinvisible{}

Proof: Let \( P_{G}(h)=\frac{e^{f(h)}}{E_{P}e^{f(h)}}P(h) \)

\( 0\leq \textrm{KL}(Q||P_{G})=E_{h\sim Q}\ln \frac{E_{h\sim P}e^{f(h)}}{e^{f(h)}}\frac{Q(h)}{P(h)} \)

\( =\textrm{KL}(Q||P)-E_{h\sim Q}f(h)+\ln E_{h\sim P}e^{f(h)} \)


\lyxnewoverlay{df}

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)

Proof: Let \( P_{G}(h)=\frac{e^{f(h)}}{E_{P}e^{f(h)}}P(h) \)


\lyxinvisible{}

\( 0\leq \textrm{KL}(Q||P_{G})=E_{h\sim Q}\ln \frac{E_{h\sim P}e^{f(h)}}{e^{f(h)}}\frac{Q(h)}{P(h)} \)

\( =\textrm{KL}(Q||P)-E_{h\sim Q}f(h)+\ln E_{h\sim P}e^{f(h)} \)


\lyxnewoverlay{df}

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)

Proof: Let \( P_{G}(h)=\frac{e^{f(h)}}{E_{P}e^{f(h)}}P(h) \)

\( 0\leq \textrm{KL}(Q||P_{G})=E_{h\sim Q}\ln \frac{E_{h\sim P}e^{f(h)}}{e^{f(h)}}\frac{Q(h)}{P(h)} \)


\lyxinvisible{}

\( =\textrm{KL}(Q||P)-E_{h\sim Q}f(h)+\ln E_{h\sim P}e^{f(h)} \)


\lyxnewoverlay{df}

Lemma: \( \forall Q,P,f\,\,E_{h\sim Q}f(h)\leq \textrm{KL}(Q||P)+\ln E_{h\sim P}e^{f(h)} \)

Proof: Let \( P_{G}(h)=\frac{e^{f(h)}}{E_{P}e^{f(h)}}P(h) \)

\( 0\leq \textrm{KL}(Q||P_{G})=E_{h\sim Q}\ln \frac{E_{h\sim P}e^{f(h)}}{e^{f(h)}}\frac{Q(h)}{P(h)} \)

\( =\textrm{KL}(Q||P)-E_{h\sim Q}f(h)+\ln E_{h\sim P}e^{f(h)} \)


\lyxnewslide{afaf}

\begin{enumerate}
\item \textcolor{red}{Occam's Razor bound}
\item \textcolor{red}{PAC-Bayes bound}
\item \textcolor{red}{Proof}
\item \textcolor{green}{Bits-Back}
\end{enumerate}

\lyxnewslide{afaf}

PAC-Bayes versus MDL

\begin{enumerate}
\item Shorter description length?
\item But \( Q\sim h \) may be very unshort
\end{enumerate}

\lyxnewslide{afa}

{\par\centering Bits-Back (Hinton and van Camp 93)\par}

\begin{enumerate}
\item Alice talks to Bob a lot.
\item Alice has labeled examples. 
\item Bob has same examples, but no labels.
\end{enumerate}
How many \emph{extra} bits are required for Alice to send the labels?


\lyxnewslide{afaf}

Suppose Alice and Bob share a learning algorithm with posterior, \( Q \).

\begin{enumerate}
\item Alice picks \( h\sim Q \) using \emph{message \( M \)} where \( |M|\simeq H(Q) \)
\end{enumerate}

\lyxinvisible{}

\begin{enumerate}
\item Alice transmits \( h \) with \( \textrm{H}(Q)+\textrm{KL}(Q||P) \) bits (+
corrections).
\item Bob decodes labeled examples
\item Bob runs learning algorithm to decode \( Q \)
\item Bob decodes \( M \)
\end{enumerate}

\lyxnewoverlay{k}

Suppose Alice and Bob share a learning algorithm with posterior, \( Q \).

\begin{enumerate}
\item Alice picks \( h\sim Q \) using \emph{message \( M \)} where \( |M|\simeq H(Q) \)
\item Alice transmits \( h \) with \( \textrm{H}(Q)+\textrm{KL}(Q||P) \) bits (+
corrections).
\end{enumerate}

\lyxinvisible{}

\begin{enumerate}
\item Bob decodes labeled examples
\item Bob runs learning algorithm to decode \( Q \)
\item Bob decodes \( M \)
\end{enumerate}

\lyxnewoverlay{k}

Suppose Alice and Bob share a learning algorithm with posterior, \( Q \).

\begin{enumerate}
\item Alice picks \( h\sim Q \) using \emph{message \( M \)} where \( |M|\simeq H(Q) \)
\item Alice transmits \( h \) with \( \textrm{H}(Q)+\textrm{KL}(Q||P) \) bits (+
corrections).
\item Bob decodes labeled examples
\end{enumerate}

\lyxinvisible{}

\begin{enumerate}
\item Bob runs learning algorithm to decode \( Q \)
\item Bob decodes \( M \)
\end{enumerate}

\lyxnewoverlay{k}

Suppose Alice and Bob share a learning algorithm with posterior, \( Q \).

\begin{enumerate}
\item Alice picks \( h\sim Q \) using \emph{message \( M \)} where \( |M|\simeq H(Q) \)
\item Alice transmits \( h \) with \( \textrm{H}(Q)+\textrm{KL}(Q||P) \) bits (+
corrections).
\item Bob decodes labeled examples
\item Bob runs learning algorithm to decode \( Q \)
\end{enumerate}

\lyxinvisible{}

\begin{enumerate}
\item Bob decodes \( M \)
\end{enumerate}

\lyxnewoverlay{k}

Suppose Alice and Bob share a learning algorithm with posterior, \( Q \).

\begin{enumerate}
\item Alice picks \( h\sim Q \) using \emph{message \( M \)} where \( |M|\simeq H(Q) \)
\item Alice transmits \( h \) with \( \textrm{H}(Q)+\textrm{KL}(Q||P) \) bits (+
corrections).
\item Bob decodes labeled examples
\item Bob runs learning algorithm to decode \( Q \)
\item Bob decodes \( M \)
\end{enumerate}

\lyxnewslide{afaf}

{\par\centering Bits-back Summary\par}

total bits = \( \textrm{H}(Q)+\textrm{KL}(Q||P)+ \)corrections 

total message = \( M,\textrm{ }Q, \) labels


\lyxnewslide{afa}

{\par\centering PAC-Bayes open questions\par}

Tightness:

\begin{enumerate}
\item Can we lose the \( m+1 \) term?
\item Can we reduce it to the CDF of the Binomial?
\end{enumerate}
Application: Where else does it apply? 

\begin{enumerate}
\item Matthias Seeger says: Gaussian Processes
\end{enumerate}
\end{document}
