Abstract
We introduce the "continuized" Nesterov acceleration, a close variant of Nesterov acceleration whose variables are indexed by a continuous time parameter. The two variables continuously mix following a linear ordinary differential equation and take gradient steps at random times. This continuized variant benefits from the best of the continuous and the discrete frameworks: as a continuous process, one can use differential calculus to analyze convergence and obtain analytical expressions for the parameters; but a discretization of the continuized process can be computed exactly with convergence rates similar to those of Nesterov original acceleration. We show that the discretization has the same structure as Nesterov acceleration, but with random parameters.
Introduction
Nesterov’s accelerated gradient descent is a cornerstone of modern optimization, offering the theoretical "speed limit" for first-order methods. However, its discrete-time structure—a sequence of carefully balanced "mixing" and "gradient" steps—is notoriously difficult to intuit. To simplify this, researchers often look at "continuous-time limits," where the step size vanishes and the algorithm becomes a smooth ordinary differential equation (ODE). While these ODEs are easier to analyze using calculus, they often suffer from a "discretization gap": when turning the smooth ODE back into a practical algorithm, errors can ruin the acceleration. This paper introduces a framework that offers the analytical simplicity of continuous time without losing the algorithmic rigor of discrete steps.
The Continuized Framework
The authors propose the continuized version of Nesterov acceleration. Instead of variables indexed by an integer step $k$, they use variables $x_t$ and $z_t$ indexed by continuous time $t$.
- Continuous Mixing: Between gradient steps, the variables $x_t$ and $z_t$ continuously "mix" or flow toward each other following a linear ODE.
- Random Jumps: Gradient steps occur at random times $T_1, T_2, \dots$ determined by a Poisson process.
- Stochastic Calculus: Because the gradient steps are random, the authors use stochastic calculus (specifically Poisson point measures) to analyze the expected convergence. This allows them to define a "Lyapunov function" that is much simpler than its discrete-time counterparts.
- Exact Discretization: Crucially, this continuous process can be sampled at the jump times to create a discrete algorithm. This resulting algorithm looks exactly like Nesterov’s acceleration but uses randomized parameters based on the time elapsed between jumps.
Empirical Validation
The theory is validated using synthetic objective functions, including a strongly convex quadratic function in $\mathbb{R}^3$ and a high-dimensional convex quadratic function in $\mathbb{R}^{100}$.
Key Results and Insights
The continuized method achieves the same optimal convergence rates as Nesterov’s: $O(1/t^2)$ for smooth convex functions and $O(\exp(-\sqrt{\mu/L}t))$ for strongly convex functions. In simulations, the "discretized" version of the continuized process performs almost identically to the deterministic Nesterov acceleration, proving that the randomization doesn't hurt performance.
By making the timing of the steps random, the authors "smooth out" the discrete jumps. This allows them to use derivatives to prove convergence, avoiding the complex algebra usually required for Nesterov’s method. In the continuized view, the optimal parameters are simple, elegant functions of time $t$ (e.g., $\eta_t = 2/t$).
Furthermore, the framework is well-suited for analyzing stochastic gradients. The continuous mixing acts as a natural buffer, and the authors provide clean proofs for how the algorithm behaves when gradients are corrupted by additive noise. The paper derives explicit bounds for noisy gradients, showing that the error term grows sub-linearly in the convex case and remains bounded in the strongly convex case.
Conclusion and Future Work
The continuized view on Nesterov acceleration bridges the gap between continuous-time analysis and discrete-time implementation. While the randomized parameters are theoretically elegant, future work could explore their implementation in specific hardware or distributed environments. Extending this view to non-Euclidean geometries (Mirror Descent) or constrained optimization (proximal methods) would be valuable. Additionally, the framework's relevance to asynchronous distributed computing offers a promising avenue for large-scale optimization research.
Summary updated