Exact Worst-case Performance of First-order Methods for Composite Convex Optimization

Abstract

We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this worst-case. We achieve this by reducing the computation of the worst-case to solving a convex semidefinite program, generalizing previous works on performance estimation by Drori and Teboulle [13] and the authors [43]. We use these developments to obtain a tighter analysis of the proximal point algorithm and of several variants of fast proximal gradient, conditional gradient, subgradient and alternating projection methods. In particular, we present a new analytical worst-case guarantee for the proximal point algorithm that is twice better than previously known, and improve the standard worst-case guarantee for the conditional gradient method by more than a factor of two. We also show how the optimized gradient method proposed by Kim and Fessler in [22] can be extended by incorporating a projection or a proximal operator, which leads to an algorithm that converges in the worst-case twice as fast as the standard accelerated proximal gradient method [2].

Published in SIOPT (updated version with corrected typo) Code available at https://github.com/AdrienTaylor/Performance-Estimation-Toolbox

References in corpus (3)

• A geometric alternative to Nesterov's accelerated gradient descent
• On the convergence analysis of the optimized gradient method
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems

Cited by in corpus (33)

• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• Acceleration Methods
• Generalizing the optimized gradient method for smooth convex minimization
• On the convergence analysis of the optimized gradient method
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Optimal Complexity and Certification of Bregman First-Order Methods
• Efficient First-order Methods for Convex Minimization: a Constructive Approach
• Optimal Algorithms for Distributed Optimization
• Universal gradient descent
• A systematic approach to Lyapunov analyses of continuous-time models in convex optimization
• Accelerated Proximal Point Method for Maximally Monotone Operators
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• Automated tight Lyapunov analysis for first-order methods
• Automatic Performance Estimation for Decentralized Optimization
• Automated Worst-Case Performance Analysis of Decentralized Gradient Descent
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• Optimal Nonergodic Sublinear Convergence Rate of Proximal Point Algorithm for Maximal Monotone Inclusion Problems
• Automated Performance Estimation for Decentralized Optimization via Network Size Independent Problems
• The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions
• On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities
• Interpolation Constraints for Computing Worst-Case Bounds in Performance Estimation Problems
• Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
• Computer-Assisted Design of Accelerated Composite Optimization Methods: OptISTA
• Optimal First-Order Algorithms as a Function of Inequalities
• A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
• Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses
• Fast Empirical Scenarios
• On the dual step length of the alternating direction method of multipliers
• Convex optimization
• Tight Convergence Rates in Gradient Mapping for the Difference-of-Convex Algorithm
• Manifold Model for High-Resolution fMRI Joint Reconstruction and Dynamic Quantification
• Optimal step length for the Newton method near the minimum of a self-concordant function