\section{Introduction}
The generalization capability of a learning algorithm is intrinsically related to the information that the output hypothesis reveals about the input training dataset: The lesser the information revealed, the better the generalization. This argument has been formalized in recent years by appealing to different notions of information stability \cite{russoZou2016controlling,generalizationRaginsky,jiao2017dependence,generalizationRaginskyBassily,veeravalli,issa2019strengthened,steinke2020reasoning,steinke2020reasoningOpen,DziugaiteRoySGLDSteinke}. Information stability quantifies the sensitivity of a learning algorithm to local perturbations of its input, and draws on a rich tradition of earlier work on algorithmic \cite{bousquet2002stability,ShalevLearnabilityStabilityUnifConvergence,bassily2016algorithmic}, and distributional \cite{feldman2015generalization,rogers2016max,feldman2018calibrating} stability in adaptive data analysis. Closely related to the information stability approach is the so-called PAC-Bayesian approach to data-dependent generalization bounds, originally due to McAllester \cite{generalizationRaginskyPACBayesMcallester,mcallester1999some,mcallesterdropout}. While these two approaches have evolved independently of each other, a principal objective of this work is to present them under a unified framework.

We consider the standard apparatus of statistical learning theory \cite{shalev2014understanding}. We have an example domain $\cZ= \cX \times \cY$ of the instances and labels, a hypothesis space $\cW$, a fixed loss function  $\ell:{\cW}\times{\cZ}\to[0,\infty)$, and a training sample $S$, which is an $n$-tuple $(Z_1,\ldots,Z_n)$ of i.i.d.\ random elements of $\cZ$ drawn according to some unknown distribution $\mu$. A learning algorithm is a Markov kernel $P_{W|S}$ that maps input training samples $S$ to conditional distributions of hypotheses $W$ in $\cW$. This defines a joint distribution $P_{SW}=P_S P_{W|S}$, $P_S=\mu^{\otimes n}$, and a corresponding marginal distribution $P_W$. The \emph{true risk} of a hypothesis $w\in\mathcal{W}$ on $\mu$ is $L_{\mu}(w) := {\mathbb{E}}_{\mu}[\ell(w,Z)]$, and its \emph{empirical risk} on the training sample $S$ is $L_S(w):= \frac{1}{n} \sum_{i=1}^n \ell(w,Z_i)$. Our goal is to control the \emph{generalization error}, $\mathrm{g}(W,S) := L_{\mu}(W)-L_S(W)$, either in expectation, or with high probability. One difficulty in achieving this goal is the nontrivial statistical dependency between the sample $S$ and the learned hypothesis $W$.

