Provable Bregman-divergence based Methods for Nonconvex and
  Non-Lipschitz Problems
  The (global) Lipschitz smoothness condition is crucial in establishing the
convergence theory for most optimization methods. Unfortunately, most machine
learning and signal processing problems are not Lipschitz smooth. This
motivates us to generalize the concept of Lipschitz smoothness condition to the
relative smoothness condition, which is satisfied by any finite-order
polynomial objective function. Further, this work develops new
Bregman-divergence based algorithms that are guaranteed to converge to a
second-order stationary point for any relatively smooth problem. In addition,
the proposed optimization methods cover both the proximal alternating
minimization and the proximal alternating linearized minimization when we
specialize the Bregman divergence to the Euclidian distance. Therefore, this
work not only develops guaranteed optimization methods for non-Lipschitz smooth
problems but also solves an open problem of showing the second-order
convergence guarantees for these alternating minimization methods.
