The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels

Authors: florian  kalinke
zoltán  szabó
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:22:23

Abstract: Kernel techniques are among the most influential approaches in data science and statistics. Under mild conditions, the reproducing kernel Hilbert space associated to a kernel is capable of encoding the independence of $M\ge2$ random variables. Probably the most widespread independence measure relying on kernels is the so-called Hilbert-Schmidt independence criterion (HSIC; also referred to as distance covariance in the statistics literature). Despite various existing HSIC estimators designed since its introduction close to two decades ago, the fundamental question of the rate at which HSIC can be estimated is still open. In this work, we prove that the minimax optimal rate of HSIC estimation on $\mathbb{R}^d$ for Borel measures containing the Gaussians with continuous bounded translation-invariant  characteristic  kernels  is $\mathcal{O}\left(n^{-1/2}\right)$. Specifically, our result implies the optimality in the minimax sense of many of the most-frequently used estimators (including the U-statistic, the V-statistic, and the Nyström-based one) on $\mathbb{R}^d$.

Main paper: 
 introduction: 
 Kernel methods [Steinwart and Christmann, 2008 , Berlinet and Thomas-Agnan, 2004 , Saitoh and Sawano, 2016] allow embedding probability measures into reproducing kernel Hilbert spaces (RKHS; [Aronszajn, 1950] ) by use of a positive definite function, the kernel function. This approach has gained considerable attention over the last 20 years. Such embeddings induce the so-called maximum mean discrepancy (MMD; [Smola et al., 2007 , Gretton et al., 2012] ), which quantifies the discrepancy of two probability measures by considering the RKHS norm of the distance of their respective embeddings. MMD is a metric on the space of probability distributions if the kernel is characteristic [Fukumizu et al., 2008 , Sriperumbudur et al., 2010] . MMD is also an integral probability metric [Zolotarev, 1983 , Müller, 1997] where the underlying function class is chosen to be the unit ball in the corresponding RKHS.MMD allows for the quantification of dependence by considering the distance between the embedding of a joint distribution and that of the product of its marginals. This construction gives rise to the so-called Hilbert-Schmidt independence criterion (HSIC; [Gretton et al., 2005] ), which is also equal to the RKHS norm of the centered cross-covariance operator. In fact, one of the most widely-used independence measures in statistics, distance covariance [Székely et al., 2007 , Székely and Rizzo, 2009 , Lyons, 2013] , was shown to be equivalent to HSIC [Sejdinovic et al., 2013b] when the latter is specialized to M = 2 components; Sheng and Sriperumbudur [2023] proved a similar result for the conditional case. For M > 2 components [Quadrianto et al., 2009 , Sejdinovic et al., 2013a , Pfister et al., 2018] , universality [Steinwart, 2001 , Micchelli et al., 2006 , Carmeli et al., 2010 , Sriperumbudur et al., 2011] of the kernels (k m ) M m=1 (on the respective domains) underlying HSIC guarantees that this measure captures independence [Szabó and Sriperumbudur, 2018] . In the case of M = 2, characteristic (k m ) 2 m=1 suffice [Lyons, 2013] .HSIC has been deployed successfully in numerous contexts, including independence testing in batch [Gretton et al., 2008 , Wehbe and Ramdas, 2015 , Bilodeau and Nangue, 2017 , Górecki et al., 2018 , Pfister et al., 2018 , Albert et al., 2022 , Shekhar et al., 2023] and streaming [Podkopaev et al., 2023] settings, feature selection [Camps-Valls et al., 2010 , Song et al., 2012 , Yamada et al., 2014 , Wang et al., 2022] with applications in biomarker detection [Climente-González et al., 2019] and wind power prediction [Bouche et al., 2023] , clustering [Song et al., 2007 , Climente-González et al., 2019] , and causal discovery [Mooij et al., 2016 , Pfister et al., 2018 , Chakraborty and Zhang, 2019 , Schölkopf et al., 2021 , Kalinke and Szabó, 2023] . In addition, HSIC has recently found successful applications in sensitivity analysis [Veiga, 2015 , Freitas Gustavo et al., 2023 , Fellmann et al., 2024 , Herrando-Pérez and Saltré, 2024] , in the context of uncertainty quantification [Stenger et al., 2020] , for the analysis of data augmentation methods for brain tumor detection [Anaya-Isaza and Mera-Jiménez, 2022] , and that of multimodal neural networks trained on neuroimaging data [Fedorov et al., 2024] .Many estimators for HSIC exist. The classical ones rely on U-statistics or V-statistics [Gretton et al., 2005 , Quadrianto et al., 2009 , Pfister et al., 2018] and are known to converge at a rate of O P n -1/2 . In fact, the V-statistic-based estimators are obtained by replacing the population kernel mean embedding with its empirical counterpart; estimating the mean embedding can be carried out at a speed O P n -1/2 [Smola et al., 2007, Theorem 2] , which implies that HSIC can be estimated at the same rate. Existing approximations such as Nyström HSIC [Kalinke and Szabó, 2023] , also achieve this rate under the assumption of an appropriate rate of decay of the effective dimension. While all of these upper bounds match asymptotically, it is not known whether HSIC can be estimated at a faster rate, that is, whether the upper bound of O P n -1/2 is optimal in the minimax sense, or if designing estimators achieving better rates is possible. Lower bounds for the related MMD are known [Tolstikhin et al., 2016] , but the existing analysis considers radial kernels and relies on independent Gaussian distributions. Radial kernels are a special case of the more general class of translation-invariant kernels that we consider. 1 The reliance on independent Gaussian distributions renders the analysis of Tolstikhin et al. [2016] inapplicable for HSIC estimation. We tackle both of these severe restrictions in the present article.We make the following contributions.• We establish the minimax lower bound O n -1/2 of HSIC estimation with M ≥ 2 components on R d with continuous bounded translation-invariant characteristic kernels. As this lower bound matches the known upper bounds of the existing "classical" U-statistic and V-statistic-based estimators, and that of the Nyström HSIC estimator, our result settles their minimax optimality.• Specifically, our result also implies the minimax lower bound of O n -1/2 for the estimation of the cross-covariance operator, which can be further specialized to get back the minimax result [Zhou et al., 2019, Theorem 5] on the estimation of the covariance operator.The paper is structured as follows. Notations are introduced in Section 2. Section 3 is dedicated to our main result on the minimax rate of HSIC estimation on R d , with proof presented in Section 4. An auxiliary result on the Kullback-Leibler divergence is shown in Appendix A.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The abstract and introduction motivate and summarize the theoretical results that we establish in the article.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
notations: 
 In this section, we introduce a few notations  and C X . Throughout the paper we consider random variables, probability measures, and kernels on R d .N >0 , [M ], I n , 0 n , 1 n , A T , ⟨v, w⟩, ∥v∥ R d , bdiag (M 1 , . . . , M N ), |A|, M + 1 R d , ψ P , KL(P||Q), L 2 R d , Λ , ∥f ∥ L 2 (R d ,Λ) , supp(Λ), H k , ϕ k , k, µ k , MMD k , ⊗ M m=1 H km , ⊗ M m=1 k m , P m , ⊗ M m=1 P m , P n , O P (r n ), O(a n ), a n ≍ b n , HSIC k ,For M ∈ N >0 := {1, 2, . . .}, let [M ] := {1, . . . , M }. Denote by I n the n × n-sized identity matrix and by 0 n = (0, . . . , 0) T ∈ R n (resp. 1 n = (1, . . . , 1) T ∈ R n ) a column vector of zeros (resp. ones). The transpose of a matrix A ∈ R d1×d2 is written as A T ∈ R d2×d1 . For v, w ∈ R d , ⟨v, w⟩ = v T w stands for their Euclidean inner product; ∥v∥ R d = ⟨v, v⟩ is the associated Euclidean norm.bdiag (M 1 , . . . , M N ) forms a block-diagonal matrix from its arguments(M n ) N n=1 (M n ∈ R dn×dn , n ∈ [N ]) and |A| denotes the determinant of a matrix A ∈ R d×d .The set of Borel probability measures on R d is denoted by M + 1 R d . For a random variable Given a measure space [Cohn, 2013, p. 207] .X ∼ P ∈ M + 1 R d , we denote its characteristic function by ψ P (ω) = E X∼P e i⟨ω,X⟩ with ω ∈ R d and i = √ -1. Let P, Q ∈ M + 1 R d ,R d , B R d , Λ , we denote by L 2 (R d , Λ) := L 2 R d , B R d , Λ the Hilbert space of (equivalence classes of) measurable functions f : R d , B R d → (R, B (R)) for which ∥f ∥ 2 L 2 (R d ,Λ) := R d |f (x)| 2 dΛ(x) < ∞. The support of a probability measure Λ ∈ M + 1 R d denoted by supp(Λ) is the subset of R d for which every open neighborhood of x ∈ R d has positive measureA function k : R d × R d → R is called a kernel if there exists a Hilbert space H and a feature map ϕ :R d → H such that k(x, x ′ ) = ⟨ϕ(x), ϕ(x ′ )⟩ H for all x, x ′ ∈ R d . A Hilbert space of functions h : R d → R is an RKHS H k associated to a kernel k : R d × R d → R if k(•, x) ∈ H k and ⟨h, k(•, x)⟩ H k = h(x) for all x ∈ R d and h ∈ H k . 2In this work, we assume all kernels to be measurable and bounded. 3 The function ϕ k (x) := k(•, x) is the canonical feature map, and [Wendland, 2005, Theorem 6 .6] (recalled in Theorem B.1) for a continuous bounded translation-invariant kernel k : R d × R d → R there exists a finite non-negative Borel measure Λ k such thatk(x, x ′ ) = ⟨k(•, x), k(•, x ′ )⟩ H k = ⟨ϕ k (x), ϕ k (x ′ )⟩ H k for all x, x ′ ∈ R d . A function κ : R d → R is called positive definite if i,j∈[n] c i c j κ(x i -x j ) ≥ 0 for all n ∈ N >0 , c = (c i ) n i=1 ∈ R n , and {x i } n i=1 ⊂ R d . A kernel k : R d × R d → R is said to be translation-invariant if there exists a positive definite function κ : R d → R such that k(x, x ′ ) = κ(x -x ′ ) for all x, x ′ ∈ R d . By Bochner's theoremEQUATIONfor all x, y ∈ R d . The (kernel) mean embedding of a probability measureP ∈ M + 1 R d is µ k (P) = R d ϕ k (x)dP(x) ∈ H k ,where the integral is meant in Bochner's sense [Diestel and Uhl, 1977, Chapter II.2] ; the boundedness of k ensures that it is well-defined. For P, Q ∈ M + 1 R d one can define the (semi-)metric called maximum mean discrepancy [Smola et al., 2007 , Gretton et al., 2012] asMMD k (P, Q) = ∥µ k (P) -µ k (Q)∥ H k .If the mean embedding µ k is injective, MMD is a metric and the kernel k is called characteristic [Fukumizu et al., 2008 , Sriperumbudur et al., 2010 , Szabó and Sriperumbudur, 2018] .Let R d = × M m=1 R dm (d = M m=1 d m ) and assume that each domain R dm is equipped with a kernel k m : R dm × R dm → R with associated RKHS H km (m ∈ [M ]). The tensor product Hilbert space of (H km ) M m=1 is denoted by ⊗ M m=1 H km ; it is an RKHS [Berlinet and Thomas-Agnan, 2004, Theorem 13 ] with the tensor product kernel k= ⊗ M m=1 k m : R d × R d → R defined by k (x m ) M m=1 , (x ′ m ) M m=1 = m∈[M ] k m (x m , x ′ m ) for all x m , x ′ m ∈ R dm , m ∈ [M ].The kernel k has the canonical feature mapϕ k (x m ) M m=1 = ⊗ M m=1 ϕ km (x m ) ∈ ⊗ M m=1 H km =: H k (x m ∈ R dm , m ∈ [M ]). Let X = (X m ) M m=1 be a random variable taking values in R d with joint distribution P ∈ M + 1 R d and marginal distributions P m ∈ M + 1 R dm (m ∈ [M ]; d = M m=1 d m ). We write ⊗ M m=1 P m ∈ M + 1 R d for the product of measures P m (m ∈ [M ]). Specifically, P n := ⊗ n i=1 P ∈ M + 1 R d n denotes the n-fold product of P. For a sequence of real-valued random variables (X n ) ∞ n=1 and a sequence (r n ) ∞ n=1 (r n > 0 for all n), X n = O P (r n ) denotes that Xn rn is bounded in probability. For positive sequences (a n ) ∞ n=1 and (b n ) ∞ n=1 , b n = O(a n ) if there exist constants C > 0 and n 0 ∈ N >0 such that b n ≤ Ca n for all n ≥ n 0 ; a n ≍ b n if a n = O (b n ) and b n = O (a n ).One can define our quantity of interest, the Hilbert-Schmidt independence criterion (HSIC; [Gretton et al., 2005 , Quadrianto et al., 2009 , Pfister et al., 2018 , Szabó and Sriperumbudur, 2018] ), asEQUATIONand C X denotes the centered cross-covariance operator.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We make the assumptions explicit in all of our results. Remark 1(a) further elaborates the characteristic assumption.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
