# Privacy Analysis of Online Learning Algorithms via Contraction
Coefficients††thanks: This work was supported in part by NSF under grants CIF
1900750 and CIF CAREER 1845852. Part of the results in this paper was
presented at the International Symposium on Information Theory 2020 [1].

Shahab Asoodeh, Mario Diaz, and Flavio P. Calmon S. Asoodeh and F. P. Calmon
are with School of Engineering and Applied Science, Harvard University
(e-mails: {shahab, flavio}@seas.harvard.edu). M. Diaz is with Universidad
Nacional Autónoma de México (e-mails: mario.diaz@sigma.iimas.unam.mx).

###### Abstract

We propose an information-theoretic technique for analyzing privacy guarantees
of online algorithms. Specifically, we demonstrate that differential privacy
guarantees of iterative algorithms can be determined by a direct application
of contraction coefficients derived from strong data processing inequalities
for $f$-divergences. Our technique relies on generalizing the Dobrushin’s
contraction coefficient for total variation distance to an $f$-divergence
known as ${\mathsf{E}}_{\gamma}$-divergence.
${\mathsf{E}}_{\gamma}$-divergence, in turn, is equivalent to approximate
differential privacy. As an example, we apply our technique to derive the
differential privacy parameters of gradient descent. Moreover, we also show
that this framework can be tailored to batch learning algorithms that can be
implemented with one pass over the training dataset.

##  I Introduction

Differential privacy (DP) [2] has become a standard definition for designing
large-scale privacy-preserving algorithms in both industrial [3, 4, 5] and
academic [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] settings. Intuitively, a
randomized algorithm is said to be diferentially private if its output does
not vary significantly with small changes in its input parameters. DP is
usually cast in terms of the maximum change of the probability distribution of
the output of an algorithm given small perturbation in its input values.

Online learning [17, 18] is a framework where a sequence of predictions are
made given the knowledge of past actions. This framework is particularly well-
suited for dynamic and adversarial environments where learning from data must
be done in real-time. Online learning is ubiquitous in practical applications
such as recommender systems [19], spam detection [20], portfolio optimization
[21, 22, 23], and convex optimization [24, 25], to name a few. The main goal
of online learning is to sequentially approximate a minimizer of

$\min_{w\in{\mathcal{W}}}\sum_{t=1}^{n}{\mathsf{f}}_{t}(w),$

where $\\{{\mathsf{f}}_{1},\dots,{\mathsf{f}}_{n}\\}$ are convex cost
functions and ${\mathcal{W}}$ is a parameter space. One popular example of
this formulation is the one-pass empirical risk minimization (ERM) problem. In
this problem, data points $x_{1},\dots,x_{n}$ are made available to a learner
one at a time. The goal of the learner is to find a minimizer of

$\min_{w\in{\mathcal{W}}}\sum_{t=1}^{n}\ell(w,x_{t})$

where $\ell(\cdot,\cdot)$ is a loss function. Observe that here
${\mathsf{f}}_{t}(w)=\ell(w,x_{t})$.

In general, an online learning algorithm proceeds as follows: the learner
first selects a random point $W_{1}$ from a convex set
${\mathcal{W}}\subset\mathbb{R}^{d}$. After committing to $W_{1}$, the cost
function ${\mathsf{f}}_{1}$ is revealed to her by nature, specifying the cost
${\mathsf{f}}_{1}(W_{1})$ incurred by the choice $W_{1}$. Upon observing the
cost function ${\mathsf{f}}_{t}$ at time $t$, the learner constructs
$W_{t+1}\in{\mathcal{W}}$ at time $t+1$ according to some update rules based
on all previous choices $W_{1},\dots,W_{t}$ and their associated costs.
Denoting this update rule at time $t$ by
$\Psi_{t}:{\mathcal{W}}\to\mathbb{R}^{d}$, this iterative algorithm can be
expressed by

$W_{t+1}=\Pi_{\mathcal{W}}[\Psi_{t}(W_{t})],$

where $\Pi_{\mathcal{W}}$ is the projection operator onto ${\mathcal{W}}$. A
prominent example of such update function is stochastic gradient descent,
where

$\Psi_{t}(w)=w-\eta_{t}\nabla{\mathsf{f}}_{t}(w)$

and $\eta_{t}$ is the learning rate at time $t$.

Like other machine learning techniques, online algorithms may compromise
privacy when applied to sensitive or individual-level data. One standard
approach to address this is to resort to DP. Considering
$\\{{\mathsf{f}}_{1},\dots,{\mathsf{f}}_{n}\\}$ as the input of online
algorithms, DP ensures that the output remains nearly the same if a single
function ${\mathsf{f}}_{i}$, for some $i\in[n]\coloneqq\\{1,\dots,n\\}$,
changes to a different ${\mathsf{f}}^{\prime}_{i}$. For example, in the one-
pass ERM problem, DP would ensure that the distribution over the minimizer $w$
would be approximately invariant to changes in one single data point $x_{i}$.
DP provides a strong privacy guarantee against an adversary with significant
side information about all cost functions except one.

The analysis of DP mechanisms in online learning is particularly challenging:
a single change in the algorithm’s cost function at any time instance may have
an accumulative impact on all future parameter updates. One standard way to
address this issue is to add calibrated noise to $\Psi_{t}$ at each iteration
[13, 14, 15, 16]. Thus, most differentially private online learning algorithms
can be expressed as

$W_{t+1}=\Pi_{\mathcal{W}}\left(\Psi_{t}(W_{t})+\sigma_{t}Z_{t}\right).$ (1)

where $\\{Z_{t}\\}$ is the collection of i.i.d. noise variables sampled from a
known density with covariance matrix $\mathbf{I}_{d}$ and $\sigma_{t}$
specifies the magnitude of noise at time $t$. In fact, this simple additive-
noise mechanism subsumes many popular differentially private algorithms [6, 7,
26, 8, 9, 11, 12, 27, 13, 28, 10, 29, 30, 31, 32, 33, 14, 15, 16].

In this paper, we provide a new framework for deriving DP guarantees for
online algorithms based on the information-theoretic tool of contraction
coefficients [34, 35]. Our main result establishes a bound on the "distance"
between the outputs $W_{n+1}$ and $W^{\prime}_{n+1}$ of process (1) after $n$
iterations when starting from two different random initial points $W_{1}$ and
$W^{\prime}_{1}$, respectively. As we delineate later, DP guarantees are fully
characterized by a certain $f$-divergence called
${\mathsf{E}}_{\gamma}$-divergence (a connection also observed in [36, 37,
12]). Given $\gamma\geq 1$, the ${\mathsf{E}}_{\gamma}$-divergence between two
probability distribution $\mu$ and $\nu$ is defined as
${\mathsf{E}}_{\gamma}(\mu\|\nu)\coloneqq\int\text{d}(\mu-\gamma\nu)^{+}$
where $(a)^{+}\coloneqq\max(0,a)$. We discuss this divergence and its
connection with privacy in Section II-C.

The following theorem establishes a multiplicative upper bound on the
${\mathsf{E}}_{\gamma}$-divergence of the output distributions of the
iterative process (1) when initiating on two different starting points and
noise variables $Z_{t}$ drawn from a Gaussian distribution. Due to the
inherent connection between DP constraints and
${\mathsf{E}}_{\gamma}$-divergence (to be discussed in Section II), Theorem 1
serves as the main tool for deriving bounds on the DP parameters of online
algorithms of the form (1).

######  Theorem 1.

Let $W_{1}\sim\mu_{1}$ and $W^{\prime}_{1}\sim\mu^{\prime}_{1}$ be two random
initial points of the iterative process (1) with $\mu_{1},\mu^{\prime}_{1}$
being probability measures on ${\mathcal{W}}$. Let also $W_{n+1}\sim\mu_{n+1}$
and $W^{\prime}_{n+1}\sim\mu^{\prime}_{n+1}$ denote the output of the
iteration $n$ starting from $W_{1}$ and $W^{\prime}_{1}$, respectively. If
$\\{Z_{t}\\}_{t=1}^{n}$ is sampled i.i.d. from
${\mathcal{N}}(0,\mathbf{I}_{d})$ and there exists $D>0$ such that
$\\{\Psi_{t}(w):w\in\mathcal{W}\\}$ has diameter $D$ for all $t\in[n]$, then
we have

${\mathsf{E}}_{\gamma}(\mu_{n+1}\|\mu^{\prime}_{n+1})\leq{\mathsf{E}}_{\gamma}(\mu_{1}\|\mu^{\prime}_{1})\prod_{t=1}^{n}\theta_{\gamma}\Big{(}\frac{D}{\sigma_{t}}\Big{)},$

where
$\theta_{\gamma}(r)\coloneqq{\mathsf{Q}}\left(\frac{\log\gamma}{r}-\frac{r}{2}\right)-\gamma{\mathsf{Q}}\left(\frac{\log\gamma}{r}+\frac{r}{2}\right)$
and
${\mathsf{Q}}(a)\coloneqq\frac{1}{\sqrt{2\pi}}\int_{a}^{\infty}e^{-u^{2}/2}\text{d}u$.

In information-theoretic parlance, this result establishes a strong data
processing inequality [34] for the Gaussian channels under
${\mathsf{E}}_{\gamma}$-divergence with the contraction coefficient specified
by the mapping $\theta_{\gamma}:(0,\infty)\to(0,1)$ (see Section II-B for more
details). The proof of this theorem relies on a result (Theorem 3) that
extends the celebrated Dobrushin’s theorem [38] from total variation distance
to ${\mathsf{E}}_{\gamma}$-divergence.

We make the following assumptions in order to apply Theorem 1 for deriving DP
guarantees of online learning algorithms:

Assumption 1:

The parameter $W_{t+1}$ in the process (1) only depends on $\mathsf{f}_{t}$
(as opposed to the entire $\\{{\mathsf{f}}_{1},\dots,{\mathsf{f}}_{t}\\}$).
Equivalently, the update function $\Psi_{t}$ only depends on $\mathsf{f}_{t}$.
In order to emphasize this assumption, we henceforth write
$\Psi_{{\mathsf{f}}_{t}}$ for $\Psi_{t}$. Thus, we write the process (1) as

$W_{t+1}=\Pi_{\mathcal{W}}(\Psi_{\mathsf{f}_{t}}(W_{t})+\sigma_{t}Z_{t}),$ (2)

where $\Psi_{{\mathsf{f}}_{t}}$ is the update function corresponding to
${\mathsf{f}}_{t}$ at iteration $t$.

Assumption 2:

We assume that the online algorithm hides all intermediate updates
$W_{1},\dots,W_{n}$ and only releases the last parameter $W_{n+1}$. Thus, our
goal is to ensure that $W_{n+1}$ is differentially private.

The Markovity condition in Assumption 1 is equivalent to a memory constraint
on the online algorithm. Moreover, it is trivially satisfied by several
popular online algorithms such as online (stochastic) gradient descent [39],
online mirror descent [17], implicit gradient descent [40], the passive-
aggressive algorithm [41], composite mirror descent [42], and the Frank-Wolfe
algorithm [43]. Nevertheless, this assumption rules out algorithms such as the
follow-the-leader (FTL) algorithm and its variants. We do note, however, that
a particular popular variant of the FTL algorithm, namely Regularized FTL [44,
45] is equivalent to online mirror descent (see [46, Lemma 1] and [47]),
rendering our framework applicable in this specific case.

Assumption 2 is also present in several recent works on last-iterate
convergence of learning algorithms [48, 49, 50, 51, 52], the privacy
amplification by iteration framework [53, 12] (see Section V for more
details), and privacy-preserving generative model for data inspection [54].
Another practical scenario where Assumption 2 naturally arises is as follows:
A learner intends to fit a model privately and publicly releases the model
parameters after a target level of accuracy is met (for instance, after a
certain number of iterations). Hiding intermediate updates not only leads to
privacy amplification [53, 12], it may also drive the final parameters to be
sparse [52]—a property which is often crucial for many applications [52].

The iterative process (2) can also correspond to batch (i.e., offline)
algorithms where a dataset is fixed and is available to the learner in
advance. For instance, consider the empirical risk minimization (ERM) problem:
Given a dataset $\\{x_{1},\dots,x_{n}\\}\in{\mathcal{X}}^{n}$, a learner seeks
to solve $\min_{w\in{\mathcal{W}}}\frac{1}{n}\sum_{t=1}^{n}\ell(w,x_{t})$ for
some convex loss function
$\ell:{\mathcal{W}}\times{\mathcal{X}}\to\mathbb{R}_{+}$. The problem of ERM
with DP constraints has been widely-studied with known asymptotically tight
upper and lower bounds for the excess loss (i.e., the difference between
achieved loss and the true minimum), e.g., [6, 7, 26, 8, 9, 27, 28, 10, 29,
31, 32, 33]. This problem can be viewed as an instance of the online learning
problem with cost functions ${\mathsf{f}}_{t}(w)=\ell(w,x_{t})$ [55]. This
observation enables us to translate the privacy analysis of the process (2) to
the privacy guarantee of batch algorithms. The caveat here is that each data
point $x_{i}$, $i\in[n]$ must be involved in the training process exactly
once. Examples of such algorithms include SGD with sub-sampling without
replacement.

The privacy properties of SGD algorithms with Gaussian perturbations was
initiated in [53] where the privacy guarantee was given in terms of a variant
of DP, namely Rényi differential privacy (RDP) [56]. However, this notion of
privacy is known to suffer from lack of operational interpretation [37]. In
Section V, we revisit the model studied in [53] and compute DP guarantees
_directly_. We demonstrate through numerical examples that our results can be
substantially tighter than what would be obtained by converting the results of
[53] on RDP to DP via the best known conversion formula (recently given in
[57]).

###  I-A Additional Related Work

The problem of analyzing DP guarantees of online algorithms was introduced in
[58] for the simple setting where ${\mathcal{W}}$ is a probability simplex and
the cost functions are linear with binary coefficients. Inspired by this work,
[13, 14, 15] developed techniques for making a large class of online learning
algorithms differentially private. The settings studied in these works violate
both of our assumptions; the output of the algorithm are the entire sequence
$W_{1},\dots,W_{n+1}$ (sometimes called the continual observation [58]
setting), and their construction relies on the tree-based aggregation [58]
which selects $W_{t+1}$ depending on
${\mathsf{f}}_{1},\dots,{\mathsf{f}}_{t}$.

Strong data processing inequalities (SDPI) for KL divergence and total
variation distance are ubiquitous in information theory and statistics. They
appear, for example, in the study of ergodicity of Markov processes [38], the
uniqueness of Gibbs measures [38], contraction of mutual information (and
generalized mutual information) in Markov chains [59, 60, 61, 62, 63] and in
Bayesian networks [64], comparison of channels [65], distributed estimation
[66], communication complexity of statistical estimation [67], distributed
function computation [68], and private estimation problems [69, 70].
Incidentally, the contraction coefficients of general Markov kernels under
total variation distance and KL divergence have simple expressions, as
outlined in [38] and [34, 59], respectively. In particular, Dobrushin [38]
derived a remarkably simple expression for the case of total variation
distance. A formula for the contraction coefficients under general
$f$-divergences is derived in [35, Theorem 5.2] for differentiable $f$. This
formula, however, is not applicable for the specific case of
${\mathsf{E}}_{\gamma}$-divergence as $f(t)=(t-\gamma)^{+}$ is not
differentiable. More recently, Kamalaruban [71, Theorem 3.10] derived a
closed-form expression for the contraction coefficient under another
$f$-divergence, namely DeGroot’s statistical information [72]. We initiate the
study of the contraction coefficient of general Markov kernels under
${\mathsf{E}}_{\gamma}$-divergence and demonstrate that it has a simple
closed-form expression (Theorem 3) of which Dobrushin’s characterization is a
special case.

###  I-B Paper Organization

The rest of the paper is organized as follows. Section II presents preliminary
definitions and results. In Section III, we study the contraction coefficient
of Markov kernels under ${\mathsf{E}}_{\gamma}$-divergence. In Section IV, we
present our main result on the connection between contraction coefficient and
the DP parameters of the iterative process (2). We then specialize this result
to distributed SGD in Section V and online gradient descent in Section VI.

###  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}})$. For a signed measure $\phi$ over
${\mathcal{W}}$, its total variation is defined as

$\lVert\phi\rVert:=\phi^{+}({\mathcal{W}})+\phi^{-}({\mathcal{W}}),$

where $(\phi^{+},\phi^{-})$ is the Hahn-Jordan decomposition of $\phi$ (see,
e.g., [73, Page 421]). Observe that if $\mu$ and $\nu$ are probability
measures,

