Skip to main content
Presentation
Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems
NIPS Proceedings 2015
  • Ruoyu Sun, Stanford University
  • Mingyi Hong, Iowa State University
Document Type
Conference Proceeding
Publication Version
Published Version
Publication Date
1-1-2015
Conference Title
29th Conference on Neural Information Processing Systems
Conference Date
December 7-12, 2015
Geolocation
(45.5016889, -73.56725599999999)
Abstract
The iteration complexity of the block-coordinate descent (BCD) type algorithm has been under extensive investigation. It was recently shown that for convex problems the classical cyclic BCGD (block coordinate gradient descent) achieves an O(1/r) complexity (r is the number of passes of all blocks). However, such bounds are at least linearly depend on K (the number of variable blocks), and are at least K times worse than those of the gradient descent (GD) and proximal gradient (PG) methods.In this paper, we close such theoretical performance gap between cyclic BCD and GD/PG. First we show that for a family of quadratic nonsmooth problems, the complexity bounds for cyclic Block Coordinate Proximal Gradient (BCPG), a popular variant of BCD, can match those of the GD/PG in terms of dependency on K (up to a \log^2(K) factor). Second, we establish an improved complexity bound for Coordinate Gradient Descent (CGD) for general convex problems which can match that of GD in certain scenarios. Our bounds are sharper than the known bounds as they are always at least K times worse than GD. {Our analyses do not depend on the update order of block variables inside each cycle, thus our results also apply to BCD methods with random permutation (random sampling without replacement, another popular variant).
Comments

This is a proceeding from the 29th Conference on Neural Information Processing Systems (2015). Posted with permission.

Copyright Owner
The Authors
Language
en
File Format
application/pdf
Citation Information
Ruoyu Sun and Mingyi Hong. "Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems" Montreal, CanadaNIPS Proceedings 2015 (2015)
Available at: http://works.bepress.com/mingyi_hong/26/