Synchronous Parallel Block Coordinate Descent Method for Nonsmooth Convex Function Minimization  

作　　者：DAI Yutong WENG Yang 

机构地区：[1]College of Mathematics,Sichuan University,Chengdu 610064,China

出　　处：《Journal of Systems Science & Complexity》2020年第2期345-365,共21页系统科学与复杂性学报（英文版）

基　　金：supported by the National Key R&D Program of China under Grant No.2018YFC0830300。

摘　　要：This paper proposes a synchronous parallel block coordinate descent algorithm for minimizing a composite function,which consists of a smooth convex function plus a non-smooth but separable convex function.Due to the generalization of the proposed method,some existing synchronous parallel algorithms can be considered as special cases.To tackle high dimensional problems,the authors further develop a randomized variant,which randomly update some blocks of coordinates at each round of computation.Both proposed parallel algorithms are proven to have sub-linear convergence rate under rather mild assumptions.The numerical experiments on solving the large scale regularized logistic regression with 1 norm penalty show that the implementation is quite efficient.The authors conclude with explanation on the observed experimental results and discussion on the potential improvements.

关 键 词：Block coordinate descent convergence rate convex functions parallel algorithms 

分 类 号：O224[理学—运筹学与控制论]