Compressed Online Sinkhorn

We appreciate your thorough review of our paper, and your feedback has been very valuable to us. We've addressed each of your points:

The authors do not discuss the performance of the algorithm in high-dimensional situations.

As mentioned above, we have clarified the issues with dimension when applying QMC-based Fourier method and explained the dimension dependence of the error bound. Asymptotically, the compressed online Sinkhorn can be more efficient. It is more difficult however to get into the asymptotic regime with the dimension $d$ is high.

However, there is a trade-off between accuracy and speed. According to assumption 4, the smaller the value of $m$, the faster the algorithm but the larger the error. The article seems to lack a detailed discussion on this matter, such as how to choose an appropriate batch size $m_t$ when solving actual OT problems.

We made some changes to Assumption 4, please check the new version. The choice of $m_t$ depends on the compression algorithm, such that Assumption 4 holds. The purpose of this assumption is that the compression error does not exceed the online Sinkhorn error in Algorithm 1, and we focus on the overall efficiency of the compressed algorithm. This allows for an increased error if there is sufficient reduction in computational effort to allow more iterations. This is now shown more effectively in the numerical experiments, where we ensure the error in the objective for the different algorithms match in the Figure 2.

The experimental sections lack the application of the algorithm on real-world data and more complex distributions.

Thanks for this valid point. This work is a first attempt at a compression method and the improvements are mainly in the asymptotic regime and lower dimensional setting. As future work, we plan on refining this by investigating adaptive choices of the parameters to enhance the fast transient behaviour in the error bound, making the algorithm more competitive for real-world data.

Thank you for your thorough review of our paper. Your feedback has been invaluable to us. We've addressed your points:

The experiments are done in settings of very low dimensionality. For the one of greater dimension (d=5), the uncompressed method starts to look quite better. I wonder if what I mentioned above regarding the uncompressed method working better and better with increasing dimension is a general trend.

We have clarified the issues with dimension when applying QMC method. Asymptotically, the compressed online Sinkhorn can be more efficient. It is difficult however to get into the asymptotic regime due to the small contraction rate ($\kappa\approx 1$) and available compression methods.

Thank you for your valuable feedback on our paper. Your insights have been very helpful in refining our work. We have made the following adjustments:

The constant $\kappa$ and the fact that it is at most $1$ are explained for the first time

A definition $\kappa = 1-\exp(-L\text{diam}\mathcal{X})$ has been added to the sketch proof of Theorem 1.

I believe the Lipschitz constant in Lemma 4 (with the notation employed) should be $L$, or maybe the formula for $T_{\beta}$ is missing a $1/\epsilon$ factor in the exponent.

This is true, we have missed out an $\epsilon$ in $T_{\mu}$. Please see the updated definition of $T_{\mu}$ before Lemma 4, thanks for pointing it out.

The last equality in the first math display in page 13 should probably be an upper bound.

Sorry about the confusion, it is defined in Lemma 7 that $M(x)=\int_y\exp((f^*(x)+g(y)-C(x,y))/\epsilon)\mathrm{d}\beta(y)$ and this equality is a simplification of the notation.

Thank you for your valuable review of our paper. We've addressed each of your points:

On the negative side, I had a hard time appreciating the five different assumptions made in the paper. I couldn’t quite tell whether they were necessary or they were made as a matter of convenience.

Assumption 1 on the cost regularity is needed for the OT problem to have a solution. The stepsize choices in Assumptions 2 are fairly standard for SGD. Assumption 3 provides criteria for the batch size in relation to the accuracy of the Monte Carlo method. We have added further commentary on the assumptions in the text.

The original Assumptions 4 and 5 are made together to ensure that the additional error is limited to $O(t^{b-a})$ and are consistent with the Online Sinkhorn error; please see Section 3.3 for the change we made to these assumptions.

Also, the paper is written in a way that makes it only accessible to people who are familiar with previous work (and not for folks who may have a good understanding of the optimal transport problem but lack familiarity with online Sinkhorn). I’m still not able to fully appreciate the result and understand within the landscape of existing algorithms (including time, space and sample complexities etc) for approximating continuous optimal transport. A discussion on this would be good.

We have added content in Section 3.1 and discussed the motivation for online Sinkhorn with compression.