For controlling the generalization error in expectation, we can rewrite the true risk of a given hypothesis $w$ as $L_{\mu}(w) = \mathbb{E}_{S'\sim \mu^{\otimes n}}[L_{S'}(w)]$, where $S'=({Z_1'},\ldots,{Z_n'})$ is an i.i.d.\ sample. Then the expected generalization error can be written as a difference of two expectations of the same loss function, 
\begin{align*
&\mathbb{E}_{SW}[\mathrm{g}(W,S)]=\mathbb{E}_{P_S\otimes P_W}[L_{S}(W)]- \mathbb{E}_{P_{SW}}[L_S(W)],
\end{align*}
where the second expectation is taken w.r.t.\ the joint distribution of the training sample and the output hypothesis, while the first expectation is taken w.r.t.\ the product of the two marginal distributions. Hence the expected generalization error reflects the dependence of the output $W$ on the input $S$. This dependence can also be measured by their mutual information as has been shown in recent works  \cite{generalizationRaginsky,jiao2017dependence,generalizationRaginskyBassily,veeravalli,issa2019strengthened,steinke2020reasoning}. We refer to such bounds as mutual information-based generalization bounds.

Alternatively, we may wish to control the generalization error of the learning algorithm $P_{W|S}$ with high probability over the training sample $S$. The expected generalization error over hypotheses chosen from the distribution ${P}$ (\emph{posterior}) output by the learning algorithm, i.e.,\ $\mathbb{E}_{{P}}[\mathrm{g}(W,S)]$, can be upper-bounded with high probability under $P_S$ by the KL divergence between ${P}$ and an arbitrary reference distribution $Q$ (\emph{prior}), that is selected \emph{before} the draw of the training sample $S$. For any $Q$, these bounds hold {uniformly} for all ${P}$, and are called PAC-Bayesian bounds \cite{generalizationRaginskyPACBayesMcallester,mcallester1999some,mcallesterdropout,TongZhangPACBayes2006,catonibook,maurer2004PACBayes,TimvanErvenPACBayesTongZhang,grunwaldTongZhangFastrates,alquierPACBayesPropertiesGibbs,germain2009Paclinear,FlatminimaBayesianSGDGermainMackay1992,rivasplataThiemannPACBackprop,rivasplatapac}, where PAC stands for \emph{Probably Approximately Correct}. Bounds of this type are useful when we have a fixed dataset $s\in\cZ^n$ and a new hypothesis is sampled from ${P}$ every time the algorithm is used. Choosing the posterior to minimize a PAC-Bayesian bound leads to the well-known Gibbs-ERM principle \cite{TongZhangPACBayes2006,generalizationRaginsky,alquierPACBayesPropertiesGibbs,rivasplatapackuzborskij}. On the other hand, for a fixed posterior ${P}$, $\mathbb{E}_S[D({P}\|Q)]$ is minimized by the \emph{oracle prior}, $Q^{\star}=\mathbb{E}_{S}[P_{W|S}(\cdot|S)]$. Note $\mathbb{E}_S[D({P}\|Q^{\star})]$ is just the mutual information $I(S;W)$, which is the key quantity controlling the expected generalization error in \cite{generalizationRaginsky,jiao2017dependence,generalizationRaginskyBassily}. 

\paragraph{Summary of contributions.}
We present a unified framework for deriving PAC-Bayesian and mutual information-based generalization bounds, starting from a fundamental information-theoretic inequality, Lemma~\ref{lem:InfoExpInequality}, due to Tong Zhang \cite{TongZhangPACBayes2006}. Besides recovering several well-known bounds of both flavors, such as the Xu-Raginsky mutual information-bound \cite{generalizationRaginsky} in Corollary~\ref{cor:XuRaginsky}, and Catoni's bound \cite{catonibook} in Corollary~\ref{thm:pacbayesCatoniDiff}, we also obtain new bounds for data-dependent priors (Proposition \ref{thm:PACDPPrior}) and unbounded loss functions (Theorem~\ref{cor:TongZhangIRM} and Proposition \ref{thm:PACUnionboundMIsubGaussian}). Proposition~\ref{thm:CMIPACBound01Loss} gives a PAC-Bayes version of the CMI bound due to Steinke and Zakynthinou \cite{steinke2020reasoning}. Optimizing these bounds w.r.t.\ the posterior gives rise to variants of the Gibbs algorithm, for which we discuss two examples and show how Catoni's bound can be used to derive a PAC-Bayes-SGD \cite{dziugaitenonvacuous} objective. In Proposition~\ref{thm:OccamPAC}, we give a PAC-Bayesian bound motivated by an Occam's factor argument, in relation to ``flat'' minima in neural networks \cite{FlatMinimaSchmidhuber}. 



\section{Preliminaries}
We write $\cM(\cW)$ to denote the family of probability measures over a set $\cW$, and $\cK(\cS,\cW)$ to denote the set of Markov kernels from $\cS$ to $\cW$. 
Proposition~\ref{Prop:logmgfProperties} collects some well-known facts about the cumulant generating function $\Lambda_X(\beta)=\ln\mathbb{E}[e^{\beta X}]$ of a random variable $X$ for $\beta > 0$ (see, e.g., \cite[\S 2]{boucheron2013concentration}, and \cite{TongZhangPACBayes2006}):
\begin{proposition}[Facts about the cumulant generating function $\Lambda_X(\beta)$ for $\beta>0$]\label{Prop:logmgfProperties}\
	
	\begin{enumerate} 
		\item $\Lambda_X(\beta)$ is infinitely differentiable and convex in $\beta$;
		\item $\tfrac{1}{\beta}\Lambda_X(\beta)$ is an increasing function of $\beta$;
		\item $\mathbb{E}[X]\le \tfrac{1}{\beta}\Lambda_{X}(\beta)\le \Lambda'_{X}(\beta)$;
		\item For real constants $a,b$, $\tfrac{1}{\beta}\Lambda_{aX+b}(\beta)=\tfrac{1}{\beta}\Lambda_X(a\beta)+b$;
		\item $\tfrac{1}{\beta}\Lambda_X(\beta) \le  \mathbb{E}[X]+\frac{\beta}{2}\mathrm{Var}(X)+O(\beta^2)$, where $\mathrm{Var}(X) = \mathbb{E}\left[(X-\mathbb{E}[X])^2\right]$;
		\item If $X\in[0,1]$, then $\tfrac{1}{\beta}\Lambda_X(\beta)\le \tfrac{1}{\beta}\ln \left(1-(1-e^{\beta})\mathbb{E}[X]\right)$, with equality when $X\in\{0,1\}$ is Bernoulli;
		\item $X$ is \emph{$\sigma$-sub-Gaussian} if 
		$\tfrac{1}{\beta}\Lambda_{X}(\beta)\le \mathbb{E}[X]+\frac{\beta\sigma^2}{2}$;
		\item $X$ is \emph{$(\sigma,c)$-sub-gamma} if $\tfrac{1}{\beta}\Lambda_{X}(\beta)\le \mathbb{E}[X]+ \frac{\beta\sigma^2}{2(1-c\beta)}$ for every $\beta$ such that $\beta \in \left(0,\tfrac{1}{c}\right)$.
	\end{enumerate}
\end{proposition}
We also note that $\Lambda_{X}(0)=0,\,\Lambda'_{X}(0)=\mathbb{E}[X]$.

We will need the following characterization of the inverse of the Fenchel-Legendre dual of a smooth convex function:
\begin{restatable}[{\cite[Lemma 2.4]{boucheron2013concentration}}]
	{lemma}{InverseFenchelConjugate}\label{lemma:psistar}
	Let $\psi$ be a convex and continuously differentiable function defined on the interval $[0,b)$, where $0<b\le \infty$. Assume that $\psi(0)= \psi'(0) = 0$. 	Then, the Legendre dual of $\psi$, defined as $$\psi^*(t) := \sup_{\beta \in [0,b)} \{\beta t-\psi(\beta)\},$$ is a nonnegative convex and nondecreasing function on $[0,\infty)$ with $\psi^*(0) = 0$. Moreover, for every $y\ge 0$, the set $\{t\ge 0: \psi^*(t)> y\}$ is non-empty and the generalized inverse of $\psi^*$ defined by $\psi^{*-1}(y) = \inf\{t\ge 0: \psi^*(t)> y\}$ can also be written as 
	\begin{align*}
	\psi^{*-1}(y) = \inf_{\beta \in (0,b)} \frac{y+\psi(\beta)}{\beta}.
	\end{align*}
\end{restatable}
We will need the following property of the Gibbs measure:
\begin{lemma}
	[{\cite[Proposition 3.1]{TongZhangPACBayes2006}}]
	\label{thm:DVlemmalikeCatoni}
	For any real-valued measurable function $f$ on $\cW$, any real $\beta>0$, and any ${P},\,Q\in\cM(\cW)$ such that $D({P}\|Q)<\infty$, we have $$\beta^{-1}D({P}\|{P}^{\ast})=\mathbb{E}_{{P}}[f(W)]+\beta^{-1}D({P}\|Q)+\beta^{-1}\ln \mathbb{E}_{Q} [e^{-\beta f(W)}],$$
	where ${P}^{\ast}$ is the Gibbs measure $${P}^{\ast}(\mathrm{d}w):= \frac{e^{-\beta f(w)}}{\mathbb{E}_{Q}[e^{-\beta f(W')}]}Q(\mathrm{d}w).$$ Consequently,
	\begin{align*
	\inf_{{P}\in\cM(\cW)}\left\{\mathbb{E}_{{P}}f(W)+\beta^{-1}D({P}\|Q)\right\}=-\beta^{-1}\ln \mathbb{E}_{Q} [e^{-\beta f(W)}].
	\end{align*} 
\end{lemma}
Finally, we recall the \emph{golden formula}: For all $Q\in\cM(\cW)$ such that $D(P_W\|Q) < \infty$, we have 
\begin{align}\label{eq:goldenformulaMI}
I(S;W )= D(P_{W|S}\|Q|P_S) - D(P_W\|Q),
\end{align}
where $D(P_{W|S} \|Q  |P_{S})=\int_{\cZ^{n}} D(P_{W|S=s} \| Q) \mu^{\otimes n}(\mathrm{d} s)$.

All information-theoretic quantities are expressed in \emph{nats}, unless specified otherwise. 
All proofs are relegated to Appendix \ref{sec:proofs}.

\section{One bound to rule them all}\label{sec:OneBoundAll}
\subsection{The information exponential inequality}\label{sec:IEI}
For any real $\beta>0$, define
\begin{align}\label{eq:TongZhanglogmgf}
M_{\beta}(w) = -\beta^{-1}\Lambda_{-\ell(w,Z)}(\beta)=-\beta^{-1}\ln \mathbb{E}_{\mu}[e^{-\beta \ell(w,Z)}]
\end{align}
which acts as a surrogate for $L_{\mu}(w)$. Following \cite{grunwaldTongZhangFastrates}, we call this quantity the \emph{annealed expectation}. 
\begin{restatable}[{Information exponential inequality (IEI) \cite[Lemma 2.1]{TongZhangPACBayes2006}}]{lemma}{InfoExpInequality}\label{lem:InfoExpInequality}
	For any prior $Q\in \cM(\cW)$, any real-valued loss function $\ell$ on $\cW\times\cZ$, and any posterior distribution ${P}\llQ$ over $\cW$ that depends on an i.i.d.\ training sample $S$, we have $${\mathbb{E}}_{S}\exp \big\{n\beta{\mathbb{E}}_{{P}}\left[M_{\beta}(W)-L_S(W)\right]-D({P} \| Q)\big\} \le 1.$$
\end{restatable}
The IEI implies bounds both in probability and in expectation for the quantity $$n\beta{\mathbb{E}}_{{P}}\left[M_{\beta}(W)-L_S(W)\right]-D({P} \| Q),$$ and is the key tool for showing the following theorem due to Tong Zhang that holds for unbounded loss functions: 
\begin{restatable}[{\cite[Theorem 2.1]{TongZhangPACBayes2006}}]{theorem}{TongZhang}\label{thm:TongZhangIRM}
	Let $\mu$ be a distribution over $\cZ$, and let $S$ be an i.i.d.\ training sample from $\mu$. Let $Q\in\cM(\cW)$ be a prior distribution that does not depend on $S$, and let $\ell$ be a real-valued loss function on $\cW\times\cZ$. Let $\beta >0$, and let $\delta\in (0,1]$. Then, with probability of at least $1-\delta$ over the choice of $S \sim\mu^{\otimes{n}}$, for all distributions ${P} \ll Q$ over $\cW$ (even such that depend on $S$), we have: 
	\begin{align}\label{eq:TongZhangHighProbBound}
	\mathbb{E}_{{P}} [M_{\beta}(W)] \leq \mathbb{E}_{{P}}[L_S(W)] + \frac{1}{n\beta}\left(D({P}\|Q)+\ln \frac{1}{\delta}\right).
	\end{align}
	Moreover, we have the following bound in expectation:
	\begin{align}\label{eq:TongZhangExpBound}
	\mathbb{E}_{SW} [M_{\beta}(W)] \leq \mathbb{E}_{SW}[L_S(W)] + \frac{1}{n\beta }D({P}\|Q|P_S).
	\end{align}
\end{restatable}
Following \cite{TongZhangPACBayes2006AnnalsStats}, we call the regularized empirical risk $$\mathbb{E}_{{P}}[L_S(W)] + \frac{1}{n\beta}D({P}\|Q)$$ as the \emph{Information Complexity (IC)}, which is a data- and algorithm- dependent quantity. 

It is useful to replace the annealed expectation $M_{\beta}(w)$ in \eqref{eq:TongZhangHighProbBound} and \eqref{eq:TongZhangExpBound} with the true risk $L_{\mu}(w)$.
By Proposition \ref{Prop:logmgfProperties} items \emph{1)} and \emph{3)}, we have $M_{\beta}(w) \le L_{\mu}(w)$. 
For general loss functions, Proposition \ref{Prop:logmgfProperties} item \emph{5)} is useful for getting bounds in the opposite direction. By items \emph{4)}, \emph{7)} and \emph{8)} of Proposition~\ref{Prop:logmgfProperties}, if for all $w\in\cW$, $\ell(w,Z)$ is $\sigma$-sub-Gaussian, resp., $(\sigma,c)$-sub-gamma under $\mu$, then we have for all $w\in\cW$, $L_{\mu}(w) \le M_{\beta}(w) + \frac{\beta}{2}\sigma^2$ for all $\beta>0$, resp., $L_{\mu}(w) \le M_{\beta}(w) + \frac{\beta}{2(1-c\beta)}\sigma^2$ for every $\beta$ such that $\beta \in \left(0,\tfrac{1}{c}\right)$.
More generally, we note the following result, which follows as a corollary to Theorem~\ref{thm:TongZhangIRM} and Lemma~\ref{lemma:psistar}:
\begin{restatable}{theorem}{TongZhangCor}
	\label{cor:TongZhangIRM}
	Suppose that there exist a convex function $\psi\colon \mathbb{R}_{\geq0} \rightarrow \mathbb{R}$ satisfying $\psi(0)=\psi^{\prime}(0)=0$, such that 
	\begin{align}\label{eq:AssumptionStar}
	\sup_{w \in \cW} \left[L_{\mu}(w)-M_{\beta}(w)\right]\leq \frac{\psi(\beta)}{\beta},\, \forall\beta>0. 
	\end{align}
	Then, under the setting of Theorem~\ref{thm:TongZhangIRM},
	with probability of at least $1-\delta$ over the choice of $S \sim\mu^{\otimes{n}}$, for all distributions ${P} \ll Q$ over $\cW$ (even such that depend on $S$), we have 
	\begin{align}\label{eq:TongZhangHighProbBoundOpt}
	\mathbb{E}_{{P}} [\mathrm{g}(W,S)] &\le \frac{1}{n\beta }\left(D({P}\|Q)+\ln \frac{1}{\delta}\right)+\frac{\psi(\beta)}{\beta}.
	\end{align}
	Moreover, we have the following bound in expectation: 
	\begin{align}\label{eq:TongZhangExpBoundOpt}
	\mathbb{E}_{SW} [\mathrm{g}(W,S)] &\le \psi^{*-1}\left(\frac{D({P}\|Q|P_S)}{n}\right).
	\end{align}
\end{restatable}
By the golden formula \eqref{eq:goldenformulaMI}, 
under the oracle prior $Q^{\star}=\mathbb{E}_S[P_{W|S}]$, $\mathbb{E}_S[D({P}\|Q^{\star})]=I(S;W)$. 
If $\ell(w,Z)$ is $\sigma$-sub-Gaussian under $\mu$ for all $w\in\cW$, then we can take $\psi(\beta)=\tfrac{\beta^2\sigma^2}{2}$ for every $\beta > 0$ and $\psi^{*-1}(y)=\sqrt{2\sigma^2y}$ \cite[\S 2.3]{boucheron2013concentration},
in which case we recover the bound in expectation due to Xu and Raginsky \cite{generalizationRaginsky}: 
\begin{corollary}\label{cor:XuRaginsky}
	If $\ell(w,Z)$ is $\sigma$-sub-Gaussian under $\mu$ for all $w\in\cW$, then $$\mathbb{E}_{SW} [\mathrm{g}(W,S)] \le \sqrt{2\sigma^2 I(S;W)/n}.$$
\end{corollary}

Corollary \ref{cor:XuRaginsky} shows that an algorithm that reveals a small amount of information about its input generalizes well. 
This observation, for instance, forms the basis for the Gibbs algorithm, which can be thought of as ``stabilizing'' the empirical risk minimization (ERM) algorithm by controlling the input-output mutual information $I(S;W)$ \cite{generalizationRaginsky}.
We discuss extensions of this idea in Section \ref{sec:ICM}. In Appendix \ref{sec:SFRL}, we highlight a functional characterization of the mutual information in relation to the ``single-draw'' generalization bound due to \cite{generalizationRaginskyBassily}.

For a $(\sigma,c)$-sub-gamma under $\mu$, we can take $\psi(\beta)=\tfrac{\beta^2\sigma^2}{2(1-\beta c)}$ for every $\beta$ such that $\beta \in \left(0,\tfrac{1}{c}\right)$ and $\psi^{*-1}(y)=\sqrt{2\sigma^2y}+cy$ \cite[\S 2.4]{boucheron2013concentration}, which gives the following result:
\begin{corollary}\label{cor:subgammaMI}
	If $\ell(w,Z)$ is $(\sigma,c)$-sub-gamma under $\mu$ for all $w\in\cW$, then $$\mathbb{E}_{SW} [\mathrm{g}(W,S)] \le \sqrt{2\sigma^2 I(S;W)/n}+cI(S;W)/n.$$
\end{corollary}
Fixing $\beta=1$ in \eqref{eq:TongZhangHighProbBoundOpt}, we recover \cite[Corollary 5]{FlatminimaBayesianSGDGermainMackay1992}:
\begin{corollary}\label{thm:PACBayesSubGamma}
	Consider the setting in Theorem~\ref{thm:TongZhangIRM}. If the loss $\ell$ is $(\sigma,c)$-sub-gamma with $c < 1$, then with probability of at least $1-\delta$ over the choice of $S \sim\mu^{\otimes{n}}$, for all distributions ${P} \ll Q$ over $\cW$, $$\mathbb{E}_{{P}} [\mathrm{g}(W,S)]\le \frac{1}{n}\left(D({P}\|Q)+ \ln\frac{1}{\delta}\right) + \frac{\sigma^2}{2(1-c)}.$$
\end{corollary}
The condition $c < 1$ guarantees that $\beta =1\in \left(0,\tfrac{1}{c}\right)$ when the sub-gamma condition in Proposition~\ref{Prop:logmgfProperties} item \emph{8)} is satisfied. 
In the limit $c\to 0_+$, a sub-gamma loss reduces to the sub-Gaussian loss \cite[\S 2.4]{boucheron2013concentration}, and we recover \cite[Corollary 4]{FlatminimaBayesianSGDGermainMackay1992}.

