The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels
Authors: Florian Kalinke
Zoltán Szabó
Venue: NeurIPS 2024 poster (2024)
Keywords: kernel method
Hilbert-Schmidt independence criterion
minimax rate
translation-invariant kernels
Primary area: learning_theory
TL;DR: We prove that the minimax optimal rate of HSIC estimation on R^d with continuous bounded translation-invariant characteristic kernels is O(n^{−1/2}).

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$.

The Minimax Rate of HSIC Estimation for Translation-Invariant Kernels
Florian Kalinke
Zoltán Szabó Department of Statistics London School of Economics
Institute for Program Structures and Data Organization
Karlsruhe Institute of Technology
Karlsruhe, Germany
London, UK z. wws.bbolsee.ac..
florian kalinke@kit.....
Abstract
Kernel techniques among the most influential approaches in data science and statistics. Under mild conditions, the reproducing kernel Hilbert space associated a kernel is capable of encoding the independence of M 2 random variables. Probably the most widespread independence measure relying on kernels is the so- called Hilbert-Schmine independence criterion (HSIC; also referred to as distance covariance in the statistics literature). Despite various existing HSIC estimators designed since its introduction close to 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 IR for Borel measures containing the Gaussians with continuous bounded translation-invariint characteristic kernels is (/2). 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-baus based one) on Rd
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 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 al. 2007 Gretton et al. 20122). which quantifies the discrepancy of two probability measures by considering the RKHS norm of the distance of their respective embeddings. MMD is a metric the space of probability distributions if the kernel is characteristic Fuuuumizu et al.) 2008 (rriperumbudur et al. 2010). MMD also an integral probability metric
Zolotarev] 1983 Müller 1997| where the underlying function class is chosen 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 the product of its marginals. This construction gives rise to the so-called Hilbert-Schmidt independence criterion (HSIC; [Grettnn 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 al. 2007| (Székely and Rizzo 2009 Lyons] 2013), was shown to be cquivalent to HSIC [Sejdinovic et al. [0133]] when the latter is specialized to M components: (Shng and Sriperumbudur [2023] proved similar result for the
conditional case. For 2 components QQaddraatoo et al. 22099 Sejdinovic et al. 2013a PPister
et al. 2018 universality [Steinwart] 2001 Micchelli et | [
Carmeli et al.) 2010 Srrieeummuuur
et al. 2011 of the kernels (kim mm (on the respective domains) underlying HSIC guarantees that
this measure captures independence (zabó and Sriperumbudur 2018). In the case of M
characteristic (kim) suffice Lyons 2013
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

HSIC has been deployed successfully in numerous contexts, including independence testing in batch
Gretton al. 2008, Wehbe and Ramdas 2013 Bilodeau and Nangue, 2017 Górecki et al. 2018
Pfister et a 2018 Albert et al. 2022 [Shekhar et al. 2023 and streaming [Podkopaey et al. 2023
settings, feature selection [Camps- Valls al. 2010 Song et al. 2012] Yamada et al. 2014 Wang
et al. [022] with applications in biomarker detection [Climente- González et 2019 and wind
power prediction [Bouche et al., 2023], ),
clustering [Song et al. Coone[Cimente-Gonzzine
et al. 2019),
and causal discovery [Mooij et 2011 Plister et al. 2011
C Chakraborty and Zhang [2019] Scchokkpp al. [202]] Kalinke and Szabó 2023]. In addition, HSIC has recently found successtul applications in
sensitivity analysis Veigaa 2015 Freitas Gustavo et al. 2023 Fellmann et al. 20244] Herrando- Pérez
and Saltre 2024), in the context of uncertainty quantification [Stngee 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 (0024)
Many estimators for HSIC exist. The classical ones rely on U-statistics or V-statistics [Gretton al. 2005 Quadrianto et al. 2009 Phister et al., 2018] and are known to converge at a rate of 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 Op (n-1/2) [Smola et al. 2007 Theorem 21, which implies that HSIC can be estimated at the same rate. Existing approxumations 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 faster rate, that is, whether the upper bound of Op (n- 1/2) is optimal in the minimax sense, or if designing estimators achieving better rates is possible. Lower bounds for the related MMD known [Tolstikhin 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 munslation-ivvaiian kernels that we consider 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.
Op nn 1/2). In fact, the V-statistic-
We make the following contributions.
We establish the minimax lower bound O (n-1/2) of HSIC estimation with M 2 2 components on Rd with continuous bounded conslatiio-invariinn characteristic kerness. As this lower bound matches the known upper bounds of the existing "classical" U-statistic and V-statistic-hased 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- for the estimation of the cross covarrance operator, which can be further specialized to get back the minimax result Zhou al., 2019 Theorem 5] on the estimation of the covariance operator.
The paper is structured as follows. Notations are introduced in Section 2 Section B dedicated to our main result on the minimax rate of HSIC estimation on Rd, with proof presented in Section 4 An auxiliary result on the Kullback-Leibh divergence is shown in Appendix A
2 Notations
In this section, we introduce few notations Noo. [M]. In. Ont In AT, (v,w), lvllg bdiag (M1,..., My), |A), Mt (Rd), the, (T.(P))Q). 1,2 (Rd A), I Supp(A), He. di, k. uk. MMD,, @M Hr.,. &M km. Pm. @M Pm. Pr, Op (rx), O(a,), a, x bn. HSIC', and Cx. Throughout the paper we consider random variables, probability measures, and kernels on Rdd
For M E N50 (1, let [M] == (1..... M). Denote by In the n x nesized identity matrix and by 0,, = (0. (O....,0)) O)T E RD (resp. 1, = (1,.... ..).... 1)T E RT) a column vector of zeros (resp. ones). The transpose of matrix A E Rd stands for their Euclidean inner product; ||vl|
xd2 xdz is written as AT E Rddxdd For v, w E Rd. (v. w) = vTw vv is the associated Euclidean norm.
'The family of radial kerelss encompasses, for example, Gaussians, mixtures of Gaussians, inverse multi- quadratics, and Matérn kernels; the Laplace kernel is translation invvariann but not radial (with respect to the traditionally-chet chosen Euclidean norm ||: l2d).

---

bdiag (M1.... ,M,) forms a block -iickona matrix from its arguments (M,) (M, E Rda n E [N) and |A| denotes the determinant of a matrix E Ruxdd
The set of Borel probability measures on Rd is denoted by Mf (R+). For a random variable X ~ IP E MT (Rd)), we denote its characteristic function by (hr(w) = Ex-r [e with E R and i 1-1. Let P.Q MI (R*), assume that IP is absolutely continuous w.r.t
dP
Q and let denote the corresponding Radon-Nikodym derivative (of IP w.n.t. Q) Then, the dQ
dP
Kullback-Leible divergence of IP and Q is defined as KL(PIIQ) = Jaa log
IQ (x)
dP(x).
Given a measure space (R B (R4) A),, we denote by L (R A) == L [R _ (R') A) the Hilbert space of (equivalence classes of) measurable functions f: (RL B (R*))
(
(R, B (R) for
which [I .A) := Ja== (XA)) < co. The support of a probability measure A E M (R")
denoted by supp(A) (A) is the subset of Tedd for which every open neighborhood of x E IR has positive measure [Cohn 2013 p. 207].
A function k : _2d x Rd - I is called kernel if there exists a Hilbert space H and feature map Φ : RRd H such that k(x, x') = (o(x), o(x')> for all x, x' R A Hilbert space of functions : Rd + R is an RKHS H4 associated to a kernel : Rd Rd + R if (.,,)) E Hx assume all kernels to h(x) for all x E Ra and h E Hx. In this work,
and (h, ((,,((())))))))) x)
be measurable and bounded F The function (x(xx) = k(,,)) x) is the canonical feature map, and 6(x,x') (k(,, x), k(. x))
is called positive definite if H4 (xx(x), Φz (x(xx)) for all x, Rd. A function k : R² R E).EEm)) Gc2x((x, xx)) 2 for all n E N с = (c) E R", and )- C Rd. A kernel & RRd x Rd + R is said to be translation- invvarinnnn if there exists positive definite function K Rd + R such that k(x,x')=
x(x xxxxxx x') for all x, e R By Bochner's theorem [Wendland] 2005 Theorem 6.6] (recalled in Theorem [B.]] for a continuous
bounded translation-invarre kernel Re x Rd + E there exists finite non-negative Borel measure Ag such that
k(x,y) = / e ixx vxx (W)(w)
(1)
for all x, y E Rd. The (kemel) mean embedding of a probability measure IP E Mi (R-) is
pa (P) JoL. du (x)dP(x) E Ha,
where the integral is meant in Bochner's sense [Destell and Uhl 1977 Chapter I1.2]: the boundedness of & ensures that it is well-defined. For I., Q E MM Rd can define the (semi-)mmetie called maximum mean discrepancy (Smola et al. 2007 Gretton et al. 2012 as
MMD; (P. Q [14
- Pa (Q) H
If the mean embedding H4 is injective, MMD is a metric and the kernel is called characteris- tic (Fukumizu al. 2008 Sriperumbudur et al. 2010 Szabó and Sriperumbudur 2018
Let IRd x - R Pd (d - dmn) and assume that each domain Rd is equipped with kernel kim Rdd.. x RRd.. IR. with associated RKHS He.,, (m [M). The tensor product Hilbert space of (H4 > denoted by @M H4... it is an RKHS |erlinntt and Thomas- Agnan 2004
Theorem 13] with the tensor product kernel l 60 60
RRd x IRdd R defined by
M 1: ((x))
= II mE(M]
km (Xm; X/m) for all Xm, X'm E RR , m E [M].
The kernel has the canonical feature map Φk ((xm) (M = 1 (xm) E @M Hkm..
Hy (Xm E Rdm, m E [M]) Let X = (Xm) M 1 be random variable taking values in Rd
FFor fixed x E Idd the function x(,x)) x): : Rd 'Boundedness of the kernel, that is, supx l(x, x') < co, implies boundedness of the feature map, that co (and vice versa); it is also equivalent supxegd k(x, x) < co.
R means x' +> x(x'xx).
is, suPxERd I (x) 1|,, my.
3

---

with joint distribution F E MI (R*) and marginal distributions Pm M (R4m) (m E [M]] = Em= dm). We write m= Pm E Mi (R+) for the product of measures Pm (m [M])
Specifically, P := _ E Mj (())") denotes the n-fold product of P. For a sequence of real-valued random variables (Xx)==1 and sequence (rx)n=1 (Tn > 0 for all n), X, = Op (Tn) denotes that Xa is bounded in probability. For positive sequences (an) and (b,, ) bn = (an) Jn if there exist constants C' > 0 and Ro E Ny-0 such that 6n < Ca,, for all π 2 noi an bn an = O (bx) and 6n = O (an). One can define our quantity of interest, the Hilbert-Schmidt independence criterion (HSIC; [Grettnn al. 2005 Quadrianto et al. 2009 Pfister et al. 2018
Szabó and Sriperumbudur 2018) ). as
HSIC& (PP) MMD,, (P. 8 aa ||Cx 1
Cx = (P) - ph M (sm=IPm) Pm) He:
and Cx denotes the centered cross-covariance operator.
3 Results
This section is dedicated to our results: The minimax lower bound for the estimation of HSIC, where k is product of continuous bounded translation-invariint characteristic kernels is given in Theorem Ii). For the specific case where k is product of Gaussian kernels (stated in Theorem | Ii), the constant in the lower bound is made explicit. Theorem [ ji also helps establish a lower bound on the estimation of the cross-covariance operator (Corollary I
Before presenting our results, recall the framework of minimax estimation Tsybakov 2009
adapted our setting. Let Fr, denote any estimator of HSIC₂ (IP) based on i.i.d. samples from P. sequence (6x),== (En. >> 0 for all n) is said to be a lower bound of HSIC estimation w.r.t. a class P of Borel probability measures on Id if there exists a constant e > 0 such that
inf sup F" {5m² HSIC (P) - P.. 2 c > O. F. BEP
(3)
If a specific estimator of HSIC F, has upper bound that matches (Sn) up to constants, that is,
HS) - Fr = -Op (Ex),
(4)
then F, called minimax optimal.
(recalled in Theorem B.5) to obtain bounds as in (3); estimators of HSIC achieving the bounds in 4 with En = n -1/2 are quoted in the introduction. The key to the application of the method is show that there exist 0 and no E No such that for all n 2 no one can find an adversarial pair of distributions (Po,. Po,) = (Poo (n), To, (n)) E P P and sn for which
We use Le Cam's 's method [L Cam 1973 Tsybakov 2009]
1. KL (PH [I2.)) < a, in other words, the corresponding n-fold product measures must be similar in the sense of Kullback-Leibles divergence, but
2. [HSIC,(P,,) HSIC, (Poo)) 2 2s,,, that is, their corresponding values of HSIC must be dissimilar.
In this case, inf p. suppep 1m (IP)CC(P) - -A
sn max | V-/2 for all n 2 no;
hence to establish the minimax optimality of existing estimators w.r.t. their known upper bounds, sufficient to find adversarial pairs (n), Po, (n)) 1220 that satisfy 1. for some positive constant
and also fulfill 2. with 8n = 112
The proof of the first part of our statement relies on the following Lemma I which yields the analytical value of HSIC2 (N(,, E)), where & @.M km is the product of Gaussian kernels km (m [M)) and Nu, Σ) denotes the multivariate normal distribution with mean Rd and covariance matrix E E gdxd

