<div dir="ltr"><div><div><br><br></div>Hi Folks,<br><br></div>Yu Lu will talk in the YPNG seminar this week:<br><br><div><div><div><div></div><div>Title: <br>Statistical and Computational Guarantees of Lloyd's Algorithm and its variants. </div><div><br></div><div>Abstract: <br>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
dimensional setting. </div><div><span style="white-space:pre-wrap"> <br></span>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. </div><div><br></div></div><div>See you Friday at 11am in the Stat's classroom.<br><br>Regards,<br>sekhar<br><br><br></div></div></div></div>