$\lVert\mu-\nu\rVert=2\sup_{A\subset{\mathcal{W}}}\big{[}\mu(A)-\nu(A)\big{]}.$

The total variation distance between two distributions $\mu$ and $\nu$ is

$\mathsf{TV}(\mu,\nu):=\frac{1}{2}\lVert\mu-\nu\rVert.$

A Markov kernel (or channel)
${\mathsf{K}}:{\mathcal{W}}\to{\mathcal{P}}({\mathcal{Y}})$ is specified by a
collection of distributions
$\\{{\mathsf{K}}(w)\in{\mathcal{P}}({\mathcal{Y}}):w\in{\mathcal{W}}\\}$.
Given a Markov kernel
${\mathsf{K}}:{\mathcal{W}}\to{\mathcal{P}}({\mathcal{Y}})$ and
$\mu\in{\mathcal{P}}({\mathcal{W}})$, we denote by $\mu{\mathsf{K}}$ 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 $\mu{\mathsf{K}}\coloneqq\int\mu(\text{d}w){\mathsf{K}}(w)$. We use
${\mathbb{E}}_{\mu}[\cdot]$ to write the expectation with respect to $\mu$ and
$[n]$ for an integer $n\geq 1$ to denote $\\{1,\dots,n\\}$. For $a\in[0,1]$,
we define $\bar{a}=1-a$. For a set $\mathcal{D}\subset\mathbb{R}^{d}$, we let
$\textnormal{dia}(\mathcal{D})$ be its diameter, i.e.,

$\textnormal{dia}(\mathcal{D})=\sup_{w_{1},w_{2}\in\mathcal{D}}\lVert
w_{2}-w_{1}\rVert.$

##  II Background

In this section, we recall the framework for online learning and the
definition of differential privacy in this context. Also, we briefly review
definitions of $f$-divergence and contraction coefficient. Finally, we present
a relation between differential privacy and a particular type of
$f$-divergence known as ${\mathsf{E}}_{\gamma}$-divergence.

###  II-A Online Learning Algorithms and Differential Privacy

Let ${\mathcal{W}}$ denote a parameter space, e.g., the coefficients of a
linear regression model. We describe typical online learning algorithms under
Assumptions 1 and 2 in the next definition.

######  Definition 1 (Online Algorithms).

An online learning algorithm ${\mathcal{M}}$ proceeds as follows. A learner
initiates the algorithm by taking a random point $W_{1}$ from ${\mathcal{W}}$.
Once $W_{1}$ is chosen, a convex real-valued cost function
${\mathsf{f}}_{1}:{\mathcal{W}}\to\mathbb{R}$ is revealed to her, implying the
cost associated with $W_{1}$ is ${\mathsf{f}}_{1}(W_{1})$. Upon observing
${\mathsf{f}}_{t}$ and $W_{t}$, the learner at time $t+1$ chooses $W_{t+1}$
according to the update rule $\Psi_{{\mathsf{f}}_{t}}$, i.e.,
$W_{t+1}=\Pi_{{\mathcal{M}}}\left(\Psi_{{\mathsf{f}}_{t}}(W_{t})\right)$.
After $n$ iterations, the algorithm outputs $W_{n+1}$. Hence, letting
${\mathsf{F}}$ be the collection of all possible convex cost functions, the
algorithm can be viewed as the mapping

${\mathcal{M}}:{\mathsf{F}}^{n}\to{\mathcal{W}},$

given by

${\mathcal{M}}(\\{{\mathsf{f}}_{1},\dots,{\mathsf{f}}_{n}\\})=W_{n+1}.$

For brevity, we denote $\\{\mathsf{f}_{1},\ldots,\mathsf{f}_{n}\\}$ by
$\\{{\mathsf{f}}_{t}\\}$. It is worth noting that in this setting we assume
the collection of cost functions
$\\{{\mathsf{f}}_{1},\dots,{\mathsf{f}}_{n}\\}$ are fixed ahead of time before
the algorithm is started—often referred to as the oblivious setting in
literature [17, Section 5.5]. We say that ${\mathcal{M}}$ is a randomized
online algorithm if $W_{t+1}$ is a random variable on ${\mathcal{W}}$ given
$\\{{\mathsf{f}}_{t}\\}$ and $W_{t}$.

The goal of the learner is to minimize regret, i.e., the difference between
the cumulative cost and that of the best fixed (offline) solution in
hindsight. Specifically, the regret of a randomized algorithm ${\mathcal{M}}$
after $n$ iterations is defined as

$R_{{\mathcal{M}}}(n)\coloneqq{\mathbb{E}}\left[\sum_{t=1}^{n}\mathsf{f}_{t}(W_{t})\right]-\min_{w\in{\mathcal{W}}}\sum_{t=1}^{n}\mathsf{f}_{t}(w),$
(3)

where the expectation is taken over the algorithm’s randomness. Two examples
of such algorithms are (1) one-pass empirical risk minimization (ERM) where
${\mathsf{f}}_{t}(w)=\ell(w,x_{t})$ with $\ell(\cdot,\cdot)$ being a loss
function and $x_{t}$ being the ground truth observation (e.g., stock price) at
time $t$, and (2) online gradient descent where
${\mathsf{f}}_{t}(w)=w-\eta_{t}\nabla{\mathsf{f}}_{t}(w)$ with $\eta_{t}$
being the learning rate at time $t$. These two examples are studied in details
in Sections V and VI, respectively. In all online learning algorithms a
sublinear regret is sought, as it implies that asymptotically the online
algorithm performs almost as well as the optimizer in hindsight.

In many practical scenarios, the cost functions $\\{{\mathsf{f}}_{t}\\}$ might
leak private information about the learner. For example, linear cost in ERM
problem may reveal significant information about an observation ${x_{t}}$.
Other examples of privacy leakage in online algorithms are listed in [74, 75].
As such, we focus on privacy attacks aimed to infer information about the cost
function ${\mathsf{f}}_{i}$ for some $i\in[n]$ upon observing the output of
the algorithm, i.e., ${\mathcal{M}}(\\{{\mathsf{f}}_{t}\\})=W_{n+1}$. Thus,
our goal is to design online algorithms such that $W_{n+1}$ does not reveal
significant information about any single cost function in
$\\{{\mathsf{f}}_{t}\\}$. The following definition formalizes this goal. We
say that two collection of cost functions $\\{{\mathsf{f}}_{t}\\}$ and
$\\{{\mathsf{f}}^{\prime}_{t}\\}$ are neighboring at index $i\in[n]$, if
${\mathsf{f}}_{t}={\mathsf{f}}^{\prime}_{t}$ for all $t\in[n]\backslash{i}$
and ${\mathsf{f}}_{i}\neq{\mathsf{f}}^{\prime}_{i}$. We denote this by
$\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}$.

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

A randomized online algorithm ${\mathcal{M}}$ is said to be
$(\varepsilon,\delta)$-differentially private, for $\varepsilon\geq 0$ and
$\delta\in[0,1]$, if we have

$\sup_{i\in[n]}\sup_{\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}}\sup_{A\subset{\mathcal{W}}}\big{[}\Pr({\mathcal{M}}(\\{{\mathsf{f}}_{t}\\})\in
A)-e^{\varepsilon}\Pr({\mathcal{M}}(\\{{\mathsf{f}}^{\prime}_{t}\\})\in
A)\big{]}\leq\delta.$

######  Remark 1.

The above definition of DP is specific to online learning. Here, a pair of
neighboring collections of cost functions is considered rather than the
"neighboring datasets" used in batch learning scenarios. Definition 2 is also
the standard notion of DP for online learning algorithm considered in [15, 14,
16, 13, 76]. Nevertheless, Definition 2 differs from previous works on
differentially private online algorithms in that privacy is ensured with
respect to only the last parameter $W_{n+1}$ rather then the entire set of
parameters $\\{W_{1},\dots,W_{n+1}\\}$.

In order to quantify the DP parameters $\varepsilon$ and $\delta$ of an online
algorithm, we model each of its iterations as a Markov kernel (i.e., a
channel) and apply the relation between the DP constraint and the contraction
coefficient of a Markov kernel, defined next.

###  II-B $f$-Divergence and Contraction Coefficients

Given a convex function $f:(0,\infty)\to\mathbb{R}$ such that $f(1)=0$, the
$f$-divergence between two probability measures $\mu$ and $\nu$ with
$\mu\ll\nu$ is defined in [77] and [78] as

$D_{f}(\mu\|\nu)\coloneqq{\mathbb{E}}_{\nu}\left[f\left(\frac{\text{d}\mu}{\text{d}\nu}\right)\right].$

Let ${\mathcal{D}},{\mathcal{W}}\subset\mathbb{R}^{d}$ and
${\mathsf{K}}:{\mathcal{D}}\to{\mathcal{P}}({\mathcal{W}})$ be a Markov
kernel. Following the information-theoretic approach initiated by Ahlswede and
Gács [34], we define the contraction coefficient (or strong data processing
coefficient) of ${\mathsf{K}}$ under $D_{f}(\cdot\|\cdot)$ as

$\eta_{f}({\mathsf{K}})\coloneqq\sup_{\begin{subarray}{c}\mu,\nu\in{\mathcal{P}}({\mathcal{D}}):\\\
D_{f}(\mu\|\nu)\neq
0\end{subarray}}\frac{D_{f}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})}{D_{f}(\mu\|\nu)}.$
(4)

This quantity has been long studied for several $f$-divergences, e.g.,
$\mathsf{KL}$-divergence for which $f(t)=t\log(t)$, $\chi^{2}$-divergence for
which $f(t)=(t-1)^{2}$, and total variation distance for which
$f(t)=\frac{1}{2}|t-1|$. In particular, Dobrushin [38] showed that the
contraction coefficient $\eta_{\mathsf{TV}}$ under total variation distance
$\mathsf{TV}$ has the remarkably simple expression

$\eta_{\mathsf{TV}}({\mathsf{K}})=\sup_{w_{1},w_{2}\in{\mathcal{W}}}\mathsf{TV}({\mathsf{K}}(w_{1}),{\mathsf{K}}(w_{2})).$
(5)

It is worth noting that (5) has been extensively used as a main tool for
studying ergodicity of Markov processes as well as Gibbs measures, e.g., see
[38, 60, 35].

###  II-C Differential Privacy and ${\mathsf{E}}_{\gamma}$-Divergence

The definition of $(\varepsilon,\delta)$-DP given in Definition 2 can be
reformulated in terms of a certain $f$-divergence, namely
${\mathsf{E}}_{\gamma}$-divergence (aka hockey-stick divergence) [79, 80, 81].
Given $\gamma\geq 1$, the ${\mathsf{E}}_{\gamma}$-divergence between two
probability measures $\mu$ and $\nu$ is defined as

$\displaystyle{\mathsf{E}}_{\gamma}(\mu\|\nu)$
$\displaystyle\coloneqq\int_{\mathcal{W}}\text{d}(\mu-\gamma\nu)^{+}$ (6)
$\displaystyle=\sup_{A\subset{\mathcal{W}}}\left[\mu(A)-\gamma\nu(A)\right]$
$\displaystyle=\mu\left(\imath_{\mu\|\nu}>\log\gamma\right)-\gamma\nu\left(\imath_{\mu\|\nu}>\log\gamma\right),$
(7)

where $(\mu-\gamma\nu)^{+}$ is the positive part of the signed measure
$\mu-\gamma\nu$ and
$\imath_{\mu\|\nu}(t)\coloneqq\log\frac{\text{d}\mu}{\text{d}\nu}(t)$ denotes
the information density between $\mu$ and $\nu$. It can be directly verified
that ${\mathsf{E}}_{\gamma}$-divergence is in fact the $f$-divergence
associated with $f(t)=(t-\gamma)^{+}$ and also that
${\mathsf{E}}_{1}(\mu\|\nu)=\mathsf{TV}(\mu,\nu)$. The next theorem, presented
in the notation of the current paper, provides a relation between this
divergence and $(\varepsilon,\delta)$-DP.

######  Theorem 2 ([36, 82]).

A randomized online algorithm ${\mathcal{M}}$ satisfying Assumption 2 is
$(\varepsilon,\delta)$-DP if

$\sup_{i\in[n]}\sup_{\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}}\mathsf{E}_{e^{\varepsilon}}(\mu_{n+1}\|\mu^{\prime}_{n+1})\leq\delta,$

where $\mu_{n+1}$ and $\mu^{\prime}_{n+1}$ are the distributions of
$W_{n+1}={\mathcal{M}}(\\{{\mathsf{f}}_{t}\\})$ and
$W^{\prime}_{n+1}={\mathcal{M}}(\\{{\mathsf{f}}^{\prime}_{t}\\})$,
respectively.

By relating DP to ${\mathsf{E}}_{\gamma}$-divergence, this theorem enables us
to quantify the DP parameters of randomized algorithms via the contraction
coefficient of Markov kernels under ${\mathsf{E}}_{\gamma}$-divergence (see
Theorem 1). We shall make this relationship precise in Section IV by casting
each iteration of an iterative algorithm as a Markov kernel. A similar
approach has been exploited in [12] to quantify the improvement of DP
parameters due to post-processing (aka privacy amplification).

Before formalizing this relationship, we first compute in the next section the
contraction coefficient of Gaussian Markov kernels under
${\mathsf{E}}_{\gamma}$-divergence. This contraction coefficient is
instrumental for the privacy analysis of popular additive-noise mechanism in
DP literature, e.g., the Gaussian mechanism.

##  III Contraction Coefficient of Markov kernels under
${\mathsf{E}}_{\gamma}$-Divergence

In this section we establish a closed-form expression for the contraction
coefficient of Markov kernels under ${\mathsf{E}}_{\gamma}$-divergence which
generalizes Dobrushin’s formula in (5). We then instantiate this expression to
derive the contraction coefficient of the projected additive Gaussian kernel.
For ease of notation, we let
$\eta_{\gamma}({\mathsf{K}})\coloneqq\eta_{{\mathsf{E}}_{\gamma}}({\mathsf{K}})$.

######  Theorem 3.

Let ${\mathcal{D}},{\mathcal{W}}\subset\mathbb{R}^{d}$ and
${\mathsf{K}}:{\mathcal{D}}\to{\mathcal{P}}({\mathcal{W}})$ be a Markov
kernel. For any $\gamma\geq 1$, we have

$\eta_{\gamma}({\mathsf{K}})=\sup_{w_{1},w_{2}\in{\mathcal{D}}}{\mathsf{E}}_{\gamma}({\mathsf{K}}(w_{1})\|{\mathsf{K}}(w_{2})).$
(8)

The proof of this theorem is given in Appendix -A. Similar to Dobrushin’s
result (5) in characterizing $\eta_{\mathsf{TV}}$, this theorem enables us to
reduce the computation of $\eta_{\gamma}({\mathsf{K}})$ to evaluating the
${\mathsf{E}}_{\gamma}$-divergence between ${\mathsf{K}}(w_{1})$ and
${\mathsf{K}}(w_{2})$ for any two inputs $w_{1},w_{2}\in{\mathcal{D}}$.The
following lemma (proved in Appendix -B) is useful for this purpose.

######  Lemma 1.

For $m\in\mathbb{R}^{d}$ and $\sigma>0$, let
$\mathcal{N}(m,\sigma^{2}\mathbf{I}_{d})$ denote the multivariate Gaussian
distribution with mean $m$ and covariance matrix $\sigma^{2}\mathbf{I}_{d}$.
If $m_{1},m_{2}\in\mathbb{R}^{d}$ and $\sigma>0$, then

${\mathsf{E}}_{\gamma}(\mathcal{N}(m_{1},\sigma^{2}\mathbf{I}_{d})\|\mathcal{N}(m_{2},\sigma^{2}\mathbf{I}_{d}))={\mathsf{Q}}\left(\frac{\log\gamma}{\beta}-\frac{\beta}{2}\right)-\gamma{\mathsf{Q}}\left(\frac{\log\gamma}{\beta}+\frac{\beta}{2}\right),$

where $\displaystyle\beta=\frac{\|m_{2}-m_{1}\|}{\sigma}$.

This lemma motivates the following definition.

######  Definition 3.

For $\gamma\geq 1$, we define $\theta_{\gamma}:[0,\infty)\to[0,1]$ by

$\displaystyle\theta_{\gamma}(r)$
$\displaystyle\coloneqq{\mathsf{E}}_{\gamma}\left(\mathcal{N}(ru,\mathbf{I}_{d})\|\mathcal{N}(0,\mathbf{I}_{d})\right)$
$\displaystyle={\mathsf{Q}}\left(\frac{\log\gamma}{r}-\frac{r}{2}\right)-\gamma{\mathsf{Q}}\left(\frac{\log\gamma}{r}+\frac{r}{2}\right),$

where $u\in\mathbb{R}^{d}$ is any vector of unit norm.

######  Remark 2.

Notice that the ${\mathsf{E}}_{\gamma}$-divergence between Gaussian
distributions ${\mathcal{N}}(m_{1},\sigma^{2}\mathbf{I}_{d})$ and
${\mathcal{N}}(m_{2},\sigma^{2}\mathbf{I}_{d})$ can be concisely expressed as

${\mathsf{E}}_{\gamma}({\mathcal{N}}(m_{1},\sigma^{2}\mathbf{I}_{d})\|{\mathcal{N}}(m_{2},\sigma^{2}\mathbf{I}_{d}))=\theta_{\gamma}\left(\frac{\lVert
m_{2}-m_{1}\rVert}{\sigma}\right).$ (9)

The mapping $r\mapsto\theta_{\gamma}(r)$ is closely related to the functions
$R_{\alpha}$, introduced by Feldman et al. in [53, Definition 10], and
$\theta(r)$, introduced by Polyanskiy and Wu in [60, Section 2.2].

The additive Gaussian kernel
${\mathsf{K}}:\mathbb{R}^{d}\to{\mathcal{P}}(\mathbb{R}^{d})$ is the kernel
determined by ${\mathsf{K}}(w)=\mathcal{N}(w,\sigma^{2}\mathbf{I}_{d})$ for
some $\sigma>0$. This kernel can represent the privacy mechanism which maps
$w\mapsto w+\sigma Z$ with $Z\sim\mathcal{N}(0,\mathbf{I}_{d})$. An
application of Theorem 3 and Lemma 1 shows that, under
${\mathsf{E}}_{\gamma}$-divergence, the contraction coefficient of the
additive Gaussian kernel is trivial111This is not surprising given the facts
that $\eta_{\mathsf{TV}}({\mathsf{K}})=1$ for any Gaussian channels
${\mathsf{K}}$ without input constraints [60] and
$\eta_{\mathsf{TV}}({\mathsf{K}})=1$ if and only if $\eta_{f}({\mathsf{K}})=1$
for any non-linear functions $f$ [83, Proposition II.4.12]., i.e.,
$\eta_{\gamma}({\mathsf{K}})=1$. Fortunately, the input and output of kernels
appearing in applications tend to be bounded. Consider, for example, the
kernel which models the online update of parameters of a machine learning
model during training (e.g., weights of a neural network). In this case the
parameters are bounded, either explicitly by design, implicitly by some
regularization mechanisms, or simply due to finite precision of floating-point
operations in computers. Motivated by this observation, we define the
projected additive Gaussian kernel as follows.

######  Definition 4.

Let $\mathcal{D}\subset\mathbb{R}^{d}$ be a bounded set,
$\mathcal{W}\subset\mathbb{R}^{d}$ a closed convex set, and $\sigma>0$. The
projected additive Gaussian kernel associated with
$(\mathcal{D},\mathcal{W},\sigma)$ is the kernel
${\mathsf{K}}:{\mathcal{D}}\to{\mathcal{P}}({\mathcal{W}})$ which models the
map $w\mapsto\Pi_{\mathcal{W}}(w+\sigma Z)$ where $\Pi_{\mathcal{W}}(\cdot)$
is the projection operator onto $\mathcal{W}$ and
$Z\sim\mathcal{N}(0,\mathbf{I}_{d})$.

The following proposition establishes $\eta_{\gamma}$ for projected Gaussian
kernels.

######  Proposition 1.

Let $\gamma\geq 1$, $\mathcal{D}\subset\mathbb{R}^{d}$ a bounded set,
$\mathcal{W}\subset\mathbb{R}^{d}$ a closed convex set, and $\sigma>0$. If
${\mathsf{K}}:\mathcal{D}\to{\mathcal{P}}(\mathcal{W})$ is the projected
additive Gaussian kernel associated with $(\mathcal{D},\mathcal{W},\sigma)$,
then

$\eta_{\gamma}({\mathsf{K}})=\theta_{\gamma}\left(\frac{\textnormal{dia}(\mathcal{D})}{\sigma}\right).$

The proof of this proposition is deferred to Appendix -C. Having identified
$\eta_{\gamma}$ for projected additive Gaussian kernels, we invoke the SDPI
relationship and Theorem 2 to derive the DP parameters of iterative process
(2) in the next section.

###  III-A Digression: An upper bound for output $f$-divergences

If $f$ is twice differentiable and convex, then $D_{f}(\mu\|\nu)$ can be
expressed in terms of ${\mathsf{E}}_{\gamma}$-divergence [84, Proposition 3]
as

$D_{f}(\mu\|\nu)=\int_{1}^{\infty}f^{\prime\prime}(\gamma){\mathsf{E}}_{\gamma}(\mu\|\nu)+\gamma^{-3}f^{\prime\prime}(\gamma^{-1}){\mathsf{E}}_{\gamma}(\nu\|\mu)\text{d}\gamma$
(10)

for any pair of probability measures $\mu$ and $\nu$. Combined with Theorem 3,
this leads to the following general result.

######  Proposition 2.

Let $f:(0,\infty)\to\mathbb{R}$ be a convex and twice differentiable function
with $f(1)=0$ and ${\mathsf{K}}:{\mathcal{W}}\to{\mathcal{P}}({\mathcal{W}})$
be a Markov kernel. Then, for any pair of probability measures
$\mu,\nu\in{\mathcal{P}}({\mathcal{W}})$ we have

$D_{f}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})\leq\int_{1}^{\infty}\eta_{\gamma}({\mathsf{K}})\left[f^{\prime\prime}(\gamma){\mathsf{E}}_{\gamma}(\mu\|\nu)+\gamma^{-3}f^{\prime\prime}(\gamma^{-1}){\mathsf{E}}_{\gamma}(\nu\|\mu)\right]\textnormal{d}\gamma.$

The previous proposition can be contrasted with the celebrated result

$\eta_{f}({\mathsf{K}})\leq\eta_{\mathsf{TV}}({\mathsf{K}}),$ (11)

for any convex functions $f$ satisfying $f(1)=0$ and Markov kernels
${\mathsf{K}}$, originally proved in [83] for discrete case and subsequently
extended to the general case in [85]. The inequality (11) implies that

$D_{f}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})\leq\eta_{\mathsf{TV}}({\mathsf{K}})D_{f}(\mu\|\nu),$
(12)

for any convex functions $f$ satisfying $f(1)=0$, Markov kernels
${\mathsf{K}}$, and any pair of probability measures $\mu$ and $\nu$. To see
the improvement of Proposition 2 over (12), we consider $\chi^{2}$-divergence
(i.e., $f(t)=(t-1)^{2}$) in the following two examples.

Example 1.  Let $X\sim{\mathcal{N}}(0,\sigma^{2})$ and
$Y\sim{\mathcal{N}}(2,\sigma^{2})$. Furthermore, let $X_{\mathcal{B}}$ and
$Y_{\mathcal{B}}$ be obtained by projecting $X$ and $Y$ onto
${\mathcal{B}}=\\{x\in\mathbb{R}:|x|\leq\frac{1}{2}\\}$, respectively. Denote
their probability distributions by $\mu$ and $\nu$, respectively. Suppose
${\mathsf{K}}$ is a projected Gaussian kernel associated with
$({\mathcal{B}},{\mathcal{B}},\sigma)$. In this case,
$\eta_{\mathsf{TV}}({\mathsf{K}})=\theta_{1}\big{(}\frac{1}{\sigma}\big{)}$
and
$\eta_{\gamma}({\mathsf{K}})=\theta_{\gamma}\big{(}\frac{1}{\sigma}\big{)}$.
Thus, according to (12) we have for $\sigma=1$

$\displaystyle\chi^{2}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})$
$\displaystyle\leq\eta_{\mathsf{TV}}({\mathsf{K}})\chi^{2}(\mu\|\nu)$
$\displaystyle=2\theta_{1}\left(1\right)\int_{1}^{\infty}\left[{\mathsf{E}}_{\gamma}(\mu\|\nu)+\gamma^{-3}{\mathsf{E}}_{\gamma}(\nu\|\mu)\right]\textnormal{d}\gamma$
$\displaystyle\leq
2\theta_{1}\left(1\right)\int_{1}^{\infty}\left[{\mathsf{E}}_{\gamma}({\mathcal{N}}(0,1)\|{\mathcal{N}}(2,1))+\gamma^{-3}{\mathsf{E}}_{\gamma}({\mathcal{N}}(2,1)\|{\mathcal{N}}(0,1))\right]\textnormal{d}\gamma$
$\displaystyle=2\theta_{1}\left(1\right)\int_{1}^{\infty}\left[\left(1+\gamma^{-3}\right)\theta_{\gamma}\left(2\right)\right]\textnormal{d}\gamma$
$\displaystyle=0.49,$

where the first equality comes from (10) and the second inequality is due to
the data processing inequality. It, however, follows from Proposition 2 that

$\displaystyle\chi^{2}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})$ $\displaystyle\leq
2\int_{1}^{\infty}\theta_{\gamma}\left(1\right)\left[{\mathsf{E}}_{\gamma}(\mu\|\nu)+\gamma^{-3}{\mathsf{E}}_{\gamma}(\nu\|\mu)\right]\textnormal{d}\gamma$
$\displaystyle\leq
2\int_{1}^{\infty}\theta_{\gamma}\left(1\right)\left[{\mathsf{E}}_{\gamma}({\mathcal{N}}(0,1)\|{\mathcal{N}}(2,1))+\gamma^{-3}{\mathsf{E}}_{\gamma}({\mathcal{N}}(2,1)\|{\mathcal{N}}(0,1))\right]\textnormal{d}\gamma$
$\displaystyle=2\int_{1}^{\infty}\theta_{\gamma}\left(1\right)\left[\left(1+\gamma^{-3}\right)\theta_{\gamma}\left(2\right)\right]\textnormal{d}\gamma$
$\displaystyle=0.26.$

Example 2.  Suppose ${\mathsf{K}}$ is the binary input binary output channel
with crossover probabilities $a,b\in[0,\frac{1}{2}]$ defined by

${\mathsf{K}}^{a,b}=\begin{bmatrix}\bar{a}&a\\\ b&\bar{b}\end{bmatrix}.$

When $a=b=\tau$, then ${\mathsf{K}}^{\tau,\tau}$ corresponds to the binary
symmetric channel with crossover probability $\tau\in[0,\frac{1}{2}]$. It can
be easily verified that
$\eta_{\gamma}({\mathsf{K}}^{a,b})=\max\\{(\bar{a}-\gamma
b)^{+},(\bar{b}-\gamma a)^{+}\\}$ for all $\gamma\geq 1$ and in particular
$\eta_{\mathsf{TV}}({\mathsf{K}}^{a,b})=1-a-b$. Applying (12), we obtain for
any binary probability measures $\mu$ and $\nu$

$\displaystyle\chi^{2}(\mu{\mathsf{K}}^{a,b}\|\nu{\mathsf{K}}^{a,b})$
$\displaystyle\leq(1-a-b)\chi^{2}(\mu\|\nu)$
$\displaystyle=2(1-a-b)\int_{1}^{\infty}\left[{\mathsf{E}}_{\gamma}(\mu\|\nu)+\gamma^{-3}{\mathsf{E}}_{\gamma}(\nu\|\mu)\right]\textnormal{d}\gamma,$
(13)

where the equality comes from (10). Thus, for $a=0.1$, $b=0.4$,
$\mu={\mathsf{Bernoulli}}(0.1)$, and $\nu={\mathsf{Bernoulli}}(0.4)$ the bound
(12) yields

$\chi^{2}(\mu{\mathsf{K}}^{a,b}\|\nu{\mathsf{K}}^{a,b})\leq 0.19.$

On the other hand, Proposition 2 renders

$\displaystyle\chi^{2}(\mu{\mathsf{K}}^{a,b}\|\nu{\mathsf{K}}^{a,b})$
$\displaystyle\leq
2\int_{1}^{\max\\{\frac{\bar{b}}{a},\frac{\bar{a}}{b}\\}}\max\\{(\bar{a}-\gamma
b)^{+},(\bar{b}-\gamma
a)^{+}\\}\left[{\mathsf{E}}_{\gamma}(\mu\|\nu)+\gamma^{-3}{\mathsf{E}}_{\gamma}(\nu\|\mu)\right]\textnormal{d}\gamma,$

implying for the same values $a$ and $b$ and probability measures $\mu$, $\nu$

$\chi^{2}(\mu{\mathsf{K}}^{a,b}\|\nu{\mathsf{K}}^{a,b})\leq 0.17.$

##  IV Privacy Analysis of Noisy Iterative Algorithms

In this section, we develop a technique for computing the DP parameters of
general iterative process (2) via the contraction coefficient introduced in
the previous section. The main goal is to establish a bound for the DP
parameters $\varepsilon$ and $\delta$ achievable by adding Gaussian noise to
the update rules $\\{\Psi_{f_{t}}\\}$. The subsequent analysis is based on two
key observations.

$\bullet$ Iterative processes as composition of Markov kernels:

Assume $\\{Z_{t}\\}$ are i.i.d. samples drawn from a Gaussian distribution. As
illustrated in Fig. 1, the iterative process (2) can be viewed as a collection
of Markov kernels $\\{{\mathsf{K}}_{{\mathsf{f}}_{t}}\\}$ for $t\in[n]$ where
each ${\mathsf{K}}_{{\mathsf{f}}_{t}}$ is a concatenation of the update rule
$\Psi_{{\mathsf{f}}_{t}}$, an additive Gaussian channel with variance
$\sigma^{2}_{t}$, and the projection operator $\Pi_{\mathcal{W}}(\cdot)$.
Consequently, we can express ${\mathsf{K}}_{{\mathsf{f}}_{t}}$ as
${\mathsf{K}}_{t}\circ\Psi_{{\mathsf{f}}_{t}}:\mathcal{W}\to{\mathcal{P}}(\mathcal{W})$
where ${\mathsf{K}}_{t}$ is the projected additive Gaussian Markov kernel
associated with
$(\Psi_{{\mathsf{f}}_{t}}({\mathcal{W}}),{\mathcal{W}},\sigma_{t})$.
Consequently, the distribution of the final parameter $W_{n+1}$ is given by
$\mu_{1}{\mathsf{K}}_{{\mathsf{f}}_{1}}\cdots{\mathsf{K}}_{{\mathsf{f}}_{n}}$,
where $\mu_{1}$ is the distribution from which the initial point $W_{1}$ is
sampled.

$\bullet$ Per-Iteration DP:

The overall premise of the DP framework is that $\mu_{n+1}$ (the distribution
of $W_{n+1}$ the final output of the process) does not change significantly
when the family of input cost functions $\\{{\mathsf{f}}_{t}\\}$ are replaced
by $\\{{\mathsf{f}}^{\prime}_{t}\\}$ satisfying
$\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}$ for some $i\in[n]$. According to
Theorem 2, DP parameter $\delta$ is given by the
${\mathsf{E}}_{\gamma}$-divergence between $\mu_{n+1}$ and
$\mu^{\prime}_{n+1}$. Due to the additive nature of the process, this
divergence might, however, change drastically depending on $i$. To see this,
notice that if $i=n$, then
${\mathsf{E}}_{\gamma}(\mu_{n+1}\|\mu^{\prime}_{n+1})$ depends only the Markov
kernel ${\mathsf{K}}_{{\mathsf{f}}_{n}}$ whereas if $i=1$, then
${\mathsf{E}}_{\gamma}(\mu_{n+1}\|\mu^{\prime}_{n+1})$ is the output
divergence of a concatenation of $n$ Markov kernels
$\\{{\mathsf{K}}_{{\mathsf{f}}_{t}}\\}_{t=1}^{n}$. To account for this (rather
unpleasant) phenomenon, Feldman et al. [53] adopted a modified definition of
DP (see also [86]) given below.

######  Definition 5 ([53]).

A randomized online algorithm ${\mathcal{M}}$ satisfying Assumption 2 is said
to be $(\varepsilon,\delta)$-DP at index $i\in[n]$ if

$\sup_{\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}}\sup_{A\subset{\mathcal{W}}}\big{[}\Pr({\mathcal{M}}(\\{{\mathsf{f}}_{t}\\})\in
A)-e^{\varepsilon}\Pr({\mathcal{M}}(\\{{\mathsf{f}}^{\prime}_{t}\\})\in
A)\big{]}\leq\delta,$ (14)

or equivalently,

$\sup_{\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}}{\mathsf{E}_{e^{\varepsilon}}}(\mu_{n+1}\|\mu^{\prime}_{n+1})\leq\delta.$

