# Differential Privacy Guarantees for
Stochastic Gradient Langevin Dynamics

Théo Ryffel  Francis Bach  David Pointcheval

###### Abstract

We analyse the privacy leakage of noisy stochastic gradient descent by
modeling Rényi divergence dynamics with Langevin diffusions. Inspired by
recent work on non-stochastic algorithms, we derive similar desirable
properties in the stochastic setting. In particular, we prove that the privacy
loss converges exponentially fast for smooth and strongly convex objectives
under constant step size, which is a significant improvement over previous DP-
SGD analyses. We also extend our analysis to arbitrary sequences of varying
step sizes and derive new utility bounds. Last, we propose an implementation
and our experiments show the practical utility of our approach compared to
classical DP-SGD libraries.

Machine Learning, Differential Privacy, Langevin Diffusion, Rényi, ICML

##  1 Introduction

Differential privacy (Dwork et al., 2014) for machine learning is a promising
approach to reduce exposure of training datasets when releasing machine
learning models. The privacy leakage from these models can be quantified using
Rényi differential privacy (Mironov, 2017) which models it through the
divergence of the distributions of two models trained on datasets that only
differ in one item. The intuition behind is that a model whose behavior is
sensitive to the presence or absence of a single individual is likely to
memorize information about specific individuals, which can then be uncovered
using several types of attacks like membership inference attacks (Shokri et
al., 2017).

The most standard approaches to training neural networks with differential
privacy are derived from Abadi et al. (2016)’s method of differentially
private stochastic gradient descent (DP-SGD). DP-SGD is an attractive method
as it closely mimics classic SGD training of neural networks, and applies to
almost all architectures. It therefore enjoys easy adoption from data
scientists and has been integrated in popular libraries like Opacus
(Yousefpour et al., 2021). Differential privacy of the whole training
mechanism is computed using the strong composition theorem (Dwork et al.,
2010), which states that the privacy leakage modeled through standard
$(\epsilon,\delta)$-differential privacy grows approximately in $\sqrt{K}$ for
high privacy regimes, where $K$ is the number of iterations. This is a strong
limitation of DP-SGD in real world applications since training for a large
number of iterations would lead to a prohibitive privacy bound.

Recently, Chourasia et al. (2021) have proposed a novel analysis of the
differential privacy dynamics of Langevin diffusion, resulting in a new
differentially private noisy gradient descent algorithm (DP-GLD). This method
notably guarantees that under strongly convex and smooth objectives, the
privacy leakage can be bounded by a constant, which allows for an unlimited
number of model updates. The key difference with DP-SGD is that the model is
assumed to be hidden during training and released only once the training is
over. This is a setting that we typically encounter while training a model
using multi-party computation (Knott et al., 2021; Wagh et al., 2021; Ryffel
et al., 2022) where only the final version of the model is visible. However,
the algorithm and the privacy analysis provided by Chourasia et al. (2021)
only addresses full gradient descent (DP-GLD) which is impractical for large
datasets and makes its adoption by data scientists or standard differential
privacy libraries less probable.

Contributions. We provide a _stochastic_ version of the noisy gradient descent
algorithm (DP-SGLD) and build a privacy analysis based on Langevin diffusion.
We prove that DP-SGLD achieves similar privacy and utility guarantees than DP-
GLD, including exponential convergence of the privacy bound, and we extend the
analysis to the case where the step size is not constant. More specifically:

  * •

We introduce DP-SGLD, a stochastic version of the DP-GLD algorithm studied by
Chourasia et al. (2021), and we show that it achieves the same privacy
guarantees including exponentially fast convergence.

  * •

We show that DP-SGLD achieves similar utility than DP-GLD up to a term due to
using stochastic estimates of the gradient. We also relax assumptions on the
step size $\eta$ in utility theorems of Chourasia et al. (2021) to only verify
$\eta\leq\frac{1}{2\beta}$ instead of $\eta\leq\frac{\lambda}{2\beta^{2}}$,
where $\beta$ is the smoothness constant and $\lambda$ the strong-convexity
parameter, thus obtaining the classical scaling from convex optimization.

  * •

We extend our analysis of DP-SGLD to non-constant step sizes and derive
utility bounds when the step size is parametrized as
$\eta_{k}=\frac{1}{2\beta+\lambda k/2}$ and removes the term due to stochastic
training.

  * •

Last, we provide an implementation of DP-SGLD111The code is provided in the
supplementary material. and an experimental evaluation where we train
differentially private logistic regressions on several datasets. We show that
DP-SGLD achieves higher experimental accuracy than DP-SGD on these tasks, and
that it almost closes the gap with non-private training. We also show that
standard DP-SGD does not benefit from training deeper networks on these tasks,
which aligns with the conclusions drawn by Tramèr & Boneh (2021).

Note that our algorithm ends up being similar to the one of Welling & Teh
(2011), except that we do not try to construct samples from the posterior
distribution but instead to derive privacy guarantees.

##  2 Preliminaries

Let us first recall the standard definition of
$(\epsilon,\delta)$-differential privacy, as introduced by Dwork et al. (2014)
:

######  Definition 2.1 ($(\epsilon,\delta)$-differential privacy).

A randomized algorithm $\mathcal{A}:\mathcal{D}\mapsto\mathbb{R}^{d}$
satisfies $(\epsilon,\delta)$-differential privacy if for any neighboring
datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$, i.e., datasets that only
differ in one item, and any subset $S\in\mathbb{R}^{d}$, the distribution of
$\mathcal{A}$ satisfies:

$\mathrm{P}[\mathcal{A}(\mathcal{D})]\leq
e^{\epsilon}\mathrm{P}[\mathcal{A}(\mathcal{D}^{\prime})]+\delta.$

An alternative notion, coined as _Rényi differential privacy_ has been
proposed by Mironov (2017), which is more suited to studying composition
mechanisms, but can be converted back to standard
$(\epsilon,\delta)$-differential privacy.

######  Definition 2.2 (Rényi differential privacy).

A randomized algorithm $\mathcal{A}:\mathcal{D}\mapsto\mathbb{R}^{d}$
satisfies $(\alpha,\varepsilon)$-Rényi differential privacy if for any
neighboring datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$, the $\alpha$
Rényi divergence satisfies
$R_{\alpha}(\mathcal{A}(\mathcal{D})\;||\;\mathcal{A}(\mathcal{D}^{\prime}))\leq\varepsilon$,
where:

$R_{\alpha}(\mathcal{A}(\mathcal{D})\;||\;\mathcal{A}(\mathcal{D}^{\prime}))=\dfrac{1}{\alpha\\!-\\!1}\log\operatorname*{\mathbb{E}}_{\theta\sim\mathcal{A}(\mathcal{D}^{\prime})}\\!\left[\\!\left(\\!\dfrac{\mu_{\mathcal{A}(\mathcal{D})}(\theta)}{\mu_{\mathcal{A}(\mathcal{D}^{\prime})}(\theta)}\\!\right)^{\alpha}\right],$

and where $\mu_{\mathcal{A}}$ denotes the density $\mathcal{A}$.

Conversion from Rényi differential privacy to $(\epsilon,\delta)$-differential
privacy is given by the following proposition:

######  Proposition 2.1 (From Rényi to $(\epsilon,\delta)$-differential
privacy (Mironov, 2017)).

If $\mathcal{A}$ satisfies $(\alpha,\varepsilon)$-Rényi differential privacy,
it also satisfies $(\epsilon,\delta)$-differential privacy for any
$0<\delta<1$ with

$\epsilon=\varepsilon+\dfrac{\log(1/\delta)}{\alpha-1}$

##  3 Privacy analysis of noisy stochastic gradient descent

We use the same notations as Chourasia et al. (2021). Let
$\mathcal{D}=(\mathbf{x}_{1},\dots,\mathbf{x}_{n})$ be a dataset of size $n$,
with $\mathbf{x}_{i}\in\mathbb{R}^{p}$. Let $\ell(\theta,\mathbf{x})$ be the
loss function of a learning algorithm parametrized by $\theta\in\mathcal{C}$
on an input $x$, where $\mathcal{C}$ is a closed convex set of
$\mathbb{R}^{d}$. $\Pi_{\mathcal{C}}$ denotes the orthogonal projection onto
$\mathcal{C}$. We denote by $\mathcal{L}_{\mathcal{D}}(\theta)$ the global
empirical loss of the model, and by $\mathcal{L}_{\mathcal{B}_{k}}(\theta)$
the estimated empirical loss computed on the batch $\mathcal{B}_{k}$ of size
$\left|\mathcal{B}_{k}\right|=m$.

$\\!\\!\\!\mathcal{L}_{\mathcal{D}}(\theta)=\frac{1}{n}\sum_{\mathbf{x}\in\mathcal{D}}\ell(\theta,\mathbf{x})\;\;\>\>\>\>\
\
\mathcal{L}_{\mathcal{B}_{k}}(\theta)=\frac{1}{m}\sum_{\mathbf{x}\in\mathcal{B}_{k}}\ell(\theta,\mathbf{x}).$

Algorithm 1 $\mathcal{A}_{\mathrm{DP-SGLD}}$: Noisy Stochastic Gradient
Descent

Dataset $\mathcal{D}=(\mathbf{x}_{1},\dots,\mathbf{x}_{n})$, loss function
$\ell$, step size $\\{\eta_{k}\\}_{k\geq 0}$, noise variance $\sigma^{2}$and
initial parameter $\theta_{0}\in\mathcal{C}$$k=0,\dots,K-1$Sample batch
$\mathcal{B}_{k}$from $\mathcal{D}$with replacement Compute
$\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})=\frac{1}{m}\sum_{\mathbf{x}\in\mathcal{B}_{k}}\nabla\ell(\theta_{k},\mathbf{x})$$\theta_{k+1}=\Pi_{\mathcal{C}}(\theta_{k}-\eta_{k}\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})+\sqrt{2\eta_{k}}\;\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d}))$$\theta_{K}$

We analyse the privacy loss of the DP-SGLD algorithm given in Algorithm 1
which implements noisy stochastic gradient descent.

Let $\theta_{k}$ and $\theta^{\prime}_{k}$ denote the parameters at the $k$-th
iteration of $\mathcal{A}_{\mathrm{DP-SGLD}}$ on neighboring datasets
$\mathcal{D}$ and $\mathcal{D}^{\prime}$, respectively. Stating that
$\mathcal{D}$ and $\mathcal{D}^{\prime}$ are _neighbors_ means that they only
differ by one $\mathbf{x}_{i_{0}}$, for some index $i_{0}$. Batch
$\mathcal{B}_{k}$ is sampled with replacement from $\mathcal{D}$, meaning that
a subset of size $m$ is chosen at random from $\mathcal{D}$ and then replaced
at the end of the $k$-th iteration. Hence, $\mathbf{x}_{i_{0}}$ can only
appear once in $\mathcal{B}_{k}$, with probability $m/n$. We denote by
$\Theta_{t_{k}}$ and $\Theta^{\prime}_{t_{k}}$ the corresponding random
variables associated with $\theta_{k}$ and $\theta^{\prime}_{k}$. We abuse
notation to also denote their probability density functions by
$\Theta_{t_{k}}$ and $\Theta^{\prime}_{t_{k}}$. Our objective is to model and
analyze the dynamics of differential privacy of this algorithm and to compare
it to the ones of the DP-GLD algorithm described by Chourasia et al. (2021),
which implements full noisy gradient descent. To this aim, we use the
theoretical framework and constructions they provide to analyze the privacy
loss of releasing the output $\theta_{K}$ of the algorithm, assuming private
internal states (i.e., $\theta_{1},\dots,\theta_{K-1}$).

More precisely, the proof strategy goes as follows: we first model the
transition from any step $k$ to the next step $k+1$ in DP-SGLD using a
diffusion process and derive the evolution equation of the distribution
$\Theta_{t}$ during $k<t<k+1$. We use the theoretical results of Chourasia et
al. (2021) to establish the evolution of the Rényi divergence of two
distributions based on neighboring datasets during $k<t<k+1$. Finally, we
compute a bound on the global Rényi divergence for the $K$-step DP-SGLD
process.

###  3.1 Tracing diffusion for DP-SGLD

To analyze the privacy loss of DP-SGLD, which is a discrete-time stochastic
process, we first interpolate each discrete update from $\theta_{k}$ to
$\theta_{k+1}$ with a piecewise continuously differentiable diffusion process.
Given step size $\\{\eta_{k}\\}_{k\geq 0}$, variance noise $\sigma^{2}$ and
initial parameter vector $\theta_{0}$, the $k$-th discrete update in Algorithm
1 is:

$\begin{array}[]{l}\theta_{k+1}=\Pi_{\mathcal{C}}(\theta_{k}-\eta_{k}\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})+\sqrt{2\eta_{k}\sigma^{2}}\mathbf{Z}_{K})\\\\[2.0pt]
\mathrm{with}\>\mathbf{Z}_{k}\sim\mathcal{N}(0,\mathbf{I}_{d}),\mathcal{B}_{k}\overset{{}_{\$}}{\leftarrow}\mathcal{D},\end{array}$
(1)

