Near-optimal Closed-loop Method via Lyapunov Damping for Convex Optimization

Severin Maier, Camille Castera, Peter OchsarXiv 2023 · DOI · arXiv

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.

Comparison of Lyapunov Damping (LD) and Accelerated Variable Damping (AVD) across different initializations.

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

Abstract

We introduce an autonomous system with closed-loop damping for first-order convex optimization. While, to this day, optimal rates of convergence are almost exclusively achieved by non-autonomous methods via open-loop damping (e.g., Nesterov's algorithm), we show that our system, featuring a closed-loop damping, exhibits a rate arbitrarily close to the optimal one. We do so by coupling the damping and the speed of convergence of the system via a well-chosen Lyapunov function. By discretizing our system we then derive an algorithm and present numerical experiments supporting our theoretical findings.
BibTeX
@misc{maier2023near,
  author = {Severin Maier and Camille Castera and Peter Ochs},
  title = {{Near-optimal Closed-loop Method via Lyapunov Damping for Convex Optimization}},
  year = {2023},
  eprint = {2311.10053},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.10053},
}
Figure