In convex optimization, Nesterov’s accelerated gradient method is celebrated for a remarkable feat: it boosts the convergence rate of first-order optimization on general convex functions from the standard sublinear $O(1/k)$ to the theoretically optimal $O(1/k^2)$.
Yet, this acceleration introduces a paradox. When applied to functions with richer local structures—such as strong convexity, uniform convexity, or local "sharpness"—standard accelerated methods often struggle to automatically exploit this geometry. Instead of converging exponentially faster, they can build up excessive momentum, overshoot the minimum, and oscillate wildly.
To fix this, researchers use a deceptively simple meta-strategy: scheduled restarts. By periodically wiping the optimizer's memory (such as its momentum or acceleration state) and restarting it using the current iterate as the new starting point, we can transform slow, sublinear algorithms into ultra-fast, linearly converging optimizers.
The Core Intuition: Turning Sublinear into Linear
To understand why resetting an algorithm makes it faster, let us look at the mathematical alchemy that happens when you chain sublinear convergence bounds together.
Imagine you have an accelerated base algorithm. When run on a general convex function, it guarantees that after $K$ iterations, the error decreases according to a sublinear profile:
$$\text{Error}_K \le \frac{C}{K^2} \text{Error}_0$$
Now, suppose our specific objective function possesses a local growth property, like strong convexity or sharpness. This property ensures that if the function value is close to the minimum, the iterate itself is physically close to the optimizer.
Because of this geometric security blanket, we can choose a fixed, finite number of iterations $K$ such that the error is guaranteed to cut exactly in half: $\frac{C}{K^2} = \frac{1}{2}$.
If we run the algorithm for $K$ steps, we halt it, wipe out the accumulated momentum, and restart it using the current iterate as the new initial point. We then run it for another $K$ steps. Because the algorithm treats this new phase as a brand-new optimization problem, the error halves again.
If we repeat this process for $M$ discrete epochs, the total number of iterations is $T = M \times K$. However, the error decreases exponentially with the number of epochs:
$$\text{Error}_T \le \left(\frac{1}{2}\right)^M = \left(\frac{1}{2}\right)^{\frac{T}{K}} = e^{-c T}$$
By breaking a continuous optimization run into scheduled, isolated intervals, we transform a sublinear $O(1/T^2)$ rate into a linear $O(e^{-cT})$ rate. As Sebastian Pokutta notes in Restarting Algorithms: Sometimes There Is Free Lunch, this acts as a black-box meta-technique that upgrades an algorithm's performance without requiring internal modifications to the underlying gradient steps.
Standard Acceleration: [--- Momentum Builds Up ---> Overshoots & Oscillates]
Scheduled Restarts: [-- Run K steps --] ↺ Restart [-- Run K steps --] ↺ Restart
From a physical perspective, Weijie J Su et al. demonstrated in A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights that Nesterov's method can be modeled as a continuous damped harmonic oscillator. For general convex functions, the friction term vanishes too quickly. Periodically resetting the velocity (momentum) to zero prevents the system from overshooting, matching the high-speed performance demanded by sharper objective landscapes.
Exploiting Local Geometry Without Tuning
The primary challenge in optimization is that we rarely know the exact global parameters of a function, such as its strong convexity constant or its local curvature. Fortunately, scheduled restarts allow algorithms to adapt to these properties dynamically.
Adapting to Sharpness and Error Bounds
Functions often exhibit "sharpness"—a measure of how rapidly the objective value grows as you move away from the minimum. In a pair of foundational papers titled Sharpness, Restart, and Acceleration, Vincent Roulet et al. (2017, 2020) showed that periodic restarts allow first-order methods to automatically latch onto this local geometry. By resetting the momentum terms at fixed intervals or using a grid-search over restart lengths, the optimizer adapts to the function's specific sharpness exponent, converting sublinear bounds into faster polynomial or linear rates.
Similarly, when a problem satisfies a general Hölderian Error Bound but the growth parameters are unknown, Yi Xu et al. proved in Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter that a restarting strategy which geometrically scales the number of inner iterations per epoch can achieve optimal convergence without manual parameter tuning.
Navigating High Dimensions and Uniform Convexity
In high-dimensional settings, global strong convexity rarely holds. However, the function might display restricted strong convexity near the solution space. Junqi Tang et al. exploited this in Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes, showing that restarting an accelerated stochastic algorithm allows it to adapt to low-dimensional structures (like sparsity) on the fly.
For functions characterized by uniform convexity (a generalization of strong convexity with higher-order growth), Alexander Gasnikov et al. demonstrated in Optimal Tensor Methods in Smooth Convex and Uniformly ConvexOptimization that periodic resets allow the algorithm to adapt to the local curvature, translating the degree of uniform convexity directly into accelerated convergence rates.
Broad Applications: Games, Noise, and Higher-Order Methods
The utility of scheduled restarts extends far beyond simple convex minimization. The same mechanism stabilizes and accelerates a wide variety of optimization paradigms.
Minimax Optimization and Games
In minimax optimization (used in training GANs or solving adversarial problems), standard gradient methods frequently fail because the parameters of the two players oscillate or spiral into divergence.
- Bilinear Games: Chris Junchi Li et al. tackled this in On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging. By partitioning the stochastic extragradient process into epochs and using the averaged iterate of the previous epoch to initialize the next, the algorithm discards the noise and the influence of the starting position at an exponential rate.
- Separable Minimax: In Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization, Chris Junchi Li et al. utilized a scheduled restart strategy to manage progress across fixed-length intervals, successfully forcing saddle-point algorithms into linear convergence.
- Saddle-Point Growth Conditions: Ekaterina Borodich et al. extended this in On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms, proving that iterative restarting schemes decouple gradient evaluations from matrix multiplications, achieving linear convergence even under relaxed growth conditions.
Mitigating Noise and High Dimensions
Restarts also act as a protective barrier against stochastic noise and high-dimensional sample complexity:
- Stochastic Radius Reduction: In Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions, Alekh Agarwal et al. introduced RADAR, an epoch-based method that shrinks the optimization search radius at each restart, achieving a fast $1/T$ convergence rate with only a logarithmic dependence on dimension.
- Heavy-Tailed Environments: When gradient noise is heavy-tailed and prone to extreme outliers, Eduard Gorbunov et al. showed in Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping that combining gradient clipping with periodic algorithm restarts preserves linear-like convergence rates.
Higher-Order and Adaptive Frameworks
Finally, restarts serve as a bridge between general convex algorithms and higher-order tensor methods. Alexander Gasnikov et al. in A hypothesis about the rate of global convergence for optimal methods (Newtons type) in smooth convex optimization and Artem Agafonov et al. in Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness demonstrated that restarting higher-order Newton-type or tensor methods allows them to adapt smoothly to local curvature and inexact data oracles, securing superlinear or linear rates in high-precision regimes.
Summary
Scheduled restart schemes work because they exploit a fundamental loophole in optimization theory: an algorithm optimized for a broad, pessimistic class of functions (like general convex functions) can be forced to behave like an algorithm optimized for a strict, well-behaved class of functions (like strongly convex functions). By systematically clearing out accumulated momentum and resetting the optimization clock, scheduled restarts turn sublinear steps into a sequence of geometric contractions—delivering a powerful, structure-adaptive performance boost across the entire spectrum of modern optimization.
Key Foundational Work
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights (2014) — contributed 1 concept elements to this direction.
Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions (2012) — contributed 1 concept elements to this direction.