Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
Authors: Raef Bassily
Cristóbal A Guzmán
Michael Menart
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Stochastic Optimization

Abstract:   We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs). Our algorithm for the $\ell_2$ setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time. Our algorithm for the $\ell_1$ setting has nearly-optimal excess population risk $\tilde{O}\big(\sqrt{\frac{\log{d}}{n}}\big)$, and circumvents the dimension dependent lower bound of \cite{Asi:2021} for general non-smooth convex losses. In the differentially private non-convex setting, we provide several new algorithms for approximating stationary points of the population risk. For the $\ell_1$-case with smooth losses and polyhedral constraint, we provide the first nearly dimension independent rate, $\tilde O\big(\frac{\log^{2/3}{d}}{{n^{1/3}}}\big)$ in linear time. For the constrained $\ell_2$-case, with smooth losses, we obtain a linear-time algorithm with rate $\tilde O\big(\frac{1}{n^{3/10}d^{1/10}}+\big(\frac{d}{n^2}\big)^{1/5}\big)$. 
  Finally, for the $\ell_2$-case we provide the first method  for {\em non-smooth weakly convex} stochastic optimization with rate $\tilde O\big(\frac{1}{n^{1/4}}+\big(\frac{d}{n^2}\big)^{1/6}\big)$ which matches the best existing non-private algorithm when $d= O(\sqrt{n})$. We also extend all our results above for the non-convex $\ell_2$ setting to the $\ell_p$ setting, where $1 < p \leq 2$, with only polylogarithmic (in the dimension) overhead in the rates.

Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
Raef Bassily
Cristóbal Guzmán
Department of Computer Science & Engineering Translational Data Analytics Institute (TDAI)
Department of Applied Mathematics
University of Twente Inst. for Mathematical and Comput. Eng. Pontificia Universidad Católica de Chile
The Ohio State University bassily.. 1@oos. edu
guzmandutvente. nn
Michael Menart
Department of Computer Science & Engineering The Ohio State University menart. 20osu. edu
Abstract
We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLss). Our algorithm for the l2 setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time. Our algorithm for the
l setting has nearly-optimal excess population risk Ö(v log d and circumvents 12.
the dimension dependent lower bound of [AFKT21] for general non-smooth convex losses. the differentially private non-convex setting, we provide several new algorithms for approximating stationary points of the population risk. For the fi-aase with smooth losses and polyhedral constraint, we provide the first nearly dimension independent rate, Ö loga/a d
in linear time. For the constrained f2-case (mz)
with smooth losses, we obtain a linear-ting time algorithm with rate Ö(117 + (mE)=75 Finally, for the fg-case provide the first method for non-smooth weakly convex stochastic optimization with rate Ö ",,/ + (me))73)
22/0 which matches the best existing
non-private algorithm when d O(vn). We also extend all our results above for the non-convex E setting to the Ep setting, where < S 2, with only polylogarithmic (in the dimension) overhead in the rates.
Introduction
Stochastic optimization (SO) a fundamental and pervasive problem machine learning, statisties and operations research. Here, the goal is to minimize the expectation of a loss function (often referred to as the population risk), given only access to a sample of i.i.d. draws from a distribution. When such a sample entails privacy concerns, differential privacy (DP) becomes an important algorithmic desideratum.
Consequently, differentially private stochastic optimization (DP-SO) has been actively investigated for over decade. Despite major progress in this area, some crucial problems remain with existing
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Loss
E--Setting
Rate
Linear Time?
Thm.
Convex GLL (Nonsmooth)
log
=
max
L v
Nearly
5
log (ne)173
Nonconvex Smooth
1
8
1 <<p52
2/a
+ 2/3
dR n=
1/5
10
w1/a
Weakly Convex
(Nonsmooth)
1 p
1///4
2//4
+ K
4/3
de n²=²2
1/6
16
Table 1: Accuracy bounds and running time for our algorithms. Here, n is sample size, d is dimension, e, 8 are the privacy parameters, & min( p-I: log d} and & = 1 + log d 1(p < 2). We omit the dependence on factors of order polylog(n, 1/6). Bounds shown for unit ép ball as a feasible set.
methods. One major problem the lack of linear-time' algorithms for nonsmooth DP-SO (even in the convex case), whereas its non-private counterpart has minimax optimal-risk algorithms which make a single pass over the data [NY83]. A second challenge arises DP-SCO for non-Euclins non-Euclidean settings; i.e. when the diameter of the feasible set, and Lipschitzness and/or smoothness of losses are measured w.r.t. a non- -uclldadd norm (c.g., Ep norm). particular, in the & é1-setting there is a stark contrast between the polylogarithmic dependence the dimension in the risk achievable for the smooth case and the necessary polynomial dependence on the dimension in the non-smooth case [AFKT21].
Finally, our understanding of DP-SO in the non-convex case is still quite limited. In the non-convex domain, there only few prior results, all of which have several limitations. First, all existing works either assume that the optimization problem is unconstrained or only consider the empirical version of the problem known as differentially private empirical risk minimization (DP-ERM) ERM). Obtaining population guarantees based on the empirical risk potentially limits the applicability of the existing methods either in terms of accuracy in terms of computational efficiency. In particular, all existing methods require super-linear running time w.r.t. the dataset size. Second, most of the existing works consider only the Euclidean setting. Finally, none of the prior works have studied non-convex DP-SO when the loss is non-smooth.
The goal of this work is to provide faster and more accurate methods for DP-SO. Some of the settings we investigate are also novel in the DP literature.
1.1 Our Results
We enumerate the different settings we investigate in DP-SO, together with our main contributions.
Convex generalized linear losses. Our first case of the study is non-smooth DP-SCO the case of generalized linear losses (GLL). This model encompasses broad class of problems, particularly those which arise in supervised learning, making it a very important particular case. Here, our contributions are two-fold. First, in the fz-setting, we provide the first nearly linear-time algorithm that attains the optimal excess risk. The fastest existing methods with similar risk work for general convex losses, but they run in superlinear time w.r.t. sample size [AFKT21, KLL21J. Our second contribution here is a weerly-dimension independent excess risk bound in the é é1-setting" for convex non-smooth GLL. This result circumvents general DP-SCO excess risk lower bound in the non- smooth fe-stttngg which shows polynomial dependence on the dimension [AFKT21], and it matches the minimax risk in the non-private case when (11) [ABRW12].
In this work, complexity is measured by the number of gradient evaluations, omitting other operations. This is in line with the oracle complexity model in optimization [NY83].
"One exception [WX19] who study the & setting the context DP-ERM under fairly strong assumption (see Related Work section).
3 As in all existing works on DP-SO, in the f fi-setting we also assume the feasible set to be polyhedral.

---

Our two contributions for GLL follow the same simple idea. We leverage the GLL structure, namely the fact that these losses are effectively "one-dimensional," to make a fast approximation of the Moreau envelope of the loss [Mor65]. We can then exploit the smoothness of the envelope to improve algorithmic performance. A similar approach was taken by [BFTT19], but their approach suffered from an increase in the running time by a factor of n due to the high cost of approximating the gradient of the envelope, which involves solving a high dimensional strongly convex optimization problem at each iteration. In the case of E2, we use an existing linear-time algorithm for smooth DP-SCO with optimal excess risk [FKT20] combined with our smoothing approach, which results in an On log -time algorithm. In the case of f1, we use existing noisy Frank- Wolfe algorithm that attains optimal empirical risk for smooth losses [TTZ15], together with generalization bounds for GLLs based on Rademacher complexity [SSBD14]. This algorithm is not linear time, and hence it is tempting to instead use a variant of one pass stochastic Frank- [AFKT21, BGN21]. However, the excess risk of these algorithms has linear dependence on the smoothness constant, which prevents us from obtaining the optimal risk via smoothing. Hence, it is an interesting future direction to improve the running time in the & f-ssttinng
algorithms, as in
Non-convex Smooth Losses. Next, we move to the setting of smooth non-convex losses, where the goal is to approximate first-order stationary points (see (1) in Section 2). This case has attracted significant attention recently, and it brings major theoretical challenges since most tools used to derive optimal excess risk in DP-SCO, such as uniform stability [HRS16, 16, BFGT20] or privacy amplification by iteration [FKT20], no longer apply. Here, we provide the first linear time private algorithms. In the L -ssttingg we obtain a mearly-dimension independent rate ( d/ [ns)) which to the best of our knowledge is new, even in the non-private case. We suspect that our rates for the -isstting are essentially tight for linear-time algorithms (at least when E = (()). In [ACD+ 19], for non-convex smooth SO in the fz-setting an oracle complexity lower bound 12 is shown for attaining a- approximate stationary points via a stochastic gradient oracle. This, together with the non -oivvaitee upper bound [FLLZ18, HKMS20. ZSM* 20], implies that in the non-private setting, the stationarity rate 1/n is optimal for linear-time stochastic first-order algorithms. In the 22-setting (and more generally, for fp-setting, where S p S 2) our stationarity rate (see Table 1) is slightly worse than the state of the art, ((d/n2))//4 [ZCH* 200. However, in [ZCH* + 20]. only the unconstrained case is considered, where the accuracy measure is the norm of the gradient; moreover, the running time is superlinear, O(n2e/ e/))).
Our workhorse for these results is a recently developed variance-reduced stochastic Frolk method [HKMS20, ZSM+20), which has also proved useful in DP-SCO [AFKT21, BGN21J. This method is based on reducing variance through a recursive estimate of the gradient at the current point, leveraging past gradient estimates and the fact that step-sizes are small. Applying this technique in DP is challenging, as we need to carefully schedule the algorithm in rounds (to prevent gradient error accumulation) and to properly tune step-sizes and noise, in order to trade-off accuracy and privacy.
Non-convex non-smooth losses. We conclude with the case of weakly convex non-smooth stochastic optimization, where we devise algorithms to compute close to rearly-stationary points. Weakly convex functions are natural and rather common model in some machine learning applications, including convex composite losses, robust phase retrieval, non-smooth trimmed estimation, covariance matrix estimation, sparse dictionary learning, etc. (see [DG19, DD19] and references therein). Moreover, this class subsumes smooth non-convex functions. To the best of our knowledge, this setting has not been previously addressed in the DP literature, Our algorithm is inspired by the eokimalll-guudeer stochastic subgradient method from [DG19]. and it is based approximating proximal steps w.r.t. the risk function, where each proximal subproblem is solved through an optimal DP-SCO method for strongly convex losses [AFKT21]. This algorithm works similarly for the L and f2 settings (and, in fact, lp for any 1 S P < 2), for which we exploit the strong convexity non-Euclidean extensions seem to be new, even in the
properties of these spaces. Here again, non-private case. Our rates for fz-setting match the best existing non-private rates, (11/n-/4), in the regime d = =(vz) (when E = @(1)). Finally, we observe that our algorithm runs in time Óminn(n2 3/2 (n3/2,nee/Vd))
Unless otherwise stated, we will refer to first-order stationary points stationary points.
3

---

1.2 Related Work
Differentially private convex optimization has been studied extensively for over a decade (see, e.g.. [CMS11. JKT12, KST12, BST14, JT14. TTZ15, BFTT19, FKT20J). Most of the early works in this area focused on the empirical risk minimization problem. The first work to derive minimax optimal excess risk in DP-SCO [BFTT19]. which has been further improved. in terms of running time (e.g. [FKT200, BFGT20, KLL21J). Non-Euclidean settings in DP convex optimization were studied in [JKT12, TTZ15]. Nearly optimal rates for non-Euclidean DP-SCO were only recently discovered in [AFKT21, BGN21J. [JT14] was one of the first works to focus on the case of private optimization for GLLs, and showed that dimension independent excess risk was possible & and & settings. These results have since been superseded in the & case by [AFKT21] and in the E2 case by [SSTT21].
In the non-convex case, [7ZMW17, WYX17, WJEGI9] studied smooth unconstrained DP-ERM in the Euclidean setting. Smooth unconstrained DP-SO was studied in [WCX19], where relatively weak guarantees on the excess risk were shown. Convergence to second-order stationary points of the empirical risk was also studied in the same reference under stronger smoothness assumptions. Smooth constrained DP-ERM was studied in [WX19] in both & and & settings. However, their result in the & setting entails the strong assumption that the loss is smooth w.r.t. the E2 norm. The special case of non-convex smooth GLLs was studied in [SSTT21], however, their result is limited to the empirical risk (DP-ERM) in the unconstrained setting. The work of [ZCH*20] studied DP-SO in the Euclidean setting, and gave convergence guarantees in terms of the population gradient, however, their results are limited to smooth unconstrained optimization.
2 Preliminaries
Normed Spaces. Let (E, II be a normed space of dimension d, and let (:.)) an arbitrary inner product over E (not necessarily inducing the norm || []). Given x E E and r >> 0, let B 1-1
{y E: lly =z|| < r). The dual norm over E is defined usual, |/vll- - max] (y, x)). With this definition, (E, || []+) is also d-dimensional normed space. As main example, consider the case of e (R || llp), where 1 S S oc and ||>||p (Eye(a) (=,,1)) 1/p As consequence of the Hölder inequality, one can prove that the dual of ty corresponds to ed where S q S oo the conjugate exponent of p, determined by 1/p + 1/9
A randomized algorithm A is said to be (e,8) differentially private (abbreviated (c, dD-D) if for any pair of datasets and differing one point and any event & in the range of A it holds that
Differential Privacy [DKM+06)
P[A(S) E E S EP((A(S)) E E +
Lemma (Advanced composition [DRVI0, DR14]. For any E > 0,5 (0, 1), and 8' E (0, 1), the class of (e, -iiffeerrnttillly private algorithms satisfies (E', kō )diffferrelt privacy under k-fold adaptive composition, for E' E / log(1/8)) + k=(e--1 1).
Stochastic Optimization.
the Stochastic Optimization problem with (E, [1l-----sttnnng we have
normed space (E, || I]): feasible set W E which is closed, convex and with diameter most D w.r.t. I|=||; and loss functions f Wx >> IR are assumed to be Lo-Lipschitz w.r.t. ||-||. Sometimes, we also consider losses which are Ls-mmooth: i.e., for all w, v E W. [IV V ff
[T]| el]-
In this problem, there is an unknown distribution DD over a set Z, and our goal is to minimize a certain accuracy measure that depends on the population risk, defined as l'( (w) Eg-D[f(w, =)],
when only given access to sample S (21, ..., 2n. i.L.d. D. In Differentially Private Stochastic Optimization (DP-SO) one concerned with solving this problem under the constraint that the algorithm used is (e, 8DP w.r.t. S.
Depending on additional assumptions the losses, the accuracy measure in DP-SO may vary. In the convex cuse, the accuracy of stochastic optimization algorithm is naturally measured by the excess population risk, defined as (w)) - mingew FD(u). For the non-convex case, providing guarantees on the excess population risk is often intractable.

---

Non-Conver Convex Stochastic Optimization. In the non-comvex smooth case, common performance measure use the stationarity gap of the population risk, which for w E W defined as
Gap (w) (
v).
-EW
Note that if the stationarity gap is zero, then is indeed stationary point of the risk. For the non-convex non-smooth case, near stationarity (i.e,, small stationarity gap) often a stringent concept, the set of points with small stationarity gap may coincide with the stationary points themselves. Hence, we will consider instead the goal of finding close to searll-stationary points [DG19, DD19], which we formally introduce in Section 5.
3 Algorithms for Convex Non-smooth Generalized Linear Losses
In this section consider the case when is non-smooth generalized linear loss.
Definition 2 (Generalized Linear Loss). We say that f W (X' x R) + R an Lo-Lipschitz, R-bounded GLL with respect to norm ||- if max ||>|| S and for every y E R there exists a function ((v) IR R such that f(w, (2,y) v)) = ((x, w)) and g(v) is Lop-hipschi..
We will occasionally refer to the x component of datapoint the feature vector. Note the GLL definition implies that f(,, 2) is RR-LLsshssss By smoothing the function f through f, one can obtain smoothing which is both efficient and invariant the norm. The first property can be used attain an optimal rate for DP-SCO in nearly linear time. The later property allows for an essentially optimal, nearly dimension independent rate in the setting for non-smooth GLLs.
3.1 Smoothing Generalized Linear Losses
Existing works such [BFTT19] have used the Moreau envelope smoothing [Mor65] for DP-SCO, but suffer from the high computational cost of computing the proximal operator. For GLLs, we can smooth instead of f to obtain smoothed function efficiently. We leave the details of the Moreau smoothing and proofs for Appendix A.1 and focus here on our results. We have the following guarantee for the smoothed version of f.
Lemma 3. Let (x, E (X IR). Let C be the Moreau envelope of glv) and define fs(w, 2) ( (ww, Then fa is 2L R-Lipschitz and 3||=1[2-smooth with respect to || and [f(w (x,μ)) fa(w, (x, v) 21 for all w E W.
By smoothing f through f, we reduce the evaluation of the proximal operator to a 1-dimensional convex problem. This allows to use the bisection method obtain the following oracle for fa which runs in logarithmic time.
Lemma 4, Let B, a > and let ||-I| be a norm. Then the there exists a gradient oracle, Og for fo (Algorithm 3 in Appendix A.l) which satisfies [V (z, y)) OO, (x, vI) a for any x such that | < R. Further, OB,o, has running time O (log( 12 /a²)).
3.2 New Results from Smoothing
Linear Time DP-SCO in the & Setting. Given the oracle described above, we can optimize fa using the linear time Phased-SGD algorithm [FKT20]. When using OB.a, instead of the true gradient oracle, V.. we need account for two additive penalties, the increase in error due to using the approximate gradient and the increase error to due to minimizing the smoothed function (see Appendix A.2 for details). We ultimately have the following guarantee.
Theorem 5. Let W Idd have || Ila-dimmeter at most D. Let W (X R) be Lpplhit and R-bounded GL.. with respect to ||2- Let B /nLo/ R, R
LaRk alog Then Phased-SGD -GD run with oracle O3.0. R and dataset E 2n satisfies (e, 8) differential privacy and
has running time On n log n). Further, if Dn the output of Phased-SGri has expected excess
population risk O (LORD
(flog(188) ne
1
Vn
5

---

Remark. The algorithm which implements O,,a, (Algoritim 3 in Appendix A.1) also works in the unconstrained case (W =R)). This is due to the fact that evaluating the gradient of the smoothed function involves solving a regularized objective, which naturally bounds the region which the minimizer lies. For differentially private GLLs this is relevant, as [SSTT21] showed that in this setting one can achieve dimension independent excess risk. For more details, see Appendix A.2.
Better Rate for & Setting. Another interesting consequence of the above smoothing is that, because it is scalar in nature, it allows us to achieve better rates in the & f1-setting. In [AFKT21] it was shown that the optimal rate for general non-smooth losses under (E, 5)-D was roughly ((Vd/[ne log d)). However, their lower bound does not apply to GLL.s. In the following, we show that using the smoothing technique previously described we can achieve a better rate of ((1/vnE). We note this rate is optimal in the regime (1)) [ABRW12].
Theorem 6. Let W I be a polytope defined by a set of vertices V of cardinality J, where W = CV) and W has I1-111 I-lam-iteeteer at most D. Let f W x (X' x R. + R be Lo Lo-Lipschitz and R-bounded GLL with respect to || 1111- Let
log- (1 (og(()) and a "log(n) Then Noisy Frank Wolfe (Algorithm in Appendix A.3) with oracle OB.a. and dataset E z satisfies (c, difffeerrttia privacy. Further, i DD the output of Noisy Frank Wolfe has expected
LaynE
excess population risk O
Lo RD
log (1/8))(1//// log(n)
Aog.
v/1
Proof details are located in Appendix A.3.
4 Algorithms for Non-convex Smooth Losses
In this section, we describe differentially private algorithms for non-convex smooth stochastic optimization in the f--setting for 1 S p S 2. We provide formal convergence guarantees in terms of the stationarity gap (see (1) in Section 2). Our algorithms
inspired by the variance-reduced stochastic Frank-Wolfe algorithm [ZSM 20). However, our algorithms involve several crucial differences from their non- non-private counterpart. In particular, they are divided into number of rounds R = (log(n)), where each round r E {0. ... R-11) 1} involves 2" updates for the iterate. Each round starts by computing fresh estimate for the gradient of the population risk at the current iterate based on a large batch of data points, then such gradient estimate is updated recursively using disjoint batches of decreasing size sampled across the 2" iterations of that round. Using this round-based structure and batch schedule, together with carefully tuned step sizes, allows us to effectively control the privacy budget while attaining small stationarity gap w.r.t. the population risk. Moreover, our algorithms make single pass on the input sample, i.e., they run in linear time.
In this section, we assume that Vz 2, f(,,2) is I. Lop-Lipsehizz and Lm-sth loss in the respective f norm. A key tool we use in our analysis in this section is the notion of regularity of normed spaces [JN08]. Roughly speaking, this notion captures the smoothness properties of the dual norm, which allows us to bound the error in the gradient estimates computed across the iterations of our algorithms. This, in turn, allows extends the applicability of our algorithms to general spaces whose dual has sufficiently smooth norm. For more details on this notion, we refer the reader Appendix B.
bound the stationarity gap of the output. In fact, this notion of regularity
4.1 Algorithm for Polyhedral and & Settings
We consider the polyhedral setup, namely, consider normed space [I, [], where the unit ball w.r.t. the norm, Bj is a convex polytope with at most J vertices. The feasible set W, is a polytope with at most J vertices and ||
||-dimmeter
0.
The formal guarantees of Algorithm I are stated below. Detailed proofs can be found in Appendix B.
Theorem 7. Let Tr.t = V44I Vr, t. Then, Algorithm is (e, -differrrett private.

---

Algorithm ApolysFW: Private Polyhedral Stochastic Frank-Wolfs Algorithm
Require: Dataset S (Z1,..... kn) E 2", privacy parameters (e, polyhedral set W with J vertices V
Us). number of rounds R, batch size b, step sizes (Br,: r O,..., R 1, = O..... 1). ....,R 1: Choose an arbitrary initial point uf W
(V1, (V..,.,,,))
2: for to R do
(og(1/8)
3: Let = 2D + D) be
4: Draw batch B of b samples without replacement from S
5: Compute Vr = E.EE V
6:
of arg min {1o, V + (v)), where vL((v) Lap (s,)
w. "EV
7:
7r.0) ) 77,00%
8:
for = to 2
do
9:
Draw a batch B of b/(t 1) samples without replacement from S.
10:
Compute A [+1 Σ SEB: [V( V (f 22)
11:
V. (1 1,,)) (V.- A:) + Th, _ EzeRy Vf(w,,
12:
Compute oz arg min vev (u, ( + (L(,,,, where ut (v) (sp)
13:
w++1 (1 nr,))u tr
14:
w++1 u
Output S uniformly chosen from (ut r {0, (o..... R- 1,, {0, ......, 25 -
Theorem 8. Let R
332 log log" log (n) /lg(11/))
Tog"(n) and Tr, VHII Vr,t. Let 'D
be any distribution over Z. Let S ~ DD be the input dataset. The output w of Algorithm I satisfies
log 2/3 (J) 1 log 1/6 (1/6)
Gappo, Po (w) = 0 D(Lo LDD) E
n 133g1/3
The proof of the above theorem relies on the following lemma, which gives a bound on the expected error in the gradient estimates V
Lemma 9, Let DD be any distribution over Let D be the input dataset of Algorithmm 1. Let the step sizes Tr, /IFI Vr, t. For every E (O...., 1}, t E {O.... 2 - 1}. the recursive gradient estimator V. satisfies
E [|| - VFD(w S 4L
Log(Ji b
(1-
v++1)
[+1 + + Lo)
log(J) Vb
(t + 1)1/4.
4.2 Algorithm for lp Settings when 1 <
Our algorithm in this setting has similar structure Algorithm I in Section 4.1, except for the following few, but crucial, differences. First, for all iterations (r, the recursive gradient estimate V and the gradient variation estimate A are replaced with noisy versions V and A obtained by adding Gaussian noise to the respective quantities. Namely, in each round = 0, ..... 1, Steps 10, and 11 in Algorithm 1 are now, respectively, computed as follows:
E 1, Σ Ee Vf 2) + No. A 5 EEEB: (Vf(w),)) ff( 2)) + Ñi, and (+ E.EB. +)) N.) where No ~ N (0, o.,Taa V = (1 - m)a) ( + A + Trat [+1
and N N (0, G2 lal The noise parameters chosen such that the algorithm is (e, 8)- log(1// The
In particular, we set o² 16 log(1/)) and 0² 161/ 83ga 13
second difference here pertains to the way the iterates are updated, which now becomes w - ) (1-7ka)u, Wr, arg min V.). Finally, use a different setting for the number of rounds R nEW than the one used earlier. Below, we state the formal guarantees of this algorithm, which we refer to as noisy stochastic Frank- Wolfe AnsFw. In Appendix B.2, we give a formal description this algorithm (Algorithm 6) together with full proofs of the statements below.
7

---

Theorem 10. Algorithm AnsFw (Algorithm 6 in Appendix B.2) is (2, 8).
Theorem 11. Consider the Ep setting of non-convex smooth stochastic optimization, where <
p S 2. Let K = min (-T22))g(dd)) and - =1+ log(d) 1pp < 2). AnsFw, let R
log and Th. = over Z, and S ~ DD be the input dataset. The output i satisfies:
log
ne
1
Vr, t. Let D be any distribution
VaR 16g(116) w log?(n)
VII
E Gapp,, (w) (w)l =0 - (DLLo+ L)D)2/3
(n))
d /// log' 1/5 (1/6) log (m)
))
1/3
n2/5g2/5
Note that for the Euclidean setting, we have =
the above bound.
The proof of the above theorem has a similar outline to that of Theorem 8 with a few exceptions to account for the additional noise in the gradient estimates V As before, the proof of this theorem relies on the following lemma that bounds the error the gradient estimates in the dual norm.
Lemma 12. Let D be any distribution over Z, and S D be the input dataset. For the same settings of parameters in Theorem 11, the gradient estimate V satisfies the following for all r,t: t:
VFb(w)) SoT0 (VT
V dNR log(1/0)
(1-
f+
E
V
bc
vt+1/
v drcki (1/))/)) (t 173/8
+ 16 (L, Lo)
(t+
vb
be
Algorithm for Weakly Convex Non-smooth Losses
Our final setting is DP stochastic weakly convex optimization. Much of the theory of weakly-smooth functions is available in [RW98], but we provide a self-contained exposition in Appendix C.1.3 We recall that function f W + R p-weakly convex w.r.t. || if for all 0 < A < 1 and w, v W,
f(2w (1 - A)u) s Af(w) (1 () + pA(1 - A) w u11?
(2)
2
It is easy to see that any Lm-shhoth function is indeed Lı-weakly convex, so weak convexity encompasses smooth non-convex functions (see Corollary 25 in Appendix C.1). However, this extension is interesting as it also contains some classes of non-smooth functions.
5.1 Proximal-Type Operator and Proximal Near Stationarity
The next property is crucial for regularization of weakly smooth functions, and it would allow us to make sense of a proximal-type operator in some non-Euclidean norms. Proofs of results in this section can be found in Appendix C.2.
be a norm such that 11l 112 is u-strongly convex w.r.f. I| If is p-weakly convex and v3 2 p. then the function w + f(w) + & [|w w- is (n3 p)-strongly convex w.E.t ||. I]-
Proposition 13. Let ||-
We provide now some useful results regarding proximal-type mapping for weakly convex functions in normed spaced. This provides a non-Euclidean counterpart to results IRW98, DG19, DD19]. First, given W C E closed and convex set, we define the proximal-type mapping as:
8 [f(v) + -1l - (oo--w13)) w||
prox (w)
arg min NeW
Despite the stark similarity with the Euclidean proximal operator, the characterization proximal points is in general different (due the formula for the subdifferential of the squared norm), need to re-derive some near-stationarity estimates derived in [DD19, DG19].
*Our motivation to reproduce the basic theory stems from the fact that [RW98] and much of the literature of weakly convex functions focuses Euclidean settings, whereas interested in more general Ep settings.

---

Lemma 14. Let || - be such that 211 -11 is differentiable and v-strongly convex w.r.f. -l- ler f: E - R be p-weakly convex subdifferentiable function, W S E a closed. convex set with diameter D, and B > p/v. Then, for any w E W, the proximal-type mapping v = proxy (w) (given in (3)) well-defined, and moreover there exists E ff()) such that
sup (g, di 0} S 3D = vEW
The previous lemma is the key insight the accuracy guarantee and algorithms will use for stochastic weakly convex optimization. First, note that in the weakly convex setting it is unlikely to find points with small norm of the gradient small stationarity gap; however, will settle for points w E W which are I-close to a nearly-stationary point [DD19, DG19], i.e., that satisfies
(Eu E W) e af())) ||w w s 0 and
sup (g, v) S d. NEW
Above, is the accuracy parameter. This accuracy measure states that w distance at most & from d-nearly stationary point. It is then apparent how the proximal-type operator can certify (4). For convenience, we define notion efficiency in weakly-convex DP-SO, particularly geared towards algorithms that certify close near stationarity via the proximal-type mapping.
Definition 15 (Proximal Near Stationarity). A randomized algorithm A : z" + E. for the stochastic optimization problem min (D(w)) w). achieves (1.,3)-pro prroximal near stationarity if
Es-D" A prox & Pb (A(S)) - A(S)]] - 0/ 1,
(5)
Notice the maximum in the denominator normalizing factor, inspired by Lemma 14. Note further that, by Lemma 14, an algorithm with proximal near stationarity ensures closeness to nearly stationary points through its proximal-type mapping: namely, if A satisfies Definition 15, then
8 (A(S)) - A(S)]I < 0 and ES-D= [ppp
ES-D=,, Gapy,, (prox Fr (A(S)))) S 9.
In the above, some technical caution must be taken to define the gap function in the stochastic non-smooth case, which defer to Appendix C.2.3. Although not defined under this name, this is precisely the certificate achieved weakly-convex SO in recent literature [DG19, DD19].
5.2 Proximally Guided Private Stochastic Mirror Descent
Now we provide an algorithm for DP-SO with weakly convex losses that certifies proximal near stationarity (Algorithm 2).
Algorithm 2 Proximally Guided Private Stochastic Mirror Descent
Require: Private dataset S = (Z1...., Zn) E 2", number of rounds R B > O regularization
parameter
1: Let p = max (p. 1 + 1/ log d}, and choose initialization E W
2: for to R do
3: Extract batch S, from S Uter Sr of size, n, = n/R
4: Let Wy+41 the the output of Asc on data S, for the objective
min [.)) == (Fo(w) + 2 -1w -,r133)
(6)
5: Output: Output R chosen uniformly at random from (w, (wE)r[(R)-
This algorithm is inspired by the proximally guided stochastic subgradient method of Davis and Grimmer [DG19], where the proximal subproblems are solved using an optimal algorithm for DP- SCO in the strongly convex case, proposed in [AFKT21], that we call Asc (see Theorem 29 in Appendix C.3 for a precise statement). Our algorithm works in rounds r = 1...., .....,R R, and at each
round the proximal-type mapping subproblem
3 min F. (w) {Fo(w) + -1l wo w1. wEW

---

by is approximately solved using separate minibatch of size n/ R with algorithm Asc. The used in the subproblem norm is chosen as p = max(p, Finally, the output is chosen uniformly at random from the iterates.
log d}. order to control the strong convexity.
Below, formally state main result in this section. The proof can be found in Appendix C.3.
Theorem 16. Consider the Ep setting of p-weakly convex stochastic optimization, where S p S 2. Let K min(1/(p- 1), log d}. == 1+ log d 10p 2), and 2pk. Suppose that nd 2 pD/Lo. Then the output of the Proximally Guided Private Stochastic Mirror Descent (Algorithm 2 in Appendix D(ne)3 1/33 [Ra2y173 log(//()
C.3) is (e, 8). and for R provide a (1. 3) -proximmal nearly stationary point, with
min
nDp
it is guaranteed to }}
<be
[1, (1,x(1,pDDD ) o
L//4 (xD))/4
/llog(1/6) (1/6) 1/6
[mp] The running time of this
VP
{ne)pp
algorithm
upper
bounded
O log log logn min
(n3/2 (23/2 Vlog n
Remark 17. Some comments are in order. First, the bound from eqn. (7) takes the particular form for p 1 and p 2, respectively,
max/1.20 1.2p log d) 0
1.8/4 (D d//
+ Vlg D(
dlog(1/8)) (nEypp
1/6
[np]
p=
max (12pD)
Le
(D)
(/3
dllo(1//5) (ns)*p
1/6
p= 2.
VP
[m
Second, the upper bound in running time can be further refined, taking into account the precise value of R. We omit the resulting bound, only for simplicity. Third, note that the accuracy of algorithm can be further refined, if one considers the initial optimality gap, A = FD (F(()) ) Fp(w") instead of the crude upper bound AF D. We make this choice only for simplicity, and to keep consistency with the previous sections. Finally, note that the algorithm Asc requires performing Bregman projections, as uses stochastic mirror-descent as subroutine.
Acknowledgements
RB's and MM's research is supported by NSF Award AF-190828,, Google Faculty Research Award, and the OSU faculty start-up support. CG's research partially supported by INRIA through the INRIA Associate Teams project and FONDECYT 1210362 project.
References
[ABRW12] Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information-theore theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inf. Theory, 58(5):3235-3249 2012.
[ACD+ + 19] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake E. Woodworth. Lower bounds for non-convex stochastic optimization. CoRR, abs/1912.02365. 2019.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in 11 geometry. CoRR, abs/2103.01516. 2021.
[Bec17] Amir Beck. First-order methods in optimization. SIAM, 2017.
[BFGT20] Racf Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. In Advances in Neural Information Processing Systems 33, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[BFTT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
10

---

[BGN2I] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. ArXiv, abs/2103.01278, 2021.
[BLSTIO] Raghav Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta. Discovering frequent patterns in sensitive data. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 503-512, 2010.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS 2014). (arXiv preprint arXiv:1405. 700,,5 pages 464-473. 2014.
[Can11] Emmanuel Candes. Mathematical optimization. Lec. notes: MATH 301, Lec, notes: MATH 301, 2011.
[CMSII] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, ((Mar):1099 1109, 2011.
[DD19] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal Optimization, 29(1):007-239, 2019.
[DG19] Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM J. Optim., (713)):998119999 2019.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. EUROCRYPT, 2006.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211 (1:44)21114400 1-401, 2014.
[DRVI0] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS, 2010.
[FGV17] Vitaly Feldman, Cristobal Guzman, and Santosh Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty-Eight Annual ACC--IAN Symposium on Discrete Algorithms, SODA '17, page 1265-1277, USA, 2017. Society for Industrial and Applied Mathematics.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private Stochastie Convex Optimization: Optimal Rates in Linear Time, page 22, 2020.
[FLZZ18] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. arXiv preprint arXiv:1807.016955 2018.
[HKMS20] Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional gradient++: (non)convex minimization and continuous submodular maximization. SIAM J. Optim., 30(4):3315-3344, 2020.
[HRS16] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: stability of stochastic gradient descent. In ICML, 2016.
[HUL01] J.-B. Biriart-Urruty and C. Lemaréchal. Convex Analysis And Minimization A volume I and II. Springer, 2001.
[JKT12] Prateck Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In 25th Annual Conference on Learning Theory (COLT), pages 24.1-24.34 2012.
[JN08] Anatoli Juditsky and Arkadi Nemirovski. Large deviations of vector-valued martingales in 2-smooth normed spaces. Rapport de recherche hal-00318071, HAL, 2008.
11

---

[JT14] Prateek Jain and Abhradeep Thakurta. (near) dimension independent risk bounds for differentially private learning. In JCML, 2014.
[KLL21] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps. arXiv:2103 15352 [cs, staf], March 2021. arXiv: 2103.15352
[KST12] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1, 2012.
[Mor65] Jean Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273-299 29927,999, 1965.
[Nem95] A Nemirovski. Information based complxity of convex programming. 1995.
[Nes05] Yu Nesterov. Smooth minimization of non-smooth functions. Math. Program.,
103(1):127-152, May 2005.
[NY83] A.S. Nemirovsky and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. A Intere-itersccience publication. Wiley, 1983.
[RW98] R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational Analysis. Springer Verlag, Heidelberg, Berlin, New York, 1998.
[SSBD14] Shai Shalev-Shwer Shwartz and Shai Ben-David. Understanding machine learning: From theory algorithms. Cambridge university press, 2014.
[SSTT21] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2638-2646. PMLR, 13-15 Apr 2021.
[TTZ15] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly optimal private lasso. In NIPS, 2015.
[TTZ16) Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry. 1rXiv:I41 1.5417 [cs, stat], November 2016. arXiv: 1411.5417.
[WCX19] Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6526-6535. PMLR, 09-15 Jun 2019.
[WJEG19] Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient privacy- preserving nonconvex optimization. CoRR, 0tss/1910.16655 2019.
[WX19] Di Wang and Jinhui Xu. Differentially private empirical risk minimization with smooth non-convex loss functions: A non-stationary view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1182-1189, 2019.
[WYX17] Di Wang, Minwei Ye, and Jinhui Xu. Differentially Private Empirical Risk Minimization Revisited: Faster and More General. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[ZCH+20] Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee, Private stochastic non-convex optimization: Adaptive algorithms and tighter generalization bounds. CoRR, abs/2006.135011 2020.
12

---

[0]
20] Mingrui Zhang, Zebang Shen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One sample stochastic frank-wolfe. In International Conference on Artificial Intelligence and Statistics, pages 4012 PMLR, 2020.
[ZZMW17] Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IICAI'17, page 5922-3923 AÀAI Press, 2017.
13


Reviews:
[{"review_id": "ciTW4CyhCwt", "reviewer": "Reviewer_KmGd", "summary": "The paper provides a series of results on differentially private optimization. The covered settings include convex (nonsmooth) generalized linear losses and nonconvex (nonsmooth) losses.\nContributions:\nThe provided convergence rates are new for the consider settings.", "questions": "", "limitations": "", "rating": 6, "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": "The paper provides a few algorithms to achieve new or improved convergence rates for a few settings of private optimization. \nStrengths:\n1. Some convergence rates have a milder dependency on dimension compared with existing results in the literature. \n2. The convergence results on non-smooth settings seem to be new.\n\nWeaknesses:\n1. The paper is hard to read, there are too many results filled in the paper which leaves little space for informative discussions on intuitions and connections to existing results. It might be better to put some less important results in Appendix and provide more discussions in the main paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Ws864chOccf", "reviewer": "Reviewer_vTqw", "summary": "This paper studies differentially private stochastic optimization under different settings and develop several novel results. The authors first consider convex and nonsmooth generalized linear models, for which they develop an algorithm with optimal generalization bounds and nearly linear time. As a comparison, the existing results require super-linear training time. Then, they move on to nonconvex and smooth problems under $\\ell_1$ and $\\ell_p$ setting, and developed private algorithms with linear time based on stochastic Frank-Wolfe algorithm. Finally, they develop the first private algorithms for nonconvex and nonsmooth problems. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper contains many theoretical results on differentially private stochastic optimization under various settings. These results seem to be novel and interesting. I have some queries on the analysis and results and would increase my scores if the authors can address my queries.\n\nThe paper contains a nice table to summarize the main results. While this table is useful to understand the contribution of the paper, it lacks of a comparison with related work. It would be helpful if the authors can summarize the state of the art in the table so that readers can clearly understand the improvement over existing work.\n\nAccording to Table 1, the bound in Theorem 10 has two terms. The first term is a decreasing function of $d$. This appears a bit surprising since it is expected that a larger dimension would always increase the difficulty of learning. It is more natural that both terms grow as $d$. It would be helpful if the authors can give some explanation.\n\nAccording to Table 1, the rates in Theorem 10 are independent of $p$. Therefore, it is not clear to me the advantage of using different norm in the learning setting. Theorem 10 suggests that algorithms in different $\\ell_p$ setting would behave similarly.\n\nIn Lemma 1, the authors use the advanced composition. In the literature, people have developed another method to handle composition called Moments Accountant [1]. As indicated in [1], MA can outperform the advanced composition by a log(T) factor in the variance of random noise. Can the results in this paper be further improved if using MA?\n\nIn the proof of Lemma 4, the meaning of $\\tau$ seems not given. The authors mention that standard guarantees of the bisection give the bound $h_\\beta(\\tilde{u})-h_\\beta(u^*)\\leq\\tau 2^{-T}$. This bound is not quite clear to me. It would be helpful if the authors can give some details.\n\nIn Algorithm 3, the authors resort to PSGD in [FKT20]. I would suggest the authors to present PSGD in the paper to make it self-contained. In the first equation of Page 16, $F_{\\beta,D}(w_K)-F_{\\beta,D}(w_\\beta^*)$ should be $F_{\\beta,D}(\\tilde{w}_K)-F_{\\beta,D}(w_\\beta^*)$. Furthermore, it is not clear how the first inequality holds. It seems that the authors omit several steps in the deduction. It would be helpful if the authors can give some details.\n\nIn Line 548, the authors remove the subscript V in the inner product. It is not clear to me how this subscript V in the inner product can be removed. I would suggest the authors to give some explanation.\n\nIn Theorem 5, the authors should mention that they consider convex problems.\n \nThe meaning of the abbreviation DP-SCO is not given.\n\nLine 189: in error to due to\n\nLine 283: normed spaced\n\n[1] Deep Learning with Differential Privacy", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theory paper and I do not see societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "9Bf1LSzE_TJ", "reviewer": "Reviewer_Dzyq", "summary": "The paper studies the stochastic optimization problem with differential privacy in both the convex and non-convex setting. The main contributions of the paper are algorithms that achieve optimal excess risk and have faster running times in a number of settings. The first setting is the non-smooth convex setting. Here a challenging open problem is to obtain nearly-linear running time, and the paper makes progress towards this goal by providing such an algorithm for the special case of generalized linear losses in the ell_2 setting. The paper also provides an algorithm for generalized linear losses in the ell_1 setting as well. The next setting considered is the smooth non-convex setting, where the main contributions are linear time algorithms for ell_2, ell_1, and more generally ell_p with 1 <= p <= 2. The final setting is weakly convex functions, where the paper gives the first algorithm with privacy for ell_p with 1 <= p <= 2.", "questions": "", "limitations": "", "rating": 7, "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": "Significance: The stochastic optimization problem with privacy is a canonical problem in the area, and it has received considerable attention. This work makes several novel contributions to this line of work, and it makes progress towards fast algorithms in both the convex and non-convex setting.\n\nNovelty/originality: There seems to be sufficient novelty in both the algorithms and the analysis. The paper builds on techniques from both the prior work on private stochastic optimization as well as non-private optimization. However, adapting and extending the techniques poses several challenges in both the algorithms and the analysis.  \n\nClarity: The paper could be made more accessible by providing more discussion and intuition for the algorithms and the analysis. Providing a discussion on the parameter choices made by the algorithms and an interpretation of the convergence results would be helpful as well.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I did not track the hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies private algorithms for stochastic convex and non-convex optimization when the losses of interest come from Generalized Linear Models. For this case, they show that faster algorithms are possible for the non-smooth convex case for ell_2, and better rates are possible for the l_1 case, compared to the corresponding results for convex non-GLM losses. The author also study non-convex losses and there they show that under various constraints, one can privately find approximately stationary points.
The paper pushes forward the research in this important are of private stochastic optimization. The authors are encouraged to go over the reviews and incorporate corrections, as well as the relevant clarifications that came in the rebuttal. I recommend this paper be accepted.
Decision: Accept (Poster)