On matching pursuit and coordinate descent
Locatello F, Raj A, Karimireddy SP, Rätsch G, Schölkopf B, Stich SU, Jaggi M. 2018. On matching pursuit and coordinate descent. Proceedings of the 35th International Conference on Machine Learning. , PMLR, vol. 80, 3198–3207.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Locatello, FrancescoISTA 
;
Raj, Anant;
Karimireddy, Sai Praneeth;
Rätsch, Gunnar;
Schölkopf, Bernhard;
Stich, Sebastian U.;
Jaggi, Martin
;
Raj, Anant;
Karimireddy, Sai Praneeth;
Rätsch, Gunnar;
Schölkopf, Bernhard;
Stich, Sebastian U.;
Jaggi, MartinDepartment
Series Title
PMLR
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/t2) for matching pursuit and steepest coordinate descent on convex objectives.
Publishing Year
Date Published
2018-07-01
Proceedings Title
Proceedings of the 35th International Conference on Machine Learning
Volume
80
Page
3198-3207
IST-REx-ID
Cite this
Locatello F, Raj A, Karimireddy SP, et al. On matching pursuit and coordinate descent. In: Proceedings of the 35th International Conference on Machine Learning. Vol 80. ML Research Press; 2018:3198-3207.
Locatello, F., Raj, A., Karimireddy, S. P., Rätsch, G., Schölkopf, B., Stich, S. U., & Jaggi, M. (2018). On matching pursuit and coordinate descent. In Proceedings of the 35th International Conference on Machine Learning (Vol. 80, pp. 3198–3207). ML Research Press.
Locatello, Francesco, Anant Raj, Sai Praneeth Karimireddy, Gunnar Rätsch, Bernhard Schölkopf, Sebastian U. Stich, and Martin Jaggi. “On Matching Pursuit and Coordinate Descent.” In Proceedings of the 35th International Conference on Machine Learning, 80:3198–3207. ML Research Press, 2018.
F. Locatello et al., “On matching pursuit and coordinate descent,” in Proceedings of the 35th International Conference on Machine Learning, 2018, vol. 80, pp. 3198–3207.
Locatello F, Raj A, Karimireddy SP, Rätsch G, Schölkopf B, Stich SU, Jaggi M. 2018. On matching pursuit and coordinate descent. Proceedings of the 35th International Conference on Machine Learning. , PMLR, vol. 80, 3198–3207.
Locatello, Francesco, et al. “On Matching Pursuit and Coordinate Descent.” Proceedings of the 35th International Conference on Machine Learning, vol. 80, ML Research Press, 2018, pp. 3198–207.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1803.09539
Google Scholar