Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local Minimizers

2017·Arxiv

Abstract

Abstract

Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an “inspect” phase to existing algorithms that helps escape from non-global stationary points. The inspection samples a set of points in a radius R around the current point. When a sample point yields a sufficient decrease in the objective, we resume an existing algorithm from that point. If no sufficient decrease is found, the current point is called an approximate R-local minimizer. We show that an R-local minimizer is globally optimal, up to a specific error depending on R, if the objective function can be implicitly decomposed into a smooth convex function plus a restricted function that is possibly nonconvex, nonsmooth. Therefore, for such nonconvex objective functions, verifying global optimality is fundamentally easier. For high-dimensional problems, we introduce blockwise inspections to overcome the curse of dimensionality while still maintaining optimality bounds up to a factor equal to the number of blocks. Our method performs well on a set of artificial and realistic nonconvex problems by coupling with gradient descent, coordinate descent, EM, and prox-linear algorithms.

Keywords R-local minimizer, Run-and-Inspect Method, nonconvex optimization, global minimum, global optimality

Mathematics Subject Classification (2000) 90C26 90C30 49M30 65K05

1 Introduction

This paper introduces and analyzes R-local minimizers in a class of nonconvex optimization and develops a Run-and-Inspect Method to find them. Consider a possibly nonconvex minimization problem:

where the variable can be decomposed into s blocks . We assume . We call a point an R-local minimizer for some R > 0 if it attains the minimum of F within the ball with center and radius R.

This work of Y. Chen is supported in part by Tsinghua Xuetang Mathematics Program and Top Open Program for his short-term visit to UCLA. The work of Y. Sun and W. Yin is supported in part by NSF grant DMS-1720237 and ONR grant N000141712162.

In nonconvex minimization, it is relatively cheap to find a local minimizer but difficult to obtain a global minimizer. For a given R > 0, the difficulty of finding an R-local minimizer lies between those two. Informally, they have the following relationships: for any R > 0,

We are interested in nonconvex problems for which the last “” holds with “=,” indicating that any R-local minimizer (for a sufficiently large R) is global. This is possible, for example, if F is the sum of a quadratic function and a sinusoidal oscillation:

where and . The range of oscillation is specified by amplitude a and frequency . We use to shift its phase so that the minimizer of F is . We also add a to level the minimal objective at .

An example of (2) with a = 0.3 and b = 3 is depicted in Figure 1.

Fig. 1 F(x) in (2) with a = 0.3, b = 3.

Observe that F has many local minimizers, and its only global minimizer is . Near each local minimizer , we look for an escape point such that . We claim that by taking , such an escape point exists for every local minimizer except .

Proposition 1 Consider minimizing F in (2). If , then the only point that satisfies the condition

is the global minimizer .

Proof Suppose . Without loss of generality we can further assume . Recall the global minimizer is .

i) If , then gives , so is the global minimizer. Otherwise, we have Indeed,

This leads to the contradiction similar to part i).

Proposition 1 indicates that we can find of this problem by locating an approximate local minimizer (using a proper algorithm) and then inspecting a small region near (e.g., by sampling a set of points). Once the inspection finds a point x such that , resume the algorithm from x and let it find the next approximate local minimizer such that . Alternate such running and inspection steps until, at a local minimizer , the inspection fails to find a better point nearby. Then, must be an approximate global solution. We call this procedure the Run-and-Inspect Method.

The coupling of “run” and “inspect” is simple and flexible because, no matter which point the “run” phase generates, being it a saddle point, local minimizer, or global minimizer, the “inspect” phase will either improve upon it or verify its optimality. Because saddle points are easier to escape from than a non-global local minimizer, hereafter, we ignore saddle points in our discussion. Related saddle-point avoiding algorithms are reviewed below along with other literature.

Sample-based inspection works in low dimensions. However, it suffers from the curse of dimensionality, as the number of points will increase exponentially with the dimension. For high-dimensional problems, the cost will be prohibitive. To address this issue, we define the blockwise R-local minimizer and break the inspection into s blocks of low dimensions: where . We call a point a blockwise R-local minimizer, where , if it satisfies

where B(x, R) is a closed ball with center x and radius R. To locate a blockwise R-local minimizer, the inspection is applied to every block while fixing the others. Its cost grows linearly in the number of blocks when the size of every block is fixed.