Figure 1: The schematic representation of the iterative process described in
(2). Each Markov kernel ${\mathsf{K}}_{{\mathsf{f}}_{t}}$, $t\in[n]$ consists
of three components: mapping $w\mapsto\Psi_{{\mathsf{f}}_{t}}(w)$, additive
noise, and projection mapping $\Pi_{\mathcal{W}}$. The initial point
$W_{1}\sim\mu_{1}$ is a random point in ${\mathcal{W}}$. Input and output of
kernel ${\mathsf{K}}_{{\mathsf{f}}_{t}}$ is $W_{t}\sim\mu_{t}$ and
$W_{t+1}\sim\mu_{t+1}$, respectively.

In our privacy analysis, we first exploit the contraction coefficient under
${\mathsf{E}}_{\gamma}$-divergence (see (4)) to compute the DP parameters at a
given index $i\in[n]$ and then use the joint convexity of
${\mathsf{E}}_{\gamma}$-divergence to "homogenized" it over all $i$. The
following lemma is key for our privacy analysis (see Appendix -D for a proof).

######  Lemma 2.

Let $f$ be a convex function with $f(1)=0$. Moreover, let
$\mu_{1}\in\mathcal{P}(\mathcal{W})$ and also
$\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}$ be a pair of neighboring
collections of cost functions for a given $i\in[n]$. Then222Here, we use the
convention that $\prod_{t=i+1}^{n}\eta_{f}({\mathsf{K}}_{{\mathsf{f}}_{t}})=1$
for $i=n$.

$\displaystyle D_{f}(\mu_{n+1}\|\mu^{\prime}_{n+1})\leq
D_{f}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}})\prod_{t=i+1}^{n}\eta_{f}({\mathsf{K}}_{{\mathsf{f}}_{t}}),$

where
$\mu_{i}\coloneqq\mu_{1}{\mathsf{K}}_{{\mathsf{f}}_{1}}\cdots{\mathsf{K}}_{{\mathsf{f}}_{i-1}}$.
Specifically, we have for any $\varepsilon\geq 0$

$\displaystyle{\mathsf{E}_{e^{\varepsilon}}}(\mu_{n+1}\|\mu^{\prime}_{n+1})\leq{\mathsf{E}}_{e^{\varepsilon}}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}})\prod_{t=i+1}^{n}\eta_{e^{\varepsilon}}({\mathsf{K}}_{{\mathsf{f}}_{t}}).$
(15)

While the above lemma follows from a routine application of SDPI, it provides
a natural framework to study privacy guarantees of general iterative
processes. In fact, inequality (15) allows us to obtain per-iteration DP
parameter $\delta$ of iterative process (2) by bounding
${\mathsf{E}_{e^{\varepsilon}}}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}})$
and $\eta_{e^{\varepsilon}}({\mathsf{K}}_{{\mathsf{f}}_{t}})$. This result is
the linchpin for our privacy analysis in the sequel.

######  Theorem 4.

Assume that $\mathcal{W}\subset\mathbb{R}^{d}$ is a closed convex set and
$P_{Z}={\mathcal{N}}(0,\mathbf{I}_{d})$. The iterative process (2) is
$(\varepsilon,\delta)$-DP at index $i\in[n]$ for $\varepsilon\geq 0$ and
$\delta$ given by

$\delta=\theta_{e^{\varepsilon}}\left(\frac{\psi}{\sigma_{i}}\right)\prod_{t=i+1}^{n}\theta_{e^{\varepsilon}}\left(\frac{\textnormal{dia}(\Psi_{{\mathsf{f}}_{t}}(\mathcal{W}))}{\sigma_{t}}\right),$
(16)

where
$\displaystyle\psi\coloneqq\sup_{{\mathsf{f}}_{1},{\mathsf{f}}_{2}\in{\mathsf{F}}}\sup_{w\in{\mathcal{W}}}\lVert\Psi_{{\mathsf{f}}_{1}}(w)-\Psi_{{\mathsf{f}}_{2}}(w)\rVert$.

The detailed proof of this theorem is given in Appendix -E. We will use this
theorem to quantify the DP guarantee of popular algorithms. Before we delve
into instantiating this result, we first convert the per-iteration privacy
guarantee given in this theorem to privacy guarantee independent of index $i$.
To this end, we follow [53] to consider the randomly-stopped variant of
process (2): Instead of terminating after pre-determined $n$ iterations, the
algorithm stops at a random time $T$ uniformly chosen in $[n]$.

Algorithm 1 Randomly-stopped variant of iterative process (2)

0: Collection of cost functions $\\{{\mathsf{f}}_{t}\\}$, convex set
${\mathcal{W}}\subset\mathbb{R}^{d}$, and noise parameter $\sigma$

1: Pick a starting point $W_{1}\sim\mu_{1}\in{\mathcal{P}}({\mathcal{W}})$
sampled from some distribution $\mu_{1}$,

2: Pick $T$ uniformly at random from $[n]$,

3: for $t\in\\{1,\ldots,T\\}$ do

4: Play $W_{t}$, then obtain the cost function ${\mathsf{f}}_{t}$,

5: $\displaystyle
W_{t+1}=\Pi_{{\mathcal{W}}}\left(\Psi_{{\mathsf{f}}_{t}}(W_{t})+\sigma_{t}Z_{t}\right)$,
$Z_{t}\sim{\mathcal{N}}(0,\mathnormal{I})$,

6: end for

7: return $W_{T+1}$.

######  Theorem 5.

Assume that $\mathcal{W}\subset\mathbb{R}^{d}$ is a closed convex set and
$P_{Z}={\mathcal{N}}(0,\mathbf{I}_{d})$. The randomly-stopped iterative
process described in Algorithm 1, is $(\varepsilon,\delta)$-DP for
$\varepsilon\geq 0$ and

$\displaystyle\delta$
$\displaystyle=\min_{i\in[n]}\left\\{\frac{1}{n}\sum_{t=i}^{n}\theta_{e^{\varepsilon}}\left(\frac{\psi}{\sigma_{i}}\right)\prod_{j=i+1}^{t}\theta_{e^{\varepsilon}}\left(\frac{D}{\sigma_{j}}\right)\right\\}$
(17)
$\displaystyle\leq\frac{1}{n}\theta_{e^{\varepsilon}}\left(\frac{\psi}{\sigma}\right)\left[1-\theta_{e^{\varepsilon}}\left(\frac{D}{\sigma}\right)\right]^{-1},$
(18)

where
$\displaystyle\psi\coloneqq\sup_{{\mathsf{f}}_{1},{\mathsf{f}}_{2}\in{\mathsf{F}}}\sup_{w\in{\mathcal{W}}}\lVert\Psi_{{\mathsf{f}}_{1}}(w)-\Psi_{{\mathsf{f}}_{2}}(w)\rVert$,
$\displaystyle
D\coloneqq\max_{t\in[n]}\textnormal{dia}(\Psi_{{\mathsf{f}}_{t}}(\mathcal{W}))$
and $\displaystyle\sigma\coloneqq\min_{t\in[n]}\sigma_{t}$.

The detailed proof of this theorem is given in Appendix -F. Similar to Theorem
4, the above result only requires that $\|\Psi_{\mathsf{f}}(w)\|$ be uniformly
bounded for all $w\in{\mathcal{W}}$ and ${\mathsf{f}}\in{\mathsf{F}}$. This
assumption is in fact weaker than the regularity conditions typically assumed
in most of differentially private iterative algorithms, such as [6, 7, 26, 8,
9, 27, 13, 28, 10, 29, 30, 31, 32, 33, 87]. To illustrate this point and
better compare our result with the existing differentially private ML
algorithm, we instantiate this theorem for several batch and online algorithms
in the following two sections.

##  V Privacy Amplification by iteration

Empirical risk minimization (ERM) is a fundamental problem in machine
learning. Given a dataset
$\mathbb{D}=\\{x_{1},\dots,x_{n}\\}\in{\mathcal{X}}^{n}$ and the loss function
$\ell:{\mathcal{W}}\times{\mathcal{X}}\to\mathbb{R}^{+}$, ERM is formulated as

$\inf_{w\in{\mathcal{W}}}\frac{1}{n}\sum_{t=1}^{n}\ell(w,x_{t}).$

A simple algorithm for solving this problem can be implemented with one pass
of stochastic gradient descent (SGD) over the data set. As discussed in the
introduction, this procedure starts with a random point $W_{1}$ in
${\mathcal{W}}$, and then iterates
$W_{t+1}=\Pi_{{\mathcal{W}}}(W_{t}-\eta\nabla\ell(W_{t},x_{t}))$ for
$t\in[n]$. This problem can be cast as an online optimization problem by
defining ${\mathsf{f}}_{t}(w)=\ell(w,x_{t})$ and, thus, the differentially
private version of such algorithm can be analyzed using the framework
introduced in Section IV.

Following the DP literature (see, e.g., [8, 33, 11, 7, 10, 88, 9]), we add
Gaussian noise to the gradient term, and thus the variance of the noise is
assumed to be $\eta^{2}\sigma^{2}$ (as opposed to $\sigma^{2}$). We also
assume $\eta_{t}=\eta$ and $\sigma_{t}=\sigma$ for all $t\in[n]$.
Consequently, we consider the following algorithm, which is known as projected
noisy SGD (PNSGD)

$W_{t+1}=\Pi_{\mathcal{W}}\left(W_{t}-\eta\nabla\ell(W_{t},x_{t})+\eta\sigma
Z_{t}\right),$

where $Z_{t}\sim{\mathcal{N}}(0,\mathbf{I}_{d})$. It can be verified that the
above algorithm is an instance of iterative process (2) with update function

$\Psi^{\mathsf{SGD}}_{x_{t}}(w)\coloneqq w-\eta\nabla\ell(w,x_{t}).$

In this setup each cost function ${\mathsf{f}}_{t}$ depends only on data point
$x_{t}$. Thus, the neighboring relationship between two collections of cost
functions $\\{{\mathsf{f}}_{t}\\}$ and $\\{{\mathsf{f}}_{t}^{\prime}\\}$
reduces to that of the datasets $\mathbb{D}=\\{x_{1},\dots,x_{n}\\}$ and
$\mathbb{D}^{\prime}=\\{x^{\prime}_{1},\dots,x^{\prime}_{n}\\}$. That is,
assuming $x\mapsto\ell(\cdot,x)$ is injective, we have
$\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}_{t}^{\prime}\\}$ if and only if the datasets
$\mathbb{D}\stackrel{{\scriptstyle i}}{{\sim}}\mathbb{D}^{\prime}$, meaning
$x_{i}\neq x^{\prime}_{i}$ and $x_{j}=x^{\prime}_{j}$ for all
$j\in[n]\backslash{\\{i\\}}$. Consequently, the definition of DP in Definition
2 can be equivalently given in terms of neighboring datasets and thus reduces
to the original definition of DP in [2].

Algorithm 2 Randomly stopped Projected Noisy SGD (PNSGD)

0: Dataset $\mathbb{D}=\\{x_{1},\ldots,x_{n}\\}$, learning rate $\eta>0$,
convex set ${\mathcal{W}}\subset\mathbb{R}^{d}$, and noise parameter $\sigma$

1: Pick $W_{1}\sim\mu_{1}\in{\mathcal{P}}({\mathcal{W}})$

2: Take $T$ uniformly on $[n]$

3: for $t\in\\{1,\ldots,T\\}$ do

4: $W_{t+1}=\Pi_{\mathcal{W}}(W_{t}-\eta[\nabla_{w}\ell(W_{t},x_{t})+\sigma
Z_{t}])$, $Z_{t}\sim{\mathcal{N}}(0,\mathbf{I}_{d})$

5: end for

6: return $W_{T+1}$

The randomly-stopped PNSGD algorithm is described in Algorithm 2. The privacy
guarantee of this algorithm has been recently studied by Feldman et al. [53]
under the name of privacy amplification by iteration. However, the notion of
privacy used in their work is Rényi differential privacy that is known to
suffer from lack of operational interpretation [37]. We can now apply the
machinery developed in Section IV to derive the privacy guarantee of this
algorithm directly in terms of DP. Specifically, the following corollary
specializes Theorem 5 to the PNSGD algorithm; with the proof given in Appendix
-G.

######  Corollary 1.

Let ${\mathcal{W}}\subset\mathbb{R}^{d}$ be a convex set with diameter 1 and
$\\{\ell(\cdot,x)\\}_{x\in{\mathcal{X}}}$ be a family of convex $L$-Lipschitz
functions over ${\mathcal{W}}$. Then the randomly-stopped PNSGD algorithm is
$(\varepsilon,\delta)$ with $\varepsilon\geq 0$ and

$\delta=\frac{1}{n}\theta_{e^{\varepsilon}}\Big{(}\frac{2L}{\sigma}\Big{)}\left[1-\theta_{e^{\varepsilon}}\Big{(}\frac{1+2\eta
L}{\eta\sigma}\Big{)}\right]^{-1}.$ (19)

If we further assume that $w\mapsto\ell(w,x)$ is333A function
$f:{\mathcal{W}}\to\mathbb{R}$ is $\beta$-smooth if $\|\nabla f(w_{1})-\nabla
f(w_{2})\|\leq\beta\|w_{1}-w_{2}\|$ for all $w_{1},w_{2}\in{\mathcal{W}}$.
$\beta$-smooth for any $x\in{\mathcal{X}}$, then a standard calculation in
convex optimization shows that $w\mapsto\Psi^{\mathsf{SGD}}_{x}(w)$ is
$1$-Lipschitz for $\eta\leq\frac{2}{\beta}$ (see Appendix -H for a detailed
proof). A similar argument as in the proof of Corollary 1 reveals that with
this extra assumption (19) can be improved as (cf. Appendix -H)

$\delta=\frac{1}{n}\theta_{e^{\varepsilon}}\Big{(}\frac{2L}{\sigma}\Big{)}\left[1-\theta_{e^{\varepsilon}}\Big{(}\frac{1}{\eta\sigma}\Big{)}\right]^{-1},$
(20)

if $\eta\leq\frac{2}{\beta}$. This enables us to formally compare our result
with [53]. To do so, we need the following definition. Given $\alpha>1$, a
mechanism ${\mathcal{M}}$ is called $(\alpha,\zeta)$-Rényi differentially-
private (RDP) if

$\sup_{\mathbb{D}\sim\mathbb{D}^{\prime}}D_{\alpha}(\mu_{n+1}\|\mu^{\prime}_{n+1})\leq\zeta,$

where $D_{\alpha}(\cdot\|\cdot)$ denotes the Rényi divergence of order
$\alpha$ and $\mu_{n+1}$ and $\mu^{\prime}_{n+1}$ are the distributions of
$W_{n+1}$ and $W^{\prime}_{n+1}$ the outputs of ${\mathcal{M}}$ when running
on neighboring $\mathbb{D}$ and $\mathbb{D}^{\prime}$, respectively.

######  Theorem 6 ([53, Theorem 26]).

Let ${\mathcal{W}}\subset\mathbb{R}^{d}$ be a convex set and
$\\{\ell(\cdot,x)\\}_{x\in{\mathcal{X}}}$ be a family of convex, $L$-Lipschitz
and $\beta$-smooth loss functions over ${\mathcal{W}}$. Then, for any
$\eta\leq\frac{2}{\beta}$ and $\alpha>1$, and $\sigma\geq
L\sqrt{2(\alpha-1)\alpha}$, the randomly-stopped PNSGD algorithm is
$(\alpha,\zeta)$-RDP for

$\zeta=\frac{4\alpha L^{2}\log n}{n\sigma^{2}}.$

While Corollary 1 provides the privacy guarantee for any $\sigma>0$, this
theorem is restricted to $\sigma$ greater than $L\sqrt{2(\alpha-1)\alpha}$.
This discrepancy stems from the fact that, unlike
${\mathsf{E}}_{\gamma}$-divergence, $(\mu\|\nu)\to D_{\alpha}(\mu\|\nu)$ is
not convex for $\alpha>1$. To get around this issue, Feldman et al. [53, Lemma
25] presented a "weak" form of joint convexity for the Rényi divergence.

In order to compare Corollary 1 with Theorem 6, we need to convert
$(\alpha,\zeta)$-RDP guarantee to $(\varepsilon,\delta)$-DP. To do so, we
invoke two existing RDP-to-DP conversion formulae, making both analytical and
numerical comparison possible.

######  Lemma 3 ([56, Proposition 3]).

If a mechanism ${\mathcal{M}}$ is $(\alpha,\zeta)$-RDP for $\alpha>1$, then it
is $(\varepsilon,e^{-(\alpha-1)(\varepsilon-\zeta)})$-DP.

