  Though mostly used as a clustering algorithm, k-means are originally designed
as a quantization algorithm. Namely, it aims at providing a compression of a
probability distribution with k points. Building upon [21, 33], we try to
investigate how and when these two approaches are compatible. Namely, we show
that provided the sample distribution satisfies a margin like condition (in the
sense of [27] for supervised learning), both the associated empirical risk
minimizer and the output of Lloyd's algorithm provide almost optimal
classification in certain cases (in the sense of [6]). Besides, we also show
that they achieved fast and optimal convergence rates in terms of sample size
and compression risk.
