Skip to main content
Presentation
NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
Proceedings of NIPS 2016
  • Davood Hajinezhad, Iowa State University
  • Mingyi Hong, Iowa State University
  • Tuo Zhao, Georgia Institute of Technology
  • Zhaoran Wang, Princeton University
Document Type
Conference Proceeding
Publication Version
Published Version
Publication Date
1-1-2016
Conference Title
30th Conference on Neural Information Processing Systems
Conference Date
December 5-9, 2016
Geolocation
(41.3850639, 2.1734034999999494)
Abstract
We study a stochastic and distributed algorithm for nonconvex problems whose objective consists a sum 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 e-1 stationary solution using...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 l1 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.
Comments

This is a proceeding from the 30th Conference on Neural Information Processing Systems (2016). Posted with permission.

Copyright Owner
The Authors
Language
en
File Format
application/pdf
Citation Information
Davood Hajinezhad, Mingyi Hong, Tuo Zhao and Zhaoran Wang. "NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization" Barcelona, SpainProceedings of NIPS 2016 (2016)
Available at: http://works.bepress.com/mingyi_hong/29/