Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks
Authors: Daogao Liu
Arun Ganesh
Sewoong Oh
Abhradeep Guha Thakurta
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Differential Privacy
Non-convex optimization
Stationary points
Exponential Mechanism

Abstract: We reconsider the challenge of non-convex optimization under differential privacy constraint. Building upon the previous variance-reduced algorithm SpiderBoost, we propose a novel framework that employs two types of gradient oracles: one that estimates the gradient at a single point and a more cost-effective option that calculates the gradient difference between two points. Our framework can ensure continuous accuracy of gradient estimations and subsequently enhances the rates of identifying second-order stationary points.
Additionally, we consider a more challenging task by attempting to locate the global minima of a non-convex objective via the exponential mechanism without almost any assumptions. Our preliminary results suggest that the regularized exponential mechanism can effectively emulate previous empirical and population risk bounds, negating the need for smoothness assumptions for algorithms with polynomial running time. Furthermore, with running time factors excluded, the exponential mechanism demonstrates promising population risk bound performance, and we provide a nearly matching lower bound.

Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks
Arun Ganesh Google Research arunganesh@google.co com
Daogao Liu University of Washington" dgliu0uw. edu
Sewoong Oh
Abhradeep Thakurta Google DeepMind athakurta@googles com
University of Washington and Google Research sewoongecs. washington. edu
Abstract
We reconsider the challenge of non-convex optimization under differential privacy constraint. Building upon the previous variance-reduced algorithm SpiderBoost, we propose a novel framework that employs two types of gradient oracles: one that estimates the gradient at single point and more cost-effective option that calculates the gradient difference between two points. Our framework can ensure continuous accuracy of gradient estimations and subsequently enhances the rates of identifying second-order stationary points. Additionally, we consider more challenging task by attempting to locate the global minima of non- convex objective via the exponential mechanism without almost any assumptions. Our preliminary results suggest that the regularized exponential mechanism effectively emulate previous empirical and population risk bounds, negating the need for smoothness assumptions for algorithms with polynomial running time. Furthermore, with running time factors excluded, the exponential mechanism demonstrates promising population risk bound performance, and provide nearly matching lower bound.
Introduction
Differential privacy 19 is standard privacy guarantee for training machine learning models. Given a randomized algorithm A p + R, where P is data domain and is a range of outputs, we say A is (e, 8) diffferrenyll private (DP) for some D,D' E pa that differ in at most one element and any R C R, the distribution the outcome of the algorithm, c.g., pair of models trained the respective datasets, are similar:
and [0, 1] if for any neighboring datasets
Pr (NAA(()
[x R] < e
Pr g~A((D)
[x
R] 6
Smaller and 8 imply the distributions closer; hence, adversary accessing the trained model cannot tell with high confidence whether an example a was the training dateset. Given this measure of privacy, consider the problem of optimizing non-convex loss while ensuring desired level of privacy. In particular, suppose we are given a dataset = [21,..., Zn drawn i.i.d. from underlying distribution P. Each loss function f(;;))
+ R is G-Lipschitz over the convex set Rdd of diameter D. Let the population risk function be Fr(x)) = Ez-pl [f;; =)] and the empirical risk function Fp (x) == E. (a;; z). We also denote (x) = 3 E.es I (2x; 2) for S C D.
Most of this work was done while the author was intern Google.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our focus is in minimizing non-convex (empirical and population) risk functions, which may have multiple local minima. Since finding the global optimum of non-convex function can be challenging. an alternative goal in the field is to find stationary points: A first-order stationary point is a point with a small gradient of the function, and a second-order stationary point a first-order stationary point where additionally the function has positive or nearly positive semi-definite Hessian. As first order stationary points can be saddle points or even a local maximum, we focus on the problem of finding second order stationary point, i.e., a local minimum, privately. Existing works in finding approximate SOSP privately only give guarantees for the empirical function FD. We improve upon the state- of-the-art result for empirical risk minimization and give the first guarantee for the population function Fp. This requires standard assumptions on bounded Lipschitzness, smoothness, and Hessian Lipschitzness, which we make precise in Section 2 and in Assumption 3.1
Compared to finding local minimum, finding global minimum can be extremely challenging. We also present two methods, polynomial and exponential time, that outperform existing guarantees measured in excess risks for respective computational complexities. Our primary results are succinctly summarized in Table
Related Work. We propose novel and simple framework based on SpiderBoost 152] and its private version 2 that achieves the current best rate for finding the first order stationary point privately. We discuss the primary difference between
framework and theirs, that is their algorithms only promise small gradient estimation errors on average, but our framework can ensure small estimation errors consistently throughout all the iterations, and the motivation behind this briefly.
In SGD and its variants, the typical approach involves obtaining an estimation A, of the gradient [aax)). In the stochastic variance-reduced algorithm SpiderBoost [52 2 it queries the gradient O O1 (arx) Rs (=(x;) directly every q steps with some oracle O,, and for the other q - steps within each period, it queries the gradient difference between two steps, that is (2 11 se f((z)) (x and maintain A, = A + (2 Zz-1). The contrast between these two types of oracles can be perceived as On being more accurate but also more costly, in terms of computation or privacy budget, although our framework does not strictly necessitate this assumption.
As SpiderBoost queries O1 every 9 steps, the error on the estimation may accumulate and || fx II can become large. Despite this, as demonstrated in (2). these estimations can, on average, suffice to find a private FOSP. However, such large deviations pose a challenge when scrutinizing behavior near a saddle point. For instance, when the current point is saddle point, but the current estimation is unsatisfactory, it becomes uncertain whether the algorithm can escape the saddle point. It could be argued that average good estimations could achieve a SOSP, but to the best of our knowledge, there is no existing result addressing this concern.
plausible solution to this challenge to maintain high-quality gradient estimations throughout all iterations, a feat accomplished by our framework. We believe this feature holds promise for improving the outcomes of various other optimization problems, thus enhancing the overall appeal and significance of our work.
1.1 Main Results
SOSP.
One of our main contributions is refined optimization framework (Algorithm [ predi- cated on the variance-reduced SpiderBoost [52], which guarantees consistently accurate gradient estimations. By integrating this framework with private gradient oracles, we achieve improved error rates for privately identifying SOSP of both empirical and population risks.
Advances in private non-convex optimization have focused on finding a first-order stationary point (FOSP), whose performance is measured in (i) the norm of the empirical gradient at the solution æ, i... // (z)]l. and (ii) the norm of the population gradient, i.e., (z)]l. We survey the recent progress in the appendix in detail.
Definition 1.1 (First-order stationary point). We say x E Id is a First-Order Stationary Point (FOSP)
of Td R iff Vz(z) 0. is an a-FOSP of g. V
Since FOSP can be a saddle point or local maxima, finding second-order stationary point is desired. Exact second-order stationary points can be extremely challenging to find 25].. Instead, progress is commonly measured in terms of how well the solution approximates an SOSP.

---

a-SOSP
Excess population risk poly-time
empirical
population
exp-time
SOTA
min
N/A
N/A
n
77
log
Ours
dt
d 8 (og(m))
n n
nL
ME
LB
vd
ne
TME
718
ns
Table I: SOTA refers to the best previously known bounds on a for a-SOSP by [46 the excess population risk by [46). We introduce algorithm that finds an a-SOSP (columns 2-3) with an improved rate. We show exponential mechanism can minimize the excess risk in polynomial time and exponential time, respectively (columns 4 and 5). requires extra assumption on bounded smoothness. The lower bounds for SOSP are from 22. and the lower bound on excess population risk
48 and on
from Theorem 5.11 We omit logarithmic factors n and d except the upper bounds for excess population risk with polynomial time.
Definition 1.2 (Second-order stationary point, (.). We say a point x Rd is a Second-Orde
Stationary Point (SOSP) of twice differentiable function g R + R iff ( = and
V (²g(2) = 0. We say x E IR. is an a-SOSP for p-Hessian panschitz,fucctii 9, if [g(x)]l s g(()) = -ppll
On the empirical risk FD, the SOTA on privately finding a-SOSP is by 46 which achieves a ((min((Vd/n)
(d/n))//]) In Theorem 4.2 we show that applying the proposed Algorithm achieves rate bounded by a = (((vd/n)22)) 22/5), which improves over the SOTA in all regime There remains a factor ( (vd/n)-
gap to known lower bound of a = 9 22vd/m) that holds even if finding only an a-FOSP [2] On the population risk Pp, applying Algorithm [ with appropriate private gradient oracles is the first private algorithm to guarantee finding an a-SOSP with = Ó(n (vd/n) n) m))/7) in Theorem 4.6 There is gap to a known lower bound of a = 2211 Vi vd/ne) that holds even if finding only a-FOSP 2]
Minimizing Excess Risk. In addition to the optimization framework, we present sampling-based algorithms designed to identify private solution zariv E _d that minimizes both the excess empirical risk: E[Fb (wPriv) ]] -mingex (x)), and the excess population risk: E E[Fp(xPrit)] -min Fp Here, the expectation is over the randomness of the solution zariv and the drawing of the training date over P. Our method is different from [46]. which Gradient Langevin Dynamics and achieves in polynomial time a bound of (d /lg log(1/5)/(C (1E l)) for both excess empirical and population risks with need for the smoothness assumption. In Table we omit excess empirical risk, as the bounds align with those of the population risk. We introduce a sampling-ban -based algorithm from the exponential mechanism, which runs in polynomial time and achieves excess empirical and population risks bounded by (dd (Tg/Tog(() (e (ng(n))) with improved dependence on (Theorem 5.6). Crucially, it achieves these results without the need for the smoothness assumption required by A6
In the case of permitting an exponential running time, (23 demonstrated O(d/ (ed)))))) upper bound for non-convex excess empirical risks alongside a nearly matching lower bound. However, establishing tight bound for the excess population risk remained an unresolved problem. We address this open
question by providing nearly matching upper and lower bounds of (dd(Een) + /d/n) for the excess population risk (Theorem 5.8).
1.2 Our Techniques
Stationary Points. In our framework, we deviate from the traditional approach of querying O once every 9 steps. Instead, we introduce novel but simple method of monitoring the total drift we make, that is drift, Ei.n. || -; I1 where represents the last timestamp when employed O,. As we are considering smooth functions, the maximum error to estimate (f(xz) f((x-1))
We want o(1) and hence assume $ n
3

---

is proportional to | - 22-1 If the value drift, is small, we know the current estimation should still be good enough, eliminating the need for an expensive fresh estimation from O, Conversely, when drift,, is large, the gradient estimation enror may be substantial, necessitating query to O1 and thus obtaining A = (z+). To effectively manage the total cost, it crucial to set an appropriate threshold to decide when the drift is significant. A smaller threshold would ensure more accurate estimations but might incur higher costs due to more frequent queries to OI
Our aim is to bound the total occurrences of the event that drift, is large, which leads to querying O crucial observation is that, if drift, increases rapidly, then the gradient norms are large and hence function values decrease quickly, which we know does not happen frequently under the standard assumption that the function is bounded.
In our framework, we assume (zx) is an unbiased estimation of Vf()), and 01(x) V/(r) is Norn-SubGaussian (Definition 2.2), and similarly O2(2, y) is unbiased estimation of f V whose error is also Norm-SubCiausiaa In the empirical case, we can simply add Gaussian noises with appropriately chosen variances to the gradients of the empirical function V for simplicity, and one can choose a smaller batch size to reduce the computational complexity. In the population case, we draw samples from the dataset without replacement avoid dependence issues, and add the Gaussian noises to the sampled gradients. Hence we only need the gradient oracle complexity to be linear in the size of dataset for the population case.
Minimizing Excess Risk. Our polynomial time approach harnesses the power of the Log-Sobolev Inequality (LSI) and the classic Stroock perturbation lemma. The previous work of [39] shows that if the density exp - B. (x) r(z)) satisfies the LSI for some regularizer r, then sampling a model
x from this density is DP with an appropriate (e, 8). If r is a strongly convex function, then the
density proportional to exp(-r) satisfies LSI with constant 1 I/1,, and exp(- exp(-3Fo(z) rxx)) satisfies LSI with constant exp(max,.y) [D( - F FD(y))/ p by the Stroock perturbation lemma. Our bound on the empirical risk follows from choosing the appropriate inverse temperature | and regularizer to satisfy (e. 6).DP. The final bound on the population risk also follows from LSI, which bounds the stability of the sample drawn from the respective distribution.
When running time is not a priority, we employ an exponential mechanism over a discretization of K. to establish the upper bound. The empirical risk bound derives from (9) and leverage the concentration of sums of bounded random variables to bound the maximum difference over the discretizations between the empirical and population risk. We show this is nearly tight by reductions from selection to non-convex Lipschitz optimization of (23
1.3 Organization
In Section 2 we present necessary definitions and backgrounds for our work. In Section 3 we construct the optimization framework, with guarantees on finding the SOSP with two different kinds of SubGaussian gradient oracles. It's crucial to note that this framework focuses solely on optimization and does not pertain to privacy. Section 4 eexplores the pursuits of finding the SOSP privately by constructing private SubGaussian gradient oracles and seamlessly integrating them into the existing framework. We bound the private excess bounds in Section[]] For other preliminaries, all omitted proofs and some further discussions on related work can be found in the Appendix.
2 Preliminaries
Throughout the paper, if not stated explicitly, the norm || means the &g norm.
Definition 2.1 (Lipschitz, Smoothness and Hessian Lipschitz). Given a function I K. R. we say J is G-Lipschitz, for all x1 E K. [s()) - [(zg) S GlIla1 - x2ll, we say function is M Msmmotth, for all 21, I2 E K.. [[V)(z)) - (f(22)) < M| - 22l1. and we say the function f is p-Hessian Lipschitz, for all æ1, 22 E K, we have 2 f(z1) v² I p||æ1 -22ll-
Definition 2.2 (SubGaussian, and Norm-SubGaussian, A random vector Rd is SubGaussian (SG(C) if there exists a positive constant Ç such that E Ev(v.zEax) < elll1l Vo E Rd. x Rd
is Norm-SubGaussian (nSG(()) if there exists ( such that Pr[]|= - Exl| 2 4 < 2e 22 VI E
Fact 2.3. For Gaussian 0 ~ (O, x² La)) 0 is SG and noG(

---

R be random vectors, and for each [k), z; Fi-1 zero-mean (SG((;) where F, the corresponding filtration. Then there exists absolute constant such that for any 5 > O, with probability at least
Lemma 2.4 (Hoeffding type inequality for norm subGaussian, [30]. Let I1,
1 1- Σ == mill S V St log(2d/w), which means Ei=1 is nSG(y clog(d) Ei=
3 Convergence to Stationary Points: Framework
We present the optimization framework for finding SOSP in this section. It's important to emphasize that this framework is dedicated exclusively to optimization concern,, with privacy considerations being outside of its purview. The results about SOSP throughout the paper follows the assumptions of 46].
Assumption 3.1. Any function drawn from P is G-Liscchitz, p-Hessian Lipschitz, and M smooth, almost surely, and the risk is upper bounded by B.
As discussed before, we define two different kinds of gradient oracles, one for estimating the gradient at one point and the other for estimating the gradient difference at two points.
Definition 3.2 (SubGaussian gradient oracles). For G-Lipchhitz and M M-smooth function F: (1) We say O2 a first kind of Ç1 nausssanaaussian Gradient oracle if given x E RRd, Oxx) satisfies E (a:) = (x)) and O (1(x) V FF()) ) is nSG(G)).
(2) We say Oz is second kind of Ç2 norm-subGaussian stochastic Gradient oracle if given æ, E Rd O2(x, u) satisfies that E 12 y) FF(x) (y)) and O2(r, (VF(x) FF(()) is
nSG((2ll yll).
Note that we should assume M 2 vpa make finding second-order stationary point strictly more challenging than finding first-order stationary point. We use smin(.) to denote the smallest eigenvalue of matrix.
Algorithm 1 Stochastic Spider
Input: Objective function F, Gradient Oracle O1, O2 with SubGaussian parameters Çi and (2. parameters of objective function B, M, G, parameter K, failure probability w
2: Set / 4C+) log( BMd pw),, r
M log( PT2
Voy
3: Set 1 = 1 0,7 BM (og dMB p7M
)/7²
4: Set drift, K, frozen 1, -
5: while t -
do
6: if V
log /BMd/ pw) A frozen,-1 < 0 then frozen, = r, drift, =0
7:
=,=0, + gr. where gr NO ((a) else if drift, - 2 then
8:
9:
V. 01 (z,), drifl, = O, [rozen, frozen;-11
11:
else
A. O2 11-1), V. V-- A. frozen; frozen--1-1
13:
end if
F++1 2t ( driffeet drift, + V. t=t+1
15:
end while
Return: ( FT}
Inspired by 2 who adapted the SpiderBoost algorithm for finding private FOSPs, we give frame- work based on the SpiderBoost in Algorithm properties we establish in this section: (i) Ve remains consistently close the true gradient F(x))) with high probability; (ii) the algorithm is capable of escaping the saddle point with high probability. and (fii) large drift implies significant decrease in the function value, which enables us limit the number of queries to the more accurate but costlier first kind of gradient oracle O₁.
[ Our analysis of Algorithm [ hinges on three key
5

---

Lemma 3.3. For any 0 < t T and letting Ti S be the largest integer such that drift,, is set to be with probability at least w/T, for some universal constant C' we have
VV - VF(x:)]1 & (42
Σ 1
||= - x111 +42)) C. log(Td/w).
(I)
Hence with probability at least 1 W, know for each T, II VF(2;))l2 S 22/16, where y² = 16C + 4C3) -lo((Td///) and k is parameter we can choose in the algorithm.
As shown in Lemma 3.3 the error on the gradient estimation for each step bounded with high probability. Then by adding the Gaussian noise in Line 8 we can show the algorithm can escape the saddle point efficiently based on previous results.
Lemma 3.4 (Essentially from [46]). Under Assumption 3.7 run SGD iterations I++1 It 1/M. Suppose 2o is a saddle point satisfying [| S a and
V with step size smin( (2F(zz)) I VV. a (dBg pw). If = VF(xo) + C1 + 62 where ||<il| S
C2 No0, d'lg(d/w))
7 Ia). and IV. (x:)l S y for all E [T]. with probability at least
1 - w log(1 (w) one has F(xr) - F(x0) S - 2 Volog
2/22
where r
M log( poa
VPy
We discuss this lemma in the Appendix in more details. The next lemma is standard, showing how large the function values can decrease in each step.
Lemma 3.5. By setting 1j 1/M, we have F(I++1) S + V/ Vell - V.ll. Moreover, with probability at least w. for each 1 S T such that [VF(( 2 7, we have
F(I++1) - F(x)) - - v 112
/6/
With the algorithm designed to control the drift term, the guarantee for Stochastic Spider find the second order stationary point is stated below:
Lemma 3.6. Suppose O and O2 are Çi and (2 norm-subGaussian respectively. If one sets
0(1) (G 4G²) log((d/w), with probability at least 1 w. at least one point in the output set {z1,- .TT of Algorithm is a-SOSP, where
log( d/w log'(
BMd
a= (BMd/ - (GG (53x+ +
4G7) /
23 + G
pa (
G
As mentioned before, bound the total time we query the oracle of the first kind.
bound the number of occurrences where the drift gets large and hence
Lemma 3.7. Under the event that V F(x)))l I f/ all t e [T] and our parameter settings, letting K {t E [T] drift, k} be the set of iterations where the drift is large, know |K| O By 2 /k) O Bn log" (dMB) )/k).
4 Private SOSP
We adopt the framework before and get our main results on finding SOSP privately by constructing private gradient oracles in this section. Finding SOSP for empirical risk function Fp and for population risk function Fp are discussed in Subsection 4.1 and Subsection 4.2 respectively.
4.1 Convergence to the SOSP of the Empirical Risk
We use Stochastic Spider improve the convergence to a-SOSP of the empirical risk, and aim at getting a Odd)/3 /3 We use the bull-batch size for simplicity, and use the gradient oracles
01(x) FFD(a) 91, and Oz(x, v) (F)(x)
VDD(y) + 92,
where 91 (N(0 and g2 ~ N(0, oB|| Ta are added to ensure privacy by Gaussian mechanism (in Appendix).

---

Before stating the formal results, note that by Lemma 3.6 the framework can only guarantee the existence of an a-SOSP in the outputted set. order to find the SOSP privately from the set, we algorithm, whose pseudo-code can be found in Algorithm a slight modification of the well-known in [20], and we get the following guarantee immediately.
adopt the well-known Above'Threshen
the Appendix. Algorithm
2
algorithm
Lemma 4.1. Algorithm 2 is (e, O)-DP. Given the point set f"1,"-","" and S of size n as the input, (i) it outputs any point 24, then with probability at least 1 w. we know
32 1ogg((2T/)) and (F -Vpa- 32 (2g(22//))))))
[VF((x)) sa+
nE
nE
(it) if there exists a a-SOSP point x E (aihe(T) then with probability at least w, Algorithm will output one point.
Choosing the appropriate noise scales for the Gaussian added in Equation 2 and running Algorithm can get private set of points which contains at least one good SOSP. Then we can run Algorithm to find the good SOSP in the set privately. The formal guarantee is stated below:
Theorem 4.2 (Empirical). For ip O()), use Equation as gradient oracles with K Gv G (oM/B//
G4/3 G4/3
2/3
02 = M (oM////B
Rumning Algo-
M513
nVP
rithm outputring the set (eet(zj (astiemm the total time to query O1 is bounded by O(Bn) log" (
otherwise outputting a T arbitrary points is (p/2))xCDPP. With probability least w, at least one point the output set is a1 R1-SO of FD with
2/3
VdBGM n//
nBMMd pw
a1= =1=00
log
Moreover, if run Algorithm with inputs { D, B, M, G,p,a ay and Vø. with probability at least W. we can get an 02-SOSP of FD with a2 = O (a1 Glog(n/Gw)
n/8 + MlggdBGMM/ pw)
yoi) The whole procedure is p-zCDP.
For more generality, we state the above theorem in terms of zCDP. 4-zCDP implies (y + 2 () which gives the bounds in Table (see Appendix for details).
Remark 4.3. It's s worth noting that the cost of gradient computation can be reduced by utilizing smaller batch sizes. However, our work does not focus on optimizing this aspect.
4.2 Convergence to the SOSP of the Population Risk
This subsection aims at getting an a-SOSP for Fp (the population function). Differing from the stochastic oracles used for empirical function Fp, we do not use full batch in the oracle. As an alternative, we draw fresh samples from D without replacement with a smaller batch size:
1 Σ 2f(1;2) + 91, and Oz(x, bi ZES1
1 Σ (V)(az))
(1)))
f - 92,
(3)
b2 ZES2
where S₁ and S2 are sets of size of by and by respectively drawn from D without replacement, gi (0, la) and 92 ~ NO oā y Ia) are added for privacy guarantee. These gradient oracles satisfy the following.
Claim 4.4. The gradient oracles O and O2 constructed in Equation (3) are a first kind of O(Ly
LV log + /do1) norm-subGaussian gradient oracle and second kind of O M Mylloga + vdoz) V
Vhz
Sonn-saaaanssian gradient oracle respectively.
Recall that the empirical case, we use Algorithm to choose the SOSP for PD. But in population case, we need to find SOSP for Fr, and what we have are samples from P. We need the following technical results to help us find the SOSP from the set, which follows from Hoeffding inequality for norn-subGaussians (Lemma 2.4 and Matrix Bernstein incquality (in the Appendix).
7

---

Lemma 4.5. Fix a point z E R.. Given a set S of m samples drawn i...d from the distribution P. then we know with probability least 1 w. we have
G Glog(d/w) v
ro(r)) S 0 M log(d/w),
- <0(
vm
By choosing the appropriate noise scales dj and 02 to ensure the privacy guarantee, we can bound the population bound similar the empirical bound with these tools.
Theorem 4.6 (Population). Divide the dataset D into two disjoint datasets Dı and D2 of size [n/2] and [n/2] respectively. Set bj
n.K. b2 = naj
G bive:
M and k. = bave
Byj max( G4/B g²/3 log2/9 d 1/3 GB2/2 /6/7 ( in Equation 3 and use them as gradient or- M
BM
01
215/3
acles. Running Algorithm 7 with D1. and outputting the set {a hei if the total time query O₁ is bounded by OBBy) log ( d
/m), otherwise outputting set of arbitrary points, is (2/2))=ZCPP, and with probability at least w. at least one point in the output is a1-SOSP of Fp with
prw
Vd )3/7) logo (nBMd/
a =1=0((BGMM log d/1/3 n2/3 + -G"/TB3/TM31
nVP
Moreover, if we Algorithm with inputs {Zihert, D2, B, M. G.p.a,
vp with probability at least 1 - W, Algorithm 2 can output an a2-SOSP of Fp with ag = M MoggndBGMMppa pw) /ai + G( llogn/GGar loz(d/w)) The whole procedure G-ZCDP. O 01 + Vaminin (P.1
n/p
5 Bounding the Private Excess Risk
In this section, we shift our focus from "second-order" guarantees to "zeroth-order" guarantees, and consider the problem of getting good private risk bounds without convexity.
5.1 Polynomial Time Approach
If we want the algorithm to be efficient and implementable in polynomial time, to our knowledge the only known bound is O( Allo((1/0) in [46] for smooth functions. [46) used Gradient Langevin Dynamics, popular variant of SGD to solve this problem, and prove the privacy by advanced composition [31] We generalize the exponential mechanism the non-convex case and implement without smoothness assumption.
e2 log
First recall the Log-Sobolev inequality: We say probability distribution satisfies LSI with constant CLST if for all f RRd + R, [ log [²] - [=]") log E=[ S 2C1.sT E., ||V fll A well-known result ((40) says if f is j-strongly convex, then the distribution proportional to exp(-f) satisfies LSI with constant 1 1/p. Recall the results from previous results (39] about LSI and DP:
Theorem 5.1 ((39). ). Sampling from exp(-6F(x: D) - r(x)) for some public regularizer is (s, DP, where E S 22 VCLsiv + log(1/5), and CLsI is the worst LSI constant.
We can apply the classic perturbation lemma to get the new LSI constant in the non-convex case. Suppose we add a regularizer ~ ||x]| and try to sample from exp(-3((F( D)+ + -
Lemma 5.2 (Stroock perturbation). Suppose æt satisfies LSI with constant CLSI(T).. If < < e (T)).
dx' da < C, then CLsI(=') < E
Lemma 5.3 is more general version of Theorem 3.4 in 23 and can be used to bound the empirical risk.
Lemma 5.3. Let (xx) x exp(-3(Fp(x)) + l1)). Then for 3GD > d, we know
E (F)(z) + ! || min Fx(x)) + ||
/
( < 3
log(3GD/d)
2
=EE
2
We now turn to bound the generalization error, and use the notion of uniform stability:
8

---

Lemma 5.4 (Stability and Generalization [0]). Given dataset D = [sitre(n) drawn i.i.d. from some underlying distribution P. and given any algorithm A, suppose we randomly replace sample in 'D by an independent fresh one 8' from P and get the neighoring dataset 'D', then EDD.A (A(()) - Fo(A(D))) ED, (llD:,,(((((()ss)) [(A(D);; &')], where A(D) is the out- put of A with imput D.
As each function f(; ) is G-Lipschitz, suffices to bound the W2 distance of A(D) and A(D"). If A is sampling from the exponential mechanism, letting TD exp(- (z) + ||x+1?)) )) and TD' exp(-3(FFx> (1:) + ~ {|>=|l²)), it suffices bound the W2 distance between uD and mpr The following lemma can bound the generalization risk of the exponential mechanism under LSI:
Lemma 5,5 (Generalization error bound), Let TD & exp(-3(Fa + - Then we have G² exp( exp(3GD)
Ep [Fp - Fb(=)] <
We get the following results:
Theorem 5.6 (Risk bound). We are given E, E (0, Sampling from { (1111) 6 log(nd))
with O GD (lo0((o(1/)))) ).H DAS (P. The empirical risk and population risk are
bounded by OGGD d-log / llg((d))
Implementation There multiple existing algorithms that can sample efficiently from density with LSI, under mild assumptions. For example, when the functions are smooth or weakly smooth, one can turn to the Langevin Monte Carlo [16). and [36). The algorithm in [46] also requires mild smoothness assumptions. We discuss the implementation of non-smooth functions in bit more details, which is more challenging.
We can adopt the rejection sampler in (26], which is based on the alternating sampling algorithm in [35] Both (5 and (26) are written in the language of log-concave and strongly log-concave densities, but their results hold as long as L.II holds. By combining them together, we can get the following risk bounds. The details of the implementation can be found in Appendix D.3
Theorem 5.7 (Implementation, risk bound). For e 8 E (0, 1/2), there is an (E. 26) efficient
sampler that can achieve the empirical and population risks O dllog log(n) / /iog(1/8) Moreover, 5 <log(nd)
in expectation, the sampler takes Ô nne' log" (d) / (og((16)/((D))) function values query and some Gaussian random variables restricted to the convex set KC in total.
5.2 Exponential Time Approach
CD In it is shown that sampling from exp(- on Fo(x)) is e-DP, and nearly tight empirical risk
bound of Ō DGd) is achieved for convex functions. It is open what is the bound we can get for non-convex DP-SO.
Upper Bound Given exponential time we can use a discrete exponential mechanism as considered in 99. We recap the argument and extend it to DP-SO. The proof is based on simple packing argument, and can be found in the Appendix.
Theorem 5.8. There exists an e-D differentially private algorithu that achieves a population risk o (GD (dlog(en/d)/(en) / (dllo(en/d)/(vi))
Lower Bound Results in 23 imply that the first term of ((Gdd/em) is tight, even if we relax to approximate DP with 8 > 0. A reduction from private selection problem shows the Ö(vd /d/n) generalization term also nearly-tight (Theorem 5.11I. In the selection problem, we have coins, each with an unknown probability p.. Each coin is flipped times such that {æt,, hee(j). each æi i..d. sampled from Bern(p.), and we want to choose a coin i with the smallest p.. The risk of choosing is p. min;- pi..
Theorem 5.9, Any algorithum for the selection problem has excess population risk u2( log

---

This follows from folklore result on the selection problem (see e.g. (5]). We can combine this with the following reduction from selection to non-convex optimization:
Theorem 5.10 (Restatement of results in 23 ). If any (e, 6)-DP algorithm for selection has risk
R(k), where P(k) is function with k as variables, then any (e, 6)DP algorithm for minimizing 1-Lipschitz losses over Ba(0, 1) (the d-dimensional unit ball) has risk R(20(d)).
From this and the aforementioned lower bounds in empirical non-convex optimization we get the following:
Theorem 5.11. For & I 1,8 E 1 any (s, 6)-DP algorithm for minimizing 1- Lipschitz losses over Ba(0, 1) has excess population risk max
6
Discussion
In this paper, we gave improved bounds for finding SOSPs under differential privacy, as well as points with low population risk. We discuss some potential follow-up questions here.
First, there is still a gap between our upper bounds and the lower bounds of (2]. Closing this gap is an interesting question and may lead to novel technical insights about private optimization. To obtain upper bounds for finding SOSP, both our work and the work of [2] uses the oracle of the second kind defined in Definition 3.2] Second, in typical private optimization work, only oracles of the first kind are used. is possible that the oracle of the second kind useful in private optimization problems besides finding stationary points, either in theory or practice. In particular, since this oracle has lower sensitivity. it may allow us to tolerate higher noise level lower privacy budget across multiple iterations. Third, we privatize the SpiderBoost in the work, and there are other versions of variance-reducee algorithms like Spiker and SARAH. It is interesting if our ideas can be used to privatize those algorithms, and compare their practical performance. Lastly, our polynomial-tine ttime excess population risk bounds have a O(1/ log n) dependence on the dataset size, whereas for convex losses standard results have max //. 1/en] dependence. The stronger dependence is achievable under LSI, but the practical settings in which LSI holds without convexity holding seems limited. remains an open question to find practical assumption weaker than convexity that allows to achieve better dependence on
7 Acknowledgement
DG would like to thank Ruoqi Shen and Kevin Tian for several discussions.
10

---

References
[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1195-1199, 2017.
[2] Raman Arora, Raef Bassily, Tomás González, Cristóbal Guzmán, Michael Menart, and Enayat Ullah. Faster rates of convergence to stationary points in differentially private optimization. arXiv preprint (iXi::2206000466 2022.
[3] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in 11 geometry. In International Conference on Machine Learning, pages 393-403, PMLR, 2021.
[4] Hilal Asi, Daniel Asher Nathan Levy, and John Duchi. Adapting function difficulty and growth conditions in private optimization. In Advances in Neural Information Processing Systems, 2021.
[5] Mitali Bafna and Jonathan Ullman. The price of selection in differential privacy. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 151-168. PMLR, 07-10 Jul 2017.
[6] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. arXiv preprint arXiv:2006.069: 2020.
[7] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. Advances in Neural Information Processing Systems, pages 11279-11288. 2019.
[8] Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic opti- mization: New results in convex and non-convex settings. Advances Neural Information Processing Systems, 34:9317 992999 2021.
[9] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proc. of 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pages 464-473, 2014.
[10] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[11] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith, editors, Theory of Cryptography, pages 635-658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.
[12] Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. arXiv preprins arXiv:2301.00457. 2023.
[13] Kamalika Chaudhuri and Claire Monteleoni. srivacy-preserving logistic regression. Advances in newral information processing systems, 21, 2008.
[14] Kamalika Chaudhuri, Claire Monteleoni, and Anand Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 1069 -109,,111,,91100 2011.
[15] Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for proximal algorithm for sampling. In Conference on Learning Theory, pages 2984-3014. PMLR, 2022.
[16] Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of langevin monte carlo from poincare to log-sobolev. In Conference on Learning Theory, pages 1-2. PMLR, 2022.
[17] Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. In Advances Neural Information Processing Systems, 2021.
11

---

[18] Ashok Cutkosky and Francesco Orabona. Momentum based variance reduction in non non-convex sgd. Advances in neural information processing systems, 32, 2019.
[19] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pages 265 284, 2006.
[20] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Rrends in Theoretical Computer Science, 9(3-4):211-00) 2014.
[21] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018
[22] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. In Proc. of the Fiffy-Second ACM Symp. Theory of Computing (STOC'20), 2020.
[23] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay, Langevin diffusion: An almost univer- sal algorithm for private euclidean (convex) optimization. arXiv preprint arX1v:220.001585, 2022.
[24] Changyu Gao and Stephen J Wright. Differentially private optimization for smooth nonconvex erm. arXiv preprint arXiv:2302.04972, 2023.
[25] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. Conference on learning theory, pages 797-842.
PMLR, 2015.
[26] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. In Conference on Learning Theory, pages 1948-1989. PMLR, 2022.
[27] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian. Private convex optimization in general norms. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithmms (SODA), pages
SIAM, 2023.
[28] Roger Iyengar, Joseph P Near. Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), 2019.
[29] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International conference on machine learning, pages 1724-1732. PMLR, 2017.
[30] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736. 2019.
[31] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1376-1385, Lille, France, 07-09 Jul 2015. PMLR.
[32] Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data, In International Conference on Machine Learning, pages 10633-10660. PMLR, 2022.
[33] 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.
[34] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in sub- quadratic steps. Advances in Neural Information Processing Systems, 34, 2021.
[35] Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted gaussian oracle. In Conference on Learning Theory, pages 2993-3050. PMLR, 2021.
12

---

[36] Jiaming Liang and Yongxin Chen. A proximal algorithm for sampling from non-smooth potentials. In 2022 Winter Simulation Conference (WSC), pages 3229-3240. IEEE, 2022.
[37] Songtao Lu, Meisam Razaviyayn, Bo Yang, Kejun Huang, and Mingyi Hong. Finding second- order stationary points efficiently in smooth nonconvex linearly constrained optimization prob- lems. Advances in Neural Information Processing Systems, 33:2811 1-222, 2020.
[38]
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103, IEEE, 2007.
[39] Kentaro Minami, HItomi Arai, Issei Sato, and Hiroshi Nakagawa. Differential privacy without sensitivity. Advances in Neural Information Processing Systems, 29, 2016.
[40] Felix Otto and Cédric Villani. Generalization of inequality by talagrand and links with the logarithmic sobolev inequality. Journal of Functional Analysis, 173(2)336144)) 4000,0,,,0200 2000.
[41] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248. IEEE, 2013.
[42] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pages 2638-2646. PMLR, 2021.
[43] Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly optimal private lasso. Advances in Neural Information Processing Systems, 28, 2015.
[44] Hoang Tran and Ashok Cutkosky. Momentum aggregation for private non-convex erm. In Advances in Neural Information Processing Systems, 2022.
[45] Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230 2015.
[46] Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pages 6526 6535. PMLR, 2019.
[47] 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 Artificial Intelligence, volume 33, pages 1182-1189, 2019.
[48] Di Wang and Jinhui Xu. Escaping saddle points of empirical risk privately and scalably via dp-trust region method. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 90-106. Springer, 2020.
Faster and more general. Advances in Neural Information Processing Systems, 30, 2017. [49] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited:
[50] Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient privacy- preserving stochastic nonconvex optimization. arXiv preprint arXiv: 13659, 2019.
[51] Yongqiang Wang and Tamer Başar. Decentralized nonconvex optimization with guaranteed privacy and accuracy. Automatica, 150: 100858, 2023.
[52] Zhe Wang, Kaiyi Ji. Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, 32, 2019.
[53] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. Advances in neural information processing systems, 31, 2018.
[54] Xiaodong Yang, Huishuai Zhang, Wei Chen, and Tie-Yan Liu. Normalized/clipped sgd with per- turbation for differentially private non-convex optimization. arXiv preprint arXiv:2206. / 13033, 2022.
13

---

[55] Qiuchen Zhang, Jing Ma, Jian Lou, and Li Xiong. Private stochastic non-convex optimization with improved utility rates, In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021.
[56] Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee. Private stochastic non-convex optimization: Adaptive algorithms and tighter generalization bounds. arXiv preprint 20Xh::2006.1351,, 2020.
14

---

A Other Preliminary
Definition A.1 (Laplace distribution). We say X Lap(b) if X has density f(x = x)
1 exp( -
26
In the analysis we use zero-comcentrated differential privacy (zCDP):
Definition A.2 (ZCDP). mechanism M is y-zCDP if for all a > 1 and neighboring D, D':
Ra (M()) S pa,
where Ra denotes the a-Rényi divergence.
Theorem A.3 (zCDP composition, (T]. The (adaptive) composition of k mechanisms that satisfy PP PPDDCPP <p2-zDDP, ... PP-zCDP respectively is (421 + 122 +... + >Pu)-zCDP
Lemma A.4. [Conversion between (5, (P and zCDP, (IT)) A mechanism that is (E, DD is also
E? /2-cCDP. mechanism that is i--cDD also (z, 8D for any >> 0 and 4 + 2/ (og(1/8).
Theorem A.5 (zCDP of Gaussian Mechanism, [T]. Given a randomized algorithm : p - IRd
let Aef = IaXxnighhorring D,D' [[A(D) A(D') l22 then releasing A(D) plus noise (00 o²) is
(A21) 20
-ZCDP.
Theorem A.6 (Matrix Bernstein inequality, [45)). Consider a sequence {Xitiem of independent,
mean-zero, symmetric d d random matrices. If for each matrix X1, we know ||Xillop S M,
then for all Z we have Pr [| Xillop 2 t| I dexp (N(
where o²
Eie(m)) E 1
B Omitted Proof of Section
B.1 Proof of Lemma
Lemma 3.3. For any 0 t S. T and letting Ti S be the largest integer such that drift,,, is set to be with probability at least w/T, for some universal constant C we have
I1 - VF(x:)1 < (33
Σ | 1=T+1
x2 +C?) C log(Td/w).
(1)
Hence with probability at least 1 - W, we know for each S T, IV VF S <22/16, where 7² 16 4C7) log(T d' and is parameter we can choose in the algorithm.
Proof. If drift, 0 happens, we use the first kind oracle to query the gradient, and hence V F((x,) is zero-mean and nSG(((1). If t Tr, Equation holds by the property of norm- subGaussian.
- For each T. + 1 < i < t, conditional on Vi-1, we know A; -VE((.)-F(;;)) F():-1)) is zero-mean and nSG I1)) Note that
V VF(x)) V - VF(x.)+ +
Σ |A (VF(z)) VF(x,-1)) i=
Equation (T) follows from Lemma 2.4
We know drift,-1 = Et=r. [2 - 11 < x almost surely by the design of the algorithm. By union bound, we know with probability at least 1 w, for each t E [T].
IV. VF(x:)1 <C(Cxx 4C7) log(Td/w)) -
15

---

B.2 Discussion of Lemma 3.4
Lemma 3,4 (Essentially from 46)). Under Assumption 3.1 run SGD iterations I++1 2t
V... with step size 1/M. Suppose Zo is a saddle point satisfying F| S a and smin( F(ro)))) v -vpa, a (dBM/pa) Vo = VF(a)) + SI + S2 where || S
C2 ~ NOO, [log(d/w) Ia). and IV (x+)) 1 7 for all E [T], with probability at least
1 1 w . log(1/w) one has ((r)) - F(oo) v - -0 Vplog darey
-/12
where r
M log pre
vPy
We briefly recap the proof of Lemma 3.4 in 46 One observation between the decreased function
value, and the distance solutions moved stated below:
Lemma B.1 (Lemmaa 11, 46)). For each [T), we know
| zu 1 (T((TF())) - F(rr)) + 50m
IV, - VF i
Σ
The difference between our algorithm and the DP-GD in 46 is the noise on the gradient. Note that with high probability, Eiery V (F(()) 1 in our algorithm is controlled and small, and hence does not change the other proofs in [6]. Hence if F(zo) F(zr) is small, i.c., the function value does not decrease significantly, we know Ie close to 200-
Let (r) be the unit ball of radius around point Denote the (r)r the point after running SGD mentioned in Lemma for I steps beginning at x. With this observation, denote B" (x))
{z Bzo (1a),, Pr[F((#)T) F(x) -b] 2 w). (46) demonstrates the following lemma:
Lemma B.2. V S a and smin F2oo())) S -VP, then the width of 13 (xro) along the
along the minimum eigenvector of F( is most [og(I/w)
The intuition is that if two different points x² x² B2, (nja). and x 2 is large along the minimum
eigenvector, then with high probability, the distance between [xx: )r (x²) rll will be large, and either [[(x)) Jr x= or (xx2)r 2²1l is large, and hence either F(x') F((x Jr) or F(x²) F((="r)
is large. The Lemma 3.4 follows from Lemma B.2 by using the Gaussian (2 to kick off the point.
B.3 Proof of Lemma 3,5
Lemma 3.5. By setting 1j 1/M, we have F(I++1) S. V.ll Vell - Moreover, with probability at least w. for each t S T such that VV 2 7, we have
F( F(x,) - v.l -
Proof. By the assumption on smoothness, know
F(F++1) <F(xx) + -x,) + M
2 | x211
- (VF(x)) - V.,))
+ (x:) V.ll |/ " |V
By Lemma 3.3 with probability at least 1 - w, for each t [T] we have [F(()) - Vella S 7/4.
Hence we know if (x..) 2 7, we have
F(I++1)- - F(x)) .11 -172/66
B.4 Proof of Lemma
Lemma 3.6. Suppose O and O2 are Çi and Sa norm-subGaussian respectively. If one sets 7 O(1) / (G 4G7) logg (dd/w), with probability at least 1 w. least point in the output set
16

---

f21,-.. , of Algorithm is a-SOSP, where
= 7 (BMdd((Mdd/ (SGN (G5 log(
d/w G3 + Ci
log
BMd pa pulCik
Proof. By Lemma 3.5 we know if the gradient Fxx))) 2 7, then with high probability that F(I(+1) F(x)) --777/// 2772/6 /6. By Lemma 3.4 if is saddle point (with small gradient norm but the Hessian has a small eigenvalue), then with high probability that F(ar+e) F( S
-3/2
-S0(
(/log" (1M uMg and the function values decrease 52
M log
J P12
on average for each step.
Recall the assumption that the risk is upper bounded by B, by our setting T = 52 RM the statement is proved.
log'
AMB
7
B.5 Proof of Lemma 3.7
Lemma 3.7. Under the event that V VF(x,))l 5//4for all E [T] and our parameter settings,
letting K = {t E [T] drift, 2 }} be the set of iterations where the drift is large, we know OBm ( )/k).
|K| O By + +T72
Proof. By Lemma 3.5 if [()))) 7. we know F(14+1) F(x)) < --n Vel and F(1+41) F(I1)= & my² otherwise. Index the items K (2,,t2," :. t(kt} such that t, < t 1- We know
F( - F(x,) < drift,,, + (li41 - -41h2n k + (4+1 4272n
6n
6n
Recall by the assumption that max, Fly) minn F(x) S B. And hence -B s |K| 6q + T) and we know
By | S 0 + TT?1)/k) O(Br log
dMB pyw
)/m).
C
Appendix for Section
The pseudocode of Algorithm is stated below:
Algorithm 2 AboveThreshold
Input: A of points
{a:)= dataset S, parameters of objective function B, M, G, p. objective
еттог a
2: Set Ti
Lap(
4G ne
16log(2T/w)G T2 - -Vpa Lap
16 log((2T)))
me
nE
n2
3: for i = 1, 1....
T do
4: if [[I
Lap 8G < f, Aminnmii(VV//) (mmin(=/ss(ss)) Lap 8M
> T then
5: Output: 27
6: Halt
7: end if
8: end for
C.1 Proof of Theorem 4.2
Theorem 4.2 (Empirical). For sp 0(1), use Equation 2) as gradient oracles with k GV BB/Bn/nor (dM .2 M M BM/ log" (AMB/W) Running Algo-
G1/3
n/4 2/3
Vd
1//2
n/e
rithm
outputting the set (x.)iE the total time to query O is bounded by O(Bn log A AcdM
//K).
pyw
17

---

otherwise outputting a set Tf arbitrary points is (p/2)-xCDR With probability at least - w. ar least one point the output set a1 - of FD with
VdBGM n/P
nBMd pw
01 =0
log
Moreover, if we run Algorithm with inputs {Ti)iE(T) D, M, G. Ot and e vo. with probability at least o (a Glog(n/Gu) log(dBGM// pw)) n/p
w. we can get an a2-SOSP of FD with a2
Von) The whole procedure is g-rCDP.
"/P/P
Proof. The privacy guarantee can be proved by zCDP composition (Lemma A.3 Gaussian Mecha- nism (Theorem A.5) and Lemma 3.7 Specifically, by Assumption 3.1and and our settings of parameters, respectively, and querying O and Og each time nto -ZCDP and x² -ZCDP respectively, We can apply the advanced composi- tion to prove the privacy guarantee of the whole algorithm. As the total number of iterations T is fixed, TM² all queries made to O2 satisfy n²a? n -ZCDP. It suffices bound the total time query O₁, which is ( )/ks), so guaranteed in the statement. That is the total times query O is Ti O(n (a p the queries Oj satisfy T₁
we know the sensitivity of O₂ and O₂ are bounded by and M [|
G²
M
-zCDP. If the time exceeds O (Bn log (dMB)) //r), then we will output a set of arbitrary points which does not occur additional privacy cost. The overall privacy guarantee
n²oo
is ( G M n n
-ZCDP. To get (1/2))-ZDDP, desired choose:
2GVT: 2G log"
4MB
By/K
2MVT TVP
2M AMlog' pw
AMB /BM
pw
σ1
02
TVP
n/p
n nv
As for the utility, we know the O2 and O₂ constructed in Equation are first kind of 01 v and second kind of 02vd norm-subGaussian gradient oracle by Fact 2.3 Hence by Lemma 3.6 the utility on satisfies that
=0 V o2vdk) dx) log (BMd/po)
G /dBB/K M log
dMB
VBM
ps
Vdx) (BMd/pW)))))
n ppp
By Lemma 3.7 with probability at least 1 w, the total time to query O is controlled and the final output will not be arbitrary points. Choosing the best demonstrates the bound di.. The bound for 02 follows from the value of an and 4..ma[4.] Combining the two items in Lemma 4. we know with probability at least w, the output point x of Algorithm satisfie that
32 log 2T /W]
32 (og((2TWW) (2T/W)M
|[Fo(()] a
and smin 2 FD(x)) -Vpa1-
n/F6
Hence we know is an SO-SO for a2 stated in the statement.
C.2 Proof of Claim
Claim 4.4. The gradient oracles O and Oz constructed in Equation 3 a first kind of
O Oloolo + Vdo1) norm-subGaussian gradient oracle and second kind of O norm-subGaussian gradient oracle respectively.
M M
+ v /do))
vbn
ab
Proof. For the oracle O₁, we know for each E S1, E/..p///(S(,, =)] (Fp(x) and V/(x. v F (a) nSG(L. due to the Lipschitzness assumption. The statement follows from Fact and Lemma 2.4 As for the O2, the statement follows similarly with the smoothness assumption.
D
18

---

C.3 Proof of Lemma 4.5
Lemma 4.5. Fix a point x E Rd. Given a set of m samples drawn i..dd from the distribution P. then we know with probability at least 1 - w, we have
G Glogld/w)
-oPPs(a)-VPPp(ana) S O M log(d/w)
IVPs(t) - VFr(2)]22 s 5
vm
vm
Proof. As for any 8 S, (x;;;) V F is zero-mean nSG(G). Then the Hoeffding inequality demonstrates with probability at least w/2, we have G log(a/w)
for norn-uuGGuassians (Lemma 2.4
[VFs(z)) - [>o(z)]l2 O
vmm
As for the other term, we know for any & E ((;))) [=)) = 0, and V2 [(:: 8) V FP(()))lop I 2M almost surely. Hence applying Matrix Bernstein inequality (Theorem A.6 with x² = 4M 1 O0 log(d/w)), we know with probability at least 1 - w/2, || V (x)
V Fz) S t/mm.
Applying the Union bound completes the proof.
C.4 Proof of Theorem 4.6
Theorem 4.6 (Population). Divide the dataset into two disjoint datasets DD and D2 of size no?
[n/2] and [n/2] respectively. Set b1 Bay b2 max( p1/3 log"
G
M and k. b2/²
BM b///p 02
1//0 (1/0 (/7)) in Equation 3 and use them as gradient or- acles. Running Algorithm 7 with D1, and outputting the set hetne if the total time to query O is bounded by O log't ( dMB /r), otherwise outputting set of arbitrary points, is (sp/2)=CCDP, mu
A1573 n 1/3 GB2/3 M573
66/T( vd
and with probability at least 1 - at least one point in the output is a a,-SOSP of Fp with
Vdl )3/7) log" (nBMd/ nVp
a1 =1=0(BBGMM log d) 1//3 + (2/TB3/TM317)
Moreover, if we run Algorithm with inputs (xitiE(T Dz, B, G. E vp with probability at least 1 - w. Algorithm 2 can output an a2-SOSP of Fp with an = M logindBGMippu) pw) O 01 + V yai + G( log(n//Co Gw) loz(dhw))) The whole procedure G-ZCDP
1/P
Proof. Recall that we draw the samples to construct the gradient oracles (Equation 3 without replacement, and we should have all samples to be fresh to avoid dependency, and hence we need
bi K + by T S n2/2.
which is satisfied by the procedure in the statement, as if the total time query the On exceeds the threshold, the algorithm fails and outputs set of arbitrary points. As we never reuse a sample, the privacy guarantee follows directly from the Gaussian Mechanism [0]. Specifically, the sensitivity of querying O2 and O₂ are bounded by G/b, and M|| yll/b2 respectively, and querying On and O2 are (<DD2) by Theorem A.5
The Nurussubaa parameters of the oracles follow from Claim 4.4 By lemma
3.6 we have
a1
log lggnMddd// pw)
=0lavvo+ Grlogd
MVR MVRlogd vb2 GvBnlogd d
+ +02vdk dd +
Vbi
=0( GBnVd
BM2
v BBM logd
+ n
dd
M MMR
nppp
Vnk
Vnai
Setting x max(
M373
log
(n) 1/3
GBB2a
MP73
6/7
)4/7), mV
Vd
we get
Vd
0n 0 1/33
(G
/3/T M
/3/7)
log (nBBdd
+
nz/3
n
19

---

Then we use the other half fresh samples D2 to find the point in the set by Algorithm 2 By Lemma 4.J and Lemma 4.5 we know with probability at least w. for some large enough constant C' > the output point x: of Algorithm 2
satisfies that
32 log (PT(TT/L) Clog(dn//w)
[VF(())l San + G(
nV6
Vni
32 log(2T/w))
C' Cllo(dn//w)
smin
pax M
n/p
vnn
Hence we know 2 is an 0:2 SOSP for a2 stated in the statement. The privacy guarantee follows from
Lemmas
A.3
A.4
and
D Omitted proof of Section
D.1 Proof of Lemma
Lemma 5.5 (Generalization error bound), Let & exp(-3((bbxx) + +
Then we have
Ep (F)(x) FD(x)) < 0 exp((GD)
np
Proof. We know how to bound the KL divergence by LSI:
/
log duD dup
KL(TD, TD.) =
dr
CLSI
d
E
V log
2 KD
dTp
S2CLsi /n².
LSI can lead to Talagrand transportation inequality [Theorem in 40 ie.,
W2(TD, & VCisi KL TD:) GL//
The generalization error bounded by D(CisIG?3/m). Using Holley-Stroode perturbation, we exp(3GD) and hence the W2 distance between TD and TD can be bounded by Ap
know (LDI(TT) <
O
G Gexp(GGD) ap ). The statement follows the Lipschitzness constant and Lemma 5.4
D.2 Proof of Theorem 5.6
Theorem 5.6 (Risk bound). We are given e, 10,1/2). Sampling from
1
with 3 = O (ogltog)) ).H = D23 (E, 6)-P. The empirical risk and population risk are
log(nd)
bounded by O d-log (oggg//
llg(ndd)
Proof. Denote (2x) & exp(-3(Fo(1) + (1))12)) By Lemma 5.2
we know CLSI(T) I
exp(3GD). Plugging in the parameters and applying Theorem 5.1 we get
2GB
exp(3GD)
GD8
= 0(1) 3olg(1188)
(gg S
nyd
and hence prove the privacy guarantee.
As for the empirical risk bound, by Lemma 5.3 we know
E (Fb(z) + 1 [=1lB) woust
min (Fo(x") + 5
S
d log (GGD/a D/d)
2
3
and we know
dlog(BGD/a)
E. FD(z)
min Fo(x*) eK
2DD2
B
20

---

Replacing the value of 3 achieves the empirical risk bound.
As for the population risk, have
E Fp(x) min Fr(y") SKEK
E [PD(2)) - FD(x)] + [x)
x min FD
min FD(x") min Pp (y())
2~0
xED
yrEK
< E [P(x)) Fb(x)) + [F()
min F FD(x"))
We can bound E (Fp()) Fo(x)] S 2 (
0
GDe GDzlog(n)
by Lemma 5.5
n² nt-=dy log(1/6)
for an arbitrarily small constant c > 0. Hence the empirical risk is dominated term compared to Egwn [F(()) FD(x)], and complete the proof.
D.3 Implementation
We rewrite them below: Let F(x) == F(x) r(x)) where r(x) is regularizer, and F Bies fi the expectation of a family of G-Lipschitz functions.
Algorithm 3 AlternateSappe, 355
Input: Function F, initial point mg ~ No. step size !]
2: for E [T' do
3: V/ 4 -t-1 + VTS where Ç ~ La)
4: Sample 2,, + exp(- 2n -1
5: end for
6: Output: DT
Theorem D.1 (Guarantee of Algorithm
(51). Let C Rd be a convex set of diameter D, and F: R, and ı x exp(- F) satisfies LSI with constant C1.s-- Then set 1j 2 0, we have
[TO x) (1 (1+ 25/4
Rg Te, T)
where Rgg (T', ,)) 3 the g-th order of Renyi divergence between T' and n.
To get a sample from guarantee is stated below:
2n vell3), we use the rejection sampler from
26 whose
26 If the step size S 2 (1/6 and the inner accuracy 8inne (0, 1/2), there an algorithm that can return random point that has dinner total variation distance to the distribution proportional to exp(-F(x)) 2n || y1l2). Moreover, the algorithm accesses (1) different fs function values and O(1) samples from the density proportional to
Lemma D.2 (Rejection Sampler,
27 y122)
Combining Theorem 5.6 Theorem D.I and Lemma D.2 we can get the following implementation of the exponential mechanism for non-smooth functions.
Theorem 5.7 (Implementation, risk bound). For e, E (0,1/2), there is an (e, 20) efficient sampler that achieve the empirical and population risks O(GD) d.log log(n), /18g(188) Moreover,
8 (log(nd)
in expectation, the sampler takes Ô n log² (d))/1gg(11)) (og(1/6))/GD)) function values query and some Gaussian random variables restricted to the convex set IC total.
Proof. By Theorem 5.6 it suffices to get a good sample from with density proportional to d Set g 1, which gives that --) is the KL-divergence. Suppose we let io is drawn from density proportional to 2 then the KL divergence between mo and is bounded by exp(g3GD).
exp(-B(FDDz) / 11) where O /Dg/1g(1//8)
slo((d))
21

---

Now let "T be the distribution we get over 2T from Algorithm if we use an exact sampler for i iterations, then the sampler of Lemma D.2 for the remaining T iterations. The output of Algorithm that we actually get is ny. Note that CT.sI S D and S B G- 1 (2T Setting
(3)
T= (LIS log log(exp((3GD)/88) = ( ne log (d) (og
GD
get dinner 8/2l in Lemma D.2 and that R1 (17 (T) , 82/8. This implies the total variation distance between my and ग is at most 6/2 by Pinsker's inequality. Furthermore, by the post- processing inequality, the total variation distance between Th( and "T ((+1) is at most 8/2T for all i. Then by triangle inequality the total variation distance between कy and π is at most 6.
(0)
D.4 Proof of Theorem 5.8
Theorem 5.8. There exists an E-DP differentially private algorithm that achieves a population risk 0f GD (dlog(en/d)((en) + /dloglen/d//(v))
Proof. We pick a maximal packing P ((D/r))) points, such that every point in X. is distance most r from some point in P. By G-Lipschitzness, the risk of any point in / for the DP-ERM/SCO problems over K. are at most Gr plus the risk of the same point for DP-ERM/SCO exponential mechanism over P gives DP-ERM risk bound of O GD log PI). Next, note that the empirical loss of each point in P is the average of n random variables in 00, GD] wlog. So, the expected maximum difference between the empirical and population loss of any point in P is
P. The
GD GDViog IP]
Putting it all together we get a DP-SCO expected risk bound of:
o ocr+ GD
(dlog(D/r)
/dlog(D/r)
en
Vn
This is approximately minimized by setting r Dd/en. This gives a bound of:
dlog(en/d)
/dloglen/d)) )
GD
en
vn
E
Conclusion
We present a novel framework that can improve upon the state-of-the-art rates for locating second- order stationary points for both empirical and population risks. We also examine the utilization of the exponential mechanism to attain favorable excess risk bounds for both a polynomial time sampling approach and exponential time sampling approach. Despite the progress made, several interesting questions remain. There is still gap between the upper and lower bounds for finding stationary
points. As noted in (2), is quite challenging beat the current (v² / empirical upper bound, and overcoming this challenge may require the development of new techniques. A potential avenue for improving the population rate for SOSP could be combining our drift-controlled framework with the tree-based private SpiderBoost algorithm in (2). Additionally, it is worth exploring it is possible to achieve better excess risk bounds within polynomial time, and what the optimal risk bound could be.
F Extended related work
In the convex setting, it is feasible to achieve efficient algorithms with good risk guarantees. In turn, and
differentially private empirical risk minimization (DP-ERM)
[3]
14
17
differentially private stochastic optimization 4 6
22
32
26
23
22
27
have been two of
22

---

the most extensively studied problems in the DP literature. Most common approaches are variants of
DP-SGD [4] or the exponential mechanism [8]]
As for the non-convex optimization, due to the intrinsic challenges in minimizing general non-convex
functions, most of the previous works 449 50
47
46
56
42
44
54
2
51 24 adopted the gradient
norm as the accuracy metric rather than risk. Instead of minimizing the gradient norm discussed before, g tried minimize the stationarity gap of the population function privately, which is defined as Gappp (x) := maXyeK, (VPp))e)) x y) which requires I. to be bounded domain. There are also some different definitions of the second order stationary point. We refer the readers [3] for more details.
The risk bound achieved by algorithms with polynomial running time is weak and requires > d to be meaningful. Many previous works consider minimizing risks of non-convex functions under stronger assumptions, such as, Dolyak-Lojasiewier condition 49 55 Generalized linear model (GLM) 46 and weakly convex functions [8]
In the (non-private) classic stochastic optimization, there is long line of influential works on finding the first and second-order stationary points for non-convex functions, [ 29
21 53 18].
First order stationary points. Progress towards privately finding a first-order stationary point is measured in (i) the norm of the empirical gradient at the solution æ, i.e.. [/V](( and (ti) the norm of the population gradient, i.e., | (P((() (I) We summarize compare these first-order guarantees achieved by Algorithm with previous algorithms in Table 2
References
Empirical
Population
N/A
47
d'
dd
yn
50
dd 2233
N/A
56
d'
vn
Vn
vd
2/3
+
N/A
//
Vd
2/3
(L
TL
Table 2: Previous work in finding first-order stationary points. We omit logarithmic terms and dependencies on other parameters such as Lipschitz constant. "N/A" means we do not find an explicit result in the work.
Second order stationary points. We say point x is Second-Order Stationary Point (SOSP), or a local minimum of twice differentiable function if VV)(z) l2 = O and smin V²9(x)) 2 0. Exact second-order stationary points can be extremely challenging find (25). Instead, common to measure the progress in terms of how well the solution approximates an SOSP.
Definition F.1 (approximate-SO9) SOSP, (... We say x TR.d is an a-second order stationary point (a-SOSP) for p-Hessian fimccint g. if
[V(())l2 S
A smin s (x)( -Vpo.
References
Empirical
Population
d=/4 VT
46
N/A
48
(2)477
N/A
24
[Vdj1/2
N/A
Ours
( I/d /2/3/3
+ ( (Vaja/7
71
Table 3: Summary of previous results in finding a-SOSP, where is demonstrated in the Table. Omit the logarithmic terms and the dependencies on other parameters like Lipschitz constant. "N/A" means we do not find an explicit result in the work.
23

---

Existing works in finding approximate SOSP privately give guarantees for the empirical function Fp. We improve upon the state-of-the- result and give the first guarantee for the population function Fp, which is summarized in Table 3
24


Reviews:
[{"review_id": "eePoQTSmfT", "reviewer": "Reviewer_kK73", "summary": "The paper studies the problem of non-convex optimization under differential privacy constraints. The goal of the paper is to find first and second order stationary points of the function. The proposed algorithm which is inspired by SpiderBoost [1] is a sampling based method that generates a private estimator that minimizes both excess empirical and population risks. \n\nThe authors studied the cases: when only polynomial run time is allowed, and when the exponential run time is permitted. In the first case, their proposed algorithm outperforms the previous best and tightens the gap between the provided upper bound and the already existing lower bound. For the case when exponential run time is allowed, the paper provides a nearly matching upper and lower bound. \n\n[1] Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, 32, 2019.\n\n", "questions": "1. What is the main technical novelty of the work?\n\n2. Is the proposed algorithm a privatized version of SpiderBoost? if yes, except the added gaussian noise what are the additional elements that are added? And can one similarly construct a privatized version of other algorithms like Spider or SARAH?\n\n3. Can you please provide an intuition that why your technique could relax the smoothness assumption?\n\n4. Except the relaxed smoothness assumption, can you please provide an intuition what would be the difference in the perfromance if one used Spider or SARAH instead of SpiderBoost?\n\n", "limitations": "The limitation of the work is the optimality gap between the upper and lower bound, where the authors mentioned this and referred to it as an open problem. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is a collection of elegant results. From a technical point of view, the paper is solid. It enhances advanced techniques to fulfill its objective. While the paper outperforms previous best algorithm [2], with polynomial run time it relaxes the smoothness assumption that has been assumed in [2]. \n\n[2] Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pages 6526–6535. PMLR, 2019.\n\n", "weaknesses": "For a reader who is not fluent with the literature, the paper is not easy to follow. Several insights left to be unexplained. The paper is quite dense without enough provided intuition on the proposed algorithm. The authors did a good job in mentioning the similarities with precious work, but they did not discuss their technical novelties. Some expressions and notation are left undefined (ex. W_2 at line 308). \n\nAs a side note, I think P at line 18 should be P*.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable reviews.\n\nWe use $P^*$ as the input dataset can be of arbitrary size. For example, we consider a set D of size n in the paper, meaning $D \\in P^n$.\n\nQ1: We discuss our techniques and the challenge of previous techniques in Subsection 1.2 (our techniques) and related work (page 2), and more details can be found there. In particular, our main technical ideas are: 1.To use the notion of drift to decide when to add the noise in SpiderBoost to get good gradient estimations all the time, which enables it to escape saddle points to reach SOSP, and 2. Design privacy analysis of the exponential mechanism and sampling method based on log-Sobolev-inequality (as opposed to smoothness) to obtain the excess population risk guarantees. \n\nQ2: Yes, our algorithm can be treated as a privatized version of SpiderBoost.  Besides adding noise, the main added element is the method for choosing when to recompute the gradient from scratch; SpiderBoost does this after a fixed number of rounds, whereas we dynamically choose to do this based on the quantities frozen and drift. We did not try to construct private versions of other algorithms like Spider or SARAH, but we believe our methods and intuitions can also be helpful for those algorithms. However, we do not expect the theoretical bounds there to be better, as all these algorithms are morally similar.\n\nQ3: Sorry for the confusion. For context, we only relax the smoothness assumption for the excess risk, but not for finding the SOSP. The intuition for relaxing the assumption for SOSP is that we are directly providing our bound via LSI (log-Sobolev inequality), rather than via a run of LMC, which explicitly requires smoothness for convergence.\n\nQ4: SpiderBoost was used by [1] to obtain DP-FOSP, and it was natural to seek whether it is able to find DP-SOSP. SpiderBoost allows a larger learning rate and hence may have better practical performance. Empirical evaluation to compare these different algorithms is left for future work.\n\n[1] Arora, R., Bassily, R., González, T., Guzmán, C. A., Menart, M., & Ullah, E. (2023, July). Faster rates of convergence to stationary points in differentially private optimization. In International Conference on Machine Learning (pp. 1060-1092). PMLR."}, {"review_id": "sjsdMD1sQl", "reviewer": "Reviewer_nTrG", "summary": "This paper studies differentially private second-order optimization problems, where the loss function is assumed to be second-order smooth. The objective is to identify second-order stationary points (SOSP) while ensuring privacy guarantees. The authors present results for both empirical risk and population risk, with notable advancements over existing state-of-the-art outcomes. Specifically, the empirical risk minimization (ERM) bound improves from the state-of-art rate, while the population risk result stands as the first of its kind in the literature on differentially private SOSP optimization. Furthermore, the paper contributes a lower bound analysis for private SOSP optimization, further strengthening its significance in this domain.", "questions": "I have a few questions regarding the general SOSP framework (Algorithm 1):\n- What role does $\\text{frozen}_t$ play?\n- line 8: why is an additional noise $g_t$ added to the private oracle $\\mathcal{O}_1(x_t)$?\n- Since Alg. 1 only serves as a non-private SOSP optimization framework, is it possible to choose other variance-reduction algorithms (e.g., [1])? If not, what is the key characteristic that distinguishes SpiderBoost from other optimizers in the private setting?\n\nAlso, Section 5 focuses on private excess risk minimization, which seems to deviate from the previous discussion about SOSP. I'm wondering how Sec. 5 relates to the previous part of the paper?\n\nReference:\n1. Ashok Cutkosky, Francesco Orabona. Momentum-Based Variance Reduction in Non-Convex SGD.", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The strength of this paper lies in its highly comprehensive study of private second-order optimization. The authors study both empirical risk minimization and population risk, and the obtained bounds improves from the state-of-the-art results in both case. The inclusion of a lower bound also closes the gap of this problem.", "weaknesses": "The authors can enhance the writing by providing additional discussion regarding the algorithm employed, the obtained results, and the insights derived from their findings. Furthermore, providing more detailed explanations for the technical results cited from previous works, such as Lemma 3.4 and Alg.2, would help clarify any confusion and prevent ambiguity. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive reviews and questions. Following are the responses to the specific questions:\n\nQ1. We use Lemma 3.4 for escaping the saddle point directly, which requires us to add “extra” Gaussian noise whenever the gradient norm of the current point is small (meaning it is possibly a saddle point). Notice that Section 3 discusses the general optimization framework and has nothing to do with DP, and hence the oracle does not necessarily need to add Gaussian noise and can even be exact.\nfrozen_t is used to control the “extra” Gaussian noise we add to escape saddle points, as adding too much extra Gaussian noise may worsen the algorithm's performance. For example, when the initial point is already a good SOSP, then ${\\rm frozen}_t$ can ensure that further extra noise can be added at most every $\\Gamma$ steps.\n\nQ2: As we mentioned in Q1, the Gaussian $g_t$ is used for helping the point escape the saddle point. (A similar idea was used in [2,3]).  \n\nQ3: This is also asked by other reviewers, and we will add a discussion on this. We chose SpiderBoost mainly because [1] used it for finding first-order stationary points privately.  We examined whether this algorithm can be used to find second-order stationary points (SOSP), and eventually solved the challenges towards achieving SOSP.\n\nIt is true that current Section 5 can be considered as an interlude. (We will make it clear in the paper.) Prior works ([1] and [2]) have considered zeroth order (excess risk), FOSP, and SOSP. Being consistent with the literature, we improve on excess risk bounds too.\n\n[1] Arora, R., Bassily, R., González, T., Guzmán, C. A., Menart, M., & Ullah, E. (2023, July). Faster rates of convergence to stationary points in differentially private optimization. In International Conference on Machine Learning (pp. 1060-1092). PMLR.\n\n[2] Wang, D., Chen, C., & Xu, J. (2019, May). Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning (pp. 6526-6535). PMLR.\n\n[3] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., & Jordan, M. I. (2017, July). How to escape saddle points efficiently. In International conference on machine learning (pp. 1724-1732). PMLR."}, {"review_id": "2uBqTWcR0k", "reviewer": "Reviewer_52pN", "summary": "The paper introduces a non-convex optimization framework that integrates two types of gradient oracle and an application of the exponential mechanism to find the global minima of non-convex objectives, requiring minimal assumptions and showcasing remarkable population risk bound performance. The paper also highlights the ability to emulate previous empirical and population risk bounds effectively, removing the necessity for smoothness assumptions.", "questions": "How does the performance of the Stochastic Spider, as presented in this paper, compare to that of the BoostSpider in practical applications? While the theoretical results indicate a rate improvement, is this enhancement accompanied by an increase in constants and an impact on finite sample performances?", "limitations": "See weaknesses.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper presents robust, theoretical insights into a clearly defined problem, and its logical flow makes it accessible and easy to comprehend. \n\nIt commendably surveys and incorporates existing related literature.", "weaknesses": "This paper appears to conclude abruptly, with the discourse ending unexpectedly following a theorem. The absence of a conclusion or summary weakens the paper's overall structure.\n\nThere is an absence of numerical experiments. \n\nAdditionally, the authors seem to have relied solely on Advanced Composition for privacy accounting. There are, however, various alternative privacy accounting methods available that could potentially improve the overall performance. For instance, the 'Better Privacy Accounting' method [1], utilization of GDP [2], or the application of tighter composition theorems [3] might be considered for future research and improvements.\n\n[1]: Altschuler, J., & Talwar, K. (2022). Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35, 3788-3800.\n\n[2] Liu, Y., Sun, K., Jiang, B., & Kong, L. (2022). Identification, amplification and measurement: A bridge to gaussian differential privacy. Advances in Neural Information Processing Systems, 35, 11410-11422.\n\n[3] Kairouz, P., Oh, S., & Viswanath, P. (2015, June). The composition theorem for differential privacy. In International conference on machine learning (pp. 1376-1385). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We will add a detailed conclusion section in the paper. In more detail, our conclusion will review the main contributions of the paper and then propose some future directions which we feel are important/interesting, including:\n- Can we close the gap between our upper and lower bounds for SOSP?\n- We used a “gradient difference oracle” O_2, which has lower sensitivity, and thus we can tolerate a higher noise multiplier on this oracle. Are there other settings where such a technique can improve the privacy-utility tradeoff? \n- Can we obtain our SOSP bounds using a batch gradient oracle instead of a full gradient oracle?\n- For population risk, do any assumptions “between” convexity and LSI admit better excess loss bounds in polynomial time?\n\nComment about the numerical experiment: The objective of our paper was to improve the current SOTA analytical bounds (see [1] and [2] in response to Reviewer nTrG, which are also purely theoretical in nature). We acknowledge having a thorough empirical study is important. We leave it for future exploration.\n\nOur results seamlessly extend to measures of privacy like GaussianDP/ RenyiDP/ zCDP.  We will update the presentation to state the main results in terms of Gaussian DP and using Gaussian DP composition (as opposed to ($\\epsilon,\\delta$)-DP). One reason for choosing the ($\\epsilon,\\delta$)-DP variant was to be consistent with the prior literature. We want to emphasize that changing the notion of privacy does not make any meaningful changes to our results, as (i) our results are based solely on the Gaussian mechanism and AboveThreshold algorithm (which are known to satisfy all the above notions of DP seamlessly.) (ii) we give polynomial improvements on the dependence on n and d, so improving log factors via tighter composition does not qualitatively change the results. \n"}, {"review_id": "XoMnOwhj0e", "reviewer": "Reviewer_mRqH", "summary": "This paper addresses the problem of private stochastic optimization for general non-convex functions. For smoothed functions, the authors propose a combination of the Gaussian mechanism and the variance reduction technique (spider algorithm) to find the SOSP of the loss function. Their results for the empirical risk improve upon previous state-of-the-art bounds by a factor of $n\\varepsilon$ and their results for the population risk are new in the field of private optimization literature. For general Lipschitz non-convex problems, the authors establish improved bounds for bounding the excess risk using exponential mechanisms. Notably, they provide a new exponentially-time algorithm that matches the proposed lower bound.\n", "questions": "I have no further questions.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and clear in its claims. The authors propose a novel approach to private stochastic optimization for both smooth and non-convex loss functions by combining existing private mechanisms with the Spider algorithm. They provide new results for both upper and lower bounds on the excess population risk, which are technically solid and contribute to the literature on private stochastic optimization. Overall, the results presented in the paper make a valuable contribution to the field.\n\n", "weaknesses": "1. The paper makes a significant contribution to improving the bounds for private optimization, but there is still a gap between the existing upper and lower bounds that needs to be explored in future work.\n2. While the paper focuses on theoretical studies, the authors could consider conducting experimental studies to validate their theoretical findings", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your kind reviews and comments. In our future work, we will both explore the tightness of our bounds, and evaluate our algorithms empirically."}, {"review_id": "OUCuyB1lJ0", "reviewer": "Reviewer_xUe2", "summary": "This paper provides a private algorithm for (Stochastic) Non-Convex Optimization using gradients, differences between two successive gradients, and the exponential mechanism for privacy (added to the gradient). It leverages the SpiderBoost algorithm and its private version to find (privately) stationary points. The main challenge addressed by the paper is to keep the quality of the gradient estimations at all steps. ", "questions": "See above", "limitations": "- traditional hypotheses on these types of results", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- simple modification of  SpiderBoost to maintain the quality of the gradient estimations.\n- interesting properties of the algorithm, i.e., the algorithm is capable of escaping the saddle point  with high probability, and a large drift implies significant decrease in the function value, limiting the number of gradient queries.", "weaknesses": "- there is something weird about Algorithm 1. drift_t is set to zero in lines 7 and 10, but then overwritten in line 14. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time reviewing and commenting on our paper. \nThanks for pointing out the typo. It should be $\\mathrm{drift}_{t+1}=\\mathrm{drift}_t+ \\eta^2 ||\\nabla_t||^2$ in line 14. Please let us know if you have further questions or concerns."}]

Author rebuttal:
**General Reply:** We thank all the reviewers for their reviews and comments. We will diligently address all the presentation issues raised by the reviewers and enhance the writing quality in future versions, like providing more explanations on the intuitions. In the following, we respond to the specific questions raised by the reviewers.

Meta-review: Private stochastic optimization for general non-convex functions is a hard task to which the authors provide solution with analysis of both upper and lower bounds.
Decision: Accept (spotlight)