This paper studies R-local and blockwise R-local minimizers and develop their global optimality bounds for a class of function F that is the sum of a smooth, strongly convex function and a restricted nonconvex function. (Our analysis assumes a property weaker than strong convexity.) Roughly speaking, the landscape of F is convex at a coarse level, and it can have many local minima. (Arguably, if the landscape of F is overall nonconvex, minimizing F is fundamentally difficult.)

This decomposition is implicit and only used to prove bounds. Our Run-and-Inspect Method, which does not use the decomposition, can still provably find a solution that has a bounded distance to a global minimizer and an objective value that is bounded by the global minimum. Both bounds can be zero with a finite R.

The radius R affects theoretical bounds, solution quality, and inspection cost. If R is very small, the inspections will be cheap, but the solution returned by our method will be less likely to be global. On the other hand, an excessive large R leads to expensive inspection and is unnecessary since the goal of inspection is to escape local minima rather than decrease the objective. Theoretically, Theorem 3 indicates a proper choice , where are parameters of the functions in the implicit decomposition. Furthermore, if R is larger than a certain threshold given in Theorem 4, then returned by our method must be a global minimizer. However, as these value and threshold are associated with the implicit decomposition, they are typically unavailable to the user.

One can imagine that a good practical choice of R would be the radius of the global-minimum valley, assuming this valley is larger than all other local-minimum valleys. This choice is hard to guess, too. Another choice of R is roughly inversely proportional to , where f is the smooth convex component in the implicit decomposition of F. It is possible to estimate using an area maximum of , which itself requires a radius of sampling, unfortunately. (is zero at any local minimizer, so its local value is useless.) However, this result indicates that local minimizers that are far from the global minimizer are easier to escape from.

We empirically observe that it is both fast and reliable to use a large R and sample the ball outside-in, for example, to sample on a set of rings of radius . In most cases, a point on the first couple of rings is quickly found, and we escape to that point. The smallest ring is almost never sampled except when is already an (approximate) global minimizer. Although the final inspection around a global minimizer is generally unavoidable, global minimizers in problems such as compressed sensing and matrix decomposition can be identified without inspection because they have the desired structure or attained a lower bound to the objective value. Anyway, it appears that choosing R is ad hoc but not difficult. Throughout our numerical experiments, we use R = O(1) and obtain excellent results consistently.

The exposition of this paper is limited to deterministic methods though it is possible to apply stochastic techniques. We can undoubtedly adopt stochastic approximation in the “run” phase when, for example, the objective function has a large-sum structure. Also, if the problem has a coordinate-friendly structure [16], we can randomly choose a coordinate, or a block of coordinates, to update each time. Another direction worth pursuing is stochastic sampling during the “inspect” phase. These stochastic techniques are attractive in specific settings, but we focus on non-stochastic techniques and global guarantees in this paper.

1.1 Related work

1.1.1 No spurious local minimum

For certain nonconvex problems, a local minimum is always global or good enough. Examples include tensor decomposition [6], matrix completion [7], phase retrieval [22], and dictionary learning [21] under proper assumptions. When those assumptions are violated to a moderate amount, spurious local minima may appear and be possibly easy to escape. We will inspect them in our future work.

1.1.2 First-order methods, derivative-free method, and trust-region method

For nonconvex optimization, there has been recent work on first-order methods that can guarantee convergence to a stationary point. Examples include the block coordinate update method [25], ADMM for nonconvex optimization [23], the accelerated gradient algorithm [8], the stochastic variance reduction method [18], and so on.

Because the “inspect” phase of our method uses a radius, it is seemingly related to the trust-region method [3,12] and derivative-free method [4], both of which also use a radius at each step. However, the latter methods are not specifically designed to escape from a non-global local minimizer.

1.1.3 Avoiding saddle points

A recent line of work aims to avoid saddle points and converge to an -second-order stationary point that satisfies

where is the Lipschitz constant of . Their assumption is the strict saddle property, that is, a point satisfying (5) for some and must be an approximate local minimizer. On the algorithmic side, there are second-order algorithms [13,15] and first-order stochastic methods [6,9,14] that can escape saddle points. The second-order algorithms use Hessian information and thus are more expensive at each iteration in high dimensions. Our method can also avoid saddle points.

1.1.4 Simulated annealing

