AI Seminar: Robust k-means Clustering for Distributions with Two Moments
Speaker
Nikita Zhivotovskiy, Postdoctoral Researcher at Google Research, Brain Team, Zürich.
Abstract
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 (https://arxiv.org/abs/2002.02339).
This seminar is a part of the AI Seminar Series organised by SCIENCE AI Centre. The series highlights advances and challenges in research within Machine Learning, Data Science, and AI. Like the AI Centre itself, the seminar series has a broad scope, covering both new methodological contributions, ground-breaking applications, and impacts on society.