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 -