Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization
Authors: Tianyi Lin
Zeyu Zheng
Michael Jordan
Venue: NeurIPS 2022 Accept (2022)
Keywords: gradient-free methods
nonsmooth nonconvex optimization
finite-time convergence guarantee
Goldstein subdifferential
smoothing

Abstract: Nonsmooth nonconvex optimization problems broadly emerge in machine learning and business decision making, whereas two core challenges impede the development of efficient solution methods with finite-time convergence guarantee: the lack of computationally tractable optimality criterion and the lack of computationally powerful oracles. The contributions of this paper are two-fold. First, we establish the relationship between the celebrated Goldstein subdifferential~\citep{Goldstein-1977-Optimization} and uniform smoothing, thereby providing the basis and intuition for the design of gradient-free methods that guarantee the finite-time convergence to a set of Goldstein stationary points. Second, we propose the gradient-free method (GFM) and stochastic GFM for solving a class of nonsmooth nonconvex optimization problems and prove that both of them can return a $(\delta,\epsilon)$-Goldstein stationary point of a Lipschitz function $f$ at an expected convergence rate at $O(d^{3/2}\delta^{-1}\epsilon^{-4})$ where $d$ is the problem dimension. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results. Finally, we demonstrate the effectiveness of 2-SGFM on training ReLU neural networks with the \textsc{Minst} dataset.

Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization
Tianyi Lin
Zeyu Zheng Michael Jordan
University of California, Berkeley
[darren_ lin, wtw.eennnnn..negnnnnnaaoaaaa (ygzhheng)berkeeegg. edu, jordan@cs fordan@cs.berkeley. edu
Abstract
Nonsmooth nonconvex optimization problems broadly emerge in machine learning and business decision making. whereas two core challenges impede the develop- ment of efficient solution methods with finite-time convergence guarantee: the lack of computationally tractable optimality criterion and the lack of computationally powerful oracles. The contributions of this paper two-fold. First, establish the relationship between the celebrated Goldstein subdifferential [46] and uniform smoothing. thereby providing the basis and intuition for the design of gradient- methods that guarantee the finite-time convergence to a set of Goldstein stationary points. Second, we propose the gradient-fiee free method (GFM) and stochastic GFM for solving class of nonsmooth nonconvex optimization problems and prove that both of them can return (8, Goldstein stationary point of Lipschitz function f at an expected convergence rate at ( (---)) where d is the problem di- mension. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results. Finally, we demonstrate the effectiveness of 2-SGFM on training ReLU neural networks with the MINST dataset.
1 Introduction
Many of the recent real-world success stories of machine learning have involved nonconvex opti- mization formulations, with the design models and algorithms often being heuristic and intuitive. Thus gap has arisen between theory and practice. Attempts have been made to fill this gap for different learning methodologies, including the training of multi-layer neural networks [25], orthogo- nal tensor decomposition [41], M-estimators [63, 64], synchronization and MaxCut [6, 66], smooth semidefinite programming [15], matrix sensing and completion [10. 42], robust principal component analysis (RPCA) [43] and phase retrieval [82. 79, 64]. For an overview of nonconvex optimization formulations and the relevant MI applications, we refer to a recent survey [51].
is generally intractable to compute an approximate global minimum [69] or to verify whether point is a local minimum high-order saddle point [67]. Fortunately, the notion of approximate stationary point gives a reasonable optimality criterion when the objective function f's smooth; the goal here is find point
I&d such that || [(x)]l || < e. Recent years have seen rapid algorithmic development through the lens of nonasymptotic convergence rates to e-stationary points [70, 44, 45, 20, 21, 53). Another line of work establishes algorithm-indege independenn lower bounds [22, 23, 4].
Relative to its smooth counterpart, the investigation nonsmooth optimization is relatively searce, particularly in the nonconvex setting, both in terms of efficient algorithms and finite-time convergence guarantees. Yet, over several decades, nonsmooth nonconvex optimization formulations have found applications in many fields. A typical example is the training multi-layer neural networks with ReLU neurons, for which the piecewise linear activation functions induce nonsmoothness. Another example arises in controlling financial risk for asset portfolios or optimizing customer satisfaction in service systems or supply chain systems. Here, the nonsmoothness arises from the payoffs of financial
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

derivatives and supply chain costs, e.g., options payoffs [38] and supply chain overage/underage costs [78]. These applications make significant demands with respect to computational feasibility. and the design of efficient algorithms for solving nonsmooth nonconvex optimization problems has moved to the fore [65, 30, 28, 85, 12, 31, 80].
The key challenges lie in two aspects: (i) the lack of computationally tractable optimality criterion, and (ii) the lack of computationally powerful oracles. More specifically, in the classical setting where the function f is Lipschitz, we can define e-stationary points based on the celebrated notion of Clarke stationarity [26]. However, the value of such a criterion has been called into question by Zhang et al. [85], who show that no finite-time algorithm guarantees e-stationarity when é is less than a constant. Further, the computation of the gradient impossible for many application problems and we only have access to a noisy function value at each point. This is a common issue in the context of simulation optimization [68, 48]; indeed, the objective function value is often achieved as the output of black-box or complex simulator, for which the simulator does not have the infrastructure needed to effectively evaluate gradients; see also Ghadimi and Lan [44] and Nesterov and Spokoiny [72] for comments on the lack of gradient evaluation in practice.
Contribution. In this paper, we propose and analyze class of deterministic and stochastic gradient- free methods for nonsmooth nonconvex optimization problems in which we only assume that the function f is Lipschitz. Our contributions can be summarized as follows.
1. We establish relationship between the Goldstein subdifferential and uniform smoothing via appeal to the hyperplane separation theorem. This result provides the basis for algorithmic design and finite-time convergence analysis of gradient-free methods to (6, -GGGdssttn stationary points.
2.
We propose and analyze a gradient-free method (GFM) and stochastic GFM for solving a class of nonsmooth nonconvex optimization problems. Both of these methods are guaranteed to return a (6, e) --Goldstein stationary point of a Lipschitz function / Rd - with an expected convergence rate of O(8/28-1
where d 2 is the problem dimension. Further, we propose the two-phase versions of GFM and SGFM. As our goal is return (6, e)-Goldstein stationary point with user-specified high probability 1 - A, we prove that the two-phase version of GFM and SGFM can improve the dependence from (1/A)* to log(1/A) in the large-deviation regime.
Related works. Our work is related to line of literature on gradient- methods for nonsmooth and nonconvex optimization and gradient-free methods for smooth and nonconvex optimization. Due to space limitations, we defer our comments on the former topic to Appendix A. In the context of gradient-free methods, the basic idea is to approximate a full gradient using either a one-point estimator [39] or a two-point estimator [1. 44, 37, 75, 72], where the latter approach achieves a better finite-time convergence guarantee. Despite the meteoric rise of two-point-based
gradient-free methods, most of the work restricted to convex optimization [37, 75, 83] and smooth and nonconvex optimization [72, 44, 61, 62, 24, 52, 49]. For nonsmooth and convex optimization, the best upper bound on the global rate of convergence is O 2) [75] and this matches the lower bound [37]. For smooth and nonconvex optimization, the best global rate of convergence is O - [72] and Odd -4) if we only have access to noisy function value oracles [44], Additional regularity conditions, e.g., finite-sum structure, allow us to leverage variance-reduction techniques [62, 24, 52] and the best known result is ( [49]. However, none of these gradient- free methods have been developed for nonsmooth nonconvex optimization and the only gradient- free method we are aware of for the nonsmooth is summarized in Nesterov and Spokoiny [72, Section 7].
2 Preliminaries and Technical Background
We provide the formal definitions for the class of Lipschitz functions considered in this paper, and the definitions for generalized gradients and the Goldstein subdifferential that lead to optimality conditions in nonsmooth nonconvex optimization.

---

2.1 Function classes
Imposing regularity on functions be optimized is necessary for obtaining optimization algorithms with finite-time convergence guarantees [71]. In the context of nonsmooth optimization there are two types of regularity conditions: Lipschitz properties of function values and bounds on function values.
We first list several equivalent definitions of Lipschitz continuity. A function f Rd - IR is said to be L--Lipschitz if for every RRd and the direction v E Rd with ||v]]| s 1, the directional projection (x.v(1) == f(x + tv) defined for t E R satisfies
1fx. - (t.( S Llt - t. for all t, t' E IR
Equivalently, f is L-Lipschitz if for every x, x' E _2d we have
[f(x) - fxx') = L||x - x'I|. Further, the function value bound - - f(x)
appears in complexity guarantees for smooth and nonconvex optimization problems [71] and is often assumed to be bounded by positive constant A > O. Note that x" is a prespecified point (i.e., an initial point for an algorithm) and we simply fix for the remainder of this paper. We define the function class which will be considered in this paper.
Definition 2.1 Suppose that A > 0 and I. O are both independent of the problem dimension d 2 1. Then, we denote Fa(A, AA, L.) as the set of T--Lipschitz,uune functions f : Rdd + IR with the bounded funcctioo value f(x") - inf xERe (x) A.
The function class Fa(A, L) includes Lipschitz functions on Rd and is thus different from the nonconvex function class considered in the literature [44, 72]. First, we do impose a smoothness condition on the function f E Fa(A, L). in contrast to the nonconvex functions studied in Ghadimi and Lan [44] which are assumed to have Lipschitz gradients. Second, Nesterov and Spokoiny [72, Section 7] presented a complexity bound for randomized optimization method for minimizing a nonsmooth nonconvex function. However, they did not clarify why the norm of the gradient of the approximate function fp of the order 5 (we use their notation) serves as a reasonable optimality criterion nonsmooth nonconvex optimization. They also assume an exact function value oracle, ruling out many interesting application problems in simulation optimization and machine learning.
In contrast, our goal is to propose fast gradient-free methods for nonsmooth nonconvex optimization in the absence of an exact function value oracle. In general, the complexity bound of gradient-free freee methods will depend on the problem dimension d 2 even when we assume that the function to be optimized is convex and smooth [37, 75]. As such, we should consider function class with a given dimension d 2 1. In particular, we consider a optimality criterion based on the celebrated Goldstein subdifferential [46] and prove that the number of function value oracles required by our deterministic and stochastic gradient-free free methods
find a (6, e)-Goldstein stationary point of Fa L.) is (poly(d, T., A, /e, 1/8) when d, E (0, 1) are constants (see the definition of Goldstein stationarity in the next subsection).
is worth mentioning that Fa(A, L.) contains a rather broad class of functions used in real-world application problems. Typical examples with additional regularity properties include Hadamard semi- differentiable functions [76, 32, 85], -hiinee-ttratffaale functions [13, 30], o-minimally definable functions [27] and a class of semi-algebraic functions [5, 30J. Thus, our gradient-fret methods can be applied for solving these problems with finite-tmme convergence guarantees.
2.2 Generalized gradients and Goldstein subdifferential
We start with the definition of generalized gradients [26] for nondifferentiable functions. This is perhaps the most standard extension of gradients to nonsmooth and nonconvex functions.
Definition 2.2 Given a point x E TRd and a direction v E RRd,, the generalized directional derivative fly+tv) ffy), Then, the
of nondifferentiable function is given by Df(x; v) = lim supy -x.110 generalized gradient of f is defined
set 0f(x) == [g RRd :g' TTgT S D D)(x; E Rd).
Rademacher's theorem guarantees that any Lipschitz function is almost everywhere differentiable. This implies that the generalized gradients of Lipschitz functions have additional properties and we can define them in a relatively simple way. The following proposition summarizes these results; we refer to Clarke [26] for the proof details.
3

---

Proposition 2.1 Suppose that f is L-Lipschitz.,or for some L > O, we have that (f is a nonempry, convex and compact set and Ig L for all g E 0x Further, af(-) is an upper-semicontiiuons set-valued map. Moreover, a generalization of mean-value theorem holds: for any X1,X0 R there
exist X E (0, 1) and g E 0f(xx: + (1 A)x2) such that f(x1) fxx2) g (x1 X2). Finally, there is simple way represent the generalized gradient 0x(x):
0f(x) == conv
g RERE :g=
lim Vf(xa)
Xx +x
which is the convex hull of all limit points of V fxx)) over all sequences X1, X2,X,,.. of differentiable points of f()) which converge to x.
Given this definition of generalized gradients, Clarke stationary point of is a point x satisfying 0 E (x). Then, it is natural to ask if an optimization algorithm can reach an e-stationary point with a finite-time convergence guarantee. Here a point x E R is an e- e-Clarke stationary point if
min flgll g E [f(x)}
This question has been addressed by [85, Theorem I]. who showed that finding e-Clarke stationary points in nonsmooth nonconvex optimization can not achieved by any finite-time algorithm given fixed tolerance E [0. 1). One possible response is to consider relaxation called near c-Clarke stationary point. Consider a point which 6-close to an e-stationary point for some 8 > 0. A point Rd is near e-stationary if the following statement holds true:
min [lgl| g E OyEB,(x)00f())) e.
Unfortunately, however, [58, Theorem 1] demonstrated that impossible to obtain worst-case guarantees for finding a near c- c-Clarke stationary point of f E Fa(A, L) when c, > 0 are smaller than some certain constants unless the number of oracle calls has an exponential dependence on the problem dimension d 2 1. These negative results suggest need for rethinking the definition of targeted stationary points. We propose to consider the refined notion of Goldstein subdifferential.
Definition 2.3
Given a point x I2d and 8 > O, the 8-Goldstein subdifferential of Lipschitz function I al x is given by 0,J == (onv(Uyez.ts)
The Goldstein subdifferential of at x is the convex hull of the union of generalized gradients at points in a d-ball around x. Accordingly, can define the (6, Gooodsetni stationary points; that is, point x E IRdd is a (6, c)-Goldstein stationary point if the following statement holds:
min ||g|| g E 0sf(xx) S.c.
It is worth mentioning that (GldssGe stationarity is weaker notion than (near) c-Clarke stationarity since any (near) e-stationary point is a (ő, e)Goodsttinn stationary point but not vice versa. However, the converse holds true under smoothness condition [85, Proposition 6] and limazo (x = ax(x) ) holds as shown in Zhang et al. [85, Lemma 7J. The latter result also enables an intuitive framework for transforming nonasymptotic analysis of convergence to (8, GoGlossttin stationary points to classical asymptotic results for finding e- e-Clarke stationary points. Thus, we conclude that finding (ò, e)- Golddstein stationary point reasonable optimality condition for general nonsmooth nonconvex optimization.
Remark 2.2 Finding a (ő, GooGssstninn stationary point in nonsmooth nonconvex optimization has been formally shown be computationally tractable in an oracle model [85, 31, 80]. Goldstein [46] discovered that one can decrease the function value of Lipschitz f by using the minimal-none element of Os. (x) and this leads a deterministic normalized subgradient method which finds (6, -olodsttnnnn stationary point within O x(2) iterations. However, Goldstein's 's algorithum is only conceptual since it is computationally intractable to return an exact minimal noorm element of 0' fx).. Recently, the randomized variants of Goldstein' 's algorithm have been proposed with a convergence
des [85, 31, 803. However, it remains unknown if gradient-free methods find a (ō, (d,e))Goldstter --Goldstein stationary point of Lipschitz function I within (poly(d, L,, A, 1/c,1/8) teeraions the absence of an exact function value oracle. Note that the dependence on the problem dimension d 2 1 is necessary for gradient-free free methods mentioned before.
guarantee of ( AT²

---

2.3 Randomized smoothing
The randomized smoothing approaches simple and work equally well for convex and nonconvex functions. Formally, given the L-Lipschitz function f (possibly nonsmooth nonconvex) and a distribution P,, define (x)
Eu-elf(x + 5u)]. In particular, letting P be standard Gaussian distribution, the function fa is a á 5T. aappoopiipoooiiitionn of f(.) and the gradient V is Ly _ where d 2 1 is the problem dimension; see Nesterov and Spokoiny [72, Theorem and Lemma 2]. Letting PP be an uniform distribution on an unit ball in l2-norm, the resulting function fa is 6L- approximation of f(-) and ffs is also cLyd Lipschitz where d 2 1 is the problem dimension; see Yousefian et al. [84, Lemma 8] and Duchi et al. [36, Lemma F.2), rephrased as follows.
Proposition 2.3 Let fo(x) [x òu]] where IP is an uniform distribution 1--ormm Assuming that f is L-Lipschitz, we have (i) (fa(x)) Σ 8L, and (ii) fo is differentiable and L-Lipschitz with the ...ss--ipschitt gradient where > 0 is constant. In addition, there exists a function if for which each of the above bounds are tight simultaneously.
unit ball in
The randomized smoothing approaches form the basis for developing gradient-fre methods [39, 1, 2, 44, 72]. Given an access to function values of f. we can compute an unbiased estimate of the gradient of fa and plug them into stochastic gradient-based methods. Note that the Lipschitz constant of fa depends the problem dimension d > 1 with least factor of vd for many randomized smoothing approaches [58, Theorem 2]. This is consistent with the lower bounds for all gradient-fie free methods in convex and strongly convex optimization [37, 75].
3 Main Results
We establish relationship between the Goldstein subdifferential and the uniform smoothing approach. We propose a gradient-free method (GFM), its stochastic variant (SGFM), and two-phase version of GFM and SGFM. We analyze these algorithms using the Goldstein subdifferential; we provide the global rate and large-deviation estimates terms of (8, Golddsein stationarity.
3.1 Linking Goldstein subdifferential to uniform smoothing
Recall that 0&f and fs are defined by (xf(x) == conv conv(UyyyBsse))) (ffF))())0f))) and fs(x) Eu-elf(x ōu)]. It is clear that is almost everywhere differentiable since is T--Lipschitz. This implies that fx = Eu-r[ /V f(x + 6u]] and demonstrates that fx((x) can be viewed intuitively as a convex combination of V fz) over an infinite number of points E [x)... As such, it is reasonable to conjecture that fx) E fsf(xx for any Rd However, the above argument is not rigorous proof; indeed, we need to justify why fx() = Eu-e f + 5u)] if f is almost everywhere differentiable and generalize the idea of convex combination to include infinite sums. To resolve
these issues, we exploit a toolbox due to Rockafellar and Wets [74].
In the following theorem, we summarize our result and refer to Appendix C. for the proof details.
Theorem 3.1 Suppose that f is L-Lipschitz and let fs(x) uniform distribution on unit ball in fn-norm and let O be a 8 5-Goldstein subdifferential of f (cf. Definition 2.3). Then, we have (x) 0xf(x) 3 for any x Rd
Eu-elf(x ōu)]. where is an
Theorem 3.1 resolves an important question and forms the basis for analyzing our gradient-free methods. Notably, our analysis can be extended justify other randomized smoothing approaches in nonsmooth nonconvex optimization. For example, Nesterov and Spokoiny [72] used Gaussian smoothing and estimated the number of iterations required by their methods output E Bd satisfying V fa [x))] < c. By modifying the proof of Theorem 3.1 and Zhang et al. [85, Lemma 7], we can prove that V V.s belongs to Goldstein subdifferential with Gaussian weights and this subdifferential converges to the Clarke subdifferential as ő - 0. Compared to uniform smoothing and the original Goldstein subdifferential, the proof for Gaussian smoothing quite long and technical [72, Page 554], and adding Gaussian weights seems unnatural in general.
5

