When cyclic coordinate descent outperforms randomized coordinate descent

Mert Gürbüzbalaban; Asuman Ozdaglar; Pablo A. Parrilo; Nuri Denizcan Vanli

Conference paper, 2017

When cyclic coordinate descent outperforms randomized coordinate descent

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo, Nuri Denizcan Vanli

Advances in Neural Information Processing Systems (NeurIPS), 2017. Spotlight presentation.

Publisher page

In brief

Random coordinate selection is usually assumed to be safer than a fixed cyclic order, because worst-case bounds say the cyclic order can be far slower. This paper exhibits a natural class of problems on which the opposite holds: the cyclic order converges provably faster than random selection, and the gap can grow with the dimension.

Topics

Incremental methods & data ordering

Cite

@inproceedings{gurbuzbalaban2017ccd,
  title   = {When cyclic coordinate descent outperforms randomized coordinate descent},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo and Nuri Denizcan Vanli},
  year    = {2017},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  url     = {https://proceedings.neurips.cc/paper/2017/hash/0e7c7d6c41c76b9ee6445ae01cc0181d-Abstract.html},
}