Scalable Simulation-free Entropic Unbalanced Optimal Transport

Jaemoo Choi, Jaewoong ChoiSubmission to ICLR 2025 · Rejected

TL;DR

This paper introduces Simulation-Free Entropic Semi-Unbalanced Optimal Transport (SF-ESUOT), a framework that scales dynamic entropic optimal transport to high-dimensional data without requiring diffusion pretraining. By pairing a stochastic optimal control formulation with the bridge "reciprocal property," the method achieves simulation-free training and single-step ($NFE=1$) generation, reaching competitive FID scores on CIFAR-10 and outperforming existing methods on image-to-image translation.

What Problem Does This Paper Address?

The Schrödinger Bridge (SB) problem—the dynamic equivalent of Entropic Optimal Transport (EOT)—finds a finite-time diffusion process that smoothly transitions a source distribution (like Gaussian noise) to a target distribution (like real images) while minimizing transport cost and entropy.

Despite their theoretical elegance, existing continuous SB methods suffer from two major bottlenecks:

  1. Severe computational burden: Existing formulations parameterize the drift vector field and rely on numerical simulation (solving SDEs/ODEs) during both training and inference, requiring tens to hundreds of steps ($NFE \ge 100$) and weeks of compute.
  2. Scalability and convergence issues: When mapping between distant, high-dimensional distributions (e.g., standard normal noise to complex images), standard SB models diverge unless initialized from a pretrained diffusion model. Furthermore, rigid marginal constraints make standard EOT sensitive to outliers and dataset imbalances.

Methods

The authors address these challenges by reformulating EOT as Entropic Semi-Unbalanced Optimal Transport (ESUOT) and deriving a simulation-free solver:

  • Semi-Unbalanced Formulation: Instead of forcing exact marginal matching on the target, ESUOT relaxes the target constraint using an $f$-divergence penalty ($D_\Psi$). This adds stability and robustness to outliers while retaining EOT as a special case.
  • Stochastic Optimal Control (SOC) & Dual Formulation: The authors derive the dynamical dual of ESUOT, proving that the inner control problem corresponds to a Hamilton-Jacobi-Bellman (HJB) PDE for a time-dependent value function $v_\phi(t, x)$.
  • Decoupled Architecture with the Reciprocal Property: Instead of parameterizing a dynamic drift field, SF-ESUOT parameterizes:
  • A static generator $T_\theta(x, z)$ mapping source samples directly to target predictions $\hat{y}$.
  • A time-dependent value potential $v_\phi(t, x)$.
  • Simulation-Free Training: By leveraging the reciprocal property of Schrödinger bridges, intermediate states $x_t$ can be sampled in closed form conditioned on endpoints $x$ and $\hat{y}$: $$x_t = (1-t)x + t\hat{y} + \sigma\sqrt{t(1-t)}\,\eta, \quad \eta \sim \mathcal{N}(0, I)$$ The potential $v_\phi$ is trained using a Physics-Informed Neural Network (PINN)-style residual loss on the HJB equation, while $T_\theta$ is updated against the HJB condition.

Datasets

  • Synthetic Benchmarks:
  • 2D toy tasks: Gaussian to 8-Gaussian ($G \to 8G$), Moon to Spiral ($M \to S$), and a 1D synthetic mixture with 2% outlier contamination.
  • 50-dimensional Gaussian-to-Gaussian transport benchmark with known analytical solutions.
  • Image Datasets:
  • CIFAR-10 ($32 \times 32$): Evaluated for scratch generative modeling.
  • CelebA ($64 \times 64$): Male $\to$ Female unpaired translation.
  • AFHQ ($64 \times 64$): Wild $\to$ Cat unpaired translation.
  • No new benchmarks were introduced.

Key Insights and Ideas

  • Unbalancedness aids optimization: Formally, semi-unbalanced OT allows target distribution errors. Counterintuitively, relaxing the marginal constraint with a soft penalty (e.g., Softplus or KL divergence) actually produced better distribution matching (lower FID) on CIFAR-10 than strict EOT, acting as a regularizer during adversarial/dual training.
  • Closed-form intermediate bridges bypass simulation: Traditional SB algorithms require costly SDE trajectory rollouts to acquire intermediate samples. Because optimal diffusion bridges condition into standard Gaussians given endpoints $(x, y)$, intermediate states can be generated instantaneously.
  • One-step ($NFE=1$) evaluation: Because the generator $T_\theta$ directly predicts the target endpoint $y$, inference requires only a single forward pass without numerical ODE/SDE integration.

Key Results

  • CIFAR-10 Generative Modeling:
  • SF-ESUOT achieved FID 3.02 with $NFE = 1$ without pretraining, matching the state-of-the-art Schrödinger bridge model (IPF: FID 3.01, $NFE = 200$) that required pretraining.
  • Standard scratch SB baselines (IPF, IMF, WLF) completely failed to converge ($\text{FID} \ge 100$).
  • Reduced training wall-clock time from over 10 days down to approximately 4 days on 2 $\times$ RTX 3090Ti GPUs.
  • Image-to-Image Translation:
  • CelebA (Male $\to$ Female): Achieved an FID of 8.44, outperforming Neural Optimal Transport (11.96) and CycleGAN (12.94).
  • AFHQ (Wild $\to$ Cat): Achieved an FID of 14.59, outperforming Diffusion Schrödinger Bridge Matching (DSBM $\ge 25$).
  • Outlier Robustness: On 1D toy data with 2% contamination, SF-ESUOT successfully ignored out-of-distribution modes, whereas standard EOT overfitted to the outlier mass.

Limitations and Future Work

  • Approximation precision vs. exact coupling: On the 50D Gaussian benchmark, SF-ESUOT showed slightly higher relative errors in mean, variance, and covariance ($\sim 3-4\%$) compared to simulation-heavy methods. The authors attribute this to the optimization difficulty of PINN-like residual objectives.
  • Resolution constraints: Experiments were restricted to $32 \times 32$ and $64 \times 64$ resolutions; testing on higher-resolution datasets (e.g., CelebA-HQ $256 \times 256$) was omitted due to computational constraints.
  • Future Directions: Developing improved optimization techniques for the HJB path constraint to enhance coupling fidelity without losing simulation-free efficiency.

Summary updated

Abstract

The Optimal Transport (OT) problem investigates a transport map that connects two distributions while minimizing a given cost function. Finding such a transport map has diverse applications in machine learning, such as generative modeling and image-to-image translation. In this paper, we introduce a scalable and simulation-free approach for solving the Entropic Unbalanced Optimal Transport (EUOT) problem. We derive the dynamical form of this EUOT problem, which is a generalization of the Schrödinger bridges (SB) problem. Based on this, we derive dual formulation and optimality conditions of the EUOT problem from the stochastic optimal control interpretation. By leveraging these properties, we propose a simulation-free algorithm to solve EUOT, called Simulation-free EUOT (SF-EUOT). While existing SB models require expensive simulation costs during training and evaluation, our model achieves simulation-free training and one-step generation by utilizing the reciprocal property. Our model demonstrates significantly improved scalability in generative modeling and image-to-image translation tasks compared to previous SB methods.
BibTeX
@misc{choi2024scalable,
  author = {Jaemoo Choi and Jaewoong Choi},
  title = {{Scalable Simulation-free Entropic Unbalanced Optimal Transport}},
  year = {2024},
  eprint = {2410.02656},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.02656},
}

Loading related content...

Figure