Research map / Learning theory and algorithms / Optimal transport
Progressive Entropic Optimal Transport Solvers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Progressive Entropic OT (ProgOT), a time-discretized dynamic OT scheme that chains Sinkhorn/entropic-map steps along an estimated McCann interpolation path with scheduled epsilon, giving coupling and map solvers that are more robust to epsilon and scale to large data.
Problem
Entropic OT solvers are highly sensitive to the entropic regularization strength epsilon, which trades off speed, statistical bias and coupling blur, making them hard to tune for both coupling and map estimation at large scale.
Approach
Decompose mass displacement into a sequence of entropic OT subproblems along an estimated McCann interpolation path (time discretization of dynamic OT), where each step uses Sinkhorn with a scheduled epsilon and the source point cloud is progressively moved toward the target, making the final step easier and more self-correcting.
Key results
- On sci-Plex map estimation, ProgOT ranks first across 5 drugs by Sinkhorn divergence, beating EOT, debiased EOT, Monge Gap and ICNN (e.g., Belinostat 64-dim 8.8 vs 9.6 for EOT).
- On GMM benchmark with d=128, ProgOT MSE 0.099 vs 0.12 for EOT and 0.36 for Monge Gap.
- As a coupling solver on 4i and sci-Plex, ProgOT returns couplings with comparable cost and entropy using a fraction of Sinkhorn iterations; on CIFAR10 blur matching at n=60,000, it scales to roughly 15 minutes on 8 A100 GPUs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use progressive EOT instead of direct EOT | EOT map estimation · sci-Plex Belinostat, PCA 64 | Sinkhorn divergence: 9.6$\pm$0.1 -> \textbf{8.8}$\pm$0.1 | Helped |
| Use progressive EOT instead of direct EOT | EOT map estimation · sci-Plex Givinostat, PCA 256 | Sinkhorn divergence: 24.7$\pm$0.9 -> \textbf{21.9}$\pm$0.3 | Helped |
| Use progressive EOT instead of direct EOT | EOT map estimation · GMM, d=128 | MSE: 0.12$\pm$0.01 -> \textbf{0.099}$\pm$0.009 | Helped |
| Use progressive EOT instead of ICNN | Map estimation · GMM, d=256 | MSE: 0.117$\pm$0.005 vs \textbf{0.12}$\pm$0.01 | Mixed |
| Vary the step-length schedule (accelerated, constant-speed, or decelerated) (ablation) | Progressive EOT · Synthetic data and sci-Plex | Sinkhorn divergence | No clear effect |
| Schedule regularization parameters instead of using default values at every step (ablation) | Progressive EOT · Synthetic data, d=64 | Sinkhorn divergence | Helped |
| Use the library default epsilon rather than cross-validating epsilon (ablation) | EOT map estimator · GMM, d=128 and d=256 | MSE: 0.12$\pm$0.01 -> 0.250$\pm$0.023; 0.16$\pm$0.02 -> 0.276$\pm$0.006 | Hurt |
Surprising findings
- Performance is reported as insensitive to the choice of step schedule alpha_k, and the method is hypothesized to be self-correcting against poor epsilon choices.
- Untuned EOT with the default OTT-JAX epsilon performs much worse (MSE 0.250 vs 0.099 on GMM d=128), showing epsilon sensitivity of standard EOT.
Limitations
- Theoretical consistency guarantee requires specific epsilon and step schedules (rates) that do not directly prescribe practical choices; practical schedules are heuristic.
- Consistency theorem is for squared-Euclidean cost with compact convex support and regularity assumptions (A1)-(A3).
- Coupling experiments only tested on a few datasets and cost functions; on some drugs EOT is slightly better (e.g., Belinostat 16-dim).
Experimental setup
Datasets: sci-Plex single-cell RNA-seq 4i multiplex melanoma cell data Gaussian mixture synthetic data CIFAR10 (grayscale)
Benchmarks: sci-Plex 4i GMM synthetic benchmark CIFAR10 blur matching
Metrics: Sinkhorn divergence MSE to ground-truth map transport cost entropy marginal violation number of Sinkhorn iterations trace of coupling KL divergence from identity coupling
Baselines: Entropic OT (Sinkhorn) Debiased EOT Monge Gap ICNN Untuned EOT
Builds on: Sinkhorn algorithm McCann interpolation entropic optimal transport Monge Gap OTT-JAX
Closest papers by meaning
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.90)
- Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport (NeurIPS 2025 · similarity 0.90)
- Energy-guided Entropic Neural Optimal Transport (ICLR 2024 · similarity 0.90)
- A Truncated Newton Method for Optimal Transport (ICLR 2025 · similarity 0.90)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.89)
- Sparsistency for inverse optimal transport (ICLR 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.