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 = {Celestine Dünner and Simone Forte and Martin Takac and Martin Jaggi}, pages = {783--792}, year = {2016}, editor = {Maria Florina Balcan and Kilian Q. Weinberger}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 783--792 %U http://proceedings.mlr.press %V 48 %W PMLR %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 PY - 2016/06/11 DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-dunner16 PB - PMLR SP - 783 DP - PMLR EP - 792 L1 - http://proceedings.mlr.press/v48/dunner16.pdf UR - http://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 PMLR 48:783-792

Related Material