{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:31Z","timestamp":1778231431059,"version":"3.51.4"},"reference-count":68,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>Lloyd\u2019s 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\u2019s 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\u2019s method as a gradient method, and the convergence analysis of gradient algorithms under Kurdyka\u2013\u0141ojasiewicz 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.<\/jats:p>\n                  <jats:p>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 \u201cANR-23-PEIA-0004\u201d. E. Pauwels thanks the 3IA Artificial and Natural Intelligence Toulouse Institute (ANITI), French \u201cInvesting for the Future\u2014PIA3\u201d 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].<\/jats:p>","DOI":"10.1287\/moor.2024.0550","type":"journal-article","created":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T10:53:56Z","timestamp":1746788036000},"page":"1120-1138","source":"Crossref","is-referenced-by-count":1,"title":["On the Sequential Convergence of Lloyd\u2019s Algorithms"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-3075-227X","authenticated-orcid":false,"given":"Leo","family":"Portales","sequence":"first","affiliation":[{"name":"Toulouse Research Institute in Information Technology, Toulouse School of Economics, National Polytechnic Institute of Toulouse, University of Toulouse, 31000 Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7444-0274","authenticated-orcid":false,"given":"Elsa","family":"Cazelles","sequence":"additional","affiliation":[{"name":"CNRS, Toulouse Research Institute in Information Technology, University of Toulouse, 31000 Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8180-075X","authenticated-orcid":false,"given":"Edouard","family":"Pauwels","sequence":"additional","affiliation":[{"name":"Toulouse School of Economics, University of Toulouse Capitole, 31080 Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1137\/040605266"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.2991\/978-94-91216-77-0_14"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0133-5"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0484-9"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0449"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1109\/18.59943"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531392"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-34514-5"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1137\/050644641"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1137\/22M1479178"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0701-9"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1091-6"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-014-0506-3"},{"key":"B14","first-page":"585","volume-title":". Advances in Neural Information Processing Systems","volume":"7","author":"Bottou L","year":"1994"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/130922732"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1034801249"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-2010-213"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255984698"},{"key":"B19","volume-title":"An Introduction to O-Minimal Geometry","author":"Coste M","year":"2000"},{"issue":"1","key":"B20","first-page":"1","volume":"39","author":"Cottrell M","year":"2018","journal-title":"Revista Investigacion Oper."},{"key":"B21","unstructured":"Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal transport. Burges CJ, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds.\n                      NIPS\u201913: Proc. 27th Internat. Conf. Neural Inform. Processing Systems\n                      , vol. 2 (Curran Associates, Red Hook, NY), 2292\u20132923."},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366190"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-018-1000-4"},{"key":"B24","doi-asserted-by":"crossref","unstructured":"Deshpande I, Hu Y, Sun R, Pyrros A, Siddiqui N, Koyejo S, Zhao Z, Forsyth D, Schwing A (2019) Max-sliced Wasserstein distance and its use for GANs.\n                      Proc. IEEE\/CVF Conf. Comput. Vision Pattern Recognition\n                      (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 10648\u201310656.","DOI":"10.1109\/CVPR.2019.01090"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02762093"},{"issue":"2","key":"B26","first-page":"497","volume":"84","author":"Dries L","year":"1996","journal-title":"Duke Math. J."},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1137\/040617364"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1137\/070691334"},{"key":"B30","unstructured":"Fleischer P (1964) Sufficient conditions for achieving minimum distortion in a quantizer.\n                      IEEE Internat. Convention Record\n                      (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 104\u2013111."},{"key":"B31","volume-title":"Advances in Neural Information Processing Systems","volume":"29","author":"Genevay A","year":"2016"},{"key":"B32","unstructured":"Genevay A, Chizat L, Bach F, Cuturi M, Peyr\u00e9 G (2019) Sample complexity of Sinkhorn divergences. Chaudhuri K, Sugiyama M, eds.\n                      Proc. 22nd Internat. Conf. Artificial Intelligence Statist.\n                      Proceedings of Machine Learning Research, vol. 89 (JMLR.org), 1574\u20131583."},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0103945"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64277-2"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/s00209-012-1138-1"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056482"},{"key":"B37","doi-asserted-by":"crossref","unstructured":"Kipnis A, Reeves G, Eldar Y, Goldsmith A (2017) Compressed sensing under optimal quantization.\n                      2017 IEEE Internat. Sympos. Inform. Theory\n                      (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 2148\u20132152.","DOI":"10.1109\/ISIT.2017.8006909"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.4171\/jems\/889"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-89178-5.50003-8"},{"key":"B40","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Kolouri S","year":"2019"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.5802\/aif.1638"},{"issue":"2","key":"B42","first-page":"129","volume":"318","author":"Kurdyka K","year":"1994","journal-title":"Comptes rendus de l\u2019Acad\u00e9mie des sciences: S\u00e9rie 1: Math\u00e9matique"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1967.1098527"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1137\/18M1193736"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.5802\/aif.1637"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-022-09586-4"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"B48","first-page":"19","volume-title":"The Japanese-Australian Workshop on Real and Complex Singularities","volume":"43","author":"Loi T","year":"2010"},{"key":"B49","first-page":"87","volume":"117","author":"\u0141ojasiewicz S","year":"1963","journal-title":"Les \u00c9quations Aux D\u00e9riv\u00e9es Partielles"},{"key":"B50","first-page":"12810","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"M\u00e9rigot Q","year":"2021"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-06-04190-0"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.4115\/jla.2023.15.1"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(97)00190-8"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1051\/proc\/201448002"},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1137\/151005622"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0834-1_8"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1561\/2200000073"},{"key":"B58","doi-asserted-by":"crossref","unstructured":"Rabin J, Peyr\u00e9 G, Delon J, Bernot M (2012) Wasserstein barycenter and its application to texture mixing. Bruckstein AM, Haar Romeny BM, Bronstein AM, Bronstein MM, eds.\n                      Scale Space and Variational Methods in Computer Vision\n                      (Springer, Berlin), 435\u2013446.","DOI":"10.1007\/978-3-642-24785-9_37"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20828-2"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1999.508.189"},{"key":"B61","doi-asserted-by":"crossref","unstructured":"Sun JZ, Goyal VK (2009) Optimal quantization of random measurements in compressed sensing.\n                      2009 IEEE Internat. Symposium Inform. Theory\n                      (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 6\u201310.","DOI":"10.1109\/ISIT.2009.5205695"},{"key":"B62","author":"Tanguy E","year":"2023","journal-title":"Trans. Machine Learn. Res."},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1986-15468-6"},{"key":"B64","first-page":"87","volume":"11","author":"van den Dries L","year":"2002","journal-title":"Model Theory Appl."},{"key":"B65","volume-title":"Optimal Transport: Old and New.","volume":"338","author":"Villani C","year":"2008"},{"key":"B66","volume-title":"Topics in Optimal Transportation","author":"Villani C","year":"2021"},{"key":"B67","doi-asserted-by":"publisher","DOI":"10.1109\/18.108266"},{"key":"B68","doi-asserted-by":"crossref","unstructured":"Zhou Y, Moosavi-Dezfooli SM, Cheung NM, Frossard P (2018) Adaptive quantization for deep neural network.\n                      Proc. AAAI Conf. Artificial Intelligence\n                      , vol. 32 (AAAI Press, Palo Alto, CA), 4596\u20134604.","DOI":"10.1609\/aaai.v32i1.11623"}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2024.0550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:24:30Z","timestamp":1778228670000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2024.0550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2024.0550"],"URL":"https:\/\/doi.org\/10.1287\/moor.2024.0550","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}