[Ml-stat-talks] Fwd: [Theory-Read] Ravi Kannan @ theory lunch Fri noon

David Blei blei at CS.Princeton.EDU
Mon Feb 20 14:35:55 EST 2012

a CS theory talk that looks very interesting (and, of course, related to ML).


---------- Forwarded message ----------
From: Sanjeev Arora <arora at cs.princeton.edu>
Date: Mon, Feb 20, 2012 at 1:54 PM
Subject: [Theory-Read] Ravi Kannan @ theory lunch Fri noon
To: Theory list <theory-read at lists.cs.princeton.edu>

Ravi Kannan of Microsoft Research will speak at the theory lunch on
Fri at 12:05pm in Room 402.

Students in my 598C class will have seen the necessary background to
understand this work as well.



   Ravi Kannan, MSR

In many applications, fairly fast clustering algorithms seem to yield
the desired solution.
Theoretically, two types of assumptions lead to provably fast
algorithms for clustering:
(i) stochastic (mixture) models of data and (ii) uniqueness of optimal
solution even
under perturbations of data. We show that under an assumption weaker
than either of these,
Lloyd's (k-means) algorithm converges to the correct solution. We
apply the result to the
planted clique problem.

Joint work with Amit Kumar.

Theory-Read mailing list
Theory-Read at lists.cs.princeton.edu

More information about the Ml-stat-talks mailing list