Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization

Gideon Dresdner, Maria-Luiza Vladarean, Gunnar Rätsch, Francesco Locatello, Volkan Cevher, Alp Yurtsever
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:8439-8457, 2022.

Abstract

We propose a stochastic conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully increasing the batch size over the course of the algorithm’s execution, which leads to computing full gradients. In contrast, the proposed method, equipped with a stochastic average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques. In applications we put special emphasis on problems with a large number of separable constraints. Such problems are prevalent among semidefinite programming (SDP) formulations arising in machine learning and theoretical computer science. We provide numerical experiments on matrix completion, unsupervised clustering, and sparsest-cut SDPs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-dresdner22a, title = { Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization }, author = {Dresdner, Gideon and Vladarean, Maria-Luiza and R\"atsch, Gunnar and Locatello, Francesco and Cevher, Volkan and Yurtsever, Alp}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {8439--8457}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/dresdner22a/dresdner22a.pdf}, url = {https://proceedings.mlr.press/v151/dresdner22a.html}, abstract = { We propose a stochastic conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully increasing the batch size over the course of the algorithm’s execution, which leads to computing full gradients. In contrast, the proposed method, equipped with a stochastic average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques. In applications we put special emphasis on problems with a large number of separable constraints. Such problems are prevalent among semidefinite programming (SDP) formulations arising in machine learning and theoretical computer science. We provide numerical experiments on matrix completion, unsupervised clustering, and sparsest-cut SDPs. } }
Endnote
%0 Conference Paper %T Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization %A Gideon Dresdner %A Maria-Luiza Vladarean %A Gunnar Rätsch %A Francesco Locatello %A Volkan Cevher %A Alp Yurtsever %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-dresdner22a %I PMLR %P 8439--8457 %U https://proceedings.mlr.press/v151/dresdner22a.html %V 151 %X We propose a stochastic conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully increasing the batch size over the course of the algorithm’s execution, which leads to computing full gradients. In contrast, the proposed method, equipped with a stochastic average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques. In applications we put special emphasis on problems with a large number of separable constraints. Such problems are prevalent among semidefinite programming (SDP) formulations arising in machine learning and theoretical computer science. We provide numerical experiments on matrix completion, unsupervised clustering, and sparsest-cut SDPs.
APA
Dresdner, G., Vladarean, M., Rätsch, G., Locatello, F., Cevher, V. & Yurtsever, A.. (2022). Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:8439-8457 Available from https://proceedings.mlr.press/v151/dresdner22a.html.

Related Material