Acceleration via Perturbations on Low-resolution Ordinary Differential Equations
Xudong Li Lei Shi Mingqi Song · 2025
Read Acceleration via Perturbations on Low-resolution Ordinary Differential Equations by Xudong Li Lei Shi Mingqi Song (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-01497.txt.
Introduction
Xudong Li, Lei Shi, and Mingqi Song use smooth flow equations to explain why some fast search methods work. Their 2025 paper studies gradient methods, which walk downhill on a cost surface to find low points. A refined equation model had shown that a correction term cuts wobble and speeds the walk.
Yet adding that term to the simpler model sometimes slows things down instead. The team builds a general perturbed equation to sort out when each term helps. They show the correction term is needed for speed, but can hurt in some cases. A second added term, based on the plain gradient, fixes the harm. Tests on sample problems match the theory, and the paper gives rules for picking settings.
Catalog record
| CREATOR | Xudong Li Lei Shi Mingqi Song |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01497
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Acceleration via Perturbations on Low-resolution Ordinary Differential Equations Thanks: Authors are listed in alphabetical order. Xudong Li Lei Shi Mingqi Song Abstract Recently, the high-resolution ordinary differential equation (ODE) framework, which retains higher-order terms, has been proposed to analyze gradient-based optimization algorithms. Through this framework, the term ∇ 2 f ( X t ) X t ˙ \nabla^{2}f(X_{t})\dot{X_{t}} , known as the gradient-correction term, was found to be essential for reducing oscillations and accelerating the convergence rate of function values. Despite the importance of this term, simply adding it to the low-resolution ODE may sometimes lead to a slower convergence rate. To fully understand this phenomenon, we propose a generalized perturbed ODE and analyze the role of the gradient and gradient-correction perturbation terms under both continuous-time and discrete-time settings. We demonstrate that while the gradient-correction perturbation is essential for obtaining accelerations, it can hinder the convergence rate of function values in certain cases. However, this adverse effect can be mitigated by involving an additional gradient perturbation term. Moreover, by conducting a comprehensive analysis, we derive proper choices of perturbation parameters. Numerical experiments are also provided to validate our theoretical findings. Keywords: Accelerated algorithms; Ordinary differential equation; Lyapunov function; Perturbations 1 Introduction The swift progression of machine learning contributes to notable advancements in first-order optimization methods. Accelerated first-order methods garner significant attention due to their ability to achieve faster iteration complexity without introducing additional computational overhead compared to their non-accelerated counterparts. A seminal contribution in this domain is Nesterov’s accelerated method [ 15 , 16 ] . However, the derivations presented therein are often considered counterintuitive and rely heavily on case-specific algebraic manipulations [ 11 ] , thus highlighting the need for a deeper understanding of the acceleration phenomenon. While there exists a long history linking optimization algorithms with trajectories of ordinary differential equations (ODEs) [ 9 , 17 , 7 ] , it was only recently that Su et al. [ 20 , 3 ] effectively connected Nesterov’s accelerated scheme for solving smooth convex problems with a specially crafted second-order ODE. Since this groundbreaking work, many subsequent studies [ 12 , 21 , 22 , 23 , 3 ] have endeavored to offer deeper insights and enhanced understanding of the acceleration schemes from the perspective of ODEs. Among these studies, the work [ 23 ] drew analogies between the differential equations of some popular algorithms and damped oscillator systems, offering valuable physical insights. Quite recently, it was observed in [ 18 ] that the continuous ODEs corresponding to the trajectory X(t) , derived following the approach in [ 20 , 21 ] for two fundamentally different algorithms—Nesterov’s accelerated gradient method for \mu -strongly convex functions (NAG-SC) and Polyak’s heavy-ball method—are identically taking the following form: \ddot{X_{t}}+2\sqrt{\mu}\dot{X_{t}}+\nabla f(X_{t})=0, (1.1) where f(x) is a smooth \mu -strongly convex function to be minimized and the following notation are used: X_{t}=X(t),\quad\dot{X_{t}}=\frac{\mathrm{d}X_{t}}{\mathrm{d}t},\quad\ddot{X_{t}}=\frac{\mathrm{d}^{2}X_{t}}{\mathrm{d}t^{2}}. This indicates that the continuous approach promoted in [ 20 ] may not fully describe the behaviors of discrete accelerated algorithms. By preserving higher-order terms, in [ 18 ] , the authors derive the following high-resolution ODEs \ddot{X_{t}}+2\sqrt{\mu}\dot{X_{t}}+(1+\sqrt{\mu s})\nabla f(X_{t})+\sqrt{s}\nabla^{2}f(X_{t})\dot{X_{t}}=0, (1.2) and \ddot{X_{t}}+2\sqrt{\mu}\dot{X_{t}}+(1+\sqrt{\mu s})\nabla f(X_{t})=0, (1.3) where s is the step size in the discrete algorithms, as more accurate surrogates for NAG-SC and the heavy-ball method, respectively. Compared to the low-resolution ODE ( 1.1 ), the two ODEs ( 1.2 ) and ( 1.3 ) contain extra high order terms \sqrt{\mu s}\nabla f(X_{t}) and \sqrt{s}\nabla^{2}f(X_{t})\dot{X}_{t} , and thus possess more potential in characterizing the performance of NAG-SC and the heavy-ball method. As one can observe, the key difference between the high-resolution ODEs of NAG-SC ( 1.2 ) and the heavy-ball method ( 1.3 ) lies in an extra term \sqrt{s}\nabla^{2}f(X_{t})\dot{X_{t}} , referred to as the gradient correction term, in ( 1.2 ). In [ 18 ] , it is emphasized that this term is essential for acceleration. Interestingly, an alternative line of research [ 1 , 2 , 4 , 3 ] also highlights the term \nabla^{2}f(X_{t})\dot{X_{t}} , where it is coined as the Hessian-driven damping term. Unlike the approach in [ 18 ] , this line of work derives the term by leveraging second-order information obtained via the Newton method. The pivotal role of the gradient correction term \nabla^{2}f(X_{t})\dot{X_{t}} in accelerating optimization algorithms is further underscored in the existing literature. For instance, this term can effectively neutralize oscillations, as demonstrated in [ 3 ] , and is crucial for achieving a rapid convergence rate of {\cal o}(1/k^{3}) in the gradient norm of Nesterov’s accelerated gradient method for minimizing convex functions (NAG-C) [ 6 ] , as well as in the proximal subgradient norm of FISTA [ 13 ] . Although the existing literature underscores the crucial impact of the gradient correction term \nabla^{2}f(X_{t})\dot{X_{t}} , an intriguing anomaly arises wherein the mere inclusion of this term into the low-resolution ODE may paradoxically decrease the convergence rate of the function value, for example the system (DIN)_{2\sqrt{\mu},\beta} in [ 3 ] . Specifically, for any given \beta\in[0,1/2\sqrt{\mu}] , (DIN)_{2\sqrt{\mu},\beta} is referred to as an inertial system for minimizing a \mu -strongly convex function f : \ddot{X_{t}}+2\sqrt{\mu}\dot{X_{t}}+\beta\nabla^{2}f(X_{t})\dot{X_{t}}+\nabla f(X_{t})=0. (1.4) The convergence rate of the function value f(X_{t})-f(x^{*}) for ( 1.4 ) derived in [ 3 , Theorem 7(i)] is {\cal O}(e^{-\frac{\sqrt{\mu}}{2}t}) , while the convergence rate of the same quantity for the corresponding low-resolution ODE ( 1.1 ) is a faster decay rate {\cal O}(e^{-\sqrt{\mu}t}) [ 22 , Proposition 5] . In contrast, the high-resolution ODE ( 1.2 ) also contains the gradient correction term but exhibits the same convergence rate {\cal O}(e^{-\sqrt{\mu}t}) as that of ( 1.1 ). We also note that the main distinction between ( 1.4 ) and ( 1.2 ) resides in the presence of the perturbation from \nabla f(X_{t}) within ( 1.2 ). Consequently, the following question naturally arises: Problem 1 . Does the presence of the gradient correction term \nabla^{2}f(X_{t})\dot{X_{t}} adversely affect the convergence rate of the function value? If so, what strategies can be employed to mitigate or eliminate this negative influence? In this paper, we address the above problem from the perturbation perspective and propose to study the following perturbed version of ( 1.1 ): \ddot{X_{t}}+2\sqrt{\mu}\dot{X_{t}}+(1+\Delta_{1})\nabla f(X_{t})+\Delta_{2}\nabla^{2}f(X_{t})\dot{X_{t}}=0, (1.5) where \Delta_{1} , \Delta_{2} are two nonnegative constants. This perturbed ODE extends the system ( 1.4 ) and covers both the high-resolution ODEs for NAG-SC ( 1.2 ) and the heavy-ball method ( 1.3 ). We begin by offering intuitive interpretations of the gradient perturbation \Delta_{1}\nabla f(X_{t}) and the gradient-correction perturbation \Delta_{2}\nabla^{2}f(X_{t})\dot{X_{t}} in ( 1.5 ). Specifically, we connect the general perturbed ODE ( 1.5 ) with a damped oscillator system, a perturbed version of the physical system studied in [ 23 ] . In our model, the term \Delta_{1}\nabla f(X_{t}) reinforces the system’s resilience, accelerating the particle’s return to the equilibrium position, but may increase the oscillations. Meanwhile, the term \Delta_{2}\nabla^{2}f(X_{t})\dot{X_{t}} can be viewed as a force resulting from the change in the impulse \Delta_{2}\nabla f(X_{t}) . It is negative if the resilience is decreasing. This may slow down the particle’s approaching the equilibrium position but is beneficial for reducing oscillations. Intuitively, properly combining these two terms may accelerate the convergence. Indeed, we can demonstrate that incorporating