# Privacy Loss of Noisy Stochastic Gradient Descent Might Converge Even for
Non-Convex Losses

Shahab Asoodeh and Mario Diaz S. Asoodeh is with Department of Computing and
Software, McMaster University (e-mail: asoodeh@mcmaster.ca). M. Diaz is with
the Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas,
Universidad Nacional Autónoma de México, Coyoacán, 04510, Mexico (e-mail:
mario.diaz@sigma.iimas.unam.mx).

###### Abstract

The Noisy-SGD algorithm is widely used for privately training machine learning
models. Traditional privacy analyses of this algorithm assume that the
internal state is publicly revealed, resulting in privacy loss bounds that
increase indefinitely with the number of iterations. However, recent findings
have shown that if the internal state remains hidden, then the privacy loss
might remain bounded. Nevertheless, this remarkable result heavily relies on
the assumption of (strong) convexity of the loss function. It remains an
important open problem to further relax this condition while proving similar
convergent upper bounds on the privacy loss. In this work, we address this
problem for DP-SGD, a popular variant of Noisy-SGD that incorporates gradient
clipping to limit the impact of individual samples on the training process.
Our findings demonstrate that the privacy loss of projected DP-SGD converges
exponentially fast, without requiring convexity or smoothness assumptions on
the loss function. In addition, we analyze the privacy loss of regularized
(unprojected) DP-SGD. To obtain these results, we directly analyze the hockey-
stick divergence between coupled stochastic processes by relying on non-linear
data processing inequalities.

##  I Introduction

Nowadays, Machine Learning (ML) models are trained using vast amounts of
sensitive data, which increases the risk of privacy breaches [CTW+21, CLE+19].
To safeguard individuals’ privacy, a commonly employed approach involves
adding noise to the model parameters at each step of the training process. One
popular method is the noisy stochastic gradient descent algorithm (Noisy-SGD),
wherein Gaussian noise with calibrated covariance is added to the gradient of
the batch loss function [ACG+16]. This algorithm closely resembles non-private
stochastic gradient descent and can be utilized in a wide range of machine
learning architectures. Consequently, it has been integrated into mainstream
ML platforms like TensorFlow [ABC+16] and PyTorch [YSS+21]. However, despite
the widespread usage and simplicity of Noisy-SGD, a tight analysis of its
privacy loss, i.e., its differential privacy parameters, has remained open.

Traditional privacy analyses of Noisy-SGD make assumptions about the release
of intermediate updates and employ composition theorems for approximate
differential privacy (DP) or Rényi differential privacy (RDP) to estimate the
privacy loss [ACG+16, WBK18]. In general, these analyses yield privacy loss
bounds that grow unboundedly as the number of iterations increases. According
to those results, in order to preserve privacy, it becomes necessary to
restrict the number of iterations allowed for Noisy-SGD, resulting in a sub-
optimal optimization error.

In many practical scenarios, only the final parameters of the model are made
public. This scenario, known as the hidden state setting111This setting was
first introduced in [FMTT18] and is sometimes referred to as the privacy
amplification by iteration., prompted Chourasia et al. [CYS21] to propose a
novel framework for analyzing the privacy loss of iterative algorithms. By
relying on a discretization of the Stochastic Gradient Langevin Dynamic
(SGLD), they derived privacy loss bounds for gradient descent that converge as
the number of iterations goes to infinity. Although this result is specific to
full batch gradient descent under smooth and strongly convex losses, it is
remarkable because it demonstrates that in the hidden state setting, it is
possible to run the algorithm without necessarily more privacy degradation.

In recent studies, Ye and Shokri [YS22] as well as Ryffel et al. [RBP22] have
achieved significant progress in understanding the privacy guarantees in the
more practical mini-batch setting, i.e., Noisy-SGD. Specifically, they
established convergent privacy loss bounds for Noisy-SGD under strongly convex
loss functions. These results represent an important step towards the
understanding of the privacy guarantees of Noisy-SGD. Concurrently, Altschuler
and Talwar [AT22] employed a fundamentally distinct technique to demonstrate
the convergence of the privacy loss of projected Noisy-SGD under convex
losses. Although the shift from strongly convex to convex loss might appear
insignificant, the technical challenges involved are non-trivial and represent
an important achievement in this field.

The works mentioned earlier heavily rely on the (strong) convexity of the loss
function. Therefore, for instance, Altschuler and Talwar [AT22] acknowledged
that their techniques cannot be directly applied to general DP-SGD, a popular
variant of Noisy-SGD where gradients are clipped to limit the impact of
individual samples on the training process. Given the widespread use of DP-SGD
in practice, it is crucial to develop appropriate techniques that can handle
the non-convex nature of this variant of Noisy-SGD. Thus, as pointed out in
both [YS22] and [AT22], it remains an important open problem to relax the
convexity (and smoothness) assumption, while proving convergent privacy upper
bounds. This paper aims to address this challenge by providing bounds for the
privacy loss of projected DP-SGD that converge exponentially fast as the
number of iterations goes to infinity for non-convex loss functions.
Additionally, we present privacy loss bounds for regularized (unprojected) DP-
SGD that exhibit favorable numerical behavior. To the best of our knowledge,
this is the first study to establish convergent privacy loss bounds for a non-
convex variation of Noisy-SGD.

Fig. 1: The privacy loss of DP-SGD with the parameters:
$D=3,C=2,\eta=0.01,\sigma=1,p=0.001$, and $\varepsilon=3$ (left) and
$\delta=10^{-3}$ (right).

###  I-A Our Contributions and Techniques

Throughout, we focus on the projected version of DP-SGD that we introduce
next. Let $\sigma\geq 0$ and $\mathcal{W}\subset\mathbb{R}^{d}$. Given a
dataset $\mathcal{X}=\\{x_{1},\ldots,x_{n}\\}$, we consider the iterative
process $\\{W_{t}\\}_{t\leq T}$ determined by $W_{0}\sim\mu_{0}$ and

$W_{t}=\Pi\big{[}\psi_{B_{t}}(W_{t-1})+\sigma Z_{t}\big{]},$ (1)

where $\Pi:\mathbb{R}^{d}\to\mathcal{W}$ is the projection onto $\mathcal{W}$,
$Z_{t}$ is a standard Gaussian vector, $B_{t}$ is a random batch, and
$\psi_{B}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ for $B\subseteq\\{1,\dots,n\\}$ is
the update function given by

$\psi_{B}(w)=w-\frac{\eta}{\lvert B\rvert}\sum_{i\in
B}\mathrm{Clip}\big{(}\nabla\ell(w,x_{i})\big{)}.$

Here, $\ell$ is the loss function, $\eta$ the learning rate, and the mapping
$\mathrm{Clip}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ is defined as

$\mathrm{Clip}(v)\coloneqq\min\Big{\\{}1,\frac{C}{\|v\|}\Big{\\}}v,$ (2)

where $C>0$ is the so-called clipping constant. In this work, we consider two
batching strategies: Poisson sampling where each individual sample is chosen
with probability $p\in(0,1)$, and sampling without replacement where we chose
a random batch of size $b\leq n$.

For ease of notation, we let $\mathsf{K}_{t}\coloneqq P_{W_{t}|W_{t-1}}$ be
the update kernel that characterizes the dynamic of the iterative process (1).
Under the _hidden state assumption_ , the iterative process (1) is
$(\varepsilon,\delta)$-differentially private after $T$ iterations if

$\mathsf{E}_{\varepsilon}(\mathsf{K}_{T}\cdots\mathsf{K}_{1}\mu_{0}\|\mathsf{K}^{\prime}_{T}\cdots\mathsf{K}^{\prime}_{1}\mu_{0})\leq\delta,$
(3)

where $\mathsf{K}_{1},\dots,\mathsf{K}_{T}$ and
$\mathsf{K}^{\prime}_{1},\dots,\mathsf{K}^{\prime}_{T}$ are the update kernels
in (1) corresponding to neighboring datasets $\mathcal{X}$ and
$\mathcal{X}^{\prime}$, respectively, and
$\mathsf{E}_{\varepsilon}(\cdot\|\cdot)$ denotes the hockey-stick divergence.
See Sec. II for preliminaries on differential privacy, hockey-stick
divergence, and contraction of Markov kernels. Hence, to obtain a privacy loss
bound for the iterative process described in (1), it is enough to study the
hockey-stick divergence in (3). We do so by establishing a coupled non-linear
data processing inequality, i.e., we show that there exist
$\alpha_{t},\beta_{t}\in(0,1)$ such that, for all probability measures $\mu$
and $\nu$ on $\mathcal{W}$,

$\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)\leq\alpha_{t}\mathsf{E}_{\varepsilon}(\mu\|\nu)+\beta_{t}.$
(4)

The previous inequality is a hockey-stick divergence analogue of a recursion
established by Ye and Shokri to study the Rényi divergence associated with
Noisy-SGD in [YS22, Lemma 3.2]. The proof of the coupled non-linear data
processing inequality in (4) relies on the joint-convexity of the hockey-stick
divergence and the strong data processing inequality for the input-constrained
Gaussian kernel proved by Asoodeh et al. in [ADC23]. In fact, note that the
update kernel $\mathsf{K}_{t}$ could be expressed as a composition of three
Markov kernels, namely, an operator specified by the update function and the
batching strategy (sub-sampling), a Gaussian kernel, and finally a projection
operator. The non-linear term in (4) comes mainly from the sub-sampling
operator, while the projection operator ensures that the input for the
Gaussian kernel remains bounded.

