Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy
Authors: Yingyu Lin
Yian Ma
Yu-Xiang Wang
Rachel Emily Redberg
Zhiqi Bu
Venue: ICLR 2024 poster (2024)
Keywords: Pure Differential Privacy
Monte Carlo sampling
Gaussian Differential Privacy
Exponential Mechanism
Primary area: optimization
TL;DR: We propose an approximate Monte Carlo sampling method to achieve pure and Gaussian differential privacy.

Abstract: Posterior sampling, i.e., exponential mechanism to sample from the posterior distribution, provides $\varepsilon$-pure differential privacy (DP) guarantees and does not suffer from potentially unbounded privacy breach introduced by $(\varepsilon,\delta)$-approximate DP. In practice, however, one needs to apply approximate sampling methods such as Markov chain Monte Carlo (MCMC), thus re-introducing the unappealing $\delta$-approximation error into the privacy guarantees. To bridge this gap, we propose the Approximate SAample Perturbation (abbr. ASAP) algorithm which perturbs an MCMC sample with noise proportional to its Wasserstein-infinity ($W_\infty$) distance from a reference distribution that satisfies pure DP or pure Gaussian DP (i.e., $\delta=0$). We then leverage a Metropolis-Hastings algorithm to generate the sample and prove that the algorithm converges in W$_\infty$ distance. We show that by combining our new techniques with a localization step, we obtain the first nearly linear-time algorithm that achieves the optimal rates in the DP-ERM problem with strongly convex and smooth losses.