where $\mathcal{B}_{k}\overset{{}_{\$}}{\leftarrow}\mathcal{D}$ means that
batch $\mathcal{B}_{k}$ is sampled with replacement from $\mathcal{D}$, and
where the loss $\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})$ is the estimated
empirical loss function over batch $\mathcal{B}_{k}$. This discrete jump can
be interpolated with the following random process $\\{\Theta_{t}\\}_{t_{k}\leq
t\leq t_{k+1}}$, where $t_{k}=\sum_{i=1}^{k}\eta_{i}$,

$\left\\{\begin{matrix}[l]\Theta_{t_{k}}=\theta_{k}\\\ \Theta_{t_{k}+\Delta
t}-\left(\Theta_{t_{k}}-\eta_{k}\sum_{i=1,i\neq
i_{0}}^{m}\dfrac{\nabla\ell(\Theta_{t_{k}},\mathbf{x}_{i})}{m}\right)\\\
\qquad=-\Delta
t\dfrac{\nabla\ell(\Theta_{t_{k}},\mathbf{x}_{i_{0}})}{m}+\sqrt{2\Delta
t\,\sigma^{2}}\mathbf{Z}_{k},\>0<\Delta t<\eta_{k}\\\\[5.0pt]
\Theta_{t_{k+1}}=\Pi_{\mathcal{C}}(\lim_{\Delta
t\rightarrow\eta_{k}}\Theta_{t_{k}+\Delta t}),\>0<\Delta
t<\eta_{k},\end{matrix}\right.$ (2)

where $\mathbf{Z}_{k}\sim\mathcal{N}(0,\mathbf{I}_{d})$, $\mathcal{B}_{k}$ is
sampled with replacement from $\mathcal{D}$, $i_{0}$ refers to the index in
$\mathcal{B}_{k}$ of the data item which differs between $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ if it is part of $\mathcal{B}_{k}$, otherwise $i_{0}$
is chosen at random.

We can compute from (2) $\lim_{\Delta
t\rightarrow\eta_{k}}\Theta_{t_{k}+\Delta
t}=\theta_{k}-\eta_{k}\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})+\sqrt{2\eta_{k}\sigma^{2}}\mathbf{Z}_{K}$.
Therefore by the update equation (1), we see that the random variable
$\Theta_{t_{k+1}}=\Pi_{\mathcal{C}}(\lim_{\Delta
t\rightarrow\eta_{k}}\Theta_{t_{k}+\Delta t})$ has the same distribution as
the parameter $\theta_{k+1}$ at $k+1^{\mathrm{th}}$ step of DP-SGLD.

We now differentiate (2) over time $t$ for
$\\{\Theta_{t}\\}_{t_{k}<t<t_{k+1}}$ and we derive the following stochastic
differential equation.

$d\Theta_{t}=-\dfrac{\nabla\ell(\Theta_{t_{k}},\mathbf{x}_{i_{0}})}{m}dt+\sqrt{2\sigma^{2}}d\mathbf{W}_{t},$
(3)

where $d\mathbf{W}_{t}\sim\sqrt{t}\mathcal{N}(0,\mathbf{I}_{d})$ describes the
Wiener process on $\mathbb{R}^{d}$, and $i_{0}$ is chosen as such:

$\left\\{\begin{matrix}[l]\\{\mathbf{x}_{i_{0}}\\}=\\{\mathbf{x}_{i},\mathbf{x}_{i}\in\mathcal{B}_{k},\mathbf{x}_{i}\notin\mathcal{B}_{k}^{\prime}\\}&\mathrm{if}\>\mathcal{B}_{k}\neq\mathcal{B}_{k}^{\prime}\\\
\mathbf{x}_{i_{0}}\overset{{}_{\$}}{\leftarrow}\mathcal{B}_{k}&\mathrm{if}\>\mathcal{B}_{k}=\mathcal{B}_{k}^{\prime},\end{matrix}\right.$

where we assume without loss of generality that two neighboring batches
$\mathcal{B}_{k}$ and $\mathcal{B}_{k}^{\prime}$ are indexed so as to be equal
on all indices but one.

This shows that $\\{\Theta_{t}\\}_{t_{k}<t<t_{k+1}}$ is a diffusion process
and we repeat the construction for $k=0,1,\dots$ to define a piecewise
continuous diffusion process $\\{\Theta_{t}\\}_{t\geq 0}$ whose distribution
at time $t=t_{k}$ is consistent with $\theta_{k}$. We refer to this process as
the tracing diffusion for DP-SGLD.

######  Definition 3.1 (Coupled tracing diffusions (Chourasia et al., 2021)).

Let $\Theta_{0}=\Theta^{\prime}_{0}$ be two identically distributed random
variables. We refer to the stochastic processes $\\{\Theta_{t}\\}_{t\geq 0}$
and $\\{\Theta^{\prime}_{t}\\}_{t\geq 0}$ defined by (2) as coupled tracing
diffusions processes for DP-SGLD under loss function $\ell(\theta,\mathbf{x})$
on neighboring datasets $\mathcal{D}$, $\mathcal{D}^{\prime}$ differing in
$i_{0}$-th data point.

The Rényi divergence $R_{\alpha}(\Theta_{t_{K}}\;||\;\Theta^{\prime}_{t_{K}})$
reflects the Rényi privacy loss of Algorithm 1 with $K$ steps. Conditioned on
observing $\theta_{k}$ and on sampling $\mathcal{B}_{k}$ from $\mathcal{D}$,
the process $\\{\Theta_{t}\\}_{t_{k}<t<t_{k+1}}$ is a Langevin diffusion along
a constant vector field $\nabla\ell(\theta_{k},\mathbf{x}_{i_{0}})$ for
duration $\eta_{k}$. Therefore, the conditional probability distribution
$p_{t|t_{k}}(\theta|\theta_{k})$ follows the following Fokker-Planck equation,
where the notation $p_{t|t^{\prime}}(\theta|\theta^{\prime})$ represents the
conditional probability density function
$p(\Theta_{t}=\theta|\Theta_{t^{\prime}}=\theta^{\prime})$:

$\displaystyle\dfrac{\partial p_{t|t_{k}}(\theta|\theta_{k})}{\partial
t}\\!=\\!\nabla\\!\\!\cdot\\!\\!\left(\\!p_{t|t_{k}}(\theta|\theta_{k})\dfrac{\nabla\ell(\theta_{k},\mathbf{x}_{i_{0}})}{m}\\!\right)\\!+\\!\sigma^{2}\Delta
p_{t|t_{k}}(\theta|\theta_{k}).$

By taking expectations over the distribution $p_{t_{k}}(\theta_{k})$ on both
sides, we get the partial differential equation that models the evolution of
probability distribution $p_{t}(\theta)$ in the tracing diffusion.

######  Lemma 3.1.

For the SDE (3), the equivalent Fokker-Planck equation at time
$t_{k}<t<t_{k+1}$ is

$\displaystyle\dfrac{\partial p_{t}(\theta)}{\partial
t}\\!=\\!\nabla\\!\\!\cdot\\!\\!\left(\\!p_{t}(\theta)\\!\\!\operatorname*{\mathbb{E}}_{\theta_{k}\sim
p_{t_{k}|t}}\\!\\!\left[\dfrac{\nabla\ell(\theta_{k},\mathbf{x}_{i_{0}})}{m}|\theta,\mathcal{B}_{k}\right]\\!\right)\\!+\\!\sigma^{2}\Delta
p_{t}(\theta).$

Using this distribution evolution equation, we model the privacy dynamics in
the tracing diffusion process. This process is similar to Langevin diffusion
under conditionally expected loss function
$\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta)=\operatorname*{\mathbb{E}}_{\theta_{k}\sim
p_{t_{k}|t}}\left[\dfrac{\nabla\ell(\theta_{k},\mathbf{x}_{i_{0}})}{m}\Big{|}\theta,\mathcal{B}_{k}\right]$.

###  3.2 Privacy erosion in tracing (Langevin) diffusion

The analysis of the privacy erosion in tracing langevin diffusion is detailed
by Chourasia et al. (2021) but we provide here the key results that we will
apply to our algorithm. Privacy erosion refers to the continuous increase of
the privacy loss over time as more data is accessed to compute the gradient of
the loss in the update equation.

Consider a Langevin diffusion process modelled through the following Fokker-
Planck equation:

$\dfrac{\partial p_{t}(\theta)}{\partial
t}=\nabla\cdot(p_{t}(\theta)\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta))+\sigma^{2}\Delta
p_{t}(\theta).$

######  Definition 3.2 (Log-Sobolev inequality (Gross, 1975)).

The distribution of a variable $\Theta$ satisfies the Log-Sobolev Inequality
for a constant $c$, or is $c$-LSI, if for all functions
$f:\mathbb{R}^{d}\to\mathbb{R}$ with continuous $\nabla f$ and
$\operatorname*{\mathbb{E}}[f(\Theta)^{2}]<\infty$, it satisfies

$\displaystyle\\!\operatorname*{\mathbb{E}}[f(\Theta)^{2}\\!\log
f(\Theta)^{2}]\\!-\\!\operatorname*{\mathbb{E}}[f(\Theta)^{2}]\log\operatorname*{\mathbb{E}}[f(\Theta)^{2}]\\!\leq\\!\dfrac{2}{c}\\!\operatorname*{\mathbb{E}}[\left\|\nabla
f(\Theta)\right\|^{2}_{2}].$

######  Lemma 3.2 (Dynamics for Rényi privacy loss under c-LSI (Chourasia et
al., 2021)).

Assuming that $\Theta$ is $c$-LSI and $S_{g}$ is the sensitivity of the loss
gradient, the dynamics of the Rényi privacy loss can be modelled as such,
where $R(\alpha,t)$ represents the $\alpha$ Rényi divergence
$R_{\alpha}(\Theta_{t}\;||\;\Theta^{\prime}_{t})$:

$\frac{\partial R(\alpha,t)}{\partial t}\\!\leq\\!\frac{1}{\gamma}\frac{\alpha
S_{g}^{2}}{4\sigma^{2}}\\!-\\!2(1\\!-\\!\gamma)\sigma^{2}c\left[\frac{R(\alpha,t)}{\alpha}\\!+\\!(\alpha\\!-\\!1)\frac{\partial
R(\alpha,t)}{\partial\alpha}\right],$ (4)

for some $\gamma$ which can be arbitrarily fixed.

The initial privacy loss satisfies $R(\alpha,0)=0$ as
$\Theta_{0}=\Theta^{\prime}_{0}$. The solution $R(\alpha,t)$ for this equation
increases with time $t\geq 0$, which models the erosion of Rényi privacy loss
in Langevin diffusion. Intuitively, the $c$-LSI condition which provides the
negative dependence $\frac{\partial R(\alpha,t)}{\partial t}$ with respect to
$R(\alpha,t)$, can be interpreted as a sufficient condition to ensure that the
the Rényi privacy loss is bounded, which is further formalized in Theorem 3.3.

###  3.3 Privacy guarantee for DP-SGLD

We now extend these results to the tracing diffusion for DP-SGLD. In addition,
we do not make the assumption that the step size is constant and use a
sequence $\\{\eta_{k}\\}_{k\geq 0}$ instead. We first bound the gradient
sensitivity of the conditionally expected loss
$\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta)=\operatorname*{\mathbb{E}}_{\theta_{k}\sim
p_{t_{k}|t}}\left[\frac{\nabla\ell(\theta_{k},\mathbf{x}_{i_{0}})}{m}|\theta,\mathcal{B}_{k}\right]$.

[normal, end, restate, one big link translated=The proof is provided in
Appendix on page, category=lemma:sensitivity]lemma[Sensitivity]Let
$\ell(\theta,\mathbf{x})$ be an $L$-Lipschitz loss function on closed convex
set $\mathcal{C}$, then for coupled tracing diffusions
$\\{\Theta_{t}\\}_{t\geq 0}$ and $\\{\Theta^{\prime}_{t}\\}_{t\geq 0}$ for DP-
SGLD on neighboring datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$, and
noise variance $\sigma^{2}$, the gradient sensitivity of conditionally
expected loss
$\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta)=\operatorname*{\mathbb{E}}_{\theta_{k}\sim
p_{t_{k}|t}}\left[\dfrac{\nabla\ell(\theta_{k},\mathbf{x}_{i_{0}})}{m}|\theta,\mathcal{B}_{k}\right]$
is bounded by:

$\displaystyle\left\|\operatorname*{\mathbb{E}}_{\theta_{k}\sim
p_{t_{k}|t}}\\!\\!\left[\dfrac{\nabla\ell(\theta_{k},\mathbf{x}_{i_{0}})}{m}|\theta,\mathcal{B}_{k}\\!\right]\\!-\\!\\!\\!\operatorname*{\mathbb{E}}_{\theta^{\prime}_{k}\sim
p^{\prime}_{t_{k}|t}}\\!\\!\left[\dfrac{\nabla\ell(\theta^{\prime}_{k},\mathbf{x}^{\prime}_{i_{0}})}{m}|\theta,\mathcal{B}_{k}\\!\right]\right\|_{2}\\!\\!\\!\leq\dfrac{2L}{n},$

where $n$ is the size of the dataset $\mathcal{D}$ and $\mathcal{D}^{\prime}$,
and $m$ is the size of the batch $\mathcal{B}_{k}$ and
$\mathcal{B}_{k}^{\prime}$.

[]We first distinguish on the events
$\mathcal{B}_{k}=\mathcal{B}_{k}^{\prime}$ and
$\mathcal{B}_{k}\neq\mathcal{B}_{k}^{\prime}$ and then use the triangle
inequality:

$\begin{array}[]{l}\Bigg{\|}\operatorname*{\mathbb{E}}_{\theta_{k}\sim
p_{t_{k}|t}}\left[\dfrac{\nabla\ell(\theta_{k};\mathbf{x}_{i_{o}})}{m}|\theta,\mathcal{B}_{k}\right]\\\
\qquad\qquad\qquad-\;\operatorname*{\mathbb{E}}_{\theta^{\prime}_{k}\sim
p^{\prime}_{t_{k}|t}}\left[\dfrac{\nabla\ell(\theta^{\prime}_{k};\mathbf{x^{\prime}}_{i_{o}})}{m}|\theta,\mathcal{B}_{k}\right]\Bigg{\|}_{2}\\\
=\mathbb{P}[\mathcal{B}_{k}\neq\mathcal{B}_{k}^{\prime}]\;\cdot\Bigg{\|}\operatorname*{\mathbb{E}}\bigg{[}\operatorname*{\mathbb{E}}\limits_{\theta_{k}\sim
p_{t_{k}|t}}\left[\dfrac{\nabla\ell(\theta_{k};\mathbf{x}_{i_{o}})}{m}|\theta\right]\\\
\qquad\qquad\qquad-\\!\\!\\!\operatorname*{\mathbb{E}}\limits_{\theta^{\prime}_{k}\sim
p^{\prime}_{t_{k}|t}}\left[\dfrac{\nabla\ell(\theta^{\prime}_{k};\mathbf{x^{\prime}}_{i_{o}})}{m}|\theta\right]|\,\mathcal{B}_{k}\\!\neq\\!\mathcal{B}_{k}^{\prime}\bigg{]}\Bigg{\|}_{2}\\\
\leq\dfrac{m}{n}\cdot\dfrac{2L}{m}\leq\dfrac{2L}{n}\end{array}$

We now substitute the sensitivity $S_{g}$ with $\frac{2L}{n}$ in equation (4)
modelling the Rényi privacy loss dynamics of tracing diffusion at $t_{k}\leq
t<t_{k+1}$ under $c$-LSI condition:

$\frac{\partial R(\alpha,t)}{\partial t}\\!\leq\\!\frac{1}{\gamma}\frac{\alpha
L^{2}}{n^{2}\sigma^{2}}\\!-\\!2(1\\!-\\!\gamma)\sigma^{2}c\left[\frac{R(\alpha,t)}{\alpha}\\!+\\!(\alpha\\!-\\!1)\frac{\partial
R(\alpha,t)}{\partial\alpha}\right].$ (5)

Following the methodology of Chourasia et al. (2021), we solve this PDE under
$\gamma=\frac{1}{2}$ and derive the RDP guarantee for the DP-SGLD algorithm.

[normal, end, restate, one big link translated=The complete proof is provided
in Appendix on page, category=th:rdp_noisysgd_clsi]theorem[RDP for DP-SGLD
under $c$-LSI] Let $\ell(\theta,\mathbf{x})$ be an $L$-Lipschitz loss function
on a closed convex set $\mathcal{C}$. Let $\\{\Theta_{t}\\}_{t\geq 0}$ be the
tracing diffusion for $\mathcal{A}_{\mathrm{DP-SGLD}}$ under loss function
$\ell(\theta,\mathbf{x})$ on dataset $\mathcal{D}$. If $\Theta_{t}$ satisfies
$c$-LSI throughout $0\leq t\leq\sum_{k=1}^{K}\eta_{k}$, then
$\mathcal{A}_{\mathrm{DP-SGLD}}$ satisfies $(\alpha,\varepsilon)$-Rényi
Differential Privacy for

$\varepsilon=\dfrac{2\alpha
L^{2}}{cn^{2}\sigma^{4}}(1-e^{-\sigma^{2}c\sum_{k=1}^{K}\eta_{k}}).$

[]At each step $k$, the Rényi privacy follows the evolution equation defined
in (5) (since it is a tracing diffusion) when $t_{k}<t<t_{k+1}$, where
$t_{k}=\sum_{i=1}^{k}\eta_{i}$:

$\dfrac{\partial R(\alpha,t)}{\partial t}\leq\dfrac{1}{\gamma}\dfrac{\alpha
L^{2}}{\sigma^{2}n^{2}}\\!-\\!2(1\\!-\\!\gamma)\sigma^{2}c\left[\dfrac{R(\alpha,t)}{\alpha}\\!+\\!(\alpha\\!-\\!1)\dfrac{\partial
R(\alpha,t)}{\partial\alpha}\right]$

Let’s $a_{1}=2(1-\gamma)\sigma^{2}c$, $a_{2}=\frac{1}{\gamma}\frac{\alpha
L^{2}}{\sigma^{2}n^{2}}$ and

$u(t,y)=\left\\{\begin{matrix}[l]\frac{R(\alpha,t)}{\alpha}-\frac{a_{2}}{a_{1}}&t_{k}<t<t_{k+1}\\\
\frac{R(\alpha,\lim_{t\to
t_{k}^{+}}t)}{\alpha}-\frac{a_{2}}{a_{1}}&t=t_{k}\end{matrix}\right.$

We can rewrite the evolution equation as such:

$\frac{\partial u}{\partial t}+a_{1}u+a_{1}\frac{\partial u}{\partial y}\leq
0\>\>,\>t_{k}<t<t_{k+1}$

with initial condition $u(t_{k},y)=\frac{R(\alpha,\lim_{t\to
t_{k}^{+}}t)}{\alpha}-\frac{a_{2}}{a_{1}}$.

Let now introduce $\tau=t$ and $z=t-\frac{1}{a_{1}}y$ and write
$v(\tau,z)=u(t,y)$. The equation now writes:

$\frac{\partial v}{\partial\tau}+a_{1}v<0$

with initial condition $v(t_{k},z)=u(t_{k},-a_{1}(z-t_{k}))$

The solution of this equation is:

$v(\tau,z)\leq v(t_{k},z)e^{-a_{1}(\tau-t_{k})}$

which also writes

$u(t,y)\leq u(t_{k},y-a_{1}(t-t_{k}))e^{-a_{1}(t-t_{k})}$

or in terms of $R(\alpha,t)$:

$R(\alpha,t)-\frac{a_{2}}{a_{1}}\alpha\leq(R(\alpha,\lim_{t\to
t_{k}^{+}})-\frac{a_{2}}{a_{1}}\alpha)e^{-a_{1}(t-t_{k})}$

for $t_{k}<t<t_{k+1}$.

Taking the limit $t\to t_{k+1}^{-}$, we have

$R(\alpha,\lim_{t\to
t_{k+1}^{-}}t)-\frac{a_{2}}{a_{1}}\alpha\leq(R(\alpha,\lim_{t\to
t_{k}^{+}}t)-\frac{a_{2}}{a_{1}}\alpha)e^{-a_{1}\eta_{k+1}}$

In addition, by the tracing diffusion process described in (2), we have

$\displaystyle\lim_{t\to
t_{k}^{+}}\Theta_{t}=\phi(\Pi_{\mathcal{C}}(\lim_{t\to t_{k}^{-}}\Theta_{t}))$
$\displaystyle\lim_{t\to
t_{k}^{+}}\Theta_{t}^{\prime}=\phi(\Pi_{\mathcal{C}}(\lim_{t\to
t_{k}^{-}}\Theta_{t}^{\prime}))$

where $\phi(\theta)=\theta-\eta\sum_{i=1,i\neq
i_{0}}^{m}\dfrac{\nabla\ell(\theta,\mathbf{x}_{i})}{m}$ is a mapping which is
the same for both processes, as the batches $\mathcal{B}_{k}$ for each
distribution only differ at most on $\mathbf{x}_{i_{0}}$. Hence, by post-
processing of Rényi divergence, we have

$R(\alpha,\lim_{t\to t_{k}^{+}}t)\leq R(\alpha,\lim_{t\to t_{k}^{-}}t)$

Combining the above two inequalities, we derive the following recursive
equation

$R(\alpha,\lim_{t\to
t_{k+1}^{-}}t)-\frac{a_{2}}{a_{1}}\alpha\leq(R(\alpha,\lim_{t\to
t_{k}^{-}})-\frac{a_{2}}{a_{1}}\alpha)e^{-a_{1}\eta_{k+1}}$

Repeating this step for $k=0,\dots,K-1$ we have

$R(\alpha,\lim_{t\to
t_{K}^{-}}t)-\frac{a_{2}}{a_{1}}\alpha\leq(R(\alpha,\lim_{t\to
0^{-}}t)-\frac{a_{2}}{a_{1}}\alpha)e^{-a_{1}t_{K}}$

where $t_{K}=\sum_{i=1}^{K}\eta_{i}$. Because coupled tracing diffusions have
the same start parameter, we have $R(\alpha,\lim_{t\to 0^{-}}t)=0$. Moreover,
since projection is a post-processing mapping we have $R(\alpha,t_{K})\leq
R(\alpha,\lim_{t\to t_{K}^{-}}t)$. Putting back the values of $a_{1}$ and
$a_{2}$ we have:

$R(\alpha,t_{K})\leq\frac{\alpha
L^{2}}{2\gamma(1-\gamma)c\sigma^{4}n^{2}}(1-e^{-2(1-\gamma)\sigma^{2}ct_{K}})$

Setting $\gamma=\frac{1}{2}$ suffices to prove the Rényi privacy loss bound in
the theorem.

_Sketch of proof_. We introduce $t_{k}=\sum_{i=1}^{k}\eta_{i}$ for $k\geq 0$.
The idea of the proof is to bound $R(\alpha,t_{K})$, the Rényi divergence
after $K$ updates in DP-SGLD, with a function of $R(\alpha,t_{0})$. This is
first done by considering the $k$-th update, and proving the following
equation for some constants $a_{1}$, $a_{2}$

$R(\alpha,\lim_{t\to
t_{k+1}^{-}}t)-\frac{a_{2}}{a_{1}}\alpha\leq(R(\alpha,\lim_{t\to
t_{k}^{+}}t)-\frac{a_{2}}{a_{1}}\alpha)e^{-a_{1}\eta_{k+1}},$

together with

$R(\alpha,\lim_{t\to t_{k}^{+}}t)\leq R(\alpha,\lim_{t\to t_{k}^{-}}t).$

This allows to bound $R(\alpha,\lim_{t\to t_{k+1}^{-}}t)$ with a function of
$R(\alpha,\lim_{t\to t_{k}^{-}}t)$ and the final bound follows by recursivity,
by noting that $R(\alpha,t_{0}^{-})=0$ since coupled tracing diffusions have
the same start parameter.

This theorem guarantees that under the c-LSI condition, the privacy loss
converges during the noisy SGD process if
$\lim_{K\to\infty}\sum_{k=1}^{K}\eta_{k}=\infty$.

In particular, the case where the step size is constant is straightforward:

######  Corollary 3.1 (RDP for DP-SGLD under $c$-LSI with constant step-size).

Let $\Theta_{t}$ be defined as in Theorem 3.3. If $\mathcal{A}_{\mathrm{DP-
SGLD}}$ has constant step size $\eta$ and if $\Theta_{t}$ satisfies $c$-LSI
throughout $0\leq t\leq\eta K$, then $\mathcal{A}_{\mathrm{DP-SGLD}}$
satisfies $(\alpha,\varepsilon)$ Rényi Differential Privacy for

$\varepsilon=\dfrac{2\alpha L^{2}}{cn^{2}\sigma^{4}}(1-e^{-c\sigma^{2}\eta
K}).$

In addition, Chourasia et al. (2021) show that the $c$-LSI condition is
satisfied in DP-GLD with constant step size, for loss functions that are
Lipschitz, strongly convex and smooth, with appropriate conditions on the
algorithm parameters and initialization. We derive an equivalent lemma for DP-
SGLD with varying step size.

######  Lemma 3.3 (LSI for DP-SGLD).

If loss function $\ell(\theta,\mathbf{x})$ is $\lambda$-strongly convex and
$\beta$-smooth over a closed convex set $\mathcal{C}$, then the coupled
tracing diffusion processes $\\{\Theta_{t}\\}_{t\geq 0}$ and
$\\{\Theta^{\prime}_{t}\\}_{t\geq 0}$ for DP-SGLD with step size
$\\{\eta_{k}\\}_{k\geq 0}$ satisfying $\eta_{k}<\frac{1}{\beta}$ for $k\geq
0$, and with initial distribution
$\Theta_{0}\sim\Pi_{\mathcal{C}}(\mathcal{N}(0,\frac{2\sigma^{2}}{\lambda}\mathbf{I}_{d}))$,
satisfy $c$-LSI for $t\geq 0$ with $c=\frac{\lambda}{2\sigma^{2}}$.

The proof of this lemma is exactly the same as Lemma 5 of Chourasia et al.
(2021), where $n$ needs to be replaced with the batch size $m$ and $\eta$ with
$\eta_{k}$.

We immediately derive the following bound on the Rényi privacy loss for DP-
SGLD.

######  Theorem 3.1 (Privacy guarantee for DP-SGLD).

Let $\ell(\theta,\mathbf{x})$ be an $L$-Lipschitz, $\lambda$-strongly convex
and $\beta$-smooth loss function on closed convex set $\mathcal{C}$, then
$\mathcal{A}_{\mathrm{DP-SGLD}}$ with start parameter
$\theta_{0}\sim\Pi_{\mathcal{C}}(\mathcal{N}(0,\frac{2\sigma^{2}}{\lambda}\mathbf{I}_{d}))$
and step-size $\eta<\frac{1}{\beta}$ satisfies $(\alpha,\varepsilon)$-Rényi
differential privacy with

$\varepsilon=\dfrac{4\alpha L^{2}}{\lambda
n^{2}\sigma^{2}}(1-e^{-\frac{\lambda}{2}\sum_{k=1}^{K}\eta_{k}}).$

The case where the step size is constant follows:

######  Corollary 3.2 (Privacy Guarantee for DP-SGLD with constant step-size).

With $\ell(\theta,\mathbf{x})$ and $\mathcal{A}_{\mathrm{DP-SGLD}}$ defined as
in Theorem 3.1, and with constant step size $\eta<\frac{1}{\beta}$,
$\mathcal{A}_{\mathrm{DP-SGLD}}$ satisfies $(\alpha,\varepsilon)$-Rényi
Differential Privacy with

$\varepsilon=\dfrac{4\alpha L^{2}}{\lambda n^{2}\sigma^{2}}(1-e^{-\lambda\eta
K/2}).$

We also provide the case where the step size is defined as
$\smash{\eta_{k}=\frac{1}{2\beta+\lambda k/2}}$, which is further analyzed in
the next section.

######  Corollary 3.3 (Privacy Guarantee for DP-SGLD with decreasing step-
size).

