skip to content

Faculty of Economics

Journal Cover

Klochkov, Y., Kroshnin, A. and Zhivotovskiy, N.

Robust k-means Clustering for Distributions with Two Moments

Annals of Statistics, forthcoming


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 Rd. In a special case of clustering in Rd, 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.

Author links:

PDF Link:

Papers and Publications

Recent Publications

Elliott, M., Golub, B. and Leduc, M. V. Supply Network Formation and Fragility American Economic Review [2022]

Merrick Li, Z. and Linton, O. A ReMeDI for Microstructure Noise Econometrica [2022]

Rauh, C. and Valladares-Esteban, A. On the Black-White Gaps in Labor Supply and Earnings over the Lifecycle in the US Review of Economic Dynamics [2023]

Carneiro, P., Liu, K. and Salvanes, K. G. The Supply of Skill and Endogenous Technical Change: Evidence from a College Expansion Reform Journal of the European Economic Association [2023]