Private Zeroth-Order Nonsmooth Nonconvex Optimization
Authors: Qinzi Zhang
Hoang Tran
Ashok Cutkosky
Venue: ICLR 2024 poster (2024)
Keywords: optimization
differential privacy
non-convex
non-smooth
Primary area: optimization

Abstract: We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives.
Given a dataset of size $M$, our algorithm ensures $(\alpha,\alpha\rho^2/2)$-Renyi differential privacy and finds a $(\delta,\epsilon)$-stationary point so long as $M=\tilde\Omega(\frac{d}{\delta\epsilon^3} + \frac{d^{3/2}}{\rho\delta\epsilon^2})$.
This matches the optimal complexity found in its non-private zeroth-order analog. 
Notably, although the objective is not smooth, we have privacy ``for free'' when $\rho \ge \sqrt{d}\epsilon$.

Published as a conference paper at ICLR 2024
PRIVATE ZEROTH-ORDER NONSMOOTH NONCONVEX OPTIMIZATION
Qinzi Zhang, Hoang Tran & Ashok Cutkosky Department of Electrical and Computer Engineering Boston University Boston, MA, USA
{qinziz, tranhp, cutkosky) edu
ABSTRACT
We introduce new zeroth- order algorithm for private stochastic optimization nonconvex and nonsmooth objectives. Given dataset size M, our algorithm ensures (ox, axp² (tp2//2)Réén)) differential privacy and finds (6, e)-stationary point long M i 82s +
d²/2
pōcz This matches the optimal complexity of its
non non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy "for free" whenever p 2 vdc.
INTRODUCTION
We study the stochastic optimization problem the form
min F(x: [.
25 2ER4
where the stochastic function f(x, 2) might be both non-convex and non-smooth with respect to æ. Our focus is on zeroth-order algorithms, often referred to as gradient-free algorithms. Unlike first-order algorithms that have access to the stochastic gradient [a z). zeroth-order algorithms can access only the function value f(x,22)
Non-convex stochastic optimization is fundamental modern machine learning. For example. in deep learning, x is the weight of some neural network model, is a datapoint, and f(æ, z) repre- sents the loss of the model evaluated on and z. Consequently, training the machine learning model equates to minimizing the non-convex objective F(x). Given its significant role, there has been marked increase research focusing on non-convex optimization recent years (Ghadimi Lan
2013
Arjevani et al. 2019; 2020, Carmon et al.) 2019 Fang et al., 2018 Cutkosky & Orabona Since finding global minimum of non-convex F(x) intractable, many previous works assume that F is smooth, and their goal is to find an e-stationary point where [[v]())] However, objectives are not always smooth, especially with the ever-increasing complexity mod- machine learning models. Making the problem even more difficult, recent research shows that
2019
finding an c-stationary point of non-smooth objective might be intractable (Zhang et al., 2020
Kornowski Shamir 2022).
To address this issue, Zhang et al. 2020) introduces an alternative objective for the convergence analysis of non-smooth non-convex optimization. Specifically, they propose the notion of Goldstein stationary point (Goldstein, 1977): æ is said to be an (ō. e essttiionn point of F if there exists subset S in the ball of radius centered æ such that |EE [v)())]] < where y uniformly distributed over S. Recently, there have been many works on first-order algorithms using this frame- work (Zhang et al. 2020 Tian et 2022, Cutkosky et al., 2023). Notably, Cutkosky et al. (2023) designs an "Omline-to-non--oowee Conversion" algorithm that finds (ő, -statiooty point with 06 samples, which is proven to be the optimal rate. However, first-order algorithms have their own limitations. For many applications, computing first-order gradients can be computation- ally expensive or even impossible (Nelson 2010 Mania et al. 2018).. Hence, there are many recent results focusing on designing efficient zeroth-order algorithms for non-smooth non-convex opti- mization (Lin et al., 2022 Chen et al.) 2023) Kornowski & Shamir (023). Recently, Kornowski & proposes zeroth-order algorithm that requires only O(db O(dd-Le-3) -33 samples, which is
Shamir (2033)

---

Published as a conference paper at ICLR 2024
the current state-of-thee thrt rate for zeroth-order optimization non non-smooth non-convex objectives. The additional dimension dependence is an inevitable cost of zeroth-order algorithms even when the objective is smooth convex (Duchi et al. 2015).
In this paper, we study zeroth-order stochastic optimization on non-convex and non-smooth objec- tives. Zeroth-order optimization is particularly important in cases where memory is constrained or the model is excessively large so that computing a backwards pass is forbiddingly expensive. In ad- dition, we also aim to protect the privacy of user's data. For example, consider the practical problem of training recommendation model or a chat response model. At each step the algorithm is given a set of different users who report the model's performance in the form of "upvotes" or "downvotes". It's important to make updates using such zeroth-order feedback while preserving the privacy of feedback from the individual users.
To this end, we require our algorithm to be differentially private (DP) (Dwork et al. 2006). which means with high probability, the output of our algorithm operating on any particular dataset is almost indistinguishable from the output when one datapoint in the dataset is perturbed.
The primary objective of private stochastic optimization is to minimize the dataset size required to solve the optimization problem while maintaining differential privacy guarantees. This area has seen extensive research efforts. While problems with convex objectives have been well-studied over the
past decade (Chaudhuri et al. 2011 1 Jain et al. [0012] Kifer et al. 2012 Bassily et al. [2014] Talwar
ct al. 2014, Jain & Thakurta 2014; Bassily et al. 2019) Feldman et al. 2020 Bassily et al. 2021b
Zhang et al.
private non-convex optimization (Wang et al. 2017: 2019a Tran & Cutkosky [2022] Wang et al.] 2019b] Zhou et al.] 2020; Bassily et al,,
2002), , more recent efforts have focused
202 Arora et al. 2023). Recently, Arora et al. (2023) designs an algorithm that, assuming the
objective is smooth, finds an e-stationayy point and satisfies (p, 7-DP with
data
complexity. While private non-convex optimization has seen rapid advancements, certain challenges remain. Many previous studies hinge on the assumption of smooth objectives since their methods are essentially extensions of non-private non-convex optimization algorithms. In fact, this limitation emerges even in situations where the objective is convex, in which case smoothness provides a critical tool for reducing sensitivity. Since the results in non-smooth non-convex optimization are recent, its differentially private counterpart remains largely unexplored.
1.1 OUR CONTRIBUTIONS
The main contribution of this paper is the introduction of zeroth-order algorithm for differentially private stochastic optimization on non-convex and non-smooth objectives. To our knowledge, this the first work under this framework. Our algorithm satisfies (a, ap² 22))Rényi differential privacy (RDP) [Mironov| 2017) (which is approximately (p, 7DDPP) and finds (6, e) -Sstatiionary point with Öd88 + 10-1 10-88-1- ---) data complexity. Notably, the non non-private term O(ōō (idd--ee" -e- matches the tiite--f-thhe art complexity found in its non-private counterpart. Moreover, when p 2 vde, the non-private term is dominating, suggesting that privacy can be attained without additional cost. This is consistent with the observations when the objective is smooth (Arora et al. 2023).
Our algorithm incorporates four essential components, each crucial for achieving the optimal rate. We leverage the non-private Online-to-non-convee Conversion (O2NC) framework by Cutkosky eet al. (2023), which finds (ō, --statiionaryy point of a non-smooth objective using a first-order ora- cle. We then build an approximate first-order oracle (i.e. a gradient estimator) with a zeroth-order oracle. Although this high-level strategy is a common technique, our approach distinguishes itself through its gradient oracle design. In contrast to prior non-private approaches that directly approxi- mate the gradient with standard zeroth-order estimator (Kornowski & Shamir 2023), we introduce a variance-reduced gradient oracle. Our approach incorporates two zeroth-order estimators: one for the gradient and another for its difference between two points. Our gradient oracle also differs subtly from the standard zeroth-order estimator by sampling i.i.d. estimators for each data point, which is required to achieve the optimal dimension dependence. Both estimators exhibit reduced sensitiv- ity. We reduce the privacy cost of our variance-reduced estimators by using the "tree mechanism" (Dwork al.) 2010 Chan et al. 2011). yielding a new tfate-ofthhe-an art privacy guarantee.
Omitting any component from our algorithm significantly impacts the results. Neither utilizing the O2NC technique nor sampling d i.i.d. estimators results in an additional dimension dependence of
2

---

measure of Published as a conference paper at ICLR 2024
Vd. Moreover, the combination of the variance- variance-reduced reduced oracle and the tree mechanism is crucial for optimal privacy. A naive approach might directly make O2NC private adding noise to classical zeroth-order gradient estimators, but this yields sub-optimal rate with an extra factor of e More details about the intuitions and challenges of our algorithm can be found in Section 4.1
2 PRELIMINARY
Notation We use bold font æ to denote a vector æ E Rd, and denote the Euclidean norm of æ by ||>|| We denote the unit ball and unit sphere in E by B and S. and denote the uniform distribution on B and S by U3 and Ug respectively. We denote an open ball in IR centered at z of radius r by B)x,r) {v : | yll < r)- For n N, we denote the set {1, ..... n) by [n], and we denote sequence d1.-.., an by dim- We use the standard big-O notation, and use Ô to hide additional logarithmic factors. We interchangeably use f(x X g(x) denote f(x) (g(x)).
Non-smooth Optimization A function h : for all æ, y RR h is H-smooth if differentiable and [[Vh(z) Vh(y)l S H|I yl for all a. V E Rd A point x² E Rd is an e-stationary point of h if |Vh(2=)] S
Rd - R is L-Lipschitz if h/(x) h(y) s L y
and h Idd + R be differentiable. The Goldstein 6-subdifferential of is 0gh(2r) (z) conv(UyEBla.s) 8) Vh(y)). We define [/Vh(a))ls inf 9 @sh(x)). Then x" is said to be Goldstein (6, -tsttioony point of h if Vh((=*)] )|s e. Note that
Definition 2.1. Let
[V & inf SCB(a.)) Eyes Vh(y)
Differential Privacy A stochastic optimization algorithm can considered as a randomized al- gorithm that takes a dataset Z (a collection of data points ..,.... 2M) and outputs an output w. Throughout this paper, we denote 2 as the set of all possible datasets of size M. Two datasets 2, Z' E Z are neighboring if they differ only in one data point. A randomized algorithm A Z - R is said to be (e, 8) difffcrentially private ((c, dD) for e, 8 > 0 for all neighboring datasets Z, Z' and measurable E C R. we have P(A(Z) E E} S E P(A(Z)) E} + 8 Dwwork et al. 2006).
Another common privacy measure is Rényi differential privacy (RDP). Algorithm A (a, PDDP for > 1, 0 if for all neighboring Z, Z', (a())))(A(Z)) S م (Mironov 2017). where (a(u)) is the Rényi divergence of distributions μe, V. RDP can be converted to [c. DD- as fol- lows: an algorithm is (a. ap² RDD for all a > 1, then it is also (2pln(1/ 1/2 8D for all 5 2 exp( p²) (Mironov 2017 Proposition 3). Therefore, use (a, ap² RDDP
differential privacy in our paper.
If [|A(()) A(Z')l I for any neighboring Z, Z' we say the sensitivity of A is bounded by It well known that in this case, adding a Gaussian noise (00 o2]) to the output of A, where sspp. ensures that A is ax,ap22)) /2))/22DDDPPP (Mironov 2017).
We also make use of the "tree mechanism" Dwork et al. 2010); Chan et al. (2011). which is a technique that allows for private release of running sums of potentially sensitive data (Algorithm 55)
algorithm by Cutkosky et al. 2023), so we briefly introduce the setting of online convex optimization (OCO) (Cesa-Bianchi & Lugosi 2006 Hazan 2019: Orabona 2019). An OCO algorithm proceeds in rounds. In each round 1, it outputs F,, receives a convex loss function (a(),, and suffers loss & (x;). It common to use linear loss fx(xx) (), An OCO algorithm has domain bounded by D if ||xll| < D for all t.
Online Learning Our algorithm builds on the Online-to-non-cont
The goal of online learning is to minimize the static regret defined as
(egr(u) = Σr (xx))) fe(u) = Σt= (Vi, u
where is some comparator vector (often, arg min ΣT (z))). There many OCO algo- rithms that achieve the minimax optimal O(VT) regret. For example, projected Online Subgradient Descent (OSD) (Zinkevich 2003) with domain bounded by D satisfies
E E[Regy < DV Et Eluu,11
3

---

Published as a conference paper at ICLR 2024
Uniform Smoothing Randomized smoothing is well known technique that converts a possibly non-smooth function to a smooth approximation (Flaxman et al. 2005 Duchi et al. 2012 Lin et al. 2022). Given a Lipschitz function h R + R and ò > O, we define the uniform smoothing of hx) Ev-22 (x -66)]. In later sections, we denote Fs(x) and fa 2) as the uniform smoothing of the objective F(x)) and f(æ, z) respectively. As shown in prior works (see (Yousefian al., 2012) and Duchi al. (2012) Section E)), uniform smoothing is a smooth approximation whose gradient can be estimated by finite differentiation. We rephrase the key properties in the following lemma, whose proof is presented in the appendix for completeness.
Lemma 2.2. Suppose h - + IR is L-Lipschitz. Then (i) hy is L-Lipschitz: (ii) [1/((1)) -achs(a))((aa0 h(x)l s L8; (iii) hy is differentiable and x/LL smoothh (iv)
Vhg(x) = Eurit h= + ōu)u] = Eu-lts 28
(h(w + o')) - h(x 8
As corollary, finding (ò, e) -statioonayy point of Fg is sufficient to find an (26, e) )-sttationary point
of F. The formal statement is as follows (Kornowski & Shamir (2023 Lemma 4); proof presented in Appendix A completeness).
Corollary 2.3. Suppose F : Rd is L-Lipschitz. Then for any c, 8 > 0, that V F ((x)]128 S. c.
S c iimplies
2.1 ANALYSIS ORGANIZATION
As a brief overview, our algorithm leverages O2NC to privately optimize the uniform smoothing of the objective. Note that O2NC does not require any smoothness itself employ uniform smoothing because it allows us to construct a low-sensitivity gradient oracle from a zeroth-order oracle. The smoothness property is tangential. We construct variance-reduced gradient oracle for O2NC and incorporate the tree mechanism for enhanced privacy. This oracle is based on two zeroth-order estimators: one for the stochastic gradient of the uniform smoothing and another for the gradient difference.
This paper is organized in the following order. In Section 3 we introduce the zeroth-order estima- tors. In Section 4.1 we present the O2NC algorithm combined with the private variance-reducee gradient oracle. In Section[4.2 we demonstrate the improved privacy guarantee provided by the tree mechanism. We conclude with the convergence analysis in Section
ZEROTH-ORDER ESTIMATORS
Let F(x) = [E =]] and denote F, and fsx as the uniform smoothing of F and f respectively. Using the randomized smoothing technique from Lemma 2.2 we can construct unbiased zeroth- order estimators for both V (x)) and F
(y)) The key properties of these estimators GRAD and DIFF, as defined in Algorithm and 2 are summarized in the following results.
Lemma 3.1. If fxx is differentiable and L-Lipschitz in æ, then for any å 0, E Rd and neighboring data batches Z1d; Z/. of size b,
E[GRAD (2RRAD,,,(0,21100 (10)) = vis(
(unbiased)
E ElIGRAD,,5 21:6) ( 16d1.
(variance)
||GRAD,, 213)) .RRADy, (2r, 21,x)) S 2dl
(sensitivity)
Lemma 3.2. fxx 2) is differentiable and L-Lipschitz in x, then for any 8 > 0, x, neighboring data batches 21.b: Z'.a. of size b,
IRd and
E|DIFF (.x y, 21+0]] v Fs(x)) Fs()))
(unbiased)
EI s y, 21:h) [v)((x) vir(v))11
16d1. 1
1
211
(variance)
DDFF y. 21:6) ( U, A1 S
2dl. 16
o
yl|
(sensitivity)
4

---

Published as a conference paper at ICLR 2024
Algorithm
gradient oracle GR 213h)
Input: loss function f. constant d > 0, parameter æ, i.i.d. data batch Z1:b
1: Sample wily.... Udd Uniform(S) i.i.d.
Return 6, 21:)) = Em= //4 د 28 (f(x + Bug 21) - f( - -reis zi) 2u)ss
2:
Algorithm 2 Zeroth-order gradient difference oracle DIFF (., y, 21:b)
Input: loss function f. constant å >> 0, parameter x. y, i.i.d. data batch 21:b
1: Sample "1....., Wdd ~ Uniform (S) i..d.
2: Return DIFF 5 az y, 21:b) Σ à Eÿ= (f(( + oui, 2i) - f(y + 8rei. 24 2uyy.
Proofs for Lemmas 3.1 and 3.2 are both stemming from the uniform smoothing properties detailed in Lemma 2.2 We defer the proofs to Appendix [ Notably, these lemmas indicate that both the gra- dient and gradient difference estimators are unbiased, with low variance and sensitivity. Specifically, in our final algorithm, we will be able to control the distance between parameters æ; y in two suc- cessive iterations by 5/T. As a result, the variance in Lemma 3.2 is bounded by O(dL² /bT"), and its sensitivity is bounded by O(dL Using these estimators, we construct zeroth-order gradient oracles by exploiting the decomposition (ax)) = F (x1) + E (x.) - V (x;-1) Rd GRAD (01,=) E DIFF,, (Z:,, =)) Our constructed oracles have low variance and low sensitivity, thus allowing us incorporate the tree mechanism to privately aggregate the sum with less noise. A more detailed exploration of this idea is presented in the subsequent sections, especially in Corollary 4.4 and Lemma 4.8]
In addition, we would like to discuss the rationale behind sampling d i.i.d. uniform vectors Ui for each data point 24- For the gradient estimaton GRAD, it is feasible approximate V far, 2;) with single two-point estimator, namely g. 28 (f(x + ōu, 2;) - f(x ōu, z)) as it is proved that El]g: ||2 (dI,2) (Shamir) 2017, Lemma 10). The central argument hinges on a concentration inequality for Lipschitz functions, which states that if h is L-Lipschitz on u and u ~ Us. then dt²
P(h((u) - [Eh(u)] 2 1} < 2 2exp(- 21,7) as per /Wainwright 2019) Proposition 3.11. In the context of their proof, h(u) = f(z + 5u) which is Lo-Lipschitz.
However, this argument isn' applicable to the gradient difference estimator DIFF. In order to apply the concentration inequality, we need to bound the Lipschitz constant of h(u) = f(x + gu) fly + Su). Although this function is indeed 2.8--ipss using this would bound the variance at O(T?2), which doesn't it match our target of O /T²). On the other hand, directly using the Lipschitzness of f bounds E||; (f(x ōu, 2)
((, 2ll2 S (dL [|xx-y))² = Consequently, we need to sample d i.i.d. uniform vectors reduce the dimension dependence of the variance by a factor of d in order to match the optimal rate. While a more efficient analysis that avoids sampling d uniform vectors might exist, we currently unaware of it.
OUR ALGORITHM AND RESULTS
4.1 PRIVATE ONLINE-TO-NON-CONEE CONVERSION
Our algorithm builds on the Online-to-Nee -ono--ovoooo Conversion (O2NC) by (Cutkosky et al. 2023), which is general framework that converts any OCO algorithm with O(vT) regret into nonsmooth nonconvex optimization algorithm that finds a (5, c)-stationary point in O -I c-3) iterations. The pseudo-code of this framework is presented in Algorithm
algorithm chooses projected Online Subgradient Descent (OSD) as the OCO a algorithm, which updates A in line 3 of Algorithm
3 Specifically,
ngو for i > 2. Here D = arg min livl D || - yl denotes the projection operator and 17 is the stepsize tuned by OSD. Regarding notations in Algorithm 3, there are two round indices t and k and we use the subscript and superseript k namely æ/t denote variable in outer loop it and inner loop t.
3 following the explicit update rule: A <- O and A + IT (
The selection of O2NC as our base non-private algorithm is deliberate and influenced by the lit- erature of non-private zeroth-order algorithms in nonsmooth nonconvex optimization. Intuitively,
5

---

Published as a conference paper at ICLR 2024
Algorithm 3 Online-to-Noncoon Conversion
Input: OCO algorithm A with domain D, gradient oracle O, initial state #1
1: for k = 1.2..... K do for tort=11 1,2, ......... do
2:
3:
Receive A from A. (For example, Af +- 0 and A + Ip(4 ng, 1),--),,_ 2.) Update 2;41 + æx + A and w <- at + of Ag, where of Uniform((O, 1)). Query gradient estimator 9e from O.
4:
5:
6:
Send (.) = (g. ) to A and A updates A,+1-
7:
end for
8: Compute whth < T Ei= w..
9:
Reset x k+1 TT+1 and restart A.
10:
end for
11: Output w Uniform (f T }).
in the realm of privacy, variance-reduction algorithm is more appealing due its inherently low sensitivity. However, straightforward application of variance-reduced SGD paired with zeroth- order estimators only achieves a sub-optimal dimension dependence of O (d2 as shown in (Chen al. 2023). A recent advancement by Kornowski & Shamir (2023) has improved the rate to O(do-t Central to their achievement is the observation that finding a (25, e)-stationary point of nonsmooth objective
equivalent finding a (6, --saatioonayy point of uniform smoothing Fs- Previous zeroth-order algorithms aim to find an c-stationary point of Fs via smooth optimiza- tion algorithms such as variance-reduced SGD, resulting in additional smoothness cost of order O(vd). In contrast, the algorithm proposed by Kornowski & Shamir (0233) leverages O2NC to find a (6, -ttttioooyy point, achieving a linear dimension dependence.
foundational non- private algorithm. Specifically, we adapt Algorithm for privacy by substituting the gradient oracle O in line 5 with more carefully designed private oracle. A main challenge in this design is to minimize sensitivity, which is required to ensure privacy. In the algorithm proposed by Kornowski & Shamir (2023),
Informed by the insights of (Kornowski & Shamir 2023). adopt O2NC
(203), the gradient oracle is simply the zeroth-order gradient estimator, gf 23 ([w) du, 2x f( : +du, 2x() )), whose sensitivity is (dL). A straightforward method to ensure privacy for this algorithm is by directly adding Gaussian noise with variance O p²). While this might seem intuitive, it leads to significantly worse data complexity. Specifically, the resulting rate 100822p11----0
which worse by factor of c when compared our proposed algorithm and importantly does not admit any value of for which we obtain the non-private convergence rate. For interested readers, we include the detailed analysis of this naive approach Appendix E
In contrast, we designed a more refined private gradient oracle in Algorithm According to Lemma and the sensitivity of g is (dT B1), while that of di is OdL]llur w Il/ B25). Setting B1 = T. B2 = and using Remark 4.1 with D = 5/T, both g and dž have sensitivity O(dL/T), apply the tree mechanism, useful technique to release sums of private
With these settings, algorithms, ensuring that the variance-reducee gradient g² achieves (a, ap² 22)-RDP Specifically, the tree mechanism adds noise of order Ô L² 22/p²1²) to each g.¹ Compared to the aforementioned naive approach, our refined approach reduces noise by a factor of T22 thus resulting in the desired data complexity.
Remark 4.1. Note that w = क - A w + +1- At + 44411141 Therefore, if the OCO algorithm has domain bounded by D (i.e., | s D for all t, k), then | w 2D. In general, for all t, [2], 1/w wt < 2|t D.
4.2 PRIVACY GUARANTEE
To ensure the privacy of the Mecine-to-Nonconvee conversion, nism, as defined in Algorithm 5 to privately aggregate the sum of gf and d'. The privacy guarantee of the tree mechanism is presented in Theorem 4.3 and the proof is presented in Append C.1 C.] Intu-
variant of the tree mecha-
itively, the tree mechanism says if each of the algorithms My...., M,, requires o² noise for privacy, then the sum Ei= Mi only needs ((I(n))o2) noise for the same level of privacy. With Theorem

---

Published as a conference paper at ICLR 2024
Algorithm 4 Private variance-reduced gradient oracle O
Input: dataset Z, constants B1, 13 Initialize: Partition Z into K'T subsets: Z of size B1 for k E [K] and Zł of size B2 for
t [2, K].A [K]. The total data size is | M ( B2 1)).
1: Upon receiving round index k, and parameters w
2: if 11=10 1then
3:
Query of 5 24).
4: else
5:
Query d y (wf w ZF) and compute of + --g;11 dē.
6: end if
7: Return g.t g (R)E(().
Algorithm 5 Tree Mechanism
Input: Index E [T'], global variables o
1: If = set NOISE + O.
2: Sample & ~ (0, lf and store & in NOISE.
3: Return Σ (-)))NoDc()) &x.
4: function NODE(T)
5: Initialize: Set k +- and S ()-
6: for O,..., [log((t) while < t do
7: Set k' + + + (0] W' < I, store S + S ((k + +1, k), and update k <- k.
8: end for
9: Return S.
end function
4.3
determine the minimal noise required ensure privacy for Algorithm in Corollary 4.4
and we evaluate the total noise added by the tree mechanism in Corollary 4.5
Remark 4.2. To better understand the NODE function in Algorithm 5 consider binary tree of
depth (t)] NODE(T) returns the largest node n, each layer i, if exists, such that n, < n, S starting from the top level. As an example, NODE(7) {(1,4), (5, 6), (7, and NODE(8) {(1, 8)). In particular, note that [NODE(!)] S [log, S ln()).
Next, we present the main privacy theorem for the tree mechanism as presented in Algorithm 5
Theorem 4.3. Let X be state space and 2(1)
2(n) be dataset spaces, and denote (1:.)
2(), Let M : Xi-1 x 2() - X be a sequence of algorithms for [n]], and let A: (1mn) X th be the algorithm that, given dataset Zun 2Z1mm), sequentially computes
2(1)
a; Σ₁= (1) (11-)-1,77) 7,) TREEF(() for E [ni] and then outputs Fin-- Suppose for all [m]
and neighboring Zi:, Zi_n_ E Z(I.n), (
10 Z S for all auxiliary
inputs :1:-1 X'-1 Then for all 1, A (a, ( where
p 22ln
max
bElx Tb
In our case, X' is the collection of weights for fax z), g(1) is the collection of all possible batches Z of size Bi defined in Algorithm and Z for t > the collection of all possible batches Z/ of size B2. Moreover, (1 corresponds to GRAD that computes O and () corresponds to DIFF that computes dy. Upon substituting these specific definition into Theorem 4.3 we have the following privacy guarantees.
Corollary 4.4. Suppose [xx,)) is differentiable and L-Lipschitz in a and the domain of A is bounded by D 6/T. Let B1, B2 satisfies B₁ 2 TB2/2. Then for any a > 1,p > 0. Algo- rithm is (a, ap² RDP if we set the noises Ti.T in the tree mechanism as
22 T4dL
==
BrTp
7

---

Published as a conference paper at ICLR 2024
Corollary 4.5. Following the assumptions and definitions in Corollary 4.4
for all [T].
8 (l1(T))
E [|] 22nn(t)do² <
BaTp
4.3 CONVERGENCE ANALYSIS
To start the convergence analysis, we revisit the convergence result of the non-private O2NC algo- rithm presented in Lemma 4.6maa4.wwosee proof included in Appendix [ completeness. Building upon the observation in Corollary 2.3 our objective shifts to finding (ô, (.f,e))-x ) point of the
uniform smoothing Fs. as opposed to directly optimizing F. This approach leads to the formulation of Corollary 4.7 Missing proofs in this section are deferred to Appendix [
Lemma 4.6. For any function F Rd - R that is differentiable and F(x1) inf F(x)) F* the domain of the OCO algorithm A is bounded by D = 8/T, then
F
K
ERegr (w
K T
(VF((w)) g AJ 4
DKT
DKT
DKT
where n IEES
(F(
FF(WF)I
Corollary 4.7. Suppose F I2d + R differentiable, L-Lipschitz, and F(x11 inf F(x) F", and suppose the domain of A is bounded by D = T/T. Then
F + 2L8
K
ERegr (ū²)
K
T
E
g. A ú
E| F(F)(() S DKT
DKT
DKT
where at - (w) IET (Fs(())
Next, we introduce a key result our convergence analysis. At its core, Lemma 4.8 suggests that the variance of the non-private gradient oracle, defined as g in Algorithm (dLL//T). This result leads to the non non-private term of (d6 e0)) in the data complexity, match- ing the optimal rate in non-private contexts. Together with Corollary 4.5 this lemma implies the main result as stated in Theorem 4.9
approximately
Lemma 4.8. Suppose fax 2) is differentiable and I.-Lipschitz in x and the domain of A bounded by D 8/T, then the variance of the gradient oracle O (Algorithm 4h is bounded by
16dT. 64dT2
E| Vl(FF((w)) 1
B1
B₂T
Theorem 4.9. Suppose f(x, z) is differentiable and L-Lipschitz x, F(x1) inf F(x) s F*. Then for any 5, 0 and 1,p there exists
M M=ò O=
1FFF 8c3
F
)
13 23
3/2
FLL
L
pōc²
pe2
such that upon running Algorithm 3 with projected OSD as the OCO algorithm, using Algorithm
the private oracle, and setting at defined in Corollary 4.4 and B T + B2 D.
T T min{( \/LLMM 22/3
( F ( (FF++00)p 1/2),,
M the algorithm outputs an (a, ap² ap2/2/ (2)- RDP 2T.
(ő, -tsttioinn point with M data points.
Proof. Since B = T+1, 1, Bg = 1 satisfy B, 2 TB//2, Corollary 4.4 implies the privacy guarantee. For the convergence analysis, Corollary 4.7 states that
F* + 2T. DKT
K ERegr (ū+) DKT
K
T
B
E
g. , át)
VF
26 S
DKT
8

---

Published as a conference paper at ICLR 2024
Recall that given sequence of stochastic vectors Dis..ry Ur, the regret of projected OSD is bounded by E[Regr(u)] - DV Σ e11
Orabona 2019). In our case, v, -. We can bound
Ell9. 12 S g v
(l )|
3B V
3 (TEE((()
80dL2
8 8lI(T)dd/22)
2
< 3.
+ 3L
+
B²T
B2Tp
where the first term is bounded by Lemma 4.8
with B1 2 TB2/2, the second by Lipschitzness of
F's (Lemma 2.2 (i)), and the third by Corollary 4.5 Consequently, we bound the regret by
vd
d/22
E EiReg (ū²) S DLVT
(1)
VBT
B2Tp
Next, note that || i= S 2D. Following the same previous bounds, we have
E B(VPss g A a*t)
2DE[I
V Fs (we
g. [[TREE((]]]
VdL
d L
D
VBT
B2Tp
Upon substituting equation 1 annd equation 2 into Corollary 4.7
we have
Fr Lg
Vd
d3/2
VdL
d3/2
V F(w)
1|2 X
+
DKT
VT
B2T
B2Tp/
/B2
B2Tp
Upon setting B₁ = T 1, B2 D,
4. the data size is M K(BI B2(T 1)) 2KT and
(F* + L8YT
VaL 1
6M
VT
Tp
Upon setting T min VaLaM
2//3
L8M [F [F*+L81p)
/1/3, we achieve the desired bound
F*+18
F'
1/3
dL3
1/3
F FTdii2
1/2
d3/2
1/2
+
6M
M
pdM
PM
Equivalently, the right hand side is bounded by if M max
F'
dL
F-1012
23/2 pc
de
23:
poèt
CONCLUSION
This paper presents novel zeroth-order algorithm for private nonsmooth nonconvex optimization. We prove that, given dataset of size M, our algorithm finds (6. st-stiooonyyy point while achiev-
ing (ox, cxp2 R2D privacy guarantee so long as M = (d( F' 1. + 6 p
De
Notably, this is the first algorithm for the private nonsmooth nonconvex optimization problem.
For future research, there are several intriguing directions. First, we are interested in exploring meth- ods that could eliminate the need sample uniform vectors per data point, limitation we delve into in Section 3 Additionally, the design of efficient first-order private algorithms for nonsmooth nonconvex optimization stands out as an area of potential exploration. Finally, the optimality of the current rate is still uncertain, and finding the lower bounds remains an open problem.
REFERENCES
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:191..02830 2019.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridha- ran. Second-order information non-convex stochastic optimization: Power and limitations. In Conference Learning Theory, pp. 242-299, 2020.

---

Published as a conference paper at ICLR 2024
Raman Arora, Raef Bassily, Tomás González, Cristóbal Guzmán, Michael Menart, and Enayat Ul- lah. Faster rates of convergence to stationary points in differentially private optimization. 2023.
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, pp.
IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 11282-11299 2019.
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic optimization: New results in convex and non-convex settings. Advances in Neural Information Processing Systems, 34, 202la.
Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochas- tic convex optimization. In Conference on Learning Theory, pp. 474 499. PMLR, 2021b.
Dimitri P Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Jour- nal of Optimization Theory and Applications, 12(2):218-23) 2-11, 1973.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, pp. 1-50, 2019.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization, 2023.
Ashok Cutkosky and Francesco Orabona. Momentum--ased variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pp. 15210-15219, 2019.
Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through Learning (ICML), 2023.
conversion. International Conference on Machine
John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):7788-28) 2212278888806,, 2015. doi: 10. 10.1109/TT.200552409222
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under con- tinual observation. In Proceedings of the forty-second ACM symposium Theory of computing, pp. 715-724, 2010.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path-integrated differential estimator. In Advances Neural Information Processing Systems, pp. 689, 2018.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439 449, 2020.
10

---

Published as a conference paper at ICLR 2024
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth anmual ACM-SIAM symposium Discrete algorithms, pp. 385-394, 2005.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal Optimization, 23(4):2341-2366 2013.
A. A. Goldstein. Optimization of lipschitz continuous functions. Math. Progrum., 13(1):14-22, dec 1977. ISSN 0025-5610.
doi: 10. 10.1007/BFO11584520. URL https::///eett http:////oo....//o.oo/o/// 1007/
BF BFC1584320
Elad Hazan.
Introduction online convex optimization. arXiv preprint arXiv: 2019.
Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differen- tially private learning. In International Conference on Machine Learning, pp. 476-484. PMLR, 2014.
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Conference on Learning Theory, pp. 24-1. JMLR Workshop and Conference Proceedings, 2012.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pp. 25-1.JMI.R Workshop and Conference Proceedings, 2012.
Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Jour- nal of Machine Learning Research, 23(314):1-44, 2022.
Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-deeendennee for zero-order nonsmooth nonconvex stochastic optimization, 2023.
Tianyi Lin, Zeyu Zheng, and Michael I. Jordan. Gradient-free methods for deterministic and stochas- tic nonsmooth nonconvex optimization, 2022.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Bisaa,B and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Ila Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Sym- posium (CSF), pp. 263-275. IEEE, 2017.
Barry L. Nelson. Optimization via simulation over discrete decision variables. In Risk and Opti- mization in an Uncertain World, pp. 193-207. INFORMS, September 2010. doi: 10.1287/educ.
1100.0069. URLhttps: /tt.///c...co http://tt........//// 1287 /eee////ucc.../ 1100. 0069
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv: 2019.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry, arXiv preprint arXiv: 2014.
Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computation of approximate stationarity concepts lipschitz functions. International Confer- ence on Machine Learning, pp.
PMLR, 2022.
Hoang Tran and Ashok Cutkosky. Momentum aggregation for private non-convex ERM. In Al- ice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neu- ral Information Processing Systems, 2022. URL httph:t////....... http:::////ppeeeviiie net forum?id
156v-UN7B11

---

Published as a conference paper at ICLR 2024
Martin J. Wainwright. High--Dimnsiooal Statisties: A Non--symptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/ 9781 10862771..
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: faster and more general. In Proceedings of the 31st International Conference on Neural Informa- tion Processing Systems, pp. 2719-2728 2017.
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference Machine Learning, pp. 6526-6535.
PMLR, 2019a.
Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient stochastic nonconvex optimization. arXiv preprint /900v:1910.136555 2019b.
Farzad Yousefian, Angelia Nedić, and Uday V. Shanbhag, On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56-67, 2012. ISSN 0005-1098.
Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Ali Jadbabaie, and Suvrit Sra. Complexity of finding stationary points of nonsmooth nonconvex functions. 2020.
Qinzi Zhang, Hoang Tran, and Ashok Cutkosky. Differentially private ouline-to-batee for smooth losses. In Advances in Neural Information Processing Systems, volume 35, 2022.
Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee. Pri- vate stochastic non-convex optimization: Adaptive algorithms and tighter generalization bounds. arXiv preprint arXiv:2006. 13501, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928-936, 2003.
12

---

Published as a conference paper at ICLR 2024
A PROOFS IN SECTION 2
A.1 PROOF OF LEMMA 2.2
Lemma 2.2. Suppose R I. is L-Lipschitz. Then (i) hy is L-Lipschitz: (ti) [hs(())) h(x)) -
Lò; (iii) hy is differentiable and v -moooth; (iv)
Vhs(#) 1u har ōu)u) Eu--tt (h(x + ōu) h((w 6u))u);
Proof. For simplicity, we drop the subscript 8 of hss By Jensen's inequality and Lipschitzness, [f(xx) - h())ll - E. 5v) - h(y + أل)هl - L|| - yll:
[1((x)) h()) - E. [h( bv) h(x))l L || - L6.
(ii)
Next, since h is Lipschitz, h is almost every differentiable by Rademacher's theorem and the uni- form smoothing h is also almost everywhere differentiable by (Bertsekas) 1973. Proposition 2.4).
Moreover, it holds that Vh((z) E., Vh(a 8r)]. Denote A as the symmetric difference, i.e.,
AAB (A \ B) U (B) \ A), and let B(x, 5)A 5). Then
Vh(xx) - (1)il = [u Vh(x + 6v) Vh(y + +wvlll
S B(ee.)) vol( (x, 5))
Vh(v)
Vh(v) dv B(y vol(B (3. 6))
du
Vh(v) du
[Vh(v)]] du vol(S)L
VdL
x 311
voI
JS vol
vol
where the second last inequality follows from ||Vh(v)]| - L. and the last follows from Lemma Finally, by definition of expectation,
A.1
Jg V f + 8v) de vol(B)
Euwih Vh(w + 8v)]
Sg f(x + du tu)u du vol(S)
E Erwin (
By Stokes' theorem,
V= 8v) du 1 [(00 uu
We then establish the first equality in (iv) by vol(B)/ vol(S) = 8/d. Next, let p be Rademacher random variable and w' u/p. Observe that w' Us well. Therefore,
Br [ + 5u)u] Ep, [gh(2 a ppu'))'
F. (gh(x a su)u gh(x (u)(-u))
This proves the second equality in (iv).
vol(S) Lemma A.I. Let x. y E Rd and S = B(x 8)AB(y, 8), then vol
S Ld yll-
Proof. Let D || - yll. Va(r) be the volume of an d-ball in Rd, and Ud(h, be the volume of the cap of an d-ball of height h. Observe that for D < 25,
vol(S) 2 Ua(5 D 2, Ua(ō 2.
vo
Va(ō)
Next, we compute the value of (h)
Ua(hrr) = 1" Va-1 (r- ( dt.
13

---

Published as a conference paper at ICLR 2024
Recall that the volume of an d-ball is Va(r) F(d/2+1) r" Therefore,
x4/2
vol(5)
[[dd-1/2+1)
7dd-1)/2
6
(2ôt
t²) "
dt
vol(
T(d/2-1) 8d
x4/2
r( +1
6+
2t
2
dt
V 1 +1
8
82
T(.) +1)
1+
u²) 1
(2u
du.
(t = 8u)
VTI( d-1 +1)
1-
Note that 2u x2 for all R. so the integral is bounded by 11
20 1 du z The
proof then follows from the fact that T( + 1)/T( + S V2d (proved Lemma A.2 for completeness).
Lemma A.2. For all E E, + 1 + S 2n.
Proof. Let n!! = n(n - (n - 4) IT<=0 31 -1 and [(2) = VT, we have
(n 2k). then by definition of I'(n + 1) = ny(n)
n!!
is even
I +1)
2n/2: VEn!!!
n is odd
Consequently, we have
T + 1)
VE(R- P even
n!!
n!!
+1)
Vin!!!
odd
(-'!'
S(n-1)11*
We finish the proof by induction. For 1, assume
I!I OT!
= 1 1.
1. For
2, =2 V2 Now
(m- 1)!! 22m for all S n. Then
m!!
(n + 1)!! n!!
1 1)!! (n 2)!!
n+1 22 22(n
(n + 1)(n 1
22 1).
7
n
n
This concludes the proof by induction.
A.2 PROOF OF COROLLARY 2.3
Corollary 2.3. Suppose F. Rd + I. is L-Lipschitz. Then for any > 0, [VFs(z))ls S implies that [<))la) S.
Proof. Recall that the 5-subdiiferential of F3 is defined as Ög Fg()) = conv(UyEB(a.)) VFs(y)). In other words, for each g E 0 (xx) is of form of g ΣA where X are convex coefficients and y, B(x, 8). (Lin et al. 2022 Theorem 10) has proved that vis(y,) Fg.().) In addition, since ly: - x|| < 6, we have (g)) C O2g Fxx). Consequently, we have
vis(y:) E 0,F C F2)F((r)
and thus g E F(x) for g (z). We conclude the proof by recalling Definition 2.1 that
[v inf g E (z)), [|VF(z)]l25 inf g F2)F(x))
and the previous result that ||0 (x(e) C Ozs F()).
14

---

Published as a conference paper at ICLR 2024
B PROOFS IN SECTION
Lemma 3.1. If f(x, z) is differentiable and L-Lipschitz in a, then for any å 0, x E Rd and neighboring data batches 21:b; 21. of size b,
E[GRAD f (0 (1,, V (ax),
(unbiased)
E 21.0) V>((()) - 16d12
(variance)
||GRAD,, 2166 GRAD, (x, 2/,b)11 S 2dL
(sensitivity)
Proof. For simplicity, let 9ij 28 (u.. 2:) ff= -u.y; : 21) J so that G2,, 21
E ビ 9ij. Since is L-Lipschitz it follows that || || S dL.
First, by F(x) (x) 2)] and Lemma 2.2 (iv).
Eu,a أgوو E.l (F(x + du.s) - F(x - (u:s)) Vfs(2)).
Taking the average over i gives E[GRAD =1:6]] v (ar)).
Next, let g, = Σ Pij and observe that Elg = Fz))).. Since g; (x) are mean-zero and independent for all i, we have
E g. Ffs))).g. Vfs(=))) E.,, (E,, g. VFs(2)), [fo())))
In other words, all cross-terms are O. Therefore,
E| B (00 21.)) v (x))1
= ن - Blgg; F=x)))
< t Σニ 1 2E g. (a) 2B / x) (=)
(3)
We first evaluate the second term. By Lemma 2.2 (i), (, and F; are L-Lipschitz, which implies
that [ (ar, 2:)1 < T. and [x=)] s L. Consequently, E/ / (a. =;) - (=x)) (2L)².
Next, note that gij fa 22 22 are mean-zero and independent for all j. Therefore,
fa 2)) 1| d2 E Elg (x, 2) (d+1)²²²
E 9:
The last inequality follows from gig - fo6 x,)1 S |ل + /Vfs 21)1 s (d + 1)I. Upon substituting back into equation
we have
E GRADD, (xx, 21.0) (xx) 12 < [d+1)122 + (2L)2 < 16d1.2 b
Finally, let Kyy Te be defined in the same way as Pijs T. but using 2/. Since 21:b, 2f. are neighbor- ing. 9: - g. O for all but one Let be the index of the different data point. Then
[RRAD 210) GRAD, =1 Il = I I'll S th Σラ
llg Shyll S
2dl b
Lemma 3.2. If f(x, 2) is differentiable and Lppshii in æ,, then for any 5 > O. xc y E IRd and neighboring data batches 21:b; 21. of size b.
E[DIFF,,o y, 21:0]] V As(x)) V Fz()):
(unbiased)
E||DFF,,, (a, y. 21:6) - (v) (Fs(2))11 <
16dL2 622
1 - -
(variance)
|DIFF (x,, 21:)) - DIFF 2 2dL
yll.
(sensitivity)
Proof. Let dij ( x) f &uig 2)) u.y Then follows that D (x, y, 21.)) = 1 E 1 E==1 dij. Since is L-Lipschitz, it also holds that ||d;il
44
|
yll-
First, by F(x) Ez[ =)) and Lemma 2.2 (iv).
Eu.: (dyy] E,, (F + su.)) Fly Su.y) vFs(x) vbs(2).
15

