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

Francesco Locatello, Rajiv Khanna, Michael Tschannen, Martin Jaggi
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:860-868, 2017.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-locatello17a, title = {{A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe}}, author = {Locatello, Francesco and Khanna, Rajiv and Tschannen, Michael and Jaggi, Martin}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {860--868}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/locatello17a/locatello17a.pdf}, url = {https://proceedings.mlr.press/v54/locatello17a.html}, 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.} }
Endnote
%0 Conference Paper %T A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe %A Francesco Locatello %A Rajiv Khanna %A Michael Tschannen %A Martin Jaggi %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-locatello17a %I PMLR %P 860--868 %U https://proceedings.mlr.press/v54/locatello17a.html %V 54 %X 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.
APA
Locatello, F., Khanna, R., Tschannen, M. & Jaggi, M.. (2017). A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:860-868 Available from https://proceedings.mlr.press/v54/locatello17a.html.

Related Material