Kernel Quantile Embeddings and Associated Probability Metrics
Authors: Masha Naslidnyk
Siu Lun Chau
Francois-Xavier Briol
Krikamol Muandet
Venue: ICML 2025 poster (2025)
Keywords: kernel methods
probability metrics
quantiles
Primary area: general_machine_learning->kernel_methods
TL;DR: We propose quantiles in RKHSs, and associated distances that are efficient, metrising under weaker conditions than MMD, and can be seen as kernelised generalisation of sliced Wasserstein. We demonstrate good performance in hypothesis testing.

Abstract: Embedding probability distributions into reproducing kernel Hilbert spaces (RKHS) has enabled powerful nonparametric methods such as the maximum mean discrepancy (MMD), a statistical distance with strong theoretical and computational properties. At its core, the MMD relies on kernel mean embeddings to represent distributions as mean functions in RKHS. However, it remains unclear if the mean function is the only meaningful RKHS representation.
Inspired by generalised quantiles, we introduce the notion of *kernel quantile embeddings (KQEs)*. We then use KQEs to construct a family of distances that:
(i) are probability metrics under weaker kernel conditions than MMD;
(ii) recover a kernelised form of the sliced Wasserstein distance; and
(iii) can be efficiently estimated with near-linear cost.
Through hypothesis testing, we show that these distances offer a competitive alternative to MMD and its fast approximations.

Kernel Quantile Embeddings and Associated Probability Metrics
Masha Naslidnyk'
Siu Lun Chau 2 François-Xavier Briol 3 Krikamol Muandet
Abstract
representation of a distribution as KME is unique, captur- ing all information about the distribution. The probability metric constructed by comparing KMEs, called maximum mean discrepancy (MMD) (Borgwardt et al., 2006; Gretton et al., 2012), has received significant attention due to its com- putational tractability. Its most common estimator has cost (n²²) and can be estimated with error On in the num- ber of data points n, but cheaper alternatives have also been proposed (Gretton et al., 2012; Chwialkowski et al., 2015a; Bodenham and Kawahara, 2023; Schrab et al., 2022). For this reason, KMEs and the MMD have been used to tackle a broad range of tasks from hypothesis testing (Gretton et al., 2012) to parameter estimation (Briol et al., 2019; Chérief- Abdellatif and Alquier, 2020), causal inference (Muandet et al., 2021; Sejdinovic. 2024), feature attribution (Chau et al., 2022; 2023), and learning distributions (Muandet et al., 2012; Szabó et al., 2016).
Embedding probability distributions into repro- ducing kernel Hilbert spaces (RKHS) has enabled powerful nonparametric methods such as the max- imum mean discrepancy (MMD), a statistical dis- tance with strong theoretical and computational properties. At its core, the MMD relies on ker- nel mean embeddings to represent distributions as mean functions in RKHS. However, it remains unclear if the mean function is the only meaning- ful RKHS representation. Inspired by generalised quantiles, we introduce the notion of kernel quan- tile embeddings (KQEs). We then use KQEs to construct family of distances that: (i) are prob- ability metrics under weaker kernel conditions than MMD; (ii) recover a kernelised form of the sliced Wasserstein distance; and (iii) can be effi- ciently estimated with near-linear cost. Through hypothesis testing, we show that these distances offer a competitive alternative to MMD and its fast approximations.
Nevertheless, the question of whether alternative kernl-- based embeddings, particularly nonlinear counterparts, could exhibit desirable properties has long remained under- explored, in part due to the associated computational chal- lenges. Recently, this gap has begun to be addressed, with works investigating kernelised medians (Nienkötter and Jiang, 2023), cumulants (Bonnier et al., 2023), and vari- ances (Makigusa, 2024a). this paper, we consider an alternative based on the concept of quantiles in an RKHS, which term kernel quantile embeddings (KQEs). Sim- ilarly to the construction of KMFs, KQFs are obtained by considering the directional quantiles of feature map ob- tained from a reproducing kemel. KQEs also lead naturally to a family of distances which we call kernel quantile dis- crepancies (KQDs). This approach is motivated from the statistics and econometrics literature (Kosorok, 1999; Do- minicy and Veredas, 2013; Ranger et al., 2020; Stolfi et al., 2022), where matching quantiles has been shown effective in constructing statistical estimators and hypothesis tests.
1. Introduction
Many machine learning and statistical methods rely on rep- resenting, comparing, and measuring the distance between probability distributions. Kernel mean embeddings (KMEs) have been shown to be mathematically and computation- ally convenient approach for this task (Berlinet and Thomas- Agnan, 2004; Smola et al., 2007; Muandet et al., 2016). At its core, a KME represents a distribution as a mean function in a reproducing kernel Hilbert space (RKHS). When the kernel function is sufficiently regular and satisfies condi- tion called 'characteristic" (Sriperumbudur al., 2010), the
'Deaarmment of Computer Science, University College London, London, UK 'College of Computing & Data Sci- ence. Nanyang Technological University, Singapore 'Department of Statistical Science, University College London, London, UK *CISPA Helmholtz Center for Information Security, Saar- brücken, Germany. Correspondence to: Masha Naslidnyk <masha.naslidnyk.. 2.21 uukk.ac.uk>.
Our paper identifies several desirable properties of KQES. Firstly, from theoretical point of view, we show in Theo- rem and Theorem 2 that KQEs can represent distributions on any space for which we can define kernel, and that the conditions to make a kernel quantile-churacternnn for KQEs to be a one-to-one representation of a probabil- ity distribution, are weaker than for the classical notion of characteristic, which we now call mean-characterrisicc We
that is
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Kernel Quantile Embeddings and Associated Probability Metries
then show in Theorem 3 that KQEs can be estimated rate of (22 in the number of samples n; the same rate as that of the empirical estimator of KMEs (Tolstikhin et al., 2017). As result, KQDs are probability metrics under much weaker conditions than the MMD (see Theorem 4), while maintaining comparable computational guarantees, in- cluding a finite-sample consistency with rate On (up to log terms) for their empirical estimators (see Theorem 5).
density of 6.
Figure Illustration of bivariate quantiles. Left: Bivariate distribution P. Center: Density of the projection of P onto direction on the unit circle, with (x) = (u,z). Right: different quantiles for all possible directions u.
Secondly, we establish a number of connections between KQDs, Wasserstein distances (Kantorovich, 1942; Villani et al., 2009), and generalisations or approximations thereof. In particular, special cases of our KQDs recover existing sliced Wasserstein (SW) distances (Bonneel et al., 2015; Wang et al., 2022; 2024a) and can interpolate between the Wasserstein distance and MMD similarly to Sinkhorn diver- gences (Cuturi, 2013; Genevay et al., 2019). These results are presented in Connections 1, 2, and 3.
[V1 ... -.. D.. The a-quantile of P. denoted p%, can be estimated using [[]]] where [-] denotes the ceiling function. This estimator is known to converge at rate of On (Serfling, 2009, Section 2.3.2).
Multivariate quantiles. Suppose now that X' C I for d > 1. The previous definition of quantiles depends on the existence of an ordering in X. and its natural generalisation to > 1 is therefore not unique (Serfling, 2002). In this paper, we will focus on the notion of a-directional quantile of along some direction u in the unit sphere Sot (Kong and Mizera, 2012).
Finally, we consider a specific instance of KQDs based on Gaussian averaging over kernelised quantile directions, which we name the Gaussian expected kernel quantile dis- crepancy (e- KQD). Beyond the desirable theoretical proper- ties described above, we show that the Gaussian e-KQD also has attractive computational properties. In particular, we show that it has natural estimator which only requires sam- pling from a Gaussian mcasure on the RKHS, and which can be computed with complexity On log" (n)). It is studied empirically in Section 5 with experiments on two-sample hypothesis testing, where we show that competitive with the MMD; it often outperforms estimators of the MMD of the same asymptotic complexity, and in some cases even outperforms MMD at higher computational costs.
Pp
Po.#pu
(u(y) = (u, 4)-
Here, du :u::0 : R the projection map onto u, and P is the standard one-dimensional a --uantiile of d P-the law of (X) for X ~ P. We note that this quantile is now d-dimensional vector opposed to scalar. The a-directional quantiles for d = 2 are illustrated in Figure 1, in which the probability measure is projected onto some line; see the left and middle plots. Once again, we can use quantiles to characterise P, although we must now consider all a quantilees over sufficiently rich family of projections {pp a E [0, 1], u 5 see Theorem 5 of (Kong and Mizera, 2012) for sufficient regularity conditions.
2. Background
Let Pxx denote the set of Borel probability measures on a Borel space X. We begin by reviewing existing definitions of quantiles, followed by a summary of relevant work on probability metrics, including the MMD and SW distances.
Although these multivariate quantiles satisfy scale equivari- ance and rotation equivariance, they do not satisfy location equivariance. To remedy this issue, Fraiman and Pateiro- López (2012) introduced related notion, the centered a- directional quantile:
2.1. Quantiles
Univariate quantiles. Let X S R. For a E 1]. the a-quantile of P E Px is defined as pp inf E X : Pry~elY<sul a). When has continuous and strictly monotonic cumulative distribution function Fr, quantiles can also be defined through the inverse of that function Ff==F Notable special cases include a = 0.5, cor- responding to the median, and a = 0.25, 0.75, correspond- ing to lower- and upper- quart-iustss respectively. Importantly, P is fully characterised by its quantiles {pf) (/f.)))
- M == (PO.#P - ou (Ex-r((X)) + Ex-P[X], (1) PP
Further details are provided in Appendix B.
2.2. Probability Metries
Kernel mean embeddings and MMD. Let X be some Borel space, and (H, (<x))) be a reproducing kernel Hilbert space (RKHS) induced by a real-valued kernel k x + R (Schölkopf and Smola, 2002; Berlinet and Thomas- Agnan, 2004), the kernel mean embedding (KME) pp X + R of any P E Px is defined as the Bochner integral
From a computational viewpoint, univariate quantiles can be straightforwardly estimated using order statistics. Suppose Vio- [yi... ... yn]' P. and denote by [yi=, the juh order statistic of yi. (i.c. the 7th largest value in the vector
2

---

