Accelerated Gradient Methods with Gradient Restart: Global Linear Convergence
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913859769466880 |
|---|---|
| author | Bao, Chenglong Chen, Liang Li, Jiahong Shen, Zuowei |
| author_facet | Bao, Chenglong Chen, Liang Li, Jiahong Shen, Zuowei |
| contents | Gradient restarting has been shown to improve the numerical performance of accelerated gradient methods. This paper provides a mathematical analysis to understand these advantages. First, we establish global linear convergence guarantees for both the original and gradient restarted accelerated proximal gradient method when solving strongly convex composite optimization problems. Second, through analysis of the corresponding ordinary differential equation model, we prove the continuous trajectory of the gradient restarted Nesterov's accelerated gradient method exhibits global linear convergence for quadratic convex objectives, while the non-restarted version provably lacks this property by [Su, Boyd, and Candés, \textit{J. Mach. Learn. Res.}, 2016, 17(153), 1-43]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07672 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Accelerated Gradient Methods with Gradient Restart: Global Linear Convergence Bao, Chenglong Chen, Liang Li, Jiahong Shen, Zuowei Optimization and Control Numerical Analysis 90C25, 65K05, 65B05, 90C06, 90C30 Gradient restarting has been shown to improve the numerical performance of accelerated gradient methods. This paper provides a mathematical analysis to understand these advantages. First, we establish global linear convergence guarantees for both the original and gradient restarted accelerated proximal gradient method when solving strongly convex composite optimization problems. Second, through analysis of the corresponding ordinary differential equation model, we prove the continuous trajectory of the gradient restarted Nesterov's accelerated gradient method exhibits global linear convergence for quadratic convex objectives, while the non-restarted version provably lacks this property by [Su, Boyd, and Candés, \textit{J. Mach. Learn. Res.}, 2016, 17(153), 1-43]. |
| title | Accelerated Gradient Methods with Gradient Restart: Global Linear Convergence |
| topic | Optimization and Control Numerical Analysis 90C25, 65K05, 65B05, 90C06, 90C30 |
| url | https://arxiv.org/abs/2401.07672 |