Recovering Nesterov accelerated dynamics from Heavy Ball dynamics via time rescaling
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908332159139840 |
|---|---|
| author | Attouch, Hedy Bot, Radu Ioan Hulett, David Alexander Nguyen, Dang-Khoa |
| author_facet | Attouch, Hedy Bot, Radu Ioan Hulett, David Alexander Nguyen, Dang-Khoa |
| contents | In a real Hilbert space, we consider two classical problems: the global minimization of a smooth and convex function $f$ (i.e., a convex optimization problem) and finding the zeros of a monotone and continuous operator $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(\cdot)$ multiplying $\nabla f$. For a generated solution trajectory $y(t)$, we show small $o$ convergence rates dependent on $b(t)$ for $f(y(t)) - \min f$, and the weak convergence of $y(t)$ towards a global minimizer of $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)$, 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$, 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 establish a time reparametrization equivalence with the Fast OGDA dynamics introduced by Bot, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15852 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recovering Nesterov accelerated dynamics from Heavy Ball dynamics via time rescaling Attouch, Hedy Bot, Radu Ioan Hulett, David Alexander Nguyen, Dang-Khoa Optimization and Control 37N40, 47H05, 47J20, 90C25 In a real Hilbert space, we consider two classical problems: the global minimization of a smooth and convex function $f$ (i.e., a convex optimization problem) and finding the zeros of a monotone and continuous operator $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(\cdot)$ multiplying $\nabla f$. For a generated solution trajectory $y(t)$, we show small $o$ convergence rates dependent on $b(t)$ for $f(y(t)) - \min f$, and the weak convergence of $y(t)$ towards a global minimizer of $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)$, 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$, 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 establish a time reparametrization equivalence with the Fast OGDA dynamics introduced by Bot, 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. |
| title | Recovering Nesterov accelerated dynamics from Heavy Ball dynamics via time rescaling |
| topic | Optimization and Control 37N40, 47H05, 47J20, 90C25 |
| url | https://arxiv.org/abs/2504.15852 |