Source-linked AI summary
Adaptive Restart for Accelerated Gradient Schemes
Brendan O'Donoghue, Emmanuel Candes
TL;DR
The paper addresses how to obtain fast accelerated convergence without prior knowledge of function parameters, especially when strong convexity is difficult to estimate. It analyzes momentum-dependent behavior and uses observed objective or gradient signals to adaptively restart the method. In many cases, this recovers the optimal linear convergence rate and can accelerate convergence near locally well-conditioned optima, while restart behavior outside the quadratic region remains uncertain.
Problem
Estimating the strong convexity parameter is challenging, and fixed restart intervals depend on global parameters that may be inappropriate in better-conditioned regions.
Method
The paper analyzes accelerated schemes as momentum systems and restarts them when objective or gradient behavior indicates excessive momentum or periodicity.
Results
The technique recovers the optimal linear convergence rate in many cases and can potentially accelerate convergence near the optimum, even without global strong convexity.
Takeaways & Limitations
Adaptive restarting can improve accelerated gradient performance without prior knowledge of function parameters and may exploit locally better-conditioned regions.
Takeaways & Limitations
The effect of restart schemes outside the quadratic region is unclear, and restarting far from the optimum can slightly slow early convergence before rapid linear convergence begins.
Abstract
from arXiv · showhide
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.
1 Introduction
Accelerated gradient methods extend gradient descent with growing momentum, but their nonmonotone behavior motivates adaptive restarting. The paper studies smooth convex optimization and connects ripple periodicity and restart timing to the local condition number.
- Accelerated gradient schemes use momentum whose current step depends on previous iterations, with momentum increasing across iterations.Restarting erases previous-iteration memory and resets momentum to zero.
- Unlike gradient descent, accelerated methods need not decrease the objective at every iteration and can exhibit regular ripples or bumps.The paper associates this behavior with excessive momentum and relates its period to the square root of the local condition number.
- The paper proposes restarting when objective behavior signals periodicity, using the relationship between ripple period and condition number to recover fast convergence in many cases.It also reports that locally well-conditioned regions can admit linear convergence through restarting.
- The methods target smooth convex minimization, where the gradient is Lipschitz continuous with constant L.
2 Accelerated methods
Accelerated schemes achieve optimal rates under suitable parameter choices, but estimating strong convexity is difficult and inaccurate momentum can severely impair convergence. The paper motivates adaptive restart by linking overestimated momentum to ripples and locally changing conditioning.
- Accelerated methods: Accelerated scheme I uses q ∈ [0, 1], and q = 1 recovers gradient descent; q = 0 with t_k = 1/L gives a guaranteed smooth-convex rate.
- Accelerated methods: For strongly convex functions, choosing q = µ/L achieves a linear convergence rate, also obtained by a simpler accelerated scheme.The rate is described as optimal for the relevant first-order complexity bounds.
- Robustness: Optimal convergence is guaranteed only when µ and L are known, while estimating the strong convexity parameter µ is particularly challenging.Using q = 0 can dramatically slow convergence when the function is strongly convex.
- Robustness: Slightly over- or underestimating q⋆ can severely harm convergence; overestimation yields monotone convergence, whereas underestimation produces regular ripples or bumps.
- Robustness: When q = 0, momentum approaches one, creating high-momentum rippling behavior; this can emerge near the optimum even with globally optimal q because conditioning is local.
3 Restarting
Fixed restarting resets momentum at a chosen interval and can achieve the optimal linear convergence rate, but its interval depends on unknown parameters and may not suit locally better-conditioned regions. Adaptive schemes instead use inexpensive observations of function or gradient behavior to decide when to restart.
- 3.1 Fixed restart: Fixed restarting resets momentum every k iterations, using the latest iterate as the new starting point.Restarting erases the algorithm’s previous memory and sets momentum to zero.
- 3.1 Fixed restart: O(sqrt(L/µ) log(1/ε)) iterations achieve the optimal linear convergence rate with an appropriately chosen fixed restart interval.The interval is selected by jointly optimizing the total iteration bound over restart length and outer iterations.
- 3.1 Fixed restart: Fixed restart intervals depend on unknown L and µ and may be inappropriate in regions that are better conditioned than the global function.A global interval cannot automatically adapt when the sequence enters a locally better-conditioned region.
- 3.2 Adaptive restart: Adaptive restart uses cheap observations to decide whether to restart, with separate function-based and gradient-based schemes.The proposed schemes are motivated by periodic or unfavorable momentum behavior.
- 3.2 Adaptive restart: The gradient scheme performs similarly to the function scheme while potentially improving numerical stability near the optimum and requiring no extra computation.Its quantities are already calculated in accelerated schemes.
- 3.2 Adaptive restart: Restarting resets momentum and prevents the characteristic spiralling behavior in the two-dimensional trajectories.Figure 4 compares trajectories under scheme I and with adaptive restart.
4 Analysis
The analysis models accelerated gradient on a convex quadratic as independent eigenmode dynamical systems, revealing low- and high-momentum regimes. High momentum produces periodicity tied to the local condition number, which adaptive restarting exploits to recover optimal convergence without knowing µ.
- Linear dynamical system: The quadratic analysis uses a fixed step size and constant momentum, then decomposes the dynamics into independently evolving eigenvector modes.The update is expressed in the eigenbasis of A, with each mode governed by its own recurrence.
- Convergence regimes: The critical momentum value separates over-damped low-momentum dynamics from under-damped high-momentum dynamics with complex characteristic roots.Low momentum gives slow monotone convergence, whereas high momentum produces periodicity.
- Observable periodicity: High-momentum oscillations have a frequency proportional to the square root of µ/L, so their period reflects the local condition number.The function value becomes dominated by the smallest-eigenvalue mode, making its oscillations observable through function values or gradients.
- Adaptive restart: Starting from zero momentum, the adaptive schemes enter the oscillatory regime and detect a restart after an additional approximately (π/2)√(L/µ) iterations.Restarting resets β_k to zero, repeating the process.
- Adaptive restart: The resulting restart interval guarantees accuracy ϵ within O(√(L/µ) log(1/ϵ)) iterations, recovering the optimal linear convergence rate without prior knowledge of µ.The argument applies when the objective is locally well approximated by a quadratic.
- Scope: Outside the quadratic region, the effect of restarting is unclear and can slightly slow early convergence before the rapid linear phase begins.The paper reports that restarting is usually helpful in practice, but this behavior is not established by the quadratic analysis.
5 Numerical examples
The numerical examples show adaptive restarting improving accelerated methods across smooth non-strongly-convex, sparse regression, and constrained quadratic problems. The experiments illustrate eventual fast linear convergence or dramatic speedups after local quadratic structure becomes relevant.
- Overview: Three numerical examples evaluate adaptive restarting for smooth non-strongly-convex optimization, sparse linear regression, and quadratic programming.The examples apply the technique to accelerated schemes including FISTA and accelerated projected gradient.
- 5.1 Log-sum-exp: For smaller ρ, decreased smoothness is expected to delay entry into the region of linear convergence.The objective is expected to be locally quadratic near the optimum, enabling linear convergence without prior knowledge of the local region or parameters.
- 5.1 Log-sum-exp: Both restart schemes eventually beat gradient descent and the accelerated scheme on the smooth non-strongly-convex example.Both function and gradient restart methods eventually enter a region of fast linear convergence.
- 5.2 Sparse linear regression: After the nonzero basis is identified in sparse regression, adaptive restarting is expected to provide linear convergence by exploiting the resulting quadratic structure.FISTA otherwise has a guaranteed convergence rate of at least O(1/k^2).
- 5.2 Sparse linear regression: Adaptive restarting provides a dramatic speedup for two sparse linear regression examples solved with FISTA.The examples use n = 2000 with either m = 100, s = 20 or m = 500, s = 100, and set ρ = 1.
- 5.3 Quadratic programming: In the constrained quadratic example, adaptive restarting is applied alongside projected gradient descent and accelerated projected gradient.The instance has n = 500, Q condition number 10^7, and 70 active constraints.
6 Summary
The paper presents heuristic adaptive restarting for accelerated gradient schemes and reports improved convergence performance. Its analysis indicates that restarting can recover optimal linear convergence in many cases, including near optima without global strong convexity.
- Summary: Adaptive restarting improves the convergence performance of accelerated gradient schemes for smooth convex optimization.The method restarts when a specified condition on the objective or gradient value is observed.
- Summary: The analysis indicates that adaptive restarting can recover the optimal linear convergence rate in many cases.The paper specifically discusses behavior near the optimum of a smooth function that is not globally strongly convex.
- Summary: The paper demonstrates the technique on numerical examples.The examples are described as simple numerical demonstrations of the scheme's performance.