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

arXiv: https://arxiv.org/abs/1605.07747 · HTML: https://mlsanity.com/paper/1605.07747/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2016.

## Built on by (most cited first, 5 of 5)

- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)
- [Beyond ADMM: A Unified Client-variance-reduced Adaptive Federated Learning Framework](https://mlsanity.com/paper/2212.01519/) (2022)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Privacy-preserving Federated Primal-dual Learning for Non-convex and Non-smooth Problems with Model Sparsification](https://mlsanity.com/paper/2310.19558/) (2023)
- [Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum](https://mlsanity.com/paper/2504.12742/) (2025)

## Abstract (arXiv)

We study a stochastic and distributed algorithm for nonconvex problems whose objective consists of a sum of N nonconvex Li/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((sumi=1N√Li/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.