Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
From MaRDI portal
Abstract: In this paper, we develop a unified framework able to certify both exponential and subexponential convergence rates for a wide range of iterative first-order optimization algorithms. To this end, we construct a family of parameter-dependent nonquadratic Lyapunov functions that can generate convergence rates in addition to proving asymptotic convergence. Using Integral Quadratic Constraints (IQCs) from robust control theory, we propose a Linear Matrix Inequality (LMI) to guide the search for the parameters of the Lyapunov function in order to establish a rate bound. Based on this result, we formulate a Semidefinite Programming (SDP) whose solution yields the best convergence rate that can be certified by the class of Lyapunov functions under consideration. We illustrate the utility of our results by analyzing the gradient method, proximal algorithms and their accelerated variants for (strongly) convex problems. We also develop the continuous-time counterpart, whereby we analyze the gradient flow and the continuous-time limit of Nesterov's accelerated method.
Recommendations
- Analysis and design of optimization algorithms via integral quadratic constraints
- Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach
- Convex Synthesis of Accelerated Gradient Algorithms
- Analysis of optimization algorithms via sum-of-squares
- Synthesis of accelerated gradient algorithms for optimization and saddle point problems using Lyapunov functions and LMIs
Cites work
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A variational perspective on accelerated methods in optimization
- Analysis and design of optimization algorithms via integral quadratic constraints
- Computational Complexity Certification for Real-Time MPC With Input Constraints Based on the Fast Gradient Method
- Convex optimization algorithms
- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- Fast convex optimization via inertial dynamics with Hessian driven damping
- First-order methods of smooth convex optimization with inexact oracle
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3249151 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- On the long time behavior of second order differential equations with asymptotically small dissipation
- On the Minimizing Property of a Second Order Dissipative System in Hilbert Spaces
- Optimized first-order methods for smooth convex minimization
- Performance of first-order methods for smooth convex minimization: a novel approach
- Proximal splitting methods in signal processing
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- Some methods of speeding up the convergence of iteration methods
- Stability of primal-dual gradient dynamics and applications to network optimization
- System analysis via integral quadratic constraints
- The Role of Convexity in Saddle-Point Dynamics: Lyapunov Function and Robustness
Cited in
(43)- A simplified view of first order methods for optimization
- Analysis of optimization algorithms via sum-of-squares
- Iterative pre-conditioning for expediting the distributed gradient-descent method: the case of linear least-squares problem
- A control-theoretic perspective on optimal high-order optimization
- Passivity-based analysis of the ADMM algorithm for constraint-coupled optimization
- Model-free based control of a HIV/AIDS prevention model
- A frequency-domain analysis of inexact gradient methods
- Synthesis of accelerated gradient algorithms for optimization and saddle point problems using Lyapunov functions and LMIs
- Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
- Efficient first-order methods for convex minimization: a constructive approach
- Linear convergence of first order methods for non-strongly convex optimization
- Proximal gradient flow and Douglas-Rachford splitting dynamics: global exponential stability via integral quadratic constraints
- Robust hybrid zero-order optimization algorithms with acceleration via averaging in time
- scientific article; zbMATH DE number 6474937 (Why is no real title available?)
- Analysis and design of optimization algorithms via integral quadratic constraints
- scientific article; zbMATH DE number 1424228 (Why is no real title available?)
- Projected dynamical systems on irregular, non-Euclidean domains for nonlinear optimization
- The connections between Lyapunov functions for some optimization algorithms and differential equations
- A unified analysis of first-order methods for smooth games via integral quadratic constraints
- A Lyapunov analysis of accelerated methods in optimization
- Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach
- Convex Synthesis of Accelerated Gradient Algorithms
- Analysis of a generalised expectation-maximisation algorithm for Gaussian mixture models: a control systems perspective
- scientific article; zbMATH DE number 7626757 (Why is no real title available?)
- Zames–Falb multipliers for convergence rate: motivating example and convex searches
- Differentially Private Accelerated Optimization Algorithms
- Contractivity of Runge-Kutta methods for convex gradient systems
- Robust accelerated gradient methods for smooth strongly convex functions
- Novel projection neurodynamic approaches for constrained convex optimization
- A zeroing neural dynamics based acceleration optimization approach for optimizers in deep neural networks
- A fixed step distributed proximal gradient push‐pull algorithm based on integral quadratic constraint
- A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization
- Dynamics based privacy preservation in decentralized optimization
- A Nonlocal Graph-PDE and Higher-Order Geometric Integration for Image Labeling
- PEPIT: computer-assisted worst-case analyses of first-order optimization methods in python
- Convergence rate bounds for the mirror descent method: IQCs, Popov criterion and Bregman divergence
- Fast symplectic integrator for Nesterov-type acceleration method
- Entropic risk-averse generalized momentum methods
- A projection-free dynamics for nonsmooth composite optimization.
- Multi-objective robust controller synthesis with integral quadratic constraints in discrete-time
- Data-driven performance guarantees for classical and learned optimizers
- On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights
- Accelerated optimization algorithms and ordinary differential equations: the convex non Euclidean case
This page was built for publication: Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4687235)
