conference paper
Faster one-sample stochastic conditional gradient method for composite convex minimization
PMLR
published
yes
Gideon
Dresdner
author
Maria-Luiza
Vladarean
author
Gunnar
Rätsch
author
Francesco
Locatello
author 26cfd52f-2483-11ee-8040-88983bcc06d40000-0002-4850-0683
Volkan
Cevher
author
Alp
Yurtsever
author
FrLo
department
AISTATS: Conference on Artificial Intelligence and Statistics
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.
ML Research Press2022Virtual
eng
Proceedings of the 25th International Conference on Artificial Intelligence and Statistics
2640-3498
2202.13212
1518439-8457
yes
Dresdner, G., Vladarean, M.-L., Rätsch, G., Locatello, F., Cevher, V., & Yurtsever, A. (2022). Faster one-sample stochastic conditional gradient method for composite convex minimization. In <i>Proceedings of the 25th International Conference on Artificial Intelligence and Statistics</i> (Vol. 151, pp. 8439–8457). Virtual: ML Research Press.
Dresdner G, Vladarean M-L, Rätsch G, Locatello F, Cevher V, Yurtsever A. Faster one-sample stochastic conditional gradient method for composite convex minimization. In: <i>Proceedings of the 25th International Conference on Artificial Intelligence and Statistics</i>. Vol 151. ML Research Press; 2022:8439-8457.
Dresdner, Gideon, et al. “ Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization.” <i>Proceedings of the 25th International Conference on Artificial Intelligence and Statistics</i>, vol. 151, ML Research Press, 2022, pp. 8439–57.
Dresdner, Gideon, Maria-Luiza Vladarean, Gunnar Rätsch, Francesco Locatello, Volkan Cevher, and Alp Yurtsever. “ Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization.” In <i>Proceedings of the 25th International Conference on Artificial Intelligence and Statistics</i>, 151:8439–57. ML Research Press, 2022.
Dresdner G, Vladarean M-L, 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. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 151, 8439–8457.
G. Dresdner, M.-L. Vladarean, G. Rätsch, F. Locatello, V. Cevher, A. Yurtsever, in:, Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2022, pp. 8439–8457.
G. Dresdner, M.-L. Vladarean, G. Rätsch, F. Locatello, V. Cevher, and A. Yurtsever, “ Faster one-sample stochastic conditional gradient method for composite convex minimization,” in <i>Proceedings of the 25th International Conference on Artificial Intelligence and Statistics</i>, Virtual, 2022, vol. 151, pp. 8439–8457.
140932023-08-21T09:27:43Z2023-09-06T10:28:17Z