Rank Minimization via Online Learning | Center for Big Data Analytics

Abstract: Minimum rank problems arise frequently in machine learning applications and are notoriously difficult to solve due to the non-convex nature of the rank objective. In this paper, we present the first online learning approach for the problem of rank minimization of matrices over polyhedral sets. In particular, we present two online learning algorithms for rank minimization – our first algorithm is a multiplicative update method based on a generalized experts framework, while our second algorithm is a novel application of the online convex programming framework (Zinkevich, 2003). In the latter, we flip the role of the decision maker by making the decision maker search over the constraint space instead of feasible points, as is usually the case in online convex programming. A salient feature of our online learning approach is that it allows us to give provable approximation guarantees for the rank minimization problem over polyhedral sets. We demonstrate the effectiveness of our methods on synthetic examples, and on the real-life application of low-rank kernel learning.

Topics:
Online Learning

Download: pdf

Citation

Rank Minimization via Online Learning (pdf, software)
R. Meka, P. Jain, C. Caramanis, I. Dhillon.
In International Conference on Machine Learning (ICML), July 2008.

Bibtex:
@inproceedings{meka2008rankminim, author = "Raghu Meka AND Prateek Jain AND Constantine Caramanis AND Inderjit S. Dhillon", title = "Rank Minimization via Online Learning", booktitle = "International Conference on Machine Learning (ICML)", number = "0", year = "2008", month = "jul", abstract = "Minimum rank problems arise frequently in machine learning applications and are notoriously difficult to solve due to the non-convex nature of the rank objective. In this paper, we present the first online learning approach for the problem of rank minimization of matrices over polyhedral sets. In particular, we present two online learning algorithms for rank minimization – our first algorithm is a multiplicative update method based on a generalized experts framework, while our second algorithm is a novel application of the online convex programming framework (Zinkevich, 2003). In the latter, we flip the role of the decision maker by making the decision maker search over the constraint space instead of feasible points, as is usually the case in online convex programming. A salient feature of our online learning approach is that it allows us to give provable approximation guarantees for the rank minimization problem over polyhedral sets. We demonstrate the effectiveness of our methods on synthetic examples, and on the real-life application of low-rank kernel learning." }