待翻译：A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport

AI 服务暂时不可用，以下为来源正文，待恢复后补全翻译。

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