Stochastic Frank-Wolfe for constrained finite-sum minimization
Négiar G, Dresdner G, Tsai A, Ghaoui LE, Locatello F, Freund RM, Pedregosa F. 2020. Stochastic Frank-Wolfe for constrained finite-sum minimization. Proceedings of the 37th International Conference on Machine Learning. International Conference on Machine Learning, PMLR, vol. 119, 7253–7262.
Download (ext.)
https://arxiv.org/abs/2002.11860
[Preprint]
Conference Paper
| Published
| English
Author
Négiar, Geoffrey;
Dresdner, Gideon;
Tsai, Alicia;
Ghaoui, Laurent El;
Locatello, FrancescoISTA ;
Freund, Robert M.;
Pedregosa, Fabian
Department
Series Title
PMLR
Abstract
We propose a novel Stochastic Frank-Wolfe (a.k.a. conditional gradient)
algorithm for constrained smooth finite-sum minimization with a generalized
linear prediction/structure. This class of problems includes empirical risk
minimization with sparse, low-rank, or other structured constraints. The
proposed method is simple to implement, does not require step-size tuning, and
has a constant per-iteration cost that is independent of the dataset size.
Furthermore, as a byproduct of the method we obtain a stochastic estimator of
the Frank-Wolfe gap that can be used as a stopping criterion. Depending on the
setting, the proposed method matches or improves on the best computational
guarantees for Stochastic Frank-Wolfe algorithms. Benchmarks on several
datasets highlight different regimes in which the proposed method exhibits a
faster empirical convergence than related methods. Finally, we provide an
implementation of all considered methods in an open-source package.
Publishing Year
Date Published
2020-07-27
Proceedings Title
Proceedings of the 37th International Conference on Machine Learning
Volume
119
Page
7253-7262
Conference
International Conference on Machine Learning
Conference Location
Virtual
Conference Date
2020-07-13 – 2020-07-18
IST-REx-ID
Cite this
Négiar G, Dresdner G, Tsai A, et al. Stochastic Frank-Wolfe for constrained finite-sum minimization. In: Proceedings of the 37th International Conference on Machine Learning. Vol 119. ; 2020:7253-7262.
Négiar, G., Dresdner, G., Tsai, A., Ghaoui, L. E., Locatello, F., Freund, R. M., & Pedregosa, F. (2020). Stochastic Frank-Wolfe for constrained finite-sum minimization. In Proceedings of the 37th International Conference on Machine Learning (Vol. 119, pp. 7253–7262). Virtual.
Négiar, Geoffrey, Gideon Dresdner, Alicia Tsai, Laurent El Ghaoui, Francesco Locatello, Robert M. Freund, and Fabian Pedregosa. “Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization.” In Proceedings of the 37th International Conference on Machine Learning, 119:7253–62, 2020.
G. Négiar et al., “Stochastic Frank-Wolfe for constrained finite-sum minimization,” in Proceedings of the 37th International Conference on Machine Learning, Virtual, 2020, vol. 119, pp. 7253–7262.
Négiar G, Dresdner G, Tsai A, Ghaoui LE, Locatello F, Freund RM, Pedregosa F. 2020. Stochastic Frank-Wolfe for constrained finite-sum minimization. Proceedings of the 37th International Conference on Machine Learning. International Conference on Machine Learning, PMLR, vol. 119, 7253–7262.
Négiar, Geoffrey, et al. “Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization.” Proceedings of the 37th International Conference on Machine Learning, vol. 119, 2020, pp. 7253–62.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2002.11860