On the Sequential Convergence of Lloyd's Algorithms

• 成果类型: Article; Early Access
• 署名作者: Portales, Leo; Cazelles, Elsa; Pauwelsc, Edouard
• 署名单位: Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0550
• 发表日期: 2025
• 关键词: subanalytic functions; descent methods; QUANTIZATION; integration; nonconvex; minimization; THEOREM

摘要

Lloyd's algorithm is an iterative method that solves the quantization problem, that is, the approximation of a target probability measure by a discrete one, and is particularly used in digital applications. This algorithm can be interpreted as a gradient method on a certain quantization functional which is given by optimal transport. We study the sequential convergence (to a single accumulation point) for two variants of Lloyd's method: (i) optimal quantization with an arbitrary discrete measure and (ii) uniform quantization with a uniform discrete measure. For both cases, we prove sequential convergence of the iterates under an analyticity assumption on the density of the target measure. This includes for example analytic densities truncated to a compact semialgebraic set. The argument leverages the log-analytic nature of globally subanalytic integrals, the interpretation of Lloyd's method as a gradient method, and the convergence analysis of gradient algorithms under Kurdyka-& Lstrok;ojasiewicz assumptions. As a by-product, we also obtain definability results for more general semidiscrete optimal transport losses such as transport distances with general costs, the max-sliced Wasserstein distance, and the entropy regularized optimal transport loss.