Primal-Dual Rates and Certificates

Celestine Dünner, Simone Forte, Martin Takac, Martin Jaggi
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:783-792, 2016.

Abstract

We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to diagnose progress, in particular in machine learning applications. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many L1, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model. Our approach provides efficiently computable duality gaps which are globally defined, without modifying the original problems in the region of interest.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-dunner16, title = {Primal-Dual Rates and Certificates}, author = {Dünner, Celestine and Forte, Simone and Takac, Martin and Jaggi, Martin}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {783--792}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/dunner16.pdf}, url = {https://proceedings.mlr.press/v48/dunner16.html}, abstract = {We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to diagnose progress, in particular in machine learning applications. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many L1, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model. Our approach provides efficiently computable duality gaps which are globally defined, without modifying the original problems in the region of interest.} }
Endnote
%0 Conference Paper %T Primal-Dual Rates and Certificates %A Celestine Dünner %A Simone Forte %A Martin Takac %A Martin Jaggi %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-dunner16 %I PMLR %P 783--792 %U https://proceedings.mlr.press/v48/dunner16.html %V 48 %X We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to diagnose progress, in particular in machine learning applications. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many L1, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model. Our approach provides efficiently computable duality gaps which are globally defined, without modifying the original problems in the region of interest.
RIS
TY - CPAPER TI - Primal-Dual Rates and Certificates AU - Celestine Dünner AU - Simone Forte AU - Martin Takac AU - Martin Jaggi BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-dunner16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 783 EP - 792 L1 - http://proceedings.mlr.press/v48/dunner16.pdf UR - https://proceedings.mlr.press/v48/dunner16.html AB - We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to diagnose progress, in particular in machine learning applications. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many L1, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model. Our approach provides efficiently computable duality gaps which are globally defined, without modifying the original problems in the region of interest. ER -
APA
Dünner, C., Forte, S., Takac, M. & Jaggi, M.. (2016). Primal-Dual Rates and Certificates. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:783-792 Available from https://proceedings.mlr.press/v48/dunner16.html.

Related Material