results: 
 This section is dedicated to our results: The minimax lower bound for the estimation of HSIC k (P),where k is a product of continuous bounded translation-invariant characteristic kernels is given in Theorem 1(ii). For the specific case where k is a product of Gaussian kernels (stated in Theorem 1(i)), the constant in the lower bound is made explicit. Theorem 1(ii) also helps to establish a lower bound on the estimation of the cross-covariance operator (Corollary 1).Before presenting our results, we recall the framework of minimax estimation [Tsybakov, 2009] adapted to our setting. Let Fn denote any estimator of HSIC k (P) based on n i.i.d. samples from P. (3)A sequence (ξ n ) ∞ n=1 (ξ n > 0 for all n) isIf a specific estimator of HSIC Fn has an upper bound that matches (ξ n ) ∞ n=1 up to constants, that is,EQUATIONthen Fn is called minimax optimal.We use Le Cam's method [Le Cam, 1973 , Tsybakov, 2009] (recalled in Theorem B.5) to obtain bounds as in (3); estimators of HSIC achieving the bounds in (4) with ξ n = n -1/2 are quoted in the introduction. The key to the application of the method is to show that there exist α > 0 and n 0 ∈ N >0 such that for all n ≥ n 0 one can find an adversarial pair of distributions (P θ0 , P θ1 ) = (P θ0 (n), P θ1 (n)) ∈ P × P and s n > 0 for which 1. KL P n θ1 ||P n θ0 ≤ α, in other words, the corresponding n-fold product measures must be similar in the sense of Kullback-Leibler divergence, but 2. |HSIC k (P θ1 ) -HSIC k (P θ0 )| ≥ 2s n , that is, their corresponding values of HSIC must be dissimilar.In this case, inf Fn sup P∈P P n HSIC k(P) -Fn ≥ s n ≥ max e -α 4 , 1- √ α/2 2 for all n ≥ n 0 ;hence to establish the minimax optimality of existing estimators w.r.t. their known upper bounds, it is sufficient to find adversarial pairs {(P θ0 (n), P θ1 (n))} n≥n0 that satisfy 1. for some positive constant α and also fulfill 2. with s n ≍ n -1/2 . The proof of the first part of our statement relies on the following Lemma 1 which yields the analytical value ofHSIC k (N (µ, Σ)), where k = ⊗ M m=1 k m is the product of Gaussian kernels k m (m ∈ [M ]) and N (µ, Σ) denotes the multivariate normal distribution with mean µ ∈ R d and covariance matrix Σ ∈ R d×d .Lemma 1 (Analytical value of HSIC for the Gaussian setting). Let us consider the Gaus-sian kernel k(x, y) = e -γ 2 ∥x-y∥ 2 R d (γ > 0, x, y ∈ R d ) and Gaussian random variable X = (X m ) M m=1 ∼ N (m, Σ) =: P, where X m ∈ R dm (m ∈ [M ]), m = (m m ) M m=1 ∈ R d , Σ = [Σ i,j ] i,j∈[M ] ∈ R d×d , Σ i,j ∈ R di×dj , and d = m∈[M ] d m . In this case, with Σ 1 = Σ and Σ 2 = bdiag(Σ 1,1 , . . . , Σ M,M ), we have HSIC 2 k (P) = 1 |2γΣ 1 + I d | 1 2 + 1 |2γΣ 2 + I d | 1 2 - 2 |γΣ 1 + γΣ 2 + I d | 1 2.In this work, we focus on continuous bounded translation-invariant kernels, which are fully characterized by Bochner's theorem [Wendland, 2005, Theorem 6.6] ; the theorem states that a function on R d is positive definite if and only if it is the Fourier transform of a finite nonnegative measure. 4 We use this description to obtain our main result, which is as follows.Theorem (i) the kernels k m : R dm × R dm → R are Gaussian with common bandwidth parameter γ > 0defined by (x m , x ′ m ) → e -γ 2 ∥xm-x ′ m ∥ 2 R dm (x m , x ′ m ∈ R dm ), or (ii) the kernels k m : R dm × R dm → R are continuous bounded translation-invariant characteristic kernels.Then, for any n ≥ n 0 , it holds thatinf Fn sup P∈P P n HSIC k (P) -Fn ≥ c √ n ≥ 1 -5 8 2 , with (i) the constant c = γ 2(2γ+1) d 4+1 > 0 (depending on γ and d only) in the first case, or (ii) some constant c > 0 in the second case.We note that while Theorem 1(ii) applies to the more general class of translation-invariant kernels, we include Theorem 1(i) as it makes the constant c explicit.The following corollary allows to recover the recent lower bound on the estimation of the covariance operator by Zhou et al. [2019, Theorem 5] as a special case that we detail in Remark 1(e). Corollary 1 (Lower bound on cross-covariance operator estimation). In the setting of Theorem 1(ii), let Fn denote any estimator of the centered cross-covariance operator C X ∈ H k defined in (2) with n ≥ 2 =: n 0 i.i.d. samples from P ∈ P. Then, for any n ≥ n 0 , it holds thatinf Fn sup P∈P P n C X -Fn H k ≥ c √ n ≥ 1 -5 8 2 ,for some constant c > 0.Remark 1.(a) Validness of HSIC. Though generally the characteristic property of (k m ) M m=1 -s is not enough [Szabó and Sriperumbudur, 2018, Example 2] The Nyström-based HSIC estimator achieves the same rate under an appropriate decay of the eigenspectrum of the respective covariance operator. Hence, Theorem 1 implies the optimality of these estimators on R d with continuous bounded translation-invariant characteristic kernels in the minimax sense.(c) Difference compared to Tolstikhin et al. [2016] (minimax MMD estimation). We note that a lower bound for the related MMD k exists. However, the adversarial distribution pair (P θ1 , P θ0 ) constructed by Tolstikhin et al. [2016, Theorem 1] to obtain the lower bound on MMD estimation has a product structure which implies that |HSIC k (P θ1 ) -HSIC k (P θ0 )| = 0 and hence it is not applicable in our case of HSIC; Tolstikhin et al. [2016, Theorem 2] with radial kernels has the same restriction.(d) Difference compared to Tolstikhin et al. [2017] (minimax mean embedding estimation). The estimation of the mean embedding µ k (P) is known to have a minimax rate of O n -1/2 . But, this rate does not imply an optimal lower bound for the estimation of MMD as is evident from the two works [Tolstikhin et al., 2016 [Tolstikhin et al., , 2017]] . The same conclusion holds for HSIC estimation.(e) Difference compared to Zhou et al. [2019] (minimax covariance operator estimation). For the related problem of estimating the centered covariance operator Zhou et al. [2019, Theorem 5] give the lower boundC XX = R d (ϕ k (x) -µ k (P)) ⊗ (ϕ k (x) -µ k (P)) dP(x) ∈ H k ⊗ H k ,inf Fn sup P∈P P n C XX -Fn H k ⊗H k ≥ c √ n ≥ 1/8in the same setting as in Theorem 1(ii), where Fn is any estimator of the centered covariance C XX , and c is a positive constant. By noting that the centered covariance is the centered cross-covariance of a random variable with itself, Corollary 1 recovers their result.The next section contains our proofs.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: We provide explicit proofs to all of our claims. External results that we use are referenced and additionally included as part of the supplement to ensure self-completeness.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.• Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.• Theorems and Lemmas that the proof relies upon should be properly referenced. 
