On Matching Pursuit and Coordinate Descent

Francesco Locatello, Anant Raj, Sai Praneeth Karimireddy, Gunnar Raetsch, Bernhard Schölkopf, Sebastian Stich, Martin Jaggi
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3198-3207, 2018.

Abstract

Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection between the two algorithms, we present a unified analysis of both, providing affine invariant sublinear $O(1/t)$ rates on smooth objectives and linear convergence on strongly convex objectives. As a byproduct of our affine invariant analysis of matching pursuit, our rates for steepest coordinate descent are the tightest known. Furthermore, we show the first accelerated convergence rate $O(1/t^2)$ for matching pursuit and steepest coordinate descent on convex objectives.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-locatello18a, title = {On Matching Pursuit and Coordinate Descent}, author = {Locatello, Francesco and Raj, Anant and Karimireddy, Sai Praneeth and Raetsch, Gunnar and Sch{\"o}lkopf, Bernhard and Stich, Sebastian and Jaggi, Martin}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3198--3207}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/locatello18a/locatello18a.pdf}, url = {https://proceedings.mlr.press/v80/locatello18a.html}, abstract = {Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection between the two algorithms, we present a unified analysis of both, providing affine invariant sublinear $O(1/t)$ rates on smooth objectives and linear convergence on strongly convex objectives. As a byproduct of our affine invariant analysis of matching pursuit, our rates for steepest coordinate descent are the tightest known. Furthermore, we show the first accelerated convergence rate $O(1/t^2)$ for matching pursuit and steepest coordinate descent on convex objectives.} }
Endnote
%0 Conference Paper %T On Matching Pursuit and Coordinate Descent %A Francesco Locatello %A Anant Raj %A Sai Praneeth Karimireddy %A Gunnar Raetsch %A Bernhard Schölkopf %A Sebastian Stich %A Martin Jaggi %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-locatello18a %I PMLR %P 3198--3207 %U https://proceedings.mlr.press/v80/locatello18a.html %V 80 %X Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection between the two algorithms, we present a unified analysis of both, providing affine invariant sublinear $O(1/t)$ rates on smooth objectives and linear convergence on strongly convex objectives. As a byproduct of our affine invariant analysis of matching pursuit, our rates for steepest coordinate descent are the tightest known. Furthermore, we show the first accelerated convergence rate $O(1/t^2)$ for matching pursuit and steepest coordinate descent on convex objectives.
APA
Locatello, F., Raj, A., Karimireddy, S.P., Raetsch, G., Schölkopf, B., Stich, S. & Jaggi, M.. (2018). On Matching Pursuit and Coordinate Descent. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3198-3207 Available from https://proceedings.mlr.press/v80/locatello18a.html.

Related Material