The paper tackles the computational bottleneck of kernel-based optimal transport (OT) estimators. These estimators provide a functional estimation alternative to plug-in, linear-programming-based OT estimators, and recent work by Vacher et al. (2021) suggests they are more statistically efficient when comparing probability measures in high dimensions. That statistical benefit, however, comes at a steep computational price: their computation relies on the short-step interior-point method (SSIPM), which exhibits large iteration counts in practice and quickly becomes intractable as the sample size n grows.

The authors propose a nonsmooth fixed-point model for the kernel-based OT problem and show it can be solved efficiently with a specialized semismooth Newton (SSN) method. The key practical contribution is exploiting the problem’s structure so that the per-iteration cost of one SSN step is significantly reduced, rather than paying the full linear-algebra cost at every iteration.

Theoretically, the SSN method achieves a global convergence rate of O(1/√k) and a local quadratic convergence rate under standard regularity conditions. Empirically, the authors report substantial speedups over SSIPM on both synthetic and real datasets. The work is a joint effort by Tianyi Lin (MIT), Marco Cuturi, and Michael I. Jordan (UC Berkeley), with equal contributions noted.

The surrounding context frames OT as increasingly central to machine learning, where its matching principles help disambiguate datasets in applications such as single-cell genomics and improve methods like balanced attention in transformers and self-supervised learning. The broader motivation also touches on two long-standing limitations of standard OT solvers—the prohibitive O(n^3) computational cost for batches of n samples and the rigidity imposed by the mass conservation constraint, which forces all points from both measures to be matched.