For the sub-Gaussian loss, fixing $\beta=1/\sqrt{n}$ in \eqref{eq:TongZhangHighProbBoundOpt}, the second term ${\psi(\beta)}/{\beta}$ decays with increasing $n$, but then the first term will have a slower decay of $1/\sqrt{n}$ instead of $1/n$.

We can also optimize $\beta$ in \eqref{eq:TongZhangHighProbBoundOpt} at a small cost using the union bound:
\begin{restatable}{proposition}{PACUnionBound}\label{thm:PACUnionboundMIsubGaussian}
	Consider the setting in Theorem~\ref{thm:TongZhangIRM}. If $\ell(w,Z)$ is $\sigma$-sub-Gaussian under $\mu$ for all $w\in\cW$, then for any constants $\alpha>1$ and $v>0$, and any $\delta\in (0,1]$, for all $\beta\in(0,v]$, with probability of at least $1-\delta$, we have
	\begin{align*
	\mathbb{E}_{{P}} [\mathrm{g}(W,S)]\le 
	\frac{\alpha}{n\beta}\left(D({P}\|Q)+\ln \frac{\log_{\alpha}\sqrt{n}+K}{\delta}\right)+\frac{\beta\sigma^2}{2},
	\end{align*}
	where $K=\max\{\log_{\alpha}\big(\frac{v\sigma}{\sqrt{2\alpha}}\big),0\}+e$.
\end{restatable}


\subsection{The conditional mutual information (CMI) bound} \label{sec:CMIb}
One drawback of the mutual information-based bounds in Corollaries~\ref{cor:XuRaginsky} and \ref{cor:subgammaMI} is that $I(S;W)$ can be unbounded in many practical situations of interest \cite{veeravalli,steinke2020reasoning}. CMI-based bounds \cite{steinke2020reasoning,steinke2020reasoningOpen} address this issue by  conditioning on a superset of the training sample called the \emph{supersample}, in effect, normalizing the information content of each datum to one bit. 
As nicely articulated by Steinke and Zakynthinou \cite{steinke2020reasoning}, intuitively, the difference between the CMI- and MI- based approaches is that between ``recognizing'' vs. ``reconstructing'' the input, given the output of the algorithm. Recognizing the input is formalized by considering a i.i.d.\ supersample $\tilde{Z}\in\cZ^{n\times 2}$ consisting of $n\times 2$ data points, which comprises of $n$ ``true'' input data points mixed with $n$ ``ghost'' data points. A selector variable $U\in \{0,1\}^n$ chooses the input samples from the supersample, uniformly at random. Given the output of the algorithm, CMI then measures how well it is possible to distinguish the true inputs from their ghosts. We note the following definition:
\begin{definition}[{CMI of an algorithm $P_{W|S}$  \cite{steinke2020reasoning}}]\label{def:CMI}
	Let $\mu$ be a probability distribution on $\cZ$ and let $\tilde{Z}\in\cZ^{n\times 2}$ consist of $2n$ i.i.d.\ samples drawn from $\mu$. Let $U=(U_1,\ldots,U_n)\in \{0,1\}^n$ be uniformly random and independent from $\tilde{Z}$ and the randomness of the algorithm. Define $S:=\tilde{Z}_U \in \cZ^n$ by $(\tilde{Z}_U)_i = \tilde{Z}_{i,U_i+1}$ for all $i \in [n]$, i.e., $S$ is the subset of $\tilde{Z}$ indexed by $U$. Then the conditional mutual information (CMI) of an algorithm $P_{W|S}$ w.r.t.\ $\mu$ is  
	\begin{align*
	\CMI{P_{W|S}}{\mu}:=I(W;U|\tilde{Z}).
	\end{align*}
\end{definition}
Since $S$ is a deterministic function of $\tilde{Z} U$, we have $W-\tilde{Z} U - S$. Also $W-S-\tilde{Z} U$ since $W$ depends on $\tilde{Z} U$ only through $S$. Together, this implies $$I(S;W)=I(\tilde{Z} U;W)=I(W;\tilde{Z})+I(W;U|\tilde{Z}).$$
Suppose that we observe the output $W$ and wish to identify $S$ given access to $\tilde{Z}$. For any estimator $\widehat{U} = \xi(W,\tilde{Z})$ of $U$, by Fano's inequality we have
\begin{align*}
	\inf_{\xi}\Pr\big(\xi(W,\tilde{Z}) \neq U\big) \ge 1-\frac{{I(W;U|\tilde{Z})}+\log 2}{n\log 2}.
\end{align*}
$I(W;U|\tilde{Z})$ thus upper-bounds the probability of successfully identifying $U$ from $\widehat{U}$.

In \cite[Theorem 2(1)]{steinke2020reasoning}, it is shown that for a $[0,1]$-valued loss, $$\mathbb{E}_{SW} [\mathrm{g}(W,S)]\le \sqrt{2 \cdot \CMI{P_{W|S}}{\mu}/n}.$$
Unlike the mutual information $I(S;W)$ that can be potentially unbounded, $\CMI{P_{W|S}}{\mu}$ is bounded above by $n\log 2$. 

We give a PAC-Bayesian version of the CMI bound in Proposition~\ref{thm:CMIPACBound01Loss}. 
Let $\bar{U}=(\bar{U}_1,\ldots,\bar{U}_n)$ be a vector obtained by inverting all the bits of $U$, and define $\bar{S}=\tilde{Z}_{\bar{U}}$. $S$ and $\bar{S}$ have a common marginal distribution, $\mu^{\otimes n}$. The algorithm maps the input $S=\tilde{Z}_U$ to a random element $W$ of $\cW$. Since $\bar{S}\independent W$, we can define the generalization error as
$\mathrm{g}(W,{\tilde{Z},U}):=L_{\bar{S}}(W)-L_S(W)$, where $L_{\bar{S}}(w):= \frac{1}{n} \sum_{i=1}^n \ell(w,(\tilde{Z}_{\bar{U}})_i)$, and $L_S(w):= \frac{1}{n} \sum_{i=1}^n \ell(w,(\tilde{Z}_U)_i)$. 
Given a realization of the supersample $\tilde{Z} = \tilde{z}$ and selector variable $U=u$, we write $Q\equiv Q_{W|\tilde{z}}$ 
and 
$P\equiv P_{W|{\tilde{z},u}}$
for, resp., the prior and the posterior distribution. 
Then the following bounds hold 
for all such prior and posterior distributions: 
\begin{restatable}{proposition}{CMIPACBound}\label{thm:CMIPACBound01Loss}
	For any $[0,1]$-valued loss function $\ell$, for any $\beta>0$ and $\delta\in (0,1]$, with probability of at least $1-\delta$ 
	over a draw of {$\tilde{Z},U$} as defined above, 
	we have:
	\begin{align}\label{eq:CMIPACBound01Loss}
	\mathbb{E}_{{P}}[\mathrm{g}(W,{\tilde{Z},U})]
	&\le \frac{1}{n\beta }\left(D({P}\|Q)+\ln \frac{1}{\delta}\right)+\frac{\beta}{2}.
	\end{align}
	Moreover, we have the following bound in expectation: 
	\begin{align}\label{eq:CMIPACBound01LossExpectation}
	\mathbb{E}_{W,{\tilde{Z},U}} [\mathrm{g}(W,{\tilde{Z},U})] \le \sqrt{\frac{2\cdot D({P}\|Q|P_{{\tilde{Z},U}})}{n}}.
	\end{align}
\end{restatable}
Using the same reasoning as earlier, supplanting the associated oracle prior recovers the bound in expectation $\sqrt{2 \cdot \CMI{P_{W|S}}{\mu}/n}$ in \cite[Theorem 2(1)]{steinke2020reasoning}. 

\subsection{Recovering classical PAC-Bayesian bounds} 
\label{sec:CatoniMcAllRecovery}
By Proposition \ref{Prop:logmgfProperties} item \emph{6)}, for a $\{0,1\}$-valued loss, we have $$M_{\beta}(w) = -{\beta}^{-1} \ln \left(1-(1-e^{-\beta})L_{\mu}(w)\right)=:\Phi_{\beta}(L_{\mu}(w)).$$
$\Phi_{\beta}$ is an increasing one-to-one mapping of the unit interval onto itself, and is convex for $\beta > 0$.
The inverse of $\Phi_{\beta}$ is given by $\Phi_{\beta}^{-1}(x)=\tfrac{1-e^{-\beta x}}{1-e^{-\beta}}$, and we recover Catoni's PAC-Bayesian bound:
\begin{restatable}[{Catoni's bound \cite[Theorem 1.2.6]{catonibook}}]{corollary}{catoniD}\label{thm:pacbayesCatoniDiff}
	For any $\{0,1\}$-valued loss $\ell$, any distribution $\mu$, prior $Q\in\cM(\cW)$, any real $\beta >0$, and any $\delta \in (0,1]$, with probability of at least $1 -\delta$ over $S\sim \mu^{\otimes n}$, 
	we have 
	for all ${P}\llQ$ over $\cW$:
	\begin{align*
	\mathbb{E}_{{P}}[L_{\mu}(W)] \le \Phi_{\beta}^{-1}\left\{\mathbb{E}_{{P}}[L_S(W)]+ \frac{1}{n\beta} \left(D({P}\|Q) +\ln\frac{1}{\delta}\right)\right\}.
	\end{align*}
\end{restatable}

Using $1\le {\beta}{(1-e^{-\beta})}^{-1} \le {(1-\tfrac{\beta}{2})}^{-1}$, we have
\begin{align
\mathbb{E}_{{P}}[L_{\mu}(W)] &\le \Phi_{\beta}^{-1}\left\{
\mathbb{E}_{{P}}[L_S(W)] + \frac{1}{n\beta} \left( D({P}\|Q) +\ln\frac{1}{\delta}\right)\right\}\notag\\
&\le \frac{\beta}{1-e^{-\beta}}\left[ \mathbb{E}_{{P}}[L_S(W)]+\frac{1}{n\beta}\left(D({P}\|Q)+\ln \frac{1}{\delta}\right)\right] \label{eq:Catonibound1}\\
&\le \frac{1}{1-\tfrac{\beta}{2}}\left[ \mathbb{E}_{{P}}[L_S(W)]+\frac{1}{n\beta}\left(D({P}\|Q)+\ln \frac{1}{\delta}\right)\right]. \label{eq:McAllesterLinear}
\end{align}
\eqref{eq:Catonibound1} and \eqref{eq:McAllesterLinear} recover, resp., Catoni's \cite[Theorem 1.2.1]{catonibook} and McAllester's ``Linear PAC-Bayes bound'' \cite[Theorem 2]{mcallesterdropout}, where for the latter we additionally require that $\beta < 2$. 

For loss functions bounded in $[0,1]$, we elaborate in Appendix~\ref{sec:PACBayes} on other approximations that lead to several well-known PAC-Bayesian inequalities such as the ``PAC-Bayes-KL inequality'' \cite{seeger2002pac,maurer2004PACBayes}.

\begin{remark}[Related work]
	A variation of the IEI for the special case of the 0-1 loss appears in the monograph by Catoni \cite[Eq.1.2]{catonibook}, and has been rediscovered more recently for the sub-Gaussian loss in \cite{guedjInformationdensitySpectrumBassily2,guedjInformationdensitySpectrumBassily1}. The statements of \cite[Corollary 3, Eq. 20]{guedjInformationdensitySpectrumBassily2} and \cite[Corollary 6, Eq. 95]{guedjInformationdensitySpectrumBassily1} which are analogues of our Proposition \ref{thm:PACUnionboundMIsubGaussian} and Proposition \ref{thm:CMIPACBound01Loss}, Eq. \ref{eq:CMIPACBound01Loss}, resp., are incorrect as they assume that $\beta$ can be optimized ``for free,'' when in fact we have to pay a union bound price for optimizing $\beta$, which is selected \emph{before} the draw of the training sample. 
	We also note two related works that focus exclusively on unifying either PAC-Bayesian bounds for the 0-1 loss  \cite{PACMDLcommunicationcomplexity}, or information-theoretic bounds for the sub-Gaussian loss \cite{DziugaiteRoySGLDSteinkeNIPS2020}.
\end{remark}



\section{Differentially private data-dependent priors}\label{sec:DPPriors}
A PAC-Bayesian bound such as \eqref{eq:TongZhangHighProbBound} stipulates that the prior $Q$ be chosen before the draw of the training sample $S$. $Q$ may depend on the data generating distribution $\mu$ \cite{leverPACBayes}. However, our access to $\mu$ is only through $S$. To have a good control over the KL term in \eqref{eq:TongZhangHighProbBound}, it is desirable that $Q$ be ``aligned'' with the data-dependent posterior ${P}$. One way to achieve this goal is to choose $Q$ based on $S$ in a differentially private fashion so that $Q$ is stable to local perturbations in $S$ \cite{dziugaitediffprivateprior}. We can then treat $Q$ ``as if'' it is independent of $S$. Here, the key quantity of interest is the approximate max-information between the input $S$ and the data-dependent prior. We shall make these notions precise. 

For $\alpha\ge 0$, the \emph{$\alpha$-approximate max-divergence} is defined as $$D_{\infty}^{\alpha}(P\|Q)= \ln \sup_{\cO \subseteq \cX:\,P(\cO)>\alpha} \frac{P(\cO)-\alpha}{Q(\cO)}.$$
The \emph{max-divergence} $D_{\infty}(P\|Q)$ is defined as $D_{\infty}^{\alpha}(P\|Q)$ for $\alpha = 0$. For a pair of variables $(X,Y)$ with joint law $P_{XY}$ and marginals $P_X$ and $P_Y$, the \emph{$\alpha$-approximate max-information} between $X$ and $Y$ is defined as $I_{\infty}^{\alpha}(X;Y) = D_{\infty}^{\alpha}(P_{XY}\|P_X\otimes P_Y)$.
The \emph{max-information} $I_{\infty}(X ; Y)$ is defined to be $I_{\infty}^{\alpha}(X ; Y)$ for $\alpha = 0$. $I_{\infty}(X;Y)$ is an upper bound on the ordinary mutual information $I(X;Y)$ \cite{feldman2015generalization}.
\begin{definition}[Differential Privacy \cite{generalizationRaginskyDworkDiffPrivacyBOOK}]
	For any $\epsilon > 0$ and $\delta\in [0,1]$, an algorithm $P_{W|S}$ is said to be \emph{$(\epsilon,\delta)$-differentially private} if for all pairs of datasets $s,s'\in\cZ^n$ that differ in a single element, 
	$D_{\infty}^{\delta}(P_{W|S=s}\|P_{W|S=s'})\le \epsilon$. The case $\delta=0$ is called pure differential privacy.
\end{definition}
\begin{definition}[{Max-Information of an algorithm \cite{feldman2015generalization}}]\label{def:MaxInfoOfAlgorithm}
	We say that an algorithm $P_{W|S}$ has $\alpha$-approximate max-information of $k$, denoted as $I_{\infty, \mu}^{\alpha}(P_{W|S}, n) \leq k$, if for every distribution $\mu$ over $\cZ$, we have $I_{\infty}^{\alpha}(S;W) \leq k$ when $S\sim \mu^{\otimes n}$. 
\end{definition}
It follows from the definition of $\alpha$-approximate max-information that if an algorithm $P_{W|S}$ has bounded approximate max-information, then we can control the probability of ``bad events'' that may arise as a result of the dependence of the output $W$ on the input $S$ \cite{feldman2015generalization}.
Let $S'\independent W$ be an independent sample with the same distribution as $S$. 
If for some $\alpha\ge 0$, $I_{\infty}^{\alpha}(S;W)= k$, then for any event $\cO\subseteq \cZ^n\times \cW$, we have
\begin{align}\label{eq:MaxInfoDependence}
\Pr((S,W)\in \cO) \le e^k \cdot \Pr((S',W)\in \cO) + \alpha.
\end{align}
Pure differential privacy implies a bound on the approximate max-information:
\begin{theorem}[{Pure differential privacy and $\alpha$-approximate max-information \cite[Theorem 20]{feldman2015generalization}}] \label{thm:max-infoDP}
	If $P_{W|S}$ is an $(\epsilon, 0)$-differentially private algorithm, then $I_{\infty, \mu}(P_{W|S}, n)\le n\epsilon$, and for any $\alpha > 0$, 
	$I_{\infty, \mu}^{\alpha}(P_{W|S}, n) \leq {n\epsilon^2}/{2} + \epsilon\sqrt{{n}\ln ({2}/{\alpha}) /2}$.
\end{theorem}
\begin{remark}\label{rem:max-infoDP}
	The result above is extended to $(\epsilon,\delta)$-differential privacy in \cite[Theorem 3.1]{rogers2016max}: If $P_{W|S}$ is an $(\epsilon,\delta)$-differentially
	private algorithm for $\epsilon \in (0,1/2]$ and $\delta \in (0,\epsilon)$, then for $\alpha =   O(n \sqrt{{\delta}/{\epsilon}})$, $I^\alpha_{\infty,\mu}(\cA, n) = O(n\epsilon^2  + n \sqrt{{\delta}/{\epsilon}})$. 
\end{remark}
\begin{restatable}{proposition}{PACDPPrior}\label{thm:PACDPPrior}
	Consider the setting in Theorem \ref{thm:TongZhangIRM}. Let $Q^0 \in \cK(\cS,\cW)$ be an $(\epsilon, 0)$-differentially private algorithm. 
	Then with probability of at least $1-\delta$ over the choice of $S \sim\mu^{\otimes{n}}$, for all ${P}\in\cM(\cW)$,
	\begin{align*}
	\mathbb{E}_{{P}} [M_{\beta}&(W)] \leq \mathbb{E}_{{P}}[L_S(W)]
	+ \frac{D({P}\|Q^0(S))+f_n(\delta,\epsilon)}{n\beta}.
	\end{align*}
	where $f_n(\delta,\epsilon):=\ln\frac{2}{\delta} + \frac{n\epsilon^2}{2} + \epsilon\sqrt{\frac{n}{2}\ln \frac{4}{\delta}}$.
\end{restatable}
By Remark~\ref{rem:max-infoDP}, the result above can be extended to $(\epsilon,\delta)$-differentially private priors. Proposition~\ref{thm:PACDPPrior} is similar in spirit to the traditional PAC-Bayesian bounds in \cite[Theorem 4.2]{dziugaitediffprivateprior}, and \cite[Eq. 7]{rivasplatapac}, 
which, however, either apply only when the loss is bounded in $[0,1]$, or entails approximating a suitable exponential moment involving the true risk. 
We can also bound the expected generalization error. 
The next result follows from Theorems \ref{thm:max-infoDP} and {\ref{cor:TongZhangIRM}}:
\begin{corollary}\label{cor:PACDPPriorCMI}
	Consider the setting in {Theorem \ref{cor:TongZhangIRM}}. Let $Q^0 \in {\cK(\cS,\cW)}$ be an $(\epsilon, 0)$-differentially private algorithm. Then with probability of at least $1-\delta$ over a draw of the sample $S$, for all ${P}$, we have
	\begin{align*
	\mathbb{E}_{{P}} [\mathrm{g}(W,S)] &\le \frac{D({P}\|Q^0(S))+f_n(\delta,\epsilon)}{n\beta}+{\frac{\psi(\beta)}{\beta}},
	\end{align*}
	where $f_n(\delta,\epsilon):=\ln\frac{2}{\delta} + \frac{n\epsilon^2}{2} + \epsilon\sqrt{\frac{n}{2}\ln \frac{4}{\delta}}$.
\end{corollary}
The main advantage of the max-information formulation is that we can get high probability guarantees at the cost of a $O(n\epsilon^2  + \epsilon\sqrt{n\ln{1/\delta}})$ correction term. This cost is compensated for by a lower KL complexity since the prior is more ``aligned'' with the data-dependent posterior than when chosen independently of the data. 
As is well-known \cite{feldman2015generalization,feldman2018calibrating}, a small mutual information between the data and the prior will not ensure that bad events will happen with low probability.



\section{Information complexity minimization}\label{sec:ICM}
Given any prior $Q$, minimizing the right hand side of \eqref{eq:TongZhangHighProbBound} gives rise to the \emph{Information Complexity Minimization (ICM)} framework \cite{TongZhangPACBayes2006,TongZhangPACBayes2006AnnalsStats}. Concretely, for a given prior $Q$ and hypothesis set $\cG \subseteq \cM(\cW)$, define the \emph{Optimal Information Complexity ($\mathrm{OIC}$)} at a given $\beta$ as 
\begin{align}\label{eq:InfoComplexity}
\mathrm{OIC}_{\cG}^{\beta}:=\inf_{{P}\in\cG}\left\{\mathbb{E}_{{P}}[L_S(W)] + {(n\beta)}^{-1}D({P}\|Q)\right\}.
\end{align}
When $\cG=\cM(\cW)$, applying Lemma~\ref{thm:DVlemmalikeCatoni} to $f(w)=nL_S(w)$, and writing $\beta$ for $n\beta$, we obtain the Gibbs measure, ${P}^{\star}$, in which case the $\mathrm{OIC}$ evaluates to the \emph{(extended) stochastic complexity} \cite{rissanen1998book,yamanishi1998} $$-{\beta}^{-1}\ln \mathbb{E}_{Q} [e^{-\beta L_S(W)}].$$ The latter in turn coincides with the negative log-marginal likelihood for $\beta=1$ and the logarithmic loss function \cite{TongZhangPACBayes2006,TongZhangPACBayes2006AnnalsStats,Barroncover1991}. 

We briefly discuss two practical examples of ICM for learning with neural networks (NNs), namely, PAC-Bayes-SGD \cite{dziugaitenonvacuous} and Entropy-SGD \cite{FlatminimaPratik}, which can be viewed as optimization schemes that search for a ``flat'' minimum of the empirical loss surface \cite{FlatMinimaSchmidhuber}. We also show a PAC-Bayesian bound motivated by an Occam factor argument \cite{FlatMinimaBayesianMackay1992} in relation to flat minima.

\subsection{PAC-Bayes-SGD}\label{sec:PAC-Bayes-SGD}
\emph{PAC-Bayes-SGD} is an approach to computing generalization bounds for overparameterized NN classifiers trained with stochastic gradient descent (SGD) \cite{dziugaitenonvacuous}. These bounds are obtained by \emph{retraining} the network using an objective derived from a PAC-Bayes bound, starting from the solution found by SGD (or in fact any other procedure) for the training loss $L_S(w)$ w.r.t.\ $w$. 
The underlying hypothesis is that SGD finds ``good'' solutions that generalize well on unseen data only if such solutions are surrounded by a large volume of equally good solutions.
The method draws on an earlier work by Langford and Caruana \cite{langfordNotBounding}, and is closely related to the \emph{bits-back argument} due to Hinton and van Camp \cite{HintonBitsBack} (see Appendix \ref{sec:SFRL}). 
We show how Catoni's bound in Corollary~\ref{thm:pacbayesCatoniDiff} can be used to derive a PAC-Bayes-SGD objective. 

Consider a binary classification setting with examples domain $\cZ=\cX\times \{0,1\}$ and loss $\ell\colon\mathbb{R}^k\times\cZ\to\{0,1\}$. Each $w\in\cW$ corresponds to a classifier $f_w\colon\cX \to \{0,1\}$ that can be interpreted as a deterministic NN with parameters in $\mathbb{R}^k$. For trainable parameters $w_{{P}}\in\mathbb{R}^k$, $\gamma\in\mathbb{R}^k_+$, $\lambda\in\mathbb{R}_+$, let $\cG$ be the set of all Gaussian posteriors of the form ${P} = \cN(w_{{P}},\mathrm{diag}(\gamma))$ and let $Q=\cN(w_0,\lambda I_k)$ be a prior centered at a non-trainable random initialization, $w_0\in\mathbb{R}^k$. 
We can use a convex surrogate of the 0-1 loss, and the reparameterization trick $w = w_{{P}}+ \nu \odot \sqrt{\gamma}$, $\nu\sim \cN(0,I_k)$ \cite{blundellBayesbyBackprop} to compute an unbiased estimate of the gradient of the PAC-Bayes bound in Corollary~\ref{thm:pacbayesCatoniDiff} w.r.t.\ the parameters $w_P,\gamma,\lambda$ and $\beta$. 
Computing the expectation $\mathbb{E}_{{P}}[L_S(f_W)]$ is difficult in practice. Instead, we can use a Monte Carlo estimate $\hat{L}_S(f_W)=\tfrac{1}{m}\sum_{i=1}^{m} L_S(f_{W_i})$, where $W_i\overset{\text{i.i.d.}}{\sim}{{P}}$. Then Corollary \ref{thm:pacbayesCatoniDiff} takes the form: For any $\delta,\delta'\in(0,1)$, fixed $\alpha>1$, $c\in (0,1)$, $b\in\mathbb{N}$, and $m,n\in\mathbb{N}$, with probability of at least $1-\delta-\delta'$ over a draw of $S\sim\mu^{\otimes n}$ and $W\sim ({P})^{\otimes m}$, 
\begin{align*
\mathbb{E}_{{P}}[L_{\mu}(f_W)] \le \inf_{{P}\in\cG,\beta>1,\lambda\in (0,c)}&\Phi_{\beta}^{-1}\Big\{\hat{L}_S(f_W)+ \frac{\alpha}{n\beta}D({P}\|Q)\notag+R(\lambda,\beta;\delta,\delta')\Big\},
\end{align*}
where $R=\frac{2\alpha}{n\beta}\ln \left[\frac{\ln \alpha^2\beta n}{\ln \alpha}\right]+\frac{\alpha}{n\beta}\ln\left[\tfrac{\pi^2 b^2}{6\delta}\left(\ln\tfrac{c}{\lambda}\right)^2\right]+\sqrt{\tfrac{1}{2m}\ln\tfrac{2}{\delta'}}$ accounts for the cost of optimizing the parameters $\beta,\,\lambda$, and using the Monte Carlo estimate of the empirical risk. For large $n,\,m$, $R$ is negligible, and the optimization is dominated by the IC term, $\hat{L}_S(f_W)+ \alpha {(n\beta)}^{-1} D({P}\|Q)$.
\subsection{Entropy-SGD}
A related approach is \emph{Entropy-SGD} \cite{FlatminimaPratik}, which directly minimizes the stochastic complexity, $$-{\beta}^{-1}\ln \mathbb{E}_{Q} e^{-\beta L_S(W)}.$$ This, however, entails optimizing the prior $Q$, when ideally $Q$ must be chosen before the draw of the training sample $S$. We can sample $Q$ instead in a differentially private fashion, and this forms the basis of the Entropy-SGLD algorithm \cite{dziugaite2017entropysgd}. For $Q = \cN\big(w,(\beta \gamma)^{-1} I_k\big)$, the stochastic complexity can be equivalently written (up to constant terms) as $$-{\beta}^{-1} \ln \int_{w'\in\mathbb{R}^k}  e^{-\beta\big[ {L_S}\left(w^{\prime}\right)+ \tfrac{\gamma}{2}\|w-w'\|^2\big]} \mathrm{d} w^{\prime},$$ which can be interpreted as a measure of \emph{flatness} of the loss surface that measures the log-volume of low-loss parameter configurations around $w$. 
From the perspective of ICM, both Entropy- and PAC-Bayes- SGD can be viewed as optimization schemes that search for flat minima solutions. 

\subsection{PAC-Bayes and Occam factor}\label{sec:PACOccam}
Lemma \ref{lemma:GibbsLaplaceApprox} gives the form of the optimal posterior under a quadratic approximation of the loss around a local minimizer
\begin{restatable}{lemma}{GibbsLaplaceApprox}\label{lemma:GibbsLaplaceApprox}
	Consider a quadratic approximation of the training loss around a local minimizer $w_{{P}}$, $\tilde{L}_S(w) = \tfrac{1}{2}(w - w_{{P}})^\top H (w - w_{{P}})$ where $H = \nabla^2 L_S(w)\vert_{w=w_{P}}$, a fixed prior $Q = \cN(w_{Q},{\lambda}^{-1}I_k)$, and a posterior distribution of the form ${P} = \cN(w_{{P}},\Sigma_{{P}})$. Then the solution to the convex optimization problem $\min_{\Sigma_{{P}}} \mathbb{E}_{{P}}[\tilde{L}_S(W)] +{(n\beta)}^{-1} D({P}\|Q)$, is given by $\Sigma_{{P}}^{\star} = H_{\lambda}^{-1}$, where $H_{\lambda}:=\left(n\beta H + \lambda I_k\right)$. Here we assume $\lambda>0$ is sufficiently large so that $H_\lambda$ is positive definite. 
\end{restatable}
We can use a posterior of the form ${P} = \cN(w_{{P}},H_{\lambda}^{-1})$ to get the following PAC-Bayesian bound that incorporates second-order curvature information of the training loss:
\begin{restatable}{proposition}{OccamPAC}\label{thm:OccamPAC}
	Let  $\{\lambda_i\}_{i=1}^k$ be the eigenvalues of $H_{\lambda}$ and suppose that $\lambda_i\ge \lambda>0$ for all $i$. Let $Q = \cN(w_{Q},{\lambda}^{-1}I_k)$ be a prior, and let ${P} = \cN(w_{{P}},H_{\lambda}^{-1})$. Then with probability of at least $1-\delta$ over a draw of the sample $S$, we have
	\begin{align}\label{eq:OccamPAC}
	\mathbb{E}_{{P}} [M_{\beta}(W)] &\leq \mathbb{E}_{{P}}[L_S(W)] + \frac{1}{n\beta}\ln \frac{1}{\delta}+ \frac{1}{n\beta}\left(\frac{\lambda}{2}\|w_{Q}-w_{{P}}\|^2+\frac{1}{2}\sum_{i=1}^{k}\ln \frac{\lambda_i}{\lambda}\right).
	\end{align}
\end{restatable}
Notably, the log-ratio term in \eqref{eq:OccamPAC}, $$\frac{1}{2}\sum_{i=1}^{k}\ln \frac{\lambda_i}{\lambda}=-\ln \sqrt{\det \tfrac{\lambda}{H_{\lambda}}}$$ is the negative logarithm of the \emph{Occam factor} \cite{FlatMinimaBayesianMackay1992,FlatminimaBayesianSGDMackay1992,energyentropycompetition}. The Occam factor can be interpreted as the fraction of the prior parameter space that is consistent with the training data. The log-Occam factor is the differential entropy associated with a Gaussian posterior with scaled covariance $\lambda (H_{\lambda})^{-1}$, and can be interpreted as the amount of information we gain about the model's parameters after seeing the training data. From the perspective of ICM, minimizing the right hand side of \eqref{eq:OccamPAC} w.r.t. the posterior leads to solutions with higher entropy and hence wider minima.


\section{Discussion}
We presented a unified treatment of PAC-Bayesian and information-theoretic generalization bounds starting from a fundamental information-theoretic inequality. Besides recovering several well-known bounds in the literature, we also obtained new bounds for data-dependent priors and unbounded loss functions. The bounds we studied are along the notion that bounded information (between the training data and the output hypothesis) implies learning. On the other hand, it is known that learning does \emph{not} imply bounded information \cite{generalizationRaginskyBassily,generalizationRaginskyBassily2}. In particular, the information revealed by a learning algorithm about its input can be unbounded even for hypothesis classes of VC dimension~1.  A result in a similar vein appears in the PAC-Bayesian framework \cite{feldmanAlonLimitationsPACBayes}. Identifying the common structural properties of these negative results in the information-theoretic and PAC-Bayesian frameworks is an important avenue for further investigation.


\section*{Acknowledgment}
This project has received funding from the European Research Council (ERC) under the EU's Horizon 2020 research and innovation programme (grant agreement n\textsuperscript{o} 757983).


\bibliographystyle{IEEEtran}
