Adaptive restart of accelerated gradient methods under local quadratic growth condition

Abstract

By analyzing accelerated proximal gradient methods under a local quadratic growth condition, we show that restarting these algorithms at any frequency gives a globally linearly convergent algorithm. This result was previously known only for long enough frequencies. Then, as the rate of convergence depends on the match between the frequency and the quadratic error bound, we design a scheme to automatically adapt the frequency of restart from the observed decrease of the norm of the gradient mapping. Our algorithm has a better theoretical bound than previously proposed methods for the adaptation to the quadratic error bound of the objective. We illustrate the efficiency of the algorithm on a Lasso problem and on a regularized logistic regression problem.

References in corpus (2)

• Restarting accelerated gradient methods with a rough strong convexity estimate
• Adaptive Accelerated Gradient Converging Methods under Holderian Error Bound Condition

Cited by in corpus (14)

• Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness
• Adaptive Gradient Descent without Descent
• Differentially Private Accelerated Optimization Algorithms
• Practical Perspectives on Symplectic Accelerated Optimization
• Faster Convergence in Deep-Predictive-Coding Networks to Learn Deeper Representations
• On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent
• Restart of accelerated first order methods with linear convergence under a quadratic functional growth condition
• Fast Gradient Methods for Uniformly Convex and Weakly Smooth Problems
• A piecewise conservative method for unconstrained convex optimization
• An adaptive proximal point algorithm framework and application to large-scale optimization
• Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach
• A generic adaptive restart scheme with applications to saddle point algorithms
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization
• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization