Research map / Learning theory and algorithms / Optimal transport
A Truncated Newton Method for Optimal Transport
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 a GPU-parallel truncated Newton solver for entropic optimal transport using a discounted Hessian (Bellman-equation view) and adaptive MDOT temperature annealing, achieving fast high-precision Bregman projections.
Problem
Solving entropic-regularized optimal transport to high precision at weak regularization quickly on GPUs, where Sinkhorn-type methods slow down and many second-order or accelerated methods are too costly or CPU-bound.
Approach
Replace the PSD dual Hessian with a rho-discounted, positive-definite surrogate whose Newton system reduces to a single n-variable linear system solved by diagonally preconditioned CG; combine with backtracking line search, asymmetric marginal smoothing, and an adaptive discount-based temperature schedule within MDOT to keep superlinear local convergence.
Key results
- On n=4096 problems, MDOT--TruncatedNewton typically reaches 6-decimal precision in 1-5 seconds on an RTX 2080 Ti and is more than 10x faster than MDOT--PNCG at the highest precision.
- The adaptive temperature schedule matches the best hand-tuned fixed schedule (1.55 s vs 1.56 s in the MNIST ablation).
- Asymmetric marginal smoothing and the adaptive schedule give numerical stability up to 9-decimal precision; the O(n)-memory variant handles n≈10^6 in about 600 MB but takes about 10 hours.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use an adaptive temperature schedule instead of fixed q=2^{1/2} (ablation) | MDOT–TruncatedNewton · Upsampled MNIST (n=4096), L1 distance | seconds: 1.56 -> 1.55 | No clear effect |
| use an adaptive temperature schedule instead of fixed q=2^{1/8} (ablation) | MDOT–TruncatedNewton · Upsampled MNIST (n=4096), L1 distance | seconds: 2.84 -> 1.55 | Helped |
| use an adaptive temperature schedule instead of fixed q=2^{1/4} (ablation) | MDOT–TruncatedNewton · Upsampled MNIST (n=4096), L1 distance | seconds: 1.99 -> 1.55 | Helped |
| use an adaptive temperature schedule instead of fixed q=2^1 (ablation) | MDOT–TruncatedNewton · Upsampled MNIST (n=4096), L1 distance | seconds: 1.76 -> 1.55 | Helped |
| use an adaptive temperature schedule instead of fixed q=2^2 (ablation) | MDOT–TruncatedNewton · Upsampled MNIST (n=4096), L1 distance | seconds: 2.41 -> 1.55 | Helped |
| use asymmetric marginal smoothing with more smoothing budget for rows than columns (ablation) | MDOT–TruncatedNewton · OT problems | median performance and numerical stability | Helped |
| use MDOT–TruncatedNewton instead of the best alternative, MDOT–PNCG | OT solvers · n=4096 OT problems at highest precision | runtime: more than 10× faster | Helped |
Surprising findings
- Sinkhorn with aggressive tuning remains competitive with many recent OT solvers in practice.
- Hessian discounting can be more aggressive than the worst-case spectral-gap analysis suggests.
Limitations
- No global convergence rate; only local superlinear convergence is proven.
- The O(n) memory variant takes about 10 hours for n≈10^6.
- Evaluation is limited to MNIST and color transfer images at n=4096 on one GPU.
Experimental setup
Datasets: Upsampled MNIST color transfer images (20 DALL-E 2 images)
Benchmarks: Upsampled MNIST (n=4096) color transfer (n=4096) high-resolution color transfer (n≈10^6)
Metrics: wall-clock time optimality gap number of O(n^2) operations
Baselines: Sinkhorn (MDOT--Sinkhorn) Mirror Sinkhorn (MSK) APDAGD Mirror Prox Sherman Optimized AAM MDOT--PNCG
Builds on: MDOT PNCG Sinkhorn-Knopp Greenkhorn
Closest papers by meaning
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.92)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.90)
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.90)
- Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport (NeurIPS 2025 · similarity 0.89)
- Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space (NeurIPS 2026 · similarity 0.88)
- A Provably Convergent and Practical Algorithm for Gromov–Wasserstein Optimal Transport (NeurIPS 2026 · similarity 0.87)
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.