A proximally constrained subgradient method finds a nearly stationary point for weakly convex objectives with weakly convex constraints in O(1/epsilon^4) deterministic and O~(1/epsilon^6) stochastic iterations.
Complexity of finding near-stationary points of convex functions stochastically
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In a recent paper, we showed 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})$. In this supplementary note, we present a stochastic subgradient method for minimizing a convex function, with the improved rate $\widetilde O(k^{-1/2})$.
fields
math.OC 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints
A proximally constrained subgradient method finds a nearly stationary point for weakly convex objectives with weakly convex constraints in O(1/epsilon^4) deterministic and O~(1/epsilon^6) stochastic iterations.