# Generalization Bounds for Noisy Iterative Algorithms
Using Properties of Additive Noise Channels

Hao Wang<EMAIL_ADDRESS>
Harvard University Rui Gao<EMAIL_ADDRESS>
The University of Texas at Austin Flavio P. Calmon<EMAIL_ADDRESS>
Harvard University

###### Abstract

Machine learning models trained by different optimization algorithms under
different data distributions can exhibit distinct generalization behaviors. In
this paper, we analyze the generalization of models trained by noisy iterative
algorithms. We derive distribution-dependent generalization bounds by
connecting noisy iterative algorithms to additive noise channels found in
communication and information theory. Our generalization bounds shed light on
several applications, including differentially private stochastic gradient
descent (DP-SGD), federated learning, and stochastic gradient Langevin
dynamics (SGLD). We demonstrate our bounds through numerical experiments,
showing that they can help understand recent empirical observations of the
generalization phenomena of neural networks.

Keywords: Information theory, algorithmic generalization bound, differential
privacy, stochastic gradient Langevin dynamics, federated learning.

##  1 Introduction

Many learning algorithms aim to solve the following (possibly non-convex)
optimization problem:

$\displaystyle\min_{\bm{w}\in\mathcal{W}}~{}L_{\mu}(\bm{w})\triangleq\mathbb{E}\left[\ell(\bm{w},\textnormal{Z})\right]=\int_{\mathcal{Z}}\ell(\bm{w},\bm{z})\textrm{d}\mu(\bm{z}),$
(1)

where $\bm{w}\in\mathcal{W}\subseteq\mathbb{R}^{d}$ is the model parameter
(e.g., weights of a neural network) to optimize; $\mu$ is the underlying data
distribution that generates Z; and
$\ell:\mathcal{W}\times\mathcal{Z}\to\mathbb{R}^{+}$ is the loss function
(e.g., 0-1 loss). In the context of supervised learning, Z is often composed
by a feature vector X and its corresponding label Y. Since the data
distribution $\mu$ is unknown, $L_{\mu}(\bm{w})$ cannot be computed directly.
In practice, a dataset
$\textnormal{S}\triangleq(\textnormal{Z}_{1},\cdots,\textnormal{Z}_{n})$
containing $n$ i.i.d. points $\textnormal{Z}_{i}\sim\mu$ is used to minimize
an empirical risk:

$\displaystyle\min_{\bm{w}\in\mathcal{W}}~{}L_{\textnormal{S}}(\bm{w})\triangleq\frac{1}{n}\sum_{i=1}^{n}\ell(\bm{w},\textnormal{Z}_{i}).$
(2)

We consider the following (projected) noisy iterative algorithm for solving
the empirical risk optimization in (2). The parameter $\bm{w}$ is initialized
with a random point $\textnormal{W}_{0}\in\mathcal{W}$ and updated using the
following rule:

$\displaystyle\textnormal{W}_{t}=\mathsf{Proj}_{\mathcal{W}}\left(\textnormal{W}_{t-1}-\eta_{t}\cdot
g(\textnormal{W}_{t-1},\\{\textnormal{Z}_{i}\\}_{i\in\mathcal{B}_{t}})+m_{t}\cdot\textnormal{N}\right),$
(3)

where $\eta_{t}$ is the learning rate; N is an additive noise drawn
independently from a distribution $P_{\textnormal{N}}$; $m_{t}$ is the
magnitude of the noise; $\mathcal{B}_{t}\subseteq[n]$ contains the indices of
the data points used at the current iteration and
$b_{t}\triangleq|\mathcal{B}_{t}|$; $g$ is the direction for updating the
parameter (e.g., gradient of the loss function); and

$\displaystyle
g(\textnormal{W}_{t-1},\\{\textnormal{Z}_{i}\\}_{i\in\mathcal{B}_{t}})\triangleq\frac{1}{b_{t}}\sum_{i\in\mathcal{B}_{t}}g(\textnormal{W}_{t-1},\textnormal{Z}_{i}).$
(4)

At the end of each iteration, the parameter is projected onto the domain
$\mathcal{W}$, i.e.,
$\mathsf{Proj}_{\mathcal{W}}(\bm{w})\triangleq\operatorname*{\arg\\!\min}_{\bm{w}^{\prime}\in\mathcal{W}}\|\bm{w}^{\prime}-\bm{w}\|$.
The recursion in (3) is run $T$ iterations and the final output is a random
variable $\textnormal{W}_{T}$.

The goal of this paper is to provide an upper bound for the _expected
generalization gap_ :

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right],$
(5)

where the expectation is taken over the randomness of the training data set S
and of the algorithm.

Noisy iterative algorithms are used in different practical settings due to
their many attractive properties (see e.g., Li et al., 2016; Zhang et al.,
2017; Raginsky et al., 2017; Xu et al., 2018). For example, differentially
private SGD (DP-SGD) algorithm (see e.g., Song et al., 2013; Abadi et al.,
2016), one kind of noisy iterative algorithms, is often used to train machine
learning models while protecting user privacy (Dwork et al., 2006). Recently,
it has been implemented in open-source libraries, including Opacus (Facebook
AI, 2020) and TensorFlow Privacy (Radebaugh and Erlingsson, 2019). The
additive noise in iterative algorithms may also mitigate overfitting for deep
neural networks (DNNs) (Neelakantan et al., 2015). From a theoretical
perspective, noisy iterative algorithms can escape local minima (Kleinberg et
al., 2018) or saddle points (Ge et al., 2015) and generalize well (Pensia et
al., 2018).

The goal of this paper is to derive generalization bounds which can help
understand recent empirical observations that are not explained by uniform
notions of hypothesis class complexity (Vapnik and Chervonenkis, 1971;
Valiant, 1984). For example, a neural network trained using true labels
exhibits better generalization ability than a network trained using corrupted
labels even when the network architecture is fixed and perfect training
accuracy is achieved (Zhang et al., 2016). Distribution-independent bounds may
not be able to capture this phenomenon because they are invariant to both true
data and corrupted data. In contrast, our bounds capture this empirical
observation, exhibiting a lower value on networks trained on true labels
compared to ones trained on corrupted labels (Figure 1). Another example is
that a wider network often has a more favourable generalization capability
(Neyshabur et al., 2014). This may seem counter-intuitive at first glance
since one may expect that wider networks have a higher VC-dimension and,
consequently, would have a higher generalize gap. Our bounds capture this
behaviour and are decreasing with respect to the neural network width (Figure
2).

In this paper, we present three generalization bounds for the noisy iterative
algorithms (Section 4). These bounds rely on different kinds of $f$-divergence
but are proved in a uniform manner by exploring properties of additive noise
channels (Section 3). Among them, the KL-divergence bound can deal with
sampling with replacement; the total variation bound is often the tightest
one; and the $\chi^{2}$-divergence bound requires the mildest assumption. We
apply our results to applications, including DP-SGD, federated learning, and
SGLD (Section 5). Under these applications, our generalization bounds own a
simple form and can be estimated from the training data. Finally, we
demonstrate our bounds through numerical experiments (Section 6), showing that
they can predict the behavior of the true generalization gap.

Our generalization bounds incorporate a time-decaying factor. This decay
factor tightens the bounds by enabling the impact of early iterations to
reduce with time. Our analysis is motivated by a line of recent works (Feldman
et al., 2018; Balle et al., 2019; Asoodeh et al., 2020) which observed that
data points used in the early iterations enjoy stronger differential privacy
guarantees than those occurring late. Accordingly, we prove that if a data
point is used at an early iteration, its contribution to the generalization
gap is decreasing with time due to the cumulative effect of the noise added in
the iteration afterward.

The proof techniques of this paper are based on fundamental tools from
information theory. We first use an information-theoretic framework, proposed
by Russo and Zou (2016) and Xu and Raginsky (2017) and further tightened by Bu
et al. (2020), for deriving algorithmic generalization bounds. This framework
relates the generalization gap in (5) with the $f$-information111The
$f$-information (see (11) for its definition) includes a family of measures,
such as mutual information, which quantify the dependence between two random
variables. $I_{f}(\textnormal{W}_{T};\textnormal{Z}_{i})$ between the
algorithmic output $\textnormal{W}_{T}$ and each individual data point
$\textnormal{Z}_{i}$. However, estimating this $f$-information from data is
intractable since the underlying distribution is unknown. Given this major
challenge, we connect the noisy iterative algorithms with additive noise
channels, a fundamental model used in data transmission. As a result, we
further upper bound the $f$-information by a quantity that can be estimated
from data by developing new properties of additive noise channels. Moreover,
we incorporate a time-decaying factor into our bounds, which enables the
contribution of early iterations on our bounds to decrease with time. This
factor is established by strong data processing inequalities (Dobrushin, 1956;
Cohen et al., 1998) and has an intuitive interpretation: the dependence
between algorithmic output $\textnormal{W}_{T}$ and the data points used in
the early iterations is decreasing with time due to external additive noise
(i.e., $I_{f}(\textnormal{W}_{T};\textnormal{Z}_{i})$ is decreasing with $T$
for a fixed $\textnormal{Z}_{i}$).

###  1.1 Related Works

There are significant recent works which adopt the information-theoretic
framework (Xu and Raginsky, 2017) for analyzing the generalization capability
of noisy iterative algorithms. Among them, Pensia et al. (2018) initially
derived a generalization bound in Corollary 1 and their bound was extended in
Proposition 3 of Bu et al. (2020) for the SGLD algorithm. Although the
framework in Pensia et al. (2018) can be applied to a broad class of noisy
iterative algorithms, their bound in Corollary 1 and Proposition 3 in Bu et
al. (2020) rely on the Lipschitz constant of the loss function, which makes
them independent of the data distribution. Distribution-independent bounds can
be potentially loose since the Lipschitz constant may be large and may not
capture some empirical observations (e.g., label corruption (Zhang et al.,
2016)). Specifically, this Lipschitz constant only relies on the architecture
of the network instead of the weight matrices or the data distribution so it
is the same for a network trained from corrupted data and a network trained
from true data.

To obtain a distribution-dependent bound, Negrea et al. (2019) improved the
analysis in Pensia et al. (2018) by replacing the Lipschitz constant with a
gradient prediction residual when analyzing the SGLD algorithm. Their follow-
up work (Haghifam et al., 2020) investigated the Langevin dynamics algorithm
(i.e., full batch SGLD), which was later extended by Rodríguez-Gálvez et al.
(2020) to SGLD, and observed a time-decaying phenomenon in their experiments.
Specifically, (Haghifam et al., 2020) incorporated a quantity, namely the
squared error probability of the hypothesis test, into their bound in Theorem
4.2 and this quantity decays with the number of iterations. This seems to
suggest that earlier iterations have a larger impact on their generalization
bound. In contrast, our decay factor indicates that the impact of earlier
iterations is reducing with the total number of iterations. Furthermore, the
bound in their Theorem 4.2 requires a bounded loss function while our
$\chi^{2}$-based generalization bound only needs the variance of the loss
function to be bounded. More broadly, Neu et al. (2021) investigated the
generalization properties of SGD. However, the generalization bound in their
Proposition 3 suffers from a weaker order $O(1/\sqrt{n})$ when the analysis is
applied to the SGLD algorithm.

In addition to the works discussed above, there is a line of papers on
deriving SGLD generalization bounds (Mou et al., 2018; Li et al., 2019). Among
them, Mou et al. (2018) introduced two generalization bounds. The first one
(Theorem 1 of Mou et al., 2018), a stability-based bound, achieves $O(1/n)$
rate in terms of the sample size $n$ but relies on the Lipschitz constant of
the loss function which makes it distribution-independent. The second one
(Theorem 2 of Mou et al., 2018), a PAC-Bayes bound, replaces the Lipschitz
constant by an expected-squared gradient norm but suffers from a slower rate
$O(1/\sqrt{n})$. In contrast, our SGLD bound in Proposition 4 has order
$O(1/n)$ and tightens the expected-squared gradient norm by the variance of
gradients. The PAC-Bayes bound in Mou et al. (2018) also incorporates an
explicit time-decaying factor. However, their analysis seems to heavily rely
on the Gaussian noise. In contrast, our generalization bounds include a decay
factor for a broad class of noisy iterative algorithms. A follow-up work by Li
et al. (2019) combined the algorithmic stability approach with PAC-Bayesian
theory and presented a bound which achieves order $O(1/n)$. However, their
bound requires the scale of the learning rate to be upper bounded by the
inverse Lipschitz constant of the loss function. In contrast, we do not need
any assumptions on the learning rate.

A standard approach (see e.g., He et al., 2021) of deriving a generalization
bound for the DP-SGD algorithm follows two steps: (i) prove that DP-SGD
satisfies the $(\epsilon,\delta)$-DP guarantees (Song et al., 2013; Wu et al.,
2017; Feldman et al., 2018; Balle et al., 2019; Asoodeh et al., 2020); (ii)
derive/apply a generalization bound that holds for _any_
$(\epsilon,\delta)$-DP algorithm (Dwork et al., 2015; Bassily et al., 2021;
Jung et al., 2019). However, generalization bounds obtained from this
procedure are distribution-independent since DP is robust with respect to the
data distribution. In contrast, our bounds in Section 5.1 are distribution-
dependent. We extend our analysis and derive a generalization bound in the
setting of federated learning in Section 5.2. A previous work by Yagli et al.
(2020) also proved a generalization bound for federated learning in their
Theorem 3 but their bound involves a mutual information which could be hard to
estimate from data.

The conference version (Wang et al., 2021) of this work investigates the
generalization of the SGLD and DP-SGD algorithms. In this paper, we study a
broader class of noisy iterative algorithms, including SGLD and DP-SGD as two
examples. This extension requires a significant improvement of the proof
techniques presented in (Wang et al., 2021). Specifically, we introduce a
unified framework for deriving generalization bounds through $f$-divergence
while the analysis in the prior work (Wang et al., 2021) is tailored to the
KL-divergence. In the context of the DP-SGD algorithm, we prove that the total
variation distance leads to a tighter generalization bound and the
$\chi^{2}$-divergence leads to a bound requiring milder assumptions compared
with the results in (Wang et al., 2021). Finally, we derive a new
generalization bound in the context of federated learning as an application of
our framework.

##  2 Preliminaries

#### Notations.

For a positive integer $n$, we define the set $[n]\triangleq\\{1,\cdots,n\\}$.
We denote by $\|\cdot\|_{1}$ and $\|\cdot\|_{2}$ the 1-norm and 2-norm of a
vector, respectively. A random variable X is $\sigma$-sub-Gaussian if
$\log\mathbb{E}\left[\exp{\lambda(\textnormal{X}-\mathbb{E}\left[\textnormal{X}\right])}\right]\leq\sigma^{2}\lambda^{2}/2$
for any $\lambda\in\mathbb{R}$. For a random vector
$\textnormal{X}=(\textnormal{X}_{1},\cdots,\textnormal{X}_{d})$, we define its
variance and minimum mean absolute error (MMAE) as

$\displaystyle\mathsf{Var}\left(\textnormal{X}\right)$
$\displaystyle\triangleq\inf_{\bm{a}\in\mathbb{R}^{d}}\mathbb{E}\left[\|\textnormal{X}-\bm{a}\|_{2}^{2}\right],$
(6) $\displaystyle\mathsf{mmae}(\textnormal{X})$
$\displaystyle\triangleq\inf_{\bm{a}\in\mathbb{R}^{d}}\mathbb{E}\left[\|\textnormal{X}-\bm{a}\|_{1}\right].$
(7)

The vector $\bm{a}$ which minimizes (6) and (7) are

$\displaystyle\operatorname*{\arg\\!\min}_{\bm{a}\in\mathbb{R}^{d}}\mathbb{E}\left[\|\textnormal{X}-\bm{a}\|_{2}^{2}\right]$
$\displaystyle=(\mathbb{E}\left[\textnormal{X}_{1}\right],\cdots,\mathbb{E}\left[\textnormal{X}_{d}\right]),$
(8)
$\displaystyle\operatorname*{\arg\\!\min}_{\bm{a}\in\mathbb{R}^{d}}\mathbb{E}\left[\|\textnormal{X}-\bm{a}\|_{1}\right]$
$\displaystyle=(\mathsf{median}(\textnormal{X}_{1}),\cdots,\mathsf{median}(\textnormal{X}_{d})),$
(9)

where $\mathsf{median}(\textnormal{X}_{i})$ is the median of the random
variable $\textnormal{X}_{i}$.

In order to measure the difference between two probability distributions, we
recall Csiszár’s $f$-divergence (Csiszár, 1967). Let
$f:(0,\infty)\to\mathbb{R}$ be a convex function with $f(1)=0$ and $P$, $Q$ be
two probability distributions over a set $\mathcal{X}\subseteq\mathbb{R}^{d}$.
The $f$-divergence between $P$ and $Q$ is defined as

$\displaystyle\textnormal{D}_{f}(P\|Q)\triangleq\int_{\mathcal{X}}f\left(\tfrac{\textrm{d}P}{\textrm{d}Q}\right)\textrm{d}Q.$
(10)

Examples of $f$-divergence include KL-divergence ($f(t)=t\log t$), total
variation distance ($f(t)=|t-1|/2$), and $\chi^{2}$-divergence
($f(t)=t^{2}-1$). The $f$-divergence motivates a way of measuring dependence
between a pair of random variables $(\textnormal{X},\textnormal{Y})$.
Specifically, the $f$-information between $(\textnormal{X},\textnormal{Y})$ is
defined as