Upon the coupled non-linear data processing inequality (4), our main result
provides a convergent upper bound for the privacy loss of DP-SGD.

######  Main Theorem (Informal).

Let $\varepsilon\geq 0$. After $T\in\mathbb{N}$ iterations, the projected DP-
SGD under sampling without replacement is
$(\varepsilon,\delta)$-differentially private with

$\delta\leq\frac{1-[(1-p)\theta]^{T}}{1-(1-p)\theta}p\theta,$ (5)

where $p\coloneqq b/n$ and $\theta\in(0,1)$ is a constant depending on the
privacy parameter $\varepsilon$, diameter of the parameter space
$\mathcal{W}$, the learning rate $\eta$, the clipping constant $C$, and the
noise variance $\sigma^{2}$.

While this theorem provides a convergent upper bound on $\delta$ for a given
$\varepsilon$, we can convert it to obtain a convergent upper bound on
$\varepsilon$ for a given $\delta$, as illustrated in Fig. 1. The details of
the conversion process are given in Appendix A. Note that the upper bound in
(5) is always less than 1. Therefore, our main theorem establishes, for the
first time, that the privacy loss of projected DP-SGD converges exponentially
fast without convexity or smoothness assumptions on the loss function.

In Sec. III, we derive a privacy loss bound similar to (5) for projected DP-
SGD under Poisson sampling. Additionally, we investigate a regularized
(unprojected) version of DP-SGD. While the analysis and resulting privacy loss
bound for the latter are more complex, they demonstrate favorable numerical
behavior. Finally, we provide a discussion of our findings and highlight open
problems for future directions in Section IV.

###  I-B Comparison with Previous Work

Our work is closely connected to the rapidly expanding literature on privacy
amplification, see, e.g., [FMTT18, BBGG19, FKT20, ADC20]. Recently, Ye and
Shokri [YS22] and Altschuler and Talwar [AT22] established convergent privacy
loss bounds for certain variants of Noisy-SGD. In this work, we focus on
establishing convergent privacy loss bounds for DP-SGD, a widely used variant
of Noisy-SGD which defines a non-convex optimization problem. A distinctive
feature of our work is that, unlike previous studies in privacy amplification
that rely on Rényi differential privacy and employ RDP-to-DP conversion, we
directly employ the hockey-stick divergence, enabling us to formulate bounds
directly in terms of $(\varepsilon,\delta)$-differential privacy. This is a
convenient feature of our bounds, as the RDP-to-DP conversion cannot be
universally applied due to restrictions on the order of the Rényi divergence
and on the noise variance, see e.g., [AT22, Remark 1.4]. Moreover, it is known
that RDP is only a lossy representation of privacy loss [ZDW22].

In our work, we study sub-sampling using a mixture of distributions and derive
recursions for computing the divergence between these mixtures, akin to the
approaches employed by Chourasia et al. [CYS21] and Ye and Shokri [YS22].
However, we take a different approach by leveraging the joint convexity of the
hockey-stick divergence instead of relying on the exponentiated Rényi
divergence. The resulting recursion, which we refer to as the coupled non-
linear data processing inequality, can be seen as an analog of the privacy
amplification by sub-sampling framework proposed by Ye and Shokri in [YS22],
but applied within the context of the hockey-stick divergence. The term
coupled carries a similar meaning as in the work by Altschuler and Talwar
[AT22], where two identical iterative processes are coupled through a
potentially different dataset or initialization. In our analysis of
regularized DP-SGD, we extend this argument by considering couplings between
different iterative processes.

An essential aspect of Altschuler and Talwar’s analysis involves investigating
the privacy amplification achieved through the composition of projection
operators with noisy gradients. In the context of the hockey-stick divergence,
Asoodeh et al. [ADC23] utilized the contraction coefficient of Markov kernels
to derive privacy amplification bounds that take into account the diameter of
the parameter space. Their work, along with subsequent studies [SBD21,
ACCO21], relies solely on the strong data processing inequality (SDPI) to
analyze the privacy guarantees of general iterative processes. However, the
sub-sampling framework does not align well with the multiplicative nature of
the SDPI. In our work, we build upon their findings and establish a coupled
non-linear data processing inequality specifically tailored to the sub-
sampling framework.

An important characteristic of DP-SGD is the gradient clipping. As noted by
Altschuler and Talwar [AT22], “clipped gradients do not correspond to
gradients of a convex loss”, and hence their results (as well as all other
works in the literature that aim at proving convergent privacy bounds) do not
apply. To deal with the non-convexity of DP-SGD, we adopt an alternative
approach that avoids requiring the geometric contraction of the update
mappings. Instead, we solely rely on the probabilistic contraction of the
Markov kernels under hockey-stick divergence. This enables us to analyze the
privacy loss without imposing any convexity assumption on the loss function.

###  I-C Notation

We use upper-care letters (e.g., $W$) to denote random variables and
calligraphic letters to represent their alphabets (e.g., $\mathcal{W}$). The
set of all distributions on $\mathcal{W}$ is denoted by
$\mathcal{P}(\mathcal{W})$. A Markov kernel
$\mathsf{K}:\mathcal{D}\to\mathcal{P}(\mathcal{W})$ is specified by a
collection of distributions
$\\{\mathsf{K}(x)\in\mathcal{P}(\mathcal{W}):x\in\mathcal{D}\\}$. Given a
Markov kernel $\mathsf{K}:\mathcal{D}\to\mathcal{P}(\mathcal{W})$ and
$\mu\in\mathcal{P}(\mathcal{D})$, we denote by $\mathsf{K}\mu$ the push-
forward of $\mu$ under $\mathsf{K}$, i.e., the output distribution of
$\mathsf{K}$ when the input is distributed according to $\mu$, and is given by
$\mathsf{K}\mu\coloneqq\int\mu(\text{d}x)\mathsf{K}(x)$. Notice that any
deterministic function $f:\mathcal{W}\to\mathcal{W}$ can be viewed as a Markov
kernel determined by $w\mapsto\delta_{f(w)}.$ Thus, $f\mu$ denotes the output
distribution of $f(W)$ when $W\sim\mu$. We use $\mathbb{E}_{\mu}[\cdot]$ to
write the expectation with respect to $\mu$. For an integer $n\geq 1$, we let
$[n]\coloneqq\\{1,\dots,n\\}$. We write $\mathsf{M}(\mathcal{X})$ to denote
the output distribution of a randomized algorithm $\mathsf{M}$. For a set
$\mathcal{D}\subset\mathbb{R}^{d}$, we let $\textnormal{dia}(\mathcal{D})$ be
its diameter, i.e.,
$\displaystyle\textnormal{dia}(\mathcal{D})=\sup_{x_{1},x_{2}\in\mathcal{D}}\lVert
x_{2}-x_{1}\rVert$.

##  II Preliminaries

###  II-A Differential Privacy

Differential privacy (DP) [DMNS06] has become the de-facto standard for
quantifying privacy in today’s machine learning. Intuitively, DP measures how
indistinguishable the outputs of a learning algorithm are when running on two
neighboring datasets, i.e., two datasets that differ in one entry. To quantify
such indistinguishability, one can measure the distance between
$\mathsf{M}(\mathcal{X})$ and $\mathsf{M}(\mathcal{X}^{\prime})$, output
distributions of the mechanism $\mathsf{M}$ when running on two neighboring
datasets $\mathcal{X}$ and $\mathcal{X}^{\prime}$. The original definition of
approximate differential privacy was based on the following “distance”
measure, often called the hockey-stick divergence.

######  Definition 1 (Hockey-stick divergence).

Given $\varepsilon\geq 0$ and two probability measures $\mu$ and $\nu$ in
$\mathcal{P}(\mathcal{W})$, the hockey-stick divergence between $\mu$ and
$\nu$ is defined as

$\mathsf{E}_{\varepsilon}(\mu\|\nu)\coloneqq\int\text{d}(\mu-e^{\varepsilon}\nu)^{+}=\sup_{A\subset\mathcal{W}}~{}[\mu(A)-e^{\varepsilon}\nu(A)],$

where $(\mu-e^{\varepsilon}\nu)^{+}$ is the positive part of the signed
measure $\mu-e^{\varepsilon}\nu$.

Observe that when $\varepsilon=0$, the hockey-stick divergence reduces to
total-variation distance, that is
$\mathsf{E}_{0}(\mu\|\nu)=\lVert\mu-\nu\rVert_{\mathrm{TV}}$. With this
definition at hand, we now define approximate differential privacy.

######  Definition 2 ([DMNS06]).

A randomized algorithm $\mathsf{M}$ is said to be $(\varepsilon,\delta)$-DP
if, for any two neighboring datasets $\mathcal{X}$ and $\mathcal{X}^{\prime}$,
we have that
$\mathsf{E}_{\varepsilon}(\mathsf{M}(\mathcal{X})\|\mathsf{M}(\mathcal{X}^{\prime}))\leq\delta$.

Note that one can replace the hockey-stick divergence in the above definition
with Rényi divergence to arrive at the definition of Rényi differential
privacy (RDP) [Mir17, BS16].

###  II-B Contraction Coefficient of Hockey-Stick Divergence

