Recovering Nesterov accelerated dynamics from Heavy Ball dynamics via time rescaling
Hedy Attouch, Radu Ioan Boţ, David Alexander Hulett, Dang-Khoa Nguyen · 2025
Read Recovering Nesterov accelerated dynamics from Heavy Ball dynamics via time rescaling by Hedy Attouch, Radu Ioan Boţ, David Alexander Hulett, Dang-Khoa Nguyen (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-15852.txt.
Introduction
Hedy Attouch, Radu Boţ, David Hulett and Dang-Khoa Nguyen wrote a 2025 math paper on fast methods for finding low points of a function. They study smooth, bowl-shaped functions and a second task, finding zeros of a steady operator. For each task they track paths made by a system like a heavy ball with friction.
The team proves rates at which the path nears the best value. Its key claim is a link between two systems that look apart. With the right choice of a growth term, each is just the other with time stretched. The same trick ties a fast method for operators to a heavy ball system.
Catalog record
| CREATOR | Hedy Attouch, Radu Ioan Boţ, David Alexander Hulett, Dang-Khoa Nguyen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15852
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Recovering Nesterov accelerated dynamics from Heavy Ball dynamics via time rescaling Thanks: Submitted to the editors DATE. Hedy Attouch, Radu Ioan Boţ, David Alexander Hulett, Dang-Khoa Nguyen Abstract In a real Hilbert space, we consider two classical problems: the global minimization of a smooth and convex function f f (i.e., a convex optimization problem) and finding the zeros of a monotone and continuous operator V V (i.e., a monotone equation). Attached to the optimization problem, first we study the asymptotic properties of the trajectories generated by a second-order dynamical system which features a constant viscous friction coefficient and a positive, monotonically increasing function b ( ⋅ ) b(\cdot) multiplying ∇ f \nabla f . When b ( ⋅ ) b(\cdot) is identically 1 1 , we recover the Heavy Ball with friction dynamics introduced by Polyak in 1964. For a generated solution trajectory y ( t ) y(t) , we show small o o convergence rates dependent on b ( t ) b(t) for f ( y ( t ) ) − min f f(y(t))-\min f , and the weak convergence of y ( t ) y(t) towards a global minimizer of f f . In 2015, Su, Boyd and Candés introduced a second-order system which could be seen as the continuous-time counterpart of Nesterov’s accelerated gradient. As the first key point of this paper, we show that for a special choice for b ( t ) b(t) , these two seemingly unrelated dynamical systems are connected: namely, they are time reparametrizations of each other. Every statement regarding the continuous-time accelerated gradient system may be recovered from its Heavy Ball counterpart. As the second key point of this paper, we observe that this connection extends beyond the optimization setting. Attached to the monotone equation involving the operator V V , we again consider a Heavy Ball-like system which features an additional correction term which is the time derivative of the operator along the trajectory. We derive small o o rates for ‖ V ( y ( t ) ) ‖ \|V(y(t))\| , which depend on two rescaling functions μ ( ⋅ ) \mu(\cdot) and γ ( ⋅ ) \gamma(\cdot) , and show the weak convergence of y ( t ) y(t) to a zero of V V . For special choices for μ ( ⋅ ) \mu(\cdot) and γ ( ⋅ ) \gamma(\cdot) , we establish a time reparametrization equivalence with the Fast OGDA dynamics introduced by Boţ, Csetnek and Nguyen in 2022, which can be seen as an analog of the continuous accelerated gradient dynamics, but for monotone operators. Again, every statement regarding the Fast OGDA system may be recovered from a Heavy Ball-like system. keywords Nesterov accelerated gradient method; Heavy Ball with friction; damped inertial dynamic; time scaling; monotone equations; monotone operator flow; convergence rates; convergence of trajectories Funding. RIB was partially supported by the Austrian Science Fund (FWF), project project P 34922-N. DAH was supported by the Doctoral Programme Vienna Graduate School on Computational Optimization (VGSCO) , funded by the Austrian Science Fund (FWF), project W1260-N35. DKN’s research was funded by the Postdoctoral Scholarship Programme of Vingroup Innovation Foundation (VINIF), code VINIF.2024.STS.37. † † runningheads: Recovering accelerated dynamics from Heavy Ball dynamics / H. Attouch, R.I. Boţ, D.A. Hulett, and D.-K. Nguyen AMS 37N40, 47H05, 47J20, 90C25 1 Introduction 1.1 Convex optimization In a real Hilbert space \mathcal{H} , for a convex and continuously differentiable function f:\mathcal{H}\to{\mathbb{R}} , consider the minimization problem \min_{x\in\mathcal{H}}f(x), (1) which we assume to have an optimal solution. Su, Boyd and Candès [ 22 ] observed that the second-order dynamical system \ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla f(x(s))=0\quad\mbox{for}\ s\geq s_{0}>0, (2) can be viewed as a continuous-time counterpart to Nesterov’s accelerated gradient method [ 16 , 17 ] , designed to efficiently solve this problem. Attouch, Chbani, Peypouquet and Redont [ 5 ] and May [ 15 ] showed that when \alpha>3 any trajectory x(s) generated by this dynamical system satisfies f(x(s))-\inf_{\mathcal{H}}f=o\left(\frac{1}{s^{2}}\right) and converges weakly to a global minimizer of f as s\to+\infty . Also connected to the problem ( 1 ), we have the Heavy Ball dynamics first introduced by Polyak [ 18 , 19 ] \ddot{y}(t)+\lambda\dot{y}(t)+\nabla f(y(t))=0, (3) where the name comes from the mechanical interpretation of this system: y(t) describes the horizontal position of an object which moves alongside the graph of the function f in a medium with viscous friction coefficient \lambda . For more details about this derivation, we refer the reader to [ 7 ] . Álvarez [ 3 ] first showed that any trajectory y(t) generated by the Heavy Ball dynamics satisfies f(y(t))\to\inf_{\mathcal{H}}f and converges weakly to a global minimizer of f as t\to+\infty . Later, it was proved that the functional values actually exhibit a rate f(y(t))-\inf_{\mathcal{H}}f=\mathcal{O}\left(\frac{1}{t}\right) as t\to+\infty . Observe how the rates for the functional values improve when instead of a constant friction coefficient \lambda , we have a so-called asymptotically vanishing damping \frac{\alpha}{t} accompanying the velocity. In [ 6 ] , Attouch, Chbani and Riahi analyzed a more general version of ( 2 ) which reads \ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+b(s)\nabla f(x(s))=0, (4) where b:[s_{0},+\infty[\to{\mathbb{R}}_{++} is a differentiable and nondecreasing function. They explain how the presence of b(\cdot) can be interpreted as the result of a time reparametrization of ( 2 ), which can yield faster convergence rates for the functional values provided b(\cdot) is correctly chosen. Following the same idea, in Section 2 we will study the asymptotic properties of \ddot{y}(t)+\lambda\dot{y}(t)+b(t)\nabla f(y(t))=0\quad\mbox{for}\ t\geq t_{0}\geq 0. (5) We will show that if b(\cdot) satisfies the growth condition \sup_{t\geq t_{0}}\frac{\dot{b}(t)}{b(t)}<\lambda , then any trajectory y(t) generated by ( 5 ) satisfies f(y(t))-\inf_{\mathcal{H}}f=o\left(\frac{1}{\int_{\frac{t_{0}+t}{2}}^{t}b(r)dr}\right) , and it converges weakly to a global minimizer of f as t\to+\infty . Furthermore, and as one of the main points of this paper, in Section 3 we will show that for an appropriate choice for b(\cdot) , ( 5 ) and ( 2 ) are time reparametrizations of each other. Every statement regarding ( 2 ) may be recovered from properties of ( 5 ). Nesterov accelerated gradient dynamics can be recovered from the Heavy Ball dynamics through a time rescaling process. 1.2 Monotone equations It turns out that this story goes beyond the optimization setting and has an analog for monotone equations. For a continuous and monotone operator V:\mathcal{H}\to\mathcal{H} , i.e. \langle V(y)-V(x),y-x\rangle\geq 0 for every x,y\in\mathcal{H} , consider the problem of finding the zeros of V . It is known that the gradient flow dynamics applied to V , \dot{x}(s)+V(x(s))=0, (6) fail in general to produce a trajectory which converges weakly to a zero of V , unless V is cocoercive, i.e., for some \beta>0 , it holds \langle V(y)-V(x),y-x\rangle\geq\beta\|V(y)-V(x)\|^{2} for every x,y\in\mathcal{H} . Attouch, Boţ and Nguyen [ 4 ] proved that in the latter case any trajectory x(s) generated by ( 6 ) satisfies \|V(x(s))\|=o\left(\frac{1}{\sqrt{s}}\right) and converges weakly to a zero of V as s\to+\infty . However, as shown by Attouch and Svaiter in [ 10 ] , by adding a correction term which is the time derivative of the operator along the trajectory, i.e., \lambda(s)\dot{x}(s)+\frac{d}{ds}V(x(s))+V(x(s))=0, (7) where \lambda(\cdot) is a positive function, then even in case of