An Homogeneous Unbalanced Regularized Optimal Transport Model with Applications to Optimal Transport with Boundary

Théo Lacombe

TL;DR

This paper identifies a subtle but significant flaw in standard Unbalanced Regularized Optimal Transport (UROT) models: the introduction of entropic regularization often breaks "homogeneity." This means scaling input data doesn't just scale the results; it fundamentally changes the structure of the optimal transport plan. The authors propose HUROT (Homogeneous Unbalanced Regularized OT), which restores this property through a modified regularization term, ensuring consistent results in complex scenarios like Optimal Transport with Boundary.

What Problem Does This Paper Address?

Optimal Transport (OT) is a framework for comparing probability distributions by finding the most efficient way to "move" mass. In many applications, we use Unbalanced OT (UOT), which allows for mass creation or destruction, and Entropic Regularization, which enables fast computation via the Sinkhorn algorithm.

The authors highlight a requirement called homogeneity: if you scale input measures $\alpha$ and $\beta$ by a factor $\lambda$, the optimal transport plan should scale by $\lambda$ as well. While standard regularized OT is homogeneous in simple balanced cases, it fails when using Total Variation (TV) penalties or in Optimal Transport with Boundary (OTB). In these settings, scaling the mass shifts the structure of the transport plan, leading to inconsistent results across different data scales.

Methods

The authors propose a novel regularization term to replace the standard entropic penalty.

  1. HUROT Model: Instead of the standard $\epsilon KL(\pi | \alpha \otimes \beta)$, they introduce a term $R(\pi | \alpha, \beta)$ that uses renormalized versions of the input measures as references. This ensures the model is 1-homogeneous.
  2. Homogeneous Sinkhorn Algorithm: This model can be solved using a modified Sinkhorn algorithm on renormalized measures, remaining computationally efficient and compatible with existing OT libraries.
  3. Regularized OT with Boundary (ROTB): The authors apply HUROT to OTB, which is particularly sensitive to mass scaling. HUROT provides a consistent way to regularize this spatially varying model where points near the boundary have different costs of disappearing.

Key Insights and Ideas

  • Regularization isn't "free": Entropic regularization can inadvertently destroy fundamental properties like homogeneity in unbalanced settings.
  • The "Slope Break": In TV-UROT, scaling input mass changes the "regime" of the solution, visible as a non-linear relationship in log-log plots.
  • Consistency for OTB: Homogeneity is vital for OTB. Without it, increasing total mass artificially makes boundary transport "cheaper," distorting comparisons between datasets.
Figure 1: Inhomogeneity in TV-UROT. Plot (b) shows the "slope break" in log-log scale, indicating non-homogeneous behavior. Plots (c) and (d) show how the structure of the transport plan changes when scaling the measures.

Key Results

  • Theoretical Proofs: The authors prove HUROT is 1-homogeneous and maintains essential properties like continuity and positivity of the Sinkhorn divergence.
  • Numerical Verification: While standard UROT fails for TV penalties and OTB, HUROT yields perfect linear scaling. In OTB experiments, the HUROT transport plan remains structurally identical under scaling, only rescaling its intensity, whereas standard UROT plans undergo structural shifts.

Limitations and Future Work

  • Loss of Convexity: HUROT is generally not convex with respect to input measures, which may complicate tasks like computing barycenters. Future work will explore convex reparametrizations.
  • Numerical Sensitivity: Even theoretically homogeneous models can behave inhomogeneously in practice due to numerical stopping criteria. Ensuring numerical homogeneity is an ongoing challenge for library developers.

Summary updated

Abstract

This work studies how the introduction of the entropic regularization term in unbalanced Optimal Transport (OT) models may alter their homogeneity with respect to the input measures. We observe that in common settings (including balanced OT and unbalanced OT with Kullback- Leibler divergence to the marginals), although the optimal transport cost itself is not homogeneous, optimal transport plans and the so-called Sinkhorn divergences are indeed homogeneous. However, homogeneity does not hold in more general Unbalanced Regularized Optimal Transport (UROT) models, for instance those using the Total Variation as divergence to the marginals. We propose to modify the entropic regularization term to retrieve an UROT model that is homogeneous while preserving most properties of the standard UROT model. We showcase the importance of using our Homogeneous UROT (HUROT) model when it comes to regularize Optimal Transport with Boundary, a transportation model involving a spatially varying divergence to the marginals for which the standard (inhomogeneous) UROT model would yield inappropriate behavior.
BibTeX
@inproceedings{lacombe2023homogeneous,
  author = {Théo Lacombe},
  title = {{An Homogeneous Unbalanced Regularized Optimal Transport Model with Applications to Optimal Transport with Boundary}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
}
Figure