Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence

Lijun Ding, Yingjie Fei, Qiantong Xu, Chengrun Yang
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:2535-2544, 2020.

Abstract

We develop a novel variant of the classical Frank-Wolfe algorithm, which we call spectral Frank-Wolfe, for convex optimization over a spectrahedron. The spectral Frank-Wolfe algorithm has a novel ingredient: it computes a few eigenvectors of the gradient and solves a small-scale subproblem in each iteration. Such a procedure overcomes the slow convergence of the classical Frank-Wolfe algorithm due to ignoring eigenvalue coalescence. We demonstrate that strict complementarity of the optimization problem is key to proving linear convergence of various algorithms, such as the spectral Frank-Wolfe algorithm as well as the projected gradient method and its accelerated version. We showcase that the strict complementarity is equivalent to the eigengap assumption on the gradient at the optimal solution considered in the literature. As a byproduct of this observation, we also develop a generalized block Frank-Wolfe algorithm and prove its linear convergence.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-ding20a, title = {Spectral Frank-{W}olfe Algorithm: Strict Complementarity and Linear Convergence}, author = {Ding, Lijun and Fei, Yingjie and Xu, Qiantong and Yang, Chengrun}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {2535--2544}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/ding20a/ding20a.pdf}, url = {https://proceedings.mlr.press/v119/ding20a.html}, abstract = {We develop a novel variant of the classical Frank-Wolfe algorithm, which we call spectral Frank-Wolfe, for convex optimization over a spectrahedron. The spectral Frank-Wolfe algorithm has a novel ingredient: it computes a few eigenvectors of the gradient and solves a small-scale subproblem in each iteration. Such a procedure overcomes the slow convergence of the classical Frank-Wolfe algorithm due to ignoring eigenvalue coalescence. We demonstrate that strict complementarity of the optimization problem is key to proving linear convergence of various algorithms, such as the spectral Frank-Wolfe algorithm as well as the projected gradient method and its accelerated version. We showcase that the strict complementarity is equivalent to the eigengap assumption on the gradient at the optimal solution considered in the literature. As a byproduct of this observation, we also develop a generalized block Frank-Wolfe algorithm and prove its linear convergence.} }
Endnote
%0 Conference Paper %T Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence %A Lijun Ding %A Yingjie Fei %A Qiantong Xu %A Chengrun Yang %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-ding20a %I PMLR %P 2535--2544 %U https://proceedings.mlr.press/v119/ding20a.html %V 119 %X We develop a novel variant of the classical Frank-Wolfe algorithm, which we call spectral Frank-Wolfe, for convex optimization over a spectrahedron. The spectral Frank-Wolfe algorithm has a novel ingredient: it computes a few eigenvectors of the gradient and solves a small-scale subproblem in each iteration. Such a procedure overcomes the slow convergence of the classical Frank-Wolfe algorithm due to ignoring eigenvalue coalescence. We demonstrate that strict complementarity of the optimization problem is key to proving linear convergence of various algorithms, such as the spectral Frank-Wolfe algorithm as well as the projected gradient method and its accelerated version. We showcase that the strict complementarity is equivalent to the eigengap assumption on the gradient at the optimal solution considered in the literature. As a byproduct of this observation, we also develop a generalized block Frank-Wolfe algorithm and prove its linear convergence.
APA
Ding, L., Fei, Y., Xu, Q. & Yang, C.. (2020). Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:2535-2544 Available from https://proceedings.mlr.press/v119/ding20a.html.

Related Material