# Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space

arXiv: https://arxiv.org/abs/2511.11359 · HTML: https://mlsanity.com/paper/2511.11359/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2025.

## Built on by (most cited first, 1 of 1)

- [Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory](https://mlsanity.com/paper/2609.33814/) (2026)

## Abstract (arXiv)

We propose Log-Averaged Mirror Prox (LAMP), a linear-space primal-dual method for large-scale optimal transport. LAMP implements primal mirror prox updates by tracking an averaged dual sequence, reducing storage complexity from O(nm) to O(n+m) while preserving dense, GPU-friendly reductions. Consequently, LAMP preserves the last-iterate widetildeO( nmvarepsilon-1) arithmetic complexity of conservatively parameterized primal-dual mirror prox. We further analyze LAMP as a direct optimal transport solver in a more performant parameter regime, providing a last-iterate sub-optimality certificate dependent on infeasibility and an explicit O(1/t) term. Moreover, we give a computable sufficient condition for best-iterate convergence to a saddle-point. Numerical experiments with an optimized CUDA implementation show that LAMP outperforms first-order baselines in several high-accuracy (entropic) optimal transport problems. LAMP is further shown to scale up to problems with n=m=218 marginal supports, which were previously beyond the reach of primal-dual first-order methods.