NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
We study a stochastic and distributed algorithm for nonconvex problems whose objective consists of a sum of N nonconvex L i /N -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-uniform sampling, a version of NESTT achieves -stationary solution using O((
L i /N ) 2 / ) gradient evaluations, which can be up to O(N ) times better than the (proximal) gradient descent methods. It also achieves Q-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.
The paper focuses on non-convex problems with objectives consisting of a finite sum of smooth nonconvex loss functions and a nonsmooth convex regularization. In contrast to the recent incremental algorithms, the authors propose new randomized variants of (linearized) ADMM algorithm (or called primal-dual splitting by the authors) to solve the nonconvex problem, which converge sublinearly to stationary solution. Compared to batch gradient descent, the proposed algorithm achieves better  complexity of gradient evaluations in certain cases (e.g. when Lipschitz constants are unbalanced). Some interesting connection to SAG/SAGA is revealed. 
 The idea of addressing finite-sum problems through augmented Lagrangian and ADMM type algorithm is straightforward but new. Convergence results of the new randomized variation for non-convex problems are also novel, to my best knowledge. Despite the notable originality, I think a couple of places need to be further discussed or clarified.   1. Although existing work on nonconvex SVRG/SAGA algorithms [1,21] only provide analysis for smooth problems, I would presume similar results (replacing gradient by prox-gradient) can also be derived with slight modification given that the original algorithms are designed to handle nonsmooth regularization and adapted to non-uniform sampling as well. So it would be good if the author could add such comparison to nonconvex SVRG/SAGA in Table 1 when applicable.   2. It appears to me that in the NESTT-G algorithm (without reducing to the single variable form) , at each iteration, setting the remaining (N-1) x variables to z  would require O(Nd) computation and memory cost, which is not negligible. In some sense, the total computation cost could be O(N) times larger than the number of gradient evaluations. Hence, the comparison between NESTT-G and GD is not quite fair.   3. When reducing to the single variable form, the NESTT-G algorithm reduces to SAGA with special choice of stepsize. However, with uniform Lipschitz constants, the complexity of NESTT-G is worse than SAGA, Perhaps the author could explain what reason leads to the gap, and whether this can be remedied.   4. In the experiment, comparison to Gradient Descent (and non-uniform SAGA/SVRG) should be added. It would be more interesting to see results with larger size instead of just 500 data points. The notation of uniform sampling is confusing and inconsistent with the theory.   5. Minor issues: wrong relation in Thm 2.2; typo in (3.17).   == post-rebuttal answer== I have read the author's rebuttal and updated my scores accordingly.