$\displaystyle
I_{f}(\textnormal{X};\textnormal{Y})\triangleq\textnormal{D}_{f}(P_{\textnormal{X},\textnormal{Y}}\|P_{\textnormal{X}}\otimes
P_{\textnormal{Y}})=\mathbb{E}\left[\textnormal{D}_{f}(P_{\textnormal{Y}|\textnormal{X}}\|P_{\textnormal{Y}})\right],$
(11)

where $P_{\textnormal{X},\textnormal{Y}}$ is the joint distribution,
$P_{\textnormal{X}}$, $P_{\textnormal{Y}}$ are the marginal distributions,
$P_{\textnormal{Y}|\textnormal{X}}$ is the conditional distribution, and the
expectation is taken over $\textnormal{X}\sim P_{\textnormal{X}}$. In
particular, if the KL-divergence is used in (11), the corresponding
$f$-information is the well-known mutual information (Shannon, 1948).

#### Information-theoretic generalization bounds.

A recent work by Xu and Raginsky (2017) provided a framework for analyzing
algorithmic generalization. Specifically, they considered a learning algorithm
as a channel (i.e., conditional probability distribution) that takes a
training set S as input and outputs a parameter W. Furthermore, they derived
an upper bound for the expected generalization gap using the mutual
information $I(\textnormal{W};\textnormal{S})$. This bound was later tightened
by Bu et al. (2020) using an individual sample mutual information. Next, we
recall the generalization bound in Bu et al. (2020). By adapting their proof
and leveraging variational representations of $f$-divergence (Nguyen et al.,
2010), we present another two generalization bounds based on different kinds
of $f$-information.

###### Lemma 1

Consider a learning algorithm which takes a dataset
$\textnormal{S}=(\textnormal{Z}_{1},\cdots,\textnormal{Z}_{n})$ as input and
outputs W.

  * •

(Proposition 1 in Bu et al., 2020) If the loss $\ell(\bm{w},\textnormal{Z})$
is $\sigma$-sub-Gaussian under $\textnormal{Z}\sim\mu$ for all
$\bm{w}\in\mathcal{W}$, then

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\right|\leq\frac{\sqrt{2}\sigma}{n}\sum_{i=1}^{n}\sqrt{I(\textnormal{W};\textnormal{Z}_{i})},$
(12)

where $I(\textnormal{W};\textnormal{Z}_{i})$ is the mutual information (i.e.,
$f$-information with $f(t)=t\log t$).

  * •

If the loss $\ell(\bm{w},\textnormal{Z})$ is upper bounded by a constant
$A>0$, then

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\right|\leq\frac{A}{n}\sum_{i=1}^{n}{\textnormal{T}}(\textnormal{W};\textnormal{Z}_{i}),$
(13)

where ${\textnormal{T}}(\textnormal{W};\textnormal{Z}_{i})$ is the
T-information (i.e., $f$-information with $f(t)=|t-1|/2$).

  * •

If the variance of the loss function is finite (i.e.,
$\mathsf{Var}\left(\ell(\textnormal{W};\textnormal{Z})\right)<\infty$), then

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\right|\leq\frac{\sqrt{\mathsf{Var}\left(\ell(\textnormal{W};\textnormal{Z})\right)}}{n}\sum_{i=1}^{n}\sqrt{\chi^{2}(\textnormal{W};\textnormal{Z}_{i})},$
(14)

where $\chi^{2}(\textnormal{W};\textnormal{Z}_{i})$ is the
$\chi^{2}$-information (i.e., $f$-information with $f(t)=t^{2}-1$) and Z is a
fresh data point which is independent of W (i.e.,
$(\textnormal{W},\textnormal{Z})\sim P_{\textnormal{W}}\otimes\mu$).

Proof  See Appendix A.1.
We apply Lemma 1 to analyze the generalization capability of noisy iterative
algorithms. Estimating the $f$-information in Lemma 1 from data is
intractable. Hence, we further upper bound these $f$-information by exploring
properties of additive noise channels in the next section. Furthermore, we
also incorporate a time-decaying factor into our bound, which is established
by strong data processing inequalities, recalled in the upcoming subsection.

Although our analysis is applicable for _any_ $f$-information, we focus on the
three $f$-information in Lemma 1 since:

  * •

Mutual information is often easier to work with due to its many useful
properties. For example, the chain rule of mutual information plays an
important role for handling sampling with replacement (see Section 5.3).

  * •

T-information often yields a tighter bound than (12) and (14). This can be
seen by the following $f$-divergence inequalities (see Eq. 1 and 94 in Sason
and Verdú, 2016):

$\displaystyle\sqrt{2}{\textnormal{T}}(\textnormal{W};\textnormal{Z}_{i})\leq\sqrt{I(\textnormal{W};\textnormal{Z}_{i})}\leq\sqrt{\log(1+\chi^{2}(\textnormal{W};\textnormal{Z}_{i}))}\leq\sqrt{\chi^{2}(\textnormal{W};\textnormal{Z}_{i})}.$

Furthermore, the T-information can be used to analyze a broader class of noisy
iterative algorithms. For example, when the additive noise is drawn from a
distribution with bounded support, the other two $f$-information may lead to
an infinite generalization bound while the T-information can still give a non-
trivial bound (see the last row in Table 1).

  * •

$\chi^{2}$-information requires the mildest assumptions. Apart from bounded
loss functions, it is often hard to verify the sub-Gaussianity of
$\ell(\bm{w},\textnormal{Z})$ for all $\bm{w}$. The advantage of (14) is that
it replaces the sub-Gaussian constant with the variance of the loss function.

###### Remark 1

Using $f$-information for bounding generalization gap has appeared in prior
literature (see e.g., Alabdulmohsin, 2015; Jiao et al., 2017; Wang et al.,
2019; Esposito et al., 2021; Rodríguez-Gálvez et al., 2021; Aminian et al.,
2021; Jose and Simeone, 2020). More broadly, there are significant recent
works (see e.g., Raginsky et al., 2016; Asadi et al., 2018; Lopez and Jog,
2018; Steinke and Zakynthinou, 2020; Hellström and Durisi, 2020; Yagli et al.,
2020; Hafez-Kolahi et al., 2020; Jose and Simeone, 2021; Zhou et al., 2021) on
deriving new information-theoretic generalization bounds and applying them to
different applications. The reason we adopt Lemma 1 for analyzing noisy
iterative algorithms is that it enables us to incorporate a time-decaying
factor into our bounds.

#### Strong data processing inequalities.

In order to characterize the time-decaying phenomenon, we use an information-
theoretic tool: strong data processing inequalities (Dobrushin, 1956; Cohen et
al., 1998). We start with recalling the data processing inequality.

###### Lemma 2

If a Markov chain $\textnormal{U}\to\textnormal{X}\to\textnormal{Y}$ holds,
then

$\displaystyle I_{f}(\textnormal{U};\textnormal{Y})\leq
I_{f}(\textnormal{U};\textnormal{X}).$ (15)

The data processing inequality states that no post-processing of X can
increase the information about U. Under certain conditions, the data
processing inequality can be sharpened, which leads to a strong data
processing inequality, often cast in terms of a contraction coefficient. Next,
we recall the contraction coefficients of $f$-divergences and show their
connection with strong data processing inequalities.

For a given transition probability kernel
$P_{\textnormal{Y}|\textnormal{X}}:\mathcal{X}\to\mathcal{Y}$, let
$P_{\textnormal{Y}|\textnormal{X}}\circ P$ be the distribution on
$\mathcal{Y}$ induced by the push-forward of the distribution $P$ (i.e., the
distribution of Y when the distribution of X is $P$). The contraction
coefficient of $P_{\textnormal{Y}|\textnormal{X}}$ for $\textnormal{D}_{f}$ is
defined as

$\displaystyle\eta_{f}(P_{\textnormal{Y}|\textnormal{X}})\triangleq\sup_{P,Q:P\neq
Q}\frac{\textnormal{D}_{f}(P_{\textnormal{Y}|\textnormal{X}}\circ
P\|P_{\textnormal{Y}|\textnormal{X}}\circ
Q)}{\textnormal{D}_{f}(P\|Q)}\in[0,1].$

In particular, when the total variation distance is used, the corresponding
contraction coefficient
$\eta_{\scalebox{0.6}{{T}V}}(P_{\textnormal{Y}|\textnormal{X}})$ is known as
the Dobrushin’s coefficient (Dobrushin, 1956), which owns an equivalent
expression:

$\displaystyle\eta_{\scalebox{0.6}{{T}V}}(P_{\textnormal{Y}|\textnormal{X}})=\sup_{\bm{x},\bm{x}^{\prime}\in\mathcal{X}}\textnormal{D}_{\scalebox{0.6}{{T}V}}(P_{\textnormal{Y}|\textnormal{X}=\bm{x}}\|P_{\textnormal{Y}|\textnormal{X}=\bm{x}^{\prime}}).$
(16)

The Dobrushin’s coefficient upper bounds all other contraction coefficients
(Cohen et al., 1998):
$\eta_{f}(P_{\textnormal{Y}|\textnormal{X}})\leq\eta_{\scalebox{0.6}{{T}V}}(P_{\textnormal{Y}|\textnormal{X}})$.
Furthermore, for any Markov chain
$\textnormal{U}\to\textnormal{X}\to\textnormal{Y}$, the contraction
coefficients satisfy (see Theorem 5.2 in Raginsky, 2016, for a proof)

$\displaystyle
I_{f}(\textnormal{U};\textnormal{Y})\leq\eta_{f}(P_{\textnormal{Y}|\textnormal{X}})\cdot
I_{f}(\textnormal{U};\textnormal{X}).$ (17)

When $\eta_{f}(P_{\textnormal{Y}|\textnormal{X}})<1$, the strict inequality
$I_{f}(\textnormal{U};\textnormal{Y})<I_{f}(\textnormal{U};\textnormal{X})$
improves the data processing inequality and, hence, is referred to as a strong
data processing inequality. We refer the reader to Polyanskiy and Wu (2016)
and Raginsky (2016) for a more comprehensive review on strong data processing
inequalities and Calmon et al. (2017) for non-linear strong data processing
inequalities in Gaussian channels.

##  3 Properties of Additive Noise Channels

Additive noise channels have a long history in information theory. Here we
show two important properties of additive noise channels which will be used
for deriving the generalization bounds in the next section. The first property
(Lemma 3) leads to a decay factor into our bounds. The second property (Lemma
4) produces computable generalization bounds.

Consider a single use of an additive noise channel. Let
$(\textnormal{X},\textnormal{Y})$ be a pair of random variables related by
$\textnormal{Y}=\textnormal{X}+m\textnormal{N}$ where
$\textnormal{X}\in\mathcal{X}$; $m>0$ is a constant; and N represents an
independent noise. In other words, the conditional distribution of Y given X
can be characterized by
$P_{\textnormal{Y}|\textnormal{X}=\bm{x}}=P_{\bm{x}+m\textnormal{N}}$. If
$\mathcal{X}$ is a compact set, the contraction coefficients often have a non-
trivial upper bound, leading to a strong data processing inequality. This is
formalized in the following lemma whose proof follows directly from the
definition of the Dobrushin’s coefficient in (16) and the fact that the
Dobrushin’s coefficient is a universal upper bound of all the contraction
coefficients.

###### Lemma 3

Let N be a random variable which is independent of
$(\textnormal{U},\textnormal{X})$. For a given norm $\|\cdot\|$ on a compact
set $\mathcal{X}\subseteq\mathbb{R}^{d}$ and $m,A>0$, we define

$\displaystyle\delta(A,m)$
$\displaystyle\triangleq\sup_{\|\bm{x}-\bm{x}^{\prime}\|\leq
A}\textnormal{D}_{\scalebox{0.6}{{T}V}}\left(P_{\bm{x}+m\textnormal{N}}\|P_{\bm{x}^{\prime}+m\textnormal{N}}\right).$
(18)

Then the Markov chain
$\textnormal{U}\to\textnormal{X}\to\textnormal{X}+m\textnormal{N}$ holds and

$\displaystyle
I_{f}(\textnormal{U};\textnormal{X}+m\textnormal{N})\leq\delta(\mathsf{diam}(\mathcal{X}),m)\cdot
I_{f}(\textnormal{U};\textnormal{X}),$ (19)

where
$\mathsf{diam}(\mathcal{X})\triangleq\sup_{\bm{x},\bm{x}^{\prime}\in\mathcal{X}}\|\bm{x}-\bm{x}^{\prime}\|$
is the diameter of $\mathcal{X}$.

Computing $f$-information in general is intractable when the underlying
distribution is unknown. Hence, we further upper bound the $f$-information in
Lemma 1 by a quantity which is easier to compute. To achieve this goal, we
introduce another property of additive noise channels. Specifically, let
$\textnormal{Y}=\textnormal{X}+m\textnormal{N}$ and
$\textnormal{Y}^{\prime}=\textnormal{X}^{\prime}+m\textnormal{N}$ be the
output variables from the same additive noise channel with input variables X
and $\textnormal{X}^{\prime}$, respectively. Then the $f$-divergence in the
output space can be upper bounded by the optimal transport cost in the input
space.

###### Lemma 4

Let N be a random variable which is independent of
$(\textnormal{X},\textnormal{X}^{\prime})$. For
$\bm{x},\bm{x}^{\prime}\in\mathbb{R}^{d}$ and $m>0$, we define a cost function

$\displaystyle\mathsf{C}_{f}(\bm{x},\bm{x}^{\prime};m)$
$\displaystyle\triangleq\textnormal{D}_{f}\left(P_{\bm{x}+m\textnormal{N}}\|P_{\bm{x}^{\prime}+m\textnormal{N}}\right).$
(20)

Then for any $m>0$, we have

$\displaystyle\textnormal{D}_{f}(P_{\textnormal{X}+m\textnormal{N}}\|P_{\textnormal{X}^{\prime}+m\textnormal{N}})\leq\mathbb{W}(P_{\textnormal{X}},P_{\textnormal{X}^{\prime}};m).$
(21)

Here $\mathbb{W}(P_{\textnormal{X}},P_{\textnormal{X}^{\prime}};m)$ is the
optimal transport cost:

$\displaystyle\mathbb{W}(P_{\textnormal{X}},P_{\textnormal{X}^{\prime}};m)\triangleq\inf\mathbb{E}\left[\mathsf{C}_{f}(\textnormal{X},\textnormal{X}^{\prime};m)\right],$
(22)

where the infimum is taken over all couplings (i.e., joint distributions) of
the random variables X and $\textnormal{X}^{\prime}$ with marginals
$P_{\textnormal{X}}$ and $P_{\textnormal{X}^{\prime}}$, respectively.

Proof  See Appendix B.1.

Noise Type | $\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)$ | $\mathsf{C}_{\chi^{2}}(\bm{x},\bm{x}^{\prime};m)$ | $\mathsf{C}_{\scalebox{0.6}{{T}V}}(\bm{x},\bm{x}^{\prime};m)$ | $\delta(A,m)$
---|---|---|---|---
Gaussian | $\frac{\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}}{2m^{2}}$ | $\exp\left(\frac{\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}}{m^{2}}\right)-1$ | $\frac{\|\bm{x}-\bm{x}^{\prime}\|_{2}}{2m}$ | $1-2\bar{\Phi}\left(\frac{A}{2m}\right)$
Laplace | $\frac{\|\bm{x}-\bm{x}^{\prime}\|_{1}}{m}$ | $\exp\left(\frac{\|\bm{x}-\bm{x}^{\prime}\|_{1}}{m}\right)-1$ | $\sqrt{\frac{\|\bm{x}-\bm{x}^{\prime}\|_{1}}{2m}}$ | $1-\exp\left(-\frac{A}{m}\right)$
Uniform on $[-1,1]$ | $\infty\mathbb{I}_{[x\neq x^{\prime}]}$ | $\infty\mathbb{I}_{[x\neq x^{\prime}]}$ | $\min\left\\{1,\left|\frac{x-x^{\prime}}{2m}\right|\right\\}$ | $\min\left\\{1,\frac{A}{2m}\right\\}$

Table 1: Closed-form expressions (or upper bounds if in blue color) of
$\mathsf{C}_{f}(\bm{x},\bm{x}^{\prime};m)$ (see (20) for its definition) and
$\delta(A,m)$ (see (18) for its definition). The function $\delta(A,m)$ is
equipped with the 2-norm for Gaussian distribution and 1-norm for Laplace
distribution. We denote the the Gaussian complementary cumulative distribution
function (CCDF) by
$\bar{\Phi}(x)\triangleq\int^{\infty}_{x}\frac{1}{\sqrt{2\pi}}\exp(-v^{2}/2)\textrm{d}v$
and define $\infty\cdot 0=0$ as convention. The proof is deferred to Appendix
B.3.

Lemmas 3 and 4 show that the functions $\delta(A,m)$ and
$\mathsf{C}_{f}(\bm{x},\bm{x}^{\prime};m)$ can be useful for sharpening the
data processing inequality and upper bounding the $f$-information in Lemma 1.
We demonstrate in Table 1 that these functions can be expressed in closed-form
for specific additive noise distributions.

###### Remark 2

Let N be drawn from a Gaussian distribution. Substituting the closed-form
expression of $\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)$
from Table 1 into Lemma 4 leads to

$\displaystyle\textnormal{D}_{\scalebox{0.6}{{K}L}}(P_{\textnormal{X}+m\textnormal{N}}\|P_{\textnormal{X}^{\prime}+m\textnormal{N}})\leq\frac{1}{2m^{2}}\mathbb{W}_{2}^{2}(P_{\textnormal{X}},P_{\textnormal{X}^{\prime}})$
(23)

