ELC seminar
Date and Time: May 13th (Mon.) 14:00 - 15:00
Place: CELC seminar room
*1) polycom access is possible
*2) for using polycom, we decided to have a seminar at the
    small seminar room.  so if you are coming to the seminar
    room, please send a message to Osamu Watanabe
    watanabe(at)is.titech.ac.jp

Title: Is Machine Learning Tractable? --- Three Vignettes
Speaker: Sanjeev Arora (Princeton University)

Abstract:
Many tasks in machine learning (especially unsupervised learning) are
provably intractable: NP-complete 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.")

The talk will be self-contained.

(Based upon joint works with Rong Ge, Ravi Kannan, Ankur Moitra, Sushant
Sachdeva.)