On the Iteration Complexity of Cyclic Coordinate Gradient Descent Methods
研究了循环坐标梯度下降法求解可分离非光滑凸最小化问题的迭代复杂度，证明了在光滑函数梯度Lipschitz连续时，算法以O(1/k)速率收敛，并在强凸等条件下达到线性收敛。
The cyclic (block) coordinate gradient descent method is an optimization method that has attracted much interest in applications of applied mathematics, statistics, and engineering. Reasons for this include its simplicity, speed, and stability, as well as its competitive performance on separable nonsmooth convex minimization problems, whose objective function is the sum of a smooth function and a separable (and possibly nonsmooth) convex function, such as the $\ell_1$-regularized linear least squares problem and the $\ell_1$-regularized logistic regression problem. But very little is known about the worst case iteration complexity of the method for solving the separable nonsmooth convex minimization problem. We prove that the method terminates in $O(1/\epsilon)$ iterations with an $\epsilon$-optimal solution, or equivalently, the convergence rate for it is $O(1/k)$, where $k$ is the iteration counter, when the smooth function of the objective has a Lipschitz gradient. Also, the linear rate convergence of the method is proved when the objective is a strongly convex function having a Lipschitz gradient or when the smooth function of the objective is a composition of a strong convex function having a Lipschitz gradient with a linear function, the convex function of the objective is polyhedral, and there is a real number whose corresponding level set of the convex function contains the set of optimal solutions and is bounded.