acceptodds
Under review as a conference paper at ICLR 2027

Douglas–Rachford Splitting for High-Accuracy Unregularised Multi-Marginal Optimal Transport

Abstract

Multi-Marginal Optimal Transport (MMOT) is commonly solved with entropic regularization because iterative scaling is fast and stable at moderate accuracy. The same regularization, however, introduces a non-vanishing bias with respect to the original linear program. We study DRMOT, a Douglas–Rachford splitting method for unregularised MMOT. Its key technical ingredient is a closed-form orthogonal projection onto the affine set of prescribed tensor marginals, which extends the known matrix projection to arbitrary-order tensors. We further introduce a scale-aware default step size and a cost-aware feasible recovery tailored to the sparse iterates produced by DR; on identical DRMOT iterates, this recovery reduces the final reported error by roughly – relative to the standard rank-one correction. We re-evaluate DRMOT under equal wall-clock budgets as a complete finite-time solver: the entropic baselines retain their published recovery rules, while DRMOT uses the proposed cost-aware recovery. On Wasserstein-barycenter grids, the best DRMOT variant is – more accurate than the best tuned entropic baseline within the same 20-second budget. In within-family cost diagnostics over the two evaluated instances per family, the best observed DRMOT-s runs are the only tested ones to reach an absolute objective gap of within 20 seconds on both Coulomb and Brenier–Euler costs, while the dimension-only DRMOT variant gives the best observed -level time on risk pooling. On model-independent option pricing, DRMOT agrees with a high-accuracy HiGHS reference down to float64 numerical precision whereas the entropic methods plateau near . These results identify the regime in which solving MMOT without entropic bias is practically beneficial.

Primary area:
optimization
Keywords:
optimal transport, multi-marginal optimal transport, non-entropic regularization, Douglas-Rachford splitting

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_5HPAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

The paper proposes a Douglas–Rachford splitting algorithm for unregularized multi-marginal optimal transport (MMOT), relying on a closed-form projection onto the affine set of prescribed marginals. It also introduces a scale-aware step size and a cost-aware feasible recovery procedure.

The numerical experiments show promising performance, particularly in the high-accuracy regime, where the proposed method outperforms the tested entropic baselines under equal computational budgets.

Critical strengths

Simple and effective algorithm. The proposed Douglas–Rachford algorithm builds on established optimization methods, remains relatively simple to implement, and demonstrates promising numerical performance, particularly in high-accuracy regimes.

Novel closed-form projection. The extension of the affine marginal projection to arbitrary-order tensors is mathematically sound and provides a useful computational ingredient for applying Douglas–Rachford splitting to MMOT.

Critical weaknesses

1. Computational complexity and hidden constants (Theorem 4.1).

Theorem 4.1 establishes an ergodic convergence rate of O(ΓDR/T)O(\Gamma_{\mathrm{DR}}/T), leading to an arithmetic complexity of O(mnm/ε)O(mn^m/\varepsilon) after suppressing the instance-dependent constant ΓDR\Gamma_{\mathrm{DR}}.

Although the authors acknowledge this simplification, I believe the dependence of ΓDR\Gamma_{\mathrm{DR}} on the problem parameters deserves further investigation. In particular, it is unclear how this constant scales with the number of support points nn, the number of marginals mm, the cost magnitude, and the chosen step size.

For instance, standard Douglas–Rachford bounds involve quantities depending on the initialization and inverse powers of the step size. Since the proposed step sizes depend explicitly on β=mnm−1\beta=mn^{m-1}, these constants could introduce significant additional dependencies on nn and mm. Similarly, Frobenius norms of the cost tensor may introduce factors scaling with nm/2n^{m/2}.

2. Linear convergence and conditioning (Theorem 4.2).

Theorem 4.2 establishes linear convergence with a problem-dependent contraction factor r∈(0,1)r\in(0,1). However, the practical significance of this result depends crucially on how close rr can be to one. For instance, if r=1−δr=1-\delta, the iteration complexity involves a factor of order 1/δ1/\delta.

The proof relies on a Hoffman error bound, whose constant may depend strongly on the conditioning of the underlying LP. Moreover, the argument involves the marginal operator and the step size, potentially introducing further dependencies on the support sizes.

3. Sinkhorn-based feasible recovery and end-to-end guarantees.

The use of Sinkhorn for feasible recovery deserves further clarification. While the subsequent rounding can ensure feasibility, it is unclear what theoretical guarantees remain for the complete algorithmespecially in term of accuracy.

Questions for authors

Q1 For weakness 1: Could the authors make these dependencies more explicit? This seems essential for a meaningful comparison with existing MMOT complexity bounds, which retain explicit dependencies on the problem parameters.

