First-order Methods for Affinely Constrained Composite Non-convex
  Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods
Wei Liu Qihang Lin Yangyang Xu
Many recent studies on first-order methods (FOMs) focus on \emph{composite
non-convex non-smooth} optimization with linear and/or nonlinear function
constraints. Upper (or worst-case) complexity bounds have been established for
these methods. However, little can be claimed about their optimality as no
lower bound is known, except for a few special \emph{smooth non-convex} cases.
In this paper, we make the first attempt to establish lower complexity bounds
of FOMs for solving a class of composite non-convex non-smooth optimization
with linear constraints. Assuming two different first-order oracles, we
establish lower complexity bounds of FOMs to produce a (near)
$\epsilon$-stationary point of a problem (and its reformulation) in the
considered problem class, for any given tolerance $\epsilon>0$. In addition, we
present an inexact proximal gradient (IPG) method by using the more relaxed one
of the two assumed first-order oracles. The oracle complexity of the proposed
IPG, to find a (near) $\epsilon$-stationary point of the considered problem and
its reformulation, matches our established lower bounds up to a logarithmic
factor. Therefore, our lower complexity bounds and the proposed IPG method are
almost non-improvable.