---

Algorithm Gradient-Free Method (GFM)
1: Input: initial point x" RR stepsize 0, problem dimension d 2 smoothing parameter and
iteration number 2 1.
2: for t = 0, 1, ......, , do
3: Sample w E Rd uniformly from a unit sphere in R2
4: Compute g² = 23 (f('
8w") f(x 8w'))w'.
5: Compute x ++1 = x 7/.6.
6: Output: x where I E 1,2 1........ T 13 is uniformly sampled.
Algorithm 2 Two-Phase Gradient-Free Method (2-GFM)
1: Input: initial point x" Rd, stepsize 7) 0, problem dimension d 2 smoothing parameter 5, iteration number 7 1, number of rounds 1 and sample size B.
do 3: Call Algorithm with x². d, and T and let x, be an output.
for 0, 2, ....
4: for = 0...,
do
5: for k
1, ......
do
6:
Sample w E R uniformly from unit sphere in Rd
7: Compute g.
(f( 5w") - f(x, 8w" ))w
28
Compute g: B-1 k- 8s
9:
Choose an index
E 10, 10,1, S- - 1} such that s" = argmin 0.11.................. 1 |lg.
10:
Output: x.*.
3.2 Gradient-free methods
We analyze gradient-free method (GFM) and its two-phase version (2-GFM) for optimizing a Lipschitz function f. Due to space limitations, we defer the proof details to Appendix D.
Global rate estimation. Let f Fd R be a L-Lipschitz function and the smooth version of is then the function f& [/ + ōu)] where IP is uniform distribution on unit ball in f2-norm. Equipped with Lemma 10 from Shamir [75], we can compute an unbiased estimator for the gradient (x') using function values.
This leads the gradient-free method (GFM) in Algorithm that simply performs one-step gradient descent to obtain x². It is worth mentioning that we use random iteration count I to terminate the execution of Algorithm and this will guarantee that GFM is valid. Indeed, we only derive that min |/ fx())] S c in the theoretical analysis (see also Nesterov and Spokoiny [72. Section 7]) and finding the best solution from {x', xx....,x" x") [V || is unknown. To estimate them using Monte Carlo simulation would incur additional approximation errors and raise some reliability issues. The idea of random output is not new but has been used by Ghadimi and Lan [44] for smooth and nonconvex stochastic optimization. Such scheme also gives us computational gain with factor of two in expectation.
is difficult since the quantity
Theorem 3.2 Suppose that f is L-Lisschitz and let
and < <<< Then, there exists some T> 0 such that the output of Algorithu I with n = 1 V 1.7/ satisfies that Elmin([le] l g (x)(x S and the total number of calls of the function value oracle is bounded by
((A+8L)
(
o
L
AL3
c
det
where d 2 1 is the problem dimension, L > 0 the Lipschtiz parameter of f and A is an upper bound for the initial objective function gap. f(x") - infxeR f(x) > 0.
Remark 3.3 Theorem 3.2 illustrates the difference between gradient- -assed and gradient-free meth- ods in nonsmooth nonconvex optimization. Indeed, Davis et al. [31] has recently proved the rate of Ô c > a randomized gradient- gradient-based based method in terms of (8,e)-GGooae GGGodsstni stationariry. Further, Theorem 3.2 demonstrates that nonsmooth nonconvex optimization is likely to intrinsically harder than all other standard settings. More specifically, the state-of-in ohe-te-art-------- rate for gradient-fres methods (de 2) for nonsmooth convex optimization terms of objective function value gap [37] and smooth nonconvex optimization in terms of gradient norm [72]. Thus, the dependence on d 2 is

---

linear in their bounds yet d' in our bound. We believe it is promising to either improve the rate of gradient-fre methods or show the impossibility by establishing a lower bound.
Large-deviation estimation. While Theorem 3.2 establishes the expected convergence rate over many runs of Algorithm we are also interested in the large-deviation properties for single run. Indeed, we hope to establish a complexity bound for computing a (ò, A)-solution; that is, a point x E I satisfying Prob min { || g E 0sf(x)} Sc) 2 1 for some > 0 and 0 < e, <
By Theorem 3.2 and Markov's 's inequality.
Prob (min(
g g E 0xs(x²)) 2 XE|min(lg]] g E 0s s x for all X > 0,
we conclude that the total number of calls of the function value oracle is bounded by
o o(a
L
8A424 0A422 ))
AL3
(3.1)
This complexity bound is rather pessimistic in terms of its dependence on A which is often set to be small in practice. To improve the bound, we combine Algorithm 1 with post-optimization procedure [44], leading to two-phase gradient-free method (2-GFM), shown in Algorithm 2.
Theorem 3,4 Suppose that f is L-Lipschitz and let ó > 0 and 0 < E.A < 1. Then, there exists some S. B > such that the output of Algorithm 2 with TO
V ed3/31,7T satisfies that Probímin {llgl) g 0xf(x, }}} 2 c) S A and the total number of calls of the function value oracle bounded by
1 M(++8L)
o d8
(
L
AL3
dL
)
1
log2
log2
ded
Ac
where d 2 the problem dimension, I. > 0 the Lipschtiz parameter of f and A is an upper bound for the initial objective function gap, [(x") - infxxx= f(x) > 0.
Clearly, the bound in Theorem 3.4 is significantly smaller than the corresponding one in Eq. (3.1) in terms of the dependence on 1/A, demonstrating the power of the post-optimization phase.
3.3 Stochastic gradient-free methods
We turn to the analysis of a stochastic gradient-free method (SGFM) and its two-phase version (2-SGFM) for optimizing a Lipschitz function f()) = EeEP, E)].
Global rate estimation. In contrast to minimizing deterministic function f, we only have access to the noisy function value F(x. {) at any point x E Id where a data sample & is drawn from distribution Py. Intuitively, this a more challenging setup. It has been studied before in the setting of optimizing a nonsmooth convex function [37, 72] or smooth nonconvex function [44]. As in these papers, we assume that (i) F(. {) is Lipsscizt with Eçer, [L)( < G2 for some G and (ii) E[F(x, E*)] = f(x) for all x E Rd where çe simulated from P,, at the 4hh iteration.
Despite the noisy function value, we can compute an unbiased estimator of the gradient (xx) where fs = (x + ōu)] Eu-P,E,, + ōu, {) In particular, we have g' dw - - F(x' ,w(, (w'("))))' Clearly, under our assumption, we have
28 (F(x*
d
Eu-P.eEP, [g'] EuwPl/EEES [g ul En-r ff(('')
where g' is defined in Algorithm 1. However, the variance of the estimator g can be undesirably large since F(-.)) {) is LiEs-hipshiizz for (possibly unbounded) random variable L(E) > 0. To resolve this issue, we revisit Shamir [75, Lemma 10] and show that in deriving an upper bound for Eu-P Cer.P.CCP,.Illee [| it suffices to assume that EçeP, [ S G for some constant G 0. The resulting bound achieves linear dependence in the problem dimension d > 0 which is the same as in Shamir [75, Lemma 10J. Note that the setup with convex and L(g)-Lipschitz functions F(:E) has been considered in Duchi et al. [37]. However, our estimator is different from their estimator of g. = =F + /w', gt) F(x", (x)',")))" which essentially suffers from the quadratic dependence in d >> 0. It is also necessary to employ random iteration count R to terminate Algorithm 3.
7

---

Algorithm 3 Stochastic Gradient-Free Method (SGFM)
1: Input: initial point x" RR stepsize 0, problem dimension d 2 smoothing parameter and iteration number
for t 0, 0,2, ...... : do
3: Simulate Ç from the distribution Pp-
4: Sample w' Rd uniformly from unit sphere in IR.
5: Compute g = 4 (P(x' + ów", g') - F(x' 8w"; w'"),"
26
6: Compute x x" "18..
7: Output: where R E {0. 1, ..,, t is uniformly sampled.
Algorithm 4 Two-Phase Stochastic Gradient- Free Method (2-GGFM)
I: Input: initial point x" RR, stepsize 7j > O, problem dimension 2 smoothing parameter 6, iteration number 7 2 1, number of rounds $ 2 1 and sample size B.
2: for = 0, 2,
S . do 3: Call Algorithm with x 1). d. ô and I' and let be output.
for 0, 1, ............
do
for l: = 0, 1, 1,2....; B
6: Simulate 5 from the distribution Pp-
Sample w* E _ uniformly from unit sphere Rd
Compute g
d (F(x, + oww 5²)) F(x, Sw ))w",
26
9: Compute g. B -k=0 ge.
10: Choose an index E 10.1, S 1} such that s argmin [lg:
11:
Output: "5*
Theorem 3.5 Suppose that F-. is L(E)-Lipschitz with EeEP (L?(EE) S G for some G > O and let and 0 < < 1. Then, there exists some T > 0 such that the output of Algorithm 3 with 1 5(A+5G)
7 = 10 V cfa/T satisfies that (minn(ggl g E 0af((x)) e and the total number of calls of the noisy function value oracle is bounded by
o
(a
G
AG3
8ed
where d > is the problem dimension. L 0 is the Lipschtiz parameter of and A 0 is upper bound for the initial objective function gap. fxx") - infx f(x) 0.
In the stochastic setting, the gradient- gradient-based based method achieves the rate of O(5-le-4) for a randomized gradient- method terms of (-Goldsnnn stationarity [31]. As such, our bound in Theo- rem 3.5 is tight up to the problem dimension d 2 1. Further, the state-of-ther
rate for stochastic gradient-free methods O(de-2) for nonsmooth convex optimization in terms objective function value gap [37] and Odd for smooth nonconvex optimization in terms of gradient norm [44]. Thus, Theorem 3.5 demonstrates that nonsmooth nonconvex stochastic optimization essentially the most difficult one among than all these standard settings.
Large-deviation estimation. As in the case of GFM, we hope to establish complexity bound of SGFM for computing a (6, c, A)-solution. By Theorem 3.5 and Markov's 's inequality, we obtain that the total number of calls of the noisy function value oracle bounded by
o A+C
0
G
AG
))
(3.2)
SA+c1
We also propose a two-phase stochastic gradient-free method (2-SGFM) in Algorithm by combining Algorithm with post-optimization procedure.
Theorem 3.6 Suppose that F(:E) LLp)-Lipschitz with Rggr [ s G for some > O and let 8 > O and ( < C, A < Then, there exists some T,S, B > O such that the output of Algorithm 4 6(++5))
with 7 1 / satisfies that Prob(min g E fxf(x,) }H 2 E) A and the total
number of calls of the noisy function value oracle is bounded by
o 0
4
AG3
1
dG²
1 )
loga
Loga
7
el Se
A
A

---

1966
Adam
Then Low
500
Adkgrad Min
Man
2-2ZMM
20227
spccs
Eouch
Esech
(a) Train Accuracy
(b) Tost Accuracy
(c) Train Loss
(d) Test Loss
Figure 1: Performance of different methods on training CNNs with the MNIST dataset.
Saito
Mo
2-:00
D-:00
50013 s081)
Jot 00801
Opoch
Opoch
Opecn
(a) Effect of B (Train)
(b) Effect B (Tes)
(c) Compare with SGD (Train)
(d) Compare with SGD (Test)
Figure 2: (a-b) Performance of 2-SGFM with different choices of B. (c-d) Performance of 2-SGFM and SGD
with different choices of learning
where d > is the problem dimension, L > 0 is the Lipschtiz parameter of and A 0 is upper bound for the initial objective function gap f(x") inf fxx) O.
Further discussions. We remark that the choice of stepsize r) all of our zeroth-order methods depend on A, whereas such dependence is not necessary in the first-order setting; see e.g., Zhang et al. [85]. Setting the stepsize without any prior knowledge of A, our methods can still achieve finite-time convergence guarantees but the order would become worse. This is possibly because the first-order information gives more characterization of the objective function than the zeroth-order information, so that for first-order methods the stepsize can be independent of more problem parameters without sacrificing the bound. A bit on the positive side is that, suffices for our zeroth-order methods to know estimate of the upper bound of ((A), which can be done in certain application problems.
Moreover, we highlight that tionarity (see Definition 2.3) relaxes c-Clarke stationarity and our methods pursue an (6, -statioonyyyy point since finding an e- c-Clarke point intractable. This is different from smooth optimization where e- e-Clarke stationarity reduces to V fxx I e and becomes tractable. In this context, the existing zeroth- order methods are designed to pursue an e-stationary point. Notably, ( -Goldstein stationary point is provably an e-stationary point in smooth optimization if we choose that relies on d and
is the desired tolerance in our setting. In fact, (ő, Gooodsstni sta-
Experiment
We conduct numerical experiments to validate the effectiveness our proposed methods. In particular, we evaluate the performance of our two two-phase version of SGFM (Algorithm 4) on the task of image classification using convolutional neural networks (CNNs) with ReLU activations. The dataset we use is the MNIST 'ataset [60] and the CNN framework we use is: (i) we set two convolution layers and two fully connected layers where the dropout layers [77] are used before each fully connected layer, and (ii) two convolution layers and the first fully connected layer associated with ReLU activation. It is worth mentioning that our setup follows the default one" and the similar setup was also consider in Zhang et al. [85] for evaluating the gradient-based methods (see the setups and results for CIFAR LO dataset in Appendix F).
The baseline approaches include three gradient- based methods: stochastic gradient descent (SGD), ADAGRAD [34] and ADAM [55]. We compare these methods with 2-SGFM (cf. Algorithm 4) and set the learning rate 7 0.001. All the experiments are implemented using PyTorch [73] on workstation with 2.6 GHz Intel Core i7 and 16GB memory.

---

68
B-50
B-50
B=100
B=100
B-200
67
B-200
Train LOSS
0.5
0-4
03
0.3
Epoch
Epoch
(a) Effect of B (Train Loss)
(b) Effect of (Test Loss)
Figure 3: Performance of 2-SGFM with different choices of B.
(4-00000
Than
18.0 2001
18:00.00 scm
Spoch
Spoch
Eouch
Eoedh
(a) Effect y (Train
(b) Effect of y (Test
(c) Effeet (Train
(d) Effect n (Test Loss)
Figure 4: Performance of 2-SGFM with different choices of learning rates.
Figure summarizes the numerical results on the performance SGD, ADAGRAD, Adagrad, ADAM, INDG [85], and our method 2-SGFM with = 0.1 and B 200. Notably, 2-SGFM is comparable to other gradient-based methods terms of training/test accuracy/loss even though it only use the function values. This demonstrates the potential value of our methods since the gradient-bar based methods are not applicable in many real-world application problems as mentioned before. Figure 2a and 2b presents the effect of batch size B > in 2-SGFM; indeed, the larger value of B leads to better performance and this accords with Theorem 3.6. We also compare the performance of SGD and 2-SGFM with different choices of n,. From Figure 2c and 2d, we that SGD and 2-SGFM achieve similar performance in the early stage and converge to solutions with similar quality.
Figure summarizes the experimental results on the effect of batch size B for 2-SGFM. Note that the evaluation metrics here are train loss and test loss. It clear that the larger value of B leads to better performance and this is consistent with the results presented in the main context. Figure interesting to
summarizes the experimental results on the effect of learning rates for 2-SGFM. see that 2-SGFM can indeed benefit from more aggressive choice of stepsize v) >> 0 in practice and choice of r) = 0.0001 seems be too conservative.
Conclusion
We proposed and analyzed class of deterministic and stochastic gradient-fred free methods for optimizing a Lipschitz function. Based on the relationship between the Goldstein subdifferential and uniform smoothing that have established, the proposed GFM and SGFM proved return (ō, e)- Goldstein stationary point guarantee and improve by combining GFM and SGFM with two-phase scheme. Experiments on training neural networks with the MNIST and CIFARIO datasets demonstrate the effectiveness of our methods. Future directions include the theory for non-Lipschitz and nonconvex optimization [11] and applications of our methods to deep residual neural network (ResNet) [47] and deep dense convolutional network (DenseNet) [50].
expected rate of (d3)225-(c-1) We also obtain large-deviation
Acknowledgements
We would like to thank the area chair and three anonymous referees for constructive suggestions that improve the paper. This work is supported in part by the Mathematical Data Science program of the Office Naval Research under grant number N00014-18 18-1-7764 and by the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-2941
10

---

References
[1] A. Agarwal, O. Dekel, and L. Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In COLT, pages 28-40. PMLR, 2010. (Cited on pages and 5.)
[2] A. Agarwal, D. P. Foster, D. Hsu, S. M. Kakade, and A. Rakhlin. Stochastic convex optimization with bandit feedback. SIAM Journal on Optimization, 23(1):213
2013. (Cited on page 5.)
[3] Y. Arjevani, Y. Carmon, J. C. Duchi, J. information in non-convex stochastic optimization: Power and limitations. In COLT, pages 242-299, PMLR, 2020. (Cited page 1.)
J. Foster, A. Sekhari, and K. Sridharan. Second-order
[4] Y. Arjevani, Y. Carmon, C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pages 1-50, 2022. (Cited on page 1.)
[5] H. Attouch, J. Bolte, and B. F. Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Mathematical Programming. 137(():91-129) 2013. (Cited on page 3.)
[6] A. S. Bandeira, N. Boumal, and V. Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. In COLT, pages 361-382. PMLR, 2016. (Cited on page 1.)
[7] A. Beck and N. Hallak. On the convergence to stationary points of deterministic and randomized feasible descent directions methods. SIAM Journal on Optimization, (0(1))56-79, 2020. (Cited on page 17.)
[8] M. Benaïm, J. Hofbauer, and S. Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328- 2005. (Cited on page 17.)
[9] D. P. Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Journal of Optimization Theory and Applications, 12(2):218-22 23,33,,, 1973. (Cited on pages 17 and 19.)
[10] S. Bhojanapalli, B. Neyshabur, and N. Srebro. Global optimality of local search for low rank matrix recovery. In NeurlPS, pages 3880-3888, 2016. (Cited on page 1.)
[11] W. Bian, X. Chen, and Y. Ye. Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Mathematical Programming. 149(1):301-33)) 2015. (Cited on page 10.)
[12] Bolte and E. Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188(1):19551, 2021. (Cited on pages 2 and 17.)
[13] J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota. Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18(2):556-55) 572, 2007. (Cited on page 3.)
[14] J. Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd. First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal on Optimization, 28(3):211--2155 2018. (Cited page 17.)
[15] N. Boumal, V. Voroninski, and A. S. Bandeira. The non-convex Burer-Monteiro approach works on smooth semidefinite programs. In NeurlPS, pages 2765-2773, 2016. (Cited on page 1.)
[16] J. V. Burke, A. S. Lewis. and M. L. Overton. Approximating subdifferentials by random sampling of gradients. Mathematics of Operations Research, 27(3):567-5844 2002. (Cited on page 17.)
[17] V. Burke, A. S. Lewis, and M. Overton. Two numerical methods for optimizing matrix stability. Linear Algebra and its Applications, 351:117-1445 2002. (Cited on page 17.).

---

[18] J. V. Burke, A. S. Lewis, and M. L. Overton. A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM Journal on Optimization, 15(3):551-77, 2005. (Cited on page 17.)
[19] Burke, E. Curtis, A. Lewis, M. L. Overton, and I.. E. A. Simöes. Gradient sampling methods for nonsmooth optimization. Numerical Nonsmooth Optimization: State of the Art Algorithms, pages 201-225, 2020. (Cited on page 17.)
[20] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. "convex until proven guilty": Dimension- free acceleration of gradient descent on non-convex functions. In JCML, pages 654-663. PMLR, 2017. (Cited on page 1.)
[21] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):1751-177 2018. (Cited on page 1.)
[22] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points
I. Mathematical Programming, 184(1):71-120, 2020. (Cited on page 1.)
[23] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points
II: First-order methods, Mathematical P Programming. 185(1):315-355) 2021. (Cited on page 1.)
[24] X. Chen, S. Liu, K. Xu, X. Li, X. Lin, M. Hong, and D. Cox. ZO-AdaMM: zeroth-order adaptive momentum method for box optimization. In NeurlPS, pages 7204-7215 2019. (Cited page 2.)
[25] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multilayer networks. In AISTATS, pages 192-204. PMLR, 2015. (Cited on page 1.)
[26] H. Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990. (Cited on pages 2 and 3.)
[27] M. Coste. An Introduction o-Minimal Geometry. Istituti Editoriali E Poligrafici Internazionali Pisa, 2000. (Cited on page 3.)
[28] A. Daniilidis and D. Drusvyatskiy. Pathological subgradient dynamics. SIAM Journal on Optimization, 3022):1327-1338, 2020. (Cited on pages 2 and 17.)
[29] D. Davis and D. Drusvyatskiy. Stochastic mrodel-basedd minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207 239, 2019. (Cited on page 17.)
[30] D. Davis, D. Drusvyatskiy, Kakade, and D. Lee. Stochastic subgradient method converges on tame functions. Foundations of Computational Mathematics, pages 2, 3, and 17.)
2020. (Cited on
[31] D. Davis, D. Drusvyatskiy, Y. T. Lee, S. Padmanabhan, and G. Ye. A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions. In NeurIPS, page To appear, 2022. (Cited pages 2, 4, 6, 8, and 17.)
[32] M. C. Delfour. Introduction to Optimization and Hadamard Semidifferential Calculus. SIAM, 2019. (Cited page 3.)
[33] D. Drusvyatskiy and C. Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178(1):503-558, 2019. (Cited on page 17.)
[34] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7):21212159, 2011. (Cited on page 9.)
[35] C. Duchi and F. Ruan. Stochastic methods for composite and weakly convex optimization problems. SIAM Journal on Optimization, (8(4):3229-3259 2018. (Cited page 17.)
[36] C. Duchi, P. L.. Bartlett, and M. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012. (Cited pages 5 and 18.)
12

---

[37] J. C. Duchi, M. I. Jordan, M. J. Wainwright, and A. Wibisono. Optimal rates for zero-orde convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (1): 2806, 2015. (Cited on pages 2, 3,5, 6, and 8.)
[38] D. Duffie. Dynamic Asset Pricing Theory. Princeton University Press, 2010. (Cited on page 2.)
[39] A. D. Flaxman, A. T. Kalai, and H. B. McMahan. Online convex optimization in the bandit setting: Gradient descent without gradient. In SODA, pages 385-394, 2005. (Cited on pages and 5.)
[40] A. Fuduli, M. Gaudioso, and G. Giallombardo. Minimizing nonconvex nonsmooth functions via cutting planes and proximity control. SIAM Journal Opfimization, 14(3):743-756, 2004. (Cited on page 17.)
[41] R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping from saddle points-onling stochastic gradient for tensor decomposition. In COLT, pages 797-842. PMLR, 2015. (Cited on page 1.)
[42] R. Ge. J. D. Lee, and T. Ma. Matrix completion has no spurious local minimum. In NeurIPS, pages 2981-2989, 2016. (Cited page 1.)
[43] R. Ge, C. Jin, and Y. Zheng. No spurious local minima in nonconvex low rank problems: unified geometric analysis. In ICML. pages 1233-1242. PMLR, 2017. (Cited page 1.)
[44] S. Ghadimi and G. Lan. Stochastic first-and zeroth- methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(():2341-2366, 2013. (Cited pages 1, 3,5, 6, 7, 8, and 21.)
[45] S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59-99, 2016. (Cited on page 1.)
[46] A. Goldstein. Optimization of Lipschitz continuous functions. Mathematical Programming, 13 (1):14-22, 22, 1977. (Cited on pages 1, 3, 4, and 17.)
[47] K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016. (Cited on page 10.)
[48] L. J. Hong, B. Nelson, and Xu. Discrete optimization via simulation. In Handbook of Simulation Optimization, pages 9 44. Springer, 2015. (Cited on page 2.)
[49] Huang. S. Gao, Pei, and H. Huang. Accelerated zeroth-order and first-order momentum methods from mini to minimax optimization. Journal of Machine Learning Research, 23(36): 1-70, 2022. (Cited on page 2.)
[50] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. CVPR, pages 4700 4708, 2017. (Cited on page 10.)
[51] P. Jain and P. Kar. Non-convex optimization for machine learning. Foundations and Trends@ in Machine Learning, (133-4):12-333) 2017. (Cited on page 1.)
[52] K. Ji, Z. Wang, Y. Zhou, and Y. Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In ICML, pages 3100-3109. PMLR, 2019. (Cited on page 2.)
[53] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68 (2):1-29, 2021. (Cited on page 1.)
[54] A. Juditsky and A. Nemirovski. Large deviations of vector-valued martingales in 2-smooth normed spaces. ArXiv Preprint: 0809.08/3, 2008. (Cited on page 21.)
[55] D. Kingma and Ba. Adam: A method for stochastic optimization. ICLR, 2015. URL https: //tp:////////eeiiee//mmmo httppp///ppppeeeeeeeeeeefrrrrrrn http://oror/iiiidggiiii///..... (Cited on page 9.)
13

---

[56] K. C. Kiwiel. Restricted step and Levenberg-Marquarii techniques in proximal bundle methods
for nonconvex nondifferentiable optimization. SIAM Journal on Optimization, 6(1):227-249, 1996. (Cited on page 17.)
[57] K. C. Kiwiel. Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM Journal on Optimization, 18(2):379-38) 2007. (Cited page 17.)
[58] G. Kornowkki and O. Shamir. Oracle complexity in nonsmooth nonconvex optimization. In NeurlPS, pages 324-334, 2021. (Cited on pages 4 and 5.)
[59] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images, Technical Report O, University of Toronto, Toronto, Ontario, 2009. (Cited on page 26.)
[60] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. tradient-basee learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322, 1998. (Cited on page 9.)
[61] X. Lian, H. Zhang, C-J. Hsieh, Y. Huang, and J. Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order first-order. In NeurIPS, pages 3062-3070 2016. (Cited page 2.)
[62] S. Liu, B. Kailkhura, P-Y. Chen, P. Ting, S. Chang, and L. Amini Zeroth-order stochastic variance reduction for nonconvex optimization. In NeurlPS, pages 3731-3741, 2018. (Cited on page 2.)
[63] P-L. Loh and M. J. Wainwright. Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima. Journal of Machine Learning Research, 16:559 116699616,20 2015. (Cited on page 1.)
[64] C. Ma, K. Wang. Y. Chi, and Y. Chen. Implicit regularization in nonconvex statistical esti- mation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations of Computational Mathematics, 40(3):451-334 2020. (Cited on page 1.)
[65] S. Majewski, B. Miasojedow, and E. Moulines. Analysis of nonsmooth stochastic approximation: the differential inclusion approach. ArXiv Preprint: 1805.01916, 2018. (Cited on pages and 17.)
[66] S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira. Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality. In COLT, pages 1515, PMLR, 2017. (Cited on page 1.)
[67] K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):11--12,, 1987. (Cited on page 1.)
[68] B. L. Nelson. Optimization via simulation over discrete decision variables. In Risk and Optimization in an Uncertain World, pages 193-207. INFORMS, 2010. (Cited on page 2.)
[69] A. S. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization.
J. Wiley, 1983. (Cited on page 1.)
[70] Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Program- ming, 140(1): 2013. (Cited on page 1.)
[71] Y. Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018. (Cited on page 3.)
[72] Y. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions. Founda- tions of Computational Mathematics, 17(2):577-566, 2017. (Cited on pages 2, 3, 5, 6, and 7.)
[73] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, and L. Antiga. Pytorch: an imperative style, high -egh-pefforancc deep learning library. In NewrlPS, pages 8026-80337 2019. (Cited on page 9.)
[74] R. Rockafellar and J-B. Wets. Variational Analysis, volume 317. Springer Science Business Media, 2009. (Cited pages and 19.)
14

---

[75] O. Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(1):1703-1713, 2017. (Cited on pages 5, 6, 7, and 19.)
[76] A. Shapiro. On concepts of directional differentiabilltyy Journal of Optimization Theory and Applications, 66(3):477-44 1990. (Cited on page 3.)
[77] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1): 1929-1958, 2014. (Cited on page 9.)
[78] H. Stadtler. Supply chain management - an overview. Supply Chain Management and Advanced Planning, pages 9-36, 2008. (Cited on page 2.)
[79] Sun, Q Qu, and Wright. geometric analysis of phase retrieval. Foundations of Computa- tional Mathematics, 18(5): 131-1198, 2018. (Cited on page 1.)
[80] L. Tian, K. Zhou, and A. M-C. So. On the finite-time complexity and practical computation of approximate stationarity concepts of Lipschitz functions. ICML, pages 21360-21379. PMLR, 2022. (Cited pages 2, and 17.)
[81] M. J. Wainwright. High-Diin Dimensionnni Statistics: A Non-asymptotic Viewpoint, volume 48. Cambridge University Press, 2019. (Cited on pages 20 and 23.)
[82] G. Wang, G. B. Giannakis, and Y. C. Eldar. Solving systems of random quadratic equations via truncated amplitude flow. IEEE Transactions on Information Theory, 64(2):773-794, 2017. (Cited on page 1.)
[83] Y. Wang, S. Du, S. Balakrishhan, and A. Singh. Stochastic zeroth-order optimization in high dimensions. In AISTATS, pages 1356-1365, PMLR, 2018. (Cited on page 2.)
[84] Yousefian, A. Nedić, and U. V. Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56-6) 67, 2012. (Cited page 5.)
[85] Zhang, H. Lin, S. Jegelka, S. Sra, and A. Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In ICML, pages 11173-11 182. PMLR, 2020. (Cited on pages 2, 3, 10, and 17.)
15

---

Checklist
The code and the data are The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A]. You are strongly encouraged include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license the code and datasets? [No] proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
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]
(c) Did you discuss any potential negative societal impacts your work? [No] Our work does not have any potential negative societal impacts
(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 of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] You can find the complete proofs in the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We run the experiment the workstation with any advanced computing sources.
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "ksJioR-u1p", "reviewer": "Reviewer_VMXu", "summary": "This paper established a novel optimality criterion for non-smooth non-convex Lipschitz function called (δ,ε)-Goldstein stationary point and proposed a gradient-free algorithm with its stochastic version by deriving the Goldstein subdifferential and uniform smoothing technical. The last-iterate convergence analysis of the proposed methods was given, which guarantee the convergence to a (δ,ε)-Goldstein stationary point with high probability for both deterministic and stochastic version. State-of-art lower bounds of total oracle calls are given in terms of δ,ϵ and Λ for the proposed methods. Numerical experiments have shown the effectiveness of the proposed methods.", "questions": "Though the paper is theoretically sound, there are still some questions need to be discussed in this paper:\n\n1.\tThe authors proposed a class of subdifferential-based gradient-free algorithms. What is the advantage of the proposed algorithms compared to the gradient-based methods and zeroth-order methods?\n\n2.\tThe authors compared the performance of the proposed algorithms with different choice on MNIST, which is literally a small-scale and simple dataset. Why not use more larger datasets to verify the excellent performance of the proposed algorithm? In addition, the author's comparison algorithms are too few, which can be compared with some more advanced zeroth-order and gradient-free optimization algorithms like INGD[R1].\n[R1] J. Zhang, H. Lin, S. Jegelka, S. Sra, and A. Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In ICML, pages 11173–11182. PMLR, 2020.\n\n3.\tIt seems that the authors trained a quite simple convolutional neural network model on image classification task rather than some more modern and efficient models like [R2] and [R3] according to the experiment results, which is insufficient for validating the effectiveness of the proposed methods. \n[R2] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016\n\n[R3] G. Huang, Z. Liu, L. Van Der Maaten and K. Q. Weinberger, \"Densely Connected Convolutional Networks,\" 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017\n\n4.\tGrammar mistakes. Line 342, “We have proposed and analyzed a class of…” “have proposed and analyzed” should be replaced by “propose and analyze”.\n", "limitations": "The authors proposed a class of subdifferential-based gradient-free algorithms. What is the advantage of the proposed algorithms compared to the gradient-based methods and zeroth-order methods? The authors compared the performance of the proposed algorithms with different choice on MNIST, which is literally a small-scale and simple dataset. Why not use more larger datasets to verify the excellent performance of the proposed algorithm?\n\n\n\n----------after feedback---------------\n\nThe authors address my comments well, so I increased my score.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theoretical result in this paper is interesting.  The authors established a novel optimality criterion for non-smooth non-convex Lipschitz function called (δ,ε)-Goldstein stationary point and proposed a gradient-free algorithm with its stochastic version by deriving the Goldstein subdifferential and uniform smoothing technical. ", "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": "dguYxaTiyYu", "reviewer": "Reviewer_fAoD", "summary": "This paper studied the gradient-free (zeroth-order) methods for the nonsmooth nonconvex optimization problems, and provided the solid theoretical analysis for the proposed gradient-free methods. Notably, it established a useful relationship between the Goldstein subdifferential and uniform smoothing via appeal to the hyperplane separation theorem. Some experimental results demonstrate the effectiveness of the proposed methods. ", "questions": "Some comments:\n\n1)\tCould we further relax the Lipschitz continuous condition in the gradient-free methods for nonsmooth nonconvex optimization ?\n\n2)\tIn the convergence analysis (Theorem 3.2,3.4-3.6), do we need to choose some small parameter $\\delta$ that relies on $d$ and $ \\epsilon$, as in the existing zeroth-order methods for smooth optimzation? \n", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Novelty of this paper: Overall, it provides some solid theoretical results on gradient-free methods for the nonsmooth nonconvex optimization.\n\nWeakness of this paper: The Lipschitz continuous condition used in the paper may be not mild. \n", "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": "2aZjFJc-7v2", "reviewer": "Reviewer_xQvN", "summary": "This paper introduced two zero-order algorithms to compute the Goldstein stationary points for nonconvex nonsmooth problem. In contrast to the first-order case, the dependence on dimension is unavoidable for algorithms that only use function values. The authors show the gradient of a randomized smoothed function with a delta-ball is belong to the Goldstein delta-subdifferential, which forms the basis for the new gradient-free algorithms. They show the new algorithms compute a Goldstein stationary point in expectation within polynomial oracle complexity and the dimension dependence is only sqrt(d) worse than the convex/smooth case. They also proved a high-probability bound with a two-phase scheme.\n", "questions": "See main comments above.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As nonconvex nonsmooth problems are everywhere especially in the DL setting, new practical algorithm with finite time oracle complexity is important and desirable nowadays. This paper studies the computation of Goldstein approximate stationary point, which has exhibited attractive algorithmic consequence in recent years. The main contributions are two zero-order finite-time methods which are further built upon an interesting observation that the randomized smoothed function with a delta-ball is belong to the Goldstein delta-subdifferential. The paper is well-written and easy to follow. My comments are as follows:\n\n* Proposition 2.3 basically repeats [78, Lemma 8]. In the proof, it might miss a norm in L629 and L634.\n* The step size of Algorithm 1,2,3 seems dependent on the \\Delta, which is usually unknown in practice and is not necessary in the first-order setting for Lipschitz functions, e.g., in [79].\n* The following reference computing Goldstein stationary points concurrent partly to [30] might be relevant:\n\n[R] Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computation of approximate stationarity concepts of Lipschitz functions. ICML, 2022.\n\n* L45: \"Clark\" -> \"Clarke\"", "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