Abstract:
Unsupervised learning —i.e., learning with unlabeled data— is increasingly important given todays data deluge. Most natural prob- lems in this domain – e.g. for models such as mixture models, HMMs, graphical models, topic models and sparse coding/dictionary 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. Recently, a sequence of results has shown that rigorous approaches lead- ing to polynomial running time are possible for several of these problems. These involve sidestepping worst-case complexity via special assump- tions on the input. Some of this work —eg for topic models—even leads to practical running times (50x faster than previous approaches). It has even become possible to analyse nonconvex optimization heuristics such as alternating minimization or kSVD.

The talk will be a survey of these new results, including topic modeling, sparse coding, and deep learning.

Bio: Sanjeev Arora is Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research area spans several areas of theoretical Computer Science. He has received the ACM-EATCS Gödel Prize (in 2001 and 2010), Packard Fellowship (1997), the ACM Infosys Foundation Award in the Computing Sciences (2012), the Fulkerson Prize (2012), the Simons Investigator Award (2012). He served as the founding director for the Center for Computational Intractability at Princeton.