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

Damek Davis, Dmitriy Drusvyatskiy

arXiv (Cornell University) · 2018 · 46 citations · 16 references

DOIFull text

Open access

Concepts

Abstract

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.

References

16