Research map / Optimization / Nonconvex and smooth optimization
Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate
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.
Shows averaged projected SGD on the non-regularized semi-dual semi-discrete OT problem estimates the OT map at minimax rate O(1/sqrt(n)) for MTW costs (compact) and quadratic cost (non-compact), using a projection set localized by a quantile argument.
Problem
Convergence guarantees for SGD-based solvers of semi-discrete optimal transport, specifically for approximating the OT map from i.i.d. samples of a continuous source measure, including unbounded source supports.
Approach
Identify a compact ℓ∞-ball projection set containing a minimizer of the non-regularized semi-dual, even for unbounded source measures, enabling a restricted strong convexity property and averaged projected SGD with O(1/sqrt(n)) OT map rate, shown minimax optimal.
Key results
- Averaged projected SGD achieves O(1/sqrt(n)) OT map estimation rate, shown minimax optimal via a lower bound over Lipschitz-density measures.
- Projected SGD achieves O(1/n) convergence of the OT cost for MTW costs and quadratic cost in compact settings (per the summary table).
- Numerical experiments show observed rate O(1/sqrt(n)) for the OT map in Examples 1 and 2, and O(1/n^0.45) in Example 3 with b=0.9.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| average the PSGD iterates (ablation) | PSGD · Examples 1 and 2 | OT map convergence rate: \mathcal{O}(1/\sqrt{n}) | Helped |
| use PSGD for semi-discrete OT with MTW costs on compact sources | PSGD · MTW costs, compact source | OT map convergence rate: \mathcal{O}(1/\sqrt{n}) | Helped |
| extend PSGD analysis to quadratic cost with non-compact source | PSGD · Quadratic cost, non-compact source | OT map convergence rate: \mathcal{O}(1/\sqrt{n}) | Helped |
| use PSGD in the general setting without additional regularity assumptions | PSGD · General setting | OT cost convergence rate: \mathcal{O}(1/\sqrt{n}) | Helped |
| use non-averaged rather than averaged iterates (ablation) | PSGD · Examples 1 and 2 | OT map convergence rate: \mathcal{O} \left( 1/n^{b/2} \right) vs. \mathcal{O}(1/\sqrt{n}) | Hurt |
| use b = 0.9 for PSGD on a non-Hölder source | PSGD · Example 3: non-smooth source measure | OT map convergence rate: \mathcal{O}(1/n^{0.45}) | Helped |
| use Projected S-Adam instead of Projected Adam | Projected Adam · Example 1 | empirical performance | Helped |
Surprising findings
- Projected Adam plateaus due to fixed step size, while projected S-Adam with decaying learning rate outperforms it on Example 1 (empirical only, no theory).
Limitations
- Non-compact analysis restricted to quadratic cost; MTW non-compact case not covered.
- Requires Hölder/Poincaré-Wirtinger type assumptions on the source density.
- Dependence on M in the map rate may be conservative (M^2/lambda).
Experimental setup
Datasets: synthetic samples from uniform, heavy-tailed density, and non-smooth densities
Benchmarks: synthetic semi-discrete OT settings (Examples 1-3)
Metrics: convergence rate of OT potential error OT map L2 error
Baselines: Adam Projected Adam S-Adam
Builds on: Genevay et al. stochastic optimization for semi-dual OT Ma-Trudinger-Wang cost conditions Adagrad S-Adam
Closest papers by meaning
- Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport (NeurIPS 2025 · similarity 0.89)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.88)
- Estimation of Stochastic Optimal Transport Maps (NeurIPS 2025 · similarity 0.88)
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.87)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.87)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.86)
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.