A KL-based Analysis Framework with Applications to Non-Descent Optimization Methods
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_ | 1866916273855660032 |
|---|---|
| author | Qiu, Junwen Ma, Bohao Li, Xiao Milzarek, Andre |
| author_facet | Qiu, Junwen Ma, Bohao Li, Xiao Milzarek, Andre |
| contents | We propose a novel analysis framework for non-descent-type optimization methodologies in nonconvex scenarios based on the Kurdyka-Lojasiewicz property. Our framework allows covering a broad class of algorithms, including those commonly employed in stochastic and distributed optimization. Specifically, it enables the analysis of first-order methods that lack a sufficient descent property and do not require access to full (deterministic) gradient information. We leverage this framework to establish, for the first time, iterate convergence and the corresponding rates for the decentralized gradient method and federated averaging under mild assumptions. Furthermore, based on the new analysis techniques, we show the convergence of the random reshuffling and stochastic gradient descent method without necessitating typical a priori bounded iterates assumptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_02273 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A KL-based Analysis Framework with Applications to Non-Descent Optimization Methods Qiu, Junwen Ma, Bohao Li, Xiao Milzarek, Andre Optimization and Control Machine Learning 90C06, 90C26, 90C30 We propose a novel analysis framework for non-descent-type optimization methodologies in nonconvex scenarios based on the Kurdyka-Lojasiewicz property. Our framework allows covering a broad class of algorithms, including those commonly employed in stochastic and distributed optimization. Specifically, it enables the analysis of first-order methods that lack a sufficient descent property and do not require access to full (deterministic) gradient information. We leverage this framework to establish, for the first time, iterate convergence and the corresponding rates for the decentralized gradient method and federated averaging under mild assumptions. Furthermore, based on the new analysis techniques, we show the convergence of the random reshuffling and stochastic gradient descent method without necessitating typical a priori bounded iterates assumptions. |
| title | A KL-based Analysis Framework with Applications to Non-Descent Optimization Methods |
| topic | Optimization and Control Machine Learning 90C06, 90C26, 90C30 |
| url | https://arxiv.org/abs/2406.02273 |