Oracle Complexity in Nonsmooth Nonconvex Optimization
Authors: Guy Kornowski
Ohad Shamir
Venue: NeurIPS 2021 Oral (2021)
Keywords: nonconvex nonsmooth optimization
optimization theory
oracle complexity
smoothing

Abstract: It is well-known that given a smooth, bounded-from-below, and possibly nonconvex function, standard gradient-based methods can find $\epsilon$-stationary points (with gradient norm less than $\epsilon$) in $\mathcal{O}(1/\epsilon^2)$ iterations. However, many important nonconvex optimization problems, such as those associated with training modern neural networks, are inherently not smooth, making these results inapplicable. In this paper, we study nonsmooth nonconvex optimization from an oracle complexity viewpoint, where the algorithm is assumed to be given access only to local information about the function at various points. We provide two main results (under mild assumptions): First, we consider the problem of getting \emph{near} $\epsilon$-stationary points. This is perhaps the most natural relaxation of \emph{finding} $\epsilon$-stationary points, which is impossible in the nonsmooth nonconvex case. We prove that this relaxed goal cannot be achieved efficiently, for any distance and $\epsilon$ smaller than some constants. Our second result deals with the possibility of tackling nonsmooth nonconvex optimization by reduction to smooth optimization: Namely, applying smooth optimization methods on a smooth approximation of the objective function. For this approach, we prove an inherent trade-off between oracle complexity and smoothness: On the one hand, smoothing a nonsmooth nonconvex function can be done very efficiently (e.g., by randomized smoothing), but with dimension-dependent factors in the smoothness parameter, which can strongly affect iteration complexity when plugging into standard smooth optimization methods. On the other hand, these dimension factors can be  eliminated with suitable smoothing methods, but only by making the oracle complexity of the smoothing process exponentially large.

Oracle Complexity in Nonsmooth Nonconvex Optimization
Guy Kornowski Weizmann Institute of Science guy. kornowskk @weizmann ac
Ohad Shamir
Weizmann Institute of Science ohad. shamir@xeizman ac i1
Abstract
It is well-known that given a smooth, bounded-from froombelow, and possibly non- convex function, standard gradient-based methods can find e-stationary points (with gradient norm less than e) in (1)c²²) iterations. However, many important nonconvex optimization problems, such those associated with training modern neural networks, are inherently not smooth, making these results inapplicable. this paper, study nonsmooth nonconvex optimization from an oracle complexity viewpoint, where the algorithm is assumed to be given access only to local informa- tion about the function at various points. We provide assumptions): First, we consider the problem of getting near c-stationary points. This is perhaps the most natural relaxation of finding e-stationary points, which is impossible in the nonsmooth nonconvex case. We prove that this relaxed goal cannot be achieved efficiently, for any distance and smaller than some constants. Our second result deals with the possibility of tackling nonsmooth nonconvex optimization by reduction to smooth optimization: Namely, applying smooth opti- mization methods on a smooth approximation of the objective function. For this approach, we prove an inherent trade-off between oracle complexity and smooth- ness: On the one hand, smoothing a nonsmooth nonconvex function can be done very efficiently (e.g., by randomized smoothing), but with dimension-dependenn factors in the smoothness parameter, which can strongly affect iteration complexity when plugging into standard smooth optimization methods. On the other hand, these dimension factors can be eliminated with suitable smoothing methods, but only by making the oracle complexity of the smoothing process exponentially large.
main results (under mild
Introduction
We consider optimization problems associated with functions / Rd - R, where f(-) is Lipschitz continuous and bounded from below, but otherwise satisfies no special structure, such as convexity. Clearly, in high dimensions, it is generally impossible to efficiently find global minimum of nonconvex function. However, if we relax our goal to finding (approximate) stationary points, then the nonconvexity is longer issue. In particular, is known that if f(-) is smooth namely, differentiable and with a Lipschitz continuous gradient then for any c >> O, simple gradient- based algorithms can find such that [x)] < using only (1)/²) gradient computations, independent of the dimension (see for example 60
Unfortunately, many optimization problems of interest are inherently not smooth. For example, when training modern neural networks, involving max operations and rectified linear units, the associated optimization problem is virtually always noncomvex well nonsmooth. Thus, the positive results above, which crucially rely on smoothness, are inapplicable. Although there are positive results even for nonconvex nonsmooth functions, they tend to be either purely asymptotic in nature (e.g..
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

depend on the internal structure and representation of the objective function, or require additional assumptions which many problems of interest do not satisfy, such as weak convexity
8 2 3G
16 26
or some separation between nonconvex and nonsmooth components (e.g.. [12 13
18
I0
15 17
This leads to the interesting question of developing black-box algorithms with con-asymptotic guarantees for nonsmooth nonconvex functions, without assuming any special structure.
In this paper, we study this question via the well-known framework of oracle complexity (27] Given a class of functions F. we associate with each f E F. an oracle, which for any x in the domain of f(),, returns local information about f()) at x (such as its value and gradien We consider iterative algorithms which can be described via an interaction with such an oracle: At every iteration t, the algorithm chooses an iterate Xt, and receives from the oracle local information about f(-) at XG, which is then used to choose the next iteration X This framework captures essentially all iterative algorithms for black-box optimization. In this framework, we fix some iteration budget T, and ask what properties can be guaranteed for the iterates xi....; Xy, as a function of 7 and uniformly over all functions JF (for example, how close to optimal they are, whether they contain an paaroximaaell-statinnaaa point, etc.). Unfortunately, as recently pointed out in 37 neither small optimization error nor small gradients can be obtained for nonsmooth nonconvex functions with such points can be easily "hidden" inside
docal-information algorithms: Indeed, approximately-stationen some arbitrarily small neighborhood, which cannot be found in a bounded number of iterations.
Instead, we consider here two alternative approaches to tackle nonsmooth nonconvex optimization, and provide new oracle complexity results for each. We note that Zhang et al. 377 recently proposed another promising approach, by defining a certain relaxation of approximate stationarity (so-called (8, )-stattionarity) ) and remarkably, prove that points satisfying this relaxed goal can be found via simple iterative algorithms with provable guarantees. However, there exist cases where their definition does not resemble a stationary point in any intuitive case, and thus remains to be seen whether is the most appropriate one. We further discuss the pros and cons of their approach in Appendix B
points, In our first contribution, we consider relaxing the goal of finding approximaeely-statione to that of finding near-approximately statiionary points: Namely, getting 8-close to point x with (generalized) gradient of norm at most e. This is arguably the most natural way to relax the goal of finding e-stationary points, while hopefully still getting meaningful algorithmic guarantees. Moreover, approaching stationary points is feasible in an asymptotic sense (see for instance (17). Unfortunately, we formally prove that this relaxation already sets the bar too high: For a very large class of gradient- algorithms (and in fact, all of them under a mild assumption), it is impossible point with worst-case finite-time guarantees, for small enough
to find aaa---pppoiimaely-stttooooo constant 6, e.
In our second contribution, we consider tackling nonsmooth nonconvex optimization by reduction to smooth optimization: Given the target function f()), we first find smooth function f(-) (with Lipschitz gradients) which uniformly approximates up to some arbitrarily small parameter e, and then apply a smooth optimization method on f(-). Such reductions are common in convex optimization (e.g., (I), and intuitively, should usually lead to points with meaningful properties with respect to the original function f-). at least when e is small enough. For example, it known that stationary points of f(-) are the limit of parooimmately-sattinnna points of appropriate smoothings of f()), as 6 - 32 Thm. 9.67].
This naturally leads to the question of how we can find a smooth approximation of a Lipschitz function f()). Inspecting existing approaches for smoothing nonconvex functions, we notice an interesting trade-off between computational efficiency and the smoothness of the approximating function: On the one hand, there exist optimization-based methods from the functional analysis literature (in particular, Lasry-Lyons regularization (251) which yield essentially optimal gradient Lipschitz parameters, but are not computationally efficient. On the other hand, there exist simple, computationally tractable methods (such as randomized smoothing [1) ). which unfortunately lead to much worse gradient I. Lipschitz parameters, with strong scaling in the input dimension. This in turn leads to larger iteration complexity, when plugging into standard smooth optimization methods. Is this kind of trf between computational efficiency and smoothness necessary? Considering
AA trivial example arising in deep learning, which does not satisfy most such structural assumptions, is the negative of the ReLU function, z + max(0, z). For non differentiable functions, we use standard generalization of gradients following 14. see Sec. details.
2 for

---

this question from an oracle complexity viewpoint, we prove that this orade-off is indeed necessary under mild assumptions: If we want smoothing method whose oracle complexity polynomial in the problem parameters, we must accept that the gradient Lipschitz, parameter may be no better than that obtained with randomized smoothing (up logarithmic factors). Thus, in a sense, randomized smoothing is an optimal nonconvex smoothing method among computationally efficient ones.
Overall, we hope that our work motivates additional research into black-box algorithms for nonconvex, nonsmooth optimization problems, with rigorous finite-time guarantees.
Our paper is structured follows. In Sec. 2 formally introduce the notations and terminology
that we use. In Sec. | we present our results for getting near approximately stationary points. In Sec. 4 present results for smoothing nonsmooth nonconvex functions. We conclude in Sec. with a discussion of open questions. The supplementary material contains, besides the full proofs, further discussion of the notion of (ő, e-sttationarity from 37 (Appendix B and proof that the diieenionnddeeedenncii arising from randomized smoothing provably affects the iteration complexity of vanilla gradient descent (Appendix C
Preliminaries
Notation. We let bold-face letters (e.g., x) denote vectors. 0 is the zero vector in Rd (where d is clear from context), and e2,.... are the standard basis vectors. Given vector x; denotes its i-th coordinate, and & denotes the normalized vector x/||x| (assuming x * 0). (, Il denote the standard Euclidean dot product and its induced norm over R& respectively. For any real number z, we denote [x]+ == max 0}. Given two functions f(-),g()) on the same domain X, we define || glloe = supxex (x) - (x)]. We denote by 8d-1 == {x E IRd ||*|| = the unit sphere. For any natural N, we abbreviate [N] == (I.....NY. We occasionally use standard big-O asymptotic notation, with O(), 0()). 2(-) hiding constants, ((.). 6(),,(()) hiding constants and logarithmic factors, and poly(.) meaning polynomial factors.
Gradients and generalized gradients. If a function f Rd + R is differentiable at x, we denote its gradient by fx). For possibly ein-differentiable functions, we let f denote the set of generalized gradients (following (14). which is perhaps the most standard extension of gradients to nonsmooth nonconvex functions. For Lipschitz functions (which are almost everywhere differentiable by Rademacher's theorem), one simple way to define it is
fx(x) = conv (u: u lim Vs(()), X + x}
K-000
(namely, the convex hull of all limit points of Vx(x)), over all sequences X1,X2,.. X.... of differentiable points of f(-) which converge to x). With this definition, a stationary point with respect to f()) is a point x satisfying 0 (x). Also, given some 0, we say that is an e-stationary point with respect to f()), if there is some u E (x such that ||u|| I e.
Oracles. In this paper, we consider two types of oracles:
A first-order oracle O (x), which given a function f(-) and a point x, returns fxx and @x)). We note that this differs somewhat from the standard formulation of first-order oracles in the literature, where it is assumed that at points of non-differentiabiiity. the oracle only returns some element in the generalized gradient set 0x(x). However, this means that our oracle complexity lower bounds hold under weaker assumptions, since we only provide more information to the algorithm. We use this type of oracle the results of Sec. S but discuss possible extensions in Remark 2
An all-derivatives oracle O7 (x), which returns fxx), 0x))., as well all higher-order derivatives of f(-) x, if they exist. This oracle provides more information than a first-order oracle, so any lower bound with respect to an all-derivatives oracle trivially applies with respect to a first-order oracle. Some our bounds apply with respect to such a powerful oracle, and we present them in setting, it remains to be seen
this generality, although we note that in the whether there any use for higher-order derivative information. We use this type of oracle in the results of Sec. !
3

---

