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.

核密度估计方法在处理高维度的可行域问题方面比线性规划方法在统计效率上更加高效，但由于使用了大量迭代计算，使得该方法对于样本数量的扩展性较差。为了提高该方法在大样本情况下的可伸缩性，本文提出了一种基于核密度估计的非光滑定点模型，并通过专门的半光滑牛顿方法来高效地求解该模型，证明了该方法具有全局收敛速度 O (1/√k) 和在标准正则性条件下的局部二次收敛速度，并在合成数据集和真实数据集上显示了相对于使用短步内点法的显著加速。