Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider a regularised optimal transport problem. They 
- obtained a dual objective in case of a general regularisation based on f-divergence,
- used 
a) the large-scale stochastic dual approach, introduced by Seguy et al., to solve the optimal transport problem in their generalised setting,
b)  Langevin Sampling to sample from the conditional distribution of Y given X,
- proved some convergence guarantees.
main_review: - There are a number of recent papers with large-scale approaches to OT, e.g.
1) Jacob Leygonie, Jennifer She, Amjad Almahairi, Sai Rajeswar, and Aaron Courville. Adversarial
computation of optimal transport maps. arXiv preprint arXiv:1906.09691, 2019.
2) Alexander Korotin, Vage Egiazarian, Arip Asadulaev, Alexander Safin, and Evgeny Burnaev.
Wasserstein-2 generative networks. In International Conference on Learning Representations, 2021.
3) Ashok Vardhan Makkuva, Amirhossein Taghvaei, Sewoong Oh, and Jason D Lee. Optimal
transport mapping via input convex neural networks. arXiv preprint arXiv:1908.10962, 2019, etc.

These methods solve un-regularized OT and recover an OT map; they significantly outperform the approach of Seguy et al. (2018). Any comments? Any comparisons? Although the problem statement is slightly different, the comparison can be done using some generative modeling application. Moreover, it is easy to outperform the approach of Seguy et al. (2018), since it uses the barycentric projection (BP) baseline which is weak compared to using the entire conditional distribution pi(y|x).

- In general, the text of the paper is rather well written. However, some details are missing, see comments below.

- Can the authors prove their theoretical result about the convergence for CNNs? It seems not optimal to use FCNN for images, so CNNs are needed. The authors mentioned that the assumptions of the theorem are valid for FCNN. What is about CNN? Moreover, could the authors provide some more visual results of the experiment with Celeba? FCNN are not efficient for such high dimensionality (64x64x3), so it could be good to analyse failure cases.

- In case of experiments with synthetic Gaussian data I would like to see how the method scales with the dimension. Moreover, the authors provide the value of the Frechet distance. However, to understand whether they are big or not we need some characteristic value or normalisation. So the current representation of the results does not allow to comprehensively analyse them.

- The authors used the Langevin dynamics to generate images. Could the authors provide some intermediate results on how the dynamics converges?

- Protocols of experiments are not fully detailed, see comments above. Also, in case of the experiment with the Celeba dataset, how the samples X and Y were organised? For each image from X there is a high-res image of the same face in Y? If yes, this simplifies the problem. Also, I would prefer to see more  results of the corresponding super-resolution task, not only values of the FID score and some faces in Figure 1. Also, why not to include more toy examples and illustrate the convergence?

- The results on Celeba are promising, they demonstrates that we can construct OT rather efficiently even for rather high-res images. 

- Overall, the results are promising and some theoretical guarantees are proved, but more details about the experiments are needed.  Also, comparisons with recent method are missing.

I need more details/comments to upgrade/downgrade the current rating.

limitations_and_societal_impact: The approach consists of several steps, and it is important to discuss limitations of different steps separately, it is unclear how these different steps perform separately.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose methodology to sample from high dimensional regularized transport maps using Langevin diffusion with neural network parameterized score (via score-matching), and neural network parameterized potentials. 

The authors derive novel quantitative convergence results regarding approximating dual potentials with wide neural nets and the subsequent quality of approximated transport map.

main_review: This paper uses NN parameterized dual potentials and NN parameterized score, both of which are not original, to sample from a transport map, which is the novel application. Arguably more interestingly, the authors derive quantitative convergence rates relating the NN parameterized dual potentials to quality of transport map approximation.

The experimental results are not very strong e.g. the upsampled CelebA results start from down sampled CelebA rather than noise and are of worse quality than using score-matching to sample images starting from noise. 

It is not clear what the advantages of using score-matching + NN parameterized potentials are over just score-matching for generative models and conditional generation. However, the theoretical results and proof using NN parameterized potentials is very interesting and may be used in other OT related work.

Strengths:
Leverages existing pre-trained score networks for sampling high dimensional OT transport maps e.g. for conditional generation.
Theoretical contributions regarding using NN parameterized potentials for OT gives legitimacy to this approach which appears novel and significant

Weaknesses:
SCONES requires pre-trained score network, yet the method’s performance (for generative modeling) appears to be worse than simply using the pre-trained score network in terms of FID score. 
Similar to previous score based methods, it requires large neural networks, and many diffusion steps resulting in slow sampling.

Missing references: Parameterizing potential with Neural networks, ICNN [1] or RKHS [2], flows [3]

