Theory Seminar

Tuesday, April 23, 2019 - 3:30pm to 4:30pm


ASA Conference Room 6115 Gates Hillman Centers


RAVI KANNAN, Principal Researcher

A General Algorithm for Unsupervised Learning Problems

The core problem in many Unsupervised Learning models (including Topic Modeling, Non-negative matrix factorization, Clustering, Overlapping Community models) is to find a latent k−simplex K in R^d given perturbed points from it, many of which lie far outside the simplex; known algorithms are model-specific. Under two reasonable assumptions, we show that there is a data-determined polytope K' (with exponentially many vertices) which is close to K.

Our algorithm is simply-stated: in each of k stages, it maximizes a carefully chosen linear function over K' which yields a good approximation to a new vertex of K. The proof of correctness is involved; it draws on new and existing tools from Numerical Analysis, especially, angles between singular spaces of close-by matrices. The algorithm has a better running time than known algorithms for the special cases.

Work by Chiranjib Bhattacharyya and Ravi Kannan

Ravi Kannan is a principal researcher at Microsoft Research India, where he leads the algorithms research group. He also holds an adjunct faculty position in the computer science and automation department at the Indian Institute of Science. Before joining Microsoft, Kannan was the William K. Lanman, Jr. Professor of Computer Science and Applied Mathematics at Yale University. He has also taught at MIT and CMU. 

Kannan's research interests include algorithms, theoretical computer science and discrete mathematics, as well as optimization. His work has mainly focused on efficient algorithms for problems of a mathematical (often geometric) flavor that arise in computer science. He has worked on algorithms for integer programming and the geometry of numbers, random walks in n-space, randomized algorithms for linear algebra, and learning algorithms for convex sets.

He was awarded the Knuth Prize in 2011 for developing influential algorithmic techniques aimed at solving long-standing computational problems, the Fulkerson Prize in 1991 for his work on estimating the volume of convex sets, and the Distinguished Alumnus Award from the Indian Institute of Technology, Bombay in 1999.

Event Website:

For More Information, Contact:


Seminar Series