In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in [8,11] for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov's technique developed in [8] for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general problem and obtain a sharper expected-value type of convergence rate than the one implied in [11]. Also, we obtain a better high-probability type of iteration complexity, which improves upon the one in [11] by at least the amount $O(n/\epsilon)$, where $\epsilon$ is the target solution accuracy and $n$ is the number of problem blocks. In addition, for unconstrained smooth convex minimization, we develop a new technique called {\it randomized estimate sequence} to analyze the accelerated RBCD method proposed by Nesterov [11] and establish a sharper expected-value type of convergence rate than the one given in [11].

本文主要研究随机块-坐标下降方法在最小化一般光滑凸函数和块可分凸函数的和时的应用，提出一种更加针对性的收敛速度和更好的迭代复杂度，同时针对无约束光滑凸函数极小化问题提出了新的随机评估序列技术并改进了现有算法的收敛速度。

随机块坐标下降方法的复杂性分析