Research map / Optimization / Optimizers
Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization
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.
Proposes DRAG, a projected averaged SGD on the semi-dual entropic OT with a decreasing entropic regularization, achieving near-minimax O(t^-1) rates for the semi-discrete OT map in the one-sample setting.
Problem
Estimating the optimal transport potential, cost, and Brenier map in semi-discrete OT when samples come from the continuous source and the discrete target is fully known (one-sample setting), where the existing best rates were O(t^-1/2) for the map.
Approach
An SGD scheme on the entropic semi-dual with a sample-count-dependent decreasing regularization eps_t = t^-a, a projection onto a bounded set exploiting local strong convexity that grows as eps decreases, and iterate averaging; this yields O(t^-2b) potential rates and near-minimax map rates.
Key results
- Proves a minimax lower bound of order M/t^2 for the discrete potential and 1/t for the OT map in the one-sample semi-discrete setting.
- DRAG achieves E||g_t - g*||^2 of order t^-2b for b in (1/2,1), approaching the quadratic rate as b tends to 1.
- Numerical experiments match the predicted rates for the potential and map, and DRAG outperforms vanilla SGD and ASGD with fixed regularization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Decrease entropic regularization with sample size and use projected averaged SGD | DRAG · Discrete Kantorovich potential estimation (one-sample) | squared error: O(t−2b), b ∈ (1/2, 1) | Helped |
| Decrease entropic regularization with sample size and use projected averaged SGD | DRAG · OT cost estimation (one-sample) | absolute error: O(t−2b) | Helped |
| Decrease entropic regularization with sample size and use projected averaged SGD | DRAG · Brenier map estimation (one-sample) | Lp error: O(t−b), b ∈ (1/2, 1) | Helped |
| Use the one-sample setting with full information about the discrete target | Semi-discrete OT map estimation · Brenier map estimation | squared L2 error: O(t−1/2) -> O(t−1) | Helped |
| Use mini-batching with nb = 16 (ablation) | DRAG · Example 2 | potential estimation error: an order of magnitude lower | Helped |
| Use weighted averaging of iterates (ablation) | DRAG · Examples 1 and 3 | potential estimation error | Helped |
| Set a = b = 0.75 (ablation) | DRAG · Example 2 | potential estimation error | Mixed |
| Use fixed regularization ε = 10−15/4 ≃ 10−4 instead of decreasing regularization (ablation) | SGD and ASGD · Example 2 | potential estimation error: 10−15/4 ≃ 10−4 | Hurt |
| Use DRAG instead of vanilla SGD or ASGD | Semi-discrete EOT solver · Example 2 | potential estimation error | Helped |
Surprising findings
- The convergence rate of the discrete potential is faster than the typical linear rate of strongly convex stochastic optimization, due to the non-regular Laguerre-cell support structure.
- Error of the non-averaged iterates grows with the number of points M as w_min^-4 in theory, with the authors noting the bound may not be sharp.
Limitations
- Constants grow as b approaches 1, so the near-minimax rate comes with large multiplicative constants.
- Theory restricted to quadratic cost and Hölder-continuous densities on a bounded support; extension to other costs is open.
- Dependence on minimum weight w_min (theory w_min^-4) is not tight relative to the conjectured w_min^-2.
Experimental setup
Metrics: squared error of discrete potential OT cost error L2 error of Brenier map
Baselines: SGD ASGD Pooladian et al. 2023 two-sample minimax rate
Builds on: Bercu and Bigot 2021 SGD for entropic OT Genevay et al. 2016 stochastic semi-dual OT Pooladian et al. 2023 entropic OT map estimation Delalande 2022 entropic potential convergence Polyak-Ruppert averaging
Closest papers by meaning
- Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate (NeurIPS 2025 · similarity 0.86)
- Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport (NeurIPS 2025 · similarity 0.86)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.84)
- Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization (NeurIPS 2025 · similarity 0.84)
- Expectile Regularization for Fast and Accurate Training of Neural Optimal Transport (NeurIPS 2024 · similarity 0.84)
- Optimal Transport with Tempered Exponential Measures (AAAI 2024 · similarity 0.83)
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.