Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper focuses on the so-called 'sharp Sinkhorn distance', which can be read as between the Wasserstein distance (without regularization) and the vanilla Sinkhorn divergence. The main contributions are two-fold: (i) the authors propose an L-BFGS algorithm to optimize the dual objective function of the Sinkhorn divergence leading to a stable transport plan (ii) an analytic form of the gradient of the shape Sinkhorn with respect to the input matrix is given. Some numerical experiments to corroborate the theoretical finds are illustrated on synthetic and real datasets.
strength_and_weaknesses: **Strength**
- LBFGS algorithm to optimize the dual objective function of the Sinkhorn divergence.
- An analytic form of the gradient of the sharp Sinkhorn with respect to the cost function.

**Weakness**
- The authors argue that the transport plan resulting from the L-BFGS algorithm is stable compared to ones from vanilla /stabilized Sinkhorn iterations. For me, this comparison is not fair, since it is only visually; it is mandatory to establish a theoretical result or an extensive empirical study showing this gain of stability. I mean one can show that the Frobenius norm (or any matrix norm) between the LBFGS plan and the unregularized plan is less than the vanilla Sinkhorn plan and the unregularized plan. Alternatively, one can investigate the difference between the objective dual function.
- The motivation behind calculating the gradient cost should be highlighted. 
- The numerical experiments on real data are limited.
clarity,_quality,_novelty_and_reproducibility: - I thank the authors for joining the code of the numerical experiments. Reproducibility is guaranteed. 
- The paper is clear and easy to follow. 
summary_of_the_review: Overall, the paper lacks some theoretical results or an extensive numerical study to prove the stability of the proposed LBFGS algorithm. 

**Superlative phrases**

In the core of the paper, I noticed that there are lots of superlative phrases. I am wondering if this fact is scientifically acceptable. 
- Abstract: "superiror performance"
- Page 8: "enjoys superior computational efficiency"
- Page 8: "huge advantage of a closed-form"
- Page 8: "proposed algorithm is the most efficient one"
- Page 9: "highlights the value of the proposed method"

**Typos**
- Page 2: "The optimal solution to (1)" --> "An optimal solution to (1)". Problem (1) could have many solutions.
- Page 2: "satisfies some suitable conditions" --> Add a reference.
- Page 3: "diagonal matix" --> "diagonal matrix".
- Page 5: in Theorem 2: the norm $\||{\gamma^*}\||$ is not specified; is it the $\ell_2$-norm? or $\ell_\infty$-norm? etc.
- Page 6: in Theorem 4: the matrix $D$ is not defined.
- Page 9: "methods achives" --> "methods achieves"
- References: "wasserstein" --> "Wasserstein"
- References: "sinkhorn" --> "Sinkhorn"
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides an analytic overview of the ``sharp Sinkhorn loss'' and its derivatives with respect both the input weights and the cost matrix (that typically depends on the input locations). Formally, given two discretes probability measures $\mu = \sum_i a_i \delta_{x_i}$ and $\nu = \sum_j b_j \delta_{y_j}$, and a cost $M = (|x_i - y_j|^2)_{ij}$ (or actually any other expression), the considered loss reads

$$ S(M,a,b) = \braket{T^\star, M} $$

where

$$T^\star \in \mathrm{argmin} \braket{T, M} - \eta h(T), $$

where $\eta > 0$ is a regularization parameter, $h$ denotes the entropy function, and the minimization is performed over the transportation polytope between $\mu$ and $\nu$ (that, in this discrete setting, only depends on $a = (a_1,\dots, a_n)$ and $b = (b_1,\dots, b_n)$). A well-known fact is that $T^\star$ can be computed (or at least, estimated) by running the Sinkhorn algorithm, an iterative fixed-point procedure. 

In applications (especially in generative models), it is often needed to compute gradients of $S$ with respect to $a,b$ and/or $M$. However, the latter is typically obtained via ``unrolling'' the iterations of Sinkhorn (via automatic differentiation). In contrast, this work computes $T^\star$ relying on a L-BFGS approach instead of the usual iterative loop. 

While using L-BFGS to get $T^\star$ is not entirely new, this paper has the following main contributions : 
- They study precisely the analytical behavior of the L-BFGS algorithm. The main takeaway are that convergence rates are (asymptotically) the same (i.e. geometric convergence), but the L-BFGS approach can be provably stable. This is an advantage over the standard Sinkhorn loop, and while unstability of the Sinkhorn loop is typically handled by performing iteration in log-domain, this comes at the price of computational efficiency. Here, the proposed approach gets the best of both world, being stable while remaining efficient. 
- An analytic expression of $\nabla_M S(M, a,b)$ has been derived, allowing "direct" differentiation rather than unrolling the iterations when---for instance---training a generative model.
- Showcase their approach through some numerical experiments. 
strength_and_weaknesses: ## Strengths

