{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T16:59:37Z","timestamp":1791392377300,"version":"4.3.3"},"reference-count":54,"publisher":"Institute of Mathematical Statistics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"We revisit Pollard\u2019s classical result on consistency for k-means clustering in Euclidean space, with a focus on extensions in two directions: first, to problems where the data may come from interesting geometric settings (e.g., Riemannian manifolds, reflexive Banach spaces or the Wasserstein space); second, to problems where some parameters are chosen adaptively from the data (e.g., k-medoids or elbow-method k-means). Toward this end, we provide a general theory, which shows that all clustering procedures described above are strongly consistent. In fact, our method of proof allows us to derive many asymptotic limit theorems beyond strong consistency. We also remove all assumptions about uniqueness of the set of optimal cluster centers.<\/jats:p>","DOI":"10.1214\/25-aos2514","type":"journal-article","created":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T05:23:02Z","timestamp":1757654582000},"page":"1559-1586","source":"Crossref","is-referenced-by-count":4,"title":["Asymptotic theory of geometric and adaptive k-means clustering"],"prefix":"10.1214","volume":"53","author":[{"given":"Adam Quinn","family":"Jaffe","sequence":"first","affiliation":[{"name":"Department of Statistics, Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"44","doi-asserted-by":"publisher","unstructured":"Roberts, G. O.<\/small> and Rosenthal, J. S.<\/small> (2004). General state space Markov chains and MCMC algorithms. Probab. Surv.<\/i> 1<\/b> 20\u201371.","DOI":"10.1214\/154957804100000024"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Dembo, A.<\/small> and Zeitouni, O.<\/small> (1998). Large Deviations Techniques and Applications<\/i>, 2nd ed. Applications of Mathematics<\/i> (New York<\/i>) 38<\/b>. Springer, New York.","DOI":"10.1007\/978-1-4612-5320-4"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Fefferman, C.<\/small>, Mitter, S.<\/small> and Narayanan, H.<\/small> (2016). Testing the manifold hypothesis. J. Amer. Math. Soc.<\/i> 29<\/b> 983\u20131049.","DOI":"10.1090\/jams\/852"},{"key":"41","doi-asserted-by":"crossref","unstructured":"Pollard, D.<\/small> (1981). Strong consistency of k<\/i>-means clustering. Ann. Statist.<\/i> 9<\/b> 135\u2013140.","DOI":"10.1214\/aos\/1176345339"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Hastie, T.<\/small>, Tibshirani, R.<\/small> and Friedman, J.<\/small> (2001). The Elements of Statistical Learning<\/i>: Data Mining, Inference, and Prediction<\/i>. Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-0-387-21606-5"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Burago, D.<\/small>, Burago, Y.<\/small> and Ivanov, S.<\/small> (2001). A Course in Metric Geometry<\/i>. Graduate Studies in Mathematics<\/i> 33<\/b>. Amer. Math. Soc., Providence, RI.","DOI":"10.1090\/gsm\/033"},{"key":"37","doi-asserted-by":"crossref","unstructured":"PARK, H.-S.<\/small> and JUN, C.-H.<\/small> (2009). A simple and fast algorithm for K-medoids clustering. Expert Syst. Appl.<\/i> 36<\/b> 3336\u20133341.","DOI":"10.1016\/j.eswa.2008.01.039"},{"key":"46","doi-asserted-by":"publisher","unstructured":"TARPEY, T.<\/small> and KINATEDER, K. K. J.<\/small> (2003). Clustering functional data. J. Classification<\/i> 20<\/b> 93\u2013114.","DOI":"10.1007\/s00357-003-0007-3"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Biau, G.<\/small>, Devroye, L.<\/small> and Lugosi, G.<\/small> (2008). On the performance of clustering in Hilbert spaces. IEEE Trans. Inf. Theory<\/i> 54<\/b> 781\u2013790.","DOI":"10.1109\/TIT.2007.913516"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Kallenberg, O.<\/small> (2002). Foundations of Modern Probability<\/i>, 2nd ed. Probability and Its Applications<\/i> (New York<\/i>). Springer, New York.","DOI":"10.1007\/978-1-4757-4015-8"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Villani, C.<\/small> (2009). Optimal Transport<\/i>: Old and New<\/i>. Grundlehren der Mathematischen Wissenschaften<\/i> [Fundamental Principles of Mathematical Sciences<\/i>] 338<\/b>. Springer, Berlin.","DOI":"10.1007\/978-3-540-71050-9"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Tibshirani, R.<\/small>, Walther, G.<\/small> and Hastie, T.<\/small> (2001). Estimating the number of clusters in a data set via the gap statistic. J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> 63<\/b> 411\u2013423.","DOI":"10.1111\/1467-9868.00293"},{"key":"1","doi-asserted-by":"publisher","unstructured":"ABAYA, E. F.<\/small> and WISE, G. L.<\/small> (1984). Convergence of vector quantizers with applications to optimal quantization. SIAM J. Appl. Math.<\/i> 44<\/b> 183\u2013189.","DOI":"10.1137\/0144013"},{"key":"2","unstructured":"ALPAYDIN, E.<\/small> (2016). Machine Learning<\/i>: The New AI<\/i>, 2nd ed. MIT Press Essential Knowledge Series<\/i>. MIT Press, Cambridge, MA."},{"key":"3","unstructured":"BAGARIA, V.<\/small>, KAMATH, G.<\/small>, NTRANOS, V.<\/small>, ZHANG, M.<\/small> and TSE, D.<\/small> (2018). Medoids in almost-linear time via multi-armed bandits (A. Storkey and F. Perez-Cruz, eds.). Proc. Mach. Learn. Res.<\/i> 84<\/b> 500\u2013509. PMLR, Playa Blanca, Lanzarote, Canary Islands."},{"key":"4","unstructured":"BAHARAV, T.<\/small> and TSE, D.<\/small> (2019). Ultra fast medoid identification via correlated sequential halving. In Adv. in Neural Inf. Process. Syst.<\/i> (H. Wallach, H. Larochelle, A. Beygelzimer, F. d\u2019 Alch\u00e9-Buc, E. Fox and R. Garnett, eds.) 32<\/b>. Curran Associates, Red Hook."},{"key":"5","doi-asserted-by":"crossref","unstructured":"BARNHILL, D.<\/small> and YOSHIDA, R.<\/small> (2023). Clustering methods over the tropical projective torus. Mathematics<\/i> 11<\/b> 3433.","DOI":"10.3390\/math11153433"},{"key":"6","doi-asserted-by":"publisher","unstructured":"BEER, G.<\/small> (1993). Topologies on Closed and Closed Convex Sets<\/i>. Mathematics and Its Applications<\/i> 268<\/b>. Kluwer Academic, Dordrecht.","DOI":"10.1007\/978-94-015-8149-3"},{"key":"8","unstructured":"BOCK, H.-H.<\/small> (2008). Origins and extensions of the k<\/i>-means algorithm in cluster analysis. J. \u00c9lectron. Hist. Probab. Stat.<\/i> 4<\/b> 18."},{"key":"10","doi-asserted-by":"publisher","unstructured":"CAO, Y.<\/small>, LEUNG, P.<\/small> and MONOD, A.<\/small> (2025). k<\/i>-means clustering for persistent homology. Adv. Data Anal. Classif.<\/i> 19<\/b> 95\u2013119.","DOI":"10.1007\/s11634-023-00578-y"},{"key":"11","doi-asserted-by":"publisher","unstructured":"CUESTA, J. A.<\/small> and MATR\u00c1N, C.<\/small> (1988). The strong law of large numbers for k<\/i>-means and best possible nets of Banach valued random variables. Probab. Theory Related Fields<\/i> 78<\/b> 523\u2013534.","DOI":"10.1007\/BF00353875"},{"key":"12","doi-asserted-by":"publisher","unstructured":"DEL BARRIO, E.<\/small>, CUESTA-ALBERTOS, J. A.<\/small>, MATR\u00c1N, C.<\/small> and MAYO-\u00cdSCAR, A.<\/small> (2019). Robust clustering tools based on optimal transportation. Stat. Comput.<\/i> 29<\/b> 139\u2013160.","DOI":"10.1007\/s11222-018-9800-z"},{"key":"14","doi-asserted-by":"publisher","unstructured":"EVANS, S. N.<\/small> and JAFFE, A. Q.<\/small> (2024). Limit theorems for Fr\u00e9chet mean sets. Bernoulli<\/i> 30<\/b> 419\u2013447.","DOI":"10.3150\/23-bej1603"},{"key":"16","doi-asserted-by":"publisher","unstructured":"FLURY, B. A.<\/small> (1990). Principal points. Biometrika<\/i> 77<\/b> 33\u201341.","DOI":"10.1093\/biomet\/77.1.33"},{"key":"17","doi-asserted-by":"publisher","unstructured":"FLURY, B. D.<\/small> (1993). Estimation of principal points. J. R. Stat. Soc<\/i>., Ser. C<\/i> 42<\/b> 139\u2013151.","DOI":"10.2307\/2347416"},{"key":"18","unstructured":"G\u00c9RON, A.<\/small> (2017). Hands-on Machine Learning with Scikit-Learn and TensorFlow<\/i>: Concepts, Tools, and Techniques to Build Intelligent Systems<\/i>. O\u2019Reilly Media, Sebastopol, CA."},{"key":"20","unstructured":"JAFFE, A. Q.<\/small> (2024). Fr\u00e9chet means in infinite dimensions. Preprint. Available at arXiv:2410.17214<\/a>."},{"key":"21","doi-asserted-by":"crossref","unstructured":"JAFFE, A. Q.<\/small> (2025). Supplement to \u201cAsymptotic Theory of Geometric and Adaptive k<\/i>-Means Clustering.\u201d https:\/\/doi.org\/10.1214\/25-AOS2514SUPP<\/a>","DOI":"10.1214\/25-AOS2514SUPP"},{"key":"22","unstructured":"JAFFE, A. Q.<\/small> and SANTORO, L. V.<\/small> (2024). Large Deviations Principle for Bures\u2013Wasserstein Barycenters. Preprint. Available at arXiv:2409.11384<\/a>."},{"key":"23","unstructured":"JIANG, H.<\/small> and ARIAS-CASTRO, E.<\/small> (2021). On the consistency of metric and non-metric K-medoids. In Proceedings of the<\/i> 24th International Conference on Artificial Intelligence and Statistics<\/i> (A. Banerjee and K. Fukumizu, eds.). Proceedings of Machine Learning Research<\/i> 130<\/b> 2485\u20132493. PMLR."},{"key":"25","unstructured":"KAUFMAN, L.<\/small> and ROUSSEEUW, P. J.<\/small> (1987). Clustering by means of medoids. In Statistical Data Analysis Based on the L<\/i>1-Norm and Related Methods<\/i> (Y. Doge, ed.) 405\u2013416."},{"key":"26","doi-asserted-by":"publisher","unstructured":"KAUFMAN, L.<\/small> and ROUSSEEUW, P. J.<\/small> (1990). Finding Groups in Data<\/i>: An Introduction to Cluster Analysis<\/i>. Wiley Series in Probability and Mathematical Statistics<\/i>: Applied Probability and Statistics<\/i>. Wiley, New York.","DOI":"10.1002\/9780470316801"},{"key":"27","doi-asserted-by":"publisher","unstructured":"KLOCHKOV, Y.<\/small>, KROSHNIN, A.<\/small> and ZHIVOTOVSKIY, N.<\/small> (2021). Robust k<\/i>-means clustering for distributions with two moments. Ann. Statist.<\/i> 49<\/b> 2206\u20132230.","DOI":"10.1214\/20-aos2033"},{"key":"28","doi-asserted-by":"publisher","unstructured":"LALO\u00cb, T.<\/small> (2010). L<\/mi><\/mrow>1<\/mn><\/mrow><\/msub><\/math>-quantization and clustering in Banach spaces. Math. Methods Statist.<\/i> 19<\/b> 136\u2013150.","DOI":"10.3103\/S1066530710020031"},{"key":"29","doi-asserted-by":"publisher","unstructured":"LE BRIGANT, A.<\/small> and PUECHMOREL, S.<\/small> (2019). Quantization and clustering on Riemannian manifolds with an application to air traffic analysis. J. Multivariate Anal.<\/i> 173<\/b> 685\u2013703.","DOI":"10.1016\/j.jmva.2019.05.008"},{"key":"30","doi-asserted-by":"publisher","unstructured":"LEMBER, J.<\/small> (2003). On minimizing sequences for k<\/i>-centres. J. Approx. Theory<\/i> 120<\/b> 20\u201335.","DOI":"10.1016\/S0021-9045(02)00010-2"},{"key":"31","doi-asserted-by":"crossref","unstructured":"LINDER, T.<\/small> (2000). On the training distortion of vector quantizers. IEEE Trans. Inf. Theory<\/i> 46<\/b> 1617\u20131623.","DOI":"10.1109\/18.850705"},{"key":"32","unstructured":"MACQUEEN, J.<\/small> (1967). Some methods for classification and analysis of multivariate observations. In Proc. Fifth Berkeley Sympos. Math. Statist. And Probability<\/i> (Berkeley, Calif<\/i>., 1965\/66), Vol. I<\/i>: Statistics<\/i> 281\u2013297. Univ. California Press, Berkeley, CA."},{"key":"33","doi-asserted-by":"publisher","unstructured":"MARDIA, K. V.<\/small>, WIECHERS, H.<\/small>, ELTZNER, B.<\/small> and HUCKEMANN, S. F.<\/small> (2022). Principal component analysis and clustering on manifolds. J. Multivariate Anal.<\/i> 188<\/b> Paper No. 104862.","DOI":"10.1016\/j.jmva.2021.104862"},{"key":"34","unstructured":"MIOLANE, N.<\/small>, GUIGUI, N.<\/small>, LE BRIGANT, A.<\/small> et al. (2020). Geomstats: A Python package for Riemannian geometry in machine learning. J. Mach. Learn. Res.<\/i> 21<\/b> Paper No. 223."},{"key":"35","unstructured":"MOLNAR, C.<\/small> (2022). Interpretable Machine Learning<\/i>, 2nd ed."},{"key":"36","doi-asserted-by":"publisher","unstructured":"PAPAYIANNIS, G. I.<\/small>, DOMAZAKIS, G. N.<\/small>, DRIVALIARIS, D.<\/small>, KOUKOULAS, S.<\/small>, TSEKREKOS, A. E.<\/small> and YANNACOPOULOS, A. N.<\/small> (2021). On clustering uncertain and structured data with Wasserstein barycenters and a geodesic criterion for the number of clusters. J. Stat. Comput. Simul.<\/i> 91<\/b> 2569\u20132594.","DOI":"10.1080\/00949655.2021.1903463"},{"key":"38","unstructured":"P\u00c4RNA, K.<\/small> (1986). Strong consistency of k<\/i>-means clustering criterion in separable metric spaces. Tartu Riikl. \u00dcl. Toimetised<\/i> 733<\/b> 86\u201396."},{"key":"39","unstructured":"P\u00c4RNA, K.<\/small> (1988). On the stability of k<\/i>-means clustering in metric spaces. Tartu Riikl. \u00dcl. Toimetised<\/i> 798<\/b> 19\u201336."},{"key":"40","unstructured":"P\u00c4RNA, K.<\/small> (1990). On the existence and weak convergence of k<\/i>-centres in Banach spaces. Tartu Riikl. \u00dcl. Toimetised<\/i> 893<\/b> 17\u201328."},{"key":"42","doi-asserted-by":"publisher","unstructured":"POLLARD, D.<\/small> (1982). Quantization and the method of k<\/i>-means. IEEE Trans. Inf. Theory<\/i> 28<\/b> 199\u2013205.","DOI":"10.1109\/TIT.1982.1056481"},{"key":"43","unstructured":"RAO, R.<\/small>, MOSCOVICH, A.<\/small> and SINGER, A.<\/small> (2020). Wasserstein K-Means for Clustering Tomographic Projections. CoRR<\/i>. Available at arXiv:2010.09989<\/a>."},{"key":"45","doi-asserted-by":"crossref","unstructured":"SURYANTO, C. H.<\/small>, SAIGO, H.<\/small> and FUKUI, K.<\/small> (2012). Protein clustering on a Grassmann manifold. In Pattern Recognition in Bioinformatics<\/i> (T. Shibuya, H. Kashima, J. Sese and S. Ahmad, eds.) 71\u201381. Springer, Berlin.","DOI":"10.1007\/978-3-642-34123-6_7"},{"key":"47","doi-asserted-by":"publisher","unstructured":"THORPE, M.<\/small>, THEIL, F.<\/small>, JOHANSEN, A. M.<\/small> and CADE, N.<\/small> (2015). Convergence of the k<\/i>-means minimization problem using \u0393-convergence. SIAM J. Appl. Math.<\/i> 75<\/b> 2444\u20132474.","DOI":"10.1137\/140974365"},{"key":"49","unstructured":"TIWARI, M.<\/small>, ZHANG, M. J.<\/small>, MAYCLIN, J.<\/small>, THRUN, S.<\/small>, PIECH, C.<\/small> and SHOMORONY, I.<\/small> (2020). BanditPAM: Almost linear time k-medoids clustering via multi-armed bandits. In Adv. in Neural Inf. Process. Syst.<\/i> (H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan and H. Lin, eds.) 33<\/b> 10211\u201310222. Curran Associates, Red Hook."},{"key":"50","doi-asserted-by":"crossref","unstructured":"TURAGA, P.<\/small>, VEERARAGHAVAN, A.<\/small>, SRIVASTAVA, A.<\/small> and CHELLAPPA, R.<\/small> (2011). Statistical computations on Grassmann and Stiefel manifolds for image and video-based recognition. IEEE Trans. Pattern Anal. Mach. Intell.<\/i> 33<\/b> 2273\u20132286.","DOI":"10.1109\/TPAMI.2011.52"},{"key":"51","doi-asserted-by":"publisher","unstructured":"VERDINELLI, I.<\/small> and WASSERMAN, L.<\/small> (2019). Hybrid Wasserstein distance and fast distribution clustering. Electron. J. Stat.<\/i> 13<\/b> 5088\u20135119.","DOI":"10.1214\/19-EJS1639"},{"key":"53","doi-asserted-by":"publisher","unstructured":"WANG, R.<\/small>, WANG, X.<\/small> and WU, L.<\/small> (2010). Sanov\u2019s theorem in the Wasserstein distance: A necessary and sufficient condition. Statist. Probab. Lett.<\/i> 80<\/b> 505\u2013512.","DOI":"10.1016\/j.spl.2009.12.003"},{"key":"54","doi-asserted-by":"crossref","unstructured":"ZHUANG, Y.<\/small>, CHEN, X.<\/small> and YANG, Y.<\/small> (2022). Wasserstein K<\/i>-means for clustering probability distributions. In Advances in Neural Information Processing Systems<\/i> 35: Annual Conference on Neural Information Processing Systems<\/i> 2022, NeurIPS<\/i> 2022, New Orleans, LA, USA, November<\/i> 28\u2013December<\/i> 9, 2022 (S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho and A. Oh, eds.).","DOI":"10.52202\/068431-0827"}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T16:37:49Z","timestamp":1791391069000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-53\/issue-4\/Asymptotic-theory-of-geometric-and-adaptive-k-means-clustering\/10.1214\/25-AOS2514.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"references-count":54,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,8,1]]}},"URL":"https:\/\/doi.org\/10.1214\/25-aos2514","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,1]]}}}