TY - JOUR

T1 - On the complexity analysis of randomized block-coordinate descent methods

AU - Lu, Zhaosong

AU - Xiao, Lin

N1 - Publisher Copyright:
© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

PY - 2015/8/24

Y1 - 2015/8/24

N2 - In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341–362, 2012), Richtárik and Takáč (Math Program 144(1–2):1–38, 2014) for minimizing the sum of a smooth convex function and a block-separable convex function, and derive improved bounds on their convergence rates. In particular, we extend Nesterov’s technique developed in Nesterov (SIAM J Optim 22(2):341–362, 2012) 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 Richtárik and Takáč (Math Program 144(1–2):1–38, 2014). As a result, we also obtain a better high-probability type of iteration complexity. In addition, for unconstrained smooth convex minimization, we develop a new technique called randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov (SIAM J Optim 22(2):341–362, 2012) and establish a sharper expected-value type of convergence rate than the one given in Nesterov (SIAM J Optim 22(2):341–362, 2012).

AB - In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341–362, 2012), Richtárik and Takáč (Math Program 144(1–2):1–38, 2014) for minimizing the sum of a smooth convex function and a block-separable convex function, and derive improved bounds on their convergence rates. In particular, we extend Nesterov’s technique developed in Nesterov (SIAM J Optim 22(2):341–362, 2012) 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 Richtárik and Takáč (Math Program 144(1–2):1–38, 2014). As a result, we also obtain a better high-probability type of iteration complexity. In addition, for unconstrained smooth convex minimization, we develop a new technique called randomized estimate sequence to analyze the accelerated RBCD method proposed by Nesterov (SIAM J Optim 22(2):341–362, 2012) and establish a sharper expected-value type of convergence rate than the one given in Nesterov (SIAM J Optim 22(2):341–362, 2012).

KW - Accelerated coordinate descent

KW - Composite minimization

KW - Convergence rate

KW - Iteration complexity

KW - Randomized block-coordinate descent

UR - http://www.scopus.com/inward/record.url?scp=84937977284&partnerID=8YFLogxK

U2 - 10.1007/s10107-014-0800-2

DO - 10.1007/s10107-014-0800-2

M3 - Article

AN - SCOPUS:84937977284

VL - 152

SP - 615

EP - 642

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -