[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).

best
dave



---------- 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.

Sanjeev
-------

  k-MEANS REVISITED

   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
https://lists.cs.princeton.edu/mailman/listinfo/theory-read


More information about the Ml-stat-talks mailing list