The Optimal Transport Bottleneck
In machine learning, comparing probability distributions or histograms—such as the distribution of colors in an image or words in a document—is a fundamental task. While simple metrics like Kullback-Leibler (KL) divergence exist, they ignore the underlying geometry of the space. For example, they treat a "dark red" bin as just as different from "light red" as it is from "bright blue."
Optimal Transport (OT), also known as the Earth Mover’s Distance (EMD), solves this by calculating the minimum "work" required to transform one distribution into another based on a ground metric. However, OT comes with a massive computational price tag. Traditional algorithms like the network simplex scale at roughly $O(d^3 \log d)$, where $d$ is the number of bins. This super-cubic complexity makes OT prohibitively slow for high-dimensional data or large-scale datasets, often taking seconds to compute a single distance on a standard CPU.
The Solution: Entropic Regularization
This seminal paper introduces Sinkhorn Distances, a regularized version of Optimal Transport that transforms a computationally heavy linear programming problem into a fast, parallelizable matrix scaling task.
The author proposes a novel approach using Entropic Regularization:
- The Constraint: Instead of searching the entire set of possible transport plans (the "transport polytope"), the search is restricted to plans with a minimum level of entropy. This effectively "smooths" the transport plan, preventing it from being overly sparse.
- The Math: By adding this entropic penalty, the optimization problem becomes strictly convex. Using Lagrange multipliers, the optimal transport plan $P$ takes the form $P = \text{diag}(u) K \text{diag}(v)$, where $K$ is a kernel matrix derived from the cost matrix ($K = e^{-\lambda M}$).
- The Algorithm: This specific form allows the use of Sinkhorn’s fixed-point iteration. To find the vectors $u$ and $v$, one simply alternates between normalizing the rows and columns of the matrix.
- Parallelism: Unlike the branching "if-then" logic of simplex-like methods, Sinkhorn’s algorithm relies entirely on matrix-vector products. This makes it trivial to implement on GPUs, allowing for the simultaneous computation of distances between one point and an entire family of points.
Key Results: Speed and Accuracy
"Lightspeed" Computation
The transition from a linear program to a matrix scaling problem is the core breakthrough. It shifts the bottleneck from complex combinatorial optimization to linear algebra, which modern hardware is specifically designed to optimize.
As shown in the computational speed benchmarks, Sinkhorn distances on a GPU are approximately 1,000x faster than the standard EMD solver on histograms of dimension $d=2048$. Even on a single CPU, the speedup is significant (roughly 10x to 100x depending on the dimension). The empirical time complexity drops to $O(d^2)$, a major improvement over traditional OT.
Improved Classification Performance
The primary empirical evaluation was conducted on the MNIST digits dataset, treating images as 400-dimensional histograms (20x20 pixels) and using Support Vector Machines (SVMs) for classification.
Remarkably, the regularization does not degrade performance; it improves it. On the MNIST classification task, the Dual-Sinkhorn divergence outperformed all other tested distances, including the classic EMD, Hellinger, and $\chi^2$ distances. From a machine learning perspective, classic OT plans are extremely sparse and can be sensitive to noise. The entropic constraint forces a smoother, more spread-out transport plan, which acts as a beneficial prior for inference tasks.
Limitations and Future Work
While Sinkhorn distances offer a massive leap forward, the paper notes a few practical considerations:
- Numerical Stability: As the regularization parameter $\lambda$ increases (to more closely approximate true, unregularized OT), the entries of the kernel matrix $K = e^{-\lambda M}$ can become so small they are represented as zeros in memory (underflow), leading to numerical instability.
- Parameter Tuning: The entropic weight $\lambda$ is a hyperparameter that must be tuned. While small values often perform better for classification, finding the "optimal" $\lambda$ for a specific task requires cross-validation.
Ultimately, Sinkhorn Distances prove that by slightly relaxing the exactness of Optimal Transport with an entropic penalty, we can unlock orders-of-magnitude speedups and better empirical performance, making geometry-aware metrics viable for modern, large-scale machine learning.
Summary updated