Kernel Quantile Embeddings and Associated Probability Metrics

We thank the reviewer for their thoughtful comments and for recognizing the desirable properties established for KQEs and the connections drawn between KQDs and Wasserstein distances. We address the points raised below and hope that, in light of these responses, the positive feedback from other reviewers, and new experimental evidence provided in response to other reviewers (particularly kcy5), the reviewer may consider raising their score.

I. “it remains unclear what specific problem KQEs address that cannot be handled by existing quantile estimation methods or previous kernel mean embeddings”.

This question is two-part: (1) value compared to “previous kernel mean embeddings” and (2) value compared to “existing quantile estimation methods.” We address these separately.

1. For benefits compared to kernel mean embeddings, and specifically when they are not enough, we refer to point (IV) in response to dCj7. In a nutshell, KQDs require weaker conditions for a kernel to be quantile-characteristic than for mean-characteristic kernels, which can be difficult to establish beyond Euclidean domains. Additionally, we show in a number of experiments that even when a mean-characteristic kernels is a good choice, the KQD can still outperform MMD approximations of similar cost, highlighting its practical advantage.
2. As to benefits compared to existing quantile methods: Sliced Wasserstein (which compares all quantiles in [0, 1]), is (1) specific to $\mathbb{R}^d$, and (2) does not take advantage of the flexibility and rich non-linear representations inherent to kernel methods—in contrast to KQD. This was pointed out in Connection 1,2: SW is KQD with the linear kernel $k(x, x’)$. The consequences of this are evident in the experiment outlined in point (III) in response to dCj7: even in $\mathbb R^d$, KQD with the Gaussian kernel $k(x, x’)$ outperforms Sliced Wasserstein, due to the Gaussian kernel’s greater expressiveness compared to the linear kernel.

II. Procedure for Hypothesis Testing and Threshold Selection:

We use a permutation-based approach with 300 permutations to estimate the null distribution of the test statistic and determine the threshold, ensuring proper Type I error control ([1]). This procedure will be added as an algorithm in the camera-ready version.

[1] Erich Leo Lehmann, Joseph P Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 1986.

III. Setting the Density Function $f_\nu$ in Algorithm 3.1:

The density function $f_\nu$ is the measure over the quantile levels. We use the uniform $\nu$ over $[0, 1]$ in our experiments, which corresponds to equal weight for all quantiles, $f_\nu \equiv 1/n$. We will add a note to Algorithm 1 for clarity.

IV. Numerical Comparison with MMD based on Other KME Approximations:

As the reviewer notes, there are several efficient KME methods currently available, and no single approach has emerged as definitively superior. The multi-diagonal approximation chosen in this study serves as a common, strong, and interpretable benchmark, supported by both general and test-specific theoretical guarantees ([2]). While a comprehensive comparison of all existing methods falls outside the scope of this paper, we did conduct additional experiments as requested.

In particular, as requested, we compared the KQD with the following (at matching cost)

1. the Mean Embedding (ME) approximation of MMD from [5] (which was identified as the best-performing method in their numerical study) and
2. the Nystrom-MMD method from [3].

The results are presented in https://pdfhost.io/v/qLDRyBQawp_nystrom_vs_ME. ME performs at the level of MMD-multi, while Nystrom has extremely high Type II error—likely due to sensitivity to hyperparameters. This result was consistent, as we also observed poor performance of Nystrom-MMD in the following simple minimum-distance parameter estimation task, illustrated in https://pdfhost.io/v/KhHzg7UPsY_par_est . The results are over 1000 runs and show high variance of Nystrom-MMD.

Although we could not complete the BCD-Fast [4] comparison in time, it is noted that the method is primarily advantageous for its robustness to outliers, a feature not explicitly addressed in our study. We are happy to complete this experiment for the final paper.

[2] Schrab, A. (2025). Optimal Kernel Hypothesis Testing (PhD thesis, UCL).

[3] Chatalic A, Schreuder N, Rosasco L, et al. Nyström kernel mean embeddings. ICML.

[4] Lerasle M, Szabó Z, Mathieu T, et al. Monk outlier-robust mean embedding estimation by median-of-means. ICML.

[5] Chwialkowski K P, Ramdas A, Sejdinovic D, et al. Fast two-sample testing with analytic representations of probability measures. NeurIPS.

We appreciate the reviewer’s feedback. In response, we have provided additional experimental results, clarified the role of $f_\nu$, and explained the motivation behind KMEs and our testing procedure. We would appreciate it if the reviewer considered raising the score.

We thank the reviewer for their thoughtful review and for recognizing the soundness and novelty of our contributions, including generalizing KME-derived distances and kernelizing Sliced-Wasserstein distances. We address the key comments below.

I. Additional Applications:

KQD is a general-purpose probability metric, applicable to many problems like conditional independence testing, causal inference, reinforcement learning, and generative modeling. Among the many possible applications, our focus has been on two-sample hypothesis testing to benchmark the proposed distances in a controlled and interpretable setting, which is commonly used in the literature. In addition, we are working on applying KQD to the task of parameter estimation in simulation-based inference. A toy version of the experimental setup is presented in point IV in response to u7Px.

