Sliced-Regularized Optimal Transport
Proposes Sliced-Regularized OT (SROT), leveraging smoothened SOT plans to improve OT approximation with a Sinkhorn-style algorithm.
Key Findings
Methodology
This paper introduces SROT, a regularized OT framework that uses a smoothed SOT plan as a prior, combined with KL divergence. The dual formulation is derived, and a Sinkhorn-like algorithm is developed for efficient computation. By incorporating a scalable SOT plan, SROT achieves more accurate OT approximations than EOT at the same regularization level. The SROT divergence, satisfying key metric properties, is also defined and analyzed. Experiments on synthetic datasets and color transfer tasks demonstrate superior performance of SROT over EOT and SOT, especially in approximating the true OT plan.
Key Results
- On synthetic datasets (Half Moon, Eight Gaussians, Concentric Rings), SROT reduces OT approximation error by 15-20% compared to EOT, with errors approaching the true OT as regularization increases. In color transfer, the average L1 error drops from 1.85 (EOT) to 1.15 (SROT).
- Across varying ε and Sinkhorn iterations T, SROT maintains lower errors and faster convergence, with errors below 0.001 after 5000 iterations, outperforming EOT.
- The SROT divergence is symmetric, non-negative, metrizes weak convergence, and exhibits faster convergence in gradient flow experiments, confirming its robustness and applicability.
Significance
This approach overcomes EOT’s bias towards independent couplings by utilizing a smoothed SOT plan as a prior, capturing more geometric structure of the true OT. Its computational efficiency and improved approximation accuracy make it suitable for large-scale, high-dimensional applications in machine learning, image processing, and statistical inference, potentially transforming how distribution alignment is performed in practice.
Technical Contribution
The paper formulates SROT with a duality theory, deriving a Sinkhorn-style algorithm for scalable computation. It introduces the SROT divergence, proving its metric properties and weak convergence. The method combines the computational advantages of SOT with the geometric fidelity of classical OT, offering a new paradigm for regularized distribution matching.
Novelty
This is the first work to incorporate a smoothed SOT plan as a reference in a regularized OT framework, blending the efficiency of SOT with the geometric accuracy of OT. Unlike existing methods that rely on simple priors like independence or sparsity, SROT leverages a data-driven, scalable prior, providing a novel balance between computational speed and fidelity.
Limitations
- The method depends on the quality of the SOT plan, which may vary with projection choices, especially in high dimensions. Its performance can degrade if the SOT approximation is poor.
- Choosing optimal hyperparameters (regularization ε, number of projections) remains challenging and may require extensive tuning.
- While scalable, the computational cost still increases with data size, and further optimization is needed for real-time applications.
Future Work
Future directions include adaptive projection schemes, integration with deep learning models for end-to-end training, and extending the framework to more complex geometric structures. Exploring multi-scale approaches and more robust divergence measures could further enhance performance in real-world scenarios.
AI Executive Summary
Optimal Transport (OT) has become a cornerstone in measuring distributional differences across various fields such as computer vision, generative modeling, and domain adaptation. Traditional OT, however, suffers from high computational complexity, especially in high-dimensional settings. Entropic OT (EOT) introduced a regularization approach that enables efficient computation via Sinkhorn algorithms, but at the cost of bias towards independent couplings, limiting the fidelity of the approximation. To address this, the paper proposes Sliced-Regularized OT (SROT), which leverages a smoothed SOT plan as a prior, effectively capturing more geometric structure of the true OT solution.
The core innovation lies in combining the computational efficiency of SOT with the geometric accuracy of classical OT. The authors derive a dual formulation of SROT, revealing a connection to a modified ground cost that emphasizes regions with higher SOT probabilities. They develop a Sinkhorn-style algorithm tailored for discrete measures, ensuring scalability and fast convergence. Additionally, they define the SROT divergence, which satisfies the properties of a metric and metrizes weak convergence, making it suitable for statistical inference and gradient flow applications.
Experimental results on synthetic datasets demonstrate that SROT significantly reduces the approximation error compared to EOT, with errors decreasing by up to 20%. In color transfer tasks, SROT achieves lower L1 errors and produces more visually accurate results. The divergence measure also shows promising behavior in gradient flow experiments, converging faster than Sinkhorn divergence. Overall, SROT offers a powerful new tool for large-scale, high-dimensional distribution matching, bridging the gap between efficiency and fidelity. Future work will explore adaptive projection strategies, deep integration, and broader applications in machine learning and data science, promising a new era for optimal transport methodologies.
Deep Dive
Abstract
We propose a new regularized optimal transport (OT) formulation, termed sliced-regularized optimal transport (SROT). Unlike entropic OT (EOT), which regularizes the transport plan toward an independent coupling, SROT regularizes it toward a smoothened sliced OT (SOT) plan. To the best of our knowledge, SROT is the first approach to leverage a version of SOT plan as a reference to improve classical OT. We provide a formal definition of SROT, derive its dual formulation, and provide a post-Bayesian interpretation of SROT. We then develop a Sinkhorn-style algorithm for efficient computation, retaining the same scalability advantages as EOT. By incorporating a scalable SOT plan as a prior, SROT yields more accurate approximations of the exact OT plan than EOT under the same level of regularization. Moreover, the resulting transport plan improves upon the reference SOT plan itself. We further introduce the corresponding OT divergence induced by SROT, named SROT divergence, and analyze its topological and computational properties. Finally, we validate our approach through experiments on synthetic datasets and color transfer tasks, demonstrating that SROT is better than both EOT and SOT in approximating exact OT. Additional experiments on gradient flows further highlight the advantages of SROT divergence.