[YPNG] YPNG, Friday 7 October 2016
sekhar.tatikonda at yale.edu
Mon Oct 3 15:56:21 EDT 2016
Yu Lu will talk in the YPNG seminar this week:
Statistical and Computational Guarantees of Lloyd's Algorithm and its
Clustering is a fundamental problem in statistics and machine learning.
Lloyd's algorithm is the most widely used algorithm in practice due to its
simplicity and its good empirical performance. However, there has been
little theoretical investigation on Lloyd's algorithm. In this paper, we
show the statistical and computational guarantees of Lloyd's algorithm for
clustering mixtures of spherical sub-Gaussians. When there are two
clusters, the initializer needs only to be slightly better than random
guess. Results are extended to general number of clusters and the high
We also extend our results to the problem of community detection and
crowdsourcing by proposing two variants of Lloyd’s algorithm. Our results
improve the previous noise ratio condition for both problems. Experimental
results on simulated and real datasets demonstrate competitive performance
with the state-of-the-art methods.
See you Friday at 11am in the Stat's classroom.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the YPNG