Adaptive Batch Size for Privately Finding Second-Order Stationary Points
Authors: Daogao Liu
Kunal Talwar
Venue: ICLR 2025 Spotlight (2025)
Keywords: Differential privacy
non-convex optimization
adaptive batch size
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We improved the previous results in finding second-order stationary points privately by utlizing adaptive batch size and the tree mechanism.

Abstract: There is a gap between finding a first-order stationary point (FOSP) and a second-order stationary point (SOSP) under differential privacy constraints, and it remains unclear whether privately finding an SOSP is more challenging than finding an FOSP. Specifically, Ganesh et al. (2023) claimed that an $\alpha$-SOSP can be found with $\alpha=\Tilde{O}(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{3/7})$, where $n$ is the dataset size, $d$ is the dimension, and $\epsilon$ is the differential privacy parameter.
However, a recent analysis revealed an issue in their saddle point escape procedure, leading to weaker guarantees.  
Building on the SpiderBoost algorithm framework, we propose a new approach that uses adaptive batch sizes and incorporates the binary tree mechanism.
Our method not only corrects this issue but also improves the results for privately finding an SOSP, achieving $\alpha=\Tilde{O}(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{1/2})$. 
 This improved bound matches the state-of-the-art for finding a FOSP, suggesting that privately finding an SOSP may be achievable at no additional cost.

Published as a conference paper at ICLR 2025
ADAPTIVE BATCH SIZE FOR PRIVATELY FINDING SECOND-ORDER STATIONARY POINTS
Daogao Liu" University of Washington
Kunal Talwar Apple
ABSTRACT
There is a gap between finding first-order stationary point (FOSP) and second- order stationary point (SOSP) under differential privacy constraints, and it remains unclear whether privately finding an SOSP is more challenging than finding an FOSP. Specifically, Ganesh et al. (2023) claimed that an a-SOSP can be found with = Ó 1.7 + va )3/7), where is the dataset size, d is the dimension, and is the differential privacy parameter. However, recent analysis revealed an issue in their saddle point escape procedure, leading to weaker guarantees. Building on the SpiderBoost algorithm framework, we propose a new approach that uses adaptive batch sizes and incorporates the binary tree mechanism. Our method not only corrects this issue but also improves the results for privately finding an SOSP, achieving a Ö( (vd) )/2). This improved bound matches the state-of-the-ard for finding a FOSP, suggesting that privately finding an SOSP may be achievable no additional cost.
ns
INTRODUCTION
Privacy concerns have gained increasing attention with the rapid development of artificial intelli- gence and modern machine learning, particularly the widespread success of large language models. Differential privacy (DP) has become the standard notion of privacy in machine learning since it was introduced by Dwork et al. (2006). Given two neighboring datasets, D and D', differing by a single item, mechanism M is said to be (c, difffeerrett private if, for any event X,, it holds that:
Pr[M(D) X1 S Pr[M(D') E 8
In this work, we focus on the stochastic optimization problem under the constraint of DP. The loss function is defined below:
Fp(r) == zwPp f(x;2),
where the functions may be non-convex, the underlying distribution P is unknown, and we given a dataset D = [=ibeej drawn i.i.d. from P. Notably, our goal is to design a private algorithm with provable utility guarantees under the i.i.d. assumption.
Minimizing non-convex functions is generally challenging and often intractable, but most models used in practice are not guaranteed be convex. How, then, can we explain the success of opti- mization methods in practice? One possible explanation is the effectiveness of Stochastic Gradient Descent (SGD), which is well-known be able to find an a-first-order stationary point (FOSP) of non-convex function f that is, point x such that [>)][ I a wiwit O(1/a²) steps (Nes- terov 1998). However, FOSPs can include saddle points or even local maxima. Thus, we focus on finding second-order stationary points (SOSP), for the non-convex function Fp.
Non-convex optimization has been extensively studied in recent years due to its central role mod- em machine learning, and we now have a solid understanding of the complexity involved in finding
FOSPs and SOSPs (Ghadimi & Lan 2013 Agarwal et al. 2017 Carmon et al. 2020 Zhang et al.
"work was done while interning at Apple, Email: 1 Liudacgac@gmai. com I Email: kunal 1 @kuna t .rg

---

Published as a conference paper at ICLR 2025
2020).
Variance reduction techniques have been shown improve the theoretical complexity, lead-
ing to the development of several promising algorithms such as Spider (Fang et al. 2018). SARAH
Nguyen et al. 2017). and SpiderBoost (Wang et al.
2019b). More recently, private non-convex
optimization has emerged as an active area of research
Waan et al. 2019a Tran & Cutkosky
2022
Arora et al., 2023 Gao & Wright 2023) Ganesh al.
2023 Wang al. 2023
Lowy al. 2024
Kornowski et al. 2024 Menart et al. (2024).
1.1 OUR MAIN RESULT
In this work, we study how to find the SOSP of Fp privately. Let us formally define the FOSP and the SOSP. For more on Hessian Lipschitz continuity and related background, see the preliminaries in Section 2
Definition 1.1 (FOSP). For 2 0, we say a point x is an a-first-order stationary point (a-FOSP) of a function if [ I a.
Definition 1.2 (SOSP, Nesterov & Polyak 2006)); Agarwal et al. (2017). For a function g IR + R
which is p-Hessian Lipschitz, we say point æ E IR" is a-second-order stationary point (a-SOSP) of g if [Vg(2>)12 a A V g(x) ž /pala.
Given the dataset size of n, privacy parameters E, 8, and functions defined over d-dimensional space, Ganesh et al. (2033) proposed private algorithm that can find an a for Fp with
+ (/7 ag = 0( 1/3 n1/3
nE
However, as shown in Arora et al. 2023). the state-of-the-art bound for privately finding op- FOSP is tighter:
OF - 0p
1 1//3
1/2)
When the privacy parameter e is sufficiently small, and the error term depending on it dominates the non-private term 1/n we observe that aF < as. This raises the question: is finding an SOSP under differential privacy constraints more difficult than finding an FOSP?
Moreover, as pointed out by Tao et al. (2025), the results in Ganesh et al. (2023) may overly optimistic. In particular, the saddle point escape subprocedure used in Ganesh et al. (2023) was designed for the full-batch setting. However, to mitigate dependence issues, the algorithm performs only single pass over the functions and relies minibatches instead. A direct fix for this issue leads to a weaker guarantee on the minimum eigenvalue of the Hessian, specifically,
2 F2(()) ł - V 2/5 Ia.
which fails to satisfy Definition correction, but their method resulted in weaker theoretical guarantees than Ganesh et al. (2023) originally claimed, yielding
T.2 To address this, Tao et al. (2055) proposed an alternative
a a= Ō
2/5)
1//3
ne
This work improves upon the results of Ganesh et al. (2023). In addition, we introduce a new saddle point escape subprocedure that correctly addresses the issue in Ganesh al. (2023) while fully recovering-and even strengthening- theoretical guarantees.
Specifically, we present algorithm that finds a-SOSP with privacy guarantees, where:
Vd
a Ō(ar) = Ō 0
1/3).
n//3
nE
This improved bound suggests that when we try to find the stationary point privately, we can find the SOSP for free under additional (standard) assumptions.
As proposed by Lowy al. (202)) allowing exponential running time enables the use of the exponential mechanism find start, which further improve the bounds for both FOSP and SOSP.
2

