用正交耦合动力学高效求解最优传输问题
Optimal Transportation by Orthogonal Coupling Dynamics
- 基于条件期望设计投影梯度下降动态
- 计算复杂度优于传统线性规划方法
- 适合需要快速计算传输映射的机器学习场景
许多数值与学习算法依赖于Monge-Kantorovich问题及Wasserstein距离的求解，这些提供了合适的分布度量。虽然自然方法是将其视为无限维线性规划，但该方法因样本量呈多项式增长且内存需求高而限制了计算性能。本文提出一种新框架，基于投影型梯度下降来解决Monge-Kantorovich问题。该动态基于条件期望概念，并利用意见动力学的联系设计高效数值方案。结果表明，该动态能恢复具有优异计算性能的随机映射。结合理论洞察，所提动态为计算最优传输映射和Wasserstein距离开辟了创新路径。
原文摘要 · Abstract (English)
Many numerical and learning algorithms rely on the solution of the Monge-Kantorovich problem and Wasserstein distances, which provide appropriate distributional metrics. While the natural approach is to treat the problem as an infinite-dimensional linear programming, such a methodology limits the computational performance due to the polynomial scaling with respect to the sample size along with intensive memory requirements. We propose a novel alternative framework to address the Monge-Kantorovich problem based on a projection type gradient descent scheme. The dynamics builds on the notion of the conditional expectation, where the connection with the opinion dynamics is leveraged to devise efficient numerical schemes. We demonstrate that the resulting dynamics recovers random maps with favourable computational performance. Along with the theoretical insight, the proposed dynamics paves the way for innovative approaches to construct numerical schemes for computing optimal transport maps as well as Wasserstein distances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。