A note on $R$-linear convergence of nonmonotone gradient methods

We concentrate on analyzing the convergence rate of gradient methods for unconstrained quadratic optimization:

where $A\in\mathbb{R}^{n\times n}$ is a real symmetric positive definite matrix and $b\in\mathbb{R}^{n}$. The gradient method solves (1) by

where $g_{k}=\nabla f(x_{k})$ and $\alpha_{k}>0$ is the stepsize. By considering the generated function values, we can roughly divided gradient methods into two categories: monotone and nonmonotone.

The classic steepest descent (SD) method developed by Cauchy cauchy1847methode is monotone, which determines the stepsize by exact line search:

It is known that the SD method converges $Q$-linearly at a rate of $\frac{\kappa-1}{\kappa+1}$ akaike1959successive ; forsythe1968asymptotic , where $\kappa=\lambda_{n}/\lambda_{1}$ is the condition number of $A$ with $\lambda_{1}$ and $\lambda_{n}$ being the smallest and largest eigenvalues, respectively. In a similar spirit to the SD method, the minimal gradient (MG) method dai2003altermin calculates the stepsize by minimizing the gradient norm, i.e.

This method is also monotone and has the same convergence speed as the SD method huang2019asymptotic . Another monotone method is due to Dai and Yang dai2006new2 whose stepsize is given by

It is proved that $\alpha_{k}^{AOPT}$ asymptotically converges to $\frac{2}{\lambda_{1}+\lambda_{n}}$, which is in some sense an optimal stepsize since it minimizes $\|I-\alpha A\|$ over $\alpha$, see dai2006new2 ; elman1994inexact . The Dai–Yang method (5) also converges $Q$-linearly at the same rate as the SD method dai2006new2 . See dai2003altermin ; dai2005analysis ; yuan2006new ; yuan2008step and references therein for other monotone gradient methods.

The Barzilai–Borwein (BB) methods barzilai1988two can be viewed as nonmonotone counterparts of the SD and MG methods since

and

where $s_{k-1}=x_{k}-x_{k-1}$ and $y_{k-1}=g_{k}-g_{k-1}$. Clearly, $\alpha_{k}^{BB1}\geqslant\alpha_{k}^{BB2}$ for the quadratic function (1). An interesting property of the above two BB stepsizes is that they satisfy the quasi-Newton secant equation in the sense of least squares:

For the BB2 method, a surprising $R$-superlinear convergence result on the two dimensional strictly convex quadratic function is presented in barzilai1988two , which is improved by Dai dai2013new for the BB1 method. Dai and Fletcher dai2005asymptotic showed similar $R$-superlinear convergence for the BB1 method in the three dimensional case. As for the $n$ dimensional case, Raydan raydan1993barzilai established global convergence of the BB1 method while Dai and Liao dai2002r proved that it converges $R$-linearly and the rate is roughly $(1-1/\kappa)^{1/n}$. Recently, Li and Sun li2021on improved the above rate to $1-1/\kappa$. A nonmonotone version of the Dai–Yang method using $\alpha_{k-1}^{AOPT}$ can be found in dai2015positive which is also $R$-superlinear convergent on two dimensional strictly convex quadratics.

Interestingly, the above mentioned nonmonotone methods are generally much faster than the corresponding monotone ones especially for quadratics. Moreover, those nonmonotone methods have a great advantage of easy extension to general unconstrained problems BDH2019stabilized ; dai2019family ; di2018steplength ; fletcher2005barzilai ; huang2020equipping ; raydan1997barzilai , to constrained optimization birgin2000nonmonotone ; crisci2020spectral ; dai2005asymptotic ; dai2005projected ; huang2020equipping ; huang2016smoothing and to various applications dai2015positive ; huang2020gradient ; huang2015quadratic ; jiang2013feasible ; tan2016barzilai ; wang2007projected . However, theoretical analysis of a nonmonotone method is generally much more difficult due to the nonmonotonity. In recent years, to achieve good performance, long and short stepsizes are often employed in alternate, cyclic, adaptive, or hybrid way by nonmonotone gradient methods dai2005projected ; de2014efficient ; frassoldati2008new ; huang2020equipping ; sun2020new ; zhou2006gradient which makes the analysis even more difficult. Consequently, the known convergence rate of a nonmonotone method is often much worse than its monotone counterpart.

An important tool for analyzing the convergence of nonmonotone methods is the following Property A suggested by Dai dai2003alternate .

Property A: Assume that $A=\operatorname{diag}\left(\lambda_{1},\cdots,\lambda_{n}\right)$ and $1=\lambda_{1}<\lambda_{2}<\cdots<\lambda_{n}$. Let $g_{k}^{(i)}$ be the $i$-th component of $g_{k}$ and

