TY - GEN
T1 - Fast gradient-based methods with exponential rate
T2 - ICML 2018: 35th International Conference on Machine Learning
AU - Sharifi K., Arman
AU - Mohajerin Esfahani, Peyman
AU - Keviczky, Tamas
PY - 2018
Y1 - 2018
N2 - Ordinary differential equations, and in general a dynamical system viewpoint, have seen a resurgence of interest in developing fast optimization methods, mainly thanks to the availability of well-established analysis tools. In this study, we pursue a similar objective and propose a class of hybrid control systems that adopts a 2nd-order differential equation as its continuous flow. A distinctive feature of the proposed differential equation in comparison with the existing literature is a state-dependent, time-invariant damping term that acts as a feedback control input. Given a user-defined scalar α, it is shown that the proposed control input steers the state trajectories to the global optimizer of a desired objective function with a guaranteed rate of convergence O(e−αt). Our framework requires that the objective function satisfies the so called Polyak–{Ł}ojasiewicz inequality. Furthermore, a discretization method is introduced such that the resulting discrete dynamical system possesses an exponential rate of convergence.
AB - Ordinary differential equations, and in general a dynamical system viewpoint, have seen a resurgence of interest in developing fast optimization methods, mainly thanks to the availability of well-established analysis tools. In this study, we pursue a similar objective and propose a class of hybrid control systems that adopts a 2nd-order differential equation as its continuous flow. A distinctive feature of the proposed differential equation in comparison with the existing literature is a state-dependent, time-invariant damping term that acts as a feedback control input. Given a user-defined scalar α, it is shown that the proposed control input steers the state trajectories to the global optimizer of a desired objective function with a guaranteed rate of convergence O(e−αt). Our framework requires that the objective function satisfies the so called Polyak–{Ł}ojasiewicz inequality. Furthermore, a discretization method is introduced such that the resulting discrete dynamical system possesses an exponential rate of convergence.
UR - http://resolver.tudelft.nl/uuid:17d15b2e-0546-4a21-91e3-df2d865fc993
M3 - Conference contribution
T3 - Proceedings of Machine Learning Research (PMLR)
SP - 2728
EP - 2736
BT - Proceedings of the 35th International Conference on Machine Learning (ICML 2018)
A2 - Dy, Jennifer
A2 - Krause, Andreas
PB - MLR Press
Y2 - 10 July 2018 through 15 July 2018
ER -