Abstract

 We study a stochastic and distributed algorithm for nonconvex problems whose objective consists of a sum of N nonconvex  -smooth functions, plus a nonsmooth regularizer. The proposed NonconvEx primal-dual SpliTTing (NESTT) algorithm splits the problem into N subproblems, and utilizes an augmented Lagrangian based primal-dual scheme to solve it in a distributed and stochastic manner. With a special non-uniformp sampling, a version of NESTT achieves  -stationary solution using  gradient evaluations, which can be up to O(N ) times better than the (proximal) gradient descent methods. It also achieves -linear convergence rate for nonconvex 1 penalized quadratic problems with polyhedral constraints. Further, we reveal a fundamental connection between primal-dual based methods and a few primal only methods such as IAG/SAG/SAGA.