proofs: 
 This section is dedicated to our proofs. We present the proof of Lemma 1 in Section 4.1, that of Theorem 1 in Section 4.2, and that of Corollary 1 in Section 4.3.AsHSIC 2 k (P) = MMD 2 k (P, Q) = ∥µ k (P) -µ k (Q)∥ 2 H k = ⟨µ k (P), µ k (P)⟩ H k + ⟨µ k (Q), µ k (Q)⟩ H k -2⟨µ k (P), µ k (Q)⟩ H k with Q = ⊗ M m=1 P m = N (m, bdiag(Σ 1,1 , . . . , Σ M,M )), P m = N (m m , Σ m,m ), it is suf- ficient to be able to compute ⟨µ k (P), µ k (Q)⟩ H k -type quantities with P = N (m 1 , Σ 1 ) and Q = N (m 2 , Σ 2 ). One can show [Muandet et al., 2011, Table 1] that ⟨µ k (P), µ k (Q)⟩ H k = e -1 2 (m 1 -m 2 ) T ( Σ 1 +Σ 2 +γ -1 I d ) -1 (m 1 -m 2 ) |γΣ1+γΣ2+I d | 1 2. Using this fact and that m = m 1 = m 2 , the result follows.The setup and the upper bound on KL(P n θ1 ||P n θ0 ) agree for (i) and (ii) but the methods that we use to lower bound |HSIC k (P θ1 ) -HSIC k (P θ0 )| differ. We structure the proof accordingly and present the overlapping part before we branch out into (i) and (ii). Both parts of the statement rely on Le Cam's method, which we state as Theorem B.5 for self-completeness.To construct the adversarial pair, we consider a class G of Gaussian distributions over R d such that every element N µ, Σ ∈ G, withEQUATIONand (fixed) i = d 1 , j = d 1 + 1, ρ ∈ (-1, 1). In other words, Σ is essentially the d-dimensional matrix I d except for the (i, j) and (j, i) entry; both entries are identical to ρ, and they specify the correlation of the respective coordinates. This family of distributions is indexed by a tuple As G ⊆ P, it holds for every positive s that(µ, ρ) ∈ R d × (-sup P∈P P n HSIC k (P) -Fn ≥ s ≥ sup P∈G P n HSIC k (P) -Fn ≥ s . Let P θ0 = N (µ 0 , Σ 0 ) and P θ1 = N (µ 1 , Σ 1 ) with µ 0 = 0 d ∈ R d , Σ 0 = Σ(d 1 , d 1 + 1, 0) = I d ∈ R d×d , µ 1 = 1 √ dn 1 d ∈ R d , Σ 1 = Σ(d 1 , d 1 + 1, ρ n ) ∈ R d×d ,where ρ n ∈ (-1, 1) will be chosen appropriately later. 5 We now proceed to upper bound KL P n θ1 ||P n θ0 and lower bound |F (θ 1 ) -F (θ 0 )|.Upper bound for KL divergence Lemma A.1 implies that with ρ 2 n = 1 n , one has the bound KL P n θ1 ||P n θ0 ≤ α := 5 4 for n ≥ 2 =: n 0 .Lower bound (i): Gaussian kernels. Recall that the considered kernel is k(x, y) = e -γ 2 ∥x-y∥ 2 R d (γ > 0). The idea of the proof is as follows.1. We express |F (θ 1 ) -F (θ 0 )| in closed form as a function of γ, ρ n , and d.2. Using the analytical form obtained in the 1st step, we construct the lower bound.This is what we detail next.• Analytical form of |F (θ 1 ) -F (θ 0 )|: Using the fact that HSIC k (P θ0 ) = 0, we have thatF (θ 1 ) -F (θ 0 ) =0 2 = F 2 (θ 1 ) = HSIC 2 k (P θ1 ) = MMD 2 k (N (µ 1 , Σ 1 ) , N (µ 1 , I d )) = ∥µ k (N (µ 1 , Σ 1 )) -µ k (N (µ 1 , I d ))∥ 2 H k = ⟨µ k (N (µ 1 , Σ 1 )) , µ k (N (µ 1 , Σ 1 ))⟩ H k (i) + ⟨µ k (N (µ 1 , I d )) , µ k (N (µ 1 , I d ))⟩ H k (ii) -2 ⟨µ k (N (µ 1 , Σ 1 )) , µ k (N (µ 1 , I d ))⟩ H k (iii), 5 Notice the dependence of P θ 1 on n.which we compute term-by-term with Lemma 1, and obtain(i) = |2γΣ 1 + I d | -1/2 = (2γ + 1) d-2 (2γ + 1) 2 -(2γρ n ) 2 -1/2 , (ii) = |2γI d + I d | -1/2 = (2γ + 1) d -1/2 , (iii) = |γΣ 1 + γI d + I d | -1/2 = (2γ + 1) d-2 (2γ + 1) 2 -(γρ n ) 2 -1/2.Combining (i), (ii), and (iii) yields thatHSIC 2 k (P θ1 ) = (i) + (ii) -2(iii) = (2γ + 1) d-2 (2γ + 1) 2 -(2γρ n ) 2 -1/2 + (2γ + 1) d -1/2 -2 (2γ + 1) d-2 (2γ + 1) 2 -(γρ n ) 2 -1/2.• Lower bound on |F (θ 1 ) -F (θ 0 )|: Next, we show that there exists c > 0 such that for anyn ∈ N >0 it holds that HSIC 2 k (P θ1 ) ≥ c n . For 0 < x < 1 + 1 2γ 2, let us consider the functionf c (x) = (2γ + 1) d-2 (2γ + 1) 2 -4γ 2 x -1/2 + (2γ + 1) d -1/2 -2 (2γ + 1) d-2 (2γ + 1) 2 -γ 2 x -1/2 -cx = z d-2 z 2 -4γ 2 x -1/2 + z d -1/2 -2 z d-2 z 2 -γ 2 x -1/2 -cx,with the shorthand z := 2γ + 1. 6 With this notation, f c (1/n) = HSIC 2 k (P θ1 ) -c/n; our aim is to determine c > 0 such that f c (1/n) ≥ 0 for any positive integer n. To achieve this goal, notice that f c (0) = 0, andf ′ c (x) = 2γ 2 z d-2 [z d-2 (z 2 -4xγ 2 )] 3/2 - γ 2 z d-2 [z d-2 (z 2 -xγ 2 )] 3/2 -c > 2γ 2 z d-2 [z d-2 (z 2 -xγ 2 )] 3/2 - γ 2 z d-2 [z d-2 (z 2 -xγ 2 )] 3/2 -c = γ 2 z d-2 [z d-2 (z 2 -xγ 2 )] 3/2 -c > γ 2 z d-2 (z d-2 z 2 ) 3/2 -c = γ 2 z 2 √ z d -c = γ 2 (2γ + 1) 2 (2γ + 1) d -c. Choosing now c = γ 2 (2γ+1) 2 √ (2γ+1) d > 0, we have f ′ c (x) ≥ 0, so f is a nondecreasing function. Note that f c (1/n) = HSIC 2 k (P θ1 ) -c/n ≥ 0, with x = 1/n and 1 + 1 2γ -2 < 1 ≤ n < ∞.By taking the positive square root, this means thatHSIC k (P θ1 ) ≥ γ (2γ + 1) (2γ + 1) d 1/4 √ n =: 2s holds for n ≥ 1, implying that |F (θ 1 ) -F (θ 0 )| ≥ 2s > 0.We conclude the proof by Theorem B.5 using that α = 5 4 and max e -5 4 4 ,1- √ 5 8 2 = 1- √ 5 8. 6 Notice that (2γ + 1) 2 -γ 2 x > (2γ + 1) 2 -4γ 2 x, and(2γ + 1) 2 -4γ 2 x > 0 ⇔ x < 1 + 1 2γ 2for a positive x; hence the imposed assumption on x ensures that the function fc is well-defined.Lower bound (ii): translation-invariant kernels. Let Λ k denote the spectral measure associated to the kernel k according to (1). Using the fact that HSIC k (P θ0 ) = 0, we have for |F (θ 1 ) -F (θ 0 )| thatF (θ 1 ) -F (θ 0 ) =0 2 = F 2 (θ 1 ) = HSIC 2 k (P θ1 ) = MMD 2 k (N (µ 1 , Σ 1 ) , N (µ 1 , Σ 0 )) (i) = ψ N (µ1,Σ1) -ψ N (µ1,Σ0) 2 L 2 (R d ,Λ k ) (ii) = R d e i⟨µ1,ω⟩-1 2 ⟨ω,Σ1ω⟩ -e i⟨µ1,ω⟩-1 2 ⟨ω,Σ0ω⟩ 2 dΛ k (ω) = R d e i⟨µ1,ω⟩ 2 =1 e -1 2 ⟨ω,Σ1ω⟩ -e -1 2 ⟨ω,Σ0ω⟩ 2 dΛ k (ω) (iii) ≥ A e -1 2 ⟨ω,Σ1ω⟩ -e -1 2 ⟨ω,Σ0ω⟩ 2 dΛ k (ω) (iv) ≥ ρ 2 n A [h ′ ω (0)] 2 dΛ k (ω) =:(2c) 2 (v) = (2c) 2 n =:(2s) 2 >0, where (i) holds by Sriperumbudur et al. [2010, Corollary 4(i) ] (recalled in Theorem B.2). (ii) follows from the analytical form ψ N (µ,Σ) (t) = e i⟨µ,t⟩-1 2 ⟨t,Σt⟩ of the characteristic function of a multivariate normal distribution N (µ, Σ). For (iii), we define the non-empty open setA = ω = (ω 1 , . . . , ω d ) T ∈ R d : ω d1 ω d1+1 < 0 ⊂ R d ,and use that the integration of a non-negative function over a subset yields a lower bound. In (iv), fix ω ∈ A and leth ω : ρ ∈ [0, 1] → e -1 2 ⟨ω,Σ(d1,d1+1,ρ)ω⟩ ∈ (0, 1].Note that h ω (ρ) = e -1 2 (ω T ω+2ρω d 1 ω d 1 +1) ; h ω is continuous on [0, 1] and differentiable on (0, 1). Hence for any ρ ∈ (0, 1), by the mean value theorem, there exists ρ ∈ (0, 1) such thath ω (ρ) -h ω (0) = ρh ′ ω (ρ) ≥ ρ min c∈[0,1] h ′ ω (c).We have the first and second derivativesh ′ ω (c) = -ω d1 ω d1+1 e -1 2 (ω T ω+2cω d 1 ω d 1 +1) , h ′′ ω (c) = ω 2 d1 ω 2 d1+1 e -1 2 (ω T ω+2cω d 1 ω d 1 +1) > 0,which implies that c → h ′ ω (c) is a strictly increasing function of c and that it attains its minimum at c = 0, that is,h ω (ρ) -h ω (0) ≥ ρh ′ ω (0) > 0,where the 2nd inequality holds by ρ > 0 and ω ∈ A. This shows that[h ω (ρ) -h ω (0)] 2 ≥ [ρh ′ ω (0)] 2 ,and the monotonicity of integration gives (iv). For (v), we note that the kernel k = ⊗ M m=1 k m is characteristic [Szabó and Sriperumbudur, 2018, Theorem 4 ] (recalled in Theorem B.4) as the (k m ) M m=1 -s are characteristic. Thus, supp (Λ k ) = R d (see Sriperumbudur et al. [2010, Theorem 9] ; recalled in Theorem B.3), implying that Λ k (A) > 0. (v) follows from the positivity of h ′ ω (0) (for any ω ∈ A), from the fact that the integral of a positive function on a set with positive measure is positive, and from our choice of ρ n = n -1/2 . Now, by taking the positive square root, we haveEQUATION)We conclude by the application of Theorem B.5 using that α = 5 4 and max e -5 4 4 ,1- √ 5 8 2 = 1- √ 5 8 2 .We use the same argument as in the beginning of the proof of Theorem 1 in Section 4.2 but adjust the setting in which we apply Theorem B.5. Specifically, we now let Θ = {θ a := C Xa : X a ∼ P a , a ∈ A} with C X defined as in (2) be the set of covariance operators, use the metric (x, y) → ∥x -y∥ H k for x, y ∈ H k , and keep the remaining part of the setup the same. Hence, it remains to lower bound C X θ 1 -C X θ 0 H k . By using that HSIC is the RKHS norm of the cross-covariance operator, we obtain thatC X θ 1 -C X θ 0 H k (i) ≥ C X θ 1 H k =HSIC k (Pθ 1 ) -C X θ 0 H k =HSIC k (Pθ 0 ) = |F (θ 1 ) -F (θ 0 )| (ii) ≥ 2s = 2c √ n ,where (i) holds by the reverse triangle inequality, F is defined as in Section 4.2, and (ii) is guaranteed by ( 11) for c > 0. We conclude as in the proof of Theorem 1(ii) to obtain the stated result.In this section, we collect an auxiliary result. Lemma A.1 presents an upper bound on the Kullback-Leibler divergence between multivariate normal distributions.Lemma A.1 (Upper bound on KL divergence). Let d = M m=1 d m , with d m ∈ N >0 (m ∈ [M ]). Fix i ∈ [d 1 ]. Let j = i + 1, P θ0 = N (0 d , I d ), and P θ1 = N (µ 1 , Σ 1 ), with µ 1 = 1 √ dn 1 d ∈ R d , and Σ 1 = Σ(i, j, ρ n ) ∈ R d×d defined as in (5) (ρ n ∈ (0, 1)). Then, for 2 ≤ n ∈ N, KL(P n θ1 ||P n θ0 ) ≤ 1 2n + n 2 ρ 2 n 1 -ρ 2 n .In particular, for ρ 2 n = 1/n, it holds that KL(P n θ1 ||P n θ0 ) ≤ 5 4 .Proof. With µ 0 = 0 d and Σ 0 = I d , we obtain that EQUATION2 n = 1/n as n 2 1/n 1 -1/n 1 n-1 ≤ 1 ⇐⇒ n 2 1 n -1 ≤ 1 ⇐⇒ n ≤ 2(n -1) ⇐⇒ n ≥ 2,and in this case (for n ≥ 2) one has that 1 2n ≤ 1 4 .For self-completeness, we include the external statements that we use. κ(x) = R d e -i⟨x,ω⟩ dΛ(ω), for all x ∈ R d .Theorem B.2 (Corollary 4(i); Sriperumbudur et al. [2010] ). Let k : R d × R d → R be a continuous bounded translation-invariant kernel. Then, for anyP, Q ∈ M + 1 R d , MMD 2 k (P, Q) = ∥ψ P -ψ Q ∥ 2 L 2 (R d ,Λ k ), with ψ P and ψ Q being the characteristic functions of P and Q, respectively, and Λ k defined in (1).Theorem B.3 (Theorem 9; Sriperumbudur et al. [2010] ). Suppose k : R d × R d → R is a continuous bounded translation-invariant kernel. Then k is characteristic if and only if supp(Λ k ) = R d , with Λ k defined as in (1). Theorem B.4 (Theorem 4; Szabó and Sriperumbudur [2018] ). Suppose k m : R dm × R dm → R is continuous bounded and translation-invariant kernel for all m ∈ [M ]. Then the following statements are equivalent:(i) (k m ) M m=1 -s are characteristic; (ii) ⊗ M m=1 k m is characteristic; (iii) ⊗ M m=1 k m is I-characteristic.The next statement follows directly from Tsybakov [2009, Eq. (2.9) ] and Tsybakov [2009, Theorem 2.2 ]. Theorem B.5 (Theorem 2.2; Tsybakov [2009] ). Let X be a measurable space, (Θ, d) is a semi-metric space, and P Θ = {P θ : θ ∈ Θ} is a class of probability measures on X indexed by Θ. We observe data D ∼ P θ ∈ P Θ with some unknown parameter θ. The goal is to estimate θ. Let θ = θ(D) be an estimator of θ based on D. Assume that there exist θ 0 , θ 1 ∈ Θ such that d(θ 0 , θ 1 ) ≥ 2s > 0 andKL(P θ1 ||P θ0 ) ≤ α < ∞ for α > 0. Then inf θ sup θ∈Θ P θ d θ, θ ≥ s ≥ max e -α 4 , 1 -α/2 2 .We have the following property of the Kullback-Leibler divergence for product measures [Tsybakov, 2009, p. 85 ]. Lemma B.1 (KL divergence of product measures).Let P = ⊗ n i=1 P i and Q = ⊗ n i=1 Q i . Then KL(P||Q) = i∈[n] KL(P i ||Q i ).The following lemma [Duchi, 2007, p. 13] shows that the Kullback-Leibler divergence of multivariate Gaussians can be computed in closed form. Lemma B.2 (KL divergence of Gaussians). The KL divergence of two normal distributionsN (µ 1 , Σ 1 ) and N (µ 0 , Σ 0 ) on R d is KL(N (µ 1 , Σ 1 )||N (µ 0 , Σ 0 )) = tr(Σ -1 0 Σ 1 ) + (µ 0 -µ 1 ) T Σ -1 0 (µ 0 -µ 1 ) -d + ln |Σ0| |Σ1| 2 .NeurIPS Paper ChecklistQuestion: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [NA] Justification: The paper does not contain experiments.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The paper does not include experiments requiring code.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: The paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: The paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: The paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research presented in this work conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This work presents basic research without any tangible societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: The paper does not use existing assets.(or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).The family of radial kernels encompasses, for example, Gaussians, mixtures of Gaussians, inverse multiquadratics, and Matérn kernels; the Laplace kernel is translation-invariant but not radial (with respect to the traditionally-chosen Euclidean norm ∥•∥ R d ).For fixed x ∈ R d , the function k(•, x) : R d → R means x ′ → k(x ′ , x).Boundedness of the kernel, that is, sup x,x ′ ∈R d k(x, x ′ ) < ∞, implies boundedness of the feature map, that is, sup x∈R d ∥ϕ k (x)∥ H k < ∞ (and vice versa); it is also equivalent to sup x∈R d k(x, x) < ∞.We note that for many translation-invariant kernels, the corresponding spectral measures are known[Sriperumbudur et al., 2010, Table 2]. 
 
 Appendix:  


Decision: The paper presents the minimax optimal rate of HSIC estimation on $R^d$ for Borel measures containing the Gaussian distributions with continuous bounded translation-invariant characteristic kernels. In particular, the result implies the optimality in the minimax sense of frequently used estimators, including the U-statistic, the V-statistic, and the Nyström-based method on $R^d$.

Reviewers all agree that the obtained result is novel, noteworthy, and of interest to the community. It is an interesting, though not particularly innovative methodologically, application of the well-known Le Cam's method for minimax risk.

Reviews: review: paper_summary: paper_summary: The rate at which HSIC can be estimated is an important and open problem, in this paper, the authors prove that
the minimax optimal rate of HSIC estimation for Borel measures is $\mathcal{O}(n^{-0.5})$ with M>=2 components, which is very important as existing conclusion only holds for M=2. Other byproducts can be naturally introduced, implying the minimax lower bound for the estimation of
cross-covariance operator, which can be further specialized to get back the minimax result on the estimation of the covariance operator.
strength_weakness: strength_weakness: 1. Overall, the paper is not easy to follow as the paper's main contribution seems to be the proof part. 
2. I wouldn't say it is the weakness or the author's problem, as this is a theoretical paper, experiments are not necessary. Still is it possible to design toy experiments to validate the conclusions in the paper?
questions: questions: NA
limitations: limitations: NA
paper_summary: paper_summary: In this work, the authors prove that the minimax optimal rate of HSIC estimation on $\mathbb R^{d}$ for Borel measures containing the Gaussians with continuous bounded translation-invariant characteristic kernels is $n^{-1/2}$.
strength_weakness: strength_weakness: Due to my ignorance, I may not be able to provide a sufficient evaluation of the importance of this problem. It would be easier for me to evaluate its importance if the author could offer more related literature and a comparison with them.
questions: questions: There are some minor issues. 

