Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.10800 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915187013976064 |
|---|---|
| author | Vankov, Daniil Rodomanov, Anton Nedich, Angelia Sankar, Lalitha Stich, Sebastian U. |
| author_facet | Vankov, Daniil Rodomanov, Anton Nedich, Angelia Sankar, Lalitha Stich, Sebastian U. |
| contents | We study gradient methods for optimizing $(L_0, L_1)$-smooth functions, a class that generalizes Lipschitz-smooth functions and has gained attention for its relevance in machine learning. We provide new insights into the structure of this function class and develop a principled framework for analyzing optimization methods in this setting. While our convergence rate estimates recover existing results for minimizing the gradient norm in nonconvex problems, our approach significantly improves the best-known complexity bounds for convex objectives. Moreover, we show that the gradient method with Polyak stepsizes and the normalized gradient method achieve nearly the same complexity guarantees as methods that rely on explicit knowledge of~$(L_0, L_1)$. Finally, we demonstrate that a carefully designed accelerated gradient method can be applied to $(L_0, L_1)$-smooth functions, further improving all previous results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10800 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods Vankov, Daniil Rodomanov, Anton Nedich, Angelia Sankar, Lalitha Stich, Sebastian U. Optimization and Control We study gradient methods for optimizing $(L_0, L_1)$-smooth functions, a class that generalizes Lipschitz-smooth functions and has gained attention for its relevance in machine learning. We provide new insights into the structure of this function class and develop a principled framework for analyzing optimization methods in this setting. While our convergence rate estimates recover existing results for minimizing the gradient norm in nonconvex problems, our approach significantly improves the best-known complexity bounds for convex objectives. Moreover, we show that the gradient method with Polyak stepsizes and the normalized gradient method achieve nearly the same complexity guarantees as methods that rely on explicit knowledge of~$(L_0, L_1)$. Finally, we demonstrate that a carefully designed accelerated gradient method can be applied to $(L_0, L_1)$-smooth functions, further improving all previous results. |
| title | Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.10800 |