Abstract
In convex optimization, achieving the optimal convergence rate of $O(1/t^2)$ typically requires non-autonomous systems with time-dependent damping, such as Nesterov’s Accelerated Gradient (NAG). However, these "open-loop" systems are highly sensitive to initial time parameters. This paper introduces LYDIA (LYapunov Damped Inertial Algorithm), an autonomous, closed-loop optimization framework. By setting the damping coefficient as a function of the system's energy (a Lyapunov function), the proposed method achieves a convergence rate arbitrarily close to the theoretical optimal while maintaining robustness to initialization.
Introduction
Accelerated methods are the cornerstone of modern optimization, with Nesterov’s Accelerated Gradient (NAG) serving as the benchmark for convex functions. When analyzed through the lens of continuous-time Ordinary Differential Equations (ODEs), NAG corresponds to a system with vanishing friction, where the damping coefficient $\gamma(t)$ is typically defined as $a/t$.
While effective, this open-loop damping makes the system non-autonomous: the trajectory and convergence behavior depend heavily on the starting clock time $t_0$. If $t_0$ is large, the damping vanishes too quickly, leading to excessive oscillations. Conversely, a small $t_0$ may result in over-damping. The challenge addressed here is the design of a closed-loop (autonomous) system—where damping depends solely on the state $(x, \dot{x})$—that matches the $O(1/t^2)$ acceleration.
The Lyapunov Damping (LD) Framework
The authors propose a system called Lyapunov Damping (LD). The core innovation lies in coupling the damping coefficient $\gamma(t)$ to the system's total energy $E(t)$:
$$\gamma(t) = \sqrt{E(t)}$$
where the energy $E(t)$ is defined as the sum of the optimality gap and the kinetic energy: $$E(t) = f(x(t)) - f^* + \frac{1}{2}\|\dot{x}(t)\|^2$$
As the system approaches the minimizer, $E(t)$ decreases, naturally reducing the friction. This feedback loop allows the system to regulate its own acceleration without an external clock. The continuous-time model is then discretized into the LYDIA algorithm for practical application.
Theoretical Convergence and Robustness
The primary theoretical contribution is the proof that for any $\delta > 0$, the LD system converges at a rate of $o(1/t^{2-\delta})$. While slightly below the exact $1/t^2$ rate of Nesterov's method, this "near-optimal" rate is a significant advancement for autonomous systems, which have historically been limited to slower convergence.
As shown in Figure 1, the autonomous nature of LD provides a distinct advantage in stability. Traditional Accelerated Variable Damping (AVD) methods exhibit wildly different trajectories and convergence profiles depending on the choice of $t_0$. In contrast, the LD trajectory remains consistent and robust, avoiding the pathological oscillations seen in AVD when $t_0$ is poorly initialized.
Empirical Validation
The algorithm was evaluated on specialized test functions designed to challenge optimization stability, such as the flat polynomial $f(x) = x^{24}$ and functions lacking the Kurdyka-Łojasiewicz property. In these settings, LYDIA consistently matched the asymptotic slope of Nesterov-style methods on log-log plots, significantly outperforming standard Gradient Descent and the Heavy Ball method.
Limitations and Future Outlook
Despite its theoretical and empirical strengths, LYDIA currently requires knowledge of the optimal function value $f^*$ to compute the energy $E(t)$. While $f^*$ is known in specific contexts (e.g., over-determined systems where $f^*=0$), extending the method to cases with unknown $f^*$ remains a critical area for future work. Additionally, while the continuous-time ODE is well-understood, further research is needed to rigorously prove that the discrete-time LYDIA maintains the exact near-optimal rate under all conditions.
Summary updated