It is known that the hockey-stick divergence satisfies the data processing
inequality, that is,
$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}\nu)\leq\mathsf{E}_{\varepsilon}(\mu\|\nu)$
for any probability measures $\mu$ and $\nu$, and any Markov kernel
$\mathsf{K}$222It is worth noting that hockey-stick divergence is a special
case of a larger family of divergences known as $f$-divergence, and that all
$f$-divergences satisfy the data processing inequality. For more details, see
[SV16, Rag16]. For many non-trivial Markov kernels this inequality is strict.
Consequently, one can think of a stronger data processing inequality by
finding a constant $\eta\leq 1$ such that
$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}\nu)\leq\eta\mathsf{E}_{\varepsilon}(\mu\|\nu)$.
The smallest such constant $\eta$ is called contraction coefficient of hockey-
stick divergence for Markov kernel $\mathsf{K}$ and is denoted by
$\eta_{\varepsilon}(\mathsf{K})$. In other words, we have

$\eta_{\varepsilon}(\mathsf{K})\coloneqq\sup_{\begin{subarray}{c}\mu,\nu\in\mathcal{P}(\mathcal{W}):\\\
\mathsf{E}_{\varepsilon}(\mu\|\nu)\neq
0\end{subarray}}\frac{\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}\nu)}{\mathsf{E}_{\varepsilon}(\mu\|\nu)}.$
(6)

If $\eta_{\varepsilon}(\mathsf{K})<1$, then we say that $\mathsf{K}$ satisfies
a strong data processing inequality (SDPI) for hockey-stick divergence with
contraction coefficient $\eta_{\varepsilon}(\mathsf{K})$.

It was recently shown [ADC23, Theorem 2] that for a Markov kernel
$\mathsf{K}:\mathcal{W}\to\mathcal{P}(\mathbb{R}^{d})$

$\eta_{\varepsilon}(\mathsf{K})=\sup_{x_{1},x_{2}\in\mathcal{W}}\mathsf{E}_{\varepsilon}(\mathsf{K}(x_{1})\|\mathsf{K}(x_{2})).$

This result enables us to quantify privacy amplification by post-processing as
follows: Given an $(\varepsilon,\delta)$-DP mechanism $\mathsf{M}$ and a
Markov kernel $\mathsf{K}$, we have for any neighboring datasets $\mathcal{X}$
and $\mathcal{X}^{\prime}$

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mathsf{M}(\mathcal{X})\|\mathsf{K}\mathsf{M}(\mathcal{X}^{\prime}))\leq\mathsf{E}_{\varepsilon}(\mathsf{M}(\mathcal{X})\|\mathsf{M}(\mathcal{X}^{\prime}))\eta_{\varepsilon}(\mathsf{K})\leq\delta\sup_{x_{1},x_{2}\in\mathcal{W}}\mathsf{E}_{\varepsilon}(\mathsf{K}(x_{1})\|\mathsf{K}(x_{2})),$

indicating $\mathsf{M}\circ\mathsf{K}$ is $(\varepsilon,\delta^{\prime})$-DP
with
$\delta^{\prime}=\delta\sup_{x_{1},x_{2}\in\mathcal{W}}\mathsf{E}_{\varepsilon}(\mathsf{K}(x_{1})\|\mathsf{K}(x_{2}))$.
Thus, characterizing privacy amplification by post-processing boils down to
computing the contraction coefficient of the post-processor. If post-processor
$\mathsf{K}$ is a Gaussian Markov kernel with bounded input, then
$\eta_{\varepsilon}(\mathsf{K})$ enjoys a simple closed-form expression, as
delineated by the following proposition. Given
$\mathcal{W}\subset\mathbb{R}^{d}$ and $\sigma>0$, we define the
$\mathcal{W}$-constrained Gaussian kernel
$\mathsf{K}_{\mathrm{G}}^{\sigma}:\mathcal{W}\to\mathcal{P}(\mathbb{R}^{d})$
as

$\mathsf{K}_{\mathrm{G}}^{\sigma}(x)=\mathcal{N}(x,\sigma^{2}\mathbf{I}_{d}).$

######  Proposition 1 ([ADC23]).

Let $\mathcal{W}\subset\mathbb{R}^{d}$ and $\sigma\geq 0$. For any
$\mathcal{W}$-constrained Gaussian kernel $\mathsf{K}_{\mathrm{G}}^{\sigma}$,
we have

$\eta_{\varepsilon}(\mathsf{K}_{\mathrm{G}}^{\sigma})=\theta_{\varepsilon}\Big{(}\frac{\mathrm{dia}(\mathcal{W})}{\sigma}\Big{)},$

where

$\theta_{\varepsilon}(r)\coloneqq
Q\Big{(}\frac{\varepsilon}{r}-\frac{r}{2}\Big{)}-e^{\varepsilon}Q\Big{(}\frac{\varepsilon}{r}+\frac{r}{2}\Big{)},$

with $\displaystyle
Q(t)\coloneqq\frac{1}{\sqrt{2\pi}}\int_{t}^{\infty}e^{-u^{2}/2}\mathrm{d}u$.

In light of this result, $\mathcal{W}$-constrained Gaussian kernels satisfy
SDPI for hockey-stick divergence if $\text{dia}(\mathcal{W})<\infty$. We will
repeatedly use this observation in the next section to derive a diameter-aware
bound on the privacy parameters of DP-SGD.

##  III Main Results

In this section, we begin with a general iterative process which we later
instantiate for different versions of DP-SGD. Let $\sigma\geq 0$ and
$\mathcal{W}_{t}\subseteq\mathbb{R}^{d}$ for each $t\leq T$. We consider the
iterative process $\\{W_{t}\\}_{t\leq T}$ determined by
$W_{0}\sim\mu_{0}\in\mathcal{P}(\mathcal{W}_{0})$ and

$W_{t}=\Pi_{t}\big{[}\psi_{B_{t}}(W_{t-1})+\sigma Z_{t}\big{]},$ (7)

where $\Pi_{t}:\mathbb{R}^{d}\to\mathcal{W}_{t}$ is the projection onto
$\mathcal{W}_{t}$, $Z_{t}$ is a standard Gaussian vector independent of all
other variables, $B_{t}$ is a random batch, and
$\psi_{B}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ is an update function dependent on
the dataset $\mathcal{X}$ through the batch $B\subset[n]$. In particular, the
update kernel $\mathsf{K}_{t}\coloneqq P_{W_{t}|W_{t-1}}$ could be decomposed
as

$\mathsf{K}_{t}=\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi,$ (8)

where $\Psi:\mathbb{R}^{d}\to\mathcal{P}(\mathbb{R}^{d})$ is the kernel given
by $\Psi=\sum_{B\subset[n]}\mathbb{P}(B_{t}=B)\psi_{B}$. Recall that, by abuse
of notation, a deterministic function $\psi_{B}$ can be viewed as a Markov
kernel determined by $w\mapsto\delta_{\psi_{B}(w)}$.

Observe that the iterative process (7) is
$(\varepsilon,\delta)$-differentially private after $T$ iterations if

$\mathsf{E}_{\varepsilon}(\mathsf{K}_{T}\cdots\mathsf{K}_{1}\mu_{0}\|\mathsf{K}^{\prime}_{T}\cdots\mathsf{K}^{\prime}_{1}\mu_{0})\leq\delta,$
(9)

where $\mathsf{K}_{1},\dots,\mathsf{K}_{T}$ and
$\mathsf{K}^{\prime}_{1},\dots,\mathsf{K}^{\prime}_{T}$ are the update kernels
in (8) corresponding to neighboring datasets $\mathcal{X}$ and
$\mathcal{X}^{\prime}$, respectively. The following result presents a
machinery to bound the hockey-stick divergence in (9) using bounds for
individual update kernels $\mathsf{K}_{t}$.

######  Lemma 1.

Let $\mathcal{X}$ and $\mathcal{X}^{\prime}$ be two neighboring datasets. Let
$\\{\mathsf{K}_{t}\\}_{t\in[T]}$ and $\\{\mathsf{K}_{t}^{\prime}\\}_{t\in[T]}$
be defined as in (8) for $\mathcal{X}$ and $\mathcal{X}^{\prime}$,
respectively. If for each $t\in[T]$ there exist $\alpha_{t},\beta_{t}\in[0,1]$
such that

$\phantom{\forall\mu,\nu\in\mathcal{P}(\mathcal{W_{t-1}}),}\qquad\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)\leq\alpha_{t}\mathsf{E}_{\varepsilon}(\mu\|\nu)+\beta_{t},\qquad\forall\mu,\nu\in\mathcal{P}(\mathcal{W}_{t-1}),$
(10)

then

$\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{T}\cdots\mathsf{K}_{1}\mu\|\mathsf{K}_{T}^{\prime}\cdots\mathsf{K}_{1}^{\prime}\nu\big{)}\leq\Big{[}\prod_{t=1}^{T}\alpha_{t}\Big{]}\mathsf{E}_{\varepsilon}(\mu\|\nu)+\sum_{t=1}^{T}\beta_{t}\prod_{s=t+1}^{T}\alpha_{s}.$
(11)

The proof of this lemma in Appendix B exploits the recursive nature of (10).
We remark that Lemma 1 resembles [YS22, Lemma 3.2], in that both present
recursive relations for computing the divergence between output distributions
of process (7) when running on two neighboring datasets.

