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 for Generalized Matching Pursuit that do not rely on restrictive assumptions like signal sparsity or dictionary incoherence.
Introduction
Greedy algorithms, such as Matching Pursuit (MP) and Frank-Wolfe (FW), are essential tools in machine learning and signal processing, powering applications from compressed sensing to matrix completion. Historically, however, their theoretical foundations have remained fragmented. MP is typically analyzed through the lens of "sparse recovery," requiring strict "incoherence" conditions on the dictionary of atoms. In contrast, FW is studied within optimization theory, focusing on objective function decrease.
This work bridges this gap by providing a unified theoretical framework. By treating MP as an optimization problem over a general smooth objective, the authors derive convergence rates that do not depend on signal sparsity or dictionary incoherence, offering a more robust understanding of these pervasive methods.
A Unified Algorithmic Framework
The core of the unification lies in the realization that both families of algorithms rely on the same fundamental subroutine: a Linear Minimization Oracle (LMO). This oracle identifies the "best" atom from a dictionary $\mathcal{A}$ by finding the one with the largest inner product with the negative gradient of the objective function.
Matching Pursuit and its Variants
Classic Matching Pursuit (Algorithm 1) iteratively builds a solution by adding atoms that best align with the current residual. While effective for least-squares problems, its general convergence properties for arbitrary smooth functions were previously less understood.
Norm-Corrective and Generalized Variants
To improve efficiency and generality, the authors introduce Norm-Corrective versions of these algorithms. Instead of minimizing the original objective $f$ at every step—which can be computationally expensive—these variants minimize a quadratic surrogate (a local upper bound).
Furthermore, the paper extends MP to Generalized Matching Pursuit (GMP), allowing it to handle any smooth convex objective. They also propose affine invariant versions, ensuring that performance remains consistent under linear transformations or re-parameterizations of the coordinate system.
Key Insights: Geometry and Convergence
A primary insight of this work is the "blown-up" relationship between the two methods: Frank-Wolfe is essentially Matching Pursuit restricted to a bounded convex set. Specifically, as the scale of the convex hull used in FW approaches infinity, the FW iterates converge to those of MP.
Moving Beyond Coherence
Traditional analysis of MP fails if the dictionary contains very similar atoms (high coherence). This paper introduces a new geometric complexity measure: the minimal intrinsic directional width (mDW). Unlike coherence, mDW is robust; the addition of a single "bad" atom does not compromise the convergence guarantees for the entire set. This shift allows for a $1/t$ convergence rate even when the optimal solution is not sparse.
Convergence Results
The unified framework yields several significant theoretical results:
- Sublinear Convergence: For general smooth objectives, both unified FW and GMP achieve a convergence rate of $O(1/t)$. This is the first explicit proof of such a rate for MP without incoherence assumptions.
- Linear Convergence: For strongly convex objectives, GMP is shown to converge at a linear (geometric) rate, $O(e^{-kt})$, where the rate constant $k$ is explicitly tied to the mDW.
- Robustness: These guarantees hold even when the LMO is only approximate, a critical feature for practical implementations where finding the exact optimal atom is often computationally prohibitive.
Conclusion and Future Directions
By unifying Matching Pursuit and Frank-Wolfe, this research provides a powerful new toolkit for analyzing greedy optimization. While the current theory is primarily situated in Hilbert spaces and depends on a constant $\rho$ (an upper bound on the atomic norm), it sets the stage for future work in more general Banach spaces and more complex atom sets, such as tensors. This optimization-centric view shifts the focus from "finding the right atoms" to "efficiently reducing the error," providing a more general and robust foundation for greedy methods in machine learning.
Summary updated