---

Published as a conference paper at ICLR 2024
Taking the average over j gives E
VFs(()) (alla))-FF(32 Fo()))
Next, let d; = 4. E d.j. AF (25(2) Fvy(y) and 4y(2;) V. 2.) v.),
Observe that E[d.] AF F and Eid [2] = (z.) Since d: AF are independent and mean-zero for all i, we have
B| DIFF f.8 (.8 (z. y. 21:b)
V (xx)(>)) (uill1
x ト 1= Bl|d, AF
- きे t 2E d - (z))) + 2E / (2.) - AFl1?
(4)
Vol. We first evaluate the second term. By Lemma 2.2 (iii), So, Fs are 8 -ggh -smotth, which implies that || y (z:) ||1 I vOL | - yll- Consequently, E| (Z:) - AF S (2val || - yll) Next,
since di - A 5 (22)) 23 mean-zero and independent for all
d. 4
Σラ Bl|dy (+)))
(2d +2
| y/1².
db
The last inequality follows from ||d
S 4f ||r: yll and
- LeL 1 yll- Therefore,
upon substituting back into equation 4
we have
f 21:6) Fa(x)) - (b3
16dL2
I y11 bd
Finally, let y. d. be defined in the same way as dij, d, but using 2/.. Since 21.b, zi.3 are neighbor-
ing, d, d. O for all but one i. Let & be the index of the different data point. Then
DIFF y (ac, y. m1.) DIFFy(ar, y, =1,x)1 || = b d. S
2dL
| - yll.
C PROOFS IN SECTION 4.2
C. PROOF OF THEOREM 4.3
Before we prove the theorem, we first prove more general composition of RDP mechanisms. For two datasets Z, Z E Z, we denote =g Z' Z, are neighbors and they differ at the q-th entry.
Lemma C.1. For any domain Z, let R S(1) x... X S((-1) x - S( be a sequence of algorithms such that R R (x15-11.) is (a,e,)-RDP for all auxiliary inputs 01;--1 Stt) x X 86-1), Let (R10(1 1,2) be the distribution of (11 Z). Suppose each dataset Z Z has data, and for each q E [m]. let
IN(4) = (i E [n] [RO(.2) (. VZ = Z)}, OUT(a) == [[]]] (N(()))
Let An 2 + 5(1 x ... x.. S(n) be the algorithm that given a dataset Z E Z sequentially computes
2; R 10 (211-1, for e [n] and then outputs Fi:n. Then An is (a, c)DPP) where
e ES maxge mm) Eicoureg) Ei-
Proof. Suppose 2 ~g L and let P. Q be the distributions of (Z, respectively. Note that P = P1 x ..... P,, where P, is the distribution of A; (Z) given ( i.e., Pz (115--1 JRU (I:). Similarly, Q = Q1 x x Qn where Q: [1: = (R10 (2:).
For all i E IN(4), (1(1111111 = Q((-(=1a-1) for all æ1.-1 by definition of IN(q): and for all i E OUT(g), since (()) (x1.-1.)) is (a, c)) RDD, Da (P. (P((( $ G. Therefore,
/ P. [ ( | dx; =exp((a
()) (1n--))))))) S
d. e)a-
1,
E IN(g),
i OuT(g).
We then conclude the proof by recursively integrating from dai, to day
(PP-1)
II Pa (m (1
1 (2: 1- dx., ... .a S
II #EOUT(g)
(a-1)e.
16

---

Published as a conference paper at ICLR 2024
Next, introduce several tree notations. Let lo E No and consider complete binary tree with n = 2 leaves. Leaves are indexed by i E [n] (or (i, interchangeably) in an ascending order from left to right, and every other node is indexed by (i.j) where is its left-most child leaf and its right-most child leaf. Let T be the set of all nodes, and let < be a total order on such that (a,b) b) < (c,d) d) if either break tie with leftmost child. We assume (T, <) is sorted in ascending order, then it's valid to label sequence w.r.t T (e.g., we can rewrite a1 a[T] as ((i,)) for (i,j) T). We denote <(e,d)((a.)) short-hand notation of (a(e,d) (c, d) < (a,b)} Now are ready to prove the theorem.
d or b = d,
In other words, we compare rightmost child first and
Theorem 4.3. Let X' be state space and z Z(n) be dataset spaces, and denote 2 ( Z(),, Let M x ( X be a sequence of algorithums for [nl, and
let A (1mm) x be the algorithm that, given a dataset Zun zZlm)), sequentially computes
2; = Σj= Mú) 7n) + TREF(i) for E [n] and then outpuis Fi:n. Suppose for all E [n] and neighboring Zim, Zinn E g(1m)), (111-1, Z;)- ( Z,)ll S for all auxiliaryy inputs 1i4-1 E X' Thenfor all a > 1, A (a, ap² RDD where
p S V2nnn
max bEiM
Proof. For any N, define T as he tree set with 2 [1or2 ml leaves. Let 2 = ((mm) and Sta. X for all (a,b) E T. For each (a, b) E T, define R(a.b) ([l(ad)<((a)) S(c.))) 2 + S(a.b) as
Rla.b) ((.d))((.b) Zi.) Σ (2 Zi) Eb.
(5)
where x, = ((e.))ENODE()) V(e.d) for each j [i 1] and & N(O, TJ We can check that æj is well-defined: for all j I b and for all (c, E NNDD(J), we have (c, d) < (a, b) by definition of NODE and thus #1:4-1 can be computed from ((i.))<(a,b) for all i E (j.
Next, since for all neighboring Ziam Zin E 2, (x15-11 Zi) M (21 ZD S 8is R.(ab)) ((t..))( has sensitivity bounded by 8(a.b) = max 8;. Therefore, upon adding Gaussian noise ((0,of R(a.b) (Bccd))(a.))) is (a, E(a.b) ) RDDP where E(a,b) = a 20
Now we are ready to apply Lemma C.I Let Ar. : ll S(abb) be composition of R, i.e. given dataset 7 sequentially computes V(a.)) = (( ((,d)) Zim) and outputs ()
Then by Lemma C.I Ar (a,c)-RDP where
E E max
Σ
E(a,b) = max
Σ
max as vEla.bj 20
(a,b)EOUT()))
(a,b))our(g)
Observe that node (a, 6) E OUT(g) if and only if the q-th data in Zim is in 2, and E [a, b). Since there is exactly one such node in each of [logz n] + layers in the binary tree associated with T, we have (OuT(g)) [log, n 1 < 2 In n. Consequently.
ap²
e 2 Salnn
max bE[n]aiS o
Finally, we conclude the proof by claiming that algorithm A defined in the theorem can be derived from Ar after post-processing. Observe that ((a.))NNDDE())) Σj Σj so by equation
b
x;
Σ
y(a.)) =
Σ
Σ
(2 Zzi) + Eo
(o.D))))DE(s)
(a.D)ENoDC())
1=0
Σ
2T) + TREE(i).
Therefore, A is indeed post-processing of AR, which concludes the proof.
17

