---
_id: '14205'
abstract:
- lang: eng
  text: Two of the most fundamental prototypes of greedy optimization are the matching
    pursuit and Frank-Wolfe algorithms. In this paper, we take a unified view on both
    classes of methods, leading to the first explicit convergence rates of matching
    pursuit methods in an optimization sense, for general sets of atoms. We derive
    sublinear (1/t) convergence for both classes on general smooth objectives, and
    linear convergence on strongly convex objectives, as well as a clear correspondence
    of algorithm variants. Our presented algorithms and rates are affine invariant,
    and do not need any incoherence or sparsity assumptions.
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: Rajiv
  full_name: Khanna, Rajiv
  last_name: Khanna
- first_name: Michael
  full_name: Tschannen, Michael
  last_name: Tschannen
- first_name: Martin
  full_name: Jaggi, Martin
  last_name: Jaggi
citation:
  ama: 'Locatello F, Khanna R, Tschannen M, Jaggi M. A unified optimization view on
    generalized matching pursuit and Frank-Wolfe. In: <i>Proceedings of the 20th International
    Conference on Artificial Intelligence and Statistics</i>. Vol 54. ML Research
    Press; 2017:860-868.'
  apa: 'Locatello, F., Khanna, R., Tschannen, M., &#38; Jaggi, M. (2017). A unified
    optimization view on generalized matching pursuit and Frank-Wolfe. In <i>Proceedings
    of the 20th International Conference on Artificial Intelligence and Statistics</i>
    (Vol. 54, pp. 860–868). Fort Lauderdale, FL, United States: ML Research Press.'
  chicago: Locatello, Francesco, Rajiv Khanna, Michael Tschannen, and Martin Jaggi.
    “A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe.”
    In <i>Proceedings of the 20th International Conference on Artificial Intelligence
    and Statistics</i>, 54:860–68. ML Research Press, 2017.
  ieee: F. Locatello, R. Khanna, M. Tschannen, and M. Jaggi, “A unified optimization
    view on generalized matching pursuit and Frank-Wolfe,” in <i>Proceedings of the
    20th International Conference on Artificial Intelligence and Statistics</i>, Fort
    Lauderdale, FL, United States, 2017, vol. 54, pp. 860–868.
  ista: 'Locatello F, Khanna R, Tschannen M, Jaggi M. 2017. A unified optimization
    view on generalized matching pursuit and Frank-Wolfe. Proceedings of the 20th
    International Conference on Artificial Intelligence and Statistics. AISTATS: Conference
    on Artificial Intelligence and Statistics vol. 54, 860–868.'
  mla: Locatello, Francesco, et al. “A Unified Optimization View on Generalized Matching
    Pursuit and Frank-Wolfe.” <i>Proceedings of the 20th International Conference
    on Artificial Intelligence and Statistics</i>, vol. 54, ML Research Press, 2017,
    pp. 860–68.
  short: F. Locatello, R. Khanna, M. Tschannen, M. Jaggi, in:, Proceedings of the
    20th International Conference on Artificial Intelligence and Statistics, ML Research
    Press, 2017, pp. 860–868.
conference:
  end_date: 2017-04-22
  location: Fort Lauderdale, FL, United States
  name: 'AISTATS: Conference on Artificial Intelligence and Statistics'
  start_date: 2017-04-20
date_created: 2023-08-22T14:17:19Z
date_published: 2017-02-21T00:00:00Z
date_updated: 2023-09-13T09:49:10Z
day: '21'
department:
- _id: FrLo
extern: '1'
external_id:
  arxiv:
  - '1702.06457'
intvolume: '        54'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1702.06457
month: '02'
oa: 1
oa_version: Preprint
page: 860-868
publication: Proceedings of the 20th International Conference on Artificial Intelligence
  and Statistics
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: A unified optimization view on generalized matching pursuit and Frank-Wolfe
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 54
year: '2017'
...
---
_id: '14206'
abstract:
- lang: eng
  text: Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe
    (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness
    and theoretical guarantees. MP and FW address optimization over the linear span
    and the convex hull of a set of atoms, respectively. In this paper, we consider
    the intermediate case of optimization over the convex cone, parametrized as the
    conic hull of a generic atom set, leading to the first principled definitions
    of non-negative MP algorithms for which we give explicit convergence rates and
    demonstrate excellent empirical performance. In particular, we derive sublinear
    (O(1/t)) convergence on general smooth and convex objectives, and linear convergence
    (O(e−t)) on strongly convex objectives, in both cases for general sets of atoms.
    Furthermore, we establish a clear correspondence of our algorithms to known algorithms
    from the MP and FW literature. Our novel algorithms and analyses target general
    atom sets and general objective functions, and hence are directly applicable to
    a large variety of learning settings.
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: Michael
  full_name: Tschannen, Michael
  last_name: Tschannen
- first_name: Gunnar
  full_name: Rätsch, Gunnar
  last_name: Rätsch
- first_name: Martin
  full_name: Jaggi, Martin
  last_name: Jaggi
citation:
  ama: 'Locatello F, Tschannen M, Rätsch G, Jaggi M. Greedy algorithms for cone constrained
    optimization with convergence guarantees. In: <i>Advances in Neural Information
    Processing Systems</i>. ; 2017.'
  apa: Locatello, F., Tschannen, M., Rätsch, G., &#38; Jaggi, M. (2017). Greedy algorithms
    for cone constrained optimization with convergence guarantees. In <i>Advances
    in Neural Information Processing Systems</i>. Long Beach, CA, United States.
  chicago: Locatello, Francesco, Michael Tschannen, Gunnar Rätsch, and Martin Jaggi.
    “Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees.”
    In <i>Advances in Neural Information Processing Systems</i>, 2017.
  ieee: F. Locatello, M. Tschannen, G. Rätsch, and M. Jaggi, “Greedy algorithms for
    cone constrained optimization with convergence guarantees,” in <i>Advances in
    Neural Information Processing Systems</i>, Long Beach, CA, United States, 2017.
  ista: 'Locatello F, Tschannen M, Rätsch G, Jaggi M. 2017. Greedy algorithms for
    cone constrained optimization with convergence guarantees. Advances in Neural
    Information Processing Systems. NeurIPS: Neural Information Processing Systems.'
  mla: Locatello, Francesco, et al. “Greedy Algorithms for Cone Constrained Optimization
    with Convergence Guarantees.” <i>Advances in Neural Information Processing Systems</i>,
    2017.
  short: F. Locatello, M. Tschannen, G. Rätsch, M. Jaggi, in:, Advances in Neural
    Information Processing Systems, 2017.
conference:
  end_date: 2017-12-09
  location: Long Beach, CA, United States
  name: 'NeurIPS: Neural Information Processing Systems'
  start_date: 2017-12-04
date_created: 2023-08-22T14:17:38Z
date_published: 2017-05-31T00:00:00Z
date_updated: 2024-10-14T12:29:50Z
day: '31'
department:
- _id: FrLo
extern: '1'
external_id:
  arxiv:
  - '1705.11041'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1705.11041
month: '05'
oa: 1
oa_version: Preprint
publication: Advances in Neural Information Processing Systems
publication_identifier:
  isbn:
  - '9781510860964'
publication_status: published
quality_controlled: '1'
status: public
title: Greedy algorithms for cone constrained optimization with convergence guarantees
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...