This is a solid work overall. I particularly appreciate that algorithmic aspects (convergence, stability) are supported by precise theoretical results (and not just empirical ones / informal intuition). 
I also think that the main idea conveyed by the paper may be impactful when it comes to use OT in ML tasks. 

## Weaknesses

- My main concern is that, in some sense, focusing on the loss $\braket{T^\star, M}$ feels somewhat ``outdated''. While it is the seminal loss proposed by Cuturi in 2013, many variants/improvements have been considered since. In particular, I would think that the so-called _Sinkhorn divergence_ [1,2,3] have taken the lead when it comes to introduce OT-based losses in ML. While I guess that a vast majority of this work holds/adapts to that setting, I think it would have been arguably better to focus on it. If there is a precise reason to focus on $\braket{T^\star, M}$ rather than the Sinkhorn divergence, this should be discussed in the paper. 
- One may argue that, although fairly convincing, the experimental section is not ``groundbreaking'' 

## Complementary comments/suggestions/questions

- I think that few statements in the introduction should be made more precise. For instance, "the computational cost of OT quickly becomes formidable" --> give the precise complexity; similarly, it would be nice to recall what is the best theoretical complexity known for the Sinkhorn algorithm. 
- It is slightly inaccurate to talk about "**The** optimal solution to (1)" as it may not be unique (in contrast to those of (2), as highlighted after in the paper). 
- [minor suggestion] Of course, that is a matter of taste, but I think that using $\eta = \lambda^{-1}$ would alleviate notations and has become more standard in computational OT literature. That would disambiguate claims like "Sinkhorn-type algorithms may be slow to converge, especially for small regularization parameter" (here, one may think that "small regularization parameter" refers to "small $\lambda$", while if my understanding is correct, this should be understood as "small $\lambda^{-1}$"). 
- Formally speaking, I think that (5) is a _concave maximization problem_ (but of course this is equivalent to a convex minimization problem). 
- In Theorem 1, $s_v$ has not been defined if I am correct. 
- "exponentiation operation are more expensive than matrix multiplications", is that correct? I would expect term-wise exponentiation to be faster as it is $O(n^2)$ vs $O(n^3)$ overall (unless "matrix multiplications" refers to "matrix-vector multiplications", but even there I would expect the complexity to be at least similar). I also think that both operations can be efficiently performed on a GPU. 
- [question] In Theorem 1 and 4, what guarantee that $D$ is invertible (and that $\lambda_{\min}(D) \neq 0$)? I tried to quickly check the appendix but did not find any discussion on that topic (I may have missed it though). 
- [suggestion/question] In Theorem 4, it may be more "reassuring" to state/recall that the condition $\epsilon^{k_0} < ... $ is always met since $\epsilon^{(k)} \to 0$ (and is decreasing); assuming the rhs term is not $0$. Related to the above question, do we have any control on how long it takes for this condition to be satisfied? 
- In numerical experiments, it is observed that when the regularization parameter $\lambda^{-1}$ is too large, $S$ is a poor approximation of $W$ in sense that it does not go to zero in that setting. In my opinion, this is an additional argument in favor of using the Sinkhorn divergence $\mathrm{SkDiv}$: while for large regularization parameters these divergences will naturally differ from exact OT in general, one still has $\mathrm{SkDiv}(\mu,\nu) = 0 \Leftrightarrow \mu = \nu$ (and more precisely, they metricize the same topology as $W$ for any $\lambda$), so they may be more suited to study the expressiveness/convergence of generative models. 
- [typo] In the appendix, both section B.4 and B.5 are called "proof of Theorem 3". 

## References 

- [1] _On wasserstein two-sample testing and related families of nonparametric tests_, Ramdas et al.
- [2] _Learning generative models with sinkhorn divergences_, Genevay et al.
- [3] _Interpolating between optimal transport and mmd using sinkhorn divergences_, Feydy et al.
clarity,_quality,_novelty_and_reproducibility: ## Clarity

The paper is overall clear. Theoretical statement are precise and numerical experiments are well described overall. 

## Quality