Due to the efficiency of RDP (especially in the context of composition), this
lemma has been extensively used in many recent private ML algorithms, see
e.g., [11, 89, 90, 5] and has been implemented in the Google’s open-source
TensorFlow Privacy444 See the function ”$\text{compute}\\_\text{eps}$” in the
analysis directory of TensorFlow Privacy in [91]. At the time of submission of
this paper, Lemma 3 is particularly implemented in the line 216 of [91]. [4].
In light of this result, Theorem 6 implies that the randomly stopped PNSGD is
$(\varepsilon,\hat{\delta})$-DP for any $\varepsilon\geq 0$ and

$\hat{\delta}\coloneqq\inf_{\alpha\in(1,\alpha^{*}]}e^{-(\alpha-1)(\varepsilon-\zeta)},$
(21)

where
$\alpha^{*}\coloneqq\frac{1}{2}\left[1+\sqrt{1+\frac{2\sigma^{2}}{L^{2}}}\right]$
and $\zeta=\frac{4\alpha L^{2}\log n}{n\sigma^{2}}$. The restriction on the
range of $\alpha$ was caused by the constraint on $\sigma$ in Theorem 6. Since
$\zeta$ is linear in $\alpha$, the minimization in (21) can be solved
analytically:

$\hat{\delta}=e^{-(\alpha^{\mathsf{opt}}-1)(\varepsilon-\rho\alpha^{\mathsf{opt}})},$
(22)

where $\rho\coloneqq\frac{4L^{2}\log n}{n\sigma^{2}}$ and

$\alpha^{\mathsf{opt}}\coloneqq\begin{cases}\alpha^{*},&\text{if}\leavevmode\nobreak\
\varepsilon^{2}\geq\rho^{2}\Big{(}1+\frac{2\sigma^{2}}{L^{2}}\Big{)},\\\
\frac{1}{2}+\frac{\varepsilon}{2\rho},&\text{otherwise}.\end{cases}$

Hence, for sufficiently large $\varepsilon$ (i.e., $\varepsilon\geq
O(\frac{\log n}{n})$), $\hat{\delta}$ behaves approximately like
$e^{-O(\varepsilon)}$ while our privacy analysis yields $\delta$ in (20) that
decays at the rate $e^{-O(\varepsilon^{2})}$.

(a) $\eta=0.2,\sigma=1$

(b) $\eta=0.1,\sigma=3$

(c) $\eta=0.05,\sigma=3$

Figure 2: The privacy parameters of PNSGD Algorithm 2 obtained from Corollary
1 and converting [53, Theorem 26] according to (22) and (23), respectively.
Here, we vary the learning rate $\eta$ and $\sigma$. Other parameters are as
follows: $L=1,\beta=1$, and $n=100$.

Despite its prevalence in practice, Lemma 3 is not tight in general. This
issue has recently prompted Asoodeh et al. [57] to derive the optimal
translation of $(\alpha,\zeta)$-RDP into $(\varepsilon,\delta)$-DP. Invoking
[57, Lemma 2], we deduce that the randomly stopped PNSGD is
$(\varepsilon,\check{\delta})$-DP for $\varepsilon\geq 0$ and

$\check{\delta}\coloneqq\inf_{\alpha\in(1,\alpha^{*}]}\min\Big{\\{}\kappa
e^{-(\alpha-1)(\varepsilon-\zeta)},\frac{e^{(\alpha-1)\zeta}-1}{\alpha\big{(}e^{(\alpha-1)\varepsilon}-1\big{)}}\Big{\\}},$
(23)

where
$\kappa\coloneqq\frac{1}{\alpha}\left(1-\frac{1}{\alpha}\right)^{\alpha-1}$
and $\zeta=\frac{4\alpha L^{2}\log n}{n\sigma^{2}}$. Although this result is
tighter than Lemma 3, it is not possible to analytically express
$\check{\delta}$. In Fig. 2, we compare the privacy parameters of the
randomly-stopped PNSGD given in Corollary 1 with $\hat{\delta}$ and
$\check{\delta}$ given in (22) and (23), respectively. As illustrated in this
figure, Corollary 1 results in significantly smaller values of $\delta$,
compared to the technique developed in [53], for sufficiently large
$\varepsilon$ across different values of parameters $\eta$ and $\sigma$. The
privacy improvement of Corollary 1 over [53] is more pronounced for smaller
values of $\frac{\eta}{\sigma}$. In particular, for the reasonable
range555Abadi et al. [11] empirically observed that the accuracy of PNSGD
algorithm is stable for a learning rate in the range of $(0.01,0.07)$ and
peaks around $0.052$. of $\eta\in(0.05,0.1)$ our technique results in tighter
privacy parameters than [53] for all $\varepsilon\geq 2$ as long as
$\sigma\geq 3$. It is also worth emphasizing that, unlike [53], the privacy
parameter given in Corollary 1 heavily depends on the learning rate $\eta$.
Intuitively, the larger the value of $\eta$, the stronger the privacy
guarantee of the PNSGD algorithm. Corollary 1 formalizes this intuition by
establishing a precise rate at which $\delta$ decreases as $\eta$ increases
for any given $\varepsilon$.

##  VI Privacy-Utility Tradeoff of the Online Gradient Descent Algorithm

In this section, we apply the technique developed in Section IV to study the
privacy guarantee of the online gradient descent (OGD) algorithm [39]. By
drawing on standard results from online convex optimization, we also expound
the tradeoff between privacy and utility in the OGD algorithm.

The OGD algorithm is an instance of the iterative process (2) with update
function

$\Psi^{\mathsf{OGD}}_{{\mathsf{f}}_{t}}(w)\coloneqq
w-\eta_{t}\nabla{\mathsf{f}}_{t}(w).$

Similar to Section V, we add Gaussian noise to the gradient term and thus the
noisy OGD algorithm iterates as

$W_{t+1}=\Pi_{{\mathcal{W}}}(W_{t}-\eta_{t}\nabla{\mathsf{f}}_{t}(W_{t})+\eta_{t}\sigma_{t}Z_{t}),$
(24)

where $Z_{t}\sim{\mathcal{N}}(0,\mathbf{I}_{d})$.

A standard quantity for measuring the utility of such algorithm is regret
(defined in (3)). However, it is implicitly assumed in this definition that
the algorithm stops at time $n$ and all $W_{1},\dots W_{n+1}$ are available
for analysis. However, these assumption are not applicable in our setting: the
algorithm stops at a random time $T\in[n]$ and only $W_{n+1}$ is available for
analysis. We therefore need to consider a variant of regret that takes these
requirements into consideration.

Recall that $\mathsf{F}$ denotes the collection of all possible real-valued
cost functions over ${\mathcal{W}}$. Here, we assume that ${\mathsf{F}}$
consists of all convex functions over ${\mathcal{W}}$ with uniformly bounded
gradients and let $\mu$ be a distribution over ${\mathsf{F}}$. We further
assume that the cost functions $\\{{\mathsf{f}}_{t}\\}$ are independently
sampled from ${\mathsf{F}}$ according to $\mu$. Inspired by Chen et al. [92],
we define stochastic regret for the randomly stopped OGD algorithm as

$SR(n)\coloneqq{\mathbb{E}}[{\mathsf{f}}(W_{T})]-\inf_{w\in{\mathcal{W}}}{\mathsf{f}}(w),$

where the expectation is taken with respect to the randomness in stopping time
$T$ and ${\mathsf{f}}(w)={\mathbb{E}}_{\mu}[{\mathsf{f}}_{t}(w)]$. Note that
$nSR(n)$ can be thought of as the average regret of an algorithm when applied
several times. The utility of the randomly stopped OGD algorithm is stated
next.

######  Proposition 3.

Assume that $\mathcal{W}\subset\mathbb{R}^{d}$ is a closed convex set,
${\mathsf{F}}$ is a family of convex functions over ${\mathcal{W}}$ with
uniformly bounded gradients, $\\{{\mathsf{f}}_{t}\\}$ are $n$ independent
samples from ${\mathsf{F}}$, and $P_{Z}={\mathcal{N}}(0,\mathbf{I}_{d})$. If
$\displaystyle\eta_{t}=\frac{\textnormal{dia}({\mathcal{W}})}{M\sqrt{t}}$ with
$\displaystyle
M=\sup_{{\mathsf{f}}_{1}\in{\mathsf{F}}}\sup_{w\in{\mathcal{W}}}\lVert\nabla{\mathsf{f}}_{1}(w)\rVert$,
then the randomly stopped OGD algorithm satisfies

$SR(n)\leq\frac{3M\textnormal{dia}({\mathcal{W}})}{2\sqrt{n}}+\frac{d}{2n}\sum_{t=1}^{n}\eta_{t}\sigma_{t}^{2}.$

The previous proposition follows from standard results in online convex
optimization, see, e.g., [17]. For the reader’s convenience, we provide a full
proof in Appendix -I. Combined with Theorem 5, this proposition can be applied
to capture the balance between privacy and utility of OGD algorithm. Consider
the following two examples. For ease of notation, we let $B$ denote the
maximum of $\textnormal{dia}({\mathcal{W}})$ and $D$ defined in Theorem 5,
i.e.,

$B=\max\Big{\\{}\textnormal{dia}({\mathcal{W}}),\max_{t\in[n]}\textnormal{dia}(\Psi^{\mathsf{OGD}}_{{\mathsf{f}}_{t}}(\mathcal{W}))\Big{\\}}.$

Example 3.  If $\sigma_{t}=\sigma$ for some $\sigma>0$, then the randomly
stopped OGD algorithm is $(\varepsilon,\delta)$-DP with666In particular, we
apply (18). Observe that, depending on the values of $\psi$, $D$ and
$\varepsilon$, the bound in (17) might yield tighter results.

$\delta=\frac{1}{n}\theta_{e^{\varepsilon}}\left(\frac{\psi
M\sqrt{n}}{B\sigma}\right)\left[1-\theta_{e^{\varepsilon}}\left(\frac{M\sqrt{n}}{\sigma}\right)\right]^{-1},$

and it satisfies

$SR(n)\leq\frac{B}{\sqrt{n}}\left(\frac{3M}{2}+\frac{d\sigma^{2}}{M}\right).$

It is worth mentioning that Zinkevich [39] showed that the regret (3) of the
OGD algorithm (without privacy constraint) scales as $O(\sqrt{n})$ for
$\eta_{t}=\frac{1}{\sqrt{t}}$ and cannot be improved in general. One can use
the above utility bound to show that $O(\sqrt{n})$ regret can be obtained on
average for the differentially private OGD algorithm (24). Nevertheless, the
privacy guarantee becomes trivial for sufficiently large $n$.

Example 4.  If $\eta_{t}\sigma_{t}=\lambda$ for some $\lambda>0$, then the
randomly stopped OGD algorithm is $(\varepsilon,\delta)$-DP with

$\delta=\frac{1}{n}\theta_{e^{\varepsilon}}\left(\frac{\psi}{\lambda}\right)\left[1-\theta_{e^{\varepsilon}}\left(\frac{B}{\lambda}\right)\right]^{-1},$

and it satisfies

$SR(n)\leq\frac{M}{2}\left(\frac{3D}{\sqrt{n}}+\frac{d\lambda^{2}}{B}\sqrt{n}\right).$

Observe that in this case the utility upper bound becomes trivial for large
$n$ as it diverges as $n\to\infty$. However, the privacy guarantee increases
in $n$ at a rate $O(1/n)$.

The above two examples illustrate the intricate balance between privacy and
utility. In particular, they elucidate that if
$\eta_{t}=O(\frac{1}{\sqrt{t}})$, then a necessary condition for non-trivial
privacy and utility is $\sigma_{t}\to\infty$ and
$\frac{\sigma_{t}}{\sqrt{t}}\to 0$, i.e., $\\{\sigma_{t}\\}_{t}$ must be an
increasing sequence but with a rate slower than $\sqrt{t}$.

##  VII Concluding Remarks and Future Works

In this work, we developed a new information-theoretic framework for studying
the privacy guarantee of online optimization algorithms obtained by adding
independent noise at each iteration. This framework is applicable to
algorithms that process only one input data at a time. Examples of such
algorithms include one pass empirical risk minimization and online gradient
descent algorithms. To characterize the differential privacy guarantee after
$n$ iterations, we first demonstrated that these algorithms can be decomposed
into a concatenation of $n$ Markov kernels each with bounded input and output.
We then showed that the differential privacy parameters of an algorithm is
fully determined by the contraction coefficients of these Markov kernels under
a certain $f$-divergence, namely ${\mathsf{E}}_{\gamma}$-divergence. This
allowed us to translate privacy analysis of an iterative algorithm into the
problem of computing contraction coefficients of its constituent Markov
kernels. When the additive noise is Gaussian, the constituent Markov kernels
were shown to be projected Gaussian Markov kernels whose contraction
coefficient under ${\mathsf{E}}_{\gamma}$-divergence can be computed in a
closed form expression. Using this expression, we characterize a provably
stronger privacy guarantee of one-pass empirical risk minimization algorithm
compared to the existing results. It is worth emphasizing that while the
technique developed in this work is applicable to algorithms that process data
points one at a time, it can be adapted to multi-pass algorithms such as batch
stochastic gradient descent algorithms. The caveat is that at each iteration a
batch of data points must be selected without replacement. With this
assumption in mind, the framework in this work can be adopted to distributed
optimization problems (e.g., federated learning) where user-to-user
communication channels are encrypted and thus the privacy leakage occurs only
by revealing the last parameter update.

This work opens an avenue for the privacy analysis of iterative algorithms
through the lens of information theory. The technique developed in this paper
can be readily adopted to study privacy guarantees of algorithms where the
privacy is measured in terms of more general $f$-divergences (as opposed to
merely ${\mathsf{E}}_{\gamma}$-divergence). For instance, recently DP was
defined in terms of total variation distance [93] and Pearson-Vajda divergence
[89]. This can potentially lead to an interesting generalization of DP with
different statistical and estimation-theoretic operational interpretations and
is the subject of further research.