With $\ell(\theta,\mathbf{x})$ and $\mathcal{A}_{\mathrm{DP-SGLD}}$ defined as
in Theorem 3.1, and with step size $\eta_{k}=\frac{1}{2\beta+\lambda k/2}$,
$\mathcal{A}_{\mathrm{DP-SGLD}}$ satisfies $(\alpha,\varepsilon)$-Rényi
Differential Privacy with

$\varepsilon=\dfrac{4\alpha
L^{2}}{\lambda\sigma^{2}n^{2}}(1-e^{-\log(1+\frac{\lambda
K}{4\beta})})=\dfrac{4\alpha L^{2}}{\lambda n^{2}\sigma^{2}}\frac{\lambda
K}{4\beta+\lambda K}.$

#### Discussion.

Let us consider that $\eta$ in Corollary 3.2 is set as
$\eta=\frac{1}{2\beta}$, so that it can be compared to Corollary 3.3 and also
matches the maximum upper bound for which we derive utility guarantees is the
next section. In the regime where $K$ is small (compared to
$\frac{\beta}{\lambda}$), both corollaries have equivalent bounds on
$\varepsilon$. Indeed, in the fixed step size setting we have with
$\smash{\eta=\frac{1}{2\beta}}$:

$\varepsilon=\frac{4\alpha L^{2}}{\lambda n^{2}\sigma^{2}}(1-e^{-\lambda
K/{4\beta}})\sim_{K\ll\frac{\beta}{\lambda}}\frac{\alpha L^{2}K}{\beta
n^{2}\sigma^{2}},$

while in the decreasing step size setting we have

$\varepsilon=\dfrac{4\alpha L^{2}}{\lambda n^{2}\sigma^{2}}\frac{\lambda
K}{4\beta+\lambda K}\sim_{K\ll\frac{\beta}{\lambda}}\frac{\alpha L^{2}K}{\beta
n^{2}\sigma^{2}}.$

In particular, $\varepsilon$ reaches the baseline composition analysis from
Abadi et al. (2016) up to a factor 2 : $\varepsilon^{\prime}=\frac{\alpha
L^{2}}{n^{2}\sigma^{2}}\cdot\eta K=\frac{\alpha L^{2}K}{2\beta
n^{2}\sigma^{2}}$.

In the regime where $K$ is sufficiently large (compared to
$\frac{\beta}{\lambda}$), both the fixed $\eta$ and decreasing $\eta_{k}$
settings also reach the same bound on $\varepsilon$, equal to

$\varepsilon\sim_{K\gg\frac{\beta}{\lambda}}\frac{4\alpha L^{2}}{\lambda
n^{2}\sigma^{2}}.$

As a side note, we notice that we can consider the unconstrained regularized
version of the problem:
$\widetilde{\mathcal{L}_{\mathcal{D}}}(\theta)=\mathcal{L}_{\mathcal{D}}(\theta)+\frac{\lambda}{2}\left\|\theta\right\|^{2}_{2}$
and derive equivalent properties. In this scenario, we no longer need the
strong convexity assumption on $\mathcal{L}_{\mathcal{D}}(\theta)$. In
addition we can use the optimality of $\theta^{*}$ for
$\widetilde{\mathcal{L}_{\mathcal{D}}}$ to derive two equations :

$\displaystyle\mathcal{L}_{\mathcal{D}}(\theta^{*})+\frac{\lambda}{2}\left\|\theta^{*}\right\|^{2}_{2}\leq\mathcal{L}_{\mathcal{D}}(0),\
\ \ \ \ c\nabla\mathcal{L}_{\mathcal{D}}(\theta^{*})+\lambda\theta^{*}=0.$

Each of these provides a bound on $\left\|\theta^{*}\right\|_{2}$, by using
respectively the positivity of $\mathcal{L}_{\mathcal{D}}$ and the
lipschitzness of $\mathcal{L}_{\mathcal{D}}$,

$\left\|\theta^{*}\right\|_{2}\leq\Big{(}\frac{2\mathcal{L}_{\mathcal{D}}(0)}{\lambda}\Big{)}^{1/2},\quad\left\|\theta^{*}\right\|_{2}\leq\frac{L}{\lambda},$

which can be used as bounds for the radius of the convex $\mathcal{C}$ we
project onto, so that we still actually end up solving the unconstrained
problem.

##  4 Utility analysis for noisy stochastic gradient descent

Differential privacy is known for setting a trade-off between privacy and
utility. To assess the utility of the noisy stochastic gradient descent
algorithm $\mathcal{A}_{\mathrm{DP-SGLD}}$, we measure two quantities, the
worst case excess empirical risk

$\max_{\mathcal{D}\in\mathcal{X}^{n}}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})],$

and the worst case average empirical risk

$\max_{\mathcal{D}\in\mathcal{X}^{n}}\operatorname*{\mathbb{E}}[\frac{1}{K}\sum_{k=1}^{K}\mathcal{L}_{\mathcal{D}}(\theta_{k})-\mathcal{L}_{\mathcal{D}}(\theta^{*})],$
(6)

where $\theta_{K}$ is the output of the randomized algorithm
$\mathcal{A}_{\mathrm{DP-SGLD}}$ on $\mathcal{D}$ during $K$ iterations,
$\theta^{*}$ is the solution to the standard non-noisy GD algorithm and the
expectation is taken over the randomness of the algorithm.

###  4.1 Fixed step size $\eta$

We propose a bound on the worst case excess empirical risk when the learning
rate is fixed and satisfies $\eta<\frac{1}{2\beta}$.

[normal, end, restate, one big link translated=The proof is provided in
Appendix on page, category=lemma:emp_risk]lemma[Empirical risk for smooth and
strongly convex loss]

Let $\ell(\theta,\mathbf{x})$ be an $L$-Lipschitz, $\lambda$-strongly convex
and $\beta$-smooth loss function on closed convex set $\mathcal{C}$,
$\mathcal{A}_{\mathrm{DP-SGLD}}$ be parameterized with step-size
$\eta<\frac{1}{2\beta}$ and start parameter
$\smash{\theta_{0}\sim\Pi_{\mathcal{C}}(\mathcal{N}(0,\frac{2\sigma^{2}}{\lambda}\mathbf{I}_{d}))}$,
then the empirical risk of $\mathcal{A}_{\mathrm{DP-SGLD}}$ is bounded by

$\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\!\leq\\!\dfrac{\beta}{2}\\!\operatorname*{\mathbb{E}}[\left\|\theta_{0}\\!-\\!\theta^{*}\\!\right\|_{2}^{2}]e^{-\lambda\eta
K}\\\ \\!\\!+\\!\dfrac{\beta\eta\xi^{2}}{2\lambda}\\!+\\!\dfrac{\beta
d\sigma^{2}}{\lambda},$ (7)

where $\theta^{*}$ is the minimizer of $\mathcal{L}_{\mathcal{D}}(\theta)$ in
$\mathcal{C}$ and
$\xi^{2}=\operatorname*{\mathbb{E}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]$.

[]

Let’s recall the noisy SGD update equation:

$\theta_{k+1}=\Pi_{\mathcal{C}}(\theta_{k}-\eta\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})+\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d}))$

From the definitions of $\Pi_{\mathcal{C}}(\cdot)$ and $\theta^{*}$, we have:

$\Pi_{\mathcal{C}}(\theta^{*})=\theta^{*}$

Combining this facts and using the contractivity of the projection
$\Pi_{\mathcal{C}}(\cdot)$, we derive:

$\begin{array}[]{l}\left\|\theta_{k+1}-\theta^{*}\right\|_{2}^{2}\\\
\;=\left\|\Pi_{\mathcal{C}}(\theta_{k}\\!-\\!\eta\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta_{k})\\!+\\!\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d}))\\!-\\!\theta^{*}\right\|_{2}^{2}\\\
\;=\left\|\Pi_{\mathcal{C}}(\theta_{k}\\!-\\!\eta\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta_{k})\\!+\\!\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d}))\\!-\\!\Pi_{\mathcal{C}}(\theta^{*})\right\|_{2}^{2}\\\
\;\leq\left\|\theta_{k}-\eta\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})+\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})-\theta^{*}\right\|_{2}^{2}\\\
\;=\left\|\theta_{k}-\theta^{*}-\eta\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})+\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\right\|_{2}^{2}\\\
\;=\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}+\eta^{2}\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})\right\|_{2}^{2}+2\eta\sigma^{2}\left\|\mathcal{N}(0,\mathbf{I}_{d})\right\|_{2}^{2}\\\
\quad+2\langle\theta_{k}-\theta^{*},\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k}),\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\theta_{k}-\theta^{*},\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})\rangle\\\
\end{array}$

We now take the expectation with respect to the random variable
$\mathcal{B}_{k}$ sampled from $\mathcal{D}$, and we note that
$\operatorname*{\mathbb{E}}_{\mathcal{D}}[\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})]=\mathcal{L}_{\mathcal{D}}(\theta_{k})$
since $\mathcal{L}_{\mathcal{B}_{k}}$ is an unbiased estimate of
$\mathcal{L}_{\mathcal{D}}$.

$\begin{array}[]{l}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\theta_{k+1}-\theta^{*}\right\|_{2}^{2}]\\\
\;=\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}+\eta^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})\right\|_{2}^{2}]\\\
\quad+2\eta\sigma^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\mathcal{N}(0,\mathbf{I}_{d})\right\|_{2}^{2}]\\\
\quad+2\langle\theta_{k}-\theta^{*},\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k}),\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\theta_{k}-\theta^{*},\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})\rangle\\\
\end{array}$

Using the classic inequality $(a+b)^{2}\leq 2(a^{2}+b^{2})$, we derive:

$\begin{array}[]{l}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})\right\|_{2}^{2}]\\\
\;=\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})-\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})+\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{*})\right\|_{2}^{2}]\\\
\;\leq\\!2\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta_{k})\\!-\\!\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta^{*})\right\|_{2}^{2}]\\!+\\!2\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta^{*})\right\|_{2}^{2}]\\\
\end{array}$

Furthermore, by $\beta$-smoothness of $\nabla\mathcal{L}_{\mathcal{B}_{k}}$,
we can use the property of co-coercivity of the gradients:

$\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta_{k})\\!-\\!\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta^{*}\\!)\right\|_{2}^{2}\\!\leq\\!\beta\langle\theta_{k}\\!-\\!\theta^{*}\\!,\\!\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta_{k})\\!-\\!\nabla\mathcal{L}_{\mathcal{B}_{k}}\\!(\theta^{*}\\!)\rangle$
(8)

Taking expectation over $\mathcal{B}_{k}$ and using optimality of
$\theta^{*}$:

$\begin{array}[]{l}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})-\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]\\\
\;\leq\beta\langle\theta_{k}-\theta^{*},\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})-\nabla\mathcal{L}_{\mathcal{D}}(\theta^{*})\rangle\\\
\;=\beta\langle\theta_{k}-\theta^{*},\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})\rangle\end{array}$
(9)

Combining these elements, we derive:

