Jorge Cortés
Professor
Cymer Corporation Endowed Chair
Convergence-rate-matching discretization of
accelerated optimization flows through opportunistic
state-triggered control
M. Vaquero, J. Cortés
Advances in Neural Information Processing Systems, eds.
H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc,
E. Fox, R. Garnett, vol. 32, Curran Associates, 2019, pp. 9767-9776
Abstract
A recent body of exciting work seeks to shed light on the behavior of accelerated methods in optimization via high-resolution differential equations. These differential equations are continuous counterparts of the corresponding discrete-time optimization algorithms, and their convergence properties can be characterized using the powerful tools provided by classical Lyapunov stability analysis. An outstanding question of pivotal importance is how to discretize these continuous flows while maintaining the rate of convergence. This paper provides a simple answer through the idea of opportunistic state-triggered control. We take advantage of the Lyapunov functions employed to characterize the rate of convergence of high-resolution differential equations to design variable-stepsize forward-Euler discretizations that preserve the acceleration properties of the original dynamics. Our approach is not limited to the discretization of accelerated methods, and can be applied to other asymptotically stable dynamical systems.
Mechanical and Aerospace Engineering,
University of California, San Diego
9500 Gilman Dr,
La Jolla, California, 92093-0411
Ph: 1-858-822-7930
Fax: 1-858-822-3107
cortes at ucsd.edu
Skype id:
jorgilliyo