\documentclass{article}

\usepackage{array}

\usepackage[nonatbib,final]{neurips_2020}
\usepackage[numbers]{natbib}%

\usepackage[utf8]{inputenc} %
\usepackage[T1]{fontenc}    %
\usepackage{hyperref}       %
\usepackage{url}            %
\usepackage{booktabs}       %
\usepackage{amsfonts}       %
\usepackage{nicefrac}       %
\usepackage{microtype}      %


\usepackage{graphicx}
\newcommand{\theHalgorithm}{\arabic{algorithm}}
\usepackage{amssymb}
\usepackage{amsmath} %
\usepackage{mathtools} %
\usepackage{latexsym}
\usepackage{amsthm}%
\usepackage{bbm}%
\usepackage[space]{grffile} %

\usepackage{wrapfig}
\usepackage{caption}
\usepackage{subcaption}

\makeatletter
\newtheorem*{rep@theorem}{\rep@title}
\newcommand{\newreptheorem}[2]{%
	\newenvironment{rep#1}[1]{%
		\def\rep@title{#2 \ref{##1}}%
		\begin{rep@theorem}}%
		{\end{rep@theorem}}}
\makeatother
\newreptheorem{theorem}{Theorem}
\newreptheorem{lemma}{Lemma}

\newtheorem{mathdef}{Definition}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}
\newtheorem{exmp}{Example}[section]


\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}
\makeatletter
\newcommand{\distas}[1]{\mathbin{\overset{#1}{\kern\z@\sim}}}%
\newsavebox{\mybox}\newsavebox{\mysim}
\newcommand{\distras}[1]{%
	\savebox{\mybox}{\hbox{\kern3pt$\scriptstyle#1$\kern3pt}}%
	\savebox{\mysim}{\hbox{$\sim$}}%
	\mathbin{\overset{#1}{\kern\z@\resizebox{\wd\mybox}{\ht\mysim}{$\sim$}}}%
}
\makeatother
\DeclareRobustCommand{\bbone}{\text{\usefont{U}{bbold}{m}{n}1}}
\DeclareMathOperator{\EX}{\mathbb{E}}%
\DeclareMathOperator{\Indicator}{\mathbbm{1}}%
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\fracslash}[2]{\left.#1\middle/#2\right.} %
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand\independent{\protect\mathpalette{\protect\independenT}{\perp}}
\def\independenT#1#2{\mathrel{\rlap{$#1#2$}\mkern2mu{#1#2}}}

\DeclarePairedDelimiterX{\infdivx}[2]{(}{)}{%
	#1\;\delimsize\|\;#2%
}
\newcommand{\divergence}{D\infdivx}
\newcommand{\KLdiv}{\text{KL}\infdivx}

\newcommand{\slfrac}[2]{\left.#1\middle/#2\right.} %

\newcommand\thickbar[1]{\accentset{\rule{.4em}{.8pt}}{#1}}

\raggedbottom %

\title{Conditioning and Processing: Techniques to Improve Information-Theoretic Generalization Bounds}


\author{%
	Hassan Hafez-Kolahi
	%
	%
	%
	\\
	Department of Computer Engineering\\
	Sharif University of Technology\\
	%
	\texttt{hafez@ce.sharif.edu} \\
	%
	\And
	Zeinab Golgooni \\
	Department of Computer Engineering \\
	Sharif University of Technology  \\
	%
	\texttt{golgooni@ce.sharif.edu} \\
	\AND
	Shohreh Kasaei \\
	Department of Computer Engineering \\
	Sharif University of Technology  \\
	\texttt{kasaei@sharif.edu} \\
	\And
	Mahdieh Soleymani Baghshah \\
	Department of Computer Engineering \\
	Sharif University of Technology  \\
	\texttt{soleymani@sharif.edu} \\
	%
	%
	%
	%
	%
}

\begin{document}
	
	\maketitle
	
	\begin{abstract}
		Obtaining generalization bounds for learning algorithms is one of the main subjects studied in theoretical machine learning. In recent years, information-theoretic bounds on generalization have gained the attention of researchers. This approach provides an insight into learning algorithms by considering the mutual information between the model and the training set. In this paper, a probabilistic graphical representation of this approach is adopted and two general techniques to improve the bounds are introduced, namely conditioning and processing. In conditioning, a random variable in the graph is considered as given, while in processing a random variable is substituted with one of its children. These techniques can be used to improve the bounds by either sharpening them or increasing their applicability. It is demonstrated that the proposed framework provides a simple and unified way to explain a variety of recent tightening results. New improved bounds derived by utilizing these techniques are also proposed.
		
		
		
		%
	\end{abstract}
	
	\section{Introduction}\label{sec:introduction}
	Bounding the generalization gap is one of the most studied problems in theoretical machine learning.
	Classically, uniform bounds on the hypothesis set were one of the most popular techniques in understanding the generalization gap, but they are not always sufficient. In particular that's the case for deep neural networks \citep{ZhangUnderstandingdeeplearning2017}. 
	Recently there has been a line of research 
	trying to reason about the generalization gap by bounding the mutual information between the dataset and the learned model \citep{RussoHowmuchdoes2015,raginsky2016information,RussoControllingbiasadaptive2016,BassilyLearnersthatUse2018,AsadiChainingMutualInformation2018,steinke_reasoning_2020}. Such bounds consider the details of the algorithm used to generate the model according to the dataset, providing new opportunities to take into account the specific dynamics involved in each learning algorithm. In particular, this idea can be used in studying deep neural networks \citep{negrea2019information, AsadiChainingMeetsChain2019,wu2020information}.  There is ongoing research to expand this information-theoretic machinery and to tighten the generalization bounds. \citet{bu_tightening_2019} provided bounds which are based on the mutual information between the model and each individual sample. In another line of work, \citet{AsadiChainingMutualInformation2018} used subgaussian assumption to apply chaining techniques in the information-theoretic framework. An idea which was later used to analyze the layered structure of deep neural networks \citep{AsadiChainingMeetsChain2019}.
	Recently \citet{steinke_reasoning_2020} proposed using a super sample where the training set is selected randomly from it, and computing the mutual information conditioned on this super sample. It was demonstrated how some of the classical tools based on VC-dimension, compression schemes, and differential privacy, can be explained in this new information-theoretic framework. Though in the case of VC theory, the obtained bounds were not tight and have an extra $\log n$ factor, a problem which authors conjectured could be solved. This work was followed by \citet{haghifam_sharpened_2020}, where individual sample bounds and data-dependent bounds were provided in this new setting. 
	
	%
	%
	%
	This paper has two main objectives. Firstly, we try to expand the tool set which is used in the information-theoretic bounds by introducing \emph{conditioning} and \emph{processing} techniques. 
	%
	To make the ideas more accessible, we adapt a probabilistic graphical representation of them (made possible by a slight generalization of the standard approach). Using these techniques we explain how bounds similar to previous tightened results can be found.
	Secondly, we study Chaining Conditional Mutual Information (CCMI) to demonstrate how the conditioning technique can be used to tighten the chaining mutual information of \cite{AsadiChainingMutualInformation2018}, a setting which needs a more elaborate treatment. This brings together the idea of conditioning on a super sample, with the chaining method. We show that this approach eliminates the extra $\log n$ factor which appears in the basic application of the conditioning technique and suggests interesting directions for future work.%
	The proofs of theorems are presented in the supplementary material.

It is worth mentioning that it is also possible to use PAC-Bayesian to derive non-uniform generalization bounds.
%It is worth mentioning that as an alternative to the information-theoretic approach, it is possible to use PAC-Bayesian to derive non-uniform generalization bounds. 
PAC-Bayesian also has been combined with chaining in \cite{audibert2004pac,audibert2007combining}. While there are situations where the PAC-Bayesian and information-theoretic approaches become close together (for example see Section 1.3 of \cite{catoni2007pac}), each of these approaches brings their advantages. 
In particular, in the information-theoretic approach the main focus is on the relation between the learned hypothesis (as a random variable) to other random variables (e.g. dataset), while in PAC-Bayesian the focus is on the relation between two distributions on hypothesis set.
An advantage of the former approach is that it is simpler to bring in various random variables in the picture and mold the bounds accordingly. This plays an important role in next sections where graphical models with multiple random variables are studied (in particular see Section \ref{sec:app:unified_view_on_prev_results}).  
An advantage of the PAC-Bayesian approach is that it explicitly provides bounds that are independent of the data distribution, while this is not the case for the information-theoretic approach (see Section \ref{sec:applicabilityOfTheBounds}).

	%
	%
	
	
	\section{Notation and Preliminaries}
	Capital letters $X$,$Y$, and $Z$ are used for random variables taking values in $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ respectively.
	The  superscripts on distributions and expectations are used to describe conditional distributions, e.g. $P_X^z$ indicates the conditional distribution of $X$ given $Z=z$ and $\EX_X^z[f(X,z)]$ indicate the expectation of $f(X,z)$ based on this distribution. The subscripts in expectations indicate the random variables upon which the expectation is acting. In many cases where these random variables are clear from the context, the subscript is omitted to prevent cluttering the notation. The KL divergence of distribution $P_X$ from $Q_X$ is denoted as $\KLdiv{P_X}{Q_X}=\int \log \frac{P(X)}{Q(X)}dP$. Mutual information is defined as $I(X;Y)=\KLdiv{P_{XY}}{P_X\otimes{P_Y}}$ where $P_X$ and $P_Y$ are marginal distributions of $P_{XY}$. The conditional mutual information is denoted as $I(X;Y|Z)=\EX_Z[I^Z(X;Y)]$ in which for all $z$, $I^z(X;Y)$ is the mutual information on the conditioned distributions $P_{XY}^z$, i.e. $I^z(X;Y)=\KLdiv{P_{XY}^z}{P_X^z\otimes P_Y^z}$.
	Throughout the paper, all logarithms are in natural base and all information-theoretic quantities are in nats.
	
	%
	\section{Conditioning and Processing}
	Let us begin by restating a very useful lemma presented by \cite{XuInformationtheoreticanalysisgeneralization2017}. 
	
	\begin{lemma}[\cite{XuInformationtheoreticanalysisgeneralization2017}]
		\label{lemma:xu2017main}
		Consider random variables $X$ and $Y$ with joint distribution $P_{XY}$ and
		a function $g:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ such that $g(X,Y)$ is $\sigma$-subgaussian under the distribution $P_{\bar{X}\bar{Y}}=P_X\otimes P_Y$\footnote{Recall that a random variable $V$ is $\sigma$-subgaussian if $\log \EX[e^{\lambda(V-\EX[V])}]\le \lambda^2\sigma^2/2$ for all $\lambda\in \mathbb{R}$.}, then
		\begin{equation}
		\abs{ \EX[g(\bar{X},\bar{Y})]-\EX[g(X,Y)]}\le\sqrt{2\sigma^2 I(X;Y)}.
		\end{equation}
	\end{lemma}
	
	%
	\begin{figure}
		\centering
		%
		\includegraphics[width=0.3\textwidth]{Fig1}
		%
		%
		\\\vspace{0.3cm}
		$\abs{ \EX[\bar{G}-G]}\le\sqrt{2\sigma^2 I(X;Y)}$
		\caption{ PGM representation for Lemma \ref{lemma:xu2017main_stochastic}. The direct line between $Y$ and $X$ is used without an arrow to indicate that it can be in either direction. The parameter $\sigma^2$ at the side of node $\bar{G}$ is used to summarize that $\bar{G}$ is $\sigma$-subgaussian.}
		\label{fig:xu2017main_sharedY}
	\end{figure}
	
	%
	
	While in Lemma \ref{lemma:xu2017main} the $\EX[g(\bar{X},\bar{Y})]$ is discussed, the result is also valid for $\EX[g(X,\bar{Y})]$  if $\bar{Y}$ is independent of $X$ since $P_{\bar{X}\bar{Y}}=P_{\bar{X}Y}$. Actually this is the case usually encountered in studying the generalization gap. This is summarized in a Probabilistic Graphical Model (PGM) represented in Fig.~\ref{fig:xu2017main_sharedY} where we defined $G=g(X,Y)$ and $\bar{G}=g(X,\bar{Y})$.  In all the figures, we use the convention that  nodes sharing the same letter in their name (with different accents, e.g. $Y$ and $\bar{Y}$), share the same (conditional) distribution. For example in Fig.~\ref{fig:xu2017main_sharedY} we have $P_Y=P_{\bar{Y}}$ and $P_{\bar{G}}^{X\bar{Y}}=P_G^{XY}$. 
	Note that the random variable $G=g(X,Y)$ in Lemma \ref{lemma:xu2017main} has a deterministic relation with $X$ and $Y$, but the result can be extended to support general stochastic mapping in form of $P_G^{XY}$.
	This is done in Lemma~\ref{lemma:xu2017main_stochastic} where we also  provided a companion tail bound to set the ground for the next steps.
	%
	
	\begin{lemma}
		\label{lemma:xu2017main_stochastic}
		Consider random variables $X,Y,\bar{Y},G$ and $\bar{G}$ with the conditional independences presented in Bayesian network of Fig.~\ref{fig:xu2017main_sharedY}. Also suppose that $P_{\bar{Y}}=P_Y$ and $P_{\bar{G}}^{X,\bar{Y}}=P_{G}^{X,Y}$.
		
		%
		
		
		(a) If the marginal distribution  $P_{\bar{G}}$ is $\sigma$-subgaussian, then
		\begin{equation}
		\abs{ \EX[\bar{G}-G]}\le\sqrt{2\sigma^2 I(X;Y)}.
		\end{equation}
		
		(b) If $P_{\bar{G}}^x$ is $\sigma$-subgaussian for all $x\in\mathcal{X}$, then
		\begin{equation}
		\Pr\left\{u\times(\bar{G}-G)\ge \epsilon\right\} \le\frac{4\sigma^2 (I(X;Y)+1)}{\epsilon^2} \;\;;\;\; u\in\left\{-1,1\right\}.
		\end{equation}
		
	\end{lemma}
	
	
	
	%
	%
	
	
	\emph{Remark:}
	Note that since in part (b) the bounds for $u=-1$ and $u=1$ are the same, using union bound we have
	%
	\begin{equation}
	\Pr\left\{|\bar{G}-G)| \ge \epsilon\right\} \le\frac{8\sigma^2 (I(X;Y)+1)}{\epsilon^2}.
	\end{equation}
	
	
	
	The conditioning and processing are general techniques that can be used to improve information-theoretic bounds such as the ones presented in Lemma \ref{lemma:xu2017main_stochastic}. 
	
	\subsection{Conditioning}
	\begin{lemma}(Conditioning)
		\label{lemma:conditioning}
		Consider random variables $X,Y,Z,H$.
		
		(a) Suppose there is a concave function $b:\mathbb{R_+}\to\mathbb{R}$ which satisfies 
		\begin{equation}
		\forall z\in\mathcal{Z}; \EX^z[H]\le b(I^z(X;Y)),\label{eq:conditioning_requirement}
		\end{equation}
		then 
		\begin{eqnarray}
		\EX[H]&\le& \EX_Z[b(I^Z(X;Y))] \label{eq:conditioning_first_ineq}
		\\
		&\le& b(I(X;Y|Z)). \label{eq:conditioning_second_ineq}
		\end{eqnarray}
		
		
		(b) Suppose there is a function $\delta:\mathbb{R_+}\times \mathbb{R}\to\mathbb{R}$ which is concave on its first argument and satisfies  $$\forall z\in\mathcal{Z},\epsilon\in\mathbb{R_+}; \Pr\nolimits^z[H\ge\epsilon]\le \delta(I^z(X;Y), \epsilon),$$ then 
		\begin{eqnarray}
		\Pr[H\ge\epsilon]&\le& \delta(I(X;Y|Z), \epsilon).
		\end{eqnarray}
	\end{lemma}
	
	
	
	%
	\begin{figure}
		\centering
		\begin{subfigure}[b]{0.4\textwidth}
			\centering
			\includegraphics[width=0.7\textwidth]{Fig2}
			\newline \\
			$\abs{\EX[\bar{G}-G]} \le \sqrt{2\sigma^2 I(X;Y|Z)}$
			\caption{}
			\label{fig:conditioning}
		\end{subfigure}
		\hfill
		\begin{subfigure}[b]{0.4\textwidth}
			\centering
			\includegraphics[width=0.7\textwidth]{Fig3}
			\newline \\
			$ \abs{ \EX[\bar{G}-G]}\le\sqrt{2\sigma^2 I(T;V)} $
			\caption{}
			\label{fig:processing}
		\end{subfigure}
		\hfill
		\caption{PGM representation of (a) conditioning and (b) processing. The gray background is used to indicate that a random variable is conditioned.}%
		\label{fig:coditioning_processing_techniques}
	\end{figure}
	
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	
	%
	
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	
	
	%
	
	In simple words, Lemma~\ref{lemma:conditioning} states that if we have a concave information-theoretic bound which is valid in a conditioned setting, there is an accompanying bound on the unconditioned setting which depends on the conditional mutual information. 
	For example by considering $H=\bar{G}-G$, Lemma~\ref{lemma:conditioning}  can be used in conjunction with Lemma~\ref{lemma:xu2017main_stochastic} in cases that $\bar{Y}$ is not independent of $Y$, but for some random variable $Z$ there is the conditional independence $\bar{Y}\independent{Y}|Z$ (see Fig.~\ref{fig:conditioning}). Though it should be noted that even in the case where  $\bar{Y}$ and $Y$ are independent, if $I(X;Y|Z)\le I(X;Y)$, this lemma can be used to achieve tighter bounds. Conditioning does not necessarily decrease mutual information. The next theorem 
	summarizes some conditions which guarantee that  conditioning will not increase the mutual information (see Corollaries of Theorem 2.8.1 in \cite{CoverElementsinformationtheory2012}).
	
	\begin{theorem}[\cite{CoverElementsinformationtheory2012}]
		\label{theorem:when_conditioning_decreases_MI}
		If the random variables $X,Y$ and $Z$ form a Markov chain (in any order), then
		\begin{equation}
		I(X;Y|Z)\le I(X;Y).
		\end{equation}
	\end{theorem}
	%
	%
	%
	
	In the Bayesian network representation, the condition of Theorem~\ref{theorem:when_conditioning_decreases_MI} is satisfied if the sub-network representing independences of $X$, $Y$ and $Z$ contains no v-structure.
	%
	
	
	
	\subsection{Processing}
	%
	%
	In many cases there are auxiliary random variables $T$ and $V$ which are generated from $X$ and $Y$ respectively and are the only ingredients needed to find $G$.
	%
	In such cases the bound can be rewritten to use $T,V$ instead of $X,Y$. 
	This is made precise in the next lemma.
	
	\begin{lemma}{(Processing)}\label{theorem:processing}
		Consider random variables $X,Y,\bar{Y},G,\bar{G},V,\bar{V}$ and $T$ with the conditional independences presented in the Bayesian network of Fig.~\ref{fig:processing}. Also suppose that $P_{\bar{Y}}=P_Y$, $P_V^Y=P_{\bar{V}}^{\bar{Y}}$ and $P_{\bar{G}}^{T,\bar{V}}=P_{G}^{T,V}$.
		%
		
		(a) If the marginal distribution  $P_{\bar{G}}$ is $\sigma$-subgaussian, then
		\begin{equation}
		\abs{ \EX[\bar{G}-G]}\le\sqrt{2\sigma^2 I(T;V)}.
		\end{equation}
		
		(b) If $P_{\bar{G}}^t$ is $\sigma$-subgaussian for all $t\in\mathcal{T}$, we have
		\begin{equation}
		\Pr\left\{u\times(\bar{G}-G)\ge \epsilon\right\} \le\frac{4\sigma^2 (I(T;V)+1)}{\epsilon^2} \;\;;\;\; u\in\left\{-1,1\right\}.
		\end{equation}
		
		%
		%
		%
		%
	\end{lemma}
	
	%
	We call this transformation "processing" as it moves away from $(X,Y)$ to $G$ by preprocessing $(T,V)$. This is demonstrated in Fig.~\ref{fig:processing}. While processing is a simple application of Lemma~\ref{lemma:xu2017main_stochastic} on $T$ and $V$, this identification as a separate step, makes it simpler to follow the reasoning when the problem gets complicated (we will encounter such problems in section \ref{sec:unified_view_on_prev_results}). Note that processing can not increase the bound because of information processing inequality.
	
	\emph{Remark:} Processing can be combined with conditioning, if the conditions are satisfied in case $Z$ is given, e.g. if $G\independent X,Y | T,V,Z$ then $\abs{ \EX[\bar{G}-G]}\le\sqrt{2\sigma^2 I(T;V|Z)}$.
	
	%
	
		
	\subsection{Applicability of the Bounds} \label{sec:applicabilityOfTheBounds}
	One thing to note about information-theoretic bounds is that even if one can show that a resulting bound is sharper, it does not necessarily mean that it is more applicable. The reason is that the information-theoretic bounds rely on the distribution of data, which is usually unknown. 
	Thus, it should be noted that the real benefit of the proposed techniques is to make it possible to easily transform the bounds, without loosening them, until the situation is ready to have a distribution independent bound or a quantity which is easy to estimate. The problems discussed in next sections demonstrate the applicability of these techniques in practice.%
	
	
	
\section{Some Applications of Conditioning and Processing}
	Recently there has been a series of papers trying to improve the information-theoretic generalization bounds \citep{BassilyLearnersthatUse2018,bu_tightening_2019,steinke_reasoning_2020,haghifam_sharpened_2020}.In Section \ref{sec:unified_view_on_prev_results} it is demonstrated that it is possible to achieve similar bounds by simple application of conditioning and processing steps. The result is a unified and simple framework to study these bounds, demonstrating the potential of the proposed techniques.
	%
	In Section 	\ref{sec:VC_basic} it is demonstrated how basic bounds based on VC-dimension can be obtained. 
	
	\subsection{A Unified View on Information-Theoretic Generalization Bounds}
	\label{sec:unified_view_on_prev_results}
	Consider learning problem where the training set $S=\{(x_j,y_j)\}_{j=1}^n\distas{}\mu^{\otimes n}$ is given and the learned hypothesis $W\in \mathcal{W}$  is generated by conditional distribution $P_W^S$. We use $S_j$ to denote the $j$th sample of $S$.  The loss of hypothesis $w$ on the sample $(x,y)$ is represented by $\ell(w,(x,y))$.  Generalization gap of hypothesis $w$ is the  difference between the expected loss and the average loss on training set
	\begin{equation}
	\text{gen}(w)=\EX_{XY}[\ell(w,(X,Y))]-\frac{1}{n}\sum_{j=1}^{n}\ell(w,S_j).
	\end{equation}
	One subject of interest is expected generalization gap, $\text{gen}(\mu,P_W^S)\triangleq\EX_W[\text{gen}(W)]$. 
	 This can be described in various ways each describing a special Bayesian network, providing a variety of opportunities to use the conditioning and processing steps to derive new bounds. These are described in the following series of equations.
	

	

	\begin{eqnarray}
	\text{gen}(\mu,P_W^S)
	%
	&=& \EX_{S,S',W}[\frac{1}{n} \sum_{j=1}^n\ell(W,S'_j) - \frac{1}{n} \sum_{j=1}^n\ell(W,S_j) ] \label{eq:gen_base}\\
	&=& \EX_{S,S',W,J}[\ell(W,S'_J)-\ell(W,S_J)] \label{eq:gen_givenJ}.
	\end{eqnarray}
	In these equations $S'\distas{} \mu^{\otimes n}$ is an independent copy of $S$ working as test set. In the second equation an auxiliary random variable $J$ is introduced which is uniformly distributed on $\{1,\dots , n\}$. These equations can be further expanded by utilizing an alternative approach to generate datasets $S$ and $S'$. Suppose $S^{(1)}$ and $S^{(2)}$ are two sets of $n$ i.i.d. samples from $\mu$ and the binary random variable $U_j$ is uniformly distributed on $\{-1,1\}$ (Rademacher distribution) and defines whether the $j$th training sample is selected from $S^{(1)}$ or $S^{(2)}$, i.e. 
	\begin{equation}
	S_j=\left\{\begin{matrix}
	S^{(1)}_j&U_j=-1
	\\ 
	S^{(2)}_j&U_j=1
	\end{matrix}\right.
	\;\;\;\;\;\;
	;
	\;\;\;
	S'_j=\left\{\begin{matrix}
	S^{(2)}_j&U_j=-1
	\\ 
	S^{(1)}_j&U_j=1
	\end{matrix}\right.
	.
	\end{equation}
	We have
	\begin{eqnarray}
	\text{gen}(\mu,P_W^S)
	&=& \EX_{S^{(1)},S^{(2)},U,W}[\frac{1}{n} \sum_{j=1}^n\ell(W,S'_j) - \frac{1}{n} \sum_{j=1}^n\ell(W,S_j) ] 
	\label{eq:gen_givenS0S1} 
	\\
	&=& \EX_{S^{(1)},S^{(2)},U,W,J}[\ell(W,S'_J)-\ell(W,S_J)] 
	\label{eq:gen_givenS0S1J}
	\\
	&=& \EX_{S^{(1)},S^{(2)},U,W,J}[U_J(\ell(W,S^{(1)}_J)-\ell(W,S^{(2)}_J))]
	\label{eq:gen_givenS0S1J_rademacher}.
	\end{eqnarray}
	The required ingredients for the following discussion is that for all $w$ the loss function $L_w=\ell(w,(X,Y))$ is $\sigma_\ell$-subgaussian\footnote{Recall that if a random variable $L$ satisfies $a\le L \le b$, it is $\slfrac{(b-a)}{2}$-subgaussian.}. 
	Define $L_j=\ell(W,S_j)$ and $L_j'=\ell(W,S'_j)$. Also define the averages $R=\slfrac{1}{n}\sum_{j=1}^nL_j$ and  $R'=\slfrac{1}{n}\sum_{j=1}^nL'_j$.
	 Note that  $R'$ is $\slfrac{\sigma_\ell^2}{n}$-subgaussian since $L'_j$s are independent.%
	
	In Table \ref{table:summary_of_gen_bound} it is demonstrated how the previous techniques can be applied to study generalization in practice. To do that the graphical model representing each of the equations (\ref{eq:gen_base}), (\ref{eq:gen_givenJ}), (\ref{eq:gen_givenS0S1}) and (\ref{eq:gen_givenS0S1J}) are represented in the first column. 
	In each diagram, the nodes with gray background are conditioned. As usual, the (conditional) distribution of nodes sharing the same base name are the same (e.g. $P_{\bar{U}}=P_U$ and $P_{\bar{R}}^{\bar{S}W}=P_R^{SW}$).
	
	The first row corresponds to the original case. Usage of Lemma~\ref{lemma:xu2017main} by \cite{XuInformationtheoreticanalysisgeneralization2017} to bound the generalization gap was based on this formulation. The tail bound was studied in \cite{BassilyLearnersthatUse2018}.	
	The individual sample bound of the second row  is the main subject of paper \cite{bu_tightening_2019} where they show that this technique could result in much sharper bounds compared to the basic bound and the chaining bound of \cite{AsadiChainingMutualInformation2018}. Applications on noisy iterative learning algorithms were  also proposed. In the third row, a set of indices $\mathcal{J}$ of size $m$ is conditioned, which is one of the inequalities presented in \cite{negrea2019information}. 
	The fourth row correspond to the setting where super sample is given, which was recently studied by \cite{steinke_reasoning_2020} and various applications were considered. The fifth row is individual sample variant of the fourth one, proposed by \cite{haghifam_sharpened_2020}.
	
	
	
	 In the checklist column, the necessary independence requirements which were validated to find the bounds are listed.  The conditioned variables are denoted as $Z$. For fourth and fifth rows were the $Z=(S^{(1)},S^{(2)})$ are given, the requirement that $S'\independent S|Z$ is no longer satisfied, thus an auxiliary random variable $\bar{S}$ is introduced in a way that guarantees $\bar{S}\independent S'|Z$. This results to bounds for $\EX[\bar{R}-R]$ and $\EX[\bar{L}-L]$ which is not the same as  $\text{gen}(\mu,P_W^S)=\EX[R'-R]=\EX[L'-L]$ that we were looking for. 
	 For tail bounds, there is actually one more difficulty. The %
	 quantity $\Pr\{R'-R\ge\epsilon\}$ is not the same as the usual quantity of interest $\Pr\{\text{gen}(w)\ge \epsilon\}$ 
	 %
	 (i.e. the generalization gap estimated by using a test set of size $n$ is not the same as true generalization gap, even though it is an unbiased estimator). This is as far as we can get by just using the general techniques of processing and conditioning to understand the problem. Fortunately, the usual bounds of interest, differ from these bounds by small constant factors. This is further discussed in the supplementary material (see Theorems
	 \ref{theorem:correcting_tailbound_base} and 	 \ref{theorem:correcting_bounds_super_sample}). 
	
	Note that the bounds derived in rows 2 to 5 are improved versions of the first row. The Individual Sample Mutual Information (ISMI) bound of the second row is shown to be always tighter than the basic bound of the first row \cite{bu_tightening_2019}. 
	%
	Similarly, the conditional mutual information $I(U;W|S^{(1)},S^{(2)})+1)$ present in the fourth row has been shown to be never larger than $I(S;W)$ \cite{haghifam_sharpened_2020}. The amount of improvement achieved by these techniques can be quite large. Actually, there are cases where the
	basic bound based on 
	%
	$I(S;W)$ is infinite while the improved bounds are finite \cite{bu_tightening_2019,steinke_reasoning_2020,haghifam_sharpened_2020}. The bound provided in the fifth row is shown to be a further tightened variant of the third row \cite{haghifam_sharpened_2020}. 
	
		One of the main applications of information-theoretic generalization bounds is to study
	%
	Stochastic Gradient Langevin Dynamics (SGLD).
	%
	In SGLD there is a series of models $W_{(1)},\dots ,W_{(T)}$. At each step $t$, a training sample $S_{U_{(t)}}$ is sampled, where $U_{(t)}\in\{1, \dots, n\}$ denotes the random index, and noisy gradient descent is used to find $W_{(t)}$ by the update rule 
	$$ W_{(t)} = W_{(t-1)} - \eta_{(t)} \nabla \ell(W_{(t-1)},S_{U_{(t)}}) + \sigma_{(t)}\xi,$$
	where $\eta_{(t)}$ is step size, $\xi$ is noise (usually a Gaussian random variable) and $\sigma_{(t)}$ controls the strength of noise at time step $t$.  This noise addition can control the amount of information stored in $W_{(t)}$ from the sample set. Consequently, information-theoretic generalization bounds can be used to bound the generalization gap. This was the idea first used by \cite{pensia_generalization_2018} to study SGLD generalization based on $I(S;W)$, which was followed by a series of tightening results using the conditional variants of the bounds \cite{bu_tightening_2019,negrea2019information,haghifam_sharpened_2020}.
	
	%
	
	
	%
	
	%
	
	
	%
	\begin{table}
		\caption{Summary of Sharpened Information-Theoretic Generalization Bounds.}
		\label{table:summary_of_gen_bound}
		\centering
		\begin{tabular}{>{\centering\arraybackslash}m{3.5cm}m{2.3cm}m{6.2cm}m{0.4cm}}
			\toprule
			%
			%
			Diagram & Checklist     & Transformations / Bounds &    \\
			\midrule
			\includegraphics[width=0.25\textwidth]{Fig4}
			\label{fig:first_bound}
			&
			\vspace{-0.75cm}
			%
			$S'\independent S$\newline
			$S'\independent W$
			& 
			\vspace{-0.3cm}
			{$ |\EX[R'-R]|\le \sqrt{\frac{2\sigma_\ell^2}{n}I(S;W)}$}
			\newline
			{$ \Pr\left\{R'-R\ge \epsilon\right\} \le\frac{4\sigma_\ell^2 (I(S;W)+1)}{n\epsilon^2}$}
			
			&
			\vspace{-0.75cm}
			\cite{XuInformationtheoreticanalysisgeneralization2017}
			\\		
			\vspace{0.2cm}
			\includegraphics[width=0.25\textwidth]{Fig5}
			\label{fig:gen_givenJ}
			&
			\vspace{-1cm}
			%
			%
			$S'\independent S|Z$ \newline
			$S'\independent W|Z$ \newline
			$L\independent S|S_JW$\newline
			& 
			\vspace{-0.7cm}
			Condition: $J$ \newline
			Process: $S\to S_J$\newline
			\newline
			{$  |\EX[L'-L]| \le \frac{1}{n} \sum_{j=1}^n{\sqrt{2\sigma_\ell^2I(S_j;W)}} $} 
			
			&
			\vspace{-0.75cm}
			\cite{bu_tightening_2019}
			\\
			%
			\vspace{0.7cm}
			\includegraphics[width=0.25\textwidth]{Fig_new0}
			\label{fig:gen_givenJ}
			&
			\vspace{-1cm}
			%
			%
			$S'\independent S|Z$ \newline
			$S'\independent W|Z$ \newline
			$R_\mathcal{J}\independent S |S_\mathcal{J}W$\newline
			%
			& 
			\vspace{-0.9cm}
			Condition: $\mathcal{J}$ \newline
			Process: $S\to S_\mathcal{J}$\newline
			\newline
			{$  |\EX[R'_\mathcal{J}-R_\mathcal{J}]| \le {\sqrt{2\frac{\sigma_\ell^2}{m}I(S_\mathcal{J};W)}} $} 
			&
			\vspace{-0.75cm}
			\cite{negrea2019information}			
			\\
			%
			%
			\includegraphics[width=0.25\textwidth]{Fig6}
			\label{fig:gen_givenS0S1}
			&
			\vspace{-1cm}
			%
			%
			$\bar{S}\independent S|Z$ \newline
			$\bar{S}\independent W|Z$ \newline
			
			& 
			\vspace{-0.7cm}
			Condition: $S^{(1)},S^{(2)}$ \newline\newline
			{$ |\EX[\bar{R}-R]|\le \sqrt{\frac{2\sigma_\ell^2}{n}I(U;W|S^{(1)},S^{(2)})}$} 
			\newline
			{$ \Pr\left\{\bar{R}-R\ge \epsilon\right\} \le\frac{4\sigma_\ell^2 (I(U;W|S^{(1)},S^{(2)})+1)}{n\epsilon^2}$}                
			&
			\vspace{-0.75cm}
			\cite{steinke_reasoning_2020}
			\\
			%
			%
			\includegraphics[width=0.27\textwidth]{Fig7}
			\label{fig:gen_givenJS0S1}
			&
			\vspace{-1cm}
			%
			%
			%
			$\bar{S}\independent S|Z$ \newline
			$\bar{S}\independent W|Z$ \newline
			$L\independent S|S_JW$\newline
			
			
			%
			%
			%
			%
			&
			\vspace{-0.7cm}
			%
			Condition: $S^{(1)},S^{(2)},J$ \newline
			
			Process: $S\to S_J$\newline
			\newline
			{$ |\EX[\bar{L}-L]| \le  \sqrt{2\sigma_\ell^2I(U_J;W|S^{(1)},S^{(2)},J)} $} 
			
			&
			\vspace{-0.75cm}
			\cite{haghifam_sharpened_2020}
			\\		
			\bottomrule
		\end{tabular}
	\end{table}
	
	\subsection{VC-dimension}
	\label{sec:VC_basic}
	In case of binary classification with zero-one loss $\ell(w,(x,y))=\Indicator(w(x)\ne y)$, bounds similar to those obtained in VC theory can be retrieved by conditioning on the super sample $S^{(1)},S^{(2)}$. The set of  dichotomies of $\mathcal{W}$ on the set $S$ is defined as $D_\mathcal{W}(S)\triangleq \{(w(S_j))_{j=1}^n \;|\; w\in\mathcal{W}\}$. Now since $S^{(1)},S^{(2)}$ is given, suppose a fixed ordering on $D_\mathcal{W}(S^{(1)}\cup S^{(2)})$ and define $K_W$ as the index of $(W(S_j))_{j=1}^n$ in this ordering.
	$W$ can be processed to $K_W$, since knowing $K_W$ and the target set $S\subset S^{(1)}\cup S^{(2)}$ is enough to calculate the error. 
	%
	Now note that 
	$$I^{S^{(1)},S^{(2)}}(S;K_W)\le H^{S^{(1)},S^{(2)}}(K_W)\le \log(\sup_{S^{(1)},S^{(2)}}|D_\mathcal{W}(S^{(1)}\cup S^{(2)})|)\le 1+d_\text{vc}(\mathcal{W})\log n,$$
	where $d_\text{vc}(\mathcal{W})$ is the VC-dimension of $\mathcal{W}$. 
	%
	The last inequality is based on the well known exponential relation between the VC-dimension and the growth function  $\Pi_\mathcal{W}(2n)=\sup_{S^{(1)},S^{(2)}}|D(S^{(1)}\cup S^{(2)})|$(see for example Section 2.1.3 of \cite{Abu-MostafaLearningdatashort2012}). Finally by noticing that zero-one loss is $1/2$-subgaussian, we have %
	\begin{equation}
	%
	|\EX[R'-R]|\le \sqrt{\frac{2\sigma_\ell^2}{n}I(S;K_W|S^{(1)},S^{(2)})}\le \sqrt{\frac{1+d_\text{vc}(\mathcal{W})\log n}{2n}},
	\end{equation}
	and
	\begin{equation}
	\Pr\left\{R'-R\ge \epsilon\right\} \le\frac{4\sigma_\ell^2 (I(S;K_W|S^{(1)},S^{(2)})+1)}{n\epsilon^2}\le\frac{2+d_\text{vc}(\mathcal{W})\log n}{n\epsilon^2}.
	\end{equation}
	We know that these bounds are not tight since there is an extra $\log n$ term which is not present in the tightest bound provided in VC theory. In the next section we will see how to overcome this.
	
	A similar result based on conditioning the super sample is presented by \cite{steinke_reasoning_2020}, but their setting does not allow processing and thus that approach does not work for all learning algorithms. More precisely, the results of \cite{steinke_reasoning_2020} show that for each hypothesis class with finite $VC$-dimension, there exists an Empirical Risk Minimizer (ERM) which its generalization can be explained by just conditioning the super sample. This is also demonstrated that there are other ERMs which does not have this property.  %
	They also conjectured that the $\log n$ factor can be removed by going beyond ERMs to find a suitable learning algorithm.
	%
	%
	This is in contrast to the standard results of VC theory which work for all learning algorithms.  
	
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	%
	
	\section{Chaining Conditional Mutual Information}
	\label{sec:CCMI}
	In the previous section, conditioning was used along with the base bound of Lemma~\ref{lemma:xu2017main_stochastic} to achieve tightened results. 
	%
	%
	But it should be noted that the conditioning technique of Lemma~\ref{lemma:conditioning} is a general method applicable to any concave information-theoretic bound.
	In this section, it is demonstrated how
	%
	this technique can be used in combination with the chaining method of \cite{AsadiChainingMutualInformation2018} to make tighter bounds. We call this technique Chaining Conditional Mutual Information (CCMI). We first state an alternative formulation of the chaining mutual information.%
	
	%
	\begin{theorem}\label{theorem:chaining_proposed}
		Assume that $X_{\mathcal{W}}=\{\sqrt{n}\text{gen}(w)\}_{w\in\mathcal{W}}$ is a separable subgaussian process on the bounded metric space $(\mathcal{W},d)$ and the learned hypothesis $W$ is a deterministic function of $X_{\mathcal{W}}$. Consider the sequence of functions $(\Pi_k)_{k=k_1(\mathcal{W})}^\infty$ where $k_1(\mathcal{W})$ is the largest integer that satisfies $2^{-(k_1(\mathcal{W})-1)}\ge \text{diam}(\mathcal{W})$, and for all $k\ge k_1$, $\Pi_k:\mathcal{W}\to\mathcal{W}$ is a function satisfying $d(w,\Pi_k(w))\le 2^{-k};\forall w\in \mathcal{W}$. Define $\tilde{W}_k=\Pi_k(W)$, we have
		\begin{equation}
		\label{eq:chaining_proposed}
		\text{gen}(\mu,P_W^S)\le \frac{1}{\sqrt{n}} 6\sqrt{2}\sum_{k=k_1(\mathcal{W})}^\infty 2^{-k}\sqrt{I(\tilde{W}_k;S)}.
		\end{equation}
	\end{theorem}
	Recall that random process $\{X_t\}_{t\in T}$ on metric space $(T,d)$ is called subgaussian if $E[X_t]=0$ for all $t\in T$ and $X_t-X_s$ is a $d(t,s)$-subgaussian random variable for all $t,s\in T$.
	Separability is a technical assumption defined in the supplementary material and is assumed in the next discussions. 
	There are two differences between Theorem \ref{theorem:chaining_proposed} and the result provided by \cite{AsadiChainingMutualInformation2018}. First of all, it is restated by focusing on the mappings $\Pi_k$, instead of partitions, a modification which makes next discussions simpler. More importantly, the constraint that $\tilde{W}_k$ should be a function of $\tilde{W}_{k+1}$ (enforced in the original formulation by using an "increasing sequence of partitions") is removed. But to do that, it was required to add 
 	 the assumption that the learning algorithm is deterministic (and increase the constant by a factor of 2). %
	%
	%
	The latter modification allows us to separately optimize each term of the sum in (\ref{eq:chaining_proposed}) when trying to find tightest bounds. 
	%
	Let us define the rate-distortion function
	\begin{equation}\label{eq:rate_distortion_of_learning_algorithm}
	R(D)\triangleq\inf_{\Pi:\mathcal{W}\to\mathcal{W}} I(\tilde{W};S); \;\;\; \;\; \text{s.t.} \;\; d(W,\tilde{W})\le D \;\; \text{a.s.},
	%
	\end{equation}
	%
	where $\tilde{W}=\Pi(W)$, we have   
	\begin{equation}\label{eq:gen_controlled_by_RD}
	\text{gen}(\mu,P_W^S)\le \frac{1}{\sqrt{n}}6\sqrt{2}\sum_{k=k_1(\mathcal{W})}^\infty 2^{-k}\sqrt{R(2^{-k})}.
	\end{equation}
	%
	Note that since the algorithms is deterministic, $I(\tilde{W};S)= I(\tilde{W};W)$ and the optimization of (\ref{eq:rate_distortion_of_learning_algorithm}) resembles the setting of rate-distortion theory  (see Chapter 10 of \cite{CoverElementsinformationtheory2012}).\footnote{But note that it differs from the usual setting in which the constraint is on the expected distance and the mappings are stochastic.}
	
	An integral part of the standard method to study empirical process $\{\text{gen}(w)\}_{w\in\mathcal{W}}$ is based on the usage of a super sample $S^{(1)},S^{(2)}$ as was done in Section~\ref{sec:unified_view_on_prev_results} (for example see Chapter 7 of \cite{Handel}). Consider Eq. (\ref{eq:gen_givenS0S1J_rademacher}), we have
	\begin{eqnarray}
	\text{gen}(\mu,P_W^S)
	&=& \EX[\frac{1}{n} \sum_{j=1}^n U_j(\ell(W,S^{(1)}_j)-\ell(W,S^{(2)}_j)) ]
	\end{eqnarray}
	Now note that when $S^{(1)}$ and $S^{(2)}$ are given, for each $w$, the randomness is only in the Rademacher random variables $U=(U_k)_{k=1}^n$. By using  Azuma-Hoeffding inequality, $\{\sqrt{n}\text{gen}(w)\}_{w\in\mathcal{W}}$ is subgaussian with distance function
\begin{equation}
d^{S^{(1)} S^{(2)}}(w,w')\triangleq 
\left[\frac{1}{n}  \sum_{(x,y)\in S^{(1)} \cup S^{(2)}}^n \left(\ell(w,(x,y))-\ell(w',(x,y))\right)^2   \right]^{1/2}.
\end{equation}
	Thus, for fixed and given $S^{(1)}$, $S^{(2)}$, the conditions of Theorem~\ref{theorem:chaining_proposed} are satisfied for $\{\sqrt{n}\text{gen}(w)\}_{w\in\mathcal{W}}$ on space  $(\mathcal{W},d^{S^{(1)} S^{(2)}})$. Now the conditioning lemma, can be used to find the bound on unconditioned case as
	\begin{equation}
	\label{eq:tmp}
	\text{gen}(\mu,P_W^S)\le \frac{1}{\sqrt{n}} \EX_{S^{(1)} S^{(2)}}[6\sqrt{2}\sum_{k=k_1(\mathcal{W})}^\infty 2^{-k}\sqrt{I^{S^{(1)} S^{(2)}}(\tilde{W}_k;S)}].
	\end{equation}
	Note that here $\tilde{W}_k$s can be generated based on the given super sample by solving the optimization
	\begin{equation}
	\label{eq:conditioned_rate_distortion_of_learning_algorithm}
	R^{S^{(1)} S^{(2)}}(D)\triangleq \inf_{\Pi:\mathcal{W}\to\mathcal{W}} I^{S^{(1)} S^{(2)}}(\tilde{W};S); \;\;\; \;\; \text{s.t.} \;\; d^{S^{(1)} S^{(2)}}(W,\tilde{W})\le D \;\; \text{a.s.}.
	\end{equation}
	Dependence on the super sample is the main difficulty of this definition. One way to resolve this is to define the uniform bound of
	\begin{equation}
	\label{eq:rate_distortion_of_learning_algorithm_uniform_on_conditioned}
	R_U(D)\triangleq \sup_{S^{(1)} S^{(2)}} R^{S^{(1)} S^{(2)}}(D),
	\end{equation}
	which can be used in (\ref{eq:gen_controlled_by_RD}) to control generalization. 
	
	Next theorem which is based on \cite{dudley1978central} shows that $R_U(D)$ can be controlled by $d_{\text{vc}}(\mathcal{W})$.%
	\begin{theorem}\label{theorem:VC_and_R_U}
		%
		Suppose $\mathcal{W}$ has VC-dimension $d_{\text{(vc)}}(\mathcal{W})$ and  $\ell(w,(x,y))=\Indicator(w(x)\ne y)$. There is a universal constant $C$ such that the following bound holds on $R_U(D)$ defined in (\ref{eq:rate_distortion_of_learning_algorithm_uniform_on_conditioned})
		\begin{equation}
		R_U(D)\le C d_{\text{(vc)}}(\mathcal{W}) \log(\frac{C}{D}).
		\end{equation}
	\end{theorem}
	
	Using this theorem with (\ref{eq:tmp})  we have 
	\begin{equation}
	\text{gen}(\mu,P_W^S)\le \frac{1}{\sqrt{n}}6\sqrt{2}\sum_{k=k_1(\mathcal{W})}^\infty 2^{-k}\sqrt{R_U(2^{-k})}=C' \sqrt{\frac{d_{\text{(vc)}}(\mathcal{W})}{n}},
	%
	\end{equation}
	for a universal constant $C'$. This eliminates the previous extra $\log n$ factor and provides the optimal rate of $\mathcal{O}(n^{-1/2})$.
	
Note that the real benefit of conditioning and processing techniques is to easily transform the information-theoretic bounds without resorting to applying the uniform bound. 
As such, it should be emphasized that the real highlight of this section was introduction of rate-distortion function $R(D)$ and its conditioned counterpart $R^{S^{(1)} S^{(2)}}(D)$ (equations~(\ref{eq:rate_distortion_of_learning_algorithm}) and (\ref{eq:conditioned_rate_distortion_of_learning_algorithm})), i.e. before applying the final uniform bound. 
Also, note that it is rather straightforward to combine CCMI with other ideas from Section \ref{sec:unified_view_on_prev_results} (e.g. by conditioning on both super sample and random index).
This is an advantage of the information-theoretic framework over the PAC-Bayesian approach, as was discussed in Section \ref{sec:introduction}.
%(e.g. \cite{audibert2004pac,audibert2007combining}) other non uniform approaches such as 
%Also note that it rather straightforward to combine CCMI 
%with the other ideas from Section \ref{sec:unified_view_on_prev_results} (e.g. by conditioning on the random index)
%is rather 
% Analyzing these objects is an interesting direction for future study.
These subjects provide interesting directions for future study.

	%
	

	\section{Conclusion}
	In this paper two techniques to improve information-theoretic generalization bounds were studied. Utilizing a probabilistic graphical representation, it was demonstrated that these techniques provide a simple machinery to reason about the generalization gap and to tighten information-theoretic bounds. Then the conditioning technique was used in conjunction with the method of chaining mutual information as a next step toward understanding the generalization gap in the context of information theory. It was demonstrated how using this technique the bounds based on VC-dimension can be achieved. The developed theory to achieve this result introduced some interesting subjects for further study. %
	
	
\section*{Broader Impact}
As a theoretical work, the direct foreseeable impact is on the academic community. In particular, in the field of machine learning, this work should be viewed along a series of works trying to understand learning algorithms from the lens of information theory. The unified framework introduced in this paper provides an intuitive and convenient way to derive tighter generalization bounds. This can increase the ability of researchers to apply information theory to derive bounds for their learning algorithms and to easily communicate their ideas. These contributions have the potential to boost the ongoing paradigm shift toward an information-theoretic understanding of machine learning.
It should also be noted that the studied techniques are not limited to deriving generalization bounds, which is evident from the quite general structure of graphical models and techniques. As such, these kinds of graphical representations along the conditioning and chaining techniques may find their way to be used in other fields beside learning theory as well.





	\begin{ack}
	There are no financial conflicts of interest to disclose.
	\end{ack}

	
	%
\bibliographystyle{plainnat}
	%
	%
	%
	\bibliography{WholeLibrary_BetterBibTex.bib}
	
	
\appendix

\pagebreak

\section*{Appendices}

\appendix

\makeatletter
\@addtoreset{theorem}{section}
\@addtoreset{equation}{section}
\@addtoreset{table}{section}
\makeatother




\renewcommand*{\thetheorem}{\Alph{section}.\arabic{theorem}}
\renewcommand*{\thelemma}{\Alph{section}.\arabic{lemma}}

\renewcommand\thetable{\Alph{section}.\arabic{table}}    
\renewcommand\theequation{\Alph{section}.\arabic{equation}}


\section{Proof of Lemma \ref{lemma:xu2017main_stochastic}}

\begin{figure}[h]
	\centering
	%
	\includegraphics[width=0.3\textwidth]{Fig1}
	%
	%
	\caption{ PGM representation for Lemma \ref{lemma:xu2017main_stochastic}.}
	\label{fig:app:xu2017main_sharedY}
\end{figure}



\begin{replemma}{lemma:xu2017main_stochastic}
	Consider random variables $X,Y,\bar{Y},G$ and $\bar{G}$ with the conditional independences presented in the Bayesian network of Fig.~\ref{fig:app:xu2017main_sharedY}. Also suppose that $P_{\bar{Y}}=P_Y$ and $P_{\bar{G}}^{X,\bar{Y}}=P_{G}^{X,Y}$.
	
	%
	
	
	(a) If the marginal distribution  $P_{\bar{G}}$ is $\sigma$-subgaussian, then
	\begin{equation}
	\abs{ \EX[\bar{G}-G]}\le\sqrt{2\sigma^2 I(X;Y)}.
	\end{equation}
	
	(b) If $P_{\bar{G}}^x$ is $\sigma$-subgaussian for all $x\in\mathcal{X}$, then
	\begin{equation}
	\Pr\left\{u\times(\bar{G}-G)\ge \epsilon\right\} \le\frac{4\sigma^2 (I(X;Y)+1)}{\epsilon^2} \;\;;\;\; u\in\left\{-1,1\right\}, \epsilon\in{\mathbb{R_+}}.
	\end{equation}
	
\end{replemma}
\begin{proof}
	For Part (a), a slight modification of proof of Lemma 1 in \cite{XuInformationtheoreticanalysisgeneralization2017} is used.
	Based on the Donsker–Varadhan variational representation of the relative entropy, for any two distributions $\pi$ , $\rho$ on a common measurable space $(\Omega,\mathcal{F})$ we have 
	\begin{equation}
	\KLdiv{\pi}{\mu}=\sup_F \left\{\int_\Omega F d\pi - \log \int _\Omega e^F d\rho \right\}
	\end{equation}
	where supremum is over all measurable functions $F:\Omega\to \mathbb{R}$, such that $e^F\in L^1(\rho)$. 
Consider the distribution $\pi=P_{XYG}=P_{XY} \otimes P_G^{XY}$ and let $\mu=P_{X\bar{Y}\bar{G}}=P_X\otimes P_Y \otimes P_G^{XY}$.
Note that  $\EX[G]$ and $\EX[\bar{G}]$ are calculated based on $\pi$ and $\mu$, respectively. 
	Define the function $f(x,y,g)=g$. For all $\lambda\in \mathbb{R}$, we have
	\begin{eqnarray}
	\KLdiv{\pi}{\mu} &\ge& \EX[\lambda f(X,Y,G)] -\log \EX[e^{\lambda f(X,\bar{Y},\bar{G})}]\nonumber
	\\
	&=& \lambda (\EX[G]-\log{\EX[e^{\lambda \bar{G}}]}) \nonumber
	\\
	&\ge& \lambda (\EX[G]-\EX[\bar{G}]) - \frac{\lambda^2 \sigma^2}{2}, \label{eq:app:parabola}
	\end{eqnarray}
	where the final inequality is due to the $\sigma$-subgaussian assumption on $P_{\bar{G}}$
	$$\log \EX[e^{\lambda(G-\EX[G])}]\le \lambda^2\sigma^2/2; \;\;\; \forall \lambda\in \mathbb{R}.$$
	The inequality (\ref{eq:app:parabola}) gives a nonnegative parabola in $\lambda$. For the inequality to hold for all $\lambda$, the discriminant of this parabola must be nonpositive. This implies that 
	\begin{equation}
	\abs{\EX[\bar{G}]-\EX[{G}]}\le \sqrt{2\sigma^2 \KLdiv{\pi}{\mu}}.
	\end{equation}
	Now noting that 
	\begin{eqnarray}
	\KLdiv{\pi}{\mu} &=& \KLdiv{P_{XY} \otimes P_G^{XY}}{P_X\otimes P_Y \otimes P_G^{XY}} \\
	&=&\KLdiv{P_{XY}}{P_X\otimes P_Y }\\
	&=& I(X;Y)
	\end{eqnarray}
	concludes the proof of Part (a).
	
	To prove Part (b), first consider that $u=1$, for $u=-1$ the proof follows similarly. Let us first restate a lemma from \cite{BassilyLearnersthatUse2018}.
	\begin{lemma}[\cite{BassilyLearnersthatUse2018}] \label{lemma:Bassily_prob_bound}
		Let $\pi$  and $\mu$ be distributions on a set $\Omega$ and let $E\subseteq\Omega$. Then, 
		\begin{equation}
		\pi(E)\le \frac{\KLdiv{\pi}{\mu}+1}{\log ({1/\mu(E)})}.
		\end{equation}
	\end{lemma}
	%
	
	Proving Part (b) requires a stronger technique based on an auxiliary distribution.
	Let $\pi$ be the distribution presented in Fig.~\ref{fig:app:xu2017main_sharedY}, 
	i.e. $\pi=P_{XYG\bar{Y}\bar{G}} =P_{XY}\otimes P_{G}^{XY} \otimes P_Y \otimes P_{G}^{XY}$. Consider another distribution $\mu$ which is similar to $\pi$ 
	except that the link between $X$ and $Y$ is severed, i.e. $\mu=P_{X'Y'G'\bar{Y'}\bar{G'}} =P_{X}\otimes P_{Y}\otimes P_{G}^{XY} \otimes P_Y \otimes P_{G}^{XY}$. Note that again we have $\KLdiv{\pi}{\mu}=I(X;Y)$. 
	
	Let $H'=\bar{G'}-G'$ and $E$ be the event that $H'\ge \epsilon$. To find $\mu(E)$, note that when $X'=x'$ is given, $G'$ and $\bar{G'}$ are independent random variables each having the same distributions as $P_{\bar{G}}^x$. As this distribution is assumed to be $\sigma$-subgaussian, for an arbitrary $x'\in\mathcal{X}$, we have
	\begin{equation}
	\EX^{x'}[e^{\lambda(\bar{G'}-G' -(\EX^{x'}[\bar{G'}-G']))}]=\EX^{x'}[e^{\lambda(\bar{G'}-\EX^{x'}[\bar{G'}])}]\EX^{x'}[e^{\lambda(G'-\EX^{x'}[G'])}]\le e^{\lambda^2\sigma^2}; \forall \lambda\in \mathbb{R}.
	\end{equation}
	This means that the conditional distribution $P_{H'}^{x'}$ is subgaussian with the variance proxy $2\sigma^2$. Also note that $\EX^{x'}[\bar{G'}-G']=0$. Now,  by using the well known fact that the tail of any subgaussian distribution around its mean, is dominated by the Gaussian distribution with the same variance proxy, we have
	\begin{equation}
	\Pr\nolimits^{x'}\{H'\ge\epsilon\}\le e^{-\frac{\epsilon^2}{4\sigma^2}}.
	\end{equation}
	Since this is valid for all $x'$, by taking expectation from both sides we have
	\begin{equation}
	\mu(E)=\Pr\{H'\ge\epsilon\}=\EX_{X'}[\Pr\nolimits^{X'}\{H'\ge\epsilon\}]\le e^{-\frac{\epsilon^2}{4\sigma^2}}.
	\end{equation}
	Now that a bound on $\mu(E)$ is found, Lemma~\ref{lemma:Bassily_prob_bound} can be used to control $\pi(E)=\Pr\{\bar{G}-G\ge \epsilon\}$. We have
	\begin{equation}
	\pi(E)\le \frac{\KLdiv{\pi}{\mu}+1}{\log ({1/\mu(E)})}\le \frac{4\sigma^2 (I(X;Y)+1)}{\epsilon^2}.
	\end{equation}
\end{proof}



\section{Proof of Lemma \ref{lemma:conditioning}}
\begin{replemma}{lemma:conditioning}(Conditioning)
	Consider random variables $X,Y,Z,H$.
	
	(a) Suppose there is a concave function $b:\mathbb{R_+}\to\mathbb{R}$ which satisfies 
	\begin{equation}
	\forall z\in\mathcal{Z}; \EX^z[H]\le b(I^z(X;Y)),\label{eq:app:conditioning_requirement}
	\end{equation}
	then 
	\begin{eqnarray}
	\EX[H]&\le& \EX_Z[b(I^Z(X;Y))] \label{eq:app:conditioning_first_ineq}
	\\
	&\le& b(I(X;Y|Z))]. \label{eq:app:conditioning_second_ineq}
	\end{eqnarray}
	
	
	(b) Suppose there is a function $\delta:\mathbb{R_+}\times \mathbb{R}\to\mathbb{R}$ which is concave on its first argument and satisfies 
	%
	 $$\forall z\in\mathcal{Z},\epsilon\in\mathbb{R_+}; \Pr\nolimits^z[H\ge\epsilon]\le \delta(I^z(X;Y), \epsilon),$$ then 
	\begin{eqnarray}
	\Pr[H\ge\epsilon]&\le& \delta(I(X;Y|Z), \epsilon).
	\end{eqnarray}
\end{replemma}

\begin{proof}
	%
	
	(a)
	Note that $E[H]=E_Z[E^Z[H]]$. Since inequality~(\ref{eq:app:conditioning_requirement}) holds for all $z\in \mathcal{Z}$, by taking expectation on $Z$ from the random upper bound $b(I^Z(X;Y))$, the  inequality~(\ref{eq:app:conditioning_first_ineq}) is achieved. Inequality (\ref{eq:app:conditioning_second_ineq}) is a consequence of the concavity of $b$, the Jensen's inequality, and the definition of conditional mutual information.
	
	(b) This part follows similarly by noting that for any event $E$ we have 
	$\EX_Z [\Pr^Z \left\{ E  \right\}]=\Pr \left\{ E  \right\}.$
	%
	%
	%
	%
	%
\end{proof}

\section{Proof of Theorem~\ref{theorem:when_conditioning_decreases_MI}}
\begin{reptheorem}{theorem:when_conditioning_decreases_MI}[\cite{CoverElementsinformationtheory2012}]
	If the random variables $X,Y$ and $Z$ form a Markov chain (in any order), then
	\begin{equation}
	I(X;Y|Z)\le I(X;Y). \label{eq:app:decreased_CMI}
	\end{equation}
\end{reptheorem}
\begin{proof}
	Suppose the conditional dependences of $X$,$Y$ and $Z$ satisfies a Markov chain  $V_1 - V_2 -V_3$ where $V_i\in\{X,Y,Z\}$ and $(V_i)_{i=1}^3$ is a specific ordering of $(X,Y,Z)$. The Markov property results in $V_1\independent V_3 |V_2$.
	If $V_2=Z$, $I(X;Y|Z)=I(V_1;V_3|V_2)=0$ has the smallest possible value and thus (\ref{eq:app:decreased_CMI}) is satisfied. If  $V_2\ne Z$ either $V_2=X$ or $V_2=Y$. Because of the symmetry between $X$ and $Y$, it is enough to consider either of these cases and the other follows similarly. Suppose $V_2=X$, i.e. $Z\independent Y |X$. By chain rule of mutual information, the quantity $I(Y;(X,Z))$ can be decomposed in two ways and we have
	\begin{equation}
	I(Y;(X,Z))=I(Y;Z)+I(Y;X|Z)=I(Y;X)+I(Y;Z|X).
	\end{equation}
	Since $I(Y;Z|X)=0$, we have 
	\begin{equation}
	I(X;Y|Z)=I(X;Y) - I(Y;Z).
	\end{equation}
	%
	Thus, (\ref{eq:app:decreased_CMI}) is obtained according to the nonnegativity of $I(Y;Z)$.
\end{proof}


\begin{figure}
	\centering
	\begin{subfigure}[b]{0.4\textwidth}
		\centering
		\includegraphics[width=0.7\textwidth]{Fig3}
		%
		
	\end{subfigure}
	\hfill
	\caption{PGM representation of processing technique.}
	\label{fig:app:processing}
\end{figure}

\section{Proof of Lemma~\ref{theorem:processing}}
\begin{replemma}{theorem:processing}(Processing)
	Consider random variables $X,Y,\bar{Y},G,\bar{G},V,\bar{V}$ and $T$ with the conditional independences presented in the Bayesian network of Fig.~\ref{fig:app:processing}. Also suppose that $P_{\bar{Y}}=P_Y$, $P_V^Y=P_{\bar{V}}^{\bar{Y}}$ and $P_{\bar{G}}^{T,\bar{V}}=P_{G}^{T,V}$.
	%
	
	(a) If the marginal distribution  $P_{\bar{G}}$ is $\sigma$-subgaussian, then
	\begin{equation}
	\abs{ \EX[\bar{G}-G]}\le\sqrt{2\sigma^2 I(T;V)}.
	\end{equation}
	
	(b) If $P_{\bar{G}}^t$ is $\sigma$-subgaussian for all $t\in\mathcal{T}$, we have
	\begin{equation}
	\Pr\left\{u\times(\bar{G}-G)\ge \epsilon\right\} \le\frac{4\sigma^2 (I(T;V)+1)}{\epsilon^2} \;\;;\;\; u\in\left\{-1,1\right\}.
	\end{equation}
	
	%
	%
	%
	%
\end{replemma}
\begin{proof}
	Note that $\bar{V}\independent (T,V)$ and marginal distributions $P_V$ and $P_{\bar{V}}$ are the same, because $P_Y=P_{\bar{Y}}$ and $P_V^Y=P_{\bar{V}}^{\bar{Y}}$. The result easilly is obtained as the conditions of Lemma~\ref{lemma:xu2017main_stochastic} are satisfied for random variables $T,V,\bar{V},G$ and $\bar{G}$.
\end{proof}


\section{A Unified View on Information-Theoretic Generalization Bounds}
\label{sec:app:unified_view_on_prev_results}
In this section results provided in Section~\ref{sec:unified_view_on_prev_results} are proved and discussed. Recall that we assumed for all $w$ the loss function $\ell(w,X)$ is $\sigma_\ell$-subgaussian. For binary classification with zero-one loss $\sigma_\ell=1/2$.
We also defined $L_j=\ell(W,S_j)$ , $L_j'=\ell(W,S'_j)$ , $R=\slfrac{1}{n}\sum_{j=1}^nL_j$ and  $R'=\slfrac{1}{n}\sum_{j=1}^nL'_j$.
Note that  $R'$ is $\slfrac{\sigma_\ell^2}{n}$-subgaussian since $L'_j$s are independent.
The object of interest is generalization gap of hypothesis $w$, which is the  difference between the expected loss and the average loss on training set
\begin{equation}
\text{gen}(w)=\EX_{XY}[\ell(w,(X,Y))]-\frac{1}{n}\sum_{j=1}^{n}\ell(w,S_j).
\end{equation}
We want to have bounds on $\text{gen}(\mu,P_W^S)\triangleq\EX[\text{gen}(w)]$ and $\Pr\{\text{gen}(w)\ge \epsilon\}; \epsilon\in \mathbb{R}_+$.

\subsection{Basic Generalization Bound} \label{sec:app:gen_basic}
\begin{figure}
	\centering
	%
	\includegraphics[width=0.25\textwidth]{Fig4}
	%
	%
	%
	%
	\caption{Basic generalization.}
	\label{fig:app:first_bound}
\end{figure}

Considering the conditional independences presented in Fig.~\ref{fig:app:first_bound}, using Lemma~\ref{lemma:xu2017main_stochastic} directly results in 
\begin{equation}
\text{gen}(\mu,P_W^S)=|\EX[R'-R]|\le \sqrt{\frac{2\sigma_\ell^2}{n}I(S;W)},
\end{equation}
and
\begin{equation}
\Pr\left\{R'-R\ge \epsilon\right\} \le\frac{4\sigma_\ell^2 (I(S;W)+1)}{n\epsilon^2}.
\end{equation}

In Section~\ref{sec:unified_view_on_prev_results}, we saw that $E[R'-R]$ in the original formulation is equal to $\text{gen}(\mu,P_W^S)$. But the situation is different for $\Pr\{\text{gen}(W)\ge \epsilon\}$ because now the variance also matters. Next theorem proves that for the large enough $N$ this difference just introduces a constant factor to the bound.

\begin{theorem} \label{theorem:correcting_tailbound_base}
	If $N\ge \frac{2}{\epsilon^2}$ we have
	\begin{equation}
	\Pr \{\text{gen}(W)\ge \epsilon\} \le 2 \Pr\{R'-R  \ge \epsilon/2 \}.
	\end{equation}
\end{theorem}
\begin{proof}
	The result follows by a standard technique in proving generalization bound that introduces an auxiliary ghost sample set (for example see Appendix A.1 of \cite{Abu-MostafaLearningdatashort2012}). 
	Define $e_\mu(W)=\EX_{XY}[\ell(W,(X,Y))]$. If $\Pr\{e_\mu(W) - R \ge \epsilon\}=0$, the desired inequality holds. Assume $\Pr\{e_\mu(W) - R \ge \epsilon\}>0$, we have 
	\begin{eqnarray}
	\Pr\{R'-R \ge \frac{\epsilon}{2} \} &\ge& \Pr \{ R'-R \ge \epsilon/2 \;\;\text{and}\;\;  e_\mu(W) - R \ge \epsilon  \}
	\nonumber\\
	&=& \Pr \{ R'-R \ge \frac{\epsilon}{2}  \;\; | \;\; e_\mu(W) - R \ge \epsilon  \}  \Pr\{e_\mu(W) - R \ge \epsilon \}
	\nonumber\\
	&\ge& \Pr \{ e_\mu(W) -R' \le \frac{\epsilon}{2} \;\; | \;\; e_\mu(W) - R \ge \epsilon  \}  \Pr\{e_\mu(W) - R \ge \epsilon\}
	\nonumber\\
	&\ge& (1-e^{-\frac{1}{2}\epsilon^2n})  \Pr\{e_\mu(W) - R \ge \epsilon\}.
	\end{eqnarray}
	First inequality holds because taking intersection with another event, does not increase probability. The second inequality is obtained since when $e_\mu(W) - R \ge \epsilon $ and $e_\mu(W) -R' \le \frac{\epsilon}{2} $ it is guaranteed that $R'-R \ge \frac{\epsilon}{2} $. In the final inequality, Hoeffding's bound is used, which is possible because $W$ is independent of $S'$.
\end{proof}

Using Theorem~\ref{theorem:correcting_tailbound_base} we have
$$\Pr \{\text{gen}(W)\ge \epsilon\} \le \frac{32\sigma_\ell^2 (I(S;W)+1)}{n\epsilon^2}.$$




\subsection{Conditioning on Sample Index} %

\begin{figure}
	\centering
	%
	\includegraphics[width=0.25\textwidth]{Fig5}
	%
	%
	%
	%
	%
	%
	%
	\caption{Conditioning on sample index.} %
	\label{fig:app:gen_givenJ}
\end{figure}

Considering  Fig.~\ref{fig:app:gen_givenJ}, by conditioning on $J$, and processing $S\to S_J$ we have
\begin{eqnarray}
\text{gen}(\mu,P_W^S)&=&\EX[L'-L]
\nonumber\\
&\le& \abs{\EX[L'-L]}
\nonumber\\
&\le& \EX_J[\sqrt{2\sigma_\ell^2I(S_J;W)}]
\nonumber\\
&=&\frac{1}{n} \sum_{j=1}^n{\sqrt{2\sigma_\ell^2I(S_j;W)}} \label{eq:app:gen_givenJ_results_expected}
\\
&\le& \sqrt{2\sigma_\ell^2I(S_J;W)}.
\end{eqnarray}
Here it is assumed that $W$ is independent of the order of samples in $S$ and thus $I(S_J;W|J)=I(S_J;W)$. In Section~\ref{sec:unified_view_on_prev_results}, we saw that $\EX[L'-L]$ is one of the equivalent ways to compute $\text{gen}(\mu,P_W^S)$, and no further corrections is needed.




\subsection{Conditioning on the Super Sample}
\begin{figure}
	\centering
	%
	\includegraphics[width=0.25\textwidth]{Fig6}
	%
	%
	%
	%
	%
	\caption{Conditioning on the super sample.}
	\label{fig:app:gen_givenS0S1}
\end{figure}

Considering  Fig.~\ref{fig:app:gen_givenS0S1}, by conditioning on $S^{(1)},S^{(2)}$ we have
\begin{equation}
|\EX[\bar{R}-R]|\le \sqrt{\frac{2\sigma_\ell^2}{n}I(U;W|S^{(1)},S^{(2)})},
\end{equation}
and
\begin{equation} \label{eq:app:gen_givenS0S1_tail}
\Pr\left\{\bar{R}-R\ge \epsilon\right\} \le\frac{4\sigma_\ell^2 (I(U;W|S^{(1)},S^{(2)})+1)}{n\epsilon^2}.
\end{equation}
Note that here we had to use another branch for random variables $\bar{U}$, $\bar{S}$ and $\bar{R}$ to have the required conditional independence. 
Moreover, we assumed that the input distribution $\mu$ is continuous, thus $S^{(1)}\cup S^{(2)}$ is a set of $2n$ distinct random variables. As a result, when $S^{(1)}\cup S^{(2)}$ is given, knowing $S$ is the same as knowing $U$ and $I(S;W|S^{(1)},S^{(2)})=I(U;W|S^{(1)},S^{(2)})$.
Also note that the discussion on Section \ref{sec:unified_view_on_prev_results} demonstrated that the distribution of $R$ and $R'$ is the same as in Section~\ref{sec:app:gen_basic}.
Next theorem shows the relation between the obtained bounds and generalization error.

\begin{theorem}\label{theorem:correcting_bounds_super_sample}
	%
	In the setting represented in Fig.~\ref{fig:app:gen_givenS0S1}, we have 
	\begin{equation}
	\text{gen}(\mu,P_W^S)=2\EX[\bar{R}-R].
	\end{equation}
	Moreover, if zero-one loss is used and $N\ge \frac{64}{\epsilon^2}$, we have
	\begin{equation}
	\Pr \{\text{gen}(W)\ge \epsilon\} \le 4\times\frac{ I(U;W|S^{(1)},S^{(2)})+1}{n(\epsilon/8)^2}
	%
	\end{equation}
	\begin{proof}
		Define $e_\mu(W)=\EX_{XY}[\ell(W,(X,Y))]$ and $e_{\hat{\mu}(W)}=\frac{1}{2n}\sum_{(x_i,y_i)\in S^{(1)},S^{(2)} } \ell(W,(x_i,y_i))$. Note that $e_{\hat{\mu}(W)}=\frac{1}{2}(R+R')$. For expectation of generalization gap, we have 
		\begin{eqnarray}
		\text{gen}(\mu,P_W^S)&=&
		%
		\EX[R'-R]
		\nonumber\\
		&=& \EX[2(e_{\hat{\mu}(W)}-R)
		\nonumber\\
		&=& 2 \EX[\bar{R}-R],
		\end{eqnarray}
		where final equality is due to the fact that $\bar{R}$ is an unbiased estimator for $e_{\hat{\mu}(W)}$, calculated using $n$ samples from $\hat{\mu}$.%
		
		For the tail bound we have
		\begin{eqnarray}
		\Pr \{\text{gen}(W)\ge \epsilon\} &\le& 2 \Pr\{R'-R  \ge \epsilon/2 \}
		\nonumber\\
		&=& 2 \Pr\{e_{\hat{\mu}(W)} -R \ge \epsilon/4 \}
		\nonumber\\
		&=& 2 \Pr\{e_{\hat{\mu}(W)} - \bar{R}) +(\bar{R}-R) \ge \epsilon/4 \}
		\nonumber\\
		&\le& 2 \Pr\{e_{\hat{\mu}(W)} - \bar{R} \ge \epsilon/8 \}+\Pr\{\bar{R}-R \ge \epsilon/8 \}
		\nonumber\\
		&\le& 2 \left(2e^{-2n(\frac{\epsilon}{8})^2}+\Pr\{\bar{R}-R \ge \epsilon/8 \}\right)
		\end{eqnarray}
		First inequality is based on Theorem~\ref{theorem:correcting_tailbound_base}. The next equality is based on the algebraic relation $e_{\hat{\mu}(W)} = \frac{1}{2} (R+R')$. In second inequality we used union bound and the mathematical relation  $A+B\ge c \Rightarrow (A\ge \frac{c}{2}) \vee (B\ge \frac{c}{2})$. In third inequality, Hoeffding's bound for sampling without replacement is used. 
		Now note that for zero-one loss $\sigma_\ell=1/2$ and by using (\ref{eq:app:gen_givenS0S1_tail}), we have
		\begin{equation}
		\Pr\left\{\bar{R}-R\ge \epsilon/8\right\}
		\le\frac{I(U;W|S^{(1)},S^{(2)})+1}{n(\epsilon/8)^2}.
		\end{equation}
		On the other hand, when $N\ge \frac{64}{\epsilon^2}$ we also have
		\begin{equation}
		2e^{-2n(\frac{\epsilon}{8})^2} \le\frac{1}{n(\epsilon/8)^2}.
		\end{equation}
		This inequality can be verified for $N = \frac{64}{\epsilon^2}$. Which means that it is also valid for larger $N$, because l.h.s approaches zero with exponential rate while the r.h.s has slower rate of $\frac{1}{n}$.
		%
		
		Finally, we have 
		\begin{equation}
		2e^{-2n(\frac{\epsilon}{8})^2}+\Pr\{\bar{R}-R \ge \epsilon/8 \}
		\le 2\times\frac{ I(U;W|S^{(1)},S^{(2)})+1}{n(\epsilon/8)^2},
		\end{equation}
		which concludes the proof.
	\end{proof}
\end{theorem}

\subsection{Conditioning on the Super Sample and Index}
\begin{figure}
	\centering
	%
	\includegraphics[width=0.27\textwidth]{Fig7}
	%
	%
	\caption{Conditioning on the super sample and index.}
	\label{fig:app:gen_givenJS0S1}
\end{figure}

Considering  Fig.~\ref{fig:app:gen_givenJ}, by conditioning on $J,S^{(1)},S^{(2)}$, and processing $S\to S_J$ we have
\begin{eqnarray}
|\EX[\bar{L}-L]|  &\le& \EX_J[\sqrt{2\sigma_\ell^2I^J(U_J;W|S^{(1)},S^{(2)})}]
\\
&\le&  \sqrt{2\sigma_\ell^2I(U_J;W|S^{(1)},S^{(2)},J)}
\end{eqnarray}
Note that the same argument which was used in Theorem~\ref{theorem:correcting_bounds_super_sample}, can be used for datasets with one sample to show that $\text{gen}(\mu,P_W^S)=2\EX[\bar{L}-L]$.








\section{Proof of Theorem \ref{theorem:chaining_proposed}}

\begin{mathdef} [Separable process] \label{separable_process}
	The random process $\{X_t\}_{t\in T}$ is called separable if there is a countable set $T_0\subseteq T$ such that $X_t\in \lim_{\substack{s\rightarrow t \\ s\in T_0}} X_s\;$ for all $~t\in T\;$  a.s.,
	where $x\in \lim_{\substack{s\rightarrow t \\ s\in T_0}} x_s$ means that there is a sequence $(s_n)$ in $T_0$ such that $s_n\rightarrow t$ and $x_{s_n}\rightarrow x$.
\end{mathdef}


\begin{reptheorem}{theorem:chaining_proposed}
	Assume that $X_{\mathcal{W}}=\{\sqrt{n}\text{gen}(w)\}_{w\in\mathcal{W}}$ is a separable subgaussian process on the bounded metric space $(\mathcal{W},d)$ and the learned hypothesis $W$ is a deterministic function of $X_{\mathcal{W}}$. 
	Consider the sequence of functions $(\Pi_k)_{k=k_1(\mathcal{W})}^\infty$ where $k_1(\mathcal{W})$ is the largest integer that satisfies $2^{-(k_1(\mathcal{W})-1)}\ge \text{diam}(\mathcal{W})$, and for all $k\ge k_1$, $\Pi_k:\mathcal{W}\to\mathcal{W}$ is a function satisfying $d(w,\Pi_k(w))\le 2^{-k};\forall w\in \mathcal{W}$. Define $\tilde{W}_k=\Pi_k(W)$, we have
	\begin{equation}
	\label{eq:app:chaining_proposed}
	\text{gen}(\mu,P_W^S)\le \frac{1}{\sqrt{n}} 6\sqrt{2}\sum_{k=k_1(\mathcal{W})}^\infty 2^{-k}\sqrt{I(\tilde{W}_k;S)}.
	\end{equation}
\end{reptheorem}
\begin{proof}
This result is based on Theorem 11 of \cite{AsadiChainingMutualInformation2018}. Here it is restated using notations used in current paper.

\begin{theorem}\label{theorem:asadi_original_restate}
Assume that $X_{\mathcal{W}}=\{X_w\}_{w\in\mathcal{W}}$ is a separable subgaussian process on the bounded metric space $(\mathcal{W},d)$. Consider the sequence of functions $(\Pi_k)_{k=k_1(\mathcal{W})}^\infty$ where $k_1(\mathcal{W})$ is the largest integer that satisfies $2^{-(k_1(\mathcal{W})-1)}\ge \text{diam}(\mathcal{W})$, and for all $k> k_1$, $\Pi_k:\mathcal{W}\to\mathcal{W}$ is a function satisfying $d(w,\Pi_k(w))\le 2^{-k};\forall w\in \mathcal{W}$. Define $\tilde{W}_k=\Pi_k(W)$ for $k\ge k_1$ and $\tilde{W}_{k_1-1}=w_0$ for an  arbitrary $w_0\in \mathcal{W}$. We have
\begin{equation}
\EX[X_W]\le 3\sqrt{2}\sum_{k=k_1(\mathcal{W})}^\infty 2^{-k}\sqrt{I(\tilde{W}_{k-1},\tilde{W}_k;X_{\mathcal{W}})}.
\end{equation}
\end{theorem}

Theorem~\ref{theorem:asadi_original_restate} is stated for a general random process. In Theorem~\ref{theorem:chaining_proposed}, we used  $X_W=\{\sqrt{n}\text{gen}(w)\}_{w\in\mathcal{W}}$. 
Moreover, knowing $S$, the values $\{\sqrt{n}\text{gen}(w)\}_{w\in\mathcal{W}}$ are all deterministically calculated. Thus, by data processing inequality $I(\tilde{W}_{k-1},\tilde{W}_k;X_{\mathcal{W}})\le I(\tilde{W}_{k-1},\tilde{W}_k;S)$. Now the only remained part is to remove the dependence in $\tilde{W}_{k-1}$ without resorting to the nested partitioning.  
We have
\begin{eqnarray}
\EX[X_W]&\le& 3\sqrt{2}\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_{k-1},\tilde{W}_k;X_{\mathcal{W}})}
\nonumber\\
&=& 3\sqrt{2}\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_k;X_{\mathcal{W}})+I(\tilde{W}_{k-1};X_{\mathcal{W}}|\tilde{W}_k)}
\nonumber\\
&\le& 3\sqrt{2}\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_k;X_{\mathcal{W}})+I(\tilde{W}_{k-1};X_{\mathcal{W}})}
\label{eq:tmp2}
\\
&\le& 3\sqrt{2}(\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_k;X_{\mathcal{W}})}+\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_{k-1};X_{\mathcal{W}})})
\label{eq:tmp3}
\\
&\le& 3\sqrt{2}(\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_k;X_{\mathcal{W}})}+\sum_{k=k_1-1}^\infty 2^{-(k+1)}\sqrt{I(\tilde{W}_{k};X_{\mathcal{W}})})
\nonumber\\
&\le& 3\sqrt{2}(\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_k;X_{\mathcal{W}})}+\sum_{k=k_1-1}^\infty 2^{-k}\sqrt{I(\tilde{W}_{k};X_{\mathcal{W}})})
\nonumber\\
&\le& 6\sqrt{2}\sum_{k=k_1}^\infty 2^{-k}\sqrt{I(\tilde{W}_{k};X_{\mathcal{W}})}.
\label{eq:tmp4}
\end{eqnarray}
Inequality (\ref{eq:tmp2}) is valid based on Theorem \ref{theorem:when_conditioning_decreases_MI} because $\tilde{W}_{k-1} \independent \tilde{W}_k|X_{\mathcal{W}}$ (which is a consequence of the deterministic relation between $W$ and $X_{\mathcal{W}}$).  In (\ref{eq:tmp3}) we used the mathematical relation $\sqrt{a+b}\le{\sqrt{a}+\sqrt{b}}; \forall a,b\in\mathbb{R}_+$. In final inequality we used $I(w_0;X_{\mathcal{W}})=0$, because $w_0$ is a deterministic value.
\end{proof}

\section{Proof of theorem \ref{theorem:VC_and_R_U}}
\begin{reptheorem}{theorem:VC_and_R_U}
	%
	Suppose $\mathcal{W}$ has VC-dimension $d_{\text{(vc)}}(\mathcal{W})$ and  $\ell(w,(x,y))=\Indicator(w(x)\ne y)$. There is a universal constant $C$ such that the following bound holds on $R_U(D)$ defined in (\ref{eq:rate_distortion_of_learning_algorithm_uniform_on_conditioned})
	\begin{equation}
	R_U(D)\le C d_{\text{(vc)}}(\mathcal{W}) \log(\frac{C}{D}).
	\end{equation}
\end{reptheorem}

\begin{proof}
	%
	%
	 Note that $I^{S^{(1)} S^{(2)}}(\tilde{W}_k,S)\le H(\tilde{W}_k)$, where $H(\tilde{W}_k)$ is the entropy of random variable $\tilde{W}_k$ and is bounded by logarithm of number of possible values it takes. A possible mapping for producing $\tilde{W}$ is to use centers of a $D$-covering. Thus, 
	\begin{equation} \label{eq:R_bounded_by_covering_number}
	R^{S^{(1)} S^{(2)}}(D)\le \log N(\mathcal{W}, d^{S^{(1)} S^{(2)}}, D),
	\end{equation}
	where $N(\mathcal{W}, d^{S^{(1)} S^{(2)}}, D)$ is the covering number of $(\mathcal{W},d)$ at the scale $D$.
	Recall that $d^{S^{(1)} S^{(2)}}(w,w')= 2 \norm{w-w'}_{L^2(\hat{\mu})}$. Here $\hat{\mu}$ is the empirical distribution of the superset and 
	\begin{equation}
	\norm{w-w'}_{L^2(\hat{\mu})}=
	\left[\frac{1}{n}  \sum_{j=1}^n \left(w(x_j)-w'(x_j)\right)^2   \right]^{1/2}.
	\end{equation}
	Now we use the following theorem which is based on \cite{Dudleysizescompactsubsets1967}. %
	\begin{theorem}[Dudley \cite{Dudleysizescompactsubsets1967}]
	There is a universal constant $C$ 	such that 
	$$\sup_\mu N(\mathcal{W}, \norm{.}_{L^2(\mu)}, D)\le \left(\frac{C}{D}\right)^{C d_{\text{(vc)}}(\mathcal{W})}; \;\; \forall D<1.$$
	\end{theorem}
	Using this theorem with inequality (\ref{eq:R_bounded_by_covering_number}) completes the proof.
\end{proof}


\end{document}

