A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe
This work provides foundational theoretical insights for researchers in optimization and machine learning, though it is incremental as it builds on existing algorithms.
The paper tackled the problem of unifying and analyzing greedy optimization algorithms, specifically matching pursuit and Frank-Wolfe, by deriving explicit convergence rates for matching pursuit methods in an optimization sense, achieving sublinear (1/t) convergence on general smooth objectives and linear convergence on strongly convex objectives.
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.