PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport
This work addresses efficiency and robustness issues in optimal transport for machine learning and optimization applications, representing an incremental improvement over existing methods.
The authors tackled the problem of numerical instability and slow convergence in optimal transport, especially with small regularization parameters, by introducing PINS, which achieved accuracy comparable to exact solutions and demonstrated superior performance in experiments.
Optimal transport (OT) is a critical problem in optimization and machine learning, where accuracy and efficiency are paramount. Although entropic regularization and the Sinkhorn algorithm improve scalability, they frequently encounter numerical instability and slow convergence, especially when the regularization parameter is small. In this work, we introduce Proximal Iterations with Sparse Newton and Sinkhorn methods (PINS) to efficiently compute highly accurate solutions for large-scale OT problems. A reduced computational complexity through overall sparsity and global convergence are guaranteed by rigorous theoretical analysis. Our approach offers three key advantages: it achieves accuracy comparable to exact solutions, progressively accelerates each iteration for greater efficiency, and enhances robustness by reducing sensitivity to regularization parameters. Extensive experiments confirm these advantages, demonstrating superior performance compared to related methods.