Suppose that there exist an integer $m$ and positive constants $M_{1}\geqslant\lambda_{1}$ and $M_{2}$ such that
(i) $\lambda_{1}\leqslant\alpha_{k}^{-1}\leqslant M_{1}$
(ii) for any integer $l\in[1,n-1]$ and $\varepsilon>0$, if $P(k-j,l)\leqslant\varepsilon$ and $\left(g_{k-j}^{(l+1)}\right)^{2}\geqslant M_{2}\varepsilon$ hold for $j\in[0,\min\{k,m\}-1]$, then $\alpha_{k}^{-1}\geqslant\frac{2}{3}\lambda_{l+1}$.

Dai dai2003alternate proved that if stepsizes of the gradient method have Property A, then either $g_{k}=0$ for some finite $k$ or the sequence $\left\{\left\|g_{k}\right\|\right\}$ converges to zero $R$-linearly and the rate is roughly $\big{(}\max\{\frac{1}{2},1-\frac{\lambda_{1}}{M_{1}}\}\big{)}^{1/n}$. Such a rate has recently been improved to $\max\{\frac{1}{2},1-\frac{\lambda_{1}}{M_{1}}\}$ huang2021On , and the rate can be further improved to $1-1/\kappa$ for the gradient method with:

where $v(k)\in\{k,k-1,\dots,\max\{k-m+1,1\}\}$ and $\rho(k)\geqslant 0$ is some real number, see friedlander1998gradient . Nevertheless, it is not very straightfoward to check Property A since it requires that for any integer $l$, the inverse stepsize is large enough when the first $l$ eigencomponents of $g_{k}$ are much smaller than the $(l+1)$-th eigencomponent. Moreover, as we will see in the next section some existing stepsize does not satisfy Property A.

In this paper, we introduce a new property, named Property B, for stepsizes of the gradient method which is straightforward and easy to check. We prove that any gradient method with stepsizes satisfying Property B will converge $R$-linearly at a rate of $1-\lambda_{1}/M_{1}$ with $M_{1}$ being the upper bound of the inverse stepsize as above. Our results indicate that gradient methods using retard, alternate, cyclic, adaptive or hybrid stepsize schemes such as the SDC method de2014efficient , the periodic gradient method in huang2019asymptotic and the methods in huang2020acceleration ; sun2020new ; zou2021fast converge $R$-linearly at the above rate. Consequently, when $M_{1}\leqslant\lambda_{n}$ the convergence rate can be refined to $1-1/\kappa$ which implies that the BB1, BB2, alternate BB dai2005projected , adaptive BB zhou2006gradient , cyclic BB dai2006cyclic , cyclic SD dai2005asymptotic , ABBmin frassoldati2008new , BB family dai2019family , and the methods in dai2015positive ; huang2020equipping ; huang2019asymptotic ; huang2020gradient ; huang2020acceleration converge at least $R$-linearly with a rate of $1-1/\kappa$. It is worth to mention that the methods in huang2019asymptotic ; huang2020acceleration satisfy Property B but not necessarily satisfy Property A. In addition, our results generalize the one in li2021on for the BB1 method, and improve those in huang2021On for the method (8) in the sense that the associated quantities in our convergence rate are smaller than or equal to those in huang2021On . We also discuss convergence rates of iterations and function values for gradient methods satisfying the proposed Property B.

The paper is organized as follows. In Section 2, we present Property B and our $R$-linear convergence results. In Section 3 we give some concluding remarks and discuss generalizations of our results.

Since the gradient method (2) is invariant under translations and rotations when applying to the quadratic problem (1), for the convenience of analysis, we assume without loss of generality that the matrix $A$ is diagonal with distinct eigenvalues, i.e.

We shall analyze $R$-linear convergence rate of gradient methods whose stepsizes satisfying the following Property B.

The only difference between Property B here and Property A is condition (ii). For the case $\psi(A)=I$, we can prove that $\alpha_{k}$ satisfies (10) also meets the condition (ii) of Property A with $M_{2}=2$. In fact, for any integer $l\in[1,n-1]$, suppose that $P(k-j,l)\leqslant\varepsilon$ and $\left(g_{k-j}^{(l+1)}\right)^{2}\geqslant 2\varepsilon$ hold for $\varepsilon>0$ and $j\in[0,\min\{k,m\}-1]$, we obtain that

However, if $\psi(A)\neq I$, the following example shows that $\alpha_{k}^{-1}<\frac{2}{3}\lambda_{l+1}$ for a stepsize satisfies (10) even if $P(k-j,l)\leqslant\varepsilon$ and $\left(g_{k-j}^{(l+1)}\right)^{2}\geqslant M_{2}\varepsilon$.

