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.STACS.2015.1
URN: urn:nbn:de:0030-drops-49581
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4958/
Go to the corresponding LIPIcs Volume Portal

Arora, Sanjeev

Overcoming Intractability in Unsupervised Learning (Invited Talk)

pdf-format:
58.pdf (0.3 MB)

Abstract

Unsupervised learning - i.e., learning with unlabeled data - is increasingly important given today's data deluge. Most natural problems in this domain - e.g. for models such as mixture models, HMMs, graphical models, topic models and sparse coding/dictionary learning, deep learning - are NP-hard. Therefore researchers in practice use either heuristics or convex relaxations with no concrete approximation bounds. Several nonconvex heuristics work well in practice, which is also a mystery.

The talk will describe a sequence of recent results whereby rigorous approaches leading to polynomial running time are possible for several problems in unsupervised learning. The proof of polynomial running time usually relies upon nondegeneracy assumptions on the data and the model parameters, and often also on stochastic properties of the data (average-case analysis). We describe results for topic models, sparse coding, and deep learning. Some of these new algorithms are very efficient and practical - e.g. for topic modeling.

BibTeX - Entry

@InProceedings{arora:LIPIcs:2015:4958,
  author =	{Sanjeev Arora},
  title =	{{Overcoming Intractability in Unsupervised Learning (Invited Talk)}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{1--1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4958},
  URN =		{urn:nbn:de:0030-drops-49581},
  doi =		{10.4230/LIPIcs.STACS.2015.1},
  annote =	{Keywords: machine learning, unsupervised learning, intractability, NP-hardness}
}

Keywords: machine learning, unsupervised learning, intractability, NP-hardness
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

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