$K-$means with learned metrics

• URL: http://arxiv.org/abs/2603.14601v2
• Date: Thu, 19 Mar 2026 00:57:30 GMT
• Title: $K-$means with learned metrics
• Abstract summary: 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.<n>We prove a general result that states that the $k-$means are continuous with respect to the measured Gromov-Hausdorff topology.
• Score: 2.339080046284584
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
  We revisit random projections for reducing the dimension of high-dimensional polygonal curves.<n>We give a simplified proof of the known $O(varepsilon-2log(nm))$ bound on the target dimension of a random projection.<n>Our proof is based on the concept of sparse oblivious subspace embeddings.
  arXiv  Detail & Related papers  (2026-07-03T08:48:35Z)
• Denoising distances beyond the volumetric barrier [13.045166411221539]
  ORDER achieves pointwise distance estimation of order $n-ari(d+5)$ up to polylogthmic factors in $n$ in time.<n>We prove that the Gromov-Wasserstein distance between the reconstructed metric measure space and the true latent manifold is of order $n-1/d$.<n>Our results are proven in a very general setting which includes general models of noisy pairwise distances, random geometric graphs, and unknown connection probability functions.
  arXiv  Detail & Related papers  (2026-04-01T03:20:16Z)
• Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds [57.179679246370114]
  We construct metrics that are geodesically complete while ensuring that every stationary point under the new metric remains stationary under the original one.<n>An $$-stationary point under the constructed metric $g'$ also corresponds to an $$-stationary point under the original metric $g'$.<n>Experiments on a practical mesh optimization task demonstrate that our framework maintains stable convergence even in the absence of geodesic completeness.
  arXiv  Detail & Related papers  (2026-01-12T22:08:03Z)
• Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach [53.66196601631798]
  We study the recently introduced Cantor-Kantorovich (or CK) distance.<n>In particular we show that the latter can be framed as a discounted sum of finite-horizon Total Variation distances.<n>More precisely, we show that the exact computation of the CK distance is #P-hard.
  arXiv  Detail & Related papers  (2025-11-22T16:02:56Z)
• Reconstruction of Manifold Distances from Noisy Observations [0.745554610293091]
  We consider the problem of reconstructing the intrinsic geometry of a manifold from noisy pairwise distance observations.<n>We develop a new framework for recovering all distances between points in a sufficiently dense subsample of $M$.<n>We show that a quantitative lower bound on sampling probabilities suffices to modify the cluster construction in the first algorithm and extend all recovery guarantees.
  arXiv  Detail & Related papers  (2025-11-17T06:24:31Z)
• Manifold learning in metric spaces [2.005299372367689]
  Laplacian-based methods are popular for the dimensionality reduction of data lying in $mathbbRN$.<n>We provide a framework that generalizes the problem of manifold learning to metric spaces and study when a metric satisfies sufficient conditions for the pointwise convergence of the graph Laplacian.
  arXiv  Detail & Related papers  (2025-03-20T14:37:40Z)
• Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
  This paper presents a new performance bound for estimation problems where the parameter to estimate lies in a smooth manifold. It induces a geometry for the parameter manifold, as well as an intrinsic notion of the estimation error measure.
  arXiv  Detail & Related papers  (2023-11-08T15:17:13Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Estimation and inference for the Wasserstein distance between mixing measures in topic models [18.66039789963639]
  The Wasserstein distance between mixing measures has come to occupy a central place in the statistical analysis of mixture models. This work proposes a new canonical interpretation of this distance and provides tools to perform inference on the Wasserstein distance in topic models.
  arXiv  Detail & Related papers  (2022-06-26T02:33:40Z)
• Tangent Space and Dimension Estimation with the Wasserstein Distance [10.118241139691952]
  Consider a set of points sampled independently near a smooth compact submanifold of Euclidean space. We provide mathematically rigorous bounds on the number of sample points required to estimate both the dimension and the tangent spaces of that manifold.
  arXiv  Detail & Related papers  (2021-10-12T21:02:06Z)
• Kernel distance measures for time series, random fields and other structured data [71.61147615789537]
  kdiff is a novel kernel-based measure for estimating distances between instances of structured data. It accounts for both self and cross similarities across the instances and is defined using a lower quantile of the distance distribution. Some theoretical results are provided for separability conditions using kdiff as a distance measure for clustering and classification problems.
  arXiv  Detail & Related papers  (2021-09-29T22:54:17Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• Intrinsic persistent homology via density-based metric learning [1.0499611180329804]
  We prove that the metric space defined by the sample endowed with a computable metric known as sample Fermat distance converges a.s. The limiting object is the manifold itself endowed with the population Fermat distance, an intrinsic metric that accounts for both the geometry of the manifold and the density that produces the sample.
  arXiv  Detail & Related papers  (2020-12-11T18:54:36Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.