content type paperpublished August 2026
A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport
AuthorsTianyi Lin†, Marco Cuturi, Michael I. Jordan‡
View publication
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 [Vacher et al., 2021]. 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/√k), and a local quadratic convergence rate under standard regularity conditions. We show substantial speedups over SSIPM on both synthetic and real datasets.
† Massachusetts Institute of Technology
‡ University of California, Berkeley
Unbalanced Low-Rank Optimal Transport Solvers
January 22, 2024research area Methods and Algorithmsconference NeurIPS
*Equal Contributors
Two salient limitations have long hindered the relevance of optimal transport methods to machine learning. First, the O(n3)O(n^3)O(n3) computational cost of standard sample-based solvers (when used on batches of nnn samples) is prohibitive. Second, the mass conservation constraint makes OT solvers too rigid in practice: because they must match \textit{all} points from both measures, their output can be heavily influenced by…
Read more
Low-Rank Optimal Transport: Approximation, Statistics and Debiasing
October 11, 2022research area Methods and Algorithmsconference NeurIPS
The matching principles behind optimal transport (OT) play an increasingly important role in machine learning, a trend which can be observed when OT is used to disambiguate datasets in applications (e.g. single-cell genomics) or used to improve more complex methods (e.g. balanced attention in transformers or self-supervised learning). To scale to more challenging problems, there is a growing consensus that OT requires solvers that can operate on…
Read more