Exact gradient methods with memory. (2nd November 2022)

• Record Type: Journal Article
• Authors: Florea, Mihai I.
• Is Part Of: Optimization methods and software. Volume 37:Number 6(2022)
• Page Start: 2324
• Page End: 2351
• Publication Date: 2022-11-02
• Subjects: Gradient method -- bundle -- piece-wise linear model -- acceleration -- Bregman distance -- relative smoothness -- composite problems; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2022.2091559
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: The Inexact Gradient Method with Memory (IGMM) is able to considerably outperform the Gradient Method by employing a piece-wise linear lower model on the smooth part of the objective. However, the auxiliary problem can only be solved within a fixed tolerance at every iteration. The need to contain the inexactness narrows the range of problems to which IGMM can be applied and degrades the worst-case convergence rate. In this work, we show how a simple modification of IGMM removes the tolerance parameter from the analysis. The resulting Exact Gradient Method with Memory (EGMM) is as broadly applicable as the Bregman Distance Gradient Method/NoLips and has the same worst-case rate of O ( 1 / k ), the best for its class. Under necessarily stricter assumptions, we can accelerate EGMM without error accumulation yielding an Accelerated Gradient Method with Memory (AGMM) possessing a worst-case rate of O ( 1 / k 2 ) . In our preliminary computational experiments EGMM displays excellent performance, sometimes surpassing accelerated methods. When the model discards old information, AGMM also consistently exceeds the Fast Gradient Method.