Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets

Thomas Kerdreux, Lewis Liu, Simon Lacoste-Julien, Damien Scieur
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5398-5408, 2021.

Abstract

It is known that the Frank-Wolfe (FW) algorithm, which is affine covariant, enjoys faster convergence rates than $\mathcal{O}\left(1/K\right)$ when the constraint set is strongly convex. However, these results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds, in contradiction with FW’s affine covariant property. In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. We show that our rates are better than any other known convergence rates of FW in this setting. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function present similar performances than its affine invariant counterpart, despite using affine dependent norms in the step size’s computation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-kerdreux21a, title = {Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets}, author = {Kerdreux, Thomas and Liu, Lewis and Lacoste-Julien, Simon and Scieur, Damien}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {5398--5408}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/kerdreux21a/kerdreux21a.pdf}, url = {https://proceedings.mlr.press/v139/kerdreux21a.html}, abstract = {It is known that the Frank-Wolfe (FW) algorithm, which is affine covariant, enjoys faster convergence rates than $\mathcal{O}\left(1/K\right)$ when the constraint set is strongly convex. However, these results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds, in contradiction with FW’s affine covariant property. In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. We show that our rates are better than any other known convergence rates of FW in this setting. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function present similar performances than its affine invariant counterpart, despite using affine dependent norms in the step size’s computation.} }
Endnote
%0 Conference Paper %T Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets %A Thomas Kerdreux %A Lewis Liu %A Simon Lacoste-Julien %A Damien Scieur %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-kerdreux21a %I PMLR %P 5398--5408 %U https://proceedings.mlr.press/v139/kerdreux21a.html %V 139 %X It is known that the Frank-Wolfe (FW) algorithm, which is affine covariant, enjoys faster convergence rates than $\mathcal{O}\left(1/K\right)$ when the constraint set is strongly convex. However, these results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds, in contradiction with FW’s affine covariant property. In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. We show that our rates are better than any other known convergence rates of FW in this setting. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function present similar performances than its affine invariant counterpart, despite using affine dependent norms in the step size’s computation.
APA
Kerdreux, T., Liu, L., Lacoste-Julien, S. & Scieur, D.. (2021). Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:5398-5408 Available from https://proceedings.mlr.press/v139/kerdreux21a.html.

Related Material