I think this is a solid work overall. Few points remain to be discussed (see Weaknesses and Questions above). 

## Novelty

Though tackling an existing problem, the proposed analysis is new to the best of my knowledge. My main concern about novelty would rather be that the work may not be placed in the most "state-of-the-art" setting of computational OT. 

## Reproducibility

From a theoretical perspective, the claims are supported by detailed proofs in the appendix. While I could not proofread all of them, I checked the proof of Theorem 1 and did not identify major flaws. The following proofs looked convincing at first glance, though I obviously encourage the authors to carefully proofread the paper as the proofs are quite technical. 

On the experimental side, code to reproduce experiments has been anonymously provided and though not tested, I am fairly confident that one could reproduce the numerical results of the paper. Also, the fact that implementation is available in both PyTorch and Jax is a nice bonus. 
summary_of_the_review: I think this is a solid work overall, with potential impact for computational OT practitioners. Nonetheless, few details remain to be clarified/discussed in my opinion before fully supporting it.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to use L-BFGS algorithm to solve the OT problem by exploiting a loose condition in the Sinkhorn algorithm. They derive a formula to compute the derivative with respect to cost matrix of the transportation cost. Then they prove some results of the convergence of their proposed algorithm.

strength_and_weaknesses: Strength:

1. The paper presents some useful results (Theorem 1) of computing derivatives of the OT cost between two distribution with respect to the cost matrix. The results could be used in some important settings, i.e generative modeling.

2. The author also presents some theoretical results to support their arguments. More particular, the convergence rate of the objective function, bound of the derivative etc. Those results are presented in Theorem 2,3 and 4.

3. Emperical results show that the method work well and faster than other methods. 

Weaknesses:

1. Theorem 2,3 and 4 are helpful but not useful. In particular, index $I$ in Theorem 2 depends on the solution. The rate $r$ in Theorem 3 is unknown, it is supposed to be dependent on $\lambda$.  The same situation in Theorem 4, where $\sigma$, $C_S, C_v$ and $C_u$ are difficult to quantified as a function of the original parameters: the marginal distribution  $a$, $b$ and the cost matrix $M$. That makes it very difficult to compare the order of the complexities of this method and the Sinkhorn algorithm in order to answer the question if this method is faster because of its initialization or it has a larger step to the optimal value etc. Note that there are already some works [1] to show the linear convergence of the objective function of the Sinkhorn algorithm, but it does not improve the upper bound of its complexity [2]. 

2. Empirical results are limited to some toy examples and small data set (MINIST).

References

 [1] Vladimir Kostic, Saverio Salzo and Massimiliano Pontil. Batch Greenkhorn Algo- rithm for Entropic Regularized Multimarginal Optimal Transport: Linear Rate of Con- vergence and Iteration Complexity. Proceedings of the 39th International Conference on Machine Learning, PMLR 162:11529-11558, 2022.

[2] Dvurechensky, P., Gasnikov, A., and Kroshnin, A. Com- putational optimal trans- port: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm. In International conference on machine learning, pp. 1367– 1376, 2018.
clarity,_quality,_novelty_and_reproducibility: It is well-written paper, easy to follow.
summary_of_the_review: Results of Theorem 1 is useful in application such as generative modeling, but other results are not.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of entropy-regularized optimal transport (EOT). The authors advocate the usage of L-BFGS algorithm to solve the EOT problem instead of the popular Sinkhorn algorithm. They analyze the convergence of L-BFGS on EOT and demonstrate its better stability compared to the Sinkhorn algorithm. They also derive a closed form of the gradient of the Sinkhorn loss w.r.t the cost matrix, leading to efficient computation of the backward pass. Finally, we illustrate their results with numerical examples.
strength_and_weaknesses: **Strength:**
1. The problem studied is a highly relevant problem.
1. They provided a convergence analysis of the L-BFGS method on the EOT problem.
1. The advocated L-BFGS + analytic gradient is computationally more efficient than other methods with which they compare.
1. The paper is well-written and easy to follow.

**Major comments:**
1. The novelty of the paper is not super clear to me.
    1. As mentioned by the authors, using L-BFGS to solve the EOT problem is a known practice. One selling point of this paper is the convergence and stability analysis of this algorithm (Theorems 2 - 4). However, this seems to be a practice problem given that L-BFGS has been extensively studied in other (potentially broader) settings. Is the proof technique new? Moreover, why can you conclude $T^{(k)}$ does not underflow from (e)? Don't you need to prove a lower bound for $min T^{(k)}$?
    1. Cuturi et al. (2019) and Cuturi et al. (2020) consider gradients w.r.t data points. Since the cost matrix is constructed from $c(X, g_\theta(Z))$ in the generative modeling application, knowing the gradients w.r.t data points is enough to get the gradients w.r.t $\theta$. Can you also compare your approach with theirs?
    1. You missed an important reference on this topic [1].
