conference paper
Stochastic Frank-Wolfe for constrained finite-sum minimization
PMLR
published
yes
Geoffrey
Négiar
author
Gideon
Dresdner
author
Alicia
Tsai
author
Laurent El
Ghaoui
author
Francesco
Locatello
author 26cfd52f-2483-11ee-8040-88983bcc06d40000-0002-4850-0683
Robert M.
Freund
author
Fabian
Pedregosa
author
FrLo
department
International Conference on Machine Learning
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.
2020Virtual
eng
Proceedings of the 37th International Conference on Machine Learning
2002.11860
1197253-7262
yes
G. Négiar, G. Dresdner, A. Tsai, L.E. Ghaoui, F. Locatello, R.M. Freund, F. Pedregosa, in:, Proceedings of the 37th International Conference on Machine Learning, 2020, 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, Gideon Dresdner, Alicia Tsai, Laurent El Ghaoui, Francesco Locatello, Robert M. Freund, and Fabian Pedregosa. “Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization.” In <i>Proceedings of the 37th International Conference on Machine Learning</i>, 119:7253–62, 2020.
Négiar G, Dresdner G, Tsai A, et al. Stochastic Frank-Wolfe for constrained finite-sum minimization. In: <i>Proceedings of the 37th International Conference on Machine Learning</i>. Vol 119. ; 2020:7253-7262.
G. Négiar <i>et al.</i>, “Stochastic Frank-Wolfe for constrained finite-sum minimization,” in <i>Proceedings of the 37th International Conference on Machine Learning</i>, Virtual, 2020, vol. 119, pp. 7253–7262.
Négiar, Geoffrey, et al. “Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization.” <i>Proceedings of the 37th International Conference on Machine Learning</i>, vol. 119, 2020, pp. 7253–62.
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 <i>Proceedings of the 37th International Conference on Machine Learning</i> (Vol. 119, pp. 7253–7262). Virtual.
141872023-08-22T14:07:52Z2023-09-12T08:03:40Z