A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport
This work addresses a computational bottleneck for researchers and practitioners using optimal transport in high-dimensional settings, offering a more efficient method but is incremental as it builds on existing kernel-based estimators.
The paper tackles the high computational cost of kernel-based optimal transport estimators by proposing a specialized semismooth Newton method, achieving a global convergence rate of O(1/√k) and local quadratic convergence, with substantial speedups over existing methods on synthetic and real datasets.
Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. Recent works suggest that these estimators are more statistically efficient than plug-in (linear programming-based) OT estimators when comparing probability measures in high-dimensions~\citep{Vacher-2021-Dimension}. Unfortunately, that statistical benefit comes at a very steep computational price: because their computation relies on the short-step interior-point method (SSIPM), which comes with a large iteration count in practice, these estimators quickly become intractable w.r.t. sample size $n$. To scale these estimators to larger $n$, we propose a nonsmooth fixed-point model for the kernel-based OT problem, and show that it can be efficiently solved via a specialized semismooth Newton (SSN) method: We show, exploring the problem's structure, that the per-iteration cost of performing one SSN step can be significantly reduced in practice. We prove that our SSN method achieves a global convergence rate of $O(1/\sqrt{k})$, and a local quadratic convergence rate under standard regularity conditions. We show substantial speedups over SSIPM on both synthetic and real datasets.