Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
This provides a theoretical guarantee for stochastic optimization in nonconvex settings, which is incremental but important for machine learning practitioners dealing with complex loss functions.
The paper proves that the proximal stochastic subgradient method converges at a rate of O(k^{-1/4}) for weakly convex functions, resolving an open question about convergence rates for minimizing sums of smooth nonconvex and convex proximable functions.
We prove that the proximal stochastic subgradient method, applied to a weakly convex problem, drives the gradient of the Moreau envelope to zero at the rate $O(k^{-1/4})$. As a consequence, we resolve an open question on the convergence rate of the proximal stochastic gradient method for minimizing the sum of a smooth nonconvex function and a convex proximable function.