Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This papers is concerned with a model that approximates optimal transport (OT) using the low-rank coupling/matrices. This model in itself has been proposed a couple of years ago and this paper aims at answering important theoretical questions such as approximation error with respect to standard OT and statistical rates of estimation. They introduce a "debiased" version of their estimation, similar to the one proposed for entropic OT and make the link with clustering methods. Their theoretical work is also complemented with additional tricks for improving the numerical efficiency of the method.

strengths_and_weaknesses: Although one can argue about the usefulness of the model studied by the authors, it is a good paper by its many theoretical contributions exploring the foundations of low-rank approximation of OT. Results are ranging from obvious, easy to non-trivial and the paper will be a reference for other research developments around this model.
Strengths:
- Paper is well written.
- Several meaningful theoretical results.
- So far I checked, the proofs are correct (I did not check proof of proposition 5).

Weakness: 
- See my question below: Authors must address my question below, if not I'll revise my rating accordingly.
questions: My main concern is about the results for statistical estimation. 

Propositions 4 and 5 is about a one-sided inequality, i.e. there is no absolute value in the left-hand side of Equation in Prop. 4, neither in Equation in Prop. 5. Note that a complete result on statistical estimation is really about both lower and upper bounds. However, the authors only give an upper bound, as written line 123.
Although I think it is true, I do not see how to get a lower bound. It is likely I may have missed a result in the paper showing that it is a simple consequence, and it was maybe obvious for the authors, and it would be meaningful to include it.

Can the authors clarify their result? 

As a side remark, it is rather borderline practice that the authors pretend to have a complete result on statistical complexity. 
Indeed they write after proposition 4: "This result shows that the estimation of LOTr,c is independent of the dimension and can be performed on general compact metric spaces."
However the result in its current form is only partial and thus one cannot claim anything on statistical estimation. Indeed, the fluctuations of the opposite quantity may be much larger and dependent on the dimension. This can happen in practice. 

So what am I misunderstanding here?

Others: 
- Is it possible to add the following result. If $\mu_n \to \mu$ for the weak-* topology then $LOT(\mu_n) \to LOT(\mu)$? 
- proof of proposition 1: the decomposition of pi line 423 in supplementary (btw, there is a typo there) should be explained a bit more. Is it a standard SVD?
- typos in the supplementary material can be corrected, line 480, line 494.

limitations: no particular comments.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The optimal transport (OT) is becoming more and more prominent in machine learning field, however, traditional algorithm such as the linear program has a slow computational speed. In the last decade the entropy-regularized OT (EOT) was proposed and the speed has been  improved a lot. This work studies the low-rank OT (LOT) which is an algorithm proposed by Scetbon $\textit{et al.}$ [2021] that has a promising linear time complexity by searching for the low-cost couplings with low-nonnnegative ranks. The rate of convergence and an dimension independent upper bound of the sample complexity are provided. Furthermore, a debiased version of LOT (DLOT) is proposed, ad the debiasing terms connect LOT to clustering methods. To improve the computation performance adaptive step size and better initializations are introduced, and the effectivenesses are empirically verified by experiments.
strengths_and_weaknesses: Strengths:
This paper extends the LOT work by Scetbon $\textit{et al.}$ [2021] and studies the theoretical and practical properties of LOT deeply in several aspects. Such complete investigation of an algorithm is essential for bringing in a member into the computational OT family. This work also proposes interesting ideas such as linking the low-rank transport bias to the clustering method, which may inspire other applications and benefit the machine learning community.

Weaknesses:
The naming for the variables and equations referencing labels are confusing, as a result, sometimes it is hard to follow. The clarity of this paper could be improved and the notations could be used in a more consistent way so the readers can understand the meanings of the plots and equations with less efforts. See questions below for more details.
questions: 1. The adaptive step size improves the convergence. The authors also suggest clipping the step size in the range of [1, 10] for most use cases. Could an explanation or evidence be provided to support this choice?

2. In Fig. 1, the notations are confusing. Could the authors choose the variable names more carefully so they are consistent with previous sections? Eg. $n$ is number of samples here and in a few places, but somewhere else $n$ represents dimension. Also, is the dimension $d$ the same as stated in line 203 or is it the dimension of the marginal? 

3. In Fig. 1, it seems that the DLOT values of larger $r$ are higher among all $d$ cases. Is there an intuition or explanation?

4. Several references of equations are mislabeled. Eg. in line 187, 192, and 252, in the main text the reference equations are (15) while in the supplements (16). Also, there is not eq. (15) in the main text. Please fix and make them consistent.

Minor errors:  
[1] Line 141-142: "...one obtained in Proposition in 4...", please remove a redundant "in".  
[2] Line 244: A typo: "...we show the iterates obtained by a gradient descent...", should iterates be "iterations"?
[3] Eq. (6): "$Diag$" should be "diag" instead.
limitations: There is no negative societal impact. The authors address the limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work advances the theory of low-rank factorizations for OT by studying the approximation error as a function of rank and the sample complexity of LOT. It additionally proposes the debiased formulation, DLOT, which is shown to interpolate between MMD and OT, and that it metrizes weak convergence. Additional connection to clustering is drawn and better practices of using adaptive stepsizes and better initializations are suggested. Experiments are done to support the claims in 2D synthetic examples as well as on the Newsgroup20 dataset.

strengths_and_weaknesses: This paper is well-written and easy to follow. Although the contributions are a bit all over the place regarding LOT, they are clearly stated and adequately justified.

On the theory side, the paper provides comprehensive bounds for approximation error and sample complexity while improving the bounds from previous results (e.g. Liu et al. 2021). Then the debiased formulation of LOT is shown to exhibit desirable properties similar to Sinkhorn divergence. The connection to clustering is interesting since it is specific to the low-rank approximation, something that full-rank versions cannot do. While I do not find any of the results surprising or groundbreaking, they are solid and much needed for future research on LOT.

The experiments section is short but verifies part of the theory. There are some missing experiments justifying the adaptive choice of $\gamma_k$ versus without adaptation. Parts of the figures and captions could be improved --- see detailed comments below.

A central question I have regarding the practicality of LOT: Is the computational benefit of LOT worth the introduction of nonconvexity and spurious local minima? I would hope to see more experiments (at least empirically) on demonstrating the benefits gained by low-rank approximation and advice on which $r$ to choose. It seems to me that LOT is only efficient when the ground cost matrix admits a low-rank factorization. In what applications is such condition met?

Comments:
- Line 99: "obtain next a control the approximation", missing "of"?
- Line 126: sample complexity shows promises since it does not depend on dimension - but wouldn't $||c||_\infty$ in Proposition 4 depend in the sense that in many applications the diameter of $\mathcal{X}$ could increase exponentially in $d$? Also as discussed in the paragraph below Proposition 4, $K_r$ could go to infinity.
- Line 187, Line 192: (15) does not exist. Do you mean (6)?
- Line 238: "we do not have access to the this", no "the" here
- Line 252: (15) should be (6)?
- Figure 1: which $r$ is used for the upper bound curve?
- Figure 4: what is the x-axis "operations"? Why do some curves not start at 0 on the x-axis?
- Figure 4: what is the takeaway message from the right figure?


questions: Please refer to my questions in the "Strengths And Weaknesses" section.
limitations: The author has addressed the limitations and future directions to take to advance LOT. Societal impact is not discussed but I don't think it's needed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides an enormous amount of theoretical analysis about low-rank OT: the convergence rate of low-rank OT to the true OT wrt rank parameter, sample complexity for estimating LOT; introduce debiased version of LOT which metrizes the weak convergence; bridge LOT with clustering methods. Practically, they propose a novel initialization to avoid the bad local minima.
strengths_and_weaknesses: Strengths:

This paper provides the rigorous theoretical analysis of low-rank OT: 

- the convergence rate of low-rank OT to the true OT wrt rank parameter, 

- sample complexity for estimating LOT is dimensional independent; 

- introduce debiased version of LOT which metrizes the weak convergence;

- LOT$(\mu,\mu)$ can be seen as a generalization of the k-means method

- Practically, they also propose a novel initialization to avoid the bad local minima.

Weakness:

- The example in Figure 2 is too simple. Swiss roll or two moons in figure 3.2 is more convincing.
questions: Question:

Figure 2, which stage is the middle two plots of Figure 2 in gradient flow? They seem to be in a very late stage of convergence, but a weird phenomenon is that the gradient flows of both DLOT and LOT exceed the target distribution firstly, and then come back. Especially when looking at those green arrows, they firstly point outside the moon, then point inside the moon. I think if you solve gradient flow correctly, it will not have this "exceed first and then pull back" process.

Typo: 

row 142 delete "in"

all the equation (6) is referenced as (16)
limitations: .
review_title: null

Meta-review: metareview: Overall: The paper focuses on advancing our knowledge, understanding and practical ability to leverage low-rank factorizations in optimal transport.

Reviews: The paper received four reviews. 4 accepts (all confident). It seems that there are several reviewers that will champion the paper for publication. The reviewers found the paper is clear and has a clean presentation. The findings are interesting. The authors have provided extensive answers to reviewers' comments, answering most of them successfully.

After rebuttal: A subset of the reviewers engaged in a consensus that the paper should be accepted.

Confidence of reviews: Overall, the reviewers are confident. We will put more weight to the reviews that got engaged in the rebuttal discussion period.
confidence: Certain
Decision: Accept