Example 1. Consider the $3$-dimensional quadratic with

We apply the gradient method in huang2020acceleration which uses the stepsize

Here we choose $\psi(z)=\left(\frac{1+2z}{z^{2}}\right)^{2}$ and $\alpha_{0}=\alpha_{0}^{SD}$. For any given $\varepsilon>0$, set $x_{0}=\left(\sqrt{\varepsilon},\frac{\sqrt{40\varepsilon}}{8},\frac{\sqrt{40\varepsilon}}{16}\right)^{T}$. We get

It follows that $\alpha_{0}=\frac{g_{0}^{\top}g_{0}}{g_{0}^{\top}Ag_{0}}\approx 0.084~{}3$ and

which gives $\alpha_{1}=\frac{g_{0}^{\top}\psi^{2}(A)g_{0}}{g_{0}^{\top}A\psi^{2}(A)g_{0}}\approx 0.295~{}8$ and

Then we have $\alpha_{2}\approx 0.705~{}6$ and

Clearly, for $j\in[0,\min\{k,m\}-1]$ with $m=2$, $P(k-j,1)\leqslant\varepsilon$ holds for $k=2,3$. However, for any $M_{2}$ such that $\left(g_{k-j}^{(2)}\right)^{2}\geqslant M_{2}\varepsilon$, we have $\alpha_{2}^{-1}\approx 1.417~{}2<16/3$ and $\alpha_{3}^{-1}\approx 4.832~{}0<16/3$.

Now we present our first convergence result for gradient methods satisfying Property B. See li2021on for analysis of the BB1 method and huang2021On for methods satisfying Property A.

Theorem 2.1 allows us to use various choices of stepsizes for the gradient method. For example, one can use a stepsize such that $v(k)=k-r$ for some integer $r\in[1,m-1]$ and all $k\geqslant r$ which includes BB1, BB2, and the method in dai2015positive as special instances. One may also use alternate, cyclic, adaptive or hybrid stepsize schemes such as the cyclic BB dai2006cyclic , ABBmin frassoldati2008new and SDC de2014efficient methods, the periodic gradient method in huang2019asymptotic and the methods in huang2020gradient ; sun2020new ; zou2021fast . Convergence results for those cases are specified in the next corollary.

Many efficient gradient methods using stepsizes satisfying $\lambda_{1}\leqslant\alpha_{k}^{-1}\leqslant\lambda_{n}$, for example, the BB1, BB2, alternate BB dai2005projected , adaptive BB zhou2006gradient , cyclic BB dai2006cyclic , and cyclic SD dai2005asymptotic methods, BB family dai2019family , and the method in dai2015positive . For such methods, next theorem refines the results in Theorem 2.1 and Corollary 1.

We introduced Property B for gradient methods and proved that any gradient method with stepsizes satisfying this property has $R$-linear convergence rate $1-\lambda_{1}/M_{1}$ where $M_{1}$ is the upper bound of the inverse stepsize. For a large collection of gradient methods, we refined the rate to $1-1/\kappa$. An important advantage of Property B is that it can easily be checked. Our results extend the one in li2021on and partly improve those in huang2021On .

With the notation $G(k,l)=\sum_{i=1}^{l}\left(\psi(\lambda_{i})g_{k}^{(i)}\right)^{2}$, we can generalize Property A in dai2003alternate as the following Property GA.

Clearly, Property GA reduces to Property A when $\psi(A)=I$. Moreover, it is not difficult to check that Property B is a special case of Property GA. By similar arguments as the proof of Theorem 2.1, we can establish $R$-linear convergence rate as (11) for any gradient method using stepsizes satisfying Property GA but with

and $\theta=\max\{\frac{1}{2},1-\frac{\lambda_{1}}{M_{1}}\}$ which is bounded by $\max\{\frac{1}{2},1-\frac{\lambda_{1}}{M}\}$ with $M=\lim\sup_{k\rightarrow\infty}\alpha_{k}^{-1}$. This extends the results in Lemma 2.2 and Theorem 2.1 of huang2021On . Other results in the former section could be obtained for Property GA as well.

All the above results on gradients can be applied to get $R$-linear convergence for iterations and function values. In fact, denote by $x^{*}=A^{-1}b$ the solution of (1) and $e_{k}=x_{k}-x^{*}$. Then we have

and

By applying (11) we obtain

which yield

where $C=(\lambda_{1}^{-1/2}C_{1},\cdots,\lambda_{n}^{-1/2}C_{n})^{T}$. In the same way, we are able to establish $R$-linear convergence for iterations and function values from (15).