Kernel Quantile Embeddings and Associated Probability Metries
(P(+) Ex~plK(X, })] H. The integral can be shown to exist provided Ex-rlv (ooliv/(xx, (xx, X < oc;; this, in turn, holds for all P E Px if and only if k is bounded (Smola et al., 2007). If the mapping P - Hup is injective, the kemme k is said to be characchrrattrisstccc. Many standard kernels- the Matérn family, Gaussian, Laplacian- have been shown to be characteristic on sufficiently regular spaces (Sripe- rumbudur et al., 2011; Ziegel al.. 2024). KMEs with mean-characteristte kernels lead to the squared maximum mean discrepancy (MMD) defined for any P, Q E Px as
A further refinement, the max-sliced Wasserstein (max-SW) distance (Deshpande al., 2018), aims identify the opti- mal projection that maximises the ID Wasserstein distance:
1/8
(P. = sup "/(OuHP.ooHH N
Both slicing distances reduce the computational complex- ity to O(n log n) and the convergence rate to O + n V-r),, where is either the number of projections, or the number of iterations of the optimiser. A further extension is the Generalised Sliced Wasserstein (GSW, Kolouri et al. (2019)), which replaces the linear projection du with non- linear mapping. While the conditions for GSW to be a probability metric are highly non-trivial to verify, the au- thors showed that they hold for polynomials of odd degree.
MMD? (P,Q) Q) = |pr 1 molla = Ex,x' ((X,x') -x X')] + X (xX,
This can be computed in rare cases (Briol al., 2025),
but typically needs to be estimated. Given i..d. real-
isations from P and Q, MMD? is most commonly esti-
Another approximation of the Wasserstein distance involves the introduction of an entropic regularisation term (Cuturi, 2013), which reduces the cost to (n2²) and can be estimated with sample complexity Onn (Genevay et al., 2019 9). The solution to this regularised problem is referred to as the Sinkhorn divergence. Interestingly, Ramdas et al. (2017); Feydy al. (2019) demonstrated that by varying the strength of the regularisation, the Sinkhorn divergence interpolates between the Wasserstein distance and the MMD with a kerne corresponding to the energy distance.
mated with a U-statistic, which converges to MMD (P, Q) as On On²)/2 and has computational complexity of O( although linear-cost alternatives are also available (Gretton
et al., 2012, Lemma 14.). These are discussed in Section 5 and Appendix A.
Wasserstein distances. Let e X' X + be a met- ric on X, and T(P, Q) S Pxxx denote the space of joint distributions on X' X' with first and second marginals P and Q, respectively. The p- w-sssestteenn distance (Kan- torovich, 1942; Villani et al., 2009) quantifies the cost of optimally transporting one distribution to another under "cost" e: X' x X' - IR. It is probability metric under mild conditions (Villani et al., 2009, Section 6), and is defined as
3. Kernel Quantile Embeddings and Discrepancies
We introduce directional quantiles in the RKHS and the corresponding discrepancies. Unlike in Section 2.1, the measures and their quantiles now live in different spaces: the measures are on X, and the quantiles are in the RKHS H. induced by a kernel on X. This leads to greater flexibility: the approach works for any space kernel can be defined on. Throughout, we assume the kernel k is measurable.
W)(P,Q)= = (.Einf inf (ox)) 1/- (xE((P.))
When X' C Rd, the metric e is typically taken to be the Euclidean distance c(z, y) = | v/12. The Wasserstein distance can then be estimated by solving an optimal trans- port problem using empirical measures constructed through samples of P and Q. an approach that suffers from high computational cost of On²)) and, when P. Q have at least 2p moments, slow convergence of O(n 1/ max(d.2p) when X' C IRd for d > 1 (Fournier and Guillin, 2015).
3.1. Kernel Quantile Embeddings
Let Six {u E H ||u]] H =) be the unit sphere of an RKHS H induced by the kernel k. For P E Px, we define its a-quantile along RKHS direction u E Sy as a function Pp" :X + Riin H with
However, when d 1, Wp can be computed at lower cost of O(n log n) with convergence of (n/w//>) when P,Q have at least 2p moments. This motivated the introduction of the sliced Wasserstein (SW) distance (Bonneel et al., 2015). Recall that (x) = u. T x. The SW distance projects nigh-dimensional distributions P, Q onto elements on the unit sphere u E gd-1 sampled uniformly, computes the Wasserstein distance between the projected distributions, now in IR, and averages over the projections:
Pp
0.0 (x) = p(())(
(2)
By the reproducing property, it holds that Pi p(() # P) (x)), where vb(x) = k( .) is the canonical fea- ture map X' + H. and (h) = (u, h)w is the 7 + H equivalent of the projection operator onto u defined in Sec- tion 2.1. Thus, when dim(H) < co, the RKHS quantiles of P on X' are exactly the multivariate quantiles of the mea- sure of k(X, :), X ~ P. on H. In other words, KQEs can be thought of as two-step embeddings: we first embed
=
(W, Q)= = (EunU(sa-1) [WB P. (())
3

---

Kernel Quantile Embeddings and Associated Probability Metrics
X~ P Px as an RKHS element and then compute its directional quantiles to obtain the KQEs.
ll _
PG
"bb
MU #Q
U2
Centered vs uncentered quantiles. Just as done for mul- tivariate quantiles in Equation (I), centered version of RKHS quantiles can be defined as
U1
U2
U2#
U2##P
U1 UP
n0: (x) = (Pu#p (u, (PPH) u(x) + up((), Pp
Figure 2: Illustration the impact the slicing direction on KQEs. Suppose X ~ P, the KQEs Pp "x)(x)== = Pu#p are obtained by considering the at quantile of u(X). Clearly, these quantiles might vary significantly depend- ing on the slicing direction used.
where up is the KME of P. This coincides with Equa- tion (1) for the measure being the law of -(X,-) with X ~ P. The impact of centering is examined in detail in Ap- pendix B, but two key observations are relevant here: (1) omitting centering eliminates the computational overhead of calculating means; (2) the only equivariance violated for the uncentered directional quantile location equivariance: shifting -X),) by h shifts the quantile by (h, u) H2 rather than by h itself. However, when KQEs used to compare two distributions, the additional term (h, ucu cancels out as it does not depend on the measure. For these reasons, we primarily work with the uncentered RKHS quantiles.
for which k(x; -) kyy. will not be able to distinguish between Dirae measures óg and öy. The proof of the follow- ing result uses characteristic functionals, an extension of characteristic functions to measures on spaces beyond Rd. Unlike moments, characteristic functionals are defined for any probability betasurr-which is the key to generality of KQEs. Further discussion and proof are in Appendix C.I. Theorem (Cramér- (Cramér-Wold Wold Theorem in RKHS). Under Al and A2, the kernel k is quantile-chrracteristi,, meaning the mapping P + {pp" E [0, 10,1... u E Sx3 is injective.
Quantile-haaracteristi kernels. The kernel le is said to if the mapping P + {pp" E [0, 11. u E Sx} is injective for P E Px. In R the Cramér Wold theorem (Cramér and Wold, 1936) states that the set of all one-dimensional projections (or, equivalently, all quantiles of all -ieeimmesio projections) determines the measure. One may therefore recognise our next theo- rem as an RKHS- extension of the Cramér-Woo theorem. Earlier Hilbert space extensions required higher- dimensional projections and imposed restrictive moment as- sumptions (Cuesta-Albertor et al., 2007). Being concerned with the RKHS case specifically allows us to prove the result under mild assumptions, as stated below.
be guantile-characterre
The mildness of the assumptions in Theorem 1 naturally raises the question: is being quantile- ceaaatte-caaaccterissicc a less restrictive condition than being mean-churucterrsttcc? This indeed holds, as shown in the result below.
Theorem 2. Every mean-characteriin kernel k is also chantile-characterinn The converse does not hold.
This result, proven in Appendix C.2, has a powerful impli- cation. For any discrepancy D(P; Q) that aggregates the 0, for KQEs injectively (i.e D(P, Q) = 0 + Pp PQ
O. but D(P, Q) > 0 A MMD Q) > O. This means D can tell apart every pair of measures MMD can, and some- times more (see the proof for examples). This is intuitive: MMD is an injective aggregation of means (MMD Q) = O + Ep [u] = Eql [u] for all u), and the set of all quan- tiles captures all the information in the mean, but not vice versa. Before introducing specific family of quantile dis- crepancies, we discuss sample versions of KQEs.
all o, u), it holds that MMD(P, Q) > 0 D(P.Q)
Assumption A is Hausdorff, separable, and o-compact,
Being Hausdorff ensures points in X' can be separated, and scparability says X' has a countable dense subset. o- compactness means X is a union of countably many com- pact sets. These are mild conditions, notably satisfied by Polish spaces-including discrete topological spaces with at most countably many elements and topological manifolds.
is possible to drop the o-compactness and separability. When X is Hausdorff and completely regular, one can still get quantil--harracterrstt properties on Radon probability measures-the the "non-pate pathoooooll Borel probability mea- sures. We discuss this in Appendix C. and refer to Willard (1970) for a review of general topological properties. Assumption A2. The kernel k is contimuous, and separating on X: for any x + y E X, holds that k(xz-)) + k(...))
Estimating KQEs. For fixed a E [0. 1] and u E Sn, esti- mating the directional quantile مم with samples æim. X boils down to estimating the R-quantile Pu#P using sam- ples u(z1.). We employ the classic, model-free approach to estimate quantile by using the order statistic estimator:
PP. (x) == Pw Pa u(x) [u(zim))aan]
(f:"(())
(3)
where P. 1/m ET day- In other words, Equation (3) uses the q-quantile of the set mmenin) the [an]- th largest element of u( We now state an RKHS version of a classic result on convergence of quantile esti- mators; the proof is provided in Appendix C.3.
This is mild condition: most commonly used kernels such as the Matérn, Gaussian, and Laplacian kernels are sepa- rating. The constant kernel k(zz x²) = c is an example of a non-separating kernel. Trivially, a non-separating kernel
4

---

Kernel Quantile Embeddings and Associated Probability Metries
Theorem 3 (Finite-Sample Consisteney for Empirical KQES), Suppose the PDF of wi P is bounded away from zero, fu# 2 Cu > 0, and imn. P. Then, with probability at least - 6, and C(,, u) = O1 (ooo(2//0))
with a non-degenerate S by (Kukush, 2020, Corollary 5.3). For example, H + H covariance operator
S()(() Sx k(z ( is non-degenerate and well-defined provided (1) 8 on A' has full support, and (2) fx /k(x,,)3(dd) 3)(rr) < co. This choice of yy also happens to be computationally convenient, as discussed in Section 4.
a. a." Ipp." Pp 2 S C(),u)n 1/2
In contrast, while conditions under which MMD is dis- tance are well-understood for bounded translation-invariant kernels on Fuclidean spaces (Sriperumbudur et al., 20 they are challenging to establish beyond this setting. For instance, it known that commonly used graph kernels are not characteristic (Kriege al., 2020).
We do not need to assume Al and A2 to prove consis- tency; this was only needed to establish that k is quantile- characteristic, and we may still have a consistent estimator when the kernel is not quantil-characterriste.. The condition fu# p (z) 2 Cu > 0 lets avoid making any assumptions on X' other than the existence of a kernel & on X.
When v is chosen as the Lebesgue measure μt, an important connection emerges between e- eQDQ, sup-KQD. and sliced Wasserstein distances. This connection is formalised in the next result, with proof provided in Appendix C.6.
3.2. Kernel Quantile Discrepancies
We propose to quantify the difference between P. Q Px in unit-norm direction u through a u-weighted expectation of power-p distance (in the RKHS) between KQEs,
Connection 1 (SW). Suppose P. P.Q have p-finite moments. Then, e-KQD, Qi Qiv,n) (.) for u corresponds to a ker- nel expected sliced p- Wasserstein distance, which has not been introduced in the literature. For X' S Rd, linear k(z, y) = x y, and uniform 7, this recovers the expected sliced p- p-Wassesstiin distance (Bonneel et al., 2015).
(PP.Qiuu - (L 1100 - 102 (Pp((d))) %
Figure 2 illustrates how u# P and u#Q vary depending direction u and the impact it has on Tp- The weighting measure y on [0, 1] assigns importance to each a-quantile. For example, the Lebesgue measure v = treats all quan- tiles as equally important, whereas a partial-supported mea- sure would allow us to ignore certain quantiles.
Connection 2 (Max-SW). Suppose P. Q have p-finite mo- ments. Then, sup-KQD, (P. Q:v) for v = p is the kernel max-sliced p- D-Wasserstein distance (Wang et al., 2022). For X' S Rd, linear k(x.y) xx y. and uniform n, it recovers the max-sliced p- D-Wasersttein (Deshpande et al., 2018).
Based on (P, Qi u), we introduce a novel family of Kernel Quantile Discrepancies (KQDs) that aggregate the directional differences Tp (P, Q; v, u) over u E Sw: the T,P- type distance expected KQD (e-KQD) that uses the average as the aggregate function, and the -tye distance supre- mum KQD (sup-KQD) that aggregates with the supremum:
For d = 1, we recover standard Wasserstein. When is non- non-linear but induces a dimensioiaiii RKHS, e-KQD is connected the Generalised Sliced Wasserstein distances of Kolouri et al. (2022)- we explore this in Appendix C.6.
Lastly, we establish a connection to Sinkhorn divergence.
Connection 3 (Sinkhorn). Sinkhorn divergence (Cuturi, 2013), like K-KQD and sup-KQD, combines the strengths of kernel embeddings and Wasserstein distances. Farthermore, for p 2 and p,, the centered version of e-KQD and sup-KQD developed in Appendix B can be represented as sum of MMD and kernelised expected or max-sliced Wasserstein distances, thus positioning these measures as mid-point interpolants between MMD and SW distances.
e- C-KOD,(P.Q.u.))) = =EBnny [5 (P.Q;;u Sup-KOD((P.Q:v)) =
(4)
(ssup Th (P.Q: .NESH
where 7 is a measure on the unit sphere Sn of the RKHS.
Next, we demonstrate that under mild conditions e-KQD and sup-KQD are indeed distances, and establish connec- tions with existing methods. The proof is Appendix C.4.
It is important to note that the MMD term within the Sinkhom divergence is restricted to specific kernel tied to the energy distance-in contrast, e-KQD and Kup-KQD offer much greater flexibility in the choice of kernel. More- over, as will be shown empirically in Section 5, the com- putational complexity of e-KQD for particular choice of 7 can be made significantly lower than that of Sinkhorn divergences, which have a cost of On?))
Theorem 4 (KQDs as Probability Metrics). Under AI, A2, and v u has full support on [0, 11. sup-KOD, y is a distance. Further, if y has full support on Sx. e-KQD,, p. a distance.
As discussed in Section 3, A1 and A2 are minor. The assumptions on the support of v and y ensure that no quan- tile level in [] and no parts of Sy are missed entirely. This is satisfied, for example, for the uniform v (that con- siders all quantiles to be equally important), and when H separable, for any centered Gaussian ? = S),
Estimating e-KD We propose a Monte- Carlo estima- tor for e-KQD, and refer to Wang et al. (2022) for an
5

---

Kernel Quantile Embeddings and Associated Probability Metries
optimisation-based. (n lng(n)) estimator for Sup-KQD. Let Fi:n P. Vi.m Q. the w1,.... uy E SH be I unit- norm functions sampled from 7, and fu to be the density of v. Denote Pn = 1/n Ei=1 6z. Qn = 1/m Σi=1 5y. Then, similarly to the order statistic estimator of the quantiles in Equation (3), (P Qui u, 7)) is the estimator of e- (PQ Qi 7), where
Algorithm 1 Gaussian e-KQD
Input: Data Ti: P. Vi:n Q, samples from the
reference measure F1:m ~ 5, kernel k. density Su, number of projections I, powwrrr p.
Initialise e-KQD + 0 and Tp. + 0 f = 1...l.
for = 1 to do
Sample A1m ~ ~N(00, Idm)
Compute f((21nn) X k( (11mm Flmm) / Vmm
c-KQD" 1m)
(5)
f((1).)) + > A (= Mi.n //m
1 EE in =1
([u(Crm))l [ur(orm)),) su (D/ml)
Compute IIfall +- v Aimm k Z1om /1 m
Compute u; fa(
(y(:n))) < //l.fall
Here, (m:(31:s)] is the j-th order statistics, meaning the j-th smallest element of uy (z)..)) [u.(z1)..... (((])))), For p = 1, we get the following result, proven in Ap- pendix C.5.
Sort u, (z and us (B/im)
(=n))]
for j = 1 to 1 do
p.i + p.a + (lui }1g (u: (/ (T(i//n)) end for e- CQQDD= + e-KQDD + +,,,1/1
Theorem 5 (Finite-Sample Consistency for Empirical KQDs). Let v have a density, P, Q be measures on X s.t. Ex-PV /k(,,) < oG and Ex-Q / /k(X, X) < 0o, and Jim P. Vin ~ Q. Then, with probability least 5, 6, and C(6) = ((Voog(1/0) that depends only on 6, V,
end for Return e-KQD"
(e-KQD, Qni.))) - (P)
We now conduct further empirical study of the squared kernel distance e-KQD,. Unlike its supremum-based coun- terpart sup-KQD, e-KQD can be approximated simply by drawing samples from y on SH, avoiding the challenges associated with optimising for the supremum. Although a uniform y is natural choice, no such measure exists when dim(H) is infinite (Kukush, 2020, Section 1.3). Instead, we follow well-established strategy from the inverse problems literature (Stuart, 2010) and take "y to be the projection onto SH of a Gaussian measure on H. Using established tech- niques for sampling Gaussian measures, we then build an efficient estimator for e-KQD, Q; 12, 7). Gaussian mea- sures Hilbert spaces are natural extension of the familiar Gaussian measures on Rdd a measure (O, C) on H is said to be a centered Gaussian measure with covariance oper- ator C : H + H if, for every f E H, the pushforward of (0, C)) under the 7 - IR projection map 6f(-) = (f, .)x
S ((( +
The rate does not depend on dim(X) this is a major advantage of projection//licing-bann based discrepancies (Nad- jahi et al., 2020), which comes at the cost of depen- dence the number or projections I. Setting I n/ logn recovers the MMD rate (up to log-terms), at matching complexity (see Section 4). Here, we do not need e-KQD to be a distance-indeed we did not as- sume A1 and A2. The condition of square root inte- grability of k(X,X X) under P, Q is immediately satisfied when k is bounded, and can fact be further weakened to Ex=PlEy=QV/K /k(X, - 2x,XX) + k(Y,Y) < co. Requiring that // has density is mild and necessary to reduce the problem to CDF convergence-wieee by the classic Dvoretzky-Kiefer- sene--iiieeee-olooiitt inequality of Dvoret- zky et al. (1956) has rate n 11/2 under no assumptions on the underlying distributions. The strength of this incquality allows us assume nothing more of X' than the fact that it is possible to define kernel it.
is the Gaussian measure (0, (C(J), z)x) on R. For fur- ther details on Gaussian measures in Hilbert spaces, we refer to Kukush (2020).
Let 7 be a centered Gaussian measure on H whose covari- ance function C. H. - H. is an integral operator with some reference measure & on X,
Further, for any integer p > 1, the n 112 rate still holds-if and only if holds that for Jr (1)) - F. (())(( /Se#t(()) both (P) and In(() are integrable over u ~ 7 and Lebesgue measure on (()). In turn, this may be reduced to a problem of con- trolling d - volumes of level sets of u. We discuss this extension further in Conjecture in Appendix C.5.
Y = -N0,C),, CUI(s) = 1 k(a, ()),
and let y be the pushforward of 7 by the projection 76 + Sy that maps any f E H to f/llfllx E Sn. By the change of variables formula for pushforward measures (Bogachev,
4. Gaussian Kernel Quantile Discrepancy
6

---

Kernel Quantile Embeddings and Associated Probability Metrics
2007, Theorem 3.6.1), it holds that
at distinguishing between distributions. It is equally impor- tant to ensure proper control of Type error, defined the rejection rate when the null hypothesis Ho is true. Specifi- cally, the Type I error rate should not exceed the specified level. Without controlling for Type I error, an inflated rejec- tion rate might not reflect the estimator's ability to detect genuine differences but instead indicate the test rejects more often than it should. We consider a significance level a of 0.05 throughout and report on Type control in Appendix D.
e-KQD;(P:Q; = Bur [TB up = E'n [7B (P. Q; //1/1=]]
This equality reduces sampling from y to sampling from a centered Gaussian measure with an integral operator covari- ance function. The next proposition reduces sampling from (a finite-sample approximation of) y to sampling from the standard Gaussian on the real line; proof is in Appendix C.7.
To determine the rejection threshold for each test statistic, we employ a permutation- based approach: for each trial we pool the two samples, randomly reassign labels 300 times to simulate draws under Ho, compute the test statistic on each permuted split, and take the 95th percentile of this empirical null distribution as our threshold. This fully nonparametric thresholding ensures Type error control without additional distributional assumptions (Lehmann et al., 1986).
Proposition 1 (Sampling from Gaussian measure). Let 21 ~ &, and Ym to be the estimate of 7 bused on the Monte Carlo estimate Cm of the covariance operator C,
1 m
Y/m = -0 Cm), (ml
k(a, 2y (z)g(
Suppose f(x) = m - t Xyk(I, 23) with Aam
Our experiments aim to demonstrate that, within a com- parable computational budget, statistics computed using quantile-charaatterstte kernels can deliver results competi- tive with those of MMD tests based on mean-charactenn kernels. Additionally, we seek explore the inherent trade- offs of the proposed methods. We focus the nonpara- metric two-sample testing problem, as it represents one of the most successful applications of the mean-embeddingg- based MMD and its variants. The code is available at https:/ /ggttbb///tttbb/t// Cooo//aaaaaaaee indyk/kgeeee
(0,,1). 1). Then, f ~ ~'
Algorithm brings together the e-KQD estimator in Equa- tion (5), and the procedure for sampling from the Gaus- sian measure in Proposition 1. The choice is left up to the user; the uniform v remains a default choice. We pro- ceed to analyse the cost. This estimator has complexity (I max(mm, m2 n log n)):: (l) for iterating over direc- tions E (1.....(): I): (nm) for computing fi(11))) and Is (y):)):: Omm²) for computing []ʃallææ: and Ov log n) for sorting (z1.)) and (.(.)) For == log n and m log n, the complexity therefore reduces to On log" n); i.e. near-linear (up to log-terms).
5.1. Benchmarking
We consider the following distances as test statistics in our experiments. Detail descriptions of these estimators are provided in Appendix A. For KQDs, we take the reference measure & (c.f. Proposition 1) to be 1/2P, + 1/2Qn.. where Pn corresponds the empirical distribution 1/1x >i= dn.- analogously for Qn. Such & is general choice that is ap- propriate in the absence of additional information about the space X. We take power p = 2 for all RQD-based discrepan- cies in our experiments; identical experiments for = 1 lead to the same conclusions and are presented for completeness in Appendix D.2. Other than in the second experiment, we use the RBF kernel k(2,, x²) exp(p-lle the bandwidth chosen using the median heuristic method, i.e. = Dodiian([|=;; xz 112, Vi,j E I,..., n2) (Gret- ton et al., 2012). Due to space constraints, we present all methods on the same plot, regardless of their computational complexity. However, it is important to note that directly comparing test power across methods with varying sampling complexities may be unfair and misleading.
5. Experiments
We empirically demonstrate the effectiveness of KQDs for nonparametric two-sample hypothesis testing which aims at determining whether two arbitrary probability distribu- tions, P and Q, differ statistically based on their respective ii.d. samples. Two-sample testing is widely adopted in scientific discovery fields, such as model verification (Gao et al., 2024), out-of-domain detection (Magesh et al., 2023), and comparing epistemic uncertainties (Chau et al., 2025). Specifically, we test the null hypothesis Ho P = Q against the alternative H1 P # Q. In such tests, (estimators of) probability metrics are commonly used as test statistics, in- cluding the Kolmogorov-Smie -mmiroy distances (Kolmogorov, 1960), Wasserstein distance (Wang et al., 2022), energy- distances (Székely and Rizzo, 2005; Sejdinovic et al., 2013), and most relevant to our work, the MMD (Gretton et al., 2006; 2009; 2012). For an excellent overview of kernel- based two sample testing, we refer readers to Schrab (2025).
x/11² /2o²) with
e-KQD (ours). For e-KQD, we set the number of projec- tions to = log n and the number of samples drawn from the Gaussian reference to m = logn. n. Conseguently, the overall computational complexity is (n log (n)).
Experiments are repeated to calculate the rejection rate, which is the proportion of tests where the null hypothesis is rejected. A high rejection rate indicates better performance
7

---

Kernel Quantile Embeddings and Associated Probability Metries
MMD Lin (O(n))
MMD Multi (Oinlog' nll
KQD; (Oinlog' n))
e-KQD; (Dinlog' ml
MMD (Din'))
KQD, Centered (0ln²))
(a) Power Decay
(b) Laplace v.s. Gaussian
(c) Galaxy MNIST
(d) CIFAR-10 v.s. CIFAR-10.
Rejection rate
0.8
Relectoo rate
0.7-
Relection rate
0.7
Rejection rate
0.6
0.6
0.6
0.5
0.4
0.2
0.2
02-
0.1-
011
126
236
512
100
550
2009
5000
10000
0.0
100
1000
1500
25:0
0.0
105
500
10000
1500
2000
Dimensioo
Number of samples
Number of samples
Number of samples
Figure 3: Experimental results comparing our proposed methods with baseline approaches. Methods represented by dotted lines exhibit quadratic complexity for single computation of the test statistic, while the remaining methods achieve near-linear or linear computational efficiency. A higher rejection rate indicates better performance in distinguishing between distributions. Overall, quadratic-time quantile-based estimators perform comparably to quadratic-time MMD estimators, while near-linear time quantile-based estimators often outperform their MMD-based counterparts.
e-KQDDeentered (ours). The centered version of e-KQD, as discussed in Appendix B, can be expressed as the sum of e-KQD term and the classical MMD. While the e- e-KQD component follows the same sampling configu- ration as above, the MMD computation is the dominant factor in complexity. leading to an overall cost of On²)).
practicality and competitiveness of our proposed methods. Additional experiments are reported in Appendix D, specifi- cally: studying the impact of changing the measures v and ç. comparing with sliced Wasserstein distances, and com- paring with MMD based on other KME approximations.
1. Power-decay experiment. This experiment investigates the effect of the curse of dimensionality on our tests, follow- ing the setup of Experiment A in Wang et al. (2022). Prior work by Ramdas et al. (2015) has shown that MMD-based methods are particularly vulnerable to the curse of dimen- sionality. Here, we assess whether our quantile-baat based test statistic exhibits similar limitations.
sup-KQD (ours). sup-KQD adopts the same sampling configuration as e-KQD (thus cost On (o)))) In- stead of averaging over projections, it selects the max- imum across all projections. This approach serves as a fast approximation of the kernel max-sliced Wasser- stein distance of Wang et al. (2022), where Riemannian block coordinate descent method is used to optimise entropic regularised objective at computational cost of (n² log( In contrast, our approach identifies the largest directional quantile difference across the sampled projections. While we do not claim that this provides an accurate estimate of the true distance, this approach allows for controlled complexity and facilitates compar- isons between averaging or taking the supremum.
We fix n = -20 and take P to be an isotropic Gaussian distribution of dimension d. Similarly, we take Q to be a d-dimensional Gaussian distribution with a diagonal covari- ance matrix Σ diag( [4, 4, 4, ......... 1)). the dimension d E [32, 64, 128, 256, 512]. the testing prob- lem becomes increasingly challenging. Figure 3a presents the results. We observe that e- e-KQD exhibits the slowest de- cline in test power among all methods, irrespective of their computational complexity. Notably, it maintains its perfor- mance significantly better than its Onn log In)) benchmark, MMD-Multi. These results suggest that quantile-bant based dis- crepancies exhibit greater robustness to high-dim data.
As we increase
MMD. The MMD is included benchmark to be com- pared with cenDceeteered and has complexity On?)).
The MMD is estimated using the U-statistic formulation.
MMD-Multi. A fast MMD approximation based in- complete U-statistic introduced in Schrab et al. (2022) is included to benchmark against our e- e-KQD distance. Configurations of MMD-Multi are chosen as to match the complexity of e-KQD for fair comparison.
2. Laplace v.s. Gaussian. This experiment aims to lustrate Theorem by demonstrating that while kernel may not be aatt---caaaaeersii-mmmae guish between two distributions using standard KMEs and MMDs-it can still be quantil-charractersttic. In such cases, the distributions can still be effectively distinguished using our KQES and KQDs. To demonstrate this, we take P to be a standard Gaussian in d = 1, and Q to be a Laplace dis- tribution with matching first and second moment. We vary n E {100, (100,500, 2000, 5000, 10000} and select a polynomial kernel of degree 3, i.e. k(z,z') ((z, x²) + 1)², for all our
cannot distin-
MMD-Lin. MMD-Linear from Gretton et al. (2012, Lemma 14.) estimates the MMD with complexity O(n).
5.2. Experimental Setup and Results
We conduct four experiments: two using synthetic data, al- lowing full control over the simulation environment, and two based on high-dimensional image data to showcase the
8

---

Kernel Quantile Embeddings and Associated Probability Metries
methods. This ensures that k cannot distinguish between the two distributions due their matching first and second moments, which leads to their KMEs being identical.
Runtime comparisons on the CIPAR-10 vs CIFAR-10.1
10
Seconds (Log-Scale)
Figure 3b shows that our KQDs, irrespective of their com- putational complexity, exhibit increasing test power as the sample size grows. In contrast, MMD-based methods fail entirely to detect any differences between P and Q. Notably, although e- e-KQDD-entered can be expressed as the sum of an MMD term and an a e- e-KQ term, the underperformance of the MMD component in this scenario is effectively com- pensated by the e-KQD term, enabling successful testing.
10
10a
R-KQD;
MMDD-Lin
--etee--entered
MX4
10
Mulli
sup Sup:KQD:
100
500
1000
1500
2000
Number of Samples
Figure 4: Comparing the time (in seconds) required com- plete the CIFAR-10 vs. CIFAR-I0.1 experiment, plotted a logarithmic scale. A shorter time indicates faster algorithm. These results align with our complexity analysis.
3. Galaxy MNIST. We examine performance on real-world data through galaxy images (Walmsley et al., 2022) in di- mension d x 64 64 = 12288, following the setting from Biggs et al. (2024). These images consist of four classes. P corresponds to images sampled uniformly from the first three classes, while Q consists of samples from the same classes with probability 0.85 and from the fourth class with probability 0.15. A Gaussian RBF kernel with bandwidth chosen using the median heuristic method is chosen for all estimators. Sample sizes are chosen from n E {1000, 500, 1000, 1500, 2000, 2500].
KQD estimator makes it suitable for larger-scale datasets.
6. Discussion and Future Work
This work explores representations of distributions in a RKHS beyond the mean, using functional quantiles to cap- ture richer distributional characteristics. We introduce ker- nel quantile embeddings (KQEs) and their associated kernel quantile discrepancies (KQDs), and establish that the condi- tions required for KQD to define a distance are strictly more general than those needed for MMD to be a distance. Addi- tionally, we propose an efficient estimator for the expected KQD based on Gaussian measures, and demonstrate its ef- fectiveness compared to MMD and its fast approximations through extensive experiments in two-sample testing. Our findings demonstrates the potential of KQEs powerful alternative to traditional mean-based based representations.
Figure 3c presents the results. e-KODDcentered and MMD exhibit nearly identical performance, suggesting that the MMD term is dominating in the e-KQD- estima- tor. Among the near-linear time test statistics, e-KQD and sup-KQD show a slight advantage over MMD-Multi in dis- tinguishing between the distributions of Galaxy images.
4. CIFAR-10 v.s. CIFAR-10.1. We conclude with an periment telling apart the CIFAR-10 (Krizhevsky al., 2012) and C1. (Recht et al., 2019) test sets, fol- lowing again Liu et al. (2020) and Biggs et al. (2024). The dimension is d = 3 x 32 x 32- = 3072. This is a challenging task, as CIFAR-10.1 was designed to provide new samples from the CIFAR-10 distribution, making it an alternative test set for models trained on CIFAR-10. We conduct the test by drawing n samples from CIFAR-10, and samples from CIFAR-10.1, with E {100, 500, 1000, 1500, 2000).
Several promising avenues remain. Firstly, future work could explore more sophisticated methods for improv- ing the empirical estimates of KQEs. The study of opti- mal kernel selection to maximize test power when using KQD for hypothesis testing, analogous to existing work on MMDs (Jitkrittum et al., 2020; Liu et al., 2020; Schrab et al., 2023) could also be explored. Secondly, considering the demonstrated potential of functional quantiles for represent- ing marginal distributions, it is natural to ask whether they could provide a powerful alternative to conditional mean embeddings (CMEs) (Song et al.. 2009; Park and Muan- det, 2020), the Hilbert space representation of conditional distributions. These complementary developments will un- lock new avenues for enhancing existing applications of KMES across a wide range of domains, including not only nonparametric two-sample testing, but also (conditional) independence testing, causal inference, reinforcement learn- ing, learning on distributions, generative modeling, robust parameter estimation, and Bayesian representations of dis- tributions via kernel mean embeddings, as explored in Flax- man et al. (2016): Chau et al. (2021 102)), among others.
Figure 3d presents the results. Consistent with previous ob- servations, test statistics with quadratic computational com- plexity exhibit nearly identical performance. However, our quantile discrepancy estimators with near-linear complexity significantly outperform the fast MMD estimators (MMD- Multi) of the same complexity, highlighting the practical advantages of our methods in real-world testing scenarios where computational efficiency a critical consideration.
An empirical runtime comparison of all methods is pre- sented in Figure 4, which shows the time (in seconds) re- quired to complete this experiment. The empirical results align with our complexity analysis: the near-linear estima- tors exhibit comparable performance, while the quadratic estimators are significantly slower. The proposed near-linear

---

Kernel Quantile Embeddings and Associated Probability Metries
Acknowledgements
K. Borgwardt, A. Gretton, M. Rasch, H.-P. Kriegel, B. Schölkopf, and A. Smola. Integrating structured bio- logical data by kernel maximum mean discrepancy, Bioin- formatics, 22(14):49-555 2006.
The authors are grateful to Carlo Ciliberto and Antonin Schrab for fruitful discussions on Gaussian measures and MMD two-sample testing respectively. MN acknowledges support from the U.K. Research and Innovation under grant number EP/S02 I 566/1, and from the Helmholtz Information & Data Science Academy (HIDA) for providing financial support enabling short-term research stay at CISPA (Ap- plication No. 14773).
F-X. Briol, A. Barp, A. B. Duncan, and M. Girolami. Sta- tistical inference for generative models with maximum mean discrepancy. arXiv:1906.05944, 2019.
F.-X. Briol, A. Gessner, T. Karvonen, and M. Mahsereci. A dictionary of closed-form kereel mean embeddings. arXiv:2504. /0005004488800 18830, 2025.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
A. Chatalic, N. Schreuder, L.. Rosasco, and A. Rudi. Nys- tröm kernel mean embeddings. In International Confer- ence on Machine Learning, pages 3006-3024. PMLR, 2022.
S. L. Chau, S. Bouabid, and D. Sejdinovic. Deconditional downscaling with gaussian processes. Advances in Neu- ral Information Processing Systems, 34:17813-17825, 2021a
References
Bach. Information theory with kernel methods. IEEE Transactions Information Theory, 69(2):752-775, 2022.
S. L. Chau, J.-F. Ton, J. González, Y. Teh, and D. Sejdi- novic. Bayesimp: Uncertainty quantification for causal data fusion. Advances in Neural Information Processing Systems, 34:3466-3477, 2021b.
A. Berlinet and C. Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer Science+Business Media, New York, 2004.
A. Bharti, M. Naslidnyk, O. Key, S. Kaski, and F--. Briol. optimally-weighted estimators of the maximum mean discrepancy for likelihood inference. In Interna- tional Conference on Machine Learning, pages 2289- 2023.
S. L. Chau, R. Hu, J. Gonzalez, and D. Sejdinovic. Rkhs- shap: Shapley values for kernel methods. Advances in neural information processing systems, 35:13050-13063 2022.
S. Chau, K. Muandet, and D. Sejdinovic. Explaining the uncertain: Stochastic shapley values for gaussian process models. Advances in Neural Information Processing Systems, -5500799-5079,, 2023.
F. Biggs, A. Schrab, and A. Gretton. MMD-FUSE: Learning and combining kernels for two-sample testing without data splitting. Advances in Neural Information Process- ing Systems, 36, 2024.
S. L. Chau, A. Schrab, A. Gretton, D. Sejdinovic, and K. Muandet. Credal two-sample tests of epistemic uncer- tainty. In International Conference on Artificial Intelli- gence and Statistics, pages 127-135. PMLR, 2025.
S. Bobkov and M. Ledoux. One-dimensional empirical measures. order statistics, and Kantorovich transport distances, volume 261. American Mathematical Society, 2019.
B.-E. Chéricf-Abdellatt and P. Alquier. MMD-Bayed Ro- bust Bayesian estimation via maximum mean discrepancy. In Proceedings of The 2nd Symposium on Advances in Ap- proximate Bayesian Inference (AABI), pages 1-21, 2020.
D. A. Bodenham and Y. Kawahara. euMMD: efficiently computing the MMD two-sample test statistic for univari- ate data. Statistics and Computing, 33(5):1-14, 2023.
V. I. Bogachev. Measure theory, volume 1. Springer, 2007.
Chwialkowski, A. Ramdas, D. Sejdinovic, and A. Gret- ton. Fast two-sample testing with analytic representations of probability measures. In Advances in Neural Informa- tion Processing Systems, pages 1981-1989, 2015a.
N. Bonneel, J. Rabin, G. Peyré, and H. Pfister. Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51:22 45, 2015.
K. P. Chwialkowski, A. Ramdas, D. Sejdinovic, and A. Gret- ton. Fast two-sample testing with analytic representations of probability measures. Advances in Neural Information Processing Systems, 28, 2015b.
P. Bonnier, H. Oberhauser, and Z. Szabó. Kernelized cu- mulants: Beyond kernel mean embeddings. Advances in Neural Information Processing Systems, 36, 2023.
10

---

Kernel Quantile Embeddings and Associated Probability Metries
H. Cramér and H. Wold. Some theorems on distribution functions. Journal of the London Mathematical Society, 1(4):290-29,, 1936.
A. Gretton, K. Fukumizu, Z. Harchaoui, and B. K. Sripe- rumbudur, A fast, consistent kernel two-sample test. Ad- vances in Neural Information Processing Systems, 22, 2009.
J. A. Cuesta-Alhertos, R. Fraiman, and T. Ransford. A sharp form of the woldér-wold theorem. Journal of Theoretical Probubility, 20(2):011-209, 2007.
A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(1):723-773, 2012.
M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 26, 2013.
M. W. Hirsch. Differential Topology, volume 33 of Graduate Texts in Mathematics. Peringer-Verlage New York, 1976.
1. Deshpande, Z. Zhang, and A. Schwing- Generative mod- cling using the sliced Wasserstein distance. In IEEE Conference on Computer Vision and Pattern Recognition, pages 3483-3491, 2018.
P. J. Huber. Robust estimation of location parameter. Ann. Math. Statist., 35(4))33-101, 1964.
W. Jitkrittum, H. Kanagawa, and B. Schölkopf. Testing goodness of fit of conditional density models with kernels. In Conference on Uncertainty in Artificial Intelligence, pages 221-230. PMLR, 2020.
Y. Dominicy and D. Veredas. The method of simulated quantiles. Journal of Econometrics, 172(2):235-44 2013.
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
L. V. Kantorovich. On the translocation of masses. Dokl. Akad. Nauk SSSR, 37(7-8)227-229, 1942. ISSN 10723374.
A. N. Kolmogorov. Foundations the Theory of Probability. Chelsea Pub Co, 2 edition, 1960.
the
J. Feydy, T. Séjourné, F.-. Vialard, S.-L. Amari, A. Trouvé, and G. Peyré. Interpolating between optimal transport and MMD using Sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics, num- ber PMLR 89, pages 2681-2690, 2019.
S. Kolouri, K. Nadjahi, U. Simsekli, R. Badcau, and G. K. Rohde. Generalized sliced Wasserstein distances. In Ad- vances in Neural Information Processing Systems, pages 261-272, 2019.
Flaxman, D. Sejdinovic, J. P. Cunningham, and Filippi. Bayesian learning of kernel embeddings. In Proceedings of the Thirty-Second Conference on Uncertainty in Artifi- cial Intelligence. Association for Computing Machinery, 2016.
S. Kolouri, K. Nadjahi, S. Shahrampour, and U. Şimşekli. Generalized Sliced Probability Metrics. In ICASSP 2022 2022 IEEE International Conference on Acous- tics, Speech and Signal Processing (ICASSP), pages 4513-4517, May 2022. doi: 10. 10.1009/CASSP44392..
N. Fournier and A. Guillin. On the rate of convergence in
2022.9746016. URL https: / /ieeexpllrree ieee. org/ desc///ccmet////// /wweeentt9/// 9746016 ISSN: 190X.
Wasserstein distance of the empirical measure. Probubil- ity Theory and Related Fields, 162(3-4):707-73, 2015.
I. Kong and I. Mizera. Quantile tomography: Using quan- tiles with multivariate data. Statistica Sinica, 22(4):1589- 1610, 2012.
R. Fraiman and B. Pateiro-López. Quantiles for finite and in- finite dimensional data. Journal of Multivariate Analysis, 108:1-14, 2012.
I. Gao, P. Liang, and C. Guestrin. Model equality test- ing: Which model is this api serving? arXiv preprint arXiv:2410.20247 2024.
M. R. Kosorok. conditions. Biometrika, 86(4):909-921, 1999.
Two-sample quantile tests under general
N. M. Kriege, F. D. Johansson, and C. Morris. A survey on graph kernels. Applied Network Science, 5:1-42, 2020.
A. Genevay, L. Chizat, F. Bach, M. Cuturi, and G. Peyré. Sample complexity of Sinkhorn divergences. In Interna- tional Conference on Artificial Intelligence and Statistics, 2019.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, volume 25, 2012.
A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, and A. Smola. A kernel method for the wwwsssaapppppllleeeee Advances in Neural Information Processing Systems, 19: 513-520, 2006.
A. Kukush. Gaussian measures in Hilbert space: construc- tion and properties. John Wiley & Sons, 2020.

---

Kernel Quantile Embeddings and Associated Probability Metries
E. L. Lehmann, J. P. Romano, and G. Casella. Testing stafistical hypotheses, volume 3. Springer, 1986.
K. Nadjahi, A. Durmus, L. Chizat, S. Kolouri, S. Shahram- pour, and U. Şimşekli. Statistical and Topolog- ical Properties of Sliced Probability Divergences, Jan. 2022. URL http:// /arxiv. org/abs/2003 05783. arXiv:2003.05783 [cs, stat].
M. Lerasle, Z. Szabó, T. Mathieu, and G. Lecué. Monk outier-robust mean embedding estimation by median-of- means. In International conference on machine learning. pages 3782-3787 3793. PMLR, 2019.
A. Nienkötter and X. Jiang. Kernel-based generalized me- dian computation for consensus learning. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 45 (5):5872-588) 5888, 2022.
Li, Y. Liu, and J. Zhu. Quantile regression in reproducing kernel Hilbert spaces. Journal of the American Statistical Association, 102(477):255-26)) 2007.
A. Nienkötter and X. Jiang. Kernel-based generalized me-
dian computation for consensus learning. IEEE Transac- lions on Pattern Analysis and Machine Intelligence, 45 (5):5872-5888, 2023.
F. Liu, W. Xu, J. Lu, G. Zhang, A. Gretton, and D. J. Suther- land. Learning deep kernels for non-parametric two- sample tests. In International conference on machine learning, pages 131666326. PMLR, 2020.
Z. Niu, J. Meier, and F.-X. Briol. Discrepancy- infer- ence for intractable generative models using quasi- quasi-Monte Carlo. Electronic Journal of Statisties, 17(1):1411 (7(1):141-14555 1-466, 2023.
A. Magesh, V. V. Veeravalli, A. Roy, and S. Jha. Principled out-of-distribution detection via multiple testing. Journal of Machine Learning Research, 24(378); 1-35,, 2023.
J. Park and K. Muandet. A measure theoreeic approach to kernel conditional mean embeddings. In Advances in Neural Information Processing Systems, volume 33, pages 21247-21259. Curran Associates, Inc., 2020.
N. Makigusa. Two-sample test based on maximum variance discrepancy. Communications in Statistics Theory and Methods, 53(15):5421-5438, 2024a.
G. Peyré, M. Cuturi, et al. Computational optimal trans- port: With applications to data science. Foundations and Trends@ in Machine Learning, 11(-6))355-607, 2019.
N. Makigusa. Two-sample test based on maximum variance discrepancy. Communications in Statistics- -Thiiry and Methods, 53(15):5421-5433 5548, 2024b. 2024b.
J. Rabin, G. Peyré, Delon, and M. Bernot. Wasserstein barycenter and its application texture mixing. In In- ternational conference scale space and variational methods in computer vision, pages 435-446 446. Springer, 2011.
S. Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli, (4), Nov. 2015. ISSN 1350- 7265. doi: 10.3150/14-BEJ64 URL http: //arivv. org/ abs//ab//aa / 1 1308 1334. 1308. [math, stat].
K. Muandet, K. Fukumizu, F. Dinuzzo, and B. Schölkopf. Learning from distributions via support measure ma- chines. In Advances in Neural Information Processing Systems 25, pages 10-18. 2012.
A. Ramdas, S. Reddi, B. Póczos, A. Singh, and L. Wasser- man. On the decreasing power of kernel and distance based nonparametric hypothesis tests in high dimensions. Proceedings of the AAAI Conference on Artificial In- telligence, volume 29, 2015.
K. Muandet, K. Fukumizu, B. K. Sriperumbudur, and B. Schölkopf. Kernel mean embedding of distributions: A review and beyonds. Foundations and Trends in Machine Learning, 10(1-2):1-141, 2016.
Ramdas, N. Gareía Trillos, and M. Cuturi. On Wasser- stein two-sample testing and related families of nonpara- metric tests. Entropy, 19(2):47, 2017.
J. Ranger, J.-T. Kuhn, and C. Szardenings. Minimum distance estimation of multidimensional diffusion-based item response theory models. Multivariate Behavioral Research, 55(6))941-99 9511119577,50 2020.
K. Muandet, M. Kanagawa, S. Saengkyongam, and S. Marukatat. Counterfactual mean embeddings. Journal of Machine Learning Research, 22(162): 2021.
A. Müller. Integral probability metrics and their generating classes of functions. Advances in applied probability, 29 (2):429 443, 1997.
B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do imagenet classifiers generalize to imagenet? In Inter- national Conference on Machine Learning, pages 5389- 5400, 2019.
K. Nadjahi, A. Durmus, L. Chizat, S. Kolouri, S. Shahram- pour, and U. Şimşekli. Statistical and topological proper- ties of sliced probability divergences. In Neural Informa- tion Processing Systems, 2020.
B. Schölkopf and A. Smola. Learning with Kernels: Sup- port Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA, 2002.
12

---

Kernel Quantile Embeddings and Associated Probability Metries
A. Schrab. A unified view of optimal kernel hypothesis testing. arXiv preprint arXiv:2503. 07084, 2025.
Z. Szabó, B. K. Sriperumbudur, B. Póczos, and A. Gretton. Learning theory for distribution regression. Journal of Machine Learning Research, 17(1)55722-5311, 2016.
A. Schrab, I. Kim, B. Guedj. and A. Gretton. Efficient ag- gregated kernel tests using incomplete U-statistics. In Ad- vances Neural Information Processing Systems, pages 18793-18807, 2022.
G. Székely and M. L. Rizzo. A new test for multivariate normality, Journal of Multivariate Analysis, 93(1):58-80, 2005.
A. Schrab, I. Kim, M. Albert, B. Laurent, B. Guedj. and A. Gretton. MMD aggregated two-sample test. Journal of Machine Learning Research, 24(194):1-811 2023.
I. Tolstikhin, B. K. Sriperumbudur, K. Mu, et al. Mini- max estimation of kernel mean embeddings. Journal of Machine Learning Research, 18(86):1-47,22 2017.
D. Sejdinovic. An overview of causal inference using kemnel embeddings. arXiv:2410.22754, 2024.
N. Vakhania, V. Tarieladze, and S. Chobanyan. Probability distributions on Banach spaces, volume 14. Springer Science & Business Media, 1987.
D. Sejdinovic, B. Sriperumbudur, A. Gretton, and K. Fuku- mizu. Equivalence of distance-based and RKHS-based statistics in hypothesis testing. The Annals of Statistics, pages 2263-2291, 2013.
C. Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
M. Walmsley, C. Lintott, T. Géron, S. Kruk, C. Krawczyk, K. W. Willett, S. Bamford, L. S. Kelvin, L. Fortson,
R. Serfling Quantile functions for multivariate analysis: Approaches and applications. Statistica Neerlandica, 56 (2):214-233) 2002.
Y. Gal, et al. Galaxy zoo decals: Detailed visual morphol- ogy measurements from volunteers and deep learning for 314 000 galaxies. Monthly Notices of the Royal Astro- nomical Society, 5096)):3966-3988, 2022.
R. Serfling. Approximation theorems of mathematical statistics. John Wiley Sons, 2009.
J. Wang. R. Gao, and Y. Xie. Two-Sample Test with Kernel Projected Wasserstein Distance. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 8022-8055. PMLR, 2022.
S. J. Sheather and J. S. Marron. Kernel quantile estimators. Journal of the American Statistical Association, 85(410): 410-416, 1990.
A. Smola, A. Gretton, L. Song, and B. Schölkopf. A Hilbert space embedding for distributions. In Proceed- ings of the 18th International Conference Algorithmic Learning Theory (ALT), pages 13-31, 2007.
J. Wang, M. Boedihardjo, and Y. Xie. Statistical and com- putational guarantees of kernel max-sliced Wasserstein distances. urXiv:2405.15444 2024a.
J. Wang, M. Boedihardjo, and Y. Xie. Statistical and com- putational guarantees of kernel max-sliced wasserstein distances. arXiv preprint arXiv:2405. /5441, 2024b.
L. Song, J. Huang, A. Smola, and K. Fukumizu. Hilbert space embeddings of conditional distributions with appli- cations dynamical systems. In Proceedings of the 26th International Conference on Machine Learning (ICML), June 2009.
S. Willard. General Topology. Addison- SieiseyyWWeeeyy Series in Mathematics. Addison Wesley Longman Publishing, New York, NY, Jan. 1970.
B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. G. Lanckriet. Hilbert space embeddings and metrics on probability measures. Jour- nal of Machine Learning Research, 11, 2010.
Ziegel, D. Ginsbourger, and L. Dümbgen. Characteristic kernels on Hilbert spaces, Banach spaces, and on sets of measures. Bernoulli, 30(2):1441-14577 2024.
B. K. Sriperumbudur, K. Fukumizu, and G. R. Lanckriet. Universality, characteristic kemels and RKHS embedding of measures. Journal of Machine Learning Research, 12 (7), 2011.
P. Stolfi, M. Bernardi, and L. Petrella. Sparse simulation- based estimator built on quantiles. Econometrics and Statistics, 2022.
A. M. Stuart. Inverse problems: bayesian perspective. Acta numerica, 19:451-559, 2010.
13

---

Kernel Quantile Embeddings and Associated Probability Metrics
Supplementary Material
This supplementary material is structured as follows. In Appendix A, we recall existing probability metrics, define alternative KQDs, and then describe their respective finite-sample estimators. In Appendix C, we provide the proofs of all theoretical results in the paper. In Appendix D, provide additional numerical experiments complement the main text.
A. Probability Metrics and Their Estimators
A.1. Maximum Mean Discrepancy
We first recall that the MMD is an integral probability metric (Müller, 1997) where the supremum can be obtained in closed-form:
MMD(P,Q)=
sup - || - uQlx 11
Using the reproducing property, we can then expressed the squared-MMD as
MMD? Q) = Ex.xx=/pkXXx,XXxx - (Ex=x.y==l(((xX)) +
(6)
This section describes the most widely used estimators for this quantity based on i.i.d. samples 2ı.. P and Via Q. The first is biased V-statistic estimator with computational complexity (n²2) and convergence rate On 1/2):
1 n
n
2
n
n k Mj)
MMD? (P. Q)
ko x,)
k Mi)
n²
==
Alternatively, an unbiased estimator can be constructed through a U-statistic. Such an estimator also has computational complexity (n?)) and convergence rate ((n~1/a (Gretton et al., 2012, Lemma 6;Corollary 16), and given by
(P.QQ n(n 1)
1
Σ k1),,
2
a
n
(ot,))) ninn - 1) Σ k(y. Uz)
n
A cheaper estimator was proposed in Lemma 14 of (Gretton et al., 2012). This estimator has computational complexity (n) and convergence rate (n (nn))/),, and we will refer to it as MMD-Lin. The estimator is given by:
n/2
MMD in (P.Q)
1
Σ
k(22-11,2)) k(y22-1, 924) k( yes) k( 921-1)
[n/2]
Finally, also studied estimators whose computational complexity are between that of MMD--in and the U- V-statistics estimators. These estimators are due to Schrab et al. (2022) and we refer to them MMD-Mult and takes the following form
2
MMD Muni (P.Q)= r(2n -
k( (445) ((r..14))) k(4,,8145) - k(
where r is the number of subdiagonal considered. In our experiments, to match the complexity with e-KQD, we set r = log22(r) (n). They have computational complexity Ornn).
Note that several estimators with faster convergence rates exist (Niu et al., 2023; Bharti et al., 2023), but these have computational cost ranging from O(n²) ) to O(n") and require more regularity conditions on k, P and Q, and we therefore omit them from our benchmark. Bodenham and Kawahara (2023) also introduced an estimator with computational complexity On log(n)) (and convergence O(n ((n")) using slices/projections to d = 1. However, their approach is restrictive in that it can only be used for the Laplace kernel, and we therefore also do not compare
14

