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-Euclinn 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 eokimally-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 Ómiin(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, -iiffeerrntiillly private algorithms satisfies (E', kō )diffferrett 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 Fv(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 nearly-statinn saarly-ttaionnry 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-hipschit.
We will occasionally refer to the x component of datapoint the feature vector. Note the GLL definition implies that f(,, 2) is (Tng RR-LLsihssss 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) (l (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,a. 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.o, 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 (x R) be Lpplhit and R-bounded GL.. with respect to ||2- Let B /nLo/ R, R alog Then Phased-SGD -GD run with oracle O3.0. R and dataset E 2n satisfies (e, 8) differential privacy and
LaRk
has running time On n log n). Further, if Dr the output of Phased-SGri has expected excess
population risk O (LORD
(flog(1/8) 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-iteetter 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,: 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 1r,)) (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, G 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)ur 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 2, 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
=0 - (DLLo+ L)D)2/3
(n))
d /// log' 1/5 (1/6) log (m)
))
E Gapp,, (w) (w)l
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/8) (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, 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 - (ooe-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, (w))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 (,2pD)
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,)) 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": "yEIKjD5WS7Q", "reviewer": "Reviewer_c6Mx", "summary": "The paper studies three different (slightly related) problems in private optimization: 1. convex private optimization for non-smooth functions, 2. non-convex smooth private optimization, and 3. non-convex non-smooth private optimization. The authors study each of these settings separately, developing different algorithms for each that has certain advantages. The nature of improvement is different in each setting: in the first, the author claim to improve runtime (achieving linear runtime) while maintaining statistical utility, in the second, (for ell_2 geometry) the authors achieve worse rates while getting better runtime, and in the third setting the authors consider the setting of weakly-convex non-smooth functions (which I think was not studied before in the privacy literature) and provide private algorithms with certain convergence guarantees.", "questions": "", "limitations": "", "rating": 4, "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": "I think the results are mostly incremental, based on standard techniques with limited novelty (see below). Moreover, the different problems (settings) in the paper are only slightly related, making the story of the paper less coherent: basically a list of different results that the author prove in different settings. Overall, I don't think the paper has sufficient novelty and new results for acceptance.\n\n\n1. Contribution for non-smooth GLL: while it is true that existing algorithms from [BFTT19, FKT20] take super-linear time for general non-smooth convex functions, the main bottleneck there is smoothening general functions which takes linear time. However, for the setting of GLL that the authors consider, it is immediate to see that existing algorithms give nearly linear time algorithms as smoothening GLLs (or finding the gradient of Moreau envelope) is quite simple as it is basically a 1-dimensional problem. So this result is basically a direct corollary of previous work.\n\n2. Comments on smooth non-convex setting:\n     \n    2.1 The results for this section are based on private implementation of variance-reduced Frank-Wolfe algorithm similarly to the \n    existing private algorithm for the convex setting [AFKT21, BGN21]. The algorithm in this paper doesn't use privacy amplification by \n    sub-sampling (as done in [AFKT21]) hence suggesting their algorithm may not be optimal. \n\n    2.2 The author conjecture (line 78) that their algorithm has tight bounds for the ell_1 setting for linear time algorithms. Is there \n    any evidence for this prediction? Following my previous comment (2.1), I think it may be possible to improve the rates using better \n    privacy accounting as done in [AFKT21].\n\n    2.3 Overall the authors overuse the term: \"we provide the first algorithm for ...\".  One such example is line 76 where the authors \n    say \"we provide the first linear time private algorithms\". There are two problems here. First, this sentence doesn't say anything \n    about the utility of the algorithm and so is not very informative. Secondly, the linear-time algorithm doesn't give optimal bounds \n    as [ZCH+20]. While the algorithm of [ZCH+20] takes n^2/\\sqrt{d} time, we can run it for linear number of steps if we require a \n    linear time algorithm. The authors should compare their bound to the bound obtained by linear-time version of [ZCH+20].\n\n\n3. Non-smooth weakly-convex: the authors should try to explain the strength of the bounds achieved in this section. Currently these are worse than the smooth setting which suggest they may not be optimal as the bounds are usually similar in ell_2 case for both smooth and non-smooth convex case. Moreover, the algorithm is a simple application of existing techniques. \n\n\nMore comments:\n\n1. I think it would be useful to add the dependence on epsilon in the bounds of the abstract as currently these are stated only for constant epsilon and makes it slightly harder to understand the privacy cost.\n\n2. The term GLM (generalized linear models) is more common than GLL.\n\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-4 hours"}, "extra_text": {}}, {"review_id": "cqfyxtpA7J5", "reviewer": "Reviewer_MuL7", "summary": "The paper considers differential private stochastic optimization in a number of convex and non-convex settings. Their contributions are as follows:\n\n1. Faster (nearly linear time) algorithm for $\\ell_2$ non-smooth convex generalized linear losses (GLLs).\n\n2. Algorithm with smaller error (nearly dimension independent) in $\\ell_1$ non-smooth convex GLLs.\n\n3. New algorithms for smooth non-convex and non-smooth weakly convex stochastic optimization in non-Euclidean ($\\ell_p$) settings.", "questions": "", "limitations": "", "rating": 8, "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": "1. The paper makes many novel and important contributions to the field of differentially private stochastic optimization. Importantly, as mentioned in the paper, many results in non-Euclidean non-convex settings are novel even without privacy constraints. \n\n2. The writing and presentation is very good and to the point. Also, the authors try to give the necessary background (in the Appendix) and explain many subtleties as required.\n\n3. The first result is a nearly-linear time algorithm for non-smooth GLLs. This contributes to a recent line of work which try to devise fast algorithms for DP-SCO. This result solves a special case of the non-smooth convex landscape. I think this result has an interesting consequence: *most* known high-dimensional oracle complexity lower bound instances in optimization are GLLs. So this result tells us that if it is indeed the case that non-smooth DP-SCO is harder than SCO, then we need to look at *new* hard instances.\n\n4. The smooth non-convex setting considers a polyhedral constrained setup even in standard $\\ell_2$ setting. I think that it is more natural/standard in literature to consider an $\\ell_2$ ball (or a simple convex set with an easy oracle-access projection). I wonder why did the authors not consider the later? Also, why not consider the unconstrained setup, which would also enable comparison with some of the previous work?\n\n5. On a related note, the non-smooth weakly convex part is not in the polyhedral constraint setting. So, do we need to access to a projection oracle for the claimed guarantees in Theorem 16? If yes, then I could not find it mentioned in this section. If no, then why is it so?\n\n6. **Coherence**: Since the authors make many contributions, one downside is that parts of the paper feel disconnected from each other -- it feels like a collection of results the authors were able to obtain in various settings. For example: GLLs part of the paper has little to do with the non-convex setting (in terms of goal/techniques). This, lots of settings and results, also led to authors' being able to put only one algorithm description (in full, as a pseudo-code) in the main paper, and the rest is deferred to the appendix.\n \n7. **Tightness of rates**: The authors only provide upper bounds for the settings they consider. Is there a way (perhaps from previous works?) to assess how sharp are the attained rates?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "R9ZA0yjyije", "reviewer": "Reviewer_Brcd", "summary": "This work studies differentially private stochastic optimization and proposes several new algorithms for convex non-smooth generalized linear losses (GLL) / general non-convex smooth objectives / weakly convex non-smooth objectives equipped with Euclidean / non-Euclidean geometry. ", "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 work proposes several new algorithms that outperform the existing methods in differentially private stochastic optimization. The authors leverage techniques such as Moreau envelop smoothing for GLL and variance-reduced stochastic Frank-Wolfe to build several linear-time algorithms in the DP setting. The authors also make the first attempt to devise algorithms for weakly convex non-smooth objectives in the DP setting. The contributions are significant and the authors are rather careful in presenting the theoretical results, which is highly appreciated. The paper is well-written but with a lot of proposed algorithms and technical details deferred to the appendix, the results remain hard to parse. Perhaps it suggests that a conference with a small page limit is not the best venue?", "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": "BsHBJE1Rve", "reviewer": "Reviewer_TpjV", "summary": "This paper studied the problem of differentially private stochastic optimization. The authors establish new results for the convex generalized linear model and new algorithms for nonconvex optimization. The main contribution of the current paper is the faster algorithms and stronger results for solving the nonsmooth DP-SCO in the case of generalized linear loss.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the new algorithms are interesting and the utility and convergence results seem to be strong. However, my major concerns are about the algorithms and results in nonconvex setting, and I summarize it as follows:\n1. It is unclear the novelty of the proposed Private Frank-Wolfe algorithm. It seems to be a straightforward application of the variance reduced stochastic Frank-Wolfe algorithm to the private setting. The authors should clarify the novelty.\n2. What are the main challenges for analyzing your proposed Private Frank-Wolfe algorithm? This could help readers understand the contributions of the paper.\n3. The proposed Private Frank-Wolfe algorithm requires a very large batch at each iteration, suggesting that the proposed algorithm will have very bad scalability.\n4. The utility guarantee of the proposed algorithm is worse than existing work. For example, in the l_2 setting, the utility guarantee is worse than the result in [ZCH+20].\n5. There are no experiments to validate the effectiveness of the proposed methods in the current paper.", "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": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper generated a lot of discussion among reviewers. The authors would be advised to improve the clarity of the discussion in order to better integrate their diverse-seeming results into one story. Please also include the improvements suggested in discussions between the reviewers and the authors.

Decision: Accept (Poster)