Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
This provides improved efficiency for stochastic optimization in machine learning, though it appears incremental as it builds on existing online learning techniques.
The paper tackles the problem of optimizing non-smooth, non-convex stochastic objectives by introducing new algorithms that reduce the complexity for finding a (δ,ε)-stationary point from O(ε^{-4}δ^{-1}) to O(ε^{-3}δ^{-1}) stochastic gradient queries, which is shown to be optimal.
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.