Gradient methods with memory. (4th May 2022)

• Record Type: Journal Article
• Authors: Nesterov, Yurii; Florea, Mihai I.
• Is Part Of: Optimization methods and software. Volume 37:Number 3(2022)
• Page Start: 936
• Page End: 953
• Publication Date: 2022-05-04
• Subjects: Convex optimization -- gradient methods -- relative smoothness -- rate of convergence -- piece-wise linear model; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1858831
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: In this paper, we consider gradient methods for minimizing smooth convex functions, which employ the information obtained at the previous iterations in order to accelerate the convergence towards the optimal solution. This information is used in the form of a piece-wise linear model of the objective function, which provides us with much better prediction abilities as compared with the standard linear model. To the best of our knowledge, this approach was never really applied in Convex Minimization to differentiable functions in view of the high complexity of the corresponding auxiliary problems. However, we show that all necessary computations can be done very efficiently. Consequently, we get new optimization methods, which are better than the usual Gradient Methods both in the number of oracle calls and in the computational time. Our theoretical conclusions are confirmed by preliminary computational experiments.