Conditional gradient methods for stochastically constrained convex minimization

Maria-Luiza Vladarean, Ahmet Alacaoglu, Ya-Ping Hsieh, Volkan Cevher
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:9775-9785, 2020.

Abstract

We propose two novel conditional gradient-based methods for solving structured stochastic convex optimization problems with a large number of linear constraints. Instances of this template naturally arise from SDP-relaxations of combinatorial problems, which involve a number of constraints that is polynomial in the problem dimension. The most important feature of our framework is that only a subset of the constraints is processed at each iteration, thus gaining a computational advantage over prior works that require full passes. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees. Preliminary numerical experiments are provided for illustrating the practical performance of the methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-vladarean20a, title = {Conditional gradient methods for stochastically constrained convex minimization}, author = {Vladarean, Maria-Luiza and Alacaoglu, Ahmet and Hsieh, Ya-Ping and Cevher, Volkan}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {9775--9785}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/vladarean20a/vladarean20a.pdf}, url = {https://proceedings.mlr.press/v119/vladarean20a.html}, abstract = {We propose two novel conditional gradient-based methods for solving structured stochastic convex optimization problems with a large number of linear constraints. Instances of this template naturally arise from SDP-relaxations of combinatorial problems, which involve a number of constraints that is polynomial in the problem dimension. The most important feature of our framework is that only a subset of the constraints is processed at each iteration, thus gaining a computational advantage over prior works that require full passes. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees. Preliminary numerical experiments are provided for illustrating the practical performance of the methods.} }
Endnote
%0 Conference Paper %T Conditional gradient methods for stochastically constrained convex minimization %A Maria-Luiza Vladarean %A Ahmet Alacaoglu %A Ya-Ping Hsieh %A Volkan Cevher %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-vladarean20a %I PMLR %P 9775--9785 %U https://proceedings.mlr.press/v119/vladarean20a.html %V 119 %X We propose two novel conditional gradient-based methods for solving structured stochastic convex optimization problems with a large number of linear constraints. Instances of this template naturally arise from SDP-relaxations of combinatorial problems, which involve a number of constraints that is polynomial in the problem dimension. The most important feature of our framework is that only a subset of the constraints is processed at each iteration, thus gaining a computational advantage over prior works that require full passes. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees. Preliminary numerical experiments are provided for illustrating the practical performance of the methods.
APA
Vladarean, M., Alacaoglu, A., Hsieh, Y. & Cevher, V.. (2020). Conditional gradient methods for stochastically constrained convex minimization. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:9775-9785 Available from https://proceedings.mlr.press/v119/vladarean20a.html.

Related Material