Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization
We study gradient-based optimization methods obtained by direct Runge-Kutta discretization of the ordinary differential equation (ODE) describing the movement of a heavy-ball under constant friction coefficient. When the function is high-order smooth and strongly convex, we show that directly simula...
| Main Authors: | , , |
|---|---|
| 其他作者: | |
| 格式: | 文件 |
| 语言: | English |
| 出版: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| 在线阅读: | https://hdl.handle.net/1721.1/130426 |
| _version_ | 1826207945669476352 |
|---|---|
| author | Zhang, Jingzhao Sra, Suvrit Jadbabaie, Ali |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Zhang, Jingzhao Sra, Suvrit Jadbabaie, Ali |
| author_sort | Zhang, Jingzhao |
| collection | MIT |
| description | We study gradient-based optimization methods obtained by direct Runge-Kutta discretization of the ordinary differential equation (ODE) describing the movement of a heavy-ball under constant friction coefficient. When the function is high-order smooth and strongly convex, we show that directly simulating the ODE with known numerical integrators achieve acceleration in a nontrivial neighborhood of the optimal solution. In particular, the neighborhood may grow larger as the condition number of the function increases. Furthermore, our results also hold for nonconvex but quasi-strongly convex objectives. We provide numerical experiments that verify the theoretical rates predicted by our results. |
| first_indexed | 2024-09-23T13:57:08Z |
| format | Article |
| id | mit-1721.1/130426 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:57:08Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1304262022-10-01T18:13:56Z Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization Zhang, Jingzhao Sra, Suvrit Jadbabaie, Ali Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We study gradient-based optimization methods obtained by direct Runge-Kutta discretization of the ordinary differential equation (ODE) describing the movement of a heavy-ball under constant friction coefficient. When the function is high-order smooth and strongly convex, we show that directly simulating the ODE with known numerical integrators achieve acceleration in a nontrivial neighborhood of the optimal solution. In particular, the neighborhood may grow larger as the condition number of the function increases. Furthermore, our results also hold for nonconvex but quasi-strongly convex objectives. We provide numerical experiments that verify the theoretical rates predicted by our results. 2021-04-09T15:16:23Z 2021-04-09T15:16:23Z 2019-12 2021-04-07T15:01:00Z Article http://purl.org/eprint/type/ConferencePaper 0743-1546 https://hdl.handle.net/1721.1/130426 Zhang, Jingzhao et al. “Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization.” Paper presented in the Proceedings of the IEEE Conference on Decision and Control, Nice, France , December 11-13 2019, Institute of Electrical and Electronics Engineers (IEEE) © 2019 The Author(s) en 10.1109/CDC40024.2019.9030046 Proceedings of the IEEE Conference on Decision and Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Zhang, Jingzhao Sra, Suvrit Jadbabaie, Ali Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization |
| title | Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization |
| title_full | Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization |
| title_fullStr | Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization |
| title_full_unstemmed | Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization |
| title_short | Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization |
| title_sort | acceleration in first order quasi strongly convex optimization by ode discretization |
| url | https://hdl.handle.net/1721.1/130426 |
| work_keys_str_mv | AT zhangjingzhao accelerationinfirstorderquasistronglyconvexoptimizationbyodediscretization AT srasuvrit accelerationinfirstorderquasistronglyconvexoptimizationbyodediscretization AT jadbabaieali accelerationinfirstorderquasistronglyconvexoptimizationbyodediscretization |