Lifted coordinate descent for learning with trace-norm regularization

Miroslav Dudik, Zaid Harchaoui, Jerome Malick
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:327-336, 2012.

Abstract

We consider the minimization of a smooth loss with trace-norm regularization, which is a natural objective in multi-class and multi-task learning. Even though the problem is convex, existing approaches rely on optimizing a non-convex variational bound, which is not guaranteed to converge, or repeatedly perform singular-value decomposition, which prevents scaling beyond moderate matrix sizes. We lift the non-smooth convex problem into an infinitely dimensional smooth problem and apply coordinate descent to solve it. We prove that our approach converges to the optimum, and is competitive or outperforms state of the art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-dudik12, title = {Lifted coordinate descent for learning with trace-norm regularization}, author = {Dudik, Miroslav and Harchaoui, Zaid and Malick, Jerome}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {327--336}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/dudik12/dudik12.pdf}, url = {https://proceedings.mlr.press/v22/dudik12.html}, abstract = {We consider the minimization of a smooth loss with trace-norm regularization, which is a natural objective in multi-class and multi-task learning. Even though the problem is convex, existing approaches rely on optimizing a non-convex variational bound, which is not guaranteed to converge, or repeatedly perform singular-value decomposition, which prevents scaling beyond moderate matrix sizes. We lift the non-smooth convex problem into an infinitely dimensional smooth problem and apply coordinate descent to solve it. We prove that our approach converges to the optimum, and is competitive or outperforms state of the art.} }
Endnote
%0 Conference Paper %T Lifted coordinate descent for learning with trace-norm regularization %A Miroslav Dudik %A Zaid Harchaoui %A Jerome Malick %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-dudik12 %I PMLR %P 327--336 %U https://proceedings.mlr.press/v22/dudik12.html %V 22 %X We consider the minimization of a smooth loss with trace-norm regularization, which is a natural objective in multi-class and multi-task learning. Even though the problem is convex, existing approaches rely on optimizing a non-convex variational bound, which is not guaranteed to converge, or repeatedly perform singular-value decomposition, which prevents scaling beyond moderate matrix sizes. We lift the non-smooth convex problem into an infinitely dimensional smooth problem and apply coordinate descent to solve it. We prove that our approach converges to the optimum, and is competitive or outperforms state of the art.
RIS
TY - CPAPER TI - Lifted coordinate descent for learning with trace-norm regularization AU - Miroslav Dudik AU - Zaid Harchaoui AU - Jerome Malick BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-dudik12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 327 EP - 336 L1 - http://proceedings.mlr.press/v22/dudik12/dudik12.pdf UR - https://proceedings.mlr.press/v22/dudik12.html AB - We consider the minimization of a smooth loss with trace-norm regularization, which is a natural objective in multi-class and multi-task learning. Even though the problem is convex, existing approaches rely on optimizing a non-convex variational bound, which is not guaranteed to converge, or repeatedly perform singular-value decomposition, which prevents scaling beyond moderate matrix sizes. We lift the non-smooth convex problem into an infinitely dimensional smooth problem and apply coordinate descent to solve it. We prove that our approach converges to the optimum, and is competitive or outperforms state of the art. ER -
APA
Dudik, M., Harchaoui, Z. & Malick, J.. (2012). Lifted coordinate descent for learning with trace-norm regularization. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:327-336 Available from https://proceedings.mlr.press/v22/dudik12.html.

Related Material