where $\mathbb{W}_{2}(P_{\textnormal{X}},P_{\textnormal{X}^{\prime}})$ is the
2-Wasserstein distance equipped with the $L_{2}$ cost function:

$\displaystyle\mathbb{W}_{2}^{2}(P_{\textnormal{X}},P_{\textnormal{X}^{\prime}})\triangleq\inf\mathbb{E}\left[\|\textnormal{X}-\textnormal{X}^{\prime}\|_{2}^{2}\right].$

This inequality serves as a fundamental building block for proving Otto-
Villani’s HWI inequality (Otto and Villani, 2000) in the Gaussian case
(Raginsky and Sason, 2012; Boucheron et al., 2013).

##  4 Generalization Bounds for Noisy Iterative Algorithms

In this section, we present our main result—generalization bounds for noisy
iterative algorithms. First, by leveraging strong data processing
inequalities, we prove that the amount of information about the data points
used in early iterations decays with time. Accordingly, our generalization
bounds incorporate a time-decaying factor which enables the impact of early
iterations on our bounds to reduce with time. Second, by using properties of
additive noise channels developed in the last section, we further upper bound
the $f$-information by a quantity which is often easier to estimate. The above
two aspects correspond to Lemma 5 and 6 which are the basis of our main result
in Theorem 1.

Before diving into the analysis, we first discuss assumptions made in this
paper.

###### Assumption 1

The mini-batch indices $(\mathcal{B}_{1},\cdots,\mathcal{B}_{T})$ in (3) are
specified before the algorithm is run and data are drawn without replacement.

If the mini-batches are selected when the algorithm is run, one can analyze
the expected generalization gap by first conditioning on
$\mathcal{B}\triangleq(\mathcal{B}_{1},\cdots,\mathcal{B}_{T})$ and then
taking an expectation over the randomness of $\mathcal{B}$:

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]=\mathbb{E}\left[\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\mid\mathcal{B}\right]\right].$

Our analysis can be extended to the case where data are drawn with replacement
(see Proposition 4) by using the chain rule for mutual information.

###### Assumption 2

The parameter domain $\mathcal{W}$ is compact and $\|g(\bm{w},\bm{z})\|\leq K$
for all $\bm{w},\bm{z}$. We denote the diameter of $\mathcal{W}$ by
$D\triangleq\sup_{\bm{w},\bm{w}^{\prime}\in\mathcal{W}}\|\bm{w}-\bm{w}^{\prime}\|$.

Our generalization bounds rely on the second assumption mildly. In fact, this
assumption only affects the time-decaying factor in our bounds which is always
upper bounded by $1$. If we remove this assumption, our bounds still hold
though the decay factor disappears.

Now we are in a position to derive generalization bounds under the above
assumptions. As a consequence of strong data processing inequalities, the
following lemma indicates that the information of a data point
$\textnormal{Z}_{i}$ contained in the algorithmic output $\textnormal{W}_{T}$
will reduce with time $T$.

###### Lemma 5

Under Assumption 1, 2, if a data point $\textnormal{Z}_{i}$ is used in the
$t$-th iteration, then

$\displaystyle I_{f}(\textnormal{W}_{T};\textnormal{Z}_{i})\leq
I_{f}(\textnormal{W}_{t};\textnormal{Z}_{i})\cdot\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}}),$
(24)

where the function $\delta(\cdot,\cdot)$ is defined in (18).

Proof  For the $t$-th iteration, we rewrite the recursion in (3) as

$\displaystyle\textnormal{U}_{t}=\textnormal{W}_{t-1}-\eta_{t}\cdot
g(\textnormal{W}_{t-1},\\{\textnormal{Z}_{i}\\}_{i\in\mathcal{B}_{t}})$ (25a)
$\displaystyle\textnormal{V}_{t}=\textnormal{U}_{t}+m_{t}\cdot\textnormal{N}$
(25b)
$\displaystyle\textnormal{W}_{t}=\mathsf{Proj}_{\mathcal{W}}\left(\textnormal{V}_{t}\right).$
(25c)

Let $\textnormal{Z}_{i}$ be a data point used at the $t$-th iteration. Under
Assumption 1, the following Markov chain holds:

$\displaystyle\textnormal{Z}_{i}\to\textnormal{U}_{t}\to\textnormal{V}_{t}\to\textnormal{W}_{t}\to\cdots\to\textnormal{W}_{T-1}\to\textnormal{U}_{T}\to\textnormal{V}_{T}\to\textnormal{W}_{T}.$
(26)

Let $\mathcal{U}_{T}$ be the range of $\textnormal{U}_{T}$. By Assumption 2
and the triangle inequality,

$\displaystyle\mathsf{diam}(\mathcal{U}_{T})\leq\mathsf{diam}(\mathcal{W})+2\eta_{T}K=D+2\eta_{T}K.$

Now we leverage the strong data processing inequality in Lemma 3 and obtain

$\displaystyle I_{f}(\textnormal{W}_{T};\textnormal{Z}_{i})$
$\displaystyle\leq I_{f}(\textnormal{V}_{T};\textnormal{Z}_{i})$
$\displaystyle\leq\delta(D+2\eta_{T}K,m_{T})\cdot
I_{f}(\textnormal{U}_{T};\textnormal{Z}_{i})$
$\displaystyle\leq\delta(D+2\eta_{T}K,m_{T})\cdot
I_{f}(\textnormal{W}_{T-1};\textnormal{Z}_{i}),$

where the first and last steps are due to the data processing inequality
(Lemma 2). Applying this procedure recursively leads to the desired
conclusion.

For many types of noise (e.g., Gaussian or Laplace noise), the function
$\delta(\cdot,\cdot)$ is _strictly_ smaller than $1$ (see Table 1). In this
case, the information about the data points used in early iterations is
reducing via the multiplicative factor in (24). Furthermore, one can even
prove that $I_{f}(\textnormal{W}_{T};\textnormal{Z}_{i})\to 0$ as $T\to\infty$
if the magnitude of the additive noise in (3) has a lower bound.

Lemma 5 explains how our generalization bounds in Theorem 1 incorporate a
time-decaying factor. However, it still involves a $f$-information
$I_{f}(\textnormal{W}_{t};\textnormal{Z}_{i})$, which can be hard to compute
from data. Next, we further upper bound this $f$-information by using
properties of additive noise channels developed in the last section (see Lemma
4).

###### Lemma 6

Under Assumption 1, if a data point $\textnormal{Z}_{i}$ is used at the $t$-th
iteration, then

$\displaystyle
I_{f}(\textnormal{W}_{t};\textnormal{Z}_{i})\leq\mathbb{E}\left[\mathsf{C}_{f}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right],$
(27)

where the function $\mathsf{C}_{f}(\cdot,\cdot;\cdot)$ is defined in (20) and
the expectation is taken over
$(\textnormal{W}_{t-1},\textnormal{Z},\bar{\textnormal{Z}})\sim
P_{\textnormal{W}_{t-1}}\otimes\mu\otimes\mu$.

Proof  Recall the definition of $\textnormal{U}_{t}$, $\textnormal{V}_{t}$ in
(25). The data processing inequality yields

$\displaystyle I_{f}(\textnormal{W}_{t};\textnormal{Z}_{i})$
$\displaystyle\leq I_{f}(\textnormal{V}_{t};\textnormal{Z}_{i}).$ (28)

By the definition of $f$-information, we can write

$\displaystyle
I_{f}(\textnormal{V}_{t};\textnormal{Z}_{i})=\mathbb{E}\left[\textnormal{D}_{f}(P_{\textnormal{V}_{t}|\textnormal{Z}_{i}}\|P_{\textnormal{V}_{t}})\right]=\int_{\mathcal{Z}}\textnormal{D}_{f}(P_{\textnormal{V}_{t}|\textnormal{Z}_{i}=\bm{z}}\|P_{\textnormal{V}_{t}})\textrm{d}\mu(\bm{z}).$
(29)

Since $\textnormal{V}_{t}=\textnormal{U}_{t}+m_{t}\cdot\textnormal{N}$ by its
definition, Lemma 4 leads to

$\displaystyle\textnormal{D}_{f}\left(P_{\textnormal{V}_{t}|\textnormal{Z}_{i}=\bm{z}}\|P_{\textnormal{V}_{t}}\right)\leq\mathbb{W}(P_{\textnormal{U}_{t}|\textnormal{Z}_{i}=\bm{z}},P_{\textnormal{U}_{t}};m_{t}).$
(30)

To further upper bound the above optimal transport cost, we construct a
special coupling. Let $\textnormal{W}_{t-1}$ be the output of the noisy
iterative algorithm at the $(t-1)$-st iteration. Then we introduce two random
variables:

$\displaystyle\textnormal{U}^{*}_{\bm{z}}\triangleq\textnormal{W}_{t-1}-\frac{\eta_{t}}{b_{t}}\Bigg{(}\sum_{\begin{subarray}{c}j\in\mathcal{B}_{t},j\neq
i\end{subarray}}g(\textnormal{W}_{t-1},\textnormal{Z}_{j})+g(\textnormal{W}_{t-1},\bm{z})\Bigg{)},$
$\displaystyle\textnormal{U}^{*}\triangleq\textnormal{W}_{t-1}-\frac{\eta_{t}}{b_{t}}\sum_{j\in\mathcal{B}_{t}}g(\textnormal{W}_{t-1},\textnormal{Z}_{j}).$

Here $\textnormal{U}^{*}_{\bm{z}}$ and $\textnormal{U}^{*}$ have marginals
$P_{\textnormal{U}_{t}|\textnormal{Z}_{i}=\bm{z}}$ and
$P_{\textnormal{U}_{t}}$, respectively. By the definition of optimal transport
cost in (22), we have

$\displaystyle\mathbb{W}\left(P_{\textnormal{U}_{t}|\textnormal{Z}_{i}=\bm{z}},P_{\textnormal{U}_{t}};m_{t}\right)\leq\mathbb{E}\left[\mathsf{C}_{f}(\textnormal{U}_{\bm{z}}^{*},\textnormal{U}^{*};m_{t})\right].$
(31)

The property of $\mathsf{C}_{f}(\bm{x},\bm{y};m)$ in Lemma 7 yields

$\displaystyle\mathbb{E}\left[\mathsf{C}_{f}(\textnormal{U}_{\bm{z}}^{*},\textnormal{U}^{*};m_{t})\right]$
$\displaystyle=\mathbb{E}\left[\mathsf{C}_{f}\left(-\frac{\eta_{t}}{b_{t}}g(\textnormal{W}_{t-1},\bm{z}),-\frac{\eta_{t}}{b_{t}}g(\textnormal{W}_{t-1},\textnormal{Z}_{i});m_{t}\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathsf{C}_{f}\left(\frac{\eta_{t}}{b_{t}}g(\textnormal{W}_{t-1},\textnormal{Z}_{i}),\frac{\eta_{t}}{b_{t}}g(\textnormal{W}_{t-1},\bm{z});m_{t}\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathsf{C}_{f}\left(g(\textnormal{W}_{t-1},\textnormal{Z}_{i}),g(\textnormal{W}_{t-1},\bm{z});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right].$
(32)

Since the data point $\textnormal{Z}_{i}$ is only used at the $t$-th
iteration, it is independent of $\textnormal{W}_{t-1}$. We introduce two
independent copies $\textnormal{Z},\bar{\textnormal{Z}}$ of
$\textnormal{Z}_{i}$ such that
$(\textnormal{W}_{t-1},\textnormal{Z},\bar{\textnormal{Z}})\sim
P_{\textnormal{W}_{t-1}}\otimes\mu\otimes\mu$. Combining (29–32) and using
Tonelli’s theorem lead to

$\displaystyle I_{f}(\textnormal{V}_{t};\textnormal{Z}_{i})$
$\displaystyle\leq\mathbb{E}\left[\mathsf{C}_{f}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right].$
(33)

Substituting (33) into (28) gives the desired conclusion.

With Lemma 1, 5, and 6 in hand, we now present the main result in this
section: three generalization bounds for noisy iterative algorithms under
different assumptions.

###### Theorem 1

Suppose that Assumption 1, 2 hold.

  * •

If the loss $\ell(\bm{w},\textnormal{Z})$ is $\sigma$-sub-Gaussian under
$\textnormal{Z}\sim\mu$ for all $\bm{w}\in\mathcal{W}$, the expected
generalization gap
$\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]$
can be upper bounded by

$\displaystyle\frac{\sqrt{2}\sigma}{n}\sum_{t=1}^{T}b_{t}\sqrt{\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{K}L}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right]\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}})}.$
(34)

  * •

If the loss function is upper bounded by a constant $A>0$, the expected
generalization gap
$\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]$
can be upper bounded by

$\displaystyle\frac{A}{n}\sum_{t=1}^{T}b_{t}\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{T}V}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right]\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}}).$
(35)

  * •

If the variance of the loss function is finite (i.e.,
$\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)<\infty$),
the expected generalization gap
$\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]$
can be upper bounded by

$\displaystyle\frac{\sigma}{n}\sum_{t=1}^{T}b_{t}\sqrt{\mathbb{E}\left[\mathsf{C}_{\chi^{2}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right]\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}})},$
(36)

where
$\sigma\triangleq\sqrt{\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)}$
with $(\textnormal{W}_{T},\textnormal{Z})\sim
P_{\textnormal{W}_{T}}\otimes\mu$.

Proof  See Appendix C.1.
Our generalization bounds involve the information (e.g., step size $\eta_{t}$,
magnitude of noise $m_{t}$, and batch size $b_{t}$) at all iterations.
Moreover, our bounds are distribution-dependent through the expectation term.
Finally, since the function $\delta$ is often strictly smaller than $1$ (see
Table 1 for some examples), the multiplicative factor
$\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}})$
enables the impact of early iterations on our bounds to reduce with time.

The generalization bounds in Theorem 1 may seem contrived at first glance as
they rely on the functions $\delta$ and $\mathsf{C}_{f}$ defined in (18) and
(20). However, in the next section, we will show that these bounds can be
significantly simplified when we apply them to real applications. Furthermore,
we will also compare the advantage of each bound under these applications.

##  5 Applications

We demonstrate the generalization bounds in Theorem 1 through several
applications in this section.

###  5.1 Differentially Private Stochastic Gradient Descent (DP-SGD)

Differentially private stochastic gradient descent (DP-SGD) is a variant of
SGD where noise is added to a stochastic gradient estimator in order to ensure
privacy of each individual record. We recall an implementation of (projected)
DP-SGD (see e.g., Algorithm 1 in Feldman et al., 2018). At each iteration, the
parameter of the empirical risk is updated using the following rule:

$\displaystyle\textnormal{W}_{t}=\mathsf{Proj}_{\mathcal{W}}\left(\textnormal{W}_{t-1}-\eta\left(g(\textnormal{W}_{t-1},\\{\textnormal{Z}_{i}\\}_{i\in\mathcal{B}_{t}})+\textnormal{N}\right)\right),$
(37)

where N is an additive noise; $\mathcal{B}_{t}$ contains the indices of the
data points used at the current iteration and
$b_{t}\triangleq|\mathcal{B}_{t}|$; the function $g$ indicates a direction for
updating the parameter. The recursion in (37) is run for $T$ iterations and we
assume that data are drawn without replacement. At the end of each iteration,
the parameter is projected onto a compact domain $\mathcal{W}$. We denote the
diameter of $\mathcal{W}$ by $D$. The output from the DP-SGD algorithm is the
last iterate $\textnormal{W}_{T}$. Finally, we assume that

$\displaystyle\sup_{\bm{w}\in\mathcal{W},\bm{z}\in\mathcal{Z}}\|g(\bm{w},\bm{z})\|\leq
K.$ (38)

This assumption can be satisfied by gradient clipping and is crucial for
guaranteeing differential privacy as it controls the sensitivity of each
update.

The differential privacy guarantees of the DP-SGD algorithm have been
extensively studied in the literature (see e.g., Song et al., 2013; Wu et al.,
2017; Feldman et al., 2018; Balle et al., 2019; Asoodeh et al., 2020). Here we
consider a different angle: the generalization of DP-SGD. We derive
generalization bounds for the DP-SGD algorithm under Laplace and Gaussian
mechanisms by using our Theorem 1.

######  Proposition 1 (Laplace mechanism)

Suppose that the additive noise N in (37) follows a standard multivariate
Laplace distribution. Let $\mathcal{W}$ be equipped with the 1-norm and
$q\triangleq 1-\exp\left(-(D+2\eta K)/\eta\right)\in(0,1)$.

  * •

If the loss $\ell(\bm{w},\textnormal{Z})$ is $\sigma$-sub-Gaussian under
$\textnormal{Z}\sim\mu$ for all $\bm{w}\in\mathcal{W}$, then

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]\leq\frac{2\sigma}{n}\sum_{t=1}^{T}\sqrt{b_{t}\cdot\mathsf{mmae}\left(g(\textnormal{W}_{t-1},\textnormal{Z})\right)\cdot
q^{T-t}}.$ (39)

  * •

If the loss function is upper bounded by $A>0$, then

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]\leq\frac{\sqrt{2}A}{n}\sum_{t=1}^{T}\sqrt{b_{t}}\cdot\mathbb{E}\left[\sqrt{\left\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\right\|_{1}}\right]\cdot
q^{T-t},$ (40)

where
$\bm{e}\triangleq\mathsf{median}\left(g(\textnormal{W}_{t-1},\textnormal{Z})\right)$.

  * •

If the variance of the loss function is bounded (i.e.,
$\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)<\infty$),
then

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]\leq\frac{\sigma}{n}\sum_{t=1}^{T}\sqrt{b_{t}\cdot\mathbb{E}\left[\exp\left(2\left\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\right\|_{1}\right)-1\right]\cdot
q^{T-t}},$ (41)

where
$\sigma=\sqrt{\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)}$
and
$\bm{e}\triangleq\mathsf{median}\left(g(\textnormal{W}_{t-1},\textnormal{Z})\right)$.

Proof  See Appendix D.1.

######  Proposition 2 (Gaussian mechanism)

Suppose that the additive noise N in (37) follows a standard multivariate
Gaussian distribution. Let $\mathcal{W}$ be equipped with the 2-norm and
$q\triangleq 1-2\bar{\Phi}\left((D+2\eta K)/2\eta\right)\in(0,1)$ with
$\bar{\Phi}(\cdot)$ being the Gaussian CCDF.

  * •

If the loss $\ell(\bm{w},\textnormal{Z})$ is $\sigma$-sub-Gaussian under
$\textnormal{Z}\sim\mu$ for all $\bm{w}\in\mathcal{W}$, then

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]\leq\frac{2\sigma}{n}\sum_{t=1}^{T}\sqrt{\mathsf{Var}\left(g(\textnormal{W}_{t-1},\textnormal{Z})\right)\cdot
q^{T-t}}.$ (42)

  * •

If the loss function is upper bounded by $A>0$, then

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]\leq\frac{A}{n}\sum_{t=1}^{T}\mathbb{E}\left[\left\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\right\|_{2}\right]\cdot
q^{T-t},$ (43)

where
$\bm{e}\triangleq\mathbb{E}\left[g(\textnormal{W}_{t-1},\textnormal{Z})\right]$.

  * •

If the variance of the loss function is bounded (i.e.,
$\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)<\infty$),
then

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]\leq\frac{\sigma}{n}\sum_{t=1}^{T}\sqrt{\mathbb{E}\left[\exp\left(4\left\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\right\|_{2}^{2}\right)-1\right]\cdot
q^{T-t}},$ (44)

where
$\sigma=\sqrt{\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)}$
and
$\bm{e}\triangleq\mathbb{E}\left[g(\textnormal{W}_{t-1},\textnormal{Z})\right]$.

Proof  See Appendix D.1.
Our Theorem 1 leads to three generalization bounds for each DP-SGD mechanism.
We discuss the advantage of each bound in the following remark by focusing on
the Gaussian mechanism.

###### Remark 3

We first assume that the loss function is upper bounded by $A$, leading to an
$A/2$-sub-Gaussian loss $\ell(\bm{w},\textnormal{Z})$ and
$\sqrt{\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)}\leq
A/2$. Since

$\displaystyle\mathbb{E}\left[X\right]\leq\sqrt{\mathbb{E}\left[X^{2}\right]}\leq\frac{1}{2}\sqrt{\mathbb{E}\left[\exp(4X^{2})-1\right]},$

then for
$\bm{e}\triangleq\mathbb{E}\left[g(\textnormal{W}_{t-1},\textnormal{Z})\right]$

$\displaystyle\mathbb{E}\left[\left\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\right\|_{2}\right]\leq\sqrt{\mathsf{Var}\left(g(\textnormal{W}_{t-1},\textnormal{Z})\right)}\leq\frac{1}{2}\sqrt{\mathbb{E}\left[\exp\left(4\left\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\right\|_{2}^{2}\right)-1\right]}.$

Therefore, we have

$\displaystyle\eqref{eq::gen_bound_TV_Gauss}\leq\eqref{eq::gen_bound_KL_Gauss}\leq\eqref{eq::gen_bound_chi_Gauss}.$

In other words, the total-variation bound in (35) yields the tightest
generalization bound (43) for the DP-SGD algorithm. On the other hand, the
$\chi^{2}$-divergence bound in (36) leads to a bound (44) that requires the
mildest assumption. At this moment, it seems unclear what the advantage of the
KL-divergence bound is. Nonetheless, we will show in Section 5.3 that the nice
properties of mutual information (e.g., chain rule) help extend our analysis
to the general setting where data are drawn with replacement.

A standard approach (see e.g., He et al., 2021) for analyzing the
generalization of the DP-SGD algorithm often follows two steps: establish
$(\epsilon,\delta)$-differential privacy guarantees for the DP-SGD algorithm
and prove/apply a generalization bound that holds for _any_
$(\epsilon,\delta)$-differentially private algorithms. However, generalization
bounds obtained in this manner are distribution-independent since differential
privacy is robust with respect to the data distribution. As observed in
existing literature (see e.g., Zhang et al., 2016) and our Figure 1, machine
learning models trained under different data distributions can exhibit
completely different generalization behaviors. Our bounds take into account
the data distribution through the expectation terms (or mmae, variance).

Our generalization bounds can be estimated from data. Take the bound in (42)
as an example. If sufficient data are available at each iteration, we can
estimate the variance term by the population variance of
$\\{g(\textnormal{W}_{t-1},\textnormal{Z}_{i})\mid i\in\mathcal{B}_{t}\\}$
since $\textnormal{W}_{t-1}$ is independent of $\textnormal{Z}_{i}$ for
$i\in\mathcal{B}_{t}$. Alternatively, we can draw a hold-out set for
estimating the variance term at each iteration.

###  5.2 Federated Learning (FL)

Federated learning (FL) (McMahan et al., 2017) is a setting where a model is
trained across multiple clients (e.g., mobile devices) under the management of
a central server while the training data are kept decentralized. We recall the
federated averaging algorithm with local-update DP-SGD in Algorithm 1 and
refer the readers to Kairouz et al. (2019) for a more comprehensive review.

Algorithm 1 Federated averaging (local DP-SGD).

Input:

Total number of clients $N$ and clients per round $C$

Total global updates $T$ and local updates $M$

DP-SGD learning rate $\eta$

Initialize: $\textnormal{W}_{0}$ randomly selected from $\mathcal{W}$

for $t=1,\cdots,T$ global steps do

Server chooses a subset $\mathcal{S}_{t}$ of $C$ clients

Server sends $\textnormal{W}_{t-1}$ to all selected clients

for each client $k\in\mathcal{S}_{t}$ in parallel do

Initialize $\textnormal{W}_{t,0}^{k}\leftarrow\textnormal{W}_{t-1}$

for $j=1,\cdots,M$ local steps do

Draw $b$ fresh data points $\\{\textnormal{Z}_{i}^{k}\\}_{i\in[b]}$ and noise
$\textnormal{N}\sim N(0,\mathbf{I}_{d})$

Update the parameter
$\textnormal{W}_{t,j}^{k}\leftarrow\mathsf{Proj}_{\mathcal{W}}\left(\textnormal{W}_{t,j-1}^{k}-\eta\left(g\left(\textnormal{W}_{t,j-1}^{k},\\{\textnormal{Z}_{i}^{k}\\}_{i\in[b]}\right)+\textnormal{N}\right)\right)$

end for

Send $\textnormal{W}_{t,M}^{k}$ back to the server

end for

Server aggregates the parameter
$\textnormal{W}_{t}=\frac{1}{C}\sum_{k\in\mathcal{S}_{t}}\textnormal{W}_{t,M}^{k}$

end for

Output: $\textnormal{W}_{T}$

It is crucial to be able to _monitor_ the performance of the global model on
each client. Although the global model could achieve a desirable performance
on average, it may fail to achieve high accuracy for each local client. This
is because in the federated learning setting, data are typically unbalanced
(different clients own different number of samples) and not identically
distributed (data distribution varies across different clients). Since in
practice clients may not have an extra hold-out dataset to evaluate the
performance of the global model, they can instead compute the loss of the
model on their training set and compensate the mismatch by the generalization
gap (or its upper bound). It is worth noting that this approach of monitoring
model performance is completely decentralized as the clients do not need to
share their data with the server and all the computation can be done locally.
As discussed in Remark 3, the total variation bound in (35) often leads to the
tightest generalization bound so we recast it under the setting of FL.

###### Proposition 3

Let $\mathcal{T}_{k}\subset[T]$ contain the indices of global iterations in
which the $k$-th client interacts with the server. If the loss function is
upper bounded by $A>0$, the expected generalization gap of the $k$-th client
has an upper bound:

$\displaystyle\mathbb{E}\left[L_{\mu_{k}}(\textnormal{W}_{T})-L_{\textnormal{S}_{k}}(\textnormal{W}_{T})\right]\leq\frac{A}{n_{k}}\sum_{t\in\mathcal{T}_{k}}\sum_{j=1}^{M}\mathbb{E}\left[\|g(\textnormal{W}_{t,j-1}^{k},\textnormal{Z}^{k})-\bm{e}\|_{2}\right]\cdot
q^{M(T+1-t)-j},$

where $n_{k}$ is the number of training data from the $k$-th client,
$\bm{e}\triangleq\mathbb{E}\left[g(\textnormal{W}_{t,j-1}^{k},\textnormal{Z}^{k})\right]$,
and

$\displaystyle q\triangleq 1-2\bar{\Phi}\left(\frac{\sqrt{C}(D+2\eta
K)}{2\eta}\right)\in(0,1)$

with $D$ being the diameter of $\mathcal{W}$,
$K\triangleq\sup_{\bm{w},\bm{z}}\|g(\bm{w},\bm{z})\|_{2}$, and
$\bar{\Phi}(\cdot)$ being the Gaussian CCDF.

Proof  See Appendix D.2.
Yagli et al. (2020) introduced a generalization bound in the context of
federated learning. However, their bound in Theorem 3 involves a mutual
information. Here we replace the mutual information with an expectation term.
This improvement allows local clients to compute our bound from their training
data more reliably.

###  5.3 Stochastic Gradient Langevin Dynamics (SGLD)

We analyze the generalization gap of the stochastic gradient Langevin dynamics
(SGLD) algorithm (Gelfand and Mitter, 1991; Welling and Teh, 2011). We start
by recalling a standard framework of SGLD. The dataset S is first divided into
$m$ disjoint mini-batches:

$\displaystyle\textnormal{S}=\bigcup_{j=1}^{m}\textnormal{S}_{j},\quad\text{where
}|\textnormal{S}_{j}|=b\text{ and
}\textnormal{S}_{j}\cap\textnormal{S}_{k}=\emptyset\text{ for }j\neq k.$

We initialize the parameter of the empirical risk with a random point
$\textnormal{W}_{0}\in\mathcal{W}$ and update using the following rule:

$\displaystyle\textnormal{W}_{t}=\textnormal{W}_{t-1}-\eta_{t}\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{S}_{B_{t}})+\sqrt{\frac{2\eta_{t}}{\beta_{t}}}\textnormal{N},$
(45)

where $\eta_{t}$ is the learning rate; $\beta_{t}$ is the inverse temperature;
N is drawn independently from a standard Gaussian distribution; $B_{t}\in[m]$
is the mini-batch index; $\hat{\ell}$ is a surrogate loss (e.g., hinge loss);
and

$\displaystyle\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{S}_{B_{t}})\triangleq\frac{1}{b}\sum_{\textnormal{Z}\in\textnormal{S}_{B_{t}}}\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{Z}).$
(46)

We study a general setting where the output from SGLD can be any function of
the parameters across all iterations (i.e.,
$\textnormal{W}=f(\textnormal{W}_{1},\cdots,\textnormal{W}_{T})$), including
the setting considered before where $\textnormal{W}=\textnormal{W}_{T}$. For
example, the output can be an average of all iterates (i.e., Polyak averaging)
$\textnormal{W}=\frac{1}{T}\sum_{t}\textnormal{W}_{t}$ or the parameter which
achieves the smallest value of the loss function
$\textnormal{W}=\operatorname*{\arg\\!\min}_{\textnormal{W}_{t}}L_{\mu}(\textnormal{W}_{t})$.

Alas, Theorem 1 cannot be applied directly to the SGLD algorithm because the
Markov chain in (26) does not hold any more when data are drawn with
replacement. In order to circumvent this issue, we develop a different proof
technique by using the chain rule for mutual information.

###### Proposition 4

If the loss function $\ell(\bm{w},\textnormal{Z})$ is $\sigma$-sub-Gaussian
under $\textnormal{Z}\sim\mu$ for all $\bm{w}\in\mathcal{W}$, then

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\leq\frac{\sqrt{2b}\sigma}{2n}\sum_{j=1}^{m}\sqrt{\sum_{t\in\mathcal{T}_{j}}\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{S}_{j})\right)},$

where the set $\mathcal{T}_{j}$ contains the indices of iterations in which
the mini-batch $\textnormal{S}_{j}$ is used.

Proof  See Appendix D.3.

Our bound incorporates the gradient variance which measures a particular kind
of “flatness” of the loss landscape. We note that a recent work (Jiang et al.,
2019) has observed empirically that the variance of gradients is predictive of
and highly correlated with the generalization gap of neural networks. Here we
evidence this connection from a theoretical viewpoint by incorporating the
gradient variance into the generalization bound.

Unfortunately, our generalization bound does not incorporate a decay
factor222We note that the analysis in Mou et al. (2018) requires
$\textnormal{W}=\textnormal{W}_{T}$. Hence, in the setting we consider (i.e.,
W is a function of $\textnormal{W}_{1},\cdots,\textnormal{W}_{T}$), it is
unclear if it is possible to include a decay factor in the bound. anymore. To
understand why it happens, let us imagine an extreme scenario in which the
SGLD algorithm outputs all the iterates (i.e.,
$\textnormal{W}=(\textnormal{W}_{1},\cdots,\textnormal{W}_{T})$). For a data
point $\textnormal{Z}_{i}$ used at the $t$-th iteration, the data processing
inequality implies that

$\displaystyle
I(\textnormal{W}_{1},\cdots,\textnormal{W}_{T};\textnormal{Z}_{i})\geq
I(\textnormal{W}_{t};\textnormal{Z}_{i}).$

Hence, it is impossible to have
$I(\textnormal{W}_{1},\cdots,\textnormal{W}_{T};\textnormal{Z}_{i})\to 0$ as
$T\to\infty$ unless $I(\textnormal{W}_{t};\textnormal{Z}_{i})=0$.

Many existing SGLD generalization bounds (e.g., Mou et al., 2018; Li et al.,
2019; Pensia et al., 2018; Negrea et al., 2019) are expressed as a sum of
errors associated with each training iteration. In order to compare with these
results, we present an analogous bound in the following corollary. This bound
is obtained by combining a key lemma for proving Proposition 4 with Minkowski
inequality and Jensen’s inequality so it is often much weaker than Proposition
4.

###### Corollary 1

If the loss function $\ell(\bm{w},\textnormal{Z})$ is $\sigma$-sub-Gaussian
under $\textnormal{Z}\sim\mu$ for all $\bm{w}\in\mathcal{W}$, the expected
generalization gap of the SGLD algorithm can be upper bounded by

$\displaystyle\frac{\sqrt{2}\sigma}{2}\min\left\\{\frac{1}{n}\sum_{t=1}^{T}\sqrt{\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{Z}^{\dagger}_{t})\right)},\sqrt{\frac{1}{bn}\sum_{t=1}^{T}\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{Z}^{\dagger}_{t})\right)}\right\\},$

where $\textnormal{Z}^{\dagger}_{t}$ is any data point used in the $t$-th
iteration.

Proof  See Appendix D.4.

Our bound is distribution-dependent through the variance of gradients in
contrast with Corollary 1 of Pensia et al. (2018), Proposition 3 of Bu et al.
(2020), and Theorem 1 of Mou et al. (2018), which rely on the Lipschitz
constant:
$\sup_{\bm{w},\bm{z}}\|\nabla_{\bm{w}}\hat{\ell}(\bm{w},\bm{z})\|_{2}$. These
bounds fail to explain some generalization phenomena of DNNs, such as label
corruption (Zhang et al., 2016), because the Lipschitz constant takes a
supremum over all possible weight matrices $\bm{w}$ and data points $\bm{z}$.
In other words, this Lipschitz constant only relies on the architecture of the
network instead of the weight matrices or data distribution. Hence, it is the
same for a network trained from corrupted data and a network trained from true
data. We remark that the Lipschitz constant used by Pensia et al. (2018); Bu
et al. (2020); Mou et al. (2018) is different from the Lipschitz constant of
the function corresponding to a network w.r.t. the input variable. The latter
one has been used in the literature (see e.g., Bartlett et al., 2017) for
deriving generalization bounds and, to some degree, can capture generalization
phenomena, such as label corruption.

The order of our generalization bound in Corollary 1 is
$\min\Big{(}\frac{1}{n}\sum_{t=1}^{T}\sqrt{\beta\eta_{t}},\sqrt{\frac{\beta}{bn}\sum_{t=1}^{T}\eta_{t}}\Big{)}$.
It is tighter than Theorem 2 of Mou et al. (2018) whose order is
$\sqrt{\frac{\beta}{n}\sum_{t=1}^{T}\eta_{t}}$. Our bound is applicable
regardless of the choice of learning rate while the bound in Li et al. (2019)
requires the scale of the learning rate to be upper bounded by the reciprocal
of the Lipschitz constant. Our Corollary 1 has the same order with Negrea et
al. (2019) but we incorporate an additional decay factor when applying our
bounds to the DP-SGD algorithm (see Proposition 2) and numerical experiments
suggest that our bound is more favourably correlated with the true
generalization gap (see Table 1 in Wang et al., 2021).

##  6 Numerical Experiments

In this section, we demonstrate our generalization bound (Proposition 4)
through numerical experiments on the MNIST dataset (LeCun et al., 1998),
CIFAR-10 dataset (Krizhevsky et al., 2009), and SVHN dataset (Netzer et al.,
2011), showing that it can predict the behavior of the true generalization
gap.

#### Corrupted labels.

Figure 1: Illustration of our generalization bound in Proposition 4. We use
the SGLD algorithm to train 3-layer neural networks on MNIST (top row) and
convolutional neural networks on CIFAR-10 (middle row) and SVHN (bottom row)
when the training data have different label corruption level
$\alpha\in\\{0\%,25\%,50\%,75\%\\}$. Left column: training accuracy. Middle
column: empirical generalization gap. Right column: empirical generalization
bound.

As observed in Zhang et al. (2016), DNNs have the potential to memorize the
entire training dataset even when a large portion of the labels are corrupted.
For networks with identical architecture, those trained using true labels have
better generalization capability than those ones trained using corrupted
labels, although both of them achieve perfect training accuracy.
Unfortunately, distribution-independent bounds, such as the ones using VC-
dimension, may not be able to capture this phenomenon because they are
invariant for both true data and corrupted data. In contrast, our bound
quantifies this empirical observation, exhibiting a lower value on networks
trained on true labels compared to ones trained on corrupted labels (Figure
1).

In our experiment, we randomly select 5000 samples as our training dataset and
change the label of $\alpha\in\\{0\%,25\%,50\%,75\%\\}$ of the training
samples. Then we use the SGLD algorithm to train a neural network under
different corruption level. The training process continues until the training
accuracy is $1.0$ (see Figure 1 Left). We compare our generalization bound
with the generalization gap in Figure 1 Middle and Right. As shown, both our
bound and the generalization gap are increasing w.r.t. the corruption level in
the last epoch. Furthermore, the curve of our bound has very similar shape
with the generalization gap. Finally, we observe that the generalization gap
tends to be stable since the algorithm converges (Figure 1 Middle). Our
generalization bound captures this phenomenon (Figure 1 Right) as the variance
of gradients becomes negligible when the algorithm starts converging. The
intuition is that the variance of gradients reflects the flatness of the loss
landscape and as the algorithm converges, the loss landscape becomes flatter.

Figure 2: Comparison between our generalization bound (Proposition 4) and the
generalization gap. We use the SGLD algorithm to train neural networks with
varying widths on the MNIST (left), CIFAR-10 (middle), and SVHN (right)
datasets.

#### Network width.

As observed by several recent studies (see e.g., Neyshabur et al., 2014; Jiang
et al., 2019), wider networks can lead to a smaller generalization gap. This
may seem contradictory to the traditional wisdom as one may expect that a
class of wider networks has a higher VC-dimension and, hence, would have a
higher generalize gap. In our experiment, we use the SGLD algorithm to train
neural networks with different widths. The training process runs for $400$
epochs until the training accuracy is $1.0$. We compare our generalization
bound with the generalization gap in Figure 2. As shown, both the
generalization gap and our bound are decreasing with respect to the network
width.

##  7 Conclusion

In this paper, we investigate the generalization of noisy iterative algorithms
and derive three generalization bounds based on different $f$-divergence. We
establish a unified framework and leverage fundamental tools from information
theory (e.g., strong data processing inequalities and properties of additive
noise channels) for proving these bounds. We demonstrate our generalization
bounds through applications, including DP-SGD, FL, and SGLD, in which our
bounds own a simple form and can be estimated from data. Numerical experiments
suggest that our bounds can predict the behavior of the true generalization
gap.

## References

  * Abadi et al. (2016) M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang.  Deep learning with differential privacy.  In _ACM SIGSAC conference on computer and communications security_ , pages 308–318, 2016.
  * Alabdulmohsin (2015) I. M. Alabdulmohsin.  Algorithmic stability and uniform generalization.  In _Advances in Neural Information Processing Systems_ , volume 28, pages 19–27, 2015.
  * Aminian et al. (2021) G. Aminian, L. Toni, and M. R. Rodrigues.  Jensen-shannon information based characterization of the generalization error of learning algorithms.  In _IEEE Information Theory Workshop_ , pages 1–5, 2021.
  * Asadi et al. (2018) A. R. Asadi, E. Abbe, and S. Verdú.  Chaining mutual information and tightening generalization bounds.  _arXiv preprint arXiv:1806.03803_ , 2018.
  * Asoodeh et al. (2020) S. Asoodeh, M. Diaz, and F. P. Calmon.  Privacy amplification of iterative algorithms via contraction coefficients.  _arXiv preprint arXiv:2001.06546_ , 2020.
  * Balle et al. (2019) B. Balle, G. Barthe, M. Gaboardi, and J. Geumlek.  Privacy amplification by mixing and diffusion mechanisms.  In _Advances in Neural Information Processing Systems_ , pages 13298–13308, 2019.
  * Bartlett et al. (2017) P. L. Bartlett, D. J. Foster, and M. J. Telgarsky.  Spectrally-normalized margin bounds for neural networks.  In _Advances in Neural Information Processing Systems_ , pages 6240–6249, 2017.
  * Bassily et al. (2021) R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman.  Algorithmic stability for adaptive data analysis.  _SIAM Journal on Computing_ , pages 377–405, 2021.
  * Boucheron et al. (2013) S. Boucheron, G. Lugosi, and P. Massart.  _Concentration inequalities: A nonasymptotic theory of independence_.  Oxford University Press, 2013.
  * Bu et al. (2020) Y. Bu, S. Zou, and V. V. Veeravalli.  Tightening mutual information based bounds on generalization error.  _IEEE Journal on Selected Areas in Information Theory_ , 2020.
  * Calmon et al. (2017) F. P. Calmon, Y. Polyanskiy, and Y. Wu.  Strong data processing inequalities for input constrained additive noise channels.  _IEEE Transactions on Information Theory_ , 64(3):1879–1892, 2017.
  * Cohen et al. (1998) J. Cohen, J. H. Kempermann, and G. Zbaganu.  _Comparisons of stochastic matrices with applications in information theory, statistics, economics and population_.  Springer Science & Business Media, 1998.
  * Csiszár (1967) I. Csiszár.  Information-type measures of difference of probability distributions and indirect observation.  _studia scientiarum Mathematicarum Hungarica_ , 2:229–318, 1967.
  * Dobrushin (1956) R. L. Dobrushin.  Central limit theorem for nonstationary Markov chains. i.  _Theory of Probability & Its Applications_, 1(1):65–80, 1956.
  * Dwork et al. (2006) C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006.
  * Dwork et al. (2015) C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth.  Preserving statistical validity in adaptive data analysis.  In _ACM Symposium on Theory of Computing_ , pages 117–126, 2015.
  * Esposito et al. (2021) A. R. Esposito, M. Gastpar, and I. Issa.  Generalization error bounds via rényi-, f-divergences and maximal leakage.  _IEEE Transactions on Information Theory_ , 2021.
  * Facebook AI (2020) Facebook AI.  Introducing Opacus: A high-speed library for training pytorch models with differential privacy, 2020.
  * Feldman et al. (2018) V. Feldman, I. Mironov, K. Talwar, and A. Thakurta.  Privacy amplification by iteration.  In _IEEE Annual Symposium on Foundations of Computer Science_ , pages 521–532, 2018.
  * Ge et al. (2015) R. Ge, F. Huang, C. Jin, and Y. Yuan.  Escaping from saddle points—online stochastic gradient for tensor decomposition.  In _Conference on Learning Theory_ , pages 797–842, 2015.
  * Gelfand and Mitter (1991) S. B. Gelfand and S. K. Mitter.  Recursive stochastic algorithms for global optimization in $R^{d}$.  _SIAM Journal on Control and Optimization_ , 29(5):999–1018, 1991.
  * Guo et al. (2005) D. Guo, S. Shamai, and S. Verdú.  Mutual information and minimum mean-square error in Gaussian channels.  _IEEE Transactions on Information Theory_ , 51(4):1261–1282, 2005.
  * Hafez-Kolahi et al. (2020) H. Hafez-Kolahi, Z. Golgooni, S. Kasaei, and M. Soleymani.  Conditioning and processing: Techniques to improve information-theoretic generalization bounds.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Haghifam et al. (2020) M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite.  Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms.  _arXiv preprint arXiv:2004.12983_ , 2020.
  * He et al. (2021) F. He, B. Wang, and D. Tao.  Tighter generalization bounds for iterative differentially private learning algorithms.  In _Conference on Uncertainty in Artificial Intelligence_ , 2021.
  * Hellström and Durisi (2020) F. Hellström and G. Durisi.  Generalization bounds via information density and conditional information density.  _arXiv preprint arXiv:2005.08044_ , 2020.
  * Jiang et al. (2019) Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio.  Fantastic generalization measures and where to find them.  _arXiv preprint arXiv:1912.02178_ , 2019.
  * Jiao et al. (2017) J. Jiao, Y. Han, and T. Weissman.  Dependence measures bounding the exploration bias for general measurements.  In _IEEE International Symposium on Information Theory_ , pages 1475–1479, 2017.
  * Jose and Simeone (2020) S. T. Jose and O. Simeone.  Information-theoretic bounds on transfer generalization gap based on jensen-shannon divergence.  _arXiv preprint arXiv:2010.09484_ , 2020.
  * Jose and Simeone (2021) S. T. Jose and O. Simeone.  Information-theoretic generalization bounds for meta-learning and applications.  _Entropy_ , 23(1):126, 2021.
  * Jung et al. (2019) C. Jung, K. Ligett, S. Neel, A. Roth, S. Sharifi-Malvajerdi, and M. Shenfeld.  A new analysis of differential privacy’s generalization guarantees.  _arXiv preprint arXiv:1909.03577_ , 2019.
  * Kairouz et al. (2019) P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Kleinberg et al. (2018) R. Kleinberg, Y. Li, and Y. Yuan.  An alternative view: When does sgd escape local minima?  _arXiv preprint arXiv:1802.06175_ , 2018.
  * Krizhevsky et al. (2009) A. Krizhevsky, G. Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * LeCun et al. (1998) Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Li et al. (2016) C. Li, C. Chen, D. Carlson, and L. Carin.  Preconditioned stochastic gradient Langevin dynamics for deep neural networks.  In _AAAI Conference on Artificial Intelligence_ , pages 1788–1794, 2016.
  * Li et al. (2019) J. Li, X. Luo, and M. Qiao.  On generalization error bounds of noisy gradient methods for non-convex learning.  _arXiv preprint arXiv:1902.00621_ , 2019.
  * Lopez and Jog (2018) A. T. Lopez and V. Jog.  Generalization error bounds using Wasserstein distances.  In _IEEE Information Theory Workshop_ , pages 1–5. IEEE, 2018.
  * McMahan et al. (2017) B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial Intelligence and Statistics_ , pages 1273–1282. PMLR, 2017.
  * Mou et al. (2018) W. Mou, L. Wang, X. Zhai, and K. Zheng.  Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints.  In _Conference on Learning Theory_ , pages 605–638, 2018.
  * Neelakantan et al. (2015) A. Neelakantan, L. Vilnis, Q. V. Le, I. Sutskever, L. Kaiser, K. Kurach, and J. Martens.  Adding gradient noise improves learning for very deep networks.  _arXiv preprint arXiv:1511.06807_ , 2015.
  * Negrea et al. (2019) J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy.  Information-theoretic generalization bounds for SGLD via data-dependent estimates.  In _Advances in Neural Information Processing Systems_ , pages 11015–11025, 2019.
  * Netzer et al. (2011) Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng.  Reading digits in natural images with unsupervised feature learning.  In _NIPS Workshop on Deep Learning and Unsupervised Feature Learning_ , 2011.
  * Neu et al. (2021) G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy.  Information-theoretic generalization bounds for stochastic gradient descent.  _arXiv preprint arXiv:2102.00931_ , 2021.
  * Neyshabur et al. (2014) B. Neyshabur, R. Tomioka, and N. Srebro.  In search of the real inductive bias: On the role of implicit regularization in deep learning.  _arXiv preprint arXiv:1412.6614_ , 2014.
  * Nguyen et al. (2010) X. Nguyen, M. J. Wainwright, and M. I. Jordan.  Estimating divergence functionals and the likelihood ratio by convex risk minimization.  _IEEE Transactions on Information Theory_ , 56(11):5847–5861, 2010.
  * Otto and Villani (2000) F. Otto and C. Villani.  Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality.  _Journal of Functional Analysis_ , 173(2):361–400, 2000.
  * Pensia et al. (2018) A. Pensia, V. Jog, and P.-L. Loh.  Generalization error bounds for noisy, iterative algorithms.  In _IEEE International Symposium on Information Theory_ , pages 546–550, 2018.
  * Polyanskiy and Wu (2016) Y. Polyanskiy and Y. Wu.  Dissipation of information in channels with input constraints.  _IEEE Transactions on Information Theory_ , 62(1):35–55, 2016.
  * Polyanskiy and Wu (2019) Y. Polyanskiy and Y. Wu.  Lecture notes on information theory.  _Lecture Notes for 6.441 (MIT), ECE 563 (UIUC), STAT 364 (Yale)_ , 2019.  URL http://people.lids.mit.edu/yp/homepage/data/itlectures_v5.pdf.
  * Radebaugh and Erlingsson (2019) C. Radebaugh and U. Erlingsson.  Introducing TensorFlow privacy: Learning with differential privacy for training data, 2019.
  * Raginsky (2016) M. Raginsky.  Strong data processing inequalities and $\Phi$-Sobolev inequalities for discrete channels.  _IEEE Transactions on Information Theory_ , 62(6):3355–3389, 2016.
  * Raginsky and Sason (2012) M. Raginsky and I. Sason.  Concentration of measure inequalities in information theory, communications and coding.  _arXiv preprint arXiv:1212.4663_ , 2012.
  * Raginsky et al. (2016) M. Raginsky, A. Rakhlin, M. Tsao, Y. Wu, and A. Xu.  Information-theoretic analysis of stability and bias of learning algorithms.  In _IEEE Information Theory Workshop_ , pages 26–30, 2016.
  * Raginsky et al. (2017) M. Raginsky, A. Rakhlin, and M. Telgarsky.  Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis.  In _Conference on Learning Theory_ , pages 1674–1703, 2017.
  * Rodríguez-Gálvez et al. (2020) B. Rodríguez-Gálvez, G. Bassi, R. Thobaben, and M. Skoglund.  On random subset generalization error bounds and the stochastic gradient Langevin dynamics algorithm.  _arXiv preprint arXiv:2010.10994_ , 2020.
  * Rodríguez-Gálvez et al. (2021) B. Rodríguez-Gálvez, G. Bassi, R. Thobaben, and M. Skoglund.  Tighter expected generalization error bounds via Wasserstein distance.  _arXiv preprint arXiv:2101.09315_ , 2021.
  * Russo and Zou (2016) D. Russo and J. Zou.  Controlling bias in adaptive data analysis using information theory.  In _Artificial Intelligence and Statistics_ , pages 1232–1240, 2016\.
  * Sason and Verdú (2016) I. Sason and S. Verdú.  $f$-divergence inequalities.  _IEEE Transactions on Information Theory_ , 62(11):5973–6006, 2016.
  * Shannon (1948) C. E. Shannon.  A mathematical theory of communication.  _The Bell system technical journal_ , 27(3):379–423, 1948.
  * Song et al. (2013) S. Song, K. Chaudhuri, and A. D. Sarwate.  Stochastic gradient descent with differentially private updates.  In _IEEE Global Conference on Signal and Information Processing_ , pages 245–248, 2013.
  * Steinke and Zakynthinou (2020) T. Steinke and L. Zakynthinou.  Reasoning about generalization via conditional mutual information.  _arXiv preprint arXiv:2001.09122_ , 2020.
  * Tsybakov (2009) A. B. Tsybakov.  _Introduction to nonparametric estimation_.  Springer-Verlag New York, 2009.
  * Valiant (1984) L. G. Valiant.  A theory of the learnable.  _Communications of the ACM_ , 27(11):1134–1142, 1984.
  * Vapnik and Chervonenkis (1971) V. Vapnik and A. Y. Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  _Theory of Probability and its Applications_ , 16(2):264, 1971.
  * Wang et al. (2019) H. Wang, M. Diaz, J. C. S. Santos Filho, and F. P. Calmon.  An information-theoretic view of generalization via Wasserstein distance.  In _IEEE International Symposium on Information Theory_ , pages 577–581, 2019.
  * Wang et al. (2021) H. Wang, Y. Huang, R. Gao, and F. P. Calmon.  Analyzing the generalization capability of SGLD using properties of Gaussian channels.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Welling and Teh (2011) M. Welling and Y. W. Teh.  Bayesian learning via stochastic gradient Langevin dynamics.  In _International Conference on Machine Learning_ , pages 681–688, 2011.
  * Wu et al. (2017) X. Wu, F. Li, A. Kumar, K. Chaudhuri, S. Jha, and J. Naughton.  Bolt-on differential privacy for scalable stochastic gradient descent-based analytics.  In _ACM International Conference on Management of Data_ , pages 1307–1322, 2017.
  * Wu (2020) Y. Wu.  Lecture notes on: Information-theoretic methods for high-dimensional statistics.  2020\.  URL http://www.stat.yale.edu/~yw562/teaching/it-stats.pdf.
  * Xu and Raginsky (2017) A. Xu and M. Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  In _Advances in Neural Information Processing Systems_ , pages 2524–2533, 2017.
  * Xu et al. (2018) P. Xu, J. Chen, D. Zou, and Q. Gu.  Global convergence of Langevin dynamics based algorithms for nonconvex optimization.  In _Advances in Neural Information Processing Systems_ , pages 3122–3133, 2018.
  * Yagli et al. (2020) S. Yagli, A. Dytso, and H. V. Poor.  Information-theoretic bounds on the generalization error and privacy leakage in federated learning.  _arXiv preprint arXiv:2005.02503_ , 2020.
  * Zhang et al. (2016) C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  _arXiv preprint arXiv:1611.03530_ , 2016.
  * Zhang et al. (2017) Y. Zhang, P. Liang, and M. Charikar.  A hitting time analysis of stochastic gradient Langevin dynamics.  In _Conference on Learning Theory_ , pages 1980–2022, 2017.
  * Zhou et al. (2021) R. Zhou, C. Tian, and T. Liu.  Individually conditional individual mutual information bound on generalization error.  In _IEEE International Symposium on Information Theory_ , pages 670–675, 2021.

