[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