Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: An enhancement over a mini-batch version of OT that provides better empirical evaluation over a large array of tasks
main_review: This paper introduces BombOT, a hierarchical approach to combining mini-batches in order to enhance the approximation quality of mini-batch-based approaches to OT.

I believe it is a nice contribution and the main strength is the comprehensive list of experiments performed, illustrating benefits on several tasks in statistics and machine learning.

I have a few concerns, though

1)The theoretical findings are not very strong. Showing that there is a distance being defined is a nice finding, and contrasting this with the lack of a metric structure in usual m-OT suggest that this construction is in the right direction. However, practitioners are more interested in convergence properties. In this regard, theorem 2 doesn't say much, as it corresponds to a comparison between batch and population versions of the proposed method. This doesn't say much about how does this relate to the original wasserstein/sliced/etc distance.

2)Similarly, experiments mainly comparse m-OT and bomb-OT. Comparisons with true Wasserstein distance are mostly lacking. We should be able to at least empirically how large batches need to be so that we will get decent approximations. As a practitioner who tried used m-OT I believe the problem is super important, but the numbers provided don't say much if they are not put into perspective with respect to the true distance. The findings reporting in Fig 3 are honest, but a bit discouraging in that respect. What is the dimension here? how large need k and m need to be so we get a reasonable approximation? (related to (1)).  

3)another suggestion (optional): I believe this method can be useful for aligning spaces, as in https://arxiv.org/abs/1809.00013. It would be good to have comparisons there as well, and to show whether this mini-batch approximation can be reasonable (i.e. compare against the no-mini batch case)
summary_of_the_review: Nice article. But requires a more thorough comparison with true wasserstein.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed Batch of Mini-batches Optimal Transport (BoMb-OT) method, which finds the optimal coupling between mini-batches in mini-batch optimal transport (m-OT), which is achieved by solving another OT problem over the mini-batches.

The authors claimed that doing this will capture the relation between different mini-batches better. They firstly proved that BoMb-OT approximates the population BoMb-OT metric in probability measure space with and without entropic regularization.

The authors then implemented the proposed BoMb-OT method and applied it on deep generative models and deep domain adaptation, showing that BoMb-OT has favourable performance over m-OT.



main_review: strengths:

The optimal transport (OT) problem studied in this paper is important. Existing work and their advantages and disadvantages are discussed and the study is well motivated. 

Theorem 2 shows that the proposed BoMb-OT method is sound and approximating some well-defined metrics. On the other hand, the authors provided the implementation and demonstrated the usefulness of the proposed method using several different applications.

weakness:

1. As mentioned, the population m-OT has some problem of not preserving metric properties. As also noted the entropic regularized version of population BoMb-OT would recover m-OT in some cases. Does this mean the BoMb-OT will also recover the same problem that m-OT would have?

2. Figure 1 is confusing to me. I get the authors wanted to provide some intuitive explanations for the advantages of using BoMb-OT. However, I do not understand why and how using BoMb-OT can achieve the right transportation in the figure while using m-OT cannot. I suggest if possible these examples can come with specific numbers such that we can calculate and verify the results, making them easier to understand and more convincing.

3. The BoMb-OT has one additional OT comparing to m-OT as noted in "Computational complexity of the BoMb-OT" paragraph ($O(k^2(m^2+1)/\epsilon^2)$ vs. $O(k^2 m^2 /\epsilon^2)$). It looks contradiction to what is mentioned in the appendix, i.e., "The run time of the m-OT nearly doubles that of the BoMb-OT". Is this from a better implementation of BoMb-OT. Please clarify this.
summary_of_the_review: Overall, I found the problems studied in this paper interesting and important, the proposed method reasonable, theoretically sound, and well supported by experiments and implementation details.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Goals: This paper introduces a new optimal transport loss based on a minibatch computation in order to alleviate some weaknesses from the original minibatch OT formulation. The formulation treats minibatches as data and seek to transport the minibatches from the source distribution to the minibatches from the target distribution. By doing so, their method prevents some undesirable connections between data.
main_review: The paper describes correctly their new loss function as well as some weaknesses from the original minibatch formulation. They provide small toy examples to see the differences between the proposed and the original losses. They also discuss the computational complexity of their method and discuss some practical aspects of their contributions. 

