Adapting to function difficulty and growth conditions in private optimization
Authors: Hilal Asi
Daniel Asher Nathan Levy
John Duchi
Venue: NeurIPS 2021 Poster (2021)
Keywords: privacy
differential privacy
adaptivity
optimization
convex
learning
sco
lower bounds
minimax
growth

Abstract: We develop algorithms for private stochastic convex optimization that adapt to the hardness of the specific function we wish to optimize. While previous work provide worst-case bounds for arbitrary convex functions, it is often the case that the function at hand belongs to a smaller class that enjoys faster rates. Concretely, we show that for functions exhibiting $\kappa$-growth around the optimum, i.e., $f(x) \ge f(x^\star) + \lambda \kappa^{-1} \|x-x^\star\|_2^\kappa$ for $\kappa > 1$, our algorithms improve upon the standard ${\sqrt{d}}/{n\varepsilon}$ privacy rate to the faster $({\sqrt{d}}/{n\varepsilon})^{\tfrac{\kappa}{\kappa - 1}}$. Crucially, they achieve these rates without knowledge of the growth constant $\kappa$ of the function. Our algorithms build upon the inverse sensitivity mechanism, which adapts to instance difficulty [2], and recent localization techniques in private optimization [25]. We complement our algorithms with matching lower bounds for these function classes and demonstrate that our adaptive algorithm is simultaneously (minimax) optimal over all $\kappa \ge 1+c$ whenever $c = \Theta(1)$.

Adapting to Function Difficulty and Growth Conditions in Private Optimization
Hilal Asi" Daniel Levy" John C. Duchi
fasi danilevy, , jduchi @stanford woffoordeed. edu
Abstract
We develop algorithms for private stochastic convex optimization that adapt to the hardness the specific function we wish to optimize. While previous work pro- vide worst-case bounds for arbitrary convex functions, it is often the case that the function at hand belongs to a smaller class that enjoys faster rates. Con- cretely, we show that for functions exhibiting k-growth around the optimum, i.e., f(x) 2 f(x") + -|x x² || for K. > 1, our algorithms improve upon the standard vd/ng privacy rate to the faster (Vd/ne) /ー-, Crucially, they achieve these rates without knowledge of the growth constant к of the function. Our al- gorithms build upon the inverse sensitivity mechanism, which adapts to instance difficulty [2], and recent localization techniques in private optimization [25]. We complement our algorithms with matching lower bounds for these function classes and demonstrate that our adaptive algorithm simultaneously (minimax) optimal over all 2 + whenever = ((1).
1 Introduction
Stochastic convex optimization (SCO) is a central problem in machine learning and statistics, where for sample space S. parameter space X' C Rd, and collection of convex losses {F(Gs): E S), one wishes to solve
minimize f(x) = [EE= [ F(x
(I)
using an observed dataset S ST ldd P. While as formulated, the problem is by now fairly well-understood [12, 38, 29, 10, 37], is becoming clear that, because of considerations beyond pure statistical accuracy accuracy-memooe memory or communication costs [45, 26, 13], fairness [23, 28), personal- ization distributed learning [35]-problem (1) is simply insufficient to address modern learning problems. To that end, researchers have revisited SCO under the additional constraint that the solu- tion preserves the privacy of the provided sample [22, 21, 1, 16, 19]. A waypoint is Bassily et al. [7], who provide a private method with optimal convergence rates for the related empirical risk min- imization problem, with recent papers focus SCO providing (worst-case) optimal rates in various settings: smooth convex functions [8, 25], non-smooth functions [9], non- Con-Euclidean geometry [5, 4] and under more stringent privacy constraints [34].
Yet these works ground their analyses worst-case scenarios and provide guarantees for the hardest instance of the class of problems they consider. Conversely, they argue that their algorithms op- timal in a minimax sense: for any algorithm, there exists a hard instance on which the error achieved by the algorithm is equal to the upper bound. While valuable, these results are pessimistic- the exhibited hard instances are typically pathological- and fail to reflect achievable performance.
Equua contribution. Author order determined by coin toss.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work, we consider the problem of adaptivity when solving (I) under privacy constraints. Importantly, we wish to provide private algorithms that adapt to the hardness of the objective f. A loss function/ f' may belong to multiple problem classes, each exhibiting different achievable rates, so a natural desideratum is to attain the error rate of the easiest sub-class. As a simple vignette, if one gets an arbitrary 1-Lipschitz convex loss function f. the worst-case guarantee of any e-DP algorithm is ( /n + (ne)). However, if one learns that f exhibits some growth property-say f is 1-strongly convex- the regret guarantee improves to the faster @11/n + (d/ (dd(ns)))) rate with the appropriate algorithm. It is thus important to provide algorithms that achieves the rates of the "easiest" class to which the function belongs [32, 46, 18).
To that end, consider the nested classes of functions F for K E oo] such that, if f FF then there exists À >> O such that for all x E X,
f(x) inf ((0) or E'
x x011..
K
For example, strong convexity implies growth with parameter K = 2. This growth assumption closely relates to uniform convexity [32] and the Polyak-Kurdyka -ojaseae- inequality [11]. and we make these connections precise in Section 2. Intuitively, smaller k makes the function much easier to optimize: the error around the optimal point grows quickly. Objectives with growth are widespread in machine learning applications: among others, the f--regularized hinge loss exhibits sharp growth (i.e. x = 1) while f or fox -constraiid k-norm regression -.e. s = (a, b) E TRd TR and F(x; s) = |6 (a, lhas- k-growth for any integer greater than 2 [43]. In this work, we provide private adaptive algorithms that adapt to the actual growth of the function at hand.
We begin our analysis by examining Asi and Duchi's inverse sensitivity mechanism [2] on ERM as a motivation. While not practical algorithm, it achieves oostance-optimal rates for any one- dimensional function under mild assumptions, quantifying the best bound one could hope to achieve with an adaptive algorithm, and showing (in principle) that adaptive private algorithms can exist. We first show that for any function with k-growth, the inverse sensitivity mechanism achieves privacy cost (d/ (d/(ns))</(<<1)) importantly, without knowledge of the function class F that f belongs to. This constitutes grounding and motivation for our work in three ways: (i) it validates our choice of sub-classes Fx as the privacy rate is effectively controlled by the value of k, (ii) it exhibits the rate we wish achieve with efficient algorithms on F and (iii) showcases that for easier functions, privacy costs shrink significantly- to illustrate, for λ 5/4 the privacy rate becomes (d/(.)))²
We continue our treatment of problem (1) under growth in Section 4 and develop practical algo- rithms that achieve the rates of the inverse sensitivity mechanism. Moreover, for approximate (c, 5)- differential privacy. our algorithms improve the rates, achieving roughly (Vd/(ne))*/te algorithms hinge on a reduction to SCO: we show that by solving a sequence of increasingly con- strained SCO problems, one achieves the right rate whenever the function exhibits growth at the optimum. Importantly, our algorithm only requires a lower bound k. I (where the actual growth of f).
Our
We provide optimality guarantees for our algorithms in Section 5 and show that both the inverse sen- sitivity and the efficient algorithms of Section 4 are simultaneously minimax optimal over all classes F whenever ε 1 + (1) and d 1 for e-DP algorithms. Finally, we prove that in arbitrary dimension, for both pure- and approximate-DP constraints, our algorithms are also simultancously optimal for all classes Fr with K 2 2.
On the way. we provide results that may be of independent interest to the community. First, we develop optimal algorithms for SCO under pure differential privacy constraints, which, to the best of our knowledge, do not exist in the literature. Secondly, our algorithms and analysis provide gigh-probability bounds on the loss, whereas existing results only provide (weaker) bounds on the expected loss. Finally, we complete the results of Ramdas and Singh [40] on (non-private) optimiza- tion lower bounds for functions with k-growth by providing information-theoree contrast to oracle-based lower bounds that rely on observing only gradient information) and captur- ing the optimal dependence on all problem parameters (namely d, L and A).
lower bounds (in
1.1 Related work
Convex optimization is one of the best studied problems in private data analysis [16, 19, 7]. The first papers in this line of work mainly study minimizing the empirical loss, and readily establish that

---

the (minimax) optimal privacy rates are d/ne for pure E-DP and lo /n/ for (E, 6)-D [16, 7]. More recently, several works instead consider the harder problem of privately minimizing the population loss [8. 25J. These papers introduce new algorithmic techniques to obtain the worst-case optimal rates of 1//nn + (1/0)//) for (c, 6)-DP. They also show how to improve this rate to the faster 1/n d'log(1/b) (0og((16))) (ne)² in the case of 1-strongly convex functions. Our work subsumes both of these results as they correspond to y oo and λ respectively. To the best of our knowledge, there has been no work in private optimization that investigates the rates under general k-growth assumptions or adaptivity to such conditions.
In contrast, the optimization community has extensively studied growth assumptions [40, 32, 15] and show that on these problems, carefully crafted algorithms improves upon the standard 1/ Vn for convex functions to the faster (1/ (T/z))/((-1), [32] derives worst-case optimal (in the first-order oracle model) gradient algorithms in the uniformly convex case (i.e. k 2 2) and provides technique adapt the growth K, while [40], drawing connections between growth conditions and active learning. provides upper and lower bounds in the first-order stochastic oracle model. We complete the results of the latter and provide information-then theoreetc lower bounds that have optimal dependence on À and n-thhir lower bound only holding for inversely proportional to d2/2-1//x, when K 2 2. Closest to our work is [15] who studies instance-optimality via local minimax complexity [14]. For ome-dimensional functions, they develop bisection-basee instance-optimal algorithm and show that on individual functions of the form f r [M|", the local minimax rate is (1 (//n))/(m>))
2 Preliminaries
We first provide notation that we use throughout this paper, define useful assumptions and present key definitions in convex analysis and differential privacy.
Notation. n typically denotes the sample size and d the dimension. Throughout this work, x refers the optimization variable, X' I to the constraint set and elements (S when random) of the sample space S. We usually denote by F: X x S + I the (convex) loss function and for a dataset (81,-.., 8a) C S, define the empirical and population losses
fs(x) = - Σ 8(); and f(x) = =E==P(F(x;)) isn
We omit the dependence P as it is often clear from context. We reserve 5 2 O for the privacy parameters of Definition 2.1. We always take gradients with respect to the optimization variable x. In the case that F(;ss) is not differentiable at we override notation and define (x; = argmingeoF(sss) l|gl|a. where OF s) is the subdifferential of F(-:s) at x. We use for (potentially random) mechanism and ST as a shorthand for (SI,..., S,).. For p 2 1, lp is the standard Ep norm,, (R) is the corresponding d-dimensional p-ball of radius R and p* is the dual of p, iee such that 1/p" + 1/p = 1. Finally, we define the Hamming distance between datasets dHam (S, = infoee, 1/s, + (o()) where 6,, is the set of permutations over sets of size
Assumptions. We first state standard assumptions for solving (1). We assume that X' is closed, convex domain such that diamz(X') = sup,,ex || - y1/2 S D < co. Furthermore, we assume that for any 8 E S, s(:ss) is convex and L-Lipschitz with respect to || I|2- Central to our work, we define the following k-growth assumption.
Assumption 1 (k-growth). Let x² argmin fzx). For loss F and distribution P, we say that (F, P) has (X, k) growth for is [o] and X > O, if the population function satisfies
for all EX, f(x) f(x*(((=)))))))))))
-
In the case where P is the empirical distribution on finite dataset S, we refer to (A, A.-wwhh of (F, P) k-growth of the empirical function fs-
Uniform convexity and fundamental notions in convex analysis: uniform convexity and the Saitykka---jssiiiizzze incquality.
inequality. Assumption closely related to two
3

---

Following [39], we say that h 2C
C.R. 12 7 R is (a, x) unifforlyy convex with > 0 and K 2 2 if
for all 2,yE 2, h(y) 2 h(z) Vh(()) x)
a vl12
This immediately implies that (i) sums (and expectations) preserve uniform convexity (ii) if uniformly convex with À and K, then it has (A, k)-goohhh. This will be useful when constructing hard instances as will suffice to consider (A, -u-uffrryyyy convex functions which are generally more convenient to manipulate. Finally, we point out that, in the general case that K 2 1, the the
literature refers to Assumption
inequality [11] with, in their notation, (p(s) (x/ (t/A)1/xg//r Theorem 5-(ii) in [11] says that, under mild conditions, Assumption implies the following inequality between the error and the gradient norm for all x E X
f(x)
inf f(x) Z'EX
[V
A--1
This is key result in our analysis of the inverse sensitivity mechanism of Section 3.
Differential privacy. We begin by recalling the definition of (s, 8) differeetia privacy.
Definition 2.1 ([22, 21J). A randomized algorithm (e, -differrrry private ((s, 6)-DP) if, for all datasets S,S' E Sh that differ in single data element and for all events O in the output space of A, we have
Pr (A(((S) E 0) c Pr(SS) E0)+ +
We use the following standard results in differential privacy.
Lemma 2.1 (Composition [20, Thm. 3.16)). If ........ A randomized algorithms that each is (s, 8D- then their composition (Ai(S), A (S)) is (ke, k
Next, we consider Laplace mechanism. We will let Lapa(o) denote d-dimennsionl vector Z E IRd such that Z iid Lap(o) for
d.
Lemma 2.2 (Laplace mechanism [20, Thm. 3.6]). Let h S" - Rd have fı-sensitivity A, that is, sups,s'es" (S, [[(S)) (SS)))l= A. Then the Laplace mechanism A(S) h(S) + Lapa(o) with A/E D-DP.
Finally, we need the Gaussian mechanism for (s, (e,8)-DP.
RR have fz-sensitivity A, that is, sups, (ateadasssSSS. ($ [[h(8) h(S'))l2 ll S A. Then the Gaussian mechanism A(S) h(S) +
Lemma 2.3 (Gaussian mechanism [20. Thm. A.1]). Let h -
N(O, o² Ia)) with a = 2A log(2/5)) is (c. 6)-D.
Inverse sensitivity mechanism. Our goal is to design private optimization algorithms that adapt to the difficulty of the underlying function. As a reference point, we turn to the inverse sensitivity mechanism of [2] as it enjoys general instance-optimality guarantees. For given function h S"
Rdd that we wish to estimate privately, define the inverse sensitivity at o T
(S; x) inf (S : ;S))h(S') = x}.
(3)
that is, the inverse sensitivity of target parameter T at instance S is the minimal number of samples one needs change to reach new instance S' such that h(S') y. Having this quantity, the inverse sensitivity mechanism samples an output from the following probability density
Amny (S) (x)
(S:x)
(4)
The inverse sensitivity mechanism preserves e-DP and enjoys instance-optimality guarantees gen- eral settings [2]. In contrast to (worst-case) minimax optimality guarantees which measure the performance of the algorithm on the hardest instance, these notions of instance-optimality provide stronger per-instance optimality guarantees.

---

3 Adaptive rates through inverse sensitivity for s-DP
To understand the achievable rates when privately optimizing functions with growth, we begin our theoretical investigation by examining the inverse sensitivity mechanism in our setting. We show that, for instances that exhibit y- x-growth of the empirical function, the inverse sensitivity mechanism privately solves ERM with excess loss roughly (d/ne) -
In our setting, we use a gradient- based approximation of the inverse sensitivity mechanism to sim- plify the analysis, while attaining similar rates. Following [3] with our function of interest h(S) = argmin,ex* fs(x), we can lower bound the inverse sensitivity len, (S;z) 2 [s)V](( 2 2T, un- der natural assumptions. We define p-smoothed version of this quantity which is more suitable to continuous domains
(z)()) wEx:llo-mlasp
inf
[s)
and define the p-smooth gradient- based inverse sensitivity mechanism
A inv (5) (5) (x) x e (0nC
(5)
Note that while exactly sampling from the un un-normalized density TA inv (S) is computationally in- tractable, analyzing its performance is an important step towards understanding the optimal rates for the family of functions with growth that we study in this work. The following theorem demonstrates the adaptivity of the inverse sensitivity mechanism to the growth of the underlying instance. We defer the proof to Appendix A.
Theorem 1. Let S- = (81,...,, .p)) E S" F(r;;) 8) be convex, T-LLipschizz for all E & Let xx argmin fs(x) and assume x² is in the interior of X. Assume that fs(æ) has k-growth (Assumption 1) with K. 2 K > 1. For p > 0, the p-smooth inverse sensitivity mechanism Agr-in (5)
e-DP, and with probubility least 8 the output Agrinn (S) has
1 (L(log(1/3) dlog (D/1)) (log(D/))) = + Lp.
fs(é) - min fs(x) s
#EX
x=
ne
Moreover, setting p (L/A)= - (d/ (d/nz)
we have
Ld
fs( - min fs( xEX
A
nE
The rates of the inverse sensitivity in Theorem 1 provide main insights regarding the landscape of the problem with growth conditions. First, these conditions allow to improve the worst-case rate d/ns to (d/ns)== for pure e-DP and therefore suggest a better rate ( log()o)))///// /f/)===)= is possible for approximate (e, 6D. Moreover, the general instance-optimality guarantees of this mechanism [2] hint that these are the optimal rates for our class of functions. In the sections to come, we validate the correctness of these predictions by developing efficient algorithms that achieve these rates (for pure and approximate privacy), and prove matching lower bounds which demonstrate the optimality of these algorithms.
4 Efficient algorithms with optimal rates
While the previous section demonstrates that there exists algorithms that improve the rates for func- tions with growth, we pointed out that Agr-inv was computationally intractable in the general case. In this section, we develop efficient algorithms-c.g. that implementable with gradient-based methods-that achieve the same convergence rates. Our algorithms build on the recent localization techniques that Feldman et al. [25] used to obtain optimal rates for DP-SCO with general convex functions. In Section 4.1, we use these techniques to develop private algorithms that achieve the optimal rates for (pure) SCO with high probability, in contrast to existing results which bound the expected excess loss. These results are of independent interest.
In Section 4.2, we translate these results into convergence guarantees privately optimizing convex functions with growth by solving a sequence of increasingly constrained SCO problems-the high- probability guarantees of Section 4.1 being crucial to convergence analysis of these algorithms.
5

---

4.1 High-probability guarantees for convex DP-SCO
We first describe our algorithm (Algorithm 1) then analyze its performance under pure-DP (Propo- sition 1) and approximate-De constraints (Proposition 2). Our analysis builds on novel tight gen- cralization bounds for uniformly-stable algorithms with high probability [24]. We defer the proofs to Appendix B.
Algorithm Localization-basel Algorithm
Require: Dataset S = (8)) E 8", constraint set X, step size 1/, initial point To. privacy parameters (s, 0);
1: Set & = [log n and no = n/k
2: for 1 to k do
3: Set = 2 2-1
4: Solve the following ERM over X; = far N: ||x ri-1/12 2 S 2Immoo::
8rig
1
Fx(2)
8;); +
|1 23-1112
nu
17:00
5=1+(i- 1)mo
5:
Let i; be the output of the optimization algorithm
6:
if 8 then
7:
Set Çi ~ (o:) where
ALn/d//E
8:
else if
then
9:
Set ~ N(O, o?? where o; = 4L1; /og(
Set 2; c + G
11: return the final iterate T&k
Proposition 1. Lei 3 S 1/(n + d), diamz(A) < D and F(x;,) be convex, L-Lipschitz for all E S. Setling
D == min (Vrlog(1/B) dlog(1/3)
then for 8 = 0, Algorithm 1 e-P and has with probability
3/2 ((x)-f(x')) < LD (log(1/3) log
d (og(3133) log
vn
nE
Similarly, by using a different choice for the parameters and noise distribution, we have the following guarantees for approximate (e, DD-
Proposition 2. Let B < 1/(n + d). diamz(X)) S D and F(x;s) 3) be convex, L-Lipschitz for all 8 E S. Setting
D min Vnlog(1/3) /dlo log(1/))
=
then for 8 > 0, Algorithm (c, 5)- and has with probability
f(x)-f(z*) LD.O (olg(11/8)oog" n Vn + (dlog(1/6) (10))//()111///11 logn
Before presenting our algorithms for functions with growth, we remark that the exact calculation not necessary; we chose to clarify the main
of the ERM solution in step 5 of Algorithm algorithmic ideas. However, as long the returned solution à; is sufficiently accurate, say F:(f;)- ming3ex Fx A, we have that || x ll2 s /2A/A, where A, 1/(n.no). This implies that as long as < L, the sensitivity of à; is at most twice the sensitivity of the exact ERM solution at and hence multiplying the noise by factor of is sufficient to guarantee privacy. As the set X; is convex, finding sufficiently accurate à; can done efficiently using standard optimization methods for minimizing convex functions over convex domains.

---

4.2 Algorithms for DP-SCO with growth
Building on the algorithms of the previous section, we design algorithms that recover the rates of the inverse sensitivity mechanism for functions with growth, importantly without knowledge of the value of Inspired by epoch-based algorithms from the optimization literature [31, 29], our algorithm iteratively applies the private procedures from the previous section. Crucially, the growth assumption allows to reduce the diameter of the domain after each run, hence improving the overall excess loss by carefully choosing the sypee-paraamttrs. We provide full details in Algorithm 2.
Algorithm Epoch-based algorithms for k-growth
Require: Dataset S (S1,..., 8n) E S", convex set X, initial point 2o, number of iterations T, privacy parameters (s, 0);
1: Set no n//T and Do di)m2(X)
2: 6 = then
3: Set
Do min 2L
no log(no) log(1/8)) (1/(8
4: else if 5 > then
Do min
5:
7o = 2L
v Vno (og( log(1/8) (dlog(1/6) log(1/3)
6:
for = 0 to T
do
7:
Let S, = ($1+ 10 Sino)
8:
Set D. 2 Do and = 2m0
9:
Set X; {I E
I zz 22 D2}
10:
Run Algorithm on dataset S; with starting point z;, privacy parameter (e, 6), domain X;
(with diameter D,), step size 7/s
11: Let 1i+1 be the output of the private procedure
return 2T
The following theorem summarizes our main upper bound for DP-SCO with growth in the pure privacy model, recovering the rates of the inverse sensitivity mechanism in Section We defer the proof to Appendix B.3.
Theorem 2. Let B S 1/(n d), diama(X) S D and F(z;s) be convex, L-Lipschitz for all s E S. Assume that f has k- k-growth (Assumption 1) with 2 K >> 1. Setting = e-DP and has with probability 1 8
2lo x-1
Algorithm is
T. T.Vlgg(1/3)
Ld log(1/3) nE(K 1)
f(xT) min f(x xEX
Vn
where Ô hides logarithmic factors depending on n and d.
Sketch of the proof. The main challenge of the proof is showing that the iterate achieves good risk without knowledge of k. Let us denote by D.p the eиror guarantee of Proposition (or Proposition for approximate- DP). At each stage as long as xº argmin f(z) belongs to X,, the excess loss is of order D and thus decreases exponentially fast with i. The challenge is that, without knowledge of we do not know the index in (roughly logg?" after which x & D3 for 2 in and the regret guarantees become meaningless with respect to the original problem. However, in the stages after in, as the constraint set becomes very small, we upper bound the variations function values f(1j+1) f(x;) and show that the sub-optimality cannot increase (overall) by more than O(Di, p). thus achieving the optimal rate of stage io.
Moreover, we can improve the dependence on the dimension for approximate (e, 8)-D, resulting in the following bounds.
Theorem 3. Let B < 1/(n + d), diam2(X) S D and F(x; , 8) be convex, L-Lipschitz for all & E S. Assume that f has k-growth (Assumption 1) with k. 2 K >> 1. Setting T = 2log and 8 0,

---

Algorithm 2 is (E, DD and has with probability 1 1-3
LV (og(3))
LV dloogl//// (0/(1/3)
f(x1) - -uin)miiin f(x) S
ZEA
A=-1
ns (K - 1)
where Ô hides logarithmic factors depending and d.
5 Lower bounds
In this section, we develop (minimax) lower bounds for the problem of SCO with k-growth under privacy constraints. Note that taking : + oo provides lower bound for the unconstrained mini- max risk. For a sample space S and collection of distributions P over S, we define the function class (P) as the of convex functions from Rd I that are L-Lipschitz and has w-growth (Assumption 1). We define the constrained minimax risk [6]
E ((a)(S))) inf f(07)) E.Ai FP
2R ( 0) = inf sup
(6)
r'E
where A 6 is the collection of 8)-D mechanisms from S" to X. When clear from context, we omit the dependency on when referring to pure-DP constraints, i.e. 2r, (X, P. e, 5 = 0) =: 2,, (X, P. _ Fxx,8 .). We
P of the function class and simply write Jx We also forego the dependence
now proceed to prove tight lower bounds for e-DP in Section 5.1 and (e, 6DD in Section 5.2.
5.1 Lower bounds for pure E-DP
Although in Section we show that the same algorithm achieves the optimal upper bounds for all values of к > 1, the landscape of the problem is more subtle for the lower bounds and need to delineate two different cases to obtain tight lower bounds. We begin with к 2 2, which corresponds to uniform convexity and enjoys properties that make the problem easier (e.g., closure under summation or addition of linear terms). The second case, 1 < K < 2, corresponds to sharper growth and requires different hard instance to satisfy the growth condition.
R-growth with k 2 2. We begin by developing lower bounds under pure DP for K 2
Theorem (Lower bound for e-DP, 2). Let d 2 1, X (R). f 2 and E N. Let P be the set of distributions S. Assume that
2--1 L
À R S 2"-1 2 V96 and ne 2 v3
The following lower bound holds
(x-1)
Ld
(X
nE
First of all, note that L 2 A2 R is not overly-restrictive assumption. Indeed, for an arbitrary (X, un)uufformlly convex and T.-Lipschitz function, it always holds that T, 2 3 R This is thus equivalent assuming (1). Note that when x 1, the standard -122 + +d/ (ne)) lower bound holds. We present the proof in Appendix C.1.1 and preview the main ideas here.
1/2
Sketch of the proof. Our lower bounds hinges on the collections of functions F(x; s)
ax- ||=|| 1 + b(zz s) for a, b 2 0 to be chosen later. These functions are [39, Lemma 4] k-uniformly and in turn, so is the population function f. We proceed as follows, we first
convex for any prove an information-theoree provides the statistical term in (7). With the same family of functions, we exhibit a collection of datasets and prove by contradiction that if an estimator were to optimize below certain error it would have violated e-Dp-this yields lower bound on ERM for our function class (Theorem in Appendix C.I.I). We conclude by proving reduction from SCO to ERM in Proposition 4. D
(non-private, lower bound (Theorem 8 in Appendix C.1.1) which

---

k-growth with (1. As the construction of the hard instance is more intricate for K < 2, we provide oinedimensional lower bound and leave the high-dimg sighdimensiionl case for future work. this case we directly obtain the result with a private version of Le Cam's method [44, 42, 6]. however with a different family of functions.
The issue with the construction of the previous section is that the function does not exhibit sharp growth for < Indeed, the added linear function shifts the minimum away from where the function is differentiable and as a result it locally behaves as a quadratic and only achieves growth
2. To establish the lower bound, we consider a different sample function F that has growth exactly 1 on one side and K on the other side. This yields the following
Theorem 5 (Lower bound for E-DP, R E (1, ). Let d = 1, S = {-1,+1}, K E (1, À 1, = 2, and n E N. There exists a collection of distributions P such that, whenever ne 2 1/v3, holds that
Dr [1,((1,,1,,,,P%2 Ω
(8)
NE
5.2 Lower bounds under approximate privacy constraints
We conclude our treatment by providing lower bounds but now under approximate privacy con- straints, demonstrating the optimality of the risk bound of Theorem 3. We prove the result via a reduction: we show that if one solves ERM with k-growth with error A, this implies that one solves arbitrary convex ERM with error o( A). Given that a lower bound of ((Vd/(ne)) holds for ERM, lower bound of (vVa((())) holds for ERM with R-growth. However, for this reduction to hold, we require that x 2 2. Furthermore, we consider to be roughly a constant-in the case that k is large, standard lower bounds on general convex functions apply.
Theorem 6 (Private lower bound for (s, 6)-D). Let 2 2 such that k = ((1), ((1),==BBB) (D) Let d > 1 and S {+1/vdj) Assume that ne D0 d), then for any (E,8) mechanism A, there exists > 0, F and S C S such that
Lvd
B[fs(A(S))
- inf fs(a') x'X
2
Ax-1
Theorem 6 implies that the same lower bound (up logarithmic factors) applies SCO via the reduction of [8, Appendix CJ. Before proving the theorem, let us state (and prove in Appendix C.2) the following reduction: if an (e, 5) algorithm achieves excess error (roughly) A on ERM for any function with x-growth, there exists an (e, 6)P algorithm that achieves error A (x-1)/x for any convex function. We construct the latter by iteratively solving ERM problems with geometrically I |lg-regularization towards the previous iterate to ensure the objective has k-growth.
increasing
Proposition 3 (Solving ERM with k-growth implies solving any convex ERM). Let K 2 2. Assume there exists an (c. 5) mechanism A such that for any L-Lipschitz loss G on y and dataset such that 95(x) Eees G(x; s) exhibits (x, kro-grwth, the mechanism achieves excess loss
1 A(n, L,C,
Elgs(A(S, (,I,,,,D))) y/ y'ey
inf (5()) <
A--I
Then, we can construct an 8)DP mechanism Al such that for any L- L-Lipschitz loss f. the mech- anism achieves excess loss
E[fs(A'(S))
fs(x') S o x'E
inf
L, L./k,, R-1
where & is the smollest integer such that k: log
タパー TiK L,E/k,0/k)
With this proposition, the proof of the theorem directly follows Bassily et al. [7] prove lower bound ②(v ((Vd/(ne)) for ERM with (e, 8D-

---

Discussion
In this work, develop private algorithms that adapt to the growth of the function at hand, achiev- ing the convergence rate corresponding to the "casiest" sub-class the function belongs to. However, the picture not yet complete. First of, there are still gaps in our theoretical understanding. the most interesting one being linear convergence [43] and raise the question, can we achieve exponentially small privacy cost in our setting? Finally, while our optimality guarantees are more fine-grained than the usual minimax results over convex functions, they are still contigent on some predetermined choice of sub-classes. Studying more general notions of adaptivity is an important future direction in private optimization.
1. On these functions, appropriate optimization algorithms achieve
Acknowledgments
The authors would like thank Karan Chadha and Gary Cheng for comments on an early version of the draft. HA, DL and JCD were supported NSF under CAREER Award CCF-1553086 and HDR 1934578 (Stanford Data Science Collaboratory), Office of Naval Research YIP Award N00014-19- 2288 and the Stanford DAWN Consortium.
Competing Interests
JCD has consulting relationship with Apple. HS has spent internships at Apple during the 2019, 2020 and 2021 summers. DL has spent an internship at Google during the summer of 2020.
References
[1] M. Abadi, A. Chu, I. Goodfellow, B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In 23rd ACM Conference Computer and Communications Security (ACM CCS), pages 308-318, 2016.
[2] H. Asi and J. Duchi. Near instance-optimality in differential privacy. arXiv:2005,10630 [cs. CRJ, 2020.
[3] H. Asi and J. C. Duchi. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in Neural Information Processing Systems 33, 2020.
[4] H. Asi, J. Duchi, A. Fallah, O. Javidbakht, and K. Talwar. Private adaptive gradient methods for convex optimization. In Proceedings of the 38th International Conference Machine Learning, pages 383-392, 2021.
[5] H. Asi, V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Opti- mal rates in é geometry. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[6] R. F. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv:1412.c 4451 [math.ST], 2014.
[7] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient al- gorithms and tight eтror bounds. In 55th Annual Symposium on Foundations of Computer Science, pages 464-473. 2014.
[8] R. Bassily, V. Feldman, K. Talwar, and Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems 32, 2019.
[9] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Advances in Neural Information Processing Systems 33, 2020.
[10] A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167-175, 2003.
[11] J. Bolte, T. P. Nguyen, J. Peypouquet, and B. Suter. From enror bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165:471-507, 2017.
10

---

[12] L. Bottou, F. Curtis, and J. Nocedal. Optimization methods for large-scale learning. SIAM Review, 60(2):223-31, 2018.
[13] M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. P. Woodruff. Communication lower bounds for statistical estimation problems via distributed data processing inequality. In Pro- ceedings of the Forty-Eightn Anmual ACM Symposium on the Theory of Computing. 2016. URL https:/ arxiv. org/ abs//506..... 07216.
[14] T. Cai and M. Low. A framework for estimating convex functions. 423 456, 2015.
Statistica Sinica, 25:
[15] Chatterjee, Duchi, Lafferty, and 7hu. Local minimax complexity of stochastic convex optimization. In Advances in Neural Information Processing Systems 29, 2016.
[16] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 12:1069-1109, 2011.
[17] C. Duchi. Information theory and statistics, Lecture Notes for Statisties 311/EE 377, Stanford University, 2019. URL http://web http:///veb.staford stanford. etu/class/stats311/ lecture-notes. pdf. Accessed May 2019.
[18] Duchi and F. Ruan. Asymptotic optimality in stochastic optimization, Annals of Statistics, 49(1):21-48, 2021.
[19] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 54th Annual Symposium on Foundations of Computer Science, pages 429 129-438, 2013.
[20] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3 & 4):21 1-407, 2014.
[21] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT 2006), 2006.
[22] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Theory of Cryptography Conference, pages 265-284, 2006.
[23] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science (ITCS), pages 214-226, 2012.
[24] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. In Proceedings of the Thirty Second Annual Conference on Computational Learning Theory, pages 1270-1279, 2019.
[25] V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Optimal rates in linear time. Proceedings of the Fifty-Second Annual ACM Symposium on the Theory of Computing, 2020.
[26] A. Garg, T. Ma, and H. I.. Nguyen. On communication cost of distributed statistical estimation and dimensionality. In Advances Neural Information Processing Systems 27, 2014.
[27] M. Hardt and K. Talwar. On the geometry of differential privacy. Proceedings of the Forty- Second Annual ACM Symposium the Theory of Computing, pages 705-714, 2010. URL http://arxiv.ort wwwpaaaiivv..aaaaaaaee wwwp/bg/g//b/ooooooee .37544
[28] Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. Fairness without demographies in repeated loss minimization. In Proceedings of the 35th International Conference Machine Learning, 2018
[29] E. Hazan and S. Kale. An optimal algorithm for stochastic strongly convex optimization. In Proceedings of the Twenty Fourth Annual Conference on Computational Learning Theory, 2011. URL http:// htop:///axxin org/ wwwaaabb.....////../// 2425.
[30] C. Jin, P. Netrapalli, Ge, S. M. Kakade, and M. I. Jordan. short note on concentration inequalities for random vectors with subgaussian norm. arXiv: 1902.03736 (math.PR) 2019.

---

[31] A. Juditsky and Y. Nesterov. Primal-dual subgradient methods for minimizing uniformly convex functions. URL http://hal. archives ouvertes / Strong-hal pdf, 2010.
[32] A. Juditsky and Y. Nesterov. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stochastic Systems, 4(1):44 80, 2014.
[33] D. Levy and J. C. Duchi. Necessary and sufficient geometries for gradient methods. In Ad- vances in Neural Information Processing Systems 32, 2019.
[34] D. Levy, Z. Sun, K. Amin, S. Kale, A. Kulesza, M. Mohri, and A. Suresh. Learning with user-level privacy. Advances in Neural Information Processing Systems 34, 2021. URL https: //arxiv. org/ abs /20222 11845.
[35] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication- efficient learning of deep networks from decentralized data. In Proceedings of the 20th Inter- national Conference on Artificial Intelligence and Statistics, 2017.
[36] M. Mitzenmacher and E. Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
[37] A. Nemirovski and D. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
[38] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal on Optimization, 19(4):1574-160) 2009.
[39] Y. Nesterov. Accelerating the cubic regularization of newton's method on convex problems. Mathematical Programming, 112(1):159-15) 181, 2008
[40] A. Ramdas and A. Singh. Optimal rates for stochastic convex optimization under tsybakov noise condition. In Proceedings of the 30th International Conference on Machine Learning, pages 365-373, 2013.
[41] A. Smith and A. Thakurta. Differentially private feature selection via stability arguments, and the robustness of the Lasso. In Proceedings of the Twenty Sixth Annual Conference on Computational Learning Theory, pages 819-850, 2013. URL http: http::://pocceeings... mlr. press/v30/Guhae html.
[42] M. J. Wainwright. High- Dimensiinnsi Statisties: A Non-Asymptotic Viewpoint. Cambridge University Press. 2019.
[43] Y. Xu, Q. Lin, and Yang. Stochastic convex optimization: Faster local growth implies faster global convergence. In Proceedings of the 34th International Conference Machine Learning, pages 3821-3830, 2017.
[44] B. Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, pages 433-435. Springer- Verlag, 1997.
[45] Y. Zhang, C. Duchi, M. Jordan, and M. J. Wainwright. Information-theoreti lower bounds for distributed estimation with communication constraints. In Advances in Neural Information Processing Systems 26, 2013.
[46] Y. Zhu, S. Chatterjee, J. Duchi, and Lafferty. Local minimax complexity of stochastic convex optimization. In Advances in Neural Information Processing Systems 29, 2016.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e-g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "iCp4SCgZW-", "reviewer": "Reviewer_GACB", "summary": "This work proposes private stochastic convex optimization algorithms that adapt to the growth condition of the objective function. This work also establishes several lower bounds that justify the optimality of the proposed algorithms.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written and easy-to-follow. The text has a nice flow of ideas. The developed algorithms only require a lower bound on the actual growth constant (probably need to make this requirement clearer in the abstract) and adapt to the true growth condition to improve the privacy rate, which is a significant contribution. The prior work/background is discussed at length throughout the paper and the theorems are attached with proof sketches and insights, which are highly appreciated. I only have some  minor comments as follows.\n\n- I wonder how the growth constant $\\kappa$ can be efficiently estimated and how a very rough estimate of $\\kappa$ would affect the rate.\n- Typos: Line 143, different fonts for A_1 and A_k; In Algorithm 1, at line 10, remove \"algorithm\"; Line 484, developing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "D8S9UugvbzV", "reviewer": "Reviewer_aQoc", "summary": "This paper presents a differentially private mechanism for releasing data and an optimisation algorithm that can use the released data and minimise a convex function. While there are many such algorithms in prior work, the current manuscript provides an algorithm that is adaptive and has convergence rate that improves with the \"growth\" of the function around the optimum point. Furthermore, the authors present matching lower bounds, which show that their algorithm is close to optimal. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Contribution*\nThe main contribution of the paper is two-fold: an upper bound which attains the claimed convergence rate and the lower bound. I was unable to read the details about the lower bound in the supplementary material and the description in the main text didn't provide a clear picture to me. So I will focus on the upper bound. The algorithm is simple to describe: In each iteration, the algorithm limits the learning rate, reduces the domain to the neighborhood of the previous point, and repeats multiple iterations of a local optimization procedure. The local optimization procedure uses ERM to minimise an $\\ell_2$-regularized version of the function with the regularizer weight updated exponentially in each inner iteration. Just before releasing the point, a Laplace noise is added to the output, which ensures differential privacy. I found it remarkable that the overall algorithm is so simple and can be (perhaps) implemented even in practice. \n\nI was able to roughly verify the proof, but I couldn't find a crisp high-level description of the algorithm. For instance, what was the role of exponentially decreasing variance in step 9? What is the tradeoff between privacy and convergence rate as a function of the noise parameter chosen in this step?\n\n\n*Originality*\nI found the problem and the result very interesting. The algorithm proposed (algorithms 1,2) are very simple, and somewhat intuitively clear. However, owing to my lack of knowledge about the prior work and lack of time to dig deeper, I was unable to evaluate the contribution in comparison with prior work. Nonetheless, the authors have provided adequate references to prior work, and I think the work is sufficiently novel. \n\n*Quality and clarity*\nThe paper is well-written, especially Section 4, and presents results on an important problem. I was a bit lost in Section 3 -- even the statement of Theorem was not very clear since the algorithm $A_{\\tt gr-inv}(S)$ was not very clear. But overall the work is of high quality. \n\n\n*Significance*\nThere is broad interest in studying optimization under privacy and similar constraints, and this paper presents a new algorithm for that setting. Even if one ignores the theoretical optimality, the paper provides an interesting algorithm for a practitioner to build on.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sufficiently addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3tq7J_fF3q", "reviewer": "Reviewer_pyyH", "summary": "This paper studies the SCO with loss function that satisfies growth conditions in the differential privacy model. Firstly, it considers the empirical risk function and provide an algorithm based on the inverse sensitivity mechanism. Then they show an efficient algorithm and the lower bounds of the problem in the both $\\epsilon$ and $(\\epsilon, \\delta)$-DP models.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Advantage:\n1)They provide a high probability version of the previous algorithm on DP-SCO with general convex loss functions, which might be used to other problems. \n2)They give the first study on DP-SCO with loss functions that satisfy the growth condition and show their upper bounds and lower bounds ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n\n1) Lower bounds only hold for the case where $k\\geq 2$ for general dimension case. \n2) As we can see from the result, theoretically, the rate of DP-SCO with growth condition loss is  faster than the general convex loss. However, there is lack of experiments, most of the previous work on SCO with growth condition has experimental studies. So I think there is still improvements.\n3)In Algorithm 2, step 10 need to do a projection step onto the set $\\mathcal{X}_i$ which is the intersection of the constraint set $\\mathcal{X}$ and a ball.  How to get the exact solution of this step. If we can get approximate solution by using such as Dykstra’s algorithm, then how to guarantee the DP and the upper bound? So I don't think it is an efficient algorithm. \n\nBased on the previous concerns, I tend to reject the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Despite some suggestions for additional results that could round out the paper, and presentation suggestions for clarifying the paper's conceptual contributions, I would like to recommend it for acceptance. In particular:

- As an algorithmic paper, providing a new suite of algorithms and complementing them with matching lower bounds tells a complete story. Experiments would be nice, but given the other results I do not believe they are necessary. 

- Concerning Reviewer pyyH's comment about inexact projections, the author's proposed modifications should indeed be implemented carefully. Ensuring that the approximate projections do not (even in the worst-case over the projection algorithm) significantly increase sensitivity affects the privacy guarantee of the final algorithm. So this is an important effect to be accounted for in detail.
Decision: Accept (Poster)