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

By Damek Davis, Dmitriy Drusvyatskiy. 2018

113 citations recorded by the source corpus.

We prove that the projected 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})$.

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

Complexity of finding near-stationary points of convex functions stochastically (2018, methodology): “Abstract In the recent paper [3], it was shown 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).”
Stochastic Subgradient Method Converges on Tame Functions (2018, background): “In particular, the convergence guarantee above for ρ-weakly convex functions appeared only recently in [11,12], with the Moreau envelope f1/(2ρ) playing a central role.”
KALE: When Energy-Based Learning Meets Adversarial Training (2020, background): “While this is a weaker requirement, it also leads to conservative convergence rates (Davis & Drusvyatskiy, 2018).”
Generalized Energy Based Models (2020, methodology): “This directly implies convergence to local optima for sub-gradient methods, according to Davis and Drusvyatskiy (2018); Thekumparampil et al. (2019).”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, background): “Instead of considering a min-max problem, most of them contribute to the non-convex minimization problem [29, 70, 30, 63, 61, 44, 1, 2, 25, 24, 72, 24].”
What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization? (2019, methodology): “The proof of Theorem 31 is similar to the convergence analysis for nonsmooth weakly-convex functions [Davis and Drusvyatskiy, 2018], except here the max-oracle has error (cid:15) .”
Stochastic model-based minimization of weakly convex functions (2018, methodology): “An analogous guarantee was recently shown in [4] when r is convex, using a different argument.”
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal (2019, methodology): “The proof of Theorem 27 is similar to the convergence analysis for nonsmooth weakly-convex functions [Davis and Drusvyatskiy, 2018], except here the max-oracle has error (cid:15) .”