##  A Proofs for Section 2

###  A.1 Proof of Lemma 1

Lemma 1 can be proved by combining the proof technique introduced in Bu et al.
(2020) and variational representations of $f$-divergence (Nguyen et al.,
2010). We provide the proof here for the sake of completeness.

Proof  Recall that (see Example 6.1 and 6.4 in Wu, 2020) for any two
probability distributions $P$ and $Q$ over a set
$\mathcal{X}\subseteq\mathbb{R}^{d}$ and a constant $A>0$,

$\displaystyle\textnormal{D}_{\scalebox{0.6}{{T}V}}(P\|Q)$
$\displaystyle=\sup_{\begin{subarray}{c}h:\mathcal{X}\to\mathbb{R}\\\
0\leq\|h\|_{\infty}\leq
A\end{subarray}}\left|\frac{\mathbb{E}_{P}\left[h(\textnormal{X})\right]-\mathbb{E}_{Q}\left[h(\textnormal{X})\right]}{A}\right|,$
(47) $\displaystyle\textnormal{D}_{\chi^{2}}(P\|Q)$
$\displaystyle=\sup_{h:\mathcal{X}\to\mathbb{R}}\frac{(\mathbb{E}_{P}\left[h(\textnormal{X})\right]-\mathbb{E}_{Q}\left[h(\textnormal{X})\right])^{2}}{\mathsf{Var}_{Q}\left(h(\textnormal{X})\right)}.$
(48)

On the other hand, the expected generalization gap can be written as

$\displaystyle\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]=\frac{1}{n}\sum_{i=1}^{n}\left(\mathbb{E}\left[\ell(\textnormal{W},\bar{\textnormal{Z}}_{i})\right]-\mathbb{E}\left[\ell(\textnormal{W},\textnormal{Z}_{i})\right]\right),$

where $(\textnormal{W},\bar{\textnormal{Z}}_{i})$ is an independent copy of
$(\textnormal{W},\textnormal{Z}_{i})$ (i.e.,
$(\textnormal{W},\bar{\textnormal{Z}}_{i})\sim P_{\textnormal{W}}\otimes\mu$).
Consequently,

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\right|\leq\frac{1}{n}\sum_{i=1}^{n}\left|\mathbb{E}\left[\ell(\textnormal{W},\bar{\textnormal{Z}}_{i})\right]-\mathbb{E}\left[\ell(\textnormal{W},\textnormal{Z}_{i})\right]\right|.$

If the loss function is upper bounded by $A>0$, taking
$P=P_{\textnormal{W},\textnormal{Z}_{i}}$ and $Q=P_{\textnormal{W}}\otimes\mu$
in (47) yields

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\right|\leq\frac{A}{n}\sum_{i=1}^{n}\textnormal{D}_{\scalebox{0.6}{{T}V}}(P_{\textnormal{W},\textnormal{Z}_{i}}\|P_{\textnormal{W}}\otimes\mu)=\frac{A}{n}\sum_{i=1}^{n}{\textnormal{T}}(\textnormal{W};\textnormal{Z}_{i}).$

Similarly, taking $P=P_{\textnormal{W},\textnormal{Z}_{i}}$ and
$Q=P_{\textnormal{W}}\otimes\mu$ in (48) leads to

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\right|\leq\frac{1}{n}\sum_{i=1}^{n}\sqrt{\mathsf{Var}\left(\ell(\textnormal{W};\textnormal{Z})\right)\cdot\chi^{2}(\textnormal{W};\textnormal{Z}_{i})}$

where $(\textnormal{W},\textnormal{Z}_{i})\sim
P_{\textnormal{W},\textnormal{Z}_{i}}$ and
$(\textnormal{W},\textnormal{Z})\sim P_{\textnormal{W}}\otimes\mu$.

##  B Proofs for Section 3

###  B.1 Proof of Lemma 4

Lemma 4 follows from a slight tweak of the proof of Theorem 4 in Polyanskiy
and Wu (2016).

Proof  First, we choose a coupling
$P_{\textnormal{X},\textnormal{X}^{\prime}}$, which has marginals
$P_{\textnormal{X}}$ and $P_{\textnormal{X}^{\prime}}$. The probability
distribution of $\textnormal{X}+m\textnormal{N}$ can be written as the
convolution of $P_{\textnormal{X}}$ and $P_{m\textnormal{N}}$. Specifically,

$\displaystyle\textrm{d}P_{\textnormal{X}+m\textnormal{N}}(\bm{y})=\int_{\bm{x}\in\mathcal{X}}\textrm{d}P_{m\textnormal{N}}(\bm{y}-\bm{x})\textrm{d}P_{\textnormal{X}}(\bm{x})=\int_{\bm{x}\in\mathcal{X}}\int_{\bm{x}^{\prime}\in\mathcal{X}}\textrm{d}P_{\bm{x}+m\textnormal{N}}(\bm{y})\textrm{d}P_{\textnormal{X},\textnormal{X}^{\prime}}(\bm{x},\bm{x}^{\prime}).$

Similarly, we have

$\displaystyle\textrm{d}P_{\textnormal{X}^{\prime}+m\textnormal{N}}(\bm{y}^{\prime})$
$\displaystyle=\int_{\bm{x}\in\mathcal{X}}\int_{\bm{x}^{\prime}\in\mathcal{X}}\textrm{d}P_{\bm{x}^{\prime}+m\textnormal{N}}(\bm{y}^{\prime})\textrm{d}P_{\textnormal{X},\textnormal{X}^{\prime}}(\bm{x},\bm{x}^{\prime}).$

Since the mapping $(P,Q)\to\textnormal{D}_{f}(P\|Q)$ is convex (see Theorem
6.1 in Polyanskiy and Wu, 2019, for a proof), Jensen’s inequality yields

$\displaystyle\textnormal{D}_{f}\left(P_{\textnormal{X}+m\textnormal{N}}\|P_{\textnormal{X}^{\prime}+m\textnormal{N}}\right)$
$\displaystyle\leq\int_{\bm{x}\in\mathcal{X}}\int_{\bm{x}^{\prime}\in\mathcal{X}}\textnormal{D}_{f}(P_{\bm{x}+m\textnormal{N}}\|P_{\bm{x}^{\prime}+m\textnormal{N}})\textrm{d}P_{\textnormal{X},\textnormal{X}^{\prime}}(\bm{x},\bm{x}^{\prime})$
$\displaystyle=\mathbb{E}\left[\mathsf{C}_{f}(\textnormal{X},\textnormal{X}^{\prime};m)\right],$
(49)

where the last step follows from the definition. The left-hand side of (49)
only relies on the marginal distributions of X and $\textnormal{X}^{\prime}$,
so taking the infimum on both sides of (49) over all couplings
$P_{\textnormal{X},\textnormal{X}^{\prime}}$ leads to the desired conclusion.

###  B.2 A Useful Property

We derive a useful property of $\mathsf{C}_{f}(\bm{x},\bm{y};m)$ which will be
used in our proofs.

###### Lemma 7

For any $\bm{z}\in\mathbb{R}^{d}$ and $a>0$, the function
$\mathsf{C}_{f}(\bm{x},\bm{x}^{\prime};m)$ in (20) satisfies

$\displaystyle\mathsf{C}_{f}(a\bm{x}+\bm{z},a\bm{x}^{\prime}+\bm{z};m)=\mathsf{C}_{f}\left(\bm{x},\bm{x}^{\prime};\frac{m}{a}\right),\quad\mathsf{C}_{f}(\bm{x},\bm{x}^{\prime};m)=\mathsf{C}_{f}(-\bm{x}^{\prime},-\bm{x};m).$

Proof  For simplicity, we assume that N is a continuous random variable in
$\mathbb{R}^{d}$ with probability density function (PDF) $p(\bm{w})$. Then the
PDFs of $a\bm{x}+\bm{z}+m\textnormal{N}$ and
$a\bm{x}^{\prime}+\bm{z}+m\textnormal{N}$ are

$\displaystyle\frac{1}{m^{d}}\cdot
p\left(\frac{\bm{w}-a\bm{x}-\bm{z}}{m}\right)\quad\text{and}\quad\frac{1}{m^{d}}\cdot
p\left(\frac{\bm{w}-a\bm{x}^{\prime}-\bm{z}}{m}\right).$

By definition,

$\displaystyle\mathsf{C}_{f}(a\bm{x}+\bm{z},a\bm{x}^{\prime}+\bm{z};m)$
$\displaystyle=\textnormal{D}_{f}(P_{a\bm{x}+\bm{z}+m\textnormal{N}}\|P_{a\bm{x}^{\prime}+\bm{z}+m\textnormal{N}})$
$\displaystyle=\frac{1}{m^{d}}\int_{\mathbb{R}^{d}}p\left(\frac{\bm{w}-a\bm{x}^{\prime}-\bm{z}}{m}\right)f\left(\frac{p\left(\frac{\bm{w}-a\bm{x}-\bm{z}}{m}\right)}{p\left(\frac{\bm{w}-a\bm{x}^{\prime}-\bm{z}}{m}\right)}\right)\textrm{d}\bm{w}.$
(50)

Let $\bm{v}=(\bm{w}-\bm{z})/a$. Then (50) is equal to

$\displaystyle\frac{a^{d}}{m^{d}}\int_{\mathbb{R}^{d}}p\left(\frac{\bm{v}-\bm{x}^{\prime}}{m/a}\right)f\left(\frac{p\left(\frac{\bm{v}-\bm{x}}{m/a}\right)}{p\left(\frac{\bm{v}-\bm{x}^{\prime}}{m/a}\right)}\right)\textrm{d}\bm{v}=\mathsf{C}_{f}\left(\bm{x},\bm{x}^{\prime};\frac{m}{a}\right).$

Therefore,
$\mathsf{C}_{f}(a\bm{x}+\bm{z},a\bm{x}^{\prime}+\bm{z};m)=\mathsf{C}_{f}\left(\bm{x},\bm{x}^{\prime};\frac{m}{a}\right)$.
By choosing $a=1$ and $\bm{z}=-\bm{x}-\bm{x}^{\prime}$, we have
$\mathsf{C}_{f}(-\bm{x}^{\prime},-\bm{x};m)=\mathsf{C}(\bm{x},\bm{x}^{\prime};m)$.

###  B.3 Proof of Table 1

We first derive closed-form expressions (or upper bounds) for the function
$\delta(A,m)$. The closed-form expression of $\delta(A,m)$ for uniform
distribution can be naturally obtained from its definition so we skip the
proof. The closed-form expressions for standard multivariate Gaussian
distribution and standard univariate Laplace distribution can be found at
Polyanskiy and Wu (2016) and Asoodeh et al. (2020). In what follows, we
provide an upper bound for $\delta(A,m)$ when N follows a standard
multivariate Laplace distribution.

Proof  For a given positive number $A$ and a random variable N which follows a
standard multivariate Laplace distribution, consider the following
optimization problem:

$\displaystyle\sup_{\|\bm{v}\|_{1}\leq
A}\textnormal{D}_{\scalebox{0.6}{{T}V}}\left(P_{\textnormal{N}}\|P_{\bm{v}+\textnormal{N}}\right)=\sup_{\|\bm{v}\|_{1}\leq
A}\mathbb{E}\left[\left(1-\frac{\exp(-\|\textnormal{N}-\bm{v}\|_{1})}{\exp(-\|\textnormal{N}\|_{1})}\right)\mathbb{I}_{\|\textnormal{N}-\bm{v}\|_{1}\geq\|\textnormal{N}\|_{1}}\right].$

By exchanging the supremum and the expectation, we have

$\displaystyle\sup_{\|\bm{v}\|_{1}\leq
A}\textnormal{D}_{\scalebox{0.6}{{T}V}}\left(P_{\textnormal{N}}\|P_{\bm{v}+\textnormal{N}}\right)\leq\mathbb{E}\left[\sup_{\|\bm{v}\|_{1}\leq
A}\left\\{\left(1-\frac{\exp(-\|\textnormal{N}-\bm{v}\|_{1})}{\exp(-\|\textnormal{N}\|_{1})}\right)\mathbb{I}_{\|\textnormal{N}-\bm{v}\|_{1}\geq\|\textnormal{N}\|_{1}}\right\\}\right].$
(51)

Note that

$\displaystyle\sup_{\|\bm{v}\|_{1}\leq
A}\left\\{\left(1-\frac{\exp(-\|\textnormal{N}-\bm{v}\|_{1})}{\exp(-\|\textnormal{N}\|_{1})}\right)\mathbb{I}_{\|\textnormal{N}-\bm{v}\|_{1}\geq\|\textnormal{N}\|_{1}}\right\\}$
$\displaystyle=1-\exp\left(-\sup_{\begin{subarray}{c}\|\bm{v}\|_{1}\leq
A\end{subarray}}\left\\{\|\textnormal{N}-\bm{v}\|_{1}-\|\textnormal{N}\|_{1}\right\\}\right)=1-\exp(-A).$

Substituting this equality into (51) gives

$\displaystyle\sup_{\|\bm{x}-\bm{x}^{\prime}\|_{1}\leq
A}\textnormal{D}_{\scalebox{0.6}{{T}V}}\left(P_{\bm{x}+\textnormal{N}}\|P_{\bm{x}^{\prime}+\textnormal{N}}\right)=\sup_{\|\bm{v}\|_{1}\leq
A}\textnormal{D}_{\scalebox{0.6}{{T}V}}\left(P_{\textnormal{N}}\|P_{\bm{v}+\textnormal{N}}\right)\leq
1-\exp(-A),$

which leads to $\delta(A,1)\leq 1-\exp(-A)$. Finally, we have

$\displaystyle\delta(A,m)=\delta\left(\frac{A}{m},1\right)\leq
1-\exp\left(-\frac{A}{m}\right).$

Now we consider the function $\mathsf{C}_{f}(\bm{x},\bm{x}^{\prime};m)$.

Proof  By Lemma 7, we have

$\displaystyle\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)=\mathsf{C}_{\scalebox{0.6}{{K}L}}\left(0,\frac{\bm{x}^{\prime}-\bm{x}}{m};1\right).$

We denote $(\bm{x}^{\prime}-\bm{x})/m$ by $\bm{v}$. Since all the coordinates
of $\textnormal{N}=(\textnormal{N}_{1}\cdots,\textnormal{N}_{d})$ are mutually
independent, $P_{\textnormal{N}}=P_{\textnormal{N}_{1}}\cdots
P_{\textnormal{N}_{d}}$ and
$P_{\bm{v}+\textnormal{N}}=P_{v_{1}+\textnormal{N}_{1}}\cdots
P_{v_{d}+\textnormal{N}_{d}}$. By the chain rule of KL-divergence, we have

$\displaystyle\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)=\textnormal{D}_{\scalebox{0.6}{{K}L}}(P_{\textnormal{N}}\|P_{\bm{v}+\textnormal{N}})=\sum_{i=1}^{d}\textnormal{D}_{\scalebox{0.6}{{K}L}}(P_{\textnormal{N}_{i}}\|P_{v_{i}+\textnormal{N}_{i}}).$
(52)

Hence, we only need to calculate
$\textnormal{D}_{\scalebox{0.6}{{K}L}}(P_{\textnormal{N}}\|P_{v+\textnormal{N}})$
for a constant $v\in\mathbb{R}$ and a random variable
$\textnormal{N}\in\mathbb{R}$.
(1) If N follows a standard Gaussian distribution, then

$\displaystyle\textnormal{D}_{\scalebox{0.6}{{K}L}}(P_{\textnormal{N}}\|P_{v+\textnormal{N}})$
$\displaystyle=\mathbb{E}\left[\log\frac{\exp(-\textnormal{N}^{2}/2)}{\exp(-(\textnormal{N}-v)^{2}/2)}\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[(\textnormal{N}-v)^{2}-\textnormal{N}^{2}\right]=\frac{v^{2}}{2}.$

Substituting this equality into (52) gives

$\displaystyle\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)=\frac{\|\bm{v}\|_{2}^{2}}{2}=\frac{\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}}{2m^{2}},$

where the last step is due to the definition of $\bm{v}$.
(2) If N follows a standard Laplace distribution, then

$\displaystyle\textnormal{D}_{\scalebox{0.6}{{K}L}}(P_{\textnormal{N}}\|P_{v+\textnormal{N}})=\mathbb{E}\left[\log\frac{\exp(-|\textnormal{N}|)}{\exp(-|\textnormal{N}-v|)}\right]=|v|+\exp(-|v|)-1.$

Substituting this equality into (52) gives

$\displaystyle\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)$
$\displaystyle=\sum_{i=1}^{d}|v_{i}|+\exp(-|v_{i}|)-1=\frac{\|\bm{x}-\bm{x}^{\prime}\|_{1}}{m}+\sum_{i=1}^{d}\left(\exp\left(-\frac{|x_{i}-x^{\prime}_{i}|}{m}\right)-1\right)$
$\displaystyle\leq\frac{\|\bm{x}-\bm{x}^{\prime}\|_{1}}{m}.$