II. Why isn’t $\gamma$ uniform?

As pointed out in footnote 2 on page 5, the uniform/Lebesgue measure or standard Gaussian measure cannot be defined on infinite-dimensional spaces ([1]). Anticipating an infinite-dimensional RKHS, we propose a (projected) Gaussian measure, which is a standard approach in the inverse problem literature (see [1]). We emphasize that when $X=\mathbb{R}^d$, the kernel is linear, and $\gamma$ is uniform over the unit sphere, KQD matches Sliced Wasserstein (Connection 1). A more general version, when the kernel is non-linear but induces a finite-dimensional RKHS, the KQD can be connected to the Generalised Sliced Wasserstein distances ([2]). We will include this discussion.

[1] Stuart, A. M. (2010). Inverse problems: a Bayesian perspective. Acta numerica.

[2] Kolouri, S. et al (2019). Generalized Sliced Wasserstein distances. Advances in neural information processing systems, 32.

III. Comparison with SW Distances

We now extended the power decay experiment to include SW distances, with directions sampled uniformly or from $(P_n + Q_n)/2$ projected onto the sphere. Results in https://pdfhost.io/v/FsnNBjRnJa_kqd_vs_sw show KQD significantly outperforms SW---since Gaussian kernel is more expressive than linear kernel (Connections 1,2: SW is KQD with linear kernel).

IV. “when is using non mean characteristic kernels useful”

KQDs require weaker conditions to be quantile-characteristic, as shown in the Laplace vs. Gaussian experiment. While mean-characteristic kernels are well understood for bounded translation-invariant kernels on Euclidean domains ([3]), beyond this, it’s hard to establish whether a kernel is mean-characteristic. For example, many graph kernels are not characteristic ([4]). Deep kernels ([5]), or any transformed kernel $k(T(u), T(u’))$, where $T$ is a non-injective map, offer examples of non-characteristic kernels.

[3] Sriperumbudur, B. K., et al (2011). Universality, Characteristic Kernels and RKHS Embedding of Measures. JMLR.

[4] Kriege, N. M., et al. (2020). A survey on graph kernels. Applied Network Science, 5.

[5] Wilson, A. G., et al. (2016). Deep kernel learning. AISTATS.

V. Figure 2 Clarification:

We apologize for the omission. Figure 2 should be referenced in Section 3.2 after defining $\tau^2$ to illustrate how the integrand varies for different directions. We will amend this and provide a clearer explanation.

VI. Reference Missing in Appendix C.5:

Thank you for pointing this out. We will add reference [6]. [6] Kukush, A. (2020). Gaussian measures in Hilbert space. Wiley.

VII. MMD Performance in Image Dataset Experiments:

We will clarify that the goal of the experiment was to demonstrate that KQD outperforms MMD approximations with matching cost, and when MMD outperforms KQD, the centered KQD offers MMD-level performance. Additionally, in response to kcy5 (I.(2)), KQD with uniform $\mu$ outperforms MMD on the CIFAR problem, and we are exploring this further.

VIII. Connection to Median and Variance-Based Extensions of KMEs:

We are happy to elaborate. Longer response with review of the methods: https://pdfhost.io/v/t2rYgcDSLS_kernel_quantile_embeddings_2_25

Kernel Covariance Embeddings (KCE) is the 2nd-order moment of $k(X, \cdot)$, while KME is the 1st-order moment. KCE exists iff KME for $k^2$ exists; and, $k$ is covariance-characteristic iff $k^2$ is mean-characteristic. The divergence between KCEs can be estimated at $O(n^3)$ due to the need to do eigenvalue decomposition, while KQE comes with a practical Monte-Carlo estimator.

The median embedding is the geometric median of $k(x, \cdot)$ in the RKHS, minimizing the $L_1$ distance. While it exists for separable Hilbert spaces, it requires iterative algorithms for estimation and has $O(n^2)$ complexity. The median-characteristic property hasn’t been explored, and the relation to 1D-projected quantiles remains unclear. Further research into geometric median embeddings is needed.

We believe these revisions address the reviewer’s concerns and improve the clarity of the paper. Thank you for your constructive feedback.

We thank the reviewer for their positive feedback on our work. We appreciate the recognition of our theoretical contributions, the rigor of our proofs, and the relevance of our evaluation criteria. We are also glad the reviewer found our near-linear Monte Carlo estimator promising for large-scale data. Below, we address specific comments, and return additional experiments suggested.

I. Further exploring the choices for weighting measure $\nu$, measure on the sphere $\xi$, reference measure $\mu$.

Thank you for this insightful suggestion.

