提出一种高效稳定的新方法，快速求解高维最优传输问题。
A Truncated Newton Method for Optimal Transport
- 设计截断牛顿法，结合熵正则化提升求解效率。
- 在24组实验中，精度远超现有方法且速度更快。
- 适合需要高精度与高速的高维数据处理场景。
构建现代最优传输（OT）求解器需权衡多项关键需求：GPU并行、高维扩展性、理论收敛保证、精度与运行时间的平衡，以及实际计算中的数值稳定性。针对这些挑战，我们提出一种专用于熵正则化最优传输的截断牛顿算法。不仅证明了无需假设黑塞矩阵利普希茨连续即可实现局部二次收敛，还提供了最大化利用局部高速收敛的实际策略。该基于GPU并行的算法展现出极佳的运行时性能，在24组测试（12个数据集 × 2种代价函数）的墙钟时间实验中，达到高精度的速度远超多数现有方法。算法在超大规模问题上亦表现出色，成功近似求解了规模约n ≈ 10^6的最优传输问题，采用弱熵正则化。
原文摘要 · Abstract (English)
Developing a contemporary optimal transport (OT) solver requires navigating trade-offs among several critical requirements: GPU parallelization, scalability to high-dimensional problems, theoretical convergence guarantees, empirical performance in terms of precision versus runtime, and numerical stability in practice. With these challenges in mind, we introduce a specialized truncated Newton algorithm for entropic-regularized OT. In addition to proving that locally quadratic convergence is possible without assuming a Lipschitz Hessian, we provide strategies to maximally exploit the high rate of local convergence in practice. Our GPU-parallel algorithm exhibits exceptionally favorable runtime performance, achieving high precision orders of magnitude faster than many existing alternatives. This is evidenced by wall-clock time experiments on 24 problem sets (12 datasets $\times$ 2 cost functions). The scalability of the algorithm is showcased on an extremely large OT problem with $n \approx 10^6$, solved approximately under weak entopric regularization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。