Simulated annealing (SA) [11] is a classical method in global optimization, and thermodynamic principles can interpret it. SA uses a Markov chain with a stationary distribution , where T is the temperature parameter. By decreasing T, the distribution tends to concentrate on the global minimizer of F(x). However, it is difficult to know exactly when it converges, and the convergence rate can be extremely slow.

SA can be also viewed as a method that samples the Gibbs distribution using Markov-Chain Monte Carlo (MCMC). Hence, we can apply SA in the “inspection” of our method. SA will generate more samples in a preferred area that are more likely to contain a better point, which once found will stop the inspection. Apparently, because of the hit-and-run nature of our inspection, we do not need to wait for the SA dynamic to converge.

1.1.5 Flat minima in the training of neural networks

Training a (deep) neural network involves nonconvex optimization. We do not necessarily need to find a global minimizer. A local minimizer will suffice if it generalizes well to data not used in training. There are many recent attempts [1,2,19] that investigate the optimization landscapes and propose methods to find local minima sitting in “rather flat valleys.”

Paper [1] uses entropy-SGD iteration to favor flatter minima. It can be seen as a PDE-based smoothing technique [2], which shows that the optimization landscape becomes flatter after smoothing. It makes the theoretical analysis easier and provides explanations for many interesting phenomena in deep neural networks. But, as [24] has suggested, a better non-local quantity is required to go further.

1.2 Notation

Throughout the paper, denotes the Euclidean norm. Boldface lower-case letters (e.g., x) denote vectors. However, when a vector is a block in a larger vector, it is represented with a lower-case letter with a subscript, e.g., .

1.3 Organization

The rest of this paper is organized as follows. Section 2 presents the main analysis of R-local and blockwise R-local minimizers, and then introduces the Run-and-Inspect Method. Section 3 presents numerical results of our Run-and-Inspect method. Finally, Section 4 concludes this paper.

2 Main Results

In sections 2.1–2.3, we develop theoretical guarantees for our R-local and R-local minimizers for a class of nonconvex problems. Then, in section 2.4, we design algorithms to find those minimizers.

2.1 Global optimality bounds

In this section, we investigate an approach toward deriving error bounds for a point with certain properties.

Consider problem (1), and let denote one of its global minimizers. A global minimizer owns many nice properties. Finding a global minimizer is equivalent to finding a point satisfying all these properties. Clearly, it is easier to develop algorithms that aim at finding a point satisfying only some of those properties. An example is that when F is everywhere differentiable, is a necessary optimality condition. So, many first-order algorithms that produce a sequence such that converge to a global minimizer. Below, we focus on choosing the properties of so that a point satisfying the same properties will enjoy bounds on and . Of course, proper assumptions on F are needed, which we will make as we proceed.

Let us use Q to represent a certain set of properties of , and define

which includes . For any point that also belongs to the set, we have

and

where diam() stands for the diameter of the set . Hence, the problem of constructing an error bound reduces to analyzing the set under certain assumptions on F.

with . This choice is admissible since . For this choice, we have

and

We use the term “implicit” because this decomposition is only used for analysis, not required by our Run-and-Inspect Method. Define the sets of the global minimizers of F and f as, respectively,

Below we make three assumptions on (7). The first and third assumptions are used throughout this section. Only some of our results require the second assumption.

Assumption 1 f(x) is differentiable, and is L-Lipschitz continuous.

Assumption 2 f(x) satisfies the Polyak-Łojasiewicz (PL) inequality [17] with :

Given a point x, we define its projection

Then, the PL inequality (8) yields the quadratic growth (QG) condition [10]:

Clearly, (8) and (9) together imply

Assumption 2 ensures that the gradient of f bounds its objective error.

Assumption 3 r(x) satisfies in which are constants.

Assumption 3 implies that r is overall -Lipschitz continuous with additional oscillations up to . In the implicit decomposition (7), though r can cause F to have non-global local minimizers, its impact on the overall landscape of f is limited. For example, the penalty in compressed sensing is used to induce sparsity of solutions. It is nonconvex and satisfies our assumption

In fact, many sparsity-induced penalties satisfy Assumption 3. Many of them are sharp near 0 and thus not Lipschitz there. In Assumption 3, models their variation near 0 and controls their increase elsewhere.

In section 2.2, we will show that every satisfies for a universal that depends on . So, we choose the condition

To derive the error bound, we introduce yet another assumption:

Assumption 4 The set is bounded. That is, there exists such that, for any , we have .

When f has a unique global minimizer, we have M = 0 in Assumption 4.

Theorem 2 Take Assumptions 1, 2 and 3, and assume that all points in have property Q in (11). Then, the following properties hold for every :

1. , if in Assumption 3;

2. and , if and Assumption 4 holds.

Proof To show part 1, we have

Part 2: Since f satisfies the PL inequality (8) and , we have

By choosing an and noticing , we also have and thus

Below we let and , respectively, denote the projections of and onto the set . Since , we obtain

In the theorem above, we have constructed global optimality bounds for obeying Q. In the next two subsections, we show that R-local minimizers, which include global minimizers, do obey Q under mild conditions. Hence, the bounds apply to any R-local minimizer.

2.2 R-local minimizers

In this section, we define and analyze R-local minimizers. We discuss its blockwise version in section 2.3. Throughout this subsection, we assume that , and B(x, R) is a closed ball centered at x with radius R.

Definition 1 The point is called a standard R-local minimizer of F if it satisfies

Obviously an R-local minimizer is a local minimizer, and when , it is a global minimizer. Conversely, a global minimizer is always an R-local minimizer. We first bound the gradient of f at an R-local minimizer so that Q in (11) is satisfied.

Theorem 3 Suppose, in (7), f and r satisfy Assumptions 1 and 3. Then, a point obeys Q in (11) with given in the following two cases:

1. if r is differentiable with and in (3) and is a stationary point of F; 2. if is a standard R-local minimizer of F.

where a) is due to the assumption on r and that is L-Lipschitz continuous; b) is because, as is fixed, the minimum is attained with . If is immediately satisfied. Now assume . To simplify (13), we only need to minimize a quadratic function of over [0, R]. Hence, the objective equals

If , from , we get

Otherwise, from , we get

Combining both cases, we have and thus

The next result is a consequence of part 2 of the theorem above. It presents the values of R that ensure the escape from a non-global local minimizer. In addition, more distant local minimizers x are easier to escape in the sense that R is roughly inversely proportional to .

Corollary 1 Let x be a local minimizer of F and . As long as either or , there exists such that F(y) < F(x).

Proof Assume that the result does not hold. Then, x is an R-local minimizer of F. Applying part 2 of Theorem 3, we get . Combining this with the assumption , we obtain

We can further increase R to ensure that any R-local minimizer is a global minimizer.

Theorem 4 Under Assumptions 1, 2 and 3 and , we have for any

R-local minimizer . Therefore, if , any R-local minimizer is a global minimizer.

Proof According to Theorem 2, part 2, and Theorem 3, part 2,

where, for the latter inequality, we have used and thus . By convex analysis on f, we have . Using it with and , we further get

. Therefore, if , then there exists such that . Being an R-local minimizer means satisfies , so is a global minimizer.

Remark 1 Since the decomposition (7) is implicit, the constants in our analysis are difficult to estimate in practice. However, if we have a rough estimate of the distance between the global minimizer and its nearby local minimizers, then this distance appears to be a good empirical choice for R.

2.3 Blockwise R-local minimizers

In this section, we focus on problem (1). This blockwise structure of F motivates us to consider block-wise algorithms. Suppose and . When we fix all blocks but , we write as .

Definition 2 A point is called a blockwise R-local minimizer of F if it satisfies

Theorem 5 Suppose f and r satisfy Assumptions 1 and 3. If is a blockwise R-local minimizer of F, then (i.e, the property Q is met) for where , .

is an -local minimizer of . Since and and satisfy Assumption 1 and Assumption 3, Theorem 3 shows that Hence

Remark 2 We can also obtain a simplified version of Theorem 5, which is

The main difference between the standar and blockwise estimates is the extra factor in the latter.

Remark 3 Since we can set , our results apply to Nash equilibrium points.

Generalized from Corollary 1, the following result provides estimates of for escaping from non-global local minimizers. The estimates are smaller when are larger.

Corollary 2 Let x be a local minimizer of F and for some i. As long as , there exists , such that .

The theorem below, which follows from Theorems 2 and 5, bounds the distance of an R-local minimizer to the set of global minimizers. We do not have a vector R to ensure the global optimality of due to the blockwise limitation. Of course, after reaching , if we switch to standard (non-blockwise) inspection to obtain an standard R-local minimizer, we will be able to apply Theorem 4.

Theorem 6 Suppose f and r satisfy Assumptions 1–3. If is a blockwise R-local minimizer of F, then

2.4 Run-and-Inspect Method

In this section, we introduce our Run-and-Inspect Method. The “run” phase can use any algorithm that monotonically converges to an approximate stationary point. When the algorithm stops at either an approximate local minimizer or a saddle point, our method starts its “inspection” phase, which either moves to a strictly better point or verifies that the current point is an approximate (blockwise) R-local minimizer.

2.4.1 Approximate R-local minimizers

We define approximate R-local minimizers. Since an R-local minimizer is a special case of a blockwise R-local minimizer, we only deal with the latter. Let . A point is called a blockwise R-local minimizer of if it satisfies

when s = 1, we say is an R-local minimizer of F up to . It is easy to modify the proof of Theorem 3 to get:

Theorem 7 Suppose f and r satisfy Assumptions 1 and 3. Then if is a blockwise R-local minimizer of F up to and for .

Whenever the condition holds, our previous results for blockwise R-local minimizers are applicable.

2.4.2 Algorithms

Now we present two algorithms based on our Run-and-Inspect Method. Suppose that we have implemented an algorithm and it returns a point . For simplicity let Alg denote this algorithm. To verify the global optimality of , we seek to inspect F around by sampling some points. Since a global search is apparently too costly, the inspection is limited in a ball centered at , and for high-dimensional problems, further limited to lower-dimensional balls.

The inspection strategy is to sample some points in the ball around the current point and stop whenever either a better point is found or it finishes the last point. By “better", we mean the objective value decreases by at least a constant amount . We call this descent threshold. If a better point is found, we resume Alg at that point. If no better point is found, the current point is an R-local or R-local minimizer of F up to , where depends on the density of sample points and the Lipschitz constant of F in the ball.

If Alg is a descent method, i.e., , algorithm 1 will stop and output a point within finitely many iterations: where is the global minimum of F.

The sampling step is a hit-and-run, that is, points are only sampled when they are used, and the sampling stops whenever a better point is obtained (or all points have been used). The method of sampling and the number of sample points can vary throughout iterations and depend on the problem structure. In general, sampling points from the outside toward the inside is more efficient.

Here, we analyze a simple approach in which sufficiently many well-distributed points are sampled to ensure that is an approximate R-local minimizer.

Theorem 8 Assume that f(x) is -Lipschitz continuousin the ball and the set of sample points has density , that is,

where . If

then the point is an R-local minimizer of F up to .

When the dimension of x is high , it is impractical to inspect over a high-dimensional ball. This motivates us to extend algorithm 1 to its blockwise version.

Algorithm 2 samples points in a block while keeping other block variables fixed. This algorithm ends with an approximate blockwise R-local minimizer.

Theorem 9 Assume that is -Lipschitz continuous in the ball for and the set of sample points has blockwise-density , that is,

where . If

then is a blockwise R-local minimizer of F up to for .

The proof is similar to that of Theorem 8. The next proposition states that inspection around a point with sufficiently large partial gradient of f ensures a sufficient descent.

Proposition 10 Assume that we sample points in the ball with density . If

, then there exists at least one sampled point which satisfies

Therefore in Theorem 9 can be bounded by . And we can set

This bound is not tight when is very large.

2.5 Complexity analysis

Since Algorithm 2 generalizes Algorithm 1 to multiple blocks, we analyze the complexity of the former. There are quite many parameters that affect the complexity results. In this analysis, we focus on the dimension of the space d and different options to set the dimension of each block, assuming that all blocks have the same dimension and evenly divides d, thus, creating exactly s = blocks of variables. We assume that the smoothness and strong-convexity parameters of f are , respectively. Of course, affect the complexity significantly though not as much as the dimensions (unless themselves depend on d). Assume the function r satisfies Assumption 3 with parameters . The R-local min tolerance of each block i is tied to (density of sample points), and . Based on Theorem 9 and Proposition 10 and using free parameters that will be tuned later, we set

late that our Algorithm 2 using will return an approximate R-local minimizer satisfying the

global error bound:

where .For simplicity, we set and assume . By (16), (17), we will get

Next, we take three steps to calculate the complexity of Algorithm 2:

– Since Alg is a descent algorithm and each inspection decreases the objective error by at least , with initial point , we need at most inspections or loops in Algorithm 2. Under our assumption , the number of inspections is

Using our choice and , we get