---

Published as a conference paper at ICLR 2025
It is also worth noting that, our improvement primarily affects terms dependent the privacy pa- rameters. In the non-private setting, as E - oo (i.e., without privacy constraints), all the results discussed above achieve a bound of ((1/n'/3), which matches the non-private lower bound estab- lished by Arjevani et al. 2023) in sigh-dimensional settings (where 2 (((1/a)). However, to our knowledge, whether this non-private term of ((1/n1/9) can be further improved in low dimension remains an open question.
1.2 OVERVIEW OF TECHNIQUES
In this work, we build on the SpiderBoost algorithm framework, similar to prior approaches (Arora ctt al., 2023: Ganesh et al. 2023), to find second-order stationary points (SOSP) privately. At a high level, our method leverages two types of gradient oracles: (1))) (x)),, which estimates the gradient at point x, and (2 y) x f(x) V fiv), which estimates the gradient difference between two points, x and y. When performing gradient descent, to compute the gradient estimator
V, at point 2t, we can either use V = O (Ix) for a direct estimate, or V V + O2(Ze, Zt-1) to update based on the previous gradient. In our setting. O₁ is more accurate but incurs higher computational or privacy costs.
The approach in Arora et al. (2023) adopts SpiderBoost by querying On periodically; they call On once and then use O2 for q subsequent queries, controlled by hyperparameter q. Their method ensures the gradient estimators are sufficiently accurate on average, which works well for finding first-order stationary points (FOSP). However, finding an SOSP, where greater precision is required, presents additional challenges when relying on average-accurate gradient estimators.
To address this, Ganesh et al. (023) introduced a variable called drift, := Ei || x4 11? where to is the index of the last lteration when O₁ was queried. If drift, remains small, the gradient estimator stays accurate enough, allowing further queries of O2. However, if drift, grows large, the gradient estimator's s accuracy deteriorates, signaling the need to query O for fresh, more accurate estimate. This modification enables the algorithm to maintain the precision necessary for privately finding an SOSP.
Our improvement introduces two new components: the use of the tree mechanism instead of using the Gaussian mechanism in Ganesh et al. (2023), and the implementation of adaptive batch sizes for constructing O2.
In the prior approach using the Gaussian mechanism, noisy gradient estimator V,-1 is computed, and the next estimator is updated via V. = V.-i + +2(,,, xt-1) + Gt. where is Gaussian noise added preserve privacy. Over multiple iterations, the accumulation of noise Σ gt can severely degrade the accuracy of the gradient estimator, requiring frequent re-queries of O₁. On the other hand, the tree mechanism mitigates this issue when frequent queries to O2 are needed.
However, simply replacing the Gaussian mechanism with the tree mechanism and using a fixed batch size does not yield optimal results. In worst-case scenarios, where the function's 's gradients are large, the drift grows quickly, necessitating frequent calls to O₁, which diminishes the advantages of the tree mechanism.
To address this, we introduce adaptive batch sizes. In Ganesh et al. (023). the oracle Og is con- structed by drawing fixed batch of size B from the unused dataset and outputting O2(1,, xt-1) =
Exes, Vf(z.))) V Given an upper bound on drift, they guaranteed that |2|, 11-1l1 D B for some parameter D, thereby bounding the sensitivity of O2.
In contrast, we dynamically adjust the batch size in proportion to ||a - xt-1ll. setting B, x || -
Fr-1 ||| and compute O2(1e, 2r-1) = Σies, - ((se-1 Fixed batch sizes present two drawbacks: (i) when || - - is large, the gradient estimator has higher sensitivity and variance, leading to worse estimate accuracy; (ii) when ||æ; xl-ill is small, progress in terms of function value decrease limited. Using a fixed batch size forces us to handle both cases simultaneously: we must add noise and analyze accuracy assuming worst-case large ||ær; zz- but for utility analysis, we pretend || - x is small to examine the function value decrease. The adaptive batch size resolves this paradox: it allows
Hr
control sensitivity and variance adaptively. When ||æ, z is small, we decrease the batch size but can still control the variance and sensitivity; when it is small, the function value decreases significantly, aiding in finding SOSP.
3

---

Published as a conference paper at ICLR 2025
By combining the tree mechanism with adaptive batch sizes, improve the accuracy of gradient estimation and achieve better results for privately finding an SOSP.
Fixing the Error: Building upon our discussion of obtaining more accurate gradient estimations through adaptive batch sizes, we extend this approach to Hessian estimations, achieving accuracy in terms of the operator norm. Upon encountering a potential saddle p characterized by a small gradient norm- utilize the Hessian inform the gradient estimation over several iterations. This process is analogous to performing stochastic power iteration methods on the Hessian to identify the direction corresponding to the smallest eigenvalue. the Hessian exhibits small enough eigenvalue (say smaller than pa), we demonstrate that this approach facilitates significant drift, effectively enabling successful escape from the saddle point. This idea can also be applied to Ganesh et al. to recover their claimed rate.
(2023)
1.3
OTHER RELATED WORK
A significant body of literature on private optimization focuses on the convex setting, where it is
typically assumed that each function f(;2) convex for any in the universe (e.g.. (Chaudhuri
et al. 2011 Bassily et al. 2014 2019
Feldman al. 2020 Asi et al. 2021 Kulkarni et al. 2021
Carmon et al. al. 2023 Gopi et al.
2023
The tree mechanism, originally introduced by the differential privacy (DP) community (Dwork et al., 2010 Chan et al. 2011) for the continual observation, has inspired tree-structure private optimiza- tion algorithms like Asi et al. (2021); BBassily et al. (2021); Arora al. (2023); Zhang et al. (024) One can also use the matrix mechanism Fichtenberger et al. (2023) which improves the tree mech- anism by constant factor. Some prior works have explored adaptive batch size techniques in optimization. For instance, De et al. (2016) introduced adaptive batch sizing for stochastic gradi- descent (SGD), while Ji et al. (2020) combined adaptive batch sizing with variance reduction techniques to modify SVRG and Spider algorithms. However, these works' motivations and ap- proaches to setting adaptive batch sizes differ from ours. To the best of our knowledge, we are the first to propose using adaptive batch sizes in the context of optimization under differential privacy constraints.
Most of the non-convex optimization literature assumes that the functions being optimized are smooth. Recent work has begun addressing non-smooth, non-convex functions well, as seen in Zhang et al. (2020); Kornowski & Shamir (202T); Davis et al. (2022); Jordan et al. (2023).
PRELIMINARIES
Throughout the paper, we use || represent both the la norm of vector and the operator norm of matrix when there is no confusion.
Definition 2.1 (Lipschitz, Smoothness and Hessian Lipschitz). Let K. C Rd. Given a twice differ- entiable function f K. + I. we say f is G-Lipschitz, for all æ 22 K. [f(x)) f f(z2) s Gl| zell; we say f is M-smooth, for all Z1, I2 E K. (IV)())))(()) we say the function f is p- p-Hessian Lipschitz, ffr all 11, K., we have | -
< M -2lll and
p|| x2|l-
2.1
OTHER TECHNIQUES
As mentioned in the introduction, use the tree mechanism (Algorithm to privatize the algo- rithm, whose formal guarantee is stated below:
Theorem 2.2 (Tree Mechanism, Dwork et al. (2010): Chan et al. (201T). Let Z,,... ....... Zy, be dataset spaces, and X be the state space. Let M, X x2, + X be sequence of algorithms for i [Σ].
Let A: (1:E)) + X be the algorithm that given dataset Z1 z(1-E), sequentially computes X, Σ M, Zz) + TREE(i) for E [Σ], and then outputs X1.X-
Suppose for all E [Σ]. and neighboring Zr. Z E 2(13) [MM Z,)
M1(X1.11, Z!1l & 8 for all auxiliary imputs X14-1 x1-1, Then setfing 4a log(11/) 1/8)
4

---

Published as a conference paper at ICLR 2025
Algorithm is (E,8)-DP. Furthermore, with probability least 1 E for all
[
[TREE()] Vdlog(1/t)o.
Algorithm Tree Mechanism
1: Input: Noise parameter Uree. sequence length Σ
2: Define T := {(u, v) j. j.2 +1, (i+1)-2 20-1 < 88 i
3: Sample and store ((a,e) NO o²) for each (u, E ET
4: for = 1,... do
5: Let (R)E(t) + Σ (w.))ENDEE))) S(n,0)
6: end for
7: Return: TREE(t) for each t e [X]
8: Function NODE:
9: Input: index E [-]
10: Initialize S {} and k =
11: for i= == 1, 1,.... flog Σ while k < t do
12:
Set k = + log -1
13: if K'' < t then
14:
5 SU {(k + 1, k)
15: end if
16:
end for
We also need the concentration inequality for norm- SuanssuaGaussian random vectors.
Definition 2.3 (SubGaussian, and Norm-SubGGausiann, We say random vector E Rd is Sub- Gaussian (SG(()) if there exists a positive constant such that E Eew..-Ba) S ellvul'<e/22, Ve Rd. We say x E Rd is norm-SubGaussian (nSG(C)) if there exists Ç such that Pr[[[x x - Exll 2 S
2c Vt R.
Lemma 2.4 (Hoeffding type inequality for norm-subGaussian Jin et al. (2019) Let æ1. . 2R
Rd be random vectors, and for each i E [k], I; Fi-1 zero-mean nSG where F, is the corresponding filtration. Then there exists absolute constant such that for any 5 0, with
probability at least w., E sill S e. V S log(2d/w)) which means Σ Nq
nSG( / clog(d) (?).
Theorem 2.5 (Matrix Azuma Inequality, Tropp (0122). Consider a finite sequence of random self- adjoint matrices X1, ... Xn with common dimensions d x d and E[X; Fi-1] = 0, X; = A, a.s., Vi. Let x² |1 E AP Let Ei= X,. Then for any Z 0, we have
Pr|||||| 2 1 S d. exp(
802
SOSP
We make the following assumption for main result.
Assumption 3.1. Let G. p. M, B > O. Any function drawn from P is G-Lipschitz, p-Hessian Lip- schitz, and M-smooth, almost surely. Moreover, we are given a public initial point Do such that Fo(xo) inf, (x(x) < B.
We modify the Stochastic SpiderBoost used in Ganesh al. (202)) and state it in Algorithm 3 The following standard lemma plays crucial role in finding stationary points of smooth functions:
Lemma 3.2. Assume F M-smooth and let n 1/M. Let It-1 = It 19:-- Then we have
F(I+1) F(x.) + nllgell |IVF(xx) gell 112 Moreover, if [[())ll y and l|g.
FF(x) & 7/4, we have
F(#+1) =1

---

Published as a conference paper at ICLR 2025
Proof. By the assumption of the smoothness, know
F(æ++1) - + zz) - M
2 2 - xzll
= - - (VF(x)) 9r. 791)
F + + ml[VF(( - gell || - 7 9e. -1
When [[+()])]] 2 7 and l1g. VF(x:)l 4/4, the conclusion follows from the calculation.
Lemma 3.2 shows that one can be able to find the FOSP with inexact gradient estimates as long as the estimated error is small enough. A key challenge in finding an SOSP, compared to an FOSP, is ensuring that the algorithm can effectively escape saddle points. Existing analyses of saddle point escape using inexact gradients are insufficient for our purposes. To address this, we propose new approach that leverages both inexact gradients and Hessians for escaping saddle points. The details are presented the following subsection.
3.1 ESCAPE SADDLE POINT WITH HESSIAN
We present the subprocedure for escaping saddle points in this section, with its pseudocode provided in Algorithmp 2
The core idea is straightforward: given sufficiently accurate estimate of the func- tion's s Hessian, we can apply the power method escape the saddle point. If the Hessian's smallest eigenvalue is sufficiently negative, then after certain number of steps, the iterate will have moved a significant distance, resulting in substantial decrease in function value- indicaand successful escape.
Definition 3.3. We say the estimation (g, H) of the pair of gradient and Hessian is (7, x-acuuraeee point x, if
lgg -
Algorithm Escape from Saddle Point
1: Input: initial point such that ||F(()] & a, (y, x) accurrae estimation pair (g. H) at zo, parameters r,
2: Process:
3: y + 20
4: for t 1,... do
5:
9t-1 =1 [H+H( mo)) + G--1, where G-11 ~ -N(0,0711)
6:
Ft F1-1 -99-11
7:
if 12, - Toll 2 E then
8:
V 5xIz Ft.
9:
Break
end if
11: end for
Output: y
The Gaussian noise 4-11 added in Line B for the privacy purpose. We have the following guarantee of Algorithm 2
Theorem 3.4. Suppose the function F satisfies the Assumption 3.1 and the initial point is saddle point such that [IVF(()) I a and 22 F(F( > -vpala. When a 2 ? log (dBM /tBMMpp). =
[a r Ô(M/ vpn). = < 7. 1/M and Vr/p. then with probability at least 1, the output y satisfies that
F(y) F(xo) < -4,
where +b 12(
3/2 vp (dM
We have the following guarantee on gt!

---

Published as a conference paper at ICLR 2025
Lemma 3.5. With probability at least 1 - 1/2, 2/2. all t [T], have
19--1 vF( s 2y + (x + pE)E.
Let &: (z() 9s denote the difference between the true gradient and our estimation. We use the following standard technical claims connect the distance of the trajectory and the function value change.
Claim 3.6 (Lemma 10 Wang et al. (2019a)) We have
F( - F(x)) S
1I 5nlleel1.
"
4
Claim 3.7 (Lemma 11 in Wang et al. (2019a)) For any t E [T] one has
| zoll2 s (nI((F(z)) - F(x))) + 50n/ lle 12.
In Algorithm 2 halt the algorithm whenever find a point 3i such that || xn /2 2 E. We use the following lemma to demonstrate that large distance at means a large function value decrease Te, that is, it escapes from the saddle point successfully:
Lemma 3.8. Suppose Algorithu 2 halts in advance when condition || - roll 2 E is satisfied, then we have
F(x;) F(ro) S +
Similar previous works Jin et al. prove that we can escape the saddle point with high probability. Fix the sequence of Gaussian noise (CI,-.-,,T
(017): Wang et al. (2019)),
coupling argument to
(r) and ensure l|Gella y for all E [r].
Let y(œ) denote the output y conditional on the first iterate #ı = x. Define the set of stuck region around 30
19:
X (xx) {xr B(xo ng r). and [1x()) zol12 S E),
where (mr). Suppose zo is the saddle point, and let e₁ be the minimum eigenvector of H. We have the following Lemma: Lemma 3.9. Suppose S /2/ For any two points w, B( if μre, with a 2 2/16vd, then at least one of w, u is not in (xx).
With these Lemmas, we can complete the proof of Theorem 3.4 In particular, Theorem 3.4 suggests that, if we meet saddle point, then after the following Õ (V) steps, the function value will decrease by least ((73/2). This means the function value decreases by $2(>2) on average for each step.
3.2 MAIN ALGORITHM
Algorithm follows the SpiderBoost framework. We primarily focus on gradient oracles and esti- mators for simplicity, the Hessian case follows the same principle. Moreover, we allow larger error tolerance for a Hessian estimate He, approximately vp7, compared to the gradient, which is y. We discuss some key variables and parameters in it.
We either query O to estimate the gradient directly or query O₂ to estimate the gradient difference between consecutive points. The term drift controls the estimated error: when drift, is small, A remains a reliable estimator, when drift, exceeds the threshold determined by the parameter k, we obtain a fresh estimate from O,
The term frozen serves technical role in the application of Theorem 3.4 specifically, when a potential saddle point is detected, we invoke the subprocedure described in Algorithm
The variable count tracks the number of saddle point escapes since the last fresh gradient estimate A, and Hessian estimate H,. Once count exceeds the threshold 7, we force fresh query to O and Og to ensure privacy, following the Gaussian Mechanism.
We have the following guarantee of Algorithm 3

---

Published as a conference paper at ICLR 2025
Algorithm 3 Stochastic Spider with Escaping Saddle Point SubProcedure
Input: Dataset D, privacy parameters E, 6, parameters objective function B, M, G, p. param-
eter K, failure probability batch size parameter b, noise parameters Oree: {or
2: set drift, = k. frozen-1 1, A 0, D, D,t 0, EscapcFlag Falsc
3: while t < T and the number of unused functions is larger than b do
// Estimate gradient and Hessian with oracle (Algorithm if drift, 2 K count 2 then
4:
5:
V. = 1 (zz), H, = Os(zt),
6:
drift, 0, frozen, frozen, count 0
7:
else
8:
A, O2( 1-1), V. V.-1 + A. V. V. TREE(1)
9:
A O4 21-1) H4 = 1
end if
//
Escape Saddle Point if EscapePlag True
11:
if V S 7 (BMd/pw) A frozene-1 S () then Set frozen, = r, EscapeFlag True, g V. H Hi, Fanchor 2t, count
12:
count + end if
13:
14:
if EscapeFlag = True then
9: = 9 Hx; Tanchor) + Ec, where & NO(,,
16:
else
9t V. end
Normal gradient descent
18:
if
19:
Te+l = Tt 19h, drift,+1 = drift, + -1g. frozen,-1 = frozen, - 1,
20:
if |r+1 Tanchor E or frozen;41 S 0 then
21:
EscapeFlag = False
22:
end if
23:
t=t+1
24:
end while
25: Return: ",,"""
Proposition 3.10. Under Assumption 3.1 and with oracles such that II VF(x))] S y and H - F2F)lll S 2 2 for any (T). When Oeree oi Valoo(T/1.) r r= O(M /PT),
x S 7. 1/M and = P setting T OB/mm² and supposing it does not halt before completing all T iterations, with probability least Ti, at least point in the output set {zi.... . of Algorithm is Ö Ö(7)-SOSP.
The proof intuition of Proposition 3.10 is, if we do not find an O(7) then on average, the function value will at least decrease by 12 (n/>²)). As know (z < F B, hence O(B/m²) steps can ensure we find an O(7)-SOSP. See the proof of Proposition 3.10 in the Appendix.
It suffices build the private oracles with provable utility guarantees. We construct the gradient oracles below in Algorithm 4
Lemma 3.11 (Oracles with bounded error). Under assumption 3.1
let & > 0 and use Algorithm as instantiations of O2 and O2. Df is i.i.d. drawn from distribution P, we have: (1) for any FG, we have [x:) = F( and
- Gllss.. S
where Si = O(G//og d/b).b) (2) for any 2,, Ft-1, we have E(O, = - (F(x,-1 and (VF VF( Pr o4
where C2 = OMI - for any It. have [x,) (²F(z,) and
Pr[1(Os(zt) - ((F(()))
8

---

Published as a conference paper at ICLR 2025
where Ss = (M v log dd/t/bb.
(4)for any Lt. 1t we have (11, (-F())) (2) and
Pr -z- -V V S
where Ça = - - x1-1 /lg((//)//b/b /b)))
From now on, adopt Algorithm 4 as the gradient oracles for Line and Line respectively in Algorithm and we set 17 = 1 1/M. We then bound the error between gradient estimator V and the true gradient (x:)) for Algorithm 3
Lemma 3.12. Suppose the dataset is drawn ii.d. from the distribution P. For any S S and letting Tr t be the largest integer such that drift,, is set be O, with probability least T for some universal constant C O, we have
G
| - VF-vF( & CC(
(2)
i=++1
M +
11 - ((Fa))
0
Σ 1111;-2-111//00 log (T
(3)
Now, we consider the noise added from the tree mechanism and the noise added the stochastic power method to make the algorithm private.
Lemma 3.13. If we set Orree = 16 + max, | [ log(1/8)/E in the tree mechanism (Algorithm
0 - + max; plla - 2E log(1/5) and use Algorithm 4 as oracles, then Algorithm (E,8)-DP.
b
Algorithm oracles
1: gradient oracle O
2: imputs: 2tz
3: draw a batch size of b among unused functions
4: return: 1 Σ 2
1: gradient difference oracle O₂
2: imputs: Tt, Tt-1
3: draw a batch size of 6, among unused functions
4: return: by Σ. (Vf(z;))) V (z(=-1)))
1: Hessian oracle O₃
2: inputs: It
3: draw a batch size of b among unused functions
4: return: } E. vz
1: Hessian difference oracle O,,
2: imputs: Nt, Tt-1
3: draw a batch size of by among unused functions
4: return: by E. (V2 (z((zz=))))
With the noise added in mind, get the high-probability error bound of gradient estimators V, and Hessian estimators H₃.
Lemma 3.14. In Algorithm batch size b, max [1 x-1gell 2 log(1 log(1/5) 1/8)a / /d, Vt and oeree each [T], we know Algorithm iis (E. DD- and with probability at least 1 1-1, ||g: F <
setting fixed batch size b = GGtd//////////aaaaaaaaaaa Mvd + M² a3/2
pe pa adaptive 1}, E= - M va Õ(M az
pr- |laell
as
o²
Maa
log (og((18)a /d correspondingly according to Lemma 3.13 for
y, H, F(xx)l2 /P7/2, where 7 Ō(a).

---

Published as a conference paper at ICLR 2025
We need to show that can find an ?-SOSP before up all the functions. We need the following technical Lemma:
Lemma 3.15. Consider the implementation of Algorithm 3 Suppose the size of dataset DD can be arbitrarity large with functions drawn i.i.d. from P, and we run the algorithm until finding an O SOSP, then with probability at least 1 Ti, the total number of functions we will use is bounded by
ky ō (BBMM +
Vd
PK
-)
BM
733
M2
Given the dataset size requirement, we can get the final bound on finding SOSP.
Lemma 3.16. With D of size n drawn ii.dd from P, setting K = max{ ava (BGM)
vd
B B3G B
a= a ((BGM) +
BBM
1/2
n/3
TEE
+0 (MB)
BM2
B4/3
B vP
Bpvd MnE))
vn
P/n
G /2/6Vpn
M1/3/n
and other parameters in Lemma 3.14
with probability at least 1 - at least of the outputs
of Algorithm is 7-SOSP, with y O(a).
Combining Lemma 3.13 and Lemma 3.16 privately:
have the following main result for finding SOSP
Theorem 3.17. Given
0,5 S O(1), with gradient oracles in Algorithm
ser-
ling h Gvd/ea + G2 /2/0222 + Mvd
+
M
be max [l.ll.va
x:11g.1 ae a² Maa
pn-llge
.1,
pe
pa
m avd (BGM)
T'= /PT), and Fue or a/Vd, Vt, 3 is (e, 8)-DP, and if the dataset is iidd drawn from the underlying distribution P. at least one of its outputed points is ((a)-SOSP, where
VT/p,T=
3/2
M M
Algorithm
Vd
B3M3G3 +B
BM)
1/2
n/3
NE
+0 + (MB) Vn P/n
VBM
B4/3
B3/GG/6 vp Bpvd
VP Mn//nn
G1/6
Vpn
Mne
Remark 3.18. If we treat the parameters B, M, constants O(1), then we get a Ō(( (212 + n173) as claimed before in the abstract and introduction.
If we make further assumptions, like assuming the functions are defined over a constraint domain X' C Idd of diameter f and we allow exponential running time, can get some other standard bounds that can be better than Theorem 3.17 in some regimes. See Appendix for more discussions.
DISCUSSION
We combine the concepts of adaptive batch sizes and the tree mechanism improve the previous best results for privately finding SOSP. Our approach achieves the same bound as the state-of-the-an method for finding FOSP, suggesting that privately finding an SOSP may incur no additional cost.
Several interesting questions remain. First, what is the tight bound for privately finding FOSP and SOSP? Second, can the adaptive batch size technique be applied in other settings? Could offer additional advantages, such as reducing runtime in practice? Finally, while we can obtain general- ization error bound of /d/n nt using concentration inequalities and the union bound, can we achieve a better generalization error bound for the non-convex optimization?
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory Computing, pp. 1195-1 1199, 2017.
10

---

Published as a conference paper at ICLR 2025
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1): 214. 2023.
Raman Arora, Raef Bassily, Tomás González, Cristóbal A Guzmán, Michael Menart, and Enayat Ullah. Faster rates of convergence to stationary points in differentially private optimization. In International Conference on Machine Learning, pp. 1060-1092. PMIR, 2023.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates 11 geometry. In International Conference on Machine Learning, pp. 393-403.
PMLR, 2021.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight emror bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 464-473, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32,
2019.
Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochas- tic convex optimization. In Conference on Learning Theory, pp. 474-499, PMLR, 2021.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programmingg 184(1):71-120, 2020.
Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 2031-2058. IEEE, 2023.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. A gra- dient sampling method with complexity guarantees for lipschitz functions in high and low dimen- sions. Advances neural information processing systems, 35:6692-6703. 2022.
Soham De, Abhay Yadav, David Jacobs, and Tom Goldstein. Big batch sgd: Automated inference using adaptive batch sizes. arXiv preprint 1610059,,, 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Prec. of the Third Conf. on Theory of Cryptography (TCC), pp. 265-284, 2006. URL htt.htt:/// //xx doi wow.rrrggl... 10. 1007/11681878
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under con- tinual observation. In Proceedings of the forty-second ACM symposium Theory of computing, pp. 715-724, 2010.
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.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SICACT Symposium Theory of Computing, pp. 439 449, 2020.
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine- Fine-grained ror bound on differentially private continual observation. In International Conference on Machine Learning, pp. 10072-10092. PMLR, 2023.
11

---

Published as a conference paper at ICLR 2025
Arun Ganesh, Daogao Liu, Sewoong Oh, and Abhradeep Thakurta. Private (stochastic) non-convex optimization revisited: Second-order stationary points and excess risks. Advances in Neural In- formation Processing Systems, 2023.
Changyu Gao and Stephen J Wright. Differentially private optimization for smooth nonconvex arXiv preprint arXiv:2302.04972, 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM journal on optimization, 23(4):2341-234 2013.
Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian. Private convex optimiza- tion in general norms. In Proceedings of the 2023 Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 5068-5089) SIAM, 2023.
Kaiyi Ji, Zhe Wang, Bowen Weng, Yi Zhou, Wei Zhang, and Yingbin Liang. History History-gradiert gradient aided batch size adaptation for variance reduced algorithms. In International Conference on Machine Learning, pp. 4762-4772. PMLR, 2020.
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, pp. 1724-1732 PMLR, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint 1rXiv:1902.03736, 2019.
Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, and Manolis Zampetakis. Deterministic nonsmooth nonconvex optimization. In The Thirty Sixth Annual Conference Learning Theory, pp. 4570-4597. PMLR, 2023.
Guy Komnwski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Ad- vances in Neural Information Processing Systems, 34:324-334, 2021.
Guy Kornowski, Daogao Liu, and Kunal Talwar. Improved sample complexity for private nons- mooth nonconvex optimization. arXiv preprint arXiv:2410.0588) 2024.
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in subquadratic steps. Advances in Neural Information Processing Systems, 34:4053 2021.
Andrew Lowy, Jonathan Ullman, and Stephen Wright. How to make the gradients small privately: Improved rates for differentially private non-convex optimization. In Forty-first International Conference on Machine Learning, 2024.
Michael Menart, Enayat Ullah, Raman Arora, Raef Bassily, and Cristóbal Guzmán. Differentially private non-convex optimization under the kl condition with optimal rates. In International Con- ference on Algorithmic Learning Theory, pp. 868-906. PMLR, 2024.
Yurii Nesterov. Introductory lectures convex programming volume i: Basic course. Lecture notes, 3(4):5, 1998.
Yurii Nesterov and Boris T Polyak. Cubic regularization newton method and its global perfor- mance. Mathematical programming. 108(1): 2006.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International conference on machine learning, pp. 2613-2621. PMLR, 2017.
Youming Tao, Dongxiao Yu, Xiuzhen Cheng, Falko Dressler, and Di Wang. Private stochastic op- timization for achieving second-order stationary points, 2025. URL httpps://openreviee OpenReview preprint, ICLR submission.
Hoang Tran and Ashok Cutkosky. Momentum aggregation for private non-convex erm. Advances in Neural Information Processing Systems, 35:10996-1 10088, 2022.
Joel Tropp. Usse-ffrinddl tail bounds for sums of random matrices. Foundations of computational mathematics, 0-389-4344 2012.
12

---

Published as a conference paper at ICLR 2025
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pp. 6526-6535. PMLR. 2019a.
Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient privacy-preserving stochastic nonconvex optimization. In Uncertainty in Artificial Intelligence, pp. 2203-2213. PMLR, 2023.
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, 2019b.
Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference Machine Learning, pp. 11173-11182 PMLR, 2020.
Qinzi Zhang, Hoang Tran, and Ashok Cutkosky, Private zeroth-order nonsmooth nonconvex opti- mization. In The Twelfth International Conference on Learning Representations, 2024.
A OMITTED PROOF OF SUBSECTION 3.1
A.1 PROOF OF LEMMA 3.5
Proof. By the concentration of the Gaussian, we know with probability at least 1 - c/2, 11sell2 S for all E [T]. The following proof conditional on the event that ||<:|12 S ? for all
By the Assumption 3.1 for each E [1], we know
11g--1 - VF [ (11-1)) g1g + H (xx-1 - Hо) + 4--1 VF((t-1)ll
S g H xτ) VF 1|5--1
< ||g + H(x--1 - mo) VF +
1gg VF(zo) (- zo) (VF(zt-1) (VFo)-))) +
2 + ||( (= xo)
where z a point in the section between f and xi. Note that ||1 uoll2 < by the algorithm design, hence know - F(2)112 x + pE. Hence, have
1191-1 VF( 12 - 2y (x p=)
This completes the proof.
A.2 PROOF OF LEMMA 3.8
Proof. By Claim 3.6 we have
F(xx) ((x)) <
V (x:)) - 5n Σ le:11
(4)
1=1
Note that 2e = 7 VF(x,) o.), which means nl VF(z,) e:)l22 2 E. By Lemma 3.5 and the preconditions, we know
| < 37.
Hence we know
V F(x;))l 25 2--3-1 V7/2p.
13

---

Published as a conference paper at ICLR 2025
Then by Equation 4 know
F(x+) F(xo) S
VF + 45n
i=1
177 45n
8 p
- 4.
A.3 PROOF OF LEMMA 3.9
Proof. For proof purposes, let (atherr and (atherr be the two trajectories with 21 w and
11 =.u. u.
It suffices to show that
max soll2, || x0llo) 2 E.
(5)
Let 2 = It xy be the difference. Hence we have
2++1 = 1/99-11 1 8--11
=2: H x²/)
=(I - n2)
Recall that pree, Amin (FF S pcc and Amin (H) S /pa/2. Then we know that
|| 2 p1
which means
|| 23
by our choices of parameters. This establishes Equation (5) and completes the proof.
A.4 PROOF OF PROPOSITION 3.10
Proof of Proposition 3.10 By Lemma 3.2 and the precondition that I| VF(xx)) S 7, we know
that, if || ((x))l 2 4y, then F(x++1) F F(ax) < -n 2 Otherwise, ||VF(x;)] < 4y. If
I (x:))l < 4ry but 24 saddle point, then by Theorem 3.4 we know with probability least
F(x44) - F(r,) < -0(73/2//// /
where r Ô PP). Then if none the points in kemm is an O then we know F(aT) F(xo) < B, which is contradictory Assumption Hence at least one point in {x, Jeije should an Ö77--SOSP and hence complete the proof.
A.5 PROOF OF THEOREM 3.4
Now we complete the proof of Theorem 3.4
Proof of Theorem 3.4 By Lemma 3.8 and the definition of X'(xo) (see Equation we have
Pr(F(y) F(x)) < ④ > Pr xı & X(xv)
||cll22 y, Vt + 1/2.
14

---

Published as a conference paper at ICLR 2025
suffices to upper bound Pr 21 E (((o) I l1sell2 S vt.. Let po = 2//4v.. Recall the Gaussian we add d0 two independent first iterates xı and z'j. By the property of Gaussians, we have Pr[ Co Sol pn] 2erf(u7/oo) /² /16.
Vdlou(T/.)) Suppose we add independent Gaussians Ço+ Só and get
Then
2 2/16 Pr [o1, 6o - Sol $ j4y Illll S y. 1c6ll S 7) S 1 L
S 2/44.
By Lemma
3.9 and independence between 2/. have
Pr 2 E (x0o)
1|sell2 S 7, vt s Pr[mi, E x(xo) |1col| S 7, |&G $ 7
$ Pr [le1, Sol S MY | S 7. ll s so]
21/2.
Hence, we show that
Pr(F(u) - F(xo) - - -
B PROOF OF SUBSECTION 3.2
B. PROOF LEMMA
Proof. We only prove the first two items, as (3) and (4) follow from similar arguments. For each data ~ P, we know
E V VF((, 0, [V/()))) VF 2G.
2G.
Then the conclusion (1) follows from Lemma 2.4
Similarly, for each data 2 ~ P, we know
E(V (zz)z) V - - VF(())(- = 0,
(z)))))) V ( -V VF
2M|| zt-1||-
The statement (2) also follows from Lemma 2.4
B.2 PROOF OF LEMMA 3.12
Proof. We consider the case when t = Ti first, i.e., we query O₁ to get V.. Then Equation
follows from Lemma B.11
When > Tt, then for each such that < i S t, we know conditional on V.-1. we have
E[A V (z.,,) - F((x-1)..
That is A, - (z, - 11;; )) is zero-mean and nSG - -;-1 log(dT/()// by
applying Lemma 3.11 Then Equation ( follows from applying Lemma 2.4
The case for Hessian estimation involves some truncation. By Lemma 3.11 we know with proba- Tí, have
bility at least
Pr| V²F 2 6ol L/T,
with 6s = O(M 10M TTg The similar concentration holds for A... We truncate the distribu-
tion of H,, around 2²F(xT)) that is H. Hr, 1 (IH - F(x |l| s (s) It straightforward
to see that
E EH,, V2F(xT)l1 1 Pr|] v2F(I,))) <ldç & Cs/T.
15

---

Published as a conference paper at ICLR 2025
Truncate A in similar way. Then by Lemma 3.11 we can show that
Hr
A
E +
E x
C
M
Σ
p²1|0
x:-111 log (Td/t) S
2
1=++1
i=7+1
(6)
Note that
H +
Σ
-
-
Σ A -
ElH,,
Σ
# (7)
i=
C' logg(Td//
M
p| - x1-1l/////b
2T
1
By union bound, we have
Pr[ T
Σ
A # 5T//2
(8)
1=
Equations
7 7 and 8
complete the proof.
B.3 PROOF OF LEMMA 3.13
Proof. We use the tree mechanism to privatize the gradients if no potential saddle point met, and use the Gaussian mechanism during escaping from the saddle point.
We first show the indistinguishability the gradients. suffices to consider the sensitivity of gradient oracles.
Consider the sensitivity of O, first. Let Oxx))' denote the output with the neighboring dataset. Then it is obvious that
G 5
-
As for the sensitivity of O2, we have
M | xz-1l
V
(02(2,,
b
by
The privacy guarantee of gradients follows from the tree mechanism (Theorem 2.2 which means {V.)e S//2,8/2 {V/). As for the Gaussian mechanism, note that for neighboring datasets with Hessian estimates H, and H; respectively, we know that
p 14 r--1l
||, Hill S b + max
by
Note that force fresh estimate from O3 after escaping the saddle points for times, and in each time, we ensure that |rr,- To I E and H, are used at most I steps, which means the difference is
M + max p||a
II, - (x+ zo)ll2 2| < H Hill || - zull I <(,
b
Then the property of Gaussian Mechanism and composition finishes the privacy guarantee proof.
B.4 PROOF LEMMA 4
Proof. By our setting of parameters, we know EVIT a/p and hence
G
|1:.11, < 2 Va.
+ max
b
b,
M
- xz-1ll
(2EVI7)= < 2ea/Vo Vd.
max
b
b
16

---

Published as a conference paper at ICLR 2025
Then our choice of Uree and de ensures the privacy guarantee by Lemma 3.13
For any t E [T], if in the process of escaping from the saddle point, and gr = g + Ha, and and our parameter settings ensure the accuracy Jt- Consider the other case when 9r V we have
Fauchorr + Et, then Lemma 3.5
1 VF(x)))
& | - Vell
+
V.
VF(2)]]
(I)
(2)
By Theorem 2.2
we know
(1) max [TREE()]] S Lovllog((1) S a dlogg S avllog s ((7).
By Lemma 3.12 and our parameter settings, we have
V VF(x))1 S(a² +
Σ
11 lboel//b)) log(nd/t)
i=++1
S(a² + Σ
Ilael| minf ar
Va. /²/113) log(nd/t)
1=
<(a² + minf
Va V2. a² /k}) log(nd/t)
ae
Sa² log(nd/1).
Hence we conclude that (2) S a (ovoogggd/) Similarly, by Lemma we can conclude that
11, 22 F(x))1 S(pa
Σ p3 /Mb²)))))bb)) log² (nd/c)
i=7et1
S(pa + Σ
p p'lleell (a/pk)) log (nd/L)
i=7e11 Spa (nd/s),
which completes the proof.
B.5 PROOF OF LEMMA 3.15
Proof. By Proposition 3.10 setting ((Brp2 suffices to find an Ö(7)-SOSP. Let {Z1.... , be the outputs of the algorithms, where < T denotes the step we halt the algorithm.
We first show
Iall S Õ(BM/T)
(9)
Denote the set := {il E [t] [[ s M. As S T = O(B/m?)) we know Eies |laill Ö(B/m))
Now consider the set S = [t] \ S denoting the index of steps when the norm of the gradient estimator is large. It suffices to bound Eies- l1gill.-
By Lemma 3.2 we know when |I 7. F(++1) F(x,) < 1119 1//16, and when || < 7, F F(1++) _ F (m:) + 2 Given the bound on the function values, we know
Σ 11.11 < Õ(B/m) SES0
17

---

Published as a conference paper at ICLR 2025
Hence
Σ Ilgil - Eiese 119il1 SES
S Ō
This completes the proof of Equation from the saddle point most O(B/$) O3, is upper bounded by
Moreover, we know the total time that we will escape $). Hence, The total number of functions used for O and
b Eierq Ioail B/ Ö(bBM/s7)-
The total number of functions used for O2 is upper bounded follows:
Σ
pi M
Σ
|alll +T BM 0 Vd
K
+ ps
1 72
+ 73 22
as
a²
72g
This completes the proof.
B.6 PROOF OF LEMMA 3.16
Proof. By Lemma 3.15 and our parameter settings, we need
bBM
BM
Vd
PK
-2)
1
72g
73
M292
First,
bBM
BGMVV KE?
GBBM
+ BMV
BM3
n 2 17(
+ KYB
KT
KAYE
KPy?
(BG
B
VBM
B/33
7 2 Ō
VnE
1/3
Vpn
G1/6
ypr
Secondly,
nz ((BMV - BM
BM
1/2).
mE
Thirdly,
Vd 2 @(BMk\>>) + S{BM
+ B4/3 B133
722
Va 1/2 +
BBMiCi
イイ Õ(VBM
n/3
ne
Fourthly,
Bpx M₂2
> B4/3G//3 p Bpvd + MaE
n > 52(
M2/3g²
B2/3G1/6 vp
Bpvd
M1///
Mns
Finally,
> ((MB/)))++ 7 Ō (MB) 1/2
Vni
Combining these together, we get the claimed statement.
18

---

Published as a conference paper at ICLR 2025
C OTHER RESULTS
The first result is combining the current result in finding the SOSP of the empirical function FD(x) 15 EeeD f(x; (), and then apply the generalization error bound as follows:
Theorem C.1. Suppose D is i.i.d drawn from the underlying distribution P and under Assump- tion 3.7 Additionally assume (G( X + R for some constrained domain X C I2d of diameter
R. Then we know for any point z E X, with probability at least 1 1 L, we have
[z)(2) (bb(z)) < [V (=
Proof. We construct a maximal packing y of O((R/r))) points for X, such that for any x X, there exists point E y such that | - yll S r.
By Union bound, the Hoeffding inequality for corn-subGaussian (Lemma 2.4 and the Matrix Bern- stein Enequality(Theoren 2.5 we know with probability at least 1 T, for all point E y we have
|V (y)) FDb(V)) s O(LValoo(RR//
v=FD(t)) Ó(M d doog R/r)/n). (10)
Conditional the above event Equation (T).. Choosing S min M/p) p) / d/n, then by the assumptions on Lipschitz and smoothness, we have for any E X. there exists E y such that || yll S and
Fx)) FDD()) V1Fp22 + VFD(O)I + (v)) VFb(2))
<b(1.a/m))
Similarly, we can show
[v) v²FD(=)] & Ó(M + pr) Ö(M
The current SOTA of finding SOSP privately of FD from Ganesh et al. (2023), where they can find an (a///dd))///-SSS/ Combining the SOTA and Theorem we can find a-SOSP of Fp privately with
Vd vd 2/3 +
a Ō
ne
If allow exponential running time, as Lowy al. 2024) suggests, we can find an initial point To privately to minmmize the empirical function and then use as warm start to improve the final bound further.
19


Reviews:
[{"review_id": "jWAS9iE9Nu", "reviewer": "Reviewer_3ujF", "summary": "The authors find that finding second-order stationary points privately can be as fast as finding first-order stationary points privately at a rate of $\\tilde{O} (\\frac{1}{n^{\\frac{1}{3}}} + (\\frac{\\sqrt{d}}{n\\epsilon})^{\\frac{1}{2}} )$.", "questions": "Can the authors expand the related work section by briefly comparing this work to the momentum-based variance-reduction methods like [1] and\nDP-SRM ([2])? I think these papers are somewhat relevant.\n\n[1]: Tran, Hoang, and Ashok Cutkosky. \"Momentum aggregation for private non-convex ERM.\" Advances in Neural Information Processing Systems 35 (2022): 10996-11008.\n\n[2]: Wang, Lingxiao, et al. \"Efficient privacy-preserving stochastic nonconvex optimization.\" Uncertainty in Artificial Intelligence. PMLR, 2023.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The authors present in a nice and neat way.\n\n2. This paper studies a timely and interesting problem - finding SOSP privately. \n\n3. The authors introduced simple yet effective tools to solve this problem effectively. Tree mechanism has been applied in many DP papers but this paper illustrates its power when combined with the adaptive batch size. And the analysis part is non-trivial. This technique might be applicable to other private optimization problems.", "weaknesses": "I see no apparent weaknesses in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KbyYPN9L9w", "reviewer": "Reviewer_Yw5T", "summary": "This paper studies privately finding second-order stationary points of stochastic optimization problems. This problem is a relevant to private machine learning. A related problem is privately finding first-order stationary points. First-order stationary points include saddle points and local optima, making them less valuable for machine learning compared to second-order stationary points, which exclude saddle points.\n\nThe paper gives a differentially private algorithm for finding second-order stationary points. Prior state-of-the-art had a rate higher than for first-order stationary points. This work achieves rate-parity between second-order and first-order stationary points under differential privacy.\n\nThe prior state-of-the-art algorithm involves infrequent gradient queries interspersed with many gradient-difference queries. The queries are answered by randomly subsampling the dataset by a fixed-size batch. Gaussian noise is introduced to ensure privacy. A drift variable tracks the total amount of l2-movement of the variable and a fresh gradient query is made when the drift crosses a threshold, which ensures that the gradient estimates do not deteriorate significantly.\n\nThis work improves upon the prior work in two ways. First, the Gaussian noise mechanism is replaced with a correlated noise mechanism that reduces the cumulative noise introduced by successive gradient-difference queries. Second, the batch-size for gradient-difference queries between two points is chosen adaptively in proportion to the l2-distance between the two points. Due to the underlying smoothness assumption, the sensitivity of the gradient-difference queries grows in proportion to this distance. Thus adaptive batch-sizes allows for more targeted noise levels and also tightens the utility-analysis.", "questions": "I was a bit surpised that the private rate only improved from $\\tilde{O}((\\sqrt{d}/\\epsilon n)^{3/7})$ to $\\tilde{O}((\\sqrt{d}/\\epsilon n)^{1/2})$ after what seem at a high level like fairly substantial improvements to the algorithm. Is this bound known to be tight for FOSP?\n\n> In our setting, $\\mathcal{O}_1$ is more accurate but incurs higher computational or privacy costs.\n\nThis point is not entirely clear to me and it seems very foundational to the structure of the algorithm. Why shouldn't we just query $\\mathcal{O}_1$ every time? I assume it is related to the sensitivity of the queries. It would be helpful for the authors to clarify the motivation for using both oracles by explicitly state the tradeoff between using $\\mathcal{O}_1$ and $\\mathcal{O}_2$ in terms of accuracy, privacy cost, and/or computational complexity.\n\n> When the privacy parameter $\\epsilon$ is sufficiently small, we observe that $\\alpha_F \\ll \\alpha_S$.\n\nI am not completely following this either. If $n$ and $d$ are fixed and we take $\\epsilon \\to 0$, then eventually we should have $(\\sqrt{d}/\\epsilon n)^{1/2} > (\\sqrt{d}/\\epsilon n)^{3/7}$. Could the authors explain the regime (in terms of relationships between $n$, $d$, and $\\epsilon$) where the improvement is most significant and clarify whether there are any limitations of their approach as $\\epsilon$ becomes very small?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper proposes a novel algorithm for an important problem in private machine learning. The algorithm improves meaningfully on the previous state-of-the-art in multiple clear ways.\n\nThe writing is generally clear and ideas are easy to follow.", "weaknesses": "My only concern is a lack of experimental results. It would be nice to see a small experiment comparing the algorithm to the prior state-of-the-art in order to give a sense of whether the new algorithm is practical to run or not as well as whether the theoretical improvements actually translate into substantive improvement in the quality of the SOSP. In particular, I would be interested to see how the runtime as well as the $\\alpha$ value of your approach compares to prior approaches on benchmark problem instances of increasing size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FjIkUxFooU", "reviewer": "Reviewer_pqBp", "summary": "This paper improves the theoretical bounds for reaching a Second-Order Stationary Point (SOSP) under differential privacy constraints. By employing an adaptive batch size and replacing the independent Gaussian mechanism with a private tree mechanism, the paper effectively reduces the error in achieving SOSP. Detailed theoretical proofs are provided.", "questions": "A minor question, does the norm in the paper mean $l_2$ norm?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper addresses an important problem by improving the theoretical bound for achieving a second-order stationary point (SOSP) under differential privacy constraints, aligning it with the bound for a first-order stationary point (FOSP). Leveraging the tree mechanism in differentially private continuous observation, which has been shown to achieve asymptotically minimal error, the paper successfully reduces the error for SOSP.  I believe the idea is noval and the contribution is sufficient.", "weaknesses": "1. There is a line of work that further improves the theoretical bound of the tree mechanism, called matrix mechanism [1]. It improves the bound of the tree mechanism by a constant factor. When training a model, it generally works better than the tree mechanism [2]. I would like to hear some discussions about whether using the matrix mechanism can help improve the theoretical analysis.\n\n2. I am confused by how you describe the adaptive batch size, the expression of $b_t$ in Lemma 3.8 depends on $\\tilde{\\Delta}_t$. Is  $\\tilde{\\Delta}_t$ private? If you need to change the batch size based on the dataset, there's a risk of leaking private information when the batch size is not protected. Could you explain how you make the batch size private?\n\n3. As stated in point 2, the notations sometimes confuse me. If would be great if there is a table of notion provided, which would help the paper more readable.\n\n[1] Fichtenberger, Hendrik, Monika Henzinger, and Jalaj Upadhyay. \"Constant matters: Fine-grained error bound on differentially private continual observation.\" In International Conference on Machine Learning, pp. 10072-10092. PMLR, 2023.\n\n[2] Choquette-Choo, Christopher A., Arun Ganesh, Ryan McKenna, H. Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. \"(Amplified) Banded Matrix Factorization: A unified approach to private training.\" Advances in Neural Information Processing Systems 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bLVDSf8N9o", "reviewer": "Reviewer_cUiT", "summary": "This paper presents a new algorithm for private stochastic optimization that builds on the SPIDER algorithm, incorporating a well-known differential privacy technique called the \"tree mechanism\" and an adaptive batch-size approach. The adaptive strategy adjusts the batch size based on a bias-variance criterion. The authors provide proofs showing that their algorithm achieves faster convergence rates to second-order stationary points than previous methods.", "questions": "- The notation $\\mathcal{O}_1$ and $\\mathcal{O}_2$ for the gradient oracles could be confusing, as it resembles the common asymptotic notation $O$. An alternative notation might reduce ambiguity.\n- How do the assumptions in this work compare to those in related papers? A comparison could add useful context.\n- The current approach allows each data point to be seen only in one of the inner loop of the SPIDER algorithm. Could sample complexity be improved by sharing data across outer loops while tracking privacy using composition and subsampling amplification?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The paper provides a theoretical improvement over the existing methods, particularly by achieving faster convergence to second-order stationary points under privacy constraints.\n- The proofs are thorough and well-written, giving strong support to the theoretical claims.\n- The paper gives sound reasons for developing the algorithm, which addresses both theoretical and practical needs in private stochastic optimization.", "weaknesses": "- The structure and flow could be improved, and feels a bit rushed. At times, the paper feels like a sequence of technical lemmas without enough overview or context, which can make it hard to follow.\n- The paper does not include an empirical evaluation of the proposed method. Although the main focus is on theoretical improvement, a comparison with other methods in private stochastic optimization would be helpful to understand the practical performance of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)