Published as a conference paper ICLR 2024
TRACTABLE MCMC FOR PRIVATE LEARNING WITH PURE AND GAUSSIAN DIFFERENTIAL PRIVACY
Yingyu Lin',, Yi-An Ma"", Yu-Xiang Wang"*, Rachel Redberg", Zhiqi Bu
UC San Diego, PUC Santa Barbara, 3 "Amazon AI {yi1208, y vianma fanna)@ucsd.c. sucsd.edu {yuxianqw, zredberg ucsb. 2higibu@amazon.ccm
ABSTRACT
Posterior sampling, i.e., exponential mechanism to sample from the posterior distribution, provides S-pure differential privacy (DP) guarantees and does not suffer from potentially unbounded privacy breach introduced by (s, -approximmte DP. In practice, however, one needs to apply approximate sampling methods such as Markov chain Monte Carlo (MCMC), thus re-introdueing the unappealing 6-approximation error into the privacy guarantees. To bridge this gap, we propose the Approximate SAample Perturbation (abbr. ASAP) algorithm which perturbs an MCMC sample with noise proportional its Wasserstein-infints (Wx) distance from reference distribution that satisfies pure DP or pure Gaussian DP (i.e., = 0). We then leverage the Metropolis-Hasting algorithm to generate the sample and prove that the algorithm converges in W distance. We show that by combining our new techniques with a localization step, we obtain the first nearly linear-time algorithm that achieves the optimal rates in the DP-ERM problem with strongly convex and smooth losses.
INTRODUCTION
The strongest form of differential privacy (DP) is S-pure DP, which provides an inviolable bound of & 2 0 on an algorithm's privacy loss. The posterior sampling mechanism associated with the loss functions (Wang ct al. 2015 Dimitrakakis et al.] 2017 Gopi et al. 2022) is known to achieve near-optimal privacy-utility tradeoff for learning under pure DP in theory. In practice, sampling from a general posterior distribution is typically either intractable or inefficient. Both issues can be solved by approximating the posterior, e.g. via MCMC sampling. But of course there is no free lunch: the approximation error introduced by this approach now degrades the privacy guarantee to the weaker notion of (s, 8) apprroxinatee DP, under which we risk a catastrophic privacy breach with some small probability 6. Our paper bridges the gap between theory and practice thus alleviating a common growing pain of DP research - by proposing efficient MCMC-based algorithm that samples from an approximate posterior while satisfying pure DP.
Recent research has explored various implementations of posterior sampling mechanisms, facing recurring challenge: each approach either compromises on DP guarantees or incurs substantial computational costs. Studies by Wang et al. (2015): Gopi et al. (2022) illustrate that employing approximate posterior sampling with sampling error solely in terms of the total variation (TV) distance downgrades the DP guarantee to approximate DP. In contrast, Seeman et al. (202T) samples from the exact posterior with pure DP. But the associated runtime can be exponentially large due rejection sampling scheme that, in the worst-case scenario, has an exponentially low acceptance rate. This motivates the following question:
Can obtain pure DP guarantees with an efficient MCMC algorithm?
In this paper, we answer the question in the affirmative by developing the Approximate Sample Perturbation (ASAP) algorithm.
"Egual connibution.

---

Published as a conference paper at ICLR 2024
1.1 OUR CONTRIBUTIONS
The main results of our paper are threefold.
1. We propose Approximate Sample Perturbation (Algorithm 2) a novel MCMC-type method designed to maintain pure DP and pure Gaussian DP by perturbing MCMC sample. Theorem (reoorem@dmmonstratee that ASAP maintains these DP guarantees when the MCMC sample distribution closely approximates the exact posterior, measured in terms of the Wasserstein-infiiity (Wxc distance.
2. We establish a novel generic lemma (Lemma 8 that facilitates the conversion of TVV distance bounds to Wo distance bounds. This transformation enables the maintenance of pure DP guarantees when employing MCMC samplers with TV distance errors. Notably, this lemma is of independent interest.
3. We introduce the Metropolis adjusted Langevin algorithm (MALA) with constraint (Algorithm that converges with respect to the Wo distance. Integrated with preceding localization step, detailed in Algorithm [ it empowers the ASAP framework to achieve optimal rates in nearly linear time while ensuring pure DP and pure Gaussian DP in the context of the Differential Privacy Empirical Risk Minimization (DP-ERM), for strongly convex and smooth losses.
IT
1.2 RELATED WORK
Posterior sampling mechanism, i.e., outputting a sample Ô ~ p(0) xx exp(->(F((O) + 2 (111111 is popular method for DP-ERM and private Bayesian learning. It was initially analyzed under pure DP Mir 2013 Dimitrakakis et al. 20177 Wang et al. 2015). then later under approximate DP (Minami et al. 2016), Rényi DP (Geumlek et al. 2017 and Gaussian DP (Gopi et al. 2022). each case, it known that with appropriate choices of 7, À parameters, it achieves the optimal rate (Bassily et al. 2014) under each privacy definition. However, the computational complexity of the MCMC methods has been a major challenge for this problem. To the best of our knowledge. Bassily et al. (2014); [hourasii et al. (2021) ; Ryffel et al. (2022); Mangoubi & Vishnoi [022) are the only known results that obtain DP guarantees using MCMC methods without having 8> 0. Bassily et al. 22014)ss 's sampler (a variant of (Applegate & Kannan (1991)) runs in O(n²) and requires explicit discretization. Chourasia et al.] 202T); I; Ryffel et al. (202))ss 's algorithms run in nearly linear time (for strongly convex DP-ERM) and enjoy pure Rényi DP, but their utility bound is factor of condition number i worse than the statistical limit. Mangoubi & Vishnoil (2022)'s 's algorithm translates the TV distance guarantee infinity-distanee
(dxc) guarantee by incorporating uniform noise and a membership oracle, while their focus is on Lipschitz continuous loss. The idea of perturbing distributions to strengthen the DP guarantee is discussed in Feldman et al. (2018) and its application to Langevin analysis (Altschuler & Talwar 2023). where additional noise converts Wo guarantee to Rényi DP guarantee. Our work is the first that archives the optimal rate for Strongly-Come Convex DP-ERM under pure DP and pure Gaussian DP with a nearly linear time algorithm (for x polylog(n)).
DP-ERM can also be solved using other methods that do not require MCMC sampling. However, these meth- ods either do not achieve optimal rates (output perturbation (Chaudhuri et al. 201Th) or are computationally
less efficient (Noisy SGD (Bassily et al. [2014] AAbadi et al. 2016)) or require the model to be (generalized)
linear (e.g., objective perturbation (Chaudhuri et al. 2011 Kifer et al. 2012 Redberg al. 2023)
2 PROBLEM SETUP AND PRELIMINARIES
Symbols and notations. Let X be the space of data points, X' :- U X" be the data space, and D E X be dataset with an unspecified number of data points. Let the parameter space U C Rd and for each x E X and A E L4, Eg (0) denotes the loss function (or negative log-like likelihood function). When D = {#1, In we denote fx, (0) by (.(0) as a short hand. Denote the total loss L = >i= l. For any set S, we denote the set of all probability distributions A or PPs. that a mechanism M : X + A is randomized algorithm. We use M(D) to denote the probability distribution as well as the corresponding random variable returned by the mechanism. For set S, we denote DSa == supa,yes ||æ vl12. and ||S]| == supaes ||:|||2-
2

---

Published as conference paper ICLR 2024
2.1 DIFFERENTIAL PRIVACY EMPIRICAL RISK MINIMIZATION (DP-ERM)
Empirical risk minimization (ERM) is classic learning framework which casts the problem of finding "good" model into an optimization task. Our goal is to find the parameter 0 in the parameter space UI C R which minimizes the empirical risk: 0* arg mingeu (E (())
The problem setting of our paper differentially private empirical risk minimization (DP-ERM): empirical risk minimization under privacy constraint.
2.2 DIFFERENTIAL PRIVACY DEFINITIONS
Definition (Differential privacy (Dwork et al. 2006
2014
Mechanism M satisfies (e, 8)-DP for all Range(M).
neighboring datasets = D' and for any measurable set
P[M(D) 8) & +
When 8 = 0, M satisfies e-(pure) DP.
Differential privacy (DP) provably bounds the privacy loss of algorithm. Approximate DP (5 0) is practical and popular DP variant which allows a "failure" event where the privacy loss exceeds the bound to occur with some probability. Beware: approximate DP does not bound the severity of a privacy breach. The privacy loss under a failure event could be arbitrarily large. Avoiding this risk requires pure DP (Ō 0), which provides deterministic bound on the privacy loss.
In comparison to approximate DP, Gaussian DP is more "controlled" relaxation of pure DP which does not have an unbounded failure mode. We can define Gaussian DP via the hockey-stick divergence.
Definition (Hockey-Stick Divergence). The Hockey--Stick Divergence of distributions P, Q is defined as
(Pll)) = = (86(0)
where (-)+ ; max(0,)) and dP denotes the Radon Radon-Nikodym derivative. aq
Definition 3 (Gaussian Differential Privacy (Dong et al., (022)). We say that mechanism M satisfies j-Gaussian differential privucy for any neighboring datasel D, D',
He(MM)))))('') s Her ())
VE E R.
This definition is equivalent to the dual definition from the hypothesis testing perspective in (Dong et al. 2022 Definition 2.6). The statement naturally provides "dominating pair" of distributions, facilitating adaptive composition, amplification by sampling, and efficient numerical computation (Zhu et al. 2022).
2.3 EXACT POSTERIOR SAMPLING: DP AND UTILITY GUARANTEES
The primary algorithm we consider a variant of the classical exponential mechanism (EM) known as posterior sampling. The posterior sampling algorithm instantiates the exponential mechanism by taking the quality score to be scaled and regularized log-lib likelihoodd function with parameter 7, X, i.e.,
i p(0) & cxp (-> (E"
((0)) + x]ll1)) E
(1)
This mechanism enjoys pure DP and Gaussian DP for appropriate choices of y, A, and domain t.
Lemma 4 (GDP of posterior sampling (Gopi et al., 2022 Theorem 4)). Assume the loss function is G- Lipschitz, posterior sampling mechanism with parameter y, 0 satisfying 7 S x/2 satisfies μ-GDP.
Lemma 5 (Pure DP of posterior sampling). Assume the loss function is G-Lipschitz, posterior sampling mechanism with parameter y > 0 (any of X) in domain O satisfies e-pure DP if G-Diam(9))
3

---

Published as a conference paper ICLR 2024
Lemma slightly improves existing analysis (Wang al. 2015 Dimitrakakis al., 2017) by the bounded range analysis (Dong et al. 2020). This approach avoids assumptions on the loss bound, which is potentially large, privacy calculations. The proof provided in Appendix [.4
We have the following lemma for the utility of posterior sampling.
Lemma (De Klerk & Laurent (2018, Corollary 1)). For convex finction F(0), and convex set θ Rd
0 ~ p(0) x exp(-x satisfies that [[) I mingee F(0)
3 TECHNICAL TOOLS
This section introduces tools that facilitate MCMC sampling for pure DP, including Lemma that converts TV
distance bound to W bound, and Algorithm an MCMC sampler that converges in W distance.
3.1 OVERVIEW: WHY DO WE USE Wo: DISTANCE?
Suppose p" is a Gibbs posterior that satisfies pure DP. In practice, MCMC samplers generate an approximate sample 9 from an approximate distribution p with drv (p. p²) < &. where drv represents the TV distance. Notice that this TV distance guarantee does not grant pure DP for sampling from ý. Instead, it provides only (c, 6)P with 5 = (1 + e ) > O, as elucidated in Proposition of Wang et al. (2015).
To circumvent this challenge, ASAP (Algorithm 2 adopts a two-part approach to address the privacy of Ó. First, we decompose into two components:
Ö 0- + (0- where 0, p²
Note that 0, p" satisfies pure DP by existing works Wang et al. (015). Our aim is to add noise to (0 0.) so the perturbed difference, (Ø- 0.) noise, also maintains pure DP. This allows the leverage of the composition lemma (Lemmal 14p to devise an MCMC sampling methodology that guarantees pure DP.
However, to release (Ø 8_) with pure DP by appending noise, is crucial to determine an upper bound on the sensitivity of this quantity with certainty of This necessitates bounding the particle-wis distance ||0 0-]1, (or | l2112 in Gaussian DP) with a probability of /. Establishing this sensitivity bound hinges on the Wasserstein-imfinng distance (Definition 7 see Fiure | for a visual illustration of Woo.
Therefore, MCMC sampling approach with Woo error bounds is essential. We introduce MALA with constraint, specially designed to guarantee strong W distance convergence.
3.2 TV DISTANCE TO oo DISTANCE
Consider two distributions P and Q on the same metric space (9, dist). We sample x and y ~ Q. When distributions P and Q are relatively "close", the corresponding samples and y are also expected to be close. Motivated by the preceding discussion of MCMC for pure DP, a natural question arises: Can we define distance for distributions P and Q that guarantees upper bound for dist(x, y) with probability 1? Wasserstein-oo distance answers this by constructing an appropriate coupling (* between and Q.
Let θ Rd be domain equipped with metric dist. Let P and Q be two probability measures on O. The Wasserstein-imfiing distance between and Q with respect to dist, denoted as (P,QQ)) is defined as
Definition 7.
Wo P+Q)==
inf
ess ess
dist(xr inf fe2 0)((((x.)) @2)dist(E, v) c))== 11} certr.o)
(Er(P.Q) (=x))((xx.c))
where T(P, Q) is the set of all couplings of and Q, i.e., the sel of all joint probability distributions C with marginals P and Q respectively. The expression ess ((xxx)) dist(x, y) denotes the essential supremum of dist(a, y) with respect to measure Ç. It captures the supremum of (ist(rr,))) y). excluding sets of S-measure zero.
4

---

Published as conference paper ICLR 2024
A
0
0
A
(a) (6, -
(b) (ô. 8 ~
Figure Two examples illustrating the couplings of and p". Let C* be the optimal coupling of W (p. ), and let p&p" denote the independent coupling. In both scenarios, the marginal distributions are ý and p' Denote A W (p. In Figure (a), when (0, 8*) follows the optimal coupling, (0, 6²) is confined within the band ( 0 < A. Conversely, Figure shows that when 0 and H independently sampled, the distance ( 0 take relatively large values with positive probability. Through appropriate coupling
distributions P and p" particularly the optimal coupling C", obtain tight almost-sur bound A the distance between the two samples and 6".
Our pursuit of pure DP relies on the W distance. However, typical MCMC samplers offer convergence based on TV distance, which leads to the weaker approximate (s, 8)- DP with 8 > reconcile this discrepancy, we present versatile lemma that facilitates the conversion from dTv bound to the W bound.
Lemma (Converting TV distance to Wx distance). Consider two probability measures, P and Q, both supported bounded closed 2-norm-bale θ C R.. On this domain θ, suppose that the density of Q bounded by a constant Pmin- We establish the following results based on the choice of metric for W oo
1. Suppose Wo is defined with the 1-norm, i.e., dist(x, y)
2 v111.
d/2
If drv(P.Q) < Punin 2d+1 r + 1) dd/2 A then WP SA
2. Suppose Woo is defined with the 2-norm, iee. dist(r. v.
| vll2-
4/22
If drv (Pv(P, < Pmin 2d+1. [[g + +1
Ad, then (x,PPQQ < A.
In both cases, I represents the gamma function.
The results naturally extend to the case where θ is a bounded open 2-norm ball.
The proof is detailed in Appendix E This lemma bridges the gap between TV distance and Wos distance, enabling the preservation of pure DP guarantees with TVV distance- MCMC samplers.
Conversion from TV distance bound to W bound necessitates extra conditions the probability measures. The following lemma establishes a lower bound (denoted as Pmin Lemma 8 for the density of distributions that log-concate and log-Ling Lipschitz continuous smooth. The proof is provided in Appendix L.I
5

---

Published as a conference paper ICLR 2024
Lemma Consider distribution with density p(0) -)-1000) supported on bounded convex domain with 2-norm diameter R, where Z = l is the normalization constans.
Assuming that J is convex and G-Lipschitz continuous, establish the following bound on the density:
inf p(0) E--GR T( +1
(R/2))
Alternativel, J is convex and 3-Lipschitz smooth, the density bound holds for any 0 E O:
I(
p(0) 2 ((111)001+)))))) EEG
inf
(
3.3 MALA WITH CONSTRAINT
From the previous discussion, the approximate and target distribution should be close in the Wx distance maintain the pure DP. According to Lemma 8] this requirement translates into an exponentially small TV distance error. Therefore, we utilize MALA, asymptotically unbiased sampler, which converges exponentially fast in TV distance accuracy. Lemma a bounded set, leading to discard samples outside our predefined domain as described in Algorithm To guarantee finite termination of the algorithm, we set a maximum restart number Tmax- We provide the expected runtime, which suggests that the algorithm typically concludes during the early trials.
g also underscores the necessity of sampling within
Notations. Define the objective function .(0) = i= Let π and p" be the unconstrained and constrained Gibbs distribution respectively with density T(0) oc e e->J(0), and (0) x e) 1 10 E O). Let B/a be the condition number, where B and are defined in Assumption 2 respectvell.
>" (0). and its minimizer l = arg mingeg (0).
Assumption (Smoothness). Function J n.8-Lisschizz smooth.
Assumption 2 (Strong-Convexity) Function J is na-strongly convex.
Assumption 3 (Domain bound). The domain is a convex set such that B(0",R)) C O, for R4 2 28/ qno"
1 with initial distribution pd (O0 yh step size h + min 1113((mm3 (d In In 1/1) (1baa))) number of itera- / /dln In 1/E, dr)) dx))) and maximum number of restarts
Theorem (Mixing time in TV-distance). Consider Algorithm
tions K @ ((dIn In 1/E) max 3/2
Tmax (In 1/E)- Under Assumptions
2 and 3 this algorithm converges to E-accuracy in drv (pout, p where Pout is the oulput distribution. The expected number of gradient queries to J is given by:
c (Idlnx+ In 1/E) max /d212/dmnn In 1/{,
Corollary 10 (Mixing time in Wor. distance). Consider the Wos distance with respect to the 1-norm. Let the domain θ be a ball of radius B. Under the same assumptions and conditions as Theorem 7 with choosing In (1/E) Oym3B dl B+d In d+ d The expected number of gradient queries to J is given by:
Algorithm Convergess to A-accuracy in W (Pout, PP"
@ (ddn(()Bd) d1n(1/A) + ²m3B²) max 3/2/2 / dd([BBdd + dln(1/A) mmBB2 dn
Each gradient query to the empirical risk J translates to n queries to the individual losses & 's.
The proof of Theorem I and Corollary i0 provided in Appendix F
6

---

Published as conference paper ICLR 2024
Remark 11. According to the choice of parameters B, y in Table 2 we have 7 (L/Tn). We note that the computation dependence on (d²)), and the number of queries to the individual losses L is (n).
comparison, if we employ vanilla rejection sampling (Casella al.) 2004) with a proposal distribution of (0, 5m13 I), then the convergence time scales as e a)j el(n- 1)d, where R₁ is defined according to Assumption This factor scales exponentially with the condition number & and the dimension
Algorithm 1 Metropolis tattropolii-aajustedd Langevin algorithm (MALA) with constraint
Input: Stepsizes {Λ*}, J. number of (inner-loop) iterations K, objective function J, domain O parameter 7. maximum number of restarts Tmax-
for t. 2, mmax 1 do Sample 0 according to distribution n for k
K 0, do
Sample 0++1 ~ N (0+ , ( 11
Sample #+1 ~ U(0, 1]. denote p(- (() as the density of N (0 N/), 21
p (04)0h+1) TT(h)
p [0k+1 (k) π (Ok+1) < +1 then
7:
gh+1 + gR
end if end for
10:
if OK
θ then Return 0 and halt
Accept the sample
12:
13:
end if end for
14.
15.
Return an arbitrary 0 θ
4 MAIN RESULTS: APPROXIMATE SAMPLE PERTURBATION (ASAP)
This section introduces Approximate Sample Perturbation, along with the end-to-end localized ASAP.
4.1
APPROXIMATE SAMPLE PERTURBATION (ASAP)
ASAP (Algorithm 2 is designed to maintain pure DP and pure Gaussian DP by smoothing out an MCMC sample. Theorem establishes the pure DP and pure GDP guarantee for the ASAP algorithm.
Consider two randomized mechanisms: a reference mechanism M and another mechanism M. Assume that M satisfies pure DP or Gaussian DP, whereas M does not inherently offer these DP guarantees. According Theorem if the distributions of M and M have bounded disparity Wa distance, then it is feasible achieve pure DP (or Gaussian DP) by generating samples from M and appending noise scaled in proportion the Wo bound.
Algorithm 2 Approximate SAmple Perturbation (ASAP)
Input: Dataset D, reference randomized mechanism M : X - Pu. Woo error A, black box sampler
M such that W (M M(D)) < A. Privacy parameter e' if pure DP (μ² if Gaussian DP).
2. Run the MCMC sampler: M(D).
Return Ô Ō + (0, 4 if GDP (or Ó Ø Z with Z, Lid (ap(2A), ), 1,..,, d if pure DP.)
7

---

Published as conference paper ICLR 2024
Theorem 2 (DP Guarantees for Approximate SAmple Perturbation). Let M, M be randomized algorithms with outpur space θ C IR that satisfy the following for any input dataset D:
(s(M(DD,, S A.
1. Suppose we define Wo with the 2-norm. If M satisfies j--DPP, then the procedure M(D) [0, (1r)zaa) satisfies vp² + HR..DP.
2. Suppose we define Wx with the 1-norm. If M satisfies e-DP, then the procedure M(D) Z with
Zi ~ Lap(" 2- i.i.d. for = 1.... d, satisfies (E -'D-
The proof provided in Appendix( As demonstrated Section and the proof, W 2o distance guarantee is essential to obtain pure DP and pure GDP with ASAP. Other weaker distance metries such as TV distance and W2 distance are generally insufficient for this purpose. Remarkably, as shown Lemma X when the domain is bounded ball and the density is bounded away from zero, we can convert weak TV distance bound into a strong Woo bound. This enables the application of Algorithm across various scenarios.
4.2 LOCALIZED ASAP AND THE END-TO-ENN -NN GUARANTEES
Lemma 8 suggests that sampling should be conducted within bounded 2-norm ball. Therefore, before sampling, we first localize to a bounded ball centered at the initial point Og denoted as θ = B(0,- B) {0 ||0 8ull2 < B}. After this localization, we implement the ASAP algorithm within the defined bounded domain, referring to the approach as "Localized ASAP."
Algorithm 3 End-to-End Localized ASAP
Input: Parameters y, À 0, B as given in Table 2 Wasserstein-infiiig error A. Dataset D, individual loss & satisfying G-Lipschitz continuity, B-smoothness, and a-strong convexity, Privacy parameter j for GDP (or e' for pure DP) for ASAP. Denote (0) = Σ;= (0) + 211 0,
Run the localization Algorithm 4 and assign its output to ty.
3: Call ASAP (Algorithm
2) with inputs
A, D, y, privacy parameter e' if pure DP (μ' if Gaussian DP)
M + Algorithm on the domain θ [0]]|0 - 0oll2 < B}, setting hus K, Tmax as per Table
M Reference distribution with density PMM(D) (0) 1-- doll s B),
and assign the output to 0. Return 0.
The computational efficiency of the sampler depends on the choices of B and 7, well as assumptions on the loss functions. The quality of the solution from the localized ASAP depends on the initialization lg. and the associated choice of B. We instantiate these parameters concretely in Appendix B
We provide the following privacy, utility, and computational guarantees for the end-to-end Algorithm 3
Theorem 3 (Guarantees for Scalized-ASAP) Set 0,g B, as Table Let be the output of Algorithm Set the pure DP (or Gaussian DP) parameters for the output perturbation and the ASAP to be (or μ). Then
1. satisfies 3e-pure DP (or /3p-Gaussian DP).
2. In pure DP case, the empirical (total) risk satisfies
B|C(O)] L()") so (dC" (Ind + lnx)
ang?
8

---

Published as a conference paper ICLR 2024
In the Gaussian DP case, the empirical risk satisfies E[C((]) - _())) S O 3. The expected overall runtime time of the algorithm for pure DP is given by @ nd (wIn(ds) In max {1312 d (K In(dx) + In Im), dx In(dk))
(d((dn)))) comp
The expected overall runtime time of the algorithm for Gaussian DP is given by @ (n dlnn + is 1:In k) max 12 / + d n + K kln di In(1s))
The proof is presented in Appendix H
Remark 12. The suboptimalityy bound matches the thoooeiiion-teerrtticc
theoretic limit this problem in (Bassily
et al. 2014) up to constant factor. We enhance the dependency in the empirical risk bound from O to (log x). To our knowledge, this is the first (() time algorithm (assuming
polylog(n) for DP-ERM (Lipschitz, smooth, strong convex losses) that achieves the optimal rates under pure DP. The nearest algorithm is from (Bassily al. 22014), exhibiting runtime of O(n") ). A nearly linear-time algorithm for DP-SCO in the smooth and strongly convex setting that achieves optimal rates exists (Feldman et al. 2020). But to the best of our knowledge, the problem remains open for DP-ERM until this paper.
Remark 13 (Improvement under Gaussian DP). The risk bound for pure DP, combined with the transition
from pure DP to Gaussian DP (as per Lemma T5), inherently provides a DP-ERM learner under Gaussian
However, we improve the dimensionality dependence the empirical risk bound, from Ô (df) (dd) under Gaussian DP with slightly less runtime.
DP with suboptimal risk bound of O d'G
anp
Comparing to the existing work. Current literature lacks pure DP or Gaussian DP learner that attains the optimal rate for strongly convex problems nearly linear time. The closest approach, Noisy Gradient Descent, runs in (n) time for strongly convex and smooth problems (with s: log n iterations), but its empirical risk is suboptimal by factor of k log n. An alternative parameter regime that runs Noisy Gradient Descent for (n²)) iterations (i.e., (n²) time) achieves the optimal rate (without additional A or log n dependence), albeit more slowly and without leveraging the smoothness. Further details are provided in Appendix J
Other works either operate in a different setting or do not apply to all problems that we consider. For instance, objective perturbation with approximate minima perturbation (lyengar et al. 2019) runs in O(n) time but is restricted to generalized linear losses, Feldman et al. (2020) develop a nearly linear time DP learner using a "privacy amplification by iteration" technique, yet it works under the DP-SCO setting, which is different from DP-ERM that we consider. The same algorithm for DP-ERM still requires O(n²) time. In addition, their focus was on (c, 8)-DP. The sampler from (Gopi et al. 2022 (without combined with localization) operates Ö log(d/o)) time, but becomes vacuous when aiming for 8 = 0 for pure DP or pure Gaussian DP.
5 CONCLUSION
Our proposed sampler Approximate SAample Perturbation (abbr. ASAP) perturbs an MCMC sample with noise proportional to its Wasserstein-co distance from reference distribution that satisfies pure DP or pure Gaussian DP. We show that our sampler obtains the first nearly linear-time end-to-end algorithm that achieves the optimal rate in the DP-ERM problem with strongly convex and smooth losses. The new techniques we developed might be of independent interest elsewhere that rely on approximate sampling.
Limitations. While the posterior sampling mechanism is known to achieve optimal rates in the general convex Lipschitz loss cases under pure DP and pure Gaussian DP (Gopi et al.) 2022). ). a meticulous adaptation of our method is necessary to attain optimal rates in this scenario with fast computation. It remains intriguing open problem to characterize the optimal computational complexity in settings that lack smoothness or strong convexity.
9

---

Published as a conference paper ICLR 2024
ACKNOWLEDGEMENTS
The research is partially supported by the NSF awards: SCALE MoDL-2134209, CCF-2112665 (TILOS), as well as CNS-2048091 (CAREER). It is also supported by the U.S. Department of Energy, the Office of Science, the Facebook Research Award, a Google Research Scholar Award, well as CDC-REA-FT-23-0069 from the CDC's Center for Forecasting and Outbreak Analytics.
YL acknowledges Geelon So and Yuxing Huang for discussing the proofs in the paper. YW appreciates early conversations with Eric Vigoda, Zongchen Chen, and Daniel Stefankovič at 2022 Summer School on MCMC in UCSB. Finally, the authors thank Jinshuo Dong for communicating Lemma 15 to us.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow. H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Jason Altschuler and Kunal Talwar. Resolving the mixing time of the langevin algorithm to its stationary distribution for log-concave sampling. In The Thirty Sixth Anmual Conference on Learning Theory, pp- 2509-2510. PMLR, 2023.
David Applegate and Ravi Kannan. Sampling and integration of near log-concave functions. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pp. 156-163, 1991.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. 2014 IEEE 55th Anmual Symposium on Foundations of Computer Science pp. 464-473. IEEE, 2014.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. arXiv preprint arXiv:2206.07116, 2022.
George Casella, Christian P Robert, and Martin T Wells. Generalized accept-reject sampling schemes. Lecture Notes-Monograph Series, pp. 342-347, 2004.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34:14771-14781, 2021.
Etienne De Klerk and Monique Laurent. Comparison of lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing. Mathematics of Operations Research, 43(4): 1317-1325, 2018.
Christos Dimitrakakis, Blaine Nelson, Zuhe Zhang, Aikateirni Mitrokotsa, and Benjamin IP Rubinstein. Differential privacy for bayesian inference through posterior sampling. Journal of machine learning research, 18(11):1-31) 2017.
Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In International Conference Machine Learning, pp. 2597-2606. PMLR, 2020.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 2022.
10

---

Published as a conference paper ICLR 2024
Raaz Dwivedi, Yuansi Chen, Martin Wainwright, and Bin Yu. Log-concave sampling: Seropolis-HHastinge algorithms are fast. Journal of Machine Learning Research, 20:1 -22, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284, Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211-477, 2014.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp- 439-449, 2020.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301. 1235, 2023.
Joseph Geumlek, Shuang Song, and Kamalika Chaudhuri. Renyi differential privacy mechanisms for posterior sampling, Advances Neural Information Processing Systems, 30, 2017.
Clark R Givens and Rae Michael Shortt. A class of wasserstein metrics for probability distributions. Michigan Mathematical Journal, (12):231-244, 1984.
Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. In Conference Learning Theory, pp. 1948-1989. PMLR, 2022.
Roger Iyengar, Joseph Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium Security and Privucy (SP), pp. 299-316. IEFE, 2019.
Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Global linear convergence of newton's method without strong-cone connexity or lipschitz gradients. arXiv preprint 1XXXv:88060004133. 2018
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high- dimensional regression. In Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings, 2012.
Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach obtaining (1/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv: 121.22121 2012.
Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pp. 1302-1338, 2000.
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I. Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 16:20881-200885 2019.
Oren Mangoubi and Nisheeth Vishnoi. Sampling from log-concave distributions with infinity-distance guarantees. Advances Neural Information Processing Systems, 35: 35: 12633-12266,, 2022.
Eric Mazumdar, Aldo Pacchiano, Yi-An Ma, Michael Jordan, and Peter Bartlett. On approximate Thompson sampling with Langevin algorithms. International Conference Machine Learning, pp. 6797-6807, 2020.

---

Published as conference paper ICLR 2024
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Symposium on Foundations of Computer Science (FOCS'07), pp. 94-103. IEEE, 2007.
Kentaro Minami, Hltomi Arai, Issei Sato, and Hiroshi Nakagawa, Differential privacy without sensitivity. Advances in Neural Information Processing Systems, 29, 2016.
Darakhshan Mir. thforrition-theorrticc foundations differential privacy. In Foundations and Practice of Security: 5th International Symposium, FPS 2012, Montreal, QC, Canada, October 25-26, 2012, Revised Selected Papers 5, pp. 374-381. Springer, 2013.
Rachel Redberg, Antti Koskela, and Yu-Xiang Wang, Improving the privacy and practicality of objective perturbation for differentially private linear learners. Advances Neural Information Processing Systems, 2023.
Théo Ryffel, Francis Bach, and David Pointcheval. Differential privacy guarantees for stochastic gradient langevin dynamics. arXiv preprint arXiv:2201.11980, 2022.
Jeremy Seeman, Matthew Reimherr, and Aleksandra Slavković. Exact privacy guarantees for markov chain implementations of the exponential mechanism with artificial atoms. Advances in Neural Information Processing Systems, 34: 14:13125-13136, 2021.
Volker Strassen. The existence of probability measures with given marginals. The Annals of Mathematical Statistics, 36(2):423 439, 1965.
Yu-Xiang Wang. Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference Machine Learning, pp. 2493-2502. PMLR, 2015.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pp. 4782-4817. PMLR, 2022.
12

---

Published as conference paper ICLR 2024
Appendix
Table of Contents
Additional Preliminaries
B Localization Techniques
Parameters Localized-ASAP
D Experiments
D. Theoretical lower bounds
16
D.2 Empirical Risks Real Datasets
16
E Proof the Conversion Lemma
19
E.1 A Key Lemma: Another Characterization of W Distance
Proof of Lemmal8
19
Proofs of Theorem and Corollary 10
21
G Proof of Theorem?
25
Proof of Theorem
26
Deferred Proofs of the Supporting Lemmas and Corollaries
31
Proof Lemma and Corollary 20
1.2
Proof Temma
Lemma
.............
31
1.3
Proof of Lemma 14
32
1.4
Proof of I Lemma
34
1.
Proof of Lemmal 15
34
Proof Lemmal
Facts about Noisy Gradient Descent
13

---

Published as a conference paper ICLR 2024
A ADDITIONAL PRELIMINARIES
Lemma 14 (Adaptive Composition). Let Mi + A satisfies EiDDP (or PDDGPP and M₂ 3 x X - A 00 satisfies E2-DP (or (u2-GDP) with probubility 1 when its first input 0, ~ (D)D).oo for any dataset D E X", then M1 x M2 satisfies (E1 + E2)-DP for V + (D2G)P)
The composition theorem traditionally requires M2 satisfy DP (or GDP) for all 82 O2. What is stated above is slightly weaker in the sense that we can ignore measure 0 set. We defer the proof to Appendix I.3
Lemma 15 (Conversion between pure DP and GDP). With denoting the cumulative distribution functttooooooni of the standard normal, an E-pure DP mechanism also satisfies y-GDP with
= 24 1 1t
We defer the proof to Appendix 1.5
Definition 16 (Exponential Mechanism McSherry & Talwar 2007 For quality score u, the exponential mechanism My: : X + A samples an outcome with probability proportional to exp (Eu(x.)) is c-DP, where Au is the global sensitivity.
and
2Av
LOCALIZATION TECHNIQUES
The choice for the algorithm for providing On and the associated B parameter in Algorithm 3 is delicate. We construct an appropriate algorithm to find 0g in this section. In particular, we use approximate output perturbation.
For the general Lipschitz loss setting, output perturbation does not quite work as it does not even achieve minimax rate. But if individual loss function é satisfies a-strongly convexity, [Bssill al. (2014) showed that one can obtain a localization using output perturbation that qualifies such that the downstream exponential mechanism on the localized is optimal. The key observation is that under strong convexity, the sensitivity of 0r = arg min, Σ (0) can be shown to be (((m)) and output perturbation satisfies pure-DP, also it satisfies (with high probability)
2Gd (og()
100 0- <
ane
This order suffices for the posterior sampling to achieve the optimal rate.
We provide the following Approximate Output Perturbation algorithm, wherein we introduce perturbations the approximate optimizer.
Algorithm 4 Approximate Output Perturbation
Input: individual losses {Le j satisfying G-Lipschitz continuity and {-smoothness; strong convexity parameter Privacy parameter y for GDP (or for pure DP).
Denote C()) i (0), and 6* = arg ming L(0). Set Å
2G an
Solve for Oapt that satisfies 00ppt - 0* 12 < I D> Instantiation: Gradient Descent or Newton Descent.
Output 0g Oupt + Z, where Z; ~ Lap( VdA
for s-pure DP (Z; ~ NO0 3 for p-GDP).
4:
Remark 17. For step 3 we make the optimization oracle black-box algorithm that enjoys linear convergence rate. Instantiation of the optimization oracle could be the Gradient Descent or the Newton Descent, which enjoy linear convergence rate under the assumptions of strong convexity and Lipschitz
14

---

Published as conference paper ICLR 2024
smoothness (or c-stable Hessian by the Theorem of Karimireddy et 2018)). Note that 110 0 0 S I not a stopping criteria of the optimization algorithm. Instead, is a property that 0 would fulfill under the stopping criteria the additional assumption on L.
The following lemma provides the bound for the sensitivity of the minimizer 0*, which helps bound the sensitivity of the approximate minimizer
Let D X Let D' X" be a neighbor such that LD LD t some x E X, then Lemma 18.
2G
(D) -''))ll -
an
With Lemma 18, we can bound the sensitivity 0, thus providing the following differential privacy guarantees.
Lemma 19. Algorithm 4 satisfies & --iifferential privacy (or μ j--Gaussian DP).
We defer the proofs of Lemma 18 and 19 to Appendix
1.2
C PARAMETERS IN LOCALIZED-ASAD
The choice of and A. Larger y provides better utility guarantee but weaker privacy guarantee. We choose y by the following fact that the posterior sampling mechanism p² satisfies E-pure DP or H-GDP.
Fact (Optimal rates for strongly convex problems). The optimal (expected) excess empirical risks for G-Lipschitz continuous and a-strongly convex (individual) losses is d'G² and dG² angz onyz for E-DP and μ-GDP
respectively. For posterior sampling, choosing
1 an
==0
G
yields the optimal rate under u- y-GDP. Unfortunately. there are no parameter choices for r, X that can yield the optimal rate under pure-DP, unless è is already localized such that satisfies that Diam(E) I dG ans"
Then the choice of (.Dia works.
The choice of B (the radius of the localized domain). For desirable the utility and computational guarantees in sampling, we hope that B is large enough such that the mode 0* and the mean are in the localized domain θ, i.e., 0" E e and 0 E θ, where 0* arg mingge [(),, and 0 (g) 7.
Moreover, Assumption requires
C for efficient constrained MALA, where R1 2 8/ Taon"
However, by Corollary and the discussion after Theorem ! we know that an excessively large B should be avoided. This is because a large B leads to reduced Pmin, which in turn necessitates greater number of steps for constrained MALA to achieve the desired accuracy. Also, note that by Fact for e-pure DP guarantee, we set y 2öB which is dependent of B.
pure DP case, suppose Og is the output of Alogrithm then we have 6g Bopt + Z, where Z, Lap(2vd (T + 4) /ne). and |l0ppt 12 I Σ. Therefore we have
2d (G + ra) In(d/p) |00g - 00 < |1uu flopt ll + |10 #* ||2 = 12 l|0 1-
+
+ n'
naE
with probability - p. In the last inequality, we apply the fact that for Y; iid Lap(A), we have
d
(1X112 2 vddin(d/p)) = Σ Y? z d(AIn(4/0))))
PP P(V 2 Aln(d/p) s.p
15

---

Published as conference paper ICLR 2024
In order to fulfill the condition B(Ø", R1) C θ where R1 = 8V 8V yan inequality should hold:
note that 2GB the following
2d (G + Ia)li((pp))
B 8V
2dGB son
(2)
noE
The above incquality is satisfied with B 2 ( ()47)))
For the sake of simplicity, we let
ane
be sufficiently small and set B C.dG In(d/p)
In GDP case, similarly, we have 8g Popt Z, where Zi N(0,,4(+ 2 and ||0 - -0'12 S n. Therefore have
2V2(Ta G)(da++ (m(1/p)
100- 10 10, O oppel22 110.pt 00
-
Z
+ + n
(3)
onp
with probability 1 1- p. the last inequality where we use the tail bound for chi-square distributions by Lemma 1 in (Laurent Massart 2000,. Again we need R1 2 10u - -B where R₁ 8/ you and
7 on This is satisfied with B > 2v2(ra+G) (l(ll//)
Again, we let be sufficiently
amp
small and B CaGlvā+ (l(1/p)
ony
Lemma implics that the choices of pmin in Algorithm are valid lower bounds of the density function. We have the following corollary.
Calculation of Pmin
Corollary 20, Consider probability with density
p(0) exp (-7 Σ (((0) + 1110 00ll) 14110-00 0oll s B}.
+
1. Ift, is G-Lipschitz for all i, then ming p(0) e (2 +($+1) xd/=8"
2. Ift; is convex and B-smooth for all then all E O, we have
min p(0) 2 (- (
T( +1)
Applying Corollary 20 we calculate Pmin as follows: Take any 0' such that 100-ool12 I B. Compute
Pmii t mi (0') [(#+1)
74/3
D EXPERIMENTS
D. THEORETICAL LOWER BOUNDS
We visualize the excess empirical risks in Figure 2 and demonstrate that e-(pure) DP can outperform Os in theory, especially when the sample size n is large.
D.2 EMPIRICAL RISKS ON REAL DATASETS
Setup. We experiment on two real datasets: Red Wine Quality and White Wine Quality from UCI reposi- tory (https: http///rchivve ics uci
http://////iiiieiuaaaa 1 iiyy. The Red Wine Quality dataset contains 1599 samples with 11 features. We standardize the data and learn a regression task via
(0) { ) 3 ||01|2 which is strongly convex problem under 100 and p 0.01. The
16

---

Published as conference paper ICLR 2024
Table Summary our results the cn--strong convex DP-ERM problem with G-Lipschitz and 9-smooth losses and that the total loss satisfies con-ttonn convexity. The utility measures the expected excess empirical (total) risk. The polylog(n) factors are ignored from the computation. Observe that we are the first algorithms that achieve the nearly linear time computation under pure DP and pure Gaue-Ga DP while still obtaining the optimal excess empirical risk.
Privacy
Excess Empirical risk
Computation
NoisyGD (see Appendix
J
μ-GDP
aG famp?
n
NoisySGD Bassily et al. 2014)
(e, 8)-D)
dG² (gg(1/5/onee
n²
PosteriorSample Gopi et al.
2022
d-ppprox μ-GDP
aG² /omp?
2/a
ExponentialMlcchaiism Bassily et al.
2014)
E-DP
G /ane?
n
Localized-PS-ASAP (This paper)
(t-GDP
&G² /oay?
R/o² or 1/45/2
Localized-EM-ASAP (This paper)
e-DP
G² fons?
1/a² or n/a0/2
The choice of B, X, 0o. A, when instantiating Algorithm 3 for pure DP or Gaussian DP learning. The choices of y ensure the DP and GDP guarantee respectively and the choice of B that the sampling Algorithm run in O(n) time (condition on the high-prob event that 6" is inside the localized set θ Polynomial dependence
Table 2:
sufficient localization such
and other parameters are hidden in Ô). For pure-DP, the choice B has the additional GDP, choice only affects computation. The optimal rate (()) [( = O 4G is always attained.
purpose of achieving optimal rate for DP-ERM C()) [()") = O d'
one?
Y
Gu
p
E-Pure DP
Gdddnnd/pp)
Algorithm
1G 2ndac
1
2GB
dx
Jt-DP
A² am G2
C2G(v0+ S5Glvat/inn1p (m()/e))
Algorithm
vdG
V2n
dx
342
222-
Excess empirical
empinniall
6.00
302
280-
3.50
3.25
242-
2.75
1.0
Figure 2: Excess empirical risks from Table for strongly convex losses. Here d = 11, G 300, a 4,6 1. Left
n = 1e4. Right n = le6.
17

---

Published as conference paper ICLR 2024
Table Choices of step sizes, number iterations, and maximum number restarts Algorithm Gaussian DP.
pure DP
Pure Differential Privacy
G In(d/p) min d (k (xIn(d)) + Inn) - .1)) oB8n
hi
d (x In max { x /d (x Iun),, dxs
K
O
(d Inn))
Tinax
Gaussian Differential Privacy
hi
min N (dk + dlnn + km)) = 21) aBn (w
G
K
+ ((dk dlnn + kln k:) max 3/2 vdx dlnn In dr})
Tiax
+ (dk ddnn + K xnx)
lneer bourd tupto carsi)
304
lawa Lound conz)
Ours, cmppiial
Ours, emji cal
Cubsut perturbaiiss, emorical
Output perturat on empriic 01-00, orpitial
Excess empinical risk
10'
DP (de L0sl, omglriall
307
10r
empirical
30F
10-1
10-1
10-4
0.25
3.50
0.75
1.00
1.25
1.50
1.75
2.00
0.2
0.3
0.4
05
Figure Excess empirical risks strongly convex losses on Wine Quality Red dataset.
109
10'
Cutzut pertutbaiien emaincal
perfuraatin, emptriaal
Excess empitical risk
DP-C0 2m51 omptriaal
Dn-52 ampatcal
307
empirical
20F
30F
10
18-4
10-1
10-1
0.25
3.50
0.75
1,00
1.25
1.50
1.75
2.00
0.2
0.6
05
Figure 4: Excess empirical risks for strongly convex losses on Wine Quality White dataset.
18

---

Published as conference paper ICLR 2024
White Wine Quality dataset contains 4898 samples with 11 features. We standardize the data and learn a regression task via e 2 (z) 0 y:)² 2 1|01) which is strongly convex problem under a 32 and
P = 0.01.
We compare with the theoretical lower bounds in Table (up to constant), the output perturbation Algorithm and DP-GD with per-sample gradient clipping (no need to set the clipping threshold) by [B et al. (2022). The experiments are conducted under both s-DP and μ-GDP, We consistently observe that our algorithms outperform the existing ones.
Results.
PROOF THE CONVERSION LEMMA
E.I KEY LEMMA: ANOTHER CHARACTERIZATION OF Woo DISTANCE
To establish Lemma we commence by furnishing equivalent characterization for the Wo distance. We also demonstrate the attainability of the infimum in Lemma 22 Our exposition begins with the introduction of the concept of tightness.
Definition 21 (Tightness). A probability measure P on θ is called tight if for any e > 0, there exists a compact set K O, such that
P(e \ K) c,
Lemma 22 (Proposition 5 and Proposition of Givens Shortt (1984)) ) Let (O, be a complete separable metric space. Let P and Q be two tight probability measures on θ The Wasserstein-co distance has the following characterization:
(P, Q) inf(r > 0: P(U) S Q(U"), for all open subsets U UCO),
where the r-expansion of U is denoted by U = {o E θ dist(x, U) sr. Furthermore, the infimum in the Definition can be attained, i.e., there exists C* (T(,Q) such that dist(r, v)
ess sup Woo (P,Q) (x.0)((0x(.C))
inf (ET(P.Q)) (x.)))
ess (ist
The proof of this lemma is presented in Givens & Shortt (1984). For completeness, we provide a detailed proof in Appendix L6
E.2 PROOF LEMMA
Proof of Lemma 8 First note that || - 11-- S vdll - ylla. for all x,y- Therefore, it suffices to prove the lemma when dist the metric.
Fix and set Pmin 2-1 r/d/2+1y Ad, so that (dvv(P.Q) <.
4/22
To prove the result that W & A, we use the equivalent definition of Woc in Lemma 22 By this definition, prove Wo (P.Q) < A, suffices to show that
P(A) < Q(A-), for all open set C O
where we re-define A == fi E Rd dist (z. A) < A). Note that by this definition, A might extend beyond O However, we still have ((44) (A1 n ne), since Q is supported on O.
Note that if (A-) = 1, it is obvious that P(A) < ((4+). When A is an empty set, the proof is trivial. So we only consider nonempty open A θ with ((A4) 1.
Note that for an arbitrary open set A C θ, we have
P(A) Q(A) drv < Q(A) +
19

---

Published as a conference paper ICLR 2024
Thus prove P(A) & Q(A-), it suffices to prove Q(A) + Q(A*), Q(A A
To prove Q(A*) \ A) 2 &, we construct an lz-ball U C IR of radius 2/2 satisfying the properties:
1. U is contained in the A A,,.. U C A A, and
2. QU)) QUU (e) g
Notice that we only consider nonempty open set A C θ with Q(AA) < 1, we construct U as follows.
Intuition and Overview of the construction U. The construction of the ball U involves determining two pivotal points. Y and VA, located at the "boundaries" of A and A, respectively. We then define U v4 dist(ua-a)) Note that by the definition of A dist(ya, 2 A. To guarantee
U Bdist
Property 1 (i..., U C A A). Va is chosen such that dist(ya. (VA((//VA)) A. Additionally, to ensure Property 2 (i.e., ( 2 {). since Q(U) QUU n)), our aim is to maximize the "size" of U n O. Therefore, we specifically require ya belong to θ, while noting that A might extend beyond O The detailed selection process of ys and VA. and the subsequent construction of U, are presented below.
Existence and Construction of ya- To find the above discussed VA.. O, we first show that:
If ((A)) < 1, then 0(44) n e + 0,
where we re-define the boundary of A 0 ((4)) f
dist (2r, A) = A}.
We prove by contradiction. If instead (A*)) ne = 0, then for all x E e, dist(r, A) * A. Due to the continuity of dist and the convexity O we know that only one of these two statements holds:
dist(r, A) < A, for all æ E O
dist(ar, A) > A, for all E O.
Since 0 * A C O, there exist x' AA E O, such that dist(x', A) = 0. Therefore, the first statement holds. Thus θ C A which contradicts Q(A=) 1.
Therefore, 0(AA) ne + 0. Then there exists VA E ((AA) n O Thus there exist VA E θ such that dist A) A.
Construction of yA- Note that by the definition of dist(;, A) and that dist A) A, there exist уı A (the closure of A), such that dist(ya. = A.
Construction of U. Let y0 =
2atza and let U be the closed ball U = B(yn, A/2) = fo E 2
Rdd dist(rr s,, yu) S A/2]. We now prove that U S A A and that Q(U) 2 &, and then the proof is concluded.
1. To prove U C. CA A, A, xe U. We show that x E A and & A. Since Uv. E U and U is ball with diameter A, we have
dist(z, ya) S A, and dist(x, ya) S A
(4)
(ar & A). If A, since A is open and dist A) A, we have that dist ya) A. which contradicts to 4 Therefore v & A.
(xr E AA), Note that μa E A, thus dist(r, A) s dist(x, yA)
A, implying that x E A
2. To prove Q(U)= > &. note that we assume the domain θ to be an Eg ball. Since MA, VA E 0, by Lemma 24 we know that VoI(U n () I 1 Vol(U). Thus
1
Q(U) = QU ne) > Pinin VoI(U no) 2 2 Pmin Vol(U) = E.
20

---

Published as a conference paper ICLR 2024
which completes the proof.
Remark 23. It is worth noting that Lemma & and Lemma 24 exteend naturally to open balls. The necessary
modifications in the proof involve changing certain inequalities: "S" becomes "<", aad "> " becomes
Lemma 24. Suppose 0 E Rd, and R > 0. If there exists E IR such that E (0, R), and that
(8, R). Then (,,
Vol (B, (0, |a 22 ) n Be, (). Vol (Be, (0. (|]l2))
2 2
Proof Since a, -a (0, R),,, we have
||a 012 s n2, and - -013 < n²,
which implies
||al2 - 2(a, 8) + 11012 = R², and ||a| + 2(a 0) + 11013 - R².
Thus, ||al2 + |101 < nt?.
Denote S BN, (0. [|a|l)) ( (0, R). We first prove that - (- S) C (0,
(0, R). For an arbitrary
I E S, since x E Bj, (0. [|all)), we have |æ||2 < ||a||2, thus | < ||a
1 + 1010 < R On the other
hand, since x & Bb, (0, It), we have || - > R2. Thus ||
-1-x--0 -01 2 ([I= + +0 - I - 013 < n2,,
which implies - E Be, (0, R). Therefore - C BN, (0, R).
Since S B₁, (0, [all2) BB,, (0, R) and S _ ,3 (0, R). we know that S ( 0. Therefore,
2V) Vol(S) -) S) Vol ($ u (-S) s vol (Bee (0. ||a|12))
Therefore
1 Vol (Be, (0. Vol (Br, (0, Vol(s) 2 2
Vol (0, n
F PROOFS OF THEOREM AND COROLLARY 10
In this section, provide the omitted proofs and supplementary facts for the Metropolis- Langevin algorithm (MALA) with constraint in Section 3.3
We first provide the definition of mixing time. Given error tolerance (0, 1) and an initial distribution Po. define the g-mixing time in total variation distance as
(E.P² p²) min (A) I|p"
11vv 5
For simplicity, we denote L n3 and m no this proof.
Proof of T We separate the proof of Theorem into three parts via splitting of Algorithm innto the inner loop, the outer loop, and the case where outer loop count reaches the maximum. We note that the inner loop, Algorithm I is performing the MALA algorithm the unconstrained space Rd. In the outer loop, it performs a rejection sampling step that takes in independent samples from MALA and keeps rejecting samples outside of the domain & until one sample falls inside O. When the sample keeps falling outside O and the outer loop count reaches the maximum, the algorithm stops by outputting an arbitrary point 0 E O. We clarify the notations as follows.
21

---

Published as conference paper ICLR 2024
Notations. Let and p" be the unconstrained and constrained Gibbs distribution respectively with density (0) e->J((), and (0) x e->>(e) 1(0 O). Let D be the distribution of the unconstrained MCMC sample after K inner-loop iterations. Let p* (0) & (0) {0 E } be the distribution of the accepted MCMC sample. Let Pout be the output distribution of Algorithm [ Let Prail be the distribution within domain e, which is the output distribution when none of the Tmax trials belong to θ
Overview. We first bound the error in the inner loop - the TV distance between the unconstrained MCMC distribution and the unconstrained Gibbs distribution: drv (p* x). Next, we bound the error of the ac- cepted sample- the TV distance between the constrained MCMC distribution and the target distribution: drv ( pp) Finally, we bound the TV distance between the output distribution and the target distribution: dv (Pout,p").
For the inner-loop part, we cite the previous results. Consider the MALA algorithm on I& with step size of
h = 2 min {
((. 1/2 LLd )),
and initial distribution 2e satisfying Bp-warmness assumption that sup Theorem Dwivedi et al. (2019), we know that the MALA algorithm with the number of iterations
(A(
S So. Then by
T(4)
K θ (In In max (n3/2 1//2/nn Bo/B, dx
(80
converges to & accuracy in terms of the TV distance: ( TT) S. By Lemma of et al. (2019). we also know that on the unconstrained space, the Gaussian distribution A²(0, (1,,), is (2x)d/2 warm with respect the posterior distribution x with condition number k. Plugging in this warmness constant, we obtain that
K xo In 1/() max { /dlnx+ 1/ dkL,
Next, for the outer-loop (rejection sampling) part, we note that if the unconstrained S and π satisfies drv (ō* (()) < &. then also obtain bound for drv (p (0), (0)), the TV distance between the constrained distributions K (0) x p (0)1 (0 E Q) and p" p0) x x()1 (0 E @). Normalizing the density gives that p0) = [ Applying the concentration argument above provides the bound:
a (pEe)
f ( 1 (0 E O)d0 21 1 2exp 32d
mmR
2 2,
where the last inequality follows by plugging in our choice
22

---

Published as conference paper ICLR 2024
of R1. From the definition of the TV-distance, know that drv (p" (0), p (0))
= -lc0 10t((0 (0) p0)
= -Jcc
(*)))
p0(
d6
Saee fz (0)d0
Sace π (0)d0
i* (0)
i (0)
pz (0)
d0 +
Jece (0)d0 d0
Jaco $ (0)d0
Joco TT (0)
Joce (0)
Jaee f (0)d0)
1
k0t (0) (0))dd
Joce (())d0
Jace (0)d0
A
2
Joce (0)dd
S 46
where (i) follows from the definition of the TV-distance.
Replacing& & by E/8, have drv(p" p²) S E/2.
Then, we bound the "failure" probability - the probability that the outer-loop count reaches Tmax = (n(2/(). while the MCMC sample still falls outside O For the rejection sampling part, know that for each individual trial, the rejection probability equals the probability mass outside O Invoking Lemma 25 below, we obtain
that for 0 ~
(1|@ Ea-p(o) [0|
2 2r)
$ 2e
ad
and that for 0* being the mode of m
Ea~ ( -1-112 v
3
mm
On the other hand, B(8", C O. Since R
2 8
2
we have 10), c
7m
B(O", R1) O Hence, applying the concentration argument above for ~ n,
& + < 2e 928
Combining with the definition of the TV distance, we know that for 0K DK obtained by running the MALA algorithm (on Rd) for K steps,
PP (0k +
P ( @) + drv ,,)) < 2e
2m Ri 32a
+ E.
Hence with max independent trials, the probability that none of the Tmax trials belong to θ is
(None the Tmax trials belong to θ) (TP (ØK $ &0))
ym 32d
2e
+ E
x 12e + E) Tiaa
-mmax
23

---

Published as conference paper ICLR 2024
where we plug in R1 2 8V ym and without loss of generality assume < <1/1 < e - 2e- Therefore, by setting Tmax = (2(2/)), we have P (None of the Tmax trials belong to 6 - E/2.
Finally, bound the TV distance between the output distribution and the target distribution: drv (Pont P Denote the event Fan = { (None of the Tmax trials belong to b), and let Hsuccess = Fua be its complement. We know from the above analysis that P(H)))) E/2.
Let oout ~ Pout. Notice that
out Huucesss p and dout Hrail Prail-
We thus have Pout = (1 IP HF ) P(HFaa)Pral Therefore, for drv (Pout: p²) = sup Pout (A) p² (A)l
A
sup (1 P((Hraa))) (A) + P( Prai (A) p² (A) - P(H px (A) + IP ((Hra))rraaA))
(A) (A) sup S sup (1*(()
A
dTv(p" K .p') + P (Fraa)dTV pran) E/2 -
where we apply drv(p" ) s 8/2, P(Hrat) & E/2, and drv (p .Paa) S 1 in the last inequality. Therefore, we prove that drv (Pout: p²) S.
At last, we calculate the expected total number of iterations. Let That be the current count of the outer loop when the algorithm stops. Then Thatt follows the finite geometric distribution with the probability of success and the maximum number of trials Tmax- Therefore, 1-2--2-178 < 2, when & < 1/16 1/8.
in each trial equals P (KK θ 2 2e E(Thatt) )
Therefore, the expected number of total iterations is given by
K (TTutt) = e (ddIn + In 1/E) max { 1/3/ /dnx In 1/5, drc)
which completes the proof.
The universal constants regarding the number of iterations can be found in the proof of Lemma 7 in Ma et al. (2019).
Lemma 25. In Rd, ifa distribution is ym-strongly log-concave, then
[B-pp(0) 10] - 0- <
7m
where 8" denotes the mode of the distribution p(0). We also have that for θ ~ p.
P (11@ @ E [0]
2c
sd
Proof We prove this Lemma following the proof of Lemma 10 Mazumdar al. 2020
For BB [0] - 11 we use the fact that p(0) is ym-strongly log- cog-concave and consequently unimodal, and that
E [Boppro 1o) [0] 0-112 <
3
7/m
24

---

Published as conference paper ICLR 2024
For | - Ee-pto) [0] we note that p(0) being 7mm-strongly log-concave implies that the random variable 0 ~ is uub-Gaussian random vector with parameter o, random variable with constant o = Plugging into the definition of we obtain that for n,
27m Consequently, it is a norm-sub-Gaussian random variable,
(11 F 101| 2r)
2e
Proof of Corollary 10 Applying Lemma
8 to obtain A-accuracy in W distance, we want that
4/2
< Pmin
Ad
2d+1 r(g + 1)d4/2
where Pmin S ming (0) and p0( ( 100 E θ) as defined in Section 3.3
Since 8" E θ by Assumption 3 applying Corollary 20 we obtain that
I +1
min p' (0) 2ymam
4/2 gd
We then set
π 4/2
(pmin 2
I(5+1)
Pmin
2d+1
r[6 + 1) dd/d/2
7//2g
2ymB8"
2d+1 d B
Therefore, we have
1n O (mmBB² + dlog d dllog B + dlog(1/A))
Therefore, applying Theorem
we obtain that Algorithm the following expected number of gradient queries to J:
Daaammmoooo converges A-accuracy in Woo (Pouts p²) with
@ (ddnn(<Bd) + (dla)/)))))(()/)) + >m3B²)
max
G PROOF OF THEOREM 2
We first provide the following lemma that converts the distance between probability measures to the distance between random variables.
Lemma 26. Let P,Q be two distributions defined on & such that W (P,(P < A under metric dist θ R. Let X P, there exists random variable Y Q such that Pldist(XX S =1
The proof of this lemma is deferred to the end of this section.
Proof of Theorem 2 Let M(D), by Lemma 26 and the condition Wo distance, there is coupling
( such that random variable y ~ M(D), (x, y) ~ Ç. and dist(æ, y) < A with probability (with respect to
(). The distribution of is equivalent the following two-step procedure
25

---

Published as conference paper ICLR 2024
(1) y ~~ M(D)
(2) x ~~ C(-b))
The second step can be further viewed first sampling Uniform([O, 1J) and then mapping u deterministically by data-dependent function x g(u) where is completely determined by ((-1y) via the inverse integral transform. g depends on D and y through Ç.
g<(u) =g<(u) resulting coupling under D'. With probability under ç. I1g;(u) yll S A. Similarly with probability 1, under Ç", llg. (u) vll z A.
Define query fu,y( (D) =
y and on neighbor dataset D' fu, (D') = (v) where Ç' is the
By union bound, with probability 1 (under ç(- g) x ('(-ly)), the global sensitivity of this query fu.y satisfies ( (D) fu, - [1 vil + (1)e. vil - 2A. Recall that ASAP returns å = - y (x: y) + Z. In the above, x y = ( By choosing appropriately as the Gaussian mechanism (or Laplace mechanism) and the adaptive composition theorem (of GDP and pure-DP), we establish the two stated claims.
Proof of Lemma 26 By the attainability of infimum for Woo stated in Lemma 22 and that WZ A, we know that there exists joint distribution Ç(x, y), such that the marginals in x and follow P and Q respectively, and that ess (uP().))e(xxe.3 dist(x, y) W (P, Q) S A. For given X P. we define a conditional distribution ((-1x), then taking Y ((-(a) statisfies P(dist(X, s A =1
H PROOF OF THEOREM 3
Proof of Theorem 3 We divide the proof into three parts: privacy, accuracy, and computation. We first present the proof for pure DP case.
Privacy. The privacy analysis follows from the adaptive composition (Lemma 14 of output perturbation &-DP and ASAP (2s-DP, Theorem 2
Accuracy. Let E denote the event of |10g- Oopell2 <
2d(G+ra) In(d/p) where Ous Oopt is defined in
Algorithm for pure DP. Then by Lemma 17 of (Chaudhuri et al.
2011
P(E)
2 1 - p. By the choice of B
from we know that under event E, we have (00",, R2) C O, where R2 = 8V and thus Assumption
holds.
Denote á the output of MALA with constraint (Algorithm and denote p" the exact posterior.
We then divide the risk into two parts
E [c(0)] L()') = c())) [(0]
EE E [<((0]] L()").
(5)
For the first part, note that 0 0 + Z, where Zi hid Lap(A i= 1,..., d, thus we have that
Jensen's 's incquality
110 0||2
E 110 013 = -v E z?
= V2d
With the nG-Lipschitz continuity of L, have
2dnGA
E c(0)
[(0)
s nGE
[|0
0112
(6)
E
For [(()]] L("*), the second part of the rinht-hand side of the equation 5). we consider two cases:
26

---

Published as conference paper ICLR 2024
1. Under the event E. By Corollary I0
we have (p. S A. Since W (p.p") I A, applying Lemma 22, there exist coupling of p and p", denoted as S", such that css (e ulla I A, thus ess sup (e. ull2 I A. Take p C(-10), then we know poet ~ p'.
We divide
(()) - _(0") E [(()) (( )
+ (TE (C((0 post )|F} L(0*)
(7)
With the nG-LLpschitz ii-niischhttzcootinuityy of L, we have
(0 )-m [(0) [(0post) E S nGT (0,0 (pmr [10 8 poost (pcat|/2/E/] 1 InGA,
(8)
which is dominated by 6 By Lemma have
B[c((p L()*) S d
(9)
2. Under the complementary event E For simplicity, set 7 in Algorithm to be sufficiently small and exclude this factor. By the n-3-Liscchtzz smooth of and the first-order condition, we have
E [()) 2(0))
nB R |10 0 2
12)
- n2 E
(10-
ooll 110 00 001l2)
E
E
(B + 1100 00111)210*
2
(10)
By Lemma 27 have
vdG 2
d(d+1)
+ B² + (d+ 1)B dG
E [100 -
so
ane
One
and
VdG ane
0 [110 0-112|b9]
d
B
Plugging these into 10 plugging in B/a,, obtain that
Gd angz
B[C(O) - C(0") s 0
(11)
Therefore, adding 6 8 and 9 as well as adding (6. and respectively, we obtain
[ C((") < V2dnGA
d&G22 (n(d/)/d))))))))))) and one?
+ +nGA +
(12)
E
E [())EE] C((') 5 VdnGA
GP ang
d2G2 (In(d/p) + dr) ang?
O
(13)
8
where we instantiated our choice of GDiam with Diam (0ameO = 2B
2CdGlog(d/p)
and
dG log(d/p))
2 G log(d/p)
2n
27

---

Published as conference paper ICLR 2024
With 12 and 113. we have
18
[(0]]
-(0))= -PE)) [(O)
+ +1 P(E)) E3 [(0)) c()-)
(C(3/((/p))
CP (In(d/ p) dk)
0
+ +p.
ane?
ams?
|f (Ind + In(1/p) + pokk)
anE?
Taking O (1/(dx)), we obtain
( (Ind+In) Inx)
[(0) =(0")=0 =0
an
Computation. time for getting solution satisfying ||0g 0" 1/n². For the sampling step, following the proof of Corollary I0 the expected computation complexity is bounded by
The optimization oracle (c.g., Newton's method or Gradient Descent) runs in On log n
((1 E) Thalt E + pTmax)
Applying Corollary 10 with taking proper B CdG log(d/p)
we have [halt [ ~ O().
ane
Plugging y given in Table
for pure DP, obtain
{ = e 2ymBB²
2d+1 dd/2 Bd
e 2d+1 dd/2 Bd Ad
(7 2GB
= Cjndln(d/p)
onE
A
(B
GrGdln(d/p)
K g
2d+1 dd/2
Gd
ane
Therefore, we have
GdIn(d/p) one
+ dln 2
In 1n O
kdln(d/p) dlnd dln
(Gdn(d//p)
0
kddn(d/p) dln
(n _ > 1, p << a
ansA
we obtain that Algorithm I converges to A-accuracy in W (Pont, p²) with Therefore, applying Theorem the following expected number of gradient queries to J:
[nnx + x In(d/p) + In e (a (Imn
(G)n(((p)) max mo/2// d klu(d/p) + In aneA
GdIn(d/p)
)) dr
ansA
0 (pd (xIn((//)) +ln
(lI((d/p)) max 13/2 Va <<n(dd/p) +ln
(GIn(d/p) ,dn.
))
aneA
oneA
28

---

Published as conference paper ICLR 2024
Plugging in A Gdlogid/p) 2n
as given in Table 2 we have
K + (x + In)) max 3/2 Vd + (nn),dx())
Therefore, the expected total computation complexity is given by
+ nd (n:Indd/)) + nn max {x3/2 / (xlldd(/pp) + lnn), dr (1 + pd (wln(d/p)) + +n))))
Taking O (1/(dx)), assuming (Imn)/K & (1), it translates into
nd (nlkk))) + In)) max { 3/2 V (xln(d))) + Inn), dx In(drs).
Gaussain DP case. The analysis of Gaussian DP closely parallels the proof of pure DP case except for the slight difference in the accuracy and computation analysis. Here, we present a simplified proof.
Let denote the event of ||ou - Ooptll2 S 2V2(ra+G)(V (i(1/o) where fu 8opt is defined in Algorithm
for Gaussian DP. Since 0g- Oppt + Z. where Z, ~ NOO 4(T chi-square distributions by Lemma 1 of (Laurent & Massart 2000), we have P(E) 2 By the choice of from (3). we know that under event E, Assumption 3 holds. For simplicity, we Algorithm to be sufficiently small and exclude this factor.
a _)² /n2 p²²). applying the tail bound for
Under this event F., by Lemma similar to the pure DP case, we have
d
nGVdA
dG²
E[C(O]E]] C(0 +
o
ampy
where we instantiated our choice of y
amam G
and A
VaG /2n2ap'
On the other hand, under E applying Lemma
27 by taking k d/2, and o )2 we have
G2 (dd++n(11p))
E [100 apt
E
(amp))2
Thus by the nB-Lipschitz smooth of L and the first-order condition, we have
E (())
[()0)
n18 E 10 E
n,3 E
(1ō 0oll2 - -1100 071aa "E"
(14)
(d+ (1n(1/01)
0o
amp²
Therefore, by combining the two cases, have
(
G (d pkd + pr pnsIn(11p)))
- so
anp?
Taking p = (1/dk),, we obtain that
(Cdd +10++lx)))
E[C(O)) - 2(0)) 0
anze
Applying Lemma taking the B,7, A, p as Table 2 for Gaussian DP, assuming (Inn)/K S O(1), the
expected total computation complexity the Gaussian DP is given by
n (dx + d Inn n + x kn) max { 1x2/2 2 + d + x lm, dis in(xs))
29

---

Published as a conference paper ICLR 2024
Lemma 27. Let X be random variable drawn from the Gamma distribution ['kk, σ), with the density
x o*T(k)) for 0, 0, and σ O.
[(x; o))
Suppose 2 1, thenfor any a > 0, we have
E(XXX > a) S ko + and B(X²XX > a) S k(k 1)0² + +a² + (k + 1)00.
Proof We have
B(X > a) Le of(=;k,o)d
1e xee - da Sa x do Sajo e Salo - r( a(k,o/o)
Sa f(i;k, odde
where 1'(k, t) is the incomplete gamma function defined as 1'(ktt) Le x z Applying integral by parts, we have
r(K kr(k)) e
We also have, for k 2 1,
t(k,t) (h: - 1)r(k 1,t) + t le 2 et
Therefore, for 22 1,
+ +(++1,0) t(k,t)
e
ehe
k +
S k: + x k + L.
t(k;t)
Taking = a/a,, we have
I(k + + 1, a(k,a/o)
E(X > a) S
S ko + a.
For E(X2IX > a), we have
~00 x f(1;kk Jo f(z k od
poc rhtle é dæ
B(X a)
xc zk - do Jaja e
Jajo rt xk-le-
[[k + 2.0/0)
I(k, a/0)
0² (k 1)T(k
+ (,,0)1/)))(///))
+ (a/o)
T(k,a/o)
50² (k+ 1)(k a/a) + (a/o)
(a/o)--1e-0)
0² 1) + a² + (k
30

---

Published as conference paper ICLR 2024
I DEFERRED PROOFS OF THE SUPPORTING LEMMAS AND COROLLARIES
L.1 PROOF OF LEMMA AND COROLLARY 20
Proof of Lemma
Denote 0 as the minimizer on O. Then
Z = / (00 do S 6))))))) / do -- (T/2(2
T(d/2 +1)
On the other hand, by the Lipschitz continuity assumption, J(0) - J(0*) - G. 110 1 001 || - GR. Hence
1 (00) 2 GR r(d/2+ 11)
7
(R/2(/
If J instead satisfies the 3-Lipschitz smoothhesss and convextiy assumptions, then for all E e
((0) - J((") = J(0) - J(0) J(Ø) _(0")
$ (J(0), 8) + 110 - 8|1 (V.(0),0 8)
8 10 0|
= -J((), 0*)
$ || 1
2 SR
Hence
I(2
inl (0)) (RIVJ( 8E8
vB e.
/ T (R/2)a
Furthermore, if 0 is the global minimizer, i.e., VJ(0") = 0, then
inf p(0) 2 >/88//2 /2 r + 1) 4/2
4θ E A.
deB
Proof of Corollary 20 It suffices invoke Lemma 9 by setting (00) Ei= 4()) + -0100 0o 1 and
θ = [0]100-
Boll S B), notice that the diameter of i 2B.
1.2 PROOF OF LEMMA 18 AND LEMMA 19
Proof of Lemma 18 By the a-strong convexity of Ln and first-order optimality conditions for 0* (D) +222 10) 0" (D')
(D (D') 2 (D (D)) + (D') 0* (D), (LD (D)) + on
2 LD (D)) + an |10 (D) - (
On the other side, by the a-strong convexity of LDr and first-order optimality conditions for 0 (D')
LD (or(0())) 2 Cn (0") (D) - (D'), (()() + an
- -0(D)))0((0)))
2 LD (D)) + am ||0" (D) - (D')
2
Add the two inequalities get
anl|0* (D) - 0' < Ln
(V'((((D')) - -O(O & - -L)(
The proof is complete by dividing both sides by ||0 (D) (D)Il
31

---

Published as a conference paper ICLR 2024
Proof of Lemma 19 It suffices to show the sensitivity of ((D) is bounded by A. Applying Lemma sensitivity of (D) is bounded by
18
D=D max []² (DD))_((D'\ll2
-00)) - < (1((D) - (D))
- D=D
max D=D'
+ -10(0")--
2T 2G
A
I.3 PROOF OF LEMMA
Proof of Lemma 14 First, observe that pure-DP (with any < oo) by definition implies absolute continuity. Let μ.. v be the two measures induced by a pure-DP mechanism on dataset D, D' respectively. DP implies that for any measurable set S. u(S) S <v(S). This inequality implies that if v(5) 0 then p(S) O. which verifies the definition of absolute continuity, i.e., / & v.
By our assumption, .M satisfies DP, thus (MI(D) absolutely continuous w.r.t (M, Similarly, M2(01, D) satisfies DP for all 0₁ except when 01 belongs to a measure 0 set, thus with probability 1, D)) is absolutely continuous w.r.t. (M) It follows that the "density" function (technically, Nakon-Nikodym derivative)
d''yyiD exists and d(Mato,_.) exists almost surely. In addition, by taking dPMpto,.o)
(D')
S = dPMjCD) > } (' the DP definition, by proof by contradiction we have
PoI~Mi(DD)laPMa (M,
dPMIED) (0₂) S c =1
(15)
and
dPMaton (O2) S 50 =1
P Da
(16)
almost surely under 01 ~ Mi')')
Let O₂ Mi(D) and O₂ M2(0 D). Similarly, let Ö Mi(D')) and Ö₂ ~ M2(02, D'). Consider
any measurable set c 0 x O2, by the Lebesgue integral
P[[O,,00) E S]
= / / 1((u1, u2) E
= / / I((11, v2) E ES) E) (P
dPMginn (u2) dP (r) dPMiies (m1) dP (PM((D)(
< / / 1((M), u2) E ES)ef= d dPMston.D((ss) 5t (PM((D)(u)) = Öz) E ST.
The inequality above follows from equation 15 and equation 16
For Gaussian DP, let P1 and Q1 be the probability measures of MD) and M2(D') respectively, and Pz(- |z = o) and Q2(- | o) be the probability measures of Mz(0, D) and Mz(o, D') respectively. Let and Q be the probability measures of (D) and MDD).
mensure definition PLM, (D') E 81 (D") S] which contradicts definition unless messue
32

---

Published as a conference paper ICLR 2024
We first show that P is absolutely continuous w.r.t Q. Noting that by the definition Gaussian DP and Hockey- stick divergence, Pi is absolutely continuous w.r.t. Q1 and P2(-|x- o) is continuous w.r.t. Q2(-1x = o) with probability Then, for arbitrary Q-measureable set A, we have that
P(A) = / / [((2,)) () E A)dP(e,
/ / 1 vI E ())P)()l2)dP((()
/ / g(( E A))P3((l)))P((()
/ / 1 vc E A)
dP2
dP1 (x))Q1(z)
(1lz)dQ2(10) (QQ2
(y)
x))
dQ2
dQi
/ / 1((,,)) E A)
dP2
dP1
(y)
())
(z)
dQ))d((.)))
dQ2
dQi
So (A) = 0 implies P(A) O, thus is absolutely continuous w.r.t Q. Moreover, from the above equity, derivative (z.
we know that the
aQ²
dPa
(v)z)
a4 (z).
Since P is absolutely continuous w.r.t Q, their Hockey-stick distance can be defined. We then have for 0,
H ((DMM)))
..H((PP (PIIQ)
= = /
dP
(v,v) v) dQ(x,v)
aQ
= -
dP
(2,8) 9) 2 a }
dP xz,
0 dQ(x,
dQ
[Q
-J
dP2 (y)
dP
dP2
dP'
=
(x) 2 a
(u|x)
(x) - a dQ2(vlz)d(
dQ2
UQi
1Q2
aQi
=J
dP3
dPI (x) 2 a
dP (x)
dP2
dP1 (x) -a) dQ2(vlz))Q11
=
dQ2
(ylx)
dQi
1
dQi
dQ2
(y|z)
dQi
dP2
(y)x)
dP1 (1)) 20
dQi (1))
dP
dP2
(y)
dP
(x)) dQ2(vlz)
dQ2
dQ₂
dQi
dP1
dP1
(x) 0
(x)
dQ1
dQ1
dP1 (x) > 0 of dQi
dP
(dP(()))) ((B((()))l(0(((+))))
(x)dQi(z)
(x))
dQi
dPI (x) > 0
dPi
$
(x)) (N(0, (100 1))
(x)dQi
dQi
dQi
= / dP (2)
dP1
dP
dP:
(x)
dPM((aa)) (2) 1
dP
(x) >
0
(x) (1)
dP
dQi
dQ
dQi
= / dPN(O.1) (2) dP:
(x)
(2)
dPN(vaa:))
dQ1
= H. (P) x N(0, 1) || Q x (((u,)))
33

---

Published as a conference paper ICLR 2024
Continuing this argument, we have
Ha (P) (N, 1) Qi x (V 1))
/ dP: (x) a. dQi
dP
dP (2)
(z)
dP
dPM(H221)
| H (PM(pga))
(PillQ1) dPN(0.1)
(z)dPN()a))(2)
aP
(x)
dPNiva:1)
dPN(o.1) (z) (2)dPN(w2.1(2))
Σ ar
1))
dPM(paa1)
aPN(0.))
dPM(O.))
dP'((00.)) (z)
dPv(0.1) (z) (1))
(w)
dP
"dN((.1))
dP
dPN((..)
(w) dPN(0.1) (z) - a)
dP dPPN(uz.))
= Ha (O, 1) x (0, || [[ x (N 1))
By taking (iw + /22)\ / 14 + p2g t = (WIW-P22 - /22)\ 1 + nzz we have,
Ha (O 1) x (N 1) N (M1, 1) x (p2,, 1))
= =/| exp( ((w )2) + (2 )12 Ct
exp(-(w² (w² + 2)))
exp( (o((--(w - 11)² + (= - ))2))))
2x
+
=/ / [exp(- 2( + 222) + +1² + (3)
a]
exp(-(1u) + x² -2( + m22) + 12 + 12) dwddz
+
2T
= / / exp( 28 V 1 + 12 + 14 + (3 a
exp( (s² + 8² 28 1t + 11 + .f + أ3) dtds
2m
/ / exp(-2s 12/
/ . + 1 + p
1
exp(-(3² - 22 ps + μي + + + p
2T
H. (N NVV 1 + 12.11
The proof is completed.
1.4 PROOF OF LEMMA
Proof of Lemma 5 Dong et al. 2020) showed that exponential sampling with utility function (D, that satisfies a property cal bounded range is differentially private even if the sensitivity is not bounded (unlike the original exponential mechanism).
range(g) D' neighhors
sup (max-mil min)mm((nD)nn -((",)))(((',)))) eE
BEE
In our problem, is the (regularized) sum of loss functions, and the difference in q between two neighbor datasets created by adding removing datapoint is simply the loss of one data point. ((D, q DD', 0) +()) It is easy to see that the range(g) < GDiam(O). By (Dong et al. 2020), we get that choosing 7 (e) gives eDD..
I.5 PROOF OF LEMMA 15 Proof Denote
fz.(2) = max cfx.e x)}, for 0 < 1,
34

---

Published as conference paper ICLR 2024
and
= - (1 -1 -4). for 0 S x S 1.
By Definition 3, Proposition and Definition 4 of Dfng et al. (2022). suffices show that fe,0(z) 2 (r), for all S < 1.
By the concavity of G and the piece-wise linearity of fe it suffices to show that Gy(aa)) fe,u(zu), with To Tite satisfying 20 e e zo. Taking 2 e
we have Gj (20) fe,o(2o))
which finishes the proof.
1.6 PROOF OF LEMMA
22
Proof of Lemma 22
Denote (ll csssupp:.) dist( (z,
To prove the lemma, it suffices show these two inequalities both hold:
inf ess sup dist(z, () - in > 0: P(U) s Q(U"), v open U c (ET(P.Q) (x.))(((xx.c))
(17)
inf (ET(P.Q) (exe,)
ess dist(x, inf 0: P(U) < Q(U"), A open U c
(18)
For the sake of clarity, denote
Wins CET(P.Q) (exe)
inf ess sup
dist(r,y) = inf
(ell,, and
<Er(P.Q)
WRHS inf 0: P(U) Q(T)), v open U O).
We first prove [77 To prove [17 it suffices show that for any WRHS, the relationship a Wi.s inherently holds.
In particular, we leverage the following Strassen's 's theorem and prove that both constants 3 and be driven to zero.
Lemma 28 (Strassen's Theorem, Strassen 1965)). Suppose that (O, dist) is separable metric space and 3 > 0. Suppose the laws P and Q are such that, for all open sets C O,
P(U) Q(U)) +
where U {x E θ dist(a, U) at.
Then for any & > 0 there exist law Cn θ x θ with marginals P and Q, such that ((dist(æ, y) + +) +
(19)
Take an arbitrary a > WRHS. Our goal to prove a 2 W WLHSS By the definition of infimum, we have P(U) - QU*)), V open U C θ
For arbitrary 8, by Strassen's 's theorem, (plugging in 19 there exist Ç3,e C(P,QQ) such that
Sa.s (dist(æx, y) a + E) 3 +e. We are going to choose 3, E to be sufficiently small (both go to zero) and take the limits using Prohorov's Theorem and Portmanteau theorem.
Taking 3 = = 1. by Strassen's 's theorem, there exists Sn. E I(P,Q) such that
Go (dist(z, v) > a a
1 n1 < 2
35

---

Published as conference paper ICLR 2024
Since P. Q are tight, for any E O, there exists two compact sets K1, K2 O such that
P(e) \ Ki) I e, Q(6 \ 5 c
Note that Sn E (IPP Q), we have (since 1 (( v) $ K1 x K2} - 1( & Ki + 1 $ K2))
((@ θ) \ (K1 K2)) - Cn (( K1) x )) Sa ( (0) K2)) - 2c
thus {Go [ tight sequence probability measures.
Since {Sn 100 tight, by Prohorov's s Theorem, there exists weakly convergent subsequence Sn(k) = C. We have T(P. Q) because Ç(A x θ) limg (A( )) P(A), and that ((9 A)
lime Sn(R) x A) Q(A).
arbitrary 0, the set {(x, v) e x x dist y) > a a open set in θ x θ. By the Portmanteau Theorem,
< (dist((, y) > a 8) s inf (a(k) (dist(x, y) > 6
k0000
1
< lim inf Sn(R)
dist(x, v) > a + n2k))
k-+00
2 n())
< lim inf
= 0.
k-
where the first incquality is by Portmantcau Theorem. The second inequality holds because there exist ko such that - a[Ako The third inequality holds due to the construction of Sn.
Since 5 arbitrary, (taking + and by Fatou's Lemma.) we have that
< (dist(zz))) a) = 0.
(20)
Therefore, a 2 ess essss (2, (x,y) y) = WL.ss Thus 17 proved.
Next, show that (18) holds. Similarly, to prove (17 it sufficess show that for any t > WLHS. the relationship t Z WRHS inherently holds.
Take an arbitrary t >> WLHS, our goal is then to prove that 2 WRHS. By definition of infimum, there exists a [[P, Q), such that
ess sup dist(x; y) < t. (mx))(((xx.))
Therefore, Ç (f(x,v) E 0 dist(x, v) +)) O. which translate into
/ lddist
v) (x,
(dd((r, v) = 0.
(21)
Thus, obtain that
36

---

Published as conference paper ICLR 2024
Q(U") Q E O dist(y, ( 5
H U) s ()d((z,))
MFE U) {t)d((x,))
/ [) 1fx E UJ1 t)d((x,
(If E U and dist(y, U) then dist(r; v) t.)
/ (=EU)NEC))((..)) (dist((z, > f)d((2.))
(Plug in 21
1 P(U).
Since Q(U9) 2 P(U), we have
te (r & Q(U"), V open U C
Thus
1 12 ia > 0: P(U) < Q(U)), A open U C C = WRHH-
Therefore, holds.
Since 17 and 18) hold, we have
inf ess dist(r; y) = in >: P(U) < Q(U)), open U c
(x.)))
which demonstrates the equivalence of the two definitions.
We now prove the attainability the infimum in Definition 7 by repeating the above construction of Ç the first part of our proof. We provide simplified proof as follows.
The above construction of ( before (20 tells us that for an arbitrary a > W (P, Q), there exists a Ç e there exists sequence {Sm} T(P, Q) such that &m (dist(r, y) > ( 0. Since {Gm} [(P, Q). likewise, we obtain that { is tight. By Prohorov's Theorem, there exists weakly convergent subsequence Sm(k) + C*. Similarly, 5" E ((P, Q). By the same token, for arbitrary > O, we have
I(P, Q) such that Ç (dist(z, y) a) = 0. Taking am Wo (P,
5* (dist(x, v) Woo (P,Q) + s lim inf Sm(k)) (dist(x, (P.(P +5) k-400
< lim Smick (dit((z,)) Woo (P,Q) + m(k) k0
0,
where the first inequality by the Portmanteau Theorem. The second inequality holds because there exist ko such that 5 > m(koJ- The third inequality holds due to the construction of Gm-
Since 8 arbitrary, (taking 22
1 and by Fatou's 's Lemma.) we have that
(dist x, y) Woo (P)Q)) 0.
37

---

Published as conference paper ICLR 2024
That is,
5" Sox =
Therefore,
W (P.Q) 2
sup dist(z, y).
(=.))((xxx.")
On the other hand, by the definition of W... since C- ETP, have
Woo (P.Q) s
inf
ess sup
dist( ()
esssup dist(2r, v).
(ET( (exee)
(e.))E(exx.6")
Therefore, Wo (P.Q) = (a.. dist(x, v), E Q), which proves the attainability of the infimum in the definition of W
J FACTS ABOUT NOISY GRADIENT DESCENT
Noisy gradient descent is an alternative algorithm that can be used obtain pure-DP or pure-Gaussian DP under the same assumptions have. While it uses full batch gradients, its analysis relies the theory of stochastic gradient descent since the full gradients in each iteration are perturbed by either the Laplace mechanism or the Gaussian mechanism. We explicitly write out the guarantees of noisy gradient descent in this section so as to substantiate our discussion related to our computational guarantee of localized-ASAP with MALA. We focus the discussion on Gaussian DP in the orn-strongly convex setting.
Theorem 4 (Noisy Gradient Descent for Lipschitz and strongly Convex Losses). Assume the loss function f(O, (x. y)) G-Lipschitz, for any data point (ar, y). Assume (,0 is on-strongly convex on O Consider the following (projected) noisy gradient descent algorithm that initializes at 0g and update the parameter by rounds using
TG2
0: ( 7)
2p² Ia)))
with ni Xt' Let 8% be the minimizer of the regularized ERM problem and 0 to be the minimizer of the unregularized ERM problem.
1. This algorithm that releases the whole trajectory 0,, 0T satisfies satisfies μ-GDP.
2. It also satisfies that
E
C
Σ
2t T(T 1)
01) ]
0:
C(O)) anlI +1)
4n²
dG2 20042²
3. IfT sn2y2, then it achieves an excess empirical risk of onp?
aga
Proof Observe that the G-Lipschitz loss says that the global sensitivity of the gradient is G. The privacy analysis follows from the composition of Gaussian mechanism via Gaussian DP for T rounds (Dong et 2022). This releases the entire sequence of parameters. The weighted average of the parameters over time is post post-processing. The second statement follows from Section 3.2 of (Lacoste- Julien et al.) 2012) by choosing the noise level and other parameters appropriately. The last statement is corollary by choosing T to be large.
In the above, the excess empirical risk achieves the optimal rates but requires the algorithm to run for O(n²) iterations. In the smooth case, one can obtain faster convergence but at the cost of the resulting excess empirical risk.
38

---

Published as conference paper ICLR 2024
Theorem 5 (Noisy Gradient Descent for smooth and strongly convex Losses). Consider the same algorithu and assume all assumptions from Theorem 4 In addition, assume individual loss functions by are B-smooth.
1. This algorithm that releases the whole trajectory 81,..., By satisfies satisfies μ y-GDP.
2. Choose a constant learning rate S
1 ng for T iterations
[ - [(07) - 2 (1 (--)om" (e)m + mB3dTG2
n3
nap
3. Choose 7 1/(33) and T = ( log n.). the excess risk is
E [ C(0)) < O BdG log
na²
Proof From Theorem 5.7 of (Garrigos Gower 2023
derive the convergence in various regimes.
It is not hard to see that there isn't 't a good choice of the learning rate parameter based on the bound above that can get rid the additional Blog factor.
39


Reviews:
[{"review_id": "Zjv2sTMUyp", "reviewer": "Reviewer_kWWS", "summary": "The paper studies the problem of approximate posterior sampling with pure differential privacy guarantee, for which prior works either have only proved weaker notions of DP guarantees (such as approximate DP and R\\'enyi DP) or have only proposed computationally expensive pure DP algorithms. The difficulty in establishing pure differential privacy guarantees lies in the gap between approximate and exact posterior sampling, contributing to a non-zero probability of unbounded information leakage. The authors circumvent this limitation by proving that as long as the posterior sampling process converges in $W_{\\infty}$ distance to a reference distribution that satisfies pure DP, then perturbing the MCMC sample with calibrated noise also satisfies pure DP. For strongly convex smooth loss functions, the author then designed a posterior sampling algorithm that converges in $W_{\\infty}$ distance by combining the Metropolic-Hasting algorithm (that converges in total variation distance) and a rejection step that only accepts samples within a bounded ball (this boundedness enables conversion from total variation distance bound to $W_{\\infty}$ distance bound). Finally, the authors showcased an application of their DP posterior sampling algorithm for the DP empirical risk minimization problem, which achieves the optimal rates in near-linear runtime.", "questions": "1. In the proof for Theorem 3 (improved utility bound for DP-ERM), equations (5) and (6) utilize Lemma 6 to analyze the **approximate** posterior sampling component MALA with constraint. However, Lemma 6 only holds under **exact** posterior sampling from $p(\\theta)\\propto \\exp(-\\gamma F(\\theta))$. Could the authors explain this discrepancy and justify this usage of Lemma 6?\n\n2. In proof of Theorem 1, when proving iteration complexity guarantee for convergence of MALA in total variation distance, the authors cited [Dwivedi et al. 2019] and [Ma et al. 2019]. Could the authors cite the specific theorems? Otherwise, it is hard to validate these claims.\n\n3. Could the authors elaborate on the possibility of extending the privacy bound to more general settings, such as general bounded domain (e.g., probability simplex) or more relaxed convex/non-convex/non-smooth loss functions?\n\nMinor comments:\n- The idea of perturbing distributions with bounded $W_{\\infty}$ distance with noise to strengthen the differential privacy guarantee seems quite similar to the shift reduction lemma in the \"privacy amplification by iteration\" analysis [Lemma 20, a]. The main difference seems to be that [Lemma 20, a] focuses on Rényi DP guarantees while the authors focus on pure DP and Gaussian DP guarantees. Maybe the authors could add more discussion regarding the non-trivialness of this extension.\n\nReference:\n- [a] Feldman, Vitaly, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. \"Privacy Amplification by Iteration.\" arXiv preprint arXiv:1808.06651 (2018).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of perturbing an MCMC sampling process (that only satisfies weaker notions of DP guarantees) with noise to achieve the stronger pure-DP guarantee is interesting and novel. To make this idea concrete, the paper has used an interesting new technique that converts the weaker  TV distance bound to a $W_{\\infty}$ distance bound under the conditions that the domain is a bounded ball and the posterior density is bounded away from zero.\n\n- The proposed algorithm achieves a near-optimal rate within near-linear runtime under pure DP for the DP ERM problem, under strongly convex smooth loss function on $\\ell_2$-bounded ball). The proved rate improves with a multiplicative factor $\\kappa\\log n$ where $\\kappa$ is the condition number, and $n$ is the number of data records.", "weaknesses": "- The improvement for DP ERM due to the designed approximate posterior sampling algorithm (and several parts of the proofs) requires further clarification. See questions 1 and 2 for more details.\n\n- The setting is quite constrained, i.e., strongly convex and smooth loss functions over $\\ell_2$-bounded ball. It is unclear whether the privacy analysis, especially the critical conversion theorem (from total variation distance bound to $W_{\\infty}$ distance bound), is generalizable to more general forms of bounded domain or loss functions.", "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": "", "extra_scores": {}}, {"review_id": "lpD4vbbi7t", "reviewer": "Reviewer_kgTq", "summary": "The authors propose a novel MCMC algorithm for pure DP and Gaussian DP empirical risk minimization. The new MCMC sampling scheme does not introduce extra privacy failure probablity and thus preserves pure DP. Moreover, the algorithm runs nearly linearly in the dataset size.", "questions": "1. See weakness 1.\n2. If in Algorithm 1, we are only allowed to perform the sampling N times, and thus must return a FAIL state if none of the $\\theta^K$s are valid, would the algorithm still be pure-DP or pure Gaussian DP?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. DP-ERM is a very fundamental task. The paper addresses very practical and important issues in differentially private optimization. \n2. The paper proposes a new algorithm for DP-ERM. The major benefit is that it avoids catastrophic privacy failures and thus guarantees pure DP, and runs linearly with the dataset size $n$. \n3. The paper has interesting technical contributions, for example, a new MCMC algorithm, the relation between TV distance and  Wasserstein-infinity distance.", "weaknesses": "1. $\\theta^*$ seems to be defined as the minimizer for the regularized loss in Section 2.1, but in Assumption 3 $\\theta^*$ is used again for the minimizer of the original loss. The authors should clarify what is the $\\theta^*$ in Theorem 3. This is a crucial problem as in existing DP-ERM literature (e.g. Bassily'14) we should care about the excess risk w.r.t. $\\min_{\\theta}\\mathcal{L}(\\theta)$, not the regularized loss. If $\\theta^*$ is the minimizer of the regularized loss, then the authors should clarify why it is used instead of the commonly adopted formulation of excess risk.\n2. In view of 1 the notation causes confusion in understanding the main theoretical results. There are other notation issues: $J$ was first defined as $\\sum_{i}\\ell_i$ which collides with $\\mathcal{L:}$, and then redefined in Algorithm 3 as the regularized loss centered at $\\theta_0$. The authors should check other notation issues.\n3. The algorithm requires rejection sampling which in the worst case may not terminate.\n4. A minor issue is that the work lacks empirical evaluations. Even a small experiment on even the simplest convex optimization problem can provide very strong support for the computation efficiency of this work and demonstrate the practicality of the proposed algorithm.\n\n====Update====\nRaised my score to 6 after the authors have addressed my concerns.", "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": "", "extra_scores": {}}, {"review_id": "Kn9lAz7Ssr", "reviewer": "Reviewer_qRJd", "summary": "The paper proposes an algorithm for pure DP or GDP DP-ERM that achieves nearly linear time complexity with an optimal error rate under regularity assumptions on the loss. The algorithm uses the exponential mechanism with MCMC sampling, and uses a novel analysis to show that the approximate sample from the MCMC can still meet pure DP or GDP with some additional privacy loss.", "questions": "- Would it be possible to use ASAP outside ERM, with a generic utility function $F(\\theta)$ for the exponential mechanism? What conditions would $F$ need to meet?\n- When discussing related work, you mentioned that an existing algorithm could solve DP-SCO in nearly linear time, but adapting their algorithm to DP-ERM would not result in a linear time. What are the differences between DP-ERM and DP-SCO, and how do they lead to this difference?\n- Isn't Lemma 5 effectively assuming that the loss is bounded, as Lipschitzness of the loss implies continuity, and $\\Theta$ must be bounded due to the upper bound on $\\gamma$?\n- In the proof of Theorem 1, shouldn't the expressions for $K$ have $\\Omega$, not $\\mathcal{O}$, so they would be lower bounds instead of upper bounds?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is fairly easy to understand, despite having lot's of theory. The MCMC technique of obtaining a pure DP or GDP guarantee from an approximate exponential mechanism is novel to my knowledge, and could find applications elsewhere, although implementing the mechanism in practice doesn't currently seem possible. While the performance guarantee of the proposed DP-ERM algorithm is purely theoretical, it advances the current knowledge on what is possible under DP.", "weaknesses": "The biggest weakness of the paper is the purely theoretical nature of the method in its current form. Implementing it would be difficult, as the required number of MALA iterations is only given as an asymptotic expression, so it would not be possible to know the required number of iterations for any given problem. If possible, it would be great to have a non-asymptotic expression for the number of iterations in the Appendix, or some other way to compute it.\n\nMinor comments:\n- Lemma 14 should be mentioned in the proof of Theorem 2 when referring to the adaptive composition theorems. In the proof, I think it is possible that for some $y$, the sensitivity of $f_{u,y}$ is greater than the bound with more than probability 0 under $\\zeta(\\cdot | y) \\times \\zeta(\\cdot | y)$, but this set of $y$ would have 0 measure under $\\zeta$ or $\\zeta'$. I think the proof still works due to Lemma 14 allowing the second mechanism to be almost surely DP, but this should be explicitly mentioned.\n- In footnote 1, both sides of the DP inequality have $D'$.\n- In the $P(A)$ expression in the GDP part of the proof of Lemma 14, line 3 is a repeat of line 2. In the expression of $H_\\alpha(\\mathcal{M}(D) || \\mathcal{M}(D'))$, there's an extra $\\frac{d P_1}{d Q_1}(x)$ in the first indicator on line 7. When that expression continues on the next page, the Gaussian Radon-Nikodym derivatives involving $\\mu_2$ at the end of the integral are the wrong way around on lines 2-5.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)