where t = 6 under our assumption.

The complexity of Algorithm 2 is the product of the number of loops and the complexity of each loop:

proportional in the dimension d. Except, if the function r is very nice with , then the relative accuracy is still good at O (1).

– In general, we can choose for , where the choice of v controls the tradeoff between the accuracy and complexity.

3 Numerical experiments

In this section, we apply our Run-and-Inspect Method to a set of nonconvex problems. We admit that it is difficult to apply our theoretical results because the implicit decomposition F = f +r with f, r satisfying their assumptions is not known. Nonetheless, The encouraging experimental results below demonstrate the effectiveness of our Run-and-Inspect Method on nonconvex problems even though they may not have the decomposition.

3.1 Test example : Ackley’s function

The Ackley function is widely used for testing optimization algorithms, and in , it has the form

Fig. 2 Landscape of Ackley’s function in

The function is symmetric, and its oscillation is regular. To make it less peculiar, we modify it to an asymmetric function:

The function F in (20) has a lot of local minimizers, which are irregularly distributed. If we simply use the gradient descent (GD) method without a good initial guess, it will converge to a nearby local

Fig. 3 Landscape and contour of F in (20).

minimizer. To escape from local minimizers, we conduct our Run-and-Inspect Method according to Algorithms 1 and 2. We sample points starting from the outer of the ball toward the inner. The radius R is set as 1 and as 0.2. Alg is GD and block-coordinate descent (BCD), and we apply two-dimensional inspection and blockwise one-dimensional inspection to them, respectively. The step size of GD and BCD is 1/40. The results are shown in Figures 4 and 5, respectively. Note that the “run” and “inspect” phases can be decoupled, so a blockwise inspection can be used with either standard descent or blockwise descent algorithms.

Fig. 4 GD iteration with 2D inspection

Fig. 5 BCD iteration with blockwise 1D inspection

From the figures, we can observe that blockwise inspection, which is much cheaper than standard inspection, is good at jumping out the valleys of local minimizers. Also, the inspection usually succeeds very quickly at the large initial value of R, so it is swift. These observations guide our design of inspection. Although smaller values of R are sufficient to escape from local minimizers, especially those that are far away from the global minimizer, we empirically use a rather large R and, to limit the number of sampled points, a relatively large as well.

When an iterate is already (near) a global minimizer, there is no better point for inspection to find, so the final inspection will go through all sample points in , taking very long to complete, unlike the rapid early inspections. In most applications, however, this seems unnecessary. If F is smooth and strongly convex near the global minimizer , we can theoretically eliminate spurious local minimizers in and thus search only in the smaller region . Because the function r can be nonsmooth in our assumption, we do not have . But, our future work will explore more types of r. It is also worth mentioning that, in some applications, global minimizers can be recognized, for example, based on they having the desired structures, achieving the minimal objective values, or attaining certain lower bounds. If so, the final inspection can be completely avoided.

3.2 K-means clustering

Consider applying k-means clustering to a set of data . We assume there are K clusters and have the variables . The problem to solve is

A classical algorithm is the Expectation Minimization (EM) method, but it is susceptible to local minimizers. We add inspections to EM to improve its results.

We test the problems in [27]. The first problem has synthetic Gaussian data in . A total of 4000 synthetic data points are generated according to four multivariate Gaussian distributions with 1000 points on each, so there are four clusters. Their means and covariance matrices are:

The EM algorithm is an iteration that alternates between labeling each data point (by associating it to the nearest cluster center) and adjusting the locations of the centers. When the labels stop updating, we start an inspection. In the above problem, the dimension of is two, and we apply a 2D inspection on one after one with radius R = 10, step size , and angle step size . The descent threshold is .

The results are presented in Figure 6. We can see that the EM algorithm stops at a local minimizer but, with the help of inspection, it escapes from the local minimizer and reaches the global minimizer. This escape occurs at the first sample point in the 3rd block at radius 10 and angle . Since the inspection succeeds on the perimeter of the search ball, it is rapid.

We also consider the Iris dataset, which contains 150 4-D data samples from 3 clusters. We compare the performance of the EM algorithm with and without inspection over 500 runs with their initial centers randomly selected from the data samples. We inspect the 4-D variables one after one. Rather than sampling the 4-D polar coordinates, which needs three angular axes, we only inspect two dimensional balls. That is, for center and radius r, the inspections sample the following points that has only two angular variables :