## References

  * [1] 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.
  * [2] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Proc. Theory of Cryptography (TCC)_ , Berlin, Heidelberg, 2006, pp. 265–284.
  * [3] Differential privacy team Apple, “Learning with privacy at scale,” 2017.
  * [4] TensorFlow Privacy, 2019. [Online]. Available: https://github.com/tensorflow/privacy
  * [5] B. McMahan, G. Andrew, I. Mironov, N. Papernot, P. Kairouz, S. Chien, and U. Erlingsson, “A general approach to adding differential privacy to iterative training procedures,” in _Workshop on Privacy Preserving Machine Learning (NeurIPS 2018)_ , 2018. [Online]. Available: https://arxiv.org/pdf/1812.06210.pdf
  * [6] 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 _SIGMOD_ , 2017, pp. 1307–1322.
  * [7] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization,” _Journal of Machine Learning Research_ , vol. 12, no. Mar, pp. 1069–1109, 2011.
  * [8] R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization, revisited,” in _ICML 2014 Workshop on Learning, Security and Privacy_ , Beijing, China, 25 Jun 2014.
  * [9] R. Bassily, V. Feldman, K. Talwar, and A. Guha Thakurta, “Private stochastic convex optimization with optimal rates,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019, pp. 11 282–11 291.
  * [10] S. Song, K. Chaudhuri, and A. D. Sarwate, “Stochastic gradient descent with differentially private updates,” in _2013 IEEE Global Conference on Signal and Information Processing_ , 2013, pp. 245–248.
  * [11] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proc. ACM SIGSAC CCS_ , 2016, pp. 308–318.
  * [12] B. Balle, G. Barthe, M. Gaboardi, and J. Geumlek, “Privacy amplification by mixing and diffusion mechanisms,” in _NeurIPS_ , 2019, pp. 13 277–13 287.
  * [13] P. Jain, P. Kothari, and A. Thakurta, “Differentially private online learning,” in _Proc. Conference on Learning Theory (COLT)_ , vol. 23, 25–27 Jun 2012, pp. 24.1–24.34.
  * [14] A. Guha Thakurta and A. Smith, “(Nearly) optimal algorithms for private online learning in full-information and bandit settings,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2013, pp. 2733–2741.
  * [15] N. Agarwal and K. Singh, “The price of differential privacy for online learning,” in _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , vol. 70. PMLR, 06–11 Aug 2017, pp. 32–40.
  * [16] A. R. Cardoso and R. Cummings, “Differentially private online submodular minimization,” in _Proc. International Conference on Artificial Intelligence and Statistics (AISTATS)_ , vol. 89, 16–18 Apr 2019, pp. 1650–1658.
  * [17] E. Hazan, “Introduction to online convex optimization,” _Found. Trends Optim._ , vol. 2, no. 3–4, p. 157–325, Aug. 2016.
  * [18] S. Shalev-Shwartz, “Online learning and online convex optimization,” _Found. Trends Mach. Learn._ , vol. 4, no. 2, p. 107–194, Feb. 2012.
  * [19] E. Takimoto and M. K. Warmuth, “Path kernels and multiplicative updates,” _Journal of Machine Learning Research_ , vol. 4, pp. 773–818, Oct. 2003.
  * [20] J. Ma, L. K. Saul, S. Savage, and G. M. Voelker, “Identifying suspicious urls: An application of large-scale online learning,” in _Proc. International Conference on Machine Learning_ , ser. ICML ’09. New York, NY, USA: Association for Computing Machinery, 2009, p. 681–688.
  * [21] T. M. Cover, “Universal portfolios,” _Mathematical Finance_ , vol. 1, no. 1, pp. 1–29, 1991.
  * [22] B. Li, S. Hoi, P. Zhao, and V. Gopalkrishnan, “Confidence weighted mean reversion strategy for on-line portfolio selection,” in _International Conference on Artificial Intelligence and Statistics (AISTAT)_ , vol. 15, 2011, pp. 434–442.
  * [23] A. Kalai and S. Vempala, “Efficient algorithms for universal portfolios,” _Journal of Machine Learning Research_ , vol. 3, p. 423–440, 2002.
  * [24] A. Ben-Tal, E. Hazan, T. Koren, and S. Mannor, “Oracle-based robust optimization via online learning,” _Operations Research_ , vol. 63, no. 3, pp. 628–638, June 2015.
  * [25] E. Hazan and S. Kale, “An optimal algorithm for stochastic strongly-convex optimization,” _Journal of Machine Learning Research_ , vol. 15, p. 2489– 2512, 2014.
  * [26] K. Chaudhuri and N. Mishra, “When random sampling preserves privacy,” in _Advances in Cryptology - CRYPTO 2006_. Springer Berlin Heidelberg, 2006, pp. 198–213.
  * [27] K. Chaudhuri and C. Monteleoni, “Privacy-preserving logistic regression,” in _Advances in Neural Information Processing Systems_ , D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, Eds., 2009, pp. 289–296.
  * [28] A. G. Thakurta and A. Smith, “Differentially private feature selection via stability arguments, and the robustness of the lasso,” in _Proceedings of the 26th Annual Conference on Learning Theory_ , ser. Proceedings of Machine Learning Research, S. Shalev-Shwartz and I. Steinwart, Eds., vol. 30. Princeton, NJ, USA: PMLR, 12–14 Jun 2013, pp. 819–850.
  * [29] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in _Proc. of IEEE Foundations of Computer Science (FOCS)_ , 2013.
  * [30] P. Jain and A. G. Thakurta, “(near) dimension independent risk bounds for differentially private learning,” in _Proc. of the 31st International Conference on Machine Learning (ICML)_ , vol. 32, no. 1, 22–24 Jun 2014, pp. 476–484.
  * [31] A. Smith, A. Thakurta, and J. Upadhyay, “Is interaction necessary for distributed private learning?” in _2017 IEEE Symposium on Security and Privacy (SP)_ , 2017, pp. 58–77.
  * [32] K. Talwar, A. Thakurta, and L. Zhang, “Nearly-optimal private lasso,” in _Proc. International Conference on Neural Information Processing Systems (NeurIPS)_ , Cambridge, MA, USA, 2015, p. 3025–3033.
  * [33] D. Wang, M. Ye, and J. Xu, “Differentially private empirical risk minimization revisited: Faster and more general,” in _Proc. of the 31st International Conference on Neural Information Processing Systems (NeurIPS)_ , 2017, p. 2719–2728.
  * [34] R. Ahlswede and P. Gács, “Spreading of sets in product spaces and hypercontraction of the markov operator,” _Ann. Probab._ , vol. 4, no. 6, pp. 925–939, 12 1976.
  * [35] M. Raginsky, “Strong data processing inequalities and$\phi$-sobolev inequalities for discrete channels,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 6, pp. 3355–3389, June 2016.
  * [36] G. Barthe and F. Olmedo, “Beyond differential privacy: Composition theorems and relational logic for $f$-divergences between probabilistic programs,” in _Proc. ICALP_ , 2013, pp. 49–60.
  * [37] B. Balle, G. Barthe, M. Gaboardi, J. Hsu, and T. Sato, “Hypothesis testing interpretations and Rényi differential privacy,” _ArXiv_ , vol. abs/1905.09982, 2019.
  * [38] R. L. Dobrushin, “Central limit theorem for nonstationary markov chains. I,” _Theory Probab. Appl._ , vol. 1, no. 1, pp. 65–80, 1956.
  * [39] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in _Proceedings of the Twentieth International Conference on International Conference on Machine Learning (ICML)_ , 2003, p. 928–935.
  * [40] B. Kulis and P. L. Bartlett, “Implicit online learning,” in _Proceedings of the 27th International Conference on International Conference on Machine Learning (ICML)_ , 2010, pp. 575–582.
  * [41] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer, “Online passive-aggressive algorithms,” _J. Mach. Learn. Res._ , vol. 7, p. 551–585, Dec. 2006.
  * [42] J. C. Duchi, S. Shalev-shwartz, Y. Singer, and A. Tewari, “Composite objective mirror descent,” in _Proc. Conference on Learning Theory (COLT)_ , 2010, pp. 14–26.
  * [43] M. Frank and P. Wolfe, “An algorithm for quadratic programming,” _Naval Research Logistics Quarterly_ , vol. 3, no. 1-2, pp. 95–110, 1956.
  * [44] J. Abernethy, E. Hazan, and A. Rakhlin, “Competing in the dark: An efficient algorithm for bandit linear optimization,” 2008. [Online]. Available: http://www.mit.edu/~rakhlin/papers/AbeHazRak08.pdf
  * [45] S. Shalev-Shwartz and Y. Singer, “A primal-dual perspective of online learning algorithms,” _Mach. Learn._ , vol. 69, no. 2–3, p. 115–142, Dec. 2007\.
  * [46] E. Hazan, “Extracting certainty from uncertainty: Regret bounded by variation in costs,” in _In COLT_ , 2008.
  * [47] B. McMahan, “Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization,” in _Proc. International Conference on Artificial Intelligence and Statistics (AISTAT)_ , vol. 15, 11–13 Apr 2011, pp. 525–533.
  * [48] A. Rakhlin, O. Shamir, and K. Sridharan, “Making gradient descent optimal for strongly convex stochastic optimization,” in _Proc. International Coference on International Conference on Machine Learning_ , 2012, p. 1571–1578.
  * [49] O. Shamir and T. Zhang, “Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes,” in _Proc. International Conference on Machine Learning_ , vol. 28, no. 1. PMLR, 17–19 Jun 2013, pp. 71–79.
  * [50] J. Abernethy, K. A. Lai, and A. Wibisono, “Last-iterate convergence rates for min-max optimization,” 2019.
  * [51] Q. Lei, S. G. Nagarajan, I. Panageas, and X. Wang, “Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes,” 2020.
  * [52] Y. Lei, P. Yang, K. Tang, and D.-X. Zhou, “Optimal stochastic and online learning with individual iterates,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019, pp. 5415–5425.
  * [53] V. Feldman, I. Mironov, K. Talwar, and A. Thakurta, “Privacy amplification by iteration,” _FOCS_ , pp. 521–532, 2018.
  * [54] S. Augenstein, H. B. McMahan, D. Ramage, S. Ramaswamy, P. Kairouz, M. Chen, R. Mathews, and B. A. y Arcas, “Generative models for effective ML on private, decentralized datasets,” in _International Conference on Learning Representations_ , 2020. [Online]. Available: https://openreview.net/forum?id=SJgaRA4FPH
  * [55] S. M. Kakade and A. Tewari, “On the generalization ability of online strongly convex programming algorithms,” in _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , 2009, pp. 801–808.
  * [56] I. Mironov, “Rényi differential privacy,” in _Proc. Computer Security Found. (CSF)_ , 2017, pp. 263–275.
  * [57] S. Asoodeh, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar, “A better bound gives a hundred rounds: Enhanced privacy guarantees via $f$-divergences,” in _Proc. of Int. Symp. Inf Theory (ISIT)_ , 2020. [Online]. Available: https://arxiv.org/abs/2001.05990
  * [58] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum, “Differential privacy under continual observation,” in _Proc. of the Forty-Second ACM Symposium on Theory of Computing_ , ser. STOC ’10, 2010, p. 715–724.
  * [59] V. Anantharam, A. Gohari, S. Kamath, and C. Nair, “On hypercontractivity and a data processing inequality,” in _2014 IEEE Int. Symp. Inf. Theory_ , 2014, pp. 3022–3026.
  * [60] Y. Polyanskiy and Y. Wu, “Dissipation of information in channels with input constraints,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 1, pp. 35–55, Jan 2016.
  * [61] A. Kontorovich and M. Raginsky, “Concentration of measure without independence: A unified approach via the martingale method,” in _Convexity and Concentration_. Springer New York, 2017, pp. 183–210.
  * [62] F. d. P. Calmon, Y. Polyanskiy, and Y. Wu, “Strong data processing inequalities for input constrained additive noise channels,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 3, pp. 1879–1892, 2018.
  * [63] A. Makur and L. Zheng, “Bounds between contraction coefficients,” 2018. [Online]. Available: http://arxiv.org/abs/1510.01844
  * [64] Y. Polyanskiy and Y. Wu, “Strong data-processing inequalities for channels and bayesian networks,” in _Convexity and Concentration_ , E. Carlen, M. Madiman, and E. M. Werner, Eds. New York, NY: Springer New York, 2017, pp. 211–249.
  * [65] A. Makur and Y. Polyanskiy, “Comparison of channels: Criteria for domination by a symmetric channel,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 8, pp. 5704–5725, 2018.
  * [66] A. Xu and M. Raginsky, “Converses for distributed estimation via strong data processing inequalities,” in _2015 IEEE International Symposium on Information Theory (ISIT)_ , 2015, pp. 2376–2380.
  * [67] M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. P. Woodruff, “Communication lower bounds for statistical estimation problems via a distributed data processing inequality,” in _Proc. of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC)_ , 2016, p. 1011–1020.
  * [68] A. Xu and M. Raginsky, “Information-theoretic lower bounds for distributed function computation,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 4, pp. 2314–2337, 2017.
  * [69] J. Duchi and R. Rogers, “Lower bounds for locally private estimation via communication complexity,” in _Proc. of the Thirty-Second Conference on Learning Theory (COLT)_ , vol. 99, 25–28 Jun 2019, pp. 1161–1191.
  * [70] M. Joseph, J. Kulkarni, J. Mao, and S. Z. Wu, “Locally private gaussian estimation,” in _Advances in Neural Information Processing Systems 32_ , 2019, pp. 2984–2993.
  * [71] P. Kamalaruban, “Transitions, losses, and re-parameterizations: Elements of prediction games,” Ph.D. dissertation, The Australian National University, 2018\.
  * [72] M. H. DeGroot, “Uncertainty, information, and sequential experiments,” _Ann. Math. Statist._ , vol. 33, no. 2, pp. 404–419, 06 1962.
  * [73] P. Billingsley, _Probability and Measure_ , 3rd ed. John Wiley and Sons, 1995.
  * [74] F. McSherry and I. Mironov, “Differentially private recommender systems: Building privacy into the netflix prize contenders,” in _Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , 2009, p. 627–636.
  * [75] R. Guerraoui, A.-M. Kermarrec, R. Patra, and M. Taziki, “D2p: Distance-based differential privacy in recommenders,” _Proc. VLDB Endow._ , vol. 8, no. 8, p. 862–873, Apr. 2015.
  * [76] E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private distributed convex optimization via functional perturbation,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 1, pp. 395–408, March 2018.
  * [77] S. M. Ali and S. D. Silvey, “A general class of coefficients of divergence of one distribution from another,” _Journal of Royal Statistics_ , vol. 28, pp. 131–142, 1966.
  * [78] I. Csiszár, “Information-type measures of difference of probability distributions and indirect observations,” _Studia Sci. Math. Hungar._ , vol. 2, pp. 299–318, 1967.
  * [79] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 5, pp. 2307–2359, 2010.
  * [80] N. Sharma and N. A. Warsi, “Fundamental bound on the reliability of quantum information transmission,” _CoRR_ , vol. abs/1302.5281, 2013. [Online]. Available: http://arxiv.org/abs/1302.5281
  * [81] I. Csiszár and P. C. Shields, “Information theory and statistics: A tutorial,” _Commun. Inf. Theory_ , vol. 1, no. 4, pp. 417–528, Dec. 2004\.
  * [82] B. Balle and Y.-X. Wang, “Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising,” in _ICML_ , vol. 80, 10–15 July 2018, pp. 394–403.
  * [83] J. Cohen, J. Kemperman, and G. Zbăganu, _Comparisons of Stochastic Matrices, with Applications in Information Theory, Statistics, Economics, and Population Sciences_. Birkhäuser, 1998\.
  * [84] I. Sason and S. Verdú, “$f$-divergence inequalities,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 11, pp. 5973–6006, 2016.
  * [85] P. Del Moral, M. Ledoux, and L. Miclo, “On contraction properties of markov kernels,” _Probab. Theory Relat. Fields_ , vol. 126, pp. 395–420, 2003.
  * [86] Y.-X. Wang, “Per-instance differential privacy,” _Journal of Privacy and Confidentiality_ , vol. 9, no. 1, Mar. 2019.
  * [87] K. S. S. Kumar and M. P. Deisenroth, “Differentially private empirical risk minimization with sparsity-inducing norms,” _arXiv:1905.04873_ , 2019.
  * [88] R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error bounds,” in _Proc. of IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2014, pp. 464–473.
  * [89] Y.-X. Wang, B. Balle, and S. P. Kasiviswanathan, “Subsampled Rényi differential privacy and analytical moments accountant,” in _AISTAT_ , vol. 89, 16–18 Apr 2018, pp. 1226–1235.
  * [90] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers, “Protection against reconstruction and its applications in private federated learning,” 2018\.
  * [91] https://github.com/tensorflow/privacy/blob/master/tensorflow_privacy/privacy/analysis/rdp_accountant.py, [Online; accessed 15-December-2020].
  * [92] L. Chen, C. Harshaw, H. Hassani, and A. Karbasi, “Projection-free online optimization with stochastic gradient: From convexity to submodularity,” in _Proc. of the 35th International Conference on Machine Learning (ICML)_ , vol. 80, 10–15 Jul 2018, pp. 814–823.
  * [93] Q. Geng, W. Ding, R. Guo, and S. Kumar, “Optimal noise-adding mechanism in additive differential privacy,” in _Proc. of International Conference on Artificial Intelligence and Statistics (AISTATS)_ , vol. 89, 16–18 Apr 2019, pp. 11–20.
  * [94] S. Bubeck, _Convex Optimization: Algorithms and Complexity_. Foundations and Trends in Machine Learning, 2015, vol. 8, no. 3–4.

###  -A Proof of Theorem 3

Observe that the case $\gamma=1$ corresponds to Dobrushin’s formula (5), so we
assume that $\gamma>1$. We begin by showing that, for any two probability
measures $\mu,\nu\in{\mathcal{P}}({\mathcal{D}})$,

${\mathsf{E}}_{\gamma}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})\leq{\mathsf{E}}_{\gamma}(\mu\|\nu)\sup_{w_{1},w_{2}\in{\mathcal{D}}}{\mathsf{E}}_{\gamma}({\mathsf{K}}(w_{1})\|{\mathsf{K}}(w_{2})),$

or equivalently

$\eta_{\gamma}({\mathsf{K}})\leq\sup_{w_{1},w_{2}\in{\mathcal{D}}}{\mathsf{E}}_{\gamma}({\mathsf{K}}(w_{1})\|{\mathsf{K}}(w_{2})).$
(25)

Let $\phi\coloneqq\mu-\gamma\nu$ and $(\phi^{+},\phi^{-})$ be its Hahn-Jordan
decomposition. By the definition of ${\mathsf{E}}_{\gamma}$ in (6), we have
that ${\mathsf{E}}_{\gamma}(\mu\|\nu)=\lVert\phi^{+}\rVert$ and

$\displaystyle{\mathsf{E}}_{\gamma}(\mu\|\nu)$
$\displaystyle=\frac{1}{2}\lVert\phi^{+}\rVert+\frac{1}{2}\lVert\phi^{-}\rVert+\frac{1}{2}\lVert\phi^{+}\rVert-\frac{1}{2}\lVert\phi^{-}\rVert$
$\displaystyle=\frac{1}{2}\lVert\phi\rVert+\frac{1}{2}(1-\gamma),$ (26)