3 Hardness of Getting Near Approximately-Stationary Points
In this section, we present our first main result, which establishes the hardness of getting near approximatel--stationnayy points.
To avoid trivialities, and following 3V will focus functions f(-) which are Lipschitz and bounded from below. In particular, we will assume that f(0) infx f(x is upper bounded by a 0 can be replaced by any other fixed
constant. We note that this is without loss of generality, reference point. Moreover, we will focus on two broad families of algorithms, which together span nearly all algorithms of interest: The first is the class of all deterministic algorithms (denoted as Adat), which are all oracle- based algorithms where X1 is chosen deterministically. and for all t > 1, x is some deterministic function of x₃ and the previously observed values and gradients. The second is the class of all zero-respecting algorithms (denoted as Agr), which are all deter- ministic or randomized oracle-based algorithms whose sequence of query points X1, X2,,..... satisfy support } S UKer support(0) (x:)) ) for all t, where support( MM (for some M C R²) is defined as E [d] Jy E M: : ys + 0}: Namely, the set of coordinates on which M has some elements with non-zero values. The notion of rero-respecting algorithms was introduced in [1 and generalizes the common notion of linear-span algorithms [1 where X is assumed to lie in the span of previous gradients. The class of zero-respecting algorithms includes nearly all algorithms of practical interest in our setting, including some which are not linear-span algorithms, such as coordinate descent methods (2)]. Our main result in this section is the following:
Theorem 1. There exist large enough absolute constant C >> O and small enough absolute constant e > O such that the following holds: For any algorithm in Adet U Agr interacting with first-order oracle, any T > 1, and any d 2 2T, there is a function f() on gd such that
f(-) is C-Lipschitz, and f(()- - infx f(x) S S.
With probability at least 1 T Texpp--pppeeee exp(-cd) over the algorithm's 's randomness (or deterministi- cally if the algorithm is deterministic). the iterates X1....,X; XT produced by the algorithm satisfy
infxes minke
||x+ x 2 c, where S is the set of c-stationary points of f(-).
The theorem implies that for a very large family of algorithms,, it is impossible to obtain worst- case guarantees for finding searr-pproximately--tataii functions unless T has exponential dependence on d.
points of Lipschitz, bounded- coaeeed--fro--eee from-below
Before continuing, we note that the result he extended any oracle-based algorithm (randomized or deterministic) under a
assumption see remark 5 in the proof for details.
Remark (More assumptions on f(.)). The Lipschitz,uncciioss functions f(-) used to prove the theorem are
based on a simple composition of affine functions, the Euclidean norm function x + ||x]|, and the max function. Thus, the result also holds for more specific families of functions considered in the function literature, which satisfy additional regularity properties, as long as they contain any Linschitzfunction composed as above (for example, Hadamard semi-differentibbl functions 37V,
functions 0 16V, semi-algebraic functions etc.).
The formal proof of the theorem appears Appendix A in the supplementary material, but can be informally described as follows: First, we construct a Lipschitz function on R. specified by a small vector w, which resembles the norm function x + ||x|| in "most" of IRd, but with "channel" leading away from neighborhood of the origin in the direction of w, and reaching a completely flat region (see Fig. D.. We emphasize that the graphical illustration a bit misleading due to the low dimension: In high dimensions, the "channel" and flat region contain a vanishingly small portion of Rdd This function has the property of having e-stationary points only in the flat region in the direction of w, even though the function appears in most places like the norm function + |xx| As result, any oracle- based algorithm that doesn't 't happen to hit the vanishingly small region where the function differs from x + |x||, receives no information about w, thus cannot determine where the e-stationary points lie. As a result, such an algorithm cannot return near near- seaa--pproiimmtll--stte statioona points.
Unfortunately, the construction described so far does not work as-is, since the algorithm can always query sufficiently close to the origin (closer than roughly ||w|)) where the gradients do provide information about w. To prevent this, we compose the function with an deppenem- affine mapping, which doesn't 't significantly change the function's properties, but ensures that the algorithm can never get too close to the (mapped) origin. We show that such an affine mapping must exist,

---

-15
Mesh and Contour plot of the function x + max (-1. and Ow (-) is defined in Lemma (as part of the proof of Thm. 1 The origin is marked with red dot. Best viewed in color.
Figure I:
f.. [x)] on IR, where w = (0.3,
based on standard oracle complexity results, which imply that oracle-based algorithms as above cannot get too close to the minimum of generic convex quadratic function with bounded number of queries. Using this mapping, and the useful property that w can be chosen arbitrarily small, leads to our theorem. The full proof details appear in Appendix in the supplementary material.
Remark (Extension higher-order algorithms). Our proof approach is quite flexible, in the sense that for any algorithm, we really only need some function which cannot be optimized to arbitrarily high accuracy, composed with "channel" construction as above. Since functions of this type also exist for algorithms employing higher-order derivatives beyond gradients (e.g., (2V), it is unlikely that such higher-order algorithms will circumvent our impossibility result.
4 Smoothing Nonsmooth Nonconvex Functions
In this section, we turn to our second main contribution, examining the possibility of reducing nonsmooth nonconvex optimization smooth nonconvex optimization, by running smooth opti- mization method on a smooth approximation of the objective function. In what follows, we focus discussion 1-Lipschitz functions: This without loss of generality, since if our objective is L-Lipschitz, we can simply rescale it by (and a Lipschitz assumption is always necessary if we wish obtain Lipschitz-gradieni smooth approximation). Also, focus smoothing functions over all of Id for simplicity, but our results and proofs easily extend to the case where we are only interested in smoothing over some bounded domain on which the function is Lipschitz.
For a nonsmooth convex function f()), a well-known smoothing approach is proximal smoothing (also known the Moreau envelope Moreau- Yosida regularization (5)) defined as Ps(f) where
1 Px(f) min (f()) + 28
lyy
x||
By picking 8 appropriately, Pf()) is arbitrarily good smooth approximation of f: More formally, 1-Lipschitz, then for any e >> 0, there exists a choice of 5 = +(c) such that [PPs()) S e, with the gradients of (f) being !-iiscchiz.. This is essentially optimal, attain a gradient Lipschitz parameter better than 2((1cc) (see Lemma 11 in Appendix F for a formal proof). Finally, computing gradients of (f( (which then be fed into bradient-based smooth optimization method) is feasible, given solution to Eq. ( which is a convex optimization problem and hence efficiently solvable in general.
e-approximation can
Unfortunately, for nonconvex functions, proximal smoothing (or other smoothing methods from convex optimization) generally fails in producing smooth approximations. However, it turns out that similar guarantees can be obtained with slightly more complicated procedure, known as Lasry-Lions regularization in the functional analysis literature 25 BI, which is essentially a double application of proximal smoothing combined with function flipping. One way to define it as follows:
(x)x) = - -P)() = max min (f(z) + 2v
z y
lly - x||
26
5

---

Once more, if is 1-Lipschitz, then choosing 6, = (c)) appropriately, we get an e-accurate approximation of f. with gradients which are S-Lipschitz for some absolute constant c. However, unlike the convex case, implementing this smoothing involves solving a non-convex optimization problem, which may not be computationally tractable.
Alternatively, a very simple smoothing approach, which works equally well on convex and non- convex problems, randomized smoothing, or equivalently, convolving the objective function with a smoothness-inducin density function. Formally, given the objective function f and a distribution P. we define f f(x) == Elfxlf( + y)]. In particular, letting P be uniform distribution on an origin-centered ball of radius e, the resulting function an e-approximation of f()). and its gradient
Lipschitz parameter is evá where с is an absolute constant and d is the input dimension [19] Moreover, given access to values and gradients of f-), computing unbiased stochastic estimates of the values or gradients of f() is computationally very easy: We just sample a single y ~ P. and returf] f(x + y) or ff(x + yy). These stochastic estimates can then be plugged into stochastic methods for smooth optimization (see 19 P10
Comparing these two approaches, we see an interesting potential trade-off between the smoothness obtained and computational efficiency, summarized in the following table:
V J Lipschitz param.
Computationally Efficient?
Randomized Smoothing
Vd/e
Lasry-Lions Regularization
c/E
X
In words, randomized smoothing is computationally efficient (unlike Lasry-Lyons regularization), but at the cost of a much larger gradient Lipschitz parameter. Since the iteration complexity of smooth optimization methods strongly depend on this Lipschitz parameter, it follows that in high- dimensional problems, we pay high price for computational tractability in reducing nonsmooth to smooth problems. We emphasize that this is a real phenomenon, and not just an artifact of iteration complexity analysis, as we demonstrate in Appendix C
This discussion leads to natural question: Is this trade-off necessary, or perhaps there exist compu- lationally efficient methods which can improve on randomized smoothing, in terms of the gradient Lipschitz parameter? Using an oracle complexity framework, we prove that this trade-off is indeed necessary (under mild assumptions), and that randomized smoothing is essentially an optimal method under the constraint of black-box access to the objective f(.,, and a reasonable oracle complexity. We note that Duchi et al. [I0 proved that the Lipschitz constant cannot be improved by simple randomized smoothing schemes, but here we consider a much larger class of possible methods.
4.1 Smoothing Algorithms
Before presenting our main result for this section, we need to carefully formalize what we mean by an efficient smoothing method, since "returning" a smooth approximating function over Rd is not algorithmically well-defined. Recalling the motivation to our problem, we want a method that given a nonsmooth objective function f(-), allows us estimate values and gradients of smooth approximation f(() at arbitrary points, which can then be fed into standard black-box methods for smooth optimization (hence, we need uniform approximation property). Moreover, for black-box optimization, it is desirable that this smoothing method operates in an oracle complexity framework, where it only requires local information about f()) at various points. Finally, we are interested in controlling various parameters of the smoothing procedure, such as the degree of approximation, the smoothness of the resulting function, and the complexity of the procedure. In light of these considerations, a natural way to formalize smoothing methods is the following:
Definition 1. An algorithm A is an (L, T, M,r -ssmohhherr for any filisschita,uucctioo f on Rd, there exists differentiable function ff on Rd with the following properties:
1. |lf fllo S e, and V f is L-Lipschitz.
Given any x E TRd,, the algorithm produces a (possibly randomized) query sequence XI,..., XT E {y ||y x|| r), of the form X,+1 A(t) (5,x, 07 .x.),...,0 O7p (xx)) where A1) maps
By Rademacher's theorem, f is differentiable almost everywhere hence v y) exists almost surely.

---

all the previous information gathered by the queries to a new query, possibly based on a draw of some random variable &. Finally, the algorithm produces a vector
x == ( (,, OJ (x.) 07 (xT))
where (ouu) is some mapping to RR, such that
Ee [x(A([x)]] -Vii--v(((l) se and Pr[lIA(f.)]] & =1
(2)
Some comments about this definition in order. First, the definition is only with respect the ability of the algorithm to approximate gradients of f()): It is quite possible that the algorithm also has additional output (such as an approximation of the value of f())) but this is not required for our results. Second, we do not require the algorithm to return (x(x): It enough that the expectation of the vector output is close to it (up to e). This formulation captures both deterministic optimization-type methods (such as Lasry-Lyons regularization, where general we can only hope to solve the auxiliary optimization problem up to some finite precision) as well as stochastic methods (such randomized smoothing, which returns fx( in expectation). Third, we assume that the queries returned by the algorithm lie at a bounded distance r from the input point x. In the context of randomized smoothing, this corresponds (for example) to using uniform distribution over ball of radius r centered on x. As we discuss later on, some assumption on the magnitude of the queries is necessary for proof technique. However, requiring almost-sure boundedness is merely for simplicity, and it can be replaced by a high- probbabbbyy bound with appropriate tail assumptions (e.g., if we are performing randomized smoothing with Gaussian distribution), at the cost of making the analysis a bit more complicated.
Remark 3. We are mostly interested in the following parameter regimes:
T poly (d, L, "),, essentially meaning that single call to A is computable in reasonable amount of time.
M = -poly (L). As we formally prove in Lemma 12 and also have L-Lipschitz gradients, we must have IVf (x) OLL). In particular, whenever M is sufficiently larger than L. Eq. 22 is interchangeable with the seemingly more natural condition Prg [[A(,,)) (x) M
in Appendix &
if we require f to approximate f
O If are interested in smoothing a 1-Lipschitz, nonconvex function up to c. &accuracy around a given point we generally expect that only its neighbboooo will convey useful information for the smoothing process. We note that this indeed satisfied by randomized smoothing (with uniform distribution around radius-e bull, with high probability if we use Gaussian distribution), as well as Lasry- regularization (in the sense that the smooth approximation at x does not change if we alter the function arbitrarily outside O(c) neighbooogo of x).
We consider all three of the above to be quite permissive. In particular, notice that randomized smoothing over a ball satisfies the much stronger T = 1, M 1, c.
Our result will require the assumption that the smoothing algorithm A is translation invariant with respect constant functions, in the sense that it treats all constant functions and regions of the input space in the same manner. In order to formalize this property, first notice that if f is a constant function then the all-derivatives oracle O (x) does not depend on Hence, for a constant function we the abbreviation O without specifying the specific input point. We use this to formalize our desired translation-invariate property as follows:
Definition 2. A smoothing algorithm A satisfies TICF (translation invariance w.r. constant func- [T], and any realization of
tions) for any two constant functions f.g, any x Rd and
( (g. x, 03
030) (1) (E, O, 0
000) +x,
(3)
and
A (out) (5, x, O 0 = (out) (5, 0, 0000000.. o 0
WWe assume nothing about e. allowing the algorithm utilize arbitrary amount of randomness.
7

---

In other words, if instead of a constant function f and an input point x, we pick some other constant function g and the origin, the distribution of the algorithm's sequence of queries remain the same (up to shift by -x), and the gradient estimate returned by the algorithm remains the same. We consider this to be mild and natural assumption, which is clearly satisfied by standard smoothing techniques.
4.2 Main result
With these definitions in hand, we are finally ready to present our main result for this section:
Theorem 2. Let A be an (L, e, T, M, (Mf,r)-smootlen -mooohher which satisfies TICF. Then there exist absolute constants C12 02 > such that
Vd (e2 -c)
I log 1)T++++))
(4)
This theorem holds for general values of the parameters L, T, M,r. Concretely, for parameter regimes of interest (see Remark B) we have the following corollary:
Corollary 1. Suppose that the accuracy parameter satisfies e S c2/2. Then any smoothing algorithm which makes at most T = poly(d, L, queries at distance at most = O(e) from the input point, and returns vectors of norm at most M = poly(d, d, L, E )), must correspond to a smooth approximation f(-) with Lipschitz gradient parameter at least I. = ((v))/))
We note that the lower bound on L in this corollary matches (up to logarithmic factors) the upper bound attained by randomized smoothing. This implies that at Icast under our framework and assumptions, randomized smoothing is an essentially optimal efficient smoothing method.
Another implication of Thm. 2 is that even if we relax our assumption that r Oc)), then as long as r does not scale with the dimension d, the gradient Lipschitz parameter of any efficient smoothing algorithm must scale with the dimension (even though there exist dimension-free smooth approximations, evidenced by Lasry-Lyons regularization):
Corollary 2. Fix any accuracy parameter S c2/2, and any r > 0. Then as long as the number of queries is T poly(d) and the output is of size M = poly(d), we must have I. 2 (2(V)).
A third corollary of our theorem is that (perhaps unsurprisingly), there is no way to implement Lasry-Lions regularization efficiently in oracle complexity framework:
Corollary 3. If S 02/2 and M = poly(d), then any smoothing algorithm for which f(:) corre- sponds to the Lasry-Lions regularization (which satisfies L O(1) must use a number of queries T = ex)()(
Remark 4 (Dependence on M). Our definition of smoothing algorithm focuses on the expectation of the algorithm's 's output. This leads to a logarithmic dependence on M (an upper bound on the algorithm's 's output) in Thm. g since in the proof we need to bound the infuence of exponentially- small-probute probability events on the expectation. It is plausible that the dependence on M can be eliminated altogether, by changing the definition a smoothing algorithm to focus on the expectation of its output, conditioned on all but highlyiimprobably events. However, that would complicate the definition and our proof.
We will now outline the proof idea, which is formally presented in Appendix A Consider a one dimensional monotonically increasing function g, which is locally constant at 9 /Vd neighbor- hood of grid A= = {0, (0.,,....,4 5x} } C [0, 1). with K roughly of order vd (see Fig. 2 in Appendix Ap We define f (x) = g(w x). where E Sá-1 is a uniformly random unit vector. We note that f is simple function, easily implemented by (say) a one-hidden layer ReLU neural network. We proceed to analyze what happens when a smoothing algorithm is given points of the form o,w, 8 E A. Since w is random, and the algorithm assumed be translation invariant, it can shown (via concentration of measure argument) that the algorithm is overwhelmingly likely to produce queries in directions which all have ( correlation with w, as long as the number of queries is polyno- mial. Consequently, with high probability, the queries all lie in region where the function f(.) is flat, and the algorithm cannot distinguish between it and a constant function. By the translation-invariane property, this implies that the gradient estimates V f (6, w) must be of small norm, uniformly for all

---

w. Combining the observation that vf(-) is small along order-of- ddmmany points between 0 and the unit vector w, together with the fact that f((- is L-Lipschitz, we can derive an upper bound on how much f()) can increase along the line segment between 0 and w, roughly on the order of L/ /d On the other hand, f() is an approximation of f. which has a constant increase between 0 and w. Overall this allows us to deduce a lower bound on L scaling as vd, which results in the theorem.
5 Discussion
In this paper, we studied the problem of nonconvex, nonsmooth optimization from an oracle complex- ity perspective, and provided two main results: One (in Sec. P is an impossibility result for efficiently getting near saaaiiiattelys-ttinaaaaa points, and the second (in Sec. proving an inherent trade-off off between oracle complexity and the smoothness parameter when smoothing nonsmooth functions. The second result also establishes the optimality of randomized smoothing as an efficient smoothing method, under mild assumptions.
Our work leaves open several questions. First, at a more technical level, there is the question of whether some or all of our assumptions can be relaxed. In particular, the result in Sec. currently holds for deterministic and zero-respecting algorithms. Although this is already a very broad class, one may ask whether it can be made to hold for all algorithms. We believe this is true, and (as we remark in Remark 5) will directly follow from a more general form of first-order oracle complexity bounds for quadratics. As for the smoothness result in Sec. T it currently requires the algorithm be translation invariant w.r.t. constant functions, as well as querying at some bounded distance from the input point x. We conjecture that the translation invariance assumption can be relaxed. possibly by a suitable reduction that shows that any smoothing algorithm can be converted to a translation invariant one. However, how to formally perform this remains unclear at the moment. As to the bounded distance of the queries, it is currently an essential assumption for our proof technique, which relies on a function which looks "locally" constant at many different points, but is globally non-constant, and this can generally be determined by querying far enough away from the input point (even along some random direction). Thus, relaxing this assumption may necessitate a different proof technique.
Another open question is whether randomized smoothing can be "derandomized": Our results indicate that the gradient Lipschitz parameter of the smooth approximation cannot be improved, but leave open the possibility of an efficient method returning the actual gradients of some smooth approximation contrast to randomized smoothing which only provides noisy stochastic
(up to machine precision), estimates of the gradient. These can then be plugged into smooth optimization methods which assume access to the exact gradients (rather than noisy stochastic estimates), generally improving the resulting iteration complexity. We note that naively computing the exact gradient of [(() arising from randomized smoothing is infeasible in general, as it involves a high-dimensional integral.
At more general level, our work leaves open the question of what the "right" metric to study for nonsmooth-nonconve optimization, where neither minimizing optimization error nor finding approximately-stationne points is feasible. In this paper, we show that the goal of getting near approximately stationary points is not feasible, at least in the worst case, whereas smoothing can be done efficiently, but not in a dimension-fre One very appealing notion is the (6, c)-stationarity of [77 that we mentioned in the introduction, which comes with clean, finite-time and dimension- free guarantees. Our negative result in Thm. [ provides further motivation to consider it, by showing that a natural variation of this notion will not work. However, as we discuss in Appendix B in the supplementary material, we need to accept that this stationarity notion can have unexpected behavior, and there exist cases where it will not resemble a stationary point in any intuitive sense. In any case, using an oracle complcxity framework to study this and other potential metrics for nonsmooth nonconvex optimization, which combine computational efficiency and finite-time guarantees, remains an interesting direction for future research.
manner. Can we find other compelling goals to consider?
Broader impact. In this work we discuss several approaches for providing formal guarantees when optimizing nonsmooth nonconvex functions, and shed light on their inherent limitations and trade- offs in an oracle complexity framework. Such optimization objectives arise when training modern deep neural networks, a practice which is currently subject to many heuristics. We believe better theoretical understanding of the field will eventually affect practice and help develop sound deep learning based technology. We find it difficult to provide more specific potential negative societal impact, other than the well known potential negative implications of such technology as a whole.

---

Funding disclosure. This research is supported by the European Research Council (ERC) grant 754705.
References
[1] Zeyuan Allen-Zhu and Elad Hazan. Optimal black-box reductions between optimization objectives. arXiv preprint arXiv:1603.05642, 2016.
[2] Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programminng, 178(1-2):327-360) 2019.
[3] Hédy Attouch and Dominique Aze. Approximation and regularization of arbitrary functions in hilbert spaces by the lasry-lions method. Annales de I'Institut Henri Poincare (C) Non Linear Analysis, 10(3):289-312 1993.
[4] Keith Ball et al. An elementary introduction to modern convex geometry. Flavors of geomelry, 31:1-58, 1997.
[5] Heinz H Bauschke, Patrick Combettes, et al. Corvex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
[6] Amir Beck and Nadav Hallak. On the convergence to stationary points of deterministic and randomized feasible descent directions methods. SIAM Journal on Optimization, 30(1):56-79, 2020.
[7] Amir Beck and Marc Teboulle. Smoothing and first order methods: A unified framework. SIAM Journal on Optimization, 22(2):557-580 2012.
[8] Michel Benaīm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328 348, 2005.
[9] Jérôme Bolte. Aris Daniilidis, Adrian Lewis, and Masahiro Shiota. Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18(2):556 572, 2007.
[10] Jérôme Bolte, Shoham Sabach, Mare Teboulle. and Yakov Vaisbourd. First order methods be- yond convexity and lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal on Optimization, 28(3):21112215) 2018.
[11] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, pages 1-50, 2019.
[12] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the evaluation complexity of composite function minimization with applications nonconvex nonlinear programming. SIAM Journal on Optimization, 21(4):122111739 2011.
[13] Xiaojun Chen. Smoothing methods for nonsmooth, nonconvex minimization. Mathematical programming, 134(1):71-99, 2012.
[14] Frank H Clarke. Optimization and nonsmooth analysis, volume 5. Siam, 1990.
[15] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-233) 2019.
[16] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, pages 1-36. 2018.
[17] Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions convex functions and smooth maps. Mathematical Programming, 178(1-2):503-55 558, 2019.
[18] John C Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimization problems. SIAM Journal on Optimization, 28(4):322933259, 2018.
[19] John Duchi, Peter Bartlett, and Martin Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 2212))674-701
10

---

[20] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2344):2341-2368, 2013.
[21] AA Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13 (1):14-22, 1977.
[22] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning- Voluue 70, pages 1724 1724-1732. JMLR. org, 2017.
[23] Krzysztof C Kiwiel. Convergence the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM Journal on Optimization, 18(2):379-388 2007.
[24] Guanghui Lan and Yi Zhou. An optimal randomized incremental gradient method. Mathematical programming, 171(1-2):167-215, 2018.
[25] Jean-Michel Lasry and Pierre-Louis Lions. A remark on regularization hilbert spaces. Israel Journal of Mathematics, 55(3):257-266, 1986.
[26] Szymon Majewski, Btažej Miasojedow, and Eric Moulines. Analysis of nonsmooth stochastic approximation: the differential inclusion approach. arXiv preprint 1805.0180, 2018.
[27] Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency optimization. Wiley, 1983.
[28] Yurii Nesterov. Smooth minimization of non-smooth functions. Mathematical programming. 103(1):127-152, 2005.
[29] Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341 1-362, 2012.
[30] Yurii Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, (88):10-11, 2012.
[31] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[32] R. Tyrrell Rockafellar and Roger J.B. Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
[33] Max Simchowitz. On the randomized complexity of minimizing a convex quadratic function. arXiv preprint a 2018
[34] Tomasz Tkocz. An upper bound for spherical caps. The American Mathematical Monthly, 119 (Tx:06-607, 2012.
[35] Blake Woodworth and Nathan Srebro. Lower bound for randomized first order convex opti- mization. arXiv preprint urXiv:1709.0359) 2017.
[36] Chao Zhang and Xiaojun Chen. Smoothing projected gradient method and its application to stochastic linear complementarity problems. SIAM Journal on Optimization, 20(2):627-649, 2009.
[37] Jingzhao Zhang, Hongzhou Lin, Suvrit Sra, and Ali Jadbabaie. On complexity of finding stationary points of nonsmooth nonconvex functions. arXiv preprint 24311,00000000 2020.


Reviews:
[{"review_id": "s8c-c1WvzIK", "reviewer": "Reviewer_KNSx", "summary": "This paper investigates the question of finding near $\\epsilon$-stationary points for \nLipschitz nonconvex functions. This is a quite challenging question, and the paper addresses it with the following advances:\n\n1. An oracle lower bound for the task of finding near $\\epsilon$-stationary points. This is achieved by an intrincate construction that resembles the trick of hiding a cone in a random direction. This result is restricted to deterministic and zero-respecting algorithms.\n\n2. The second contribution is the study of smoothings from an oracle perspective. It is shown in particular that in this oracle model, the Lipschitz gradient bounds obtained by randomized smoothing are essentially optimal, which rules out e.g. efficient implementations of the Lasry-Lions regularization. BTW, I wonder if Corollary 3 readily implies that computing saddle points has exponential oracle complexity with respect to the dimension (these type of results are already known, but this would be a more transparent proof, I believe).\n\n3. A less emphasized third contribution is the observation that the relaxation used in Zhang et al. 2020 (based on the convex hull of a union of subdifferentials around the point) does not lead to anything resembling a nearly stationary point.\n", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper is a great addition to the understanding of nonconvex optimization. It provides\na reasonably sized proof that finding nearly $\\epsilon$-stationary points is difficult, it provides a nice model to argue about smoothings algorithmically, and touches upon other works addressing similar questions. This material is clearly relevant for the NeurIPS community.\n\nIn terms of the cons, it is a problem the fact that the oracle lower bound for nearly $\\epsilon$-stationary points is restricted to deterministic zero-respecting algorithms, though I share the authors view that this might be an artifact of the current analysis, and it could be resolved in follow up work. On a related note, regarding remark 5: could you use a black box function which enjoys the property of Them 3 without being a quadratic (e.g., the one in Woodworth and Srebro)? Perhaps this is an easier way to extend the applicability of the result without having to deal with the lower bound for general algorithms on quadratics, which is known to be difficult. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "X7k4aNQi6eY", "reviewer": "Reviewer_Hx4f", "summary": "The authors consider the problem of nonsmooth nonconvex optimization through an oracle complexity perspective.\n\nThe authors propose a precise mathematical statement of the idea that there is no complexity estimate for nonsmooth nonconvex optimization based on first order oracles. This is the first contribution presented in the manuscript. The convergence criterion is a quantitative version of the property of \"being close to an almost critical point\". The authors show that obtaining such an approximate critical point is not possible in a dimension independant finite time, in general. \n\nAs a second contribution, the authors consider the possibility to use smoothing techniques for nonsmooth nonconvex optimization. For a smoothed objective, usual optimality criteria, such as small gradient norm, can be used. Yet classical first order methods come with complexity estimates which depend on the Lipschitz constant of the gradient of the objective. It is a known fact that randomized smoothing (formally, convolution with a density) allows to obtain Lischitz constants which have a square root dependency in the dimension. The authors show that this is actually tight in the sense that a large class of computationally implementable local smoothers need to account for such a dimension dependency.\n\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The proposed analysis is well presented and correct up to my understanding. I found the manuscript very clear and well written, the arguments and proofs are carefully detailed and the written material is of very high quality. The questions adressed by this paper are timely and the proposed answers are very satisfactory. I believe that this is of relevance to the machine learning community for which nonsmooth nonconvex optimization are central.\n\n\n- About semi-algebraicity (and regularity).\nThe proposed counter-examples are actually semi-algebraic. The oracle complexity perspective is usually presented in a convex optimization context, which enforces a lot of structure. In the nonconvex world, there is a very large gap between general Lipschitz functions and more structured functions (such as semi-algebraic). I believe that it is worth emphasizing that the proposed counter examples are semi-algebraic. This is stronger than most classes cited in Remark 1 as Lipschitz semi-algebraic functions are both Hadamard semi-differentiable and Whitney stratifiable.\n\nThe main mechanism used in [15] for \"stratifiable functions\" is a projection formula which was introduced by the following reference, which is worth citing:\nBolte, J., Daniilidis, A., Lewis, A., & Shiota, M. (2007). Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18(2), 556-572.\n\nI do not believe that the reference to regular functions in Remark 1 is appropriate. Regularity means that all non-smoothness are qualitatively similar to convex like nonsmoothness. For example the function t -> -max(0,t) is not regular. I am not sure that the constructed counter examples are regular.\n\n- Relation between smoothing and near-approximately-stationary. \nIt would be interesting to have a more detailed discussion of the relation between the two contributions. Although it is not explicitely stated, it is implicit in the second contribution that the overall goal is to find a near critical point of a smoothed version of the objective. The authors prove that this goal cannot be achieved in a dimension independant way. However, I think that being a near critical point of a smoothed version of the objective may suffer from the same drawback as described in appendix B: creation of spurious critical points which are far from any \"real\" critical point. At least for local averaging, I strongly believe that a similar phenomenon as in appendix B could be described: smoothing creates an artificial critical point in an area where the original function has none. Since the targets of the two contributions is overall different, it would be interesting to emphasize and discuss these differences between near criticalilty for a smoothed objective and the proposed near-approximate-stationarity.\n\n\n- Relevance of qualitative / assymptotic results.\nThe manuscript starts by emphasizing limitation of qualitative results which are of purely asymptotic nature. The authors then proceed to show that the proposed notion of near-approximate-stationarity is not accessible in a dimension independent way and conclude that one should resort to more relaxed notions of approximate criticality (possibly producing spurious unexpected artifacts). \n\nI think that in addition it should be explicitely stated and emphasized that the asymptotic analysis, presented in [8,15] for example, do prove that near-approximately-stationary points will be reached in finite time (without explicit estimates). The authors show that this goal is out of reach if we impose this finite time not to depend on the dimension of the problem or a specific initialisation. To me these highlight the relevance of asymptotic / qualitative results in this context as the author essentially show that there is no dimension independent quantitative counterpart. Such results remain the only available way to prove that even the simplest subgradient method has a minimizing behavior and is attracted by critical points in nonsmooth nonconvex optimization.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "Vdphw4GlL3N", "reviewer": "Reviewer_nyBG", "summary": "### Update\n\nI'd like to thank the authors for their response. \n\nI have decided to increase my score to 9 in light of the other reviews and these comments. I look forward to seeing this work published.\n\n========\n\nThis submission investigates two problems central to non-smooth, non-convex optimization: i) the oracle complexity of computing approximately stationary points and ii) the complexity of smoothing non-convex functions. \nTo tackle the first problem, the authors propose a new concept of _near approximately-stationary_ points, which the set of points within $\\delta$ (in some metric) of an $\\epsilon$ stationary point.\nThis differs from previous work [35], which classified $(\\epsilon, \\delta)$-stationarity as $\\epsilon$-stationarity of a convex combination of (generalized) gradients in a local neighbourhood of size $\\delta$. \nThe authors prove that, unlike for $(\\epsilon, \\delta)$-stationarity, finding near approximately-stationary points is impossible in finite time for the classes of deterministic and randomized, zero-respecting algorithms under standard assumptions and for sufficiently small $\\epsilon, \\delta$. \nFor the second problem, the submission formalizes trade-offs between the degree of smoothness in the smooth approximation, as measured in the Lipschitz modulus of the gradient, and the computational complexity of the smoothing operation.\nIn particular, it is shown that for every smoothing algorithm which has polynomial running-time in the problem parameters, there exists a function for which the modulus of the smoothed function is $\\tilde O(\\sqrt{d})$. \nAs a consequence, randomized smoothing by convolution with a Gaussian or uniform distribution is seen to obtain the optimal dimension dependence out of polynomial-time smoothing procedures.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "# Detailed Comments\n\nThis work is a good submission with two significant theoretical contributions.\n\nComputing stationary points of non-smooth, non-convex functions is a central task in current machine learning practice due to the ubiquity of deep neural networks with ReLU activations. \nThe strong impossibility result for finding such finding critical points that the authors present is both novel and of practical importance to optimizers in the NeurIPS community.\n\nThe theory on smoothing operators for non-smooth, non-convex functions is also interesting, but less immediately attractive in the context of neural networks; \nsmooth activation functions can always be used to obtain differentiable, if not Lipschitz smooth, networks and I am not aware of an alternative class of non-convex, non-smooth problems where smoothing is an attractive idea. \nWith that said, the result is new and it has interesting consequences for the optimality of different smoothing operators, as the authors point out.\n\nThe major weakness of the submission is the limited connection between the two theoretical results. \nThe two major theorems are largely related by their shared setting in non-convex, non-smooth optimization and at times the paper reads like two separate submissions. \nIndeed, I feel that both results might work better and command more interest if further developed in separate works: one devoted to finding stationary points and one devoted to smoothing procedures.\n\nFor example, an interesting questing arising from the first result is the following: \nwhat kind of reasonable guarantees can be expected for subgradient methods in the non-convex setting? \nThis question is especially interesting since the authors show that $(\\epsilon, \\delta)$-stationarity is unsuitable.\n\n## Writing\n\nThe writing in the main paper is very polished.\nHowever, I found the proof of Theorem 2 in Appendix A.2 quite difficult to follow.\nPerhaps this section and section A.1 could be improved by the inclusion of a \"roadmap\" outlining of the argument.\n\nI think Figure 1 is excellent and really contributes to an intuitive understanding of the construction for Theorem 1.\n\n\n## Theory \n\nI checked the proofs, which appear to be correct. I have several small comments/questions.\n\n- Line 708 (18): How can Lemma 11 be applied here to control the value of $L$? So far we have made no assumptions on the form of $f$, while Lemma 11 assumes $f(\\mathbf{x}) = L_0 |x_1|$.\nThe conclusion derived from Lemma 11, namely,\n$$\n\\sqrt{\\log((M + 1))\\log((T + 1))} \\leq \\frac{\\sqrt{d}}{32r}\n$$\nis necessary for $\\Delta$ to be a grid on the unit interval.\nCan the authors please clarify this issue?\n\n- Display after line 908 (page 28): Shouldn't it be $q^{2i}$, rather than $q^i$? The subsequent bound still holds, of course.\n\n- Line 652 (page 16): Shouldn't this be \"between $\\|x - x^* \\|$ and $\\frac{1}{\\sqrt{2}}\\|x - x^*\\|$\"? Well, I suppose that this is a slightly tighter bound and the bound $\\lambda_{\\text{min}}(M^{1/2}) > 1 / 2$ also holds.\n\n- Footnote 7 (page 17): Should the last line read \"In particular, this bad event will occur with probability larger than $T \\exp\\{-d/18\\}$ for some realization of the \\*\\*algorithm's randomness\\*\\*\"?\n    Otherwise I do not see how the desired contradiction arises.\n\n- Eq. 10 (page 18): I believe the left-hand side of the equation is missing a factor of $2$.\n\n## Experiments\n\nN/A\n\n## Questions for the Authors\n\n- The set of \"zero-respecting\" algorithms does not include many simple and interesting randomized algorithms. \nFor example:\n i) choose a random point $z \\in \\mathbb{R}^d$,\n\n ii) take $x_k^* =$ argmin  $\\{ f(y) : y \\in \\{ z, x_k } \\} $,\n\n iii) set \n$x_{k+1} = x_k^+ - \\eta_k \\nabla f(x_k^+)$.\n\n\nI really don't see what value the zero-respecting assumption has has over the classical \"remains in the span of the gradients\" assumption aside from being technically weaker. \nCan the authors suggest an interesting algorithm which falls in one class but not the other?\n\n- The impossibility result for finding stationary points relies on a dimension-dependent argument where $d \\geq 2 T$ is necessary.\nDo the authors think that a dimension-independent impossibility result is feasible? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. This is a theoretical paper with no forseeable societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "Hu1D-bXFdf", "reviewer": "Reviewer_SE7Y", "summary": "This is a theoretical paper on the oracle complexity of nonconvex and nonsmooth optimization problem. The paper mainly consists of two results: one is a negative result showing that it is impossible to get a near-approximately stationary points with worst-case finite-time guarantees for a large class of optimization algorithms; the other one is a positive result showing the trade-off between the computational efficiency and smoothness of the approximation scheme indeed exists.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Although the literature on nonconvex and nonsmooth optimization problem is overwhelming in recent years, I felt the current manuscript adds value to this crowded line of research. In particular, it demonstrates the difficulty for getting an approximate stationary point in the simultaneous presence of the nonconvexity and nonsmoothness from the complexity perspective. The paper is written clearly and very easy to follow. In particular, the constructive proof of Theorem 1 is nice and generalizable. \n\nOne major question that I have for this paper is on the definition of a near-approximately stationary solutions. My feeling is that the epsilon-stationary point is not defined very well here. Consider the example that f(x) = \\|x\\|_1. Obviously x=0 is the only stationary point. However, if one defines the epsilon-approximate stationary point as the existence of u\\in \\partial f(x) such that \\|u\\| \\leq epsilon, then this set of approximate stationary solutions is still a singleton \\{x=0\\}, as long as epsilon <1. This means that even for such a simple convex function, the ``approximate'' solution may be as strong as an exact stationary solution, which is of course not desirable. In fact, the definition of approximate stationary solutions in this work is equivalent to \\{x : distance(0, \\partial f(x)) \\leq epsilon\\}. Since \\partial f is a set-valued mapping that is potentially discontinuous due to the nonsmoothness of f, this definition is not robust and the above mentioned issue is likely to happen. Perhaps a more relaxed definition of approximate solution may lead to a better worst case result.\n\nAnother question is on the assumption of the global Lipschitz continuity of the function f. This assumption is quite strong and in particularly excludes the deep neural network problems with more than one layer. However, Rademacher's theorem only requires the local Lipschitz continuity of the function. This means both the definition of (approximate) stationarity and the randomized smoothing algorithm can be applied directly with the much weaker local Lipschitz continuity. Can the authors explain the necessity to assume the global Lipschitz continuity throughout the paper?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a purely theoretical paper on the complexity of numerical algorithms. I felt this work does not have negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3qlntVUbTFy", "reviewer": "Reviewer_vcVQ", "summary": "This paper presented strong technical results for nonsmooth nonconvex problems. The main lower bound is counter-intuitive; the argument for random smoothing is deep. Meanwhile, the main body gives a very good illustration of the hard technical content. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "I like this paper as I learned a lot about nonsmooth nonconvex optimization from it. Many contents are new for me such as generalized gradients and Lasry-Lions Regularization, but the writing makes them accessible. The content about random smoothing is surprising but reasonable. \n\nSome minor comments are that I do not find the exact $(\\delta, \\epsilon)$ Near Approximately-Stationary Points. Maybe it is just because the notation is changed in Theorem 1. \n\nSome open question is that despite the theoretical meaning, are there any implications of this work for practical problems? It seems that most of the problems we encounter are structured. Even for deep neural networks, we can still consider smoothing ReLu by smoothing nonlinearity. I think that such a strong lower bound may be not application for most of the nonsmooth nonconvex problems we need to solve. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No Societal Impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides  oracle complexity of nonconvex and nonsmooth optimization problem. The paper provides useful and interesting results about the complexity of getting a near-approximated stationary points, and the techniques and results are new to the literature. 

Overall the paper is very well-written, easy to follow, but the results are substantial. I recommend acceptance of this paper at least as a spotlight paper. 
Decision: Accept (Oral)