Approximate Earth Mover's Distance in Truly-Subquadratic Time

Lorenzo Beretta, Aviad Rubinstein

Introduction

The Earth Mover’s Distance (EMD), also known as the Wasserstein-1 distance, is a fundamental metric used to quantify the difference between two probability distributions. Intuitively, if distributions are viewed as piles of dirt, the EMD represents the minimum work required to transform one pile into the shape of the other. While EMD is a powerful tool in machine learning, computer vision, and statistics, its computational cost has long been a significant bottleneck.

For two discrete distributions with $n$ points each, the standard approach requires computing an $n \times n$ cost matrix of all pairwise distances. This immediately imposes a runtime of at least $\Omega(n^2)$. While specialized algorithms exist for low-dimensional Euclidean spaces, general metrics—where distances might represent shortest paths in a graph or arbitrary non-negative costs—have remained stuck at the quadratic barrier for decades. Even popular approximations like the Sinkhorn algorithm scale as $O(n^2)$ in the general case. This paper presents the first algorithm to estimate EMD in "truly subquadratic" time—$O(n^{2-\delta})$—for general metrics by allowing for a small additive error.

The Computational Challenge: The Quadratic Barrier

The primary difficulty in computing EMD lies in the necessity of inspecting the relationship between every pair of points in the two distributions. In a general metric space, there is no inherent structure (like a grid or a low-dimensional coordinate system) that allows an algorithm to skip these pairwise comparisons. Consequently, any exact algorithm or multiplicative approximation has traditionally been forced to pay the $O(n^2)$ cost of building or traversing the cost matrix.

Methodology

The authors bypass the quadratic requirement by combining a classic optimization framework with recent breakthroughs in sublinear-time graph algorithms. Their approach rests on four technical pillars:

1. The Primal-Dual Template

The algorithm adapts the Gabow-Tarjan algorithm, a classic primal-dual method for minimum-weight perfect matching. The algorithm maintains "potentials" for each vertex and iteratively searches for augmenting paths to grow the matching while minimizing costs. Traditionally, finding these paths would require searching the entire graph, but the authors modify this process to work with incomplete information.

2. Sublinear Matching Oracles

Instead of explicitly constructing the $n \times n$ cost matrix, the algorithm utilizes matching oracles. These are sophisticated data structures capable of answering queries about the matching (e.g., "is this vertex matched, and to whom?") in sublinear time. By using these oracles, the algorithm avoids ever fully materializing the cost matrix.

3. Handling Outliers and Robustness

The core technical innovation is a scheme for "Min-Weight Perfect Matching with Outliers." By allowing the algorithm to ignore a tiny fraction ($\gamma$) of the vertices, the authors can employ randomized sublinear-time subroutines. These subroutines, building on recent work in graph theory (Bhattacharya et al., 2023), can identify augmenting paths much faster than traditional deterministic methods. This "robustness" to a few expensive points is what enables the jump from quadratic to subquadratic time.

4. Metric Independence

Remarkably, the algorithm makes no assumptions about the underlying metric. It does not require the triangle inequality to hold, making it applicable to any arbitrary non-negative cost function. This distinguishes it from previous subquadratic attempts that relied on specific geometric properties.

Key Insights

  • Additive Error as a Catalyst: The paper demonstrates that while a multiplicative approximation for general EMD is impossible in subquadratic time, an additive approximation is achievable. By accepting an error of $\pm \gamma$, the algorithm gains the flexibility to use randomized sampling and skip large portions of the cost matrix.
  • EMD as a Robust Problem: A major insight is that EMD becomes computationally "easier" when treated as a robust problem. In a standard Minimum Spanning Tree, changing a single edge can drastically alter the total cost. In EMD with additive error, ignoring a small subset of "expensive" points does not significantly change the overall distance, allowing the algorithm to focus only on the most relevant connections.
  • Oracle-Based Implementation: The work proves that complex primal-dual optimization can be executed entirely through oracles, where each step only requires looking at a fraction of the total possible edges.

Results and Implications

The authors establish several landmark results for the field of algorithmic optimal transport:

  1. Truly Subquadratic Time: The algorithm achieves a runtime of $O(n^{2-\delta})$ for some constant $\delta > 0$ that depends on the desired accuracy $\gamma$.
  2. Optimal Sample Complexity: The algorithm only requires $\tilde{O}(n)$ samples from the distributions, which is nearly optimal for this class of problems.
  3. Breaking the Sinkhorn Limit: This work represents the first theoretical breakthrough to move past the $O(n^2)$ limit of the Sinkhorn algorithm for additive EMD approximation on general metrics.

Limitations and Future Work

While this paper marks a significant theoretical milestone, several challenges remain for practical application. The exponent $\delta$ in the $O(n^{2-\delta})$ runtime is likely very small and heavily dependent on the error tolerance $\gamma$. The paper focuses on the existence of a subquadratic algorithm rather than optimizing the specific constants. Furthermore, the recursive oracle structures are complex; future research is needed to determine if these techniques can be simplified for high-performance software libraries. Finally, because the approximation is additive, the algorithm may be less effective when the true EMD is extremely small, as the error term could overshadow the actual distance.

Summary updated

BibTeX
@inproceedings{beretta2024approximate,
  author = {Lorenzo Beretta and Aviad Rubinstein},
  title = {{Approximate Earth Mover's Distance in Truly-Subquadratic Time}},
  booktitle = {STOC},
  year = {2024},
  doi = {10.1145/3618260.3649629},
}
Figure