The statement of “breaking curse of dimensionality” is tangential to the main work and is only true under strong sub-Gaussian assumption, line 544 in appendices.

The method appears expensive e.g. CelebA upsampling uses 16 GPUs for 4 days. Is this just for training the potential networks or both potential and score networks?

No comparison with other transport samplers rather than barycentric average is provided. See e.g. [3], I imagine there are others sampling the transport map rather than averaging.

Minor:
Notation: 
$\lambda_\max$ not formally defined, I assume eigenvalues, line 193
Do you mean M or H in proof, appendices line 533-542
Typo using $S_{\theta_1}- S_{\theta_2}$ in line 485 of appendices but I assume means $\theta_1-\theta_2$ as in proof line 497

Careful with splitting main/supplementary,  I assume these will be corrected when files are combined:
Latex errors, links/refs e.g.  “??” missing in Appendices in main file
Link [15] in the supplementary should be [14], line 527
Comment with initials “MD” left in appendices on main file, line 425

[1] Optimal transport mapping via input convex neural networks, 
[2] Stochastic Optimization for Large-scale Optimal Transport, 
[3] Learning normalizing flows from Entropy-Kantorovich potentials, 

limitations_and_societal_impact: They mention that FID is not as good as regular score matching generative modeling
There is limited societal impact compared to existing methods.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Using score-based generative modeling and Langevin dynamics, this paper proposes a new method to sample from the Sinkhorn coupling distribution. The method first solves the dual problem of regularized optimal transport by parameterizing the dual variables with neural networks. After learning the dual variables, the coupling distribution is known up to a normalizing constant, and can therefore be sampled from using Langevin dynamics and a score-based model as the prior. Experiments demonstrate advantages over barycenter methods.
main_review: Solving large scale optimal transport has important practical applications, and is of high relevance to the NeurIPS community. This paper proposes a new method to sample from the optimal coupling distribution.

Advantages of this submission:
1. Very clear writing. 
2. I am not an expert on optimal transport, but the following theoretical contributions seem to be new: (i) generalizing regularized optimal transport to f-divergence regularizers; (ii) convergence rate of learning neural network based $\phi_\theta$ and $\psi_\theta$ models with gradient descent (under some rather strong assumptions). 
3. The proposed SCONES method is very general, and can be applied to regularized optimal transport problems with any f-divergence regularizer. When a pre-trained score-model is available, SCONES is also quite efficient.

Disadvantages of the submission:
1. It is unclear whether samples from Langevin dynamics really capture the optimal coupling distribution in practice. Authors provide some sanity check on synthetic Gaussian distributions, but it is important to check on image problems as well. It is not hard anyways: why not just estimate the transportation cost using samples from SCONES, and compare it with the value of the dual problems obtained after learning $\phi_\theta$ and $\psi_\theta$ models. Given that authors only used 8 pages out of a 9-page limit, there should be enough space to include such an experiment.

2. Authors need to demonstrate more practical applications of sampling from the optimal coupling distribution. Why would we want to convert MNIST to USPS images and vice versa? Why should we use optimal transport to upsample images? It's not clear to me that optimal transport will provide correct upsampled images and can have any practical advantage over existing methods for superresolution.

Some minor issues:
1. "by providing" repeated twice on line 184.
2. Some broken references in the appendix.

Post rebuttal update:
Authors addressed some of my concerns in the response. I am happy to increase my score to 6.
limitations_and_societal_impact: No obvious limitations or negative societal impact to me.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a method to sample from the regularized OT plan (Sinkhorn plan) via a score-based method and Langevin dynamics.
main_review: **Originality**

The proposed method is original. Nevertheless, the main topic of this paper is OT but the only related paper discussed/compared to in this paper is Seguy et al. (2018). There are already a lot of other methods (primarily based on the unregularized OT), which outperform the BP method of Seguy et al. (2018), some even consider applications to images. I will list some of them in the next sections. Therefore, a comparison with some of them should probably be included. Most of them solve a slightly different problem (recover pure "unregularized" OT map), but it seems ok since the generative modeling applications the authors consider require roughly the same.

**Quality**

There are some questions, comments which probably should be discussed in detail.

(1) The authors use dense networks (potentials) which is a contrast to most works computing OT for images. Why do the authors not use Conv Nets?

