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

Understand

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.