Research map / Optimization / Nonconvex and smooth optimization
On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods
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.
Shows that Sinkhorn for partial optimal transport (POT) outputs infeasible plans, proposes Round-POT to project onto the feasible set, and derives feasible Sinkhorn, APDAGD and Dual Extrapolation algorithms with improved complexity bounds.
Problem
Partial optimal transport (POT) between unbalanced measures requires exact total transported mass; existing Sinkhorn-based solvers return solutions that violate the mass equality constraint, and efficient first-order POT solvers were lacking.
Approach
A new rounding procedure (Round-POT) for POT that projects an approximate solution onto the feasible POT polytope in O(n^2) time; it enables a feasible Sinkhorn variant, an accelerated primal-dual method (APDAGD) and a dual extrapolation method with area-convex regularizer for POT.
Key results
- Round-POT guarantees a feasible POT plan in O(n^2) time with ||x - x_bar||_1 <= 23 delta.
- Feasible Sinkhorn complexity revised to Õ(n^2 ||C||_max^2 / ε^4) versus Õ(n^2 ||C||_max^2 / ε^2) for infeasible Sinkhorn.
- APDAGD achieves Õ(n^2.5 ||C||_max / ε) and Dual Extrapolation achieves Õ(n^2 ||C||_max / ε), the best known POT complexity; DE is practically slower than APDAGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Round-POT and choose a sufficiently large A instead of the standard POT Sinkhorn rounding | Sinkhorn · POT approximation | computational complexity: \tilde{\mathcal{O}} \left(\frac{n^2 \|\mathbf{C}\|^2_{\max} }{\varepsilon^2} \right) -> \tilde{\mathcal{O}} \left(\frac{ | Hurt |
| Use the original Sinkhorn rounding procedure for POT | Sinkhorn · POT approximation | feasibility | Hurt |
| Use Round-POT to project approximate solutions onto the feasible POT set | POT algorithms · POT approximation | feasibility: 23 \delta | Helped |
| Use APDAGD rather than DE in the tested runtime setup | POT solvers · CIFAR-10 | practical runtime | Helped |
| Use APDAGD rather than Sinkhorn | POT solvers · CIFAR-10 | average per-iteration cost: 0.68 | Helped |
| Use APDAGD's feasible POT plan instead of the pre-revised Sinkhorn plan | Point cloud registration · Point cloud registration | alignment quality | Helped |
| Use a POT plan instead of an OT plan | Point cloud registration · Point cloud registration | alignment quality | Helped |
| Use APDAGD instead of pre-revised Sinkhorn | Color transfer · Color transfer | qualitative match to exact solution | Helped |
| Increase the transported mass parameter α | APDAGD color transfer · Color transfer | color transfer quality | Mixed |
Surprising findings
- Pre-revised Sinkhorn's optimality gap cannot be reduced below the tolerance ε, and its infeasibility can yield a better-looking point cloud registration result than the feasible solution, which the authors attribute to infeasibility.
- Dual Extrapolation performs relatively poorly in practice despite the best theoretical complexity, due to large constants.
Limitations
- Revised Sinkhorn requires a large entropic-related constant A ~ ||C||_max/ε, worsening its complexity to ε^-4.
- Dual Extrapolation has poor practical performance due to large constants despite best asymptotic complexity.
- Experiments are small-scale and the exact POT solution is computed with cvxpy for comparison.
Experimental setup
Datasets: CIFAR-10 Point cloud rabbit (Stanford bunny-style point sets) Color transfer images
Benchmarks: CIFAR-10 image marginals (runtime) color transfer point cloud registration
Metrics: primal optimality gap constraint violation runtime per-iteration cost
Baselines: Sinkhorn for POT (pre-revised) Dual Extrapolation for OT Iterative Bregman projections cvxpy linear program
Builds on: Sinkhorn algorithm Accelerated Primal-Dual Gradient Descent (APDAGD) Dual Extrapolation Round-to-feasible rounding for OT (Altschuler et al.)
Closest papers by meaning
- Screening Sinkhorn Algorithm for Regularized Optimal Transport (NeurIPS 2019 · similarity 0.89)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration (NeurIPS 2017 · similarity 0.89)
- Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm (ICML 2018 · similarity 0.89)
- On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm (ICML 2020 · similarity 0.88)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.87)
- Accelerating Sinkhorn algorithm with sparse Newton iterations (ICLR 2024 · 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.