A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization
From MaRDI portal
Abstract: First-order methods are often analyzed via their continuous-time models, where their worst-case convergence properties are usually approached via Lyapunov functions. In this work, we provide a systematic and principled approach to find and verify Lyapunov functions for classes of ordinary and stochastic differential equations. More precisely, we extend the performance estimation framework, originally proposed by Drori and Teboulle [10], to continuous-time models. We retrieve convergence results comparable to those of discrete methods using fewer assumptions and convexity inequalities, and provide new results for stochastic accelerated gradient flows.
Recommendations
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
- The connections between Lyapunov functions for some optimization algorithms and differential equations
- A general system of differential equations to model first-order adaptive algorithms
- Optimum Lyapunov functions
- scientific article; zbMATH DE number 4129510
Cites work
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A dynamical system associated with the fixed points set of a nonexpansive operator
- A Lyapunov analysis of accelerated methods in optimization
- A variational perspective on accelerated methods in optimization
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Acceleration of Stochastic Approximation by Averaging
- Analysis and design of optimization algorithms via integral quadratic constraints
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
- Applied stochastic differential equations
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Exact worst-case performance of first-order methods for composite convex optimization
- Fast convex optimization via inertial dynamics with Hessian driven damping
- Generalized momentum-based methods: a Hamiltonian perspective
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- Linear convergence of first order methods for non-strongly convex optimization
- Numerical analysis.
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- Performance of first-order methods for smooth convex minimization: a novel approach
- Potential-function proofs for gradient methods
- Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
- Second order forward-backward dynamical systems for monotone inclusion problems
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- Some methods of speeding up the convergence of iteration methods
- Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations
- The connections between Lyapunov functions for some optimization algorithms and differential equations
- Understanding the acceleration phenomenon via high-resolution differential equations
- Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation
Cited in
(16)- The new nonprobabilistic criterion of failure for dynamical systems based on convex models
- Convex Programs for Temporal Verification of Nonlinear Dynamical Systems
- A general system of differential equations to model first-order adaptive algorithms
- The connections between Lyapunov functions for some optimization algorithms and differential equations
- Time-varying continuous-time optimisation with pre-defined finite-time stability
- Computation of Lyapunov functions for smooth nonlinear systems using convex optimization
- Friction-adaptive descent: a family of dynamics-based optimization methods
- Robustness analysis of continuous-depth models with Lagrangian techniques
- Another approach to build Lyapunov functions for the first order methods in the quadratic case
- Properties and practicability of convergence-guaranteed optimization methods derived from weak discrete gradients
- Interpolation conditions for linear operators and applications to performance estimation problems
- Stochastic modified flows for Riemannian stochastic gradient descent
- Automated tight Lyapunov analysis for first-order methods
- Stochastic asymptotical regularization for nonlinear ill-posed problems
- Accelerating optimization over the space of probability measures
- On the application of explicit Runge-Kutta methods to the construction of stochastic gradient descent methods for convex optimization
This page was built for publication: A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116244)
