On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization

Abstract

In this paper, we investigate the non-asymptotic stationary convergence behavior of Stochastic Mirror Descent (SMD) for nonconvex optimization. We focus on a general class of nonconvex nonsmooth stochastic optimization problems, in which the objective can be decomposed into a relatively weakly convex function (possibly non-Lipschitz) and a simple non-smooth convex regularizer. We prove that SMD, without the use of mini-batch, is guaranteed to converge to a stationary point in a convergence rate of $\mathcal{O}(1/\sqrt{t})$. The efficiency estimate matches with existing results for stochastic subgradient method, but is evaluated under a stronger stationarity measure. Our convergence analysis applies to both the original SMD and its proximal version, as well as the deterministic variants, for solving relatively weakly convex problems.

arXiv comment15 pages

References in corpus (3)

• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• The proximal point method revisited
• "Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent

Cited by in corpus (17)

• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
• A generalization of regularized dual averaging and its dynamics
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Stochastic model-based minimization under high-order growth
• Mirror Descent View for Neural Network Quantization
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
• Geometry-Aware Gradient Algorithms for Neural Architecture Search
• Enhanced Bilevel Optimization via Bregman Distance
• Dual Averaging is Surprisingly Effective for Deep Learning Optimization
• Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence
• Bregman Gradient Policy Optimization
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval