[Colloquium] Combinatorics & Theoretical CS Seminar Today
Donna Brooms
donna at cs.uchicago.edu
Tue Sep 29 08:05:45 CDT 2015
REMINDER
Combinatorics & Theoretical Computer Science Seminar
Sanjeev Arora
Princeton University
www.cs.princeton.edu/~arora/ <http://www.cs.princeton.edu/~arora/>
Tuesday, September 29th
Ryerson 251 @ 3:00pm
Title: Overcoming intractability in unsupervised learning
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). Some of these new algorithms are very efficient and practical ---e.g. for topic modeling.
In some cases one can also give rigorous analyses of existing algorithms that had hitherto proven hard to analyse, e.g., alternating minimization based algorithms for sparse coding.
Host: Prof. Razborov
(Refreshments will be served prior to the talk I Ry. 255 at 2:30 pm)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150929/7c8bf142/attachment.htm
More information about the Colloquium
mailing list