On the Universality of Langevin Diffusion for Private Euclidean (Convex) Optimization
Authors: Arun Ganesh
Abhradeep Guha Thakurta
Jalaj Kumar Upadhyay
Venue: Submitted to ICLR 2023 (2023)
Keywords: differential privacy
empirical risk minimization
stochastic convex optimization
Langevin diffusion

Abstract: In this paper, we revisit the problem of differentially private empirical risk minimization (DP-ERM) and differentially private stochastic convex optimization (DP-SCO). We show that a well-studied continuous time algorithm from statistical physics, called Langevin diffusion (LD), simultaneously provides optimal privacy/utility trade-offs for both DP-ERM and DP-SCO, under $\epsilon$-DP, and $(\epsilon,\delta)$-DP both for convex and strongly convex loss functions. We provide new time and dimension independent uniform stability properties of LD, with which we provide the corresponding optimal excess population risk guarantees for $\epsilon$-DP.  An important attribute of our DP-SCO guarantees for $\epsilon$-DP is that they match the non-private optimal bounds as $\epsilon\to\infty$. 

Under review as conference paper at ICLR 2023
ON THE UNIVERSALITY OF LANGEVIN DIFFUSION FOR PRIVATE EUCLIDEAN (CONVEX) OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we revisit the problem of differentially private empirical risk min- imization (DP-ERM) and differentially private stochastic convex optimization (DP-SCO), We show that well-studied continuous time algorithm from statis- tical physics, called Langevin diffusion (LD), simultaneously provides optimal pri- vacy /utilitttyyyy trade-offs for both DP-ERN and DP-SCO, under e-DP, and (e,8)-DP both for convex and strongly convex loss functions. We provide new time and dimension independent uniform stability properties of LD, with which we pro- vide the corresponding optimal excess population risk guarantees for e-DP. An important attribute of our DP-SCO guarantees for e-DP is that they match the non-private optimal bounds as E + co.
1 INTRODUCTION
Over the last decade, there has been significant progress in providing tight upper and lower bounds for differentially private empirical risk minimization (DP-ERM) (Chaudhuri et al.) 2011
2017 Smith et al. 2017: Wu et al.) 2017: lyengar al. 2019: Song al. 2020 Chourasia et al.
Kifer et al.) [012] Bassily et al.,
2014
Song et al.
2013 McMahan et al.,
202T and differentially
private stochastic optimization (CP=SCO) (Bassily et al.. 2019) Feldman et al. 2020 Bassily et al.
2020
Kulkarni al. 2021: Gopi et al. 2022 Asi et al. 2021b), both in the D-DP setting and in the
8) DDP setting' While we know tight bounds for both DP-ERM and DP-SCO in the Oe setting (Bassily et al. 2014 2019), the space is much less understood in the e-DP setting (i.e., where 5 0). First, to the best of our knowledge, tight DP-SCO bounds are not known for e-DP. In this paper when we say a bound is tight for any problem, we implicitly always expect the bound to reach the optimal non-private bound (including polylogarithmic factors) for the same task as e co. Second, the algorithms for both DP-ERM and DP-SCO in the e-DP setting are inherently different from the de, setting. While all the algorithms in the (E,5)-DP setting are based on DP variants of gradient descent (Bassily et al. 2014 2019 Feldman et al. 2020 Bassily et al. 2020), the best a algorithms for e-DP are based on a combination of exponential mechanism (McSherry & Talwar 2007) and output perturbation (Chaudhuri et al. 2011). Third, we know that as we move from to (e, DDP, for convex problems, we gain polynomial improvement in the error bounds It is unknown if such an improvement is even possible when the loss functions are non-convex. In this work, we close these gaps in our understanding of DP-ERM and DP-SCO via the following contributions.
in terms of the model dimensionality,
We only focus on fz- 12-Lipschitz losses and the constraint set is bounded in the f--nrm;; the non-Eucledian setting (Talwar et al. 2015; Asi et al. 2021a Bassily et al. 2021 are beyond the scope of this work.
1

---

Under review as conference paper at ICLR 2023
1. We provide a unified framework for DP-ERM/DP-SCO via an information theoretic tool called Langevin diffusion (Langevin 1908 Lemons & Gythiel 1997) (LD) (defined in eq. (1) and eq. 2), which under appropriate choice parameters interpolates between opti mal/ hag/tight utility bounds for both DP-ERM and DP-SCO, both under and (e,8)-DP.
2. We provide tight DP-SCO bounds for both convex and strongly convex losses under &- DP. To achieve these bounds, we show uniform stability of the exponential mechanism on strongly convex losses (which was to the best of our knowledge unknown prior to our work). Notably, our proof of uniform stability is almost immediate given the unified framework from item
3. We provide lower bound showing that if the loss functions are non-convex, it is not possible to obtain any polynomial improvement in the error in terms of the model di- mensionality when we shift from e-DP to (-, This is in sharp contrast to the convex setting.
4. Along the way we provide set of results, which may be of independent interest:
(a) A simple Rényi divergence bound between two Langevin diffusions running on loss functions with bounded gradient difference.
(b) For strongly convex and smooth losses, a Rényi divergence bound between two Langevin diffusions that approaches the Rényi divergence between their stationary distributions.
(c) Improved analyses for e-DP-ERM: For strongly convex losses we improve the bound by log factors via better algorithm, and for non-convex losses we remove the as- sumption of Bassily et al. 2014) that the constraint set contains a ball of radius r. optimization algorithm, using con-
(d) A last-iterate analysis of Langevin diffusion tinuous analogs of techniques in Shamir & Zhang (2013). To the best of our knowl- edge, this is the first analysis tailored to a continuous-time DP algorithm.
Our work initiates a systematic study of DP continuous time optimization. We believe this may have ramifications in the design of discrete time DP optimization algorithms analogous to that in the non-private setting. In the non-private setting, continuous time dynamical viewpoints have helped in designing new algorithms, including the celebrated mirror-descent (see the discussion in Chapter 3 of Nemirovskij & Yudin (1983) and Polyak's 's momentum method (Polyak (964), and understanding the implicit bias of gradient descent (Vardi al.) 2022). Extending the dynamical viewpoint to private optimization would help us understand the price of privacy for the conver- gence rate of private optimization. Further, it is known that privacy helps in generalization and implicit bias underlies the generalization ability of (non-private) machine learning models trained by stochastic gradient descent. Taking the dynamical viewpoint would help us understand if there is a more fundamental reason for the generalization ability of differential privacy.
In the rest of this section, we elaborate on each of these conceptual contributions, and alongside highlight the technical advances that were required. At the end, we provide comparison to most relevant works. We defer a broader comparison to other works in the area to Appendix(A)
Problem description: Consider a data set = (d.....,de ..). drawn from some domain T and an associated loss function & C x T + IR, where C c IRF is called the constraint set. The ob- jective in DP-ERM is to output a model gpriv while ensuring differential privacy that approxi-
mately minimizes the excess empirical risk, RiskERM (ePrrv )
" Σ
((prrvv ;d;) min 1 Σ (() AEC " 1
"1 For brevity, we will refer to 1 Σ ((0;d)) L(0:D), or the empirical loss. For DP-SCO,
sume each data point di in the data set D is drawn i.dd from some distribution D over the domain t, and the objective is to minimize the excess population risk given by Risksco (Bpriv)
2

---

Under review conference paper at ICLR 2023
BBLD [e[OPri :d)] min BaD [e(0:d)] In other words, the goal of DP-ERM is output @priv that BEC
minimizes the average loss on while the goal of DP-SCO to output (priv that performs well
on the 'unseen' data sampled from D. It is easy to see that DP-SCO is a stronger requirement.
Throughout the paper, we make two standard assumptions in differentially private optimization: (i) the loss function ((0;d) is L-Lipschitz w.r.t. 42-norm, i.e, V0 E C, E T, V1 ([V)E((;d) ll S L and (ii) constraint set has bounded diameter. W.l.o.g., we assume the loss functions are twice continuously differentiable within the constraint set -f not, we can ensure this by convolving the loss function with finite variance Gaussian kernel (Feldman al. 2018). Depending on the problem context, we make additional assumptions like m-strong convexity, i.e, D) = ml, and M-smoothness, i.e, (e; D) I MI, where A < B denotes that B - A is a positive semidefinite matrix. We drop the subscript f when it clear from the context. We provide notational details in Appendix [
Langevin Diffusion (LD): We will start with the Langevin Diffusion (LD) algorithm in eq- (1) which forms the building block for all the algorithms considered in this paper. Intuitively, one should think of (1) as the limit of noisy gradient descent and (2) the limit of projected noisy gradient descent, both as + 0.
Langevin diffusion. Let W; be the standard Brownian motion in p-dimensions, and ß; > 0 be the called inverse temperature. Then Langevin diffusion is the following stochastic differential equation:
v2 Br
do, = Bı VVL(OI - dt
dW:
(1)
"Projected" Langevin diffusion. Sometimes, we will only have the Lipschitz guarantee within constrained set. We can also consider the following "projected" version of LD:
V2 Bi
do: - B: -VC(B;) dt + dW; + vz((tt) VV2 0:0EC.
(2)
where L is measure supported on ft: 0 E ac} and vi is an outer unit normal vector at 9 for all such f/. See e.g. [Bubeck et al., 20188 Section 3.1, for discussion of / /Vvriiiicationn that solution exists for convex C' under M-smoothness for some finite M (which can be enforced with arbitrarily small perturbations the loss via convolution).
1.1 OUR RESULTS AND TECHNIQUES: CONCEPTUAL CONTRIBUTIONS
Optimal Excess Population Risk for DP-SCO under e-DP: DP-SCO, at this point, is very well- studied problem in the literature (see references of previous works above). One approach towards obtaining the optimal excess population risk is to first prove optimal DP-ERM bound, and then use uniform stability property (Bousquet & Elisseeff 2002) (Definition B.14 of the underlying DP algorithm to obtain population risk guarantee. These two steps indeed provides the optimal
bounds of @
(loo((10) for convex losses and t En
+ plog(1/5)
for m-strongly convex
m²* n²
losses under (e,8)-DP via variants of DP-SGD (Bassily et al. 2020 bounds is that they reach the non-private optimal bounds as E + co. In our work, we obtain
One crucial aspect of these
logn m
for convex losses and ① Analogous to the (D setting, these bounds reach the non-private optimal as E + co. As mentioned earlier, such bounds for the e-DP setting was unknown prior to this work. Our optimal
for m-strongly convex losses, under &DD..
3

---

Under review as conference paper at ICLR 2023
E-DP
(,,
Assumption
Excess Risk
Time
Excess Risk
Time
Convex
Lp EN
L (pplo((1/5
1 L? log(1 (og(1/1))))) log m²
EN log (pen)
ERM
+p mrin?
1. plplog(1/5)
11-CC
00
me-n2
Non-convex
Lp 671 Ln
log
8
LP log
8
Convex
Lp
L Vn
+
L log
min
log(1/8
SCO
V1I
in
tn
p'
m-SC
L2
+
log
L2
(1/)
log"(pen)
L' log log(1/)) (1/) log (
m²²n=
n
1222
Summary of our upper bounds for DP-ERM and DP-SCO. The bounds marked in blue were not known even via different algorithms. Every bound is tight up to polylog (), factors. Convex: Class of convex bounded Lipschitz losses, m-SC: Convex with (²((0;-) > ml. Non- convex: Class of losses with ||V S Here, time (T) refers to the length till which we run the Langevin Diffusion algorithm; for the e-DP results, T = oo means we use the stationary distribution of the Langevin diffusion. We set the diameter of the constraint set ||C||2 =.
Table 1:
DP-SCO bound obtained by proving a dimension independent uniform stability guarantee for
the standard exponential mechanism on the loss function L(;; D) + mt |10112. The translation to DP- SCO guarantee is immediate (Bousquet & Elisseeff 2002) by appealíng to the DP-ERM guarantee for exponential mechanism for such score functions, and combining with the uniform stability guarantee.
To show dimension-independern uniform stability of the exponential mechanism the regular- ized loss D():D) + ||0|2, we view the exponential mechanism as the limiting distribution of -uniform stability of LD. Here, L is the Lz-Lipschitz
LD, and provide time independent O
parameter of the loss function ((0;-). Equipped with this bound, we can easily combine with the DP-ERM bound to obtain the excess population risk bound we intended to achieve. We believe the above proof technique can be of independent interest, as it allows one to reduce showing the ex- ponential mechanism uniformly stable to showing gradient descent has inne-independent uniform stability, which is a more well-understood problem.
Unification of DP-ERM and DP-SCO via LD: In this work we show that LD Langevin 1908
Lemons & Gythiel, 1997), defined in 11 and (2), interpolates between optimal known utility bounds for both DP ERM and DP-SCO, and both under é- and (e, DDD.. Based on the inverse tem- perature, 6t, and the length for which the diffusion process is run, T, Langevin diffusion not only recovers the best known bounds in all the settings mentioned above, but also provides new pre- viously not known results. For example, it recovers the optimal excess population risk bound for convex and strongly convex DP-SCO under e-DP improving on the previous best known bounds of Asi et al. 20211). summary of the results we achieve in this paper are given in Table
While our algorithm is purely information theoretic, it is worth highlighting that it was not clear whether such universal object that achieves optimal excess risk for both 8- and (e,8)-DP even exists. As we discuss later, the inverse temperature settings of LD that gives rise to the best al- gorithms for eDDP and (D are off by roughly a factor of /p (p being the number of model parameters or the dimension of the parameter space). Hence, under constant e regime for (e, DDP, analyze LD far before it has converged to stationary distribution.
4

---

Under review as conference paper at ICLR 2023
Two-phase analysis of DP-Langevin diffusion: In the process of demonstrating the universality of LD, we discovered two clear phases in the diffusion process, which enable us to obtain either (e, () or e-DP results. For the purposes of brevity, it easiest explain this in the context of Lipschitz convex losses. We provide details for other losses in the remainder of the paper. As evi- dent from To obtain the DP-ERM and DP-SCO bounds in the (e, setting, the LD runs for T= whereas, in the e-DP setting, it needs to run until it convergences to a stationary distri-
bution. It is easy to show that, when I' < }, the diffusion process cannot converge to a stationary distribution under reasonable choice of inverse temperature required to ensure DP. This follows from the fact that, within the mentioned time period, for certain loss functions and constraint sets, which contains cO(p)
pf
with high probability, LD does not escape ball of diameter ||C||2 for of the probability mass of the stationary distribution. However, LD is still able to obtain the de- sired ERM bounds in this time because the desired ERM bounds are satisfied by points at distance Q /p/ sp/)n from the empirical minimizer (see Appendix for a more detailed discussion). In the e-DP case, however, we run LD till it has converged to The stationary distribution, which is the exponential mechanism (see Appendix[]ie
more detailed discussion).
As result, the utility analysis for these phases are very different. In the (DP case, we analyze the algorithm as a noisy gradient flow and use tools from optimization theory (Wilson et al. 2021), whereas, in the e-DP setting, we analyze the utility in terms of the stationary distribution that the diffusion process converge to, i.e., the Gibbs distribution. Following this viewpoint, if one studies DP-SGD (Bassily et al. 2014) (which is a typical optimization algorithm in the (e, case) as a discretization of the LD process, one can observe that under optimal parameter settings it does not converge to anywhere near the stationary distribution (see Appendix
1.2 OUR RESULTS AND TECHNIQUES: TECHNICAL CONTRIBUTIONS
In this section we give an overview of our technical results. Due to space constraints, we only give formal statements for our most novel results and high-level descriptions for remaining results.
Rényi divergence bounds for LD (Appendix Cand Appendix D: : We cannot use standard com- position theorems of DP (Dwork & Roth 2014) because the underlying algorithm is a continuous time process. One main technical contribution of this work is quantify the Rényi divergence
between two LD processes when run on neighboring data sets:
Lemma 1.1 (Simplified version of Lemma C.1).
Let O (O.T) be the distribution of the trajectory (0
in Suppose we have that VV D) V VL( D')I1 S A for all 0. Then for all a 2 1:
R p.. 00,7) a4² T Brtt.
The idea behind the above lemma is to define an infinite sequence of pairs of DP-SGD runs on D, D' with decreasing step sizes, such that (i) there is fixed Rényi divergence bound that holds for all pairs in the sequence and (ii) the trajectory of 2 is the limit of the sequence. We then conclude using Fatou's lemma. This result forms the foundation of the privacy analysis in the rest of the paper. A similar result was also provided in Chourasia et al. (2021). Our result is stronger in that proves a divergence bound between the entire histories {8, JosiST rather than just the last iterate 0r, which enables us to output weighted averages of 0g privately. Furthermore, it is proven using only tools from the differential privacy literature and Fatou's lemma, providing an arguably much simpler proof. Additionally, for the special case of strongly convex and smooth loss functions, we leverage techniques from Vempala & Wibisono (2019) and Ganesh & Talwar (2020) to show a Rényi-divergence bound (Lemma [T] that approaches the divergence between the stationary distributions of the LD processes, i.e., the privacy guarantee of the exponential mechanism. Since this bound is not needed for our DP-ERM or DP-SCO results, we defer it to Appendix
5

---

Under review as conference paper at ICLR 2023
LD as exponential mechanism, DP-ERM under e-DP (Appendix D): The observation made in privacy analysis of Langevin diffusion (LD) allows us to derive the results on private optimization using exponential mechanism (McSherry Talwar 2007). One technical challenge that we need to overcome while mapping LD to exponential mechanism is the issue with optimizing within the constraint set C. We do this via result of Tanaka (1979), stated in Lemma D.2 This, in turn, read- ily gives us optimal empirical risk for & f--Lipschiz convex functions (described in Appendix (D) using the utility analysis in BBasslly et al. (2014) (see Theorem D.I). To get optimal empirical risk for strongly convex Lipschitz functions requires an algorithmic improvement. Recall the algo- rithm in BBsssiy et al. (2014) for strongly convex losses uses a two step process: output pertur- bation (Chaudhuri et al. 20111, and then one shot exponential mechanism. In Algorithm 3 we propose an iterated exponential mechanism which can be of independent interest. This algorithm allows us to define an algorithm purely based on an exponential mechanism over the loss function D). The idea is to iteratively run the exponential mechanism on a sequence of constraint sets (C Co 2 C 2 2 Cx), where Ci+1 B(e, r;) Ci, 0 being the output of the E,-DP exponential mechanism on C, For appropriate choices of é r; we get the following ERM bound for 0g that is the output of the exponential mechanism on the final constraint set:
Theorem 1.2 (Simplified version of Theorem D.3 Algoritim 3
is E-DP and for m-strongly convex
losses, outputs 8g such that
E [RisKERM (0x) = O (L2 +
( plogn) m22n2
This is a mild improvement on the excess empirical risk over Bassily et al. (2014), who achieved OLL'p² logp2 nog For non-convex functions, the results of Bassily et al. (2014) either assume a small ball of radius is contained in the constraint set C, with utility depending on [og(||C||, /r), or use the discrete exponential mechanism on ball-covering of C. One of our technical contri- butions is to show that the continuous exponential mechanism achieves the optimal excess loss without the small ball assumption (Theorem D.5). Our algorithm is (arguably) more flexible than the ball-covering algorithm in Bassily et al. (2014), since for certain classes of non-convex losses, one can still approximately sample from the continuous exponential mechanism efficiently (e.g., if the stationary distribution satisfies a Poincaré inequality or isoperimetry (Chewi et al. 2021 Sable[ssmmmaizee these results.
LD as noisy gradient flow, and DP-ERM under (e, 0-DP (Appendix F11; The view of LD we took for the eDD case was when the diffusion has converged to stationary distribution. We also study LD in the setting when it is far from convergence. In fact, we argue in Appendix [1tat, under the settings we operate with, the algorithm's 's convergence to the stationary distribution is not much better than point distribution We present two results under (e, (e.d) i) LD achieves optimal excess empirical risk bounds for convex losses (Theorem
F.1 and ii) LD achieves optimal excess
empirical risk bounds for strongly convex losses (Theorem
The optimality of these algorithms follow from the standard lower bounds in Bassily et al. (00 4 and privacy guarantee follows from the privacy accounting machinery described above (see Table 1 for a summary of the bounds).
Our utility bound holds for the last model fr output by LD. On the technical side, for the convex case, we derive a continuous analogue of the excess empirical risk bound for the last iterate of noisy SGD in Shamir & Zhang (2013). One of the technical challenges in extending Shamir & Zhang 22013) to continuous case is in finding the best potential function to bound the loss L(BT; D).
2There is setting of parameters obtaining the optimal (asymptotic) excess empirical loss, loss function C, and constraint set C such that the total variation (1-Wassertein, resp.) distance to the stationary distribution can be large as o(1) (O(IIC])2), resp.).
6

---

Under review as conference paper at ICLR 2023
Unfortunately, as Shamir & Zhang (2013) also mentions, a direct comparison to min L(; does
BEC
not result in the optimal error. Shamir & Zhang 2013) get around this by bounding the error
T
in terms of the tail averaged loss for small number of iterates, i.e. S = F+
1
L), 1=T-k
Σ
They then use a recursive argument to compare Sg with S Sk-2, to finally relate to the required error bound. This approach fails in the continuous setting because there is no concept of a time step. In order to get our bound, we extend the operator Sy to operate over small discretized windows of width y and then use Fatou's lemma to take lim to obtain the continuous analogue.
7-0
We believe this technique could be of independent interest.
The case for strongly convex loss function is more challenging as the usual choice of potential/Lyupanoo" function, ||0 0e112, does not immediately provide the right rate of con- vergence. We pick e |10, 0* 1 (based on Wilson (0018) as the Lyupanov function instead of ||0, 8 1/2. (Here, B, is some fixed function of f.) The choice of this Lyupanov function now allows So" 0,dem
us to get an optimal excess empirical risk guarantee for gpriv
Uniform stability of LD, and unifying convex DP-SCO (Appendices E and F22: We finally show the empirical risk to population risk transformation by showing uniform stability bounds for both e-DP and (e, -DP For the e-DP setting, standard transformation from empirical risk to population risk in Bassily et al. (014)) (either via fz-regularizatio, or the stability property of DP itself) leads to a bound sub-optimal by Vp-factor. We improve this and get an optimal bound as follows:
Theorem 1.3 (Simplified version of Theorem E.4). Let @priv be the output of the expomential mechanism when on the regularized loss Lm D) C(0; D) + mi ||01|2- For appropriate choice of m have:
Egpriv |Risksco (Opriv) )] = Lp ||Cll2 L L1|C112] /n
en
The above bound is obtained by showing a dimension-inddeeedeeri uniform stability result for the exponential mechanism on strongly convex losses by viewing the exponential mechanism as the limit as as 1 + 0, + of gradient descent, which has a dimension and time-indeepeddet uniform stability bound for strongly convex losses (see Corollary E.3) While Raginsky et al. (2017) as well as exten- sions of results in Bassily et al. (2014) give dimensionndeppedenn uniform stability bounds for the exponential mechanism, a dimension-independeer
bound was not known prior to this work. A -nneeeeoonnndeeendeent uniform stability bound was also proven independently of us in the con- temporary work of Gopi et al. (002) (Theorem 6.10), albeit using different proof. We discuss it in more detail in Appendix A Given uniform stability of the exponential mechanism on strongly convex losses, we apply it in the convex case by adding a regularizer to the loss function. In the strongly convex case, where we use the iterated exponential mechanism, we show that the pop- ulation and empirical minimizers of a strongly convex loss function are close to each other with high probability. Given this claim and the uniform stability bound, only a slight modification of our DP-ERM analysis is needed to get the desired SC- bound informally stated as below:
Theorem 1.4 (Simplified version of Theorem E.6) Let 0g be the output of Algorithm 3 with slight modification to the algorithm's parameters. Then it 15 DD and for m-strongly convex losses satisfies
log
1
E Risksco (B+)
+
m
mn
A Lyapunov function maps scalar or vector variables to real numbers (RP + RR and decreases along the solution trajectory of an SDE. They are primarily used in ordinary differential equation to prove stability and in continuous optimization to prove convergence.
7

---

Under review as conference paper at ICLR 2023
We also prove uniform stability of LD in the (e, setting via analyzing noisy gradient de- scent when learning rate tends to zero. The optimality of the results above follows from standard arguments (see Appendix C in Bassily et al. (2
Lower-bound for non-convex functions (Appendix G In the case of convex loss functions, it is known that we can improve the excess error by vP factor by going from e-DP to (e, (D,P However, the excess empirical risk of our algorithm for non-convex loss function under (D is the same as that under e-DP. We finally show that it is not an artifact of our algorithm or analysis, rather, in general, it is not possible to get an improvement by going from e-DP to (E, for non- convex loss functions:
Theorem 1.5 (Simplified version of Theorem G.1 p. There exists a dataset D = .d....., An} and 1-Lipschitz non-convex function L such that for every p E IN, there is no (e, diffferrirelllllllll private algorithm A that outputs (priv such that RiskERM (@Priv) E o o (plog (1/8)/ (ne)).
The lower bound uses a reduction to the top-k-selection problem defined over the universe of size s. In particular, we define packing over the p-dimensional Euclidean ball such that there is an bi- jective mapping between the centers of the packing and [s]. Then we define a non-convex function such that the function attains the minimum at the center that corresponds to the coordinate j E [s] with maximum frequency. Since the size of the a-net is 2e 1/a" and there is a bijective mapping, this gives the desired lower bound using Steinke & Ullman (017).
1.3 RELATED WORKS
Comparison to Gopi et al. 2022; : In concurrent, independent, and complementary work on convex losses Gopi et al. 2022) showed that the stationary distribution of retropolis-Hastiing style process provides the optimal algorithm both for DP-SCO and DP-ERM under (e, O-DP for 6z- Lipschitz and convex losses. Their results immediately imply a single algorithm that spans across e and (e, 5DDP for DP-ERM. In comparison, our work captures much larger spectrum of unifica- tion, i.e., DP-ERM and DP-SCO, under e and (e, DDP, for fz-Lisschitz losses with/without wwihhuut strong convexity. Furthermore, unlike Gopi et al. (2022) our privacy analysis does not rely on convexity. In terms of gradient oracle complexity, Gopi et al. 2022) give oracle efficient algorithms for their construction. While we acknowledge that the oracle complexity of our LD based algorithm is an important research question, we leave it for future work (see Section 1.4), and focus statistical efficiency only. The DP-SCO result in Gopi et al. 22022 relies on uniform stability property of expo- nential mechanism, analogous to our work. While their result relies on bounding the Wasserstein distance between two exponential mechanisms run on neighboring data sets, our uniform stabil- ity guarantee follows immediately from the uniform stability guarantee of the diffusion process (which in limit matches the exponential mechanism).
Comparison Chourasia et al. 2001); Altschuler & Talwar (2022 Ryffel et al. (2022) : Recently,
Chourasia et al. (2021) studied discretization of the LD algorithm as (P-(shcchastic) Gradient Langevin Dynamics (DP-SGLD), and Ryffel et al. 2022 extended these results of Chourasia et al. (2021) to the mini-batch setting. They show that under smoothness and strong convexity the loss function L(e; D), the privacy cost of DP-SGLD converges to stationary finite value, even when the number of time steps goes to co. This in-turn improves the gradient oracle complexity over differentially private stochastic gradient descent, dubbed as DP-SGD, (Algorithm T. Our anal- ysis of DP-LD improves on the result of Chourasia al. (2021) by allowing divergence bounds
"The lower bound in Bassily et al. 2019) is technically for (c, but can be interpreted as that for cDDP up to slack factors of polylog(1)
The authors of Gopi et al. 2022 also formally acknowledged the independence claim.
8

---

Under review as conference paper at ICLR 2023
between the entire histories (0+)0 rather than just the last iterate OT, which enables us out- put weighted averages of Bt privately, which is necessary for some of our (e,5)-DP guarantees. Altschuler & Talwar (2022) in follow-up work to ours, removes the requirement of strong con- vexity in ChChuuaaa et al. 2021)) and provides an analogous bound only for the last iterate 0y using a different technique based on optimal transport. In general, these results are orthogonal to us since they do not seek to either unify the existing algorithms or provide tighter utility/ utility/privacy trade-offs via the Langevin syynamccs/diffusion
diffusion view point.
(001b : Asi et al. (0021b) showed DP-SCO bounds under general con- dition called k-growlt via a custom localization based algorithm. A corollary of their results is log
Comparison to Asi et al.
3/2 plog for Lipschitz con-
that under e-DP one can obtain a excess population risk of O
V
vex losses, and O log" n mm
p² p²log" 1 m=-"1
for Lipschitz and m-strongly convex losses under e-DP. Notice
that the bounds do not reach the non-private optimal bounds of O Vn (+)) and O
respectively
as + co, Our bounds on the other hand have the property of matching the non-private optimal bounds as - co. To the best of our knowledge, the polylog(n) dependence in the non-private er- ror bounds of Asi et al. (2021b) is not slack in the analysis, but is unavoidable for their algorithm. We note that Asi et al.
(2021b) has the advantage of requiring weaker primitives (solving an ERM problem instead of the exponential mechanism) and thus being easier to implement. However, our improvements are not solely due to using stronger primitives; e.g., our uniform stability bound a generalization of uniform stability bound implicitly used in their paper.
Asa
We provide a thorough comparison to other related works in Appendix A
1.4 FUTURE DIRECTIONS
While we know that most of the DP-ERM and DP-SCO bounds are optimal, our understanding of the optimal rates of convergence (in terms of gradient oracle complexity (Bubeck) 2015) to these error bounds is far from being complete. For example, Kuru et al. (2020) shows DP algorithms with accelerated oracle complexity for strongly convex and smooth losses; can we obtain optimal DP-SCO/DP-ERM rates with accelerated oracle complexity without strong convexity?
Understanding the trajectory of private optimization has further ramifications, such under- standing of the natural scope of higher order descent methods under privacy constraints, and phenomena that gradients are heavy tailed and lie in a low dimensional subspace. For example, in the non-private setting, higher order methods can be naturally explained using variational meth- ods that study the trajectory of optimization (Wibisono et al., 2016). For DP, one can study the corresponding stochastic variational methods. Here, we can use differentiation as a linear opera- tor and then use the machinery of operator algebra understand the necessary conditions for the calculus that allows us to derive stochastic variational methods.
From a practical perspective, these methods can be helpful in understanding whether DP-SGD converges to robust network not when training deep neural network. Without privacy, we know that there is an implicit bias of gradient descent towards non-robust local minima of non-convex problems even though robust networks exist (Vardi et al. 2022). However, because of stochastic- ity, DP-SGD behaves as the so called Ornstein- Ornstein-Ulllenbeek Uhlenbeck process. An immediate consequence of this phenomenon is that it activates the second-order Taylor's 's expansion adding a regularizer-like behavior. This phenomenon does not exist in gradient flow and we conjecture that it might be the critical aspect of DP-SGD that allows convergence to robust network.
9

---

Under review conference paper at ICLR 2023
REFERENCES
Jason M Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. arXiv preprint arXiv:2205.13710, 2022.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in 11 geometry. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 393-403, PMLR, 28-24]] Jul 2021a. URL httts://proceddigg mmr..
press/v139/ as i2lbb. ht.l]
Hilal Asi, Daniel Asher Nathan Levy, and John Duchi. Adapting to function difficulty and growth conditions in private optimization. In Advances in Neural Information Processing Systems, 2021b.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 464-473, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances Neural Information Processing Systems, pp- 11279-11288, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. arXiv preprint arXiv:200606914 2020.
Raef Bassily, Cristobal Guzman, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Proceedings of Thirty Fourth Conference on Learning Theory, pp. 474-499, 2021.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from log-concave distribution with projected langevin monte carlo. Discrete and Computational Geometry, 59, 06 2018. doi:
Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal Computing, 47(5):1888-199) 2018
Alexandre Cabot, Hans Engler, and Sébastien Gadat. On the long time behavior of second or- der differential equations with asymptotically small dissipation. Transactions of the American Mathematical Society, (61(1))59833-611, 2009.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(Mar):1099-1109, 2011.
Xiang Cheng and Peter Bartlett. Convergence of langevin memc in kl-divergence. In Firdaus Janoos, Mehryar Mohri, and Karthik Sridharan (eds.), Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pp. 186-211. PMLR, 07-09 Apr 2018. URL http::ttt////c htttttss://pocccc...oooo ml www.:mww....aae.mmmmmmmmmmmmmr wwt.p/pwwws..e.eeeeeeeee.e www.ghha.nnn...e... hhtml
10

---

Under review conference paper at ICLR 2023
Xiang Cheng, Niladri Chatterji, Yasin Sbbasi-Yadkori, Peter Bartlett, and Michael Jor- dan. Sharp convergence rates for langevin dynamics in the nonconvex setting. arXiv preprint arXiv:1805.01649. 2018.
Sinho Chewi, Murat A Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang. Analysis of langevin monte carlo from poincar e to log-sobolev. arXiv preprint arXiv:2112.1266,, 2021.
Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential sion and noisy gradient descent. In Advances in Neural Information Processing Systems, 2021.
dynamics of langevin diffu-
Arnak S. Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- concave densities. Journal of the Royal Statistical Society. Series B (Statistical Methodology), 79(3)6651-676, 2017. ISSN 13697412, 14679868. URL http://www pastor.org/sta.... otggstable////////o../.. 44681805
Kumar Avinava Dubey, Sashank Reddi, Sinead A Williamson, Barnabas Poczos, Alexander J Smola, and Eric P Xing. Variance reduction in stochastic gradient langevin dynamics. Advances in neural information processing systems, 29, 2016.
Alain Durmus and Éric Moulines. Sampling from a strongly log-concave distribution with the Unadjusted Langevin Algorithm. Preliminary version, April 2016. URL https://hal,
archives Sechives-ouvetee www.reesssvveeees.tooo fr/hal -
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 (0044)211--07 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in EUROORIP, pp. 486-503, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Proc. of the Third Conf. on Theory of Cryptography (TCC), pp- 265-284, 2006b. URL http: doi. wtt../......///11100/11111133311
Murat A Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with dis- cretized diffusions. Advances in Neural Information Processing Systems, 31, 2018.
Murat A. Erdogdu, Rasa Hosseinzadeh, and Matthew S. Zhang. Convergence of langevin monte carlo in chi-squared and renyi divergence, 2021.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 59th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 521-532, 2018.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. Proc. of the Fifty-Second ACM Symp. on Theory of Computing (STOC'00), 2020.
Yuanyuan Feng, Lei Li, and Jian-Guo Liu. Semi-groups of stochastic gradient descent and on- line principal component analysis: properties and diffusion approximations. arXiv preprint arXiv:1712.06509, 2017.
11

---

Under review conference paper at ICLR 2023
Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence anal- ysis of discretized langevin memc. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and
H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7222-7233. Curran Associates, Inc., 2020. URL
c82 F pap.eeopor0raee22aaaaaaeeeeepee wwtp://nnerrricrreeeeoeee copuuipps.cc/pppee/220000
Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mech- anism. arXiv preprint arXiv:2203.00263, 2022.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML'16, pp. 1225-1234. JMLR.org, 2016.
Harold, G Kushner, and George Yin. Stochastic approximation and recursive algorithm and applications. Application of Mathematics, 35, 1997.
Thomas P. Hayes. A large-deviation inequality for vector-valued martingales. 2003.
Bin Hu and Laurent Lessard. Dissipativity theory for nesterov's accelerated method. In International Conference on Machine Learning, pp. 1549-1557. PMLR, 2017.
Wenqing Hu, Chris Junchi Li, Lei Li, and Jian-Guo Liu. On the diffusion approximation of non- convex stochastic gradient descent. Annals Mathematical Sciences and Applications, 4(1), 2019.
Kiyosi Itô. 109. stochastic integral. Proceedings of the Imperial Academy, 20(8):519-524, 1944.
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. To- wards practical differentially private convex optimization. In 2019 IEEE Symposium Security and Privacy (SP), 2019.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pp. 25-1, 2012.
Walid Krichene and Peter L Bartlett. Acceleration and averaging in stochastic descent dynamics. Advances in Neural Information Processing Systems, 30, 2017.
Walid Krichene, Alexandre Bayen, and Peter L Bartlett. Accelerated mirror descent in continuous and discrete time. In NeurIPS. Curran Associates, Inc., 2015.
Walid Krichene, Alexandre Bayen, and Peter L Bartlett. Adaptive averaging in accelerated descent dynamics. Advances Neural Information Processing Systems, 29, 2016.
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in sub- quadratic steps. Advances in Neural Information Processing Systems, 34, 2021.
Nurdan Kuru, S. ilker Birbil, Mert Gurbuzbalaban, and Sinan Yildirim. Differentially private ac-
celerated optimization algorithms, 2020. URL
Paul Langevin. Sur la théorie du mouvement brownien. Compt. Rendus, 146:530-533, 1908.
Don S Lemons and Anthony Gythiel. Paul langevin's 1908 paper "on the theory of brownian motion"("sun la théorie du mouvement brownien," cr acad. (paris) 146, 530-533 (1908)). American Journal of Physics, 1997.
12

---

Under review as conference paper at ICLR 2023
Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, pp. 2101-2110. PMLR, 2017.
Stephan Mandt, Matthew D Hoffman, and David M Blei. Stochastic gradient descent as approxi- mate bayesian inference. arXiv preprint arXiv:1704.0425: 2017.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06966; 2017.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07,, pp- 94-103. IEEE, 2007.
Panayotis Mertikopoulos and Mathias Staudigl. On the convergence of gradient-like flows with noisy gradient input. SIAM Journal on Optimization, 28(1):163-197, 2018.
GN Mil'steen, Approximate integration of stochastic differential equations. Theory of Probability & Its Applications, 19(3):557-56,, 1975.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEEE, 2017.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Brendan O'dongguue and Emmanuel Candes. Adaptive restart for accelerated gradient schemes. Foundations of computational mathematics, 15(3):715-732, 2015.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr
computational mathematics and mathematical physics, 4(5):1-17, 1964.
Maxim Raginsky and Jake Bouvrie. Continuous-ting time stochastic mirror descent on a network: Variance reduction, consensus, convergence. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp. 6793-6800. IEEE, 2012.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Proceedings of the 2017 Conference on Learning Theory, pp. 1674-1703, 2017.
Théo Ryffel, Francis Bach, and David Pointcheval. Differential privacy guarantees for stochastic gradient langevin dynamics. arXiv preprint arXiv:2201. 11980, 2022.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In International Conference on Machine Learning, pp. 71-79, 2013.
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In 2017 IEEE Symposium on Security and Privacy (SP), pp. 58-77. IEEE, 2017.
Shuang Song, Kamalika Chaudhuri, and Anand Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 148-248. IEEE, 2013.
Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing clipped gradient descent on convex generalized linear problems. arXiv preprint 217 2020.
13

---

Under review conference paper at ICLR 2023
Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy, arXiv preprint arXiv:1501 150.::999..00 2015.
Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), Pp. 552-563. TEEE, 2017.
Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nesterov's accelerated gradient method: theory and insights. Advances in neural information processing systems, 27, 2014.
Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly optimal private lasso. In Advances in Neural Information Processing Systems, 2015.
Hiroshi Tanaka. Stochastic differential equations with reflecting boundary condition in convex regions. Hiroshima Mathematical Journal, 9(1) - 177, 1979. doi: http991//mmm1226111111
URL
32917 3tt.:....222mmmmmmmeeeee//21 //tpm/mm211221112233
Belinda Tzen, Tengyuan Liang, and Maxim Raginsky. Local optimality and generalization guaran- tees for the langevin algorithm via empirical metastability. In Conference On Learning Theory, PP. 857-875. PMLR, 2018.
T. van Erven and P. Harremos. Rényi divergence and Kullback-Leibler divergence. IEEE Transactions on Information Theory, 60(7):3797-3820, July 2014. ISSN 1557-9654. doi: 10.1709/ TIT.2014.232500..
Gal Vardi, Gilad Yehudai, and Ohad Shamir. Gradient methods provably converge to non-robust networks. arXiv preprint arXiv:2202.0434 2022.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL
Sebastian Vollmer, Konstantinos C Zygalakis, and Yee Whye Teh. Exploration of the (non-) asymptotic bias and variance of stochastic gradient langevin dynamics. The Journal of Machine Learning Research, 17(1):5504-558 5544, 2016.
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pp. 6526-6535. PMLR, 2019.
Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 113(47):B7351- E7358, 2016.
Ashia Wilson. Lyapunov arguments in optimization. University of California, Berkeley, 2018.
Ashia C Wilson, Ben Recht, and Michael I Jordan. A Iyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-34, 2021.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey F. Naughton. Bolt- differential privacy for scalable stochastic gradient descent-based analytics. In Semih Sali- hoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu (eds.), Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD, 2017.
14

---

Under review as conference paper at ICLR 2023
Min Yan, Extension of convex function, 2012. URL Bttpss//aaxx...or////1000...
15

---

Under review as conference paper at ICLR 2023
A OTHER RELATED WORK
Work on optimization: Although optimization methods in computer science have been mostly discrete, there is a vast literature that studies optimization from continuous time dynamical point of view, with the earliest example being the mirror-descent (see the discussion in Nemrivosky and Yudin [Nemirovskij & Yudin 1983 Chapter 3)) and Polyak's momentum method (Polyak) [164). In fact, Polyak in his 1964 paper motivated his approach using heavy ball moving in a potential and used this physical intuition to give rigorous proof for quadratic loss. More recent works have also shown a closer connection between gradient flow and gradient descent (Wilson 2018) and between accelerated methods and second-order ordinary differential equations by taking a variational perspective (Hu & Lessard 2017: Li et al.; 2017; Su et al., 2014 Wibisono et al., 2016 Wilson et al. 2021). This, in the case of the unconstrained case, can be interpreted as a damped non- linear oscillator (Cabot et al. 2009). This observation has led to fruitful works to get an averaging interpretation of accelerated dynamics (Krichene et al. 2015 2016 and also a comerstone of the "restarting" " heuristic (O'donoghue& & Candes] 2015).
The idea of approximating discrete-time stochastic algorithms by continuous time equations can be traced back to the vast literature of stochastic approximation theory. We refer the readers to the excellent monograph by Harold, Kushner and Yin on the same topic (Harold et al., 1997). In optimization theory with machine learning as the motivation, the earliest work to the best of our knowledge that studied the dynamical properties of stochastic gradient descent algorithms the independent and concurrent works of (Li et al., 2017 Mandt et al., 2017 Vollmer et al.) 2016). Li et al. (2017) and Mandt et al. (2017) independently gave the first asymptotic convergence of stochastic gradient descent and momentum method as an approximation to stochastic differential equation while Vollmer et al. (2016) gave non-asympootic bound on convergence of the stochastic gradient LD algorithm by using the Poisson equations.
The idea of discretizing stochastic differential equations (and by extension stochastic gradient de- scents and its variants) can be dated back to the seminal work of Mil'shejj (175) who performed an extensive numerical analysis of stochastic differential equations. Since then, several works have studied continuous time gradient descent (Hu et al.) 2019 Feng et al. 2017), mirror descent (Mer- tikopoulos Staudigl 2018 Raginsky Bouvrie 2012), and stochastic variance reduced gradient LD Dubby et al. 2016) for Bayesian posterior inference.
Some attempts have been made to even study the non-convex setting, considering dissipative loss functions (Raginsky et al. 2017) as well as acceleration (Krichene & Bartlett 2017) for the vanishing noise limit. In recent work, Tzen et al. (Tzee et al. 2018) introduced the concept of meta-stability to study the generalization properties of L. nonconvex functions. This was further generalized and extended by Erdogdu et al. (Erdogdu et al. 2018).
Work on sampling: Central to this has been the use of Langevin dynamics that has played a sig- nificant role in sampling algorithms. A large line of recent work (including e.g., Dalalyan (2017); ; Durmus & Moulines (2016); Cheng & Bartlett (2018); Cheng et al. (2018); Vempala & Wibisono (2019); Ganesh & Talwar (2020); Erdogdu et al. (2021); 7 Chewi et al. (2021) show that using the Langevin dynamics, under certain assumptions (otten strong convexity and smoothness or vari- ants thereof) one can efficiently obtain an approximate sample from the stationary distribution. In particular, the gradient oracle complexity of these results is often linear in the dimension and inverse polynomial in the approximation error. The error metric varies from paper to paper; orig- inally, total variation distance, Wasserstein-distance and KL-divergences were more commonly studied but starting with Vempala & Wibisono (2019), recent works have focused on Rényi diver- gence bounds.
16

---

Under review as conference paper at ICLR 2023
Work on DP and optimization: The connection between dynamical systems and differential pri- vacy is also not new. Chourasia et al. (2021) and Ryffel et al. (2022) study discretization of the LD algorithm as DP-(Stochastic) Gradient Langevin Dynamics (DPSGLD). They show that un- der smoothness and strong convexity on the loss function (0; D), the privacy cost of DP-SGLD converges to a stationary finite value, even when the number of time steps goes to co. Wang et al. (2019) used the result by Raginsky et al. (2017) to prove sub-optimal excess empirical risk of
p (1/6) for non-convex loss functions. In concurrent, and complementary work on con- log(1))
vex losses, Gopi et al. (2022) study private optimization and show the universality of exponential
mechanisms for both stochastic convex optimization and empirical risk minimization. Their anal-
ysis takes the sampling perspective when the diffusion process has completed.
is probably important mention that objective perturbation (Chaudhuri et al., 2011 Kifer al., 2012) can be potentially thought of as a (near) universal algorithu for the problem classes con- sidered in this paper, albeit the following two caveats: i) The instantiation of the algorithm for e-DP and (e, 8DD require two different noise models to be drawn from, namely, Gamma distribu- tion, and Normal distribution, and ii) It requires the loss functions ((;-)) to be twice-continuously differentiable, and (0; to have a near constant rank. As mentioned in the remainder of our paper, Langevin diffusion does not require any such assumptions.
NOTATION AND PRELIMINARIES
In this section, we give a brief exposition of the concepts and results required used in the rest of the paper. In Table 2 we provide summary of all the notation used in the paper.
Background on Langevin dynamics. One of the important tools in stochastic calculus is Ito's lemma (Iōō] 1944). It can be seen as the stochastic calculus counterpart of the chain rule and be derived from Taylor's expansion and noting that the second order does not go to zero under quadratic variation:
1944)). Let x; E Rp be governed by the Langevin diffusion process dx; H4 dt + ot dWe, where We is the standard Brownian motion in p-dimensions, be E RR the drift, and of E R is the standard deviation. We have the following for any fixed function f IR + R:
Lemma B.1 (Ito's lemma Itō
))
of
P pf(x) dx?
df(x:) = V (xxxx
+
dt + o+ (Vx=x,(xx,
2
Here, V x=x corresponds to
evaluated at x
dxy
dxp
Rényi divergence and differential privacy. Rényi divergence is the generalization of KI. diver- gence to higher order and satisfies many useful properties (van Erven & Harremos 2014). More formally,
Definition B.2 (Rényi Divergence). For 0 < < c0, # 1 and distributions P, Q, such that supp(P) supp(Q) the RéRén divergence between P and Q
IIn particular, we can always ensure twice differentiability by convolving the loss function with the bump kernel (Kifer et al. 2012), and then make the smoothness parameter finite but arbitrarily large which does not affect the Lipschitzness.
17

---

Under review conference paper at ICLR 2023
Notation
D (1y.... ,u
data set data distribution domain set of data
D
T
C
R
convex set/ aetaparameter space
loss function
L
empirical loss function
RiskERM
excess empirical risk
Risksco
excess population risk
If!
strong convexity parameter
M
smoothness parameter
L
Lipschitz constant
gpriv
private model output
g*
optimal model
B;
inverse temperature
Potential/Lyypanoo function
W;
standard Brownian motion
Ra(s.)
Renyi divergence order a
T
continuous time
A 0
is positive semidefinite
A A
A- B positive semidefinite
Ip
p x p identity matrix
Table 2: Notation Table
1-1 In / (U)
P(x)a Q(x)a-Iax dx
P(x)
R. (P,
In
E
4-1
Q(x)a
The x-Rényi divergence for (resp. oo) is defined by taking the limit of (P Q) as a approaches (resp. co) and equals the KL divergence (resp. max divergence).
We next define differential privacy, our choice of the notion of data privacy. Central to the notion of differential privacy is the definition of adjacent neighboring datasets. Two datasets D and D are called adjacent if they differ in exactly one data point.
2006b a ). A randomized mechanism M D > R said have (e, (e, -dif-ffrrretttal privacy or (E, for short, if for any adjacent D, D' D and measurable subset S C R, it holds that
Definition B.3 (Approximate Differential privacy (Dwork et al.
Pr(M(D) E S) S (PH(M(( S +
When 0, it is known pure differential privacy, and we denote it by s-DP.
Definition B.4 (Renyi Differential privacy (Mironov 2017 ). A randomized mechanism M : D + R
is said have (Rém) differential privacy, or (a, (x,E)-RDP for short, if for any adjacent D, E D holds that
R (c(M(D),M(D)) S.
It is easy to see that eDDP is merely eoo,e)-RDP. Similarly, the following fact relates (e, to (a, -DDD
18

---

uDD,r)) If is continuous, we Under review conference paper at ICLR 2023
Fact B,5 ((Mironov 2017
Proposition 3)). If M satisfies (a,e)-RDP, then M is (e log1/6
a-1 8)-
differentially private for any
1.
Rényi divergences satisfy a number of other useful properties, which we list here.
Fact B.6 (Monotonicity (van Erven & Harremos 2014 Theorem 3)). For any distributions P, and 0 5 &1 I 42 we have Rxy (P,Q) (00))RRs) Raz(",Q).
Fact B.7 (Post-Processing (van Erven & Harremos, 2014 Theorem 9). For any sample spaces X,y, distributions P, P.Q over X, and function A
have R (f()())((())) S Ra (P.Q).
Lemma B.8 (Gaussian dichotomy (van Erven & Harremos, 2014 Example 3)). Let P Pix P2
... and Ω = 2 x Q2 x .., where Pi and Q are unit variance Gaussian distributions with mean and V,, respectively. Then
R₂ 21) 2 2 vi)²
and by additivity for > O,
Ra (P,, 2) a 2u
Σ (1i - -vi) 2
As a corollary, we have:
||x
Ra (N N(x, (1p)) 2
20
N2 be ar- bitrary sample spaces. For each E [K], let fū A(X;-1) > (Xx) be maps from distributions over X;-1 to distributions over X; such that for any distribution X, over X; 1, Ra Ra(,,X, 1).f((X, 1)) S Ej. Then, for F,F', ((%)) + ((X)) defined as F(.) = (..ff-((.....)))))
Fact B.9 (Adaptive Composition Theorem (Mironov 2017 Proposition 1)). Let No, ,,...,
and F'(.) = ((.
we have R2 (F(o)), F' (Xo)) 1 any Xo E A(X)).
Fact B.10 (Weak Triangle Inequality (Mironov
2017 Proposition 11)). For any a 1, 9 1 and
distributions P2, P3 with the same support:
a- 1/1 a a- RRa (P,, P2) R Ra--1 (P2, P3).
(R( S
We discuss two differentially private mechanisms for optimization in this paper. The first one is the exponential mechanism. (McSherry & Talwar 2007). Given some arbitrary domain D and range R, the exponential mechanism is defined with respect to some loss function, f. D
IR. Definition B.11 (Exponential mechanism (McSherry Talwar 2007)) ). Given privacy parameter e, the range Ri and loss function é D x R + IR, the exponential mechanism samples a single element from based on the probability distribution
e (a((D)))22)
(T(
Ercore d(DDr)/2
where Dg is the sensitivity of defined as := = max Dwnty instead sample from the distribution with pdf:
rCB
Po(r) =
JrEoR e e((D))/2d.ddr
19

---

Under review conference paper at ICLR 2023
Algorithm 1 Differentially private stochastic gradient descent (DP+SGD) (Bassily et al. 2014)
Require: Data set D {di,-.. duh. loss function: l C x D - R, gradient f2-norm bound: L,
constraint set: C C R², number of iterations: T, noise variance: o², learning rate: 1)-
1: Choose any point fg C. 7
2: for .,..., 7 - do
3: Sample di uniformly at random from D with replacement.
4: Vgpriv f Vi(0;;d)) + +N (0, where x² 871. log(1/8)
5: 0(+1 + 1le (0+ t7 V@priv) ), where Ilc(v) arg min || 0112-
DEC
6: end for
7:
return 8:.
The second algorithm that we discuss is the stochastic gradient descent used in Bassily et al. (2014) and presented in Algorithm The algorithm can be seen as noisy stochastic variant of the classic gradient descent algorithm, where stochasticity comes from two sources in every iteration: sam- pling of de and explicit noise addition to the gradient before the descent stage.
We use the result by Steinke & Ullman (2017) for our lower bound proof. We use their equivalent result for empirical mean (see equation (2) in Steinke Ullman (2017)) and for privacy parameters
(c, using standard reduction (Bun et al. 2018 Steinke Ullman 2015
Theorem B.12. Fix n,s,k I. Set
8 maxx (2,288 Let pl,..., Beta B) and let X (x,,'., _x,} be such that X; E {0,1}* for all E [m]], Xt,j is independent (conditioned on P) and E[x;,] pl for all i E [n] and [s]. Let M () + {0, 1 be (1, diffferenttl private.
log
Suppose [|M(x)] [IMx)]1 for all X with probability 1 and
k
Σ
XL
Xi,u
M
n
sc [S
20"
KE
MixN=1
Then n E Ω (o)l)g(i))
Results from statistics and machine learning: We will sometimes use Fatou's lemma in our proofs. The form we will use is stated here for convenience:
Lemma B.13 (Fatou's Lemma). Lef {Xi} be a sequence of random variables such that there is some constant e such that for all Pr[X; 2 c) 1. Them:
E lif X 1-000
lim [Xi].
For our SCO bounds, we will use uniform stability. Uniform stability of learning algorithm is notion of algorithmic stability introduced to derive high-probability bounds on the generalization error. Formally, it is defined as follows:
Steinke Ullman 2017) present their result the terms of population mean and privacy parameters (1,
20

---

Under review conference paper at ICLR 2023
Definition B.14 (Uniform stability (Bousquet & Elisseeff 2002).. A mechanism M is p(n) Juniformyy stable with respect to & if for any pair of databases D, D' of size n differing in at most one individual:
sup
EE (<(M(D), EM [((M(D'), a,]]] s u(n).
dET
In this paper, we will need the following result. Lemma B.15 (Bousquet Elisseeff (002)). ) Suppose M -mifforny stable. Then:
ED-D= (Rissss <
DDDDD (RiskERM (M(D))] +n))
C RÉNYI DIVERGENCE BOUND FOR LANGEVIN DIFFUSION (LD)
This section is devoted to proving the divergence bounds between two LD processses when run on neighboring datassess. forms the basis of the privacy analysis the rest of the paper.
Lemma C.1. Let Oo, 0 have the same distribution Do, Or be the solution to 2 given O and database D, and let 8 be the solution to (2) given Og and database D', such that D ~ D'. Lef @ 0,7] be the distribution of the trajectory (0)))) Suppose we have that | L(0; D) VL(0; s A for all O. Then for all a 2 1:
S ad2 T R₂ (7 (.7). (O.r)) 4
Bidt.
The idea behind the proof is to use bound on the divergence between Gaussians and RDP com- position to provide bound on the divergence between the projected noisy gradient descents on datasets D and D'. Then, taking the limit the step size in gradient descent goes and applying Fatou's lemma (Lemma B.13 we get the bound above.
Proof. For ease of presentation, we will show divergence bound between O Or which are the distributions of 0, 6,, and then describe how to modify the proof to show the same bound between
@ (.. 0 (0.7) [
Let Y D,m, be map from (distributions over) IRP to (distributions over) IR that takes the point 0
iT/m
to the distribution TTe N 0
Bidt
where ITe is the E2-projection
(i-1)T/m
into C. is well known (see e.g. Lemma
B.8 that:
ON a
<|x1||
20
So by post-processing (Fact B.7 and the Lipschitzness assumption, Ra (YDDm Y (i)m bounded by
21

---

Under review conference paper at ICLR 2023
iT
iT/m
R
N
Bidt
2T C D),
N e
f
Bidt
VL((;DD),
2T
m
m
1)T/m
1)T/m
iT/m
2T
T (VL(0:D) (())
R
N
0,
II
N
Bidt
m
m
1
/m
Bidt
a12
(i-
T/m
Let D.m denote the composition Y D.m, o Y D,mm-1 o... DDm,111 By Fact B.9 we have
R Y D,m (O)), Y Dr (Op)) < max { Ra (Y (YD,m,()))) Y D m. (0))
8
Plugging in the bound on Rs ( Dm) (0), Y m. (0)), we get
2
iT/m
Ra (m Y ((o)) -
aA2
m
Bidt
4
T
1)T/m
Note that θ7 -oo Y D.m (O), and 0 m Y (Oo). Since exp((a (P, 2)) monotone function of R₂ (P, 2) and is the expectation of positive random variable, by Fatou's lemma we have:
R₂ (O,, ØG) S
lim R₂ (. Y (Ooo) m y00
2
aA2 j B7
iT m
aA2
lim
Bidt
4
(i- 1)T//m
This gives the bound on R, (O,, 0/)). To obtain the same bound for R, (, 0 (,7)) ) modify Y mim,i so that instead of receiving (i-//T/m and outputting iTT/m it receives the joint distribution / and outputs (m Josisi by appending the (also jointly distributed) variable
im/m
T m
i ITc
N
Bydt
VL(O
D),2
D),2
(i (1-1)m/m
That is, we update 4 DDmm so it outputs the distributions of all iterates seen so far instead of just the distribution of the last iterate; the limiting value of the joint distribution 10/T/mJosjaa is then + (0,7] according to eg. (2, and the same divergence bound holds.
22

---

Under review as conference paper at ICLR 2023
D LD AS EXPONENTIAL MECHANISM AND DP-ERM UNDER E-DP
In this section, we study the privacy-utility trade-offs of LD when viewed as variants of exponen- tial mechanism (McSherry& & Talwar 2007). Using this view point we show that LD can achieve the optimal excess empirical risk bounds for fz-Lipschitz losses, including non-convex, convex, and strongly convex losses.
D.1 BOUND FOR CONVEX LOSSES
We revisit the result from Bassily et al. 2014 for convex losses, and quote the result for complete- ness purposes. Notice that the privacy guarantee in Theorem D.1 does not rely on convexity.
Algorithm 2 Exponential mechanism
Input: Loss function L, constraint set C C R with bounded diameter, Lipschitz constant L, number of iterations k, privacy parameter e, data set of n-samples.
1: Sample and output point gpriv from the constraint set C w.p. exp 222][( [(0;
Theorem D.1. Assume each of the individual loss function in L( D) is L-Lipschitz within the constraint set C, individual loss function E(0;-) is convex, and the constraint set C is convex. Then, Algorithm 2 is E-differentially private. Furthermore, for @priv as specified in Algorithm 2
over the randomness of the
algorithm,
Lp L.- -P111C1l2 ( EN
Egeri [RiskERM (@priv)
=0 =0
Equivalence of Algorithm 2 and Langevin diffusion: The following lemma, which is implied by, e.g. (Tanaka 1979 Theorem 4.1), shows that one can implement Algorithm 1 using only solutions (2) are efficiently sampleable.
eq. (2) note that this does not necessarily mean solutions to eq.
Lemma D.2. Let L. be M-smooth function for some finite M. Then if B. B for all t, then the stationary distribution of 2 has pdf proportional
1 E C), where I (-) is the indicator function.
We recall that one can ensure smoothness by convolving C (appropriately extended to all of R²) with the Gaussian kemnel of finite variance (Feldman et al., 2018 Appendix C). In particular, since we only need M to be finite, we can take the convolution with the Gaussian kernel (0, A² for arbitrarily small A > 0, and in turn the result of the convolution is L/ L/A-smooth (which is perhaps arbitrarily large but still finite) and differs from L by an arbitrarily small amount everywhere in C.
D.2 BOUND FOR STRONGLY CONVEX LOSSES
Our algorithm for strongly convex losses, given Algorithm 3 is an iterated version of the expo- nential mechanism. Again, we note that Algorithm can be implemented using only the Langevin Diffusion as a primitive.
Theorem D.3. For any E, suppose we run Algorithm with k = 1 (ooglo(((=))) ell (p+log )1, and e; e/2 Assume each of the individual loss function in L(e; D) is L-Lipschitz within the constraint set Co. Then Algorithm is E-differentially private. Additionally, if the loss function L(0; D) is m-strongly convex, and the consTraint set Co is convex, then over the randomness of the algorithm, the output 0g of Algorithm satiisiie
(0+)== =0 105 + plogn)
E [RiskERM (0:))
m22n²
23

---

Under review conference paper at ICLR 2023
Algorithm 3 Iterated Exponential Mechanism (ITEAAEE--XX--MIHHANSS)
Input: Loss function L, constraint set Co C RP with bounded diameter, Lipschitz constant L, strong convexity parameter m, number of iterations k, privacy parameter sequence { and data set D of n samples.
1: io to k do
Sample 8 from C- with probability proportional to exp( 27 27-10
[(0; D)).
c-+ c 110 -0112 S
cLlp 3logn) C- ll2
3:
mey
4: end for
5: return 0g
The theorem follows by solving a recurrence for ||C:ll2 to bound the diameter of the final set Ck- Then, we show that the minimizer over Co also in Cx-1 with high probability, so the analysis of the exponential mechanism gives the theorem. We also note that similar result is achieved by Bassily et al. 20014). However, we improve the p2 log in their result to p² + p log and only need the exponential mechanism as a primitive (whereas their algorithm requires computing the minimum of C).
To bound the prove Theorem D.3 we first need the following lemma, which shows that with high probability we choose series of C; that all contain the optimal for Co-
Lemma D.A. Suppose we sample 0 from the convex constraint set C C IRP with bounded diameter with
probability proportional to exp (- 22||C
Em ((0; where L(;;D) is an m-strongly convex function. Let
arg mingec L(0; D). Then for any z and for some sufficiently large constant c we have
cL(p + |C112 > 1-2
Pr
110
0-112
S
men
The lemma follows from a tail bound on the excess loss of the exponential mechanism, and using m-strong convexity to translate this into distance bound. The proof is given below.
Proof of Lemma D.4 By e.g. the proof of (Bassily et al. 2014 Theorem III.2), we know that for some
sufficiently large constant
cL1|C|12 (p +1) 2 2-!
Pr [(0:D) L(0":D)
(4)
2en
We now show that the claim holds conditioned on this event. By optimality of 6* and convexity of C, we know
(VL(0': 0-) 2 0.
(5)
So, by m-strong convexity, we have
cL |CI|
(p +1)
L(0:D) - L(0":)) 2 (VL(O) 8t)
m1
0
8
1112
111
|0
A*
12
2en
2
5
2
24

---

Under review conference paper at ICLR 2023
Rearranging gives the claim.
Given Lemma D4
now prove Theorem D.3
Proof of Theorem
D.3 The privacy guarantee is immediate from the privacy guarantee of the expo-
nential mechanism, composition, and the fact that for this choice of k,,,, we have D E;
Setting = 3 logg in Lemma D.4 in iteration i, letting 0 arg mingec, [(; D), we have that with probability 2 1 n 0, E C₁ and thus 8 = 0/ Then by a union bound, we have that with probability 1 */4 2 1 1 log loglog(en) 0j CR-1 (equivalently, 0f = 02
When this event fails to happen, excess loss is at most I. ||ooll2 and in turn the contribution of this event failing to hold to the expected excess loss is O 7-ICoo lp log log(ee)) which is asymptotically less than our desired excess loss bound. So it suffices to provide the desired expected excess loss bound conditioned on this event. By the analysis of the exponential mechanism, conditioned on this event, we have that
x²a
- (0 (TPPICCAalll)
(LP1ICx-1ll2) )
Eg, [4(0;; D(0))) =0
(6)
EK71
Note that D) minsec, D) by definition, so now suffices to bound ||Cx-1ll2 by L(p logn) To do this, we have the recurrence relation:
men
cL(p + 3log n) ||Ci-1ll2
||ill s V
me;
Solving the recurrence relation for CB-1, we get:
4cc((p + 3lg
1-2 (k-1)
(1(Coll)) (K-1)
k-1 (K-1)
||C 1ll2 -
mn
(7)
1-2 (1-1)
4cc[(p + 3log
(1(Coll))
(K
(2 1k (
men
1=1
We claim the following:
2L
||Coll <
(8)
Let Oglobal be the minimizer of L(0:D) over all of IR. By triangle inequality, there exists a point 0 in Co which at distance at least ||ooll /2 far from fglobal- By m-strong convexity, this implies that the gradient at 0 has f2-norm at least mı ||Coll2 /2. Now, by Lipschitzness over Co, know that the gradient at has fz-norm at most L. This gives us eq. (8)
Using eq.
8 we simplify eq. to
25

---

Under review conference paper at ICLR 2023
1-2-08-1 (2-1)
2L. (20(p++3 3lgg
(2 111))2
||Cx-1l12 -
We have:
k-1 (22 1=1
8-
log2
1(=-
E(++1)2 =
In other words, [7 (21k 11 )2 () is at most 8, regardless of the value of k. Now, using the fact that m /logmm (1) constant, our final upper bound on ||Ck-1ll2 is:
(p (P log
1 1-2 1-2-(k-1)
L(p logn)
1C=-1l1== =
= =0
!/
ER
mEn
Plugging in eq. (6 gives us Theorem D.3
D.3 BOUND FOR NON-CONVEX LOSSES
the loss function is non-convex but still L-Lipschitz, we can still obtain a comparable error bound for Algorithm 2 as long as the constraint set C is convex.
Theorem D.5. Assume the constraint set C C R' with bounded diameter is convex, and each of the individual loss function in L(0; D) is L-Lipschitz within C. Then for p S en/2, over the randomness of Algorithm the output gpriv satisfies
E RiskERM (Opriv) 0] =0
<pp (0
Lp-11|C11 En
En p ))
log
Note that the assumption on can easily be removed: if > en/2, any 0 C achieves (0) < L |||C||2 < 21p 2pp-ICl, [Cliz by L-Lipschitzness. To prove Theorem D.5, we show there is a "good" subset of C, C Good C, with large volume and only containing points with small excess loss. We note that Bassily et al. (0144) also gave an analysis for the continuous exponential mecha- nism on non-convex losses, although their analysis assumes contains an 22-ball of radius > 0, which they use to choose CGood in their analysis. In turn, their error bound is roughly proportional (1g(1/r). In contrast, by choosing CGood more carefully, we remove this dependence on
Proof. By the analysis of the exponential mechanism, for any G we have:
[(ppriv :D]] max L(0, =0
|||CIl = log en
Vol(C) Vol(g) ))
Egpriv
BEG
Let us define G to be
= (0 +
- 0²) ac,0
for some < we will choose later, where 8* is a minimizer of L(e, in C, and ac is the boundary of C. By convexity of C, is contained in C. Furthermore, G is simply C rescaled by
26

---

Under review conference paper at ICLR 2023
in all directions around the point 0* (i.e., if 0* were the origin, 9 would simply be RC), so (1/R)P. So the analysis of the exponential mechanism gives
Vol(C)
Vol(g)
[C(epriv D)]
max (() = ( BEg
( (LpIIC [pp|CCl2
log (R) ))
Eppriv
(9)
En
By L-Lipschitzness of [(0; D) and since G is C rescaled by R, and thus maxøeg ||0 - 0*112 - R ||||l2 we have:
max L) -(0";) ;D) S RL |Cl12-
(10)
Deg
Combining (9) and 10
we get:
RiskERM (OPriv) ) [L(ICCl
P. en
1 R
+ +R)).
ggriv
log
(11)
The above bound is minimized by choosing R R= an theorem.
which is at most by assumption, giving the
E UNIFORM STABILITY OF LD AND OPTIMAL DP-SCO UNDER E-DP
In this section we provide the uniform stability bounds for LD in the setting of e-DP. These bounds combined with excess empirical risk bounds in Section D provide us optimal excess population risk bounds for convex losses and strongly convex losses.
E.1 BOUND FOR CONVEX LOSSES
All our algorithms in the e-DP case are primarily based on the exponential mechanism. Therefore, to get SCO bound, we establish uniform stability of the exponential mechanism regularized losses. To the best of our knowledge, such uniform stability bounds for exponential mechanism were unknown prior to this work. We first recall the following fact about projected noisy gradient descent on strongly convex (and smooth) losses.
Lemma E.1. Let f. be m-strongly convex, M-smooth functions such that [ ((())), S A for all E C. Recall that given convex set C, projected noisy gradient descent on f performs the following random update: sample čt ~ N(0, ((0,021p) and compute 0,+1 = IIc (0; - 7): f(,e) + 5t) Here Te is the Euclidean projection onto C. Let {0r]t, {0]}, be the trajectories given by rumning projected noisy gradient descent on f. respectively starting from the same point 0, and suppose M < 1/ max; fj.. Then for any A
(shared) fixed realization of the noise {5 ||0, 0/12 m
Lemma E.1 is implied by e.g. the proof of (Hardt et al. 2016 Theorem 3.9). We have the following corollanes:
Corollary E.2. If is m-strongly convex and L-Lipschitz, then for any B. such that fd Bidt is finite if 0 0 S b, and any t O, outputting 0, that is the solution to (2) (given some fixed Og independent of L) is 212 -uniformly stable.
Corollary E.3. If is convex and L-Lipschitz, then running Algorithm 2 on the regularized loss function (m; D)= L(e, D) + / |101|2 is 212 -l--unifomlyy stable (with respect to the unregularized loss L).
im
27

---

Under review conference paper at ICLR 2023
The idea behind the proofs is that the uniform stability bound implied by Lipschitzness and Lemma E.1 is independent of I), and so it applies to the limiting distribution as - 0 (giv- ing Corollary E.2) and f + 09, which by Lemma D.2 is the exponential mechanism (giving Corollary E.3 We believe that this proof demonstrates the power of the unified framework that is the focus of this paper; once we have this framework in mind, we can almost immediately obtain optimal SCO bounds under e-DP and also improve on Asi et al. (2021b) by polylog (n) factors.
Proof of Corollary E.2 have
Since the regularizer does not depend on the dataset, D, by L-Lipschitzness
2BL n
(
Fix some 1/
and set = C, -i-- Brdtt o² 2nj in Lemma E.1 and note that the
bound in Lemma E.1 does not depend on o2. We will assume L M-smooth for some finite M, since per the discussion in Section D we can easily replace L with smoothed version of that differs from by an arbitrarily small amount. Lemma E.1 then gives that, 0,, 0 are the result of running projected noisy gradient descent on L using D' respectively (from the same initial 0g), then we have |10: - -61ll < 21. for any fixed realization of the noise { as long as the smoothness assumption is satisfied. Taking the limit as goes to O, the trajectory of this projected noisy gradient descent approaches the solution
RUR
22. Furthermore, taking this limit the smoothness assumption in Lemma E. is trivially satisfied as all 7/: go to O. Therefore, by Fatou's lemma (Lemma ).13), we have the following: for all t, if 8,, ej are the solutions to eq. 2 using D'D' respectively and fixed realization of the Brownian motion, then
2L
|1. 0/112
mn
Taking the expectation over the Brownian motion and using L-Lipschitzness of f, we can conclude that for any and all d E T,
2L mn
, (,(,(((();))) d(O);
Proof of Corollary E.3
Similarly to the proof of Corollary E.2 if 9, o are the solutions to eq. 2 (run
on the regularized loss function 2m) using D, D' respectively with B, f and fixed realizatin of the Brownian motion, then
2L mn'
E [| 0/112] <
and thus
2L2 mn
E (e(ridd( E(e/:d))
Note that the above inequality holds for the unregularized loss. Taking the limit as t - and use Lemma D.2 to conclude that, for Opriv and gpriv' output by Algorithm 2 using D and D', respec- tively,
212
E gpris aari [e(ppriv, ;d) E(ppriv' ;d)] < mm
for all d E
28

---

Under review conference paper at ICLR 2023
Then, from Corollary E.3 and Theorem D.1 we have the following theorem:
Theorem E.4. Let (priv be the output of Algorithu 2 when run on the regularized loss Lm (0;
C),:D)+ |101|2 Ifecch is convex and L-Lipschitz, then for m 11 we have:
Lp Illlll (
(<PIICI12
L 1|C112
Eppriv RRisksco (Opriv )] =
EN
n
Furthermore, outputting gariv (e, (dife-diffrrettiilll private.
Proof. Assume wlog that 0 e C. Let 8 be the empirical minimizer of C. If m S constant does not change by more than constant factor, so we have by Theorem D.1. |C],
L the Lipschitz
Egpriv [c (@priv, :D] (0"; S Egpiv (Cm (OPriv DD] min L. (0: = O (
Lp ||Cll2
BEC
en
The functions f. and L differ by at most " ||C||2 everywhere in C, so in turn:
Egrii RRskERRM (Øpriv - -0
Lp ( m [IC113
en
Finally, we apply the uniform stability bound from Corollary
E.3 to get:
Lp ||C|12
1
E Egrriv [Risksco (@priv )
+ m |Cc11 +
en
mn
The theorem follows by setting m
[Cllavn'
E.2 BOUND FOR STRONGLY CONVEX LOSSES
Under strong convexity, using a similar proof to the proof of Theorem E.4 we can obtain near- optimal DP-SCO bounds for e-DP.
We first show that the empirical minimizer close to the population minimizer with high proba- bility:
Lemma E.5. Let l be m-strongly convex function and C C R² be convex set with bounded diameter such that for any d, 0,
VV(():)) EL-D [V((O:d)]ll s A, and let 0" arg mingec Ed-D [e(0:d)] and gemp arg mingec E(0; D). Then for D D", with probability 1 B, we Juve::
A (1/((111)) m m/nn
mp - -01112 =0
29

---

Under review conference paper at ICLR 2023
Proof. Consider a function ? over I' which has gradient Vē(0)= Ve(ll((()) + m(0 Ilc())). We will show that the assumptions on & in the lemma statement also hold for f, and that the distance between the empirical and population minimizers of & over R dominates the distance between the empirical and population minimizers of & over So proving the lemma holds for l and R implies it holds for l and C, i.e. it suffices to prove the lemma assuming C = IRP.
By m-strong convexity of in C, ē is also m-strongly convex². Also, for any d, we have [(((ed)) Eg-D [V((ed))]l2 vē(0;d) EDD V(((;d)) || A.
So, we have shown the assumptions in the lemma hold on as desired.
From strong convexity of É, the empirical/population population minimizers of i over R' are the unique points with gradient 0. This gives us that for any D, the empirical minimizer of E over IRP is equal to
1 Ve(erMp,D)
@emp := rum
m
where gemp is the minimizer of E(0; D), and the population minimizer of EAdD [((ed)] is
0" = 0" EA-D [V](O";
Note that convexity either V D) = or V((B<mp; is tangent vector of at pemp (and the same is true for 0*). In turn, gemp [cc (fmp) and 0* = [0" and since projection non- expansive operator, [ 0- Z ||@mmp 0- 1|2- This shows the distance between minimizers of
? dominates the distance between minimizers of é as desired.
We now turn to proving the lemma assuming C = IR. If
R then EL-D (((0; 0. Now, by the assumptions in the lemma and vector Azuma inequality (see e.g., Hayes 2003
we have ||V](0) = O Av AAyloi/// with probability - over D. Furthermore, we know v'n
v (( D) = 0 by strong convexity and since = IRP. Then by strong convexity, we have
||0" - gemip < [[VE(0r;)) VE(0-mP; D)
|] o A Alog((1/P) m/n
m
m
with probability 1 1 B as desired.
Given Lemma E.5 if we want to ensure the population minimizer rather than empirical minimizer
remains in the sets we choose in Algorithm 3 we just need to choose a slightly larger ball. From
this modification and uniform stability, we get the following DP-SCO bound:
Theorem E.6. Let m, n, p, l be as in lemma E.5
Let 0g be the output of Algorithm except we let the
radius of C, be v ee.pp+3 log C 1l12 + cl /logg instead of V
ccl(p+3 log a] C, ill2
(chosen in Theorem D.3
me: obtain optimal ERM bound). Then
myn
MEE
EE Risksco (0+) -0 0 (L2p 0 m²2n2
(L''p'log logn
L2
+
mn
8This follows since E(0) is m-strongly convex iff 7(0) ||0| is. By m-strong convexity of in C, Z(0) o |012 is convex in C, and then its convexity over IR then follows from e.g. Theorem 4.1 in Yan 2012
30

---

Under review conference paper at ICLR 2023
Proof. Note that by L-Lipschitzness of l in C, we have [[VE(0;)) Eg-D [V((Od))]lz I 2L. By E.5 and a triangle inequality, we have that if c is sufficiently large then the population minimizer of in C; is in C for each i with probability - 2/n². Then by union Cg-1- When this event fails to hold, our excess 2 and so the contribution of this event to the expected excess loss is L loglog(en)
Lemma D.4
Lemma
bound, we have that the population minimizer population loss is (L ||Co|
o TilCaaly log (eg) n²¹
which is asymptotically less than desired bound. So it suffices to provide the desired expected excess loss bound conditioned on this event. We can bound the diameter of Cx-1 similarly to the proof of Theorem D.3 by noting that:
-
muz"
cL(p + llg ||C,-1l2 clylog
11:11 2 max 21
me,1
myn
Then, rolling out the recursion, we have similarly to the proof of Theorem D.3
( (L(pt)ogg))
L Lylog
||c=1ll2=0 =0
mEn
myn
Now, combining Theorem D.1 and the uniform stability bound of Corollary expected excess population loss of 0g compared to the population minimizer over Cg is:
E.3 we get that the
Lp CC1-1ll2
1
L nm
(p² + +p2+plogg
Pv
+1)) =0 -
I.2 log L
En
+
mn
=
+
EVn
me n2
+
mn
the geometric mean of 1² log and 1 and thus En
In the final equality, we the fact that
ev"
Pylog" LV" I max{ 1og An 11. We conclude by noting that conditioned the event the population minimizer over Co is contained in CR-1, 0g has this same excess population loss bound compared the population minimizer over Co.
F LD AS NOISY GRADIENT FLOW AND DP-ERM AND DP-SCO UNDER (E,
We now investigate LD (defined in and ( as noisy gradient flow algorithm (i.e., for finite time T or when is far from convergence). In fact, in Section H. we argue that the setting of parameters operate with, the algorithm could not have converged to limiting distribution in any reasonable sense. In the following, we provide optimal DP-ERM and DP-SCO bounds via LD for both convex and strongly convex losses. All the proofs are deferred to Appendix
F.1 DP-ERM BOUNDS FOR CONVEX AND STRONGLY CONVEX LOSSES
We first provide the excess ERM bounds for the LD in 2 for convex losses.
31

---

Under review conference paper at ICLR 2023
Theorem F.1. Let the inverse temperature B, for all f 0. Then for an appropriate choice of B, T, the
solution to 2 Opriv =r (e, diffeeriffrylntiallyyy private and
L L||C|| v p
RiskERM (Opriv) =0
EN
The proof this theorem can be viewed as a continuous analogue of Shamir Zhang 2013). We sketch the proof here. We define a potential Φr & ||0 - - and use Ito's lemma to analyze the rate of the change of Φt. Rearranging the resulting inequality and using convexity, we then bound the integral of the excess loss of 0; over any interval of time [a, bl. Using techniques similar to those in Shamir & Zhang (2013), we translate this into a bound on the excess loss of 07 in terms of T and B. We use Lemma to choose the value of ß that preserves privacy, and then optimize the resulting bound over
We now provide the excess ERM bounds of LD in 2 for strongly convex losses. To simplify the presentation, we assume only in this theorem alone L satisfies 2m-strong convexity instead of m-strong convexity this does not affect our final bound by more than constant factors.
Theorem F2. Let 0: be the solution to (2) if we set ß: 1a Suppose L is 2m-sstoogly convex. Then
for any e, and an appropriate choice of a, T, for B = a+1 and gpriv = man O,demB, over the
1=1
randomness of the algorithm,
E RiskERM (OPriV) b] =o ( (pL2log(1/0)
pē2n? log(1/0)
m log
en
log
m²2n2
Lvlog(1/8)
Furthermore, outputting Opriv is (e, (e..0-differentialll private.
The proof is fairly similar to that of Theorem F.1 the main differences are that we now define the potential to be proportional to e ||e, 1= instead of ||0 1*1 and there is need to translate to a bound on the final iterate like Theorem
F.2 DP-SCO BOUNDS FOR CONVEX AND STRONGLY CONVEX LOSSES
The uniform stability bound of LD in the case of () follows from taking the limit as the step sizes go in the bound presented in (Bassily et al. 2020 Lemma 3.1):
Lemma E33 Let 0y the solution to 2 time T, and suppose each & L-Lipschitz. Then outputting oy
satisfies y-uniform stability for:
21
Bidt.
Combining Lemma E3 with Theorem
F1 we obtain tight DP-SCO guarantees for convex losses.
Theorem F.4. If each l is convex and L-Lipschitz, then for appropriate choice of Bi, T, for gpriv Or that is the solution to (2, we have:
( V + L
E Egariv Risksso (epriv =0
En
/n
32

---

Under review conference paper at ICLR 2023
We can also combine Corollary E.2 and Theorem F22 obtain tight DP-SCO guarantees for strongly convex losses.
Theorem F.5. Suppose i is m-strongly convex and L- L-Lipschitz, then for an appropriate choice of Pt, T, T,for @priv defined in Theorem F.2 we have;
E Egeri Risksco ((priv) ) =0
( n22
pI. (1/)
log
EN
log (log(118)
pE2n?
)
I.2
(.
mn
In both cases, outputting (priv is (e, (differrirrltllialll private.
G LOWER BOUND ON DP-ERM FOR NON-CONVEX LOSSES
In this section, we show the following lower bound on the excess empirical risk for 1-Lipschitz non-convex loss functions. The lower bound implies that that there is no advantage, in terms of the dependence on dimensions (p), to move from E-DP to (e, 8)-DP.
Theorem G.1. Let S 1, Q(m) < S 1/n OQ), and B(0, 1) be a unit Euclidean ball centered origin. Then there exists 1-Lipschitz non-corvex function L B(O, 1) x X and a dataset [d1,... =dd,, du} such that for every p IN, there is no (effe-dfffeenntially private algorithm A that outputs gpriv such that
1)
D =
L(epriv D)- min L)): = plog (1/8) BEB,(1)
(12)
nE
Proof. We first perform two translations of Theorem B.12 first from (1, 1s) to (e, from Steinke & Ullman (2015) and then from sample complexity to result stated in the terms of accuracy bound. direct corollary of Theorem B.12 with is as follows: for every s E N, no (e.f))diiferenttiall private algorithm input X satislying the premise of Theorem B. 1.12 outputs index j E [s] such that
Xij
max
1
Σ 1=1
Xi,u
0
log me
log (1/8))
(13)
M
HE[$] N
where S and (m)(n) < d - 1/(1+
Using this lower bound on top-selection, we give our lower bound by defining an appropriate non-convex loss function. In particular, we define a packing over the p-dimensional Euclidean ball such that there is an bijective mapping between the centers of the packing and [s]. Then the function attains the minimum at the center of packing which corresponds to the coordinate j e [s] with maximum frequency. Since the size of the a-net is 1/a² and there is bijective mapping, this gives a lower bound using eq. (13).
Let O 1) be the p-dimensional Euclidean ball centered at origin and let a E (0, be constant. Consider an a-packing with centers C = {c1, 02, ... )). It is known that the size of such packing,
9The dataset, D {di, dx) is such that d, e (0, 1) for all i e [m), d is independent (conditioned on P) and B(d.,) pl for all i [n] and / [s]. Here the distribution that is defined in Theorem B.12
33

---

Under review conference paper at ICLR 2023
(() is (4) < N(a) < (2) Let N(a). Further, let f B(0,1) + {1, ,s} be an injective
function defined as follows:
f(0)
;:c
arg min ||e c|2
cCC
In particular, f is the function that maps a point on the unit ball its closest point in C.
We now define our loss function follows:
1 Σ
||0 sill - dij.
[(; D) = 11 d,ED
((0;d;) where ((0;d;) = min c/eC
(14)
For Lipschitz property, note that each loss function is 1/ 1/a-Lipschitz because the gradient when it is defined is just g y-q We prove it formally.
al|a-s;ll2"
Consider any e, in B(), and data point dj E D. We wish to show |E(0;4,) e(0'; S 1 |10 02 We can split the line segment from 0 to 0' into sequence of line segments (0o, 01), (0,, (B),
where to = =0,0z 0', such that for any line segment (0m, mm+1), (0x 0x0
On and 0m+1 share minimizer in C of (1ex dif. 10
a
It now suffices to show (e(Omidi) 2(0m+1idi)l S 1 110m 0 0m ll2 for each m, since then have:
k-1 0lt1l12
1 110 0'112
(((0;d;) 2(0' < [((0mid)) - e(0m+1id;) s
Σ
10mm
m-
(1ل=مill) dif for On and 0m If dij then trivially [((0mid))
Let 9j be shared minimizer of E(e ((0m+17di) < 1 ||0m - em+ Otherwise dij and by triangle inequality, we have:
a
0n c1ll2 |10m11 9ill
|((Omid;)) - E(0m +::d;) =
mm
6m 1ll2-
&
Now let us suppose there is (), differretel private algorithm A that input non-convex function C and data points {d1,- ,x outputs gpriv such that
C(prrvv D)] min L(e; = 0CB(1)
(plog (1/5)
E A
(15)
ne
where D = {dh,.. d.
10 particular, for each e; let B, be the set of points in B(0 such that ej is minimizer of [|0_//la dif-
We can split the line segment from 0 to at each point where it enters or leaves some B, to get this sequence of line segments, and by this construction each line segment's endpoints are both in B, for some
34

---

Under review conference paper at ICLR 2023
We will construct an algorithm that uses as subroutine and solve top-selection problem with an error ollog(s)), contracting the lower bound of Theorem B.12
Algorithm B:
On input X = {x,,-.. xn), invokes A on the function defined by eq. (14 and data points
X to get (priv as output.
Output f(OPriv).
Since the last step is post- post-processing, B (e,0)--iifferentiaal) private. We now show that if A
outputs a Opriv satisfying eq. (15), then j := f(OPri)) satisfies eq. 13 leading to contradiction.
First note that, for any E Cad all 0 Bp(c, a) such that ||0
c|l2 3.
L(;; Σ xis(e) S L))
Therefore,
(
x()";)): == min C(c,X) = min
- Σ xif(()
CEC
CEC
This implies that
f(0") = arg max 15jss
Xi,j
11
which is exactly the top-selection problem. Therefore, eq. 15 implies eq. 13) because p
log(s) S p log (2) and a E (0,1/2) is constant.
H ON THE CONVERGENCE TIME OF LD UNDER (E,O)-DP
In this section provide a discussion into the choice of the time for which LD was run for our ap- proximate DP results. In particular, we will discuss why for convex losses, the optimal runtime in Theorem F.1 is 1/p p, and why for the setting of parameters in Theorem F.1 the diffusion process does not come close to converging to the stationary distribution. We show that such properties are present even in DP-SGD (Bassily al. 2014), when analyzed carefully while taking the learning rate and the number of time steps into account.
On Optimal Time for DP-ERM with Approximate DP: For DP-ERM with convex loss and ap-
proximate DP, our eventual choice of T is |IC|]/ /p, i.e. decreasing in the dimension if ||C||2 fixed. We note that this phenomenon is not unique our analysis; e-g., for learning rate 1) 0, the eventual value of Ty in the same setting in Bassily et al. (2019) also is roughly proportional 1/p. This perhaps counterintuitive, as in the non-noisy setting, the amount of time one runs gradient descent for is generally independent of the dimension. We can provide some intuition for this phenomenon from the perspective of the Langevin diffusion.
As an example, consider the loss function (()) ||@||,, and suppose C = B(0,1), ie. an & ball of radius 1 centered at the origin. For privacy, per Lemma C.1 we will set ß & 1/VT vp. At
35

---

Under review as conference paper at ICLR 2023
B))
dWL.
K
d0t
- -VL(O,)dt
Figure 1: An abstract visualization of how the gradient drift and Brownian motion counteract each other in Langevin diffusion for L(0; D) =10112 C ( 1) is the unit Euclidean ball centered at O. The blue arrow shows the integral of gradient drift over time 17. The red arrow shows the integral of Brownian motion over time ! perpendicular to the gradient drift. In the left picture, we can see that when we are close to the minimizer (the center of the circle), Brownian motion has a stronger that when are far from the minimizer,
effect than gradient drift. In the right picture, we the opposite is true. In the middle picture, we see the equilibrium point where the two counteract each other. As the dimension increases, the ratio of the red arrow's 's length to blue arrow's length increases, and so the equilibrium point will get further from the minimizer.
distance proportional to p/ß & /p from the minimizer, Langevin diffusion stops making progress towards the minimizer in expectation, as this distance the progress towards the minimizer due to the drift- (() is cancelled out by the movement in perpendicular directions due to the Brownian motion (see Figure I for a visualization of this phenomenon). This suggests that we only need to run the diffusion until B, reaches this distance from the minimizer, as past that point, we do not expect the diffusion to make progress. Now, the distance yp is increasing with the dimension, and in turn the distance from the ball of radius /p centered at the origin to the boundary of C is decreasing since ||C||2 is a constant. So even if we start at the boundary of C (the worst case for this loss function) the distance the Langevin diffusion needs to travel to be within v distance of the origin is decreasing with the dimension. The total distance we travel due to the gradient drift
is roughly Tб VT, and thus the time we need to run the diffusion for to reach this ball also decreases with the dimension. In particular, once the dimension is large enough, the diffusion will stay very close to the boundary of C with high probability, i.e. taking an arbitrary initial point and outputting it is about as good as in this example as running the diffusion for any amount of time.
On Non-Convergence of DP-SGD/Finite Time Diffusion: We show here that while both the Langevin diffusion and DP-SGD achieve optimal error rates in finite time, for the same parameter settings they do not converge to the stationary distribution. This in part explains why e-g. the finite-time Langevin diffusion for convex losses achieves a much better privacy parameter than its stationary distribution. We use the same example in the preceding discussion, i.e. L(0) ||012, C = B(0,1) 1). In the proof of Theorem F11 we show optimal error rates are achieved when Langevin diffusion runs for time T = z Asymptotically, we get the same bound if we use e.g.
T= r so let us instead consider this choice of T. Since B /T, and the movement due to the gradient drift is proportional to TB, the movement due to gradient drift for our parameter choices decreases with p. The integral from to T of the Brownian motion has distribution N(0, 7I,), iee.
36

---

Under review conference paper at ICLR 2023
with probability 1 1 e-pp), the total movement due to Brownian motion is most, say, 2 Tp 5. In particular, we get that for all sufficiently large with probability 1 - - Langevin diffusion does not move more than total distance 3. If is the boundary, then the probability a random point from the stationary distribution is in a ball of radius & centered at 0o is e-(()) So even though f in expectation obtains the (asymptotic) optimal excess empirical loss, the total variation distance between 0r and the stationary distribution is at least - Q(p), and similarly e.g. any p-Wasserstein distance between 0y and the stationary distribution is Q(1) = ((()))))
I SPLIT REGIMES FOR RÉNYI DIVERCENCE BOUNDS ON LANGEVIN DIFFUSION
In this section, we show that when the loss functions are strongly convex and smooth, can show bound on the Rényi divergence between two diffusions using different loss functions that converges to roughly the divergence between the stationary distributions of the diffusions. In doing so, we show that Rényi divergence bounds between two diffusions exist in two different regimes, where for small T algorithm, and for large T it is advantageous to analyze privacy of LD to an algorithm which samples from approximately a Gibbs distribution.
advantageous to analyze privacy of LD as noisy optimization
1.1 "LONG TERM" RÉNYI DIVERGENCE BOUND
Under m-strong convexity and M-smoothness, using the results in Vempala & Wibisono (2019) we can also give a bound on the Rényi divergence depending on the closeness to the station- ary distribution. Since we rely on the bounds in Vempala & Wibisono (2019) which apply to the unconstrained setting, we will also focus only on the unconstrained setting here. In order to ensure the initial Rényi divergence to the stationary distribution finite, we assume that both [0; D), L(;; D') have minimizers Sopt, opt respectively such that ||0opt|l2/ 1 ll S R.
Lemma 1.1. Suppose we sample 0g =% On N ( 1 Let O O be the resulting distributions of 0;, 0r according to (1) using D, D' respectively. Let P, P' be the stationary distributions of using D, D' respectively. Then for any T 2 to = log(( (a 1) max M/ mm)) and a 2 2:
Rx(O,,04) 5 (M/R(( + + PM
M
(_ (m)
log
exp
+ Raa (P,P'..
3x
Proof. Since adding a constant to L does not affect the sampling problem, assume without loss of generality that there a density function P such that P(0) eX)(-BL(@:D)). Let
Q = N(Oopt, pm pp). By m-strong convexity of C, L(0 - L(Oopt: D) > 2 m ||e 0optll so we
have:
37

---

Under review conference paper at ICLR 2023
P(0)*
exp((a (P),,()
Q(0)a-1
R"
2x
pla-1)/2
(a- 1)ßm
exp(x log P(0)
|0 0opt112) d0
6m
2
R"
2tT
p(a-1)/2
fm
P )fopt)
exp(
||0
pm
2
R²
2nx
pR/2
B1nI
BM
pa./2
2nT
pa/2
M
pa/2
2x
6m
where the first inequality uses strong convexity, and in the second inequality, we use the fact that the 6m-log strongly convex, BM-log smooth distribution with mode opt that has the largest density function popt is N(fopt, 1
PM Tp).
The above bound thus implies that
R₂ (P, 2)
I
pa
log
2( 1 1)
m
By a similar argument, but instead using M-smoothness and the fact that the fm-log strongly convex, BM-log smooth distribution with mode copt that has the smallest density function at 8opt is (foopt/ fm p),, for M-m
M
2(0)a
exp (1aaa1))a(220)))
P(0)a-118
Bm
[aamm ||0 popt 112 + +(a (a0-10 1-1 P(0)))))))))))))))))))))))))PP do
ap/2
exp
2n
R"
Bm
app/2pppppppp ((opt)
((ap))))(((a))
(a-1) / exp
(aB(M- - m) -MM BM)
110
Sopt 112
d0
2.
IRF
8tmt
(ap(M m) -BM) 110 0apt112 d0
p/2
exp
2.r
RP
m
)p/2
M
a aMM m)
p
- PQ, <
log
((x
1)
M (M m)
38

---

Under review conference paper at ICLR 2023
In (*), we use the assumption on ensure the integral does not diverge. In particular, choosing
a 1+ M satisfies the assumption and gives:
PM
M
1 (Q,P)
log
2m
m
The same bounds hold for p', Q' defined using D' and 0pt instead of D, Oopt respectively.
Using the weak triangle inequality for Renyi divergences (Fact B.10), letting Oo N(O, have for any a 2 1,9 2,920 1:
1 Bm
pp),
1/9 R& (P', I
a Rya
1P'221 R R (Q',
Setting 9 2, plugging in our above bound and Lemma B.8
we get:
(a S 2(a 1a-11 1)
pa
log
M
+
Bm 2x 1)R2
m
a 2 2, this can be simplified to:
M
Bm (2x -1)R2
R₂ (P', S plog
2
Then following the proof in (Ganesh & Talwar 2020
Lemma 20), we get that a 2:
Tßm, ) 1 p plog
M
6m (2x - 1)R2
T TBm
Ra (P(P,O') S (a((P(0)) exp(
+
eepp
m
2
a
Similarly we have:
Ra Ra(O,, & -11/ Rạa (,, Q) R (Q,P). &
9-1
Letting a (2 M2 1 g and again plugging in our above bound and Lemma B.8
R 149-1 (O,, P) - (1 + 9) R 1-1-1111///99 Q) + R (+1/g((,P))
g2
< (1 + R R Op Q) + R R1+m/M(277
Bm 0² + 29
1/q)
PM
M
log
2
2m
m
Now, using /Vempala & Wibisono
2019
Theorem and Lemma 14), we have that for any a 2 2
and T > to 2l)g((a-1))):
39

---

Under review conference paper at ICLR 2023
21mm (- (-2ifm
< (q 1)
2(T - to) pm
(OT,r, < Rx P) exp
R (...()))))
exp exp
a
q² 1//a
To simplify, we will use the fact that to upper bound this by:
2, in conjunction with our bound on R
1+ (0, P)
Bmi + 22--//q)R
pM
M m
(T- )mm ( (T (1-to)
log 2m
exp
2
&
We can now use the weak triangle inequality (Fact B.10) twice and monotonicity Renyi diver- gences (Fact B.6 to directly prove divergence bound between O and Op for a 2 2:
& 8/1/3 <
3x/2 -
Ru (or, (O),
R3a (Or, +
3x/2 -322 R3x (3x-((PPP)) + R3a 2(P",
R 1-1
5
R3a (0,, P) + R3a PP)P") + R3a (Pa (P', OG) 3
(16)
Substituting the bounds on R3a (T, P), R3. (P, P'), and R3x (P', O₂), we have a bound
(16 S BmR². max/30, 5 M m) 10M/ m] + 18a - 33. + 5pM m 3p log
M
m
(T
1m)
4
+ (P,
exp
3x
This completes the proof of Lemma I.1
One can modify the proof such that the bound converges R₂ (P, (P,P') P') rather than $ R3x (P, P)), To do so, note that both the leading 4/3 and the leading constant in 3a arise from applying Fact B.10 (16) with fixed parameter q. By instead applying Fact B.10 with parameter 9 depending on T, we can replace $ Ra (P,P') with the expression R( R PPP') for some functions (()) approaching 1 and a respectively. The cost of doing this is that the coefficient 5/3 in front of the first term in (16), and the orders 3a in the first and last term in (16) will become larger over time; however, for a fixed order these terms decay as (xp(-T/a) so if we choose in our application
of Fact B.10 such that these values grow sub-linearly, the first and last term in (16) will still decay as exp( - 7 for some 0 < <<l. 1.
This modification heavily complicates the proof and the form of the final bound, so we omit proof including this modification and instead opt for simpler presentation and weaker bound here.
I.2 SWITCHING BETWEEN "SHORT" AND "LONG" TERM
both loss functions are m-strongly convex and we use a fixed Bt = B, then Chourasia et al. Chourasia et al. 2021 Corollary 1) implies the following:
40

---

Under review conference paper at ICLR 2023
-V((0))))-V(00 I A for all 0, and L(0; L(); ((0) are both m- strongly convex with respect to Then if do and 6g are sampled from On = N(0, pm 1p), , for all a 2 1 and T20 0:
Lemma 1.2. Suppose [IV V'I0;
Ra (o 07) < asa²
(1 -2----0 e /2)
!!
When we have m-strongly convexity, M-smoothness, and bound of on the 42-norm of the difference between the gradients of ((; D) and ((), both Lemma L1 and Lemma I.2 give bound on the Renyi divergence. Intuitively, Lemma 1.2 bounds the divergence between the noisy gradient flows. Therefore, it is initially 0 when there the distributions are the same. However, it worsens as increases, since the distribution at time the difference between the history of the noisy gradient flows and
history of the noisy gradient flows and
T' becomes more dependent less dependent on the shared initial distribution. On the other hand, Lemma [.1 effectively is a bound on the "sampling error" between the finite-time distribution and stationary distribution of each diffusion, plus the divergence between the stationary distributions of the two diffusions. The former improves T increases, and the latter is fixed. In turn, as long as
4 R3x (P) <
4642
!!!
That is, the asymptotic bound of Lemma I.2 is worse than the asymptotic bound of Lemma [.] Since the sampling error goes to T goes to infinity, there shift in regimes where roughly speaking the divergence due to sampling error becomes smaller than the divergence between the noisy gradient flows. At this point, it directs us to use the "long" term bound instead of "short" term bound. In particular, this regime shift occurs roughly when:
PM m
M
(T fo) fm
aB42 m
4 R30 (P, P'),,
0(MRR((M//)) aa) +
log m
exp
3x
3
Rearranging, we get that we shift regimes at roughly time T such that
BmR(M/m + a) + PM
log
M
T" 2log((a 1) m2 M))
log Bm
asA²
m - R3a
Again, we remark that one can modify Lemma For this asymptotic bound, the inequality
1.1 approach (P(P,P') instead of (P, P').
aBA²
Ra (P(PP') <
m
is always satisfied, i.e., either the limiting bound of Lemma tion, or such regime shift always exists.
1.2 is tight for the stationary distribu-
J DEFERRED PROOFS FROM SECTION
Proof of Theorem F1 Let (0:)
25 0| x|| be the potential w.rtt. fixed C. We will write
(0:) as the sum of two terms, d (8:), which is equal to (0,) if we used eq. I1 instead of
41

---

Under review conference paper at ICLR 2023
eq. (2) and (0:), which is simply the difference ddx(0,) (0.). For example, d is 0
when 8 is not on the boundary of C. Since C is convex, if 0 is point on the boundary of C and is
a normal vector of C at 0, then (0- x) t) 2 0. Then by definition of Ie,, this implies d (0:) 2 0
always, so d (0:) _ (0t).
By Ito's lemma (Lemma B.1 we have the following:
8, - xx-x-vAa -V(())((t V2 dw,
d = Pat +
(17)
B
Combining eq. (7 with the fact that (0)) & dd. (0:), we get:
V2 dt +
dpx(0)) ( (8:-
B (0) 206-x,WWi dWW)
(18)
Furthermore, by linearity of expectation we have the following:
v2
E (0:) < dt EE [10 x, V=(0;;))) dt +
E [(0 x,dWi)]
B
v2
+ [0, x, VL(00; dt
P B
dl
[10 d.)) - E [d))
P
di
-E [d.x
B
(19)
The last equality in eq. 199 follows from the following observation:
E [(0 x, ddW)]] = E [(0;, dW:)] - E dW,)]
E [(0,, [[:)]]
(20)
B- IE
(O0;;: dt,
/2.
(dZz, awi)
(21)
/2- E
dzz
dW:
dWW,
0,
(22)
where in eq. (2 Zr is the standard Brownian motion, and in eq. 22 we used the law of iterated expectations and the fact that in the Ito integral, dW; is independent of { (WrJosrst-
By convexity of the loss function L we have:
L(0; L)x < (0, - x, VL((;,
(23)
Combining eq. 199 and eq.
23
we have the following:
E [C(e;; D) - L(x p. dt
E [d)x((1)]
(24)
B
42

---

Under review as conference paper at ICLR 2023
Let S b. Integrating eq. (24) from (a, b), we have the following:
b
b
dt
/ (pp((1)
D)) di E (((0:))-((x))))
S p
E
B
==
1=b
b
dt
p
E
(4x((ss)
-xx
B
1=1
p. (b
a)
1
1
+ E
|1
x112
110b
x11
(25)
B
2B
2B
by the definition of the potential (x()))
|10, x
2B
Consider two non-negative real numbers k and y such that y < k. Define
T
SkY k + 7 1=T-k
D)dt and
5, = lim Sky
7 >0
That is, 5z is the average value of L);;; over the interval [T - k, 77, and in particular So C(0r; D). We have the following:
T- T-(--7)
E [k. Sk-mr] =E
L(0;;
= EE
D(d:
IE
[(0;; D)d!
(kT-(k-7)
4-T-k
T
T- (k-
= E [k 7)
SkIT - IE
[(0;;
dt
(26)
T
T 7)
To upper bound -E
L(0;; D)dt above, we use eq. (55 as follows, while setting a = T k
T-
and b T.
B
[[((x:))
<
p
+
1
E |10 x1[]]
1
j c(er:
B
2B(b a)
a
p
+
1
E
|10 x12]
k + Y
E [San]]
B
2B- k
k
This implies that
T- (-(k-))
T-(k-7)
-E
C(0s; D)dt
<
PY
+
1 IF
10r k --0 -0
- -(1+ 2) 7. F [Skm]]
B 2B k
1=T-k
1=T-k
+ 7 1IC113
< PY
(1 k) 7) -7 EE |kxTl
(27)
B
2B k
43

---

Under review conference paper at ICLR 2023
Plugging in eq. 27) into eq. 26 have the following:
S E [
72
PY
7 ||C12
k-
5k-nn
SkY
+
+
k
B
26- k
Dividing by k, get
SI (1-
72
PY
Y 11C112 26 K2
SKY
+
+
k2
Bk
Rearranging the terms, we get
E Sk-na (1 (1-
72 122
PY
7 1|C112
SKY
+
Bk
2B. k2
This gives the following set of implications
Sk 7/7
Sky
Sk 9k-7/Y
SKYT
P
|CC12
E lim 7-10
lim E
7
7-10
7
Bk
26 R2
d
+ ||C112
E [Sk c) 5 pk 2B A2
dc
S EE [Sx] + P + ||C12
E
[S)]
(28)
B
2B k
Where the inequality (+):
SK-10 1,7
Skyy
Sx-
Sk,7
E
lim
lim IE
(29)
7 >
y
St St-7 Sen we get:
follows because of the following argument. Using the definition of
T
Sx-7 - -Sky
1
D();
((0r:D)dt
7
ky
(k+
T=T-k
1=T
T-K+y
1
L(0;: +(k+7)
L(0;
k(k 7) 1=T
1=T-k
k 7
1
min L(1;; - (k +)+
max max D),
(30)
k(k + 7)
Since 0, E C for all f, and L is L-Lipschitz, we get that L(,, D) is lower and upper bounded by some constants for all f. Using eq. (30), this implies that Sama Ska is lower bounded by some constant for all y < k. In other words, we can apply Fatou's lemma to upper bound the expectation of the limit by the limit of the expectation, hence the inequality (+).
Now setting in eq. 28 we get:
Sol] < E
[TT]
P
+
C
2
(31)
B
2BT
44

---

Under review conference paper at ICLR 2023
If we 0,b T in eq.
25
and then divide by have:
|
E [ST] - L(x;
< P +
E
100 x11
100
x112
- +
(32)
B
2PT
28T
28T
Combining eq. 31 and eq.
32 and setting x = 0* where 0r is any minimizer over C, we get:
2p
|CI2
E [[((T:) [(e";
(33)
B
BT
We now need choose p, to minimize the above bound while satisfying privacy. By setting A
2L/n in Lemma C.1 and setting + 2log(1/5) in Fact B.5 we get that as long as 2log(1/8) satisfy (e, diffferrnnt privacy suffices if:
> to
log B2TT
BS
(34)
En2
2
L
87 lo
Plugging B Lo881og(1/8) into eq. (3
we get:
E - - 4pI. 2T logg
2L 22g (1/8) (log(1/8)
|cc12
+
(35)
EN
VTen
ICI| 2p
The above bound is optimized by choosing
giving the theorem statement.
Proof of Theorem F22 Note that 6;
2t B, by definition, and let Φ: = mBe ||0
112 Similarly to
eq. 19 by Ito's Lemma we have:
v2
dæ: SmBre"BB 110, 0-1 mB 0r -0,-,,--B -,,,BB;VV((;D))) +
dw;
+ Be dt
Taking expectation on both sides,
[ddp]] mB E m 1 0013 (0' o,, VL(0; dt pemBi dt.
(36)
By 2m-strong convexity we have
D() L(0::D) 2 (VL(O:D), R* 01) 1|0: 0* 0²122.
(37)
Note that mB; = mB Then plugging eq. 37 into eq. 36 we get:
E [dbb]] < BB [C(0"; - EE [C(0; dt + mB dt
(38)
45

---

Under review conference paper at ICLR 2023
This implies that
E [)(:: L(""; D)] dem S -E [dΦi] pe dt.
(39)
Now, integrating eq.
38
from to T and noting that 4; for all f get:
T
E [C(0;; _(""; :D]demmB < mipo + mp / mB dt.
(40)
By Jensen's inequality,
(emBr - 1)P(i :D) -
[(0;; d
(41)
Plugging eq.
41 into eq. 40 and using linearity of expectation we have:
m&o + mp f BB dt
[((PPrv :D]] - D()";
(42)
BB
We now determine what choice of a function of T ensures privacy when B 8a Our final
choice of a will satisfy 2 0 for all sufficiently large n. Recall from Lemma C.1 that for (e,8)- differential privacy, since we have L-L.ipschitzees suffices if:
4L 1og((10)) Bttt
Se E
en
e2n
2 dt <
4L (1/8)
(2a + 1)
+ 1
(43)
4L log(1/8)
Note that we use the assumption 2 0 to show the integral is equal to 2 rather than diverging. For eq. (3 to hold, assuming > 0, we have 2a + 1 2 1, so letting
suffices. We will eventually choose T that is at most 2 for suffi- ciently large n, which implies that a 2 0 for all sufficiently large n as promised. We now wish to evaluate from eq. 42 the integral:
108max(2.77 2L 2oggo1)(
46

---

Under review conference paper at ICLR 2023
/ exp (nB;)dd= =
T
mf++1
T
nit
108max
22, 22./oog//85)
V
exp(
dt
exp
dt
(44)
mEn
<
exp
dt.
(45)
2
Let 2(a / and x cvt. Then dr upper bounded as:
c
2 2x
So the last integral in eq. (44) can be
2
2 CT 2 xe = /
[ exp(cv/Fdtt
eV (VT
22 VT(EVT- -1)
(46)
2
Where the last inequality follows from the inequality ex 2 1+ x. We also have that the denom-
inator of eq. 42 equal to emB; - e'VT 1. So plugging eq. (44), eq. (46) into eq. 42) we have:
[(epriv D)] L(0"; D) < mndo
2mpvT
E
(47)
e -1
If we choose T log 11) and plug in the expression for c, eq.
47)
becomes:
x²
E C(opriv :D] L(0*; <
m@o R
2log +1)
mdo
8p(a + 1)L2 (1/5)
log()oog(RR R + +1
R
m22n2
(48)
Note that d0 = |10) - 10 < ||c12 <
12 m²
So complete the proof, we can choose
2 pdo <
pe2n2
R =
(49)
21 log218)11/8)
2 2lg((1/8)
Which causes the second term eq. statement.
48 to be larger than the first term and gives the theorem
Proof of Theorem
E4
We again choose B
L./8Tlog(1/8 as in Theorem F1
Then combining
Lemma H3 with eq. 35 we get the following bound
44pL/22og(1// en
V2EL
2L 22 (1/8)
|Cl1
E garivv [Risksco (0priv
5 VT
Mog(118)
VT
en
(50)
47

---

Under review as conference paper at ICLR 2023
To minimize the right hand side of the above inequality, we choose T log(//>)/< f'n
(min ||C|6
}). The result follows.
48


Reviews:
[{"review_id": "kl6G-fkrW7", "reviewer": "Reviewer_yW9T", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the differentially privacy guarantee, empirical risk bound and population risk bound of continuous time Langevin dynamics with tunable temperature and tuning time. For convex loss, the ε-DP result is cited from (Bassily et al., 2014). The ε-DP result for strongly convex function is derived for some iterated exponential mechanism similar to (Bassily et al., 2014). To derive the ε,δ-DP guarantee this paper uses Renyi differentially privacy as a sufficient condition. The Renyi divergence of two Langevin diffusions is derived using standard combinations of post processing theorem and composition theorem. \nThe population risk for stochastic convex optimization is derived with uniform stability bound similar to (Hardt et al., 2016).\nCombining these techniques, authors show various optimal bound under privacy guarantee in a unified model ,i.e. Langevin diffusion.", "summary_of_the_review": "This paper present continuous Langevin dynamics as a unified approach to the problem of differential privacy. In particular, the bounds derived in this paper recover or exceed the best known bounds in the field. At the same time, the limitation of continuous dynamics and infinite computation budget raise questions on the practical significance.", "strength_and_weaknesses": "Strength:\n\nAlthough most techniques used in this paper exist in prior work, they are adapted to the specific problem considered here.\nCombining these techniques, authors not only recover best known bounds, but also derive new results.\nThe collection of optimal bounds under various setting manifest that Langevin diffusion is indeed capable to serve as a unified framework to analysis empirical risk and population risk with privacy constraints.\n\nWeakness:\nThe main weakness is that algorithms 2,3 in this paper are not actually algorithm, because sampling exactly from an Gibbs measure is generally not possible within finite number of operations.\nAny implementation necessarily introduce a sampling bias which decrease with computation budget. For example, DP-SGD in (Bassily et al., 2014) uses a fixed step size.\nIt is still unclear how such bias interfere with bounds provided in this paper.\n\nAnother consequence of continuous model is that the effect of stochastic gradient error is totally ignored. For example, DP-SGD in (Bassily et al., 2014) uses a mini-batch for each iteration. However, in continuous time LD, all information of the whole dataset is used at every time point.\n\nGiven these mismatch between continuous time LD and real world algorithms, it is not clear how significant results in this paper is to the development of practical differentially private algorithms.\n\nMore specifically, it seems all improvement over existing results happens for ε-DP with $T=\\infty$ (please correct me if I am wrong), thus it is hard to see whether the improvement is due to better algorithm design or a bonus of infinite computation power.\n\ntypos:\n\nIn eq 34, ε in denominator should not be square.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "f4ijnO6D1gE", "reviewer": "Reviewer_ymJu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies differentially private empirical risk minimization (DP-ERM) and differentially private stochastic (convex) optimization (DP-SCO). The authors consider the Langevin diffusion, which is a popular continuous-time algorithm, and show that Langevin diffusion has optimal privacy and utility trade-offs for both DP-ERM and DP-SCO under $\\varepsilon$-DP and $(\\varespilon,\\delta)$-DP both for convex and strongly convex loss functions. They also obtain new uniform stability results for Langevin diffusion that are time and dimension independent. ", "summary_of_the_review": "The paper studies an important and interesting topic. It is a solid theory paper. However, it has quite a few weaknesses as I mentioned previously. ", "strength_and_weaknesses": "The paper is a solid theory paper, and the authors have provided detailed and rigorous treatment in the relatively long appendix. The authors also seem to be quite familiar with the relevant literature. The topic is important and worth investigating. \n\nHowever, I have some concerns about the assumptions and especially how the paper is presented. \n\n(1) The assumptions are often confusing. For example, on page 2, when the authors introduce the problem description, one considers a constrained set $\\mathcal{C}\\subseteq\\mathbb{R}^{d}$. However, it is not clear to me when $\\mathcal{C}=\\mathbb{R}^{d}$ and when it is a proper subset of $\\mathbb{R}^{d}$. Moreover, if it is a proper subset of $\\mathbb{R}^{d}$, what is the assumption on $\\mathcal{C}$? For another example, the authors mentioned on page 3, that \"Depending on the problem context, we make additional assumptions like $m$-strong convexity...\" I am perfectly fine with this. However, it is not clear when you make such an assumption and when you do not. For example, in the statement of Lemma 1.1., you didn't mention the strong convexity assumption, so I suppose it is not used. But then, in Theorem 1.2., $m$ appears in the equation, does that mean you used this $m$-strongly convex assumption? If so, you should mention it. If not, you should mention what $m$ means in Theorem 1.2. \n\n(2) It seems that the paper is hard to read unless you go back and forth between the main body and the appendix. For example, in Theorem 1.2., it uses Algorithm 3, but you cannot find Algorithm 3 in the main paper at all. \n\n(3) Some of the assumptions might be too strong. For example, the authors assumed that the loss function is $L$-Lipschitz. That assumption is quite strong when $\\mathcal{C}=\\mathbb{R}^{d}$, because for the Langevin literature that I am familiar with, people usually just assume (strong) convexity plus smoothness, but not the Lipschitz assumption. If your $\\mathcal{C}$ is compact, you need to make an assumption and make it clear in the main body of the paper. For instance, when I look at the statement of Theorem 1.3., it seems to me that $\\mathcal{C}$ needs to be bounded. But when I'm looking at Lemma 1.1., I don't know whether you need assumption on $\\mathcal{C}$ or not. \n\n(4) I am a bit confused with equation (2), about \"Projected\" Langevin diffusion on page 3. I understand that for Langevin algorithm on a constrained domain, you can project it back to the constrained set if the algorithm exits the domain. However, in equation (2), you are considering a continuous-time dynamics. In Bubeck et al., they showed that (discrete-time) projected Langevin algorithm, in the continuous-time limit, corresponds to a Langevin diffusion that is reflected when it touches on the boundary. You are considering a continuous-time SDE in equation (2), that makes me wonder why it is not a reflected SDE, but rather involves a projection map?\n\n(5) The fact that the authors are considering a \"continuous-time\" algorithm, instead of a discrete time algorithm, makes the contributions of the paper a bit weak. \n\n(6) Langevin algorithm is used in the optimization literature usually when the objective is non-convex, so that the injected Gaussian noise can help the algorithm escape local minima; see e.g. Raginsky et al. (2017). It is not clear to me when for convex optimization, one needs to use a Langevin algorithm. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UMkDfjzxw-", "reviewer": "Reviewer_J76Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses differential privacy using the Langevin dynamic and claims to achieve the optimal utility-privacy trade-off for DP-ERM and DP-SCO. This paper provides bounds for excess risk on the \\epsilon-DP-SCO. ", "summary_of_the_review": "This paper provides bounds on the DP-ERM and DP-SCO with the use of the Langevin dynamic. Seems like, with techniques borrowed from the literature, this paper provides bounds that claim to be \"tight\" specifically for \\epsilon-DP.", "strength_and_weaknesses": "Strength: \n- This is a very interesting problem to look at even though this is not the first time that DP is viewed through the Langevin dynamic. \n- Provides a comprehensive background on the topic. \n------------------------------------------------------------------------\nWeakness: \n- This paper can be hard to follow. The main body of the paper is not self-sufficient and one should constantly go to the appendix to understand the paper. Perhaps it could have been a bit more organized. \n- This paper is way too long for a conference paper.  And it feels like the main contribution is lost in the notation and the amount of unnecessary information provided in the paper. \n- It feels like the main idea stems from one of the recent papers on the use of Langevin diffusion for DP (DP guarantees for SGLD by Ryffel), without having any sort of comparison for them. Notations, use of Renyi divergence and etc are borrowed from the same paper.\n- Proofs seem to be correct as they follow the properties of LD and straightforward techniques in DP. \n- Due to the similarity of techniques (use of LD in this paper and the one by Ryffel), comparison/discussion on both these methods is required. Since some techniques are borrowed, how is this work different aside from being applied to ERM and SCO. Techniques seem to be very similar. \n- What can say about the sensitivity under the LD? \n- Are strong convexity a necessary condition? If this assumption was not made, how would the bound change?  \n- I understand this paper is meant to be understood as theoretical but some practical implications of that could be helpful. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Ey2rHsfFF9t", "reviewer": "Reviewer_wZ3h", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes achieve trade-offs of privacy and utility for DP-ERM and DP-SCO via Langevin diffusion. Tight DP-SCO bounds for both convex and strongly convex are provided through the lens of algorithmic stability. For non-convex case, a lower bound is provided to show the impossibility of improvement from $\\epsilon$-DP to $(\\epsilon, \\delta)$-DP.", "summary_of_the_review": "Overall, I think the contribution of this paper is to employ Langevin diffusion to provide a framework to analyze the privacy/utility trade-offs, but it does not show a significant improvement compared with previous work. Additionally, the assumptions for uniform stability seem strict. However, it indeed provides a new thinking of analysis.\n", "strength_and_weaknesses": "Strengths:\n1. The main contribution of the paper is providing a framework based on Langevin diffusion to analyze privacy/utility trade-offs for DP-ERM and DP-SCO. \n2. Algorithmic stability is employed to provide the tight DP-SCO bounds.\n3. The paper is well-written and solid in theoretical analysis.\n\nWeaknesses: \n1. The comparison of tight bounds for DP-ERM and DP-SCO with related work is lacking(a table may can demonstrate the comparison better).\n2. The theorems are fairly restrictive. (i.e. For Theorem 1.2, if $p \\ll n$, the improvement from $p^2 \\log(n)$ to $p\\log(n) + p^2$ is limited; if $p \\gg n$, the bound seems to be less meaningful. The assumptions for stability bound are required strongly convex and smooth, which are also strict. The choice of learning rate should satisfy empirical case and population case simultaneously.)\n3. The experiment part is missing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject