{"id":"463f986f-aa78-4cd7-9182-7d1822ed1719","arxiv_id":"2505.20433","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Kernel quantile embeddings produce a new family of distribution distances that are probability metrics under separating kernels and can be estimated in O(n log^2 n) time.","lead":"The paper introduces kernel quantile embeddings, a way to represent a probability distribution by the quantiles of its kernel-feature projections, and builds distances from them. These distances can separate distributions under weaker kernel conditions than the standard MMD and can be estimated in near-linear time, with tests competitive with MMD.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The near-linear e-KQD estimator uses a finite-rank Gaussian direction measure γ_m that is not covered by the metric or consistency theorems, leaving the implemented estimator without the advertised guarantees.","rationale":"The paper's strongest claim is that kernel quantile embeddings are injective under mild assumptions and that the induced kernel quantile discrepancies are probability metrics, while the practical contribution is a near-linear estimator. The metric and injectivity results appear well-supported: Theorem 1 uses characteristic functionals plus the Cramér-Wold argument, and Theorem 4's identity-of-indiscernibles proof for the expectation case is careful about full support of γ. The weakest point is exactly where the reader placed it: the algorithm replaces the full-support Gaussian γ by a finite-rank, data-dependent γ_m, and no theorem controls this replacement. This is load-bearing because the experiments, complexity claims, and even the claim that e-KQD is a metric for the implemented statistic all rely on the estimator being an approximation of the theoretical e-KQD. Unlike a mere missing constant or an overly optimistic rate, this is a structural gap: the support of γ_m is a finite-dimensional subspace, so the metric property can fail completely for certain distribution pairs. The p > 1 conjecture is also a real gap since the headline experiments use p = 2, but it is secondary because p = 1 is already covered and the empirical conclusions are similar. The rejection-rate plots without error bars are a reporting weakness, not a correctness issue. Overall, the reader's CONDITIONAL verdict is appropriate: the core construction is promising and probably correct, but the theoretical guarantees must be extended to the estimator actually used before the finite-sample claims can be accepted.","tokens_in":37536,"tokens_out":6576,"duration_ms":70486,"concrete_test":"Construct P and Q whose difference is concentrated in an RKHS direction orthogonal to span{k(z_{1:m}, ·)} for the m = log n reference points used by Algorithm 1, e.g. by shifting P along a high-frequency kernel feature that the finite reference set does not represent. Compute Algorithm 1's e-KQD with m = log n and compare it against a high-accuracy estimate using a much larger reference set (m >> n) or an analytic full-γ value. If the Algorithm 1 statistic is near zero while the full-γ value is bounded away from zero, the finite-rank γ_m gap is confirmed. Analytically, attempt to prove a bound sup_{P,Q} |e-KQD_p(γ_m) - e-KQD_p(γ)| ≤ φ(m, n) with φ(m, n) → 0; if no such bound follows from Proposition 1, Theorem 5 must be extended to cover the actual sampling distribution of Algorithm 1 before the stated guarantees are claimed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical results are Theorem 1 (quantile-characteristic kernels) and Theorem 4 (KQDs as probability metrics), which appear internally sound. The load-bearing gap is in the step from those results to Algorithm 1. Theorem 4 makes e-KQD a metric only when γ has full support on the RKHS unit sphere S_H, and Theorem 5 bounds the error between the empirical estimator and the population quantity for a fixed full-support γ, with Monte Carlo directions γ_l from that same γ. Algorithm 1 instead draws directions from γ_m, the projection onto S_H of the degenerate Gaussian N(0, C_m) from Proposition 1, where C_m is built from m = log n reference points z_{1:m}. Because span{k(z_j, ·)} is m-dimensional, γ_m is supported on a proper subspace of S_H: it does not satisfy Theorem 4's full-support condition, so the implemented e-KQD is not guaranteed to be a probability metric and may be blind to distributional differences lying in orthogonal RKHS directions. In the experiments z_{1:m} is drawn from ξ = (P_n + Q_n)/2, making γ_m data-dependent, and no result in the paper bounds sup_{P,Q} |e-KQD_p(γ_m) - e-KQD_p(γ)|. The stated O(n^{-1/2} + l^{-1/2}) consistency rate therefore applies to a different estimator than the one implemented and benchmarked. The p > 1 conjecture is a secondary gap; the γ_m issue affects even the p = 1 case.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces kernel quantile embeddings (KQEs), defined as RKHS-valued directional quantiles of a distribution under all unit-norm RKHS directions, and uses them to construct two families of discrepancies, e-KQD and sup-KQD. The main theoretical contributions are Theorem 1 (quantile-characteristic kernels under mild topological assumptions), Theorem 2 (mean-characteristic implies quantile-characteristic, with a converse failure), Theorem 4 (the KQDs are probability metrics under full-support conditions on the quantile-level measure ν and, for e-KQD, the direction measure γ), and Theorem 5 (an O(n^{-1/2} + l^{-1/2}) consistency bound for the p=1 empirical e-KQD with a fixed direction measure γ and Monte Carlo directions γ_l). The paper also connects KQDs to sliced Wasserstein distances, proposes a near-linear-time estimator based on sampling from a Gaussian measure on the RKHS (Algorithm 1), and reports two-sample testing experiments with p=2. The central injectivity and metric results are clean and appear sound, but the practical estimator in Algorithm 1 uses a finite-rank Gaussian direction measure γ_m that is not covered by Theorems 4 and 5, and the proof of Theorem 5 contains a flawed inequality that requires an additional bounded-range assumption.","tokens_in":37860,"tokens_out":7151,"duration_ms":74466,"significance":"If fully established, this work would be a valuable contribution to kernel-based distribution testing: it shows that quantile-based embeddings separate distributions under conditions strictly weaker than those required for MMD, and it provides a conceptual bridge between kernel embeddings and sliced Wasserstein distances. The proofs of Theorems 1, 2, and 4 are elegant and reduce to standard external results (Vakhania's characteristic-functionals theorem, Cramér-Wold, Dvoretzky-Kiefer-Wolfowitz, Bobkov-Ledoux), with no fitted constants or circular reasoning. The paper includes a detailed appendix and a code repository, which are strengths. However, the advertised statistical and metric guarantees do not currently apply to the estimator actually implemented and benchmarked: the finite-rank γ_m used in Algorithm 1 is degenerate and data-dependent, and the p=2 rate used throughout the experiments is left as a conjecture. These gaps are substantial, but they are localized to the estimation theory and presentation, and are plausibly fixable within the manuscript's scope.","major_comments":[{"comment":"The estimator implemented in Algorithm 1 replaces the full-support direction measure γ by γ_m, the projection onto S_H of the finite-rank Gaussian N(0,C_m) built from m=log n reference points z_{1:m}. Theorem 4 guarantees that e-KQD_p is a probability metric only when γ has full support on S_H, and Theorem 5 bounds the difference between the population quantity at a fixed γ and its Monte Carlo average over l directions sampled from that same γ. No result in the paper bounds the gap between e-KQD_p(·;γ_m) and e-KQD_p(·;γ), and γ_m is supported on an m-dimensional subspace of H, so it cannot satisfy the full-support condition of Theorem 4. Consequently, the implemented e-KQD is not proven to be a probability metric, and the consistency rate of Theorem 5 does not apply to it. The authors should either prove a bound on the finite-rank approximation error or explicitly reframe Algorithm 1 as estimating a different, finite-rank object and adjust the theoretical claims accordingly.","section":"Section 4, Algorithm 1, Proposition 1 and Theorem 4"},{"comment":"The proof of Lemma 5 contains the inequality ∫_{u(X)} |F_{u#P_n}(t) - F_{u#P}(t)| dt ≤ sup_{t∈u(X)} |F_{u#P_n}(t) - F_{u#P}(t)|, which is only valid if the Lebesgue measure of u(X) is at most one. In general u(X) ⊂ R is unbounded (for example, when k is an unbounded kernel on R^d), and the integral can be infinite even when the supremum is small. This invalidates the current proof of Lemma 5 and therefore the n^{-1/2} term in Theorem 5. The proof needs an additional assumption such as boundedness of u(X), or a truncation and dominated-convergence argument, before the stated consistency result can be accepted.","section":"Appendix C.5, proof of Lemma 5"},{"comment":"All main experiments in Section 5.1 use power p=2 for KQD-based discrepancies, yet Theorem 5 establishes the O(n^{-1/2}) rate only for p=1. The p>1 rate is explicitly left as Conjecture 1, with a proof sketch that relies on unverified control of the integral in Equation (19). Thus the statistical rate claimed in the abstract and introduction for the empirical estimators is not proven for the value of p used in the benchmark experiments. The authors should either prove Conjecture 1 under the stated regularity conditions, or restrict the rate claims to p=1 and present the p=1 experiments as the primary evidence for the statistical guarantees.","section":"Section 5.1 and Conjecture 1"}],"minor_comments":[{"comment":"The notation in Algorithm 1 is confusing: λ_{1:m} ∼ N(0, Id_m) is a vector, but the expressions λ_{1:m}^T k(z_{1:m}, x_{1:n})/√m and λ_{1:m}^T k(z_{1:m}, z_{1:m}) λ_{1:m}/m mix row/column conventions; clarifying whether k(z_{1:m}, x_{1:n}) is an m×n matrix and λ is an m×1 vector would improve reproducibility.","section":"Section 4, Algorithm 1"},{"comment":"Theorem 5 uses γ_l for the Monte Carlo approximation of a fixed γ, while Proposition 1 and Algorithm 1 introduce a different finite-rank measure γ_m based on m reference points. The two are conflated in the main text, which makes it easy for a reader to mistakenly believe that Theorem 5 covers Algorithm 1; the notation should be separated or unified with explicit caveats.","section":"Theorem 5 and Section 4"},{"comment":"The reference list contains several duplicated entries with different years or suffixes (e.g., Chwialkowski et al. 2015a/b, Nienkötter and Jiang 2022/2023, Makigusa 2024a/b, Wang et al. 2024a/b), which should be consolidated.","section":"References"},{"comment":"The main text states that 'identical experiments for p=1 lead to the same conclusions', but Appendix D.2 reports that centered e-KQD1 performs noticeably worse than centered e-KQD2 in the Laplace-vs-Gaussian experiment; the wording should be softened to reflect this difference.","section":"Appendix D.2"},{"comment":"Setting l = log n and m = log n leads to non-integer values for small n (e.g., n=32 gives log n ≈ 3.47); the text should specify that these are rounded to integers in the experiment.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The core idea and the metric/injectivity theorems are strong and likely publishable, but the manuscript currently promises more than it proves for the estimator actually used in experiments. The finite-rank γ_m gap is the main obstacle: it affects both the metric guarantee and the consistency claim, and it is not merely a presentation issue. I would ask the authors to either provide an approximation-error bound for γ_m or restructure the claims so that Algorithm 1 is presented as a heuristic estimator whose theoretical status remains open. The p=2 rate being a conjecture is a secondary but important gap given the experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nHere is my read on Naslidnyk et al. The one thing to know: the paper has a genuinely new construction and a genuinely good metric theorem, but the estimator it actually benchmarks is not the estimator its main consistency result covers. That gap should be fixed before anyone uses the algorithm as advertised.\n\nWhat is actually new. The paper defines kernel quantile embeddings and shows (Theorem 1) that they injectively represent distributions under a separating, continuous kernel on a Polish-like space, and (Theorem 2) that quantile-characteristic is strictly weaker than mean-characteristic. Theorem 4 then shows the induced e-KQD and sup-KQD are probability metrics under the same mild assumptions. That is a real advance over the universal-kernel conditions in the kernel sliced Wasserstein literature. The expected KQD with a Gaussian direction measure also seems new, and the connection to sliced Wasserstein is clearly stated. The near-linear estimator is clever, and the empirical comparison against MMD variants is substantial. The theory leans on standard external results (Vakhania, Serfling, DKWM, Bobkov-Ledoux) rather than circular self-citations.\n\nWhere the soft spots are. Theorem 5 gives the O(n^-1/2 + l^-1/2) rate only for p=1, but the experiments use p=2 and the p>1 rate is explicitly left as a conjecture. The bigger issue is the direction measure. The metric and consistency theorems assume a fixed gamma with full support on the RKHS unit sphere. Algorithm 1 samples directions from gamma_m, the projection of a Gaussian with covariance built from m=log n reference points. Since those points span an m-dimensional subspace, gamma_m has support on a proper subspace and is also data-dependent in the experiments (z's are drawn from the pooled empirical measure). No bound controls the gap between e-KQD(gamma_m) and e-KQD(gamma), so the advertised guarantees do not cover what the code runs. There is also a minor technical slip in Lemma 5: bounding the integral of |F_n-F| by the sup norm requires a bounded range for u(X), which is not assumed. The empirical plots would benefit from error bars, especially on rejection rates.\n\nNone of this kills the paper. The metric characterization is the core contribution and it appears sound. The implementation gap is bridgeable with a careful analysis of the finite-rank approximation, or by presenting Algorithm 1 as a heuristic with separate validation.\n\nWho should read it. Anyone working on kernel two-sample testing or distribution distances. It deserves serious peer review: the construction is novel, the main theorem is clean, and the flaws are fixable rather than fatal.\n\nI recommend engaging with it and sending it out, with the expectation of a major revision that either proves the gamma_m error bound or explicitly reframes the algorithm's guarantees.\n\nBest","headline":"Genuinely new quantile-based distribution metrics with a sound metric theorem, but the implemented estimator is not the one the consistency proof covers.","tokens_in":38437,"tokens_out":3195,"would_cite":true,"duration_ms":32627,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G05","62G10","60B10","46E22"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that kernel quantile embeddings are injective for any continuous separating kernel on a sigma-compact Hausdorff space, making the associated kernel quantile discrepancies probability metrics under weaker conditions than…","keywords":["kernel quantile embedding","kernel quantile discrepancy","maximum mean discrepancy","sliced Wasserstein distance","two-sample testing","kernel mean embedding","quantile-characteristic kernel","Gaussian measure sampling"],"falsifier":"Exhibit two distinct Borel probability measures $P$ and $Q$ on a $\\sigma$-compact Hausdorff space with a continuous separating kernel such that $\\rho^{\\alpha}_{u\\#P} = \\rho^{\\alpha}_{u\\#Q}$ for every $\\alpha \\in [0,1]$ and every unit-norm RKHS direction $u$; Theorem 1 asserts no such pair exists, so one such pair would settle the question directly.","tokens_in":37331,"feed_emoji":"📊","tokens_out":13013,"duration_ms":109525,"temperature":0.7,"pith_summary":"The paper introduces kernel quantile embeddings (KQEs), which represent a probability distribution by the quantiles of its one-dimensional projections onto unit-norm directions in a reproducing kernel Hilbert space. Its central claim is that this representation is injective for any continuous separating kernel on a $\\sigma$-compact Hausdorff space, so every such kernel is quantile-characteristic even when it is not mean-characteristic in the sense required by MMD. From these embeddings the paper builds kernel quantile discrepancies (KQDs), and proves they are probability metrics under those same mild assumptions. If correct, KQDs give practitioners a distance that separates every pair of distributions MMD separates, plus some pairs MMD cannot, with a near-linear-time estimator and an $O(n^{-1/2})$ sample rate.","feed_headline":"Kernel quantile embeddings separate distributions MMD cannot","feed_subtitle":"A quantile-based distance separates every pair MMD does, plus some it misses, at near-linear cost.","key_machinery":"The load-bearing object is the kernel quantile embedding (KQE): for a unit-norm RKHS direction $u$, the embedding of $P$ is $\\rho^{\\alpha,u}_P(x) = \\rho^{\\alpha}_{u\\#P} u(x)$, with $\\rho^{\\alpha}_{u\\#P}$ the ordinary univariate $\\alpha$-quantile of the scalar random variable $u(X)$ for $X \\sim P$. Comparing these directional quantiles across all $\\alpha$ and all $u$ yields the kernel quantile discrepancies, and the proof of injectivity rests on characteristic functionals $\\varphi_P(f) = \\int e^{i f(x)} P(dx)$, which determine a measure and let the authors extend the Cramér-Wold theorem from $\\mathbb{R}^d$ to the RKHS under mild topological assumptions.","core_discovery":"On the paper's own terms, the discovery is that the mean is not the only meaningful RKHS representation of a distribution: the full collection of directional quantile embeddings $\\{\\rho^{\\alpha,u}_P : \\alpha \\in [0,1], u \\in \\mathbb{S}_{\\mathcal{H}}\\}$, where $\\rho^{\\alpha,u}_P = \\rho^{\\alpha}_{u\\#P} u$, is a one-to-one encoding of probability measures under assumptions much weaker than those required for mean embeddings to be characteristic. Theorem 1 establishes this as an RKHS extension of the Cramér-Wold theorem; Theorem 2 shows every mean-characteristic kernel is quantile-characteristic but not conversely, so the polynomial-kernel example distinguishes distributions with matching low-order moments. Theorem 4 turns this into distances: the expected and supremum kernel quantile discrepancies are probability metrics when the averaging measure on quantile levels (and on the sphere, for the expected version) has full support. The paper also proves finite-sample consistency at rate $O(n^{-1/2})$ and shows the Gaussian expected version recovers kernelised sliced Wasserstein distances, linking the construction to optimal transport.","pith_inferences":["Extension: if a bound on the gap between the full-support Gaussian measure $\\gamma$ and the finite-rank approximation $\\gamma_m$ used in Algorithm 1 can be established, the near-linear estimator would inherit the metric property and consistency guarantees, which currently hold only for the idealised full-support version.","Extension: because Theorem 1 needs only a continuous separating kernel, KQDs may provide probability metrics on discrete or structured spaces where characteristic kernels for MMD are known to fail, including the graph-kernel case the paper itself notes.","Extension: reweighting the quantile-level measure $\\nu$ toward central quantiles gives a natural robustness dial, and the paper's experiments show the optimal weighting is problem-dependent, suggesting a tunable family rather than a single fixed distance.","Extension: the paper's future-work remark points toward conditional versions of KQEs, so a conditional quantile embedding for conditional distributions is a concrete and testable next step."],"forward_implications":["Any pair of distributions that MMD can separate with a kernel $k$ will also be separated by a KQD built from $k$, because every mean-characteristic kernel is quantile-characteristic.","Some pairs that MMD cannot separate, such as a Gaussian and a Laplace distribution with matching first two moments under a cubic polynomial kernel, are separated by KQDs.","KQDs are probability metrics under continuous separating kernels on sigma-compact Hausdorff spaces, without requiring the kernel to be characteristic in the mean-embedding sense.","With Lebesgue weighting over quantile levels, e-KQD and sup-KQD become kernelised expected and max sliced Wasserstein distances, reducing to classical sliced Wasserstein for a linear kernel with uniform directions.","The Gaussian e-KQD estimator runs in $O(n \\log^2 n)$ with an $O(n^{-1/2} + l^{-1/2})$ sample-error rate, matching the rate of MMD estimators at lower cost."],"supporting_citations":[{"why":"Supplies the classical theorem that all one-dimensional projections determine a measure, which Theorem 1 extends to the RKHS setting.","marker":"Cramér and Wold (1936)"},{"why":"Defines alpha-directional quantiles, the multivariate quantile notion on which KQEs are based.","marker":"Kong and Mizera (2012)"},{"why":"Provides the characteristic-functional machinery that proves equality of all projections implies equality of measures.","marker":"Vakhania et al. (1987)"},{"why":"Defines MMD and its estimators, the benchmark KQDs are compared with and whose separation power is strictly weaker.","marker":"Gretton et al. (2012)"},{"why":"Establishes the characteristic-kernel conditions under which MMD is a metric, used for comparison in Theorem 4.","marker":"Sriperumbudur et al. (2010)"},{"why":"Introduces the sliced Wasserstein distance that e-KQD recovers for a linear kernel.","marker":"Bonneel et al. (2015)"},{"why":"Introduces max-sliced Wasserstein distance, which sup-KQD recovers.","marker":"Deshpande et al. (2018)"},{"why":"Gives the theory of Gaussian measures on Hilbert spaces used to construct and sample the direction measure gamma.","marker":"Kukush (2020)"},{"why":"Provides the order-statistic quantile estimator and its O(n^{-1/2}) convergence used in Theorem 3.","marker":"Serfling (2009)"},{"why":"Introduces kernel projected Wasserstein distances and the optimisation-based estimator that sup-KQD approximates.","marker":"Wang et al. (2022)"}],"fun_headline_variants":["Quantile embeddings beat MMD in kernel feature spaces","Kernel quantile distances: stronger separation at linear cost","Quantile RKHS embeddings: more than just the mean","Kernel quantile distances: separating what MMD misses","Beyond mean embeddings: quantile RKHS distances"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The fast estimator samples directions from a finite-rank Gaussian $\\gamma_m$ built from $m = \\log n$ reference points, while the metric and consistency theorems assume a full-support Gaussian $\\gamma$ on the infinite-dimensional unit sphere; no error bound controls the gap between $\\gamma$ and $\\gamma_m$.","fun_headline_variants_meta":{"raw":{"variants":["Quantile embeddings beat MMD in kernel feature spaces","Kernel quantile distances: stronger separation at linear cost","Quantile RKHS embeddings: more than just the mean","Kernel quantile distances: separating what MMD misses","Beyond mean embeddings: quantile RKHS distances"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000691,"raw_usage":{"total_tokens":3116,"prompt_tokens":921,"completion_tokens":2195,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":2117}},"tokens_in":537,"tokens_out":2195,"duration_ms":15687,"temperature":1.0,"reasoning_tokens":2117,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:55:54.725485+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit two distinct Borel probability measures $P$ and $Q$ on a $\\sigma$-compact Hausdorff space with a continuous separating kernel such that $\\rho^{\\alpha}_{u\\#P} = \\rho^{\\alpha}_{u\\#Q}$ for every $\\alpha \\in [0,1]$ and every unit-norm RKHS direction $u$; Theorem 1 asserts no such pair exists, so one such pair would settle the question directly.","supporting_citations":[],"review_version":1}