Events Calendar

CS Distinguished Lecture Series: Sanjeev Arora: Is Machine Learning Tractable? --- Three Vignettes

Speaker: Sanjeev Arora, Princeton University

Talk Title: Is Machine Learning Tractable? --- Three Vignettes

Series: CS Distinguished Lectures

Abstract: Many tasks in machine learning (especially unsupervised learning) are provably intractable: NP-hard or worse. Nevertheless, researchers have developed heuristic algorithms to try to solve these tasks in practice. In most cases, these algorithms are heuristics with no provable guarantees on their running time or on the quality of solutions they return. Can we change this state of affairs?

This talk will suggest that the answer is yes, and describe three of our recent works as illustration. (a) A new algorithm for learning topic models. (It applies to Linear Dirichlet Allocations of Blei et al. and also to more general topic models. It provably works under some reasonable assumptions and in practice is up to 50 times faster than existing software like Mallet. It relies upon a new procedure for nonnegative matrix factorization.) (b) What classifiers are worth learning? (Can theory illuminate the contentious question of what binary classifier to learn: SVM, Decision tree, etc.?) (c) Provable ICA with unknown gaussian noise. (An algorithm to provably learn a "manifold" with small number of parameters but exponentially many "interesting regions.")

Biography: 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 Godel Prize (in 2001 and 2010), Packard Fellowship (1997), the ACM Infosys Prize for midcareer scientists (in 2012), the Fulkerson Prize (2012), the Simons Investigator Award (2012).
He served as the founding director for the Center for Computational Intractability at Princeton.

Host: Shaddin Dughmi

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Assistant to CS chair