Adaptive Restart for Accelerated Gradient Schemes
arXiv:1204.3982
Abstract
In this paper we demonstrate a simple heuristic adaptive restart technique that can dramatically improve the convergence rate of accelerated gradient schemes. The analysis of the technique relies on the observation that these schemes exhibit two modes of behavior depending on how much momentum is applied. In what we refer to as the 'high momentum' regime the iterates generated by an accelerated gradient scheme exhibit a periodic behavior, where the period is proportional to the square root of the local condition number of the objective function. This suggests a restart technique whereby we reset the momentum whenever we observe periodic behavior. We provide analysis to show that in many cases adaptively restarting allows us to recover the optimal rate of convergence with no prior knowledge of function parameters.
17 pages, 7 figures
References in corpus (1)
Cited by in corpus (12)
- SGDR: Stochastic Gradient Descent with Warm Restarts
- A quasi-Newton proximal splitting method
- From Averaging to Acceleration, There is Only a Step-size
- Learning interactions through hierarchical group-lasso regularization
- Distributed Certifiably Correct Pose-Graph Optimization
- Low-Rank Modeling and Its Applications in Image Analysis
- Accelerated and Inexact Soft-Impute for Large-Scale Matrix and Tensor Completion
- Local and Global Convergence of an Inertial Version of Forward-Backward Splitting
- RAPID: Rapidly Accelerated Proximal Gradient Algorithms for Convex Minimization
- A dual algorithm for a class of augmented convex models
- Adaptive Braking for Mitigating Gradient Delay
- Projected shrinkage algorithm for box-constrained L1-minimization