On matching pursuit and coordinate descent PMLR Locatello, Francesco ; https://orcid.org/0000-0002-4850-0683 Raj, Anant Karimireddy, Sai Praneeth Rätsch, Gunnar Schölkopf, Bernhard Stich, Sebastian U. Jaggi, Martin 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. ML Research Press 2018 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/14204 Locatello F, Raj A, Karimireddy SP, et al. On matching pursuit and coordinate descent. In: <i>Proceedings of the 35th International Conference on Machine Learning</i>. Vol 80. ML Research Press; 2018:3198-3207. eng info:eu-repo/semantics/altIdentifier/arxiv/1803.09539 info:eu-repo/semantics/openAccess