Many thanks for answering our rebuttal before the deadline
We are very grateful for your timely response. Here are a few more answers:
> **In the revision you must clarify that you talk both about statistical and computational complexities [...] This would be much clearer for the sentences where I thought it was unclear.**
Yes, we heard you on this, and we will emphasize more strongly this trade-off, starting with the abstract, that we can change as
*Recent works suggested that kernel-based OT [...] practice. In this paper, we propose [...]
To
*Recent works suggested that kernel-based OT estimators are more statistically efficient than plug-in OT estimators when comparing probability measures in high-dimensions [59]. However, this comes at a very steep computational price. These estimators are very costly, since their computation relies on the short-step interior-point method for which the required number of iterations is known to be large in practice. To improve on the scalability of these approaches, we propose in this paper a nonsmooth equation model for kernel-based OT estimation and show that it can be efficiently solved via a specialized semismooth Newton (SSN) method.*
and more generally amend the introduction and background sections accordingly.
> **I would also insist on being self-contained on SSN methods, then instantiate the kernel-OT case inside a theorem [...]**
We agree you, and we will provide in Section 2.3 a self-contained introduction to SSN methods that will be about half a page.
> **[...] Why can't we scale to more than 500 samples ? Compared to entropic OT which scales 'reasonably' for 10^4 samples on GPUs, this seems very limiting, and you do not seem to solve this issue. Could you contextualize in the paper if it could be solved, or if it is due to solving a different approximation of OT problem ?**
This is indeed due to the fact that kernel-OT targets a completely different approximation of OT problems:
- kernel-based OT solvers target a **functional** optimization problem, i.e. their solutions are directly dual potential functions that agree with prior smoothness assumptions (line 130).
- by contrast, the Sinkhorn algorithm is a discrete solver that computes a transport **matrix**, or dual potential **vectors**. While its outputs have been recently used to recover dual potential functions (as in [Pooladian+21]), this is mostly an interpolation, a smooth c-transform of pointwise potential values, inspired by semi-discrete OT, and not the result of a functional optimization (as done with RKHS in kernel based OT).
The approach by Vacher et. al was illustrated on a maximal number of 200 points. We propose experiments with 500 points. Our solver can scale reasonably (about 20 seconds) for 1000 points, but the IPM solver of Vacher does not, we will add this to the curves.
While we agree this is still a bit small, it does start to open up some possibilities, using e.g. mini-batch OT. We will discuss this explicitly in the paper, and expand on Remark 2.2
> **Side remark which I noticed from checking your paper, but entropic OT does not suffer curse of dimensionality, but like kernel-OT, the constant might depend exponentially in the dimension, see e.g. [1]. [...]**
A discussion on entropic OT vs. kernel-OT is provided in the **State of the art** section of Vacher et al [59].
We can add our summary of this: While the entropic OT rate you mention does indeed gives a $1/\sqrt{n}$ statistical dependency, this is only valid for a **fixed** regularization $\varepsilon>0$ level (i.e. statistical complexity assumes **regularized OT** between densities is the target ground truth). However, because that constant is dimensionality dependent, it will blow up exponentially fast to infinity as $\varepsilon\rightarrow 0$, if one wants to approximate the **non-regularized OT**. In that sense, entropic OT does not provide a dimension-free (event w.r.t. constants) way to compute non-regularized OT, and, more qualitatively, entropic OT can only make sense statistically for high regularizations (constant degrades exponentially fast). As $\varepsilon \rightarrow \infty$, one recovers the MMD complexity.
By contrast, Vacher et al's show that kernel OT does not suffer from such a blow-up. While their constants do depend exponentially in $d$, they are **fixed**, and the rate in $1/\sqrt{n}$ to target non-regularized OT is valid.
> **For this reason I decide to increase my score. However, I would not personnaly advocate for a complete acceptance, because the requested modifications might need a new reviewing process due to their importance.**
We are very grateful for your score increase. We believe that the modifications you have requested only target the background section, only with clarifications (Vacher’s methods computational/statistical tradeoff + brief background on SSN). We do not need to add new material or original contributions to satisfy your requests. We humbly request your trust on carrying out these modifications.