Machine learning currently relies on many heuristics---algorithms for which we have no provable guarantees on running time and/or performance. In fact, many underlying problems are NP-hard or worse! Is machine learning really intractable?

The talk will present some thoughts on this, some recent new algorithms for some classic machine learning problems (nonnegative matrix factorization and topic models) under some realistic assumptions, and sketch the myriad open problems in this arena.

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