\section{Background}
\label{sec:background}

The primary technical framework we leverage in this paper is PAC-Bayes theory. In Section \ref{sec:pac bayes learning}, we provide a brief overview of the key results from PAC-Bayes theory in the context of supervised learning. We first provide some brief background on the properties of the Kullback-Leibler (KL) divergence in Section \ref{sec:kl divergence} and show how we can compute its inverse using Relative Entropy Programming (REP) in Section \ref{sec:kl inverse}.

\subsection{KL divergence}
\label{sec:kl divergence}

Given two discrete probability distributions $P$ and $Q$ defined over a common set, the KL divergence from Q to P is defined as
\begin{equation}
\KL(P \| Q) := \sum_i P[i] \log \Bigg( \frac{P[i]}{Q[i]} \Bigg).
\end{equation}
For scalars $p,q \in [0,1]$, we define
\begin{equation}
\label{eq:kl bernoulli}
\KL(p \| q) := \KL(B(p) \| B(q)) = p \log \frac{p}{q} + (1 - p) \log \frac{1 - p}{1 - q},
\end{equation}
where $B(p)$ denotes a Bernoulli distribution on $\{0,1\}$ with parameter (i.e., mean) $p$. 

For distributions P and Q of a continuous random variable, the KL divergence is defined to be
\begin{equation}
\KL(P\|Q)=\int p(x)\,\log {\frac {p(x)}{q(x)}}\,dx,
\end{equation}
where $p$ and $q$ denote the densities of $P$ and $Q$. Importantly, if $P$ and $Q$ correspond to normal distributions $N_p = \mathcal{N}(\mu_p, \Sigma_p)$ and $N_q = \mathcal{N}(\mu_q, \Sigma_q)$ over $\RR^d$, the KL divergence can be computed in closed form as
\begin{equation}
\label{eq:KL normal}
\KL(N_p \| N_q) = \frac{1}{2} \Bigg( \textrm{Tr}(\Sigma_q^{-1} \Sigma_p) + (\mu_q - \mu_p)^T \Sigma_q^{-1} (\mu_q - \mu_p) + \log \frac{\textrm{det}(\Sigma_q)}{\textrm{det}(\Sigma_p)} - d \Bigg).
\end{equation}

\subsubsection{Computing KL inverse using Relative Entropy Programming}
\label{sec:kl inverse}

PAC-Bayes bounds (Section \ref{sec:pac bayes learning}) are typically expressed as bounds on a quantity $q^\star \in [0,1]$ of the form $\KL(p \| q^\star) \leq c$ (for some $p \in [0,1]$ and $c \geq 0$). These bounds can then be used to upper bound $q^\star$ by the \emph{KL inverse} as follows:
\begin{equation}
\label{eq:kl inverse}
q^\star \leq \KL^{-1} (p \| c) := \sup \{ q \in [0,1] \ | \ \KL(p \| q) \leq c \}.
\end{equation}

In prior work on PAC-Bayes theory, the KL inverse was numerically approximated using local root-finding techniques such as Newton's method \citep{Dziugaite17, Dziugaite17a}, which do not have a priori guarantees on convergence to a global solution. Here we observe that the KL inverse is readily expressed as the optimal value of a simple Relative Entropy Program (ref. Section \ref{sec:related work}). In particular, the expression for the KL inverse in \eqref{eq:kl inverse} corresponds to an optimization problem with a (scalar) decision variable $q$, a linear cost function (i.e., $-q$), linear inequality constraints (i.e., $0 \leq q \leq 1$), and a constraint on the KL divergence between the decision variable $q$ and the constant $p$.
We can thus compute the KL inverse exactly (up to numerical tolerances) using convex optimization (e.g., interior point methods \citep{Chandrasekaran17}).

\subsection{PAC-Bayes Theory in Supervised Learning}
\label{sec:pac bayes learning}

We now provide a brief overview of the key results from PAC-Bayes theory in the context of supervised learning.
Let $\Z$ be an input space and $\Z'$ be a set of labels. Let $\D$ be the (unknown) true distribution on $\Z$. Let $\HH$ be a hypothesis class consisting of functions $h_w: \Z \rightarrow \Z'$ parameterized by $w \in \RR^d$ (e.g., neural networks parameterized by weights $w$). Let $l: \HH \times \Z \rightarrow \RR$ be a loss function\footnote{Note that we are considering a slightly restricted form of the supervised learning problem where each input $z \in \Z$ has only one correct label $z' \in \Z'$. The loss thus only depends on the input $z$ and the label $h_w(z)$. The PAC-Bayes framework applies to the more general setting where there is an underlying true distribution on $\Z \times \Z'$ and the loss thus has the form $l: \HH \times \Z \times \Z' \rightarrow \RR$. However, the more restricted setting is sufficient for our needs here.}. We will denote by $\PP$ the space of probability distributions on the parameter space $\RR^d$. Informally, we will refer to distributions on $\HH$ when we mean distributions over the underlying parameter space.

