$K-$means with learned metrics

Pablo Groisman; Matthieu Jonckheere; Jordan Serres; Mariela Sued

math.STMar 15, 2026

$K-$ means with learned metrics

Authors: Pablo Groisman, Matthieu Jonckheere, Jordan Serres, Mariela Sued

Abstract

We study the Fréchet $k-$ means of a metric measure space when both the measure and the distance are unknown and have to be estimated. We prove a general result that states that the $k-$ means are continuous with respect to the measured Gromov-Hausdorff topology. In this situation, we also prove a stability result for the Voronoi clusters they determine. We do not assume uniqueness of the set of $k-$ means, but when it is unique, the results are stronger. This framework provides a unified approach to proving consistency for a wide range of metric learning procedures. As concrete applications, we obtain new consistency results for several important estimators that were previously unestablished, even when $k=1$ . These include $k-$ means based on: (i) Isomap and Fermat geodesic distances on manifolds, (ii) difussion distances, (iii) Wasserstein distances computed with respect to learned ground metrics. Finally, we consider applications beyond the statistical inference paradigm like (iv) first passage percolation and (v) discrete approximations of length spaces.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means
Jul 15, 2024Max Dupré la Tour, David SaulpicClustering Approximation Algorithms
Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms
Aug 11, 2026Florian Beier, Stephan EcksteinClustering Vector Quantization
Department of Mathematics, University of Tübingen, Germany
$k$ -Nearest Neighbors in Gromov--Wasserstein Space
Jun 9, 2026Kaitlyn Hohmeier, Nicolas Fraiman, Caroline MoosmuellerGraph Classification k-Nearest Neighbors
University of North Carolina at Chapel Hill, Department of Mathematics · University of North Carolina at Chapel Hill, Department of Statistics and Operations Research

Jul 15, 2024J/K move · Enter open · S save

Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means

Max Dupré la Tour, David Saulpic

Clustering Approximation Algorithms

Open paper AskPDF arXiv

Clustering problems such as

k

-means and

k

-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art.

Abstract

Clustering

Explore similar work

Faster and Simpler Greedy Algorithm for kkk-Median and kkk-Means

Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms

kkk-Nearest Neighbors in Gromov--Wasserstein Space

Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means

$k$ -Nearest Neighbors in Gromov--Wasserstein Space