Adaptive Restart for Accelerated Gradient Schemes

By Brendan O'Donoghue, E.J. Candes. 2012

834 citations recorded by the source corpus.

In this paper we introduce 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 at each iteration. 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. Separately, it is known that the optimal restart interval is proportional to this same quantity. This suggests a restart technique whereby we reset the momentum whenever we observe periodic behavior. We provide a heuristic analysis that suggests that in many cases adaptively restarting allows us to recover the optimal rate of convergence with no prior knowledge of function parameters.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Physics

Citations in the corpus

Lookahead Optimizer: k steps forward, 1 step back (2019, methodology): “We follow the approach of [31] and model the optimization of this function as a linear dynamical system allowing us to compute the rate exactly.”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, methodology): “Thus, we require a method to estimate the strong convexity parameter, which is challenging [60, 64].”
A Lyapunov Analysis of Momentum Methods in Optimization (2016, result): “Therefore, and we have the following convergence rate guarantee which is the same convergence rate as the quasi-monotone subgradient method (21).”
Privacy-Preserving Stochastic Gradual Learning (2018, background): “ is highly related to the regularization intensity , privacy parameter "s and dimension d. Note that, the convergence rate of PRESTIGE can be further sped up with Nesterovs accelerated strategy [44,45], which will be discussed in our future work. Proof. According to the update rule of PRESTIGE,”
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update (2014, methodology): “Maintaining the monotonicity of F(xk) can significantly improve the numerical performance of the algorithm, as shown in our numerical results below and also in [46,60].”
A variational perspective on accelerated methods in optimization (2016, background): “Thus, the eﬀect of moving from a ﬁrst-order gradient ﬂow to a second-order Lagrangian ﬂow is to reduce the friction from inﬁnity to a ﬁnite amount; this permits oscillation [30, 32, 17], but also allows faster convergence.”
Linear convergence of first order methods for non-strongly convex optimization (2015, background): “the algorithm (FGM) has the following convergence rate [3,19]:”
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights (2014, methodology): “Among many approaches to gain acceleration via adaptively estimating μ/L, [15] proposes a restarting procedure for Nesterov’s scheme in which (1.”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, methodology): “Such a rippling behavior is normal for the accelerated methods, for example, as studied in (Odonoghue and Candes, 2015).”
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (2013, methodology): “’ There are several other methods that share similar characteristics, such as [55–62], as well as some techniques for solving the split-feasibility problem [35].”
On Accelerated Methods in Optimization (2015, result): “This point of view is also consistent with the work [11], who addressed this oscillation issue by a restart scheme (cf.”