173. A unified Euler--Lagrange system for analyzing continuous-time accelerated gradient methods
Invited abstract in session FC-4: Large-scale optimization III, stream Large-scale optimization.
Friday, 11:25 - 12:40Room: M:M
Authors (first author is the speaker)
| 1. | Mitsuru Toyoda
|
| Department of Mechanical Systems Engineering, Tokyo Metropolitan University | |
| 2. | Akatsuki Nishioka
|
| Department of Mathematical Informatics, The University of Tokyo | |
| 3. | Mirai Tanaka
|
| Department of Statistical Inference and Mathematics, The Institute of Statistical Mathematics |
Abstract
This talk presents a unified Euler--Lagrange system of continuous-time accelerated gradient methods and its convergence analysis based on a unified Lyapunov function. To understand the mysterious dynamics of discrete-time accelerated gradient methods, continuous-time ordinary differential equation (ODE) models have been recently developed; however, dumping terms appearing in the ODE models still have technical time-varying coefficients and have difficulties on the interpretability. Besides, in various problem settings (e.g., strong convexity of an objective function), an associated model and its Lyapunov function have been separately developed. Based on the background, this study proposes a Lagrangian, deriving an Euler--Lagrange system, and Lyapunov function for the unified analysis of existing ODE models. The introduced Lyapunov function naturally shows the conditions that the design parameters in the Lagrangian and Lyapunov function must satisfy. The obtained conditions suggests that the dumping terms in the ODE models are chosen to improve the resulting convergence rate. Furthermore, the extension to non-smooth objective functions with associated smooth approximation is available. The preprint of this study is available at ``arXiv:2404.03383''.
Keywords
- Convex and non-smooth optimization
- Complexity and efficiency of optimization algorithms
- Optimal control and applications
Status: accepted
Back to the list of papers