It is also worth noting that Lemma 1 differs from the framework based on the
strong data processing inequality (SDPI) proposed by Asoodeh et al. in
[ADC23]. First, the kernels $\mathsf{K}_{t}$ and $\mathsf{K}_{t}^{\prime}$ in
(10) are potentially different (although they could share some common
randomness), and thus
$\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)$
cannot be bounded directly via contraction coefficients. Second, the existence
of the additive term $\beta_{t}$ in (10) renders the upper bound in (11)
fundamentally different from the multiplicative bounds in [ADC23, Theorem 1].
In this sense, condition (10) could be regarded as a coupled non-linear DPI.
In the sequel, we prove that such condition holds for different versions of
DP-SGD, leading to the convergence of the associated privacy losses.

###  III-A Projected DP-SGD

In this section, we consider a projected version of the algorithm known as DP-
SGD introduced by Abadi et al. in [ACG+16]. As it is customary, we take
$\mathcal{W}_{t}=\mathcal{W}$ for some fixed convex set
$\mathcal{W}\subset\mathbb{R}^{d}$ and let $\Pi$ be the projection onto
$\mathcal{W}$. For a dataset $\mathcal{X}=\\{x_{1},\ldots,x_{n}\\}$, we define
the update mapping with respect to a batch $B\subset[n]$ as

$\psi_{B}(w)=w-\frac{\eta}{\lvert B\rvert}\sum_{i\in
B}\mathrm{Clip}\big{(}\nabla\ell(w,x_{i})\big{)}.$ (12)

where $\mathrm{Clip}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ is the clipping
function, defined in (2), with clipping constant $C$.

The following lemma, whose proof could be found in Appendix B, establishes a
key boundedness property of projected DP-SGD.

######  Lemma 2.

Under projected DP-SGD, we have that

$\sup_{B_{1},B_{2}\subset[n]}\sup_{w_{1},w_{2}\in\mathcal{W}}\lVert\psi_{B_{2}}(w_{2})-\psi_{B_{1}}(w_{1})\rVert\leq
D+2\eta C,$

where $D=\mathrm{dia}(\mathcal{W})$, $\eta$ is the learning rate, and $C$ is
the clipping constant.

In the sequel, we prove that the coupled non-linear DPI in (10) is satisfied
for projected DP-SGD under both Poisson sampling and sampling without
replacement.

####  III-A1 Poisson Sampling

In this sampling scheme, each datapoint is selected with probability
$p\in[0,1]$ at each iteration. Thus, the average batch size is $b=pn$. Under
Poisson sampling, the kernel $\Psi$ in (8) is given by

$\Psi=\sum_{B\subset[n]}p^{\lvert B\rvert}(1-p)^{n-\lvert B\rvert}\psi_{B}.$
(13)

The following proposition establishes the coupled non-linear DPI in (10) for
the kernel associated with projected DP-SGD under Poisson sampling.

######  Proposition 2.

Let $\mathcal{X}$ and $\mathcal{X}^{\prime}$ be two neighboring datasets. Let
$\Psi$ and $\Psi^{\prime}$ be defined as in (13) for $\mathcal{X}$ and
$\mathcal{X}^{\prime}$, respectively. If
$\mathsf{K}=\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi$ and
$\mathsf{K}^{\prime}=\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi^{\prime}$,
then, for all $\mu,\nu\in\mathcal{P}(\mathcal{W})$,

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)\leq(1-p)\theta_{\varepsilon}\bigg{(}\frac{D+2\eta
C}{\sigma}\bigg{)}E_{\varepsilon}(\mu\|\nu)+p\theta_{\varepsilon}\bigg{(}\frac{D+2\eta
C}{\sigma}\bigg{)}.$ (14)

The proof of this proposition in Appendix B indicates that the multiplicative
term in (14) comes from the batches that do not contain the different point in
$\mathcal{X}$ and $\mathcal{X}^{\prime}$ and the additive term comes from the
batches that contain such a point. In both cases, the strong data processing
inequality for input-constrained Gaussian kernels in Proposition 1 produces
the factor $\theta_{\varepsilon}$.

The previous proposition and Lemma 1 enable us to characterize the privacy
guarantees of DP-SGD under Poisson sampling.

######  Theorem 1.

Let $\varepsilon\geq 0$. After $T\in\mathbb{N}$ iterations, projected DP-SGD
under Poisson sampling is $(\varepsilon,\delta)$-differentially private with

$\delta\leq\frac{1-[(1-p)\theta]^{T}}{1-(1-p)\theta}p\theta,$

where $\theta\coloneqq\theta_{\varepsilon}\big{(}(D+2\eta C)/\sigma\big{)}$.

####  III-A2 Sampling without Replacement

In this sampling scheme, a random sample of size $b\leq n$ is selected at each
iteration. Thus, any batch $B\subseteq[n]$ of size $b$ is selected with
probability $\binom{n}{b}^{-1}$. Under the sampling without replacement, the
kernel $\Psi$ in (8) is given by

$\Psi=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert B\rvert=b}\psi_{B}.$ (15)

The following proposition establishes the coupled non-linear DPI in (10) for
the kernel associated with projected DP-SGD under sampling without
replacement.

######  Proposition 3.

Let $\mathcal{X}$ and $\mathcal{X}^{\prime}$ be two neighboring datasets. Let
$\Psi$ and $\Psi^{\prime}$ be defined as in (15) for $\mathcal{X}$ and
$\mathcal{X}^{\prime}$, respectively. If
$\mathsf{K}=\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi$ and
$\mathsf{K}^{\prime}=\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi^{\prime}$,
then, for all $\mu,\nu\in\mathcal{P}(\mathcal{W})$,

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)\leq\bigg{(}1-\frac{b}{n}\bigg{)}\theta_{\varepsilon}\bigg{(}\frac{D+2\eta
C}{\sigma}\bigg{)}\mathsf{E}_{\varepsilon}(\mu\|\nu)+\frac{b}{n}\theta_{\varepsilon}\bigg{(}\frac{D+2\eta
C}{\sigma}\bigg{)}.$

The proof of the previous proposition, which can be found in Appendix B, is
similar to the proof of Proposition 2. Together with Lemma 1, Proposition 3
enable us to characterize the privacy guarantees of DP-SGD under sampling
without replacement.

######  Theorem 2.

Let $\varepsilon\geq 0$. After $T\in\mathbb{N}$ iterations, the projected DP-
SGD under sampling without replacement is
$(\varepsilon,\delta)$-differentially private with

$\delta\leq\frac{1-[(1-p)\theta]^{T}}{1-(1-p)\theta}p\theta,$

where $p\coloneqq b/n$ and $\theta\coloneqq\theta_{\varepsilon}\big{(}(D+2\eta
C)/\sigma\big{)}$.

Comparing this theorem with Theorem 1, we observe that DP-SGD under sampling
without replacement with batch size $b$ has the same privacy guarantees as DP-
SGD under Poisson sampling with sub-sampling probability $b/n$.

Theorems 1 and 2 identify the privacy guarantees of projected DP-SGD, where
the update at each iteration is projected onto a given parameter space
$\mathcal{W}$. In the next section, we seek to study the privacy guarantees of
regularized (unprojected) DP-SGD using the framework established in Lemma 1.

###  III-B Regularized DP-SGD

In this section, we analyze the privacy loss of regularized DP-SGD. For ease
of exposition, in the sequel we only consider sampling without replacement.
The analysis of Poisson sampling is similar, so the details are left to the
reader.

Let $\lambda\in(0,1)$. We consider the iterative process
$\\{\tilde{W}_{t}\\}_{t\leq T}$ determined by333The assumption
$\tilde{W}_{0}=0$ is immaterial but we adopted it for ease of exposition.
$\tilde{W}_{0}=0$ and

$\tilde{W}_{t}=\psi_{B_{t}}(\tilde{W}_{t-1})+\sigma Z_{t},$ (16)

where $B_{t}$ is a random batch of size $b$ and, for each $B\subset[n]$,

$\psi_{B}(w)=(1-\lambda)w-\frac{\eta}{\lvert B\rvert}\sum_{i\in
B}\mathrm{Clip}\big{(}\nabla\ell(w,x_{i})\big{)}.$ (17)

Note that we assume that the regularization term (i.e., $\lambda w$) is added
after clipping, as considered by Ye and Shokri in their recent work [YS22].
Since there is no projection in this case, the update kernel
$\tilde{\mathsf{K}}_{t}\coloneqq P_{\tilde{W}_{t}|\tilde{W}_{t-1}}$ could be
decomposed as

$\tilde{\mathsf{K}}_{t}=\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi\qquad\text{where}\qquad\Psi=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\psi_{B}.$ (18)

We study the privacy loss of (16) by relying on the particular instance of the
iterative process (7) described next.

Let $\kappa>0$. We consider the iterative process $\\{W_{t}\\}_{t\leq T}$
determined by $W_{0}=0$ and

$W_{t}=\Pi_{t}\big{[}\psi_{B_{t}}(W_{t-1})+\sigma Z_{t}\big{]},$ (19)

where $\Pi_{t}:\mathbb{R}^{d}\to\mathcal{W}_{t}$ is the projection onto
$\mathcal{W}_{t}\coloneqq\mathbb{B}_{d}(r_{t})=\\{w\in\mathbb{R}^{d}:\|w\|\leq
r_{t}\\}$ with

$r_{t}=(\eta C+\kappa\sigma)\frac{1-(1-\lambda)^{t}}{\lambda}.$ (20)

Note that the update kernel $\mathsf{K}_{t}\coloneqq P_{W_{t}|W_{t-1}}$ could
be decomposed as
$\mathsf{K}_{t}=\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi$. The
introduction of the iterative process $\\{W_{t}\\}_{t\leq T}$ is motivated by
the following three intuitions:

  * (i)

