ScoreQuant

Stability of K-Means Clustering

Rakhlin, Caponnetto2006Vector quantization and Voronoi theory

PDF

Rakhlin & Caponnetto (2006): almost-minimizer rigidity

Use

direct prior art for the compact-codebook rigidity and uniform-law core of DS16.1. What does not transfer: their feasible objects are nearest-center codebooks, whereas DS16 starts from arbitrary sample groupings; they also do not handle unbounded finite-second-moment sources, signed nuisance moments, profiled Fisher information, or a nuisance-margin price.

For bounded Euclidean sources and the nearest-center squared-error risk, Rakhlin & Caponnetto define population almost-minimizers and prove that their diameter shrinks when the population minimizer is unique. A covering-number uniform law transfers that geometry to empirical minimizers and stability under sample replacement.

NeurIPS 19. For bounded sources and nearest-center squared-error codebooks, uniqueness of the population minimizer forces the population almost-minimizer set to shrink; a covering-number uniform law transfers this to empirical stability. Direct prior art for DS16.1's codebook-rigidity ingredient, but not for arbitrary groupings or nuisance moments.

Cited by