where the last equality follows from the fact that $\phi^{+}$ and $\phi^{-}$
are positive measures and thus

$\displaystyle\lVert\phi^{+}\rVert-\lVert\phi^{-}\rVert=\phi^{+}({\mathcal{D}})-\phi^{-}({\mathcal{D}})=\phi({\mathcal{D}}).$

Mutatis mutandis, we have that

${\mathsf{E}}_{\gamma}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})=\frac{1}{2}\lVert\phi{\mathsf{K}}\rVert+\frac{1}{2}(1-\gamma).$
(27)

It can be verified that if $\phi^{+}$ is the zero measure, then so is
$(\phi{\mathsf{K}})^{+}$. In this case, (25) holds trivially as
${\mathsf{E}}_{\gamma}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})=\lVert(\phi{\mathsf{K}})^{+}\rVert=0$.
Assume that $\phi^{+}$ is not the zero measure. Observe that

$\phi^{+}({\mathcal{D}})-\phi^{-}({\mathcal{D}})=\phi({\mathcal{D}})=1-\gamma<0,$

which implies that $\phi^{-}({\mathcal{D}})>0$. In particular, the measures
$\lVert\phi^{+}\rVert^{-1}\phi^{+}$ and $\lVert\phi^{-}\rVert^{-1}\phi^{-}$
are probability measures. A straightforward manipulation shows that

$\displaystyle\lVert\phi{\mathsf{K}}\rVert$
$\displaystyle=\left\lVert\int{\mathsf{K}}(w_{1})\text{d}\phi^{+}(w_{1})-\int{\mathsf{K}}(w_{2})\text{d}\phi^{-}(w_{2})\right\rVert$
$\displaystyle=\left\lVert\int\int\Big{[}\lVert\phi^{+}\rVert{\mathsf{K}}(w_{1})-\lVert\phi^{-}\rVert{\mathsf{K}}(w_{2})\Big{]}\frac{\text{d}\phi^{+}(w_{1})}{\lVert\phi^{+}\rVert}\frac{\text{d}\phi^{-}(w_{2})}{\lVert\phi^{-}\rVert}\right\rVert$
$\displaystyle\leq\sup_{w_{1},w_{2}\in{\mathcal{D}}}\left\lVert\lVert\phi^{+}\rVert{\mathsf{K}}(w_{1})-\lVert\phi^{-}\rVert{\mathsf{K}}(w_{2})\right\rVert.$

By adding and subtracting the term
$\gamma\lVert\phi^{+}\rVert{\mathsf{K}}(w_{2})$, the triangle inequality
implies that

$\displaystyle\left\lVert\lVert\phi^{+}\rVert{\mathsf{K}}(w_{1})-\lVert\phi^{-}\rVert{\mathsf{K}}(w_{2})\right\rVert$
$\displaystyle\leq\lVert\phi^{+}\rVert\lVert{\mathsf{K}}(w_{1})-\gamma{\mathsf{K}}(w_{2})\rVert+\lVert\phi^{-}\rVert-\gamma\lVert\phi^{+}\rVert$
$\displaystyle=\lVert\phi^{+}\rVert\left(\lVert{\mathsf{K}}(w_{1})-\gamma{\mathsf{K}}(w_{2})\rVert+1-\gamma\right)-(1-\gamma),$

where we used the inequality
$\lVert\phi^{-}\rVert-\gamma\lVert\phi^{+}\rVert\geq 0$ and the identity
$1-\gamma=\lVert\phi^{+}\rVert-\lVert\phi^{-}\rVert$. Therefore,

$\displaystyle\lVert\phi{\mathsf{K}}\rVert$
$\displaystyle\leq\lVert\phi^{+}\rVert\sup_{w_{1},w_{2}\in{\mathcal{D}}}\left(\lVert{\mathsf{K}}(w_{1})-\gamma{\mathsf{K}}(w_{2})\rVert+1-\gamma\right)-(1-\gamma)$
$\displaystyle=2\lVert\phi^{+}\rVert\sup_{w_{1},w_{2}\in{\mathcal{D}}}{\mathsf{E}}_{\gamma}({\mathsf{K}}(w_{1})\|{\mathsf{K}}(w_{2}))-(1-\gamma),$

where the equality follows from (26). By plugging the previous inequality in
(27), we obtain that

${\mathsf{E}}_{\gamma}(\mu{\mathsf{K}}\|\nu{\mathsf{K}})\leq{\mathsf{E}}_{\gamma}(\mu\|\nu)\sup_{w_{1},w_{2}\in{\mathcal{D}}}{\mathsf{E}}_{\gamma}({\mathsf{K}}(w_{1})\|{\mathsf{K}}(w_{2})).$

Now we show that the equality in (25) is attained. For $w\in{\mathcal{D}}$,
let $\delta_{w}$ be the Dirac mass at $w$. Observe that for
$w_{1},w_{2}\in{\mathcal{D}}$ such that $w_{1}\neq w_{2}$, we have that

${\mathsf{E}}_{\gamma}(\delta_{w_{1}}\|\delta_{w_{2}})=(\delta_{w_{1}}-\gamma\delta_{w_{2}})^{+}({\mathcal{D}})=1.$

Since $\delta_{w}{\mathsf{K}}={\mathsf{K}}(w)$ for each $w\in{\mathcal{D}}$,
we have that

$\frac{{\mathsf{E}}_{\gamma}(\delta_{w_{1}}{\mathsf{K}}\|\delta_{w_{2}}{\mathsf{K}})}{{\mathsf{E}}_{\gamma}(\delta_{w_{1}}\|\delta_{w_{2}})}={\mathsf{E}}_{\gamma}({\mathsf{K}}(w_{1})\|{\mathsf{K}}(w_{2})).$

By the definition of $\eta_{\gamma}({\mathsf{K}})$ in (4), we conclude that

$\displaystyle\eta_{\gamma}({\mathsf{K}})$ $\displaystyle\geq\sup_{w_{1}\neq
w_{2}}\frac{{\mathsf{E}}_{\gamma}(\delta_{w_{1}}{\mathsf{K}}\|\delta_{w_{2}}{\mathsf{K}})}{{\mathsf{E}}_{\gamma}(\delta_{w_{1}}\|\delta_{w_{2}})}$
$\displaystyle=\sup_{w_{1}\neq
w_{2}}{\mathsf{E}}_{\gamma}({\mathsf{K}}(w_{1})\|{\mathsf{K}}(w_{2})),$

as we wanted to show.

###  -B Proof of Lemma 1

A direct computation shows that

$\iota_{\mathcal{N}_{1}\|\mathcal{N}_{2}}(t)=\frac{2\langle
t,m_{1}-m_{2}\rangle+\|m_{2}\|^{2}-\|m_{1}\|^{2}}{2\sigma^{2}},$

where $\langle\cdot,\cdot\rangle$ denotes the inner product and $\iota_{P\|Q}$
is defined in Section II-C. As a consequence, we have that

$\iota_{\mathcal{N}_{1}\|\mathcal{N}_{2}}(Y)\sim\begin{cases}{\mathcal{N}}(\beta^{2}/2,\beta^{2})&\text{whenever
}Y\sim{\mathcal{N}}_{1},\\\
{\mathcal{N}}(-\beta^{2}/2,\beta^{2})&\text{whenever
}Y\sim{\mathcal{N}}_{2},\end{cases}$ (28)

where $\displaystyle\beta\coloneqq\frac{\|m_{1}-m_{2}\|}{\sigma}$. Therefore,
by plugging (28) in the expression for ${\mathsf{E}}_{\gamma}$ given in (7),

${\mathsf{E}}_{\gamma}(\mathcal{N}_{1}\|\mathcal{N}_{2})={\mathsf{Q}}\left(\frac{\log\gamma}{\beta}-\frac{\beta}{2}\right)-\gamma{\mathsf{Q}}\left(\frac{\log\gamma}{\beta}+\frac{\beta}{2}\right),$

as required.

###  -C Proof of Proposition 1

For ease of notation, let ${\mathsf{K}}_{0}$ denote the (unbounded) additive
Gaussian kernel. Note that
${\mathsf{K}}=\Pi_{\mathcal{W}}\circ{\mathsf{K}}_{0}$. By Theorem 3, we have
that

$\displaystyle\eta_{\gamma}({\mathsf{K}})$
$\displaystyle=\sup_{w_{1},w_{2}\in\mathcal{D}}{\mathsf{E}}_{\gamma}(\Pi_{\mathcal{K}}({\mathsf{K}}_{0}(w_{1}))\|\Pi_{\mathcal{W}}({\mathsf{K}}_{0}(w_{2})))$
$\displaystyle\leq\sup_{w_{1},w_{2}\in\mathcal{D}}{\mathsf{E}}_{\gamma}({\mathsf{K}}_{0}(w_{1})\|{\mathsf{K}}_{0}(w_{2}))$
$\displaystyle=\sup_{w_{1},w_{2}\in\mathcal{D}}{\mathsf{E}}_{\gamma}(\mathcal{N}(w_{1},\sigma^{2}\mathbf{I}_{d})\|\mathcal{N}(w_{2},\sigma^{2}\mathbf{I}_{d})),$

where the inequality follows from the data processing inequality. It could be
verified that $r\mapsto\theta_{\gamma}(r)$ is increasing. Hence, by (9), we
conclude that

$\eta_{\gamma}({\mathsf{K}})=\sup_{w_{1},w_{2}\in\mathcal{D}}\theta_{\gamma}\left(\frac{\|w_{2}-w_{1}\|}{\sigma}\right)=\theta_{\gamma}\left(\frac{\textnormal{dia}(\mathcal{D})}{\sigma}\right),$

as desired.

###  -D Proof of Lemma 2

Recall that, by definition,

$\mu_{n+1}=\mu_{1}{\mathsf{K}}_{{\mathsf{f}}_{1}}\cdots{\mathsf{K}}_{{\mathsf{f}}_{n}}\quad\text{and}\quad\mu_{n+1}=\mu_{1}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{1}}\cdots{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{n}}.$

Since $\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}$, we have
${\mathsf{K}}_{{\mathsf{f}}_{t}}={\mathsf{K}}_{{\mathsf{f}}^{\prime}_{t}}$ for
all $t\in[n]\backslash{\\{i\\}}$ and
${\mathsf{K}}_{{\mathsf{f}}_{i}}\neq{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}}$.
In particular,

$\mu_{n+1}=\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}{\mathsf{K}}_{{\mathsf{f}}_{i+1}}\cdots{\mathsf{K}}_{{\mathsf{f}}_{n}}\quad\text{and}\quad\mu^{\prime}_{n+1}=\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}}{\mathsf{K}}_{{\mathsf{f}}_{i+1}}\cdots{\mathsf{K}}_{{\mathsf{f}}_{n}}.$

By repeatedly invoking (4), we obtain that

$\displaystyle D_{f}(\mu_{n+1}\|\mu^{\prime}_{n+1})$
$\displaystyle=D_{f}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}{\mathsf{K}}_{{\mathsf{f}}_{i+1}}\cdots{\mathsf{K}}_{{\mathsf{f}}_{n}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}}{\mathsf{K}}_{{\mathsf{f}}_{i+1}}\cdots{\mathsf{K}}_{{\mathsf{f}}_{n}})$
$\displaystyle\leq
D_{f}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}})\prod_{t=i+1}^{n}\eta_{f}({\mathsf{K}}_{{\mathsf{f}}_{t}}),$

as we wanted to prove.

###  -E Proof of Theorem 4

Let $\mu_{1}$ be the initial distribution of the iterative process and
$\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}^{\prime}_{t}\\}$ be a pair of neighboring
collections of cost functions. In light of Theorem 2 and Lemma 2, we have

$\delta={\mathsf{E}}_{e^{\varepsilon}}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}})\prod_{t=i+1}^{n}\eta_{e^{\varepsilon}}({\mathsf{K}}_{{\mathsf{f}}_{t}}).$
(29)

We begin by bounding $\eta_{\gamma}({\mathsf{K}}_{{\mathsf{f}}_{t}})$. Each
kernel ${\mathsf{K}}_{{\mathsf{f}}_{t}}$ can be decomposed as

${\mathsf{K}}_{{\mathsf{f}}_{t}}={\mathsf{K}}_{t}\circ\Psi_{{\mathsf{f}}_{t}},$

where ${\mathsf{K}}_{t}$ is the projected additive Gaussian kernel associated
with $(\Psi_{{\mathsf{f}}_{t}}(\mathcal{W}),\mathcal{W},\sigma_{t})$, as
defined in Section III. By Theorem 3, we have

$\displaystyle\eta_{e^{\varepsilon}}({\mathsf{K}}_{{\mathsf{f}}_{t}})$
$\displaystyle=\sup_{w_{1},w_{2}\in\mathcal{W}}{\mathsf{E}}_{e^{\varepsilon}}({\mathsf{K}}_{t}(\Psi_{{\mathsf{f}}_{t}}(w_{1}))\|{\mathsf{K}}_{t}(\Psi_{{\mathsf{f}}_{t}}(w_{2})))$
$\displaystyle=\sup_{w_{1},w_{2}\in\Psi_{{\mathsf{f}}_{t}}(\mathcal{W})}{\mathsf{E}}_{e^{\varepsilon}}({\mathsf{K}}_{t}(w_{1})\|{\mathsf{K}}_{t}(w_{2}))$
$\displaystyle=\eta_{{e^{\varepsilon}}}({\mathsf{K}}_{t})$
$\displaystyle=\theta_{{e^{\varepsilon}}}\left(\frac{\textnormal{dia}(\Psi_{{\mathsf{f}}_{t}}(\mathcal{W}))}{\sigma_{t}}\right),$
(30)

where the last equality comes from Proposition 1.

Next, we look at the first term in the RHS of (29). By Jensen’s inequality, we
can write

${\mathsf{E}}_{e^{\varepsilon}}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}^{\prime}})\leq\int_{\mathcal{W}}{\mathsf{E}}_{e^{\varepsilon}}({\mathsf{K}}_{{\mathsf{f}}_{i}}(w)\|{\mathsf{K}}_{{\mathsf{f}}_{i}^{\prime}}(w))\text{d}\mu_{i}(w).$

Observe that, for every $w\in\mathcal{W}$,

${\mathsf{K}}_{{\mathsf{f}}_{i}}(w)\sim\Pi_{\mathcal{W}}(\Psi_{{\mathsf{f}}_{i}}(w)+\sigma_{i}Z),$

where $Z\sim\mathcal{N}(0,\mathbf{I}_{d})$. A similar relation holds for
${\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}}$. By the data processing inequality,
we obtain that

${\mathsf{E}}_{e^{\varepsilon}}({\mathsf{K}}_{{\mathsf{f}}_{i}}(w)\|{\mathsf{K}}_{{\mathsf{f}}_{i}^{\prime}}(w))\leq{\mathsf{E}}_{e^{\varepsilon}}(\Psi_{{\mathsf{f}}_{i}}(w)+\sigma_{i}Z\|\Psi_{{\mathsf{f}}^{\prime}_{i}}(w)+\sigma_{i}Z).$

Therefore, Lemma 1 implies that

$\displaystyle{\mathsf{E}}_{e^{\varepsilon}}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}^{\prime}})$
$\displaystyle\leq\int_{{\mathcal{W}}}\theta_{e^{\varepsilon}}\left(\frac{\|\Psi_{{\mathsf{f}}_{i}}(y)-\Psi_{{\mathsf{f}}^{\prime}_{i}}(y)\|}{\sigma_{i}}\right)\text{d}\mu_{i}(y)\leq\theta_{e^{\varepsilon}}\left(\frac{\psi}{\sigma_{i}}\right),$
(31)

where the last inequality is due to the fact that $r\mapsto\theta_{\gamma}(r)$
is increasing. Plugging (30) and (31) into (29), we obtain the desired result.

###  -F Proof of Theorem 5

Assume that $\\{{\mathsf{f}}_{t}\\}$ and $\\{{\mathsf{f}}^{\prime}_{t}\\}$ are
collections of cost functions such that
$\\{{\mathsf{f}}_{t}\\}\stackrel{{\scriptstyle
i}}{{\sim}}\\{{\mathsf{f}}_{t}^{\prime}\\}$ for some $i\in[n]$. Let $T$ be a
uniform random variable over $[n]$. If $\mu_{T+1}$ and $\mu^{\prime}_{T+1}$
are the distributions of the output of Algorithm 1 applied to
$\\{{\mathsf{f}}_{t}\\}$ and $\\{{\mathsf{f}}^{\prime}_{t}\\}$, respectively,
then

