An efficient algorithm for entropic optimal transport under martingale-type constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915461186191360 |
|---|---|
| author | Tang, Xun Shavlovsky, Michael Rahmanian, Holakou Xiao, Tesi Ying, Lexing |
| author_facet | Tang, Xun Shavlovsky, Michael Rahmanian, Holakou Xiao, Tesi Ying, Lexing |
| contents | This work introduces novel computational methods for entropic optimal transport (OT) problems under martingale-type conditions. The considered problems include the discrete martingale optimal transport (MOT) problem. Moreover, as the (super-)martingale conditions are equivalent to row-wise (in-)equality constraints on the coupling matrix, our work applies to a prevalent class of OT problems with structural constraints. Inspired by the recent empirical success of Sinkhorn-type algorithms, we propose an entropic formulation for the MOT problem and introduce Sinkhorn-type algorithms with sparse Newton iterations that utilize the (approximate) sparsity of the Hessian matrix of the dual objective. As exact martingale conditions are typically infeasible, we adopt entropic regularization to find an approximate constraint-satisfied solution. We show that, in practice, the proposed algorithms enjoy both super-exponential convergence and robustness with controllable thresholds for total constraint violations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_17641 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An efficient algorithm for entropic optimal transport under martingale-type constraints Tang, Xun Shavlovsky, Michael Rahmanian, Holakou Xiao, Tesi Ying, Lexing Optimization and Control Numerical Analysis This work introduces novel computational methods for entropic optimal transport (OT) problems under martingale-type conditions. The considered problems include the discrete martingale optimal transport (MOT) problem. Moreover, as the (super-)martingale conditions are equivalent to row-wise (in-)equality constraints on the coupling matrix, our work applies to a prevalent class of OT problems with structural constraints. Inspired by the recent empirical success of Sinkhorn-type algorithms, we propose an entropic formulation for the MOT problem and introduce Sinkhorn-type algorithms with sparse Newton iterations that utilize the (approximate) sparsity of the Hessian matrix of the dual objective. As exact martingale conditions are typically infeasible, we adopt entropic regularization to find an approximate constraint-satisfied solution. We show that, in practice, the proposed algorithms enjoy both super-exponential convergence and robustness with controllable thresholds for total constraint violations. |
| title | An efficient algorithm for entropic optimal transport under martingale-type constraints |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2508.17641 |