---

Kernel Quantile Embeddings and Associated Probability Metrics
A.2. Wasserstein Distance
The Wassersttin distance (Kantorovich, 1942; Villani et al., 2009) is defined as
inf E (xx,))=ll((xxX) 1/2 Wp(PQQ) (E
Given samples Tim P and Mi:n ~ Q, this distance can be approximated using a plug-in W,y'/ Ee Sn. &y. which can be computed in closed-form a cost of O(n²), but converges to W,(P, Q) with convergence rate O Vin
When X' C IRd and p = 1, we obtain the I-Wasserstein distance which, similarly to the MMD, can written as an integral probability metric (Mäller, 1997):
(P,PQQ
sup 11
-Ex-
where I x - f(w) y/l denotes the Lipschitz norm.
When P. Q distributions dimensional space X C R that have p-finite moments, the p- Wasserstein distance be expressed in terms of distance between quantiles of P and Q (see for instance Peyré et al. (2019, Remark 2.30))
QP, ( Po
1/8
- dd
natural estimator for the Wasserstein distance is therefore based on approximating these one-dimensional quantiles using order statistics. Given Zim P and f/.m Q, denote by P, 1/1 Σ 6z, and Qn 1/n Σx= 6y, the corresponding empirical approximations to P and Q. Then, the [5/m]-th quantiles of P. and Qn exactly the j-th order statisties [x1:m]] and [yr. meaning the j'th smallest elements of 2 and yı:1 respectively, Then Wp(P Qn) takes the exact form
[mr= - [[m=l
(8)
and is an estimator W, (P, This estimator costs (n log(n)) to compute (due to the cost of sorting n data points), and convergence rate of (/2) for p = 1, and minimax convergence rate O( for integer p > when P, Q have least 2p finite moments. In some cases, the p rate can be improved upon to match the O(n (n--/2) rate of p = we refer to Bobkov and Ledoux (2019) for thorough overview.
A.3. Sliced Wasserstein
The sliced Wasserstein (SW) distances (Rabin al., 2011; Bonneel et al., 2015) between two distributions P, Q on Rd use one-dimensional projections reduce computational cost.
Expected SW. For an integer p 2 1, expected SW defined as
sw p (P.Q) =
((()))
where U(Sd-1) is the uniform distribution on the unit sphere Sd-11 the measures du P. ou m.##Q are pushforwards under the projection operator (x) = (u, 2). and W, the oie-dimensional p- Wasserstein distance as in Equation (7). Given Fi: P and V1.n Q, the integral over the sphere is approximated by Monte Carlo sampling of directions U1d. which together with the estimator in Equation (8) gives
(P,QP) = +
Σ w Wo #Pn, ou, #Qn) In
(((u,) [Ku,, )lm)),,
Here, [(u,, My is the j-th order statistics, meaning the j-th smallest element of (u;, 21.n) = [(44, 2.)...,, (u,, TT.) This estimator can be computed in (In log n) time (the cost on sorting n samples, for directions) and was shown to converge at rate (22-1/ 2/2 + n 122 for p = (Nadjahi et al., 2022).
15

---

Kernel Quantile Embeddings and Associated Probability Metries
Max SW. The max-sliced Wasserstein (max-SW) distance (Deshpande al., 2018) replaces the average over projections in expected SW with supremum over directions,
max-Sw (P.QQ) = sup (I 1/2 AMESO-1
where, (x) (u, z² is again the projection operator, and W, is the nne-dimensionaly p> Wasserstein distance of Equation (7). Max-SW emphasizes the direction of greatest dissimilarity between the measures.
Given Jim ~ P and Vio ~ P. max-SW is estimated as (o # P, our #Q), for u² the projection that maximises (o(O pu #nn) as given in Equation (8). In (Deshpande et al., 2018), u" was approximated by optimising a heuristic, rather than the actual WB (du# Pn,, Du #n)). Then, Kolouri et al. (2022) approached the actual problem of
u' argmax (0 PP #Q.).
||u||=1
by running projected gradient descent on S where each gradient step requires computing the derivative of the 1D Wasserstein distance w.r.t. u. Concretely, they initialise 2n randomly and iterate
Ux++1 projge-1 (Voplim(V..Wgg (du, #P, on, #Q), una)):
where Projs=-1(2) x/|| is the operator projecting onto the unit sphere, and Optim is an optimiser of choice, such as ADAM. Each evaluation of Wp and its gradient in one dimension costs On log n). so the overall complexity O(Tn log n) for T gradient steps. It is important to point out the optimisation may be noisy, with the value objective getting worse after some iterations. Indeed, if 2441 is the solution to Optim ( V V. W
p (Øn, # P, &u, #Q), u1:e), is it improvement over u4 meaning (0 HP, Qu, #Q) I Wp(O # daa #Q). Written out explicitly,
Σ xim))s [uu, Bim) S
Σ
(1(241171mm) - Him))al' 5=1
Then, u++1 = Projsa-1 (2++1) = 24+1/|22++111 |l. and it may happen that (o #P, on, #Q) > WP #P. Ou #Q).
The desired (o # P., Q.. #Q)= S WP (0uri # Ouetr #Q) guaranteed when || 1| S 1, which may not happen.
A.4. Generalised Sliced Wasserstein
The generalised Mlix-ss Wasserstein (GSW and max-GSW) distances (Kolouri et al., 2022) extend SW and max-SW by using a family of nonlinear feature maps (Jo Rd + R RJace instead of linear projections. Formally,
max-GSW, (PP.) = sup W3( 1/2 AEE
GSW, = (Bo,))))(Bo,,, (,(O,,,,00
where P denotes the pushforward of by fo and μ is a probability measure over the parameter space θ. For fa(x) = x) and θ 5 with uniform p. GSW reduce to the standard SW distances. For expected GSW, sampling {0.) ~ μ yields estimator with the same OIn log n) computational complexity expected SW (Kolouri et al., 2022). For max-GSW, the projected gradient descent approach of Equation (9) applies, at the same complexity of O(Tn logn) as for max-SW.
Statistical and topological properties of GSW depend completely on the choice of the family {ffe f E θ}. Kolouri et al. (2022) consider the specific case of polynomial fa. and show GSW is then metric on probability distributions on Rdd
A.5. Kernel Sliced Wasserstein
A special case of the GSW arises when the feature maps fo are drawn from reproducing kernel Hilbert space (RKHS). Let k d x d + R be positive definite kernel that induces the RKHS H with unit sphere Sn. Then, the kernel sliced Wasserstein (KSW) can be introduced as
1/0 max- MIN-KSW,CC (P.QQ = sup Wf(u#P, ((u#P,u#()) u+4
c-KSW, Q) = (Euny WP u#Q)) 1/2
(uESK
16

---

Kernel Quantile Embeddings and Associated Probability Metries
where 7 is some probability measure on Sx- The expected KSW is new construct, while -SX was introduced in Wang et al. (2022), and studied further in Wang al. (2024b); in both papers was assumed to be universal. Finding the optimal u" for max-KSW was shown to be NP-hard in Wang et al. (2024b); they propose an estimator at cost O(TS/2n)) Though still more expensive than computing the V-statistic estimator of MMD, this is an improvement over ( in the original work of Wang et al. (2022).
As pointed out in the main text, the choice of uniform 7 in e-KSW, while seemingly natural, may not be feasible as there is no uniform or Lebesgue measure in infinite dimensional spaces. In the main paper, we propose a practical choice of y that facilitates an efficient estimator, and study computational cost. Further, we establish statistical and topological properties that apply to both expected and max-KSW-- and do not assume a universal kernel.
A.6. Sinkhorn Divergence
The entropic regularisation of optimal transport leads to the Sinkhorn divergence (Cuturi, 2013; Genevay et al., 2019). For distributions P, Q and regularisation parameter ε >> O, the entropic OT cost is defined as
Bxx - YIP] cTI 4/
(P,Q) =
inf (EEI(P,))
The Sinkhorn divergence then corrects for the entropic bias:
Sp.e == (P..( - (P.
(Q, Q)/2.
(10)
This quantity interpolates between MMD-like behavior for large and true Wasserstein for - 0, and can be computed efficiently via Sinkhorn iterations cost (n²)) per iteration (Cuturi, 2013).
A.7. Kernel covariance embeddings
Kernel covariance (operator) embeddings (KCE, Makigusa (2024h)) represent the distribution P the second-order moment of the function -xX,-), for X ~ P. as an alternative to the first-order moment (the kernel mean embedding). Due to being moments of the same distribution, the two share key positives and drawbacks: KCE for kernel &o exists if and only if KME for k2 exists, and the kernel k is covariance characteristic if and only if k22 is mean- wwean-chaaacteristic (Bach, 2022). The divergence proposed in Makigusa (2024b) is the distance between the KCE, and is estimated at ((n3) due to the need to compute full eigendecomposition of the KCE in order to compute the norm. In contrast, our proposed kernel quantile embeddings (KQE) embed quantiles, and therefore the relation to the KCE comes down to matching quantiles (which always exist, and come with efficient estimator), compared to matching the second moment in the defnite-dimmnsionn RKHS (which may not exist, and requires eigenvalue decomposition)..
A.8. Kernel median embeddings
The median embedding (Nienkötter and Jiang, 2022) of P the geometric median of k(X,),, in the RKHS, meaning the RKHS element which, on average, is L' cloossst to the point k(X..). .). Explicitly put, is the function medp H defined through
medp- argmin / [l,(.) - k(x, )llx
JEH
The median exists for any separable Hilbert space (Minsker, 2015). However, even for an empirical Pa = =1/n 11/E Σ Sg. there is no closed-form solution to this L -problem, and the median is typically approximated using iterative algorithms like Weiszfeld's algorithm. The estimator proposed Nienkötter and Jiang (2022) has a computational complexity of (n²). The property of being reddianchaaaccteristic,, as far as the authors are aware, has not been explored, and no theoretical guarantees are available.
The connection to ID-projected quantiles as done in KQE, even specifically the ID-projected median, is also unclear. Expanding the understanding geometric median embeddings is an area for future research.
A.9. Other Related Work
Kernel methods have also been studied in the context of quantile estimation and regression (Sheather and Marron, 1990; Li et al., 2007). These methods, however, focus on using either kernel density estimation or kernel ridge regression to estimate
17

---

Kernel Quantile Embeddings and Associated Probability Metries
univariate quantiles. In contrast, our focus lies in exploring directional quantiles in the RKHS, and using them estimate distances between distributions. We introduce this idea in the following section.
B. Connection between Centered and Uncentered Quantiles
Proposition 2 (Centered e-)QD)), The e-KQD2 and Sup-QDD correspondence derived based on centered directional quantiles, now expressed as (P: 7 and sup-KQD, (. can be expressed as follows,
=
E (Bxx((xxx -xy-o/)))--y--U)))
2 (
sup-KQD, ")=
(P, 1, (Ex~plu(X) -Bx-))]IExx-ll(x] (MD)((P.Q)
sup HESH
2 Sup-KQD,
MMD)((P (MM
Proof. Let P,Q Px be measures instance space X. Further, define s - k(x,, +), and write P.: x P and Q2 #. Now Pe and Qu are measures on the RKHS H4. Recall the definition of centered directional quantiles in Section 2.1,
20.1 Pp
= (Po. - (x(Bx>P, + By Ey [Y]
Now since we are working in the RKHS Hk. the expectation term Ey [Y] corresponds the kernel mean embedding Mp = Ep(k(X,,)) )), thus rewrite the above expression as,
20.0 Pp
(Pow#Po - (p)) a + up
PQ. can be defined analogously. Now consider integrating the difference between the two centered directional quantiles along all quantile levels, leading to
.0."
(L pa. - PQx 1 lInn
(P.Q..),)))
(11)
We now proceed to show 73 Q, μr, u) ,whee y is the Lebesgue measure, can be expressed as sum between an uncentered e- e-KQD, term with the MMD. Starting with expanding the RKHS norm inside the integrand,
20. 1Ppp
PQ. lift
11 [1
Pb. (u, uP (Q) + ur 1
=:AER
||Au (MP -m2)
-((Au, HP (u)) + ||Au|| + 11ppp- - mell
=2A(u, HP - (Q) + A2 (P.Q((P.))
(12)
Plugging the expression from Equation (12) into Equation (11), we get the following.
(P,Q. - S HP - pQ) + A²) + (M.)((PQ)
= =(u,, ur -app-aa ua) S'' Au(da) (' +Pp(da)+MMD2(
(13)
For the first term on the right hand side, notice that,
S Ap(da)) = / -
Po_ - - (u, up - (e)))((a))
(14)
18

---

Kernel Quantile Embeddings and Associated Probability Metries
Recall standard results from probability theory that integrating the quantile function between with the Lebesgue measure returns you the expectation, specifically, that is,
L #o,aa, = Ex-r[u(X]] (u, pP).
Using this fact, the terms in Equation (14) cancels out, leaving So Ap(da) = O. Therefore, continuing from Equation (13), we have,
(P.Q..p)))) f A2 (MD
(DoNtPo - Pon#Q0 - (u HP - 12)) u(da) + MMD*((.Q)
L 11 100% ((
u(da) + MMD)((PQ)
where Spr.u R - IR is a shifting function defined spp,u(r) - (u, for E IR. Alternatively, after expanding the terms in AZ, we can express 72 Q, M, u) as,
(2 = L. (Don#Po Pbu#Q. -Po.4q. - (Elu((X) =()))) MMDD
= (P. + MMD?(P.Q) - (E(u(X) =(
As a result, for y a measure on the unit sphere of H4. the centered version of e-KQD, and sup-KQD,, now expressed as e-KQD, and sup-KQD are given by,
c.KOD,(P.Q:H.))
= Eunyy (;
= =c-KDD((P.Q:A.))) - (M,)( - E (Ex- - By>olu(Y))) <c.KO,((.QQ:.nn)² +MM)((P.Q)
sup-KOD,(P,Q0:444) = sup
WESH
(T2 Q,,, - (E] - B(u(()))) + MMD?((P
= sup
nESn
s sup
TP -sup (E|u Blu(())) + MMD?((
sup
w
WESH
< (PPp MM.2
When = j and the connections Sliced Wasserstein explored in Connection and Connection 2 emerges, the mean- shifting property of Wasserstein distances allows us to express centered KQD as sum of uncentered KQD, and MMD curious interpretation of centering.
C. Proof of Theoretical Results
This section now provides the proof of all thcoretical results in the main text.
C.1. Proof of Theorem 1
The main result in this section, Proposition 3, shows that the set of Ih measures (u#P u E Sx) fully determines the distribution P. Since quantiles determine the distribution. Theorem follows immediately.
Being concerned with the RKHS case specifically allows us to prove the result under mild conditions by using characteristic functionals, an extension of characteristic functions to measures on spaces beyond Rdd Characteristic functionals describe Borel probability measures as operators acting on some function space F: X R.
19

---

Kernel Quantile Embeddings and Associated Probability Metries
Definition 1 (Vakhania et al. (1987), Section IV.2.1). The suntracct up : F C of Borel probability measure P on X is defined as
(r(f) / (2 P(dx).
Theorem 2.2(a) in Vakhania et al. (1987, Chapter 4) establishes that P-characteristic functional on F uniquely determines the distribution P-on the smallest o-algebra under which all function F are measurable. Therefore, when F is such that this o-algebra coincides with the Borel o-algebra, the distribution is fully determined by P-characteristic functional on F. We show that, indeed, this holds our setting, for F = H.
Lemma 1. Suppose Al and A2 holds. Then, the Borel o-algebra ((x) is the smallest o-algebra on X under which all functions f E H. are measurable.
Proof. Denote by Č(X, H) the smallest o-algebra on X' under which all functions f E H. are measurable, and recall that the Borel r-algebra the o-algebra that contains all closed sets. Therefore, we need to show that Ć(x, 7) contains every closed set in X. We split the proof into two parts: (1) show that contains a countable separating subspace, and (2) show that this implies that every closed set lies in C(X, (H).
H. contains countable separating subspace. Recall that function space F on X is said to be separating when for any # I2 E X, there is function f E F such that fx1 # f(z2). Since k is separating, H is separating. Since H is separable, it contains a countable dense subspace Ho C H. By Ho being dense in H. it must also be separating.
Every closed set lies in C(X, H). By Vakhania al. (1987, Section I.1, Exercise 9), all compact sets X lie in C(X' Ho), by Hn being countable, continuous, separating space of real-valued functions. By definition, C(X, Ho) C(X, H), and so Č(X, H.) contains all compact sets. We now show this means every closed set must also lie in C(X', H.).
By being o-compact, there is family compact sets { such that X L Take any closed K S X; then, K _ (K). Since X; & compact as the intersection of a compact set and a closed set, and o-algebras are closed under countable unions, K must lie in C(X, H). As this holds for every closed K, we conclude B(()) C(X H).
now restate the RKHS-specific version the Vakhania result here for completeness.
Theorem 6 (Theorem 2.2(a) in Vakhania et al. (1987) for RKHS). Suppose Al and A2 holds, and for Borel probability measures P. Q on X. holds that up((f) = (f) for every f H. Then, P=
We now ready prove the distribution of projections uniquely determines the distribution.
Proposition Under Al and A2, holds that
u# P = u#Q for all u E SH + P=Q.
Proof. The main idea the proof is to show that equality of u# P and ##Q implies equality of characteristic functionals, (pp(f) = (f) for all f E H such that f(x) = tu(x) for some / I and the unit sphere. Since such f form the entire H. the result immediately follows.
First, recall that u# P = u#Q for all u if and only if their characteristic functions coincide, meaning
[ itz ## = / ( (((=) Vu Sn, e
(15)
Notice that the measure u# P a pushforward of P under the map x - u(x). Then, for any measurable g holds that
[ glu(=)) = ((2))##((ds Yu E Sx.
(16)
Take g(2) = itt for some t E R. Then, for all u it holds that Ja tt et u = Jg e ((dz). and consequently
by (15) we have that
[ utull))
/ (tt(() Vu E Sz, Vt ER.
(17)
x
20

---

Kernel Quantile Embeddings and Associated Probability Metries
Finally, let pick an f E H and show that sp((f) - (.((). Define = -//I[[],, and L = [|/l|: then,
pp(s) 1 eo/(t) P(dx) Ixe ((tu(() ((uu())((dx),
and by (17), we arrive at the equality of characteristic functionals, (pr(f) = (f((f) ). By Theorem 6 characteristic functionals uniquely determine the underlying distribution, meaning P = Q.
For the sake of clarity, we give the proof of the original result.
Proof of Theorrmm I. Suppose {op- a E 10. E SH} = [0g 100==aa a E [0, E Sx} for some Borel probability measures P.Q. For any fixed u, since every quantile of of u# and u#Q coincide, the measures coincide as well, u# P Q.Q. As that holds for every u. by Proposition 3, P PQQ. Q.
Lastly, we point out Al may be relaxed. Provided X' is a Tychonoff space-paaseee meaning, completely regular Hausdorff space-part part (b) of Theorem 2.2 in Vakhania et al. (1987) says the following.
Theorem 7 (Theorem 2.2(b) in Vakhania et al. (1987) for RKHS). Suppose X is Tychonoff. A2 holds, and for Radon probability measures P. Q on X, holds that (p((f) = PQQ (f) for every H. Then, P Q.
Therefore, when Al is replaced with X' being Tychonoff, Theorem I continues to hold-but only for Radon P,Q, not any Borel P. Q. Radon probability measures can be intuitively seen the "non- noonppahological" Borel measures- restriction employed in order to drop the regularity assumptions of X being separable and o-compact.
C.2. Proof of Theorem 2
We prove that every mean-characteristie kernel is quantilecharaacterstiic, and give example quantile-characterstte kernel that is not mean-characteristic.
mean-characteristic + quantile-hharacterstti. Suppose on X' is mean-characteristic, and P o Q are any probability measures on X. We will identify unit-norm for which the sets of quantiles of u# P and u#Q differ.
Since is mean characteristic, pup * pQg, and MMD3 Q) = 1|pp m2ll > 0. Recall that MMD can expressed as
(MDQ(P.Q)= sup HE
(xx-Pu(X-EY-qq((() Er-qu(Y)),
and the supremum is attained at =² = (up - -upp=p)/llee-ol Hollx (Gretton et al., 2012). In other words, Ex~pu" (X) + Ey-qq"(() (Y)) the means of u² # and u" #Q don't coincide. Therefore, the measures u² #"# and u² ### don't coincide, or equivalently { : a E [0, 1]} A {p-- a E 1]3. Then, (p a [0, 1], u E SH3 A tgg a a [ 1]. Sx.. And since this holds for any arbitrary P + Q, the kernel is is charattecccarrcceristti....
quantile-characterisiic A mean-characteristic To show the converse implication does not hold, we provide an example but not mean-characteristie. Take X' Rd. and let l be degree T polynomial kernel, x' + 1)T. Since Al and A2 hold-IR Rd is Polish, and A is trivially continuous and separating by Theorem I
when & is quantile-characterise
k(x,,') = Tx' the kernel & is quantil-chharacteristi..
Now, we show k is not mean-characctrrsticc. Suppose P and Q are such that Ex-PX*= = EY for i (1,..., ,,, T) for example, the Gaussian and Laplace distribution with matching expectation and variance and T 2, as is done in Section 5.2. Then, EX~P(X xa)² = EY=P(YYT T'')i for any x' E IRd, and since
T Σ (1) 1=0
pr(x')= == Ex=rk(X,z)) = Ex=p((XTad T + 1)-1 = ExaP
Σ 1=
1 (X (XT
2''" (XTx7))
Ex-p (xxT2))..
holds that po = MQQ. The kernel not mean-characteristic.
21

---

Kernel Quantile Embeddings and Associated Probability Metries
C.3. Proof of Theorem 3
By the Theorem in Serfling (2009, Section 2.3.2), for any E >> 0 it holds that
fu#r(t)dt, f
P( Pu#pll E) 2e 2nd2 2222
for 8. = min
Piup-e Susr(()at)
Pump
Since it assumed lu#p(z) 2 Cu > 0, it holds that de Gue, and P(lpürr. Pugrl > 8) 2e =e=2ne equivalently,
P(PPu Pu#pl SE) 2-22 -2
Take 8 = 2e = Then,
P(PPupP. - Puuell S C(o, ()00,))mm19 1/2) 2 1 - 5, for C(6,u) = log(2/6)
2c
Since I|pr,"
a.u Pp
11 = Putrr Puprll the proof is complete.
C.4. Proof of Theorem 4
We prove eQD and sup- KQD, defined in Equation (4) as
(PKQ = (Eung (P. 4/- Tp (P,Q; 4/ NESx
suP-KO = sup
are probability metrics on the set of Borel probability measures on X. Symmetry and non-negativity hold trivially. Triangle inequality. By Minkowski inequality, for any P, Q.
[ 108 /f.11xu(da)) S (V/ 108 n8 (8l((dd)) 1/8
+ (1,1 lna p8 (u(i)))
1/2 p
Plugging this in and using Minkowski inequality again on the outermost integral, we get
Boen (
1B. 1p3-1--''udan 1/8
P'; (P),.))
Ensry (16') 10B 108--88 -18l (((((d)) 1/0
1/p m 1/v
+ (f/)) 108 - -p (2o
1/8
Buny 1/' 10B P81 p8l(v(dda)
1/8
pp + (Eunn 1'' I08 11p- (p()a(((d)
22

---

Kernel Quantile Embeddings and Associated Probability Metries
Similarly, since s [P(x)) (sup, (())) for any
( (5--0.PP((d))) 1/8
sup-KQD, PP p1,)))
sup
Sx
(() 108 -pal -a0l" v(dai)
1/0
sup WESN
(S, 108 - -pp -p8.1""v(dae (l((aaaa) )
1/p P 1/8
I |88 p81 ((((da))
1/8
sup SEEH
{ p8 -pp. - sup UESH
1/2
sup-KQD, Sup-KQD, (Q) P0,0P' ;,,7)
Identity of indiscernibles. In the rest of this section, we show that (KQOD,(PQuxx))
P P= Q: and sup-KOD,(P.Q:vz.))
= P=Q.
Necessity (meaning the < direction) holds qrivially-quantiles identical measure are identical. To prove sufficiency, we only need to show that both discrepancies aggregate the directions in way that preserves injectivity, meaning
e-KOD,
Pp
c.a a. for all a, u; and sup-KOD, (P.,D,,,P..) 0 Pp
PQ
PQ for all a, u.
Together with Theorem 1, this will complete the proof of sufficiency.
First, we show that for any pair of probability measures, a v-aggregation over the quantiles is injective. Lemma 2. Let have full support, meaning v(A) 0 for any open C 10. For any Borel probubility measures P'Q',
12g S.¹ P -
p6. = p& for all a E
Proof. Suppose Jn l0g.- 1v((a)))) O. but there is an ag such that ppr = PQ' We will show that this implies the existence of an open set (containing ax) over which Ipp: 1 0-which will contradict having full support.
Since l0p p 1 > 0 and the quantile function + of is left-continuous (by definition) for any probability measure P. there is 0r < og such that Ip.. p 2 for all a E (01, ag]. Take some 02 (01, og). Then, for all a E (a1, 02). we have l0p- p |2 > We arrive at a contradiction. Such ag cannot exist, and therefore pp. = P& for all a E [0,
This result applies directly the directional differences Tp. Provided v has full support,
Tp P. (P.Quu,u)= =
p p = P for all a [0.
Since supremum aggregation simply considers that corresponds the largest TP, v, u), this concludes the proof for sup-KQD. Expectation aggregation over the directions needs an extra result, given below.
Lemma 3. Let y have full support on Sn, and have full support on [0. 1). For any Borel probability measures P,Q on X.
Busry ( u)
P=Q.
Proof. Same as in the proof Theorem 1, we will use the technique of characteristic functionals pp, PQQ, to carefully prove equality almost everywhere with respect to a full support measure 7 implies full equality. Consider the function
f (-(r(() - (f)
23

---

Kernel Quantile Embeddings and Associated Probability Metries
which is continuous by continuity of characteristic functionals. Define fo 0, the zero function in H. The
H = (f E H (fo) =p((f) - (P((f) E R [0)] = (f E H (fo) : (p((f) + po(s)}
is open, a preimage of an open set R \ {0), intersected with an open set {H \ {fo}}. Since the projection map + S/1l/l is open on H {oo), the projection of Hi, onto SH is open. In other words, the set
* = {u E SH (p((uu)) & (p((uu) for some iu E RJ
is open in S4. Then, by definition of characteristic functionals, for E S it holds that
(uu) (p (t (t#)(tt))
meaning the characteristic functions u# and u#Q are not identical, and therefore u#P + u#Q. Since v has full support on [0, 1], it follows that
(PP.Quu,u) 1 Piip-- Pa#q
Pa#ql"u(da) (v(l)ddd))))))))))))<))) > 0, for all u E S
We arrive at contradiction: since y has full support Sy and
5/0 S2 was shown to be open set, it holds that
S
E 2
> 0.
s/p
Therefore, for Eu Q; u) to be zero, S must be empty-wiich, by construction, can only happen when 7/ is empty, i.c. (p(() = (f) for all f E H H,),A for where fo = O. Since (p(fo) @Q (fo) holds trivially for any P, Q.Q. the characteristic functionals of and Q are identical. By Theorem 6, P == Q. This concludes the proof.
C.5. Proof of Theorem 5
We start with two auxiliary lemmas that, when combined, bound e- K-Q approximation error due to replacing P, Q.Q with Pa. Qn in 1/2 This will be crucial in showing convergence of the approximate e-KQD to the true e-KQD.
Lemma 4, For any measure v on [0, 1) and any measure on SH, it holds that
le-KOD, (Pn, Qniu, (P, e-KQD, (Pn, P.u,)) K ()))
Proof. By the definition of e-KQD, and Jensen inequality for the absolute value.
Bunn [h' (IR Piteeal -I Pu#q da
Ie-KQD, ( --Q,, (.0
Buny [/" ||PuTr -uut |i Pupellda
By the reverse triangle inequality followed by the triangle inequality,
I P. - Pu -lpu - PuwØll
s 10 P.. Pup p + Pu#a - Pu#e.l lou Puy pl + +I Puppl
(18)
and the statement of the lemma follows.
Lemma 5. Let v be a measure on Jo, 1] with density fu bounded above by C2 > O. With probability at least 6/ for C²(8) = 2C, /log log(8//)/22 it holds that
e-KQD (P..))) <
2 n 1/2
24

---

Kernel Quantile Embeddings and Associated Probability Metrics
Proof. Recall that
eP P;u,7) Bryyy (T) (Pas (P uiv,u), (PPn, = / 1Ro#es -Rusplydda).
Let Fugp and Pu#P, be the CDFs of u# and u.PP respectively. Then,
S( [ Pünp Payplu(da) S Cp // Pinn, Pug plaa -C Cv / Fu#Po. (t) - F Fu#r(t)|ds
u(x)
sup Fa#tr F Fu)r(t)), nEu(X)
where the last equality is the well known fact that integrated difference between quantiles is equal to integrated difference between CDFs (see, for instance, Bobkov and Ledoux (2019, Theorem 2.9)). By the Dvoretzky- Kiefer- Seefer-Wolfowiz inequality, with probability at least 6/4 it holds that,
sup |Fu P. (1) Fu) < /log(8/0)/22n112
20, and therefore, with probability at least 1 - 6/4 for (²))) - 20,2 /log///////0//.
Ti (P P;k,u) 1/¹ Putp. P())) <
C²
2
In other words, the random variable ti (Pn, Pi u) is sub-Gaussian with sub-Gaussian constant C, == C2/(2n) meaning
Pr (r Piu, u)
One of the equivalent definitions for sub-Gaussian random variable is the moment condition: for any p 2 1,
Eri.. (P,, P;u, 2
An application of Jensen inequality and Fubini's theorem shows that the moment condition holds for BEw TI P; u),
ErE. [Eury T1 (P u),, < Er,.. Bany (P,, P, 21), = E... (P., P; u) 5 2CTT(p/2 1).
Therefore, Buny 71 (Pn, P.v, u) sub-Gaussian with constant C, = C// (2n), meaning it holds with probability at least 5/4 that
C²
(P,, (Pn,) Eus,y T1 (Pn, P;v
2 n 1/2
We are now ready to prove the full result.
Proof of Theorem 5. Let C₂ be an upper bound on the density of v. By triangle inequality, the full error can be upper bounded by R₁, the error due to approximation of y with nts plus R,, the error due to approximation of P, P.Q with P,, Qn.
- - (eKKD, (Pn, Quius 7) e-KQD, Qniu, + Io-KOD, (P,, Qniu,) (OO
R + R.,
We bound Ri in 1-122 and R2 in -1/2, with high probability.
25

---

Kernel Quantile Embeddings and Associated Probability Metries
Bounding Rs Recall that e-KQD (Pn, Qn) = Bury Jo Pü#r Pa# (u(da)) Therefore, we may apply McDi- armid's incquality provided for any u, uf E Sx we upper bound the difference
1,x
Pa#p Pu+el
I Pu#al u(da)
We have that
Jo' |G*#P -uu#Ql
(A) PP Pw v((da)
/ Pu#e Pu##
-u# v(da) + f fiezol
(B)
2C2 sup W Wi u+Q) uESN
2C, sup Ex-pBy-qlu(X -x)))(X)) wESH
-
k(X, -k A(Y,Y
where (A) holds by Jensen's and triangle inequalities; (B) uses boundedness of the density of by C₂ and the property of the Wasserstein distance in I from Equation (7); (C) uses the infimum definition of the Wasserstein distance; and (D) holds by the reasoning we employed multiple times through the paper, via reproducing property, Cauchy-Schward and having u, E SH. So we arrive at a bound
Lo Pupp Puwel - 1p P v(da)
Now that boundedness of the difference has been established, by McDiarmid's inequality, with probability least 1 - 5/22 and for (5) C2 log(4/6) it holds that
CC"
Bounding R. By Lemma 4,
le-KQD (Pns Qni4,)) <Q (C. Q;44))
By Lemma and the union bound, with probability at least 1 - 5/2 and for (* = 2C, 2C, it holds that
Rs (e-KOD, Qniun) - (Q.0;
7) s ('()
Combining bounds.
By applying the union bound again, to R& + Rn, we get that, with probability at least 1 - 8,
(-KOQD, Qn; m) KKO
R R. S CC CC C') (0)mm11/2 1/2 ((())(11112 n 1122) n
for C(o) = max mmxxmaxx)p (C)( (*) ( (ooTTg((1/)) This completes the proof
As pointed out in the main text, Bx>-PBy-QVA(X,X) Ex~PVk(X,X) and Ex=Qvk(X,XX) are finite, and even more specifically, when the kernel & is bounded. Unbounded and finite expectations, for example, happens when the tails of both P and Q decay fast enough to "compensate" for the growth of k(x,,) æ). For instance, when is polynomial kernel of any order (which is unbounded), and P and Q are laws of sub-exponential random variables. For clarity, note that Exx / xX,,X) 2k(X, Y) + k(Y, Y) does not compare to MMD, which integrates (() rather than X, X) (see Equation (6)).
21,(X, Y) +(Y,Y) < oo holds immediately when
For integer > 1, proving the n- 1/2 convergence rate is feasible if more sooovvd--rimmrriyy because we can no longer reduce the problem convergence of empirical CDFs true CDFs. In general, for p > 1,
S. PiSP, Pl # [x(
|uurr, (1) Fut Par.
Ju(x)
The following result, restated in our notation, makes the added complexity explicit.
26

---

Kernel Quantile Embeddings and Associated Probability Metries
Lemma 6 (Theorem 5.3 in Bobkov and Ledoux (2019)). Suppose k IR R + R is a bounded kernel, and has density 0 Cv fo s Cv [0, 1. Then, for any u E SH, and for any p 2 1 and 1,
5pCy
(F) P Pu dl (upp(z)
B (: -
vn++2) Jp(u#P), for Jp(u#P)= Je(x)
Further, holds that P (T P: =(nn [(n]) if and only if P) 20.
We now state a likely result for p > 1 as conjecture, and outline the proof.
Conjecture 1 (Finite-Sample Consistency for Empirical KQDs for p 1). Let X R v have density, P,Q be measures on X with densities bounded away from zero, fr( 2
0 and fe(x) 2 cQ > 0. Suppose
Ex-P Exxp)k(X, X x) < oc and E (x>qlk(k (K(X, X) co, and Tim ~ P.Vim Q. Then,
E rlen- Qn:u, e-KQD, (P.Q., 7) 0 1/2 + n V2).
Sketch proof. Analogously to the proof of Theorem 5, we can decompose the term of interest
Er VianQ
(o... Qnivmn) c-KQD, -
S ExL e-KQD (Pr, Qniv, m) - e-KQD, (Prs Qniv, 7)) M
P3 n)) 1/8 (Ev (e Q Qi4,)))
The first term can be, same as in the proof of Theorem 5, bounded by McDiarmid's inequality. The second term (to the power p) takes the form
E EE pe- PaiineeeeD (P., Ex... 1 (p P.v,
Then, by Lemma 6 (possibly modified to account for extra expectation), to get the result we will need show that Tn < co,
Eusry (u#HP) = Buewy / (x(x)
P
di
< x
The nominator is upper bounded by P The denominator may get arbitrarily small without the nominator getting arbitrarily small: when the PDF (z) is small, the CDF Fug ((x) need not be close to zero or one. Therefore, it is necessary and sufficient to show
E Euvy
dt oc.
(19)
(((x) (
We proceed to outline key elements of the proof of such result, and leave a rigorous proof for future work. By the coarea formula, and since fr(x) 2 cp >
fu)p(t) = / (w-1(e) [u(x)]
fp(x) (dx) 2 00 S,- Ju-1c) Vu(x))
Hd (dx), for Vu(x)] =
Σ
d
(u((x) 2
Ox;
where u- -t)) (a X u(x) t). and Hd is the d 1-dimensional Hausdorff measure, which within X S Rd is equal dimensional Lebesgue measure, scaled by constant that only depends d 1. Therefore, the integral in Equation (19) may diverge the integral
J.- 11-10 Vu(x))
1
Hd (dr)
(20)
gets very small over "large" parts of ((X)) on average over u ~ y. Trivially, if is constant over some interval or more generally, a has infinitely many critical points- thh integral diverges. Fortunately, the more general condition easy to
27

---

Kernel Quantile Embeddings and Associated Probability Metries
control: if u is a Morse function and X' is compact, then has only a finite number of critical points. It is classic result (see, for instance, Hirsch (1976, Theorem 1.2)) that Morse functions form dense open subset of twice differentiable real-valued functions on R² denoted C² Therefore, if H C C² (which can be reduced to smoothness of the kernel k-it holds for instance, for the Matérn-5/2 kemne),, we get that u has a finite number of critical points almost surely under mild regularity assumptions on 7-
The final ingredient is to use the Morse lemma to lower bound Equation (20) in the epsilon-ball of each critical point. Morse lemma says u is quadratic around each critical whith-which yields bounds on both the volume of u (t) and 1//Vu(z)] in
terms of the eigenvalues of the Hessian. Careful analysis of the eigenvalues will be needed to ensure the expectation with respect to u ~ yy is finite.
C.6. Proof of Connections and 2
The equality in Equation (7) immediately gives the connection of c-KQD and sup-KQD to the expected-SW and max-SW previouul only defined on X' = Rdd.
Further, for X' = IRd, viewing x k(z,-) transformation on X' reveals connection to Generalised Sliced Wasserstein (GSW, Kolouri et al. (2022)). In particular, the polynomial kernel k(xx,, x²) = (x x' + 1)" of odd degree T recovers the polynomial transformation for which GSW was proven to be a probability metric. Outside of the case of the polynomial case, proving that GSW is a metric is highly challenging. This is easier under the kernel framework, as we showed in Theorem 4. In Kolouri et al. (2022), the authors investigate learning transformations with neural networks (NNs). An interesting direction for future work is the relationship between said NNs and the kernels they induce.
C.7. Proof of Proposition 1
Recall that by definition of Gaussian measures in Hilbert spaces (Kukush, 2020), a random element f E H has the law of a Gaussian measure (O, Cm) on H when for any g E H.
(f N(0, (Cmlgl. g)).
(21)
Since C. (z)) = 1/m Ey= o(2,) (22)) x),, by the reproducing property,
(Cmlgl. = g g(z))2
(22)
Take f(x Em Xyk(2,, r),, for Ai...., Am NNO Id). Then, for any g E H. by the reproducing property it holds that
1 {))(())) N 0. m
(f,9)=
Vm
which is exactly the Gaussian measure with covariance operator Cm, as per Equations (21) and (22).
D. Additional Numerical Results
D.1. Type I control
We report the Type control experiments for the CIFAR-10 v.s. CIFAR-10.1 experiment. Results are shown in Figure 5.
D.2. Figure for e-KQD,
is common power p-parametrised methods to select p = 2, balance out sensitivity outliers (which is higher for larger p, the point of methods becoming brittle for p > 2), and robustness (which tends to be highest for p 1); this trade-off, for instance, inspired the introduction of the Huber loss (Huber, 1964). However, for completeness, we now repeat experiments in the main paper for = 1. The relationship to baseline Hpproaches-MMD. MMD-Multi, and HMMD-Linremmain the same as observed for p = 2. However, it is evident that e-KQD, performed better than e- e-KQD, at the power decay and galaxy MNIST experiments, but the centered e-KQD; performed worse than centered e- e-KDD, at the Laplace v.s. Gaussian experiment. The implications of choosing p warrants a deeper investigation, left to future work.
28

---

Kernel Quantile Embeddings and Associated Probability Metrics
Type control CIFAR vs CIFAR10.1 experiment
0.5
e-KQD
MMD
e- KKDDCentered
sup-KQD KQD
0.4
MMD-Multi
Type error rate
Rejection rate
MMD-Lin
0.3
0.2
0.1
0.0
100
500
1000
1500
2000
Number Samples
Figure 5: Type I control results for experiment CIFAR-10 v.s.
CIFAR-10.1. We all methods control their Type
I error around or below the specified Type error rate 0.05, thus confirming our tests in the main text are valid testing procedures.
MMD Lin (O(n))
* MMD Multi (Ointag' nll
sup KQD; (Ointog' n))
e e-KQD (Ginlag' m)
*
MMD (Oin'))
e-KgDD Contered (Otn²))
(a) Power Decay
Laplace v.s. Gaussian
Galaxy MNIST
(d) CIFAR-10 v.s. CIFAR-10.1
1.0
10--
0.8
Rejection rate
Rejection rate
Rejection rate
Rejection rate
0.6
0.6-
0.4
8--
0.4
02-
6.0
32
64
126
256
512
100
530
2003
5000
30000
100
500
1000
1.000
2000
2500
300
500
10000
1500
2000
Dimension
Number of samples
Number of samples
Number of samples
Figure 6: The experiments in Figure 3 repeated for 1. Experimental results comparing our proposed methods with baseline approaches. A higher rejection rate indicates better performance in distinguishing between distributions. Same as for p = 2, quadratic-time quantile-based estimators perform comparably to quadratic-time MMD estimators, while near-linear time quantile-based estimators often outperform their MMD-based counterparts.
D.3. Comparison of weighting measures
The Gaussian Kernel Quantile Discrepancy introduced Section has multiple weighting measures that determine properties of the distance: the measure y the quantile levels, the measure & within the covariance operator, and the measure 7 on the unit sphere Sz. We investigate the impact of varying these.
Varying v. We conducted the following experiment using the Galaxy MNIST and CIFAR datasets. We varied v. from assigning more weight to the extreme quantiles to down- wwwnhweightinggg them. The results are presented in Figure 7, where the reverse triangle / stands for up-weighing extreme quantiles, and the triangle /\ stands for down-weighing them. We observed some improvement over the uniform v: for Galaxy MNIST, test power improved when assigned less weight to extremes, whereas for CIFAR, the opposite was true, with higher test power when more weight was given to extremes. Uniform weighting of the quantiles remained a good choice. This suggests that tuning 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 similar, benefit from emphasising extremes, while Galaxy MNIST, which contains 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.
Varying The reference measure & in the covariance operator C serves to "cover the input space" and is typically set to a "default" measure on the space- for Rd the standard Gaussian measure. The choice (P,, + Qw)/2 made in the main body of the paper is aiming to adhere to the most general setting, when no default measure may available -nnly P, and Q...
29

---

Kernel Quantile Embeddings and Associated Probability Metries
e-KQ;; (Dinlagān))
c: e-KQD>-A (OInlag"n)
c-KQD>, H (1QR111100000000000000011 349) x NOO, 1) (OInlag"n))
MMD (O(n"))
-V (Oiniog' n))
e-KQD; μ KUR 11 (Otniog'
Galaxy
CIFAR-10 V.S. CIFAR-10.1
CIFAR-10 v.s.
CIFAR-10.1
1.0
0.7
Rejection rate
Rejection rate
0.6
0.6
0.6
0.4
0.3
02-
0.2
0.2
100 500
3500
2000
2500
500
3000
1500
2000
100
1000
1500
2000
Number samples
Number samples
Number of samples
Figure 7: Gaussian KQD test power under different weighting measures. Left. middle: Varying measure v: down-weighing (/\) extremes boosts power on Galaxy MNIST, while up-weighing (V) them helps on CIFAR. Uniform weighting remains strong default, with optimal depending the dataset. Right: Varying measure &: using IQR-scaled Gaussian uniform default reference measure & both outperform MMD indicating potential advantage of "default" & over the problem-basee & = (Pn + Qn)/2.
We report a comparison on performance when the reference measure is: (P, 22: (2) a standard Gaussian measure, scaled by IQR/1.349 to match the spread of the data, where IQR is the interquantile range of P,. + Qu, and 1.349 the interquantile range of the standard Gaussian; and (3) uniform measure on [-1, 1J scaled by IQR.
The results, presented Figure 7, show performance superior to MMD for the standard/uniform Ç. This indicates value in picking a "default" measure when one available.
Varying 7 Varying the measure on the sphere beyond a Gaussian is extremely challenging in diiinte-dimmnssioall spaces due to the complexity of both its theoretical definition and practical sampling, Since no practically relevant alternative has been proposed, we leave this direction unexplored.
D.4. Comparison to sliced Wasserstein distances
We extend the power decay experiment to include sliced Wasserstein and max-sliced Wasserstein distances, with directions (1) sampled uniformly on the sphere, and (2) sampled from (P, + Qx)/2 and projected onto the sphere. The results are plotted Figure 8, and show that sliced Wasserstein distances perform significantly worse than e-KQD. This outcome is expected-as noted Connections and sliced Wasserstein is equivalent to e-KQD with the linear kernel, which is less expressive than the Gaussian kernel.
D.5. Comparison with MMD based on Other KME Approximations
There are several efficient kernel mean embedding methods available in the literature, and no single approach has emerged as definitively superior. To complement experiments in the main body of the paper, we compare the e-KQD (at matching cost) with (1) The Mean Embedding (ME) approximation of MMD of Chwialkowski al. (2015b), which was identified as the best- berforrnn method in their numerical study; (2) the Nyström-MM method of Chatalic al. (2022), and (3) the Oodiannof--Mant (MOM) approximation of Lerasle et al. (2019), specifically, their faster method (MONK BCD-Fast) that achieves matching cost to our e- C-KQD at the number of blocks Q = n log
The results presented in Figure 8. ME performs the level of MMD-multi, while Nyström has extremely high Type II error, likely due to sensitivity to hyperparameters. Due to (with the number of optimiser iterations set to T = 100), we apply it to cheaper Power Decay problem (rather than the larger and more complicated Galaxy MNIST), where it performs at the level the linear approximation of MMD. This may be due to MOM primarily being robustness-enforeing method, rather than method aiming to build an efficient approximation of MMD.
still being considerably slower than e-KQD
30

---

Kernel Quantile Embeddings and Associated Probability Metrics
e-sW, == A for (P, 0,12
e KQD2
MMD-Mult
Nyström
MMD-Lin (O(n)
e-SW,, Unif
MMD (O(n"))
MOM
Power decay
Galaxy MNIST
Power decay
Rejection rate
0.8
Rejection rate
0.6
Rejection rate
0.8
0.4
0.4
0.2
0.
0.0
Dimension
Number of samples
Dimension
Figure 8: All methods are cost On log" n) unless specified otherwise. Left: Gaussian KQD compared with sliced Wasserstein with uniform or data-driven directions, on the power decay problem. Sliced Wasserstein fall well below OgDDconsistenn with their equivalence to KQD using a less expressive linear kernel. Middle: Comparison with alternative approximate KME methods, matching cost. ME matches MMD-multi power, while Nyström-MMD suffers high Type Il emror Right: Comparison with Median-of-Means (MOM) KME approximation, matching cost. MOM is primarily robustness-enforcingg method, not a cheap-aprroximation method, and doesn't 't perform well at set cost of O log n).
31


Reviews:
[{"review_id": "lxS6BBDncM", "reviewer": "Reviewer_EZmy", "summary": "The paper proposes an alternative to kernel mean embeddings where they embedd the quantile functions instead of the mean, each quantile function being computed in the direction of a unit-norm function in the RKHS. They show that such embedding is injective under milder conditions on the kernel than the known characteristic property for the mean embedding counterpart. The authors propose a new family of discrepencies based on these quantile embeddings, and exhibit conditions under which these are metrics on the space of Radon probability measures. As the computation of these discrepencies involves an expectation over the unit ball of the RKHSs, the authors develop tools based on Gaussian measures to compute it efficiently. Numerical experiments highlight the benefits of the approach.\n\n## update after rebuttal\n\nThe rebuttal confirms the problem in Theorem 5. The authors then failed to answer subsequent questions about the implications of the correct bound and the choice of the hyperparameters.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## I. Proof of Theorem 5, and a discussion of trade-offs:\n\nThank 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. \n\n## II. Choice of Kernels for e-KQD Approximation:\n\nWe 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.\n\n## III. Sample size in experiments:\n\nWe 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.", "claims_and_evidence": "Yes, most of the claims are supported by clear and convincing evidence, except Theorem 5 whose proof cannot be located in the appendix.", "methods_and_evaluation_criteria": "Yes, they make sense.", "theoretical_claims": "The claims seem sound, even though I only skimmed through the proofs.\n\nI just have a problem with Theorem 5. It is the only result not proved in the appendix. I would have expected the bound to scale as $\\mathcal{O}(n^{-1/2} + l^{-1/2})$ and I am surprised by the multiplicativity of the bound: $\\mathcal{O}(n^{-1/2} * l^{-1/2})$ means that we can keep only one direction $u$ in the RKHS and still get consistency as long as $n \\to \\infty$. Or am I wrong here ?", "experimental_designs_or_analyses": "I found no issue with the experimental designs.", "relation_to_broader_scientific_literature": "The idea of using quantile embeddings instead of mean embeddings is of great originality.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "+: The paper is clear and well written. The topic is of interest to the ICML community.\n\n-: The limitations of the KQD are not enough discussed. It remains to be shown that picking $l$ and $m$ logarithmic w.r.t. $n$ is a good choice in terms of approximation error. Yes, you lose the quadratic dependency, but you add a layer of difficulty in that you need to compute the quantities along several directions. There should be a trade-off to find.", "other_comments_or_suggestions": "More of a suggestion: maybe there is something to investigate about how different kernels may allow easier approximation of the e-KQD (i.e. smaller $l$) when the associated RKHS is small (sum of the eigenvalues of the integral operator as a suitable measure ?)", "questions_for_authors": "What was the motivation behind staying in the small data regime $(n \\leq 2000)$ ? Do you know how the estimator behaves beyond that ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DYki51LJrc", "reviewer": "Reviewer_kcy5", "summary": "This paper introduces the concept of Kernel Quantile Embeddings (KQEs) in reproducing kernel Hilbert spaces (RKHS) and investigates how these embeddings can be leveraged to define a new family of probability metrics: Kernel Quantile Discrepancies (KQDs). The authors argue that KQEs are a natural analogue of quantiles in function spaces and can capture distributional information beyond the first moment. The paper proves that these embeddings can be estimated at the same rate O(n-1/2) as classical kernel mean embeddings. It then proposes specific instances of these discrepancies (e-KQD and sup-KQD), connecting them to well-known probability metrics like sliced Wasserstein and Sinkhorn divergences. The authors also provide an estimator with near-linear O(nlog2n) complexity for a version of the e-KQD, and demonstrate empirically—in two-sample hypothesis testing tasks—that KQDs can be competitive with MMD, sometimes surpassing standard MMD or its fast approximations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## I. Further exploring the choices for weighting measure $\\nu$, measure on the sphere $\\xi$, reference measure $\\mu$.\nThank you for this insightful suggestion.\n1. $\\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.\n2. $\\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.\n3. $\\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.\n## II. Conditional Quantile Embeddings and Independence Testing as Future Work:\nThe 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.\n\nIndependence 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.\n\n[1] Gretton et al., 2008. A kernel statistical test of independence. NeurIPS.\n\n[2] Doran et al., 2014. A permutation-based kernel conditional independence test. UAI.\n## III. Clarifying “Cramér–Wold in RKHS” in Early Paragraphs\nWe will add a clarification.\n## IV. Experiment on Centered e-KQD for Mixture Distributions\nWe 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.\n## IV.  “Could there be issues if X is not connected or if k is unbounded?”:\nBoundedness: 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).\n\nConnectivity: KQD remains a valid probability metric for completely regular Hausdorff spaces, including disconnected spaces like totally ordered sets.\n\nWe 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.", "claims_and_evidence": "Claim (1): KQEs offer a strictly weaker requirement on the kernel to preserve injectivity (quantile-characteristic) than classical mean-characteristic kernels.\nEvidence: The authors give proofs (Theorems 1–2) showing that every mean-characteristic kernel is quantile-characteristic, but not vice versa.\nClaim (2): KQDs defined from KQEs form valid probability metrics under weaker conditions.\nEvidence: Theorem 4 establishes that e-KQD and sup-KQD satisfy the properties of a metric, assuming the kernel has “full support” in the specified sense.\nClaim (3): An estimator for e-KQD can be computed in O(nlog2n) time and achieves  O(n-1/2) convergence in the two-sample setting.\nEvidence: The authors outline a Monte Carlo sampling procedure (using Gaussian measures in the RKHS) and show a theoretical sample complexity bound (Theorem 5).\nOverall, these claims are supported by rigorous proofs (for theoretical statements) and empirical experiments (for computational cost and testing power).", "methods_and_evaluation_criteria": "The method centers on constructing quantiles in RKHS by projecting the kernel feature maps onto directions, then computing one-dimensional quantiles.\nEvaluation criteria revolve around:\nThe rate at which KQD-based two-sample tests converge (statistical consistency),\nThe computational complexity of the KQD estimators,\nThe test power in detecting distributional differences for multiple synthetic and real benchmarks.\nThese criteria align well with the standard practice in two-sample testing and kernel-based distribution comparison.", "theoretical_claims": "The “quantile-characteristic” property (Theorems 1 and 2) generalizes the common “mean-characteristic” property in kernel embeddings.\nThe curvature arguments and integral transform approach in the proofs are consistent with known results on characteristic functionals in topological vector spaces.\nThe authors’ expansions connecting KQDs to Sliced/Max-Sliced Wasserstein and Sinkhorn-like divergences (Connections 1–3) appear algebraically consistent.\nI did not find obvious flaws in the proofs from a correctness standpoint; the steps follow standard theorems about characteristic functionals in Hilbert spaces.", "experimental_designs_or_analyses": "The authors run two-sample tests on both synthetic (Gaussian vs. Gaussian with different variances, Laplace vs. Gaussian, etc.) and high-dimensional image data (Galaxy MNIST and CIFAR10 vs CIFAR10.1).\nThey use standard metrics: rejection rate under different sample sizes, and also check Type I error.\nThe analyses compare KQD-based tests against multiple MMD-based tests (including linear, multi, and full).\nOverall, the experimental design is sensible for measuring the performance of a novel test statistic in a fairly standard manner.", "relation_to_broader_scientific_literature": "The paper extends the kernel embedding framework (Smola et al., 2007; Gretton et al., 2012; Muandet et al., 2016).\nIt connects directly to quantile-based distance measures in classical statistics (Kosorok, 1999; Ranger et al., 2020) and to sliced Wasserstein approaches (Bonneel et al., 2015).\nBy bridging the concept of “quantiles” in infinite-dimensional Hilbert spaces, the paper also resonates with prior works that exploit directional statistics (Cramér–Wold theorem).\nThe references seem adequate and highlight the synergy between kernel methods, quantile-based methods, and integral probability metrics.", "essential_references_not_discussed": "The coverage is mostly thorough.", "other_strengths_and_weaknesses": "Strengths:\n\nSubstantial theoretical contribution that expands kernel embeddings beyond means.\nEmpirical demonstration that the proposed distances are competitive with MMD.\nThe proposed near-linear Monte Carlo estimator is especially appealing for large-scale data.\n\nWeaknesses:\nThe weighting measure ν and reference measure ξ are not deeply explored in terms of best practical choices. The authors choose them fairly generically (often uniform or half from Pn, half from Qn). Additional experiments on different weighting might help.\nThe paper mentions potential broader applications (like conditional independence) but does not provide concrete evidence or experiments in such directions.", "other_comments_or_suggestions": "Minor writing comment: Some early paragraphs heavily reference “Cramér–Wold in RKHS,” so it might help to add a more elementary explanation or an example in the main text.\nAlso, if feasible, an experiment on centered e-KQD for a mixture distribution scenario might illustrate the effect of the MMD “shift.”", "questions_for_authors": "Weighting measure: Have you tried or do you have insights on using different weighting distributions ν besides the uniform one, e.g., a heavier weighting around certain quantile regions? Could that accelerate the test in practice or help with tail detection?\nConditional embeddings: You mention the possibility of extending to “conditional quantile embeddings.” Do you see a straightforward approach, or are there structural challenges that differ from conditional mean embeddings?\nPotential domain constraints: Could there be issues if X is not connected or if the kernel is unbounded? You mention bounded k, but might large or unbounded kernels degrade the performance or the theory?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JBB2i98cpc", "reviewer": "Reviewer_dCj7", "summary": "This paper presents an alternative of kernel mean embeddings of distributions through the use of quantiles rather than the mean. More precisely, the embedding of a distribution on a set X is given by the collection of all alpha-quantiles of the pushforwards of the distribution all directions, each given by a unit vector in a RKHS (defined by a kernel k on X). The authors show a number of properties of the resulting embedding that mirror those of kernel mean embeddings, such as the conditions (much weaker as in KME) under which a kernel is characteristic (i.e. the embedding is injective), and complexity and approximation error of empirical estimators. They proceed to define a distance between probability distributions using the embeddings, in a similar fashion to MMD for KME. The resulting distances (the proof that it is indeed a distance is given) are integrals (or a maximum) over alpha and the unit-norm directions of the RKHS, which is reminiscent of the way Sliced Wasserstein distances are defined. The authors indeed show a connection to this class of distances in a particular case, as well as to Sinkhorn divergences. Finally they put forward a particular instance of the distance where the unit norm directions are sampled from a Gaussian measure on the RKHS. The authors finally present a set of experiments using the proposed KQD for  two sample hypothesis testing, where its performance and complexity in various cases is tested against MMD estimators. Sensitivity to the input space dimension, capacity to distinguish between close (in moments) distributions with a polynomial kernel are tested, and experiments on image datasets are shown.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## I. Additional Applications:\n\nKQD 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.\nIn 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.\n## II. Why isn’t $\\gamma$ uniform?\nAs 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.\n\n[1] Stuart, A. M. (2010). Inverse problems: a Bayesian perspective. Acta numerica.\n\n[2] Kolouri, S. et al (2019). Generalized Sliced Wasserstein distances. Advances in neural information processing systems, 32.\n## III. Comparison with SW Distances\nWe 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).\n## IV. “when is using non mean characteristic kernels useful”\nKQDs 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.\n\n[3] Sriperumbudur, B. K., et al (2011). Universality, Characteristic Kernels and RKHS Embedding of Measures. JMLR.\n\n[4] Kriege, N. M., et al. (2020). A survey on graph kernels. Applied Network Science, 5.\n\n[5] Wilson, A. G., et al. (2016). Deep kernel learning. AISTATS.\n## V. Figure 2 Clarification:\nWe 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.\n## VI. Reference Missing in Appendix C.5:\nThank you for pointing this out. We will add reference [6].\n[6] Kukush, A. (2020). Gaussian measures in Hilbert space. Wiley.\n\n## VII. MMD Performance in Image Dataset Experiments:\nWe 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.\n\n## VIII. Connection to Median and Variance-Based Extensions of KMEs:\n\nWe are happy to elaborate. Longer response with review of the methods: https://pdfhost.io/v/t2rYgcDSLS_kernel_quantile_embeddings_2_25\n\nKernel 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.\n\nThe 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.\n\nWe believe these revisions address the reviewer’s concerns and improve the clarity of the paper. Thank you for your constructive feedback.", "claims_and_evidence": "The theoretical claims of the paper are sound, and the proposed measures of discrepancies are interesting in how the generalize KME derived distances such as MMD and kernelize (and generalize) Sliced-Wasserstein distances. The milder condition for a kernel to be characteristic is interesting as well. \n\nAs for the experimental claims, the sensitivity to input dimension and the capability to distinguish between Laplace and Gaussian distributions with the same first and second order moments under a cubic kernel are well supported by the experiments. The results of the image datasets are slightly less convincing, since it looks like MMD is the superior metric to use in this cases (the centered version of the proposed metrics is used and compares similarly to MMD, but the authors show that this version actually interpolates between MMD and Sliced Wasserstein distances – except the choice of kernel is more general). This observation is mitigated by the fact that among the linear or quasi-linear estimators, the KQE ones perform better.\n\n## Update after rebuttal\n\nAs mentioned in my comment below, I maintain my positive evaluation of the paper and my recommendation of acceptance.", "methods_and_evaluation_criteria": "The method to benchmark the proposed metrics is sound : two sample hypothesis tests are one of the key applications of MMD and KME. The authors actually check that the statistical tests actually are meaningful by checking that the tests’ significance level is respected. However, it would have been interesting to showcase different applications that are usually considered with MMD (generative modeling, for instance).", "theoretical_claims": "I skimmed through a few of the proofs (all in appendices), namely those of theorem 2 and connections 1 and 2, which seemed correct to me.", "experimental_designs_or_analyses": "It is not very clear why the Gaussian Kernel Quantile discrepancy is put forward instead of a simple version where \\gamma is uniform over the sphere (as in SW distances) ? Is it for computational reasons and the fact that in fine only a standard univariate normal is sampled in fine ? \n\nAlso, it would have been interesting to consider more variants of the distances : for instance, the authors show that they are able to kernelize SW distances, which are widely used as an efficient distance between probability distributions ; I am curious to see how this would have compared (possibly generalizing through the kernel) to the Gaussian version put forward here.  The theoretical connection is really nice though.\n\nAlso, even though under quantile embeddings the conditions for a kernel to be characteristic are very mild (X is sensible as a topological space and the kernel is separating), in practice this doesn’t seem very important since in all the experiments but the second a Gaussian Kernel is used (which is characteristic for both kernel mean and quantile embeddings).", "relation_to_broader_scientific_literature": "I believe the paper is generally well positioned in the literature related to MMD and distances between probability measures, and the proposed distances essentially generalize several of those in meaningful ways. However, I feel like the connection to attempts at generalizing kernel mean embeddings using medians or variance, though mentioned, could have been detailed a bit further. How different are the constructions in those cases (I am not familiar with that literature) ? Would it have made sense to compare the resulting estimators in the experimental part ?", "essential_references_not_discussed": "I can’t think of a key reference that would be missing.", "other_strengths_and_weaknesses": "I have underlined a number of strengths and weaknesses of the work in my comments above.", "other_comments_or_suggestions": "It seems that Fig 3 is never referenced in the text. Besides a description seems necessary as I am not sure I understood it well. For instance, u1 looks like the identity map in the left panel, but the original and projected measures seem different (the projections are smoother). What am I missing ?\n\nThere is a missing reference in app C.5.", "questions_for_authors": "1) What are situations where using a polynomial kernel (typical of non mean-characteristic kernels) is advantageous wrt a kernel such as the Gaussian or exponential ones ? Or more generally situations where using non mean characteristic kernels is actually useful ?\n\n2) How do the more complex (Gaussian measure and kernel) variants of the proposed metrics compare to the more classical SW distance (uniform measure and linear kernel) ? What is the added value in practice of the generalization ? \nIs there an explanation as to why MMD seems superior in the image dataset experiments ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ADdVkVWahM", "reviewer": "Reviewer_u7Px", "summary": "This paper introduces kernel quantile embeddings (KQEs) as a novel way to represent probability distributions in reproducing kernel Hilbert spaces (RKHS), extending beyond traditional kernel mean embeddings (KMEs). The authors leverage KQEs to define a new family of probability metrics that require weaker kernel conditions than MMD, connect to the sliced Wasserstein distance, and enable efficient near-linear estimation, demonstrating their effectiveness in hypothesis testing.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n## I. “it remains unclear what specific problem KQEs address that cannot be handled by existing quantile estimation methods or previous kernel mean embeddings”.\nThis 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.\n1. 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.\n2. 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.\n## II. Procedure for Hypothesis Testing and Threshold Selection:\nWe 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.\n\n[1] Erich Leo Lehmann, Joseph P Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 1986.\n## III. Setting the Density Function $f_\\nu$ in Algorithm 3.1:\nThe 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.\n## IV. Numerical Comparison with MMD based on Other KME Approximations:\nAs 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.\n\nIn particular, as requested, we compared the KQD with the following (at matching cost)\n1. the Mean Embedding (ME) approximation of MMD from [5] (which was identified as the best-performing method in their numerical study) and \n2. the Nystrom-MMD method from [3]. \n\nThe 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.\n\nAlthough 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.\n\n[2] Schrab, A. (2025). Optimal Kernel Hypothesis Testing (PhD thesis, UCL).\n\n[3] Chatalic A, Schreuder N, Rosasco L, et al. Nyström kernel mean embeddings. ICML.\n\n[4] Lerasle M, Szabó Z, Mathieu T, et al. Monk outlier-robust mean embedding estimation by median-of-means. ICML.\n\n[5] Chwialkowski K P, Ramdas A, Sejdinovic D, et al. Fast two-sample testing with analytic representations of probability measures. NeurIPS.\n\nWe 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.", "claims_and_evidence": "My main concerns are as follows:\n1. There is no intuitive explanation behind the KQE. While the authors claim their approach is motivated by concepts from the statistics and econometrics literature, it remains unclear what specific problem KQEs address that cannot be handled by existing quantile estimation methods or previous kernel mean embeddings.\n2. The procedure for conducting the hypothesis test and determining the threshold is not described.\n3. In Algorithm 3.1, the density function $f_v$ is assumed to be given. How should this function be set in practice? Does it require additional data for simulation?", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "This paper establishes several desirable properties of KQEs and highlights the connection between KQDs and Wasserstein distances.", "experimental_designs_or_analyses": "There is a lack of comparison with other embedding methods proposed in Chatalic et al. (2022), Lerasle et al. (2019), and Chwialkowski et al. (2015).\n\nReferences:\n\nChatalic A, Schreuder N, Rosasco L, et al. Nyström kernel mean embeddings[C]//International Conference on Machine Learning. PMLR, 2022: 3006-3024.\n\nLerasle M, Szabó Z, Mathieu T, et al. Monk outlier-robust mean embedding estimation by median-of-means[C]//International conference on machine learning. PMLR, 2019: 3782-3793.\n\nChwialkowski K P, Ramdas A, Sejdinovic D, et al. Fast two-sample testing with analytic representations of probability measures[J]. Advances in Neural Information Processing Systems, 2015, 28.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a generalization of mean embeddings called kernel quantile embeddings and introduces a distance in the space of probability distributions called the kernel quantile distance. Some interesting results are presented about its connection to the sliced Wasserstein distance, max-sliced Wasserstein distance, and Sinkhorn distance, along with the metric property and sample complexity. I concur with the reviewers that the results are interesting and novel; however, some aspects require more discussion. Given its novelty, the paper will generate some discussion and promote further investigation. Therefore, following the reviewer comments, I recommend accepting the paper.

I strongly urge the authors to incorporate all the discussion provided in the rebuttal in the final version of the paper. Among many, particular things to fix would be: $l^{-1/2}+n^{-1/2}$ and therefore $l$ has to be chosen as of order n; discussion about the choice of $m$ both on computational and statistical behavior; additional experiments as requested by the reviewers and as promised by the authors.
Decision: Accept (poster)