arXiv:2602.04335stat.MLcs.LG2026-02

提出无需求解器的快速最优传输距离估计方法,可自动校准误差并提升计算效率。

Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation

  • 利用半对偶泛函构造免求解器的最优传输估计器,无须调参
  • 首次实现基于采样误差衰减的快速内在维数估计,精度高且稳定
  • 适用于需要精准水桶距离估算的机器学习任务,尤其适合高维数据

在大规模最优传输(OT)问题中,通常通过采样测度转化为可处理的离散问题。尽管离散求解器的精度可控,但其收敛速度受限于数据的内在维数。因此,真正的瓶颈在于采样误差的掌握与控制。本文提出新的采样误差与内在维数估计器。核心发现是:仅利用半对偶OT泛函即可构建一个简单、免调参的$ ext{OT}_c(ρ, arρ)$估计器,且完全无需运行任何OT求解器。进一步,我们从采样误差的多尺度衰减特性中导出一种快速内在维数估计方法。该框架在实践中带来显著的计算与统计优势,使我们能够(i)量化离散化误差的收敛速率,(ii)根据数据内在几何结构校准Sinkhorn散度的熵正则化参数,(iii)引入一种基于内在维数的新型理查森外推估计器,有效消除水桶距离估计的偏差。数值实验表明,该几何感知流程能有效缓解离散化误差瓶颈,同时保持高效计算性能。

原文摘要 · Abstract (English)

Solving large scale Optimal Transport (OT) in machine learning typically relies on sampling measures to obtain a tractable discrete problem. While the discrete solver's accuracy is controllable, the rate of convergence of the discretization error is governed by the intrinsic dimension of our data. Therefore, the true bottleneck is the knowledge and control of the sampling error. In this work, we tackle this issue by introducing novel estimators for both sampling error and intrinsic dimension. The key finding is a simple, tuning-free estimator of $\text{OT}_c(ρ, \hatρ)$ that utilizes the semi-dual OT functional and, remarkably, requires no OT solver. Furthermore, we derive a fast intrinsic dimension estimator from the multi-scale decay of our sampling error estimator. This framework unlocks significant computational and statistical advantages in practice, enabling us to (i) quantify the convergence rate of the discretization error, (ii) calibrate the entropic regularization of Sinkhorn divergences to the data's intrinsic geometry, and (iii) introduce a novel, intrinsic-dimension-based Richardson extrapolation estimator that strongly debiases Wasserstein distance estimation. Numerical experiments demonstrate that our geometry-aware pipeline effectively mitigates the discretization error bottleneck while maintaining computational efficiency.

最优传输内在维数水桶距离采样误差

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。