nips nips2011 nips2011-80 nips2011-80-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nicolò Cesa-bianchi, Ohad Shamir
Abstract: Most online algorithms used in machine learning today are based on variants of mirror descent or follow-the-leader. In this paper, we present an online algorithm based on a completely different approach, which combines “random playout” and randomized rounding of loss subgradients. As an application of our approach, we provide the first computationally efficient online algorithm for collaborative filtering with trace-norm constrained matrices. As a second application, we solve an open question linking batch learning and transductive online learning. 1
[1] K. Sridharan A. Rakhlin and A. Tewari. Online learning: Random averages, combinatorial parameters, and learnability. In NIPS, 2010.
[2] J. Abernethy, P. Bartlett, A. Rakhlin, and A. Tewari. Optimal strategies and minimax lower bounds for online convex games. In COLT, 2009.
[3] J. Abernethy and M. Warmuth. Repeated games against budgeted adversaries. In NIPS, 2010.
[4] F. Bach. Consistency of trace-norm minimization. Journal of Machine Learning Research, 9:1019–1048, 2008.
[5] P. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. In COLT, 2001.
[6] S. Ben-David, E. Kushilevitz, and Y. Mansour. Online learning versus offline learning. Machine Learning, 29(1):45–63, 1997.
[7] S. Ben-David, D. P´l, and S. Shalev-Shwartz. Agnostic online learning. In COLT, 2009. a
[8] A. Blum. Separating distribution-free and mistake-bound learning models over the boolean domain. SIAM J. Comput., 23(5):990–1000, 1994.
[9] N. Cesa-Bianchi, Y. Freund, D. Haussler, D. Helmbold, R. Schapire, and M. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485, May 1997.
[10] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[11] T. Chung. Approximate methods for sequential decision making using expert advice. In COLT, 1994. ´
[12] R. M. Dudley. A Course on Empirical Processes, Ecole de Probabilit´s de St. Flour, e 1982, volume 1097 of Lecture Notes in Mathematics. Springer Verlag, 1984.
[13] R. Foygel, R. Salakhutdinov, O. Shamir, and N. Srebro. Learning with the weighted trace-norm under arbitrary sampling distributions. In NIPS, 2011.
[14] E. Hazan. The convex optimization approach to regret minimization. In S. Nowozin S. Sra and S. Wright, editors, Optimization for Machine Learning. MIT Press, To Appear.
[15] P. Bartlett J. Abernethy, A. Agarwal and A. Rakhlin. A stochastic view of optimal regret through minimax duality. In COLT, 2009.
[16] S. Kakade and A. Kalai. From batch to transductive online learning. In NIPS, 2005. 8
[17] Y. Koren. Collaborative filtering with temporal dynamics. In KDD, 2009.
[18] J. Lee, B. Recht, R. Salakhutdinov, N. Srebro, and J. Tropp. Practical large-scale optimization for max-norm regularization. In NIPS, 2010.
[19] R. Salakhutdinov and A. Mnih. Probabilistic matrix factorization. In NIPS, 2007.
[20] R. Salakhutdinov and N. Srebro. Collaborative filtering in a non-uniform world: Learning with the weighted trace norm. In NIPS, 2010.
[21] O. Shamir and S. Shalev-Shwartz. Collaborative filtering with the trace norm: Learning, bounding, and transducing. In COLT, 2011.
[22] N. Srebro, J. Rennie, and T. Jaakkola. Maximum-margin matrix factorization. In NIPS, 2004.
[23] N. Srebro and A. Shraibman. Rank, trace-norm and max-norm. In COLT, 2005. 9