Research map / Learning theory and algorithms / Optimal transport
The Sparse-Plus-Low-Rank Quasi-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 SPLR, a quasi-Newton method for dual entropic-regularized OT that adds a rank-two BFGS-style low-rank correction to a sparsified Hessian, with eigenvalue theory for Hessian sparsification and global linear convergence.
Problem
Solving entropic-regularized optimal transport quickly: Sinkhorn is slow for small regularization, and existing sparse Newton methods (SNS, SSNS) perform poorly when the transport plan/Hessian is dense.
Approach
Combine a flexible sparsified Hessian (with theoretically justified eigenvalue/condition-number properties and a density-adaptive scheme that always keeps one row and column) with a rank-two BFGS-style low-rank correction and a diagonal shift, yielding a sparse-plus-low-rank quasi-Newton approximation.
Key results
- Theory: sparsified Hessian preserves positive definiteness and has λmax(HΩ) ≤ λmax(H), λmin(HΩ) ≥ λmin(H) under a weak positivity assumption (Corollary 3.4).
- Algorithm 1 is globally convergent (gradient norm → 0) with linear convergence rate of f(x_{k+1})−f* ≤ r[f(x_k)−f*] (Theorems 5.1–5.3).
- SPLR is fastest or among the fastest solvers across synthetic, MNIST, Fashion-MNIST, and ImageNet experiments; it outperforms SSNS notably when the Hessian is dense (Synthetic I, large η on ImageNet).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the low-rank term to the sparse approximate Hessian (ablation) | Sparse Newton on Synthetic I and Synthetic II · Synthetic I and Synthetic II, n = m = 1000, 5000, and 10000 | gradient norm convergence | Helped |
| combine sparse Hessian approximation with a low-rank correction | entropic-regularized OT solvers · Synthetic I | run time to reduce gradient norm | Helped |
| combine sparse Hessian approximation with a low-rank correction | entropic-regularized OT solvers · Synthetic II | run time to reduce gradient norm | Helped |
| add the low-rank term to sparse Newton | entropic-regularized OT solvers · MNIST and Fashion-MNIST image pairs | gradient norm convergence | Helped |
| add the low-rank term to sparse Newton | entropic-regularized OT solvers · ImageNet Tench vs Cassette player, η = 0.01 | gradient norm convergence | Helped |
| increase the regularization parameter from η = 0.001 to η = 0.01 | SSNS · ImageNet Tench vs Cassette player | gradient norm convergence | Hurt |
| use a purely sparsification-based Hessian approximation instead of SPLR (ablation) | SPLR · Synthetic I and Synthetic II | gradient norm convergence | Hurt |
Surprising findings
- Adding the low-rank term gives a clear speedup even on sparse-friendly problems, and SSNS performs poorly on Synthetic I because the Hessian there is dense.
Limitations
- Theoretical linear convergence rate only; experiments suggest faster behavior but no proven superlinear rate.
- Convergence analysis assumes eigenvalue bounds on the Hessian over a closed set D.
- Experiments limited to moderate sizes (n up to 10000) and a single regularization setting in the main text.
Experimental setup
Datasets: MNIST Fashion-MNIST ImageNet
Benchmarks: synthetic OT problems (Synthetic I and II) MNIST OT Fashion-MNIST OT ImageNet class OT
Metrics: log10 gradient norm vs iterations log10 gradient norm vs run time
Baselines: Sinkhorn (BCD) APDAGD L-BFGS-Dual Newton SSNS
Builds on: SNS (sparse Newton Sinkhorn) SSNS (safe sparse Newton) BFGS Sinkhorn algorithm
Closest papers by meaning
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.96)
- A Truncated Newton Method for Optimal Transport (ICLR 2025 · similarity 0.90)
- Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport (NeurIPS 2025 · similarity 0.90)
- Accelerating Sinkhorn algorithm with sparse Newton iterations (ICLR 2024 · similarity 0.89)
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.89)
- Optimal Transport with Tempered Exponential Measures (AAAI 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.