$\mu_{T+1}=\frac{1}{n}\sum_{t=1}^{n}\mu_{1}{\mathsf{K}}_{{\mathsf{f}}_{1}}\dots\mathsf{K}_{{\mathsf{f}}_{t}}\quad\text{and}\quad\mu^{\prime}_{T+1}=\frac{1}{n}\sum_{t=1}^{n}\mu_{1}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{1}}\dots\mathsf{K}_{{\mathsf{f}}^{\prime}_{t}}.$

The convexity777For any convex function $f$ on $\mathbb{R}_{+}$, its
perspective, i.e., $(p,q)\mapsto qf\big{(}\frac{p}{q}\big{)}$, is convex on
$\mathbb{R}_{+}^{2}$. Since
$D_{f}(\mu\|\nu)={\mathbb{E}}_{\nu}\Big{[}f\big{(}\frac{\text{d}\mu}{\text{d}\nu}\big{)}\Big{]}$,
it follows that $(\mu,\nu)\mapsto D_{f}(\mu\|\nu)$ is convex. of
$(\mu,\nu)\mapsto{\mathsf{E}}_{\gamma}(\mu\|\nu)$, and Jensen’s inequality
imply that

$\mathbb{{\mathsf{E}}}_{e^{\varepsilon}}(\mu_{T+1}\|\mu^{\prime}_{T+1})\leq\frac{1}{n}\sum_{t=1}^{n}\mathbb{{\mathsf{E}}}_{e^{\varepsilon}}(\mu_{1}{\mathsf{K}}_{{\mathsf{f}}_{1}}\dots\mathsf{K}_{{\mathsf{f}}_{t}}\|\mu_{1}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{1}}\dots\mathsf{K}_{{\mathsf{f}}^{\prime}_{t}}).$
(32)

Recall that ${\mathsf{f}}_{j}={\mathsf{f}}_{j}^{\prime}$ for all $j\neq i$. In
particular,
$\mu_{1}{\mathsf{K}}_{{\mathsf{f}}_{1}}\dots\mathsf{K}_{{\mathsf{f}}_{t}}=\mu_{1}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{1}}\dots\mathsf{K}_{{\mathsf{f}}^{\prime}_{t}}$
for all $t<i$ and hence

$\mathbb{{\mathsf{E}}}_{e^{\varepsilon}}(\mu_{T+1}\|\mu^{\prime}_{T+1})\leq\frac{1}{n}\sum_{t=i}^{n}{\mathsf{E}_{e^{\varepsilon}}}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\dots\mathsf{K}_{{\mathsf{f}}_{t}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}}\dots\mathsf{K}_{{\mathsf{f}}^{\prime}_{t}}),$
(33)

where
$\mu_{i}=\mu_{1}{\mathsf{K}}_{{\mathsf{f}}_{1}}\dots\mathsf{K}_{{\mathsf{f}}_{i-1}}$.
As in the proof of Theorem 4, each summand can be bounded via Lemma 2 to
obtain

${\mathsf{E}}_{e^{\varepsilon}}(\mu_{T+1}\|\mu^{\prime}_{T+1})\leq\frac{1}{n}\sum_{t=i}^{n}{\mathsf{E}}_{e^{\varepsilon}}(\mu_{i}{\mathsf{K}}_{{\mathsf{f}}_{i}}\|\mu_{i}{\mathsf{K}}_{{\mathsf{f}}^{\prime}_{i}})\prod_{j=i+1}^{t}\eta_{e^{\varepsilon}}({\mathsf{K}}_{{\mathsf{f}}_{j}}).$
(34)

Furthermore, (30) and (31) imply that

${\mathsf{E}}_{e^{\varepsilon}}(\mu_{T+1}\|\mu^{\prime}_{T+1})\leq\frac{1}{n}\sum_{t=i}^{n}\theta_{e^{\varepsilon}}\left(\frac{\psi}{\sigma_{i}}\right)\prod_{j=i+1}^{t}\theta_{e^{\varepsilon}}\left(\frac{D}{\sigma_{j}}\right),$

where we used the fact that $r\mapsto\theta_{\gamma}(r)$ is increasing. By
taking the minimum over $i$, Theorem 2 leads to (17). By further exploiting
the monotonicity of $r\mapsto\theta_{\gamma}(r)$, we obtain that

$\delta\leq\frac{1}{n}\sum_{t=i}^{n}\theta_{e^{\varepsilon}}\Big{(}\frac{\psi}{\sigma}\Big{)}\prod_{j=i+1}^{t}\theta_{e^{\varepsilon}}\Big{(}\frac{D}{\sigma}\Big{)}.$

A straightforward manipulation leads to

$\displaystyle\delta$
$\displaystyle\leq\frac{1}{n}\theta_{e^{\varepsilon}}\Big{(}\frac{\psi}{\sigma}\Big{)}\sum_{t=0}^{n-i}\left[\theta_{e^{\varepsilon}}\Big{(}\frac{D}{\sigma}\Big{)}\right]^{t}$
$\displaystyle\leq\frac{1}{n}\theta_{e^{\varepsilon}}\Big{(}\frac{\psi}{\sigma}\Big{)}\left[1-\theta_{e^{\varepsilon}}\left(\frac{D}{\sigma}\right)\right]^{-1},$

as claimed in (18).

###  -G Proof of Corollary 1

Define $\Psi^{\mathsf{SGD}}_{x}(w)=w-\eta\nabla\ell(w,x)$ for
$x\in{\mathcal{X}}$. The PNSGD algorithm can then be expressed as

$W_{t+1}=\Pi_{\mathcal{W}}\left(\Psi^{\mathsf{SGD}}_{x_{t}}(W_{t})+\eta\sigma
Z_{t}\right).$

Applying Theorem 5, we obtain that this algorithm is $(\varepsilon,\delta)$-DP
for $\varepsilon\geq 0$ and

$\delta=\frac{1}{n}\theta_{e^{\varepsilon}}\Big{(}\frac{\psi}{\eta\sigma}\Big{)}\Big{[}1-\theta_{e^{\varepsilon}}\Big{(}\frac{D}{\eta\sigma}\Big{)}\Big{]}^{-1},$
(35)

where

$\psi=\sup_{x_{1},x_{2}\in{\mathcal{X}}}\sup_{w\in{\mathcal{W}}}\|\Psi^{\mathsf{SGD}}_{x_{1}}(w)-\Psi^{\mathsf{SGD}}_{x_{2}}(w)\|,$

and
$D=\max_{t\in[n]}\mathsf{dia}\big{(}\Psi^{\mathsf{SGD}}_{x_{t}}({\mathcal{W}}))$.
Note that

$\displaystyle\|\Psi^{\mathsf{SGD}}_{x_{1}}(w)-\Psi^{\mathsf{SGD}}_{x_{2}}(w)\|$
$\displaystyle=\eta\|\nabla\ell(w,x_{1})-\nabla\ell(w,x_{2})\|$
$\displaystyle\leq\eta\left(\|\nabla\ell(w,x_{1})\|+\|\nabla\ell(w,x_{2})\|\right)$
$\displaystyle\leq 2\eta L,$ (36)

and thus

$\psi\leq 2\eta L.$ (37)

We can also write for each $t\in[n]$

$\displaystyle\mathsf{dia}\big{(}\Psi^{\mathsf{SGD}}_{x_{t}}({\mathcal{W}}))$
$\displaystyle=\sup_{w_{1},w_{2}\in{\mathcal{W}}}\|\Psi^{\mathsf{SGD}}_{x_{t}}(w_{1})-\Psi^{\mathsf{SGD}}_{x_{t}}(w_{2})\|$
$\displaystyle=\sup_{w_{1},w_{2}\in{\mathcal{W}}}\|w_{1}-\eta\nabla\ell(w_{1},x_{t})-w_{2}+\eta\nabla\ell(w_{2},x_{t})\|$
$\displaystyle\leq\|w_{1}-w_{2}\|+\eta\|\nabla\ell(w_{1},x_{t})-\nabla\ell(w_{2},x_{t})\|$
$\displaystyle\leq 1+2\eta L,$ (38)

implying

$D\leq 1+2\eta L$ (39)

Plugging (37) and (39) into (35), we obtain the desired result.

###  -H Missing proof of Section V

We first show that if $w\mapsto f(w)$ is convex and $\beta$-smooth on
${\mathcal{W}}$, then $G(w)\coloneqq w-\eta\nabla f(w)$ is $1$-Lipschitz for
$\eta\leq\frac{2}{\beta}$. To do so, we write for any
$w_{1},w_{2}\in{\mathcal{W}}$

$\displaystyle\|G(w_{1})-G(w_{2})\|^{2}$
$\displaystyle=\|w_{1}-w_{2}+\eta\nabla f(w_{2})-\eta\nabla f(w_{1})\|^{2}$
$\displaystyle=\|w_{1}-w_{2}\|^{2}+\eta^{2}\|\nabla f(w_{1})-\nabla
f(w_{2})\|^{2}-2\eta\langle\nabla f(w_{1})-\nabla f(w_{2}),w_{1}-w_{2}\rangle$
$\displaystyle\leq\|w_{1}-w_{2}\|^{2}+\eta\Big{(}\eta-\frac{2}{\beta}\Big{)}\|\nabla
f(w_{1})-\nabla f(w_{2})\|^{2}$ (40) $\displaystyle\leq\|w_{1}-w_{2}\|^{2},$
(41)

where the inequality in (40) follows from [94, Lemma 3.11] that states
$\langle\nabla f(w_{1})-\nabla
f(w_{2}),w_{1}-w_{2}\rangle\geq\frac{1}{\beta}\|\nabla f(w_{1})-\nabla
f(w_{2})\|^{2}$.

Replacing $f(w)$ with $\ell(w,x)$, we obtain that
$w\mapsto\Psi^{\mathsf{SGD}}_{x}(w)$ is $1$-Lipschitz for all
$x\in{\mathcal{X}}$. To obtain (20), we modify (38) in the proof of Corollary
1 as follows

$\displaystyle
D=\max_{t\in[n]}\mathsf{dia}\big{(}\Psi^{\mathsf{SGD}}_{x_{t}}({\mathcal{W}}))$
$\displaystyle=\sup_{w_{1},w_{2}\in{\mathcal{W}}}\|\Psi^{\mathsf{SGD}}_{x_{t}}(w_{1})-\Psi^{\mathsf{SGD}}_{x_{t}}(w_{2})\|\leq
1.$ (42)

Plugging this and (37) into (35), we obtain (20).

###  -I Proof of Proposition 3

For ease of notation, let $\displaystyle w^{\ast}\in\mathop{\rm
arg\,min}_{w\in{\mathcal{W}}}{\mathsf{f}}(w)$ and
$\tilde{D}=\textnormal{dia}({\mathcal{W}})$. Since $T$ is uniformly
distributed on $[n]$,

${\mathbb{E}}\left[{\mathsf{f}}(W_{T})\mid
W_{1},\ldots,W_{n}\right]=\frac{1}{n}\sum_{t=1}^{n}{\mathbb{E}}[{\mathsf{f}}(W_{t})\mid
W_{1},\ldots,W_{n}].$

Therefore, we have that

${\mathbb{E}}[{\mathsf{f}}(W_{T})]-\inf_{w\in{\mathcal{W}}}{\mathsf{f}}(w)={\mathbb{E}}\left[\frac{1}{n}\sum_{t=1}^{n}\big{\\{}{\mathsf{f}}(W_{t})-{\mathsf{f}}(w^{\ast})\big{\\}}\right].$

Since ${\mathsf{F}}$ is a family of convex functions, the function
${\mathsf{f}}(w)={\mathbb{E}}[{\mathsf{f}}_{t}(w)]$ is convex. In particular,
it follows that

${\mathbb{E}}[{\mathsf{f}}(W_{T})]-\inf_{w\in{\mathcal{W}}}{\mathsf{f}}(w)\leq{\mathbb{E}}\left[\frac{1}{n}\sum_{t=1}^{n}\langle\nabla{\mathsf{f}}(W_{t}),W_{t}-w^{\ast}\rangle\right].$
(43)

Define

$G_{t}\coloneqq\nabla{\mathsf{f}}_{t}(W_{t})-\sigma_{t}Z_{t}.$

Recall that ${\mathsf{f}}_{t}$ and $Z_{t}$ are independent of $W_{t}$. Hence,
by differentiation under the integral sign,

${\mathbb{E}}\left[G_{t}\mid W_{t}\right]=\nabla{\mathsf{f}}(W_{t}).$

As a consequence, we obtain that

$\displaystyle{\mathbb{E}}[\langle G_{t},W_{t}-w^{\ast}\rangle]$
$\displaystyle={\mathbb{E}}\left[\langle{\mathbb{E}}[G_{t}\mid
W_{t}],W_{t}-w^{\ast}\rangle\right]$
$\displaystyle={\mathbb{E}}\left[\langle\nabla{\mathsf{f}}(W_{t}),W_{t}-w^{\ast}\rangle\right].$

Therefore, (43) becomes

${\mathbb{E}}[{\mathsf{f}}(W_{T})]-\inf_{w\in{\mathcal{W}}}{\mathsf{f}}(w)\leq\frac{1}{n}\sum_{t=1}^{n}{\mathbb{E}}[\langle
G_{t},W_{t}-w^{\ast}\rangle].$ (44)

Recall that, for every $w\in\mathbb{R}^{d}$ and every $w_{0}\in{\mathcal{W}}$,

$\lVert\Pi_{{\mathcal{W}}}(w)-w_{0}\rVert\leq\lVert w-w_{0}\rVert.$

Thus, the update rule in (24) and the definition of $G_{t}$ imply that

$\displaystyle\lVert W_{t+1}-w^{\ast}\rVert^{2}$ $\displaystyle\leq\lVert
W_{t}-\eta_{t}G_{t}-w^{\ast}\rVert^{2}$ $\displaystyle=\lVert
W_{t}-w^{\ast}\rVert^{2}+\eta_{t}^{2}\lVert G_{t}\rVert^{2}-2\eta_{t}\langle
G_{t},W_{t}-w^{\ast}\rangle.$

A straightforward manipulation shows that

${\mathbb{E}}[\langle
G_{t},W_{t}-w^{\ast}\rangle]\leq{\mathbb{E}}\left[\frac{\lVert
W_{t}-w^{\ast}\rVert^{2}-\lVert
W_{t+1}-w^{\ast}\rVert^{2}}{2\eta_{t}}\right]+\frac{\eta_{t}(L^{2}+\sigma_{t}^{2}d)}{2},$

where the last inequality uses the fact that

${\mathbb{E}}[\lVert G_{t}\rVert^{2}]\leq L^{2}+\sigma_{t}^{2}d.$

Therefore, (44) becomes

$\displaystyle{\mathbb{E}}[{\mathsf{f}}(W_{T})]-\inf_{w\in{\mathcal{W}}}{\mathsf{f}}(w)$
$\displaystyle\leq\frac{1}{n}\sum_{t=1}^{n}\left\\{{\mathbb{E}}\left[\frac{\lVert
W_{t}-w^{\ast}\rVert^{2}-\lVert
W_{t+1}-w^{\ast}\rVert^{2}}{2\eta_{t}}\right]+\frac{\eta_{t}(L^{2}+\sigma_{t}^{2}d)}{2}\right\\}$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{n}\frac{{\mathbb{E}}[\lVert
W_{t}-w^{\ast}\rVert^{2}]}{2}\left(\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}\right)+\frac{1}{n}\sum_{t=1}^{n}\frac{\eta_{t}(L^{2}+\sigma_{t}^{2}d)}{2},$

where for ease of notation we define $1/\eta_{0}=0$. Since
$\displaystyle\eta_{t}=\frac{\tilde{D}}{L\sqrt{t}}$ and $\lVert
W_{t}-w^{\ast}\rVert\leq\tilde{D}$ for every $t$, we have that

${\mathbb{E}}[{\mathsf{f}}(W_{T})]-\inf_{w\in{\mathcal{W}}}{\mathsf{f}}(w)\leq\frac{L\tilde{D}}{2\sqrt{n}}+\frac{1}{n}\sum_{t=1}^{n}\frac{\eta_{t}(L^{2}+\sigma_{t}^{2}d)}{2},$

Finally, by the inequality $\displaystyle\sum_{t=1}^{n}\frac{1}{\sqrt{t}}\leq
2\sqrt{n}$, we conclude that

${\mathbb{E}}[{\mathsf{f}}(W_{T})]-\inf_{w\in{\mathcal{W}}}{\mathsf{f}}(w)\leq\frac{L\tilde{D}}{2\sqrt{n}}+\frac{L\tilde{D}}{\sqrt{n}}+\frac{d}{2n}\sum_{t=1}^{n}\eta_{t}\sigma_{t}^{2},$

as required.