1. $\nu$: We conducted experiments on the Galaxy MNIST and CIFAR datasets, varying $\nu$ from up-weighing extreme quantiles to down-weighing them. Results are in https://pdfhost.io/v/jeaYtK5X2Y_varying_nu , where triangle "/\” indicates up-weighting, and reverse triangle “\/” indicates down-weighting. For Galaxy MNIST, down-weighting extremes improved test power, whereas for CIFAR, up-weighting extremes worked better. Uniform weighting of the quantiles remained a good choice. This suggests that tuning $\nu$ beyond the uniform is problem-dependent and can enhance performance. The difference likely arises from the nature of the problems: CIFAR datasets, where samples are expected to be similar, benefit from emphasising extremes, while Galaxy MNIST, which has fundamentally different galaxy images, performs better when “robustified,” i.e., focusing on differences away from the tails. Exploring this further presents an exciting avenue for future work.
2. $\mu$: The reference measure in the covariance operator serves to “cover the input space” and is typically set to a “default” measure—for $\mathbb R^d$, typically the standard Gaussian. We considered $(P_n + Q_n)/2$ to stick to the most general setting, when no “default” is available—only $P_n$ and $Q_n$. We now compare this choice against (i) standard Gaussian scaled by IQR/1.349 , where IQR is the interquantile range of $(P_n+Q_n)/2$, and 1.349 is the interquantile range of $\mathcal N(0, 1)$; (ii) a uniform measure on $[-1,1]^d$, scaled by IQR. Results in https://pdfhost.io/v/wtc2mgbFGU_varying_mu show performance superior to MMD for the standard/uniform $\mu$. This is a valuable finding, we will be performing further analysis.
3. $\xi$: Varying $\xi$ on the sphere in inf-dim spaces is extremely challenging due to the complexity of both theoretical definition and practical sampling (no uniform or standard Gaussian measure can be defined on an infinite-dimensional space). To the best of our knowledge, no practical alternative has been proposed.

II. Conditional Quantile Embeddings and Independence Testing as Future Work:

The population-level embedding of $P(Y|X=x)$ will be defined in the same way as a quantile embedding: for every $x$, we have a standard quantile embedding. Estimating conditional quantiles requires learning a mapping from $x, u, \alpha$ to \rho^\alpha_{u \\# P}, a complex task beyond the scope of this paper; however, given the likely smoothness of this mapping in $x, u, \alpha$, it is reasonable to expect that it should be possible to develop a practical method.

Independence testing can be framed as a two-sample testing problem (e.g., [1, 2]). However, a thorough investigation, comparable to that in [1, 2], is necessary to develop this approach rigorously. We leave this exploration for future research.

[1] Gretton et al., 2008. A kernel statistical test of independence. NeurIPS.

[2] Doran et al., 2014. A permutation-based kernel conditional independence test. UAI.

III. Clarifying “Cramér–Wold in RKHS” in Early Paragraphs

We will add a clarification.

IV. Experiment on Centered e-KQD for Mixture Distributions

We thank the reviewer for their suggestion. However, we would like to emphasise that moments on the input space map highly non-linearly to the RKHS. As a result, shifts in moments on the input space translate non-trivially to the outcome of the experiment, breaking the interpretability of results. We will instead focus on constructing an example where moments in the kernel features space (instead of the input space) vary. We will aim to identify these before camera-ready.

IV. “Could there be issues if X is not connected or if k is unbounded?”:

Boundedness: we highlight that boundedness is not required to define KQD as a probability metric. This contrasts with MMD, which requires the kernel to be bounded in order to be defined over all probability measures—due to the need to take an integral to obtain the mean (see “Why bounded kernels?” in www.jmlr.org/papers/volume24/21-0599/21-0599.pdf).

Connectivity: KQD remains a valid probability metric for completely regular Hausdorff spaces, including disconnected spaces like totally ordered sets.

We thank the reviewer again for their insightful feedback. We have addressed your concerns by providing additional experimental results and elaborating on future work in conditional independence/CMEs, and therefore would appreciate a raise in score.

We thank the reviewer for their thoughtful comments and positive evaluation of our work. We appreciate the recognition of the originality of using quantile embeddings, the clarity of our presentation, and the relevance of our contribution to the ICML community. We have carefully addressed all your comments below.

I. Proof of Theorem 5, and a discussion of trade-offs:

Thank you for pointing this out. We apologize for the omission, which was an oversight at the time of submission. The proof, which we will include in the revised version, uses the triangle inequality to decompose the error into two terms: (1) the error due to approximating the expectation, which is $\\mathcal{O}(l^{-1/2})$ by Hoeffding’s inequality (valid since the kernel is bounded), and (2) the error from quantile approximation, which is $\\mathcal{O}(n^{-1/2})$ by Theorem 3. Therefore, the correct bound is indeed $\\mathcal{O}(n^{-1/2}) + \\mathcal{O}(l^{-1/2})$, and we will update this in the revision.

II. Choice of Kernels for e-KQD Approximation:

We appreciate this insightful suggestion—this direction definitely has potential! Of course, it involves a thorough theoretical study that is beyond the scope of this paper, since it involves extending RKHS theory aimed at KMEs to the non-linear case of KQEs. This is something we are planning on looking into in detail in a follow-up study to this paper.

III. Sample size in experiments:

We note that the Laplace VS Gaussian experiment goes up to 10,000 datapoints, and the sample sizes in each experiment align with prior work in similar settings. However, our proposed near-linear Monte Carlo estimator means the method is suitable for large datasets, both in higher-dimensional (note d=12288 for Galaxy MNIST) and larger-sample settings (see scaling in Figure 4); we will include a note to that effect in the revised version.