Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems

dc.contributor.author Sun, Ruoyu
dc.contributor.author Hong, Mingyi
dc.contributor.author Hong, Mingyi
dc.contributor.department Industrial and Manufacturing Systems Engineering
dc.date 2018-02-18T04:44:39.000
dc.date.accessioned 2020-06-30T04:47:01Z
dc.date.available 2020-06-30T04:47:01Z
dc.date.copyright Thu Jan 01 00:00:00 UTC 2015
dc.date.embargo 2017-02-21
dc.date.issued 2015-01-01
dc.description.abstract <p>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 <em>K </em>(the number of variable blocks), and are at least <em>K </em>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 <em>K</em> (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 <em>K </em>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).</p>
dc.description.comments <p>This is a proceeding from the <em>29th Conference on Neural Information Processing Systems </em>(2015). Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/imse_conf/47/
dc.identifier.articleid 1054
dc.identifier.contextkey 9722720
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath imse_conf/47
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/44306
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/imse_conf/47/0-NIPS_Permission.pdf|||Sat Jan 15 00:24:53 UTC 2022
dc.source.bitstream archive/lib.dr.iastate.edu/imse_conf/47/2015_Hong_ImprovedIteration.pdf|||Sat Jan 15 00:24:54 UTC 2022
dc.title Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems
dc.type article
dc.type.genre conference
dspace.entity.type Publication
relation.isAuthorOfPublication fc95af08-1606-4279-89b3-d787d4df2369
relation.isOrgUnitOfPublication 51d8b1a0-5b93-4ee8-990a-a0e04d3501b1
File
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
2015_Hong_ImprovedIteration.pdf
Size:
170.01 KB
Format:
Adobe Portable Document Format
Description:
No Thumbnail Available
Name:
0-NIPS_Permission.pdf
Size:
191.99 KB
Format:
Adobe Portable Document Format
Description: