nips nips2012 nips2012-208 nips2012-208-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Rina Foygel, Nathan Srebro, Ruslan Salakhutdinov
Abstract: We introduce a new family of matrix norms, the “local max” norms, generalizing existing methods such as the max norm, the trace norm (nuclear norm), and the weighted or smoothed weighted trace norms, which have been extensively used in the literature as regularizers for matrix reconstruction problems. We show that this new family can be used to interpolate between the (weighted or unweighted) trace norm and the more conservative max norm. We test this interpolation on simulated data and on the large-scale Netflix and MovieLens ratings data, and find improved accuracy relative to the existing matrix norms. We also provide theoretical results showing learning guarantees for some of the new norms. 1
[1] N. Srebro and A. Shraibman. Rank, trace-norm and max-norm. 18th Annual Conference on Learning Theory (COLT), pages 545–560, 2005.
[2] R. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. Journal of Machine Learning Research, 11:2057–2078, 2010.
[3] S. Negahban and M. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. arXiv:1009.2118, 2010.
[4] R. Foygel and N. Srebro. Concentration-based guarantees for low-rank matrix reconstruction. 24th Annual Conference on Learning Theory (COLT), 2011.
[5] R. Salakhutdinov and N. Srebro. Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm. Advances in Neural Information Processing Systems, 23, 2010.
[6] R. Foygel, R. Salakhutdinov, O. Shamir, and N. Srebro. Learning with the weighted trace-norm under arbitrary sampling distributions. Advances in Neural Information Processing Systems, 24, 2011.
[7] J. Lee, B. Recht, R. Salakhutdinov, N. Srebro, and J. Tropp. Practical Large-Scale Optimization for Max-Norm Regularization. Advances in Neural Information Processing Systems, 23, 2010.
[8] E. Hazan, S. Kale, and S. Shalev-Shwartz. Near-optimal algorithms for online matrix prediction. 25th Annual Conference on Learning Theory (COLT), 2012.
[9] M. Fazel, H. Hindi, and S. Boyd. A rank minimization heuristic with application to minimum order system approximation. In Proceedings of the 2001 American Control Conference, volume 6, pages 4734–4739, 2002.
[10] N. Srebro, J.D.M. Rennie, and T.S. Jaakkola. Maximum-margin matrix factorization. Advances in Neural Information Processing Systems, 18, 2005.
[11] J.D.M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference on Machine learning, pages 713–719. ACM, 2005.
[12] R. Salakhutdinov and A. Mnih. Probabilistic matrix factorization. Advances in neural information processing systems, 20:1257–1264, 2008.
[13] P. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463–482, 2002.
[14] J. Bennett and S. Lanning. The netflix prize. In Proceedings of KDD Cup and Workshop, volume 2007, page 35. Citeseer, 2007.
[15] MovieLens Dataset. Available at http://www.grouplens.org/node/73. 2006. 9