Research map / Optimization / Optimizers
Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport
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 for semi-discrete entropic OT whose regularization decreases with the number of iterations, proving unbiased O(1/t) rates for OT cost and potential and O(1/sqrt(t)) for the OT map.
Problem
Solving semi-discrete optimal transport with sample-based access to the continuous source measure while avoiding the bias introduced by fixed entropic regularization; existing solvers do not adapt regularization to sample size.
Approach
Run projected SGD with averaging on the entropic semi-dual while decreasing the regularization epsilon_t = 0.1/t^a over iterations, exploiting a local restricted strong convexity that is independent of epsilon so iterates stay near the moving optimum.
Key results
- Theory: E||Ḡ_t - g*||^2 ≲ 1/t^s with s=min{1,2a+2a alpha'}, giving O(1/t) rates for OT cost and potential when a=1/3^- and b=2/3 and alpha>1/2.
- Map estimation rate O(1/sqrt(t)) in L^p(mu) for the Brenier map.
- Empirically DRAG stays one to two orders of magnitude more accurate than fixed-regularization projected ASGD over the run, and outperforms Adam on Example 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use decreasing entropic regularization and average the iterates | DRAG · Semi-discrete OT | potential estimation error: \mathcal{O}(1/t) | Helped |
| Use decreasing entropic regularization and average the iterates | DRAG · Semi-discrete OT | OT cost estimation error: \mathcal{O}(1/t) | Helped |
| Estimate the OT map using the c-transform of the averaged potential | DRAG · Semi-discrete OT | OT map estimation error: \mathcal{O}(1/\sqrt{t}) | Helped |
| Replace fixed regularization with decreasing regularization | Projected ASGD · Synthetic Example 1 | solution accuracy | Helped |
| Use fixed regularization that is too large | Projected ASGD · Synthetic Example 1 | solution accuracy | Hurt |
| Use fixed regularization that is too small | Projected ASGD · Synthetic Example 1 | convergence | Hurt |
| Use non-regularized rather than decreasing-regularization ASGD | Projected ASGD · Synthetic Examples 1–3 | solution accuracy: one to two orders of magnitude | Hurt |
| Use DRAG instead of ADAM | Generative model · Spiralarms | target coverage | Helped |
| Use DRAG instead of ADAM | Generative model · Swissroll | sample generation quality | No clear effect |
| Use DRAG instead of Online Sinkhorn or Neural OT | Semi-discrete OT solver · Monge-Kantorovich quantiles | quantile estimate bias | Helped |
| Use weighted averaging with \omega =2 instead of uniform averaging (ablation) | DRAG · Synthetic Examples 2 and 3 | potential estimation error: orders of magnitude | Helped |
| Use a mini-batch of size n_b = 16 (ablation) | DRAG · Synthetic Examples 1–3 | estimator error: an order of magnitude | Helped |
Surprising findings
- Non-regularized projected ASGD also eventually converges given enough iterations, though much more slowly than DRAG.
Limitations
- Analysis restricted to quadratic cost and compactly supported source with Hölder density (alpha>1/2 needed for the O(1/t) rate).
- Convergence results depend on constraints on exponents a and b; the map rate is O(1/sqrt(t)) rather than optimal for all alpha.
Experimental setup
Datasets: synthetic uniform source measures on [0,1]^1000 and ball swissroll and spiralarms toy datasets boomerang-shaped discrete target (M=10^5)
Benchmarks: synthetic semi-discrete OT examples 1-3 with known OT cost, map and potential
Metrics: convergence error of OT potential OT cost error OT map error
Baselines: Projected ASGD with fixed regularization Non-regularized projected ASGD Adam Online Sinkhorn Neural OT
Builds on: Entropic optimal transport (Cuturi) Averaged SGD for semi-dual EOT Sinkhorn algorithm Adam
Closest papers by meaning
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.90)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.90)
- A Truncated Newton Method for Optimal Transport (ICLR 2025 · similarity 0.89)
- Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate (NeurIPS 2025 · similarity 0.89)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.89)
- Expectile Regularization for Fast and Accurate Training of Neural Optimal Transport (NeurIPS 2024 · similarity 0.88)
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.