Expected Sliced Transport Plans

The introduction focuses on computational efficiency; however, I don't see any empirical results demonstrating this point. Because the datasets being used here aren't huge by machine learning standards, it seems important to be precise about what is meant by this claim.

Answer: We agree with the reviewer that this is a key point and that we need to emphasize it more clearly. For this reason, we have included the new Subsection 3.1 and Appendix C on the computational efficiency of our proposed method. Below is a brief overview of these arguments.

For the following analysis, let us consider two finite discrete probability measures on $\mathbb R^d$, $d>1$, concentrated at $n$ particles ($\mu=\sum_{i=1}^n p_i\delta_{x_i}$, $\nu=\sum_{j=1}^n q_j\delta_{y_j}$). The complexity of using the linear programming approach for solving the optimal transport problem between them is of order $\mathcal{O}(n^3\log(n))$. When using entropic regularization, the problem becomes easier to solve using iterative algorithms like Sinkhorn's algorithm, having complexity of order $\mathcal{O}(n^2 \log(n)/\lambda^2)$, where $\lambda$ is the regularization parameter (Dvurechensky et al., 2018, Altschuler et al., 2018), but introducing an approximation to the original problem.

When dealing with measures in the real line, by using sorting algorithms, we reach a complexity of order $\mathcal{O}(n\log(n))$. The proposed EST method has following computational complexity when considering $L$ slices or unit vectors $\\{\theta_l\\}_{l=1}^L$ in $\mathbb{S}^{d-1}$:

• For each one of the $L$ directions ($\\{ \theta_l \\}_{l=1}^L$), the slicing operation involves $\mathcal{O}(Ldn)$ operations to obtain $\theta_l \cdot x_i$ and $\theta_l \cdot y_j$ for $i,j \in [1,n]$.

• To compute the 1D plan $\Lambda_{\theta_l}^{\mu,\nu}$, for each $L\leq \ell\leq L$, we essentially need to solve a one-dimensional optimal transport problem (sorting problem), which is of order $\mathcal O(n\log(n))$. Thus, when considering all the slices, this step is of order $\mathcal O(Ln\log n)$.

• The lifting process that gives rise to $\gamma_{\theta_l}^{\mu,\nu}$ does not requires operations to be taken into account.

• The plan $\bar\gamma^{\mu,\nu}$ can be represented as an $n\times n$ matrix. The $(i,j)$-entry is given by $\sum_{l=1}^L\gamma_{\theta_l}^{\mu,\nu}(\{(x_i,y_j)\})$, requiring $L$ operations. Thus, the complexity of this step is $\mathcal O(L n^2)$.

• Finally, once we have $\bar\gamma^{\mu,\nu}$, for computing the EST-distance we require another $\mathcal O(n^2d)$ operations.

Thus, the complexity of computing the plan $\bar\gamma^{\mu,\nu}$ is $\mathcal O(L(nd+n\log n+n^2))$, or simply, $\mathcal O(Ln^2+Lnd)$, and that of the EST-distance is $\mathcal{O}((L+d)n^2)$. As it is generally the case, $n$ is much larger than $d$, so the computational complexity of both the EST-plan and the EST-distance is of order $\mathcal{O}((L+d)n^2)$.

Besides, in the following Figures (Fig.1 - Fig.2) we report the wall-clock times of the Sinkhorn algorithm, used for computing the entropic regularized version of OT (for different values of the regularization parameter $\lambda$), compared to the proposed EST distance (calculated with different numbers of slices $L$) between two $N$-sized empirical distributions. The only difference between the two figures is the scale used for the horizontal axis, which has been adjusted for visualization purposes.

We have added this discussion and figures in the new Subsection 3.1 and in the Supplementary Material (Appendix C).

"Traditional models scale cubically" What methods are being invoked here?

Answer: We thank the reviewer for this comment and we will clarify this issue in the revised version as follows: "Traditional models scale cubicallyTraditional OT solvers for discrete measures typically scale cubically with the number of samples $n$ (i.e., the support size) (Kolouri et al., 2017, Peyre and Cuturi, 2019). Precisely, when using linear programming, the computational complexity is $\mathcal{O}(n^3\log(n))$."

"However, the number of iterations required for convergence typically increases as the regularization parameter decreases, which can offset the computational benefits of these methods." I don't understand this critique.

Answer: This is a good point. Precisely, the complexity of Sinkhorn method is of order $\mathcal{O}(n^2 \ln(n)/\lambda^2)$, where $\lambda$ is the regularization parameter in the regularized version of OT
Dvurechensky et al., 2018, Altschuler et al., 2018. Thus, $\lambda$ decreases, and the number of iterations and hence the corresponding operations increases.

We thank the reviewer for their comment. We have included this clarification in the new version of the paper.

Just a minor point. I would reverse the orders of the rows in Figure 4, so that rows with the best quality are closer to the original OT interpolation.

This is a great suggestion, and we have updated the Figure in the paper accordingly.

I agree with "A metric offers a precise and consistent way to measure the "distance" between two elements in a space." My point was that the purpose of proving the metric properties in the paper was not clear. Why is it important that "the resulting transportation plan be used to define a metric between the two probability measures"? What if it's a pseudo metric? What applications of the plan will not hold if it doesn't define a metric? I understand the benefits of a true metric but I didn't find the benefits demonstrated in the paper.

The reviewer raises a fantastic point.

One of the main motivations for our paper originates from a statement highlighted in Mahey, 2023: although Sliced-Wasserstein-like distances are attractive due to their computational efficiency, proper metric properties, and ability to metricize weak* convergence, they do not provide an optimal transport (OT) plan as classical Optimal Transport theory does (i.e., when computing the Wasserstein distance, one also obtains the corresponding optimal coupling). Thus, one of our goals was to contribute along these lines by developing a technique that yields both a metric and a coupling between probability measures in $\mathbb{R}^n$. Furthermore, we proved that the new metric induces a topology equivalent to that of weak* convergence (in the case of discrete probability measures).

Thus, we establish the metric property of our Expected Sliced Transport framework to ensure theoretical rigor and demonstrate that, while prioritizing computational efficiency in constructing the transport plan, we preserve the core theoretical benefits of optimal transport, which is its metricity.

The OT framework simultaneously provides 1) an optimal transportation plan that establishes correspondences between the two input measures or between samples in empirical settings and 2) a metric that quantifies the distance between the input measures. Our proposed framework adheres to this paradigm, offering a transportation plan that defines a metric between the input measures. The reviewer raises an interesting question: beyond theoretical rigor, what are the practical advantages of obtaining a transportation plan that defines a metric rather than one that merely provides a pseudo-metric?

The practical benefits are implicitly demonstrated in the classification experiments presented in the paper, as well as in the additional results provided during the rebuttal on ModelNet40. Consider the transportation plans obtained via entropy-regularized OT (using the Sinkhorn algorithm). In our classification experiments, we leveraged the core idea of Linearized OT to utilize the transportation plans for classification tasks. In this setting, where $\lambda$ is the entropy regularization coefficient, we observe the following behavior:

• As $\lambda \to 0$, we recover the standard OT plans, which yield the highest classification accuracy.
• As $\lambda$ increases, the classification accuracy progressively declines.
• In the limit as $\lambda \to \infty$, the transportation plan approaches the outer product of the input measures, providing no useful information for distinguishing between classes.

This demonstrates that the transportation plans maintaining metric properties (as achieved when $\lambda \to 0$) are crucial for preserving the discriminatory information needed for classification. Below, we reiterate the classification results reported in the paper, which support our argument.

Interestingly, a similar observation can be made for our proposed method as a function of number of slices. Our proposed method is a metric when we have expectation on slices, i.e., as $L\to\infty$. We see that our method performance also increases as we approach having a plan that defines a true metric.

These numerical results show the superiority of metric-inducing transport plans. We postpone a more rigorous analysis of applications that require metric-inducing transport plans for future work.

