Complexity of finding near-stationary points of convex functions stochastically

By Damek Davis, Dmitriy Drusvyatskiy. 2018

18 citations recorded by the source corpus.

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 $\widetilde O(k^{-1/2})$.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “We refer interested readers to [12, 13] and the references therein.”
The Complexity of Making the Gradient Small in Stochastic Convex Optimization (2019, methodology): “4The idea of replacing the sub-algorithm in SGD3 was also used by Davis and Drusvyatskiy (2018), who showed that recursive regularization with a projected subgradient method can be used to find near-stationary points for the Moreau envelope of any Lipschitz function.”
Stochastic model-based minimization of weakly convex functions (2018, methodology): “Since this procedure and its analysis is somewhat long and is independent of the rest of the material, we have placed it in an independent arXiv technical report [20].”