nonconvex proximal splitting : batch and incremental algorithms

Abstract. Within the unmanageably large class of nonconvex optimization, we consider the rich subclass of nonsmooth problems having composite objectives (this 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 de-velop perturbation-based batch and incremental (online like) nonconvex prox-imal splitting algorithms. To our knowledge, this is the first time that such perturbation-based nonconvex splitting algorithms are being proposed and an-alyzed. While the main contribution of the paper is the theoretical framework, we complement our results by presenting some empirical results on matrix fac-torization