Research map / Learning theory and algorithms / Optimal transport
Safe and Sparse Newton Method for Entropic-Regularized 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 SSNS, a sparsified Newton-type method for the dual of entropic-regularized optimal transport with a provably positive-definite Hessian sparsification, global and quadratic local convergence guarantees, and no Sinkhorn warm start.
Problem
Solving large-scale entropic-regularized optimal transport quickly: Sinkhorn converges sub-linearly, and existing sparsified Newton methods (SNS) lack invertibility guarantees and convergence theory.
Approach
A new adaptive Hessian sparsification (select_small masking of the transport plan with a threshold δ tied to the gradient norm) that provably keeps the sparsified Hessian positive definite and has a controlled operator-norm error, combined with a Levenberg–Marquardt-style shift λ = µ‖g‖ and a trust-region-like acceptance rule, yielding a safe Newton method with global and quadratic local convergen
Key results
- SSNS reaches marginal error tolerance in far fewer iterations than Sinkhorn/BCD, APDAGD and L-BFGS, and shows roughly an order-of-magnitude runtime speedup on MNIST and Fashion-MNIST at eta=0.001 relative to the dense Newton method.
- Vanilla Newton fails numerically at eta=0.001 on the benchmarks (nearly singular Hessian, line search fails), while SSNS converges.
- On synthetic OT with n=m=10000, SSNS shows fast, quadratic-like convergence while BCD converges linearly; the paper proves global convergence and quadratic local convergence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SSNS instead of BCD | ImageNet OT with ℓ1 cost and log10(η)=-2 · ImageNet ℓ1 | Iterations: 217 -> 13 | Helped |
| Use SSNS instead of BCD | ImageNet OT with squared Euclidean cost and log10(η)=-2 · ImageNet squared Euclidean | Time (s): 0.438 -> 2.235 | Hurt |
| Use SSNS instead of BCD | ImageNet OT with squared Euclidean cost and log10(η)=-2.5 · ImageNet squared Euclidean | Time (s): 3.327 -> 0.997 | Helped |
| Reduce regularization η | BCD on ImageNet with ℓ1 cost · ImageNet ℓ1 | Iterations: 217 -> > 500 | Hurt |
| Reduce regularization η | SSNS on ImageNet with ℓ1 cost · ImageNet ℓ1 | Iterations: 13 -> 120 | Hurt |
| Reduce regularization η | SSNS on ImageNet with ℓ1 cost · ImageNet ℓ1 | Time (s): 1.523 -> 0.383; 0.771 | Mixed |
| Use SSNS instead of vanilla Newton | Entropic-regularized OT at η = 0.001 · MNIST, Fashion-MNIST, ImageNet | Run time | Helped |
| Use SSNS instead of vanilla Newton | ImageNet OT at η = 0.001 · ImageNet | Valid results | Helped |
| Use SSNS instead of BCD | Large-scale synthetic OT · Synthetic data, n = m = 1000, 5000, 10000 | Convergence speed | Helped |
Surprising findings
- Vanilla Newton method fails to produce valid results at eta=0.001 because the Hessian is nearly singular, while the shifted sparsified method succeeds.
- For SSNS, runtime can decrease as eta decreases even though iteration counts increase, because the Hessian becomes sparser.
Limitations
- Approach relies on the transport plan being approximately sparse; for some OT problems the Hessian stays dense even after sparsification.
- Runtime is relatively worse than Sinkhorn-type baselines on ImageNet at eta=0.01 because the transport plan is dense.
Experimental setup
Datasets: MNIST Fashion-MNIST ImageNet (Imagenette subset, 10 classes) synthetic exponential-to-normal-mixture distributions
Benchmarks: MNIST OT Fashion-MNIST OT ImageNet feature OT synthetic large-scale OT (n up to 10000)
Metrics: marginal error (log10) run time (seconds) iterations
Baselines: Sinkhorn (BCD) APDAGD Dual L-BFGS globalized Newton with line search SNS
Builds on: Sinkhorn-Newton-Sparse (SNS) regularized Newton method Levenberg-Marquardt Nocedal and Wright trust-region Cauchy point
Closest papers by meaning
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.96)
- Accelerating Sinkhorn algorithm with sparse Newton iterations (ICLR 2024 · similarity 0.92)
- A Truncated Newton Method for Optimal Transport (ICLR 2025 · similarity 0.92)
- 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)
- Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation (NeurIPS 2026 · 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.