Since $\mathsf{K}_{t}$ and $\tilde{\mathsf{K}}_{t}$ differ only by the
projection step $\Pi_{t}$, by making $\kappa$ large enough this projection
becomes immaterial, i.e., if $\kappa$ is large enough then $\lVert
W_{t}\rVert\leq r_{t}$ with high probability. In this case, the distributions
of $\\{W_{t}\\}_{t\leq T}$ and $\\{\tilde{W}_{t}\\}_{t\leq T}$ are close.

  * (ii)

The projection step $\Pi_{t}$ in $\mathsf{K}_{t}$ allows us to establish a
coupled non-linear DPI similar to the one derived for projected DP-SGD in
Proposition 3. This, together with Lemma 1, enables us to characterize the
privacy guarantees of $\\{W_{t}\\}_{t\leq T}$.

  * (iii)

Upon a triangle inequality for the hockey-stick divergence by Liu et al.
[LCV16], we can transfer the privacy guarantees of $\\{W_{t}\\}_{t\leq T}$ to
$\\{\tilde{W}_{t}\\}_{t\leq T}$.

The following proposition formalizes the first intuition.

######  Proposition 4.

Let $\chi^{2}_{d}$ be a chi-squared random variable with $d$ degrees of
freedom. If $W_{t}\sim\mu_{t}$ and $\tilde{W}_{t}\sim\tilde{\mu}_{t}$, then
$\displaystyle\lVert\tilde{\mu}_{t}-\mu_{t}\rVert_{\mathrm{TV}}\leq
1-\mathbb{P}(\chi^{2}_{d}\leq\kappa^{2})^{t}$ for all $t\geq 0$.

As anticipated, sufficiently large $\kappa$ implies that the distributions of
$\\{W_{t}\\}_{t\leq T}$ and $\\{\tilde{W}_{t}\\}_{t\leq T}$ are close. The
next proposition provides a coupled non-linear DPI for $\\{W_{t}\\}_{t\leq
T}$, formalizing the second intuition above.

######  Proposition 5.

Let $\mathcal{X}$ and $\mathcal{X}^{\prime}$ be two neighboring datasets. For
each $B\subset[n]$, let $\psi_{B}$ and $\psi_{B}^{\prime}$ be defined as in
(17) for $\mathcal{X}$ and $\mathcal{X}^{\prime}$, respectively. If
$\mathsf{K}_{t}=\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi$ and
$\mathsf{K}_{t}^{\prime}=\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi^{\prime}$
where $\Pi_{t}$ is the projection onto
$\mathcal{W}_{t}=\mathbb{B}_{d}(r_{t})$, then, for all
$\mu,\nu\in\mathcal{P}(\mathcal{W}_{t-1})$,

$\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)\leq\bigg{(}1-\frac{b}{n}\bigg{)}\theta_{\varepsilon}\bigg{(}\frac{r_{t}-\sigma\kappa}{\sigma}\bigg{)}\mathsf{E}_{\varepsilon}(\mu\|\nu)+\frac{b}{n}\theta_{\varepsilon}\bigg{(}\frac{r_{t}-\sigma\kappa}{\sigma}\bigg{)}.$

Finally, we obtain the privacy loss of $\\{\tilde{W}_{t}\\}_{t\leq T}$ upon
Propositions 4 and 5. The proof of the following theorem, which can be found
in Appendix B, relies on a triangle inequality for the hockey-stick divergence
proved by Liu et al. in [LCV16].

######  Theorem 3.

Let $\varepsilon\geq 0$ and $\kappa>0$. After $T\in\mathbb{N}$ iterations,
regularized DP-SGD under sampling without replacement is
$(\varepsilon,\delta)$-differentially private with

$\delta\leq(1+e^{\varepsilon})\Big{[}1-\mathbb{P}(\chi^{2}_{d}\leq\kappa^{2})^{T}\Big{]}+\frac{b}{n-b}\sum_{t=1}^{T}\bigg{(}1-\frac{b}{n}\bigg{)}^{T-t}\prod_{s=t}^{T}\theta_{\varepsilon}\bigg{(}\frac{r_{s}-\sigma\kappa}{\sigma}\bigg{)},$
(21)

where $\displaystyle r_{s}=(\eta
C+\kappa\sigma)\frac{1-(1-\lambda)^{s}}{\lambda}$.

Note that (21) holds for every $\kappa>0$. Hence, this parameter has to be
optimized (numerically) in order to obtain the tightest bound. However, the
numerical optimization of (21) could be subtle for some range of parameters.
Therefore, it is unclear if the optimized bound in Theorem 3 converges with
respect to the number of iterations. In fact, Figure 2 shows that even
numerically such convergence is unclear. Nonetheless, for some parameter
values the bound produces reasonable estimates for the privacy loss.

Fig. 2: The privacy loss of regularized unprojected DP-SGD according to
Theorem 3 with parameters: $C=1,\eta=0.1,\sigma=5,\varepsilon=5,p=0.001$, and
$\lambda=0.65$ (left) and $\lambda=0.01$ (right).

##  IV Discussion

The framework developed in this work assumes that the Gaussian Markov kernel
that model each iteration of Noisy-SGD have bounded input. This can be
realized by either gradient clipping or by running Noisy-SGD on the smoothed
version of the objective (e.g., by Gaussian convolution or Moreau-Yousida
smoothing). This enables us to exploit the probabilistic contraction of
Gaussian kernels to prove convergence of the privacy loss under minimal
assumptions on losses.

It is worth mentioning that typical regularity assumptions on the loss
function (such as convexity and smoothness) would improve our results. For
instance, it can be shown via geometric contraction arguments in [FMTT18,
BBGG19] that the map $w\mapsto w-\eta\nabla\ell(w,x)$ is contractive for
smooth and (strictly) convex loss functions. Consequently, the diameter of the
input of Gaussian kernel in Noisy-SGD is (strictly) smaller than
$\text{dia}(\mathcal{W})$, thus leading to tighter bounds on the contraction
coefficients of Gaussian kernels.

As mentioned earlier, it is not clear that our technique leads to a convergent
upper bound for the regularized DP-SGD. A natural future direction is to
improve Theorem 3 (perhaps by means of a different coupling process) and
analytically prove the convergence of privacy loss in this setting.

##  Appendix A Conversion of Privacy Loss Bounds

Recall that according to Main Theorem (or Theorem 2), the projected DP-SGD
under sampling without replacement with batch size $b$ is
$(\varepsilon,\delta)$-differentially private with $\varepsilon\geq 0$ and

$\delta\leq\frac{1-[(1-p)\theta]^{T}}{1-(1-p)\theta}p\theta,$

where $p\coloneqq\frac{b}{n}$,
$\theta\coloneqq\theta_{\varepsilon}\big{(}\frac{D+2\eta C}{\sigma}\big{)}$
and

$\theta_{\varepsilon}(r)\coloneqq
Q\Big{(}\frac{\varepsilon}{r}-\frac{r}{2}\Big{)}-e^{\varepsilon}Q\Big{(}\frac{\varepsilon}{r}+\frac{r}{2}\Big{)}$

with $\displaystyle
Q(t)\coloneqq\frac{1}{\sqrt{2\pi}}\int_{t}^{\infty}e^{-u^{2}/2}\mathrm{d}u$.

It can be easily verified that the above upper bound for $\delta$
monotonically converges to $\displaystyle\frac{p\theta}{1-(1-p)\theta}$ as $T$
goes to infinity. Thus, it follows that

$\varepsilon\leq\varepsilon^{*}_{\delta},$ (22)

where $\varepsilon^{*}_{\delta}$ is the unique $\varepsilon$ that solves

$\theta_{\varepsilon}(r)=\frac{\delta}{p+(1-p)\delta},$

with $r\coloneqq\frac{D+2\eta C}{\sigma}$. Unfortunately,
$\varepsilon^{*}_{\delta}$ cannot be computed in closed-form; however, we can
obtain the following upper bound by noticing that
$\theta_{\varepsilon}(r)<Q\big{(}\frac{\varepsilon}{r}-\frac{r}{2}\big{)}$:

$\varepsilon\leq
r\left[\frac{r}{2}+\Phi^{-1}\bigg{(}\frac{p(1-\delta)}{p+(1-p)\delta}\bigg{)}\right],$
(23)

where $\Phi^{-1}$ is the inverse of CDF of standard Gaussian distribution.

Fig. 3: The privacy loss of DP-SGD as described in Theorem 2 with the
following parameters: $D=3,C=2,\eta=0.01,\sigma=1,\delta=10^{-3}$ and
$p=0.001$. Red curves correspond to the upper bounds on $\varepsilon$ derived
in (22) and (23).

##  Appendix B Proofs of the Main Results

###### Proof of Lemma 1.

Define $\mu_{T-1}\coloneqq\mathsf{K}_{T-1}\cdots\mathsf{K}_{1}\mu$ and
$\nu_{T-1}=\mathsf{K}^{\prime}_{T-1}\cdots\mathsf{K}^{\prime}_{1}\nu$. Due to
the projection $\Pi_{T-1}$ present in both $\mathsf{K}_{T-1}$ and
$\mathsf{K}_{T-1}^{\prime}$, we have that
$\mu_{T-1},\nu_{T-1}\in\mathcal{P}(\mathcal{W}_{T-1})$. Hence, (10) implies
that

