  Within the unmanageably large class of nonconvex optimization, we consider
the rich subclass of nonsmooth problems that have composite objectives---this
already includes the extensively studied convex, composite objective problems
as a special case. For this subclass, we introduce a powerful, new framework
that permits asymptotically non-vanishing perturbations. In particular, we
develop perturbation-based batch and incremental (online like) nonconvex
proximal splitting algorithms. To our knowledge, this is the first time that
such perturbation-based nonconvex splitting algorithms are being proposed and
analyzed. While the main contribution of the paper is the theoretical
framework, we complement our results by presenting some empirical results on
matrix factorization.
