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.
- 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.
- 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.
- 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.
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