Second-Order Convergence in Private Stochastic Non-Convex Optimization
Authors: Youming Tao
Zuyuan Zhang
Dongxiao Yu
Xiuzhen Cheng
Falko Dressler
Di Wang
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
non-convex optimization
saddle points
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We investigate the problem of finding second-order stationary points (SOSP) in differentially private (DP) stochastic non-convex optimization. Existing methods suffer from two key limitations: \textbf{(i)} inaccurate convergence error rate due to overlooking gradient variance in the saddle point escape analysis, and \textbf{(ii)} dependence on auxiliary private model selection procedures for identifying DP-SOSP, which can significantly impair utility, particularly in distributed settings. To address these issues, we propose a generic perturbed stochastic gradient descent (PSGD) framework built upon Gaussian noise injection and general gradient oracles. A core innovation of our framework is using model drift distance to determine whether PSGD escapes saddle points, ensuring convergence to approximate local minima without relying on second-order information or additional DP-SOSP identification. By leveraging the adaptive DP-SPIDER estimator as a specific gradient oracle, we develop a new DP algorithm that rectifies the convergence error rates reported in prior work. We further extend this algorithm to distributed learning with heterogeneous data, providing the first formal guarantees for finding DP-SOSP in such settings. Our analysis also highlights the detrimental impacts of private selection procedures in distributed learning under high-dimensional models, underscoring the practical benefits of our design. Numerical experiments on real-world datasets validate the efficacy of our approach.

Second-Order Convergence in Private Stochastic Non-Convex Optimization
Youming Tao
Zuyuan Zhang
TU Berlin & Shandong University tao@ces-1ad laassslabboorrgr
The George Washington University zuyuan baanaanzzang@guu.. edu
Dongxiao Yu
Xiuzhen Cheng Shandong University xzcheng@sdu. edu. cn
Falko Dressler
Shandong University dxyu@sdu. edu. cn
TU Berlin
dressler@ccs- .rg
Di Wang KAUST
di. wwwg@kaust.edu. edu.
Abstract
We investigate the problem of finding second-order stationary points (SOSP) in differentially private (DP) stochastic non-convex optimization. Existing methods suffer from two key limitations: (i) inaccurate convergence error rate due to over- looking gradient variance in the saddle point escape analysis, and (ii) dependence on auxiliary private model selection procedures for identifying DP-SOSP, which can significantly impair utility, particularly in distributed settings. To address these issues, we propose generic perturbed stochastic gradient descent (PSGD) framework built upon Gaussian noise injection and general gradient oracles. core innovation of our framework is using model drift distance to determine whether PSGD escapes saddle points, ensuring convergence to approximate local minima without relying second-order information or additional DP-SOSP identification. By leveraging the adaptive DP-SPIDER estimator as specific gradient oracle, we develop new DP algorithm that rectifies the convergence error rates reported in prior work. We further extend this algorithm to distributed learning with hetero- gencous data, providing the first formal guarantees for finding DP-SOSP in such settings. Our analysis also highlights the detrimental impacts of private selection procedures in distributed learning under high-dimensional models, underscoring the practical benefits of our design. Numerical experiments on real-world datasets validate the efficacy of our approach.
Introduction
Stochastic optimization is fundamental problem in machine learning and statistics, aimed at training models that generalize well unseen data using finite sample drawn from an unknown distribution. As the volume of sensitive data continues to grow, privacy has become pressing concern. This has led the widespread adoption of differential privacy (DP) [I]], which provides rigorous privacy guarantees while preserving model utility in learning tasks.
In the past decade, significant progress has been made in DP stochastic optimization, particularly for convex objectives g 29 39 43 While convex problems are relatively well understood, non-convex optimization introduces unique challenges, primarily due the presence of saddle points.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Most existing DP algorithms for non-convex problems focus on finding first-order stationary points (FOSP), characterized by small gradient norms 12 54 However, FOSP include not only local minima but also saddle points and local maxima, often leading to suboptimal solutions [2] 42 Consequently, second-order stationary points (SOSP), where the gradient is small and the Hessian positive semi-definite, are more desirable as they guarantee convergence to local minima.
Motivated by this, substantial research has been devoted to finding SOSP in non-convex optimiza- tion 14 24 T0 22 [7]. However, the study of SOSP under differential privacy constraints (DP- SOSP) remains limited. At the same time, distributed learning has become increasingly important for training large-scale models across decentralized edge devices. Yet, no existing work has addressed DP-SOSP in non-convex stochastic optimization under distributed settings. Compared to single- machine setups, distributed learning introduces additional challenges, including data heterogeneity, cross-participant privacy, and communication efficiency.
Limitations in the State-of-the-Art. A notable exception in the study of DP-SOSP for stochastic optimization is the recent work by (30), which injects additional Gaussian noise into the DP gradient estimator near saddle points to facilitate escape. Despite its contributions, this method suffers from two key limitations. (i) Its saddle point escape analysis overlooks the variance of gradients, leading to incorrect error bounds. A direct correction of the analysis would unfortunately yield a weaker type of SOSP guarantee than originally targeted. This because their design relies on additional injected noise beyond the inherent DP noise for escape, highlighting the need for an effective way of exploiting the DP noise already present. (ii) Their learning algorithm outputs all model iterates and guarantees only the existence of a DP-SOSP, requiring an auxiliary private model selection procedure to identify one. While effective in single-machine settings, it faces critical issues in distributed environments due to decentralized data access. In particular, auxiliary private selection introduces non-negligible error and communication overhead, especially when sharing high-dimensional second-order information. These drawbacks also underscore the necessity of new learning algorithm that inherently outputs DP-SOSP without dependence on any additional private selection procedure.
Our Contributions. We refer to Appendix A for more detailed discussions of the limitations outlined above. To address the challenges identified above, we propose generic algorithmic and analytical framework for finding DP-SOSP in stochastic non-convex optimization. Our approach not only corrects existing error rates but also extends naturally to distributed learning. The main contributions are summarized as follows:
1. A generic non-convex stochastic optimization framework: We introduce perturbed stochastic gradient descent (PSGD) framework that employs Gaussian noise and general stochastic gradient oracles. This framework serves as a versatile optimization tool for non-convex stochastic problems beyond the DP setting. A key innovation is a novel criterion based on model drift distance, which enables provable saddle point escape and guarantees convergence to approximate local minima with low iteration complexity and high probability.
2. Corrected error rates for DP non-convex optimization: By incorporating the adaptive DP- SPIDER estimator as the gradient oracle, we develop a differentially private algorithm that achieves a corrected error rate bound of Ó 1773 the suboptimal bound of 0,,
2/5). where n is the number of samples. This corrects reported in [30].
+
cm
Vd 3/T en
3. Application to distributed learning: We extend the adaptive DP-SPIDER estimator to distributed learning. Via adaptivity, our learning algorithm improves upon the DIFF2 37 which only guarantees convergence to DP-FOSP under homogeneous data. In contrast, our method provides the first error bound for converging to DP-SOSP under heterogeneous data: Ō ((ma))77 + is the number of participants and n is the number of samples per participant. Furthermore, we analyze the adverse effects of private model selection, showing that it deteriorates utility guarantees in high- -iah--iimnnionall regimes, thereby highlighting the necessity of our framework.
vdd 2//5). where m evram
Due to the space limit, technical lemmata, omitted proofs, experimental results and broader impacts, conclusions are all included in the Appendix.
2

---