Can the author provide a more concrete definition of HSIC? For example, in equation (2), does it imply that we have fixed a decomposition 
$d=d_{1}+...+d_{M}$ and $P_{m}$  is the marginal distribution of P on $R^{d_{m}}$.?
​
limitations: limitations: None
paper_summary: paper_summary: This paper studies the statistical property of Hilbert Schmidt Independence Criterion (HSIC). Specifically, under either Gaussian or continuous bounded translation-invariant characteristic kernel that is defined on $\mathbb{R}^d$, the paper prove that HSIC can be estimated at the optimal rate in the minimax sense. The minimax lower bound is obtained via the Le Cam's method, where the authors find two distributions that are close in the KL divergence sense, but is dissimilar in the HSIC sense. Their results further demonstrates that many empirical estimators in literature is minimax optimal.
strength_weakness: strength_weakness: While the authors explain how they obtain the lower bound via Le Cam's method, I would more appreciate if the authors can briefly explain the main technical challenge in proving the lower bound. It seems that the lower bound proof is a straight forward application of Le Cam's approach.

It seems that in Zhou et al., (2019), they also obtain the lower bound for the centred covariance operator $C_{XX}$. The definition of $C_{XX}$ is similar to the HSIC setting and the lower bound is almost the same. I would appreciate the authors to provide more discussion on the difference between the two settings and how the proof is different from Zhou et al., (2019).
questions: questions: See weakness
limitations: limitations: NA

Comments: comment: Thanks for replying. I will maintain my score.
Thanks for replying. I will maintain my score.