文章基本信息

标题：Beyond Matrix Completion (Invited Talk)
本地全文：下载
作者：Ankur Moitra
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：45
页码：8-8
DOI：10.4230/LIPIcs.FSTTCS.2015.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Here we study some of the statistical and algorithmic problems that arise in recommendation systems. We will be interested in what happens when we move beyond the matrix setting, to work with higher order objects - namely, tensors. To what extent does inference over more complex objects yield better predictions, but at the expense of the running time? We will explore the computational vs. statistical tradeoffs for some basic problems about recovering approximately low rank tensors from few observations, and will show that our algorithms are nearly optimal among all polynomial time algorithms, under natural complexity-theoretic assumptions. This is based on joint work with Boaz Barak.
关键词：matrix completion; recommendation systems; tensor prediction