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

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.

12 pages

References in corpus (1)

• The proximal point method revisited

Cited by in corpus (25)

• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Efficient Algorithms for Smooth Minimax Optimization
• Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Stochastic model-based minimization under high-order growth
• Estimating Barycenters of Measures in High Dimensions
• Complexity of finding near-stationary points of convex functions stochastically
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• An efficient nonconvex reformulation of stagewise convex optimization problems
• Generalized Energy Based Models
• Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization
• Outlier-Robust Sparse Estimation via Non-Convex Optimization
• Stochastic Optimization for Non-convex Inf-Projection Problems
• Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence
• Minimax Optimization with Smooth Algorithmic Adversaries
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives