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

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.

arXiv commentappearing at AISTATS 2017

Cited by in corpus (9)

• Frank-Wolfe Network: An Interpretable Deep Structure for Non-Sparse Coding
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
• Training Neural Networks for and by Interpolation
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
• Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features
• A Bandit Approach to Maximum Inner Product Search
• Bayesian posterior approximation via greedy particle optimization
• A Unifying Perspective on Descent Directions for Constrained Minimization and Switching Criteria
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets