TR2022-159

ODE Discretization Schemes as Optimization Algorithms


    •  Romero, O., Benosman, M., Pappas, G., "ODE Discretization Schemes as Optimization Algorithms", IEEE Conference on Decision and Control (CDC), December 2022.
      BibTeX TR2022-159 PDF
      • @inproceedings{Romero2022dec,
      • author = {Romero, Orlando and Benosman, Mouhacine and Pappas, Geroge},
      • title = {ODE Discretization Schemes as Optimization Algorithms},
      • booktitle = {IEEE Conference on Decision and Control (CDC)},
      • year = 2022,
      • month = dec,
      • url = {https://www.merl.com/publications/TR2022-159}
      • }
  • MERL Contact:
  • Research Area:

    Optimization

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.

 

  • Related News & Events