3. Second question, "can this plan be used to define a metric between the measures". Maybe the interpolation experiment shows a little bit of the usage of the metric properties. Other than that, from reading this paper, I don't see the reason of studying the metric properties.

Answer: The second question highlighted in the Introduction of the paper reads: "can the resulting transportation plan be used to define a metric between the two probability measures?"

The definition of our proposed discrepancy is provided in Definition 2.6, and its metric properties are outlined in Theorem 2.10. We have now made this explicit in our second bullet point contribution.

The importance of having a metric in mathematics and its applications lies in the structure and rigor it provides for comparing elements—in our case, comparing probability measures in $\mathbb{R}^n$. A metric offers a precise and consistent way to measure the "distance" between two elements in a space.

From a theoretical standpoint, defining a metric endow the probability space with a topological structure. This structure allows us to rigorously work with foundational concepts such as convergence and continuity, which are essential in both mathematical theory and practical applications.

From a machine learning perspective, pairwise distances in a dataset are crucial for tasks such as manifold learning, constructing graph structures, dimensionality reduction, and designing kernel methods (e.g., kernel Support Vector Machines). A well-defined metric ensures that these algorithms are consistent and meaningful, which is essential for reliable optimization and learning.

The empirical results are weak because the dataset is too simple to prove its usefulness in real applications. They're at most for proof of concept.

Answer: We agree with the reviewer that our experiments are conducted on simple datasets. Our goal was to keep the paper's message clear and focused on our theoretical findings, avoiding additional complexities that more intricate datasets might introduce. We also agree with the reviewer that including experiments with more complex data would greatly enhance the paper. To address this, we have added Appendix D, where we further demonstrate the efficiency of our proposed method for the classification task using ModelNet40, a widely used benchmark dataset in 3D computer vision and geometric deep learning. In Figure, we compare the accuracy and computation time required for performing a 1-NN classifier using distance information provided by three different methods: OT, entropic regularization via the Sinkhorn algorithm, and the proposed EST method.

Besides, as mentioned earlier in this rebuttal, we have revised our last listed contribution for clarity, and the updated version reads as follows: "Illustrating the potential applicability of the proposed distance and transport plan, with a focus on interpolation and classification tasks." Using the wording "potential applicability," we acknowledge that our experiments serve as proof of concept.

On another note, the experiments presented in Section 3.4, which demonstrate the equivalence between the topology induced by our new metric and the topology given by the Wasserstein distance (and, consequently, the weak* topology), are rigorously proven in the appendix for discrete probability measures with finite or compact support.

As stated in our paper, our ultimate goal is for the theoretical insights and experimental results presented here to inspire the development of efficient transport-based algorithms in machine learning and beyond.

Questions:

(1) In 144: "As a result, it is more convenient to work with lifted transport plans." Is plan the emphasis of the sentence? Instead of maps? And the difference between, as implied in this paper, is that maps apply to the support and plans apply to labels?

Answer: We thank the reviewer for their thorough reading.

The word "convenient" should be replaced by "appropriate". We will address this is the revised manuscript.

Our emphasis in this sentence is that using transport plans is more appropriate because transport maps may not always be well-defined. Specifically, transport maps might not be defined on the support of the reference measure $\mu^1$. (However, as they are expressed in terms of permutations $\tau_\theta$ and $\zeta_\theta$ in the symmetric group, which operate on labels $\{1, \dots, N\}$ they can be defined on maps on those labels $\{1, \dots, N\}\mapsto \{1, \dots, N\}$).

Intead, the lifted transport plans $\gamma_\theta^{\mu^1, \mu^2}$ are measures supported on $\{(x_i, y_j)\}$, where $\{x_i\}$ is the support of $\mu^1$ and $\{y_j\}$ is the support of $\mu^2$. Additionally, these lifted transport plans can be defined for measures supported on differing numbers of points, which transport maps alone cannot always accommodate.

I appreciate the detailed response of the authors. The revised version represents the computational complexities of the algorithms clearly and addresses the concern properly. I have raised the score.