Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ arXiv.org e-Print Ar...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
HAL INRAE
Article . 2024
License: CC BY
Data sources: HAL INRAE
Mathematics of Operations Research
Article . 2025 . Peer-reviewed
Data sources: Crossref
https://dx.doi.org/10.48550/ar...
Article . 2024
License: CC BY
Data sources: Datacite
versions View all 4 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

On the Sequential Convergence of Lloyd’s Algorithms

Authors: Leo Portales; Elsa Cazelles; Edouard Pauwels;

On the Sequential Convergence of Lloyd’s Algorithms

Abstract

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–Ł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. Funding: This work benefited from financial support from the French government managed by the National Agency for Research under the France 2030 program, with the reference “ANR-23-PEIA-0004”. E. Pauwels thanks the 3IA Artificial and Natural Intelligence Toulouse Institute (ANITI), French “Investing for the Future—PIA3” program [Grant ANR-19-PI3A-000], the Air Force Office of Scientific Research, Air Force Material Command [Grant FA8655-22-1-7012], TSE-P, Institut Universitaire de France, and acknowledges support from ANR Chess [Grant ANR-17-EURE-0010], ANR Regulia and ANR MAD [Grant ANR-24-CE23-1529-02].

Keywords

Optimization, O-minimal, Gradient methods, Lloyd's algorithm, Optimization and Control (math.OC), Quantization, KL inequality, Optimal transport, FOS: Mathematics, [MATH] Mathematics [math], Mathematics - Optimization and Control

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green
Related to Research communities
INRAE