A Proximal-Sinkhorn-Newton Method for Entropic Optimal Transport

Entropic optimal transport (OT) enables efficient distribution alignment via the Sinkhorn method, but suffers from numerical instability and slow convergence under weak entropic regularization. To address these challenges, we first employ an inexact proximal point method to decompose entropic OT into simpler subproblems, yielding numerically stable approximate solutions. We then introduce a dynamic Newton method with global convergence and a locally quadratic convergence rate to refine these solutions. We also establish, to the best of our knowledge, the first complexity result for Newton-type methods. Under relatively heavy entropic regularization, Sinkhorn scaling can serve as an alternative to the Newton method, since numerical instability is handled in the first stage. The resulting Proximal-Sinkhorn-Newton method combines the strengths of proximal, Sinkhorn, and Newton approaches and outperforms baseline methods across a wide range of regularization strengths and accuracy requirements.