Resource-Aware Discretization of Accelerated Optimization Flows
arXiv:2009.09135
Abstract
This paper tackles the problem of discretizing accelerated optimization flows while retaining their convergence properties. Inspired by the success of resource-aware control in developing efficient closed-loop feedback implementations on digital systems, we view the last sampled state of the system as the resource to be aware of. The resulting variable-stepsize discrete-time algorithms retain by design the desired decrease of the Lyapunov certificate of their continuous-time counterparts. Our algorithm design employs various concepts and techniques from resource-aware control that, in the present context, have interesting parallelisms with the discrete-time implementation of optimization algorithms. These include derivative- and performance-based triggers to monitor the evolution of the Lyapunov function as a way of determining the algorithm stepsize, exploiting sampled information to enhance algorithm performance, and employing high-order holds using more accurate integrators of the original dynamics. Throughout the paper, we illustrate our approach on a newly introduced continuous-time dynamics termed heavy-ball dynamics with displaced gradient, but the ideas proposed here have broad applicability to other globally asymptotically stable flows endowed with a Lyapunov certificate.
References in corpus (7)
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- A Lyapunov Analysis of Momentum Methods in Optimization
- A geometric alternative to Nesterov's accelerated gradient descent
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- Hamiltonian Descent Methods
- Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions
- High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions