Research map / Learning theory and algorithms / Optimal transport
Accelerating Sinkhorn algorithm with sparse Newton iterations
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 Sinkhorn-Newton-Sparse (SNS), which runs a few Sinkhorn steps then switches to a Newton method whose Hessian of the Lyapunov potential is thresholded to a sparse matrix, giving O(n^2) per-iteration cost and far fewer iterations for entropic OT.
Problem
Entropic optimal transport via the Sinkhorn algorithm converges slowly (poly-like in practice) in iteration count, and exact Newton steps cost O(n^3) per iteration.
Approach
View Sinkhorn as alternating maximization of a concave Lyapunov potential; the Hessian of this potential is approximately sparse near the solution, so a thresholded sparse Hessian makes Newton steps O(n^2) per iteration while retaining fast (near super-exponential) convergence, with theoretical sparsity bounds.
Key results
- On random assignment (n=500), SNS reaches machine accuracy in 29 iterations (0.34 s) versus 56199 iterations (233.36 s) for Sinkhorn.
- On MNIST L2 cost, SNS total 53 iterations (2.33 s) versus Sinkhorn 2041 iterations (18.84 s).
- On MNIST L1 cost (non-unique solutions), SNS total 777 iterations (12.22 s) versus Sinkhorn 5748 iterations (45.75 s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SNS instead of Sinkhorn | Entropic random assignment · Random assignment | Time (s): 233.36 -> 0.34 | Helped |
| Use SNS instead of Sinkhorn | Entropic random assignment · Random assignment | Iterations: 56199 -> 29 | Helped |
| Use SNS instead of Sinkhorn | MNIST L2 optimal transport · MNIST L2 | Time (s): 18.84 -> 2.33 | Helped |
| Use SNS instead of Sinkhorn | MNIST L2 optimal transport · MNIST L2 | Iterations: 2041 -> 53 | Helped |
| Use SNS instead of Sinkhorn | MNIST L1 optimal transport · MNIST L1 | Time (s): 45.75 -> 12.22 | Helped |
| Use SNS instead of Sinkhorn | MNIST L1 optimal transport · MNIST L1 | Iterations: 5748 -> 777 | Helped |
| Replace sparse Hessian approximation with the full Hessian (remove sparsification) (ablation) | SNS · Random assignment, n=2000, Newton stage | Time per iteration (s): 0.30 -> 11.86 | Hurt |
| Replace sparse Hessian approximation with BFGS or L-BFGS (ablation) | SNS · MNIST L1 and L2 | Runtime efficiency | Hurt |
| Replace sparse Hessian approximation with BFGS or L-BFGS (ablation) | SNS · Entropic random linear assignment | Improvement over Sinkhorn | No clear effect |
| Use SNS instead of Sinkhorn | MNIST L1 optimal transport across tested entropy settings · MNIST L1, η=28 to η=308 | Time (s): 1.96 -> 1.45; 9.63 -> 5.32; 14.53 -> 5.41; 15.56 -> 6.10; 17.81 -> 7.78; 19.76 -> 8.08 | Helped |
| Use SNS instead of Sinkhorn | MNIST L2 optimal transport across tested entropy settings · MNIST L2, η=576 to η=6336 | Time (s): 9.95 -> 3.40; 32.92 -> 5.10; 62.96 -> 7.08; 108.24 -> 9.70; 166.97 -> 12.83; 248.43 -> 22.30 | Helped |
Surprising findings
- Quasi-Newton methods (BFGS, L-BFGS) gave little improvement over Sinkhorn and were slower on MNIST experiments.
- Theory suggests sparsity of O(1/sqrt(n)) for the optimal face under a specific non-uniqueness cost condition, connecting to extremal combinatorics.
Limitations
- Sparsity theory is proven mainly for unique-solution cases; non-unique cases rely on empirical tuning of target sparsity.
- Super-exponential convergence is observed empirically but not proven.
- Hyperparameters (N1, lambda, eta) are chosen per experiment and the switch point is heuristic.
Experimental setup
Datasets: MNIST random synthetic cost matrices (uniform costs)
Benchmarks: random entropic linear assignment (n=500) MNIST optimal transport with L2 and L1 costs
Metrics: runtime (s) iteration count convergence to machine accuracy
Baselines: Sinkhorn algorithm Sinkhorn-Newton BFGS L-BFGS
Builds on: Sinkhorn algorithm Sinkhorn-Newton algorithm variational view of Sinkhorn as alternating maximization
Closest papers by meaning
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.92)
- Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance (NeurIPS 2018 · similarity 0.91)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.89)
- Linear convergence of Sinkhorn's algorithm for generalized static Schrödinger bridge (ICML 2025 · similarity 0.87)
- On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods (AAAI 2024 · similarity 0.87)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.86)
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.