$\displaystyle\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{T}\cdots\mathsf{K}_{1}\mu\|\mathsf{K}_{T}^{\prime}\cdots\mathsf{K}_{1}^{\prime}\nu\big{)}$
$\displaystyle=\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{T}\mu_{T-1}\|\mathsf{K}_{T}^{\prime}\nu_{T-1}\big{)}$
$\displaystyle\leq\alpha_{T}\mathsf{E}_{\varepsilon}(\mu_{T-1}\|\nu_{T-1})+\beta_{T}.$

By applying the same argument iteratively, we obtain that

$\displaystyle\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{T}\cdots\mathsf{K}_{1}\mu\|\mathsf{K}_{T}^{\prime}\cdots\mathsf{K}_{1}^{\prime}\nu\big{)}$
$\displaystyle\leq\alpha_{T}\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{T-1}\cdots\mathsf{K}_{1}\mu\|\mathsf{K}_{T-1}^{\prime}\cdots\mathsf{K}_{1}^{\prime}\nu\big{)}+\beta_{T}$
$\displaystyle\leq\alpha_{T-1}\alpha_{T}\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{T-2}\cdots\mathsf{K}_{1}\mu\|\mathsf{K}_{T-2}^{\prime}\cdots\mathsf{K}_{1}^{\prime}\nu\big{)}+\beta_{T-1}\alpha_{T}+\beta_{T}$
$\displaystyle\;\;\vdots$
$\displaystyle\leq\Big{[}\prod_{t=1}^{T}\alpha_{t}\Big{]}\mathsf{E}_{\varepsilon}(\mu\|\nu)+\sum_{t=1}^{T}\beta_{t}\prod_{s=t+1}^{T}\alpha_{s},$

as desired. ∎

###### Proof of Lemma 2.

From the definition of $\mathrm{Clip}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ in (2),
we have that $\lVert\mathrm{Clip}(v)\rVert\leq C$ for any
$v\in\mathbb{R}^{d}$. Hence, (12) implies that, for all $B\subset[n]$ and
$w\in\mathcal{W}$,

$\lVert\psi_{B}(w)-w\rVert\leq\eta C.$

Hence, the triangle inequality implies that, for all $B_{1},B_{2}\subset[n]$
and $w_{1},w_{2}\in\mathcal{W}$,

$\displaystyle\lVert\psi_{B_{2}}(w_{2})-\psi_{B_{1}}(w_{1})\rVert$
$\displaystyle\leq\lVert\psi_{B_{2}}(w_{2})-w_{2}\rVert+\lVert
w_{2}-w_{1}\rVert+\lVert w_{1}-\psi_{B_{1}}(w_{1})\rVert$
$\displaystyle\leq\mathrm{dia}(\mathcal{W})+2\eta C.$

Since $B_{1},B_{2}\subset[n]$ and $w_{1},w_{2}\in\mathcal{W}$ were arbitrary,
the result follows. ∎

###### Proof of Proposition 2.

Let $\mathcal{X}=\\{x_{1},\ldots,x_{n}\\}$ and
$\mathcal{X}^{\prime}=\\{x^{\prime}_{1},\ldots,x^{\prime}_{n}\\}$. Without
loss of generality, we may assume that $x_{n}\neq x^{\prime}_{n}$ and
$x_{i}=x^{\prime}_{i}$ for $i\in[n-1]$. Recall the definition of $\Psi$ in
(13). In particular, we have that

$\mathsf{K}=\sum_{B\subset[n]}p^{\lvert B\rvert}(1-p)^{n-\lvert
B\rvert}\Pi\circ\mathsf{K}^{\sigma}_{\mathrm{G}}\circ\psi_{B}\qquad\text{and}\qquad\mathsf{K}^{\prime}=\sum_{B\subset[n]}p^{\lvert
B\rvert}(1-p)^{n-\lvert
B\rvert}\Pi\circ\mathsf{K}^{\sigma}_{\mathrm{G}}\circ\psi_{B}^{\prime}.$

By the convexity of $(P,Q)\mapsto\mathsf{E}_{\varepsilon}(P\|Q)$, the previous
expressions lead to

$\displaystyle\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)$
$\displaystyle\leq\sum_{B\subset[n]}p^{\lvert B\rvert}(1-p)^{n-\lvert
B\rvert}\mathsf{E}_{\varepsilon}\big{(}(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B})\mu\|(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B}^{\prime})\nu\big{)}$
$\displaystyle=\sum_{B\subset[n]}p^{\lvert B\rvert}(1-p)^{n-\lvert
B\rvert}\mathsf{E}_{\varepsilon}\big{(}(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma})(\psi_{B}\mu)\|(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma})(\psi_{B}^{\prime}\nu)\big{)}$
$\displaystyle\leq\sum_{B\subset[n]}p^{\lvert B\rvert}(1-p)^{n-\lvert
B\rvert}\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}\mu)\|\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}^{\prime}\nu)\big{)},$

where the last inequality follows from the data processing inequality. Notice
that in this setting $\mathsf{K}_{\mathrm{G}}^{\sigma}$ is an
$\mathcal{S}$-constrained Gaussian kernel where

$\mathcal{S}\coloneqq\bigcup_{B\subset[n]}\psi_{B}(\mathcal{W}).$

It follows from Lemma 2 that $\mathrm{dia}(\mathcal{S})\leq D+2\eta C$.
Therefore, Proposition 1 implies that

$\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}\mu)\|\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}^{\prime}\nu)\big{)}\leq\theta_{\varepsilon}\bigg{(}\frac{D+2\eta
C}{\sigma}\bigg{)}\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi^{\prime}_{B}\nu),$

and, as a result,

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)\leq\sum_{B\subset[n]}p^{\lvert
B\rvert}(1-p)^{n-\lvert
B\rvert}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu),$

where $\theta=\theta_{\varepsilon}\big{(}(D+2\eta C)/\sigma\big{)}$. A
straightforward manipulation shows that

$\displaystyle\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)$
$\displaystyle\leq\sum_{B\subset[n]}\mathbf{1}_{\\{n\notin B\\}}p^{\lvert
B\rvert}(1-p)^{n-\lvert
B\rvert}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu)$
$\displaystyle\quad+\sum_{B\subset[n]}\mathbf{1}_{\\{n\in B\\}}p^{\lvert
B\rvert}(1-p)^{n-\lvert
B\rvert}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu).$

By the definition of $\psi_{B}$ in (12), we note that
$\psi_{B}=\psi_{B}^{\prime}$ whenever $n\notin B$. Hence, the data processing
inequality implies that

$\displaystyle\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)$
$\displaystyle\leq\sum_{B\subset[n]}\mathbf{1}_{\\{n\notin B\\}}p^{\lvert
B\rvert}(1-p)^{n-\lvert B\rvert}\theta\mathsf{E}_{\varepsilon}(\mu\|\nu)$
$\displaystyle\quad+\sum_{B\subset[n]}\mathbf{1}_{\\{n\in B\\}}p^{\lvert
B\rvert}(1-p)^{n-\lvert
B\rvert}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu).$

A simple combinatorial argument implies that

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)\leq(1-p)\theta\mathsf{E}_{\varepsilon}(\mu\|\nu)+p\theta,$

where we used the trivial upper bound
$\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu)\leq 1$. ∎

###### Proof of Proposition 3.

Let $\mathcal{X}=\\{x_{1},\ldots,x_{n}\\}$ and
$\mathcal{X}^{\prime}=\\{x^{\prime}_{1},\ldots,x^{\prime}_{n}\\}$. Without
loss of generality, we may assume that $x_{n}\neq x^{\prime}_{n}$ and
$x_{i}=x_{i}^{\prime}$ for $i\in[n-1]$. Recall the definition of $\Psi$ in
(15). In particular, we have that

$\mathsf{K}=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B}\qquad\text{and}\qquad\mathsf{K}^{\prime}=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B}^{\prime}.$

By the convexity of $(P,Q)\mapsto\mathsf{E}_{\varepsilon}(P\|Q)$, the previous
expressions lead to

$\displaystyle\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)$
$\displaystyle\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathsf{E}_{\varepsilon}\big{(}(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B})\mu\|(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B}^{\prime})\nu\big{)}$
$\displaystyle=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathsf{E}_{\varepsilon}\big{(}(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma})(\psi_{B}\mu)\|(\Pi\circ\mathsf{K}_{\mathrm{G}}^{\sigma})(\psi_{B}^{\prime}\nu)\big{)}$
$\displaystyle\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}\mu)\|\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}^{\prime}\nu)\big{)},$

where the last inequality follows from the data processing inequality. As in
the proof of Proposition 2, $\mathsf{K}_{\mathrm{G}}^{\sigma}$ is an
$\mathcal{S}$-constrained Gaussian kernel where

$\mathcal{S}\coloneqq\bigcup_{B\subset[n]:\lvert
B\rvert=b}\psi_{B}(\mathcal{W}).$

In light of Lemma 2, we have $\mathrm{dia}(\mathcal{S})\leq D+2\eta C$.
Therefore, Proposition 1 implies that

$\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}\mu)\|\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}^{\prime}\nu)\big{)}\leq\theta_{\varepsilon}\bigg{(}\frac{D+2\eta
C}{\sigma}\bigg{)}\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi^{\prime}_{B}\nu),$

and, as a result,

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu),$

where $\theta=\theta_{\varepsilon}\big{(}(D+2\eta C)/\sigma\big{)}$. A
straightforward manipulation shows that

$\displaystyle\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)$
$\displaystyle\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\notin
B\\}}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu)$
$\displaystyle\quad+\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\in
B\\}}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu).$

By the definition $\psi_{B}$ in (12), we note that
$\psi_{B}=\psi_{B}^{\prime}$ whenever $n\notin B$. Hence, the data processing
inequality implies that

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\notin
B\\}}\theta\mathsf{E}_{\varepsilon}(\mu\|\nu)+\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\in
B\\}}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu).$

A simple combinatorial argument implies that

$\mathsf{E}_{\varepsilon}(\mathsf{K}\mu\|\mathsf{K}^{\prime}\nu)\leq\bigg{(}1-\frac{b}{n}\bigg{)}\theta\mathsf{E}_{\varepsilon}(\mu\|\nu)+\frac{b}{n}\theta,$

where we used the trivial upper bound
$\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu)\leq 1$. ∎

###### Proof of Proposition 4.

We proceed by induction on $t\geq 0$. Since $\mu_{0}=\tilde{\mu}_{0}$ by
assumption, the desired inequality holds with equality for $t=0$. Assume that
$\displaystyle\lVert\tilde{\mu}_{t}-\mu_{t}\rVert_{\mathrm{TV}}\leq
1-\mathbb{P}(\chi^{2}_{d}\leq\kappa^{2})^{t}$ for some $t\in\mathbb{N}$. Since
$\tilde{\mu}_{t+1}=\tilde{\mathsf{K}}_{t+1}\tilde{\mu}_{t}$ and
$\tilde{\mathsf{K}}_{t+1}=\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi$, we
obtain that

$\tilde{\mu}_{t+1}=(\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi)\tilde{\mu}_{t}=\mathsf{K}_{\mathrm{G}}^{\sigma}(\Psi\tilde{\mu}_{t}).$

By the definition of the Gaussian kernel $\mathsf{K}_{\mathrm{G}}^{\sigma}$,
we have that

$\phantom{\forall\nu\in\mathcal{P}(\mathbb{R}^{d}).}\qquad\qquad\qquad\mathsf{K}_{\mathrm{G}}^{\sigma}\nu=\int_{\mathbb{R}^{d}}\nu\ast\delta_{\sigma
x}\mathrm{d}G(x),\qquad\qquad\qquad\forall\nu\in\mathcal{P}(\mathbb{R}^{d}).$

where $G$ is the standard Gaussian distribution in $\mathbb{R}^{d}$ and $\ast$
is the additive convolution operator in $\mathcal{P}(\mathbb{R}^{d})$. In
particular, we obtain that

$\displaystyle\tilde{\mu}_{t+1}$
$\displaystyle=\int_{\mathbb{R}^{d}}\Psi\tilde{\mu}_{t}\ast\delta_{\sigma
x}\mathrm{d}G(x)$
$\displaystyle=\int_{\mathbb{B}_{d}(\kappa)}\Psi\tilde{\mu}_{t}\ast\delta_{\sigma
x}\mathrm{d}G(x)+\int_{\mathbb{B}_{d}(\kappa)^{c}}\Psi\tilde{\mu}_{t}\ast\delta_{\sigma
x}\mathrm{d}G(x),$ (24)

where
$\mathbb{B}_{d}(\kappa)\coloneqq\\{w\in\mathbb{R}^{d}:\|w\|\leq\kappa\\}$.
Similarly, we can show that

$\mu_{t+1}=\Pi_{t+1}\bigg{(}\int_{\mathbb{R}^{d}}\Psi\mu_{t}\ast\delta_{\sigma
x}\mathrm{d}G(x)\bigg{)}.$

Since the kernel $\Pi_{t+1}$ is linear over $\mathcal{P}(\mathbb{R}^{d})$, we
obtain that

$\displaystyle\mu_{t+1}$
$\displaystyle=\int_{\mathbb{R}^{d}}\Pi_{t+1}(\Psi\mu_{t}\ast\delta_{\sigma
x})\mathrm{d}G(x)$
$\displaystyle=\int_{\mathbb{B}_{d}(\kappa)}\Pi_{t+1}(\Psi\mu_{t}\ast\delta_{\sigma
x})\mathrm{d}G(x)+\int_{\mathbb{B}_{d}(\kappa)^{c}}\Pi_{t+1}(\Psi\mu_{t}\ast\delta_{\sigma
x})\mathrm{d}G(x).$ (25)

Recall that $\mu_{t}=\mathsf{K}_{t}\mu_{t-1}$ and
$\mathsf{K}_{t}=\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\Psi$ where
$\Pi_{t}$ is the projection onto $\mathcal{W}_{t}=\mathbb{B}_{d}(r_{t})$. In
particular, we have that
$\mathrm{Supp}(\mu_{t})\subseteq\mathbb{B}_{d}(r_{t})$. By the definition of
$\psi_{B}$ in (17), it is immediate to verify that, for all
$w\in\mathbb{B}_{d}(r_{t})$ and $B\subset[n]$,

$\lVert\psi_{B}(w)\rVert\leq(1-\lambda)r_{t}+\eta C.$

As a result, we obtain that
$\mathrm{Supp}(\Psi\mu_{t})\subseteq\mathbb{B}_{d}\big{(}(1-\lambda)r_{t}+\eta
C\big{)}$. By the triangle inequality, for any
$w\in\mathbb{B}_{d}\big{(}(1-\lambda)r_{t}+\eta C\big{)}$ and
$x\in\mathbb{B}_{d}(\kappa)$,

$\lVert w+\sigma x\rVert\leq(1-\lambda)r_{t}+\eta C+\sigma\kappa=r_{t+1},$

where the equality follows from the definition of $r_{t}$ in (20). Therefore,
for all $x\in\mathbb{B}_{d}(\kappa)$, we have that
$\mathrm{Supp}(\Psi\mu_{t}\ast\delta_{\sigma
x})\subseteq\mathbb{B}_{d}(r_{t+1})$ and

$\Pi_{t+1}\big{(}\Psi\mu_{t}\ast\delta_{\sigma
x}\big{)}=\Psi\mu_{t}\ast\delta_{\sigma x}.$

By plugging the previous equality into (25), we obtain that

$\mu_{t+1}=\int_{\mathbb{B}_{d}(\kappa)}\Psi\mu_{t}\ast\delta_{\sigma
x}\mathrm{d}G(x)+\int_{\mathbb{B}_{d}(\kappa)^{c}}\Pi_{t+1}(\Psi\mu_{t}\ast\delta_{\sigma
x})\mathrm{d}G(x).$

The previous expression and (24) lead to

$\displaystyle\lVert\tilde{\mu}_{t+1}-\mu_{t+1}\rVert_{\mathrm{TV}}$
$\displaystyle\leq\int_{\mathbb{B}_{d}(\kappa)}\lVert\Psi\tilde{\mu}_{t}\ast\delta_{\sigma
x}-\Psi\mu_{t}\ast\delta_{\sigma x}\rVert_{\mathrm{TV}}\mathrm{d}G(x)$
$\displaystyle\quad+\int_{\mathbb{B}_{d}(\kappa)^{c}}\lVert\Psi\tilde{\mu}_{t}\ast\delta_{\sigma
x}-\Pi_{t+1}(\Psi\mu_{t}\ast\delta_{\sigma
x})\rVert_{\mathrm{TV}}\mathrm{d}G(x).$

By the data processing inequality, we have that

$\lVert\Psi\tilde{\mu}_{t}\ast\delta_{\sigma x}-\Psi\mu_{t}\ast\delta_{\sigma
x}\rVert_{\mathrm{TV}}\leq\lVert\tilde{\mu}_{t}-\mu_{t}\rVert_{\mathrm{TV}}.$

Since the total variation distance is bounded by 1, we conclude that

$\displaystyle\lVert\tilde{\mu}_{t+1}-\mu_{t+1}\rVert_{\mathrm{TV}}$
$\displaystyle\leq\lVert\tilde{\mu}_{t}-\mu_{t}\rVert_{\mathrm{TV}}\int_{\mathbb{B}_{d}(\kappa)}\mathrm{d}G(x)+\int_{\mathbb{B}_{d}(\kappa)^{c}}\mathrm{d}G(x)$
$\displaystyle=\lVert\tilde{\mu}_{t}-\mu_{t}\rVert_{\mathrm{TV}}\mathbb{P}(\chi^{2}_{d}\leq\kappa^{2})+1-\mathbb{P}(\chi^{2}_{d}\leq\kappa^{2}).$

The theorem follows from the previous inequality and the induction hypothesis.
∎

###### Proof of Proposition 5.

Let $\mathcal{X}=\\{x_{1},\ldots,x_{n}\\}$ and
$\mathcal{X}^{\prime}=\\{x^{\prime}_{1},\ldots,x^{\prime}_{n}\\}$. Without
loss of generality, we may assume that $x_{n}\neq x^{\prime}_{n}$ and
$x_{i}=x_{i}^{\prime}$ for $i\in[n-1]$. Recall the definition of $\Psi$ in
(18). In particular, we have that

$\mathsf{K}_{t}=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B}\qquad\text{and}\qquad\mathsf{K}_{t}^{\prime}=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B}^{\prime}.$

By the convexity of $(P,Q)\mapsto\mathsf{E}_{\varepsilon}(P\|Q)$, the previous
expressions lead to

