Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
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.
Code (2)
Tasks
Open-Ended Question AnsweringSimilar Papers 제목 키워드 기반
Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems
In this paper, we introduce a stochastic projected subgradient method for weakly convex (i.e., uniformly prox-regular) nonsmooth, nonconvex functions---a wide class of functions which includes the additive and convex com…
On Distributed Non-convex Optimization: Projected Subgradient Method For Weakly Convex Problems in Networks
The stochastic subgradient method is a widely-used algorithm for solving large-scale optimization problems arising in machine learning. Often these problems are neither smooth nor convex. Recently, Davis et al. [1-2] cha…
Compressive SensingDictionary LearningRetrievalStochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions
In non-smooth stochastic optimization, we establish the non-convergence of the stochastic subgradient descent (SGD) to the critical points recently called active strict saddles by Davis and Drusvyatskiy. Such points lie …
Stochastic OptimizationDelayed Algorithms for Distributed Stochastic Weakly Convex Optimization
This paper studies delayed stochastic algorithms for weakly convex optimization in a distributed network with workers connected to a master node. Recently, Xu~et~al.~2022 showed that an inertial stochastic subgradient …
Subgradient Selection Convergence Implies Uniform Subdifferential Set Convergence: And Other Tight Convergences Rates in Stochastic Convex Composite Minimization
In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the …
Stochastic Optimization