[YPNG] YPNG, Friday 11 November 2016

[Sekhar Tatikonda]

Hi Everyone,

Yu Lu will talk in the YPNG seminar this week.  This is a continuation of
the work he
presented a few weeks ago.

Title: Statistical and Computational Guarantees of Lloyd's Algorithm

Abstract: Clustering is a fundamental problem in statistics and machine
learning. Lloyd’s
algorithm, proposed in 1957 by Stuart Lloyd, is still possibly the most
widely used clustering
algorithm in practice due to its simplicity and empirical performance. However,
there has
been little theoretical investigation on the  statistical and computational
guarantees of
Lloyd's algorithm. In this paper, we show that under a suitable
initialization, Lloyd's
algorithms converges to an exponential small clustering error after an
order of log n
iterative steps for clustering mixture of sub-Gaussians, where n is the
sample size.
Implications of our results on random initialization are discussed.

See you Friday at 11am in the Stat's classroom.

Regards,
sekhar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/ypng/attachments/20161107/81e51ec8/attachment.html