$\displaystyle\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)$
$\displaystyle\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathsf{E}_{\varepsilon}\big{(}(\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B})\mu\|(\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma}\circ\psi_{B}^{\prime})\nu\big{)}$
$\displaystyle=\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathsf{E}_{\varepsilon}\big{(}(\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma})(\psi_{B}\mu)\|(\Pi_{t}\circ\mathsf{K}_{\mathrm{G}}^{\sigma})(\psi_{B}^{\prime}\nu)\big{)}$
$\displaystyle\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}\mu)\|\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}^{\prime}\nu)\big{)},$

where the last inequality follows from the data processing inequality. By the
definition of $\psi_{B}$ in (17), it is immediate to verify that, for all
$w\in\mathbb{B}_{d}(r_{t-1})$ and $B\subset[n]$,

$\lVert\psi_{B}(w)\rVert\leq(1-\lambda)r_{t-1}+\eta C=r_{t}-\sigma\kappa.$

As a result, we obtain that
$\mathrm{Supp}(\psi_{B}\mu)\subset\mathbb{B}_{d}(r_{t}-\sigma\kappa)$. Mutatis
mutandis, we can also show that
$\mathrm{Supp}(\psi_{B}^{\prime}\nu)\subset\mathbb{B}_{d}(r_{t}-\sigma\kappa)$.
Therefore, Proposition 1 implies that

$\mathsf{E}_{\varepsilon}\big{(}\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}\mu)\|\mathsf{K}_{\mathrm{G}}^{\sigma}(\psi_{B}^{\prime}\nu)\big{)}\leq\theta_{\gamma}\bigg{(}\frac{r_{t}-\sigma\kappa}{\sigma}\bigg{)}\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu),$

and, as a result,

$\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu),$

where
$\theta\coloneqq\theta_{\varepsilon}\big{(}(r_{t}-\sigma\kappa)/\sigma\big{)}$.
A straightforward manipulation shows that

$\displaystyle\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)$
$\displaystyle\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\notin
B\\}}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu)$
$\displaystyle\quad+\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\in
B\\}}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu).$

By the definition $\psi_{B}$ in (17), we note that
$\psi_{B}=\psi_{B}^{\prime}$ whenever $n\notin B$. Hence, the data processing
inequality implies that

$\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)\leq\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\notin
B\\}}\theta\mathsf{E}_{\varepsilon}(\mu\|\nu)+\frac{1}{\binom{n}{b}}\sum_{B\subset[n]:\lvert
B\rvert=b}\mathbf{1}_{\\{n\in
B\\}}\theta\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu).$

A simple combinatorial argument implies that

$\mathsf{E}_{\varepsilon}(\mathsf{K}_{t}\mu\|\mathsf{K}_{t}^{\prime}\nu)\leq\bigg{(}1-\frac{b}{n}\bigg{)}\theta\mathsf{E}_{\varepsilon}(\mu\|\nu)+\frac{b}{n}\theta,$

where we used the trivial upper bound
$\mathsf{E}_{\varepsilon}(\psi_{B}\mu\|\psi_{B}^{\prime}\nu)\leq 1$. ∎

###### Proof of Theorem 3.

Let $\mathcal{X}$ and $\mathcal{X}^{\prime}$ be two neighboring datasets. Let
$\tilde{\mu}_{T}$ and $\tilde{\mu}_{T}^{\prime}$ be the corresponding
distributions under the regularized iterative process (16) and $\mu_{T}$ and
$\mu_{T}^{\prime}$ the corresponding distributions under the projected
iterative process (19). In [LCV16], Liu et al. established that for
$\varepsilon_{1},\varepsilon_{2}\geq 0$ and probability measures $P,Q$, and
$S$,

$\mathsf{E}_{\varepsilon_{1}+\varepsilon_{2}}(P\|Q)\leq\mathsf{E}_{\varepsilon_{1}}(P\|S)+e^{\varepsilon_{1}}\mathsf{E}_{\varepsilon_{2}}(S\|Q).$
(26)

A repeated application of (26) leads to

$\displaystyle\mathsf{E}_{\varepsilon}(\tilde{\mu}_{T}\|\tilde{\mu}_{T}^{\prime})$
$\displaystyle\leq\mathsf{E}_{0}(\tilde{\mu}_{T}\|\mu_{T})+\mathsf{E}_{\varepsilon}(\mu_{T}\|\tilde{\mu}_{T}^{\prime})$
$\displaystyle\leq\mathsf{E}_{0}(\tilde{\mu}_{T}\|\mu_{T})+\mathsf{E}_{\varepsilon}(\mu_{T}\|\mu_{T}^{\prime})+e^{\varepsilon}\mathsf{E}_{0}(\mu_{T}^{\prime}\|\tilde{\mu}_{T}^{\prime}).$

Since $E_{0}(P\|Q)=\lVert P-Q\rVert_{\mathrm{TV}}$, Proposition 4 implies that

$\mathsf{E}_{\varepsilon}(\tilde{\mu}_{T}\|\tilde{\mu}_{T}^{\prime})\leq(1+e^{\varepsilon})\Big{[}1-\mathbb{P}(\chi^{2}_{d}\leq\kappa^{2})^{T}\Big{]}+\mathsf{E}_{\varepsilon}(\mu_{T}\|\mu_{T}^{\prime}).$

The theorem follows from Proposition 5 and Lemma 1. ∎

## References

  * [ABC+16] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, and et al.  Tensorflow: A system for large-scale machine learning.  In Symposium on Operating Systems Design and Implementation, 2016\.
  * [ACCO21] Shahab Asoodeh, Wei-Ning Chen, Flavio P. Calmon, and Ayfer Özgür.  Differentially private federated learning: An information-theoretic perspective.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 344–349, 2021.
  * [ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [ADC20] S. Asoodeh, M. Diaz, and F. P. Calmon.  Privacy amplification of iterative algorithms via contraction coefficients.  In Proc. IEEE International Symposium on Information Theory (ISIT), 2020.
  * [ADC23] Shahab Asoodeh, Mario Diaz, and Flavio P. Calmon.  Contraction of $\mathsf{E}_{\gamma}$-divergence and its applications to privacy.  arXiv 2012.11035, 2023.
  * [AT22] Jason Altschuler and Kunal Talwar.  Privacy of noisy stochastic gradient descent: More iterations without more privacy loss.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 3788–3800. Curran Associates, Inc., 2022.
  * [BBGG19] Borja Balle, Gilles Barthe, Marco Gaboardi, and Joseph Geumlek.  Privacy amplification by mixing and diffusion mechanisms.  In NeurIPS, pages 13277–13287. 2019.
  * [BS16] Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In Theory of Cryptography, pages 635–658, 2016.
  * [CLE+19] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In 28th USENIX Security Symposium (USENIX Security 19), pages 267–284, Santa Clara, CA, August 2019. USENIX Association.
  * [CTW+21] Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Úlfar Erlingsson, Alina Oprea, and Colin Raffel.  Extracting training data from large language models.  In 30th USENIX Security Symposium (USENIX Security 21), pages 2633–2650. USENIX Association, August 2021.
  * [CYS21] Rishav Chourasia, Jiayuan Ye, and Reza Shokri.  Differential privacy dynamics of langevin diffusion and noisy gradient descent.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Proc. Theory of Cryptography (TCC), pages 265–284, Berlin, Heidelberg, 2006.
  * [FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: Optimal rates in linear time.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 439–449. Association for Computing Machinery, 2020.
  * [FMTT18] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta.  Privacy amplification by iteration.  FOCS, pages 521–532, 2018.
  * [LCV16] Jingbo Liu, Paul Cuff, and Sergio Verdú.  $e_{\gamma}$-resolvability.  IEEE Transactions on Information Theory, 63(5):2629–2658, 2016\.
  * [Mir17] Ilya Mironov.  Rényi differential privacy.  In Proc. Computer Security Found. (CSF), pages 263–275, 2017.
  * [Rag16] M. Raginsky.  Strong data processing inequalities and$\phi$-sobolev inequalities for discrete channels.  IEEE Transaction on Information Theory, 62(6):3355–3389, June 2016\.
  * [RBP22] Théo Ryffel, Francis Bach, and David Pointcheval.  Differential privacy guarantees for stochastic gradient langevin dynamics, 2022.
  * [SBD21] Matteo Sordello, Zhiqi Bu, and Jinshuo Dong.  Privacy amplification via iteration for shuffled and online PNSGD.  In Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and José Antonio Lozano, editors, Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part II, pages 796–813. Springer, 2021.
  * [SV16] Igal Sason and Sergio Verdú.  $f$-divergence inequalities.  IEEE Transaction on Information Theory, 62(11):5973–6006, 2016\.
  * [WBK18] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan.  Subsampled Rényi differential privacy and analytical moments accountant.  In AISTAT, volume 89, pages 1226–1235, 16–18 Apr 2018.
  * [YS22] Jiayuan Ye and Reza Shokri.  Differentially private learning needs hidden state (or much faster convergence).  In Advances in Neural Information Processing Systems, 2022.
  * [YSS+21] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov.  Opacus: User-friendly differential privacy library in pytorch.  In NeurIPS 2021 Workshop Privacy in Machine Learning, 2021.
  * [ZDW22] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang.  Optimal accounting of differential privacy via characteristic function.  In International Conference on Artificial Intelligence and Statistics, pages 4782–4817. PMLR, 2022.