Iteration Complexity of Fixed-Step-Momentum Methods for Convex Quadratic Functions

Melinda Hagedorn, Florian Jarre

Published 2022-11-18Version 1

This note considers the momentum method without line search but with fixed step length applied to strictly convex quadratic functions assuming that exact gradients are used and appropriate upper and lower bounds for the extreme eigenvalues of the Hessian matrix are known. Simple 2-d-examples show that the Euclidean distance of the iterates to the optimal solution is non-monotone. In this context an explicit bound is derived on the number of iterations needed to guarantee a reduction of the Euclidean distance to the optimal solution by a factor $\varepsilon$. The bound is optimal up to a constant factor and complements earlier asymptotically optimal results.