Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies how to approximate Sinkhorn computation using more efficient kernel matrix representations (low-rank approach + LSH based sparse approach). Neither of both ideas is completely new, the authors studies a combination of them that hasn't been explored in the literature, and use the proposed tech in three applications: ranking, embedding alignment, graph distance regression. 

Pro:

- Authors have attempted multiple applications to prove the effectiveness with quantitative metrics. The main contribution seems the empirical validations. 

Con:

- I think the presentation is a bit out of focus. Some sections can be left for appendix (e.g., Backpropagation in Sec 4. and Sec 5.) since some are either very standard in the literature or not really solidly experimented. Since I consider the main contribution to be the empirical evidences, the space should left for more details on those empirical experiments (for reproducibility purpose).

- the paper's idea is not particularly innovative. (yet it is not the sole reason for my scoring). 

- Some relevant works on low-rank ideas have not been compared/cited. e.g.  

Forrow, Aden, et al. "Statistical optimal transport via factored couplings." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.

- The writing can be improved. A lot citations/references are not particularly relevant to what this paper is about and make some parts not enough self-explained. 

----
The authors addressed my concerns and I raised my evaluation ratings. 





review_title: A practical OT work that enhances performance on three application tasks

final_score: rating: 6: Marginally above acceptance threshold
review_content: Proposal:
- First log-linear time algorithms for entropy-regularized OT that work for complex 
  real-world tasks using high-dimensional spaces with little to no loss in accuracy
  ... many claims in one statement
- Locally Corrected Nyström
  ... this would deserve a single paper - just to proof everything is still fine and valid
  in particular to alternatives
- In the way this paper is written I am positive it gets accepted 
  (because it fits the writing style of the more recent papers in the field)
  and contains sufficient novelty
  ... but I always wonder if good (published) science originates from clarity (or confusion)

comments:
- sorry but the text is very hard to follow !
- 'Optimal transport is concerned with the problem' (on p.3) - I think some introductive
  work may not harm in the first page
- the reader is thrown up by terms and references - in my view more confusing than enlighting
  --> it may not harm to add some brief explainations of terms (from Cuturi:)
  'A transport plan is a flow on that graph satisfying source (a i flowing out of each node i) 
   and sink (b j flowing into each node j 0 ) ... --- which is simple an optimal flow
  in a graph ... I am not sure why we not simple can call it like this but need to come up with
  new terms
- The paper is written (following the very strange title
   ... although Cuturi did the same it would be nice if we can stop having marketing titles
  but focus a bit on science again ... in particular in 10 years many things proposed nowadays
  are not lightspeed or warpspeed anymore) like providing an all issues solving theory 
  --> this does not improve the readability of the paper
  For example Eq.2 what is the 'meaning' of (s) and (t) -- I have an idea but it is not written there
- it is hard to proofread and verify a paper if it is written with the objective to confuse the
  reviewer ;-)
- widely incremental work by combing some known ideas (Nystreom, LSH, ...) - with a lot of addon
  theory which is probably correct but not very clear in the presentation
- 'Since the Nyström method is a low-rank approximation it only accounts for the
global structure of the kernel matrix K and not for the local structure around each point x.'
  - this is actually wrong (!) - if the landmarks are indepentent and the number of landmarks
  aligns with the rank of the matrix - Nystroem will provide a perfect (!) reconstruction
	--> there is a lot of work on the approximation bound of Nystroem (and related methods) - see
  e.g. work by Dhillon
- where is the definition of 'sparse approximation K^sp' used in Eq 3? 
- how precisely does \bar{P} (after Eq 3) link to the part around Eq 2? - is the Kernel K_{ij} used
  here as well and / or where is the actually input data Kernel matrix 
- in Eq 1 what should be a cost function here and how do you obtain C_{ij}?
- Ok Eq 4 is an actual proposal by balancing (and joining) sinkhorn and Nystroem in one distance formulation
  and it would not harm to motivate why and where you need such a distance in advance 
  (problem statement --> solutions --> particular strategy --> outlined proposal --> evaluation + proofs)
- 'Most modern ML models are trained using backpropagation' - lets rephrase it as: nowadays neural network
  approaches are trained by backprop ... there are many other methods which are not at all trained by backprob
  for good reasons 
- '... Usually we want to learn embeddings which act as point sets X p and X q and therefore need gradients' 
  - well yes, if we stick on neural networks we need vectorial inputs and hence are often looking for (costly)
  embeddings - if we do not use NN we may not have this problem (but others)
- 'We can either estimate these gradients via automatic differentiation' - this is in general the more costly
  way to do things and I am happy to see that explicit derivations are given
- regarding table 1 --> before you come with numbers (where you measured something) it would be good to specify
  details of your scenario (which are omitted before) - in particular which data, which cost function, which parameters 
  a.s.o. -- and although I understand that you like your method most it would still be good to provide some
  oldfashion baseline (and not - not from sinkhorn)
- 'We propose the graph transport network (GTN) to evaluate approximate Sinkhorn and enhanced optimal transport and advance the state of the art on this task.' --- fantastic on page 6 you actually outline a more userfriendly motivation

review_title: Review on Warpspeed Computation of Optimal Transport, Graph Distances, and Embedding Alignment

final_score: rating: 7: Good paper, accept
review_content: Summary:
The paper considers the problem of approximating Sinkhorn divergence and corresponding transportation plan by combining low-rank and sparse approximation for the Sinkhorn kernel and using Nystrom iterations as a substitute for Sinkhorn's iterations. The corresponding approach is amenable to differentiation and can be used as a building block in different architectures. Numerical experiments in several settings are performed to compare  the proposed approach with existing ones and demonstrate its scalability.