Q2 For weakness 2: Could the authors provide a more explicit characterization of the contraction factor, particularly its dependence on nn, mm, and the cost structure? Without such information, the linear convergence result remains largely qualitative and does not establish an informative computational complexity.

Q3 For weakness 3:

In particular, can the authors establish a computational complexity bound for obtaining a feasible plan with objective error at most δ\delta, accounting for the finite number of Sinkhorn iterations and the additional error introduced by rounding?

This is particularly relevant because Theorem 4.1 concerns potentially infeasible shadow iterates, whereas the numerical experiments evaluate recovered feasible plans.

Q4 Section 3.3: What motivates the choice c=0.7c=0.7 in the scale-aware step-size rule? Was this value selected through empirical tuning, or is there a theoretical intuition?

Minor comments

Lines 140–142: The proximal operator is not defined. It would be useful to recall its definition and clarify that the indicator function takes values 00 on the constraint set and +∞+\infty outside, rather than using the 0/10/1 convention.

Lines 152–153: The sentence introducing the DR update appears incomplete.

Line 209: The quantity λ⋆\lambda^\star is introduced without a definition. Please clarify what it represents.

Reviewer_68q9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper extends Douglas–Rachford splitting to dense, unregularized multi-marginal optimal transport. It derives a closed-form projection onto the affine marginal constraints and uses it to implement efficient tensor updates. It also introduces a cost-scaled step-size rule and a cost-aware recovery procedure that turns intermediate iterates into feasible transport plans.

Critical strengths
  1. The method gives a simple implementation for general tensor marginals. The closed-form projection avoids an auxiliary constrained solve or an explicitly formed pseudoinverse. The residual recursion further reduces repeated tensor operations. This makes the extension to multiple marginals practical to implement.

  2. The paper evaluates feasible outputs and measures the effect of recovery directly. Comparing the two recovery procedures on identical DRMOT iterates is a useful ablation.

Critical weaknesses
  1. The ablation does not clearly show what drives the overall improvement. Table 2 shows that the new recovery step reduces DRMOT’s error by roughly 5–10 times, but this recovery is tested only with DRMOT. A comparison applying both recovery rules to DR and the competing solvers would help separate the effects of the optimization method, the recovery step, and their interaction. The baseline evaluation also lacks stabilized Sinkhorn with epsilon continuation, such as Schmitzer (2019), and a timed HiGHS comparison. Without these controls, it is difficult to tell how much of the reported advantage is specific to DR.

2.The benchmark evidence is too limited for the broader high-accuracy claims. Figure 4 takes a lower envelope over both hyperparameters and different problem instances. Different methods can therefore be represented by different instances, so these curves do not establish consistent wins on matched problems.

Questions for authors
  1. How do the rankings change when the same cost-aware recovery is applied to all solvers, with its runtime included? This would help separate the contribution of the DR iteration from the contribution of recovery.

  2. Can the authors provide separate accuracy-versus-time curves for each instance in Figure 4, together with timed HiGHS results on the tractable instances? Please also clarify whether the entropic baselines use log-domain stabilization or epsilon continuation.

Reviewer_2taYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a DRMOT method for solving MMOT problem. Standard entropic regularization methods are fast but suffer from accuracy problems due to inherent bias. To achieve high accuracy, the author propose a closed-form orthogonal projection onto the affine marginal-consistency set for arbitrary-order tensors. By integrating this projection with a scale-aware default step size and a cost-aware feasible recovery strategy, DRMOT computationally matches entropic solvers in per-iteration cost while effectively breaking the high-accuracy barrier.

Critical strengths

The paper addresses a meaningful computational problem, and obtains highly accurate MMOT solutions without the bias introduced by fixed entropic regularization. The closed-form projection makes the multi-marginal DR updates straightforward to implement using tensor operations.

Critical weaknesses
  1. The novelty of this method is incremental compared with existing Douglas–Rachford method for marginal OT. The tensor projection is useful, but the splitting framework and convergence arguments largely follow established machinery, while the step-size rule is primarily motivated empirically.

  2. The main results combine the DR updates with a new recovery procedure that independently provides substantial gains. Although the end-to-end comparison is valid, the current ablation does not sufficiently separate improvements from the optimization trajectory and those from feasible recovery.

  3. The complexity concerns the iterations, its constant can change from one problem to another. It does not show that the same bound holds for the feasible solutions used in the experiments.

Questions for authors
  1. How does DRMOT compare with HiGHS and a suitable unregularized first-order solver in time to a common objective gap and feasibility tolerance?

  2. Do the observed entropic accuracy plateaus persist with stabilized implementations and a decreasing regularization schedule under the same total runtime budget?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.