---

Published as a conference paper at ICLR 2024
C.2 PROOF OF COROLLARY 4.4
Corollary 4.4. Suppose [x,=) is differentiable and L-Lipschitz in a and the domain of A is bounded by D 8/T. Let B1, B2 satisfies Bi 2 TB2/2. Then for any a 1, 0, Algo-
rithm 3 is (ox, app (2)-RDP if we set the noises 1:T in the tree mechanism as
ot - 21n T4dL
B2Tp
Proof. Since the private oracle defined in Algorithm 4 uses disjoint data in different iteration k [K], Algorithm 3 is post-processing of { ..... ke( Therefore, it suffices to prove that for each k [K] the composition (gi.....gh 9f) is (a, ap? RDD
The key is to observe that (g"..... ) can be written as the adaptive composition in Theorem 4.3
Let of = (Z & GRAD),s swwf. Zf) and d = =M 2 DIFF j.s (,w w 2 This is well-defined because w is post-processing of 9i: by construction of O2NC. Therefore, g.- = = + Ei= d Ei= M 1, ) and Theorem 4.3 can be applied.
2dL By Remark 4.1 and Lemma 3.2 the By Lemma 3.1 the sensitivity of ( is bounded by
B,
sensitivity of ((()) (gf :) is bounded by 8; Bzd / w S B.T for all 2 Since we 2dl
assume B2222
2, it holds that $1 S St for all 2 Therefore, upon setting o, 2 In T for all & E [7'. Theorem 4.3 implies that (øf 94) is (a, ap2 /2)-RDP where
p' 2nn
8i S v2lnT
82 02
max DE DE(m).Sn Ob
p.
C.3 PROOF OF COROLLARY
Corollary 4.5. Following the assumptions and definitions in Corollary
4.4
for all t E [T].
8 dd
E| [|EEE(())] S 22ln())do2 =
B2Tp
Proof. Recall that TREE(t) = E( (()))NODE(() Es. Since &ı's are independent and & N(O, I)
TREE()))
Σ
Ell
Σ
do - ln(())o
(NDD)))
(s))ENODE())
The last inequality follows from Remark 4.2 that [NDD((t] S 1n(t). We then conclude the proof by substituting the value of a defined Corollary 4.4
D MISSING PROOFS IN SECTION
Lemma 4.6. For any function F ; Rdd R that is differentiable and F(xx)) - inf F(x) S F", if
the domain of the OCO algorithm A is bounded by D 8/T, then
F
ERegy (w
K ΣΣ
((FF(wt) - gt A v)
E F(w)
DKT
DKT
DKT
where t - ΣT |E FF(W))I
(F(
Proof. First, by fundamental theorem of calculus, have
F(w - F(xt)= L' (V + 1a az(i), a ax:) dl
(VF( + +1at,, At) dt Ex (VF(( A/).
18

---

Published as a conference paper at ICLR 2024
Next, upon taking the telescopic sum (and recall z/+1
2 we have
K
T
K T
= EF(xT+1) - F(x;))
[[F(x
F(xt)) = E(FF(W A,).
k=
k=1
Note that )F(Ww),, by definition of u² and Regr (
A.) (VF(w)) uh) (gt -
g A u²)) Therefore,
T
E(VF(w)) =
Σ (F(wF)
+ Regr(" + Σ (V((w))) of. u
1=1
Upon rearranging the inequality and applying F(x)+11 F(x))) - F", we have
K
Σ DE VF(WF)
S F*
ERegr
+ Σ (VF(w)) g.. A ut))
Finally, note that 1loof w² S DT 8, so
VV
I|1 S + V by definition of
|| [|s- Moreover, F = | Σ -i=1 VF (eFF(w">ll [la)] Therefore, dividing both sides of the inequality by DKT concludes the proof.
Corollary 4.7. Suppose F 12d R is differentiable, L-Lipschitz, and F(x1) inf F(x) F*, and suppose the domain of A is bounded by D = = Then
F + 2L0
K
ERegr (ū²)
T ΣΣ
FV - A a
E F
DKT
DKT
DKT
k=
Et= ( DE (eo
where a = -
Proof. By Lemma 2.2
Fs is differentiable. Next, since || FFI S L6,
is Fa(m)) inf Pz( F(x1) inf F(x) ) 2T. F* 2T.
Hence, upon applying Lemma 4.6 on the uniform smoothing Fs. have
F"
2T.
ERegr( (ū*)
K
E BVV (ow g.. A a
Fo uD | S
DKT
DKT
DKT
Finally, by Corollary 2.3 E F(w) 222 also bounded by RHS, which concludes the proof.
Lemma 4.8. Suppose f(x, 2) differentiable and L--ipsehitz in x and the domain of bounded
by D = 8/T, then the variance of the gradient oracle O (Algorithm 4 is bounded by
16dL2
64dl2
E B)( gf
B
B₂T
Proof. First, we recall a martingale concentration bound. Let ......, Un sequence of random vectors and let F, (Vv..) be the o-algebra generated by U1st If E/v, [F, = 0, then for all cross terms < j. 04 E Fz-1 and thus EE(, v₁) = EF,-, Elo, = 0. Consequently,
E Σi 11 Σi= E1
In our case, note that ( = (w + + Vf(w)) - V w i) and recall that g
gf + Dizd, d, Therefore, by the concentration inequality and Lemma 3.1 and 3.2
El(V((w))) gf V
1f
Σ
E(VF(
VF( d, 112
1=2
16dI2
16dI2
Σ
k 12 E
B
Bz82
1=2
We conclude the proof by Remark
4.1 that
|!
wx -=
2D < 2
19

---

Published as a conference paper at ICLR 2024
Algorithm 6 Naive private gradient oracle
Input: dataset Z, constant B, noise Initialize: Partition Z into KT subsets z of size B. The data size is |Z| = M = BKT. Upon receiving round index k, and parameter w.
2: Sample U1..... ug ~ Uniform(S) i.i.d.
B 3: g <- B 2i=1 (f(w + duu; 24) f(w 5u,, 2)) where 2; is the i-th data in Z
4: Return g. +- g Et where E ~N(00, o2 i..d.
E COMPARISON WITH NAIVE APPROACH
To concrete the discussion from Section 4.1 we 'Il delve into the analysis of the naive private algo- rithm built on O2NC. Specifically, this algorithm replaces the gradient oracle (as seen in line 5 of Algorithm 3 with direct zeroth-order estimator, as defined in Algorithm 6 As remark, o is an unbiased estimator and Ellg," 112 Σ ( + 1), according to (Krnowski & Shamir 2023) Remark 6. Moreover, following the same argument as the sensitivity bound in Lemma 3.1 the sensitivity of g bounded by O). Consequently, we set o = dL/ Bp, each ğ achieves (a, ap² /2)-RDP.
Although the algorithm appears more straightforward, its convergence analysis is less favorable. Following the proof idea of Theorem 4.9
we first recall the result in Corollary 4.7
F + 2L8
K
ERegr (ū*)
K T
B(FFs(wss (w)) g.. A
F 128
ΣΣ
DKT
DKT
DKT
Recall that E[Regr ((kk))r("))) S DV Σt E 11 Therefore, we can bound the regret of OSD by
E[Regr ii ) ) S DV ΣT Ellg
11
$ DV Σt= 12 +
1822
B"
$ DLVT
+ 1 Bp
1322
Next, bound the sum of inner product. It's important because A is independent of Z Therefore, using the martingale concentration bound, we have
that ((Vi)(w))) -t. A
Σ B(Vis(wt)) gt A an) E
V
vis(w?)
g -
D
Σ
EE
V
F&
(w()))
of 11 + E
1=1
S DLVT
+1+
2/2
VB
Bp
Upon substituting back into Corollary 4.7 have
Fr + L8
L
Vd
63/2
E V/ &
1+
DKT
VT
VB
Bp
Upon replacing D = 5/T and M = KBT, we have
L8)BBT
VAL
L
8M
VBT
VT
BVTp
To achieve the optimal non nri-ptivate rate O(d8 -33)), we need to set = 1. Therefore, upon setting
T = min(( ( ((YL6M 22/3, 8/2 LBdd 22/3,, we have
((p Lo)p
F + LO)dL2
1/3
((F+
L8)d8/2132 1/3
+
5M
P
20

---

Published as a conference paper at ICLR 2024
Equivalently, V 26 I e M = a (d( des + (S5 + ( = whose dom-
pôet +
inating term is 9idd + ((d5-1c- suffers an additional cost o for privacy.
In contrast, our carefully designed algorithm only requires samples, as proved in Theorem 4.9 Notably, the naive algorithm
21


Reviews:
[{"review_id": "kRI3nKE78Q", "reviewer": "Reviewer_oD4K", "summary": "This paper studies the problem of zeroth-order nonsmooth nonconvex optimization with differential privacy and provides an algorithm with sample complexity $\\tilde{O}(\\frac{d}{\\delta\\epsilon^3} + \\frac{d^{3/2}}{\\rho\\delta\\epsilon^2})$, where the optimal sample complexity for the non-private version is $\\tilde{O}(\\frac{d}{\\delta\\epsilon^3})$. The authors obtain this result by constructing a variance-reduced oracle with the tree mechanism.", "questions": "-", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is technically solid. The private setting is both important and interesting. This was done without sacrificing a good complexity; the sample complexity is optimal in some regimes $\\rho > \\sqrt{d} \\epsilon$. In general, I think this is a nice paper with a clear idea and with good explanations that show the motivation for each statement or its proof. I really like the authors explained why the naive approach would give the sub-optimal rate in the appendix.", "weaknesses": "1. The result heavily based on the previous paper on the non-private version (Cutkosky et al., 2023.) makes it seem a bit incremental. \n2. Understandably, there is no space in the current ICLR format for experimental evaluation, this is something that could be looked at in the future.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3JRSDgqDYt", "reviewer": "Reviewer_P8ng", "summary": "This work introduces a zeroth-order stochastic optimization algorithm for nonconvex and nonsmooth objectives. This algorithm finds a $(\\delta,\\epsilon)$-stationary point with $(\\alpha, \\alpha \\rho^2/2)$-Renyi differential privacy within $O(d {\\delta^{-1} \\epsilon^{-3}} + d^{3/2} \\delta^{-1} {\\rho^{-1} \\epsilon^{-2}})$ data complexity. \n\nThis algorithm uses non-private Online-to-non-convex Conversion (O2NC) framework proposed in previous work that finds a $(\\delta,\\epsilon)$-stationary point using a first-order oracle. On top of this framework, this paper builds an approximate first-order oracle with a zeroth-order oracle. Specifically, this first-order oracle samples $d$ iid estimators for each data point to achieve optimal dependence on $d$.", "questions": "1. It is claimed in Section 1.1 that \"the non-private term $O(d {\\delta^{-1} \\epsilon^{-3}})$ matches the optimal rate found in its non-private counterpart.\" Is this sample complexity proved to be the lower bound for zeroth-order optimization on non-smooth non-convex objectives?\n2. The algorithm samples $d$ iid estimators for each data point. Do you think it is essentially necessary to achieve the current dependence on $d$, or is it limited to the analysis technique?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This work investigates the important problem of nonconvex and nonsmooth optimization, which is a frequent setting in modern machine learning. It provides an efficient algorithm that finds a stationary point while attaining differential privacy. The sample complexity required matches its non-private analog. \n2. The paper is technically solid, clearly presented, and well-structured, with the key proof step contained in the main text, so that it is easy for the readers to follow the key proof ideas.", "weaknesses": "1. As discussed in the paper, the need to sample $d$ iid estimators for each data point seems to be less natural. \n2. It would be good to have some discussions on how differential privacy is attained in other similar (e.g., 1st order) optimization problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7HrhPWlzgf", "reviewer": "Reviewer_oGL7", "summary": "The paper studies differentially private zeroth-order algorithms for nonsmooth nonconvex optimization and proposes the first algorithm under this topic. The convergence analysis of the algorithm shows that the non-private term matches with the optimal rate in non-private zeroth-order nonsmooth nonconvex optimization. The private term is $d/\\delta$ times worse than the best-known rate for private first-order algorithms for smooth nonconvex optimization.", "questions": "See Weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper studies a new topic that aims to obtain private zeroth-order algorithms for nonsmooth nonconvex optimization, while most existing works for private nonconvex optimization focus on first-order algorithms for smooth objective functions. The proposed method creatively combines existing results and leads to a non-trivial convergence analysis. The presentation of the paper is well-structured and clearly introduces different components of this new algorithm.", "weaknesses": "1. The reason to study differentially private (DP) zeroth-order methods for nonsmooth nonconvex optimization is not well motivated in this paper. I agree it is important to study DP nonconvex optimization, and there is indeed a rich literature that focuses on first-order methods. The paper mentions some applications of zeroth-order methods where gradients can be hard to obtain, including reinforcement learning. However, there is no notion of the dataset in these applications, then it is not immediate to incorporate DP. The paper should find some settings where DP zeroth-order algorithms are necessary. The current introduction looks like a simple combination of different concepts.\n\n2. The computation complexity is never reported and compared with existing DP first-order methods and non-DP zeroth-order methods. I guess it will be $d$ times worse since $d$ samples are required to construct the zeroth-order estimators, which could be bad when $d$ is large. I understand the need for $d$ samples to reduce the variance of DIFF, but why is it also used for GRAD? Also, the paper uses a two-point estimator for GRAD and a one-point estimator for each gradient in DIFF. Is there any specific reason for this difference in the choice?\n\n3. Is the assumption that $f(x,z)$ is differentiable required? I think Lipschitzness is enough in most nonsmooth nonconvex optimization literature, which implies the function is almost everywhere differentiable. Moreover, the main convergence results rely on the assumption that the domain of $\\mathcal{A}$ is bounded by $\\delta/T$. Projection is thus required to make sure this assumption is satisfied. However, as $\\delta/T$ is typically very small, such projection suggests that each update of $x$ only increases the magnitude of $x$ by at most $\\delta/T$ and every iterate remains in a ball with radius $\\delta$ centered at $x_1$ after $T$ updates. What if there is no stationary point in this ball? Does the convergence result still make sense? I guess it is then required that $\\delta$ should be sufficiently large, and the $(\\delta, \\epsilon)$-stationarity would be weak.\n\n4. I find it hard to parse Remark 4.2 and Theorem 4.3. What is the definition of $n_j$, $\\mathcal{X}^i$ and $\\mathcal{S}^{(i)}$? What is the need for the first index in the tuple of NODE? It is only required to sum the second index in NODE as per line 3 of Algorithm 5. I am also confused by the statement in Remark 4.2 that says NODE stores the largest node in each layer. NODE(7) and NODE(8) both have 3 layers, but one has 3 elements while the other only has 1 element.\n\n5. Minor: The standard results in $(\\epsilon, \\delta)$-DP say something like $\\Vert \\nabla F\\Vert^2 \\leq \\sqrt{d\\log(1/\\delta)}/(n\\epsilon)$. Here, the dataset with size $n$ is given, and the best achievable rate given $n$ is studied. It might be good to also report such a rate following the standard since private data is not as many as one can collect and is assumed to be given in advance; The proposed method is a single-pass algorithm, but in machine learning practice, training tends to be in multiple epochs; In Section 2, $(\\epsilon, \\delta)$-DP is used when introducing differential privacy. It might be good to change it to avoid confusion with $(\\delta, \\epsilon)$-stationarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lvNzNb1jGd", "reviewer": "Reviewer_pExn", "summary": "The paper proposes a differentially-private zero-order algorithm for nonsmooth nonconvex optimization, and analyzes its convergence rate.", "questions": "Questions:\n- Preliminaries, Definition of $\\|\\nabla h(x)\\|_\\delta$: Regarding the \"equivalent\" definition - why is this equivalent? This is not clear to me, unless repetitions in S are allowed. Can the authors please explain this? Only a bound in one direction is immediate, as far as I can tell (which suffices for the main result of the paper). Also, the inequality in the definition is probably meant to be an equality (though only the inequality is clear to me, as I previously mentioned).\n- Lemma 2.2: I do not see why the \"immediate corollary\" is immediate. Can the authors please explain?\n\nMinor comments:\n- Section 1.1, 2nd paragraph typos: 1) \"Out gradient oracle...\"=Our; 2) Citing Dwork et al., Chan et al.: \\citep is more suitale than \\citet.\n- Section 1.1, 3rd paragraph arrives too early in my opinion. The authors discuss technicalities which are completely unclear at this point of the paper.\n- Preliminaries, Definition of $\\|\\nabla h(x)\\|_\\delta$: The infimum is of the norm over the set, currently miswritten as the set itself.\n- Differential privacy preliminaries: The authors should define Renyi divergence, and ref the two stated facts - \"then it is also...\", and \"ensures that \\Acal is ...-RDP\" (specifically cite the result, not the whole manuscript).\n- More generally, regarding the differential privacy preliminaries paragraph: it is not clearly explained how differential privacy relates to the stochastic optimization model, this is important and should be revised. e.g., \"two datasets Z,Z'\\in\\Zcal\", what is \\Zcal? It should be explained that this is the same z in the stochastic objective etc.\n- Equation in online learning (standard OSD regret bound) - add citation.\n- Lemma 2.2: Actually h does not need to be differentiable (it is automatically differentiable almost everywhere anyhow by Rademacher's theorem, which suffices for everything).\n- Section 2.1, 1st paragraph: \"... a low sensitivity gradient oracle from ...\", maybe should emphasize that this is a *stochastic* gradient oracle.\n- Section 3, paragraph second to last: \"as Lin et al. has proved...\" - As Lin et al. write before the proof of Lemma D.1, the lemma is actually taken from the paper \"An optimal algorithm for bandit and zero-order convex optimization with two-point feedback\" by Shamir [2017, Lemma 10], only restated by them. Hence this is a more appropriate reference.\n- Paragraph before Remark 4.1 includes a forward reference to Remark 4.1, maybe the remark should appear earlier? (I do not see a reason not to.)\n- Remark 4.2: I appreciate the authors adding an informal explanation about the Node function, though I found it hard to follow and I suggest revising it.\n- Proof after Corollary 4.4 - this is a proof of Theorem 4.3, right? Should clarify this.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written overall.\nThe contribution fits naturally into the line of recent developments in nonsmooth nonconvex optimization, introducing the first private algorithm for this setting (as far as I know).\nThe techniques, though well rooted in previous works, are nontrivial to compose and are executed nicely.", "weaknesses": "The main weakness in my opinion is that most proof components (as far as I can tell, all but the trick of decomposing the gradient into a sum of differences and applying a grad-difference estimator) appear in previous works, adequately cited throughout the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)