$\begin{array}[]{l}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\theta_{k+1}-\theta^{*}\right\|_{2}^{2}]\\\
\;=\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}+2\eta^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta_{k})-\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]\\\
\quad+2\eta^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]+2\eta\sigma^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\mathcal{N}(0,\mathbf{I}_{d})\right\|_{2}^{2}]\\\
\quad+2\langle\theta_{k}-\theta^{*},\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k}),\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\theta_{k}-\theta^{*},\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})\rangle\\\
\;\leq\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}+2\eta(\eta\beta-1)\langle\theta_{k}-\theta^{*},\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})\rangle\\\
\quad+2\eta^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]+2\eta\sigma^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\mathcal{N}(0,\mathbf{I}_{d})\right\|_{2}^{2}]\\\
\quad+2\langle\theta_{k}-\theta^{*},\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k}),\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad\mathrm{\>using\>(\ref{eq:cocoercitivity})\>and\>}(\ref{eq:expected_coco})\end{array}$

Let’s assume that $\eta\leq\frac{1}{2\beta}$. Therefore,
$2\eta(\eta\beta-1)\leq-\eta$. By optimality of $\theta^{*}$ and strong
convexity arguments on $\mathcal{L}_{\mathcal{D}}$, we deduce the following
inequality:

$\begin{array}[]{ll}\\!\\!-\langle\theta_{k}\\!-\\!\theta^{*}\\!,\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})\rangle\\!\\!\\!\\!\\!&\leq\mathcal{L}_{\mathcal{D}}(\theta_{k})\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)\\!+\\!\dfrac{\lambda}{2}\\!\left\|\theta_{k}\\!-\\!\theta^{*}\right\|_{2}^{2}\\\
&\leq\lambda\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}\end{array}$

Plugging this together, we have:

$\begin{array}[]{l}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\theta_{k+1}-\theta^{*}\right\|_{2}^{2}]\\\
\;\leq(1-\eta\lambda)\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}+\eta^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]\\\
\quad+2\eta\sigma^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\mathcal{N}(0,\mathbf{I}_{d})\right\|_{2}^{2}]\\\
\quad+2\langle\theta_{k}-\theta^{*},\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k}),\sqrt{2\eta\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\end{array}$

We take the expectation again:

$\operatorname*{\mathbb{E}}[\left\|\theta_{k+1}-\theta^{*}\right\|_{2}^{2}]\leq(1-\eta\lambda)\operatorname*{\mathbb{E}}[\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}]\qquad$
(10)
$\qquad\qquad\qquad+\eta^{2}\operatorname*{\mathbb{E}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]+2\eta
d\sigma^{2}$

Now, by $\beta$-smoothness of $\mathcal{L}_{\mathcal{D}}(\cdot)$, we have:

$\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})\leq\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta^{*}),\theta_{K}-\theta^{*}\rangle+\dfrac{\beta}{2}\left\|\theta_{K}-\theta^{*}\right\|_{2}^{2}$

Second, by optimality of $\theta^{*}$ in $\mathcal{C}$ and the fact that
$\theta_{K}\in\mathcal{C}$, we have

$\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta^{*}),\theta_{K}-\theta^{*}\rangle=0$

Combining these two we get:

$\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})]\leq\dfrac{\beta}{2}\operatorname*{\mathbb{E}}[\left\|\theta_{K}-\theta^{*}\right\|_{2}^{2}]$

Using the recursive equation (10) repeatedly for $k=0,\dots,K-1$, we have:

$\begin{array}[]{l}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})]\\\
\;\leq\dfrac{\beta}{2}(1-\eta\lambda)^{K}\operatorname*{\mathbb{E}}[\left\|\theta_{0}-\theta^{*}\right\|_{2}^{2}]\\\
\qquad\qquad\qquad\quad+\dfrac{\beta}{2}(\eta^{2}\xi^{2}+2\eta
d\sigma^{2})\sum_{k=0}^{K-1}(1-\eta\lambda)^{k}\\\
\;\leq\dfrac{\beta}{2}e^{-\lambda\eta
K}\operatorname*{\mathbb{E}}[\left\|\theta_{0}-\theta^{*}\right\|_{2}^{2}]+\dfrac{\beta\eta\xi^{2}}{2\lambda}+\dfrac{\beta
d\sigma^{2}}{\lambda}\\\\[7.0pt]
\mathrm{where}\>\xi^{2}=\operatorname*{\mathbb{E}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]\end{array}$

Sketch of proof. First, we recursively bound
$\smash{\left\|\theta_{k+1}-\theta^{*}\right\|_{2}^{2}}$ as a function of
$\smash{\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}}$, using the definition
of $\theta_{k+1}$. Then, we take the expectation with respect to
$\mathcal{B}_{k}$ and use co-coercivity of the gradients, and take the
expectation again to derive a recursive relationship between
$\smash{\operatorname*{\mathbb{E}}[\left\|\theta_{k+1}-\theta^{*}\right\|_{2}^{2}]}$
and
$\smash{\operatorname*{\mathbb{E}}[\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}]}$.
Last, we express the empirical risk
$\smash{\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})]}$
as a function of
$\smash{\operatorname*{\mathbb{E}}[\left\|\theta_{K}-\theta^{*}\right\|_{2}^{2}]}$.

This shows that under Lipschitz smooth strongly convex loss function, the
empirical risk of $\mathcal{A}_{\mathrm{DP-SGLD}}$ decreases as the iterations
increase, and reaches a constant factor which is the sum of a term directly
related to the variance of the noise $\sigma^{2}$ added at each iteration and
another term which represents the error due to the SGD process, which
decreases with the learning rate $\eta$.

######  Lemma 4.1 (Empirical risk for smooth and strongly convex loss,
independent of $\theta$).

Let $\ell$ and $\mathcal{A}_{\mathrm{DP-SGLD}}$ be defined as in Lemma 4.1,
then the empirical risk is bounded by

$\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\leq\dfrac{2\beta
L^{2}}{\lambda^{2}}e^{-\lambda\eta
K}\\!\\!+\\!\dfrac{\beta\eta\xi^{2}}{2\lambda}\\!+\\!\dfrac{\beta
d\sigma^{2}}{\lambda},$

where
$\xi^{2}=\operatorname*{\mathbb{E}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]$.

###### Proof.

Since we have $\left\|\mathcal{C}\right\|\leq\frac{2L}{\lambda}$, we can bound
$\operatorname*{\mathbb{E}}[\left\|\theta_{0}-\theta^{*}\right\|_{2}^{2}]\leq\frac{4L^{2}}{\lambda^{2}}$,
as $\theta_{0},\theta^{*}\in\mathcal{C}$. ∎

Combining now Lemma 4.1 and Theorem 3.1, we derive the utility of
$\mathcal{A}_{\mathrm{DP-SGLD}}$ under $(\alpha,\varepsilon)$-Rényi
differential privacy.

[normal, end, restate, one big link translated=The complete proof is provided
in Appendix on page, category=th:utility_renyi]theorem[Utility bound for
$(\alpha,\varepsilon)$-Rényi differential privacy] Let
$\ell(\theta,\mathbf{x})$ be an $L$-Lipschitz, $\lambda$-strongly convex and
$\beta$-smooth loss function on closed convex set $\mathcal{C}$, then
$\mathcal{A}_{\mathrm{DP-SGLD}}$ with start parameter
$\smash{\theta_{0}\sim\Pi_{\mathcal{C}}(\mathcal{N}(0,\frac{2\sigma^{2}}{\lambda}\mathbf{I}_{d}))}$
and constant step-size $\eta=\frac{1}{2\beta}$, satisfies
$(\alpha,\varepsilon)$ Rényi differential privacy and

$\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})]=O\left(\dfrac{\alpha\beta
dL^{2}}{\varepsilon\lambda^{2}n^{2}}\right)+\dfrac{\xi^{2}}{4\lambda},$

where $\sigma^{2}$ and $K$ are set as such:

$\sigma^{2}=\dfrac{4\alpha L^{2}}{\varepsilon\lambda n^{2}},\quad
K=\dfrac{2\beta}{\lambda}\log\\!\left(\dfrac{\varepsilon n^{2}}{\alpha
d}\right).$

[]First, as $\theta_{0},\theta^{*}\in\mathcal{C}$ and
$\left\|C\right\|_{2}\leq\frac{2L}{\lambda}$, we have
$\operatorname*{\mathbb{E}}[\left\|\theta_{0}-\theta^{*}\right\|_{2}^{2}]\leq\frac{4L^{2}}{\lambda^{2}}$.

Then, we plug the values of $\sigma^{2}$ and $K$ in Lemma 4.1:

$\begin{array}[]{ll}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\!\\!\\!\\!&\\!\leq\\!\dfrac{\beta}{2}\\!\dfrac{4L^{2}}{\lambda^{2}}e^{-\lambda\eta
K}\\\ &\quad+\dfrac{\beta
d\sigma^{2}}{\lambda}\\!+\\!\dfrac{\beta\eta\xi^{2}}{2\lambda}\\\
&\\!\leq\\!\dfrac{2\beta L^{2}}{\lambda^{2}}\\!\dfrac{\alpha d}{\varepsilon
n^{2}}\\\ &\quad+\dfrac{\beta d}{\lambda}\dfrac{4\alpha
L^{2}}{\lambda\varepsilon n^{2}}\\!+\\!\dfrac{\beta\eta\xi^{2}}{2\lambda}\\\
&\leq\dfrac{6\alpha\beta
dL^{2}}{\varepsilon\lambda^{2}n^{2}}+\dfrac{\xi^{2}}{4\lambda}\>\mathrm{with}\>\eta\\!=\\!\dfrac{1}{2\beta}\par\end{array}$

[normal, end, restate, one big link translated=The complete proof is provided
in Appendix on page, category=th:utility_dwork]theorem[Utility bound for
$(\epsilon,\delta)$-differential privacy]With the same conditions as is
Theorem 4.1, for $\epsilon\leq 2\log(1/\delta)$ and $\delta>0$,
$\mathcal{A}_{\mathrm{DP-SGLD}}$ satisfies $(\epsilon,\delta)$ differential
privacy and

$\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})]=O\left(\dfrac{\beta
dL^{2}\log(1/\delta)}{\epsilon^{2}\lambda^{2}n^{2}}\right)+\dfrac{\xi^{2}}{4\lambda},$

where $\sigma^{2}$ and $K$ are set as such:

$\displaystyle\sigma^{2}=\dfrac{8L^{2}(\epsilon+2\log(1/\delta)}{\epsilon^{2}\lambda
n^{2}}$ $\displaystyle
K=\dfrac{2\beta}{\lambda}\log\\!\left(\dfrac{\epsilon^{2}n^{2}}{4\log(1/\delta)d}\right).$

[]By setting $\varepsilon=\frac{\epsilon}{2}$, we derive from Proposition 2.1
:

$\alpha=1+\frac{2}{\epsilon}\log(1/\delta)$

.

We use this to rewrite the results from Theorem 4.1:

$\begin{array}[]{ll}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\!\\!&\leq\dfrac{6\alpha\beta
dL^{2}}{\varepsilon\lambda^{2}n^{2}}+\dfrac{\xi^{2}}{4\lambda}\\\
&=\dfrac{6\beta
dL^{2}}{\lambda^{2}n^{2}}\dfrac{1+\frac{2}{\epsilon}\log(1/\delta)}{\frac{\epsilon}{2}}+\dfrac{\xi^{2}}{4\lambda}\\\
&=\dfrac{6\beta
dL^{2}}{\lambda^{2}n^{2}}\dfrac{2\epsilon+4\log(1/\delta)}{\epsilon^{2}}+\dfrac{\xi^{2}}{4\lambda}\\\
&\leq\dfrac{6\beta
dL^{2}}{\lambda^{2}n^{2}}\dfrac{8\log(1/\delta)}{\epsilon^{2}}+\dfrac{\xi^{2}}{4\lambda}\\\
&\quad\mathrm{using}\>\epsilon\leq 2\log(1/\delta)\end{array}$

Similarly,

$\begin{array}[]{ll}\sigma^{2}\\!&=\dfrac{4L^{2}\alpha}{\lambda
n^{2}\varepsilon}\\\ &=\dfrac{4L^{2}}{\lambda
n^{2}}\dfrac{1+\frac{2}{\epsilon}\log(1/\delta)}{\frac{\epsilon}{2}}\\\
&=\dfrac{8L^{2}(\epsilon+2\log(1/\delta)}{\epsilon^{2}\lambda
n^{2}}\end{array}$
$\begin{array}[]{ll}K\\!&=\dfrac{2\beta}{\lambda}\log\\!\left(\dfrac{n^{2}}{d}\dfrac{\varepsilon}{\alpha}\right)\\\
&=\dfrac{2\beta}{\lambda}\log\\!\left(\dfrac{n^{2}}{d}\dfrac{\frac{\epsilon}{2}}{1+\frac{2}{\epsilon}\log(1/\delta)}\right)\\\
&=\dfrac{2\beta}{\lambda}\log\\!\left(\dfrac{n^{2}}{d}\dfrac{\epsilon^{2}}{2\epsilon+4\log(1/\delta)}\right)\\\
&\leq\dfrac{2\beta}{\lambda}\log\\!\left(\dfrac{\epsilon^{2}n^{2}}{4\log(1/\delta)d}\right)\end{array}$

As a side note, arguments of the proof of Lemma 4.1 (like the co-coercivity of
the gradients) can be reused to improve the upper bound on $\eta$ from
$\frac{\lambda}{2\beta^{2}}$ to $\frac{1}{2\beta}$ in Theorem 4 of Chourasia
et al. (2021) on the utility of DP-GLD. We provide experimental evidence in
the next section that this factor $\frac{\lambda}{\beta}$ is non-negligible.

###  4.2 Decreasing step size $\eta_{k}$

To remove the $\frac{\xi^{2}}{4\lambda}$ term which is due to using stochastic
gradient descent, we follow the approach from Roux et al. (2012) and propose
to bound the worst case average empirical risk (6) when the step size is
decreasing and follows:

$\eta_{k}=\dfrac{1}{2\beta+\frac{\lambda k}{2}}\,,\,k\geq 0.$

[normal, end, restate, one big link translated=The proof is provided in
Appendix on page, category=lemma:emp_risk_decreasing_eta]lemma[Empirical risk
for smooth and strongly convex loss with decreasing learning rate] Let
$\ell(\theta,\mathbf{x})$ be an $L$-Lipschitz, $\lambda$-strongly convex and
$\beta$-smooth loss function on closed convex set $\mathcal{C}$,
$\mathcal{A}_{\mathrm{DP-SGLD}}$ be parameterized with _decreasing_ step-size
$\smash{\eta_{k}=\frac{1}{2\beta+\lambda k/2}}$ and start parameter
$\smash{\theta_{0}\sim\Pi_{\mathcal{C}}(\mathcal{N}(0,\frac{2\sigma^{2}}{\lambda}\mathbf{I}_{d}))}$,
then the average empirical risk of $\mathcal{A}_{\mathrm{DP-SGLD}}$ is bounded
by

$\operatorname*{\mathbb{E}}[\frac{1}{K}\\!\\!\sum_{k=1}^{K}\\!\mathcal{L}_{\mathcal{D}}(\theta_{k}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\!\leq\\!\dfrac{2\beta}{K}\operatorname*{\mathbb{E}}[\left\|\theta_{0}\\!-\\!\theta^{*}\\!\right\|_{2}^{2}]\\\
\\!+\\!\dfrac{4\xi^{2}}{K\lambda}\\!\log\\!\left(\\!\\!1\\!+\\!\dfrac{\lambda
K}{4\beta}\\!\\!\right)\\!+\\!2d\sigma^{2},$ (11)

where $\theta^{*}$ is the minimizer of $\mathcal{L}_{\mathcal{D}}(\theta)$ in
$\mathcal{C}$. []We define $\eta_{k}$ as such

$\eta_{k}=\dfrac{1}{2\beta+\frac{\lambda k}{2}}.$

Note that in particular that for $k\geq 0$, $\eta_{k}\leq\frac{1}{2\beta}$ and
hence $2\eta_{k}(\eta_{k}\beta-1)\leq-\eta_{k}$.

As detailed in the proof of Lemma 4.1 we have the following:

$\begin{array}[]{l}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\theta_{k+1}\\!-\\!\theta^{*}\right\|_{2}^{2}]\\\
\;\leq\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}+2\eta_{k+1}(\eta_{k+1}\beta-1)\langle\theta_{k}-\theta^{*},\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})\rangle\\\
\quad+2\eta_{k+1}^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]+2\eta_{k+1}\sigma^{2}\operatorname*{\mathbb{E}}_{\mathcal{D}}[\left\|\mathcal{N}(0,\mathbf{I}_{d})\right\|_{2}^{2}]\\\
\quad+2\langle\theta_{k}-\theta^{*},\sqrt{2\eta_{k+1}\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad-2\eta_{k+1}\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k}),\sqrt{2\eta_{k+1}\sigma^{2}}\mathcal{N}(0,\mathbf{I}_{d})\rangle\\\
\quad\mathrm{\>using\>(\ref{eq:cocoercitivity})\>and\>}(\ref{eq:expected_coco})\end{array}$

By taking expectation again we derive

$\begin{array}[]{ll}\operatorname*{\mathbb{E}}[\left\|\theta_{k+1}\\!\\!-\\!\theta^{*}\right\|_{2}^{2}]\\!\\!\\!\\!\\!&\leq\operatorname*{\mathbb{E}}[\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}]\\\
&\\!\\!\\!\\!+2\eta_{k+1}(\eta_{k+1}\beta\\!-\\!1)\operatorname*{\mathbb{E}}[\\!\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k}\\!),\theta_{k}\\!-\\!\theta^{*}\rangle]\\\
&\\!\\!\\!\\!+2\eta_{k+1}^{2}\operatorname*{\mathbb{E}}[\left\|\nabla\mathcal{L}_{\mathcal{B}_{k}}(\theta^{*})\right\|_{2}^{2}]+2\eta_{k+1}\sigma^{2}d\\\
&\\!\\!\\!\\!\leq\operatorname*{\mathbb{E}}[\left\|\theta_{k}-\theta^{*}\right\|_{2}^{2}]\\\
&\\!\\!\\!\\!-\eta_{k+1}\operatorname*{\mathbb{E}}[\langle\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k}),\theta_{k}-\theta^{*}\rangle]\\\
&\\!\\!\\!\\!+2\eta_{k+1}(\eta_{k+1}\xi^{2}+d\sigma^{2})\end{array}$

By optimality of $\theta^{*}$ and strong convexity arguments on
$\mathcal{L}_{\mathcal{D}}$, we have

$\begin{array}[]{ll}\\!\\!-\langle\theta_{k}\\!-\\!\theta^{*}\\!,\nabla\mathcal{L}_{\mathcal{D}}(\theta_{k})\rangle\\!\\!\\!\\!\\!&\leq\mathcal{L}_{\mathcal{D}}(\theta_{k})\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)\\!+\\!\dfrac{\lambda}{2}\\!\left\|\theta_{k}\\!-\\!\theta^{*}\right\|_{2}^{2}\end{array}$

Hence we have

$\begin{array}[]{l}\operatorname*{\mathbb{E}}[\left\|\theta_{k+1}\\!-\\!\theta^{*}\right\|_{2}^{2}]\\\
\;\leq(1\\!-\\!\dfrac{\eta_{k+1}\lambda}{2})\operatorname*{\mathbb{E}}[\left\|\theta_{k}\\!-\\!\theta^{*}\right\|_{2}^{2}]\\!-\\!\eta_{k+1}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{k})\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\\
\quad+2\eta_{k+1}(\eta_{k+1}\xi^{2}+d\sigma^{2})\end{array}$

Equivalently

$\begin{array}[]{l}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{k})\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*})]\\\
\;\leq-\dfrac{1}{\eta_{k+1}}\operatorname*{\mathbb{E}}[\left\|\theta_{k+1}\\!-\\!\theta^{*}\right\|_{2}^{2}]+(\dfrac{1}{\eta_{k+1}}-\dfrac{\lambda}{2})\operatorname*{\mathbb{E}}[\left\|\theta_{k}\\!-\\!\theta^{*}\right\|_{2}^{2}]\\\
\quad+2(\eta_{k+1}\xi^{2}+d\sigma^{2})\end{array}$

Plugging in the definition of $\eta_{k}$ we have

$\begin{array}[]{l}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{k})\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*})]\\\
\;\leq-(2\beta+\dfrac{\lambda}{2}(k+1))\operatorname*{\mathbb{E}}[\left\|\theta_{k+1}\\!-\\!\theta^{*}\right\|_{2}^{2}]\\\
\quad\>\>+(2\beta+\dfrac{\lambda}{2}k)\operatorname*{\mathbb{E}}[\left\|\theta_{k}\\!-\\!\theta^{*}\right\|_{2}^{2}]\\\
\quad\>\>+2(\eta_{k+1}\xi^{2}+d\sigma^{2})\end{array}$

We derive the average empirical risk

