A note on R-linear convergence of nonmonotone gradient methods

Publication date 12 July 2022

Abstract: Nonmonotone gradient methods generally perform better than their monotone counterparts especially on unconstrained quadratic optimization. However, the known convergence rate of the monotone method is often much better than its nonmonotone variant. With the aim of shrinking the gap between theory and practice of nonmonotone gradient methods, we introduce a property for convergence analysis of a large collection of gradient methods. We prove that any gradient method using stepsizes satisfying the property will converge

R

-linearly at a rate of

1 - l a m b d a_{1} / M_{1}

, where

l a m b d a_{1}

is the smallest eigenvalue of Hessian matrix and

M_{1}

is the upper bound of the inverse stepsize. Our results indicate that the existing convergence rates of many nonmonotone methods can be improved to

1 - 1 / k a p p a

with

k a p p a

being the associated condition number.

This page was built for publication: A note on $R$-linear convergence of nonmonotone gradient methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404784)