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

By Davood Hajinezhad, Mingyi Hong, Tuo Zhao, Zhaoran Wang. 2016

45 citations recorded by the source corpus.

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 $\epsilon$-stationary solution using $\mathcal{O}((\sum_{i=1}^N\sqrt{L_i/N})^2/\epsilon)$ gradient evaluations, which can be up to $\mathcal{O}(N)$ times better than the (proximal) gradient descent methods. It also achieves Q-linear convergence rate for nonconvex $\ell_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.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Hanlin Tang
2. Ji Liu
3. Ce Zhang
4. Mingyi Hong
5. Dan Alistarh
6. Haoran Sun
7. Cédric Renggli
8. Davood Hajinezhad

In Computational Mechanics

1. Hanlin Tang
2. Ji Liu
3. Mingyi Hong
4. Haoran Sun
5. Ce Zhang
6. Davood Hajinezhad
7. Dan Alistarh
8. Mingmin Zhao

In Numerical Analysis

1. Mingyi Hong
2. Haoran Sun
3. Dan Alistarh
4. Ji Liu

Citations in the corpus

• Distributed Learning over Unreliable Networks (2018, methodology): “For example, Hajinezhad et al. (2016) utilize a primal-dual based method for optimizing a finite-sum objective function and proved that it’s possible to achieve a O(n) speedup corresponding to the number of the workers.”
• Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, background): “Once we have xi[2] 6= 0 for some i ∈ [2M/3+1, M ], then according to (42), it is possible to have ∂hi(xi) ∂xi[3] 6= 0, and once this gradient becomes non-zero, the corresponding variable xi[3], i ∈ [2M/3 + 1, M ] can become nonzero.”
• Prox-PDA: The Proximal Primal-Dual Algorithm for Fast Distributed Nonconvex Optimization and Learning Over Networks (2017, methodology): “This observation suggests that in contrast to (Hong et al., 2014; Hajinezhad et al., 2016a) the augmented Lagrangian alone cannot serve as the potential function for Prox-PDA.”