{"id":"41cec3f8-69ee-4c50-a214-f0eece3eca7d","arxiv_id":"2607.24235","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Minimax lower bounds for MMD, HSIC and KSD estimation are n^{-1/2} on general topological spaces under mild kernel assumptions, matching existing estimators.","lead":"The paper proves that estimating popular kernel discrepancies (MMD, HSIC, KSD) cannot be done faster than the parametric n^{-1/2} rate on general topological spaces under mild kernel assumptions. This matches known upper bounds and closes the optimality question beyond Euclidean spaces with bounded kernels.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"The lower bounds are sound, but \"settling optimality with unbounded kernels\" is not established: the lower bound is over P1(K;X) (finite E√K(x,x)), while matching n^{-1/2} upper bounds for unbounded kernels only hold under subexponentiality — a strictly smaller class over which the adversarial pairs","rationale":"I agree with the reader that the proofs are internally sound and that Assumption 1(ii)/6(ii)/10(ii) is the logical linchpin of the perturbation construction; but that assumption is genuinely mild (Lemma 2 covers separable metric spaces with bounded continuous kernels, and its failure modes are degenerate topologies where characteristic kernels are unavailable anyway). I therefore only partially agree that it is the weakest point. The concern I identify is different and more consequential for the paper's headline: the class mismatch between the lower bound (over P1(K;X), first moment of ||K(·,x)||) and the available upper bounds (subexponential √K for unbounded kernels). This is not a correctness flaw in any theorem — the lower bounds stand — but the abstract's claim that the results \"settle the question of optimal estimation\" of these discrepancies with unbounded kernels is not supported as written: (a) over P1 with heavy-tailed ||K(·,x)||, parametric-rate estimation fails outright, so the lower bound cannot be matched there; (b) over the subexponential classes where n^{-1/2} upper bounds hold, the paper never verifies its adversarial measures belong to them. This is a scoping/interpretation gap rather than a derivation gap, which is why I recommend CONDITIONAL rather than REJECT: the paper is a clean accept if the optimality claim is scoped to classes where upper bounds hold (with a lemma showing the adversarial pairs (A.8) can be chosen inside them — plausibly true via discrete P0 with weights adapted to the growth of √K), or if the bounded-kernel case is foregrounded. The concrete test above directly settles whether the gap is real: the n^{-1/5} calculation for the specified heavy-tailed P0 is elementary stable-limit theory and its confirmation would force the scoping revision.","tokens_in":33408,"tokens_out":7633,"duration_ms":242954,"concrete_test":"Take X=ℝ, K(x,y)=(1+xy)² (unbounded; √K(x,x)=1+x²), and P0 with density ∝(1+|x|)^{-7/2}. Then E√K(X,X)<∞ (P0∈P1) but E[K(X,X)]=∞. The tail P(||K(·,X)||>s)≍s^{-5/4}, so by the stable CLT (index α=5/4) ||µK(Pn)−µK(P0)|| decays as n^{1/α−1}=n^{-1/5}, strictly slower than n^{-1/2}. Verify numerically (simulate the embedding error decay) or analytically. If confirmed, Corollary 4's n^{-1/2} lower bound is not tight over the stated class for this kernel, refuting \"settled optimality\" over P1. Companion check: try to choose the adversarial P0 in (A.8) within the subexponential class of Kalinke et al. (e.g., discrete P0=Σ2^{-i}δ_{xi} with √K(xi,xi)=O(i)); if such a choice is always possible under the paper's assumptions, optimality over the upper-bound classes is rescued and should be stated as a lemma.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The theorems as stated appear correct: the Le Cam two-point construction (A.8, A.16) is clean, the separation Cφ>0 follows from injectivity plus Lemma B.4/C.2, and the KL bound (Lemma B.6) is tight. The reader's flagged Assumption 1(ii) is genuinely necessary but mild (it only excludes degenerate spaces where all continuous bounded functions are a.s. constant). The more load-bearing soft spot is the claim in the abstract and contribution (i) that the lower bounds \"match the upper ones of available estimators, hence settle their minimax optimality\" for UNBOUNDED kernels. The lower bounds are proved over P1(K;X) = {P : E√K(X,X)<∞}, the natural domain of the mean embedding. But for unbounded K, the cited n^{-1/2} upper bounds (Kalinke et al. 2025b, 2026) require subexponentiality of √K under P — and n^{-1/2} convergence of the empirical mean embedding itself requires E[K(X,X)]<∞ (second moment). P1(K;X) contains measures with E[K(X,X)]=∞, for which the embedding error has infinite variance and decays strictly slower than n^{-1/2} (stable-index scaling). Two consequences: (1) over the stated class P1 with unbounded K, no uniform n^{-1/2} upper bound exists in general, so the proved lower bound cannot be certified tight — the true minimax rate over P1 may be slower (indeed, over all measures with only a finite first moment of ||K(·,x)||, no uniform rate exists at all); (2) conversely, the lower bound does not transfer to the smaller subexponential classes where upper bounds DO hold, unless the adversarial P0 and perturbed P(n) can be shown to lie inside them — the paper's construction takes P0 arbitrary from Assumption 1(ii) and never checks moment conditions beyond membership in P1. For bounded kernels everything coincides (P1 = all measures) and the optimality claim is airtight; the gap is precisely in the unbounded-kernel regime the abstract advertises as the advance. Note this does not touch the correctness of Theorems 3, 7, 11 as lower bounds — it undermines the \"we","agreement_with_reader":"partial"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper establishes minimax lower bounds for estimating three kernel discrepancies — MMD (rate n^{-1/2} + m^{-1/2}), HSIC (n^{-1/2}), and KSD (n^{-1/2}) — on general topological spaces, plus corollaries for the mean embedding and the centered cross-covariance operator. The proofs use Le Cam's two-point method with adversarial measures built by multiplicative perturbations P^{(n)}(A) = ∫_A (1 + ε_n φ) dP_0, where ε_n = c n^{-1/2} and φ is a bounded continuous mean-zero perturbation whose existence is guaranteed by a non-degeneracy assumption (Assumptions 1(ii)/6(ii)/10(ii)). Separation of the functional values follows from injectivity of the mean embedding (characteristic / I-characteristic kernels), and the KL bound KL(P^{(n)} || P_0) ≤ α ε_n^2 is proved in Lemma B.6. The KSD result (Theorem 11) is recalled from the authors' prior AISTATS paper; the MMD, HSIC, and the two corollaries are new. Prior lower bounds were restricted to R^d with translation-invariant or radial kernels, so the generality here is the main contribution.","tokens_in":33801,"tokens_out":3764,"duration_ms":112607,"significance":"If the results hold — and I believe they do, modulo the framing issue in Major Comment 1 — the paper provides the first minimax lower bounds for MMD, HSIC, KSD, mean-embedding, and cross-covariance estimation that apply on general topological spaces with unbounded kernels, substantially relaxing the R^d / translation-invariant / radial assumptions of Tolstikhin et al. (2016, 2017), Chamakh and Szabó (2024), and Kalinke and Szabó (2024). The lower bounds are parameter-free in the relevant sense (the constant c in eps_n = c n^{-1/2} is arbitrary, and B > 0 is exhibited, not fitted) and rely only on characteristicness plus a mild non-degeneracy assumption. The proofs are short, checkable, and the assumptions are close to necessary for a nontrivial lower bound. This is a useful reference result for the kernel-discrepancy literature.","major_comments":[{"comment":"The claim in contribution (i) that the lower bounds 'match the upper ones of available estimators, hence settle their minimax optimality' for unbounded kernels is not fully supported as stated. The lower bounds are proved over P1(K;X) = {P : E_P sqrt(K(X,X)) < infty}. For unbounded K, the cited n^{-1/2} upper bounds (Kalinke et al. 2025b, 2026) require subexponentiality of sqrt(K(X,X)) under P, and even n^{-1/2} convergence of the empirical mean embedding requires the second moment E_P[K(X,X)] < infty. P1(K;X) contains measures with E[K(X,X)] = infty, over which no uniform n^{-1/2} upper bound exists. Two consequences: (a) over the stated class P1(K;X) with unbounded K, tightness at n^{-1/2} cannot be certified — the true minimax rate there may be slower; (b) a lower bound over the larger class P1 does not automatically transfer to the smaller subexponential classes where the upper bound","section":"§1, contribution (i); §3, Theorems 3, 7, 11; class P1(K;X) defined in §2"},{"comment":"Related to the previous point: the abstract and §3 should state explicitly which class the optimality claim refers to. As written, Theorem 3 (and similarly 7, 11) lower-bounds the minimax risk over [P1(K;X)]^2, while the matching upper bounds cited in §1 hold only over moment/tail-restricted subclasses. A reader can currently read the paper as claiming optimality over P1(K;X) itself for unbounded kernels, which the arguments do not establish. Please align the statement of the class in the theorems, the upper-bound citations in §1, and the 'settle the question' sentence in the abstract; bounded-kernel cases (where P1 = M_1^+ and the upper bounds of Smola et al. 2007 apply) are fine as is.","section":"Abstract; §1, paragraph on convergence rates; §3.1–3.3"}],"minor_comments":[{"comment":"In the proof of Corollary 8 the map F is defined as F : P1(K;X) -> R, P -> C_K(P), but C_K(P) is an element of H_K; the codomain should be H_K.","section":"§A.5"},{"comment":"The equation label (A.9) is used both in the proof of Theorem 3 and again in the proof of Corollary 4; the second occurrence should be renumbered.","section":"§A.3"},{"comment":"Lemma 2 (sufficient conditions for Assumption 1(ii)) assumes K in C_b(X^2), so it does not cover the unbounded-kernel regime that is the paper's main selling point. Assumption 1(ii) can in fact be verified much more cheaply whenever C_b(X) contains a non-constant function (e.g., X Tychonoff with at least two points): take phi_0 non-constant in C_b(X) and P0 a two-point mixture of Diracs at x, y with phi_0(x) != phi_0(y); finitely supported measures are always in P1(K;X). A remark to this effect would strengthen the 'mild assumptions' claim for unbounded kernels.","section":"§3.1, Lemma 2"},{"comment":"In §1 the upper bounds for unbounded kernels are attributed to Kalinke et al. (2025b, 2026), which are KSD papers; please clarify which results provide the n^{-1/2} + m^{-1/2} (resp. n^{-1/2}) upper bounds for MMD (resp. HSIC) with unbounded kernels, or restrict that sentence to KSD.","section":"§1, paragraph on estimator convergence rates"},{"comment":"In (A.12), step (g) (C_phi > 0) uses that P^{(n)} != P0 via Lemma C.2; a pointer to Lemma C.2 at that step would parallel the treatment in (A.9) and help the reader.","section":"§A.4"},{"comment":"The dependency chart is helpful, but 'C.5 C.3' in the header row is easy to misread; consider formatting the figure caption or layout so that external results (Appendix C) are visually distinguished from auxiliary ones (Appendix B).","section":"Appendix A, Figure 1"}],"recommendation":"minor_revision","confidential_remarks":"The KSD result (Theorem 11) is recalled from the authors' own AISTATS 2026 paper with appropriate disclosure; the new content is the MMD/HSIC/mean-embedding/cross-covariance extension, which is written out independently and is not duplicative. The technical contribution is solid but incremental in method (standard two-point perturbations); the value lies in the generality of the statement. The only substantive framing issue — the \"settle optimality for unbounded kernels\" claim relative to the class P1(K;X) — is detailed in Major Comment 1 and is fixable without new proof machinery. Fit with the journal seems good."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real news is that they get matching n^{-1/2} (and n^{-1/2}+m^{-1/2}) minimax lower bounds for MMD, HSIC and KSD on general topological spaces under characteristic / I-characteristic kernels plus a mild non-degenerate continuous perturbation. Same rates for the mean embedding and centered cross-covariance. Prior lower bounds stopped at R^d with radial or translation-invariant kernels; this is the natural extension, and the proofs are written out carefully.\n\nWhat they do well: standard two-point Le Cam with multiplicative continuous perturbations of a base measure. The auxiliary lemmas (membership in P1, distinctness, mean-embedding formula, KL bound, product-space perturbations) are clean and self-contained. Characteristic injectivity gives the separation C_φ > 0. The KSD case reuses their concurrent note but MMD/HSIC are independent. Citation pattern is honest about the R^d predecessors. No circularity; rates come straight from ε_n ~ n^{-1/2}.\n\nSoft spot, in proportion: the abstract and contribution (i) claim these lower bounds \"match the upper ones of available estimators, hence settle their minimax optimality\" for unbounded kernels. The lower bounds are over P1(K;X) = {E √K < ∞}. For unbounded K the cited √n upper bounds need subexponentiality (or at least E K < ∞ for the embedding itself). P1 is strictly larger; inside it the empirical embedding need not be √n. The construction never forces the adversarial pair into the subexponential subclass where the upper bounds live. So the theorems as lower bounds are fine; the \"settled optimality for unbounded kernels\" slogan is a notch too strong. For bounded kernels everything coincides and the claim is airtight. Assumption 1(ii) is load-bearing but mild; Lemma 2 gives the usual separable-metric sufficient conditions.\n\nThis is for people who care about kernel testing, Stein methods, and nonparametric rates outside Euclidean space. Solid theory paper, fully written proofs, no data. I would send it to referees; the gap is fixable by tightening the abstract or restricting the class. Worth engaging if you work in this area.","headline":"Clean Le Cam lower bounds that close the topological-space gap for MMD/HSIC/KSD, with one overstated tightness claim for unbounded kernels.","tokens_in":35009,"tokens_out":552,"would_cite":true,"duration_ms":11240,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Estimating MMD, HSIC and KSD cannot beat the parametric n^{-1/2} rate on general spaces under mild kernel assumptions.","keywords":["maximum mean discrepancy","Hilbert-Schmidt independence criterion","kernel Stein discrepancy","minimax lower bound","reproducing kernel Hilbert space","mean embedding","perturbations","Le Cam method"],"falsifier":"Exhibit a topological space, a characteristic kernel, and a sequence of estimators whose risk is o(n^{-1/2}) uniformly over the stated class of measures, or prove that every continuous bounded function is almost surely constant for every measure in that class.","tokens_in":34655,"feed_emoji":"📉","tokens_out":831,"duration_ms":23048,"temperature":0.7,"pith_summary":"Kernel discrepancies such as MMD, HSIC and KSD are standard tools for comparing distributions, testing independence and checking goodness of fit. Existing estimators already achieve the parametric rate n^{-1/2} (or n^{-1/2}+m^{-1/2} for two-sample MMD) under mild conditions, even with unbounded kernels. This paper proves matching minimax lower bounds of the same order, holding on arbitrary topological spaces rather than only Euclidean space with restrictive kernels. The same lower bounds transfer immediately to estimation of the mean embedding and the centered cross-covariance operator. The result closes the optimality question for these widely used discrepancy measures.","feed_headline":"Kernel discrepancies cannot beat the 1/√n rate","feed_subtitle":"Matching lower bounds hold on general spaces for MMD, HSIC and KSD under mild assumptions","key_machinery":"Le Cam’s two-point method applied to a carefully chosen adversarial pair of measures obtained by continuous bounded perturbations of a base measure; the construction forces the functional values to separate at rate n^{-1/2} while keeping the KL divergence between the product measures bounded.","core_discovery":"Under the assumptions that the kernel is characteristic (or I-characteristic) and that there exists at least one probability measure admitting a non-almost-surely-constant continuous bounded perturbation, the minimax risk of estimating MMD is of exact order n^{-1/2}+m^{-1/2} and the risks of estimating HSIC and KSD are of exact order n^{-1/2}, on general topological spaces. The identical rates hold for the mean embedding and the centered cross-covariance operator.","pith_inferences":["The same perturbation-plus-Le-Cam template should extend without change to other integral-probability-metric discrepancies once a characteristic property and a non-constant continuous function are available.","On spaces where every continuous function is constant almost everywhere (highly pathological topologies), the lower bound may fail and faster rates could become possible.","Practical kernel choice on non-Euclidean data (graphs, manifolds, sequences) can now safely target the parametric rate without fear that a cleverer estimator exists."],"forward_implications":["Existing U-statistic, V-statistic and accelerated estimators of MMD, HSIC and KSD are minimax optimal on far more general domains than previously known.","The same optimality statement holds for mean-embedding estimation and for estimation of the centered cross-covariance operator.","No estimator of these discrepancies can improve on the parametric rate under the stated mild conditions, even when kernels are unbounded.","The lower-bound technique applies uniformly across two-sample, independence and goodness-of-fit settings."],"fun_headline_variants":["MMD HSIC KSD minimax rates pinned at 1/√n","Kernel discrepancies face hard n^{-1/2} lower bound","Optimal kernel discrepancy estimation cannot beat 1/√n","Minimax lower bounds settle MMD HSIC KSD at parametric rate","General-space lower bounds lock MMD HSIC KSD at n^{-1/2}"],"cache_read_input_tokens":128,"weakest_assumption_plain":"There must exist at least one probability measure in the class that is not almost-surely constant under every continuous bounded real function; without such a non-constant perturbation the two-point argument cannot be built.","fun_headline_variants_meta":{"raw":{"variants":["MMD HSIC KSD minimax rates pinned at 1/√n","Kernel discrepancies face hard n^{-1/2} lower bound","Optimal kernel discrepancy estimation cannot beat 1/√n","Minimax lower bounds settle MMD HSIC KSD at parametric rate","General-space lower bounds lock MMD HSIC KSD at n^{-1/2}"]},"model":"grok-4.5","effort":"low","cost_usd":0.004242,"raw_usage":{"total_tokens":1258,"prompt_tokens":772,"num_sources_used":0,"completion_tokens":85,"cost_in_usd_ticks":42424000,"prompt_tokens_details":{"text_tokens":772,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":401,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":772,"tokens_out":85,"duration_ms":7661,"temperature":1.0,"reasoning_tokens":401,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T20:18:35.189955+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a topological space, a characteristic kernel, and a sequence of estimators whose risk is o(n^{-1/2}) uniformly over the stated class of measures, or prove that every continuous bounded function is almost surely constant for every measure in that class.","supporting_citations":[],"review_version":1}