1. The numerical experiments are not convincing. In particular,
    1. Fig. 2 does not provide a fair comparison. As mentioned by the authors themselves, one iteration of the L-BFGS algorithm is more time-consuming than one iteration of the Sinkhorn algorithm. Why not use a similar plot as in Fig. 3?
    1. In Table 2, what are the stopping criteria for each of the methods?
    1. In Sections 7.2 and 7.3, while the goal is to compute the Sinkhorn loss, the performance is measured in Wasserstein distance. This mismatch makes it difficult to evaluate the improvement. I would use the Sinkhorn divergence (Feydy et al. '19) instead since this value should decrease as well.
1. I would like to see the full algorithm of the advocated forward and backward passes with complexity analysis.

[1] Tianyi Lin, Nhat Ho, Michael I. Jordan. On the Efficiency of Entropic Regularized Algorithms for Optimal Transport. JMLR (2022).

**Minor comments**
1. The notation $\mu^{-}$ is a bit confusing. I would use $\mu^{-1}$ instead.
1. It would be better to define $s_v$ directly rather than $\tilde s_v$.
1. For matrices $M$ and $T^\star$, their tilde versions are not defined.
1. It would be interesting to know how the marginal constraints of $T^{(k)}$ change with the number of iterations in Theorem 3.
1. In Theorem 4, how large is $\sigma$ typically?
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow, and the authors provided code to reproduce their results. However, I have concerns about the quality and novelty of the work as detailed in my major comments in the "Strength and Weakness" section.
summary_of_the_review: The paper studies a relevant problem and provides some new insights. However, I have some concerns about the quality and novelty of the work as detailed in my major comments in the "Strength and Weakness" section. I thus recommend rejection.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose a closer look at the differentiation of what is has been called the "sharp" Sinkhorn divergence, which is equal to the dot product of the optimal regularized OT matrix with the cost matrix. This is essentially $\langle T^\star_\lambda(M),M\rangle$. The gradient of that quantity involves differentiating through an argmin, which is then naturally solved with what the authors call an "analytical differentiation". The authors then propose to revisit and study in depth L-BFGS to solve the dual OT problem. They benchmark this approach against vanilla log-Sinkhorn.

Reviewers have liked certain aspects of the paper, but have found some parts underwhelming, notably experiments, novelty, or, for instance, questioning the interest of focusing specifically on the "sharp Sinkhorn divergence". They are overall pushing for a reject.

In addition to the several actionable pieces of feedback provided by reviewers, I think that the authors should consider two aspects to improve their draft:

- I think the authors have to be more straightforward and say that the "analytical derivation" of the gradient of the Sharp Sinkhorn *is* just implicit function differentiation (mentioned in the proof, below Eq. 16). In fact, I fail to see any algorithmic difference between what is carried out in existing toolboxes, and/or the references cited, and what the authors propose. In particular, their analytical formula requires to solve, just like IFT, a linear system. It does not really matter whether the authors rewrite things slightly differently, or change notations. Ultimately, this all boils down to differentiating the dual regularized OT problem optimality conditions, something that is extremely standard at this point, and which has been used in several references. It will be difficult to sell that minor variant of IFT as a contribution in an ICLR paper in 2023, and blurs the overall message.

- The benchmark propose to compare sinkhorn and L-BFGS is not convincing. The authors choose data sizes $n,m$ to be 100~512, or even below in some experiments (Table 2,3 Fig 6). At that scale, the hungarian algorithm or the network simplex is probably faster than all baselines. Worse, for such sizes, the simple overhead of running objects/wrappers (or compiling in the case of jax code, if running jit) makes things extremely blurry. Those sizes are also irrelevant for practical use cases. To be convincing, this section should at the very least look at sizes of 5k and well above. This is 10x more than what the authors have spent their efforts on. More generally, one would expect such benchmarks to replicate settings (e.g. convergence tolerance, epsilon value, data distributions) that are used in real applications.
justification_for_why_not_higher_score: Experimental part is wrong. Presentation of results is misleading.
justification_for_why_not_lower_score: NA
Decision: Reject