Funding: This work was supported by the National Science Foundation [Grant DMS-2006990].
]]>We consider the problem of minimizing a Lipschitz objective function f : R n ! R. We suppose that we are given a Lipschitz constant, an initial point x 0 2 R n , and an upper bound on the gap f (x 0 ) inf f . We have access to f at input points x 2 R n through an oracle that outputs only local information, such as the function value f(x) and a subgradient in @f (x). It is easy to see that the problem of approximating the minimum value inf f within a given tolerance ✏ > 0 suffers from the curse of dimensionality; it requires what amounts to grid search, needing a number of oracle calls growing like O 1 ✏ n ⇥ , so depending exponentially on the dimension n.
Relaxing our goals, rather than minimization, we may instead seek points that are, in some sense, nearly critical. A well-known example is the case of a smooth but nonconvex objective function f : R n ! R, for which finding a point x 2 R n satisfying |rf (x) | ✏ is relatively easy. Assuming that f is bounded below and L-smooth, meaning that its gradient has a known Lipschitz constant L, elementary calculus shows that the gradient descent iteration x
x 1 L rf (x) always reduces the objective value f(x) by at least 1 2L |rf (x) | 2 . Assuming a bound M on the gap between the initial objective value and inf f , the algorithm succeeds after no more than 2LM ✏ 2 iterations, independent of the dimension n.
Less well known is an interesting analogous result for objectives f that are nonsmooth but convex; Davis and Drusvyatskiy [4] present a randomized algorithm that finds a point within a distance ✏ of some point at which f has a subgradient with norm no larger than ✏ using Õ 1 ✏ 2 ⇥ subgradient evaluations. The Õ(•) notation suppresses logarithmic factors, but again, the complexity estimate is dimension independent. When f is just weakly convex, meaning that the function f + ρ 2 | • | 2 is convex for some constant ρ > 0, the analogous algorithm (see Davis and Drusvyatskiy [5]) still has a dimension-independent complexity bound, now of the form O 1
For general Lipschitz functions f, however, the analogous problem is intractable (see Kornowski and Shamir [15]). More precisely, any algorithm guaranteed to approximate within a distance ✏ a point with a Clarke subgradient of norm less than ✏ must suffer from the same curse of dimensionality as grid search, requiring a number of subgradients growing like O 1
Although that intractability might seem the end of the question, there is a more relaxed proxy approach to minimizing Lipschitz functions, dating back to work of Goldstein [10] in the 1970s. This method can be viewed as seeking a point in R n around which f is differentiable on some cluster of nearby points at which the gradients have a small convex combination-a small "Goldstein subgradient" in the language of Goldstein [10]. Although some published algorithms, such as that of Mahdavi-Amiri and Yousefpour [16], accomplished this goal, no complexity analysis existed until recently.
A 2020 breakthrough of Zhang et al. [24] presented an algorithm for this Goldstein subgradient problem with a complexity analysis depending on the radius δ of the cluster and the size ✏ of the subgradient but independent of the dimension n. The algorithm assumes directional differentiability of the objective f and relying on an associated directional subgradient oracle, uses an innovative randomized line search to achieve an efficiency guarantee of essentially O(✏ 3 δ 1 ). The development of Zhang et al. [24] may have practical as well as theoretical interest. The basic algorithm in Zhang et al. [24] employs "null" steps, rather like the traditional bundle methods that have long enjoyed considerable success in large-scale convex optimization (see Sagastizábal [21]). The practicality of the basic algorithm of Zhang et al. [24] remains unclear, but a related algorithm performs at least comparably with stochastic gradient descent in the authors' preliminary experiments. Two subsequent papers, Davis et al. [6] and Tian and So [22], point out that small random perturbations allow a standard subgradient oracle to replace the directional version of Zhang et al. [24].
Two recent developments, Jordan et al. [13] and Kornowski and Shamir [15] (see also Jordan et al. [14] 1 ), raise the question of deterministic algorithms for this problem. Although both papers prove positive results in the smooth case and Jordan et al. [14] thereby develop a "white-box" deterministic smoothing approach to the nonsmooth problem, both manuscripts also prove negative results for the general dimension-independent question. However, the negative results of Jordan et al. [13] and Kornowski and Shamir [15] concern general Lipschitz optimization. In contrast, by modestly restricting the class of nonsmooth objectives, we are able to develop a simple deterministic black-box version of the algorithm of Zhang et al. [24] with increased but still dimensionindependent complexity. Specifically, our contribution is an algorithm that achieves, up to a nonconvexity modulus for the objective, a dimension-independent complexity of O(✏ 4 δ 1 ), thus derandomizing the method of Zhang et al. [24] at the expense of an extra order of ✏. When δ à ✏, we arrive at the estimates noted in the abstract: O(✏ 4 ) for the original method of Zhang et al. [24] and O(✏ 5 ) for our deterministic modification (which strengthens to O(✏ 4 ) in the weakly convex case). A higher level of nonconvexity corresponds to a larger nonconvexity modulus and hence, to a larger complexity bound; in this sense, the modulus measures a complexity "cost" for finding nearly critical points of nonconvex functions. Our analysis covers interesting objectives, such as piecewise linear functions, which are not even weakly convex. We relate the nonconvexity modulus of the objective with its distributional second derivative, hinting at an intriguing relationship between such derivatives and algorithmic complexity in general optimization.
Primarily to emphasize the elementary nature of our development, we adopt a rudimentary setting for our optimization problem. On a real inner product space X with corresponding norm | • |, we consider the problem of minimizing a function f : X ! R. The objective f may be neither smooth nor convex, and the space X may be neither finite dimensional nor even complete. The method we develop, following Zhang et al. [24], relies on an the following underlying idea. Definition 1. We say that an objective function f : X ! R has a directional subgradient map G : X 2 ! X when for all points x 2 X and directions e 2 X, the Gâteaux directional derivative
exists and satisfies hG(x, e), ei à f 0 (x; e):
We say that G is L-bounded for some constant L > 0 if its norm |G(x, e)| is never larger than L.
In applications, the objective function f is L-Lipschitz, and the vector G(x, e) is a subgradient of some kind for f at the point x associated with the direction e; therefore, we loosely refer to G(x, e) as a "subgradient." Nonetheless, we choose this rudimentary setting to emphasize again the elementary nature of our development, which makes no recourse to variational or Lipschitz analysis.
Example 1 (Differentiable Functions). For any function f that is L-Lipschitz and has a Gâteaux derivative rf (x) at every point x 2 X, the equation
defines an L-bounded directional subgradient map.
Example 2 (Convex Functions). For an L-Lipschitz convex function f with convex subdifferential @f , any map G satisfying G(x, e) 2 argmax{hg, ei : g 2 @f (x)} for all x, e 2 X is an L-bounded directional subgradient map.
More generally, we have the following example, which covers many interesting objectives, including the weakly convex case. For a Lipschitz function f : R n ! R, the Clarke subdifferential @ c f (x) is the convex hull of the set of all limits of the form limrf (x r ) for points x r ! x in R n . The function f is subdifferentially regular when its Gâteaux directional derivative satisfies f 0 (x; e) à max{hg, ei : g 2 @ c f (x)} for all x, e 2 R n :
Example 3 (Subdifferentially Regular Functions). Consider any L-Lipschitz subdifferentially regular function f : R n ! R. Then, any map G satisfying G(x, e) 2 argmax{hg, ei : g 2 @ c f (x)} for all x, e 2 R n is an L-bounded directional subgradient map.
Notwithstanding the generality of this example, we emphasize that our framework is not restricted to objectives that are subdifferentially regular, as the following result shows.
Proposition 1 (Directional Clarke Subgradient Maps). Any locally Lipschitz function f : R n ! R that is directionally differentiable has a directional subgradient map G : R n ⇥ R n ! R n satisfying G(x, e) 2 @ c f (x) for all x, e 2 R n .
Proof. We just need to prove that if f has a Gâteaux directional derivative at the point x 2 R n in the direction e 2 R n , then there exists a Clarke subgradient g 2 @ c f (x) satisfying hg, ei à f 0 (x; e). For r à 1, 2, 3, : : : , by the nonsmooth mean value theorem, there exists a point x r 2 x, x + 1 r e ⇤ ⌅ and a subgradient g r 2 @ c f (x r ) satisfying
Because the subdifferential @ c f mapping is closed and locally bounded, any limit point g of the sequence {g r } has the desired property. w
As discussed in Section 1, rather than trying to minimize the objective f, we instead seek a point x 2 X that is, in some sense, approximately critical. To this end, we make the following definition. We denote the closed ball in X of radius δ and center x by B δ (x).
Definition 2. Consider the setting of Definition 1. Corresponding to any constant δ > 0, a Goldstein subgradient at x is a vector of the form
for a positive integer k, positive weights λ i summing to one, points x i 2 B δ (x), and directions e i 2 X for i à 1, 2, : : : , k. The set of all Goldstein subgradients is denoted by @ δ f (x).
Loosely speaking, the Goldstein subdifferential @ δ f (x) consists of all convex combinations of subgradients at nearby points. Strictly speaking, our notion is potentially smaller than the standard definition for Lipschitz f : R n ! R, namely the closed convex hull of the set @ c f (B δ (x)).
We can now state our goal, which relies on a second constant ✏ > 0.
Aim. Find a point x 2 X and a Goldstein subgradient g 2 @ δ f (x) such that | g| ✏.
The development of Zhang et al. [24] accomplishes this goal, explicitly in the setting of Proposition 1 and assuming that f is directionally differentiable in the (stronger) Hadamard sense. It relies on the following oracle.
Input:
• a point x 2 X, • a direction e 2 X. Output:
• the objective value f(x),
• the directional derivative f 0 (x; e), • a subgradient-like vector G(x, e).
In this work, we rely on the same directional subgradient oracle. We emphasize that this oracle is stronger than the standard subgradient oracle. We cannot directly compare our approach with algorithms relying only on the standard oracle because the extra computational cost of the directional oracle is hidden in our analysis, just as it is in Zhang et al. [24]. How generally available a directional oracle might be is unclear; a cautionary point of comparison is the NP hardness of deciding the existence of descent directions (see Nesterov [18]).
In generic practice, however, for a Lipschitz objective f, we may expect that the algorithm we describe never encounters points x where f is nondifferentiable, in which case any subgradient oracle simply returns g à rf (x) (see Bianchi et al. [1]). More formally, nonetheless, we must consider nonsmooth points. Undeterred, Zhang et al. [24] argue that availability of the directional oracle, although a nontrivial restriction, may be a reasonable assumption, directional subgradients being potentially computable via nonsmooth calculus rules. In contrast with Zhang et al. [24], our aim here is a fully deterministic algorithm. Accordingly, although we use this same stronger oracle, we instead use a deterministic line search, much as in Kornowski and Shamir [15]. To ensure termination, we make a mild assumption about the directional behavior of the objective function f, similar in spirit to the idea of semismoothness (see Mifflin [17]) common in nonsmooth computation but simpler and weaker.
Rather than the directional subgradient oracle on which we here rely, combined with a line search, one might instead consider other potential oracles. In particular, given an oracle that returns a descent direction, one might try to mimic smooth techniques, simply searching along that direction. However, even laying aside the NP hardness of a general descent direction oracle noted, such a basic approach is flawed. A classical example of Wolfe [23] shows that gradient descent with exact line search on a nonsmooth continuous convex function can encounter only smooth points and yet, converge to a point that is not a minimizer. Nonsmoothness necessitates a more robust approach. Definition 3. Consider a directionally differentiable function f : X ! R. We call f directionally semismooth if all points x 2 X and directions e 2 X satisfy lim
On the other hand, following the approach of Facchinei and Pang [9], f is semismooth if it is Lipschitz, and the following stronger property holds: f 0 (x + e; e) f 0 (x; e) à o(e) as e ! 0: Most Lipschitz functions in practice are semismooth, including in particular, difference-of-convex functions and semialgebraic functions; see Bolte et al. [3]. As we shall see, directional semismoothness suffices to guarantee termination of our algorithm, but before describing it, we focus first on the line search.
Following Zhang et al. [24], as is usual in black-box-style analysis, we suppose that the optimizer has no access to the implementation of Oracle 1 (directional subgradient). In one interesting class of practical examples, the output "subgradients" may be generated cheaply but opaquely by standard autodifferentiation algorithms, like that in PyTorch (see Paszke et al. [19]). Indeed, in the image classification experiments in Zhang et al. [24], where precise implementation of the directional subgradient oracle seems challenging, the authors simply use as a heuristic an autodifferentiation routine, assuming that it should never encounter nonsmooth ingredients in practice. In fact, even in the presence of nonsmooth ingredients, the occasional failure of autodifferentiation to output correct subgradients seems to have no impact on practical optimization, for reasons discussed by Bolte and Pauwels
As a more precise illustration of the computational cost of the directional subgradient oracle, we present a simple formal example of an easily implementable version-a special case of Example 3. Consider an objective of the form f (x) à max i2I f i (x) for smooth functions f i indexed by a finite set I. Given an input consisting of a point x and direction e, the oracle works by first finding the active subset I(x) of indices i maximizing f i (x) and then, chooses as the output subgradient any gradient rf i (x) maximizing the inner product hrf i (x), ei over i 2 I(x). Typically, the gradient computations dominate, so the cost of the directional oracle is proportional to the size of the set I. We emphasize, however, that to be interesting, this computation should be invisible to the optimizer; given the same access to the functions f i as the oracle, the optimizer could solve the problem easily using classical nonlinear programming tools.
We pose the line search problem as a self-contained question. Consider points p < q in R and a function h :
. Suppose that h is right differentiable on the interval [p, q), and an oracle returns, for any input t 2 [p, q), the value h(t) and the right derivative
(possibly extended valued). How difficult is it to find a point t satisfying h 0 + (t) < 0? When h is Lipschitz, the most basic randomized strategy-uniformly sampling random points t in the interval-solves this problem with high probability. Denoting the Lipschitz constant by L, the right derivative h 0 + always lies in the interval [ L, L]. Denote the measure of the subset S of the interval [p, q] where h 0 + 0 by λ. Then, providing that the average slope satisfies h(q) h(p) q p à σ < 0, the fundamental theorem of calculus implies
Because the integrand is bounded below by zero on S and by -L on the complement S c , a set of measure (q p) λ, we deduce
Hence, the probability λ q p that a uniformly distributed random point t 2 [p, q] fails to satisfy h 0 (t) < 0 is no larger than 1 σ L . Thus, for small σ, using at least L σ independent samples, the probability of success is at least 1 2 . However, we seek a deterministic algorithm, so we instead consider the following simple method, similar in spirit to one described by Davis et al. [6]. We repeatedly bisect the interval [p, q], each time discarding the subinterval over which the function h decreases the least. The algorithm checks whether the right derivative at the midpoint of the current interval is negative, in which case it terminates.
input:
Notice that the algorithm initially calls the oracle at the left end point p of the given interval, calculates the function value at the right end point q, and then, calls the oracle once during each bisection.
In general, this algorithm may fail to terminate. It is easy to construct a Lipschitz function h satisfying h(p) > h(q), and yet, the derivative of h at the initial end point p and at every midpoint m is positive. To rule out such oscillatory examples, we can rely on directional semismoothness of h, which in this univariate setting, Semismoothness is more than enough to prove termination of the line search. The simple argument also applies to non-Lipschitz functions.
Proposition 2 (Termination of the Line Search). Suppose that the function h : [p, q] ! R satisfies h(p) > h(q) and that its left and right derivatives satisfy the semismoothness conditions
Then, Algorithm 1 terminates.
Proof. If the algorithm does not terminate, then it generates monotonic sequences l k " and r k #, satisfying r k l k ! 0,
for each iteration k à 0, 1, 2, : : : . (The line search ensures that the ratio in the second inequality never increases.) Denote the two sequences' mutual limit by m. Semismoothness ensures
which is a contradiction. Hence, for all large k, we have q > r k > m. The right end points r k decrease to m and so, are always updated eventually; hence, the line search guarantees
Adding now gives a contradiction. w
To minimize a locally Lipschitz function f : X ! R using the directional subgradient oracle described, we study the following algorithm. The method we describe is essentially that of Zhang et al. [24] but with the deterministic line search described in the preceding section.
Apply Algorithm 1 (bisection) using the formula
Notice that, in contrast with the classical subgradient method but like many classical approaches involving line searches, trust regions, or subgradient bundling techniques, this algorithm only updates the current iterate when it satisfies a sufficient decrease condition. Intermediate "null" steps serve to shorten the current Goldstein subgradient g.
When the objective f is directionally semismooth, Algorithm 1 terminates by Proposition 2, which in turn, guarantees termination of Algorithm 2, as we shall now prove. We use the following simple tool, following Zhang et al. [24].
Lemma 1. If two vectors g, g 0 2 B L (0) satisfy hg 0 , gi 1 2 |g | 2 , then the shortest vector g 00 in the line segment [g, g 0 ] satisfies
Proof. For all t 2 [0, 1], we have
8L 2 proves the result. w We can now prove the validity of the algorithm, again imitating parts of the argument in Zhang et al. [24], which we reproduce for ease of reading.
Theorem 1 (Finite Termination). Suppose that we apply Algorithm 2 to a directionally semismooth function f : X ! R that is bounded below, with tolerance ✏ > 0, radius δ > 0, and initial point x 0 2 X. Suppose that the directional subgradient map in Oracle 1 is L-bounded. Then, the algorithm terminates with a point x 2 X and a subgradient g 2 @ δ f (x) satisfying |g | ✏. The number of line searches required does not exceed
Proof. Suppose that the current subgradient g is inadequate in the sense that, in the terminology of the algorithm description, it neither is small nor generates sufficient decrease. We then apply the bisection method, Algorithm 1, to the given function h. The initial interval is [p, q] à [0, δ], and the average slope satisfies
We thus arrive at a subgradient g 0 2 @ δ f (x) satisfying hg 0 , ĝi < ✏ 2 . We deduce hg 0 , gi <
2 . The algorithm replaces the current subgradient g by the shortest vector g 00 in the line segment [g, g 0 ]. Because g 00 2 @ δ f (x), we can repeat this shortening process, providing that g 00 is also inadequate. Suppose that the subgradient g remains inadequate after completing k such shortening steps. Let ρ i denote the quantity
16L 2 after i à 0, 1, 2, : : : , k steps. Then, ρ 0 1 16 , and for each I, we have
Hence, after no more than
shortening steps, each requiring one line search, we arrive at an adequate subgradient g 2 @ δ f (x). To summarize, starting at any point with an inadequate subgradient, we require no more than 16L 2 ✏ 2 line searches before finding an adequate subgradient g.
There are now two possibilities. Either the subgradient g satisfies | g| ✏, in which case we stop, or we perform a reduction step, replacing the current point x by x δ g | g | , thereby decreasing the objective value by at least the quantity δ✏ 3 . Because the objective is bounded below, beginning from the initial point x 0 , this procedure terminates after no more than d 3 δ✏ (f (x 0 ) inf f ))e reduction steps, from which the line search bound (1) follows. Proposition 2 ensures that each line search requires only finitely many oracle calls, completing the proof. w
To complete our complexity analysis for the minimization algorithm, we simply need to bound the number of oracle calls needed by each line search and multiply by our bound (1) on the number of line searches. Consider, therefore, the bisection method. When the function h : [p, q] ! R is convex, the problem is trivial; because h(p) > h(q) ) h 0 + (p) < 0, the algorithm terminates at the first oracle call. More generally, we proceed by correcting any lack of convexity in h by adding a convex perturbation s : [p, q] ! R.
Recall that, for any interval J, a function h : J ! R is difference of convex when there exists a convex function s : J ! R such that h + s is also convex. For such functions, we have the following tool.
Lemma 2. Consider a function h : [p, q] ! R and a convex function s : [p, q] ! R such that h + s is also convex. For any points x < y in the interval [p, q], if h 0 + (x) 0, then h(y) h(x) y x s 0 + (x) s 0 (y): Proof. Denote the convex function h + s by r. The convex functions r and s satisfy r 0 + (x) 2 @r(x) and s 0 (y) 2 @s(y):
Hence,
h(y) h(x) + r 0 + (x)(x y) h(y) h(x) + s 0 + (x)(x y), and the result follows. w
We can then use the change in derivative of the necessary perturbation s to bound the number of iterations in the line search.
Theorem 2. Consider a function h : [p, q] ! R and a convex function s : [p, q] ! R such that h + s is also convex. If the bisection method, Algorithm 1, evaluates h 0 + , the right derivative, k 1 times without terminating, then h(q) h(p) q p s 0 + (p) s 0 (q) k :
Proof. We proceed by induction on the number of evaluations k à 1, 2, 3, : : : . The case k à 1 follows immediately from Lemma 2 by setting x à p and y à q. Suppose that the result holds for any points p < q and for any number of evaluations no larger than k. Now, consider an instance of the algorithm that completes k + 1 evaluations. After the first evaluation, consider the midpoint m à 1 2 (p + q). There are two possible cases depending on whether 2h(m) < h(p) + h(q):
(
We consider them in turn. Suppose first that Inequality (2) holds. After the first evaluation, the algorithm makes k further evaluations, beginning with the initial interval [p, m]. Hence, by the induction hypothesis,
Because the algorithm did not terminate during the first two evaluations, we know h 0 + (m) 0. Applying Lemma 2 with x à m and y à q shows h(q) h(m) q m s 0 + (m) s 0 (q): Hence,
The case where Inequality (2) fails is similar. After the first bisection, the algorithm makes k further bisections, beginning with the initial interval [m, q]. Hence, by the induction hypothesis, h(q) h(m) q m s 0 + (m) s 0 (q) k : Hence,
Definition 4. Given any interval J ⇢ R, the concave deviation of a function h : J ! R is the infimum of the Lipschitz constants of convex functions s : J ! R such that the sum h + s is also convex. Consider, for example, a ρ-weakly convex function h, for some constant ρ 0, meaning that the function t
⇥ 2 is convex, with Lipschitz constant ρ 2 (q p), and h + s is also convex. w The concave deviation for functions that are not weakly convex may shrink more slowly than the length of the interval. For example, on the interval [ δ, δ], the function h(t) à |t| The concave deviation of a function h : [p, q] ! R that is difference of convex may not be finite. An example is the concave function Ç Ç • p on the interval [0, 1]. However, if h extends to a difference-of-convex function on an open interval containing the interval [p, q], then its nonconvexity bound on [p, q] must be finite because we can write h as a difference-of-convex functions, each of which must be Lipschitz on [p, q].
Consider any continuous semialgebraic function h : R ! R. We can partition R into finitely many closed intervals J such that each restriction h| J is either convex or concave. In general, such a partition may not guarantee that h is difference of convex; an example is the function x 1 3 . However, if h is also Lipschitz, then each convex or concave ingredient h| J extends to a corresponding convex or concave Lipschitz function on R, and from these, we can easily decompose h into a difference-of-convex Lipschitz functions. Thus, all semialgebraic Lipschitz functions on R are difference of convex, with finite concave deviation on any bounded interval.
then the number of evaluations of h 0 + , the right derivative, required before the bisection method, Algorithm 1, terminates is no more than 1 + b 2M σ c. Proof. Suppose that the bisection method evaluates the right derivative k 1 times without terminating. Fix any value M 0 > M. By assumption, there exists a convex function s with Lipschitz constant less than M 0 such that the sum h + s is also convex. From Theorem 2, we deduce the inequalities Given an open interval I, consider a difference-of-convex function h : I ! R. As observed by Hartman [11], such functions are characterized by having left and right derivatives everywhere, which furthermore, are of bounded variation on every compact interval in I. Any such function h also has a second derivative D 2 h in the distributional sense; in general, it is a signed Radon measure on the interval I (see Dudley [7]).
We review briefly the underlying construction. Consider any convex function s : I ! R. Its right derivative s 0 + is nondecreasing and right continuous, and hence, it defines a nonnegative Radon measure D 2 s on the interval I via the property (D 2 s)(p, q] à s 0 + (q) s 0 + (p) for all p < q in I:
(We could equivalently work from the property (D 2 s)(p, q) à s 0 (q) s 0 + (p).) More generally, for any difference-ofconvex function h : I ! R, consider any convex function s : I ! R such that h + s is also convex. The second derivative D 2 h is just the signed measure D 2 (h + s) D 2 s, which is independent of the choice of s. Convexity of h is characterized by the property D 2 h 0. More generally, the Jordan decomposition decomposes D 2 h uniquely into a difference of nonnegative Radon measures,
with the minimality property (see Rudin [20, p. 127]) that any other decomposition into a difference of nonnegative Radon measures D 2 h à λ µ satisfies λ (D 2 h) + and µ (D 2 h) .
Proof. Consider any convex function s : [p, q] ! R such that h + s is also convex. The second derivatives satisfy
so the minimality of the Jordan decomposition implies D 2 s (D 2 h) . If s is M-Lipschitz on [p, q], then
If the right-hand side is infinite, this completes the proof; so, suppose that it is finite. Define a function g : (p, q] ! R by
Then, g is a nonnegative nondecreasing left-continuous function that is bounded above and g(t) # 0 as t # p. Now, define a convex function s : [p, q] ! R by
Then, s 0 (t) à g(t) for all t 2 (p, q] and s 0 + (p) à 0. Furthermore, we have
is also convex, as is h + s, and the function s has Lipschitz constant
This completes the proof. w
As an illustration, we have the following result. Corollary 2 (Piecewise Linear Functions). Consider a continuous piecewise linear function h : [p, q] ! R, with m derivative discontinuities t 1 < t 2 <⋯< t m in the interval (p, q). Define t 0 à p and t m+1 à q, and let g i be the value of the derivative on the interval (t i , t i+1 ) for 0 i m. Then, h has concave deviation
If h is L-Lipschitz, then this bound is no larger than d m 2 eL. Proof. Denoting a unit point mass at the point t by δ t , we have
and hence,
from which the claimed equation follows. The inequality is an easy consequence, using |g i | L for each i. w
As an illustration, we present an example that underlines why the line search complexity estimate in Corollary 1 is the best that we can expect in general. In outline, although the functions h : [p, q] ! R that we consider satisfy h(p) > h(q), their derivatives may often be positive.
Example 4 (Optimality of the Line Search). Consider any constant M > 0 and a set T ⇢ [0, 1) of cardinality strictly less than 2M. Then, there exists a function h : [0, 1] ! R with concave deviation less than M that satisfies h(0) à 0 and h(1) à 1 and that has strictly positive derivative throughout T.
To see this, suppose first T ⇢ (0, 1). (The case when T contains zero is an easy modification.) Enumerate the points in increasing order:
where k < 2M. Define h(0) à 0 and h(1) à 1. Fix any small γ > 0, and define h(t i γ) à t i γ 2 and h(t i + γ) à t i + γ 2 for i à 1, 2, : : : , k: At intermediate points in [0, 1], define h by linear interpolation. A quick calculation, using Corollary 2, shows that h has concave deviation 1 2
providing that γ is sufficiently small. Now, consider any line search method applicable to functions h : [0, 1] ! R satisfying h(0) à 0 and h(1) à 1, relying on evaluations of the value h and the right derivative h 0 + at points chosen one by one, and terminating once a derivative is negative. Suppose that the method is guaranteed to terminate after at most k queries, providing that the underlying function h has concave deviation strictly less than some given value M > 0. The example proves k 2M.
To understand the complexity of Algorithm 2 (nonsmooth minimization), we apply our analysis in the previous section to restrictions of multivariate objectives f to line segments. For any convex set C ⇢ X, consider a function f : C ! R. Given any length δ > 0, let Λ(δ) denote the supremum over all points x, y 2 C with |x y| δ of the concave deviation for the function h : [0, δ] ! R defined by
We call the function Λ : R ++ ! [0, + 1] the nonconvexity modulus for f. The following illustration follows immediately from Proposition 3. More generally, the function f is difference of convex when there exists a convex function q : C ! R such that f + q is also convex.
Proposition 5. Consider a convex set C ⇢ X and functions f , q : C ! R with both q and f + q convex. If q is M-Lipschitz, then the nonconvexity modulus of f satisfies Λ(δ) M for all δ > 0.
Proof. Consider any points x, y 2 C with |x y | δ and the function h defined by Equation (3). The function s : [0, δ] ! R defined by
is convex and M-Lipschitz, and h + s is convex; therefore, the concave deviation of h is no larger than M. The result follows. w
As a consequence, we deduce the following result.
Corollary 3. Consider any convex sets C ⇢ C 0 ⇢ R n , where C is nonempty and compact and C 0 is open, and any differenceof-convex function f : C 0 ! R. Then, the nonconvexity modulus of the restriction f C is uniformly bounded; there exists a finite constant M such that Λ(δ) M for all δ > 0.
In particular, because polyhedral functions are globally Lipschitz, we have the following fact.
Corollary 4. If a function f : X ! R is the difference p q between a convex function p : X ! R and a polyhedral convex function q : X ! R, then the nonconvexity modulus of f is no larger than any Lipschitz constant for q.
More generally, consider a continuous function f : X ! R that is semilinear in the sense that X is a finite union of polyhedra, on each of which the function f is affine. Any such function has a Lipschitz constant L and furthermore, a uniform upper bound m on the number of possible gradient discontinuities in any function of the form (3). By Corollary 2, we deduce that the nonconvexity modulus Λ(δ) is no larger than d m 2 eL. Returning to our analysis of Algorithm 2, we are ready for our main result.
Theorem 4 (Complexity of Minimization). Given a tolerance ✏ > 0 and a radius δ > 0, consider a convex set C ⇢ X, a function f : C ! R that is bounded below, an associated L-bounded directional subgradient map G : X 2 ! X, and an initial point x 0 2 C such that f (x) f (x 0 ) and |y| δ ) x + y 2 C: Suppose that f has finite nonconvexity modulus Λ(δ). Then, Algorithm 2 (nonsmooth minimization) requires at most
calls to Oracle 1 (directional subgradient) to find a point x 2 X and a Goldstein subgradient g 2 @ δ f (x) satisfying |g | ✏.
Proof. Corollary 1 with σ à ✏ 6 shows that the bisection method requires at most ⇥ noted in the abstract.
In summary, our deterministic algorithm, when applied to difference-of-convex objectives with bounded nonconvexity modulus, returns a point with an ✏-Goldstein subgradient of norm no larger than ✏ after O(✏ 5 ) oracle
We saw previously that the concave deviation of a univariate function h is determined by the negative part of its second distributional derivative D 2 h. In our application, we consider functions h that are restrictions of the underlying objective f to line segments of fixed length δ. We would, therefore, expect the nonconvexity modulus of f to be related to its own distributional second derivative. Here, we explore that relationship informally. Consider a locally Lipschitz function f : R n ! R. The distributional derivative of f is an n-vector Df, entries of which are distributions-linear functionals on the space of smooth, compactly supported functions g : R n ! R (test functions)that are continuous with respect to uniform convergence on compact sets. We can define Df through the relationship
for all vectors u 2 R n and test functions g : R n ! R. However, by a suitable version of Rademacher's theorem (see Evans and Gariepy [8, section 6.2, theorem 1]), the gradient rf exists almost everywhere and is essentially bounded, and it satisfies
In standard terminology (see Evans and Gariepy [8]), we can identify the classical gradient rf with both the distributional derivative Df and the "weak" derivative of f. The second distributional derivative of f is an n-by-n matrix D 2 f , entries of which are distributions. We can define D 2 f through the relationship
for all vectors u, v 2 R n and test functions g. If f is smooth, then D 2 f is just the matrix-valued measure with density r 2 f . More generally, we must consider D 2 f as a distribution, but at least for convex functions, we can be more specific; it is a positive semidefinite-valued Radon measure (see Dudley [7] and Evans and Gariepy [8, section 6.3]).
Example A.1 (A Piecewise Linear Function). Consider the convex function f : R 2 ! R defined by f (x) à x + 1 . For any vectors u, v 2 R 2 and smooth, compactly supported function g : R 2 ! R, we have
by the Gauss-Green formula. Thus, D 2 f is the matrix µ 0 0 0 , where the measure µ is related to Lebesgue measure λ via
for all measurable subsets of S ⇢ R 2 . For a more general understanding, we begin with the univariate case.
Example A.2 (Univariate Convex Functions). Consider a convex function f : R ! R. For 0 < γ < 1, we can construct a smooth approximation h γ : R ! [0, 1] of the standard step function, with the following properties:
and h is convex on [0, γ 2 ], linear on [γ 2 , γ γ 2 ], and concave on [γ γ 2 , γ]. For any interval (p, q] ⇢ R, the test function r γ :
Kong and Lewis: The Cost of Nonconvexity in Deterministic Nonsmooth Optimization R ! [0, 1] defined by
converges pointwise to the characteristic function χ (p, q] pointwise as γ # 0. By dominated convergence, we deduce
However, the left-hand side is Z r 0 γ f 0 à
as γ # 0. We, thus, reproduce our earlier definition:
Clearly, this fact also holds for any difference-of-convex function f : R ! R.
The modulus of nonconvexity for a function f : R n ! R, which we denoted Λ(δ) (for δ > 0), is the supremum of the concave deviation of the restriction of f to line segments of the form S à {z + tw : 0 t δ} for some point z 2 R n and unit direction w 2 R n . That concave deviation is the measure of S under the negative part of the measure D 2 (f | S ). We would, therefore, like to compare the distributional second derivative of this restriction with the distributional second derivative D 2 f . As we see in the next result, we should focus specifically on the directional distributional second derivative w T (D 2 f )w.
A simple approach is furnished by mollification. We fix a mollifier φ : R n ! R: a test function satisfying R φ à 1 and with the property that, as γ # 0, the function φ γ (x) à γ n φ 1 γ x ⌘ ✓ converges as a distribution to the Dirac delta function.
Given a Radon measure µ on R n and any test function g : R n ! R, we can define the convolution g ? µ : R n ! R by In this result, the effect of the convolution is to focus attention on the line through the point z in the direction w. In informal language, we deduce that the modulus of nonconvexity Λ(δ) is determined by the concentration of the negative parts of the measures w T (D 2 f )w around line segments of length δ in unit directions w.
For more intuition on directional distributional second derivatives of the form w T (D 2 f )w, let us consider a convex function f : R 2 ! R. After a suitable choice of basis, we can suppose that w is the first unit vector e 1 and therefore, consider the Radon measure (Df ) 11 . To understand this measure, consider the integral Z More generally, this argument suggests, loosely, that w T (D 2 f )w measures the variation of the directional derivative f 0 (•; w) along the direction w.
Endnote 1 We became aware of these concurrent independent works after completing the initial draft of this manuscript.
Mathematics of Operations Research, Articles in Advance, pp. 1-17, © 2023 INFORMS Downloaded from informs.org by [31.4.245.160] on 21 December 2023, at 05:59 . For personal use only, all rights reserved.
Kong and Lewis: The Cost of Nonconvexity in Deterministic Nonsmooth Optimization
Downloaded from informs.org by [31.4.245.160] on 21 December 2023, at 05:59 . For personal use only, all rights reserved.