Specialized Semismooth Newton Method for Kernel-Based Optimal Transport

Kernel-based Optimal Transport (OT) estimators are statistically more efficient than existing plug-in methods when comparing high-dimensional probability measures. However, because they rely on the Short-step Interior Point Method (SSIPM), they require many iterations, causing computational costs to increase sharply as the sample size $n$ grows.

To address this, a nonsmooth fixed-point model for kernel-based OT problems is proposed. This model can be efficiently solved via a specialized Semismooth Newton (SSN) method that leverages the structural properties of the problem to significantly reduce the computational cost per iteration.

The key achievements of the proposed SSN method are as follows:

• Convergence performance: Achieves a global convergence rate of $O(1/\sqrt{k})$ and local quadratic convergence under standard regularity conditions.
• Speed improvement: Demonstrates significant speed improvements over the existing SSIPM on both synthetic and real-world datasets.