A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions
Authors: Damek Davis
Dmitriy Drusvyatskiy
Yin Tat Lee
Swati Padmanabhan
Guanghao Ye
Venue: NeurIPS 2022 Accept (2022)
Keywords: nonconvex optimization
nonsmooth optimization
nonconvex nonsmooth optimization
Goldstein subdifferential
cutting plane method.

Abstract: Zhang et al. (ICML 2020) introduced a novel modification of Goldstein's classical subgradient method, with an efficiency guarantee of $O(\varepsilon^{-4})$ for minimizing Lipschitz functions. Their work, however, makes use of an oracle that is not efficiently implementable. In this paper, we obtain the same efficiency guarantee with a standard subgradient oracle, thus making our algorithm efficiently implementable. Our resulting method works on any Lipschitz function whose value and gradient can be evaluated at points of differentiability. We additionally present a new cutting plane algorithm that achieves an efficiency of  $O(d\varepsilon^{-2}\log S)$ for the class of $S$-smooth (and possibly non-convex) functions in low dimensions. Strikingly, this $\epsilon$-dependence matches the lower bounds for the convex setting. 

A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions"
Damek Davis Cornell University dsd95@cornell.c edu
Dmitriy Drusvyatskiy University of Washington, Seattle ddrusv@uw.c edu
Yin Tat Lee
Swati Padmanabhan University Washington, Seattle pswati pwwatiduw.o edu
University of Washington, Seattle yintat@uw edu
Guanghao Ye Massachussetts Institute Technology ghye@mit edu
Abstract
Zhang, Lin, Jegelka, Sra, and Jadbabaic [i] introduce method for minimizing Lipschitz functions with an efficiency guarantee of O(sa)). Their method a novel modification of Goldstein's classical subgradient method. Their work, however, makes use of nonstandard subgradient oracle model and requires the function to be directionally differentiable. Our firs! contribution in this paper is to show that both of these assumptions can be dropped by simply adding a small random perturbation in each step of their algorithm. The resulting method works on any Lipschitz function whose value and gradient can be evaluated at points diffcrentiabilityy Our second contribution is cutting plane algorithm that achieves better efficiency in low dimensions: O(de-) for Lipschitz functions and O(de for those that are weakly convex.
Introduction
The subgradient method [2] is classical procedure for minimizing nonsmooth Lipschitz function on Rdd Starting from an initial iterate Zig the method computes
x++1 = 0: where e E 0f(x;).
(I)
Here, the positive sequence {ar is user-specified, and the set 0f is the Clarke subdifferential [3, 4],
0f(x) conv lim Vf(x,) : >r 2; dom {
dom(vV)
In classical circumstances. the subdifferential reduces to familiar objects: for example, when f is C'l -mmooth at z, the subdiffereenial 0f (z) comprises of only the gradient f.((), while for convex functions. it reduces the subdifferential in the sense of convex analysis.
For functions f that are weakly convex - a broad class of functions first introduced in English in [5] - the limit points ž of the subgradient method are known to be first-order critical, meaning
Authors ordered alphabetically.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

0 E 0f( Recall that a function f is called p-weakly convex if the quadratically perturbed function + f(=)+ + + ||1=|1 convex. In particular, convex and smooth functions are weakly convex [6]. Going beyond asymptotic guarantees, finite-time complexity estimates are known for smooth, convex, or weakly convex problems [7-14].
Modern machine learning, however, has witnessed the emergence of problems far beyond the weakly convex problem class. Indeed, tremendous empirical success has been recently powered by industry-backed solvers, such as Google's TensorFlow and Facebook's 's PyTorch, which routinely train nonsmooth nonconvex deep networks via (stochastic) subgradient methods. Despite a vast body of work on the asymptotic convergence of subgradient methods for nonsmooth nonconvex problems [15-19], no finite-timm time nonasymptotic convergence rates were known outside the weakly convex setting until recently, with Zhang, Lin, Jegelka, Sra, and Jadbabaie [1] making a big leap forward towards this goal.
In particular, restricting themselves to the class of Lipschitz and directionally differentiable functions, [1] developed an efficient algorithm motivated by Goldstein's conceptual subgradient method [20]. Moreover, this was recently complemented by [21] with lower bounds for finding pear-approximate- stationary points for nonconvex nonsmooth functions.
While significant breakthrough in both result and technique, one crucial limitation of [1] is that their complexity guarantees and algorithm use a nonstandard first-order oracle whose validity is unclear in examples. To elaborate, their algorithm requires the following oracle access: given I, u E I' solve the auxiliary convex feasibility problem:
find g E az))) subject to (g, u) - ['(x,, u).
The first issue with this oracle that no general recipe exists for representing the full subdifferential (x()) analytically, and evaluating even an arbitrary element of the subdifferential can be highly non-trivial [22, 23]. Moreover, O (z) could be a very complicated set, e.g., for deep ReLU neural network, the subdifferential is polyhedron with a potentially huge number of facets, making the complexity of (2) unclear.
Further, [1] claim that for a composition of directionally differentiable functions with a closed-forn directional derivative for each function, we can find the desired y by the chain rule. While the chain rule does compute the directional derivative f'(x, u), to the best of our knowledge, this does not translate solving (2). This is owing to the crucial fact that the chain rule (and sum rule) can easily fail for the computation of the subdifferential (although these are indeed valid for the directional derivative of a composition of directionally differentiable functions). We believe that this could potentially render the oracle of [1] computationally intractable.
Finally, we are unaware of other optimization algorithms imposing this oracle model. Therefore, face value, the convergence guarantees of [1] are not comparable to those of others.
1.1 Our results
Weakly convex optimization via a standard oracle. Our first contribution is to recover the complexity result of [1] under much weaker assumption: specifically, we replace the non sta-standard assumption in (2) with a standard first-order oracle model. We show (Section 2) that a simple, yet critical, modification of the algorithm of [1], wherein one simply adds small random perturbation in each iteration, works for any Lipschitz function assuming only an oracle that can compute gradients and function values almost every point of Rd in the sense of Lebesgue measure. In particular, such oracles arise from automatic differentiation schemes routinely used in deep learning [24, 19]. Our end result is a randomized algorithm for minimizing any L-Lipschitz function that outputs (ō, -)-stationary point (Definition 1) after using at most O evaluations. Here A is the initial function gap and y is the failure probability.
AL'
1og(1/7)) 3 gradieet and function e
We provide simple example to demonstrate this claim: Consider the function f(x, v) - f1 ff(2,, v) with fi (a. y) = [c] and fa (z. y) = -|z]. Choose the direction u = (0, 1). and let = = (0, 0). Then, f((z, u) fz u) = 0, and 0f((2) we may choose the subgradient V1 (-1, 0), and for f2, we may choose the subgradient as (-1,0) since (v1, = = (v2, u). However, U1 + 0/2 = (-2, 0), which is not subgradient of f = 0 at 2. Throughout the paper, we use Ø(-) hide poly- logarithmic factors in L, ō, A, and
0f)(z) = [] x O. Therefore, to satisfy the oracle (2), for fi.

---

In light of the above modifications, our algorithm is implementable in the many important settings like deep neural networks that [1] is not, Along the way, we also simplity their proof techniques by providing geometric viewpoint of the algorithm.
We would like to highlight the concurrent work of Tian, Zhou, and Man-Cho So [25], which obtains this part of our result with very similar technique.
Improved complexity in low dimensions. Having obtained the result of [1] within the standard first-order oracle model, we then proceed to investigate the following question.
Can we improve the efficiency of the algorithm in low dimensions?
In addition to being natural from the viewpoint of complexity theory, this question is well-grounded in applications. For instance, numerous problems in control theory involve minimization of highly irregular functions of small number of variables. We refer the reader to the survey [26, Section 6] for an extensive list of examples, including Chebyshev approximation by exponential sums, spectral and pseudospectral abscissa minimization, maximization of the "distance to instability". and fixed-orde controller design by static output feedback. We note that for many of these problems, the gradient sampling method of [26] is often used. Despite its ubiquity in applications, the gradient sampling method does not have finite-time efficiency guarantees. The algorithms we present here offer an alternative approach with complete complexity theory.
The second contribution of our paper is an affirmative answer to the highlighted question. We present a novel algorithm that uses ( (Add
e²8 (og(1/n) calls to our (weaker) oracle. Thus we are able to trade off the factor Le with d. Further, if the function is p-weakly convex, the complexity improves to δ (Ad log(p)), which matches the complexity in 8 = of gradient descent for smooth minimization. Strikingly, the dependence on the weak convexity constant p is only logarithmic.
To put this contribution in perspective, assume for now 5 = e: then, our algorithm's dependence on in the case of Lipschitz, weakly convex functions is likely optimal in low dimensions, following a conjecture by Bubeck and Mikulincer [27] on the optimality of gradient descent for smooth optimization in dimension d log( 4) (thus matching the lower bound by Carmon, Duchi, Hinder, and Sidford [28]. Aside from possible optimality, the logarithmic dependence on smoothness/weak convexity exhibited by our iteration complexity is a significant improvement over the prior result of either (11/c*) by [1] or Nemirovski and Yudin's 's rate of O(1/e") with a polynomial dependence on smoothness. In the process, we also show that the minimal- -oom element of the Goldstein- subdifferential in low dimensions can be found in time ([log(1/e)), thus settling question open since the 70s.
Techniques. The main idea underlying our improved dependence on in low dimensions is outlined next. The algorithm of [1] comprises of an outer loop with O ( iterations, each performing either a decrease in the function value or an ingenious random sampling step to update the descent direction. Our observation, central to improving the dependence, is that the violation of the descent condition can be transformed into a gradient oracle for the problem of finding a minimal norm element of the Goldstein subdifferential. This gradient oracle may then be used within a cutting plane method, which achieves better dependence at the price of dimension factor (Section 3).
Linitations. One limitation of work is that second contribution does not immediately extend to the stochastic setting. We consider this to be an interesting open problem to resolve.
Notation. Throughout, we let d denote d-dimensional Euclidean space equipped with dot product (.-)) and the Euclidean norm ||2||2 / (2, 2:). The symbol (x) denotes an open Euclidean ball of radius >> 0 around point x. Throughout, we fix function f: Ed - ER that is L-Lipschitz, and let dom (Vf) denote the set of points where f is differentiable--a full Lebesgue measure set by Rademacher's theorem. The symbol f'(x,, u) def lim r (f + ru) - f(x)) denotes the directional derivative of f at in direction u, whenever the limit exists.
3

---

2 Interpolated normalized gradient descent
In this section, we describe the results [1] and our modified subgradient method that achieves finite-time guarantees in obtaining (ô, --tatioonayy for L-Lipschitz function f IR + R. The main construction we use is the Goldstein subdifferential [20].
Definition (Goldstein subdifferential). Consider a locally Lipschite,unntiin
function f: Rdd - R, a point E R and a parameter 8 > 0. The Goldstein subdifferential of f at is the set
(x)(x) def conv (U a(()))
yEB,(*)
A point is called (6, c)-staiionary if dist(O, 0z 0zf(z)) S.
Thus, the Goldstein subdifferential of f at is the convex hull of all Clarke subgradients at points in a 8-ball around z. Famously, [20] showed that one can significantly decrease the value of f by taking step in the direction of the minimal norm element of f, Throughout the rest of the section, fix E (0, 1) and use the notation
9 def
9/ 0/llll1 for any nonzero vector g E IRd.
(3)
Theorem ([20)). Fix a point and let be minimal norm element of (x) Then as long as 9 + O, we have f (x 6g) - f(x) - 81[g||2-
Theorem immediately motivates the following conceptual descent algorithm:
1++1 3t ögt, where It E argmin ||g||2-
9E8sf(2)
In particular, Theorem guarantees that, defining A def [(xo - min f, the approximate stationarity
condition
( A 6e
min 11 S c holds after T =
iterations of (4).
Evaluating the minimal norm element of f ) is impossible in general, and therefore the descent method described (4) cannot be applied directly. Nonetheless it serves as a guiding principle for implementable algorithms. Notably, the gradient sampling algorithm [29] in each iteration forms polyhedral approximations K2 of Osf (x:) by sampling gradients in the ball B2x(x) and computes search directions E argminge K, ||g|22 These gradient sampling algorithms, however, have only
asymptotic convergence guarantees [26].
The recent paper [1] remarkably shows that for any E Rd one can find an approximate minimal norm element of 0s fx) using a number of subgradient computations that independent of the dimension. The idea of their procedure is as follows. Suppose that we have trial vector E fz)()) (not necessarily a minimal norm element) satisfying
5 (x ((x) g119112-
That is, the decrease in function value is not as large as guaranteed by Theorem for the true minimal norm subgradient. One would like to now find a vector u. E Ös fx)( that the norm of some convex combination (1 A)g + Au smaller than that of g. A short computation shows that this is sure to be the case for all small À > 0 as long (u.g) g) l 11. The task therefore reduces to:
find some (x)( satisfying (u,g) S 1lal13.
The ingenious idea of [1] is a randomized procedure for establishing exactly that in expectation. Namely, suppose for the moment that / happens to be differentiable along the segment [a, x 8g); we will revisit this assumption shortly. Then the fundamental theorem of calculus, conjunction with (5), yields
2 |zg/z f(x) -fx 5g) = 1/50 (Vi(z -7)) dr.
(6)

---

Consequently, a point y chosen uniformly at random in the segment (ac, 6g] satisfies
((V)()). - -lall2
Therefore the vector u fy) can act as the subgradient we seek. Indeed, the following lemma shows that, in expectation, the minimal norm element of [g, u| is significantly shorter than g. The proof extracted from that of [1, Theorem 8).
Lemma 2 (II). Fix vector g E Rd, and let IRd be random vector satisfying E(u, g) & Suppose moreover that the inequality ||g]|2 1|ull2 S holds for some L < co. Then the minimal-
nom vector the segment [g, u| satisfies:
119122
E| S 1991
16
Proof. Applying E(u, g) & $ 11 and |1 /ul/2 - L, we have, for any X E (0, 1),
B| < Elgg + X(1
9) = |1a11 + 2 (g. g) + X g1l2
< ll 2 42
Plugging in the value
1 SL*
(0, minimizes the right hand side and completes the proof.
L
The last technical difficulty to overcome is the requirement that f be differentiable along the line segment [g, u.. This assumption is crucially used obtain (6) and (7). To cope with this problem, [1] introduce extra assumptions on the function f to be minimized and assume nonstandard oracle access to subgradients.
We show, using Lemma 3, that no extra assumptions are needed if one slightly perturbs
Lemma 3. Let f: TRd TR. be a Lipschitz focchitzfnnttinn function, and fix a point a E Rdd. Then there exists a set 'D C TRd of full Lebesgue measure such that for every E DD the line spanned by x and intersects dom(V) (V) )
a full Lebesgue measure set TR., Then, for every y E DD and all T R. we have
f(+ -o)=x)) x))= ((x)= = [ (Vi(x +
sly +sy
x)), x) ds.
Proof. Without loss of generality, we may assume x 0 and f(x) = 0. Rademacher's theorem guarantees that dom V f) has full Lebesgue measure in R Fubini's theorem then directly implies that there exists a set Q C Sd-1 of full Lebesgue measure within the sphere gd-1 such that for every y Q. the intersection R+ {8} n f") is Lebesgue null in R. It follows immediately that the set D {ry 7 > O. y E Q} has full Lebesgue measure in Rd Fix now point y E D and any T E R.. Since f is Lipschitz, is absolutely continuous on any line segment and therefore
[ir + + x)) f(x) S'¹ l' s(y x), x)) ds [ (Vi(x s(y x)), y x) ds.
The proof is complete.
We now have all the ingredients present modification of the algorithm from [1], which, under a standard first-order oracle model, either significantly decreases the objective value or finds an approximate minimal norm element of 0sʃ.
The following theorem establishes the efficiency of Algorithm 1, and its proof similar to that of [1, Lemma 13]. For completeness, we include the full proof in Appendix A.
Theorem 4. Let } be generated by MinNorm(ze (z, 6, e). Fix an index k 2 0, and define the stopping
def inf [k: fa 5ğx) < f(x) 8119x112/4 or 119 S E}. Then, we have
time
16I.2
E [1l9* 1|1 <
16 A'
An immediate consequence of Theorem 4 is that MinNorm(2s 6, terminates with high- bighhprobbbility.
5

---

Algorithm MinNorm zz 6,6)
Input. 2, 0, and c O.
2: Let k = 0, ((())) where Co ~ Bs(x).
3: while I|gx l2 > and 1 1119/122 2 2 f(x) - f (x - 5īt.) do
4: Choose any satisfying 0 < <<< 11 v1 (1
1l 12 1287.
5: Sample S& uniformly from (ok).
6: Choose yk uniformly at random from the segment [x, 6Ca).
7:
9h+11 argminge(ge. (xve) ||
8:
== 1.
9:
end while
10:
Return gk-
Corollary MinNorm(z, 8, terminates in at most 61r 1og((1/))
itera-
tions with probability at least ?, where we define the stopping time inf (k: f(x - dgx) < -
def
- 81
ll24 1l////1/4
11 S {).
Combining Algorithm/ with (4) yields Algorithm 2, with convergence guarantees summarized in Theorem 6, whose proof is identical to that of [1, Theorem 8].
Algorithm Interpolated Normalized Gradient Descent (INGD( T))
Initial To. counter T for t 0,..., , do g MinNorm(xr))
Computational complexity Ō(L²/e²)
Set 3x+1 Tt 6g
We define ÿ in (3)
end for Return TT
Theorem Fix an initial point 2o E Rdd and define A = f(xo) - inf, f(x). Set the num- ber of iterations T
4A
Se Then, with probability 7 the point ør = INGD(#o. T) satisfies
d0st(0, (xT)) S in total of most
4A
2
4A 756
2 log
function-value and gradient evaluations.
5c
2
In summary, the complexity of finding a point satisfying dist(0,0sf(z)) - is at most dET log <A with probability 7. Using the identity 0f(x) lim sups-so (zf(x), this result also provides strategy for finding Clarke stationary point, albeit with complexity guar- antee. is thus natural to ask whether one may efficiently find some point æ for which there exists y (x(x) satisfying d0st(0, (v)) < This exactly the guarantee
O
subgradient methods on weakly convex functions in [6]. [30] shows that for general Lipschitz functions, the number of subgradient computations required achieve this goal by any algorithm scales with the dimension of the ambient space. Finally, we mention that the perturbation technique similarly applies to the stochastic algorithm of [1, Algorithm 2), yielding method that matches their complexity estimate.
3 Faster INGD in low dimensions
In this section, we describe our modification of Algorithm ("INGD") for obtaining improved runtimes in the low-dimensional setting. Our modified algorithm hinges computations similar to (5), (6), and (7) except for the constants involved, and hence we explicitly state this setup. Given a vector g E 0g (x)),, say it satisfies the descent condition x if
dc
f(x 8g) - f())
(8)
3

---

Recall that Lemma 3 shows that for almost all 9. we have
f(x fxx 8g)
(V (V)))=11)).) dt 5- - ()
Hence, when g does not satisfy the descent condition (8), we can output a random vector Os (a) such that
E(u, g) S
- -1lall2
(9)
Then, an arbitrary vector 9 either satisfies (8) or can be used to output random vector u satisfying (9). As described in Corollary 5, Algorithm achieves this goal in Ó /c2 iterations.
In this section, we improve upon this oracle complexity by applying cutting plane methods (which we review shortly) to design Algorithm 3, which finds a better descent direction in (Ld//e) oracle calls for L-Lipschitz functions and Old L/fe) log(ôp/e)) oracle calls for p-weakly convex functions.
Brief overview of cutting-plane methods. We first provide a brief relevant overview of cutting plane methods here and refer the reader to standard textbooks in optimization for more in-depth exposition. Given a convex function if with its set S of minimizers,
putting--pann method (CPM) minimizes by maintaining a convex search set (k) 2 S the kth iteration and itcratively shrinking g()) guided by the subgradients of f that act as "separation oracles" for the set S. Specifically, this is achieved by noting that for any 2((h) chosen from g(4), if the gradient oracle indicates V (x()(() * O.
(i.e.ze (x( & S), then the convexity of f guarantees S C H((), {u (V)(z(())) -x(()) S 0}. and hence& S S H(()) E(k), The algorithm continues by choosing g(k+1) g(k) n ((),,, and different choices of (*) and g(k) yield different rates of shrinkage of (1) until point in S is found.
In light of this description, the minimization of a convex function over a constrained convex set via method requires, at each iteration, merely a subgradient of the function. Our novel
this cutting-plan insight is that a lack of function decrease implies we have roughly such a subgradient, which we may then use in a cutting- plane method for computing the minimum norm element of the subdifferential faster in low dimensions (with improved complexity for weakly convex functions).
Setting the stage for our algorithm. In Appendix B, we demonstrate how to remove the expectation in (9) and turn the inequality into high probability statement. For now, assume the existence of an oracle O as in Definition 2.
Definition 2 (Inner Product Oracle). Given vector g E 0sf(x) that does not satisfy the descent condition (8), the inner product oracle (gg) outputs vector u E fxf(x) such that
(u.9) S 2 1|lll2.
We defer the proof of the lemma below to Appendix B.
Lemma 7. Fix Rd and unit vector Rd such that f is differentiable almost everywhere the line segment [z. v). where y def x 8g. Suppose that 2 E Rd sampled uniformly from {z, v) satisfies gradient evaluations of 7 the estimate (Vf(2). () S holds. Moreover, if f is p-weakly convex, we can find E Rd such that (V S using only O(log(ôp/e)) function evaluations of f.
E. (V < 3. Then we can find v E Rdd using at most O
f, such that with probability at least
Our key insight is that this oracle is almost identical to the gradient oracle of the minimal norm element problem
min ||9||2-
Therefore, we can use it in the cutting plane method to find an approximate minimal norm element of Osf. When there is element of 0&f with norm less than c, our algorithm will instead find a vector that satisfies the descent condition. The main result of this section is the following theorem.
Theorem 8. Let d R be L--Lipschitz function. Fix an initial point To E RR,, and let
def f(x)) infz f(z). Then, there exists an algorithum that outputs a point E IRd satisfying dist((0, 0sf(()) I and, with probability at least ",, uses most
ALd
o
llg(LL/)) log(L/7))
function value/gradient evaluations.
8c2
7

---

f f is p-weakly convex, the analogous statement holds with probability one and with the improved efficiency estimate ( de log(L/e) lo)( of function value/gradient evaluations.
3.1 Finding a minimal norm element
In this section, show, via Algorithm 3, how to find approximate minimal norm element of fz)( Instead of directly working with the minimal norm problem, we note that, by Cauchy- Schwarz inequality and the Minimax Theorem, for any closed convex set Q, we have
min g 12 min max (g. b) geQ
max ||
min(g. u) _eE
max (Q))), 11l
(10)
gEQ
where (Q(v) def mingE (g, v)., and Lemma 9 formally connects the problem of finding the minimal norm element with that of maximizing &q- The key observation in this section (Lemma 10) is that the inner product oracle O is separation oracle for the (dual) problem max//|las1 (o with
Q = O and hence can be used in cutting plane methods.
Lemma 9. Ler Q C Rd be closed convex set that does not contain the origin. Let 96 be minimizer of mi ||9||2.
Then, the vector vi 9
/19g/) l12 satisfies
(o 9) 2 ll12l12
for all E Q.
and vs = arg maxioollss (Q()).
Proof. We omit the subscript to simplify notation. Since, by definition, g" minimizes l|gl|2 over all E Q we have
(g'g))
2 l1g 112 for all g e Q,
and the inequality tight for g = g" Using this fact and c0(*)) = minge (g: q" gives
o(v") |1g
min |اوو2 min max (g. v) gEQ
max min (g. v) max d(v),
gEQ e:llella51
| gEQ v:||e|la51
where we used Sion's minimax theorem in the second to last step. This completes the proof.
Using this lemma, we can show that O is a separation oracle.
Lemma 10. Consider vector g E 0fs((z) (1) that does not satisfy the descent condition (8), and let
the output of querying the oracle at g be u O(g). Suppose that dist((, (ast(0,,s(()) [x)()))) 2 5. Let g" be the minimal-none norm element of 3 Then the normalized vector def inclusion:
9" / /lg"" l|2 satisfies the
v² E (w Rd: (u. - 20--w) w) Z0).
Proof. Set - (z). By using (u, < & (the guarantee of per Definition 2) and (u, v*) lg (from Lemma 9), we have (u, v²) (u, g) (u, 0*) < _ ||g || S 0.
(u,"*)
Thus Lemma 10 states that if x not (8. ; halfspace He that separates Ò from v". Since 0 is a separation oracle, we can combine it with any cutting plane method to find o*. For concreteness, we use the center of gravity method and display our algorithm in Algorithm 3. We note that 2g is an intersection of a ball and some half spaces, hence we can compute its center of gravity in polynomial time by taking an average of the empirical samples from this convex set. While we use simple cutting outting-plane plane method, any algorithm in this class may be used; our focus merely on minimizing the oracle complexity. Further note that in algorithm, use point Ça close to the true center of gravity of lg. and therefore, we invoke result about the perturbed center of gravity method.
( sttttionary point of f. then the oracle O produces
Theorem 11 (Therrem 3 of [31]; see also [32]). Let K be a convex set with center of gravity i and covariance matrix A. For any halfspace H that contains some point with || - ullA-1 S t, we have
vol(K n H) < (1 1/e + t)vol(K).
8

---

Algorithm 3 MinNormCG(z1)
Initialize center point I.
2: Set h = 0, the search region S4 = B2()),, the set of gradients Qo = (Vf(()) and satisfying
< <</(3d)L)
3: while mingeQ. ligll2 > do
4: Let ug be center gravity of 2g.-
5: if' ug satisfies the descent condition (8) at z then Return Uj.
6:
7:
end if
8:
Sample ÇL uniformly from B, (v).
9:
uk (((k)
10:
2++1 = Q4 n fw (ux, Sk w) - 0).
QK+1 cQnv(Qu U {ux})
12:
k k= ++++
13:
end while
14:
Return arg min 1
Theorem 12 (Theorem 4.1 of [33]). Let be a convex set in Rd with center of gravity μ and covariance matrix A. Then,
K c 0: ff - S S a(d vd(d+2)
We now have all the tools to show correctness and iteration complexity of Algorithm 3.
Theorem 13. Let f Rd > TR be an L--Lipschitz function. Then Algorithm 3 returns a vector E (z) that either satisfies the descent condition (8) or satisfies ||la|2 S e in
[8dlog(8L/c)] calls to O.
Proof. By the description Algorithm 3, either returns vector satisfying the descent condition or returns E 3s)(x) with ||g||2 I We now obtain the algorithm's claimed iteration complexity.
Consider iteration i such that 9u does contain ball of radius iz Let Aş be the covariance matrix of convex set Qg. By Theorem 12, we have
2
A
I.
8dL
Applying this result the observation that in Algorithm Cx is sampled uniformly from (,(k)) gives
SdL
| - Calla, S
(11)
Recall from Algorithm and the preceding notation that Qr has center of gravity en and covariance
matrix Ag- Further, the halfspace {w (ux, &A w) < 0} in Algorithm 3 contains the point & satisfying (11). Given these statements, since Algorithm sets 2++1 = 22 n (w (wx. Sx - w)
may invoke Theorem 11 to obtain
vol(S2+) < (1 - 1/e + 10 < (1 1/10)* 10
(12)
We claim that Algorithm 3 takes at most of contradiction, suppose that this statement is false. Then, applying (12) with A = T + gives
steps where T d dooo (cL())). For the sake
vol(S S -S] (o)(
(13)
On the other hand, Algorithm 3 generates points u, (())) in the i-th call Ø and the set Q: conv {ui, U2 4 Since we assume that the algorithm takes more than T + 1 steps, we have mingeQr4: llalla e. Using this and u; Qr+1. Lemma 10 lets conclude that "2r2, E { E Rd (u,, Gi w) 50) for i E [T+ +1. Since Ωr intersection of the unit ball and these halfspaces, we have
v 2T++1

---

Per (13), 9r++1 does not contain ball of radius and therefore we may conclude that 12
there exists point 7 E B 27. ("Qr+1) such that 7 ø 4r+1-
Since ū (0), the fact V & Ur++ must be true due to one of the halfspaces generated in Algorithm 3. In other words, there must exist some E [ + 1] with
(u: 4 1) 0.
By the guarantee of Ø, we have (44, (i) 2. and hence
(u, 8) (us, 0t) (u, 2s - 8) <
(14)
By applying ū E B. (v2r ). us E (xf( L-Lipschitzness of f, and Lemma we have
(us, 8) 2 (uis uer 2L |uile (ui, "2r.1) 2 19 2
(15)
Combining (14) and (15) yields that mingeQr41 l|91|2 l ,|22 c. This contradicts the assumption that the algorithm takes more than T + steps and concludes the proof.
Now, we are ready to prove the main theorem.
Proof of Theorem 8. We note that the outer loop in Algorithm runs at most O A times because we decrease the objective by S((6c) every step. Combining this with Theorem 13 and Lemma 7, we have that with probability - 7/, the oracle complexity for L-Lipschitz function is
8e
4A Ec
36L
44 7ōc
ALd
[8dlog(8T./e))]
2lo
O
log([//e) 1og(1/7)
8c2
and for T-LLipschtz and p-weakly convex function is 0 Ad (o/(T//)) log(5p/<)).
Acknowledgements
Research of D. Davis was supported by an Alfred P. Sloan research fellowship and NSF DMS award 2047637. Research of D. Drusvyatskiy was supported by NSF 1MS-1651851 and CCF- 2023166 awards. Research of YL. was supported by NSF awards CCF-1749609,
DMS-2023166 CCF-2105772, Microsoft Research Faculty Fellowship. Sloan Research Fellowship. and Packard Fellowship. Research of GY was supported by an MIT Presidential Fellowship. Part of this work was done while GY was a student at the University of Washington.
10

---

References
[1] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 11173-11182, Virtual, 13-18 Jul 2020.
[2] Naum Z. Shor, Krzysztof C Kiwiel, and Andrzej Ruszcayríski. Minimization methods for non-differentiable functions, 1985.
[3] Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
[4] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009.
[5] E. A. Nurminskii.
The quasigradient method for the solving of the nonlinear programming problems. Cybernetics, 91):145-150, Jan 1973. ISSN 1573-8337, doi: 10.1007/BF01066677, URL https: bttps://doi... http://oio..oggi/
wrg/ 10. 007/6700068677
[6] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-23) 2019.
[7] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2365 2013.
[8] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pages 314-323. PMLR, 2016.
[9] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1723 1732. PMLR, 2017.
[10] Zeyuan Allen-Zhu. How to make the gradients small stochastically: Even faster convex and nonconvex sgd. Advances in Neural Information Processing Systems, 31, 2018.
[11] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):1751 2018.
[12] Damek Davis, Dmitriy Drusvyatskiy, Kellie J MacPhee, and Courtney Paquette. Subgradient methods for sharp weakly convex functions. Journal of Optimization Theory and Applications, 179(3):922-982, 2018.
[13] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic math-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018.
[14] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
(15) Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328-333 334,, 2005.
[16] Krzysztof Kiwiel. Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM Journal on Optimization, 18(2):379-388, 2007.
[17] Szymon Majewski, Blažej Miasojedow, and Eric Moulines. Analysis of nonsmooth stochastic approximation: the differential inclusion approach. arXiv preprint arXiv:1805.01916 2018.
[18] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 20(1): 119-154, 2020.
[19] Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188(1): 2021.

---

[20] AA Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13 (1):14-22, 1977.
[21] Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 34, 2021.
[22] J.V. Burke, A.S. Lewis, and M.L. Overton. Approximating subdifferentials by random sampling of gradients. Mathematics of Operations Research, 27(3):667-588 2002. doi: 10. 1887moooo 27.3.567.317.
[23] Kamil A Khan and Paul I Barton. Evaluating an element of the clarke generalized jacobian of a composite piecewise differentiable function, ACM Trunsactions on Mathematical Software (TOMS), (-9(4):1-28) 2013.
[24] Jerome Bolte and Edouard Pauwels. A mathematical model for automatic differentiation in machine learning. arXiv preprint arXiv:2006. 02080, 2020.
[25] Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computation of approximate stationarity concepts of lipschitz functions. In International Conference on Machine Learning, pages 21360-21379. PMLR, 2022.
[26] James Burke, Frank Curtis, Adrian S Lewis, Michael I. Overton, and Lueas EA Simões. Gradient sampling methods for nonsmooth optimization. In Numerical Nonsmooth Optimization, pages 201-225. Springer, 2020.
[27] Sébastien Bubeck and Dan Mikulincer. How to trap gradient flow. Conference on Learning Theory, pages 940-960. PMLR, 2020.
[28] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points Mathematical Programming, 184(1):71-120, 2020.
[29] James V Burke, Adrian Lewis, and Michael L. Overton. A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM Journal on Optimization, 15(3):751-779, 2005.
[30] Ohad Shamir. Can we find nea--pproximmatlly-tatiinan points of nonsmooth nonconvex functions? arXiv preprint 0rXiv:2002./1962 2020.
[31] Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. J.
ACM, 51(4):540-556, 2004.
[32] Branko Grünbaum. Partitions of mass mass-distributions and of convex bodies by hyperplanes. Pacific Journal of Mathematics, 10(4):1257-1261. 1960.
[33] R. Kannan, Lovász, and M. Simonovits. Isoperimetric problems for convex bodies and localization lemma. Discrete Comput. Geom,, 13(3-4):541-559 Dec 1995.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 1.1
(c) Did you diseuss any potential negative societal impacts of your work? [N/A] Due the theoretical nature our work, we do not foresee any immediate potential negative societal impacts of
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All our complete proof' are in the appendix.
12


Reviews:
[{"review_id": "sRiqkcJ_DI", "reviewer": "Reviewer_e5FR", "summary": "This paper considers the problem of minimising a Lipschitz function that is potentially non-smooth. Such functions are widely used in machine learning such as neural networks based on the ReLU activation function.\nThey are known to be differentiable almost everywhere (in Lebesgue measure sense), and the so-called Clarke sub-differential can be used in place of the usual gradient.\n\nThe subgradient method is a classical algorithm for minimising such functions, and its behaviour has been well studied for weakly convex functions. Recently, the paper [ZLJ+20] proposed an algorithm for finding stationary points for arbitrary Lipshitz and directionally differentiable functions based on Goldstein's conceptual sub gradient method. Recently, this was also complemented with lower bounds.\n\nDespite its strengths, the algorithm of [ZLJ+20] requires the solution of a so-called auxiliary convex feasibility problem, which may be very difficult when the subgradient of the function is complicated. Hence the algorithm is not easy to implement in practice. \n\nThe paper proposes two algorithms that address these concerns by replacing the non-standard auxiliary problem (oracle) of [ZLJ+20] with a standard first-order oracle. This is implementable for any Lipschitz function where the gradients can be computed almost everywhere in terms of Lipschitz measure. The algorithms output an approximate stationary point. The number of gradient/function evaluations for the first algorithm has no dimension dependence, and $O(1/(\\epsilon^3 \\delta))$ dependence in the approximation accuracy parameters $\\epsilon$ and $\\delta$. The second algorithm has a better behaviour in low dimensions, with $O(d/(\\epsilon^2 \\delta))$ dependence, and even better rates for weakly convex functions.", "questions": "Do the authors think that this new algorithm could be used for training ReLU-based neural networks?\nThere have been many efforts recently on coming up with sharp bounds on the Lipschitz constants, but perhaps the computation time for such algorithms could be a limiting factor.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In our opinion, this is a very nice paper that studies a highly practically relevant question on finding stationary points for non-smooth Lipschitz functions.  The contributions of the paper are novel algorithms together with rigorous convergence analysis that obtain state-of-the-art accuracy guarantees for this problem. These algorithms cleverly use randomisation ideas to get around the issues of non-differentiability on a set of Lebesgue measure zero. The paper is very well written and it is a pleasure to read. In our opinion, this is an important contribution to the literature.\n\nThis is an important theoretical contribution with a significant amount of effort devoted to the proofs. It is understandable that there is no space in the current NeurIPS format for experimental evaluation, this is something that could be looked at in the future.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WU1gOgXpBkJ", "reviewer": "Reviewer_hvUX", "summary": "In this paper the authors propose a new algorithm to minimize a Lipschitz function.  The general machinery is based on the [ZLJ 20] algorithm and the main contribution of this paper is to propose a novel implementable oracle for it.\n", "questions": "line 53: extra space between reference and a word. \n\nparagraph after eq (4): either not larger instead of smaller or it should be a strict inequality later. Otherwise, $u=g$ is a counterexample.\n\nLemma 2: I think the constant can be improved from 16 to 4. It is clear that the given proof is not optimal: we estimate $\\|u - g\\|$ in a crude way. Instead, we should use $\\|u\\|^2, \\|g\\|^2$ separately because for the inner product we have a much nicer bound.  Not important of course, but a few consecutive constants will become smaller.\n\nLemma 3: We integrate here over $S^{d-1}\\times \\mathbb{R}_+$ and Fubini's theorem allows us to switch integrals. Why does it give us the existence of the set $Q$? I feel it should be correct but perhaps some argument is missing.\n\nProof of Lemma 3: different fonts for $Q$.\n\nline 194: Don't we need boundedness of $Q$ for min?\n\nline 204: It is correct, but I spent like 5 min to understand why it is so. Just adding \"first-order optimality condition\" would save me them.\n\nSection 3.1: I think it would be nicer to add more details. Right now it is written by someone and for someone who already knows all the ingredients: cutting plane algorithms, ellipsoid algorithms, center of gravity, etc. Perhaps with an extra page it would be possible to make that part more readable.\n\nProof of Th. 4: In the display equation we use Lipschitzness of $f$ twice, why not to mention it?\nMy simple geometry suggests that the bound for $\\| \\hat g_k - \\hat \\zeta\\|^2$ contains an extra factor $2$. \n", "limitations": "--", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In contrast to [ZLJ 20], the proposed algorithm is easy to implement. This was done without sacrificing a good complexity, which in our case  matches lower bounds. In lower dimensions using the cutting plane algorithm instead of the subgradient method, the authors were able to improve complexity upon [ZLJ 20].\n\nI think it is a nice paper with a clear and well-executed idea and with good explanations that show the motivation for each statement or its proof. However, the last section on low dimensions can be improved: first to make the reading more or less uniform and second to familiarize readers with those concept given there without definitions and intuition. I presume it was the page limit that prevented the authors from doing it in the first place.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "KeNP9TRNZr", "reviewer": "Reviewer_4qyS", "summary": "This work studies the problem of finding stationary points of a Lipschitz function. The paper is an improvement to [ZLJ+20], where in the latter the authors proposed an algorithm motivated by Goldstein's subgradient method. The main obstacle of [ZLJ+20] is that the proposed algorithm needs the solutions of a convex feasibility problem (outlined in eq. (2), page 2). Under the assumption that the objective function is Lipschitz and its gradient and function evaluations can be computed almost everywhere, this paper proposed an algorithm that overcomes the aforementioned limitation of [ZLJ+20] and can recover the main result of [ZLJ+20], outlined in Theorem 6, page 6.  Then, the authors claim that the paper can improve the efficiency of the algorithm in low dimensions. The results also provide a further improvement in the case that the objective function is weakly convex (defined in line 19). ", "questions": "1. Lines 110 - 111: \"Famously, [ZLJ+20] showed that one can significantly decrease the value of $f$...\". I will appreciate that if the authors address this in [ZLJ+20] and point out where is exactly such a result. \n\n2. In the proof of Lemma 3, what are the definitions of $\\mathbb{R}_{+}\\{y\\}$ and $Q$?\n\n3. In Algorithm 3, line 4: Since $\\Omega_k$ may be a complicated set, how one can compute the center of gravity of such a set?\n\n4. In Theorems 11 and 12: What is the definition of the covariance matrix of a convex set?", "limitations": "The authors addressed the limitations of their work (lines 98 - 99). I will update this part after the discussion phase and author responses. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The main contribution of the paper which is an improvement to [ZLJ+20] is well motivated. \n2. The authors provide a sufficient literature review. \n\nWeaknesses: \n\n1. From a technical point of view, it is not clear what the main technical novelties of this paper compare to [ZLJ+20].\n2. The paper suffers from a lack of a discussion section at the very end of the paper.\n3. In section 3 it would be nice if the authors emphasize more the role of \"low dimensions\", how they characterize the notion of \"low dimensions\" and technically exactly at which part they are exploring the low dimension phenomena.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6hnohsfzCCR", "reviewer": "Reviewer_XcwW", "summary": "This paper deals with optimization in the non smooth and non convex setting. This work is mainly based on the definitions of [Gol77] and recent results of [ZLJ+20].\n\nIt allows to find an efficient algorithm (combination of Algorithms 1 and 2) which guarantees (Corollary 5 and Theorem 6) hold only assuming $L$-Lipschitz continuity and almost everywhere differentiability (in the sense of the Lebesgue measure).\n\nThen, authors propose a cutting-plane method to solve the intermediate minNorm problem (previously solve by Algorithm 1).\nThe advantage of this is the improvement in complexity dependance to $\\epsilon$.\nThe drawback is the dependence on $d$.\nThis is therefore useful in small dimension.", "questions": "l.47: I think what the cited paper means is that if one has access to the solution of (2) for the functions that are composed together, then the chain rule provides the solution for the function of interest.\n\nl.61: This is a strong affirmation based on the assumption that the previous claim is false.\n\nl.110: « Famously, [ZLJ+20] showed ». I think authors here refer to « [Gol77] ».\n\nl.113: minor: authors use the notation $x_0$ to refer to the first iterate. Then use the indices starting from 1 for $g$. I suggest uniforming the notations.\n\nl.113: I also suggest removing the O notation in the last equation since it seems we have $T\\leq\\frac{\\Delta}{\\delta \\epsilon}$.\n\nl.123: « A short computation shows that this is sure to be the case for all small $\\lambda > 0$ as long as $\\left< u, g \\right> \\leq \\|g\\|^2$ ». As one can see in l.132, this argument relies on the first order expansion on the norm of interest. the second term is non negative, but for small $\\lambda$, we expect the first term to be dominant. This is actually true if and only if the first term is not zero, hence the inequality $\\left< u, g \\right> \\leq \\|g\\|^2$ must be replaced by the strict inequality: $\\left< u, g \\right> < \\|g\\|^2$. Reason why the $\\delta / 2$ is used in equation (4) and Algorithm 1 even uses $\\delta/4$.\n", "limitations": "No limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Good guarantees with few assumptions.\n\nWeakness:\n- [ZLJ+20] already got similar results. Only the need of solution to (2) is assumed. And the claim made by this paper on this oracle seem strong (see first point of next section).\n\n===================================================================================================\n========================================= After rebuttal ==============================================\n===================================================================================================\n\nThe oracle [ZLJ+20] uses is indeed not computationally easy to build, for instance not compatible with the chain rule.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept