The Global R-linear Convergence of Nesterov's Accelerated Gradient Method with Unknown Strongly Convex Parameter
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912395577786368 |
|---|---|
| author | Bao, Chenglong Chen, Liang Li, Jiahong |
| author_facet | Bao, Chenglong Chen, Liang Li, Jiahong |
| contents | The Nesterov accelerated gradient (NAG) method is an important extrapolation-based numerical algorithm that accelerates the convergence of the gradient descent method in convex optimization. When dealing with an objective function that is $μ$-strongly convex, selecting extrapolation coefficients dependent on $μ$ enables global R-linear convergence. In cases where $μ$ is unknown, a commonly adopted approach is to set the extrapolation coefficient using the original NAG method. This choice allows for achieving the optimal iteration complexity among first-order methods for general convex problems. However, it remains unknown whether the NAG method with an unknown strongly convex parameter exhibits global R-linear convergence for strongly convex problems. In this work, we answer this question positively by establishing the Q-linear convergence of certain constructed Lyapunov sequences. Furthermore, we extend our result to the global R-linear convergence of the accelerated proximal gradient method, which is employed for solving strongly convex composite optimization problems. Interestingly, these results contradict the findings of the continuous counterpart of the NAG method in [Su, Boyd, and Candés, J. Mach. Learn. Res., 2016, 17(153), 1-43], where the convergence rate by the suggested ordinary differential equation cannot exceed the $O(1/{\tt poly}(k))$ for strongly convex functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14080 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Global R-linear Convergence of Nesterov's Accelerated Gradient Method with Unknown Strongly Convex Parameter Bao, Chenglong Chen, Liang Li, Jiahong Optimization and Control Numerical Analysis 90C25, 65K05, 65B05, 90C06, 90C30 The Nesterov accelerated gradient (NAG) method is an important extrapolation-based numerical algorithm that accelerates the convergence of the gradient descent method in convex optimization. When dealing with an objective function that is $μ$-strongly convex, selecting extrapolation coefficients dependent on $μ$ enables global R-linear convergence. In cases where $μ$ is unknown, a commonly adopted approach is to set the extrapolation coefficient using the original NAG method. This choice allows for achieving the optimal iteration complexity among first-order methods for general convex problems. However, it remains unknown whether the NAG method with an unknown strongly convex parameter exhibits global R-linear convergence for strongly convex problems. In this work, we answer this question positively by establishing the Q-linear convergence of certain constructed Lyapunov sequences. Furthermore, we extend our result to the global R-linear convergence of the accelerated proximal gradient method, which is employed for solving strongly convex composite optimization problems. Interestingly, these results contradict the findings of the continuous counterpart of the NAG method in [Su, Boyd, and Candés, J. Mach. Learn. Res., 2016, 17(153), 1-43], where the convergence rate by the suggested ordinary differential equation cannot exceed the $O(1/{\tt poly}(k))$ for strongly convex functions. |
| title | The Global R-linear Convergence of Nesterov's Accelerated Gradient Method with Unknown Strongly Convex Parameter |
| topic | Optimization and Control Numerical Analysis 90C25, 65K05, 65B05, 90C06, 90C30 |
| url | https://arxiv.org/abs/2308.14080 |