A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe

Francesco Locatello, Rajiv Khanna, Michael Tschannen, Martin Jaggi

TL;DR

This paper unifies two prominent greedy optimization algorithms, Matching Pursuit (MP) and Frank-Wolfe (FW), under a single optimization framework. It provides the first explicit convergence rates for MP methods on general atom sets, showing they achieve sublinear convergence for smooth objectives and linear convergence for strongly convex ones, mirroring FW's performance.

What Problem Does This Paper Address?

Greedy optimization algorithms are widely used in machine learning and signal processing. Two prominent examples are Matching Pursuit (MP) and Frank-Wolfe (FW). While FW algorithms have well-established convergence guarantees, MP algorithms have historically lacked explicit optimization convergence rates, especially for general sets of "atoms" (basis elements). Existing MP convergence analyses often rely on strong assumptions like incoherence or sparsity, which limit their applicability. This paper aims to bridge this gap by providing a unified view of MP and FW, deriving explicit, norm-independent convergence rates for MP that are more general and robust.

Methods

The core of the paper is a unified framework that views both MP and FW as optimizing a quadratic upper bound of the objective function. This allows for a direct comparison and derivation of new convergence rates. Key methodological contributions include:

  • Unified Algorithm Formulation: Presenting generalized versions of MP and FW (Norm-Corrective variants) that share a common structure, making their parallels explicit.
  • New Geometric Complexity Measure: Introducing the "minimal intrinsic directional width" (mDW) of an atom set, which is crucial for deriving linear convergence rates for MP. This measure is shown to be more robust than traditional coherence measures.
  • Affine Invariant Rates: Developing algorithms and convergence rates that are invariant to affine transformations of the problem domain, a desirable property for optimization methods.
  • Handling Approximate Oracles: Extending the analysis to account for approximate Linear Minimization Oracles (LMOs), which are often used in practice for efficiency.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • MP and FW are fundamentally similar: By framing both algorithms around optimizing a quadratic upper bound, the paper reveals their deep structural similarities, going beyond superficial resemblances.
  • MP can be as theoretically robust as FW: The paper demonstrates that MP, when analyzed through this unified lens, can achieve explicit sublinear and linear convergence rates comparable to FW, even without sparsity assumptions.
  • A new geometric measure unlocks linear rates: The introduction of the minimal intrinsic directional width (mDW) provides a novel way to characterize the geometry of atom sets, enabling the derivation of linear convergence rates for MP on strongly convex objectives.
  • Affine invariance is achievable and beneficial: The development of affine invariant algorithms and rates makes the analysis and application of these methods more general and less dependent on specific norm choices.

Key Results

  • First explicit convergence rates for MP: The paper provides the first explicit sublinear ($O(1/t)$) convergence rates for MP on general smooth objectives and linear convergence rates for strongly convex objectives, for general atom sets.
  • Rates are affine invariant: The derived algorithms and rates are invariant under affine transformations.
  • No sparsity or incoherence assumptions needed: The convergence guarantees do not rely on traditional assumptions like sparsity of the solution or incoherence of the atom set.
  • Unified convergence analysis: The paper establishes a clear correspondence between algorithm variants and their convergence properties, showing how FW iterates can converge to MP iterates.
  • Impact of mDW: The linear convergence rate for MP is shown to depend on the novel mDW measure, highlighting its importance in characterizing the geometry of atom sets.

Limitations and Future Work

  • Approximate LMO impact: While the paper considers approximate LMOs, the exact impact of approximation quality on the rates is explicitly reflected, suggesting further analysis could explore tighter bounds or specific approximation strategies.
  • Computational complexity: The paper focuses on theoretical convergence rates. While it mentions that approximate LMOs can be more efficient, a detailed analysis of the practical computational complexity of the proposed algorithms, especially in comparison to existing methods, would be valuable.
  • Empirical validation: The paper includes an illustrative experiment to show the tightness of the linear rate, but more extensive empirical studies on various problems and datasets would be beneficial to demonstrate the practical performance of the proposed algorithms.
  • Further exploration of mDW: The paper introduces mDW and shows its theoretical importance. Future work could explore its properties more deeply and its implications in other optimization contexts.

Summary updated

Abstract

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.
BibTeX
@inproceedings{locatello2017unified,
  author = {Francesco Locatello and Rajiv Khanna and Michael Tschannen and Martin Jaggi},
  title = {{A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=9mWLB0K6GYZ},
}
Figure