---

Lemma 1 (Analytical value of HSIC for the Gaussian setting). Let us consider the Gaus- sian kernel k(x,y) x y (7 O, x,y Rd) and Gaussian random variable X Xm)m= (m, Σ) P. where Xm E R (m E [M]). m (mm)m= R Σ EmpleeeAM E Bddd Eig Rdxxd, and d E Eme[M] dm In this case, with Σn E and
Σ₂ bdiag(21,.1 MM, we have
1
2
(P)
2y Id
12 + La|
hE E + Ldl
In this work, we focus on continuous bounded translation- invariant kernels, which are fully character- ized by Bochner's 's theorem [Wendland 2005| Theorem 6.6]; the theorem states that function on R positive definite if and only it is the Fourier transform of a finite nonnegative measure R this description to obtain our main result, which is as follows.
We use
Theorem 1 (Lower bound for HSIC estimation on R Let P be a class of Borel probability measures over Rdd containing the d-dimensional Gaussian distributions. Let d = > mmE(M] dm and F, denote any estimator of HSIC& (P) with 2 2 =: no i...d. samples from IP P. Assume farther that &M km=1km where either, for i E [M],
(i) the kernels km Ram Rd R Gaussian with common bandwidth parameter ?
defined by (Xm; xm) m C. - f1|lxmm----- -xx li (Xm: x'm (Rdm ), or
(ii) the kernels km : Rd x Rdm kernels.
- R are continuous bounded translation-invarinn characteristic
Then, for any n 2 no, holds that
1- 2
HSIC (P) F
inf sup IP F. PEP
vn
with (i) the constant c= constant in the second case.
> 0 (depending ry and d only) in the first case, or (ii) some
2 2
We note that while Theorem Tii applies to the more general class of translation-invariint kernels, we include Theorem ii) makes the constant explicit.
The following corollary allows to recover the recent lower bound on the estimation of the covariance operator by Zhou et al. 22199 Theorem 5] as special case that we detail in Remark[Te)..
Corollary 1 (Lower bound on cross cross-covariance operator estimation). In the setting of Theorem T ii). let F,, denote any estimator of the centered cross-covariance operator Cx E Hr defined in (2 with n =: ng i..dd samples from P E P. Then, for any ng, holds that
1
[ ffllx-Fullnn
inf sup Ipn F. PEP
for some constant e > 0. Remark 1.
(a) Validness of HSIC. Though generally the characteristic property of (km
(km)) M is not enough
Szabó and Sriperumbudur 2018 Example for M 2 ensure the I-charucteristic property of k 8. - (in other words, that (S) = 0 iff. P = @M IF on Hd under the imposed continuous bounded translation-invariant assumption (i) being characteristic, (ii) being I-characteristic, and (iii) (km, ) being characteristic are equivalent (Theorem B. B.4).
(b) Minimax optimality of existing HSIC estimators. The lower bounds in Theorem Dasympottlayyy match the known upper bounds of the U-statistic and V-statistic-bass estimators of &n. n 1/2
*We note that for many translation innaaaiiionnn kernels, the corresponding spectral measures are known rumbudur al. 2010 Table 2].
Sripe
5

---

that of The Nyström- based HSIC estimator achieves the same rate under an appropriate decay of the eigenspectrum of the respective covariance operator. Hence, Theorem iimpless the optimality of these estimators on Rd 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 lower bound for the related MMD & exists. However, the adversarial distribution pair (1 Fo,) constructed by Tolstikhin et al. (2016 Theorem 1] to obtain the lower bound on MMD estimation has product structure which implies that |HSCC& (F&,
HSIC (P eg and hence not Theorem 2] with radial kernels has the
applicable in our case of HSIC: Tolstikhin et al. 2016 same restriction.
(d) Difference compared to Tolstikhin et al. [2017] (minimax mean embedding estimation). The estimation of the mean embedding (PP known to have a minimax rate of O (n -1/)). But, this rate does not imply an optimal lower bound for the estimation of MMD as is evident from the
Two works [Tolstikhin al.
2016
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
1 (bx(z) - uo (P)) & (dx(x) - (P)) E Ha 8 Hk.
Cxx
Zhou et al. 2019 Theorem 5] give the lower bound
f|Icxx Fn
inf sup pr F. PEP
1/8
in the same setting in Theorem ii), where F., is any estimator of the centered covariance Cxx, and is a positive constant. By noting that the centered covariance the centered cross-covariance of random variable with itself. Corollary recovers their result.
The next section contains our proofs.
4 Proofs
This section is dedicated our proofs. We present the proof of Lemma 1 in Section 4.1 Theorem [ in Section 4.2 and that of Corollary in Section 4.3
4.1 Proof of Lemmal
As
(P) MMD Q -Iax(B)-H((Q))
(PP) + (Mu(Q)) MN (M)) (2))
(P), p4: (1))
with Q PM N(m, bdiag( E ........ M.M))). Pm N(mm Em,m) it is suf-
ficient to be able to compute (ux (IP), ( (1),, -type quantities with IP = N(m , En) and N(m,, Σz). One can show MMuandet et al. 2011 Table 1] that (px(P), uu (Q)
(on mn ( 121 (ma mg)
Using this fact and that m = m, = my, the result follows.
4.2 Proof of Theorem i
The setup and the upper bound KL(PM, |[P% agree for (i) and (ii) but the methods that we use to lower bound (S&.,, ) HSIC& s, 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 Cam's 's method, which state as Theorem B.5 for self-completeness.

---

To construct the adversarial pair. we consider a class G of Gaussian distributions over R such that every element N (p, 2) G, with
0
07
= E(ij.p)
0
p
0
E IRddd
(5)
and (fixed) i d1, dj 11+1,pe (-1.1). In other words, essentially the d-dimensional matrix La except for the (i.j) and (i.t) entry; both entries are identical to p. and they specify the correlation of the respective coordinates. This family of distributions is indexed by a tuple ().p) E IR& x (-1,1) =: A and, for E A, we write Pa for the associated distribution. To bring ourselves into the setting of Theorem B.5 we fix n E No0. choose X' (IR)) set θ {0. := HFIC,(P.)
A}. Pe [PP A} {IT 0g E )), and use the metric (x, y) + x- for z, y E R. Hence, the data D P. Pe. For brevity, let F
E stand for + HSIC
and Fn stand for the corresponding estimator based on n samples.
As G C P, it holds for every positive that
sup Pd FEP
[HSIC& (P) -Fr 25)
sup Pa FEG
HSSCI (P) - F 20]
Let Po, N (mo, Eo) and Pe. N (mI En) with
= 0g E Rdd
Eg = E(d,, + 1,0) ((4,,4+1,0)
= Raadd
1 μ1 Vdn
Rd.
Σ, E(d,, d1 + P.) Raxd
where E (-1,1) will be chosen appropriately later We now proceed to upper bound
KL. (Pb. (PP;,) and lower bound [F(O)) - -(()))
Upper bound for KL divergence Lemma A.1 implies that with p n one has the bound
KL (Pg [PP))
a 5 for =: no-
Lower bound (i): Gaussian kernels. Recall that the considered kernel is k(x,y) = e- -
(y > 0). The idea of the proof is as follows.
1. We express [F(0)) F F(6)] in closed form function of 7, Pa. 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(O1) F(Oo)]: Using the fact that HSIC (Po,) = O. we have that
F (01) - F (00) F2 (0,) = HSTC (Po,) MMD (W (M, E (mn, Ia))
llme (N (mi1 Ex)) - pa (N (M1, La)
(un (N (Mi1, E1) : ur (N (MI, E Ei)) + (ux (N (wi, Ia)) pm (N (Mi, (a)))))))
(88)
-2 (pu (N (pi, Ei)) Ma (N (pe, Ia)))
(11))
'Nticee the dependence of 1o,

---

which we compute term-by cemm-by-trm with Lemma 1 and obtain
1/| (27 + 1)a-2 (2) + -(2pp))))
(1) | 1 Ia]
(ii) = 12 Lal
1//2 [27 + =1)9
1/2
1/2
(dit) = h + IIa La|
1/2 (2 + 10)+11a²2 (27 1)² 10111))--(0000 -(xpm)))
( -1/2
Combining (i), (ii), and (iii) yields that
HSTC (Po,) = (i) + (ii) 2(ti))
-[12 + +1)a (22 + -122p()ppn) (2210)))]]]
+ [[27 + 1)0]] 1/2
-1/2
2 (27 +1)a² (127 + 1)² - -(1pm) {>}
1)²
Lower bound [F(01) - F(00)]: Next, we show that there exists Nso it holds that HSIC (Fo,) 2 f.
0 such that for any
For <<<<<<<< (1
) let us consider the function
fc(x) = (27 + +1)d-2 + 1)² 47)2 1/2
+ (27 [2x + 1)9 -1/2
- 2 (27 + 1)0-2 (22 + 1)² --²x)
- cx
= 2 (x² 47]x]] - 1/2 + (241 1/2
11/3 -2 12ah (z² (2)]] 1/2 cr,
with the shorthand 2 = 2 + +10
With this notation, fc(1/n) = HSIC (To,) - c/n; our aim is
to determine > 0 such that fc(T/ /n) 2 for any positive integer n. To achieve this goal, notice that fc(0) 0, and
2-2
222-2
fz) = 12 2 (22 - 2)
12d (22 - 2//2)
21-2
2220-2
222d-2
-c 2 (22 - 2//2)
1rd (22 - 2)//2
1rd (22 - 2272)///2
22
72
7.2
22 3/2
==
2² 2d
(2 + 1)2 / /22 + 1)a
Choosing now (27+1)2 (2++1) O. we have f((x) 0. f is a nondecreasing function.
and Note that fe(1/n) HSICK (Po,)) - c/n 2 0, with x and (1+ # -2
< <15 n < 00.
By taking the positive square root, this means that
7
HSIC (Po,) 2
2s
(2 1) (22 (12+ 1)9)+ 1/4
vn
holds for n 2 1, implying that [F(0;) F(1b)) 2 28 > 0.
We conclude the proof by Theorem B.5 using that 5
3/2 and max
c
'Notice that (2> + - (2 + - - and + 0 (1 2)²² for
positive hence the imposed assumption x ensures that the function fe is well-defined.
8

---

Lower bound (ii): translation-invariant kernels. Let Aş denote the spectral measure associated the kernel l according that
T Using the fact that HSIC; (Fn,) we have for [F(0,) F()))
F (01) F (0o) / = -F² HSICH (Pa.) MMD (N (#i, 1i,,,,,,. ,N (M1, En))
(INN En} - WNTH En> L L²
(4))
(w ((uu e (( - (w. )oww 2
ddx(w)
Rd
J Rd
c Siw) w - c - dds(ww
?
(1i8)
- - Ewws 2 c Hw (ww
(āv) ddu(ww) Pr [M] d)x(w)
(
(2c)2
n
(2c))
[2,)3>>0
where (i) holds by (Sriperumbudur et al. 2010 Corollary 4()) (recalled in Theorem B.2).
(ii)
follows from the analytical form di x) (t) = e( (t. of the characteristic function of
multivariate normal distribution M(, E). For (iii). we define the non-empty open set
A= {w (wi..... wa) R² wa, wa < 0} R,
and use that the integration of a non-negative function over subset yields a lower bound. In (io). fix E A and let
hw p E [0, 1] + - - (e +1,p)w) (0,
Note that (w) = e [W 2 wes 1 1); lw is continuous on [0. 1] and differentiable on (0, 1).
Hence for any p E (0, 1), by the mean value theorem, there exists E (0, 1) such that
hp) (0) pP) 2 min 1/ (c).
eE
We have the first and second derivatives
(c) = wa we [ww w 2ewa, (c) wi, wā, +1 - [wwT way+1) >>> 0,
which implies that h' (c) is strictly increasing function of and that it attains its minimum at e = 0, that is,
(p) - (0) 2 ph > 0,
where the 2nd inequality holds by > and w E A. This shows that
(p) how (0)) 2 (0)]
and the monotonicity of integration gives (iv). For (v). we note that the kernel A
@ m= km
characteristic (Szabó and Sriperumbudur, 2018 Theorem 4] (recalled Theorem B.4 as the ( )M characteristic. Thus, supp (Ag) = Rd (see Sriperumbudur al. 2210 Theorem 9];
recalled in Theorem B.3). implying that A₃ (AA) > 0. (v) follows from the positivity K (0) (for
any A), from the fact that the integral of positive function set with positive measure is positive, and from our choice of Pn. n 1/2
Now, by taking the positive square root, have
2c
F (01) - F(o))
2s.
(11)
Vn
We conclude by the application of Theorem B.5 using that a = and max
1
1-v3
1-
4
2

---

4.3 Proof of Corollary
We use the same argument as the beginning of the proof of Theorem I in Section 4.2 adjust the setting in which we apply Theorem B.5 Specifically, we now let Q ( = Cx. Xg ~ P.. E A} with Cx defined as in (2) be the set of covariance operators, use the metric (x, v) + || yll
for y E HA. and keep the remaining part of the setup the same. Hence, it remains to lower bound [Cxx, Cxe, Pd.
By using that HSIC is the RKHS norm of the cross-covariance operator, we
obtain that
(i) = =F(()) F(0o) 2 2s vn
2c
Cxx,, - Cxa, ll
||xxo 11 1p2e
||C 1,ze
Ale
(Po,)=((Po))
-HSIC& (Pog)
where (i) holds by the reverse triangle inequality, is defined as Section 4.2 and (ii) is guaranteed by (1I for e <> 0. We conclude as in the proof of Theorem Tii) to obtain the stated result.
Acknowledgments and Disclosure of Funding
This work was supported by the German Research Foundation (DFG) Research Training Group GRK 2153: Energy Status Data Informatics Methods for its Collection, Analysis and Exploitation, and by the pilot program Core-Informatics of the Helmholtz Association (HGF).
References
Mélisande Albert, Béatrice Laurent, Amandine Marrel, and Anouar Meynaoui. Adaptive test of independence based on HSIC measures. The Annals of Statisties, 50(2):858-877 2022.
Andrés Anaya-Isaza and Leonel Mera-Jiménez. Data augmentation and transfer learning for brain tumor detection in magnetic resonance imaging. IEEE Access, 10:23217-23233, 2022.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68:337-404 1950.
Alain Berlinet and Christine Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Kluwer, 2004.
Martin Bilodeau and Aurélien Guetsop Nangue. Tests of mutual or serial independence of random vectors with applications. Journal of Machine Learning Research, 18:1-40, 2017.
Dimitri Bouche, Rémi Flamary, Florence d' Alché Buc, Riwal Plougonven, Marianne Clausel, Jordi Badosa, and Philippe Drobinski. Wind power predictions from nowcasts 4-hour forecasts: learning approach with variable selection. Renewable Energy, 211 :938-997, 2023.
Gustavo Camps-Valls, Joris M. Mooij, and Bernhard Schölkopf. Remote sensing feature selection by kernel dependence measures. IEEE Geoscience and Remote Sensing Letters, 7(3):587-591, 2010.
Claudio Carmeli, Ernesto De Vito, Alessandro Toigo, and Veronica Umanitá. Vector valued repro- ducing kernel Hilbert spaces and universality. Analysis and Applications, 8:19-61, 2010.
Shubhadeep Chakraborty and Xianyang Zhang. Distance metrics for measuring joint dependence with application to causal inference. Journal of the American Statistical Association, 114(528): (638-1650, 2019.
Héctor Climente-Gonzáleez Chloé-Agathe Azencott, Samuel Kaski, and Makoto Yamada. Block HSIC Lasso: model-free biomarker detection for ultra-high dimensional data. Bioinformatics, 35
(14):4427-i435, 2019.
Donald L. Cohn. Measure Theory. BirkhäuserrSpringee,, second edition, 2013.
Joseph Diestel and John Jerry Uhl. Vector Measures. American Mathematical Society, Providence, 1977.
10

---

John Duchi. Derivations for linear algebra and optimization. Berkeley, California, (00)2235--5770 2007.
Alex Fedorov, Eloy Geenjaar, Lei Wu, Tristan Sylvain, Thomas P DeRamus, Margaux Luck, Maria Misiura, Girish Mittapalle, R Devon Hjelm, Sergey M Plis, et al. Self-supervised multimodal learning for group inferences from MRI data: Discovering disorderr-elevant brain regions and multimodal links. Neurolmage, 285:120485, 2024.
Noé Fellmann, Christophette Blanchet-Scallle Céline Helbert, Adrien Spagnol, and Delphine Sinoquet. Kernel-basee sensitivity analysis for (excursion) sets. Technometrics, 2024.
Michael Freitas Gustavo, Matti Hellström, and Toon Verstraelen. Sensitivity analysis for ReaxFF reparametrizationn using the Hilbert-Schhidt independence criterion. Journal of Chemical Theory and Computation, 19(9:2557-2573, 2023.
Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf. Kernel measures of conditional dependence. In Advances in Neural Information Processing Systems (NIPS), pages 498-496, 2008.
Tomasz Górecki, Miroslaw Krzyško, and Waldemar Wolyúski. Independence test and canonical correlation analysis based on the alignment between kernel matrices for multivariate functional data. Artificial Intelligence Review, pages 1-25, 2018.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with Hilbert- Schmidt norms. In Algorithmic Learning Theory (ALT), pages 63-78. 2005.
Arthur Gretton, Kenji Fukumizu, Choon Hui Teo, Le Song, Bernhard Schölkopf, and Alexander Smola. A kernel statistical test of independence. In Advances in Neural Information Processing Systems (NIPS), pages 585-592, 2008
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-773, 2012.
Salvador Herrando- and Frédérik Saltré. Estimating extinction time using radiocarbon dates.
Quaternary Geochronology. 79:101489, 2024.
Florian Kalinke and Zoltán Szabó. Nyström M-Hilbert-Schmidt independence criterion. In Confer- ence on Uncertainty in Artificial Intelligence (UAI), pages 1005-1015, 2023.
Lucien Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, 1:38-53, 1973.
Russell Lyons. Distance covariance in metric spaces. The Annals of Probability, 41:3284-3305. 2013.
Charles Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine
Learning Research, 7:2651-2667 2006.
Joris Mooij. Jonas Peters, Dominik Janzing. Jakob Zscheischler, and Bernhard Schölkopf. Distin- guishing cause from effect using observational data: Methods and benchmarks. Journal of Machine Learning Research, 17:1-102, 2016.
Krikamol Muandet, Kenji Fukumizu, Francesco Dinuzzo, and Bernhard Schölkopf. Learning from distributions via support measure machines. In Advances in Neural Information Processing Systems (NIPS), pages 10-18, 2011.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29:429 1997.
Niklas Pfister, Peter Bühlmann, Bernhard Schölkopf, and Jonas Peters. Kernel-based tests for joint independence. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(1): 5-31, 2018

---

Aleksandr Podkopaev. Patrick Blöbaum, Shiva Kasiviswanathan, and Aaditya Ramdas. Sequential kerneiized independence testing. In International Conference Machine Learning (ICML), pages 27957-27993, 2023.
Novi Quadrianto, Le Song, and Alex Smola. Kemelized sorting. In Advances in Neural Information Processing Systems (NIPS), pages 1289-1296, 2009.
Saburou Saitoh and Yoshihiro Sawano. Theory of Reproducing Kernels and Applications. Springer Singapore, 2016.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5):612-634, 2021.
Dino Sejdinovic, Arthur Gretton, and Wicher Bergsma. A kernel test for three-variable interactions. In Advances in Neural Information Processing Systems (NIPS), pages 1124-1132, 2013a.
Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-based and RKHS-based statistics in hypothesis testing. Annals of Statistics, 41:2263-2291, 2013b.
Shubhanshu Shekhar, Ilmun Kim, and Aaditya Ramdas. A permutation-fiee kernel independence test. Journal of Machine Learning Research, 24(369):1-68, 2023.
Tianhong Sheng and Bharath K. Sriperumbudur. On distance and kernel measures conditional independence. Journal of Machine Learning Research, 24(7):1-16, 2023.
Alexander Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A Hilbert space embedding for distributions. In Algorithmic Learning Theory (ALT), pages 13-31, 2007.
Le Song, Alexander J. Smola, Arthur Gretton, and Karsten M. Borgwardt. dependence maximiza- tion view of clustering. In International Conference on Machine Learning (ICML), pages 815-822, 2007.
Le Song, Alex Smola, Arthur Gretton, Justin Bedo, and Karsten Borgwardt, Feature selection via dependence maximization. Journal of Machine Learning Research, 13(1):1393-1444, 2012.
Bharath Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert Lanckriet. Hilbert space embeddings and metrics on probability measures. Journal of Machine Learning Research, 11:1517-1561, 2010.
Bharath Sriperumbudur, Kenji Fukumizu, and Gert Lanckriet. Universality, characteristic kernels and RKHS embedding measures. Journal of Machine Learning Research, 12:2389-2410, 2011.
Ingo Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research, 6(3):67-93, 2001.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer, 2008
Jerome Stenger, Fabrice Gamboa, Merlin Keller, and Bertrand Iooss. Optimal uncertainty quantifica- tion of a risk measurement from a thermal-hydraulic code using canonical moments. International Journal for Uncertainty Quantification, 10(1), 2020.
Zoltán Szabó and Bharath K. Sriperumbudur. Characteristic and universal tensor product kernels. Journal of Machine Learning Research, 18(233):1-29 2018.
Gábor J. Székely and Maria L. Rizzo. Brownian distance covariance. The Annals of Applied Statistics, 3:1236-1265, 2009.
Gábor Székely, Maria L.. Rizzo, and Nail K. Bakirov. Measuring and testing dependence by correlation of distances. The Annals of Statistics, 35:2769-2793 27994, 2007.
Ilya Tolstikhin, Bharath Sriperumbudur, and Bernhard Schölkopf. Minimax estimation of maximal mean discrepancy with radial kernels. In Advances in Neural Information Processing Systems (NIPS), pages 1930-1938, 2016.
12

---

Ilya Tolstikhin, Bharath Sriperumbudur, and Krikamol Muandet. Minimax estimation of kernel mean
embeddings. Journal of Machine Learning Research, 18:1-47, 2017.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009.
Sebastien De Veiga. Global sensitivity analysis with dependence measures. Journal of Statistical Computation and Simulation, 85(7):1283-1305, 2015.
Andi Wang, Juan Du, Xi Zhang, and Jianjun Shi. Ranking features promote diversity; An approach based on sparse distance correlation. Technometrics, 64(3):384-395, 2022.
Leila Wehbe and Aaditya Ramdas. Nonparametric independence testing for small sample sizes, In International Joint Conference on Artificial Intelligence (IJCAI), pages 3777-3783, 2015.
Holger Wendland. Scattered data approximation. Cambridge University Press, 2005,
Makoto Yamada, Wittawat Jitkrittum, Leonid Sigal, Eric P. Xing, and Masashi Sugiyama. High- dimensional feature selection by feature-wise kernelized Lasso. Neural Computation, 26(1): 185-207, 2014.
Yang Zhou, Di-Rong Chen, and Wei Huang. A class optimal estimators for the covariance operator in reproducing kernel Hilbert spaces. Journal Multivariate Analysis, 169: 12211666-78 2019.
V. Zolotarev. Probability metries. Theory of Probability and its Applications, 28:278-333 -02,, 1983.
13

---

A Auxiliary Result
In this section, we collect auxiliary result. Lemma A. presents an upper bound on the Kullback- Leibler divergence between multivariate normal distributions.
Lemma A.1 (Upper bound on KL divergence). Let d = Em= dm with dm E N>0 (m E [M]). Fix i E [d1]. Let j = i 1, Ps. = (O,,, Id), and Po. = N E1). with μl = - ld E R and Σ [i. Pn)) E IRddd defined as in (5) (pn E (0, 1)). Then, for 2 I n E E,
vdn
1
n Pr
KL(P%, IIP -
+
2n
2 1
P
In particular, for Ph. 1/n, it holds that (L, 8,
4'
Proof. With μ4 = O₂ and En = Ia. we obtain that KL(Pe, |1P2,)
KL |Poo))
sE[n]
(b)
tr Eg Σn) + (f4 mn) = " 11) - -d+n
|
n
tr(2n)
d +
In
2
Σ
1-
12
(
1
71
2
5
In
2n
2
2n
2
1
P
where (a) is implied by Lemma[..] (b) follows from Lemma the determinant, (d) is the consequence of the inequality In(x) holds for n 2 2 and P 1/n as
B
(c) follows from the definition of
S x 1 holding for x > 0, and (e)
n 1/n
n 1
1
<1
n 2(n 11 = n 2 2,
1/n
2n
n-
and in this case (for 2 2) one has that 1 5
B External Theorems
For self-completenesss we include the external statements that we use. The well-known result by Bochner, stated in Theorem B.I. completely characterizes continuous bounded ionslation-invarian kernels. Theorem B.2 allows expressing MMD with continuous bounded translation cunslationinvarriat kernels in terms of characteristic functions, and Theorem B.3 gives an equivalent condition for a continuous bounded translation-invariint kernel to characteristic. Theorem B.4 connects characteristic kernels to characteristic product kernels and to Z-characteristic product kernels on IRd (we include only the part relevant to our paper for brevity). We recall Cam's method in Theorem B.5]and collect results on the Kullhack-Leible divergence in Lemma B.1 and Lemma B.2
Theorem B.1 (Bochner: Theorem 6.6; Wendland 2005)). continuous function & : Rdd - R is positive definite if and only if it is the Fourier transform of a finite nonnegative Borel measure A on Rd that is,
x(x) = 1 e((xxw)) dA(w). for all E Rdd.
nd
Theorem B.2 (Corollary 4()x Sriperumbudur et al. bounded translation-
2010 Let k: Rdd x IRd R. be continuous
cranslation-imvriiant invariant kernel. Then, for any
P,Q E Mi (R.).
MMD ||ا - wall
with the and the being the characteristic funccitoo of P and Q respectively, and As defined in
14

---

Theorem B.3 (Theorem 9: Sriperumbudur et al. (0100). Suppose k. R x R - R is a continuous bounded translation-ivvariant kemel. Then & characteristic if and only (usp((At) RR, with Ag defined as in ①T.
Theorem B.4 (Theorem 4; Szabó and Sriperumbudur [01 Suppose km RRmm x RR + IR is
continuous bounded and translatin-invvaiinn kernel Jor all [M]. Then the following statements are equivalent:
(i) (km) m- characteristic:
(ii) @ M km is characteristic;
(ii) 8 &M kim is I-characteristic.
The next statement follows directly from Tsybakov 2009 Eq. (2.9)] and Tsybakov 2009 Theo- rem 2.2].
Theorem B,5 (Theorem 2.2: Tsybakov 2009 ). Let X be a measurable space, (9, d) a semi-metric
space, and Pe (Po 0 E 3 is class of probability measures X indexed by 6. We observe
data ~ Po E Pe with some unknown parameter The goal is to estimate 0. Let 0 ((D) be an estimator of 0 based on D. Assume that there exist Oo 01 E a such that d(0a, 01) 2 28 > 0 and Then
KL,(Po, (|Po,) S a < 00 for a >
inf sup Fo (d (d(0,) 26) max
a
V a/2
BEe
4
2
We have the following property of the Kullback-Leibler divergence for product measures 2009 85].
Tsybakov
Lemma B.1 (KL divergence product measures). Let P and 1 Then
KL(PI|Q)
Σ (L(P.IIQ.).
iE(m)
The following lemma [Duchi 2007 p. 13] shows that Kullback-Leible divergence of multivariate Gaussians be computed in closed form.
Lemma B.2 (KL divergence of Gaussians). The KL divergence of two normal distributions N(p, E,) and (N Eg) on I2 is
tr(E) " + (14 - 2
14)
Σn Σ1
KL(N(HI, E.)lI En)) Ex),
15

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
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 contribu- tions 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 results can be expected generalize to other settings.
It is fine include aspirational goals as motivation as long clear that these goals are not attained by the paper.
2. Limitations
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 results. Remark T 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 create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations 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 few datasets or with 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 the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 review- ers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged 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.
16

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide explicit proof' 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 the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: 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 reprodueible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending 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 specific model and empirical evaluation, 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 good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of 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 the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution primarily a new model architecture, the paper should describe architecture clearly and fully.
If the contribution is new model (c.g., large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-soure, dataset or instructions for how to construct the dataset).
17

---

(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 should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access 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, 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
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g.. for new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines (https 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,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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 much information as possible in supplemental material (appended to the paper) is recommended, including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type 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 presented in the core of the paper to level of detail that necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

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 (c.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 I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. 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 experi- mental 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 into the paper).
Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethies http://///errrrr..a////a/////aaa
Answer: [Yes]
Justification: The research presented in this work conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due laws or regulations in their jurisdiction).
10. Broader Impacts
19

---

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 societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment 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 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 point out that 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 fuucciioning conrectly, 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. 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 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 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.
20

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com/ /annattastts has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoddl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
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.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should paid least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals
Question:
21

---

(or equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing 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 NeurlPS 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.
22


Reviews:
[{"review_id": "15MiIf8fNx", "reviewer": "Reviewer_6YpR", "summary": "The rate at which HSIC can be estimated is an important and open problem, in this paper, the authors prove that\nthe 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\ncross-covariance operator, which can be further specialized to get back the minimax result on the estimation of the covariance operator.", "questions": "NA", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper answers an important while open problem which may be very important for the community and generalizes the existing result from M=2 to M>=2. \n2. The paper's structure is clear and well organized.\n3. The paper is solid and mathematically heavy, the proof is provided with details.", "weaknesses": "1. Overall, the paper is not easy to follow as the paper's main contribution seems to be the proof part. \n2. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort invested, and for the kind review. \n\nTo answer the question regarding experiments: In the minimax framework, one bounds the convergence rate from above and from below. \n- The former can be validated empirically in some cases. Indeed, for HSIC, one can compute the theoretical (= population) HSIC value for a fixed (kernel, distribution)-pair---for instance, for the Gaussian kernel with the Gaussian distribution (Lemma 1)---, and verify the known (Smola et al., 2007; Theorem 2) convergence rate of the estimator w.r.t. this value.\n- The latter, that is, the lower bound, can only be derived theoretically---as one must consider all possible estimators ($\\inf_{\\hat{F_n}}$ in (3)) and all possible probability distributions ($\\sup_{P\\in\\mathcal{P}}$ in (3)) of the considered class ($\\mathcal{P}$)---which is what we tackled in this article.\n\nMinor note regarding the point 'existing conclusion only holds for $M=2$': We are not aware of minimax guarantees for HSIC even for $M=2$; our minimax analysis handles both the case of $M=2$ and $M>2$ in a unified fashion (for $M \\ge 2$).\n\nWe hope that this settles the stated questions.\n\n__References.__\n\nSmola, A., Gretton, A., Song, L., & Schölkopf, B. (2007). A Hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory (pp. 13-31).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gghiXQrPrJ", "reviewer": "Reviewer_tUTX", "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}$.", "questions": "There are some minor issues. \n\nCan the author provide a more concrete definition of HSIC? For example, in equation (2), does it imply that we have fixed a decomposition \n$d=d_{1}+...+d_{M}$ and $P_{m}$  is the marginal distribution of P on $R^{d_{m}}$.?\n​", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Testing whether a pair of random variables are independent is the central problem in statistics or machine learning community.  There are lots of independence tests proposed in past years such as distance correlation, dynamic slicing, etc. \n\nThe author established the minimax lower bound \\( \\Omega(n^{-1/2}) \\) of HSIC estimation with \\( M \\geq 2 \\) components on \\( \\mathbb{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, their result settles their minimax optimality.\n\nEstablishing minimax rates is often deemed a challenging task. Given that the result sounds solid, I consider this a noteworthy result.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort invested, and the kind review.\n\nIn the following, we answer the questions.\n\n- __Related work.__ The related work can be divided into lower bounding the rate of estimating (1) the kernel mean embedding, (2) maximum mean discrepancy, and (3) the covariance operator. The existing results do not permit establishing the minimax rate of HSIC estimation due to the following reasons.\n1.  The estimation of the mean embedding (1) concerns the estimation of an element in an RKHS, which could be more difficult than the estimation of a real-valued function of it (MMD; Tolstikhin et al., 2016, or, in our case, HSIC). \n2. The proof for obtaining the lower bound of (2) relies on a distribution pair in which both distributions factorize, that is, they are independent. The corresponding HSIC value is thus zero and Le Cam's method is not applicable; hence the existing proof does not address the setting of HSIC.\n3. In the case of (3), one intuitively expects that estimating the real-valued HSIC is \"easier\" than estimating the covariance operator, which is an element in a tensor product RKHS. Our result sheds light on a surprising phenomenon: this intuition is false. Moreover, with Corollary 1, we are able to recover the lower bound on covariance operator estimation.\n\nThese notes are also elaborated in Remark 1(c)--(e).\n\n- __Definition of HSIC.__ HSIC captures the dependencies of a probability measure by quantifying the discrepancy of the measure to the product of its marginals as the distance of the corresponding mean elements in an RKHS. This also corresponds to the norm of the cross-covariance operator, which (2) makes explicit; the equivalence holds for arbitrary kernel-enriched domains. In line with Line 121-122 and Theorem 1, and as correctly stated in the review, we consider $\\mathcal{X} = \\times_{m=1}^M \\mathcal{X_m}$ with $\\mathcal{X}=\\mathbb{R}^d$ (for the domain of $\\mathbb{P}$), $\\mathcal{X}_m=\\mathbb{R}^{d_m}$, i.e. one has the decomposition $d=d_1 + \\cdots + d_M$, with $\\mathbb P_m$-s being the corresponding marginals of $\\mathbb{P}$ on $\\mathbb R^{d_m}$ ($m=1,\\ldots,M$). The associated kernels are $k_m:\\mathbb R^{d_m} \\times \\mathbb R^{d_m} \\to \\mathbb{R}$.\n\nWe hope that this answer clarifies all the questions of the reviewer.\n\n__References.__\n\nTolstikhin, Ilya O., Bharath K. Sriperumbudur, and Bernhard Schölkopf. \"Minimax estimation of maximum mean discrepancy with radial kernels.\" Advances in Neural Information Processing Systems 29 (2016).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QCE7Olc309", "reviewer": "Reviewer_g9Na", "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.", "questions": "See weakness", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper provides the first minimax optimal rate for HSIC learing, via obtaining the information theoretical lower bound. This is an important contribution the litearture since HSIC is widely used for independence test.\n\nA minor contribution is that the authors derive the closed form formula of HSIC under the Gaussian setting.\n\nIn proving the lower bound for the translation invariant kernel case, the authors restrict the integration of to be computed in a subset of $\\mathbb{R}^d$, thereby obtaining a lower bound on the HSIC between $P_{\\theta_1}$ and $P_{\\theta_0}$. To me this is novel.", "weaknesses": "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.\n\nIt 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort invested, and the kind review.\n\nBelow we answer the questions in detail.\n\n- __Technical challenge.__ There are three main tools for deriving lower bounds in the minimax setting: Le Cam's method, Fano's method, and Assouad's lemma. The main technical challenge in applying these known tools is coming up with an adversarial distribution pair and then also showing that the assumptions of the respective statements are all satisfied. In our case, we chose Le Cam's method and showed that its assumptions are satisfied for the parameterized Gaussian distribution (5) and its instantiations in Line 239 in the case of HSIC.\n- __Difference to (Zhou et al., 2019).__ Indeed, the rate obtained by (Zhou et al., 2019) for the covariance operator is the same as the one that we obtained for HSIC. Intuitively, one would guess that estimating the covariance operator, an element in a tensor product RKHS, is more challenging than estimating HSIC, a real number. Surprisingly, this is not the case, as our results indicate. Moreover, by an application of the reverse triangle inequality, our result allows to recover their result (see Corollary 1 and its proof). Regarding differences in the proof: The distribution pair considered by (Zhou et al., 2019) has a product structure, which, similar to (Tolstikhin et al., 2016), does not allow to obtain a lower bound for HSIC estimation.\n\nWe hope that this answers all the questions of the reviewer.\n\n__References.__\n\nTolstikhin, I. O., Sriperumbudur, B. K., & Schölkopf, B. (2016). Minimax estimation of maximum mean discrepancy with radial kernels. Advances in Neural Information Processing Systems, 29.\n\nZhou, Y., Chen, D. R., & Huang, W. (2019). A class of optimal estimators for the covariance operator in reproducing kernel Hilbert spaces. Journal of Multivariate Analysis, 169, 166-178.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents 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.
Decision: Accept (poster)