A Conditional-Gradient-Based Augmented Lagrangian Framework

Alp Yurtsever, Olivier Fercoq, Volkan Cevher
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:7272-7281, 2019.

Abstract

This paper considers a generic convex minimization template with affine constraints over a compact domain, which covers key semidefinite programming applications. The existing conditional gradient methods either do not apply to our template or are too slow in practice. To this end, we propose a new conditional gradient method, based on a unified treatment of smoothing and augmented Lagrangian frameworks. The proposed method maintains favorable properties of the classical conditional gradient method, such as cheap linear minimization oracle calls and sparse representation of the decision variable. We prove $O(1/\sqrt{k})$ convergence rate for our method in the objective residual and the feasibility gap. This rate is essentially the same as the state of the art CG-type methods for our problem template, but the proposed method is arguably superior in practice compared to existing methods in various applications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-yurtsever19a, title = {A Conditional-Gradient-Based Augmented Lagrangian Framework}, author = {Yurtsever, Alp and Fercoq, Olivier and Cevher, Volkan}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {7272--7281}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/yurtsever19a/yurtsever19a.pdf}, url = {https://proceedings.mlr.press/v97/yurtsever19a.html}, abstract = {This paper considers a generic convex minimization template with affine constraints over a compact domain, which covers key semidefinite programming applications. The existing conditional gradient methods either do not apply to our template or are too slow in practice. To this end, we propose a new conditional gradient method, based on a unified treatment of smoothing and augmented Lagrangian frameworks. The proposed method maintains favorable properties of the classical conditional gradient method, such as cheap linear minimization oracle calls and sparse representation of the decision variable. We prove $O(1/\sqrt{k})$ convergence rate for our method in the objective residual and the feasibility gap. This rate is essentially the same as the state of the art CG-type methods for our problem template, but the proposed method is arguably superior in practice compared to existing methods in various applications.} }
Endnote
%0 Conference Paper %T A Conditional-Gradient-Based Augmented Lagrangian Framework %A Alp Yurtsever %A Olivier Fercoq %A Volkan Cevher %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-yurtsever19a %I PMLR %P 7272--7281 %U https://proceedings.mlr.press/v97/yurtsever19a.html %V 97 %X This paper considers a generic convex minimization template with affine constraints over a compact domain, which covers key semidefinite programming applications. The existing conditional gradient methods either do not apply to our template or are too slow in practice. To this end, we propose a new conditional gradient method, based on a unified treatment of smoothing and augmented Lagrangian frameworks. The proposed method maintains favorable properties of the classical conditional gradient method, such as cheap linear minimization oracle calls and sparse representation of the decision variable. We prove $O(1/\sqrt{k})$ convergence rate for our method in the objective residual and the feasibility gap. This rate is essentially the same as the state of the art CG-type methods for our problem template, but the proposed method is arguably superior in practice compared to existing methods in various applications.
APA
Yurtsever, A., Fercoq, O. & Cevher, V.. (2019). A Conditional-Gradient-Based Augmented Lagrangian Framework. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:7272-7281 Available from https://proceedings.mlr.press/v97/yurtsever19a.html.

Related Material