Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
Authors: Guy Kornowski
Daogao Liu
Kunal Talwar
Venue: ICML 2025 poster (2025)
Keywords: Differential privacy
nonconvex optimization
nonsmooth optimization
Goldstein stationarity
Primary area: social_aspects->privacy
TL;DR: Improved algorithms for differentially private nonsmooth nonconvex optimization

Abstract: We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstein-stationary point with sample complexity bounds that improve on existing works.
We start by providing a single-pass $(\epsilon,\delta)$-DP algorithm that returns an $(\alpha,\beta)$-stationary point as long as the dataset is of size $\widetilde{\Omega}(\sqrt{d}/\alpha\beta^{3}+d/\epsilon\alpha\beta^{2})$, which is $\Omega(\sqrt{d})$ times smaller than the algorithm of Zhang et al. (2024) for this task, where $d$ is the dimension.
We then provide a multi-pass polynomial time algorithm which further improves the sample complexity to $\widetilde{\Omega}\left(d/\beta^2+d^{3/4}/\epsilon\alpha^{1/2}\beta^{3/2}\right)$, by designing a sample efficient ERM algorithm, and proving that Goldstein-stationary points generalize from the empirical loss to the population loss.

Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
Guy Kornowski'
Daogao Liu ? Kunal Talwar?
Abstract
Due to its fundamental importance in modern machine learn- ing, the field of nonconvex optimization has received sub- stantial attention in recent years. Moving away from the classical regime of convex optimization, many works aimed at understanding the complexity of producing approximate- stationary points (with small gradient norm) for smooth nonconvex functions (Ghadimi & Lan, 2013; Fang et al., 2018; Carmon et al., 2020; Arjevani et al., 2023). However, smoothness rarely holds in modern practice, posing major challenge for large and highly expressive models such as deep neural networks. Indeed, using ReLUs and MaxPool layers is common practice (LeCun et al., 2015), and more- over, stochastic gradient descent (SGD) with a large batch size tends to converge to sharp minima (Keskar et al., 2017)
We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstein-stattinnary point with sample complexity bounds that improve on existing works. We start by providing single- pass (e, 6D algorithm that returns an (a,, 3)- stationary point as long the dataset is of size 2(Vd/a,3 + ddEa,3²), which is (Vvd) times smaller than the algorithm of Zhang et al. (2024) for this task, where d is the dimension. We then provide a multi-par pass polynomial time algorithm which further improves the sample complexity to 2 (d/3² + d3/4 3/2//33))) by designing a sample efficient ERM algorithm, and proving that Goldstein- Goldstein-stationaryy points generalize from the empirical loss to the population loss.
As it turns out, without smoothness, it is actually impossi- ble to directly minimize the gradient norm without suffer- ing from an exponential-dimensio dependent runtime in the worst case (Kornowski & Shamir, 2022). Nonetheless, a nuanced notion coined as Goldstein -tatiinins (Gold- stein, 1977). has been shown in recent years to enable fa- vorable guarantees. Roughly speaking, a point x E Rd is called an (a, B-Goolssttii stationary point (or simply (a, -ttstaaion))y if there exists convex combination of gradients in the a-ball around æ whose norm is at most (3. Following the groundbreaking work of Zhang et al. (2020), surge of works study NSNC optimization through the lens of Goldstein stationarity, with associated finite-time guar- antees (Davis et al., 2022; Lin et al., 2022; Cutkosky et al., 2023; Jordan et al., 2023; Kong & Lewis, 2023; Grimmer & Jia, 2024; Kornowski & Shamir, 2024; Tian & So, 2024).
1. Introduction
We consider optimization problems in which the loss func- tion is stochastic or empirical, of the form
F(x) S~p
E
(xx
(stochastic)
FP(x) = 1
f(x; &t,,
(ERM)
where P is the population distribution from which we sam- ple a dataset D- (E1. .EI....,E.. En) pn, and the component functions f() : Rd + R may be neither smooth nor convex. Such problems are ubiquitous throughout machine learning, where losses given by deep-learning based models give rise to highly nonsmooth nonconvex (NSNC) land- scapes.
In this work, we study NSNC optimization problems under the additional constraint of differential privacy (DP) (Dwork et al., 2006). With the ever ever-growing deployment of MI. models in various domains, the privacy of the data on which models are trained is a major concern. Accordingly, DP optimization is an extremely well-studied problem, with a vast literature focusing on functions that assumed to be either convex or smooth (Bassily et al., 2014; Wang et al., 2017; Bassily et al., 2019; Wang et al., 2019; Feldman et al.,
'Weizmann Institute of Science; work done while intern- ing at Apple. *Google; work done while at University of Washington and Apple. AAplle. Correspondence to: Guy Ko- mowski <guy korkkookwwskiiee coomowsti@weizzmm.ac. wwizmann.ac.ill. ic. Daogao Liu <liu- daogao @ea.l.maaalm..m...
Previous works typically use the notational convention (6, E)- stationarity instead of (o, 8), namely where 5 is the radius (instead of a) and E the norm bound (instead of (3). We depart from this notational convention in order to avoid confusion with the standard privacy notation of (s. DDP
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Private Nonsmooth Nonconvex Optimization
2020; Gopi al., 2022; Arora al., 2023; Carmon al., 2023; Liu et al., 2024).
Sample complexity
empirical
stochastic
da/2 eay
The fundamental investigation in this literature is the privacy-utility trade-off, that is, assessing the minimal dataset size n (referred to as the sample complexity) re- quired in order to optimize the loss up to some error under DP. Being able to improve utility while using less samples has significant consequences, as in applications the amount of available data is serious bottleneck, or arguably soon to become one (Villalobos et al., 2024).
(Zhang et al., 2024) (SP)
r/3
Theorem 3.1 (SP)
vd ag3
+
20:37
d9/4
63/4 /288//2
Theorem 4.1 (MP)
1/3
za
Table 1. Main results (ignoring dependence on Lipschitz constant, initialization, and log terms). SP=Single pass, MP=Multi-pass.
For NSNC DP optimization, to the best of our knowledge the only existing result is by Zhang et al. (2024), which provided a zero-order algorithm (namely, utilizing only function value evaluations of f(:: ()) that preforms single pass over the dataset and returns an -sstatiiyy point of I' under (e, 6DDP long
Notably, Eq. (3) substantially improves Eq. (2) (and thus, Eq. (1)) in parameter regimes of interest (small e, a, B, large d) with respect to the dimension and accuracy pa- rameters, and in particular is the first algorithm to per- form private ERM with sublinear dimension-dependentt sample complexity for NSNC objectives.
d
1/22
Ω
0.g3
e0;32
In order to utilize our empirical algorithm for stochastic objectives, we must argue that Goldstein-sttaionarityy gen- eralizes from the ERM to the population. No such result appears in the literature, thus we proceed to prove it:
1.1. Our contributions
In this paper, we provide several new algorithms for NSNC DP optimization, which improve the previously best-known sample complexity for this task. Equivalently, given the same amount of data, they provide better utility. For con- sistency with the previous result by Zhang et al. (2024), throughout most of this paper we propose and analyze zero- order algorithms, yet we later generalize our results ac- commodate first-order (i.e. gradient) oracles.
Additional contribution: generalizing from ERM to population in NSNC optimization (Proposition 5.1). We show that with high probability, any (a, 3)- stationary point of FD is an (a, -)stttiionyyy point of F, for 8 3 + Ö(vd/n). Hence, the empirical guarantee Eq. (3) generalizes to stochastic losses with an additional d/ additive term in (up to log terms).
Our contributions, summarized in Table 1, are as follows:
1. Improved single-pass algorithm (Theorem 3.1): We provide an (2. 8)DDP algorithm that preforms single pass over that dataset, and returns an (a, 8) -sstttiion point as long as
3. First-order algorithm with reduced oracle complexity (Theorem 6.1): We provide first-order (i.e., gradient- based) algorithm with the same sample complexity de- rived thus far, which requires ii(d²) times less oracle calls compared to the zero-order case. Overall, this es- tablishes the best-known algorithm for NSNC DP both in terms of sample efficiency and oracle efficiency.
Vd
d
n n=
(2)
a
Ea.32
which is ((vd) times smaller than (1). Notably, the "non-private" term vd/ag3 has sublinear dimension de-
1.2. Our techniques
pendence, as opposed to Eq. (1), which was erroneously claimed impossible by previous work (see Remark 3.2).
One of the main techniques we use is constructing better gradient estimator with an improved effective sensitivity. We consider the zero-order gradient estimator
2. Better multi-pass algorithm (Theorem 4.1): In order to further improve the sample complexity, we move to consider ERM algorithms that go over the data polynomi- ally many times, which we will later argue generalize to the population loss. To that end, we provide an (s, 8DP FRM algorithm, that returns an (a, 33-Gooddstei station- ary point of FD as long as
1 m
d (f(z + ayy;E) f(x -aygie))
(z:
2a
(4)
for (y.)m 3dd Unif(Sd-1), which is an unbiased estimator of the smoothed gradient V f. (z; {) (cf. Section 2 for de- tails), to which we then apply variance reduction. Zhang
d/4
52
(3)
3/232333/2
2

---

Improved Private Nonsmooth Nonconvex Optimization
al. (2024) considered this oracle specifically with m = d, for which it is easy to bound the estimator's sensitivity over neighboring minibatches LL.B, fi.B of size B by
Randomized smoothing. Given any function h IR
R. denote its randomized smoothing (x) By-B, h(z+y), We recall the following standard properties of randomized smoothing (Flaxman et al., 2005; Yousefian et al., 2012; Duchi et al., 2012; Shamir, 2017).
S B
1
B Σ (1)
Ld
(5)
B
Fact 2.3 (Randomized smoothing). Suppose h R + R is L-Lipschirz. Then: (i) ha is L-Lipschitz: (ii |he - h(2)) V La for any x E Rdd (ii) ha is (iv) (a) = (Vh[,,V =
Our key observation is that while this is indeed the worst- case sensitivity, we can get substantially lower sensitivity with high probability: For sufficiently large m, standard sub- Gaussian concentration bounds ensure that (x; Ei)= x fa (x; Ex) with high probability, and hence under this event we show the sensitivity over a mini-batch can be decreased to order of -. This is factor of d smaller than Eq. (5), thus we can add significantly less noise in order to privatize, leading to faster convergence to stationarity.
Byoagr 12 (h(r + aay) h(x - -oy))ul
The following result shows that in order to find a Goldstein- stationary point of a function, it suffices to find a Goldstein- stationary point of its randomized smoothing:
Lemma 2.4 (Kornowski & Shamir, 2024, Lemma 4). Any (a, -)stttionaryy point of ha is a (2a, -)stttiionryy point of h.
2. Preliminaries
Notation. We denote by (.-)). -1- || the standard Euclidean dot product and its induced norm. For IRd and > 0, we denote by B(I a:) the closed ball of radius centered at x, and further denote IB, := B(0, a). gd-1 C Rd denotes the unit sphere. We make standard use of O-notation to hide absolute constants, Ô Ω2 to hide poly-logarithmic factors, and also let f S g denote ʃ = O(y).
Differential privacy. Two datasets D, D' E supp(P)" are said to be neighboring if they differ in only one data point. A randomized algorithm A 2n + R is called (e, 6) differentially private (or ()-)) for e, > 0 if for any two neighboring datasets D. D' and measurable E C R in the algorithm's 's range, it holds that Pr(A(D) E E] S e Pr(A(D") E F. + 5 (Dwork et 2006).
Nonsmooth optimization. A function h RRd + R is called L-Lipschitz if for all x, y E R Ih(z) h(y) < |||l We call h H-smooth, if h is differentiable and 4h is H-Lipschitz with respect to the Euclidean norm. For Lip- schitz functions, the Clarke subgradient set (Clarke, 1990) can be defined as
Tree mechanism. Next, we revisit the well-known tree mechanism, detailed in Algorithm 1. In essence, the tree mechanism enables the privatization of cumulative sums ビ gy for all E [Σ]. which, in our context, correspond to summed gradient estimators. A naive approach would add independent Gaussian noise Cj to each gj. leading to an error that scales as VE.. In contrast, the tree mechanism reduces this error to O(log Σ) by introducing correlated Gaussian noise. Broadly speaking, the mechanism generates a set of independent Gaussian noise values and organizes them in a tree-like structure, where each node corresponds to specific noise value. To compute any cumulative sum Σ Mj. the mechanism selects at most O(log Σ) nodes (Function NODE in Algorithm 1) from the tree and privatizes the sum using the aggregated noise from these nodes (i.e., final noise TREE(() generated by Algorithm 1). The formal guarantee associated with this mechanism provided below.
0h(x) == convig : 99= lim Vh(an), Vn + xh, n-000
namely the convex hull of all limit points of Vh(xx) over se-
quences of differentiable points (which are full Lebesgue- measure set by Rademacher's theorem), converging to x. For a 0, the Goldstein a-subdifferential (Goldstein, 1977) is further defined as
hz) conv(U (V))),
and we denote the minimum-norm element of the Goldstein a-subdifferential by
Dah(a)= == arg min sea, |l
Proposition 2.5 (Tree Mechanism Dwork et al., 2010; Chan et al., 2011: Zhang et al., 2024). Let Zi, Zz, be datasel spaces, suppose X C IRd and let M, : xi-1 x Z, + X be a sequence of algorithms for i [[. Let ALG : (I:E) + TT. be the algoritim that given dataset Z1 2(1)))
Definition 2.1. A point x E Rd is called an (a,3) 3)- Goldstein stationary point of h if [[ah(=)]] s B.
sequentially computes X; Ej=M, (X((xij-1, Zj) + TREE(i) for i E [-], and then outputs X1ST. Sup- pose for all i E [Σ], and neighboring Z,,,, Zi E (u.S,l|,,,X.
Throughout the paper we impose the following standard Lipschitz assumption:
Assumption 2.2. For any &. f(:1E) Rd + R L- Lipschitz (hence, so is F).
Z.) - -M,(X.:-1- Z/)I S for all auxiliary inputs X15-1 E X--1 Then setting =
3

---

Improved Private Nonsmooth Nonconvex Optimization
4s V /log E more, for any E Σ E [[TREE(()]
Algorithm 1 is (e, 0)-DP. Further- 0 and
and derive the corresponding guarantees through Proposi- tion 2.6. As previously remarked, throughout most of the paper, our oracles will be based on zero-order queries of the component functions -() yet in Section 6 we construct oracles with the same sample complexity using first-order queries, leading to a lower oracle complexity overall.
| [REE(())) 2 d'oo(E))o?.
In our case, the "dataset spaces" Z, will be collections of possible minibatches of some determined size, and M; will be gradient estimator with respect the sampled minibatch at some current iterate.
Algorithm 2 Nonsmooth Nonconvex Algorithm (based on O2NC (Cutkosky et al., 2023))
Algorithm 1 Tree Mechanism
1: Input:
Oracle O R- + R. initialization zo E R2, clipping parameter D > 0, step size rj > 0, averaging length M E N. iteration budget T E N.
1: Input: Noise parameter a, sequence length Σ
2: Define T = {(u, r) : u- = = j- 1, 1)+
2 2 l - log Σ, 0 j S 1/22-1-11 -1]
Initialize: A = 0
3: Sample and store ((u,e) NN o²) for all (u, ET
for t L, ..... T do
4: fort = 1,... do
4: Sample 8t Unif(0, 1]
5: Let TREE(() + (U.)ENDDE) S(u,v)
5: I₁ #1-1 + A,
6: end for
6: 2t It-1 + s,
7: Return: TREE(() for each / E [X]
7: It O
8:
8: D = min (1, Ai-nüel } (A: - ng.))
9: Function NODE:
9: end for
10: Input: index E [Σ]
10: K = M
11: Initialize S () and h: = 0
11: for l = I..... K do
12: for = 1,.., [log E1 while k < t do
M
12: Ty M Em=1 2(8-1)M44
13:
Set k' = =k + 20log [1og>:1>
13: end for
14:
k < 1 then
14: Sample zon Unif(T .z}
15:
5 SU [(k- + 1, 1,,)), k + k
15: Output: out
16: end if
17:
end for
3. Single-pass algorithm
2.1. Base algorithm: O2NC
In this section, we consider Algorithm 3, which provides an oracle to be used in Algorithm 2. Algorithm 3 is such that throughout T calls, it uses each data point once, and hence, privacy is maintained with need for composition. The main theorem in this section is the following:
Similar to Zhang et al. (2024), our general algorithm is based on the so-called "Online-to-Non-Coovaa conversion" (O2NC) of Cutkosky et al. (2023), which is generally an opti- mal method for finding Goldstein-stationar points (without the privacy constraint). We slightly modify previous proofs by disentangling the role of the variance of the gradient estimator vs. its second order moment, follows:
Theorem 3.1 "Single-pass algorithm). Suppose F( infz F(x) I Φ, that Assumption 2.2 holds,
and let a, 0, E > 0 such that S $ Then setting B
Proposition 2.6 (O2NC). Suppose that O(-) is a stochastic gradient oracle of some differentiable function h Ed - R. so that for all Rdd E [[())) - V/(22)12 < GB and [=)((2))| G7. Then rumning Algorithm 2 with 17 E D
Σ, Bg = 1, M = a/4D, m = Bd +
da B²
D2
o
Ō L + LDVa ) Σ = O1( 2/3 + Da ) D = Po's 1//3,1100 1/2, (o/TT,37
Bie
aBae
θ (min|{( 4²a LTT 1/3,
(LLT) )133)
115
1/31),
LITa/a T (n), and ranning Algorithm 2 with Algorithm 3 as the oracle subroutine, is (E, ()DP Furthermore, its output satisfies E 10 F F(xout)
MD < uses T calls to O(.), and satisfies
GLVM
)]| S 3 as long
E (an( < M((0) - inf
3G1
Go-
DT
2/M
LLLVV
LLd E0,
n n= π
0,93
We provide a proof of Proposition 2.6 in Appendix B. Re- calling that by Lemma 2.4 any (a, 9) -stationnyy point of F. is a (2a, B) -)-stationary point of F, we see that it is enough to design a private stochastic gradient oracle O of F.., while controlling its variance Go and second moment G1. In the next sections, we show how to construct such private oracles
Remark 3.2. It is interesting to note that the "non-private" term Ld2 in Theorem 3.1 has sublinear depen- dence on the dimension d. Not only is this the first such result, this was even (erroncously) claimed impossible by Zhang et al. (2024). The reason for this confusion that
4

---

Improved Private Nonsmooth Nonconvex Optimization
Algorithm 3 Single-pass instantiation of ((2)) in Line 7 of Algorithm 2
least 6/2 that
1: Input: Current iterate 2,, time E N. period length Σ E N, accuracy parameter a > 0, batch sizes B1, B2 E N, gradient validation size m N, noise level >> 0.
11 L
L Bi
+
Ldy log(dB,
vm
Otherwise. conditioned gc-1 ---1- we have with prob- ability at least 1 - 88/2:
2: if t'' mod Σ then
3: Sample minibatch St of size B1 from unused samples
4: for each sample Ç: E St do
IvdD aB2 +
Ld Idv/og(dBi10))
5: Sample y1..... Mm iid Unif(
119: S'll
vm
6: fzti Ex) +n Eje(m) de (f(z + oygi Ei)
f(z - oty; {())
With the sensitivity bound given by Lemma 3.4, we easily derive the privacy guarantee of our oracle from the Tree Mechanism (Proposition 2.5).
7:
end for
8:
9: - - I.,ES, Eses, (.)
9:
else
10:
Sample minibatch St of size B2 from unused samples
Lemma 3.5 (Privacy).
Running Algorithm 3 with (log(dB2/0)(dDBB = and o ( is (e,
11:
for each sample & E St do
12:
Sample y1..... 92m ~ Ba.)
L (V/og(1/0) LDVdlog(1/0) BB2
13:
f((: Er) = 1
Lje(m] [m] 2a (f(z) + agj; Et) -
o
Bie
f(ze {=(=-1; 1: (t)
14:
1 2m d (f(zz1
2-j=+1 2a
We next analyze the variance and second moment of the gradient oracle.
agzi Ex) - f(2-11 aty: Ei))y
15:
end for
Lemma 3.6 (Variance). In Algorithm for all t [T] it holds that
16:
St = 91-1+ 1.
B3 EE.es. (Vf(21; (f)vf((z-1 &))
17:
end if
18:
Return Tt- = gt + TREE(O, (t mod ))
L L2d
12-DDR
E f1 - VF.
2
+
+
Bi
Bim
a²B2
2 dl log E
mB²
while the optimal zero-order oracle complexity is d/a,3 (Kornowski& & Shamir, 2024), and in particular must scale linearly with the dimension (Duchi et al., 2015), the sample complexity might not.
L2d
L2dD2E
E |
< L
Bim
B²
L2
+ 0 log E
mB2
Remark 3.3. Since Algorithm 2 uses T calls to O(-), ), and it easy to see that the amortized oracle complexity of O..) (m)) the overall oracle complexity we get is (Tm). As previously mentioned, we set m to reduce the sensitivity of O-)), leading an improvement in sample complexity.
Combining the ingredients that we have set up, we can derive Theorem 3.1.
Proof of Theorem 3.1. The privacy guarantee follows di- rectly from Lemma 3.5, by noting that our parameter assign- ment implies B + B&T O(n), which allows letting T O(n) while never re-using samples (hence no privacy composition is required). Therefore, it remains to show the utility bound. By applying Lemma 2.4 and Proposition 2.6, we get that
More generally, our analysis allows trading-off sample and oracle complexities in Pareto-front fashion. We further use this observation in Section 6, where we show that first- order oracles allow setting a substantially smaller m while maintaining the same reduced sensitivity.
In the rest of the section, we will present the basic prop- erties of this oracle in terms of sensitivity (implying the privacy), variance and second moment. We will then plug these into Algorithm 2, which enables proving Theorem 3.1. Corresponding proofs are deferred to Appendix A.
E 110 F(x:out)1
||
S E 10 (I.
F. (2o) - inf Fa +
3G1
<
+ Go
DT
M
24
3G1
Lemma 3.4 (Sensitivity). Consider the gradient oracle O()) in Algorithm 3 when acting on two neighboring minibatches S, and St, and correspondingly producing 9t and gi re- spectively. Ift mod Σ 1, then holds with probability at
DT
2/M
+ Go.
(6)
where the last inequality used the fact that Assumption 2.2 and Fact 2.3 together imply that Fa (xo) - inf F. S
5

---

Improved Private Nonsmooth Nonconvex Optimization
F(z)) F La $ + La S 2Φ. Under our pa-
Algorithm MMlti-pass instantiation of (2e) Line 7 of
rameter assignment, Lemma 3.6 yields
Algorithm 2
1: Input: Current iterate 2t. time t E N. period length
G1 S Go + L,
(7)
Σ. N, accuracy parameter a > 0, gradient validation
size E N, noise levels di, 02 > 0.
which plugged into Eq. (6) gives
2: if t mod Σ = 1 then
L
3: for each sample & D do
E | 12 F( [x" = 0
Go)
(8)
sdd 4: Sample y1, ....... Um ~ Unil(gu-1)
DT
VM
5: f 6.) = + Σ je(ml 2a (f(2 + azy; Ei)
d
Moreover, under our parameter assignment, Lemma 3.6 also gives the bound
f(z oy5; Ei)lys
6: end for
7: 9: = - - {z(z;
L
LDVRE
Go -
+
+ t dlog
8: Return:
9t. + Xt, where X N((0,
VBi
ayB2
9:
else
12
Ld
LDd
10: for each sample & E D do
=
Σe
aE
11:
Sample y1,.... 92m Una)
sid
which propagated into Eq. (8) and recalling that M = (a)/D) shows that
12:
V [= {t) 1 プド 2a (f(a
onfs Ei)
f(2 aty; E,)1y,
13:
f2 13 E.) = m
2a (f(2-1 +
E
1 2a P P(
II
ayj; {,) - ff(1111 - -oyji Ei))ys
= ō Φ
LD
LD
14: end for
a1/2 +
15: 9: 9t-1 + HeGEDD ( (zs E,) - - E.)
DT
16:
Return: 9: 9t + Xt. where Xt NN00,
L
L2
LDd
17:
end if
V
Le
as
Plugging our assignments of Σ and D, and recalling that n = O(T), a straightforward calculation simplifies the bound above to
the empirical objective = ((=:(), Ez). After establishing ERM results, in Section we show that any empirical Goldstein-stationarityy guarantee generalizes the population loss.
[2zaF(zouu
Similarly to the single-pat pasle-pass oracle (Algorithm 3), we use randomized smoothing and variance reduction. A difference in the oracle construction is that we replace the tree mech- anism with the Gaussian mechanism and apply advanced composition for the privacy analysis (since now samples are reused). The main theorem for this section is the following:
= =ō(
2 @ 1/3
4dL 1/2
L' 1/5
no
nag
no?2
Bounding by B and solving for n. results in
LL'VV
Ld Eq
8//
n á
+
Theorem 4.1 (Multi-pass ERM). Suppose FP(xo) inf, FP((x) S 4, Assumption 2.2 holds, and let ot, B, 0, 0, O such that S T.- Then setting
a
e1/2a,3512
To complete the proof, we simply note that 2//24 < 27/70
L'dE nof no
L2d
$1.'Vd
&Ldd by the AM-GM inequality, and so the third
L σ1 = 0
Lolo//o 1og(1/ 02 = O0 LDV/Talo(11/))
Σ =
ag
ane and running Algo-
term above is negligible.
θ " D = 2g ) (
$12 (
rithm with Algorithm 4 as the oracle subroutine is (c, DP. Furthermore, its output satisfies E 1102a (x )|| <
4. Multi-pass algorithm
8 as long as
V
In this section, consider different oracle construction given by Algorithm 4, to be used in Algorithm 2. The main difference from the previous section is that this ora- cle reuses data points a polynomial number of times, and therefore cannot directly guarantee generalization to the stochastic objective. Instead, in this section we analyze
n=
Ea1/233/2
Remark 4.2. As we will show in Section 5, Theorem 4.1 also provides the same population guarantee for 100,0 F(z with an additional L L'd/ 32 term (up to log factors) to the sample complexity.
6

---

Improved Private Nonsmooth Nonconvex Optimization
To prove Theorem 4.1, we analyze the properties of the oracle given by Algorithm 4. The sensitivity of gr in Algo- rithm 4 directly follows from Lemma 3.4. By the standard composition results of the Gaussian mechanism (e.g., Abadi et al. 2016; Mironov 2017; Kulkarni et al. 2021); we have the following privacy guarantee:
algorithms with the same sample complexity, and improved oracle complexity.
The idea is to replace the zero-order gradient estimator from Eq. (4) by the smoothed first-order estimator
1 m
Lemma 4.3 (Privacy). Calling Algorithm 4 T times with = 1''x= + nof noj"
(x((;;))
Vf(2 + agyi
(10)
01 = ((LVTlog(//)//) and 02 = L'd
m
me
LDVTTdlo((1/)) is (E ane
for (u:) rid Unif($ While this estimator has the ~
0
same expectation as the zero-order variant, the key differ- ence lies in the fact that its sub-Gaussian norm is substan- tially smaller, and in particular, it does not depend on d. Hence, smaller m suffices for similar concentration. This observation enables reducing the oracle complexity, while ensuring the same sample complexity guarantee as earlier.
In terms of the oracle's variance, we show:
Lemma 4.4 (Variance). In Algorithm 4, for any t E [T]. we have
L''D
E 1 - ( 2 mn
+ toîd + ozdE,
We fully analyze here a single-pase first-order oracle pre- sented Algorithm 5, which can be used in Algorithm 2, similarly Section 3. We note that the same analysis can be applied to the multi-pass oracle of Section 4, once again by replacing Eq. (4) by Eq. (10), which omit here for brevity. The main result in this section is the following:
E | 1 x L
mn + +o, + + ozdE.
The proof of Theorem 4.1, which we defer to Appendix A, is a combination of the two lemmas and Proposition 2.6.
5. Empirical to population Goldstein- stationarity
Theorem 6.1 (First-order). Suppose F(zo)
inf, F(x)
I v. that Assumption 2.2 holds, and
let a, 0, > 0 such that a S I. Then setting B2aa
In this section, we provide a generalization result, showing that our ERM algorithm from the previous section also in terms of the population loss. We prove the following more general statement:
B1 = Σ, B2 = 1, M- = =a/DD, m = Ō
Ded
o
Ō L. + LDVd), E = 6(( 22/3 + D& D
guarantees
Bid aBgs
@(min(( ( ( ) 0² 115
s'a
1/3)),
Proposition 5.1. Under Assumption 2.2, suppose 'D ~ 'pn, and consider rumning an algorithm on FDD whose (pos- sibly randomized) output z E X C Rd is supported over a set X of diameter S R. Then with probabil- ity at least 1 --:: F(rut)) s 17. (z) + Ö (TVd (R)CC)))
T= (n)), and ranning Algorithm 2 with Algorithm 5 as the oracle subroutine, is (e, 8)D.. Furthermore, its oulput satisfies E 10aa Fzzout) S 3 as long as
DL3VV
LLd
n n= Ω
ag3
Remark 6.2. Compared to the analogous zero-order result given by Theorem 3, we see that the number of calls to O(-), ), namely T,, is on the same order, and that in both cases the amortized oracle complexity of O(-) .) is 0(m). The dif- ference between the settings is that the first-order oracle instantiation sets m to be (2d2) times smaller than its zero- order counterpart, and hence we gain this multiplicative factor in the overall oracle complexity. It is interesting to compare this gain to non-private optimization, where the ra- tio between zero- and first-order oracle complexities is ((d) (Duchi et al., 2015; Kornowski & Shamir, 2024), whereas here we obtain an even larger gap in favor of gradicnt- optimization.
We remark that in all algorithms of interest, the output known to lie in some predefined set, such as a suffi- ciently large ball around the initialization. As long as the diameter R is polynomial in the problem parame- ters, the log( Rt) in the result above is therefore negligi- ble. For instance, Algorithm 2 is easily verified to out- put point zut E [B(2o, DT') (since || - xx|| < D for all f). Hence, in our use case, Proposition 5.1 ensures ||02a F(x (z S 1|āza PD (1:ot)] + 3 for n = (d)/32).
6. Improved efficiency with gradients
In this section, our goal is to show that the zero-order al- gorithms presented thus far can be replaced by first-order
As in Section 3, we will present the basic properties of this oracle. We will then plug these into Algorithm 2, leading to the main result of this section, Theorem 6. Corresponding proofs are deferred to Appendix A.
In this section we use full-batch size for simplicity, yet using smaller batches (of arbitrary size) and applying privacy amplifica- tion by subsampling, yields the same results up to constants.
7

---

Improved Private Nonsmooth Nonconvex Optimization
Algorithm 5 First-order instantiation of (22)) in Line 7 of Algorithm 2
Lemma 6.5 (Variance). In Algorithm 5, for all & it holds that
1: Input: Current iterate 2,, time t E N. period length Σ E N, accuracy parameter a > 0, batch sizes B1, B2 E N, gradient validation size m N, noise level >> 0.
I
L'
E Elge - VFa(zi)
2
B1
a²
3
2: if mod Σ then
+ d Σ
mB²
3: Sample minibatch St of size B1 from unused samples
4: Sample .)...... M/,
sid ~ (B.)
E
1 1| < 1.2
5: 9t = 1 B. Eqes, f2 + y4 Er)
a² B2
6: else
+ 0 d E + L2
7: Sample minibatch S, of size B2 from unused samples
mB2
8: for each sample &, E St do
9: Sample V/..... 72m rid
Uni
Having set up the required bounds, we can prove our main result for the first-order setting.
10:
fz(zz; 5r) = 2j=1 Vf(= + Vjj Ei)
mm
11:
f=(=-1 Ex) = Ej=m+ Vf(2-1 + My: +.
Proof of Theorem 6.1. The privacy guarantee follows di- rectly from Lemma 6.4, by noting that our parameter as- signment implies B,T/E + B2T O(n), hence it allows letting T = (n) while never re-using samples.
12:
end for
13:
9: = 91-1+ B2 Dg.es. (Vf(2) {.) - E.)
14:
end if
15:
Return 9r- gt + TREE(o, (t) mod 2))
As to the sample complexity, note that our parameter assign- ment ensures that
Lemma 6.3 (Sensitivity). Consider the gradient oracle (-) in Algorithm 5 when acting on two neighboring minibatches Se and Si, and correspondingly producing St and de re-
G = 00=00 (Go + L),
Go 6 δ
L
LDd4/221/2
Ld Ee
LDd
spectively. tft mod E = 1, then
VV
ag
L 11ge - gclll S Bi
similarly to Eq. (7) and Eq. (9) in the proof of Theorem 3.1. The rest of the proof is therefore exactly the same as for Theorem 3.1.
Otherwise, conditioned on -t-1 = -h we have with prob- ability at least 1 6
7. Discussion
LVDD Wlog(dB2/0) 11,e - I
In this paper, we studied nonsmooth nonconvex optimiza- tion, and proposed differentially private algorithms for this task which return Goldstein staationrt points, improving the previously known sample complexity for this task.
aB2
Vm
With the sensitivity bound given by Lemma 6.3, we easily derive the privacy guarantee of our algorithm from the Tree Mechanism (Proposition 2.5).
Our single-pass algorithm reduces the sample complexity by at least a (2(vd) factor compared to the previous such result by Zhang et al. (2024). Furthermore, our result has a sublinear dimension-dependden "non-private" term, which was previously claimed impossible. Moreover, we propose multi-pass algorithm which preforms sample-efficient ERM with sublinear dimension dependence, and show that it fur- ther generalizes to the population.
Lemma 6.4 (Privacy). Running Algorithm 5 with B8a²
L/gg((1/)))
m = (llg(dB228)) D' and a = =0( B,e
(1og(111/)) is (e, DDD
aB3e
Proof. By Lemma 6.3 and our assignment of m, we know that with probability at least 1 - 5/2, for any f, we have
It is interesting to note that our guarantees are in terms of so-called "approximate" (e, whereas Zhang et al. (2024) derive Rényi-DP guarantee (Mironov, 2017). This is in fact inherent to our techniques, since we condition highly probable event in order to substantially decrease the effective sensitivity of our gradient estimators. Further ex- amining this potential gap between approximate- and Rényi- DP for nonsmooth nonconvex optimization is an interesting direction for future research.
L LVdD
19 aell S
B, aB2²
Then the privacy guarantee follows from the Tree Mecha- nism (Proposition 2.5).
We next provide the required oracle variance bound.
8

---

Improved Private Nonsmooth Nonconvex Optimization
Another important problem that remains open is establish- ing tight lower bounds for DP nonconvex optimization and perhaps further improving the sample complexities obtained in this paper. We note that the current upper and lower bounds do not fully match even in the smooth setting. In Appendix C, we provide evidence that our upper bound can be further improved, by proposing a computationally- inefficient algorithm, which converges a relaxed notion of stationarity, using even fewer samples than the a algorithms we presented in this work.
Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
Carmon, Y., Duchi, J. C.,. Hinder, O., and Sidford, A. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
Carmon, Y., Jambulapati, A., Jin, Y., Lee, Y. T., Liu, D., Sidford, A., and Tian, K. Resqueing parallel and private stochastic convex optimization. In 2023 IEEE 64th An- nual Symposium Foundations of Computer Science (FOCS), pp. 2031-2058. IEEE, 2023.
Acknowledgements
Chan, T.-H. H., Shi, E., and Song, D. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
The authors would like to thank the anonymous reviewers for their helpful suggestions, and in particular, for spotting miscalculation in the previous version of this work. GK is supported by Azrieli Foundation graduate fellowship.
Clarke, F. H. Optimization and Nonsmooth Analysis. SIAM, 1990.
Impact Statement
Cutkosky, A., Mehta, H., and Orabona, F. Optimal stochas- tic non-smooth non-convex optimization through online- to-non-convex conversion. In International Conference on Machine Learning, pp. 6643-6670) PMLR, 2023.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Davis, D., Drusvyatskiy, D., Lee, Y. T., Padmanabhan, S., and Ye, G. A gradient sampling method with complex- ity guarantees for lipschitz functions in high and low dimensions. Advances in neural information processing systems, 35:6692-6703, 2022.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Duchi, J. C., Bartlett, P. L.,, and Wainwright, M. J. Ran- domized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61()))2788 2806, 2015.
Arjevani, Y., Carmon, Y., Duchi, C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165-214, 2023.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cali- brating noise sensitivity in private data analysis. In The- ory of Cryptography Conference, pp. 265-284. Springer, 2006.
Arora, R., Bassily, R., González, T., Guzmán, C. A., Menart, M., and Ullah, E. Faster rates of convergence to stationary points in differentially private optimization. In Interna- tional Conference on Machine Learning, pp. 1060-1092. PMLR, 2023.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Dif- ferential privacy under continual observation. In Proceed- ings of the forty-second ACM symposium on Theory of computing, pp. 715-724, 2010.
Attouch, H. and Aze, D. Approximation and regularization of arbitrary functions in hilbert spaces by the lasry-lions method. In Annales de I I'Institut Henri Poincaré C, Anal- yse non linéaire, volume 10, 3, pp. 289-312. Elsevier, 1993.
Fang, C., Li, J., Lin, Z., and Zhang, T. Spider: Near- optimal non-convex optimization via stochastic path- integrated differential estimator. Advances in neural in- formation processing systems, 31, 2018
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foun- dations of computer science, pp. 464 473. IEEE, 2014.
Feldman, V., Koren, T., and Talwar, K. Private stochastic convex optimization: optimal rates in linear time. In Pro- ceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 4399,49,,4 2020.
Bassily, R., Feldman, V., Talwar, K., and Guha Thakurta, A.

---

Improved Private Nonsmooth Nonconvex Optimization
Flaxman, A. D., Kalai, A. T., and McMahan, H. B. Online convex optimization in the bandit setting: gradient de- scent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 385-394, 2005.
Lasry, J.-M. and Lions, P.-L. A remark regularization in hilbert spaces. Israel Journal of Mathematics, 55: 257-266, 1986.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. nature, 521(7553):436-444 2015.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-2368, 2013.
Lin, T., Zheng. Z., and Jordan. M. Gradient free methods for deterministic and stochastic nonsmooth nonconvex
optimization. Advances in Neural Information Processing Systems, 35:26160-266 60-26175, 2022.
Goldstein, A. A. Optimization of lipschitz continuous func- tions. Mathematical Programming, 13:14-22, 1977.
Liu, D., Ganesh, A., Oh, S., and Guha Thakurta, A. Private (stochastic) non-convex optimization revisited: Second- order stationary points and excess risks. Advances in Neural Information Processing Systems, 36, 2024.
Gopi, S., Lee, Y. T., and Liu, D. Private convex optimization via exponential mechanism. In Conference on Learning Theory, pp.
PMLR, 2022.
Lowy, A., Ullman, J., and Wright, S. How to make the gra- dients small privately: Improved rates for differentially private non-convex optimization. In Forty-first Interna- tional Conference Machine Learning, 2024.
Grimmer, B. and Jia, Z. Goldstein stationarity in lipschitz constrained optimization. Optimization Letters, pp. 1-11, 2024.
Hazan, E. Introduction to online convex optimization. Foun- dations and Trends@ in Optimization, 2(3-4):157-325, 2016.
Mei, S., Bai, Y., and Montanari, A.
The landscape of empir- ical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-2774, 2018.
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint 1902.039, 2019.
Mironov, Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263- 275. IEEE, 2017.
Shamir, O. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017
Jordan, M., Kornowski, G., Lin, T., Shamir, O., and Zam- petakis, M. Deterministic nonsmooth nonconvex opti- mization. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4570-4597 PMLR, 2023.
Tian, L. and So, A. M.-C. No dimension-free deterministic algorithm computes approximate stationarities of lips- chitzians. Mathematical Programming, pp. 1-24, 2024.
Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. T. P. On large- batge-batch training for deep learning: Generalization gap and sharp minima. In Inter- national Conference on Learning Representations, 2017.
Villalobos, P., Ho, A., Sevilla, J., Besiroglu, T., Heim, L., and Hobbhahn, M. Position: Will we run out of data? limits of Ilm scaling based on human generated data. In Forty-first International Conference on Machine Learn- ing, 2024.
Kong, S. and Lewis, A. The cost of nonconvexity in deter- ministic nonsmooth optimization. Mathematics of Opera- tions Research, 2023.
Wang, D., Ye, M., and Xu, J. Differentially private empiri- cal risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
Kornowski, G. and Shamir, O. Oracle complexity in non- smooth nonconvex optimization. Journal of Machine Learning Research, 23(314):1-44, 2022.
Kornowski, G. and Shamir, O. An algorithm with optimal dimension--dependenne for zero-order nonsmooth noncon- vex stochastic optimization. Journal of Machine Learning Research, 25(122): 2024.
Wang. D., Chen, C., and Xu, J. Differentially private em- pirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pp. 6526-6535, PMLR, 2019.
Kulkarni, J., Lee, Y. T., and Liu, D. Private non-smooth erm and sco in subquadratic steps. Advances in Neural Information Processing Systems, 34:4053 4064, 2021.
Yousefian, F., Nedić, A., and Shanbhag. U. V. On stochas- tic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56-67, 2012.
10

---

Improved Private Nonsmooth Nonconvex Optimization
Zhang, J., Lin, H., Jegelka, S., Sra, S., and Jadbabaie, A. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference Machine Learning, pp. 11177-11182, PMLR, 2020.
Zhang, Q. Tran, H., and Cutkosky, A. Private zeroth-order nonsmooth nonconvex optimization. In The Twelfth Inter- national Conference on Learning Representations, 2024.

---

Improved Private Nonsmooth Nonconvex Optimization
A. Proofs
A.1. Proofs from Section
Proof of Lemma 3.4. Note that for any y E Unif(8 21,, (f + ay; - f(z ay; E)lll - Ld due to the Lipschitz assumption. Hence, for any E St, by standard sub-Gaussian bound (Theorem D.2) we have
Ld Ldggoo(8dB//0)
Pr [Vf( E) Vza(zz E)l S
88/BB.
(11)
Vm
t mod Σ 1, then
11 ال'l =
(z(z)))) - Σ v((aiE\))
Bi
EE
S'ER
f((())) - vfalatE))
+
fa((z)))
Σ ffa(zt)))
B1
Bi
EESL
SESt
g'E
{((z)e)) v(a(zt)7)) -
+
Bi
C'ER
Further note that bound,
(Eees, (z((z()) - Exes Via(a; S 2L/B,, B1, hence by Equation Eq. (11) and the union
Bi
2L
Ld Idglog(SdB, /6)
Pr
(((z))))
- Σ ([(=)())
S1 51-8/8,
B
B
Vm
EES.
E'ESt
which proves the claim in the case when mod Σ 1. The other case follows from the same argument.
Proof of Lemma 3.5. By Lemma 3.4 and our assignment of m, we know that with probability at least 1 - 66/2, the sensitivity of is bounded by O L + aB,
LV(D), namely for all t:
L
LVDD
ll.. - Aell -
Bi
aB2
Then the privacy guarantee follows from the Tree Mechanism (Proposition 2.5).
Proof of Lemma 3.6. First, note that by Proposition 2.5 and the facts that E[gg] (z) and [VF((=)] S L, we get
E 1l Ilgel? 2 + do² log S E llg. VFa(2()) 2 do log E,
and also
E - - VF.
S 13 - gcll2 + E (F S d log Σ + E g. (za
Therefore, we see that in order to obtain both claimed bounds, it suffices to bound E 11gr VF. (=:))2 To that end, denote by to S t the largest integer such that to mod = 1, and note that t - to < Σ. Further denote A = gj 95-1. Then we have
Blg VF.(2)] E 9to
Σ A,
(V V.. (Fa(z)))
j=t++1
1=t++1
E 11tto
Σ
- vFd(2)-1))1
(12)
(1)
j=t++
(1))
12

---

Improved Private Nonsmooth Nonconvex Optimization
where the last equality is due to the cross terms having zero mean. We further that
(1)
E
E
910
(Z(oii))
+E
Via(ztoi:))
VF, (2to)
B
B1
S
EiESto
L2d
L
(13)
Bim
B1
as well as
(IT) E
(V5(3):)) 6) Vf(3)-1: E.) (VFa(z)) (Fa(zz-1))
B2
E:ES.
- ([( 6) Vf(3-1: - (VFa(2)) VFa(3)-))]1
B E
1
Σ
Bl]ff(2) 41) Vfalz, + +
6.) - v.a(zz-11 E
3
(la 6.) ([((z)-1: 61) (VFa - VFa(3-1)))1
2 12
d2
mB, +
(14)
a²
Plugging Eq. (13) and Eq. (14) into Eq. (12) and recalling that f to < E completes the proof.
A.2. Proofs from Section 4
Proof of Lemma 4.4. First, it suffices to prove the first bound, as
E | < lg+ V (2))1 + E (+)) E - VEP((2)) + L22
To that end, let to S be the largest integer such that to mod Σ 1, and note that to Σ. Define A, f(z--1 &.). It holds that
1 (V E.)
(Zz(
E -9:
VF 2
E 10. - (= (1))) + Σ E - (VF. - (2)-)))) +
E 11x;112..
(1T)
:=fo
(ITT)
Similar to the proof of Lemma 3.6, we have that
2
LPdL
(7)
E
Sto
V
(Z(ooiii)
S
nm
EDED
(IT)
E ||
(V (x) vf(3)-1:Ei) - (2))())) (2g
n
SED
< n EDED
Σ
V +1) Vfale; G) E & Vfa(e)-1: 5.11)
E
x
mn
(III) < do + do 1),
overall completing the proof.
13

---

Improved Private Nonsmooth Nonconvex Optimization
L'dD L'd noj naz 01 O O LLTloo(L/8)/ and 02 O
LD LLLLDVTdi To
Proof of Thhorrem 4.1. Setting m
)
the privacy
ne
ane
guarantee follows from Lemma 4.3. Moreover, by our parameter settings, we have
lodTlog(1/6)/3 n²g²
EDD 2²
c = E
V F
(=+]l
L' (1/8)/
LA log
c 1.2
n²
a²n2g²
Therefore, setting Σ= ( Dval ( ) we see that Go Ō
LVDT and G1 S + Go. By Proposition 2.6, we also know neva
that
Fa(zo) - inf Fa
3G1
E 120 (z S E 10 F2 (cout))
+
Go
DT
2/M M
2Φ
3G,
+ Go.
DT
2/M
Recalling that M = @(a/D) and setting = 0 08²
) T ô x2 ), we have
12
LVD
LVDT
E 1a
FD a
(x || =
+
DT
Va
nEva
LLB/A V
+0
nE nevoB
The latter is bounded by 39 for n = π
Lv/ c3//33372
hence completing the proof.
A.3. Proofs from Section
Proof of Proposition 5.1. Applying gradient uniform convergence bound for Lipschitz objectives over bounded domain (Mei al., 2018, Theorem 1), shows that with probability at least for any differentiable X:
(FP VF()) = δ I
dlog (R/S)
(15)
n
Therefore, given any x E X, let yı...., U3 E BBx, a) be points satisfying T, (2) A A.VP'(()) for coefficients
(Ar) | 2 0, E A 1 note that such points exist by definition of the Goldstein subdifferential. Noting that A FF()) E FgF(()) and recalling that o, F()) ) is the minimal norm element of Fz),, we get that
[a.F())] S Σ CVVF(
Σ A
(36) + vi) (+)
where vy := VF(y) (f:(2s) satisfy || = Ō L
dlog(R/C)
for all i E [k] by Eq. (15). Hence
<
> X V
(w:)
+
Σ x
<
0 D
(z)
+ Σ
Ao ||eill
1=1
dlog(R//))
<
0
+ t
[
n2
14

---

Improved Private Nonsmooth Nonconvex Optimization
A.4. Proofs from Section 6
Proof of Lemma 6.3. The case when mod 1 trivially follows the Lipschitz assumption. Thus we will consider the more involved case. For any & Sz. by standard sub-Gaussian bound (Theorem D.2) we have
I IVlog(8d22/0
Pr [Vf(Zz 5) Vfa (2:: E)Il S
21 8/8B2.
vm
so by the union bound, we get that with probability at least 6/8, for all & E St:
LV LVlog(8d22/ vm
[V/(2 5) - VLa E)
(16)
Hence,
119. gill -
1
Σ
(V)())))) vf(=(-:))) (of(a:))VV(aaa-:ee) (Vfa(z:E)) vfa(((-1()))
B2
1 ((V(azzz))) v(((==1;()) Σ (Vif(zziE)) -VialtnttVV/aattt))) V[a(Zz))))
B2 SES,
EEE
1 Σ </cc) - V(((=)11(1)))
(VI.
B2 g'ESt
LVDD
Lolog(dB3)
aB2 +
mm
where the last inequality step is due to the smoothness of fa (Fact 2.3) combined with the fact that 1|24 - 21-1/ S 2D, and Eq. (16).
Proof of Lemma 6.5. Applying by Proposition 2.5, we have
E 0 V.. (2
S E 0g gell2 Elge (F. S do log E + BBlge VFa
and also since E[g.] (2)) and V Fa (2x) 1| - L, we have
| 2 S || 2 + log Σ Elg. (Fa(=)]1 + 1.2 do? Σ.
We therefore see that both claimed bounds will follow from bounding E || VF. (z))
To that end, denote by to < t the largest integer such that to mod Σ = 1, and note that t - to < E. Further denote
A, = 9j 93-1- Then we have
E 11g VFa(2))12
= E
9to
+
Σ
A -
Σ
-VPa(2)) VE. + +
1 1=to+1
1=1++1
E
V Fa (zro))1 +
E (VF.(z,) - (Fa(2)-1))1??
==
I22
+
Σ
E E1 - (VFa(z)) (F2(
(17)
B1
j=lo
15

---

Improved Private Nonsmooth Nonconvex Optimization
where the second equality is due the cross terms having zero mean. Moreover, we have
1
= E
Σ
(Vi(zz; - ()(
(3a(())1)))
B2 ÇES.
EI((S[(2)) 6 V/(z)-1; 9) - (VP.(zz) - VFr((z-1)))
B2 SES,
B [[ 8 - Vfa(zz 0) + (2 5) Vfa(zy-1i E)1
23
SES
+ B ((V[(i() Via(z--1; - (VF.(()) VRo(t)-)))1)
2 d
mB2
a²
which plugged into Eq. (17) completes the proof by recalling that t to S E.
B. Proof of Proposition 2.6 (O2NC)
We start by noting that the update rule for A, which is given by
D A+11 min 11, noil } (A, n)t))
precisely the online project gradient descent update rule, with respect to linear losses of the form t.(- (gr, 1), over the ball of radius D around the origin. Accordingly, recalling that E 1lăe Vh(2))12 < G?. combining the linearity of expectation with the standard regret analysis of online linear optimization (cf. Hazan, 2016) gives the following:
Lemma B.1. By setting 17
D G. GM for any u E Rd with ||/||| < D it holds that
M
(gm Am u))
I 2
3 DDGVVMM
m==1
Back to analyzing Algorithm 2, since De Xt-1 + A. it holds that
Mxx)) h(xe-1) = S/' (Vi(sr- s D.) ds
E
(Vh(zz-1+ a.), A. (V)(()) A.)]-
S,.Uni((0.1]
Note that (Vh(2), = (Vh(z)), u) + (rr, A
- u) + (Vh(2)) - - A. u), so by summing over t E [T] = [K x M).
we get for any fixed sequence Wl,..., uk E Rd
inf S h(TT) S ((200) + Σ (VV()))
M
= -((0)= +
(0 A(K-1)M+m - ux)l
m=1
K M
T
E (1 +
E((Vh(zz) gc. A. -1]l
m=1
M
5 <h(w0) + +3KDG M
+ GoDT,
16

---

Improved Private Nonsmooth Nonconvex Optimization
where the last inequality follows from applying Lemma B.1 to each M consecutive iterates, and combining the bias bound E l vh(z+)]l & Go with Cauchy-Schwarz.
M m=1 mp(----
(MM)))))M-m))
Letting uy
D
rearranging and dividing by DT DKM,, obtain
K
M Vh(z(k- )MMM))) Vh(z(--DM+m))
h(zo) - inf h
3G1
E
+ GG.
(18)
DT
2/M
Finally, note that for all & E [K]. m E [M] iterate is at most of distance D to its predecessor, and therefore (1((((-1)MM-m) E da)(T)). Since the set 0-h(-) is convex by definition, we further see that
|| 21- M) -xull S MD & since the clipping operation ensures each
M
E (Th(TT)
M m==1
and hence by Eq. (18) we get
E
Dah(2
|||
1 K
Σ
K
e Bah(TTH)
M(ro) - inf h
3G1
+ Go.
DT
2v M
C. Even better sample complexity via optimal smoothing
In this Appendix, our aim is to provide evidence that the sample complexities of NSNC DP optimization obtained in our work are likely improvable, at least with a computationally inefficient method. This approach inspired by Lowy et al. (2024), which in the context of smooth optimization, showed significant sample complexity gains using algorithms with exponential runtime. As as we will show, similar phenomenon might hold for nonsmooth optimization. To that end, we propose a slight relaxation of Goldstein-stationarii and show it can be achieved using less samples via an exponential time algorithm.
C.1. Relaxation of Goldstein-stationarity
Recall that x E Rd is called an (a, GGGoldsenn stationary point of an objective F(x) [x] if there exist y1...., Vs E B(x, a) and convex coefficients (Ao)_ so that || Eien A; B S B. Arguably, the two most important properties satisfied by this definition are that
If [(x; are L-smooth, any (a, 9) sttatioony point O(a + -))-statiooary.
(ii) If Fx))
|| A O, then F x To F.. 0. PlF(x) S F(x) - a [(0
The first property shows that Goldstein--ttationaiii reduces to ("classic") stationarity under smoothness. The second, known as Goldstein's 's descent lemma (Goldstein, 1977), is generalization of the classic descent lemma for smooth functions.
is easy to see that Goldstein-stationaiie is equivalent to the existence of a distribution P supported over B(x, at), such that || FEg, pr V I| < B. We will now define a relaxation of soldstein-stationnl that easily verified to satisfy both of the aforementioned properties.
Definition C.I. We call a point E Rd an (a, ciimooettntt Goldstein-stationa point of F(x) [x] if there exist distributions P& supported over [rx,, at), such that Eg, p- (V / (v: E)]]l < 3.
In other words, the definition above allows the sampled points yI,...: M/ in the vicinity of x to vary for different components, and as before, the sampled gradient must have small expected norm. We next show that this relaxed stationarity notion allows improving the sample complexity of DP NSNC optimization.
C.2. Optimal smoothing and faster algorithm
In the previous sections, given an objective f. we used the fact that Goldstein statiionnttttinaryy points of the randomized smoothing fa correspond to Goldstein-stationas point of f, and therefore constructed private gradient oracles of fax which
17

---

Rd. Rearranging the definition of the Moreau envelope by Improved Private Nonsmooth Nonconvex Optimization
O(Vd/a)-smool Consequently, the sensitivity of the gradient oracle had v dimension dependence (as seen in Lemma 3.4), thus affecting the overall sample complexity.
Instead of randomized smoothing, we now consider the Lasry-Lions (LL) smoothing (Lasry & Lions, 1986), method that smooths Lipschitz functions in dimension independent manner, which we now recall. Given h : R + IR denote the so-called Moreau envelope
(x) = min h(w) + 2A 11 - xx12)
and the Lasry-Lions smoothing:
hxLL(*) -MX(( maxmin h(2)
| v11
2A 1ly x=1?
1
(19)
4A
Fact C.2. (Lasry & Lions, 1986; Attouch & Aze, 1993] Suppose h R² + IR is L-Lipschitz. Then: (i) hALL is L-Lipschitz; (ii) (xx h(())) S for any x E Rd;; (iii) arg min hALI. = arg min h; (iv) hxLa. is O(L/ (LL///smmoohh
The key difference between LL-smoothing and randomized smoothing is that the smoothness constant of Lmootohtiing is dimension independent. By solving the optimization problem in Eq. (19), it is clear that the values, and therefore gradients, of JALL &,) can be obtained up to arbitrarily high accuracy, Notably, it was shown by Kornowski & Shamir (2022) that solving this problem requires, in general, an exponential number of oracle calls the original function.
Nonetheless, computational considerations aside, a priori it is not even clear that the LL smoothing can help finding Goldstein-statee statiinnrrt points of the original function, which was previously shown for randomized smoothing (Lemma 2.4).
This is the purpose of the following result, which we prove:
Lemma C.3. If h is L-Lipschitz, then any 3-stationary point of hALL is (3XL, 3) Goldstein stationary point of h.
Given the lemma above, we are able to utilize smooth algorithms for finding stationary points, and convert the guarantee Goldstein-statin stationary points of our objective of interest. Specifically, will invoke the following result.
n Ei= f(x; {s) with Lo Lo-Lipschitz and Lı-shooth components, and an initial point Tn E IRd such that dist arg min F) I R, there's 's an (c, DDD algorithm that returns jout with V P [Fo Ō R2/3 12//312/111 11/3 ga
Proposition C.4 (Lowy et al., 2024). Given an ERM objective F(z) 1
Lovd d ne
ne
We remark that we assume for simplicity that (as arg min (P) dist(rro, arg min F) < R. though the analysis extends that where R is the initial distance to point with sufficiently small loss (e.g.. if the infimum is not attained). Overall, by setting À = a/3L, and combining Fact C.2, Lemma C.3 and Proposition C.4, we get the following:
Theorem C.5. Under Assumption 2.2. suppose dist(2o, arg min fP) S R. Then there is an (e, algorithm that outputs out satisfying (a, (a,8) co-cooooonettwwiii Goldstein Goldstein-stationane stationarity (in expectation) as long as
RR//3 LA/3
Ω
/33
C.3. Proofs from Appendix C
Proof of Lemma C.3. Suppose z is a --stationarry point of hALL- Let 2" E Rd be the solution of the maximization problem defining the L.L smoothing. By (Attouch & Aze, 1993, Remark 4.3.e), 2" uniquely defined, and satisfies
VisLi(*) E (1))=))
(20)
Further denote y == arg miny [b(y) + 4x expanding the square, we see that
1 -1 y113]
M2x(1)(²*)=
1
1|=
1
max (z*,0) 2Xh(v) [1v11]
47
2X
18

---

Improved Private Nonsmooth Nonconvex Optimization
from which we get
1 (3* 21
(3)=
0M2xh(=*) 2X =" conv {v" : y conv
(21)
2X
Furthermore, for any '² E by first-order optimality it holds that
1 41 l1y" 2 =11p] s Oh(y")
1
0 0 h(y") +
+
2 (v" - -2"),
2x
and therefore
(3* y²) ah(y").
(22)
By combining Eq. (20), Eq. (21) and Eq. (22) we conclude that
(h)LL()) E 0M2xh(²") conv (Oh(y"): :/¹ {
S 0,h(2))
where the last holds for m |æe v" Therefore, recalling that [ S
all that remains is bound
To that end, it clearly holds that S || - - + max," Ev" || y" Furthermore, by (Attouch & Aze, 1993, Remark 4.3.e) it holds that 2" maxy ED* ||2" y"1 < 2A- MaX) [g|| < 2XL, by the fact that M2x (h) is L-Lipschitz. Overall S XB + 2AL, and as we can assume without loss of generality that 3 s L since otherwise the claim is trivially true (note that all points are stationary), this completes the proof.
AVhxa (z) which implies || - A3. As to the second summand, by Eq. (21) it holds that
D. Concentration lemma for vectors with sub-Gaussian norm
Here we recall standard concentration bound for vectors with sub-Gaussian norm, which notably applies in particular to bounded random vectors.
Definition D.1 (Norm-sub-Gaussian). We say a random vector X E Rd is Ç-norm-sub- Suaussuu for Ç > 0, if Pr
XX 2 1) < -t/22 for all & ' 0.
Theorem D.2 (Hoeffding-type inequality for Sram--uu-Gauusiaan Jin et al., 2019). Let X .x E IRd be random
vectors, and let F. o' XX.) for [k] be the corresponding filtration. Suppose for each i [k]. X; Fi zero-mean Çy-nrrm-sube sub- Gaussian. Then, there exists absolute constant >> O, such that for any 0
Saarm--u--Gaussinn
Pr
Σ X; kE[k]
2c
log(d/7)
Σ kE[A]
?
ST.
19


Reviews:
[{"review_id": "m0fSZzWpel", "reviewer": "Reviewer_haDW", "summary": "The paper provided presents advancements in differentially private (DP) optimization algorithms for stochastic and empirical objectives that are neither smooth nor convex. Here is a summary of the results:\n\n1. Zeroth-order Single-pass algorithm.:\n- The proposed $(\\epsilon, \\delta)$-DP algorithm improves the dependence on the number of dimensions over existing algorithms by a factor of $\\Omega( \\sqrt{d} )$ in the leading term.\n\n2. Zeroth-order Improved multi-pass algorithm:\n- To further reduce the sample complexity, a multi-pass polynomial time algorithm is introduced. This algorithm returns the first known algorithm in private ERM with sublinear dimension-dependent sample complexity for non-smooth non-convex objectives.\n\n3. First-order algorithm with reduced oracle complexity: A first-order (i.e., gradient-based) algorithm is also provided, which maintains the sample complexity but reduces the oracle complexity compared to its zero-order counterpart. This makes the gradient-based algorithm significantly more efficient in terms of oracle calls, confirming it as the best-known method in terms of both sample efficiency and oracle efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer and are encouraged by the positive review!\n\nDesigning optimization algorithms for nonsmooth-nonconvex losses is a topic that gained substantial attention recently mainly due to deep learning applications. Indeed, only few works further provide grounded privacy guarantees when optimizing such losses, as this is a relatively new area of research, yet as the reviewer noted, “Preserving privacy of the data used to train machine learning models is a very important area with broad interest.”   Our work aims to bridge this gap and provide foundational algorithms that may be widely applied as privacy-preserving machine learning continues to grow in importance.", "claims_and_evidence": "See above.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "I understood the high-level ideas of the proofs but I was not able to check all the details.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "Preserving privacy of the data used to train machine learning models is a very important area with broad interest.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths\n-----------------------------------\n\n- The paper provides a clear improvement for a natural problem defined recently by Zhang et al. 2024.\n\n- The paper is well-written and it provides a very clear comparison to previous work.\n\nWeaknesses and Comments\n-----------------------------------\n\n1. Although this is a clear improvement of Zhang et al. 2024, the problem studied is esoteric and for this reason it seems that is of interest to a small group of people specialized on this topic.", "other_comments_or_suggestions": "No.", "questions_for_authors": "See Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hQ2ISOD7fE", "reviewer": "Reviewer_bTS4", "summary": "This paper presents novel differentially private (DP) optimization algorithms for nonsmooth and nonconvex objectives, with a focus on achieving Goldstein-stationary points while improving sample complexity. The authors introduce a single-pass algorithm that improves the sample complexity by a factor of $\\sqrt{d}$ over previous results, as well as a multi-pass algorithm that further reduces sample complexity while preserving privacy guarantees.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer and are encouraged by the positive review!", "claims_and_evidence": "The claim presented in this paper appears to be clear and correct.", "methods_and_evaluation_criteria": "The privacy and utility guarantees of the algorithms have been rigorously proven.", "theoretical_claims": "The proof appears to be correct.", "experimental_designs_or_analyses": "Not applicable; the proof appears to be correct.", "relation_to_broader_scientific_literature": "This paper contributes to the literature on differentially private optimization, particularly in the context of nonsmooth and nonconvex objectives.", "essential_references_not_discussed": "The paper appears to provide sufficient references to related work.", "other_strengths_and_weaknesses": "Strength:\n\n* This paper introduces novel algorithms and improves the sample complexity for differentially private nonsmooth and nonconvex (DP NSNC) optimization problems.\n\n* The application of a concentration argument to tighten the sensitivity bound of the gradient estimator is particularly noteworthy and adds technical depth.\n\nWeakness:\n* The algorithmic components, such as the use of the tree-based mechanism, have been explored in prior work. However, the analytical approach adopted in this paper appears to be original and contributes new insights.", "other_comments_or_suggestions": "I did not identify any noticeable typographical errors in the paper.", "questions_for_authors": "Overall, I find the paper to be well-written and clear, and I have no further questions at this time.\n\n## update after rebuttal\nI keep my positive score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VDIgvEk9c2", "reviewer": "Reviewer_Qpoq", "summary": "This paper studies the problem of non-smooth non-convex (NSNC) optimization problem under the constraint of differential privacy (DP). The authors first proposed a zeroth-order and single-pass NSNC-DP algorithm that achieves sample complexity of $O(\\frac{1}{\\alpha\\beta^3}+\\frac{d}{\\epsilon\\alpha\\beta^2}+\\frac{d^{3/4}}{\\epsilon^{1/2}\\alpha\\beta^{5/2}})$ to find a $(\\alpha,\\beta)$-Goldstein stationary point. Notably, this result improves from the existing best rate by a factor of $\\sqrt{d}$, and the key is an improved zeroth-order gradient estimator that has an improved sensitivity in high probability. In addition, the authors also extend the result to the ERM problem where they proposed a multi-pass algorithm, and connected the result to the stochastic case by showing a reduction of Goldstein stationary point from ERM loss to generalization loss. Finally, the authors proposed a first-order algorithm, showing it achieves the same sample complexity while reducing oracle complexity by $O(d^2)$.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer and are encouraged by the positive review!\nWe clarify the raised issues below:\n\nRegarding the \"weakness\" mentioned, we want to clarify that we did not assume anything stronger than previous results. In our proof, we use concentration inequalities for sub-Gaussian vectors, but these vectors are actually bounded due to the Lipschitz assumption (a standard assumption in the literature, also used by Zhang et al. (2024)).\n\nWe address the Questions below:\n\n(1) We are not aware of a sample complexity lower bound in the non-private literature for finding a Goldstein-stationary point. Regarding oracle complexity, it is known to be $\\Theta(1/\\alpha\\beta^3)$ (see Cutkosky et al., ICML 2023). As pointed out by Reviewer rnQ5, there is a small bug in our analysis that leads to a worse non-private term $O(\\sqrt{d}/\\alpha\\beta^3)$  after fixing the error (primarily by resetting the hyperparameters). Despite this, our result still breaks upon the zero-order oracle lower bound of previous work. The dimension-dependence likely stems from the randomized smoothing technique we employed. We conjecture that the previously claimed dimension-independent bound $O(1/\\alpha\\beta^3)$ could be achieved, possibly through an improved smoothing technique. Therefore, we cannot currently determine the full extent to which our results might be further improved.\n\n(2) Yes, this is true. As discussed in Remark 3.3, our choice of m aims to minimize the sample complexity, and we will rewrite this to be more clear that this is indeed at the cost of larger oracle complexity in the zero-order case.\n\n(3) The privacy guarantee always holds - the tail event is accounted for in the 'delta' in the $(\\epsilon,\\delta)$-DP definition, which allows the privacy to break with probability at most $\\delta$. As the reviewer correctly guessed, this approach is indeed standard in the DP literature, and we also discuss this in the Discussion section.", "claims_and_evidence": "NA", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "The theoretical claims are valid.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "This work fits in the subfield of DP optimization for NSNC objectives. The proposed zeroth-order algorithm improves the existing best known rate in the literature. Furthermore, this paper also provides a multi-pass algorithm for ERM problem, and a first-order algorithm, which are both the first results in the literature.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "### Strengths\n\nThis paper provides very concrete results for DP-NSNC optimization problems. The main result, a zeroth-order single-pass algorithm equipped with an improved gradient estimator, improves the sample complexity by a factor of $O(\\sqrt{d})$ compared to the best know rate in the literature. This is a significant result since the optimal rate is yet unknown, and technical novelty of using a low-sensitivity gradient estimator is interesting by itself. Furthermore, the proposed multi-pass zeroth-order algorithm and the first-order algorithm are the first results in the literature. \n\n### Weaknesses\n\nI think the high probability guarantee of the sensitivity implicitly assumes the gradient estimator has norm-sub-Gaussian noise, which is not clearly justified. This is a slightly stronger assumption than standard literature.\n\nOverall, I think this paper greatly contributes to the understanding of DP-NSNC problem, and I'd recommend acceptance.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Regarding the non-private term in the single-pass bound, do the authors know if $O(1/\\alpha\\beta^3)$ is the optimal sample complexity for non-private NSNC optimization? Also, could the authors further elaborate on Rmk 6.2 that the oracle complexity of first-order algorithm is $d^2$ smaller than zeroth-order algorithm while they achieve the same sample complexity? Does that imply the sample complexity of zeroth-order algorithm could possibly be further improved?\n\n2. In terms of oracle complexity, it seems that $m\\gg d^{3/2}$. Is it true that the oracle complexity of zeroth-order algorithm is larger than the previous algorithm by Zhang et. al. 2024 (where their sample complexity if $\\sqrt{d}$ worse, but oracle complexity is fixed to be $d$ per sample)?\n\n3. The privacy guarantee is based on high probability bound of the sensitivity instead of a worse case (almost surely) bound. Would that break the privacy guarantee? For example, in the tail event where sensitivity is unbounded, I think privacy no longer holds since the divergence is no longer bounded. Is there a known result that fixes the issue, e.g. some theorem like privacy guarantee in high probability generalizes to privacy guarantee almost surely.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rAYyONl6cj", "reviewer": "Reviewer_rnQ5", "summary": "This paper provides randomized algorithms for nonconvex nonsmooth optimization under the constraint of differential privacy. The sample complexities of zeroth-order algorithms are greatly improved over those of the previous work (Zhang et al. 2024). \nIn addition, the author further extended the methodology with first-order algorithms to reduce the oracle complexity.\n\n## update after rebuttal\nThe author's reply makes sense, so I keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their work and are encouraged by their appreciation of our results!\nWe will incorporate the suggested changes and references into the final version.\n\nWe are extremely grateful for the reviewer's careful review and for finding numerous typos. We note that the only change incurred by these straightforward fixes (specifically, due to the $\\sqrt{B_1}$ in the denominator in Line 286) will be the non-private term in Theorem 3.1 becoming $\\sqrt{d}$ times larger, that is $\\sqrt{d}/\\alpha\\beta^3$. We emphasize that this does not affect the main claims in our paper: Our obtained complexity is still $\\Omega(\\sqrt{d})$ smaller than previous results, and still breaks the erroneous lower bound claimed in previous work. Moreover, neither of our improved empirical/generalization results later in the paper are affected. \n\nWe conjecture that the previously claimed dimension-independent bound $O(1/\\alpha\\beta^3)$ might still be achievable. The $\\sqrt{d}$ factor appears to stem from the randomized smoothing technique we employed. With improved smoothing approaches, it may be possible to eliminate this dimension dependence. In the final version we will accommodate the current fix accordingly, explore this conjecture further, and plan to acknowledge the reviewer for their help.\n\nWe also appreciate the references suggested by the reviewer. We will add proper citations to Abadi et al. (2016) for the moment account method for privacy composition, as well as to Kulkarni et al. (2021) for their enhancements to the approach.\n\nRegarding the oracle complexity concern, the reviewer is correct that our choice of large $m$ increases the oracle complexity. As noted in Remark 3.3, our parameter choice prioritizes minimizing sample complexity, which comes at the cost of increased oracle calls. In the final version, we will clarify this trade-off more explicitly and discuss potential approaches to balance sample and oracle complexity for different application needs.", "claims_and_evidence": "Strength:\n\n* The sample complexity of zeroth-order algorithms greatly improves over existing work (Zhang et al. 2024).\n\n* The generalization from ERM to excess population loss of nonconvex nonsmooth optimization is a novel and interesting result.\n\nWeakness:\n\n* Although the sample complexity of the proposed zeroth-order algorithms is greatly reduced, these methods have high oracle complexities due to the choice of a large $m$. The overall oracle complexity is no better than the previous work.\n\n* There are multiple typos in the proofs, which makes them hard to read.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are sound and make sense to me.", "theoretical_claims": "I checked the proof of most theorems in the main text and supplementary materials, there are some typos and errors. Most errors are negligible, and some are really confusing. \nLet me list some typos as follows:\n\n* In Line 236 Theorem 3.1, should the nominator value of $m$ be $\\log(d B_1 \\delta)$?\n\n* In Line 286 Theorem 3.1, I am confused that the denominator of the first term is $B_1$ instead of $\\sqrt{B_1}$. Taking square root on both sides of Lemma 3.6 will give you $\\sqrt{B_1}$.\n\n* In Line 575, the proof of Lemma 3.4, the right-hand side of $\\geq$ in the probability seems to miss one term $2L / B_1$\n\n* In Line 602, the term II should sum from $t_0 + 1$ to $t$?\n\n* In Line 608 Eq. (13), subscripts should be $\\xi_i$ instead.\n\n* In Line 656, is (III) miss a factor of $d$ in the second term?", "experimental_designs_or_analyses": "I do not think experiments need to be provided for this paper.", "relation_to_broader_scientific_literature": "This paper is a really interesting work for private nonconvex nonsmooth optimization, however, there are too many typos in the proof.", "essential_references_not_discussed": "Some essential references to differential privacy are not discussed in the paper. For example, the multi-pass algorithm uses the moment account method for privacy composition, which was introduced in the following paper:\n\n* Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016, October). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security (pp. 308-318).\n\nTheir proof was enhanced by the following manuscript:\n\n* Kulkarni, J., Lee, Y. T., & Liu, D. (2021). Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103.15352.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper develops a new differentially private algorithm targeting the non-smooth non-convex optimization problem. In the single pass/gradient oracle constrained setting, it improves the dimension dependency of prior work. In the general multi-pass setting/sample constrained setting, it provides an improved sample complexity. Reviewers are generally positive about the significance and presentation of the results.
Decision: Accept (poster)