Linear Time Sinkhorn Divergences using Positive Features

Meyer Scetbon, Marco Cuturi

Introduction

Optimal Transport (OT) is a powerful mathematical framework for comparing probability distributions, making it highly useful for tasks involving point clouds, images, and generative modeling. However, its widespread adoption has historically been bottlenecked by computational cost. While the introduction of the "Sinkhorn algorithm" (which uses entropic regularization) sped things up significantly, it still requires $O(n^2)$ operations per iteration, where $n$ is the number of data points.

When $n$ scales to hundreds of thousands or millions, this quadratic complexity becomes a prohibitive brick wall. Previous attempts to bypass this limitation relied on "low-rank" approximations of the kernel matrix, such as the Nyström method. Unfortunately, these approximations often fail in practice because the Sinkhorn algorithm requires the kernel matrix to have strictly positive entries to converge reliably. Furthermore, these data-dependent approximations are often not fully differentiable, making them difficult to integrate as loss functions in deep learning architectures like Generative Adversarial Networks (GANs).

This paper introduces a novel method to compute Sinkhorn divergences in linear time. By cleverly designing cost functions based on "positive features," the authors reduce the computational complexity from $O(n^2)$ to $O(nr)$, where $r$ is a small number of features, making OT feasible for massive datasets.

Methods: A Bottom-Up Approach to Kernel Design

Instead of starting with a standard cost function (like Euclidean distance) and struggling to approximate it, the authors propose a "bottom-up" approach. They define a cost function $c(x, y)$ that is inherently guaranteed to result in a low-rank, strictly positive kernel.

Standard Sinkhorn Iterations
  1. Positive Feature Maps: The cost is defined as $c(x, y) = -\epsilon \log \langle \phi(x), \phi(y) \rangle$, where $\phi$ is a map that projects data into the positive orthant $\mathbb{R}^r_+$.
  2. Kernel Factorization: This specific formulation ensures that the Sinkhorn kernel, $\mathbf{K} = \exp(-C/\epsilon)$, can be factored exactly into a simple dot product of feature matrices: $\mathbf{K} = \Phi^T \Psi$.
  3. Linear Time Iterations: As seen in the standard Sinkhorn loop above, the algorithm relies heavily on matrix-vector products ($\mathbf{K}v$ and $\mathbf{K}^Tu$). Because $\mathbf{K}$ is now factorized, these products can be computed sequentially as $\Phi^T (\Psi v)$. This associative trick shifts the computational complexity from $O(n^2)$ to $O(nr)$. Since $r \ll n$, the time required scales linearly with the number of samples.
  4. Approximating Standard Costs: The authors prove that common cost functions, such as squared Euclidean distance, can be effectively approximated using these positive random features (specifically via a modified Gaussian kernel).
  5. Differentiability: Crucially for modern machine learning, the authors provide explicit formulas for the gradients of this "Linear Sinkhorn" divergence, allowing it to be used seamlessly as a loss function during backpropagation.

Key Insights

  • Kernel-First Design: The most elegant insight of the paper is realizing that selecting the right kernel—one built inherently from positive features—yields an $O(n)$ speedup "for free" without sacrificing the strict convergence guarantees of the Sinkhorn algorithm.
  • Positivity is Non-Negotiable: Standard low-rank methods can produce negative values in the kernel, which breaks Sinkhorn iterations. Mapping features strictly to the positive orthant ensures algorithmic stability.
  • End-to-End Differentiability: Unlike previous approximations that are difficult to differentiate through, this feature-based approach uses a fixed functional form, making it perfectly suited for adversarial training.

Key Results

The paper evaluates the method on synthetic data (2D normal distributions and uniform distributions on a 3D sphere) to benchmark accuracy versus speed, as well as on image datasets (CIFAR-10 and CelebA) for generative modeling.

Performance Comparison: Deviation vs. Time
  • Speedup and Stability: As shown in the performance plots above, the proposed Random Features (RF) method achieves order-of-magnitude speedups over the standard Sinkhorn (Sink) algorithm. More importantly, it is significantly more stable than Nyström (Nys) approximations. In large-scale experiments (e.g., 40,000 samples), the RF method consistently converged with high accuracy, particularly at lower regularization levels where Nyström frequently failed.
  • GAN Training: The authors successfully trained an OT-GAN on CIFAR-10 and CelebA. Because the computation is linear, they were able to use vastly larger mini-batches (up to 7,000 samples). This led to much better approximations of the true data distribution and higher-quality generated images.

Limitations and Future Work

While highly effective, the method's approximation accuracy depends on the number of random features $r$. For extremely high-dimensional data, a large $r$ might still be required to maintain precision, which could offset some performance gains. Additionally, this technique relies on the specific structure of entropic regularization and does not directly apply to "exact" unregularized Optimal Transport.

For future work, the authors suggest that instead of using random features to approximate Euclidean distances, the feature map $\phi$ could be learned directly by a neural network. This could allow models to discover task-specific, optimal cost functions entirely end-to-end.

Summary updated

Abstract

Although Sinkhorn divergences are now routinely used in data sciences to compare probability distributions, the computational effort required to compute them remains expensive, growing in general quadratically in the size $n$ of the support of these distributions. Indeed, solving optimal transport (OT) with an entropic regularization requires computing a $n\times n$ kernel matrix (the neg-exponential of a $n\times n$ pairwise ground cost matrix) that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-\log\dotp{\varphi(x)}{\varphi(y)}$ where $\varphi$ is a map from the ground space onto the positive orthant $\RR^r_+$, with $r\ll n$. This choice yields, equivalently, a kernel $k(x,y)=\dotp{\varphi(x)}{\varphi(y)}$, and ensures that the cost of Sinkhorn iterations scales as $O(nr)$. We show that usual cost functions can be approximated using this form. Additionaly, we take advantage of the fact that our approach yields approximation that remain fully differentiable with respect to input distributions, as opposed to previously proposed adaptive low-rank approximations of the kernel matrix, to train a faster variant of OT-GAN~\cite{salimans2018improving}.
BibTeX
@inproceedings{scetbon2020linear,
  author = {Meyer Scetbon and Marco Cuturi},
  title = {{Linear Time Sinkhorn Divergences using Positive Features}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=AXQexZ2JE7},
}
Figure