Global convergence of the Heavy-ball method for convex optimization

Introduction

First-order convex optimization methods have a rich history dating back to 1950’s Hestenes:52 ; Frank:56 ; KjA:58 . Recently, these methods have attracted significant interest, both in terms of new theory Devolder:13 ; GuN:14 ; DrT:14 and in terms of applications in numerous areas such as signal processing BeT:09 , machine learning Xia:14 and control NeN:14 . One reason for this renewed interest is that first-order methods have a small per-iteration cost and are attractive in large-scale and distributed settings. But the development has also been fuelled by the development of accelerated methods with optimal convergence rates Nes:83 and re-discovery of methods that are not only order-optimal, but also have optimal convergence times for smooth convex problems Pol:64 . In spite of all this progress, some very basic questions about the achievable convergence speed of first-order convex optimization methods are still open DrT:14 .

The basic first-order method is the gradient descent algorithm. For unconstrained convex optimization problems with objective functions that have Lipschitz-continuous gradient, the method produces iterates that are guaranteed to converge to the optimum at the rate $\mathcal{O}(1/k)$ where $k$ is the number of iterations. When the objective function is also strongly convex, the iterates are guaranteed to converge at a linear rate Pol:87 .

In the early 1980’s, Nemirovski and Yudin NeY:83 proved that no first-order method can converge at a rate faster than $\mathcal{O}(1/k^{2})$ on convex optimization problems with Lipschitz-continuous gradient. This created a gap between the guaranteed convergence rate of the gradient method and what could potentially be achieved. This gap was closed by Nesterov, who presented an accelerated first-order method that converges as ${\mathcal{O}}(1/k^{2})$ Nes:83 . Later, the method was generalized to also attain linear convergence rate for strongly convex objective functions, resulting in the first truly order-optimal first-order method for convex optimization Nes:04 . The accelerated first-order methods combine gradient information at the current and the past iterate, as well as the iterates themselves Nes:04 . For strongly convex problems, Nesterov’s method can be tuned to yield a better convergence factor than the gradient iteration, but it is not known how small the convergence factor can be made.

When the objective function is twice continuously differentiable, strongly convex and has Lipschitz continuous gradient, the Heavy-ball method by Polyak Pol:64 has linear convergence rate and better convergence factor than both the gradient and Nesterov’s accelerated gradient method. The Heavy-ball method uses previous iterates when computing the next, but in contrast to Nesterov’s method it only uses the gradient at the current iterate. Extensions of the Heavy-ball method to constrained and distributed optimization problems have confirmed its performance benefits over the standard gradient-based methods GsJ:13 ; ObP:14a ; Wang:14 .

On the other hand, when the objective function is not necessary convex but has Lipschitz continuous gradient, Zavriev et al. ZaK:93 provided sufficient conditions for the Heavy-ball trajectories to converge to a stationary point. However, there are virtually no results on the rate of convergence of the Heavy-ball method for convex problems that are not necessarily twice-differentiable. Recently, Lessard et al LRP:14 showed by an example that the Heavy-ball method does not necessarily converge on strongly convex (but not twice differentiable) objective functions even if one chooses step-size parameters according to Polyak’s original stability criterion. In general, it is not clear whether the Heavy-ball method performs better than Nesterov’s method, or even the basic gradient descent when the objective is not twice continuously differentiable.

The aim of this paper is to contribute to a more complete understanding of first-order methods for convex optimization. We provide a global convergence analysis for the Heavy-ball method on convex optimization problems with Lipschitz-continuous gradient, with and without the additional assumption of strong convexity. We show that if the parameters of the Heavy-ball method are chosen within certain ranges, the running average of the iterates converge to the optimal point at the rate $\mathcal{O}(1/k)$ when the objective function has Lipschitz continuous gradient. Moreover, for the same class of problems, we are able to show that the individual iterates themselves converge at rate $\mathcal{O}(1/k)$ if the Heavy-ball method uses (appropriately chosen) time-varying step-sizes. Finally, if the cost function is also strongly convex, we show that the iterates converge at a linear rate.

The rest of the paper is organized as follows. Section 2 reviews first-order convex optimization algorithms. Global convergence proofs for the Heavy-ball method are presented in Section 3 for objective functions with Lipschitz continuous gradient and in Section 4 for objective functions that are also strongly convex. Concluding remarks are given in Section 5.

