Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds
研究并行随机坐标下降法求解复合最小化问题，证明其亚线性收敛率，并针对新定义的广义误差界函数类得到线性收敛率，理论估计依赖于随机选取的块数和目标函数的光滑部分的可分离性度量。
In this paper we employ a parallel version of a randomized (block) coordinate descent method for minimizing the sum of a partially separable smooth convex function and a fully separable nonsmooth convex function. Under the assumption of Lipschitz continuity of the gradient of the smooth function, this method has a sublinear convergence rate. Linear convergence rate of the method is obtained for the newly introduced class of generalized error bound functions. We prove that the new class of generalized error bound functions encompasses both global/local error bound functions and smooth strongly convex functions. We also show that the theoretical estimates on the convergence rate depend on the number of blocks chosen randomly and a natural measure of separability of the smooth component of the objective function.