Fig. 6 Synthetic Gaussian data with 4 clusters. Left: clustering result; Right: objective value in the iteration

Such inspections are very cheap yet still effective. Similar lower-dimensional inspections should be used with high dimensional problems. We choose , and a descent threshold . The results are shown in Figures 7 and 8.

Fig. 7 histogram of the final objective values in the 500 experiments

Fig. 8 left: 3-D distribution of Iris data and clustering result in one trial; right: objective value in the iteration of this trial.

Among the 500 runs, EM gets stuck at a high objective value 0.48 for 109 times. With the help of inspection, it manages to locate the optimal objective value around 0.263 every time. The average radius-at-escape during the inspections is 2, and the average number of inspections is merely 1.

3.3 Nonconvex robust linear regression

In linear regression, we are given a linear model

and the data points . When there are outliers in the data, robustness is necessary for the regression model. Here we consider Tukey’s bisquare loss, which is bounded, nonconvex and defined as:

The empirical loss function based on is

A commonly used algorithm for this problem is the Iteratively Reweighted Least Squares (IRLS) algorithm [5], which may get stuck at a local minimizer. Our Run-and-Inspect Method can help IRLS escape from local minimizers and converge to a global minimizer. Our test uses the model

where is noise. We generate . We also create 20% outliers by adding extra noise generated from N(0, 5). And we use Algorithm 1 with . For Tukey’s function, is set to be 4.685. The results are shown in Figure 9.

Fig. 9 The left picture displays the contour of the empirical loss and the path of iterates. Starting from the initial point, IRLS converges to a shallow local minimum. With the help of inspection, it escapes and then converges to the global minimum. The right picture shows linear model obtained by IRLS with (red) and without (magenta) inspection.

3.4 Nonconvex compressed sensing

Given a matrix and a sparse signal , we observe a vector

The problem of compressed sensing aims to recover x approximately. Besides and -norm, 1) quasi-norm is often used to induce sparse solutions. Below we use and try to solve the problem

by cyclic coordinate update. At iteration k, it updates the jth coordinate, where j = mod(k, n) + 1, via

It has been proved in [26] that (21) has a closed-form solution. Define

Then

where . In our experiments, we choose m = 25, 50, 100 and n = 2m. The elements of A are generated from i.i.d. The vector x has 10% nonzeros with their values generated from U(0.2, 0.8) i.i.d. Set b = Ax. Here, we apply coordinate descent with inspection (CDI), and compared it with standard coordinate descent (CD) and half thresholding algorithm (half ) [26]. For every pair of (m, n), we choose the parameter and run 100 experiments. When the iterates stagnate at a local minimizer , we perform a blockwise inspection with each block consisting of two coordinates. Checking all pairs of two coordinates is expensive and not necessary since is sparse. We improve the efficiency by pairing only i, j where . Similar to previous experiments, we sample points from the outer of the 2D ball toward the inner. We choose . The results are presented in Table 1 and Figure 10. CDI shows a significant improvement over its competitors.

3.5 Nonconvex Sparse Logistic Regression

Logistic regression is a widely-used model for classification. Usually we are given a set of training data , where and . The label y is assumed to satisfy the following conditional distribution:

Table 1 Statistics of 100 compressed sensing problems solved by three

1. half : iterative half thresholding; CD: coordinate descent; CDI: CD with inspection.

2. a is the ratio of correctly identified nonzeros to true nonzeros, averaged over the 100 tests (100% is impossible due to noise and model error); b is the number of tests with all true nonzeros identified; c is the number of tests in which the returned points yield lower objective values than that of the true signal (only model error, no algorithm error). Higher a, b, c are better.

3. “ave obj” is the average of the objective values; lower is better.

Fig. 10 Comparison of the true signal x and signals recovered from half, CD, CDI.

In one experiment, CDI recovered all positions of nonzeros of x, while CD failed to recover algorithm just got stuck at a local minizer far from x.

which is convex and differentiable. When N is relatively small, we need variable selection to avoid over-fitting. In this test, we use the minimax concave penalty (MCP) [28]:

The penalty is proximable with

where . We apply the prox-linear (PL) algorithm to solve this problem. When it nearly converges, inspection is then applied. We design our experiments according to [20]: we consider d = 50 and N = 200 and

