Near-Optimal Algorithms for Online Matrix Prediction
Abstract
In several online prediction problems of recent interest the
comparison class is composed of matrices. For
example, in the online max-cut problem, the comparison class is
matrices which represent cuts of a given graph and in online
gambling the comparison class is matrices which represent
permutations over $n$ teams. Another important example is online
collaborative filtering in which a widely used comparison class is
the set of matrices with a small trace norm. In this paper we
isolate a property of matrices, which we call
$(\beta,\tau)$-decomposability, and derive an efficient online
learning algorithm, that enjoys a regret bound of
$\tilde{O}(\sqrt{\beta\,\tau\,T})$ for all problems in which the
comparison class is composed of $(\beta,\tau)$-decomposable
matrices. By analyzing the decomposability of cut matrices, low trace-norm matrices, and triangular matrices, we derive near optimal
regret bounds for online max-cut, online
collaborative filtering, and online gambling. In particular, this resolves (in the
affirmative) an open problem posed by Abernethy (2010) and Kleinberg et al (2010). Finally, we
derive lower bounds for the three problems and show that our upper
bounds are optimal up to logarithmic factors. In particular, our lower bound
for the online collaborative filtering problem resolves another open
problem posed by Shamir and Srebro (2010).
comparison class is composed of matrices. For
example, in the online max-cut problem, the comparison class is
matrices which represent cuts of a given graph and in online
gambling the comparison class is matrices which represent
permutations over $n$ teams. Another important example is online
collaborative filtering in which a widely used comparison class is
the set of matrices with a small trace norm. In this paper we
isolate a property of matrices, which we call
$(\beta,\tau)$-decomposability, and derive an efficient online
learning algorithm, that enjoys a regret bound of
$\tilde{O}(\sqrt{\beta\,\tau\,T})$ for all problems in which the
comparison class is composed of $(\beta,\tau)$-decomposable
matrices. By analyzing the decomposability of cut matrices, low trace-norm matrices, and triangular matrices, we derive near optimal
regret bounds for online max-cut, online
collaborative filtering, and online gambling. In particular, this resolves (in the
affirmative) an open problem posed by Abernethy (2010) and Kleinberg et al (2010). Finally, we
derive lower bounds for the three problems and show that our upper
bounds are optimal up to logarithmic factors. In particular, our lower bound
for the online collaborative filtering problem resolves another open
problem posed by Shamir and Srebro (2010).
Research Areas