Similarly, by Lemma 7, we have

$\displaystyle\mathsf{C}_{\chi^{2}}(\bm{x},\bm{x}^{\prime};m)=\mathsf{C}_{\chi^{2}}\left(0,\frac{\bm{x}^{\prime}-\bm{x}}{m};1\right).$

We denote $(\bm{x}^{\prime}-\bm{x})/m$ by $\bm{v}$. By the property of
$\chi^{2}$-divergence (see Section 2.4 in Tsybakov, 2009), we have

$\displaystyle\mathsf{C}_{\chi^{2}}(\bm{x},\bm{x}^{\prime};m)=\textnormal{D}_{\chi^{2}}(P_{\textnormal{N}}\|P_{\bm{v}+\textnormal{N}})=\prod_{i=1}^{d}\left(1+\textnormal{D}_{\chi^{2}}(P_{\textnormal{N}_{i}}\|P_{v_{i}+\textnormal{N}_{i}})\right)-1.$
(53)

Hence, we only need to calculate
$\textnormal{D}_{\chi^{2}}(P_{\textnormal{N}}\|P_{v+\textnormal{N}})$ for
$v\in\mathbb{R}$ and $\textnormal{N}\in\mathbb{R}$.
(1) If N follows a standard Gaussian distribution, then

$\displaystyle\textnormal{D}_{\chi^{2}}(P_{\textnormal{N}}\|P_{v+\textnormal{N}})$
$\displaystyle=\mathbb{E}\left[\frac{\exp(-\textnormal{N}^{2}/2)}{\exp(-(\textnormal{N}-v)^{2}/2)}\right]-1$
$\displaystyle=\exp(v^{2}/2)\mathbb{E}\left[\exp(-vN)\right]-1=\exp(v^{2})-1.$

Substituting this equality into (53) gives

$\displaystyle\mathsf{C}_{\chi^{2}}(\bm{x},\bm{x}^{\prime};m)=\exp(\|\bm{v}\|_{2}^{2})-1=\exp\left(\frac{\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}}{m^{2}}\right)-1.$

(2) If N follows a standard Laplace distribution, then

$\displaystyle\textnormal{D}_{\chi^{2}}(P_{\textnormal{N}}\|P_{v+\textnormal{N}})$
$\displaystyle=\mathbb{E}\left[\frac{\exp(-|\textnormal{N}|)}{\exp(-|\textnormal{N}-v|)}\right]-1$
$\displaystyle=\frac{2}{3}\exp(|v|)+\frac{1}{3}\exp(-2|v|)-1.$

Substituting this equality into (53) gives

$\displaystyle\mathsf{C}_{\chi^{2}}(\bm{x},\bm{x}^{\prime};m)$
$\displaystyle=\prod_{i=1}^{d}\left(\frac{2}{3}\exp\left(\frac{|x_{i}-x^{\prime}_{i}|}{m}\right)+\frac{1}{3}\exp\left(\frac{-2|x_{i}-x^{\prime}_{i}|}{m}\right)\right)-1$
$\displaystyle\leq\exp\left(\frac{\|\bm{x}-\bm{x}^{\prime}\|_{1}}{m}\right)-1.$

Finally, we use Pinsker’s inequality (see Theorem 4.5 in Wu, 2020, for a
proof) for proving an upper bound of
$\mathsf{C}_{\scalebox{0.6}{{T}V}}(\bm{x},\bm{x}^{\prime};m)$:

$\displaystyle\mathsf{C}_{\scalebox{0.6}{{T}V}}(\bm{x},\bm{x}^{\prime};m)$
$\displaystyle=\textnormal{D}_{\scalebox{0.6}{{T}V}}\left(P_{\bm{x}+m\textnormal{N}}\|P_{\bm{x}^{\prime}+m\textnormal{N}}\right)$
$\displaystyle\leq\sqrt{\frac{\textnormal{D}_{\scalebox{0.6}{{K}L}}\left(P_{\bm{x}+m\textnormal{N}}\|P_{\bm{x}^{\prime}+m\textnormal{N}}\right)}{2}}$
$\displaystyle=\sqrt{\frac{\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)}{2}}.$

Hence, any upper bound of
$\mathsf{C}_{\scalebox{0.6}{{K}L}}(\bm{x},\bm{x}^{\prime};m)$ can be naturally
translated into an upper bound for
$\mathsf{C}_{\scalebox{0.6}{{T}V}}(\bm{x},\bm{x}^{\prime};m)$. This is how we
obtain the upper bounds of
$\mathsf{C}_{\scalebox{0.6}{{T}V}}(\bm{x},\bm{x}^{\prime};m)$ under Gaussian
or Laplace distribution in Table 1. On the other hand, if N follows a uniform
distribution on $[-1,1]\subseteq\mathbb{R}$, by Lemma 7 we have

$\displaystyle\mathsf{C}_{\scalebox{0.6}{{T}V}}(x,x^{\prime};m)=\mathsf{C}_{\scalebox{0.6}{{T}V}}\left(0,\frac{x^{\prime}-x}{m};1\right)=\min\left\\{1,\left|\frac{x-x^{\prime}}{2m}\right|\right\\}.$

Note that in this case $\bm{x},\bm{x}^{\prime}\in\mathbb{R}$ so we write them
as $x,x^{\prime}$.

###### Remark 4

We used Pinsker’s inequality for deriving an upper bound of
$\mathsf{C}_{\scalebox{0.6}{{T}V}}(\bm{x},\bm{x}^{\prime};m)$ in the above
proof. One can potentially tighten this bound by exploring other
$f$-divergence inequalities (see e.g., Eq. 4 in Sason and Verdú, 2016).

##  C Proofs for Section 4

###  C.1 Proof of Theorem 1

Proof  Combining Lemma 5 and 6 together leads to an upper bound of
$I_{f}(\textnormal{W}_{T};\textnormal{Z}_{i})$ for any data point
$\textnormal{Z}_{i}$ used at the $t$-th iteration:

$\displaystyle
I_{f}(\textnormal{W}_{T};\textnormal{Z}_{i})\leq\mathbb{E}\left[\mathsf{C}_{f}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right]\cdot\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}}).$
(54)

Additionally, if the loss $\ell(\bm{w},\textnormal{Z})$ is $\sigma$-sub-
Gaussian for all $\bm{w}\in\mathcal{W}$, Lemma 1 and Assumption 1 altogether
yield

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W}_{T})-L_{\textnormal{S}}(\textnormal{W}_{T})\right]\right|$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\sqrt{2\sigma^{2}I(\textnormal{W}_{T};\textnormal{Z}_{i})}$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{T}\sum_{i\in\mathcal{B}_{t}}\sqrt{2\sigma^{2}I(\textnormal{W}_{T};\textnormal{Z}_{i})}.$
(55)

Substituting (54) into (55) yields the following upper bound of the expected
generalization gap:

$\displaystyle\frac{\sqrt{2}\sigma}{n}\sum_{t=1}^{T}\sum_{i\in\mathcal{B}_{t}}\sqrt{\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{K}L}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right]\cdot\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}})}$
$\displaystyle=\frac{\sqrt{2}\sigma}{n}\sum_{t=1}^{T}b_{t}\sqrt{\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{K}L}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});\frac{m_{t}b_{t}}{\eta_{t}}\right)\right]\cdot\prod_{t^{\prime}=t+1}^{T}\delta(D+2\eta_{t^{\prime}}K,m_{t^{\prime}})}.$

Similarly, we can obtain another two generalization bounds using Lemma 1 and
the upper bound in (54).

##  D Proofs for Section 5

###  D.1 Proof of Proposition 1 and 2

In the setting of DP-SGD, the three generalization bounds in Theorem 1 become

$\displaystyle\frac{\sqrt{2}\sigma}{n}\sum_{t=1}^{T}b_{t}\sqrt{\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{K}L}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]\cdot\left(\delta(D+2\eta
K,\eta)\right)^{T-t}}$ (56)

where $\sigma$ is the sub-Gaussian constant;

$\displaystyle\frac{A}{n}\sum_{t=1}^{T}b_{t}\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{T}V}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]\cdot\left(\delta(D+2\eta
K,\eta)\right)^{T-t}$ (57)

where $A$ is an upper bound of the loss function; and

$\displaystyle\frac{\sigma}{n}\sum_{t=1}^{T}b_{t}\sqrt{\mathbb{E}\left[\mathsf{C}_{\chi^{2}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]\cdot\left(\delta(D+2\eta
K,\eta)\right)^{T-t}}$ (58)

where
$\sigma\triangleq\sqrt{\mathsf{Var}\left(\ell(\textnormal{W}_{T};\textnormal{Z})\right)}$.

Proof  We prove Proposition 2 first.

  * •

If the additive noise follows a standard multivariate Gaussian distribution,
Table 1 shows that

$\displaystyle\delta(D+2\eta K,\eta)$
$\displaystyle=1-2\bar{\Phi}\left(\frac{D+2\eta K}{2\eta}\right),$ (59)
$\displaystyle\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{K}L}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]$
$\displaystyle=\frac{1}{2b_{t}^{2}}\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})\|_{2}^{2}\right].$
(60)

We introduce a constant vector $\bm{e}$ whose value will be specified later.
Since $\|\bm{a}-\bm{b}\|_{2}^{2}\leq 2\|\bm{a}\|_{2}^{2}+2\|\bm{b}\|_{2}^{2}$,
we have

$\displaystyle\frac{1}{2b_{t}^{2}}\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})\|_{2}^{2}\right]$
$\displaystyle\leq\frac{1}{b_{t}^{2}}\left(\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}\right]+\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})-\bm{e}\|_{2}^{2}\right]\right)$
$\displaystyle=\frac{2}{b_{t}^{2}}\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}\right],$
(61)

where the last step is because $\textnormal{W}_{t-1}$ is independent of
$(\textnormal{Z},\bar{\textnormal{Z}})$ and
$\textnormal{Z},\bar{\textnormal{Z}}$ follow the same distribution. By
choosing the constant vector
$\bm{e}=\mathbb{E}\left[g(\textnormal{W}_{t-1},\textnormal{Z})\right]$, we
have

$\displaystyle\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}\right]=\mathsf{Var}\left(g(\textnormal{W}_{t-1},\textnormal{Z})\right).$
(62)

Combining (60–62) gives

$\displaystyle\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{K}L}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]\leq\frac{2}{b_{t}^{2}}\mathsf{Var}\left(g(\textnormal{W}_{t-1},\textnormal{Z})\right).$
(63)

Substituting (59), (63) into (56) leads to the generalization bound in (42).

  * •

Similarly, Table 1 shows for Gaussian noise

$\displaystyle\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{T}V}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]$
$\displaystyle\leq\frac{1}{2b_{t}}\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})\|_{2}\right].$
(64)

Furthermore, by the triangle inequality,

$\displaystyle\frac{1}{2b_{t}}\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})\|_{2}\right]$
$\displaystyle\leq\frac{1}{2b_{t}}\left(\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}\right]+\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})-\bm{e}\|_{2}\right]\right)$
$\displaystyle=\frac{1}{b_{t}}\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}\right].$
(65)

By choosing the constant vector
$\bm{e}=\mathbb{E}\left[g(\textnormal{W}_{t-1},\textnormal{Z})\right]$ and
combining (64) with (65), we have

$\displaystyle\mathbb{E}\left[\mathsf{C}_{\scalebox{0.6}{{T}V}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]$
$\displaystyle\leq\frac{1}{b_{t}}\mathbb{E}\left[\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}\right].$
(66)

Substituting (59), (66) into (57) leads to the generalization bound in (43).

  * •

Finally, Table 1 shows for Gaussian noise

$\displaystyle\mathbb{E}\left[\mathsf{C}_{\chi^{2}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]$
$\displaystyle=\mathbb{E}\left[\exp\left(\frac{\|g(\textnormal{W}_{t-1},\textnormal{Z})-g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})\|_{2}^{2}}{b_{t}^{2}}\right)\right]-1.$
(67)

The Cauchy-Schwarz inequality implies that

$\displaystyle\mathbb{E}\left[\exp\left(\frac{\|g(\textnormal{W}_{t-1},\textnormal{Z})-g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})\|_{2}^{2}}{b_{t}^{2}}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\exp\left(\frac{2\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}}{b_{t}^{2}}\right)\exp\left(\frac{2\|g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})-\bm{e}\|_{2}^{2}}{b_{t}^{2}}\right)\right]$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\exp\left(\frac{4\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}}{b_{t}^{2}}\right)\right]\mathbb{E}\left[\exp\left(\frac{4\|g(\textnormal{W}_{t-1},\bar{\textnormal{Z}})-\bm{e}\|_{2}^{2}}{b_{t}^{2}}\right)\right]}$
$\displaystyle=\mathbb{E}\left[\exp\left(\frac{4\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}}{b_{t}^{2}}\right)\right].$
(68)

By choosing the constant vector
$\bm{e}=\mathbb{E}\left[g(\textnormal{W}_{t-1},\textnormal{Z})\right]$ and
combining (67) with (68), we have

$\displaystyle\mathbb{E}\left[\mathsf{C}_{\chi^{2}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\exp\left(\frac{4\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}}{b_{t}^{2}}\right)\right]-1.$
(69)

Since for any $x\geq 0$ and $b\geq 1$,

$\displaystyle\exp\left(\frac{x}{b}\right)-1\leq\frac{\exp(x)-1}{b},$

the inequality in (69) can be further upper bounded as

$\displaystyle\mathbb{E}\left[\mathsf{C}_{\chi^{2}}\left(g(\textnormal{W}_{t-1},\textnormal{Z}),g(\textnormal{W}_{t-1},\bar{\textnormal{Z}});b_{t}\right)\right]$
$\displaystyle\leq\frac{1}{b_{t}^{2}}\left(\mathbb{E}\left[\exp\left(4\|g(\textnormal{W}_{t-1},\textnormal{Z})-\bm{e}\|_{2}^{2}\right)\right]-1\right).$
(70)

Substituting (59), (70) into (58) leads to the generalization bound in (44).

By a similar analysis, we can prove the generalization bounds in Proposition 1
for the Laplace mechanism.

###  D.2 Proof of Proposition 3

Proof  Within the $t$-th global update, we can rewrite the local updates
conducted by the client $k\in\mathcal{S}_{t}$ as follows. The parameter is
initialized by $\textnormal{W}_{t,0}^{k}=\textnormal{W}_{t-1}$ and for
$j\in[M]$,

$\displaystyle\textnormal{U}_{t,j}^{k}=\textnormal{W}_{t,j-1}^{k}-\eta\cdot
g\left(\textnormal{W}_{t,j-1}^{k},\\{\textnormal{Z}_{i}^{k}\\}_{i\in[b]}\right)$
(71a)
$\displaystyle\textnormal{V}_{t,j}^{k}=\textnormal{U}_{t,j}^{k}+\eta\cdot\textnormal{N}$
(71b)
$\displaystyle\textnormal{W}_{t,j}^{k}=\mathsf{Proj}_{\mathcal{W}}\left(\textnormal{V}_{t,j}^{k}\right)$
(71c)

where $\\{\textnormal{Z}_{i}^{k}\\}_{i\in[b]}$ are drawn independently from
the data distribution $\mu_{k}$ and $\textnormal{N}\sim N(0,\mathbf{I}_{d})$.
If a data point $\textnormal{Z}_{i}^{k}$ is used at the $t$-th global update,
$j$-th local update, then the following Markov chain holds:

$\displaystyle\underbrace{\textnormal{Z}_{i}^{k}\to\\{\textnormal{U}_{t,j}^{k}\\}_{k\in\mathcal{S}_{t}}\to\\{\textnormal{V}_{t,j}^{k}\\}_{k\in\mathcal{S}_{t}}\to\\{\textnormal{W}_{t,j}^{k}\\}_{k\in\mathcal{S}_{t}}\to\cdots\to\\{\textnormal{W}_{t,M}^{k}\\}_{k\in\mathcal{S}_{t}}}_{\text{local}}\underbrace{\to\textnormal{W}_{t}}_{\text{global}}\to\cdots\to\textnormal{W}_{T}$

Hence, following a similar analysis in the proof of Lemma 5, we have

$\displaystyle{\textnormal{T}}(\textnormal{W}_{T};\textnormal{Z}_{i}^{k})$
$\displaystyle\leq
q^{M(T-t)}\cdot{\textnormal{T}}(\textnormal{W}_{t};\textnormal{Z}_{i}^{k})$
$\displaystyle\leq
q^{(M-j)+M(T-t)}\cdot{\textnormal{T}}(\\{\textnormal{W}_{t,j}^{k}\\}_{k\in\mathcal{S}_{t}};\textnormal{Z}_{i}^{k}),$
(72)

where the constant $q$ is defined as

$\displaystyle q\triangleq 1-2\bar{\Phi}\left(\frac{\sqrt{C}(D+2\eta
K)}{2\eta}\right).$

Analogous to the proof of Lemma 6, we have

$\displaystyle{\textnormal{T}}(\\{\textnormal{W}_{t,j}^{k}\\}_{k\in\mathcal{S}_{t}};\textnormal{Z}_{i}^{k})\leq\frac{1}{b}\mathbb{E}\left[\|g(\textnormal{W}_{t,j-1}^{k},\textnormal{Z}^{k})-\bm{e}\|_{2}\right]$
(73)

