Convergence Rate of Optimal Quantization and Application to the Clustering Performance of the Empirical Measure
Liu, Yating; Pagès, Gilles (2020), Convergence Rate of Optimal Quantization and Application to the Clustering Performance of the Empirical Measure. https://basepub.dauphine.fr/handle/123456789/20716
TypeDocument de travail / Working paper
External document linkhttps://hal.archives-ouvertes.fr/hal-02484426
Series titleJournal of Machine Learning Research
MetadataShow full item record
Abstract (EN)We study the convergence rate of the optimal quantization for a probability measure sequence (µn) n∈N* on R^d converging in the Wasserstein distance in two aspects: the first one is the convergence rate of optimal quantizer x (n) ∈ (R d) K of µn at level K; the other one is the convergence rate of the distortion function valued at x^(n), called the "performance" of x^(n). Moreover, we also study the mean performance of the optimal quantization for the empirical measure of a distribution µ with finite second moment but possibly unbounded support. As an application, we show that the mean performance for the empirical measure of the multidimensional normal distribution N (m, Σ) and of distributions with hyper-exponential tails behave like O(log n √ n). This extends the results from [BDL08] obtained for compactly supported distribution. We also derive an upper bound which is sharper in the quantization level K but suboptimal in n by applying results in [FG15].
Subjects / KeywordsClustering performance; Convergence rate of optimal quantization; Distortion function; Empirical measure; Optimal quantization
Showing items related by title and author.