Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization

By Meisam Razaviyayn, Mingyi Hong, Zhi-Quan Tom Luo, Jong-Shi Pang. 2014

112 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Yang Liu
2. Mingyi Hong
3. Qiang Yang
4. Tianjian Chen
5. Yan Kang
6. Yong Cheng
7. Davood Hajinezhad
8. Wotao Yin

In Computational Mechanics

1. Mingyi Hong
2. Wotao Yin
3. Jinshan Zeng
4. Yu Wang
5. Davood Hajinezhad
6. Yang Liu
7. Xinwei Zhang
8. Tuo Zhao

In Numerical Analysis

1. Mingyi Hong
2. Jinshan Zeng
3. Yu Wang
4. Qiang Yang
5. Tuo Zhao
6. Yang Liu
7. Wotao Yin
8. Julien Mairal

Citations in the corpus

• A Communication Efficient Vertical Federated Learning Framework (2019, methodology): “Block coordinate (gradient) descent (BCD) is a classical algorithm for optimization [7] and has been extensively applied to applications in areas such as signal/image processing and machine learning [8–15].”
• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “When f is nonsmooth, the original BCD can get stuck at a non-stationary point [2, Page 94], but not if the nonsmooth part is separable (see [17,31,49, 50,60,41,40,61,62] for results on different forms of f and different variants of BCD).”
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach (2014, background): “It is easy to show that k ˜ ∇ f ( x t ) k = 0 implies that x t is a stationary solution for problem (45) (see, for example, [56], [58]).”
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization (2016, background): “These features are critical in our following rate analysis.”