Abstract:

Motivated by the recent trend in works that study optimization algorithms from the point of view of dynamical systems and control, we seek to understand how to best systematically discretize a given generic continuous-time analogue of a gradient-based optimization algorithm, represented by ordinary differential equations (ODEs). To this end, we show how a suboptimality bound for such continuous-time algorithms can be combined with an ODE solver’s accuracy bound in order to provide non-asymptotic suboptimality bounds upon discretization. In particular, we show that subexponential, exponential, and finite-time convergence rates in continuous time can be nearly matched upon discretization by merely using off-the-shelf ODE solvers of modestly high order. We then illustrate our findings on a modified version of the celebrated second-order ODE that models Nesterov’s accelerated gradient. Lastly, we apply our approach on the rescaled gradient flow.