AI Seminar: Robust k-means Clustering for Distributions with Two Moments

Nikita Zhivotovskiy portrait photo


Nikita Zhivotovskiy, Postdoctoral Researcher at Google Research, Brain Team, Zürich.


This talk is devoted to robust algorithms for the k-means clustering problem where a quantizer is constructed based on N independent observations. First, I will present an overview of some recent results on the robust mean estimation. Then I will explain how to extend these results to prove sharp non-asymptotic performance guarantees for the k-means clustering that hold under the two bounded moments assumption in a general Hilbert space. This extends the renowned asymptotic result of David Pollard (Annals of Stats, 1981) who showed that the existence of two moments is sufficient for strong consistency of an empirically optimal quantizer. I will conclude by providing some algorithmic open problems.

Based on a joint recent work with Y. Klochkov and A. Kroshnin (