Background

We consider unconstrained convex optimization problems on the form

then, we say that $f$ belongs to $\mathcal{S}^{1,1}_{\mu,L}$.

Our baseline first-order method is gradient descent:

where $\alpha$ is a positive step-size parameter. Let $x^{\star}$ be an optimal point of (1) and $f^{\star}=f(x^{\star})$. If $f\in$ $\mathcal{F}^{1,1}_{L}$, then $f(x_{k})-f^{\star}$ associated with the sequence $\{x_{k}\}$ in (2) converges at rate $\mathcal{O}(1/k)$. On the other hand, if $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$, then the sequence $\{x_{k}\}$ generated by the gradient descent method converges linearly, i.e., there exists $q\in[0,1)$ such that

The scalar $q$ is called the convergence factor. The optimal convergence factor for $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$is $q=(L-\mu)/(L+\mu)$, attained for $\alpha=2/(L+\mu)$ Pol:87 .

The convergence of the gradient iterates can be accelerated by accounting for the history of iterates when computing the ones to come. Methods in which the next iterate depends not only on the current iterate but also on the preceding ones are called multi-step methods. The simplest multi-step extension of gradient descent is the Heavy-ball method:

for constant parameters $\alpha>0$ and $\beta>0$ Pol:87 . For the class of twice continuously differentiable strongly convex functions with Lipschitz continuous gradient, Polyak used a local analysis to derive optimal step-size parameters and to show that the optimal convergence factor of the Heavy-ball iterates is $(\sqrt{L}-\sqrt{\mu})/(\sqrt{L}+\sqrt{\mu})$. This convergence factor is always smaller than the one associated with the gradient iterates, and significantly so when the Hessian of the objective function is poorly conditioned. Note that this local analysis requires twice differentiability of the objective functions, and is, therefore, not valid for all $f\in$ $\mathcal{F}^{1,1}_{L}$nor for all $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$.

In contrast, Nesterov’s fast gradient method Nes:04 is a first-order method with better convergence guarantees than the basic gradient method for objectives in $\mathcal{F}^{1,1}_{L}$and $\mathcal{S}^{1,1}_{\mu,L}$classes. In it’s simplest form, Nesterov’s algorithm with constant step-sizes takes the form

When $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$, the iterates produced by (4) with $\beta=(\sqrt{L}-\sqrt{\mu})/(\sqrt{L}+\sqrt{\mu})$ converge linearly towards the optimal point with a convergence factor $1-\sqrt{\mu/L}$. This factor is smaller than that of the gradient, but larger than that of the Heavy-ball method for twice-differentiable cost functions.

In this section, we consider the Heavy-ball iterates (3) for the objective functions $f\in$ $\mathcal{F}^{1,1}_{L}$. Our first result shows that the method is indeed guaranteed to converge globally and estimates the convergence rate of the Cesáro averages of the iterates.

Assume that $f\in$$\mathcal{F}^{1,1}_{L}$and that

Then, the sequence $\{x_{k}\}$ generated by Heavy-ball iteration (3) satisfies

where $\overline{x}_{T}$ is the Cesáro average of the iterates, i.e.,

Since $f\in$ $\mathcal{F}^{1,1}_{L}$, it follows from (Nes:04, , Theorem 2.1.5) that

Substituting the above inequalities into (10) yields

where $\lambda\in(0,1]$ is a parameter which we will use to balance the weights between the first two inequities in (11). Collecting the terms in the preceding inequality, we obtain

Note that when $\alpha\in[0,(2-\lambda)(1-\beta)/L]$, the last term of (12) becomes non-positive and, therefore, can be eliminated from the right-hand-side. Summing (12) over $k=0,\ldots,T$ gives

Additionally, according to (Nes:04, , Lemma 1.2.3), $f(x_{0})-f^{\star}\leq(L/2)\|x_{0}-x^{\star}\|^{2}$. The proof is completed by replacing this upper bound in (14) and setting $\lambda=1$ for \alpha\in\bigl{(}0,(1-\beta)/L\bigr{]} and $\lambda=2-(\alpha L)/(1-\beta)$ for \alpha\in\bigl{[}(1-\beta)/L,2(1-\beta)/L\bigr{)}. ∎