2 Related Work
Private Stochastic Optimization. Differential privacy (DP) has become a erucial consideration in stochastic optimization due to increasing concerns about data privacy. The pioneering work by | established the foundational principles of DP, and its application in stochastic optimization has since seen significant progress. Early efforts primarily focused on convex optimization, achieving strong privacy guarantees while ensuring efficient learning, with a long list of representative works 40 Recent advances have extended DP to non-convex settings, mainly focusing on first-order stationary points (FOSP). Notable works in this area include 52 2). which improved error rates in non-convex optimization with balanced privacy and utility in stochastic gradient methods. However, these works generally fail address the more stringent criterion of second-order stationary points (SOSP). The very recent work [30] tired to narrow this gap, but unfortunately has some issues in their results as we discussed before. Our work builds on this foundation by correcting error rates and proposing framework that ensures convergence to SOSP while maintaining DP.
e.g. [6] 48
47
20
43
[46] [4
5
In non-convex optimization, convergence to FOSP is often insufficient, as saddle points can lead to sub-optimal solutions [21 42.. Achieving SOSP, where the gradient is small and the Hessian is positive semi-definite, ensures that the optimization converges to a local minimum rather than a saddle point. Techniques for escaping saddle points, such as perturbed SGD with Gaussian noise, have been explored in works like 17 and [24] 17 first showed that SGD with a simple parameter perturbation can escape saddle points efficiently. Later, the analysis was refined by [2 Recently, variance reduction techniques have been applied to second-order guaranteed methods These methods ensure escape from saddle points by introducing noise to the gradient descent process. In contrast, the studies of SOSP under DP are quite limited, and most of them only consider the empirical risk minimization objective, such as 446 50 31. Very recently, [30] addressed the population risk minimization objective. but with notable gaps in their error analysis, particularly in the treatment of gradient variance. Moreover, all of these works are limited to the single- machice setting and cannot be directly extended to the more general distributed learning setting.
Finding SOSP.
18 2
Distributed Learning. With the rise of large-scale models and decentralized data, distributed learning has gained significant attention. Methods like federated learning [34 have enabled multiple clients to collaboratively train models without sharing their local data. Recent studies, such as [T6 32 33 have
investigated DP learning in distributed settings, but these works are limited to first-order optimality. While some studies have investigated SOSP in distributed learning, their focus was primarily on ryzantine-fauil tolerance [53], and communication efficiency (36, 71. No effort, our knowledge, has been made to to ensure DP-SOSE in distributed learning scenarios with heterogeneous data. Our proposed framework fills this gap by introducing the first distributed Icarning algorithm with DP-SOSP guarantees while effectively handling data heterogeneity across clients.
3 Preliminaries
Notations. We denote by || the & norm and by A-in(-) the smallest eigenvalue of matrix. The symbol La represents the d-dimensional identity matrix. We use O(-) and Ω(() to hide constants independent of problem parameters, while Ö(-) and 2(-) additionally hide polylogarithmic factors.
Stochastic Optimization. Let f: Rd x Z + R be a (potentially non-convex) loss function, where Rdd denotes the d-dimensional model parameter and E 2 is data point.
The loss function f(::2) is G-Lipschitz. M-smooth, and p-Hessian Lipschitz. Specifically, for any Z and any 22 Rd, we have: (i) (f =) fxz; 2)] < G G||a1 x2
Assumption 1.
(ii) / - V fx=z < M ||=] - r2 ||: (iii) f(= {2)(1=))) S p|| - x2ll-
Let DD denote the unknown data distribution. The population risk is defined as the expected loss: Fo(x) EL- z)] for Vr e d.d When clear from context, we omit D and simply write F(x).
Assumption 2. Let xx denote a minimizer of the population risk and F* = F(x*) its minimum value. There exists U E R such that max, F(x) F < U.
3

---

Let D denote dataset of n i.idd samples from D. The empirical risk is defined as fD(z) = [o EEED fx;; 2). Given access D. the goal is to find an approximate second-order stationary point (SOSP) of the unknown population risk F(.). In general, we have the notion of (ag. Oz (gg ) Definition 1 ((ag. aH)) ) -OOSP). A point is an (ag. az ) of twice differentiable function F(-) if x satisfies [>)l I Og and V Fx)) OO ld-
As shown in 153 Proposition 1]. there exists lower bound of Ö(a. for wh given ag. implying that (a, O ((aa) -SOSP is the best second-order guarantee achievable. Accordingly, we target the notion of a-SOSP in this work, following [30].
Definition (a-SOSP). A point is an a-SOSP of twice differentiable function F(-) if satisfies [[V S a and V²F(z) /vp Ld.
An a-SOSP excludes a-strict saddle points where Fx) - -vpoLa thereby ensuring conver-
gence to an approximate local minimum. Following prior work [3 24 we assume M 2 vpa so
that finding SOSP is strictly more challenging than finding an FOSP.
Distributed Learning. the distributed (federated) learning setting, m clients collaboratively learn under the coordination of central server. Each client j E [m]] has a local dataset D2 of size n, sampled from an unknown local distribution Dj. The population risk for client j is defined as FD, (x) == EgwDylf(a =)] simply F, (x)). The global population risk is defined as the average of the local population risks: (a( m Ejemm] (x)),, or simply F(x).. We allow for heterogeneous local datasets, meaning that the local distributions {Dj)jejm may differ.
Differential Privacy. We aim to find an a-SOSP under the requirment of Differential Privacy (DP), which is referred as an a-DP-SOSP. We say two datasets D and D' are adjacent if they differ by at most one record. DP ensures that the output of the stochastic optimization algorithm on any pair of adjacent datasets is statistically indistinguishabe.
Definition 3 (Differential Privacy (DP) [TI.. Given c, > 0, a randomized algorithm AA: 2 + X is (c, 6D if for any pair of adjacent datasets D' D' Z, and any measurable subset S S X, IP(((D) E S] S exp(e) IP[A(D") E S] + 6.
In distributed learning, we focus on inter-client record-level DP (ICRL-DP), which assumes that clients do not trust the server or other clients with their sensitive local data. This notion has been widely adopted in state-of-the-ee distributed learning works, such as 16 32 33.
Definition 4 (Inter-Client Record- DP (ICRL-DP)). Given 8 0, randomized algorithm
A: 2m + X' satisfies (e, ò)-ICRL-DP if, for any client j E [m]] and any pair of local datasets D, and DJ, the full transcript of client j's sent messages during the learning process satisfies 3 assuming fixed local datasets for other clients.
Variance Reduction via SPIDER. Since the population risk F(.) is unknown, standard SGD approximates the true gradient VF(xx-1) iteration / using stochastic estimate Jt- However, such estimates often exhibit high variance, degrading convergence. The Stochastic Path Integrated Differential Estimator (SPIDER) [3] mitigates this variance using two gradient oracles O and O2. For mini-batch B, at iteration f, we define
( 1, B,) = Vfs, (2,-1), O2(x1-1, B,) = fa, Tf,((x12)
SPIDER queries O every y iterations to refresh the gradient estimate. Between these updates, it uses O₂ to incrementally refine the estimate:
(1t B.),
if (1 1) mod p = 0,
9t 9--1 + O2(11-1,, 11- Bi), otherwise.
For smooth functions, the variance of O2 B,) scales with || - 2z 2z-2 which is typically small when updates are minimal. This allows SPIDER to achieve low-variance gradient estimates while maintaining accuracy.
We choose SPIDER because it achieves state-of offtt--o-the-arr the-art error rates for privately finding first-order stationary points (DP-FOSP) 2]. Our goal is to investigate whether its variance reduction can extend to DP-SOSP. Importantly, the insights in this paper are not specific to SPIDER; they also apply to other reduced methods such as STORM 9 or SARAH [8). However, since these algorithms are conceptually similar, no significant improvement is expected from substituting them.

---

4 Our Generic Perturbed SGD Framework
In this section, we introduce generic frame- work for finding an a-SOSP of the population risk F-(-) by escaping saddle points. Our frame- work is Gaussian perturbed stochastic gradient descent method, denoted Gauss-PSGD.
Algorithm 1: Gauss-PSGH Gaussian Perturbed Stochastic Gradient Descent Input:
Failure probability w, initial model zo. learning rate 1), # of escape repeats Q, model deviation threshold R, # of escape steps T
4.1 Gradient Oracle Setup
< O;
while true do
Since (.D(.) is unknown, direct gradient de- scent is infeasible. As in standard stochastic op- timization, we assume access to a stochastic gra- dient oracle Is that approximates VFD (x; at iteration t. For example, It can be computed as an empirical gradient over a mini-batch B, sam- pled from D. We model the oracle as
t 2--1 + 1;
Gr L_GGraddOracll
| - 3x then
/* Saddle point escape */
E 1, 3 t- 1;-1, esc false;
for q + 1. do
t 2t 1 I;
= VF(+=-1) + Gt.
(1)
for 1,. , do
where Ç represents inherent gradient noise. Fol- lowing 24 30), we assume Çe no) where
10
P [_Ga__Oracle Oracle(*)
2, f- x2 17 9
nSG denotes a norm-sule waa--suu---Gaae distribution (Definition 7 in Appendix BB.
if It . 2 R then
13
esc <- true;
To enable saddle point escape, introduce an additional Gaussian perturbation to form a per- turbed gradient oracle gr:
break;
else
16
L ++
+ E. VF( + G. + E..
17
esc true then break;
where & ~ N(0, I2). We define the effective noise magnitude in ge
if esc false then return F4-1
s = 02 r
20
21 else
The model update then performed by
/* Normal descent step */
22 Ht + It 17- 9t;
Dt It-1 n/t-
(4)
Our problem setting fundamentally differs from that in [24]. In their setting, the target error a is given, and the perturbation magnitude is determined accordingly. In contrast, in our privacy- constrained setting, r is dictated by the privacy parameters (e, 5), and the goal is to achieve the smallest possible under this constraint. Crucially, their parameterization /////Vdd, This non -onverertiblle relationship
=(V(aa + /3/2//d) implies that
depends both and determined by max(o/ between r and a makes their setting incompatible with ours. First, under DP constraints, r is determined by (c and may be smaller than a/ /á d in weak privacy regimes, violating the required lower bound. Second, because and a not uniquely determined by each other, it is not meaningful to directly translate their error bounds into our setting. Thus, their analysis and results cannot be directly applied our problem.
4.2 Our Approach: A General Gaussian- SGD Framework
We present our Maauss-PSGD framework in Algorithm T which finds an a-SOPP with high probability Caussian-perturbeed
at least 1 As specified in 2). employ a general Gaussian- perturbed stochastic gradient oracle, denoted as P ___ra_d_rraaee [0l_0rralee* *) in steps 4 and 10, where abstracts the specific arguments required by the oracle implementation. This abstraction allows Gauss-PSGD serve flexible optimization framework for non-convex stochastic problems, applicable beyond the differential privacy (DP) setting.
At each iteration, the gradient estimate ÿr computed by P P_Crad_Oracleff Draclee*). and the model parameter is updated via the gradient descent step in 4). The algorithm proceeds until it encounters
5

---

This point ğ may lie near a saddle point with large negative eigenvalue of the Hessian. To escape such a saddle point, the framework enters an escape procedure (steps 6-20), which performs Q rounds of T-desceet (steps 9-16).
point λ satisfying |l I 3x, where is specified in ().
In each round, the algorithm executes at most T perturbed SGD iterations starting from .. If at any iteration we observe |2, il || 2 R for threshold R (specified in (5), indicating that the iterate has moved sufficiently far from ā. we declare that the algorithm has successfully escaped the saddle point and resume normal PSGD from It. If no such movement is observed after Q rounds, we declare T an a-SOSP of the population risk Fb(.) and output Ø. The repetition over Q rounds ensures a high probability of escape: as we will prove later, each I -edeccent succeeds in escaping a saddle point with constant probability, and multiple repetitions reduce the failure probability any desired level.
central innovation of our framework is using model drift distance as the escape criterion (step 12), replacing the function value decrease criterion used in [22 24 This design enables the algorithm to identify an SOSP with high probability during the optimization process itself, eliminating the need for an auxiliary private model selection step. Our key insight as follows: escaping a saddle point not only causes a decrease in the objective function (22 (2) but also induces a substantial displacement of the model parameter beyond a threshold R. Shifting from monitoring function values to tracking parameter movement is critical in population risk settings, where the objective function is unknown and function evaluations are unavailable, unlike in empirical risk minimization [22.. However, the model iterates and their deviations are observable. By leveraging this property, our framework can directly output an SOSP, rather than merely guaranteeing its existence among the iterates.
4.3
Main Results for Gauss- PPGD Framework
We begin by introducing the parameter setup and notations used throughout the analysis:
& = sHl
X = AVCsp²y
a
4X
a
8
a
pa
(5)
r
R
/ pa
1.5
8
M
where 8 is sufficiently large absolute constant to be chosen later, and is a logarithmic factor:
9d
4C1/1 sqp
160
+b
log 47 1/4
p max
8
log
CV/Any/pp
log
TTT
2
1
(6)
Here C an absolute constant that may change across expressions. The rationale behind these parameter choices is further discussed in Remark following Theorem Let 7 denote saddle point of the population risk F(-), and H == v F²F(T. Let Umin be the eigenvector corresponding to Amin(HH (H), and P P-rmin be the projection onto the orthogonal complement of Umin. Set -Amin
Definition 5 (Coupling Sequence). Let {æ;} and {x() be two PSGD sequences initialized at f. We say they are coupled if they share the same randomness for P P-vmi & and Çe at each iteration f, but use opposite perturbations in the Umin direction: "Hin = - - g!
The following lemma ensures that under I -edesceet, at least one of the coupled sequences escapes the saddle point with constant probability (proof in Appendix[c.I]
Lemma 1 (Escaping Saddle Points). Let {x;} and {x]} be coupled PSGD sequences initialized at such that | [+)]] S a and Amin A (V2 < par. Then, with probability at least 1/4, there exists I such that max f||x, 11, |2 =|I R.
From this, we immediately obtain corollary that applies to any PSGD sequence:
Corollary 1. For any PSGD sequence {a:} starting at ā with VF < a and Amin Aonin(V* (V²F(T)) < -ypar, with probability at least 1/8, there exists < such that I - x > R.
To ensure high-probabille escape from a saddle point, we repeat P-descent for Q rounds: Lemma 2 (Escape Amplification via Repetition). Given any we E (0, 1), repeating -edescent 26 log( L) rounds ensures escape with probability at least wp.
independently for Q 3

---

The proof is deferred to Appendix C.2 We now analyze the total number of PSGD steps needed for convergence. Let Pt == Se & denote the combined noise in the gradient estimate. Lemma 3 (Descent Lemma). For any to. the following holds:
F(r F 5 2
VF (Zto+ )l + Σ
P
(7)
1=1
Since it can be bounded with high probability, have: Corollary 2. For any lo and some constant with probability at least -
F( F(I()) - 1
V (F(t crpb + 1).
(8)
Proofs of Lemma and Corollary Mare in Appendix C.3 and C.4 These imply that large gradients
lead to rapid function decrease. We next show in Lemma that successful saddle point escape via l'-descent leads to a significant decrease in function value, whose proof is in Appendix C.5
Lemma 4 (Value Decrease per Escape). Let a -edescent starting from Ito succeed after 7 steps. With probability at least -ee F(xt++)) F(x+)) S
$
We bound the total number of PSGD steps required for convergence, based the following estimate:
Lemma 5 (Gradient Estimate Error Bound). With probability at least 1 - w/2, for all E [T],
|| S / log
Sx
Lemma 6 (Maximum Number of Descent Steps). Given failure probability w, set Q 16. (FF
26 log
Gauss-PSGD returns a-SOSP within at most ((1/a2.5 PSGD steps.
x3
Proofs of Lemmas 3 and 6 are in Appendix C.6 and C.7
respectively.
Remark 1 (On Gradient Complexity). While Lemma appears to improve gradient complexity from O(1/a²) in [24] to O(1/a2.5), the two results are not directly comparable. In [24], the error target is treated as an input and can be arbitrarily small, with gradient variance a typically treated as constant. In contrast, in our setting, the perturbation and variance are fixed by privacy constraints, and a emerges as a function of these. Thus, our gradient complexity fundamentally depends on a and r, though express it in terms of for clarity.
Combining all the above, we obtain the final convergence guarantee:
Theorem 1 (Convergence Guarantee of Gauss-PSGD). Let Assumptions and 2 hold. For any failure probability w E (0, 1), using the parameter settings in ( and setting Q
26 log (F, F*)
e then with probability at least - w, Gauss -PGD (Algorithm re-
5
turns a-SOSP of F-),, where 4x, within most 2(1/22.5) PSGD steps.
Remark 2 (On the setting of parameters). The parameters introduced in (5) are chosen in accordance with our convergence and privacy analysis. Specifically, the escape threshold X matches the gradient estimation error, ensuring uniform expected decrease in the objective value per PSGD step (cf. Blad Lemma (). The model drift threshold x: balances the cumulative error from the gradient
oracles O and Oz, while the maximum drift threshold R. and maximum escape steps I jointly control the curvature-dependent term (t) and keep the stochastic gradient noise PPgg(t) bounded
(see Eq. (41) and 43 Finally, the repeat number Q is chosen to grow logarithmically in the failure probability parameter to amplify the overall success probability, as established Lemma 2
Rectified Error Rate for finding SOSP in DP Stochastic Optimization
5.1 Adaptive Gradient Oracle: Ada-DP-SPIDO
In this section, we derive the upper bound on the error rate for DP stochastic optimization by instantiating the Causs-PSGD framework with specific gradient oracle. We adopt an adaptive version
7

---

of the DP-SPIDER estimator, referred to as Ada -da-DP-SPIDER which is presented in Algorithm 2 This adaptive version refines the original SPIDER by dynamically adjusting gradient queries based on model drift. Unlike standard SPIDER, which queries On at fixed intervals and may suffer from growing estimation error over time, Ada-DD -P--SPIDER tracks the cumulative model drift defined as
drift:
Σ (=T(()
| - 11,
where r(t) is the last iteration at which the full gradient oracle Or was queried.
The intuition that, for smooth functions, the error of O2, which estimates ( (F(+ 2). is proportional to || -r--lll- When the model drift is small, O₂ remains accurate, allowing for continued use to reduce variance (steps 9-11). However, when the drift becomes large, further use of O2 can accumulate significant errors. To mitigate this, the algorithm triggers fresh query to O (steps 4-7). A threshold x is used in step to determine when the drift is large. This enables adaptive switching between oracles based on the model drift, ensuring the total error remains well controlled.
Our approach differs fundamentally from that of 30 In their method, in addition to using model drift to trigger O1, they also invoke O1 when approaching potential saddle points and inject an additional Gaussian noise on top of the DP gradient estimator to escape. To prevent excessive noise injection, they introduce a Frozen state to restrict how frequently this occurs. In contrast, our method leverages the inherent Gaussian noise from the DP gradient estimator for saddle point escape and uses model drift as the sole trigger for querying O1 This results in simpler, more efficient estimator without auxiliary state tracking or redundant noise injection.
5.2 Error Rate Analysis for DP-SOSP with Ada-DP-SPIDER
To minimize the error rate for DP-SOSP using Ada-DP-SPIDEE we must carefully tune algorithmic parameters, including the mini-batch sizes 61. b2, and the drift threshold k. These parameters directly influence the gradient estimation error, which, according to Theorem I dominates the learning error. The following lemma characterizes how these parameters affect the estimation quality:
Lemma 7. Let Assumption] 1
hold. For all & [7]. the gradient estimate ÿt given by
satisfies: a S O
log" log" d k6 bi
S O (V
G (1/(1/))
M (og(1/))
by
The proof is given in Appendix D.1 To ensure that b and by remain valid mini-bater sizes under fixed sample budget, we must control the number of times O₂ is queried. Lemma bounds the count:
Lemma 8. Let Assumption I and 2 hold. Define T = {t E [7'] drift, xc as the set of rounds
where the drift exceeds the threshold K. With high probability (as in Theorem D. IT S O (UT/K) k)).
Proof is in Appendix D.2 Guided by Lemmas 7 and 8
we now derive the error bound for via appropriate choices of b1, b2, and и: in Theorem The proof is provided in Appendix D33
Theorem 2. Let Assumption and hold. Define by 20n by
waxx and 20
@2/221//22/22 (24/15,0/5po (ne)44
8/15 Then, running Gauss-PSGD with gradient oracle in-
max
stantiated by Ada-DP-SPIDER ensures (e, 8)D for constants c1. C2 and returns an a-SOSP with a a=Ō
2/5
Va
+
1173
Remark 3 (No Cyclic Dependency Among Parameters). All algorithmic parameters consistently defined in terms of the problem parameters n. d, and e. Specifically, Gauss-PSGD parameters such as the step size 77 and the noise scale depend on the target error a (see (5)). and the gradient oracle parameters bj and by are defined through y and X. and thus also indirectly depend on a. In the proof of Theorem [] by utilizing the relationship a = 0(vo2 + rdd), we obtain the closed-form expression of a that depends solely the problem parameters n, d. and e. As a result, all algorithm parameters are ultimately determined by n, d, and e, and there is no cyclic dependency in the parameter design.
For clarity, the bound stated here omits constant factors stemming from the Lipschitzness, smoothness, and Hessian Lipschitz assumptions. The complete expression, including these constants and their dependencies, is provided in the proof in Appendix. The same convention applies to Theorem g
8

---

Algorithm 2: Ada-DP-SPIDER
Algorithm 3: Distributed Ada-DP-SPIDER
Input: DP budget and horizon T, model iterates 1 drift threshold
Input: DP budget e and 6, horizon T. model iterates {24-1 drift threshold
4 drift + K;;
4 1, drift <-
2 while 1 < T'
while < do
3
if drift then for every client j in parallel do Sample mini-batch BJ of size b from Dj; Sample
if drift 2 then
/* Using oracle O₂ */
Sample mini-batch B, of size by from D; Sample
G log La); b,
EAe ~ N/0,
Go La):
& NO
Dife
Ú3.t t O ( B,,) + E9,i
91 + (1 BB) Exi drift + 0:
Send gy.e to the server;
7
drift c- 0:
else
10
else
/* Using oracle O2 // Sample mini-batch B, of size 12
for every client i in parallel do Sample mini-batch Bj, of size b2 from Dj;
9
b2 from D;
Sample & ~NO
13
Sample Ej,t ~ NNO,
M log 6
|| - 2 11);
M log 2 1 II
C2 life
14
Ij.t - -
11
9. + 91-1 O2 t Bi) Eei
O2 02(21-1,22-22 B,,)) En.
15
Send $g.e to the server;
drift drift + 1
9e - 1 2/=1 9j.
13
+ 1;
drift <- drift + 17 19 11:
Output: 91.9e 12.9...... gr
18
t t + 1;
Output: 91, .9T
Extension to Distributed SGD
By adapting the centralized gradient oracle Ada-DP-SPIDER (Algorithm 2 the distributed setting, we obtain Distributed Ada-DP-SP SPIDER (Algorithm 3 enabling our Gauss-PSO -PCD framework to extend seamlessly to distributed learning scenarios. The primary difference lies in the computation and communication scheme: in the distributed variant, each client performs local gradient estimation with private noise and communicates the privatized estimate the server, which then aggregates the results. This avoids centralized access to raw data while still leveraging collective information.
The learning algorithm using Distributed Ada-DP-SPIDD can be viewed of the DIFF2 algorithm [37]. which uses standard SPIDER and limited to convergence to DP-FOSP under homogeneous data. To the best of our knowledge, method is the first achieve convergence to DP-SOSP in a distributed setting with heterogeneous data.
adaptive extension
Following the same analytical strategy as in Section 5 we first quantify in Lemma 9 the gradient estimation quality the distributed case. The proof is provided in Appendix E.
Lemma 9. Let Assumption
[ hhold. For all E [T], the distributed Ada-DP-SB IDER ensures that the
(1
gradient estimate J satisfies a S O G log? d +
M² log" m-b2
G² Ing m.63.3
log mibjee c
K
+
m-b;
Based this, derive the error bound for in the distributed setting. The proof is in Appendix E.2
Theorem 3. Let Assumption and hold. Define
20 by
wix² 20
and
(G8/2/11/2 1/22
//4/15,0/5 8/15 Then, running Gauss- with gradient oracle instanti-
max
[67 M/4/10 (v/mee)
ated by distributed dda-DP-SPIDDE ensures (e, -IRCLDD for some constants çı, C2, and returns 2/5
an a-SOSP with a δ [man]1/3 +
Vmne

---

Algorithm 4: Private Model Selection in Distributed Learning
Input: Model iterates { DP budget ć
for & < 1,... .T do
2
for every client j in parallel do
Compute VFJ + fss (x+) + 0i,,, where O, ~ N (0,
G nee
Compute (x.) + v (Ix) HHH,, where Hj is symmetric matrix with its upper triangle (including the diagonal) being i.i.d. samples from NN (0, M (1/()/)) and each lower triangle entry is copied from its upper ".e"
triangle counterpart:
Send (x,) and v F2 F2(,), to the server;
(x(x)) Ejn (ar( V in Σラ= (mr)(
if (VF(()) aat Glog(Bd) /V (og(1/5) 1og(16/w") and
Vmnn
Vinc
Amin (v2F(a)))
Vpai M
log(8d/w/)
Mdy log((1 log (32/w")
then
778
v ymnc
Return St.
Remark 4. The error rate shown in Theorem Baemmmmihhhhhi highllgght the collaborative synergy among clients, indicating the learning performance benefits from distributed learning. Specifically, the first non- private term of a exhibits a linear dependence on before n,, while the second term, which accounts for the privacy cost, demonstrates a square root dependence v /mn before n. This separation reflects the impact of data heterogeneity in distributed setting. The benefit of distributed collaboration under DP constraints is consistent with prior results in heterogeneous federated learning [6].
We conclude by demonstrating the advantages of our Gauss framework in distributed learning by eliminating the need for separate private model selection procedure. Without the guarantee of directly outputting an a-SOSP, one must resort to evaluating all model iterates generated during the learning process and privately selecting an approximate SOSP from them. As discussed in Ap- pendix A the AboveTThresee Threshlld mechanism used in 30 for the single-machine case is not applicable distributed settings due to decentralized data access. To overcome this, we adapt [66 Algorithm 5] to the distributed setting, resulting in Algorithm 4 In this scheme, each client computes privatized gradients and Hessian estimates using additional local data, which are then aggregated by the server to evaluate the stationary point conditions. Suppose distributed learning algorithm produces sequence (æx hejrr that contains at least one a-DP-SOSP. The following result characterizes the quality of the point selected by Algorithm 4 whose proof is provided in Appendix E.3
8d then Theorem 4. Algorithm satisfies J-CRLL-DL Let Assumption 1 hold and mn log of with probability least 1- w/, there exists a-SOSP xP E {0t an a SOSP with a' Ö (o++ Vman
then the selected point xo is
d²
Vmn
Vmnnea37
Remark 5. To ensure that the selected model's eтror a' does not exceed the training error a, the da following must hold: Vmmnes77 "mmnea77 377 <Ō(a). This implies a constraint on the model dimension: d < min mnin((mmmne))) (aammnn))((mm))))). (vmnc)6/133. Thus, in high-dimensional regimes, private model selection degrades the overall error rate, marking the limitation of selection-based approaches.
Va
Remark The error bound a' in Theorem can be improved by estimating the smallest eigenvalue of the Hessian via Hessian-vector products using iterative methods such as the power method [26].
This reduces the dimensional dependence in the noise scale from O(d) to O(vd). However, the remaining Vd factor is sill problematic in high dith-immenionall settings. In contrast, in the single-maching case, private model selection only requires perturbing sealar quantities, making the error independent of dimension, preserving the error guarantee of the learning algorithm. In distributed settings, sharing perturbed vectors becomes unavoidable. This emphasizes the necessity and superiority of our Gauss-PSGn framework that inherently avoids the need for any separate model selection step.
10

---

Acknowledgments and Disclosure of Funding
Youming Tao was supported in part by the National Science Foundation of China (NSFC) under Grant 623B2068. Dongxiao Yu is supported in part by the Major Basic Research Program of Shandong Provincial Natural Science Foundation under Grant ZR2025ZD18. Xiuzhen Cheng is supported in part by the Major Basic Research Projects of Shandong Natural Science Foundation under Grant ZR2022ZD02. Di Wang is supported part by the funding BAS/1/1689-01- and funding from KAUST Center of Excellence for Generative AI, under award number 5940.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages 308-315 318, 2016.
[2] 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, pages 1090-1092. PMLR, 2023.
[3] Dmitrii Avdiukhin, Michael Dinitz, Chenglin Fan, and Grigory Yaroslavtsev. Noise all you need: Private second-order convergence of noisy sgd. arXiv preprint 1..iv:2400006878 2024.
[4] 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.
[5] 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-993 -7-9329, 2021.
[6] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464 473. IEEE, 2014.
[7] Sijin Chen, Zhize Li, and Yuejie Chi. Escaping saddle points in heterogeneous federated learning via distributed sgd with communication compression. In International Conference on Artificial Intelligence and Statistics, pages 2701-2709 PMLR, 2024.
[8] Christopher A Choquette-Chore Chhoe,, Arun Ganesh, and Abhradeep Thakurta. Optimal rates for dp-sco with a single epoch and large batches. arXiv preprint arXiv:2406.0274 027111 2024.
[9] Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction non-convex sgd. Advances in neural information processing systems, 32, 2019.
[10] Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pages 164. PMLR, 2018
[11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[12] Cynthia Dwork, Aaron Roth, et The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3 11:211 407, 2014.
[13] 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.
[14) Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory, pages 1192-1234, PMLR, 2019.
11

---

[15] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, pages
2020.
[16] Changyu Gao, Andrew Lowy, Xingyu Zhou, and Stephen J Wright, Private heterogeneous federated learning without a trusted server revisited: Error-optimal and commumication-effeeeeeec algorithms for convex losses. arXiv preprint wxxv:2447.09690 2024.
[17] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle online stochastic gradient for tensor decomposition. In Conference learning theory, pages 797-842.
PMLR, 2015.
[18) Rong Ge, Zhize Ii, Weiyao Wang, and Xiang Wang. Stabilized svrg: Simple variance reduction for nonconvex optimization. In Conference on learning theory, pages 1394-1448. PMLR, 2019.
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, In Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
[20] Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41 ACM SIGMOD- SICACT-SIGAI Symposium on Principles of Database Systems, pages 227-236, 2022.
[21] Prateck Jain, Chi Jin, Sham M Kakade, and Praneeth Netrapalli. Computing matrix squareroot via non convex local search. arXiv preprint
2015.
[22] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International conference machine learning, pages 1724-1732. PMLR, 2017.
[23] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. short note concentration inequalities for random vectors with subgaussian norm, arXiv preprint arXiv:1902.037366 2019.
[24] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 18(2):1229, 2021.
[25] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[26] Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. 1950.
[27] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
[28] Zhize Li. Ssrgd: Simple stochastic recursive gradient descent for escaping saddle points. Advances in Neural Information Processing Systems, 32, 2019.
[29] Daogao Liu and Hilal Asi. User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates. In International Conference on Artificial Intelligence and Statistics, pages 4240 4248. PMLR, 2024.
[30] Daogao Liu, Arun Ganesh, Sewoong Oh, and Abhradeep Guha Thakurta. Private (stochastic) non-convex optimization revisited: Second-order stationary points and excess risks. Advances in Neural Information Processing Systems, 36, 2024.
[31] Ruixuan Liu, Yang Cao, Hong Chen, Ruoyang Guo, and Masatoshi Yoshikawa. Flame: Differ- entially private federated learning in the shuffle model. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8688-8696, 2021.
[32] Andrew Lowy, Ali Ghafelebashi, and Meisam Razaviyayn. Private non-convex federated learning without a trusted server. In International Conference on Artificial Intelligence and Statistics, pages 5749-5786. PMLR, 2023.
12

---

[33] Andrew Lowy and Meisam Razaviyayn. Private federated learning without trusted server: Optimal algorithms for convex losses. In The Eleventh International Conference on Learning Representations, 2023.
[34] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication ceanunication-effiieent efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[35] Frank D McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the 28th ACM SIGMOD International Conference on Manage- ment of data (SIGMOD), pages 19- 19-30, 2009.
[36] Tomoya Murata and Taiji Suzuki. Escaping saddle points with bias-variance reduced local perturbed sgd for communication efficient nonconvex distributed learning. Advances Neural Information Processing Systems, 35:5039-5051, 2022.
[37] Tomoya Murata and Taiji Suzuki. Diff2: Differential private optimization via gradient differ- ences for nonconvex distributed learning. In International Conference on Machine Learning. pages 25523-25548, PMLR, 2023.
[38] 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, pages 2613-2621. PMLR, 2017.
[39] Jinyan Su, Lijie Hu, and Di Wang. Faster rates of private stochastic convex optimization. In International Conference on Algorithmic Learning Theory, pages 995-1009 PMLR, 2022.
[40] Jinyan Su, Lijie Hu, and Di Wang. Faster rates of differentially private stochastic convex optimization. Journal of Machine Learning Research, 25(114):1-41,
[41] Jinyan Su, Changhong Zhao, and Di Wang. Differentially private stochastic convex optimization in (non)-euclidean space revisited. In Uncertainty in Artificial Intelligence, pages 2026-2035. PMLR, 2023.
[42] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 2379 2383. IEEE, 2016.
[43] Youming Tao, Yulian Wu, Xiuzhen Cheng, and Di Wang 0015. Private stochastic convex optimization and sparse learning with heavy-tailed data revisited. In IJCAI, pages 3947-3953, 2022.
[44] Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of compula- tional mathematics, 12:389-434, 2012.
[45] Roman Vershynin. High-dimensional probability. University of California, Irvine, 10:11, 2020.
[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-6553 6636-6535.00 PMLR, 2019.
[47] Di Wang, Marco Gaboardi, Adam Smith, and Jinhui Xu. Empirical risk minimization in the non-interactive local model of differential privacy. Journal of machine learning research, 21(200):1-39, 2020.
[48] Di Wang, Marco Gaboardi, and Jinhui Xu. Empirical risk minimization in non-interactive local differential privacy revisited. Advances in Neural Information Processing Systems, 31, 2018.
[49] Di Wang, Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, pages 10091- PMLR, 2020.
[50] Di Wang and Jinhui Xu. Escaping saddle points of empirical risk privately and scalably via dp- trust region method. In Machine Leurning and Knowledge Discovery in Databuses: European Conference, ECML, PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings, Part III, pages 90-106. Springer, 2021.
13

---

[51] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
[52] Hanshen Xiao, Zihang Xiang, Di Wang, and Srinivas Devadas. A theory to instruct differentially- private learning via clipping bias reduction. In 2023 IEEE Symposium on Security and Privacy (SP), pages 2170-2189. IEEE, 2023.
[53] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Defending against saddle point attack in byzantine-robust distributed learning. In International Conference Machine Learning, pages 7074-7084. PMLR, 2019.
[54] 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 1350,
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the main contributions-namee the development of a PSGD-based framework that corrects prior analytical errors, eliminates reliance private model selection, and extends distributed learning with heterogeneous data. We also provide list of our core contributions explicitly our introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide the limitation discussion in Section H the Appendix, where we highlight the theoretical assumption of unbiased gradient oracles and discuss its potential divergence from practical DP optimizers. We also outline the challenges and directions for extending the framework to handle biased gradient estimates.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
15

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We state all assumptions for our theoretical results in Section 2. For each theoretical result (lemma, theorem, etc.), we explicitly indicate the assumptions relies and provide complete proof, with the location of each proof clearly referenced in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
We provide comprehensive description of our experimental setup, including running environments, datasets, learning models, hyperparameter settings, and evaluation metrics, in Section F of the Appendix. This ensures that the main experimental results are reproducible and support the core claims of the paper.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
16

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The datasets used in experiments are publicly available. While code is not yet released at the time of submission, we plan to open-source it with detailed instructions reproduce all experimental results as described in the Appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.cor
Sealiic/giies/Codeee wwc.eeSuummssiiooool11111.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ssinnooicciyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all necessary experimental details in the experiment section (Section Finn Appendix). These details ensure that the experimental setup and results can be fully understood and independently reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We reported error bars in experimental results.
17

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We specify all the computational resources used for our experiments in the experiment section (Section F in Appendix).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't I make it into the paper).
paper (e.g., preliminary or failed experiments that
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp::/harrrppp..c/////////las
Answer: [Yes]
Justification: Our research fully complies with the NeurIPS Code of Ethics. We have carefully reviewed and ensured adherence to all relevant standards.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
18

---

Answer: [Yes]
Justification: We provide a Broader Impact Statement in Section discussing both the potential positive impacts-such enabling trustworthy and crivacy-preservig machine learning in sensitive domains like healthcare and finance-and the broader limitations of differentially private learning, including potential reductions in model accuracy. This balanced discussion reflects both societal benefits and possible drawbacks.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not existing assets.
Guidelines:
19

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve research with human subjects.
20

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non standardd components.
Please refer to our LLM policy for what should or should not be described.
21


Reviews:
[{"review_id": "NNQp4c18rC", "reviewer": "Reviewer_jpLh", "summary": "This paper introduces a new approach to find second-order stationary points (SOSP) in differentially private (DP) stochastic non-convex optimization. \nWith their analysis, the authors correct an existing convergence rate result by means of a more careful consideration of gradient variances when escaping saddle points.\nThe approach does not rely on separate private model selection and therefore can be applied to distributed settings.\nThe proposed Gauss-PSGD algorithm uses Gaussian perturbations and model drift to efficiently escape saddle points, and achieves improved convergence rates compared to existing results.", "questions": "* Can the model drift criterion misidentify local minima as saddle points?\n* Are your results useful/applicable to some degree to, e.g.,  Rényi DP?\n* What happens if the gradient noise is not sub-Gaussian?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths \n\nThe proposed Gauss-PSGD algorithm improves (and corrects) upon existing work with respect to convergence error rates.\nIt also avoids the need for separate private model selection procedures to identify SOSPs, which is especially problematic in distributed settings due to high communication and privacy costs.\nAs a methodological contribution, the authors use model drift (instead of function value) to determine whether a saddle point has been escaped.\nThe extension to a distributed (heterogeneous) setting has been previously unaddressed by related work.\n\n\n## Weaknesses\n\n**Empirical evaluation.**\nThe empirical evaluation does not, in my opinion, satisfactorily support the practical utility of the method presented.\nWhile it is clear from your problem statement that your contributions are of theoretical rather than empirical nature, it would be important to see how your approach compares to other strong DP baselines.\nIn the classifications tasks you perform on MNIST and CIFAR-10 it is not clear how your approach compares to other state-of-the-art DP classification techniques.\nI do nevertheless acknowledge the importance of comparing your approach to the baseline method from Liu et al. [1], which more directly compares to your problem setting.\n\n**Theoretical assumptions and ease of implementation.**\nAs far as I can judge, your results seem theoretically sound.\nThey require, however, a number of assumptions which may easily not hold in real-world tasks.\nI think it would be important to comment to which degree the Lipschitzness and smoothness assumptions, as well as the necessity for hyperparameter tuning, affect real-world applicability.\nBig-O notation often omits, as commonly done, polylog factors.\nThis however makes it difficult to keep track of the actual impact of the different contributions in the bounds, which both hinders practical implementations and makes it difficult to understand how much the hidden factors weigh on the bound.\nA more structured presentation, in the appendix, of the bounds with some additional comments on the practical implications would be a useful addition.\n\n\n[1] Daogao Liu, Arun Ganesh, Sewoong Oh, and Abhradeep Guha Thakurta. Private (stochastic) non-convex optimization revisited: Second-order stationary points and excess risks. Advances in Neural Information Processing Systems, 36, 2024.\n\n**Minor comments.**\n\n* The paper lacks visual aids like diagrams, which could help explain saddle point escape or the distributed setup more intuitively.\n* The \"failure probability\" $\\omega$ appears for the first time in algorithm 1 without introduction.\nOther symbols like $\\eta$ (in the same section) also require introduction.\n* \"Saddle point escape/escaping saddle points\", as an expression, could use for some more formal definition.", "was_revised": true, "final_justification": "The rebuttal sufficiently addressed the weak points I raised in my review, as the added experiments further motivate the proposed theoretical advancements proposed by the authors.", "rebuttal": "We thank Reviewer jpLh for the detailed and constructive feedback. We are especially grateful for the recognition of our theoretical contributions, including the improved and corrected convergence error rates, the avoidance of separate private model selection procedures, and the extension to distributed heterogeneous settings. We also appreciate the acknowledgement of our use of model drift as a novel escape criterion for saddle points.\n\n## Response to Weaknesses\n\n**1. Regarding empirical evaluation:** We acknowledge the importance of empirical validation in differentially private optimization. As the reviewer noted, our work is primarily theoretical, and our experiments are designed to evaluate the effectiveness of our approach specifically in the context of DP-SOSP under population risk minimization, where Liu et al. [1] is the only prior relevant baseline. In this regard, we believe our experiments are both necessary and sufficient to support the contributions of this work. We agree that broader empirical comparisons (e.g., with general-purpose DP classifiers) are valuable but fall outside the specific scope of our problem. We view this direction as important future work and plan to pursue more comprehensive empirical studies that explore utility trade-offs across broader tasks.\n\n**2. Regarding theoretical assumptions and ease of implementation:** We thank the reviewer for this valuable suggestion. We agree that a clearer discussion of how hyperparameters (whether stemming from the assumptions such as Lipschitzness and smoothness, or from the optimization procedure such as the drift threshold and learning rate) influence practical performance would help make our results more accessible. We will also include in the appendix a structured summary of the constants and polylog factors that are currently hidden in the Big-O notation, as well as comments on their practical implications.\n\n**3. Regarding the minor comments:** We thank the reviewer for the constructive suggestions. We will take all of them into consideration when preparing the final version.\n\n## Response to Questions\n\n**Q1:** While it is possible that a local minimum in a very flat landscape may trigger noticeable model drift, our algorithm is designed to ensure that it eventually returns a true local minimum. Specifically, the algorithm escapes every saddle point with high probability (as shown in Lemma 1), and each successful escape (whether from a saddle point or a flat region) incurs a large model drift and sufficient function decrease (Lemma 4). Since the objective is bounded below, the total number of such escapes is bounded. Therefore, the algorithm must eventually reach and return an approximate local minimum (i.e., an $\\alpha$-SOSP).\n\n**Q2:** Yes, our framework can be readily extended to other privacy notions such as Rényi DP, Gaussian DP, or z-CDP. We emphasize that changing the specific DP definition does not meaningfully affect our results, as our analysis is based on the Gaussian mechanism, which satisfies all these privacy notions. Any improvements would only be polynomial in terms of $log(1/\\delta)$, which does not qualitatively change our convergence guarantees.\n\n**Q3:** Norm-sub-Gaussian random vectors are a general class that includes sub-Gaussian vectors as a special case (see [22]), and this assumption has been adopted in prior state-of-the-art work on non-private SOSP problems [23]. We believe it is a reasonable and flexible starting point for analyzing DP-SOSP. That said, we agree that understanding the behavior of saddle point escape under heavy-tailed noise is an important direction for future work, and we plan to investigate this further."}, {"review_id": "4TGYFH8LJ3", "reviewer": "Reviewer_DNHR", "summary": "This paper studies the second order convergence guarantees of a differentially private stochastic non-convex optimization problem. Authors assume a sufficiently smooth loss function (Lipschitz, smooth and Lipschitz Hessian), and propose a generic optimization algorithm Gauss-PSGD that obtains the gradients from arbitrary gradient oracles. The algorithm tries to detect if the optimization has ran into a saddle point, and tries to escape it by continuing the stochastic optimization and checking if the parameter value has moved enough from the supposed saddle point. Authors prove several theoretical properties for the Gauss-PSGD: high-probability bound of escaping the saddle point, high-probability convergence guarantee into a 2nd order optimal point, and using specific DP gradient oracle show an improved error rate for DP non-convex optimization. Authors also extend the setting for a distributed learning, where the data can be heterogeneous among the clients. In this setting authors can recover very similar error rate as with the general DP non-convex optimization.", "questions": "1. Is there a reason to have the constants $c_1$ and $c_2$ in Thm 2.? I guess the constants arise from the moments-accountant-like analysis, and hence for a fixed $\\epsilon$ and $\\delta$ mainly affect the noise level, which (I guess) is not explicitly present in Thm 2. Maybe there is some reason to have them there, but to me it seemed just confusing to have the explicitly stated when the expression does not depend on them.\n2. The constants $c_1$ and $c_2$ in Thm. 2 remain a bit unclear to me. First, as they are not explicitly part of the bound, is is necessary to have them? Second, are these constants effectively the same as in moments accountant privacy analysis by Abadi et al. 2016?\n3. It seems that the Gauss-PSGD achieves better test accuracy with $\\epsilon=0.5$ than $\\epsilon=2$ (Fig. 2, m=10 result). Do you have any idea why this is?\n4. Does the single hidden layer NN you have selected for the experiments actually satisfy some of the regularity conditions (Assumptions 1 and 2)? If the objective is not Lipschitz, I guess you have used the biased clipped gradient oracle? And if so, can you report the clipping threshold for clarity sake.\n5. typo: \"requirment\"", "limitations": "Yes, although the discussion is pushed mainly to the Appendix.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n1. The paper presents a novel 2nd order error analysis for DP non-convex optimization problem. The proposed error rates improve (although somewhat moderately) over the existing bounds, allowing to better understand the limits of DP non-convex optimization.  (**Originality + Significance**) \n2. The extension to distributed setting is interesting, especially given that the prior work only has convergence results for the homogeneous data. (**Significance**) \n3. The proposed optimization framework Gauss-PSGD gives a simple unified framework for the non-convex optimization. For DP (and distributed DP) authors propose a specific gradient oracle Ada-DP-SPIDER, that tries to reduce the variance in the optimization. Authors demonstrate through some simple experiments that the proposed method out-performs an existing DP non-convex optimization method targeted for 2nd order guarantees. (**Significance + Quality**) \n4. Paper is rather busy, but the key points are explained and argued extremely well. (**Clarity**)\n\n## Weaknesses\n1. While the paper is mainly theoretical, it does propose an algorithm. So far, the experiments have been limited to somewhat simple models, so some more demanding tasks would strengthen the claims. Furthermore, having other baselines would allow putting the results in a better perspective. E.g. how would plain DP-SGD perform in the chosen tasks. (**Significance**)\n2. I think having the conclusions (amongst many other important sections) in the Appendix is a bit weird. I know that you operate under a strict page limit, but compressing the main paper does not seem impossible, especially as the conclusions and limitations allow contain some important discussion about the proposed method. (**Clarity**)", "was_revised": true, "final_justification": "Authors rebuttal addressed my concerns, and I will retain my original positive score on the paper. In my opinion this is a solid theory paper that makes a novel and significant contribution to the field. However, empirical comparisons against e.g. DP-SGD would further strengthen the paper and demonstrate if the second order guarantees lead to practically significant improvements.", "rebuttal": "We thank Reviewer DNHR for the positive assessment and for highlighting the originality, significance, and clarity of our work. We are particularly grateful for the recognition of our new second-order error analysis for DP non-convex optimization, the extension to distributed heterogeneous data, the design of the unified Gauss-PSGD framework with Ada-DP-SPIDER, and the clarity of our theoretical exposition despite the technical density.\n\n## Response to Weaknesses\n\n**1. Regarding the scope of experiments:** We agree that more demanding tasks and broader baselines would strengthen the empirical perspective. However, as the reviewer noted, our paper is primarily theoretical. Our experiments are designed to validate the theoretical claims, particularly by demonstrating that our method outperforms the only existing DP non-convex baseline with second-order guarantees (Liu et al. [1]). While general-purpose baselines like DP-SGD are widely used, they do not target second-order guarantees and are therefore not directly comparable in this context. That said, we fully agree that expanding the experimental evaluation to more complex models and broader tasks is a valuable direction, which we plan to pursue in future work on differentially private optimization.\n\n**2. Regarding the conclusion being the appendix:** We appreciate this suggestion and agree that key discussion sections such as the conclusion and limitations are best included in the main text. In the final version, we will further compress technical parts as needed and take advantage of the optional extra content page (if accepted) to bring these important sections back into the main paper.\n\n## Response to Questions\n\n**Q1 & Q2:** Thank you for raising this point. We agree that including $c_1$ and $c_2$ in Theorem 2 could be confusing, since they do not appear explicitly in the final error bound. These constants originate from the Gaussian mechanism and determine the variance of added noise. In the final version, we will remove these constants from the theorem statement and instead include them only in the algorithmic and privacy analysis sections, with a clearer explanation of their origin and meaning. To answer the second part: yes, these constants are consistent with those derived in standard moments-accountant analyses (e.g., Abadi et al. 2016), and we will make this more explicit in the paper.\n\n**Q3:** This is a sharp observation. We note that the difference in test accuracy is marginal, which we believe is primarily due to random variation across runs. As the number of clients $m$ and the number of samples per client $n$ increase, the marginal gain in utility from relaxing the privacy budget (i.e., increasing $\\epsilon$) becomes smaller. This aligns with our theoretical bound $\\tilde{O}(\\frac{1}{(mn)^{1/3}} + \\big(\\frac{\\sqrt{d}}{\\epsilon \\sqrt{m}n}\\big)^{2/5})$, where the influence of $\\epsilon$ becomes less significant when $mn$ grows. Therefore, in high-data regimes, the effect of changing $\\epsilon$ may be overshadowed by the inherent variance of the stochastic training process.\n\n**Q4:** Thank you for pointing this out. You are correct. We apply gradient clipping during training. The clipping threshold was chosen via grid search, and the configuration reported in the paper uses a threshold of 1.0. We will add this detail in the final version.\n\n**Q5:** Thank you for catching this typo. We will fix it in the final version."}, {"review_id": "BgkKW2W4Hh", "reviewer": "Reviewer_Rud7", "summary": "This manuscript aims to find second-order stationary points in differentially private non-convex optimization. They propose a generic non-convex stochastic optimization framework PSGD, and provide an improved error rate bound. Besides, they extend their theoretical analysis to distributed learning and obtain the first error bound for DP-SOSP under arbitrarily heterogeneous data.", "questions": "- This manuscript mainly compares their result with \"Private (stochastic) non-convex optimization revisited: Second-order stationary points and excess risks\" regarding the population risk. What about the empirical risk, compared with SOTA and Lower bound?", "limitations": "Yes.(Section I in Appendix)", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- This manuscript is well-organized, clearly presenting their theoretical analysis.\n\n- They obtain the recified error rate compared to prior work for finding SOSP and obtain the first error bound for DP-SOSP under arbitrarily heterogeneous data.\n\n**Weaknesses**\n\n- I notice that authors have conducted experiments for varying privacy budget and the number of clients in the Appendix. I suggest authors briefly mention their empirical results, which validate the effectiveness of their method, in the main text for better readability.\n\n- I acknowledge the statistical contribution of this manuscript. It would be better for machine learning community to understand if more explanations or insights are included. For example, why studying DP-SOSP is important; what insights we can get from all those theorems.", "was_revised": true, "final_justification": "The authors have well answered my questions. I perceive that more introductions and insights related to the machine learning community are needed for a better understanding of the contribution. Overall, I will maintain my scores.", "rebuttal": "We thank Reviewer Rud7 for the thoughtful feedback and for acknowledging the clarity of our theoretical analysis and the significance of our results, particularly the rectified error rate and the first error bound for DP-SOSP under arbitrarily heterogeneous data.\n\n## Response to Weaknesses\n\n**1. Regarding empirical results only mentioned in the appendix:** We appreciate the reviewer’s suggestion. We will summarize the key empirical results in the main text and, if accepted, use the extra page to incorporate them more clearly.\n\n**2. Regarding need for more insights into the importance of DP-SOSP and the theorems:** Thank you for pointing this out. We agree that providing more intuitive explanations about the motivation and implications of DP-SOSP would benefit a broader audience. In the final version, we will update the introduction to emphasize why DP-SOSP is important: while first-order convergence (FOSP) may still return saddle points or local maxima, second-order guarantees are essential for ensuring meaningful local optimality in non-convex problems. We will also include a brief comment on what insights the theorems provide.\n\n## Response to Question\n\nOur work focuses on population risk minimization because the issues we identified in the prior method and its analysis primarily arise in this setting. For ERM, we note that our Gauss-PSGD framework is also compatible with ERM analysis, and whether it can improve the bound for ERM is an interesting problem to investigate for future work. Regarding lower bound, the results presented in [29] are directly from [1], which primarily addresses convex loss functions and first-order stationary points. In contrast, establishing lower bounds for finding DP-SOSP in non-convex optimization is inherently more challenging and remains an open problem, which we leave for future work."}, {"review_id": "6AfoTfwAFa", "reviewer": "Reviewer_jvqK", "summary": "This paper proposes a generic perturbed stochastic gradient descent (PSGD) framework based on Gaussian noise injection and general gradient oracles to address the problem of second-order stationary points (SOSP) in differential privacy (DP) stochastic non-convex optimization, addressing two limitations of existing methods: （1）Inaccuracy of convergence error rates due to neglect of gradient variance; （2）Utility degradation caused by reliance on auxiliary private model selection procedures. The paper also discusses the limitation of private model selection in high-dimensional distributed settings, and provides numerical experiments to support its approach.", "questions": "1. How are the hyperparameters, including the escape threshold, model drift threshold, maximum drift threshold, maximum escape steps, and maximum repeat number of escape, determined? .\n2. Beyond what is covered in the appendix, what important usage scenarios or risks where model drift-based DP-SOSP is especially helpful or potentially problematic?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper demonstrates specific flaws in their saddle point escape analysis in prior works. Based on these findings, the paper motivates and delivers an algorithmic redesign that resolves these inherent limitations.\n2. The paper introduces of Gauss-PSGD , which uses model drift distance as the escape trigger and allows the algorithm to avoid the need for high-overhead, additional DP model selection.\n3. The paper is technically sound and clear in its theorems, algorithmic procedures, and justification for each design and proof step.\n4. Another significant contribution is the extension to federated/distributed learning with arbitrary data heterogeneity.\n\n\n\n**Weakness**\n\n1. Parameter setting explanations (e.g., for step sizes, batch sizes, drift thresholds in Section 3.3 and 4.2) are quite technical and packed with dense notation. More intuitive explanations are required to help understand trade-offs.\n2. Although the results advance DP-SOSP theory, the discussion in the main paper is focused on theoretical mechanisms and error rates, with little commentary on how these results could impact industrial-scale machine learning tasks where privacy and distributed non-convex optimization interact.\n3. There is only a brief mention of numerical experiments in the abstract and summary, and detailed results are placed in the appendix. It is better to remove them to the main submission, especially the comparison with [29].\n4. Several important pieces, such as the detailed discussion of prior works, and experimental evaluations, are delegated to the appendix. A more self-contained and empirically substantiated presentation would considerably strengthen the case for publication.", "was_revised": true, "final_justification": "The rebuttal satisfactorily addresses all of my concerns, and I have increased my score by one point accordingly.", "rebuttal": "We thank Reviewer jvqK for the detailed and constructive review. We are grateful for the recognition of our contributions, including the correction of flaws in prior saddle point escape analysis, the design of Gauss-PSGD based on model drift, the elimination of high-overhead private model selection, and the extension to distributed learning with heterogeneous data. We also appreciate the acknowledgment of the clarity and rigor of our theorems and algorithmic design.\n\n## Response to Weaknesses\n\n**1. Regarding dense parameter settings in Section 3.3 and 4.2：** Thank you for the suggestion. In the final version, we will supplement the main text with more intuitive explanations of the parameters, including how they relate to algorithmic behavior and theoretical guarantees, to improve accessibility for broader audiences.\n\n**2. Regarding practical impact for industrial-scale ML tasks:** We agree that connecting our theoretical results to real-world applications is important. This work focuses primarily on improving and correcting the theoretical foundations of DP-SOSP, particularly addressing limitations in [29] and providing a refined understanding of saddle point escape behavior. That said, we will add a brief discussion to highlight potential industrial use cases, such as privacy-preserving distributed training, and we plan to explore more empirical evaluations in future work.\n\n**3 & 4. Regarding the organization of the paper:** We appreciate the helpful suggestions. Due to strict page constraints, we initially placed some experimental results and prior work discussions in the appendix. We agree that summarizing key empirical findings, especially the comparison with [29], in the main paper would strengthen the presentation. If accepted, we will use the additional content page to reincorporate the most essential experiments and discussion of prior works into the main submission, making it more self-contained and empirically grounded.\n\n## Response to Questions\n\n**Q1:** The parameter settings are derived from our convergence and privacy analysis:\n- The escape threshold $\\chi$ is set to match the gradient estimation error, as established in Lemma 5, which ensures a uniform average decrease in function value of at least $O(\\chi^2\\eta)$ per PSGD step, regardless of whether the algorithm is in an escape phase, as shown in Lemma 6. \n- The model drift threshold $\\kappa$ is chosen to balance the cumulative error introduced by the gradient oracle $\\mathcal{O}_1$ and $\\mathcal{O}_2$, as shown around lines 790 and 820. \n- The maximum drift threshold $\\mathcal{R}$ and the maximum escape steps $\\Gamma$ are designed to (1) control the curvature-dependent term $\\mathscr{P}_h(t)$, as in Eq. (41); and (2) ensure that the stochastic gradient noise term $\\mathscr{P} _{sg}(t)$ remains bounded, as in Eq. (43). \n- The maximum repeat number $Q$ is selected logarithmically in failure probability to amplify success probability, as specified in Lemma 2. \n\n**Q2:** The model drift criterion is particularly useful in settings where global function values are inaccessible, but model updates are observable, such as the population risk minimization setting considered in our paper. One potential issue is that small, flat local minima may trigger unnecessary escapes. However, as noted in our response to Reviewer jpLh's Q1, this does not affect our convergence guarantee to a DP-SOSP. Moreover, this property could potentially be leveraged to encourage flatter minima, in line with recent work on sharpness-aware minimization for improved generalization. We view this as a promising direction for future research."}]

Author rebuttal:

Meta-review: This paper investigates second-order convergence guarantees for differentially private stochastic non-convex optimization, offering refined complexity bounds (with matching lower bounds in certain cases) and an algorithm that combines variance reduction with a tailored perturbation mechanism. While there has been prior work on second-order methods under DP, the paper’s analysis sharpens some existing bounds and integrates these components in a cohesive framework.

Reviewers found the theoretical results technically sound and relevant, but noted that the empirical evaluation is limited and that some proofs would benefit from additional intuition. The paper is generally well written, though parts of the technical presentation are dense.

Overall, the work contributes new insights in a challenging setting and is likely to be of interest to researchers in private optimization. Expanding the empirical evaluation and improving the accessibility of technical arguments would further enhance its impact.
Decision: Accept (poster)