Robust \(k\)-means Clustering for Distributions with Two Moments

We consider the robust algorithms for the \(k\)-means clustering problem where a quantizer is constructed based on \(N\) independent observations. Our main results are median of means based non-asymptotic excess distortion bounds that hold under the two bounded moments assumption in a general separa...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-11
Main Authors: Klochkov, Yegor, Kroshnin, Alexey, Zhivotovskiy, Nikita
Format: Article
Language:English
Subjects:
Algorithms
Asymptotic properties
Clustering
Distortion
Hilbert space
Lower bounds
Robustness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the robust algorithms for the \(k\)-means clustering problem where a quantizer is constructed based on \(N\) independent observations. Our main results are median of means based non-asymptotic excess distortion bounds that hold under the two bounded moments assumption in a general separable Hilbert space. In particular, our results extend the renowned asymptotic result of Pollard, 1981 who showed that the existence of two moments is sufficient for strong consistency of an empirically optimal quantizer in \(\mathbb{R}^d\). In a special case of clustering in \(\mathbb{R}^d\), under two bounded moments, we prove matching (up to constant factors) non-asymptotic upper and lower bounds on the excess distortion, which depend on the probability mass of the lightest cluster of an optimal quantizer. Our bounds have the sub-Gaussian form, and the proofs are based on the versions of uniform bounds for robust mean estimators.
ISSN:2331-8422