Acceleration Methods

Abstract

This monograph covers some recent advances in a range of acceleration techniques frequently used in convex optimization. We first use quadratic optimization problems to introduce two key families of methods, namely momentum and nested optimization schemes. They coincide in the quadratic case to form the Chebyshev method. We discuss momentum methods in detail, starting with the seminal work of Nesterov and structure convergence proofs using a few master templates, such as that for optimized gradient methods, which provide the key benefit of showing how momentum methods optimize convergence guarantees. We further cover proximal acceleration, at the heart of the Catalyst and Accelerated Hybrid Proximal Extragradient frameworks, using similar algorithmic patterns. Common acceleration techniques rely directly on the knowledge of some of the regularity parameters in the problem at hand. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates while adapting to unobserved regularity parameters.

Published in Foundation and Trends in Optimization (see https://www.nowpublishers.com/article/Details/OPT-036)

References in corpus (15)

• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• A Variational Perspective on Accelerated Methods in Optimization
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Optimized first-order methods for smooth convex minimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• A Generalized Accelerated Composite Gradient Method: Uniting Nesterov's Fast Gradient Method and FISTA
• Generalizing the optimized gradient method for smooth convex minimization
• An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems
• Adaptive Restart of the Optimized Gradient Method for Convex Optimization
• On the convergence analysis of the optimized gradient method
• Efficient First-order Methods for Convex Minimization: a Constructive Approach
• Automated Worst-Case Performance Analysis of Decentralized Gradient Descent

Cited by in corpus (8)

• A systematic approach to Lyapunov analyses of continuous-time models in convex optimization
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• Nesterov Acceleration for Ensemble Kalman Inversion and Variants
• NLTGCR: A class of Nonlinear Acceleration Procedures based on Conjugate Residuals
• Snacks: a fast large-scale kernel SVM solver
• A feasible smoothing accelerated projected gradient method for nonsmooth convex optimization
• About some works of Boris Polyak on convergence of gradient methods and their development
• Accelerated-gradient-based generalized Levenberg--Marquardt method with oracle complexity bound and local quadratic convergence