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

2018/02/08 by Davis, Damek, Drusvyatskiy, Dmitriy · 5 citations
#65K05 #65K10 #90C15 #90C30 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1802.02988

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.

Cited by

• Robust Least Squares Problems with Binary Uncertain Data
• On Tackling High-Dimensional Nonconvex Stochastic Optimization via Stochastic First-Order Methods with Non-smooth Proximal Terms and Variance Reduction
• The Measure of Deception: An Analysis of Data Forging in Machine Unlearning
• Zeroth-Order Non-smooth Non-convex Optimization via Gaussian Smoothing
• Can SGD Handle Heavy-Tailed Noise?

Related

• Complexity of finding near-stationary points of convex functions stochastically
• Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems
• Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity
• A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions
• Handbook of Convergence Theorems for (Stochastic) Gradient Methods