License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.8
URN: urn:nbn:de:0030-drops-56650
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5665/
Go to the corresponding LIPIcs Volume Portal

Moitra, Ankur

Beyond Matrix Completion (Invited Talk)

pdf-format:
51.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{moitra:LIPIcs:2015:5665,
  author =	{Ankur Moitra},
  title =	{{Beyond Matrix Completion (Invited Talk)}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{8--8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5665},
  URN =		{urn:nbn:de:0030-drops-56650},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.8},
  annote =	{Keywords: matrix completion, recommendation systems, tensor prediction}
}

Keywords: matrix completion, recommendation systems, tensor prediction
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI