Rank minimization via online learning

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