Lifted coordinate descent for learning with trace-norm regularization

Miro Dudik 1 Zaid Harchaoui 2 Jérôme Malick 3
1 NY
Yahoo! Labs New York
2 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
3 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
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.
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download


https://hal.inria.fr/hal-00756802
Contributor : Thoth Team <>
Submitted on : Friday, November 23, 2012 - 5:24:54 PM
Last modification on : Thursday, February 7, 2019 - 5:28:41 PM
Long-term archiving on : Sunday, February 24, 2013 - 3:55:10 AM

Files

dhm_2012_rod_atomdescent.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-00756802, version 1

Citation

Miro Dudik, Zaid Harchaoui, Jérôme Malick. Lifted coordinate descent for learning with trace-norm regularization. AISTATS - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics - 2012, Apr 2012, La Palma, Spain. pp.327-336. ⟨hal-00756802⟩

Share

Metrics

Record views

1318

Files downloads

712