- 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 , leading to an arithmetic complexity of after suppressing the instance-dependent constant .
Although the authors acknowledge this simplification, I believe the dependence of on the problem parameters deserves further investigation. In particular, it is unclear how this constant scales with the number of support points , the number of marginals , 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 , these constants could introduce significant additional dependencies on and . Similarly, Frobenius norms of the cost tensor may introduce factors scaling with .
2. Linear convergence and conditioning (Theorem 4.2).
Theorem 4.2 establishes linear convergence with a problem-dependent contraction factor . However, the practical significance of this result depends crucially on how close can be to one. For instance, if , the iteration complexity involves a factor of order .
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 , , 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 , 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 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 on the constraint set and outside, rather than using the convention.
Lines 152–153: The sentence introducing the DR update appears incomplete.
Line 209: The quantity is introduced without a definition. Please clarify what it represents.