Practical Large-Scale Optimization for Max-norm Regularization

Part of Advances in Neural Information Processing Systems 23 (NIPS 2010)

Bibtex Metadata Paper


Jason D. Lee, Ben Recht, Nathan Srebro, Joel Tropp, Russ R. Salakhutdinov


The max-norm was proposed as a convex matrix regularizer by Srebro et al (2004) and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro (2003) to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.