Robust k-means clustering for distributions with two moments

DOI10.1214/20-AOS2033zbMATH Open1487.62070arXiv2002.02339OpenAlexW3204688258MaRDI QIDQ2054489FDOQ2054489

Authors: Yegor Klochkov, Alexey Kroshnin, Nikita Zhivotovskiy 

Publication date: 3 December 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2002.02339

Recommendations

• Robust moment estimation and improved clustering via sum of squares
• Robust interval type-2 possibilistic \(C\)-means clustering
• Robust and sparse \(k\)-means clustering for high-dimensional data
• Robust hierarchical \(k\)-center clustering
• Robust estimation of the mean vector for high-dimensional data set using robust clustering
• A robust algorithm for cluster initialization using uniform effect of \(k\)-means
• A review of robust clustering methods
• Some refinements of rough \(k\)-means clustering
• Robust clustering by double bisection crossing minimization

zbMATH Keywords

clusteringrobust estimation\(k\)-meansexcess distortion bounds

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Robustness and adaptive procedures (parametric inference) (62F35)

Cites Work

• Strong consistency of k-means clustering
• Extensions of Lipschitz mappings into a Hilbert space
• High-Dimensional Probability
• Title not available (Why is that?)
• The space complexity of approximating the frequency moments
• Concentration inequalities. A nonasymptotic theory of independence
• Foundations of quantization for probability distributions
• Upper and Lower Bounds for Stochastic Processes
• Title not available (Why is that?)
• Theory of Classification: a Survey of Some Recent Advances
• $K$-Dimensional Coding Schemes in Hilbert Spaces
• On Hölder fields clustering
• Fast rates for empirical vector quantization
• Improved Minimax Bounds on the Test and Training Distortion of Empirically Designed Vector Quantizers
• On the Performance of Clustering in Hilbert Spaces
• The minimax distortion redundancy in empirical quantizer design
• Quantization and clustering with Bregman divergences
• Empirical risk minimization for heavy-tailed losses
• Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries
• Robust machine learning by median-of-means: theory and practice
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• Robust Bregman clustering
• Testing the manifold hypothesis
• Sub-Gaussian estimators of the mean of a random vector
• Robust covariance estimation under \(L_4\)-\(L_2\) norm equivalence
• Near-optimal mean estimators with respect to general norms
• Regularization, sparse recovery, and median-of-means tournaments
• Robust classification via MOM minimization
• A Vector-Contraction Inequality for Rademacher Complexities

Cited In (7)

• Snipping for robust \(k\)-means clustering under component-wise contamination
• Robustifying Markowitz
• Distribution-free robust linear regression
• K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means
• Topics in robust statistical learning
• Upper bound estimations of misclassification rate in the heteroscedastic clustering model with sub-Gaussian noises
• Also for \(k\)-means: more data does not imply better performance

This page was built for publication: Robust \(k\)-means clustering for distributions with two moments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2054489)