Evaluation:
I believe the proposed framework is a valuable contribution in terms of practical performance and wide list of applications where OT could not be used before because of the high computational cost. So, I would recommend accepting this paper. 

Pros:
1. High scalability of the proposed approach and linear up to log factors in dimension complexity.
2. Flexibility of the framework due to a combination of sparse and low-rank approximations, which are complementary to each other.

Cons:
1. Some parts of the paper seem to be not clear for a general audience.

a. First page. $n$ is undefined.

b. First paragraph of Sect. 2. What is "set of embeddings"?

c. Last but one paragraph on p.2. $d$ is not defined.

d. In (1) $F$ stands for the Frobenius product, does it?

e. Proposition 1. $N$ is not defined.

f. First paragraph of Sect. 5. What is "OT with multiple heads"?

g. What is meant as embedding?

h. In the experiments, what is used as the cost function to define the Sinkhorn kernel $K$? If this is an $L_2$ distance, the convolutions can be used to accelerate the standard Sinkhorn and it would be nice to see the comparisons with convolutional Sinkhorn, which is also log linear.

i. Appendix A. $B,r,b$ are not defined when they are first used.

j. In (17), how was the last equality obtained?

k. In (19), (20), how were the first equalities obtained?

l. Appendix E, first paragraph. What is "log-sum-exp trick"?

m. Appendix G. What is "similarity matrix"?

2. As far as I understood, the proposed approach is not amenable to parallel computations on GPU as opposed to standard Sinkhorn.


Minor comments
1. Maybe it is too strong to state in the abstract that this is the first log-linear time algorithm given that when the Sinkhorn kernel corresponds to a convolution, the Sinkhorn's algorithm is log-linear by using the FFT.
2. Bibliographical note. (Altschuler et al., 2017) did not show $1/\varepsilon^2$ bound for the Greenkhorn. Their bound for Greenkhorn is the same $1/\varepsilon^3$ as for the Sinkhorn. The bound for Sinkhorn was improved to $1/\varepsilon^2$ in http://proceedings.mlr.press/v80/dvurechensky18a.html and the bound for Greenkhorn was improved to $1/\varepsilon^2$ in http://proceedings.mlr.press/v97/lin19a.html.
3. Bibliographical note. Quadratic regularization for OT was proposed in https://arxiv.org/abs/1704.08200.
4. Appendix A. I believe that in this framework a general value of the regularization parameter $\lambda$ is used. If it is the case, then the number of Sinkhorn iterations to find an $\varepsilon$-solution to the regularized problem is $1/(\varepsilon \lambda)$. This follows from http://proceedings.mlr.press/v80/dvurechensky18a.html Theorem 1 and an estimate for $R$ in Lemma 1. The bound $1/\varepsilon^2$ corresponds to finding an $\varepsilon$-solution for the non-regularized problem. In this case one has to set $\lambda=\varepsilon/(4 \ln n)$, which may be too small.
review_title: Good practical approach, but not sufficiently clear for a general audiece

final_score: rating: 6: Marginally above acceptance threshold
review_content: Overall, I found this paper interesting, and I think it does address a relevant problem for the community.


I have been playing with Nystrom approximations myself and I know the results are a bit disappointing, but it is grounded on strong theory. Then, it is pretty much welcome that attempts to patch the problems of Nystroms are made, so Optimal Transport becomes more scalable.

The reason for why my judgement is below acceptance is that I believe both theory and results altogether are not strong enough so they live up to what is promised in the abstract. Typically when new methods are proposed with the promise of bridging a gap and solving a relevant problem, I hope they will have a thorough theoretical justification, or the results will be compelling. None of this convincing enough here.

1)On the theoretical side, I missed a convergence analysis, as the one in the Nystrom method. The theory side focuses on some derivative calculations, but I would love to see how the interplay between sparsity, Nystrom method and LSH lead to better convergence. I acknowledge this can be hard to do, though. Without having the theory it is hard to understand whether any reported experimental result is a consequence of choosing particularly good example for their method.

2)I found the experimental/methodological side was a bit disconnected from the rest; the paper contains  several vignettes about some applications/improvements in the practical side, but when reading that felt like belonging to other paper. I recommend authors work in creating a more coherent story
2a) I found the discussion on Multi-Head OT unjustified and even a bit misleading. The Authors refer to some NLP papers, like arguing OT plays a role there. But none of these papers have any OT at all. The analogy of  "softmax for rows" is not convincing as this is simply a softmax applied many times. There is a world of difference between that and the result of sinkhorn algorithm, but the narrative seems to downplay the actual difference between them. I recommend the authors elaborate more on this connection, because otherwise it is hard to follow (and the subsequent results).
2b)Results on translation seem impressive (Table 2), but raise a concern. Why would your method outperform Sinkhorn if it is only approximation? is it perhaps the result of randomness? since an explanation of this phenomenon is missing I am led to believing. Authors should improve the exposition of the baseline "original". Why does full Sinkhorn does better than original?. In summary, I think authors should improve the discussion about the validity/significance of their empirical results, highlighting the regimes when they are supposed to express and when they are not.
2c)The main figure is Fig 2. I recommend authors build on this and expand those results so it is clear when their method is better and when it is not
review_title: Interesting paper and potentially significant.But theory is lacking, and experimental section can be improved

Decision: Reject