A Unified Analysis for the Subgradient Methods Minimizing Composite
  Nonconvex, Nonsmooth and Non-Lipschitz Functions
Daoli Zhu Lei Zhao Shuzhong Zhang
In this paper we propose a proximal subgradient method (Prox-SubGrad) for
solving nonconvex and nonsmooth optimization problems without assuming
Lipschitz continuity conditions. A number of subgradient upper bounds and their
relationships are presented. By means of these upper bounding conditions, we
establish some uniform recursive relations for the Moreau envelopes for weakly
convex optimization. This uniform scheme simplifies and unifies the proof
schemes to establish rate of convergence for Prox-SubGrad without assuming
Lipschitz continuity. We present a novel convergence analysis in this context.
Furthermore, we propose some new stochastic subgradient upper bounding
conditions and establish convergence and iteration complexity rates for the
stochastic subgradient method (Sto-SubGrad) to solve non-Lipschitz and
nonsmooth stochastic optimization problems. In particular, for both
deterministic and stochastic subgradient methods on weakly convex optimization
problems without Lipschitz continuity, under any of the subgradient upper
bounding conditions to be introduced in the paper, we show that $O(1/\sqrt{T})$
convergence rate holds in terms of the square of gradient of the Moreau
envelope function, which further improves to be $O(1/{T})$ if, in addition, the
uniform KL condition with exponent $1/2$ holds.