Skip to main content
Presentation
Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
Proceedings of NIPS 2014
  • Mesiam Razaviyayn, Stanford University
  • Mingyi Hong, Iowa State University
  • Zhi-Quan Luo, University of Minnesota - Twin Cities
  • Jong-Shi Pang, University of Southern California
Document Type
Conference Proceeding
Publication Version
Published Version
Publication Date
1-1-2014
Conference Title
28th Conference on Neural Information Processing Systems
Conference Date
December 8-13, 2014
Geolocation
(45.5016889, -73.56725599999999)
Abstract
Consider the problem of minimizing the sum of a smooth (possibly non-convex) and a convex (possibly nonsmooth) function involving a large number of variables. A popular approach to solve this problem is the block coordinate descent (BCD) method whereby at each iteration only one variable block is updated while the remaining variables are held fixed. With the recent advances in the developments of the multi-core parallel processing technology, it is desirable to parallelize the BCD method by allowing multiple blocks to be updated simultaneously at each iteration of the algorithm. In this work, we propose an inexact parallel BCD approach where at each iteration, a subset of the variables is updated in parallel by minimizing convex approximations of the original objective function. We investigate the convergence of this parallel BCD method for both randomized and cyclic variable selection rules. We analyze the asymptotic and non-asymptotic convergence behavior of the algorithm for both convex and non-convex objective functions. The numerical experiments suggest that for a special case of Lasso minimization problem, the cyclic block selection rule can outperform the randomized rule.
Comments

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

Copyright Owner
The Authors
Language
en
File Format
application/pdf
Citation Information
Mesiam Razaviyayn, Mingyi Hong, Zhi-Quan Luo and Jong-Shi Pang. "Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization" Montreal, CanadaProceedings of NIPS 2014 (2014)
Available at: http://works.bepress.com/mingyi_hong/27/