A note on the optimal convergence rate of descent methods with fixed step sizes for smooth strongly convex functions

2021/06/15 by Uschmajew, André, Vandereycken, Bart · 1 citation
#90C25 (Primary) 65K05 (Secondary) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2106.08020

Abstract

Based on a result by Taylor, Hendrickx, and Glineur (J. Optim. Theory Appl., 178(2):455--476, 2018) on the attainable convergence rate of gradient descent for smooth and strongly convex functions in terms of function values, an elementary convergence analysis for general descent methods with fixed step sizes is presented. It covers general variable metric methods, gradient related search directions under angle and scaling conditions, as well as inexact gradient methods. In all cases, optimal rates are obtained.

Cited by

• Accelerated Evolving Set Processes for Local PageRank Computation

Related

• Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions
• A Proof of Exact Convergence Rate of Gradient Descent. Part I. Performance Criterion \Vert ∇ f(x_N)\Vert²/(f(x₀)-f_*)
• New insights in smoothness and strong convexity with improved convergence of gradient descent
• A Proof of the Exact Convergence Rate of Gradient Descent
• Provably Faster Gradient Descent via Long Steps