(2.1) To train OT plan, the authors use entropy-regularized OT, the optimization of which is known to be practically unstable in the continuous case. For example, Seguy et al. (2018) in Section 5.3 considered exactly L2 regularization, not entropy. Most later works Leygonie et al. (2019), Li et al. (2020), Makkuva et al. (2020), Korotin et al. (2020) which either use regularized OT or compare their method to it, all primarily use L2 reg. as it is claimed to be more stable than entropy. Therefore, I have doubts about the practical stability of the continuous entropy-OT training procedure, especially in the dims which are considered by the authors (64x64x3). My concern is that exp(lambda^-1*(phi+psi-c)) term appearing in training explodes since, e.g., for lambda=0.01, we already have exp(100). Can the authors comment on this?

(2.2)  The main baseline Seguy et al. (2020) considered in this paper is rather outdated (a lot of newer related work exists), i.e. comparison just with it might seem unfair.  Comparison with barycentric projection (BP) baseline by Seguy et al. (2018) might seem unreasonable. BP uses conditional expectation E\pi(y|x) while this paper considers the entire conditional distribution \pi(y|x). One may say that it is obvious that the method outperforms BP. Besides, BP is also known to suffer from bias. In README.MD of the official repo of Seguy et al. (2018) there is an image demonstrating the performance of BP in 2D. Even in this toy example, it is seen how different the BP is from the true samples (RED vs. GREEN points). 

(3) In the synthetic data experiment, it is not transparent how the ground truth optimal plan is computed. Besides, the values of Frechet distance themself are not interpretable. Could the authors please provide values of its normalized variant BW-UVP, see Fan et. al. (2020)? In general, probably a more thorough evaluation is needed on Gaussian synthetic data (e.g. in various dimensions 2,4,...), to understand the scalability of the method.

(4) How are the samples shown in Figures 1,2 chosen? Are they sequential iterations of Langevin dynamics? Please comment.

(5) As far as I understand, in the CelebA experiment, for each face its downsampled copy is available on the other dataset. Such pairing might simplify the problem. Probably, half of the CelebA dataset should be coupled with the downsampled other half to avoid any inductive bias in data.

(6) Experimental details are given in Appendix, some code is present in the supplementary. However, reproducing the results might be hard due to the high required computational power. It seems to me that the paper lacks "easy" experiments, e.g. those which a reader can briefly reproduce on a single GPU or even CPU. Why do I think this is essential? The authors clearly point out that, e.g., Celeba Experiment, requires 4 days on 8xP100 GPUs. Even not all research groups who might be interested in improving/using current work are capable of spending so much computational time on reproducing the experiments.

**Clarity**

The paper is well written in general. Some places, e.g., Figures 1, 2, could be enriched. It would be nice to see a toy qualitative performance on 2D examples for better transparency, e.g. how well do the samples match the true distribution? This seems to be a necessary attribute of all OT papers nowadays.

**Significance**

This is probably the first paper demonstrating the application of a continuous regularized OT plan at a truly large scale. The performance of the method is promising. Besides, the method is supported by the convergence/stability theoretical results.

I admit the contribution of the authors, but I think a lot of details should be clarified and a more thorough evaluation to be performed. I set the score based on the current state of the paper but will be happy to reconsider it after the rebuttal phase.

**Additional feedback**

Please do not use \mu and \sigma simultaneously to denote probability distributions. This is misleading for obvious reasons. (!)

**Post rebuttal**
I raise the score to 5.

**Post rebuttal v2**
I raise the score to 7, see my last post.

limitations_and_societal_impact: Social impact is ok. About the limitations:

The proposed pipeline consists of several successive elements (OT plan, score function, sampling) which might be practically complex and hard to set up. This is a limitation and should be emphasized and discussed. Besides, it is unclear how each of these elements performs separately (it is not clearly discussed in the paper). In particular, the quantitative evidence that the procedure actually samples from the true Sinkhorn transport plan requires more discussion.

The computational complexity is large (4 days of computing on 16 NVIDIA p100 GPUs for CelebA experiment), but this is discussed fairly well.
review_title: null

Meta-review: This paper proposes a method to sample from high dimensional regularized optimal transport maps using Langevin diffusion on neural network parameterized potentials. The reviewers compliment the authors on being some of the first to tackle this problem at a truly large scale. The problem is important and the proposed solution seems technically sound and practically promising.

After the first round of reviews some concerns surfaced about the correctness of some of the presented results. In addition to general concerns about experimental validation from multiple reviewers, reviewer zJ3u pointed out some irregularities in the reported BW-UVP values which turned out to be caused by a scaling error in the regularization used in some of the experiments. The authors responded by providing updated results, in addition to acknowledging and fixing the error. The reviewers are satisfied with the author response and are now unanimous in their recommendation to accept the paper.

Authors, please carefully revise your paper for the camera ready version, and make sure to incorporate all new results and all changes that were promised in the discussion with the reviewers.
Decision: Accept (Poster)