Timezone: »

 
Poster
NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
Davood Hajinezhad · Mingyi Hong · Tuo Zhao · Zhaoran Wang

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #29
in Tuesday Posters »
We study a stochastic and distributed algorithm for nonconvex problems whose objective consists a sum $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 {\it primal-dual} based methods and a few {\it primal only} methods such as IAG/SAG/SAGA.
Keywords: Convex Optimization · (Other) Optimization · Stochastic Methods · (Other) Machine Learning Topics
[ PDF] 

Author Information

Davood Hajinezhad (Iowa State University)
Mingyi Hong (iowa state university)
Tuo Zhao (Johns Hopkins University)
Zhaoran Wang (Princeton University)

More from the Same Authors