用几何方法解决低秩最优传输的收敛慢、调参难问题。
A Riemannian Approach to Low-Rank Optimal Transport
- 将低秩传输建模为流形,利用黎曼几何优化提升效率。
- 无需迭代即可实现无平衡传输,每轮计算线性复杂度。
- 适用于各类最优传输问题,收敛更快且无需调参。
低秩最优传输缓解了经典求解器的二次复杂度问题,但现有方法依赖一阶镜像下降更新,需精细调参且忽略优化曲率。本文提出统一的黎曼几何框架,将平衡与非平衡的 rank-$r$ 正定因子耦合视为正卦限中的光滑嵌入子流形,并赋予 Fisher-Rao 乘积度量。由此导出可计算的黎曼投影、回映射及海森-向量积。该代价无关框架可无缝扩展至线性 OT、Gromov-Wasserstein (GW)、融合 GW 及其非平衡版本。在平衡情形下,通过高效共轭梯度与迭代 Bregman 更新实现几何分量;在非平衡情形下,操作退化为闭式缩放,彻底消除内层迭代循环。两种情形下每轮迭代复杂度均随数据集规模线性增长,并提供全局最优性的秩充分性验证证书。大量实验表明,本方法的无正则化一阶与二阶求解器在多种问题规模下均实现更快收敛与更优性能,超越现有最先进低秩 OT 方法。
原文摘要 · Abstract (English)
Low-rank optimal transport (OT) mitigates the quadratic scaling of classical solvers, yet existing approaches rely heavily on first-order mirror-descent updates that require careful hyperparameter tuning and ignore the optimization landscape's curvature. To address these limitations, we propose a unified Riemannian geometric framework for low-rank OT, modeling balanced and unbalanced rank-$r$ positive factored couplings as novel smooth embedded submanifolds of the positive orthant. By equipping these manifolds with the Fisher-Rao product metric, we derive tractable formulations for Riemannian projectors, retractions, and Hessian-vector products. Our cost-agnostic framework seamlessly extends to linear OT, Gromov-Wasserstein (GW), fused GW, and their unbalanced counterparts. For balanced OT, our geometric ingredients are computed via efficient conjugate-gradient and iterative Bregman updates. For the unbalanced OT, our operations elegantly reduce to closed-form scalings, completely eliminating inner iterative loops. In both regimes, per-iteration complexity scales linearly with dataset size, and we provide a rank-sufficiency certificate for global optimality verification. Extensive experiments across a range of problem sizes demonstrate that our regularization-free first- and second-order solvers achieve faster convergence and superior performance over existing state-of-the-art low-rank OT solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。