---
_id: '14204'
abstract:
- lang: eng
  text: 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.
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Francesco
  full_name: Locatello, Francesco
  id: 26cfd52f-2483-11ee-8040-88983bcc06d4
  last_name: Locatello
  orcid: 0000-0002-4850-0683
- first_name: Anant
  full_name: Raj, Anant
  last_name: Raj
- first_name: Sai Praneeth
  full_name: Karimireddy, Sai Praneeth
  last_name: Karimireddy
- first_name: Gunnar
  full_name: Rätsch, Gunnar
  last_name: Rätsch
- first_name: Bernhard
  full_name: Schölkopf, Bernhard
  last_name: Schölkopf
- first_name: Sebastian U.
  full_name: Stich, Sebastian U.
  last_name: Stich
- first_name: Martin
  full_name: Jaggi, Martin
  last_name: Jaggi
citation:
  ama: '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.'
  apa: Locatello, F., Raj, A., Karimireddy, S. P., Rätsch, G., Schölkopf, B., Stich,
    S. U., &#38; Jaggi, M. (2018). On matching pursuit and coordinate descent. In
    <i>Proceedings of the 35th International Conference on Machine Learning</i> (Vol.
    80, pp. 3198–3207). ML Research Press.
  chicago: 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 <i>Proceedings of the 35th International Conference
    on Machine Learning</i>, 80:3198–3207. ML Research Press, 2018.
  ieee: F. Locatello <i>et al.</i>, “On matching pursuit and coordinate descent,”
    in <i>Proceedings of the 35th International Conference on Machine Learning</i>,
    2018, vol. 80, pp. 3198–3207.
  ista: 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.
  mla: Locatello, Francesco, et al. “On Matching Pursuit and Coordinate Descent.”
    <i>Proceedings of the 35th International Conference on Machine Learning</i>, vol.
    80, ML Research Press, 2018, pp. 3198–207.
  short: F. Locatello, A. Raj, S.P. Karimireddy, G. Rätsch, B. Schölkopf, S.U. Stich,
    M. Jaggi, in:, Proceedings of the 35th International Conference on Machine Learning,
    ML Research Press, 2018, pp. 3198–3207.
date_created: 2023-08-22T14:16:25Z
date_published: 2018-07-01T00:00:00Z
date_updated: 2024-10-14T12:29:40Z
day: '01'
department:
- _id: FrLo
extern: '1'
external_id:
  arxiv:
  - '1803.09539'
intvolume: '        80'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1803.09539
month: '07'
oa: 1
oa_version: Preprint
page: 3198-3207
publication: Proceedings of the 35th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: On matching pursuit and coordinate descent
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 80
year: '2018'
...