A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming

Alp Yurtsever, Olivier Fercoq, Francesco Locatello, Volkan Cevher
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5727-5736, 2018.

Abstract

We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines smoothing and homotopy techniques under the CGM framework, and provably achieves the optimal convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. In contrast with the relevant work, we are able to characterize the convergence when the non-smooth term is an indicator function. Specific applications of our framework include the non-smooth minimization, semidefinite programming, and minimization with linear inclusion constraints over a compact domain. Numerical evidence demonstrates the benefits of our framework.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-yurtsever18a, title = {A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming}, author = {Yurtsever, Alp and Fercoq, Olivier and Locatello, Francesco and Cevher, Volkan}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5727--5736}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/yurtsever18a/yurtsever18a.pdf}, url = {https://proceedings.mlr.press/v80/yurtsever18a.html}, abstract = {We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines smoothing and homotopy techniques under the CGM framework, and provably achieves the optimal convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. In contrast with the relevant work, we are able to characterize the convergence when the non-smooth term is an indicator function. Specific applications of our framework include the non-smooth minimization, semidefinite programming, and minimization with linear inclusion constraints over a compact domain. Numerical evidence demonstrates the benefits of our framework.} }
Endnote
%0 Conference Paper %T A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming %A Alp Yurtsever %A Olivier Fercoq %A Francesco Locatello %A Volkan Cevher %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-yurtsever18a %I PMLR %P 5727--5736 %U https://proceedings.mlr.press/v80/yurtsever18a.html %V 80 %X We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines smoothing and homotopy techniques under the CGM framework, and provably achieves the optimal convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. In contrast with the relevant work, we are able to characterize the convergence when the non-smooth term is an indicator function. Specific applications of our framework include the non-smooth minimization, semidefinite programming, and minimization with linear inclusion constraints over a compact domain. Numerical evidence demonstrates the benefits of our framework.
APA
Yurtsever, A., Fercoq, O., Locatello, F. & Cevher, V.. (2018). A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5727-5736 Available from https://proceedings.mlr.press/v80/yurtsever18a.html.

Related Material