# K-means with learned metrics

arXiv: https://arxiv.org/abs/2603.14601 · HTML: https://mlsanity.com/paper/2603.14601/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 63 references that are in the map.
- First posted on arXiv 15 Mar 2026.

## Builds on (most cited first, 15 of 15)

- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Balancing Geometry and Density: Path Distances on High-Dimensional Data](https://mlsanity.com/paper/2012.09385/) (2020)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [Power Weighted Shortest Paths for Clustering Euclidean Data](https://mlsanity.com/paper/1905.13345/) (2019)
- [Intrinsic persistent homology via density-based metric learning](https://mlsanity.com/paper/2012.07621/) (2020)
- [Asymptotic Theory of Geometric and Adaptive k-Means Clustering](https://mlsanity.com/paper/2202.13423/) (2022)
- [On clustering uncertain and structured data with Wasserstein barycenters and a geodesic criterion for the number of clusters](https://mlsanity.com/paper/1912.11801/) (2019)
- [A kernel-based analysis of Laplacian Eigenmaps](https://mlsanity.com/paper/2402.16481/) (2024)
- [Choosing the parameter of the Fermat distance: navigating geometry and noise](https://mlsanity.com/paper/2311.18663/) (2023)
- [Manifold learning in metric spaces](https://mlsanity.com/paper/2503.16187/) (2025)
- [Wasserstein k-Centers Clustering for Distributional Data](https://mlsanity.com/paper/2407.08228/) (2024)
- [On uniqueness of the set of k-means](https://mlsanity.com/paper/2410.13495/) (2024)
- [Finite sample bounds for barycenter estimation in geodesic spaces](https://mlsanity.com/paper/2502.14069/) (2025)

## Abstract (arXiv)

We study the Fr'echet 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.