A few remarks regarding the results of Theorem 3.1 are in order: first, a similar convergence rate can be proved for the minimum function values within $T$ number of Heavy-ball iterates. More precisely, the sequence $\{x_{k}\}$ generated by (3) satisfies

Note that this convergence factor is always smaller than the one for the gradient descent method obtained by setting $\beta=0$ in (8), i.e.,

Finally, setting $\bar{\alpha}=1/L$ in the preceding upper bounds, we see that the factors coincide and equal the best convergence factor of the gradient descent method reported in BeT:09 .

Next, we show that our analysis can be strengthened when we use (appropriately chosen) time-varying step-sizes in the Heavy-ball method. In this case, the individual iterates $x_{k}$ (and not just their running average) converge with rate $\mathcal{O}(1/k)$.

Assume that $f\in$$\mathcal{F}^{1,1}_{L}$and that

where $\alpha_{0}\in(0,1/L]$. Then, the sequence $\{x_{k}\}$ generated by Heavy-ball iteration (3) satisfies

which together with the inequalities in (10) implies that

Summing this inequality over $k=0,\ldots,T$ gives

To illustrate our results, we evaluate the gradient method and the two variations of the Heavy-ball method on a numerical example. In this example, the objective function is the Moreau proximal envelope of the function $f(x)=(1/c)\|x\|$:

For objective functions $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$, it is possible to use constant step-sizes in Nesterov’s method and still guarantee a linear rate of convergence Nes:04 . For the objective functions on the class $\mathcal{F}^{1,1}_{L}$, however, to the best of our knowledge no convergence result exists for Nesterov’s method with fixed step-sizes. Using a similar analysis as in the previous section, we can derive the following convergence rate bound.

Assume that $f\in$$\mathcal{F}^{1,1}_{L}$and that $\beta\in[0,1)$. Then the sequence $\{x_{k}\}$ generated by Nesterov’s iteration (4) satisfies

Considering (4) and substituting the $y$-th iterates in the $x$-th iterates yields

After rearrangement of terms, we thus have

Multiplying the sides of (20) in $L/2$ and summing over $k=0,\ldots,T$ gives

Using the convexity inequality (13) concludes the proof. ∎

Recently, Allen-Zou and Orrechia ZhO:14 demonstrated that another fast gradient method due to Nesterov Nesterov:13 converges with constant step-sizes for all $f\in$ $\mathcal{F}^{1,1}_{L}$. That method generates iterates in the following manner

where $\tau\in$, and $V_{x}(\cdot)$ is the Bergman divergence function ZhO:14 .Similar to Theorem 3.3, it has been shown in ZhO:14 that the Cesáro average of the iterates generated by (21) converges to the optimum at a rate of $\mathcal{O}(1/k)$. Note that while both iterations (4) and (21) enjoy the same global rate of convergence, the two schemes are remarkably different computationally. In particular, (21) requires two gradient computations per iteration, as opposed to one gradient computation needed in (4).

In this section, we focus on objective functions in the class $\mathcal{S}^{1,1}_{\mu,L}$and derive a global linear rate of convergence for the Heavy-ball algorithm. In our convergence analysis, we will use the following simple lemma on convergence of sequences.

Let $\{A_{k}\}_{k\geq 0}$ and $\{B_{k}\}_{k\geq 0}$ be nonnegative sequences of real numbers satisfying

Then, the sequence $\{A_{k}\}_{k\geq 0}$ generated by (22) satisfies

It is easy to check that (23) holds for $k=0$. Let $\gamma\geq 0$. From (22), we have

The first term in (25) along with $\gamma\geq 0$ is equivalent to have $(-a_{1}+\sqrt{a_{1}^{2}+4a_{2}})/2\leq\gamma$. Moreover, the second condition in (25) can be rewritten as $c/b-a_{1}\leq\gamma$. Thus, if

then (25) holds. Denoting $q\triangleq a_{1}+{\gamma}<1$ , it follows from (24) that

Since $A_{t}$ and $B_{t+1}$ are nonnegative, (23) holds. The proof is complete.

We are now ready for the main result in this section.

Assume that $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$and that

Then, the Heavy-ball method (3) converges linearly to a unique optimizer $x^{\star}$. In particular,

Moreover, since $f$ belongs to $\mathcal{F}^{1,1}_{L}$, it follows from (Nes:04, , Theorem 2.1.5) and (3) that

