Research map / Learning theory and algorithms / Optimal transport
On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Greenkhorn analysis with new l_inf bound on dual optimum (instead of shift-property argument) | Greenkhorn algorithm · regularized OT worst-case complexity | iteration/arithmetic complexity in epsilon: from O~(n^2/ε^3) to O~(n^2/ε^2) | Helped |
| Adaptive primal-dual accelerated mirror descent with l_inf-smooth line search and Bregman divergence (1/2n)||.||_2^2 | regularized OT (APDAMD) · MNIST and synthetic images | robustness and speed vs APDAGD | Mixed |
| Greedy row/column updates (Greenkhorn) instead of Sinkhorn block updates | regularized OT on synthetic images · synthetic 20x20 images, distance to transportation polytope vs row/col updates | iterations to reach error | Helped |
Closest papers by meaning
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.88)
- On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods (AAAI 2024 · similarity 0.88)
- Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space (NeurIPS 2026 · similarity 0.87)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.87)
- Optimal Transport with Tempered Exponential Measures (AAAI 2024 · similarity 0.87)
- A Truncated Newton Method for Optimal Transport (ICLR 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.