Optimal, Stochastic, Non-smooth, Non-convex Optimization through Online-to-Non-convex Conversion

We present new algorithms for optimizing nonsmooth, 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 improved non-smooth analysis also immediately recovers all optimal or best-known results for finding ∊ stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings.