Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper presents the complexity analysis of two problems: robust optimal transport and robust barycenter problem. For both these problems, the paper analyzes a sinkhorn-based algorithm and obtains a complexity of O(n^2 / \epsilon). Finally, the authors show some numerical analysis to support the theoretical claims.


main_review: My main concern is that the paper is very similar to the analysis in  [26] where the convergence proof of unbalanced Sinkhorn is provided. This paper analyses a modification of unbalanced optimal transport in which the variable X is forced to be a transportation plan. This modification also translates to a normalization step in the sinkhorn algorithm. In Figure 1, the authors show why this modification is important. The convergence proof of Theorem 1, however, looks very similar to [26]. There is a slight difference due to the normalization step. 

The authors also analyze the robust barycenter problem, which is an extension of the robust OT problem. This convergence analysis, which looks like an extension of the robust OT analysis, provides a O(n^2/\epsilon) solution for the barycenter problem.

I am not a theory person, so I did not go over the proofs in detail. However, from a quick look, I am concerned about the similarity of the problem/analysis compared to [26] and not sure of the novelty. I would like if the authors help clarify this.

limitations_and_societal_impact: The similarity with [26] seem to be the biggest concern for me.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The present paper is on optimal transport problems. The authors derived computational complexity results for robust optimal transport and robust barycenter in the special case with two marginals.
main_review: Originality:
The theoretical results derived in this work is new. The methods and proof techniques are essentially the same as [1].

Quality: 
The theoretical results and the associated proof seem to be solid. The result on barycenter is restricted to the setting with only two marginals.
Though this is a pure theoretical work, the authors provided numerical examples to support their claims, which is a plus.

Clarity:
The paper is well-written. The presentation is well-structured and clear. 

Significance:
The theoretical results in this paper are elegant, but I feel the contribution is incremental in view of [1]. Also, the barycenter result is a bit restricted.

[1] K. Pham et al, On unbalanced optimal transport: an analysis of Sinkhorn algorithm
limitations_and_societal_impact: The limitations have been discussed. It is stated that there is not societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes two robust formulation of the optimal transport problem (namely RSOT and ROT) based on the relaxation of the marginal constraints of the optimal transport plan using Kullback-Leibler divergence. The authors introduces algorithms based on Sinkhorn iterations in order to solve RSOT and ROT problems, and analyse their computational complexities. The fixed-support Wasserstein barycenter problem is also tackled using the proposed RSOT as a divergence, and the algorithm shows a better complexity than the one based on entropy regularised OT. Numerical experiments are also provided to support the theoretical results and applied task are performed (color transfer and generative modeling).
main_review: Originality : The proposed robust optimal transport is very similar the unbalanced optimal transport. Moreover the algorithms proposed are largely inspired from existing method (UOT [9]). For example, the ROT algorithm follows the generalised Sinkhorn algorithm with a extra step that is the normalisation of the transport plan.

Quality : The complexity analysis of the proposed algorithms (solving ROT, RSOT and RobustIBP) are theoretically strong, as they in particular provide an $\varepsilon$-approximation of the solutions. Additionally, a low-rank approximation improves the complexity of the algorithm solving ROT. On the other hand, ROT is presented as a robust method but there are no theoretical or experimental results that truly support this claim (except for Figure 1, see Limitations).

Clarity : This paper is well written and the different problems are clearly stated.

Significance : In my opinion, the improvements of the methods proposed in the article compared to the UOT is not clear. Indeed, both problem have the same complexity. Moreover, the methods are compared with UOT in terms of complexity analysis but not in terms of behaviour: how does an optimal transport plan move the mass under ROT or RSOT? Does the normalising step significantly impact the results? What are the key differences?
limitations_and_societal_impact: Limitations :
- When dealing with color transfer applications, it is known that OT behaves poorly. To be fair, the authors should compare their results with more adapted OT-liked method, such as [Adaptive Color Transfer With Relaxed Optimal Transport, Julien Rabin, Sira Ferradans, Nicolas Papadakis] for example.
- The complexity of the RobustIBP algorithm, that aims at computing the Wasserstein barycenter, is only available when computing the barycenter of two measures.

Questions : 
- I find the toy example in Figure 1 interesting in order to differentiate the proposed method and UOT. However, is the poor solutions coming from UOT are simply due to the choice of the regularisation parameter? Since UOT does not impose any constraints on the optimal plan being a probability measure, I imagine that larger parameters for the KL penalties on the marginals should give better results.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper proposes the Robust Optimal Transport(ROT), Robust Semi-constrained Optimal Transport (RSOT), Robust Unconstrained Optimal Transport (RUOT) and Robust Semi-constrained Barycenter Problem (RSBP). In these problems, the equality constraints in the original OT problem is replaced by the soft KL divergence. Then the Sinkhorn-like algorithms are proposed to solve the corresponding dual problems. Finally, the detailed convergence analysis is given. 
main_review: - It seems unfair to compare the proposed methods with the Sinkhorn algorithm, since the solution of the proposed method is even not in $\Pi(P,Q)$. Also, there is no comparison between the proposed methods and Sinkhorn, in terms of both accuracy and efficiency.
- By further relaxing the equality constraints, the problem should be simpler and easier to compute. But what's the purpose of such a relaxing? 
- In Fig. 2, what's the meaning of different colors? Is there any way to enlarge the difference of different lines like plotting them in the log-domain? Currently they just mix together.
- Similar relaxation about OT has been proposed in [Fast Unbalanced Optimal Transport on a Tree] and its cited works. Please see the first formula of this paper.
- No comparison between the proposed methods and other similar ones, like the standard OT and UOT. Without such comparisons, it is hard to see the merits of the proposed ones.
- Many missing references about partial optimal transport: 
  - Alessio Figalli.  The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533–560, 2010
  - Luis A Caffarelli and Robert J McCann. Free boundaries in optimal transport and monge-ampere obstacle problems. Annals of mathematics, pages 673–730, 2010.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on the computational complexity of robust optimal transport between discrete probability measures. The authors propose two Sinkhorn-based algorithms with near-optimal complexity to approximate the optimal cost. Furthermore, for solving a robust barycenter problem, they propose an algorithm based on iterative Bregman projections (IBP) and show that it also has near-optimal complexity between two discrete probability distributions.
Experiments verify the presented complexities for the above algorithms. The main limitations and future work directions are also discussed.
main_review: - For robust optimal transport and its corresponding barycenter problem, the authors develop Sinkhorn-based and IBP-based algorithms for solving them, and provide a comprehensive study of the computational complexity. The proposed algorithms can achieve near-optimal complexity, which outperform state-of-the-art competitors.

- The organization of this paper is satisfactory, and the motivation is very clear.

- The experiments are implemented on various synthetic and real datasets; the experimental settings and results are well explained.

- Some existing work considers the problem of robust optimal transport with similar  idea, e.g., [1] and [2]. More discussion is needed to compare them with the proposed method.

[1] Mukherjee, Debarghya, et al. "Outlier-Robust Optimal Transport." arXiv preprint arXiv:2012.07363 (2020).

[2] Jawanpuria, Pratik, N. T. V. Dev, and Bamdev Mishra. "Efficient robust optimal transport: formulations and algorithms." arXiv preprint arXiv:2010.11852 (2020).
 
limitations_and_societal_impact: - The complexity of ROBUSTIBP algorithm is near-optimal only when the number of discrete probability distributions, $m$, equals 2. This case is quite special and restrictive.

- In the experimental part, the approximation error of proposed algorithms is not discussed. Also, there is a lack of comparison with other methods.

- Optimal transport methods usually suffer from the curse-of-dimensionality.
For example, the convergence rate of the Wasserstein distance may be arbitrarily slow as the number of dimension increases.
I am wondering how does the size of the dimension affect the performance of the proposed method? Some discussion and empirical results are needed.
review_title: null

Meta-review: Most of the reviewers and the AC agree that the submission makes a worthwhile theoretical contribution in designing and analyzing new algorithms for RSOT and RIBP. 

The reviewers highlight the following main concerns:
- The algorithm appears to be a simple normalized version of the Sinkhorn algorithm for UOT. 
- the technical novelty appears to be somewhat incremental, as the necessary techniques already appear in the OT and UOT literature.
In the rebuttal, the authors explain that the obstacle to overcome in the analysis of the new algorithms. They also stress the fact that no simple, very efficient algorithms were known for RSOT and RIBP before this work. The AC believes that the simplicity of the algorithm and the lack of other algorithms besides standard convex solvers makes this paper close to the acceptance threshold for NeurIPS.

A number of issues spotted by the reviewers and the AC could be addressed by the authors in a final version:
- the discussion of the significance and novelty of the convergence analysis of RSOT should appear in the paper,
- the experimental section would ideally include more varied experiments. In particular, larger examples would be nice to test the scalability of the method, even if it may not be possible to run cvxpy on them to obtain the ground-truth optimum.
Decision: Accept (Poster)