Evaluation: My feeling is that the theoretical and experimental aspects are not studied enough. 

For instance on the theoretical side:

(i) While discussing the connections between samples from the transport plan, the authors do not discuss the transported mass. 

(ii) Also a study similar to [1] about the possible bias of stochastic gradient is important. Would minimizing your proposed loss function with SGD lead to the correct minimum ? 


On the experimental side, there are many experiments, but some of them are not extensive (generative modelling and domain adaptation) which make the performances of their method unclear. I am also skeptical that the method is really competitive in practice (numerically and memory) with state of the art method due to the fact that it needs a bigger k for the loss to be computed.

(i) I would encourage the authors to compelete their work on generative modelling and domain adaptation with comparison with recent methods, including methods which are also not based on optimal transport. 

(ii) On domain adaptation and generative modelling, I am not convinced that the proposed method outperforms other methods in practice due to its overall complexity (k>1). Other methods rely on a k equals to 1 (including deepjdot) which might make them faster to train and as efficient or more.

(iii) On domain adaptation, there are more recent methods and I would like to see the comparison [2,3]. There is also this paper [4] that you cite in your supplementary and that you should compare to as this paper also tries to minimize the impact of undesirable connections from minibatches.

Related Work and Discussion: The related work is complete and well discussed. The bibliography style seems respected.

Clarity: The paper is clearly written except for the experimental part. A reader which do not know about generative modelling, domain adaptation, color transfer or bayesian computation can not understand the purpose of the different experiments as the explanations are in the supplementary materials. This gives the feeling that the authors just stacked experiments without discussing them properly and entirely. I think this is mostly due to the high number of different experiments. I suggest to focus on two different experiments, to develop the original problem, their methods to solve them and, finally to produce extensive experiments of different methods on several datasets. The remaining experiments could be added to the supplementary.

Questions and remarks:
1. Does your loss transport all samples ? I think it does, but it should be proven. An overall theoretical study of the transport plan is lacking. 
2. Is your method an upper bound of OT and a lower bound of minibatch OT ?
3. Time comparison between your method and original minibatch OT. This could be done on domain adaptation experiments for instance. 
4. Name of tables are unclear. Please add the meaning of the scores you five (Table 1 and 2).

[1] Learning with minibatch Wasserstein: asymptotic and gradient properties, Fatras et al.
[2] Sliced Wasserstein Discrepancy for Unsupervised Domain Adaptation, Lee et al.
[3] Reliable Weighted Optimal Transport for Unsupervised Domain Adaptation, Xu et al.
[4] Unbalanced minibatch Optimal Transport; applications to Domain Adaptation, Fatras et al.


------------------------------
Rebuttal
------------------------------

Thank you for your detailed answers to my questions. I have read the other reviews and the different answers. I still think that the idea is appealing, but the way the paper is written and the fact that the experiments are not extensive enough prevent a publication at that time in my opinion. I keep my score unchanged and I would encourage the authors to pursue the experimental evaluations or theoretical evaluations (distance of the plan marginals to the marginals ?) of their method.
summary_of_the_review: The proposed formulation is appealing and I like the idea. However, in my opinion, some theoretical and experimental aspects are lacking, and that prevent a publication at the moment (see the different points above). There is a big discussion regarding where the method can applied and it could be replaced by a discussion on theoretical aspects which are not mentionned. Regarding experiments, I encourage the authors to focus on two experiments (Generative modelling and domaine adaptation) and to make extensive experiments with recent baselines.
review_title: null

Meta-review: This paper propose a way to make minibatch Optimal transport (m-OT) more efficient by computing an optimal assignment (in the OT sens) and us this assignment to compute instead a hierarchical OT loss (bomb-OT ) that can be used instead of the m-OT loss. The authors discuss how the equivalent OT plan with bomb-OT is much more sparse, and how the proposed approach is actually not biased when the number of mini-batches $k\rightarrow \infty$ . Numerical experiments  show that the proposed method allows a gain in performances in applications such as generative modeling, domain adaptation, color transfer and approximate Bayesian computation.

