Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.07061 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916477149380608 |
|---|---|
| author | Ahn, Kwangjun Magakyan, Gagik Cutkosky, Ashok |
| author_facet | Ahn, Kwangjun Magakyan, Gagik Cutkosky, Ashok |
| contents | This work investigates the effectiveness of schedule-free methods, developed by A. Defazio et al. (NeurIPS 2024), in nonconvex optimization settings, inspired by their remarkable empirical success in training neural networks. Specifically, we show that schedule-free SGD achieves optimal iteration complexity for nonsmooth, nonconvex optimization problems. Our proof begins with the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into an optimization algorithm for nonconvex losses. Our general framework not only recovers existing conversions but also leads to two novel conversion schemes. Notably, one of these new conversions corresponds directly to schedule-free SGD, allowing us to establish its optimality. Additionally, our analysis provides valuable insights into the parameter choices for schedule-free SGD, addressing a theoretical gap that the convex theory cannot explain. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07061 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization Ahn, Kwangjun Magakyan, Gagik Cutkosky, Ashok Machine Learning Optimization and Control This work investigates the effectiveness of schedule-free methods, developed by A. Defazio et al. (NeurIPS 2024), in nonconvex optimization settings, inspired by their remarkable empirical success in training neural networks. Specifically, we show that schedule-free SGD achieves optimal iteration complexity for nonsmooth, nonconvex optimization problems. Our proof begins with the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into an optimization algorithm for nonconvex losses. Our general framework not only recovers existing conversions but also leads to two novel conversion schemes. Notably, one of these new conversions corresponds directly to schedule-free SGD, allowing us to establish its optimality. Additionally, our analysis provides valuable insights into the parameter choices for schedule-free SGD, addressing a theoretical gap that the convex theory cannot explain. |
| title | General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2411.07061 |