Complexity of finding near-stationary points of convex functions stochastically

Abstract

In a recent paper, we showed that the 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})$. In this supplementary note, we present a stochastic subgradient method for minimizing a convex function, with the improved rate $\tilde{O}(k^{-1/2})$.

9 pages

References in corpus (1)

• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions

Cited by in corpus (4)

• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• Higher-Order Accelerated Methods for Faster Non-Smooth Optimization
• Learning Functions over Sets via Permutation Adversarial Networks
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums