# Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 31 Oct 2025.

## Builds on (most cited first, 27 of 27)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Neural Optimal Transport](https://mlsanity.com/paper/2201.12220/) (2022)
- [Large-Scale Optimal Transport and Mapping Estimation](https://mlsanity.com/paper/1711.02283/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Understanding DDPM Latent Codes Through Optimal Transport](https://mlsanity.com/paper/2202.07477/) (2022)
- [Optimal Transport for Diffeomorphic Registration](https://mlsanity.com/paper/1706.05218/) (2017)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Entropic Optimal Transport: Convergence of Potentials](https://mlsanity.com/paper/2104.11720/) (2021)
- [Semi-dual Regularized Optimal Transport](https://mlsanity.com/paper/1811.05527/) (2018)
- [Gradient methods for convex minimization: better rates under weaker conditions](https://mlsanity.com/paper/1303.4645/) (2013)
- [Minimax estimation of discontinuous optimal transport maps: The semi-discrete case](https://mlsanity.com/paper/2301.11302/) (2023)
- [Asymptotics for semi-discrete entropic optimal transport](https://mlsanity.com/paper/2106.11862/) (2021)
- [DPM-OT: A New Diffusion Probabilistic Model Based on Optimal Transport](https://mlsanity.com/paper/2307.11308/) (2023)
- [Convergence of a Newton algorithm for semi-discrete optimal transport](https://mlsanity.com/paper/1603.05579/) (2016)
- [A gradual, semi-discrete approach to generative network training via explicit Wasserstein minimization](https://mlsanity.com/paper/1906.03471/) (2019)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression](https://mlsanity.com/paper/1606.03000/) (2016)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport](https://mlsanity.com/paper/2110.12678/) (2021)
- [Anisotropic power diagrams for polycrystal modelling: efficient generation of curved grains via optimal transport](https://mlsanity.com/paper/2403.03571/) (2024)
- [Projected Stochastic Gradients for Convex Constrained Problems in Hilbert Spaces](https://mlsanity.com/paper/1807.09132/) (2018)

## Abstract (arXiv)

Adding entropic regularization to Optimal Transport (OT) problems has become a standard approach for designing efficient and scalable solvers. However, regularization introduces a bias from the true solution. To mitigate this bias while still benefiting from the acceleration provided by regularization, a natural solver would adaptively decrease the regularization as it approaches the solution. Although some algorithms heuristically implement this idea, their theoretical guarantees and the extent of their acceleration compared to using a fixed regularization remain largely open. In the setting of semi-discrete OT, where the source measure is continuous and the target is discrete, we prove that decreasing the regularization can indeed accelerate convergence. To this end, we introduce DRAG: Decreasing (entropic) Regularization Averaged Gradient, a stochastic gradient descent algorithm where the regularization decreases with the number of optimization steps. We provide a theoretical analysis showing that DRAG benefits from decreasing regularization compared to a fixed scheme, achieving an unbiased O(1/t) sample and iteration complexity for both the OT cost and the potential estimation, and a O(1/√t) rate for the OT map. Our theoretical findings are supported by numerical experiments that validate the effectiveness of DRAG and highlight its practical advantages.