# Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 23 May 2024.

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

- [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)
- [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)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections](https://mlsanity.com/paper/2107.01718/) (2021)
- [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)
- [Minimax estimation of discontinuous optimal transport maps: The semi-discrete case](https://mlsanity.com/paper/2301.11302/) (2023)
- [A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation](https://mlsanity.com/paper/2101.05380/) (2021)
- [Asymptotics for semi-discrete entropic optimal transport](https://mlsanity.com/paper/2106.11862/) (2021)
- [Convergence of a Newton algorithm for semi-discrete optimal transport](https://mlsanity.com/paper/1603.05579/) (2016)
- [On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression](https://mlsanity.com/paper/1606.03000/) (2016)
- [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)

Optimal Transport (OT) based distances are powerful tools for machine learning to compare probability measures and manipulate them using OT maps. In this field, a setting of interest is semi-discrete OT, where the source measure μ is continuous, while the target nu is discrete. Recent works have shown that the minimax rate for the OT map is O(t-1/2) when using t i.i.d. subsamples from each measure (two-sample setting). An open question is whether a better convergence rate can be achieved when the full information of the discrete measure nu is known (one-sample setting). In this work, we answer positively to this question by (i) proving an O(t-1) lower bound rate for the OT map, using the similarity between Laguerre cells estimation and density support estimation, and (ii) proposing a Stochastic Gradient Descent (SGD) algorithm with adaptive entropic regularization and averaging acceleration. To nearly achieve the desired fast rate, characteristic of non-regular parametric problems, we design an entropic regularization scheme decreasing with the number of samples. Another key step in our algorithm consists of using a projection step that permits to leverage the local strong convexity of the regularized OT problem. Our convergence analysis integrates online convex optimization and stochastic gradient techniques, complemented by the specificities of the OT semi-dual. Moreover, while being as computationally and memory efficient as vanilla SGD, our algorithm achieves the unusual fast rates of our theory in numerical experiments.