TR2022-159
ODE Discretization Schemes as Optimization Algorithms
-
- "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}
- }
,
- "ODE Discretization Schemes as Optimization Algorithms", IEEE Conference on Decision and Control (CDC), December 2022.
-
MERL Contact:
-
Research Area:
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
-
NEWS MERL Researchers Presented Six Papers at the 2022 IEEE Conference on Decision and Control (CDC’22) Date: December 6, 2022 - December 9, 2022
Where: Cancún, Mexico
MERL Contacts: Mouhacine Benosman; Karl Berntorp; Ankush Chakrabarty; Devesh K. Jha; Arvind Raghunathan; Diego Romeres; Yebin Wang
Research Areas: Control, OptimizationBrief- MERL researchers presented six papers at the Conference on Decision and Control that was held in Cancún, Mexico from December 6-9, 2022. The papers covered a broad range of topics in the areas of decision making and control, including Bayesian optimization, quadratic programming, solution of differential equations, distributed Kalman filtering, thermal monitoring of batteries, and closed-loop control optimization.