Let $\theta\in(0,1)$, multiply both sides of (29) by $L\theta/(2-2\theta)$, and add the resulting identity to (30) to obtain

Assume that $(1-\theta)/L\leq\alpha<2(1-\theta)/L$. Then, since $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$, it follows from (Nes:04, , Theorem 2.1.10) that

which is on the form of Lemma 1 if we identify $A_{k}$ with $f(x_{k})-f^{\star}$ and $B_{k}$ with $\|x_{k}-x^{\star}\|^{2}$. It is easy to verify that for $\theta\in(0,1)$ and $(1-\theta)/L\leq\alpha<2(1-\theta)/L$, one has

it holds that $c<b$ and consequently one can apply Lemma 1 with constants $a_{1},a_{2},b$, and $c$ to conclude the linear convergence (28). Defining $\lambda\triangleq 1-\theta$ the stability criteria reads

The first two conditions can be rewritten as

Substituting $\lambda=\alpha L/2$ into the upper stability bound on $\beta$ completes the proof. ∎

This result extends earlier theoretical results for $\mathcal{S}^{2,1}_{L,\mu}$ to $\mathcal{S}^{1,1}_{\mu,L}$and demonstrates that the Heavy-ball method has the same rate of convergence as the gradient method and Nesterov’s fast gradient method for this class of objective functions. A few comments regarding our stability criteria (27) are in order.

First, we observe that (27) guarantees stability for a wider range of parameters than the stability criteria (5) for $f\in$ $\mathcal{F}^{1,1}_{L}$, and wider ranges of parameters than the stability analysis of the Heavy-ball method for non-convex cost functions presented in ZaK:93 . In particular, when $\alpha$ tends to $2/L$, our stability criterion allows $\beta$ to be as large as $\mu/L$, whereas the stability condition (5) requires that $\beta$ tends to zero when $\alpha$ reaches $2/L$; see Fig. 2.

Second, by comparing (27) with $\alpha$ and $\beta$ that guarantee stability for twice differentiable strongly convex functions Pol:87 :

our stability criteria may appear restrictive at first. However, motivated by LRP:14 , we consider a counter example where the original stability criteria (33) for twice differentiable strongly convex functions do not hold for the class $\mathcal{S}^{1,1}_{\mu,L}$. In particular, let us consider

It is easy to check that $\nabla f$ is continuous and $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$with $\mu=5$ and $L=50$. According to our numerical tests, for initial conditions in the interval $x_{0}<-0.8$ or $x_{0}>0.15$, the Heavy-ball method with parameters $\alpha^{\star}=4/(\sqrt{L}+\sqrt{\mu})^{2}$ and $\beta^{\star}=(\sqrt{L}-\sqrt{\mu})^{2}/(\sqrt{L}+\sqrt{\mu})^{2}$ (the optimal step-sizes for the class $\mathcal{S}^{2,1}_{L,\mu}$ in Pol:87 ) produces non-converging sequences. However, Fig. 3 shows that using the maximum value of $\alpha$ permitted by our global analysis results in iterates that converge to the optimum.

Finally, note that Lemma 1 also provides an estimate of the convergence factor of the iterates. In particular, after a few simplifications one can find that when

and $\theta=1-\alpha L$ in (32), the convergence factor of the Heavy-ball method (3) is given by $q=1-\alpha\mu$. Note that this factor coincides with the best known convergence factor for the gradient method on $\mathcal{S}^{1,1}_{\mu,L}$ (Pol:87, , Theorem 2, Chapter 1). However, supported by the numerical simulations we envisage that the convergence factor could be strengthened even further. This is indeed left as a future work.

CONCLUSIONS

Global stability of the Heavy-ball method has been established for two important classes of convex optimization problems. Specifically, we have shown that when the objective function is convex and has a Lipschitz-continuous gradient, then the Cesáro-averages of the iterates converge to the optimum at a rate no slower than $\mathcal{O}(1/k)$, where $k$ is the number of iterations. When the objective function is also strongly convex, we established that the Heavy-ball iterates converge linearly to the unique optimum.

In our future work, we hope to extend the present results to the constrained optimization problems and derive sharper bounds on the guaranteed convergence factor when $f\in$ $\mathcal{S}^{1,1}_{\mu,L}$.

References