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

2018/02/08 by Damek Davis, Davis, Damek, Dmitriy Drusvyatskiy +1 · 18 citations
Computer Science · Engineering · Mathematics · #65K05 #65K10 #90C15 #90C30 #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #msc:65K05 #msc:65K10 #msc:90C15 #msc:90C30

paper · pdf · doi:10.48550/arxiv.1802.02988

12 pages

openalex publication_date 2018/02/08 · arxiv created 2018/02/19 · arxiv updated 2018/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

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?
• Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises
• Non-smooth stochastic gradient descent using smoothing functions
• Minimax Optimization with Smooth Algorithmic Adversaries
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Generalized Energy Based Models
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• An efficient nonconvex reformulation of stagewise convex optimization problems
• Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing
• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Optimal Deterministic Oracle Complexity for Weakly Convex Optimization

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