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

Abstract

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.

35 pages, 2 figures

References in corpus (3)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Convex Optimization for Big Data
• Fast Incremental Method for Nonconvex Optimization

Cited by in corpus (11)

• Non-Intrusive Energy Disaggregation Using Non-negative Matrix Factorization with Sum-to-k Constraint
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Distributed Deep Learning with Event-Triggered Communication
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• SAGA and Restricted Strong Convexity
• A Nonlinear Bregman Primal-Dual Framework for Optimizing Nonconvex Infimal Convolutions
• Estimation of Graphical Models through Structured Norm Minimization