NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization

Abstract

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