Revisiting Subgradient Method: Complexity and Convergence Beyond
  Lipschitz Continuity
Xiao Li Lei Zhao Daoli Zhu Anthony Man-Cho So
The subgradient method is one of the most fundamental algorithmic schemes for
nonsmooth optimization. The existing complexity and convergence results for
this algorithm are mainly derived for Lipschitz continuous objective functions.
In this work, we first extend the typical complexity results for the
subgradient method to convex and weakly convex minimization without assuming
Lipschitz continuity. Specifically, we establish $\mathcal{O}(1/\sqrt{T})$
bound in terms of the suboptimality gap ``$f(x) - f^*$'' for convex case and
$\mathcal{O}(1/{T}^{1/4})$ bound in terms of the gradient of the Moreau
envelope function for weakly convex case. Furthermore, we provide convergence
results for non-Lipschitz convex and weakly convex objective functions using
proper diminishing rules on the step sizes. In particular, when $f$ is convex,
we show $\mathcal{O}(\log(k)/\sqrt{k})$ rate of convergence in terms of the
suboptimality gap. With an additional quadratic growth condition, the rate is
improved to $\mathcal{O}(1/k)$ in terms of the squared distance to the optimal
solution set. When $f$ is weakly convex, asymptotic convergence is derived. The
central idea is that the dynamics of properly chosen step sizes rule fully
controls the movement of the subgradient method, which leads to boundedness of
the iterates, and then a trajectory-based analysis can be conducted to
establish the desired results. To further illustrate the wide applicability of
our framework, we extend the complexity results to the truncated subgradient,
the stochastic subgradient, the incremental subgradient, and the proximal
subgradient methods for non-Lipschitz functions.