Frank-Wolfe with Subsampling Oracle

Thomas Kerdreux, Fabian Pedregosa, Alexandre d’Aspremont
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2591-2600, 2018.

Abstract

We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small subset of the original domain. The first algorithm that we propose is a randomized variant of the original FW algorithm and achieves a O(1/t) sublinear convergence rate as in the deterministic counterpart. The second algorithm is a randomized variant of the Away-step FW algorithm, and again as its deterministic counterpart, reaches linear (i.e., exponential) convergence rate making it the first provably convergent randomized variant of Away-step FW. In both cases, while subsampling reduces the convergence rate by a constant factor, the linear minimization step can be a fraction of the cost of that of the deterministic versions, especially when the data is streamed. We illustrate computational gains of both algorithms on regression problems, involving both ℓ1 and latent group lasso penalties.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-kerdreux18a, title = {Frank-{W}olfe with Subsampling Oracle}, author = {Kerdreux, Thomas and Pedregosa, Fabian and d'Aspremont, Alexandre}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2591--2600}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/kerdreux18a/kerdreux18a.pdf}, url = {https://proceedings.mlr.press/v80/kerdreux18a.html}, abstract = {We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small subset of the original domain. The first algorithm that we propose is a randomized variant of the original FW algorithm and achieves a $\mathcal{O}(1/t)$ sublinear convergence rate as in the deterministic counterpart. The second algorithm is a randomized variant of the Away-step FW algorithm, and again as its deterministic counterpart, reaches linear (i.e., exponential) convergence rate making it the first provably convergent randomized variant of Away-step FW. In both cases, while subsampling reduces the convergence rate by a constant factor, the linear minimization step can be a fraction of the cost of that of the deterministic versions, especially when the data is streamed. We illustrate computational gains of both algorithms on regression problems, involving both $\ell_1$ and latent group lasso penalties.} }
Endnote
%0 Conference Paper %T Frank-Wolfe with Subsampling Oracle %A Thomas Kerdreux %A Fabian Pedregosa %A Alexandre d’Aspremont %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-kerdreux18a %I PMLR %P 2591--2600 %U https://proceedings.mlr.press/v80/kerdreux18a.html %V 80 %X We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small subset of the original domain. The first algorithm that we propose is a randomized variant of the original FW algorithm and achieves a $\mathcal{O}(1/t)$ sublinear convergence rate as in the deterministic counterpart. The second algorithm is a randomized variant of the Away-step FW algorithm, and again as its deterministic counterpart, reaches linear (i.e., exponential) convergence rate making it the first provably convergent randomized variant of Away-step FW. In both cases, while subsampling reduces the convergence rate by a constant factor, the linear minimization step can be a fraction of the cost of that of the deterministic versions, especially when the data is streamed. We illustrate computational gains of both algorithms on regression problems, involving both $\ell_1$ and latent group lasso penalties.
APA
Kerdreux, T., Pedregosa, F. & d’Aspremont, A.. (2018). Frank-Wolfe with Subsampling Oracle. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2591-2600 Available from https://proceedings.mlr.press/v80/kerdreux18a.html.

Related Material