assume the true has K non-zero entries. In the training procedure, we generate data from i.i.d. standard Gaussian distribution, and we randomly choose K non-zero elements with i.i.d standard Gaussian distribution to form . The labels are generated by , where w is sampled according to the Gaussian distribution . We use PL iteration with and without inspection to recover . After that, we generate 1000 random test data points to compute the test error of the . We set the parameter and the step size 0.5 for PL iteration. For each K and , we run 100 experiments and calculate the mean and variance of the results. The inspection parameters are , and . The sample points in inspections are similar to those in section 3.4. The results are presented in Table 2. The objective values and test errors of PLI, the PL algorithm with inspection, are significantly better than the native PL algorithm. On the other hand, the cost is also 3 – 6 times as high.

Table 2 Sparse logistic regression results of 100 tests. PL is the prox-linear algorithm. PLI is the PL algorithm with inspection. “var” is variance.

We plot the convergence history of the objective values in one trial and the recovered in Figure 11. It is clear that the inspection works in learning a better by reaching a smaller objective value.

Fig. 11 Sparse logistic regression result in one trial.

4 Conclusions

In this paper, we have proposed a simple and efficient method for nonconvex optimization, based on our analysis of R-local minimizers. The method applies local inspections to escape from local minimizers or verify the current point is an R-local minimizer. For a function that can be implicitly decomposed to a smooth, strongly convex function plus a restricted nonconvex functions, our method returns an (approximate) global minimizer. Although some of the tested problems may not possess the assumed decomposition, numerical experiments support the effectiveness of the proposed method.

Reference

1. Chaudhari, P., Choromanska, A., Soatto, S., LeCun, Y.: Entropy-SGD: Biasing gradient descent into wide valleys. arXiv preprint arXiv:1611.01838 (2016)

2. Chaudhari, P., Oberman, A., Osher, S., Soatto, S., Carlier, G.: Deep relaxation: Partial differential equations for optimizing deep neural networks. arXiv preprint arXiv:1704.04932 (2017)

3. Conn, A.R., Gould, N.I., Toint, P.L.: Trust region methods. SIAM (2000)

4. Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. No. 8 in MPS-SIAM series on optimization. Society for Industrial and Applied Mathematics / Mathematical Programming Society, Philadelphia (2009)

5. Fox, J.: An R and S-Plus Companion to Applied Regression. Sage Publications, Thousand Oaks, Calif (2002) 6. Ge, R., Huang, F., Jin, C., Yuan, Y.: Escaping from saddle points—online stochastic gradient for tensor decompo- sition. In: Conference on Learning Theory, pp. 797–842 (2015)

7. Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. In: Advances in Neural Information Processing Systems, pp. 2973–2981 (2016)

8. Ghadimi, S., Lan, G.: Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathe- matical Programming 156(1-2), 59–99 (2016)

9. Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.I.: How to escape saddle points efficiently. arXiv preprint arXiv:1703.00887 (2017)

11. Kirkpatrick, S., Gelatt Jr, C.D., Vecchi, M.P.: Optimization by simulated annealing. In: Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications, pp. 339–348. World Scientific (1987)

12. Martínez, J.M., Raydan, M.: Cubic-regularization counterpart of a variable-norm trust-region method for uncon- strained minimization. Journal of Global Optimization 68(2), 367–385 (2017)

13. Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Mathematical Programming 108(1), 177–205 (2006)

14. Panageas, I., Piliouras, G.: Gradient descent converges to minimizers: The case of non-isolated critical points. CoRR, abs/1605.00405 (2016)

15. Pascanu, R., Dauphin, Y.N., Ganguli, S., Bengio, Y.: On the saddle point problem for non-convex optimization. arXiv preprint arXiv:1405.4604 (2014)

16. Peng, Z., Wu, T., Xu, Y., Yan, M., Yin, W.: Coordinate friendly structures, algorithms and applications. Annals of Mathematical Sciences and Applications 1(1), 57–119 (2016)

17. Polyak, B.T.: Gradient methods for minimizing functionals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 3(4), 643–653 (1963)

18. Reddi, S.J., Hefny, A., Sra, S., Poczos, B., Smola, A.: Stochastic variance reduction for nonconvex optimization. In: International conference on machine learning, pp. 314–323 (2016)

19. Sagun, L., Bottou, L., LeCun, Y.: Singularity of the Hessian in deep learning. arXiv preprint arXiv:1611.07476 (2016)

designed for accessibility and to further open science