Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915765023670272 |
|---|---|
| author | Kassing, Sebastian Weissmann, Simon |
| author_facet | Kassing, Sebastian Weissmann, Simon |
| contents | In this work, we analyze the convergence of Polyak's heavy ball method in both continuous and discrete time for non-convex $C^4$-objective functions satisfying the Polyak-Lojasiewicz inequality. Under this weak assumption, we recover the asymptotic convergence rates originally derived by Polyak in [Polyak, U.S.S.R. Comput. Math. and Math. Phys., 1964] for strongly convex objectives. Our results demonstrate that the heavy ball method exhibits asymptotic local acceleration on this class of functions. In particular, in the discrete time setting, we prove local convergence of the iterates to a minimum once the method enters a sufficiently small neighborhood of the set of minima, for a broad range of hyperparameters, including aggressive choices for the momentum parameter and the step-size for which global convergence is known to fail. Instead of the usually employed Lyapunov-type arguments, our approach leverages a new differential geometric perspective of the Polyak-Lojasiewicz inequality proposed in [Rebjock and Boumal, Math. Program., 2025]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_16849 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality Kassing, Sebastian Weissmann, Simon Optimization and Control Machine Learning Primary 90C26, Secondary 90C30, 37C10, 34D45 In this work, we analyze the convergence of Polyak's heavy ball method in both continuous and discrete time for non-convex $C^4$-objective functions satisfying the Polyak-Lojasiewicz inequality. Under this weak assumption, we recover the asymptotic convergence rates originally derived by Polyak in [Polyak, U.S.S.R. Comput. Math. and Math. Phys., 1964] for strongly convex objectives. Our results demonstrate that the heavy ball method exhibits asymptotic local acceleration on this class of functions. In particular, in the discrete time setting, we prove local convergence of the iterates to a minimum once the method enters a sufficiently small neighborhood of the set of minima, for a broad range of hyperparameters, including aggressive choices for the momentum parameter and the step-size for which global convergence is known to fail. Instead of the usually employed Lyapunov-type arguments, our approach leverages a new differential geometric perspective of the Polyak-Lojasiewicz inequality proposed in [Rebjock and Boumal, Math. Program., 2025]. |
| title | Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality |
| topic | Optimization and Control Machine Learning Primary 90C26, Secondary 90C30, 37C10, 34D45 |
| url | https://arxiv.org/abs/2410.16849 |