PAC-Bayes analysis then applies to learning algorithms that output a \emph{distribution} over hypotheses. Specifically, the PAC-Bayes framework applies to learning algorithms with the following structure:
\begin{enumerate}
\item Choose a \emph{``prior" distribution} $P_0 \in \PP$ \emph{before} observing any data.
\item Observe training data samples $S = \{z_i\}_{i=1}^N$ and choose a \emph{posterior distribution} $P \in \PP$. This posterior can depend on the data and the prior. 
\end{enumerate}
It is important to note that the posterior distribution $P$ \emph{need not} be the Bayesian posterior. PAC-Bayes theory applies to \emph{any} distribution $P$.

Let us denote the training loss associated with the posterior distribution $P$ as:
\begin{equation}
l_S(P) := \frac{1}{N} \sum_{z \in S} \underset{w \sim P}{\EE} [l(h_w; z)],
\end{equation}
and the true expected loss as:
\begin{equation}
l_\D(P) := \underset{z \sim \D}{\EE} \ \underset{w \sim P}{\EE} [l(h_w; z)].
\end{equation}
The following theorem is the primary result from PAC-Bayes theory\footnote{The bound we state here is due to Maurer \citep{Maurer04} and improves slightly upon the original PAC-Bayes bounds \citep{McAllester99}. The stated bound holds when costs are bounded in the range $[0,1]$ (as assumed here) and we have $N \geq 8$ samples.

}. 

\begin{theorem}[PAC-Bayes Bound for Supervised Learning \citep{McAllester99, Maurer04}]
\label{thm:pac bayes kl}
For any $\delta \in (0,1)$, with probability at least $1 - \delta$ over samples $S \sim \D^N$, the following inequality holds:
\begin{equation}
\label{eq:pac bayes kl}
\KL(l_S(P) \| l_\D(P)) \leq \frac{\KL(P \| P_0) + \log(\frac{2 \sqrt{N}}{\delta})}{N}.
\end{equation}
\end{theorem}
Here, $\KL(l_S(P) \| l_\D(P))$ is interpreted as a KL divergence between Bernoulli distributions and computed using \eqref{eq:kl bernoulli} (this is meaningful since $l_S(P)$ and $l_\D(P)$ are scalars bounded within $[0,1]$). 

Intuitively, Theorem \ref{thm:pac bayes kl} provides a bound on how ``close'' the training loss $l_S(P)$ and the true expected loss $l_\D(P)$ are. However, in practice, one would like to find an \emph{upper bound} on the true expected loss $l_\D(P)$. Such an upper bound can be obtained by computing the KL inverse (ref. Section \ref{sec:kl inverse}):
\begin{equation}
\label{eq:pac bayes learning kl version}
l_\D(P) \leq \KL^{-1}\Big(l_S(P) \| \frac{\KL(P \| P_0) + \log(\frac{2 \sqrt{N}}{\delta})}{N} \Big).
\end{equation}

Another upper bound that is useful for the purpose of optimization is provided by the following corollary, which follows from Theorem \ref{thm:pac bayes kl} by applying the well-known upper bound for the KL inverse one obtains by applying Pinsker's inquality: $\KL^{-1}(p \| c) \leq p + \sqrt{c/2}$.

\begin{corollary}[PAC-Bayes Upper Bound for Supervised Learning \citep{McAllester99, Maurer04}]
\label{thm:pac bayes learning}
For any $\delta \in (0,1)$, with probability at least $1 - \delta$ over samples $S \sim \D^N$, the following inequality holds:
\begin{equation}
\label{eq:pac bayes upper bound}
\underbrace{l_\D(P)}_{\text{True expected loss}} \leq \underbrace{l_S(P)}_{\text{Training loss}} + \underbrace{\sqrt{\frac{\KL(P \| P_0) + \log(\frac{2 \sqrt{N}}{\delta})}{2N}}}_{\text{``Regularizer"}}.
\end{equation}
\end{corollary}
Corollary \ref{thm:pac bayes learning} provides a strategy for choosing a distribution $P$ over hypotheses with a provable guarantee on generalization: minimize the right hand side (RHS) of inequality \eqref{eq:pac bayes upper bound} consisting of the training loss and a ``regularization" term.
{"config": "arxiv", "file": "1806.04225/sections/background.tex"}