Stochastic Optimization for Large-scale Optimal Transport
Aude Genevay CEREMADE, Univ. Paris-Dauphine INRIA – Mokaplan project-team Marco Cuturi Kyoto University Gabriel Peyré CNRS and CEREMADE, Univ. Paris-Dauphine INRIA – Mokaplan project-team Francis Bach INRIA – Sierra project-team Département d’Informatique de l’ENS (CNRS/ENS/INRIA)
Abstract
Optimal transport (OT) defines a powerful framework to compare probability distributions in a geometrically faithful way. However, the practical impact of OT is still limited because of its computational burden. We propose a new class of stochastic optimization algorithms to cope with large-scale problems routinely encountered in machine learning applications. These methods are able to manipulate arbitrary distributions (either discrete or continuous) by simply requiring to be able to draw samples from them, which is the typical setup in high-dimensional learning problems. This alleviates the need to discretize these densities, while giving access to provably convergent methods that output the correct distance without discretization error. These algorithms rely on two main ideas: (a) the dual OT problem can be re-cast as the maximization of an expectation ; (b) entropic regularization of the primal OT problem results in a smooth dual optimization optimization which can be addressed with algorithms that have a provably faster convergence. We instantiate these ideas in three different setups: (i) when comparing a discrete distribution to another, we show that incremental stochastic o
中文速览
最优传输（Optimal Transport, OT）能以几何上忠实的方式度量两个概率分布之间的差异，但其高昂的计算代价严重限制了实际应用。为此，作者提出了一类基于随机优化的新算法，核心思路是将对偶OT问题改写成期望最大化的形式，从而只需对分布进行采样而无需预先离散化，并借助熵正则化使对偶目标变得光滑以加速收敛。针对离散、半离散（一离散一连续）、纯连续三种场景，分别设计了增量随机梯度算法、平均随机梯度下降，以及基于再生核希尔伯特空间（Reproducing Kernel Hilbert Space, RKHS）展开对偶变量的全新方法；其中连续-连续场景此前完全没有可用的收敛算法，本文是首次给出可证明收敛的解法。实验表明，在大规模问题上这些方法在精度和效率方面均优于或持平于当前最优的Sinkhorn算法及离散化暴力求解基线，从而为机器学习中广泛存在的大规模分布比较任务提供了切实可行的OT计算工具。
原文 arXiv:1605.08527;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1605.08527v1