$\begin{array}[]{l}\operatorname*{\mathbb{E}}[\frac{1}{K}\sum_{k=0}^{K-1}\mathcal{L}_{\mathcal{D}}(\theta_{k}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\\
\;=\dfrac{1}{K}\sum_{k=0}^{K-1}\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{k}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\\
\;=-\dfrac{1}{K}(2\beta+\dfrac{\lambda}{2}K)\operatorname*{\mathbb{E}}[\left\|\theta_{K}\\!-\\!\theta^{*}\right\|_{2}^{2}]\\\
\quad+\dfrac{2\beta}{K}\operatorname*{\mathbb{E}}[\left\|\theta_{0}\\!-\\!\theta^{*}\right\|_{2}^{2}]+2d\sigma^{2}+\dfrac{2\xi^{2}}{K}\displaystyle{\sum_{k=1}^{K}}\eta_{k}\\\
\;\leq\dfrac{2\beta}{K}\operatorname*{\mathbb{E}}[\left\|\theta_{0}\\!-\\!\theta^{*}\right\|_{2}^{2}]+2d\sigma^{2}+\dfrac{2\xi^{2}}{K}\displaystyle{\sum_{k=1}^{K}}\dfrac{1}{2\beta+\frac{\lambda
k}{2}}\\\
\;\leq\dfrac{2\beta}{K}\operatorname*{\mathbb{E}}[\left\|\theta_{0}\\!-\\!\theta^{*}\right\|_{2}^{2}]+2d\sigma^{2}+\dfrac{2\xi^{2}}{K}\displaystyle{\int_{0}^{K}}\dfrac{1}{2\beta+\frac{\lambda
t}{2}}dt\\\
\;\leq\dfrac{2\beta}{K}\operatorname*{\mathbb{E}}[\left\|\theta_{0}\\!-\\!\theta^{*}\right\|_{2}^{2}]+2d\sigma^{2}+\dfrac{4\xi^{2}}{K\lambda}\log\left(1+\dfrac{\lambda
K}{4\beta}\right)\end{array}$

The term $\smash{\frac{\xi^{2}}{\lambda}}$ decreases roughly in
$\smash{\frac{1}{K}\log(K)}$. The term $d\sigma^{2}$ still appears as in Lemma
4.1 but without the $\smash{\frac{\beta}{\lambda}}$ factor, that we observe to
be quite significant in Section 5.

We then use this lemma to derive the following utility bound under
$(\alpha,\varepsilon)$-Rényi differential privacy:

[normal, end, restate, one big link translated=The complete proof is provided
in Appendix on page, category=th:utility_renyi_decreasing_eta]theorem[Utility
bound for $(\alpha,\varepsilon)$-Rényi differential privacy with decreasing
learning rate] Let $\ell(\theta,\mathbf{x})$ be an $L$-Lipschitz,
$\lambda$-strongly convex and $\beta$-smooth loss function on closed convex
set $\mathcal{C}$, then $\mathcal{A}_{\mathrm{DP-SGLD}}$ with start parameter
$\smash{\theta_{0}\sim\Pi_{\mathcal{C}}(\mathcal{N}(0,\frac{2\sigma^{2}}{\lambda}\mathbf{I}_{d}))}$
and _decreasing_ step-size $\smash{\eta_{k}=\frac{1}{2\beta+\lambda k/2}}$,
satisfies $(\alpha,\varepsilon)$ Rényi differential privacy and

$\operatorname*{\mathbb{E}}[\frac{1}{K}\\!\\!\sum_{k=1}^{K}\\!\mathcal{L}_{\mathcal{D}}(\theta_{k}\\!)-\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]=O\left(\dfrac{\alpha
dL^{2}}{\varepsilon\lambda n^{2}}\right),$

where $\sigma^{2}$ and $K$ are set as such:

$\sigma^{2}=\dfrac{4\alpha L^{2}}{\varepsilon\lambda n^{2}},\quad
K=\max\\!\left(\dfrac{\beta}{\lambda}\dfrac{\varepsilon n^{2}}{\alpha
d},\dfrac{\lambda}{\beta}\left(\dfrac{\varepsilon n^{2}}{\alpha
d}\right)^{2}\right).$

[]Since $\theta_{0},\theta^{*}\in\mathcal{C}$ and
$\left\|C\right\|_{2}\leq\frac{2L}{\lambda}$, we have
$\operatorname*{\mathbb{E}}[\left\|\theta_{0}-\theta^{*}\right\|_{2}^{2}]\leq\frac{4L^{2}}{\lambda^{2}}$.
Additionally, by Lipschitzness of the loss we have $\xi^{2}\leq L^{2}$.

We can use this and plug the value of $\sigma^{2}$ to rewrite Lemma 4.2:

$\begin{array}[]{ll}\operatorname*{\mathbb{E}}[\frac{1}{K}\\!\\!\sum_{k=1}^{K}\\!\mathcal{L}_{\mathcal{D}}\\!(\theta_{k}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}\\!(\theta^{*}\\!)]\\!\\!\\!\\!&\\!\leq\\!\dfrac{8\alpha
dL^{2}}{\varepsilon\lambda n^{2}}+\dfrac{8\beta L^{2}}{K\lambda^{2}}\\\
&\quad+\dfrac{L^{2}}{\beta}\dfrac{4\beta}{K\lambda}\log(1+\dfrac{K\lambda}{4\beta})\\\
\end{array}$

Then, we use the following bound on the logarithmic function from (Mitrinovic
& Vasic, 1970):

$\forall x>-1,\dfrac{1}{x}\log(1+x)\leq\dfrac{1}{\sqrt{1+x}}$

to derive:

$\dfrac{L^{2}}{\beta}\dfrac{4\beta}{K\lambda}\log(1+\dfrac{K\lambda}{4\beta})\leq\dfrac{L^{2}}{\beta}\dfrac{1}{\sqrt{1+\dfrac{K\lambda}{4\beta}}}$

We can now plug the value of $K$.

$\begin{array}[]{ll}\operatorname*{\mathbb{E}}[\frac{1}{K}\\!\\!\sum_{k=1}^{K}\\!\mathcal{L}_{\mathcal{D}}\\!(\theta_{k}\\!)\\!-\\!\mathcal{L}_{\mathcal{D}}\\!(\theta^{*}\\!)]\\!\\!\\!\\!&\\!\leq\\!\dfrac{8\alpha
dL^{2}}{\varepsilon\lambda n^{2}}+\dfrac{8\beta L^{2}}{K\lambda^{2}}\\\
&\quad+\dfrac{L^{2}}{\beta}\sqrt{\dfrac{4\beta}{\lambda}\dfrac{\beta}{\lambda}\left(\dfrac{\alpha
d}{\varepsilon n^{2}}\right)^{2}}\\\ &\\!\leq\\!\dfrac{18\alpha
dL^{2}}{\varepsilon\lambda n^{2}}\end{array}$

Compared to previous Theorem 4.1, we improve the utility bound by a factor
$\frac{\beta}{\lambda}$ which is non negligible in practice. However, the
number of iterations $K$ can now evolve either in $n^{2}$ or in $n^{4}$ in the
regime where $\smash{\frac{\varepsilon n^{2}}{\alpha
d}>\big{(}\frac{\beta}{\lambda}\big{)}^{2}}$.

[normal, end, restate, one big link translated=The complete proof is provided
in Appendix on page, category=th:utility_dwork_decreasing_eta]theorem[Utility
bound for $(\epsilon,\delta)$-differential privacy with decreasing learning
rate]With the same conditions as is Theorem 4.2, for $\epsilon\leq
2\log(1/\delta)$ and $\delta>0$, $\mathcal{A}_{\mathrm{DP-SGLD}}$ satisfies
$(\epsilon,\delta)$ differential privacy and

$\operatorname*{\mathbb{E}}[\mathcal{L}_{\mathcal{D}}(\theta_{K})-\mathcal{L}_{\mathcal{D}}(\theta^{*})]=O\left(\dfrac{dL^{2}\log(1/\delta)}{\epsilon^{2}\lambda
n^{2}}\right),$

where $\sigma^{2}$ and $K$ are set as such:

$\displaystyle\sigma^{2}$
$\displaystyle=\dfrac{8L^{2}(\epsilon+2\log(1/\delta)}{\epsilon^{2}\lambda
n^{2}}$ $\displaystyle K$
$\displaystyle=\max\Bigg{(}\dfrac{\beta}{\lambda}\dfrac{\epsilon^{2}n^{2}}{4\log(1/\delta)d},\dfrac{\lambda}{\beta}\left(\dfrac{\epsilon^{2}n^{2}}{4\log(1/\delta)d}\right)^{2}\Bigg{)}.$

[]By setting $\varepsilon=\frac{\epsilon}{2}$, we derive from Proposition 2.1
:

$\alpha=1+\frac{2}{\epsilon}\log(1/\delta)$

.

We use this to rewrite the results from Theorem 4.2:

$\begin{array}[]{ll}\operatorname*{\mathbb{E}}[\frac{1}{K}\\!\\!\sum_{k=1}^{K}\\!\mathcal{L}_{\mathcal{D}}(\theta_{k}\\!)-\mathcal{L}_{\mathcal{D}}(\theta^{*}\\!)]\\!\\!\\!&\leq\dfrac{18\alpha
dL^{2}}{\varepsilon\lambda n^{2}}\\\ &=\dfrac{18dL^{2}}{\lambda
n^{2}}\dfrac{1+\frac{2}{\epsilon}\log(1/\delta)}{\frac{\epsilon}{2}}\\\
&=\dfrac{18dL^{2}}{\lambda
n^{2}}\dfrac{2\epsilon+4\log(1/\delta)}{\epsilon^{2}}\\\
&\leq\dfrac{18dL^{2}}{\lambda n^{2}}\dfrac{8\log(1/\delta)}{\epsilon^{2}}\\\
&\quad\mathrm{using}\>\epsilon\leq 2\log(1/\delta)\end{array}$

Similarly,

$\begin{array}[]{ll}\sigma^{2}\\!&=\dfrac{4L^{2}\alpha}{\lambda
n^{2}\varepsilon}\\\ &=\dfrac{4L^{2}}{\lambda
n^{2}}\dfrac{1+\frac{2}{\epsilon}\log(1/\delta)}{\frac{\epsilon}{2}}\\\
&=\dfrac{8L^{2}(\epsilon+2\log(1/\delta)}{\epsilon^{2}\lambda
n^{2}}\end{array}$ $\begin{array}[]{ll}\dfrac{\epsilon n^{2}}{\alpha
d}\\!&=\dfrac{n^{2}}{d}\dfrac{\frac{\epsilon}{2}}{1+\frac{2}{\epsilon}\log(1/\delta)}\\\
&=\dfrac{n^{2}}{d}\dfrac{\epsilon^{2}}{2\epsilon+4\log(1/\delta)}\\\
&\leq\dfrac{\epsilon^{2}n^{2}}{4\log(1/\delta)d}\\\ \end{array}$
$\begin{array}[]{ll}K\\!&=\max\left(\dfrac{\beta}{\lambda}\dfrac{\epsilon
n^{2}}{\alpha d},\dfrac{\lambda}{\beta}\left(\dfrac{\epsilon n^{2}}{\alpha
d}\right)^{2}\right)\\\
&\leq\max\left(\dfrac{\beta}{\lambda}\dfrac{\epsilon^{2}n^{2}}{4\log(1/\delta)d},\dfrac{\lambda}{\beta}\left(\dfrac{\epsilon^{2}n^{2}}{4\log(1/\delta)d}\right)^{2}\right)\\\
\end{array}$

##  5 Experiments: application to logistic regression

We now propose an experimental evaluation of DP-SGLD and compare it to DP-SGD
on a classification task using logistic regression on two vision datasets,
CIFAR10 and Pneumonia, a dataset of chest X-ray images of pediatric pneumonia
published by Kermany et al. (2018). Details about the datasets and models are
available in Appendix D.

The task consists of pre-training a model (here AlexNet or ResNet18) on a
dataset that will be considered _public_ (here we take CIFAR100 and Imagenet).
Then, all layers of the model are freezed except for the last one which is
retrained from scratch using a softmax loss function on a _private_ dataset
(here CIFAR10 or Pneumonia). This corresponds to logistic regression and some
regularization is added to guarantee strong convexity. Pre-training provides
generic feature maps learned on a public dataset which improves the task
accuracy without any compromise on the privacy.

First, we formalize this setting and provide the smoothness and convexity
constants for logistic regression. Second, we report accuracy achieved with
DP-SGLD and compare it to DP-SGD for constant and decreasing step size $\eta$.

###  5.1 Smoothness and convexity of logistic regression

For clarity, we replace the generic parameter $\theta$ with the single matrix
$\mathbf{W}$ that it represents for logistic regression.

The loss with regularization writes
$\ell(\mathbf{W},\mathbf{x})=\log\big{(}\boldsymbol{\sigma}(\mathbf{W}\mathbf{x})\big{)}_{y}+\lambda\left\|\mathbf{W}\right\|_{2}^{2}$
where $C$ is the number of classes, $y\in[1,C]$ is the label of sample
$\mathbf{x}$, $\smash{\mathbf{W}\in\mathbb{R}^{C\times p}}$ and
$\smash{\boldsymbol{\sigma}:\mathbb{R}^{C}\mapsto\mathbb{R}^{C}}$ is the
sigmoid function (not to be confused with the noise variance $\sigma$):

$\big{(}\boldsymbol{\sigma}(\mathbf{z})\big{)}_{i}=\dfrac{e^{z_{i}}}{\sum_{j=1}^{C}e^{z_{j}}},\>\forall
i=1,..,C\>,\mathbf{z}\in\mathbb{R}^{C}$

[normal, end, restate, one big link translated=The proof is provided in
Appendix on page, category=lemma:smoothness_cvx_log_reg]lemma[Convexity and
smoothness constants for regularized logistic regression]Let
$\ell(\mathbf{W},\mathbf{x})$ be defined as above. Then $\ell$ is
$\lambda$-strongly convex and $\beta$-smooth, with

$\displaystyle\beta=\dfrac{1}{2}\lambda_{\mathsf{max}}\Big{(}\dfrac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}\mathbf{x}_{i}^{\top}\Big{)}+\lambda$

where $\lambda_{\mathsf{max}}$ refers to the maximum eigenvalue.

[]By plugging in the definition of the sigmoid, the loss $\ell$ also writes:

$\ell(\mathbf{W},\mathbf{x})=\log\dfrac{\exp\big{(}(\mathbf{W}\mathbf{x})_{y}\big{)}}{\sum_{i=1}^{C}\exp\big{(}(\mathbf{W}\mathbf{x})_{i}\big{)}}+\lambda\left\|\mathbf{W}\right\|_{2}^{2},$

where $\mathbf{W}\in\mathbb{R}^{C\times p}$ also writes
$[\mathbf{w}_{1}^{\top},\dots,\mathbf{w}_{C}^{\top}]^{\top}$.

Let’s define for i = 1, …, C

$\displaystyle p_{i}=P(y_{i}=1|\mathbf{x},\mathbf{W})$
$\displaystyle=\dfrac{\exp\big{(}(\mathbf{W}\mathbf{x})_{i}\big{)}}{\sum_{c=1}^{C}\exp\big{(}(\mathbf{W}\mathbf{x})_{c}\big{)}}$
$\displaystyle=\dfrac{\exp(\mathbf{w}_{i}^{\top}\mathbf{x})}{\sum_{c=1}^{C}\exp(\mathbf{w}_{c}^{\top}\mathbf{x})}$

We can rewrite the loss $\ell$ as such

$\ell(\mathbf{W},\mathbf{x})=\log\prod_{i=1}^{C}p_{i}^{y_{i}}+\lambda\left\|\mathbf{W}\right\|_{2}^{2}$

where the label $y$ is now one-hot encoded: $y=(y_{0},\dots,y_{C})$.

Following the work of (Böhning, 1992), we have:

$\nabla^{2}\ell(\mathbf{W},\mathbf{x})=(\mathbf{D}(\mathbf{p})-\mathbf{p}\mathbf{p}^{\top})\otimes\mathbf{x}\mathbf{x}^{\top}+\lambda\mathbf{I}_{C}$

where $\mathbf{D}(\mathbf{p})=\mathbf{I}_{C}\mathbf{p}$.

We derive

$\nabla^{2}\mathcal{L}_{\mathcal{D}}(\mathbf{W})=\dfrac{1}{n}\sum_{j=1}^{n}(\mathbf{D}(\mathbf{p}_{j})-\mathbf{p}_{j}\mathbf{p}_{j}^{\top})\otimes\mathbf{x}_{j}\mathbf{x}_{j}^{\top}+\lambda\mathbf{I}_{C}$

where $\mathbf{p}_{j}$ corresponds to $\mathbf{p}$ conditioned with
$\mathbf{x}_{j}$.

As shown in (Krishnapuram et al., 2005),
$\nabla^{2}\mathcal{L}_{\mathcal{D}}(\mathbf{W})$ satisfies the following

$\lambda\mathbf{I}_{C}\preceq\nabla^{2}\mathcal{L}_{\mathcal{D}}(\mathbf{W})\preceq\dfrac{1}{2}\big{(}\mathbf{I}_{C}-\dfrac{1}{C}\mathbf{1}_{C}\mathbf{1}_{C}^{\top}\big{)}\otimes\dfrac{1}{n}\mathbf{X}\mathbf{X}^{\top}+\lambda\mathbf{I}_{C}$

where
$\mathbf{X}=[\mathbf{x}_{1},\dots,\mathbf{x}_{n}]^{\top}\in\mathbb{R}^{n\times
d}$. In particular, we deduce:

$\displaystyle\beta$
$\displaystyle=\lambda_{\mathsf{max}}(\nabla^{2}\mathcal{L}_{\mathcal{D}}(\mathbf{W}))$
$\displaystyle\leq\lambda_{\mathsf{max}}\left(\dfrac{1}{2}\big{(}\mathbf{I}_{C}-\dfrac{1}{C}\mathbf{1}_{C}\mathbf{1}_{C}^{\top}\big{)}\otimes\dfrac{1}{n}\mathbf{X}\mathbf{X}^{\top}+\right)+\lambda$
$\displaystyle=\max_{\lambda_{\mathsf{eig}},\lambda_{\mathsf{eig}}^{\prime}}\lambda_{\mathsf{eig}}\left(\dfrac{1}{2}\big{(}\mathbf{I}_{C}-\dfrac{1}{C}\mathbf{1}_{C}\mathbf{1}_{C}^{\top}\big{)}\right)\lambda^{\prime}_{\mathsf{eig}}\left(\dfrac{1}{n}\mathbf{X}\mathbf{X}^{\top}\right)+\lambda$
$\displaystyle\leq\dfrac{1}{2n}\lambda_{\mathsf{max}}\left(\mathbf{X}\mathbf{X}^{\top}\\!\right)+\lambda$

###  5.2 Experimental utility of logistic regression

We compare our DP-SGLD algorithm with the standard DP-SGD from Abadi et al.
(2016) implemented in Opacus and with the baseline SGD without DP on several
vision tasks. In particular, we study the case where the step size is constant
$\smash{\eta=\frac{1}{2\beta}}$ and where it is decreasing as follows :
$\smash{\eta_{k}=\frac{1}{2\beta+\lambda k/2}}$. To be able to provide
somewhat comparable results, all methods (DP-SGLD, DP-SGD and No-DP) use the
same step size, number of training epochs, privacy budget
$(\epsilon,\delta)=(1.0,10^{-5})$ when applicable and use no momentum. Other
hyperparameters are tuned to provide optimal accuracy for each method and are
provided in the source code included in the submission.

Results are given in Table 1 for constant step size and in Table 2 for
decreasing step size. The model indicated is the feature extraction model,
which is pre-trained on CIFAR100 when the task is on CIFAR10 and on Imagenet
when the task is on Pneumonia. Only its last layer is re-trained using
logistic regression. As the tables show, DP-SGLD outperforms standard DP-SGD
for the tasks considered and considerably reduces the gap in accuracy compared
to SGD without differential privacy. However, such results need to be taken
cautiously before drawing conclusions since this task is strongly convex and
smooth while DP-SGD also applies to non-convex tasks.

To better understand the effect of clamping DP-SGD to smooth and strongly
convex tasks, we repeat the first experiment of Table 1, but instead of
leveraging only the last layer for DP-SGD, we also unfreeze the last and
fourth block of the ResNet18 architecture, composed notably of 5 convolutional
layers. Results for DP-SGD and SGD without DP provided in Table 3 show that
while SGD benefits from this fine-tuning and increases accuracy from 70.7% to
77.0%, DP-SGD does not improve and accuracy even decreases marginally from
68.0% to 67.8%. Such observation aligns with Tramèr & Boneh (2021) in the
sense that basic models like logistic regression currently are competitive
compared to deeper models when trained with differential privacy, which
underlines the importance of studying classical tasks like training smooth and
strongly convex objectives.

Last, we provide in Table 4 the experimental value of some parameters, in
light with comments made after Lemma 4.2 about the value of
$\frac{\beta}{\lambda}$ and after Theorem 4.2 about the dependence in $n^{2}$
or $n^{4}$ of $K$, depending of the ratio $\smash{\frac{\varepsilon
n^{2}}{\alpha d}/\big{(}\frac{\beta}{\lambda}\big{)}^{2}}$. As we show, this
ratio is of magnitude $10^{-3}$ or less which shows that the evolution of $K$
is quadratic in $n$.

Table 1: Accuracy (in %) of logistic regression using SGD with a constant learning rate.  Method | Dataset | Model | Epochs | $\epsilon$ | Acc.
---|---|---|---|---|---
DP-SGLD | CIFAR10 | Resnet18 | 30 | 1.0 | 70.3
DP-SGD | CIFAR10 | Resnet18 | 30 | 1.0 | 68.0
No DP | CIFAR10 | Resnet18 | 30 | - | 70.7
DP-SGLD | CIFAR10 | Alexnet | 30 | 1.0 | 57.5
DP-SGD | CIFAR10 | Alexnet | 30 | 1.0 | 56.4
No DP | CIFAR10 | Alexnet | 30 | - | 57.7
DP-SGLD | Pneumonia | Resnet18 | 50 | 1.0 | 58.8
DP-SGD | Pneumonia | Resnet18 | 50 | 1.0 | 58.8
No DP | Pneumonia | Resnet18 | 50 | - | 59.3
Table 2: Accuracy (in %) of logistic regression using SGD with a decreasing learning rate.  Method | Dataset | Model | Epochs | $\epsilon$ | Acc.
---|---|---|---|---|---
DP-SGLD | CIFAR10 | Resnet18 | 30 | 1.0 | 70.1
DP-SGD | CIFAR10 | Resnet18 | 30 | 1.0 | 68.1
No DP | CIFAR10 | Resnet18 | 30 | - | 70.2
DP-SGLD | CIFAR10 | Alexnet | 30 | 1.0 | 57.3
DP-SGD | CIFAR10 | Alexnet | 30 | 1.0 | 56.4
No DP | CIFAR10 | Alexnet | 30 | - | 57.6
DP-SGLD | Pneumonia | Resnet18 | 50 | 1.0 | 58.8
DP-SGD | Pneumonia | Resnet18 | 50 | 1.0 | 58.8
No DP | Pneumonia | Resnet18 | 50 | - | 59.3
Table 3: Accuracy (in %) when fine-tuning ResNet18.  Method | Dataset | Model | Epochs | $\epsilon$ | Acc.
---|---|---|---|---|---
DP-SGD | CIFAR10 | Resnet18 | 30 | 1.00 | 67.8
No DP | CIFAR10 | Resnet18 | 30 | - | 77.0
Table 4: Value of some parameters used for DP-SGLD. Dataset | Model | $\beta$ | $\frac{\beta}{\lambda}$ | ${\color[rgb]{1,1,1}\Big{|}}\frac{\varepsilon n^{2}}{\alpha d}\big{/}\\!\big{(}\frac{\beta}{\lambda}\big{)}^{2}$
---|---|---|---|---
CIFAR10 | Resnet18 | 55 | 5.5 $\times 10^{4}$ | 3.2 $\times 10^{-3}$
CIFAR10 | Alexnet | 259 | 2.6 $\times 10^{5}$ | 1.5 $\times 10^{-4}$
Pneumonia | Resnet18 | 354 | 7.1 $\times 10^{4}$ | 6.8 $\times 10^{-5}$

##  6 Conclusion

We have extended the theoretical framework of Chourasia et al. (2021) to
provide a differential privacy analysis of noisy stochastic gradient descent
based on Langevin diffusion (DP-SGLD) with arbitrary step size. Although our
experiments already show the practical utility of our results, relaxing the
smoothness and strong convexity hypothesis remains an open challenge and would
pave the way for wide adoption by data scientists.

## Acknowledgments

We would like to thank Pierre Tholoniat for the helpful discussions throughout
this project. We are also grateful for the long-standing support of the
OpenMined community and in particular its dedicated cryptography team.

This work was supported in part by the French-German Project CRYPTO4GRAPH-AI
and by PRAIRIE, the PaRis Artificial Intelligence Research InstitutE.

## References

  * Abadi et al. (2016) Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L.  Deep learning with differential privacy.  In _Proceedings of the SIGSAC conference on computer and communications security_ , pp. 308–318, 2016.
  * Böhning (1992) Böhning, D.  Multinomial logistic regression algorithm.  _Annals of the institute of Statistical Mathematics_ , 44(1):197–200, 1992.
  * Chourasia et al. (2021) Chourasia, R., Ye, J., and Shokri, R.  Differential privacy dynamics of langevin diffusion and noisy gradient descent.  _Advances in Neural Information Processing Systems_ , 2021.
  * Dwork et al. (2010) Dwork, C., Rothblum, G. N., and Vadhan, S.  Boosting and differential privacy.  In _Annual Symposium on Foundations of Computer Science_ , pp. 51–60. IEEE, 2010.
  * Dwork et al. (2014) Dwork, C., Roth, A., et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3-4):211–407, 2014.
  * Gross (1975) Gross, L.  Logarithmic Sobolev inequalities.  _American Journal of Mathematics_ , 97(4):1061–1083, 1975.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the Conference on Computer Vision and Pattern Recognition_ , pp. 770–778, 2016.
  * Kermany et al. (2018) Kermany, D. S., Goldbaum, M., Cai, W., Valentim, C. C., Liang, H., Baxter, S. L., McKeown, A., Yang, G., Wu, X., Yan, F., et al.  Identifying medical diagnoses and treatable diseases by image-based deep learning.  _Cell_ , 172(5):1122–1131, 2018.
  * Knott et al. (2021) Knott, B., Venkataraman, S., Hannun, A., Sengupta, S., Ibrahim, M., and van der Maaten, L.  Crypten: Secure multi-party computation meets machine learning.  _Advances in Neural Information Processing Systems_ , 2021.
  * Krishnapuram et al. (2005) Krishnapuram, B., Carin, L., Figueiredo, M. A., and Hartemink, A. J.  Sparse multinomial logistic regression: Fast algorithms and generalization bounds.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 27(6):957–968, 2005.
  * Krizhevsky et al. (2012) Krizhevsky, A., Sutskever, I., and Hinton, G. E.  Imagenet classification with deep convolutional neural networks.  In _Advances in Neural Information Processing Systems_ , pp. 1097–1105, 2012.
  * Krizhevsky et al. (2014) Krizhevsky, A., Nair, V., and Hinton, G.  The CIFAR-10 dataset.  _online:cs.toronto.edu/~kriz/cifar.html_, 55, 2014.
  * Mironov (2017) Mironov, I.  Rényi differential privacy.  In _Computer Security Foundations Symposium (CSF)_ , pp. 263–275. IEEE, 2017.
  * Mitrinovic & Vasic (1970) Mitrinovic, D. S. and Vasic, P. M.  _Analytic Inequalities_ , volume 1.  Springer, 1970.
  * Roux et al. (2012) Roux, N., Schmidt, M., and Bach, F.  A stochastic gradient method with an exponential convergence rate for finite training sets.  In _Advances in Neural Information Processing Systems_ , pp. 3167–3175, 2012.
  * Ryffel et al. (2022) Ryffel, T., Tholoniat, P., Pointcheval, D., and Bach, F.  Ariann: Low-interaction privacy-preserving deep learning via function secret sharing.  _Proceedings on Privacy Enhancing Technologies_ , 2022.
  * Shokri et al. (2017) Shokri, R., Stronati, M., Song, C., and Shmatikov, V.  Membership inference attacks against machine learning models.  In _Symposium on Security and Privacy (SP)_ , pp. 3–18, 2017.
  * Tramèr & Boneh (2021) Tramèr, F. and Boneh, D.  Differentially private learning needs better features (or much more data).  In _9th International Conference on Learning Representations, ICLR_ , 2021.
  * Wagh et al. (2021) Wagh, S., Tople, S., Benhamouda, F., Kushilevitz, E., Mittal, P., and Rabin, T.  FALCON: Honest-Majority Maliciously Secure Framework for Private Deep Learning.  _Proceedings on Privacy Enhancing Technologies_ , 2021.
  * Welling & Teh (2011) Welling, M. and Teh, Y. W.  Bayesian learning via stochastic gradient Langevin dynamics.  In _Proceedings of the International conference on machine learning_ , pp. 681–688. Citeseer, 2011.
  * Yousefpour et al. (2021) Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj, A., Zhao, J., Cormode, G., and Mironov, I.  Opacus: User-friendly differential privacy library in pytorch.  _arXiv preprint arXiv:2109.12298_ , 2021.

##  Appendix A (Proofs) Privacy analysis of noisy stochastic gradient descent

[lemma:sensitivity]

[th:rdp_noisysgd_clsi]

##  Appendix B (Proofs) Utility analysis for noisy stochastic gradient descent

###  B.1 (Proofs) Fixed learning rate $\eta$

[lemma:emp_risk]

[th:utility_renyi]

[th:utility_dwork]

###  B.2 (Proofs) Decreasing step size $\eta_{k}$

[lemma:emp_risk_decreasing_eta]

[th:utility_renyi_decreasing_eta]

[th:utility_dwork_decreasing_eta]

##  Appendix C (Proofs) Experiments: application to logistic regression

[lemma:smoothness_cvx_log_reg]

##  Appendix D Datasets and models

### Datasets

We have selected for our experiments two datasets commonly used for training
image classification models: CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2014),
and also a dataset with healthcare data which can more closely mimic a
scenario where we care about training a model on sensitive data: Pneumonia
(Kermany et al., 2018).

CIFAR CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2014) both consist of 50,000
images in the training set and 10,000 in the test set. They are respectively
composed of 10 and 100 different balanced classes (such as airplanes, dogs,
horses, etc.) and each image consists of a colored 32$\times$32 image. The
datasets are disjoints, which allows us to pretrain our models AlexNet and
Resnet18 on CIFAR-100 and consider it _public_ pre-training before performing
logistic regression on CIFAR10.

Pneumonia Pneumonia is a dataset of chest X-ray images of pediatric pneumonia
that was published by (Kermany et al., 2018). It is composed of 5163 training
and 624 test non-colored images of varying sizes. Images are divided in 3
classes: bacterial (26%), normal (48%) and viral (26%). It provides an
interesting use case as it is a relatively small dataset and is composed of
healthcare data.

### Models

We have selected 2 models for our experimentations.

AlexNet AlexNet is the famous winner of the 2012 ImageNet ILSVRC-2012
competition (Krizhevsky et al., 2012). It has 5 convolutional layers and 3
fully connected layers and it can use batch normalization layers for stability
and efficient training.

ResNet18 ResNet18 (He et al., 2016) is the runner-up of the ILSVRC-2015
competition. It is a convolutional neural network that is 18 layers deep, and
has 11.7M parameters. It uses batch normalisation layers, but as only the last
layer is retrained with differential privacy, we need not replace those layers
with group normalisation.