## Abstract

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).

Original language | English (US) |
---|---|

Pages (from-to) | 615-642 |

Number of pages | 28 |

Journal | Mathematical Programming |

Volume | 152 |

Issue number | 1-2 |

DOIs | |

State | Published - Aug 24 2015 |

Externally published | Yes |

### Bibliographical note

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

## Keywords

- Accelerated coordinate descent
- Composite minimization
- Convergence rate
- Iteration complexity
- Randomized block-coordinate descent