where
$\bm{e}\triangleq\mathbb{E}\left[g(\textnormal{W}_{t,j-1}^{k},\textnormal{Z}^{k})\right]$.
Combining (72), (73) with the T-information bound in Lemma 1 yields the
desired generalization bound for the $k$-th client.

###  D.3 Proof of Proposition 4

We first present the following lemma whose proof follows by using the
technique in Section II. E of Guo et al. (2005).

###### Lemma 8

Let X be a random variable which is independent of $\textnormal{N}\sim
N(0,\mathbf{I}_{d})$. Then for any $m>0$ and deterministic function $f$

$\displaystyle
I(f(\textnormal{X})+m\textnormal{N};\textnormal{X})\leq\frac{1}{2m^{2}}\mathsf{Var}\left(f(\textnormal{X})\right).$
(74)

More generally, if Z is another random variable which is independent of N,
then for any fixed $\bm{z}$

$\displaystyle
I(f(\textnormal{X})+m\textnormal{N};\textnormal{X}\mid\textnormal{Z}=\bm{z})\leq\frac{1}{2m^{2}}\mathsf{Var}\left(f(\textnormal{X})\mid\textnormal{Z}=\bm{z}\right).$
(75)

Proof  By the property of mutual information (see Theorem 2.3 in Polyanskiy
and Wu, 2019),

$\displaystyle
I(f(\textnormal{X})+m\textnormal{N};\textnormal{X})=I\left(\frac{f(\textnormal{X})-\bm{e}}{m}+\textnormal{N};\textnormal{X}\right)$
(76)

where $\bm{e}\triangleq\mathbb{E}\left[f(\textnormal{X})\right]$. We denote

$\displaystyle g(\bm{x})\triangleq\frac{f(\bm{x})-\bm{e}}{m}.$ (77)

The golden formula (see Theorem 3.3 in Polyanskiy and Wu, 2019, for a proof)
yields

$\displaystyle I\left(g(\textnormal{X})+\textnormal{N};\textnormal{X}\right)$
$\displaystyle=\textnormal{D}_{\scalebox{0.6}{{K}L}}\left(P_{g(\textnormal{X})+\textnormal{N}|\textnormal{X}}\|P_{\textnormal{N}}|P_{\textnormal{X}}\right)-\textnormal{D}_{\scalebox{0.6}{{K}L}}\left(P_{g(\textnormal{X})+\textnormal{N}}\|P_{\textnormal{N}}\right)$
$\displaystyle\leq\textnormal{D}_{\scalebox{0.6}{{K}L}}\left(P_{g(\textnormal{X})+\textnormal{N}|\textnormal{X}}\|P_{\textnormal{N}}|P_{\textnormal{X}}\right).$
(78)

Furthermore, since X and N are independent, we have

$\displaystyle\textnormal{D}_{\scalebox{0.6}{{K}L}}\left(P_{g(\textnormal{X})+\textnormal{N}|\textnormal{X}=\bm{x}}\|P_{\textnormal{N}}\right)=\textnormal{D}_{\scalebox{0.6}{{K}L}}\left(P_{g(\bm{x})+\textnormal{N}}\|P_{\textnormal{N}}\right)=\frac{\|g(\bm{x})\|_{2}^{2}}{2},$

where the last step is due to the closed-form expression of the KL-divergence
between two Gaussian distributions. Finally, by the definition of conditional
divergence, we have

$\displaystyle\textnormal{D}_{\scalebox{0.6}{{K}L}}\left(P_{g(\textnormal{X})+\textnormal{N}|\textnormal{X}}\|P_{\textnormal{N}}|P_{\textnormal{X}}\right)=\frac{1}{2}\mathbb{E}\left[\|g(\textnormal{X})\|_{2}^{2}\right]=\frac{1}{2m^{2}}\mathsf{Var}\left(f(\textnormal{X})\right),$
(79)

where the last step is due to the definition of $g$ in (77). Combining (76–79)
leads to the desired conclusion. Finally, it is straightforward to obtain (75)
by conditioning on $\textnormal{Z}=\bm{z}$ and repeating our above
derivations.

Next, we present the second lemma which will be used for proving Proposition
4.

###### Lemma 9

If the loss function $\ell(\bm{w},\textnormal{Z})$ is $\sigma$-sub-Gaussian
under $\textnormal{Z}\sim\mu$ for all $\bm{w}\in\mathcal{W}$, the expected
generalization gap of the SGLD algorithm can be upper bounded by

$\displaystyle\frac{\sqrt{2}\sigma}{2n}\sum_{j=1}^{m}\sqrt{\sum_{t\in\mathcal{T}_{j}}\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\bar{\textnormal{Z}}_{j})\right)},$

where the set $\mathcal{T}_{j}$ contains the indices of iterations in which
the mini-batch $\textnormal{S}_{j}$ is used and the variance is over the
randomness of $(\textnormal{W}_{t-1},\bar{\textnormal{Z}}_{j})\sim
P_{\textnormal{W}_{t-1},\bar{\textnormal{Z}}_{j}}$ with
$\bar{\textnormal{Z}}_{j}$ being any data point in the mini-batch
$\textnormal{S}_{j}$.

Proof  We denote
$\textnormal{Z}^{(k)}\triangleq(\textnormal{Z}_{1},\cdots,\textnormal{Z}_{k})$
for $k\in[n]$ and
$\textnormal{W}^{(t)}\triangleq(\textnormal{W}_{1},\cdots,\textnormal{W}_{t})$
for $t\in[T]$. For simplicity, in what follows we only provide an upper bound
for $I(\textnormal{W};\textnormal{Z}_{n})$. Since W is a function of
$\textnormal{W}^{(T)}=(\textnormal{W}_{1},\cdots,\textnormal{W}_{T})$, the
data processing inequality yields

$\displaystyle I(\textnormal{W};\textnormal{Z}_{n})\leq
I(\textnormal{W}^{(T)};\textnormal{Z}_{n})\leq
I(\textnormal{W}^{(T)},\textnormal{Z}^{(n-1)};\textnormal{Z}_{n}).$ (80)

By the chain rule,

$\displaystyle
I(\textnormal{W}^{(T)},\textnormal{Z}^{(n-1)};\textnormal{Z}_{n})=I(\textnormal{W}_{T};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)},\textnormal{Z}^{(n-1)})+I(\textnormal{W}^{(T-1)},\textnormal{Z}^{(n-1)};\textnormal{Z}_{n}).$
(81)

Let $\bm{w}=(\bm{w}_{1},\cdots,\bm{w}_{T-1})$ and
$\bm{z}=(\bm{z}_{1},\cdots,\bm{z}_{n-1})$ be any two vectors. If
$\textnormal{Z}_{n}$ is not used at the $T$-th iteration, without loss of
generality we assume that the data points
$\textnormal{Z}_{1},\cdots,\textnormal{Z}_{b}$ are used in this iteration.
Then

$\displaystyle
I(\textnormal{W}_{T};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z})$
$\displaystyle=I\left(\bm{w}_{t-1}-\frac{\eta_{T}}{b}\sum_{i=1}^{b}\nabla_{\bm{w}}\hat{\ell}(\bm{w}_{T-1},\bm{z}_{i})+\sqrt{\frac{2\eta_{T}}{\beta_{T}}}\textnormal{N};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z}\right)$
$\displaystyle=I\left(\textnormal{N};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z}\right)$
$\displaystyle=0.$ (82)

On the other hand, if $\textnormal{Z}_{n}$ is used at the $T$-th iteration,
without loss of generality we assume that the other $b-1$ data points which
are also used in this iteration are
$\textnormal{Z}_{1},\cdots,\textnormal{Z}_{b-1}$. Then

$\displaystyle
I(\textnormal{W}_{T};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z})$
$\displaystyle=I\left(\bm{w}_{t-1}-\frac{\eta_{T}}{b}\left(\sum_{i=1}^{b-1}\nabla_{\bm{w}}\hat{\ell}(\bm{w}_{T-1},\bm{z}_{i})+\nabla_{\bm{w}}\hat{\ell}(\bm{w}_{T-1},\textnormal{Z}_{n})\right)+\sqrt{\frac{2\eta_{T}}{\beta_{T}}}\textnormal{N};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z}\right)$
$\displaystyle=I\left(-\frac{\eta_{T}}{b}\nabla_{\bm{w}}\hat{\ell}(\bm{w}_{T-1},\textnormal{Z}_{n})+\sqrt{\frac{2\eta_{T}}{\beta_{T}}}\textnormal{N};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z}\right).$
(83)

By Lemma 8, we have

$\displaystyle
I\left(-\frac{\eta_{T}}{b}\nabla_{\bm{w}}\hat{\ell}(\bm{w}_{T-1},\textnormal{Z}_{n})+\sqrt{\frac{2\eta_{T}}{\beta_{T}}}\textnormal{N};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z}\right)$
$\displaystyle\leq\frac{\beta_{T}\eta_{T}}{4b^{2}}\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\bm{w}_{T-1},\textnormal{Z}_{n})\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z}\right).$
(84)

Substituting (84) into (83) gives

$\displaystyle
I(\textnormal{W}_{T};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z})\leq\frac{\beta_{T}\eta_{T}}{4b^{2}}\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\bm{w}_{T-1},\textnormal{Z}_{n})\mid\textnormal{W}^{(T-1)}=\bm{w},\textnormal{Z}^{(n-1)}=\bm{z}\right).$

Taking expectation w.r.t. $(\textnormal{W}^{(T-1)},\textnormal{Z}^{(n-1)})$ on
both sides of the above inequality and using the law of total variance lead to

$\displaystyle
I(\textnormal{W}_{T};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)},\textnormal{Z}^{(n-1)})\leq\frac{\beta_{T}\eta_{T}}{4b^{2}}\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{T-1},\textnormal{Z}_{n})\right).$
(85)

To summarize, (82) and (85) can be rewritten as

$\displaystyle
I(\textnormal{W}_{T};\textnormal{Z}_{n}\mid\textnormal{W}^{(T-1)},\textnormal{Z}^{(n-1)})$
(86)
$\displaystyle\leq\begin{cases}\frac{\beta_{T}\eta_{T}}{4b^{2}}\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{T-1},\textnormal{Z}_{n})\right)\quad&\text{if
}\textnormal{Z}_{n}\text{ is used at the }T\text{-th iteration},\\\
0&\text{otherwise.}\end{cases}$

Assume that the data point $\textnormal{Z}_{n}$ belongs to the $j$-th mini-
batch $\textnormal{S}_{j}$. Now substituting (86) into (81) and doing this
procedure recursively lead to

$\displaystyle
I(\textnormal{W}^{(T)},\textnormal{Z}^{(n-1)};\textnormal{Z}_{n})\leq\sum_{t\in\mathcal{T}_{j}}\frac{\beta_{t}\eta_{t}}{4b^{2}}\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{Z}_{n})\right),$

where the set $\mathcal{T}_{j}$ contains the indices of iterations in which
the mini-batch $\textnormal{S}_{j}$ is used. Hence, this upper bound along
with (80) naturally gives

$\displaystyle
I(\textnormal{W};\textnormal{Z}_{n})\leq\sum_{t\in\mathcal{T}_{j}}\frac{\beta_{t}\eta_{t}}{4b^{2}}\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{Z}_{n})\right).$
(87)

By symmetry, for any data point in $\textnormal{S}_{j}$ besides
$\textnormal{Z}_{n}$, the mutual information between W and this data point can
be upper bound by the right-hand side of (87) as well. Finally, recall that
Lemma 1 provides an upper bound for the expected generalization gap:

$\displaystyle\frac{\sqrt{2}\sigma}{n}\sum_{i=1}^{n}\sqrt{I(\textnormal{W}_{T};\textnormal{Z}_{i})}=\frac{\sqrt{2}\sigma}{n}\sum_{j=1}^{m}\sum_{\textnormal{Z}\in\textnormal{S}_{j}}\sqrt{I(\textnormal{W}_{T};\textnormal{Z})}.$
(88)

By substituting (87) into the above expression, we know the expected
generalization gap can be further upper bounded by

$\displaystyle\frac{\sqrt{2}\sigma}{2n}\sum_{j=1}^{m}\sqrt{\sum_{t\in\mathcal{T}_{j}}\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\bar{\textnormal{Z}}_{j})\right)},$

where $\bar{\textnormal{Z}}_{j}$ is any data point in the mini-batch
$\textnormal{S}_{j}$.

Finally, we are in a position to prove Proposition 4.

Proof  Consider a new loss function and the gradient of a new surrogate loss:

$\displaystyle\ell(\bm{w},\textnormal{S}_{j})\triangleq\frac{1}{b}\sum_{\textnormal{Z}\in\textnormal{S}_{j}}\ell(\bm{w},\textnormal{Z}),\quad\nabla_{\bm{w}}\hat{\ell}(\bm{w},\textnormal{S}_{j})\triangleq\frac{1}{b}\sum_{\textnormal{Z}\in\textnormal{S}_{j}}\nabla_{\bm{w}}\hat{\ell}(\bm{w},\textnormal{Z}).$

Then $\ell(\bm{w},\textnormal{S}_{j})$ is $\sigma/\sqrt{b}$-sub-Gaussian under
$\textnormal{S}_{j}\sim\mu^{\otimes b}$ for all $\bm{w}\in\mathcal{W}$. We
view each mini-batch $\textnormal{S}_{j}$ as a data point and view
$\ell(\bm{w},\textnormal{S}_{j})$ as a new loss function. By using Lemma 9, we
obtain:

$\displaystyle\left|\mathbb{E}\left[L_{\mu}(\textnormal{W})-L_{\textnormal{S}}(\textnormal{W})\right]\right|\leq\frac{\sqrt{2}\sigma}{2m\sqrt{b}}\sum_{j=1}^{m}\sqrt{\sum_{t\in\mathcal{T}_{j}}\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{S}_{j})\right)}.$
(89)

Since the dataset contains $n$ data points and is divided into $m$ disjoint
mini-batches with size $b$, we have $n=mb$. Substituting this into (89) leads
to the desired conclusion.

###  D.4 Proof of Corollary 1

Proof  The Minkowski inequality implies that for any non-negative $x_{i}$, the
inequality $\sqrt{\sum_{i}x_{i}}\leq\sum_{i}\sqrt{x_{i}}$ holds. Therefore, we
can further upper bound the generalization bound in Lemma 9 by

$\displaystyle\frac{\sqrt{2}\sigma}{2n}\sum_{j=1}^{m}\sum_{t\in\mathcal{T}_{j}}\sqrt{\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\bar{\textnormal{Z}}_{j})\right)}=\frac{\sqrt{2}\sigma}{2n}\sum_{t=1}^{T}\sqrt{\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{Z}^{\dagger}_{t})\right)}.$

Alternatively, by Jensen’s inequality and $n=mb$, we can further upper bound
the generalization bound in Lemma 9 by

$\displaystyle\frac{\sqrt{2}\sigma}{2}\sqrt{\frac{1}{bn}\sum_{t=1}^{T}\beta_{t}\eta_{t}\cdot\mathsf{Var}\left(\nabla_{\bm{w}}\hat{\ell}(\textnormal{W}_{t-1},\textnormal{Z}^{\dagger}_{t})\right)}.$

##  E Supporting Experimental Results

Recall that our generalization bound in Proposition 4 involves the variance of
gradients. To estimate this quantity from data, we repeat our experiments 4
times and record the batch gradient at each iteration. This batch gradient is
the one used for updating the parameters in the SGLD algorithm so it does not
require any additional computations. Then we estimate the variance of
gradients by using the population variance of the recorded batch gradients.
Finally, we repeat the above procedure 4 times for computing the standard
deviation, leading to e.g., the shaded areas in Figure 1. We provide
experimental details in Table 2 and 3 and code in
https://github.com/yih117/Analyzing-the-Generalization-Capability-of-SGLD-
Using-Properties-of-Gaussian-Channels for reproducing our experiments.

Parameter | Details
---|---
Dataset | MNIST
Number of training data | 5000
Batch size | 500
Learning rate | Initialization = 0.03, decay rate = 0.96, decay steps=2000
Inverse temperature | $\beta_{t}=10^{6}/(2\eta_{t})$
Architecture | MLP with ReLU activation
Depth | 3 layers
Width | 64 hidden units
Objective function | Cross-entropy loss
Loss function | 0-1 loss

Table 2: Experiment details of Figure 1 and 2 on the MNIST dataset. The
network width is varying among $\\{16,32,64,128,256\\}$ hidden units for
Figure 2.

Parameter | Details
---|---
Dataset | CIFAR-10 and SVHN
Number of training data | 5000
Batch size | 500
Learning rate | Initialization = 0.03, decay rate = 0.96, decay steps = 2000
Inverse temperature | $\beta_{t}=10^{6}/(2\eta_{t})$
Architecture |  $\mathsf{conv}(5,32)$ $\mathsf{pool}(2)$ $\mathsf{conv}(5,32)$ $\mathsf{pool}(2)$ $\mathsf{fc}(120)$ $\mathsf{fc}(84)$ $\mathsf{fc}(10)$
Objective function | Cross-entropy loss
Loss function | 0-1 loss

Table 3: Experiment details of Figure 1 and 2 on the CIFAR-10 and SVHN
datasets. Here $\mathsf{conv}(k,w)$ is a $k\times k$ convolutional layer with
$w$ filters; $\mathsf{pool}(k)$ is a $k\times k$ max pooling layer; and
$\mathsf{fc}(k)$ is a fully connected layer with $k$ units. The convolutional
layers and the fully connected layers all use ReLU activation function. The
network width (i.e., number of filters in CNN) is varying among
$\\{8,16,32,64,128\\}$ for Figure 2.