Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908481117749248 |
|---|---|
| author | Cutkosky, Ashok Mehta, Harsh Orabona, Francesco |
| author_facet | Cutkosky, Ashok Mehta, Harsh Orabona, Francesco |
| contents | We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for finding a $(δ,ε)$-stationary point from $O(ε^{-4}δ^{-1})$ stochastic gradient queries to $O(ε^{-3}δ^{-1})$, which we also show to be optimal. Our primary technique is a reduction from non-smooth non-convex optimization to online learning, after which our results follow from standard regret bounds in online learning. For deterministic and second-order smooth objectives, applying more advanced optimistic online learning techniques enables a new complexity of $O(ε^{-1.5}δ^{-0.5})$. Our techniques also recover all optimal or best-known results for finding $ε$ stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03775 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion Cutkosky, Ashok Mehta, Harsh Orabona, Francesco Machine Learning Optimization and Control We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for finding a $(δ,ε)$-stationary point from $O(ε^{-4}δ^{-1})$ stochastic gradient queries to $O(ε^{-3}δ^{-1})$, which we also show to be optimal. Our primary technique is a reduction from non-smooth non-convex optimization to online learning, after which our results follow from standard regret bounds in online learning. For deterministic and second-order smooth objectives, applying more advanced optimistic online learning techniques enables a new complexity of $O(ε^{-1.5}δ^{-0.5})$. Our techniques also recover all optimal or best-known results for finding $ε$ stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings. |
| title | Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2302.03775 |