Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex Optimization
Accelerated gradient methods have the potential of achieving optimal convergence rates and have successfully been used in many practical applications. Despite this fact, the rationale underlying these accelerated methods remain elusive. In this work, we study gradient-based accelerated optimization...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8979360/ |
| _version_ | 1818736529393057792 |
|---|---|
| author | Ruijuan Chen Xiuting Li |
| author_facet | Ruijuan Chen Xiuting Li |
| author_sort | Ruijuan Chen |
| collection | DOAJ |
| description | Accelerated gradient methods have the potential of achieving optimal convergence rates and have successfully been used in many practical applications. Despite this fact, the rationale underlying these accelerated methods remain elusive. In this work, we study gradient-based accelerated optimization methods obtained by directly discretizing a second-order ordinary differential equation (ODE) related to the Bregman Lagrangian. We show that for sufficiently smooth objectives, the acceleration can be achieved by discretizing the proposed ODE using s-stage q-order implicit Runge-Kutta integrators. In particular, we prove that under the assumption of convexity and sufficient smoothness, the sequence of iteration generated by the proposed accelerated method stably converges to the optimal solution at a rate of O((1-C̅<sub>p,q</sub>·μ/L)<sup>N</sup>N<sup>-p</sup>), where p ≥ 2 is the parameter in the second-order ODE and C̅<sub>p,q</sub> is a constant depending on p and q. Several numerical experiments are given to verify the convergence results. |
| first_indexed | 2024-12-18T00:38:36Z |
| format | Article |
| id | doaj.art-68b07ecb83864473bcbfd8f4e70b9ff5 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-18T00:38:36Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-68b07ecb83864473bcbfd8f4e70b9ff52022-12-21T21:26:57ZengIEEEIEEE Access2169-35362020-01-018286242863410.1109/ACCESS.2020.29670648979360Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex OptimizationRuijuan Chen0https://orcid.org/0000-0003-0745-4032Xiuting Li1https://orcid.org/0000-0002-3876-583XSchool of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan, ChinaSchool of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan, ChinaAccelerated gradient methods have the potential of achieving optimal convergence rates and have successfully been used in many practical applications. Despite this fact, the rationale underlying these accelerated methods remain elusive. In this work, we study gradient-based accelerated optimization methods obtained by directly discretizing a second-order ordinary differential equation (ODE) related to the Bregman Lagrangian. We show that for sufficiently smooth objectives, the acceleration can be achieved by discretizing the proposed ODE using s-stage q-order implicit Runge-Kutta integrators. In particular, we prove that under the assumption of convexity and sufficient smoothness, the sequence of iteration generated by the proposed accelerated method stably converges to the optimal solution at a rate of O((1-C̅<sub>p,q</sub>·μ/L)<sup>N</sup>N<sup>-p</sup>), where p ≥ 2 is the parameter in the second-order ODE and C̅<sub>p,q</sub> is a constant depending on p and q. Several numerical experiments are given to verify the convergence results.https://ieeexplore.ieee.org/document/8979360/Implicit Runge-Kutta methodsordinary differential equationsunconstrained convex optimization |
| spellingShingle | Ruijuan Chen Xiuting Li Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex Optimization IEEE Access Implicit Runge-Kutta methods ordinary differential equations unconstrained convex optimization |
| title | Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex Optimization |
| title_full | Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex Optimization |
| title_fullStr | Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex Optimization |
| title_full_unstemmed | Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex Optimization |
| title_short | Implicit Runge-Kutta Methods for Accelerated Unconstrained Convex Optimization |
| title_sort | implicit runge kutta methods for accelerated unconstrained convex optimization |
| topic | Implicit Runge-Kutta methods ordinary differential equations unconstrained convex optimization |
| url | https://ieeexplore.ieee.org/document/8979360/ |
| work_keys_str_mv | AT ruijuanchen implicitrungekuttamethodsforacceleratedunconstrainedconvexoptimization AT xiutingli implicitrungekuttamethodsforacceleratedunconstrainedconvexoptimization |