The paper originally got borderline-negative scores from the reviewers. While the reviewers acknowledged that the idea is interesting, they had some concerns about the theoretical results strength, some missing baselines and discussions in the numerical experiments. The authors did a detailed reply that clarified some problems. the new numerical experiments with m-UOT were also greatly appreciated by the reviewers but they also raised some questions about the paper. Some concerns detailed below about the comparison with m-OT appeared during the reviewers discussion. Despite the new information,  the reviewers reached an agreement that this paper is interesting but needs more work and another round of reviews before acceptance. For theses reasons  the AC recommends a rejection for this paper.

More details and suggestions below:

- While it is clearly not the objective of the paper a discussion about the proximity of the average plan to the exact OT plan is interested. Also a short numerical experiments showing that the bomb-OT average plan is closer to the exact plan than m-OT would be a good illustration of the better performance of bomb-OT. This seems more important for the paper than the color transfer experiments that is kind of a toy problem.

- After checking the definition in the paper and discussion between reviewers it appeared that the comparison with m-OT is a bit unfair due to the reformulation of the problem in (1). indeed in the usual formulation, k pairs of independent  minibatches are used and the OT is done on those pairs (a sum of k OT) not on all the possible pairwise permutation as in definition of m-OT in equation (1). In other  words in m-OT the batches are supposed to be independent which is not the case  in the proposed formulation (it is equivalent in the population case though).  It means that in practical application, for the same computational complexity  (k^2 OT computed), m-OT actually uses $k^2m$ independent samples on each distribution  whereas the bomb-OD (and the m-OT defined in equation (1) ) use $km$ samples . By implementing m-OT as  in (1) they actually prevent m-OT to explore the dataset as its original  formulation does. This means that all the experiments should be done either with the original m-OT implementation of both the original and (1) in addition to bomb-OT. The proposed method will proably work better but the current experiment do not allow this fair comparison. 

- The theoretical result need more discussion and justification.  For instance  m-OT converges to its population value in 
 $O(m^{1/2}n^{-1/2}+k^{-1/2})$ that is independent from the dimensionality  $d$, but the authors prove the  concentration of bomb-OT in  of $O(m^{1/2}n^{-1/d})$  which is  clearly a problem for large $d$. Also the dependence on  $k$ of the convergence would be important since  bomb-OT is well defined is true only in the population case where $k$ is  large. Note that the claim that it is well defined and hence better is also a  bit dubious because it is well defined for $k=\infty$, which is also the case for m-OT when $m=\infty$. Both $m$ and $k$ large will lead to not practical optimization problems so they are comparable except that m-OT converged to the true OT plan when $m\rightarrow \infty$ which is not the case for bomb-OT.

- While the contribution of the paper in indeed a methodological method and does not require to be state of the art on all applications the numerical experiments should be improved. First as discussed above the comparison with m-OT is actually unfair an do not correspond to what in done in practice (where all mini batches are independent). m-OT should be implemented with  $k^2$ truly independent minibatches.

- Second , the authors use approximate W2 on two of  the GAN dataset and FID on the third. This is  problem because approximate W2 is not defined in the paper. FID is the standard performance measure and should be used for all dataset. 

- Third the novel experiments comparing also raises a lot of questions. m-UOT is far better than BoMb-OT suggesting that Unbalanced OT can compensate for the limits of m-OT far better than bomb-OT itself. Yes there is a slight increase in performance  for ebomb-UOT over m-UOT but is is so small (0.08 %) that it is hard to find them significant, especially since we have no variance. This result that is provided only for DA application actually  suggest that the competitor of bomb-OT is m-UOT and not m-OT so it should also be part of the comparison in the other experiments. The authors talk in their replay about the limits of m-UOT but stating that the experiences are not done in the paper is not an excuse for evaluating this clear competitor on other problems and showing numerically these limits.

- Finally in the current version of the paper puts a lot of things in the annex that make the paper clearly not self content. Some experiments could go in annex/supp for instance the color transfer to make place for more details in the main paper. 

Note that it is not one of those comments above that lead the the reject decision but the sum of them that clearly show that the paper needs more work.
Decision: Reject