Efficiently Learning Significant Fourier Feature Pairs for Statistical Independence Testing
Authors: Yixin Ren
Yewei Xia
Hao Zhang
Jihong Guan
Shuigeng Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: independence test
learnable Fourier feature
Primary area: causal_inference
TL;DR: A novel framework for statistical independence tests that enable effective learning significant Fourier feature pairs to maximize test power

Abstract: We propose a novel method to efficiently learn significant Fourier feature pairs for maximizing the power of Hilbert-Schmidt Independence Criterion~(HSIC) based independence tests. We first reinterpret HSIC in the frequency domain, which reveals its limited discriminative power due to the inability to adapt to specific frequency-domain features under the current inflexible configuration. To remedy this shortcoming, we introduce a module of learnable Fourier features, thereby developing a new criterion. We then derive a finite sample estimate of the test power by modeling the behavior of the criterion, thus formulating an optimization objective for significant Fourier feature pairs learning. We show that this optimization objective can be computed in linear time (with respect to the sample size $n$), which ensures fast independence tests. We also prove the convergence property of the optimization objective and establish the consistency of the independence tests. Extensive empirical evaluation on both synthetic and real datasets validates our method's superiority in effectiveness and efficiency, particularly in handling high-dimensional data and dealing with large-scale scenarios.

Efficiently Learning Significant Fourier Feature Pairs for Statistical Independence Testing
Yixin Ren', Yewei Xia 1.4,
Hao Zhang Jihong Guan 2.a, Shuigeng Zhou !.
Shanghai Key Lab of Intelligent Information Processing, and School of Computer Science, Fudan University, Shanghai, China Department of Computer Science and Technology, Tongji University, Shanghai, China SSAA,, Chinese Academy of Sciences, Shenzhen, China *Machine Learning Department, MBZUAI, Abu Dhabi, UAE (yxren21, ywxia23) @m. fudan. edu. cn, h. 2hang10@siat ac. jhguan@tongji edu. cn, sgzhou@fudan edu, en
Abstract
We propose novel method efficiently learn significant Fourier feature pairs for maximizing the power of Hilbert- Schhiidt Independence Criterion (HSIC) based independence tests. We first reinterpret HSIC the frequency domain, which reveals its limited discriminative power due to the inability to adapt to specific frequency-doman features under the current inflexible configuration. To remedy this shortcoming, we introduce a module of learnable Fourier features, thereby developing new criterion. We then derive a finite sample estimate of the test power by modeling the behavior of the criterion, thus formulating an optimization objective for significant Fourier feature pairs learning. We show that this optimiza- tion objective can be computed in linear time (with respect to the sample size n)), which ensures fast independence tests. We also prove the convergence property of the optimization objective and establish the consistency of the independence tests. Extensive empirical evaluation on both synthetic and real datasets validates method's superiority in effectiveness and efficiency, particularly in handling high-dimensional data and dealing with large-scale scenarios.
Introduction
Testing for independence a crucial and challenging task in machine learning and statistics, with wide-range applications in causal inference [1]] 31], feature selection [6] and deep learning [23] 42). Its primary objective to determine whether two random variables, X and Y are independent, based on the observations of the underlying joint distribution Pxy. While traditional independence tests, such as Pearson's 's correlation coefficient [ and Kendall's 's т, can only detect monotonic relationships between low-diment www-immnssionl variables, more modern tests 26 4g 25 27 35 19] 20 aim to deal with complex non-linear interactions in much more challenging gigeer-dimensionll space
29
One class of nonlinear dependence measures kernel embeddings [13,, primarily derived from the cross-covariance operators the reproducing kernel Hilbert space (RKHS). Among them, Hilbert-Schmii Independence Criterion (HSIC) [14] the most popular one. utilizes the squared Elllbert-chhmin norm to detect dependence and exhibits outstanding performance across various data contexts by choosing suitable kernels. On the other hand, some other fundamental nonlinear dependence measures employ characteristic functions
aims to capture distributional characteristics using
Corresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to detect the smoothed discrepancy between the joint distribution and the product of marginals. By employing appropriate characteristic functions, the statistic [39 40 computes the covariance between distances of variable pairs. It has been demonstrated that these distance-based
methods are equivalent to HSIC with specific kernels [33]. However, all these measures suffer from the drawback of requiring quadratic time (w.r.t. the sample size n)) to compute the feature covariance and necessitating fixed kernel or distance functions, rendering them impractical on large-scale datasets due to the unaffordable time cost and lacking flexibility in handling complex scenarios.
To address these challenges, a multitude of works grounded on these measures have emerged. Upon HSIC, [44] proposes some linear-time tests including a block-averaged statistic, statistic with Nyström approximation. and one with lnite-dimensional feature mappings using random Fourier features (RFF) (28). For convenience, these tests are referred to as BHSIC, NyHSIC, and FHSIC, respectively. FHSIC and NyHSIC are observed to have considerable advantage over BHSIC. However, remaining drawback of these methods is that the features are not learnable. Therefore, these methods lack enough adaptability to complex settings, thus leading to performance degradation.
In addition to time efficiency, another research direction II 30] aims to make independence tests adaptive better capturing distributional distinctions. These methods either select/combine appro- priate kernels from a predefined set or learn parameterized kernels. Nonetheless, their criteria still inherit the quadratic time complexity of HSIC, thus cannot be readily applied to large-scale data.
Furthermore, some approaches T7 32 try to address both challenges simultancously. For instance, HSICAgg 32] suggests combining several kernels from a predefined set (e.g. kemnlls with different preset bandwidths) and aggregating the test results for improving performance. Additionally, an incomplete U-statistic of HSIC is proposed to ensure computational efficiency. Nevertheless, selecting from a predefined set of kernels imposes limitations on flexibility, and in cases where scaling optimization is required on each dimension, the number of kernel pairs escalates exponentially, Also, NFSIC [88 proposes to combine a time-efficient technique called analytic kernel embeddings (8] I7] and learn the important local distributional features. However, its learning objective is merely a lower bound of test power and demands a substantial number of samples to ensure accuracy.
In this paper, we propose novel test method that flexibly learns distributional features while maintaining high efficiency. We first reinterpret HSIC from a frequency-domain perspective, then point out its potential shortcomings with elaborate example and indicate corresponding improvement directions. Finally an central optimization objective is derived by directly modeling test power, which can be computed in linear time while maximizing the test performance. Comparing with [30] that also addresses the kernel learning problem in independence testing with a time/space complexity of Onn²), our criteria for learning are designed to have complexity of (n)) for both space and time. Consequently, the whole test framework can efficiently handle large-scale data.
We propose novel approach that efficiently learns significant Fourier feature pairs for maximizing the power of HSIC- based independence tests. 2) We design optimization objective that can be computed in linear time, which is derived by directly modeling test power. 3) We theoretically establish the non-asymptotic convergence property of the optimization objective and demonstrate the consistency of our method. 4) We conduct extensive experiments on both synthetic and real data, showcasing its superiority in effectiveness and efficiency in handling high-dimensional data (e.g. image data) and addressing large-scale scenarios.
Contributions. In summary, the contributions of the work as follows: 1)
Outline. The rest of the paper is organized as follows: Sec. reviews HSIC-based statistical independence tests. Sec.B] B reinterrpesss HSIC from a frequeney-domenn perspective, and explain its potential shortcomings with an elaborate example and indicate corresponding improvement directions. Sec. E designs an optimization objective by directly modeling test power, which can be computed in linear time. Sec. pressenss the theoretical analysis and Sec. @evalluates the performance of the proposed method on synthetic and real dataset. We conclude the paper in Sec. 7
2 Preliminaries and Notations
We begin by introducing notions and reviewing the hypothesis testing framework for independence tests. Let X x y be separable metric space, typically Rd= x RRd,, Pxx denotes a Borel probability measure defined on X' x Y, while IPx and Py denote the respective marginal distributions. Given

---

Uo Ve) independent and identically distributed (i.i.d) samples Z : (X, = = Fxy. we aim to test whether X, are independent (i.e., X 11 Y). This corresponds hypothesis testing problem formulated as Ho Pxy = PxPPy versus H1 Px o Pxy..
with distribution
The testing procedure is as follows: First, define the statistic p and caleulate its estimated value using the samples. Then, choose significance level a (typically set to 0.05), which represents the probability that the sampling of p under Hi least as extreme as the observed value. Finally, the null hypothesis Ho is rejected if the p-value is not greater than a.
Two types of errors may occur in this procedure. Type I error occurs when Ho is falsely rejected, while Type error happens when Hy is incorrect but not rejected. A good test [43] needs to control Type I error within while maximizing the testing power (1 (1-Type II error rate).
For independence tests, a commonly used statistic is HSIC, defined as follows:
Definition 1. (14). Let F be an RKHS with kernel k: X X R and G be second RKHS on y with kernel 1 : y x y + IR, the HSIC between X and Y, denoted as HSIC(X, Y) is defined as
E X'XX E[[, x E [[I - 2 [E (o)K(XXX))By((XX Ey,(Y, (1)
where XX,Y') is a independent copy of (X,Y) Y). An estimator of HSIC(X, Y) is given by
1
1
1 n² (KHHHH)
HSIC&(Z) n2
kigles + n
Rigler - 12 Σ
Reglig
where kig == k( Kz): ). Li := Uy Hj) are the entries of the n x n kernel matrices K, L respectively,
H " 111 is the centering matrix and is a vector of ones.
3 Revisiting HSIC from Frequency Domain Perspective
We denote F as the Fourier transform, and F-! its inverse. When the kernels k. I are translation- invariant, i.e., there exist functions ah, the, 8/ such that for all (x, x') E X x X and (y. s/) E y x V,
<0 x' y 3') vx 2' (ii(y - s/) = k(x, x My.. v').
(3)
Then, according to the results of [36, Corollary 4], the HSIC with function ib can be formulated as
Jr x 1 (w) - prx ( (w))dw,
HSIC(X,Y)
where w = (Wa, wyy E Rdd x Rdy, Wa are the frequencies of X and Y respectively, and
OFXY (w) = f e (WWTatTTo dP dPxY, P = (s (e-tuEnary dPx (
iu dPy
(5)
are the characteristic functions of Px and Px respectively. Intuitively, Eq, means that HSIC can be understood the difference between the joint distribution and the product of the marginal distributions in the frequency domain, with different weights (F-(w)(w) being attached to different frequencies, which are determined by the kernel function. When F is almost everywhere non- zero, it can be shown that the kernel is characteristic [36 [0]. The characteristic condition ensures that the criterion is discriminative for discrepancies at almost all frequencies. However, with inappropriate choices of 1-, the differences may not be significant enough. We explain this with an example:
Example. Consider the Sinusoid model that X' x y = |- 7/2 and (X, Y) ~ Pay( y) xx 1+ sin(waa) swoy), where Pay is the probability density function and wo is a positive integer. Combining Eq. (5). we can calculate that @p (w) ò(wr )o(s,) and de (w) 6(w=))((w))) 18(wi, + wo) + (ww wo (o)], + wo) + ō(w, - wo)]. where is the Dirac delta function, thus the difference between them only relies on the frequency wp- When the Gaussian kernels with width 22x, and V2X, are used, i.e., k(æ, x²) = exp(-Ile
x' (18/(422), 1V, v') = exp( poo--lly- of 1/11/// (1/(()))), then the inverse Fourier transform of v is (F ()) myy = क - dody exp( - (1 + 1) 4n - exp(-(23 + X3 1)) whose maximum is taken at X; X //(v2unp indicating that the widths need to be adjusted to focus on some specific frequencies. If the common setting [14 44] is adapted, which uses mid-width (i.c., the median distance does
Hence HSIC(X,
3

---

not change with wi since the marginal distributions do not change with wo), then the criterion will exponentially decline to 0 as wh increases. In contrast, the criterion using the adaptive optimization width (1/wo, 1/wo) decreases at rate of (ww))) which is a considerable improvement.
This example illustrates the loss of the discriminatory power of the criterion when an inappropriate F is chosen. The discriminatory power of the criterion heavily impacts the sample size required for the test to obtain significant results in practice, and existing inflexible configurations may lead to inadequate test power in the presence of reasonably large sample sizes. Consequently, it is important to design learnable F- v. To this end, we subsequently design a learnable objective and let be optimized in data-driven manner. Before this, we provide approach to make the criterion be computed efficiently. This can be achieved by sampling in the frequency domain. Formally, finit-dimennsional approximation in the frequency domain of the integral in Eq. (4) is given as follows:
Du
Dy
1
HSIC = D2 ==
@PXY (West, Wy:s) - x (Warss Wyst))yys)) Wys))
(6)
where { [Wys 1- are sampled independently with the measure F wk F 1% respec-
tively. Note that F- و/ is a product measure, i.e., F- = (F-1 @ (F- wh)). This type of
approximation is also called random Fourier features (RFF) (28] that had been applied to various
kernel algorithms. We will incorporate this technique to efficiently perform computation later.
Learning Significant Fourier Feature Pairs
4.1 HSIC with Learnable Fourier Feature Pairs
To design F-14b, we need to make sure that supp(FF-1)) Rdd R.dy to meet the characteristic condition and that its integral over the full space is to ensure it is probability measure. Also, for practical utility, Fー should embody a familiar probability density function, facilitating sampling procedures. Fortunately, versatile array of options emerges through the judicious selection of kernels
F with adjustable parameters. Take kernel k as an example, some commonly used kernels listed in Tab. [ and their inverse Fourier transforms are listed simultancously. Additionally, to
Table 1: Some popular kernels (parameterized by o, 2) with corresponding density functions. (-bb(w))
Kernel (A)
To, (x)
(w(w)
Gaussian
[
2
(27)-dr/2 2 oo
2/o
(2x) da -da/2e - 1wll3/2
Laplace
BAl1
- (2th
o= 12
z/a V 1t43
Mahalanobis
1/2 w- -
E//2z
(2x) (2a)
1w1l3/2 1w111/2
be able to apply gradient-based optimization techniques, we invoke method that disentangle the sampled objects and the learnable parameters. Specifically, we leverage variable transform To, (a bijection function parameterized with 0g) to convert the probability measure F-1t/h into a simple distribution (e.g. standard Gaussian distribution) Px(w). Simultancously, component onto X. Consequently, we can focus on learning parameterized transformations To, and simplifying the computation by enabling sampling directly from pk (w).
relocate the learnable
Remark. The above scheme provides a broader form for designing. The mapping To, can be viewed as feature extractor, which makes it possible to flexibly combine models (e.g., neural network) thus incorporating deep kernel (24] into the framework. Also, should be noted that the single kernel example can also be extended to multi-kemel setting [1] by executing the procedure for each kernel.
Next, we obtain the learnable independence criterion and utilize the sampling technique in Eq. (6) to compute efficiently. Note that for simplicity, we take the same value for both D,, and D, in Eq. 6 by default. By the definition, the kernel function can be expressed
th (To, x. To, x') F[F [x)]]] = / /- (To (To To ppk (u(wdw::
"The bounded, continuous, translation iivarriann kernel satisfies the characteristic condition 12

---

By applying the frequency sampling technique, we obtain the approximation as
1/2
2 1/2
(hu (To, - To, = D e
2
Σ
(To -- =To,)) = Σ cos (wi (Te, - Te,
(8)
where (wx.g D/22
ر= are sampled independently with distribution pk (w) and the last equation is because the kernel function real. To get a more computationally tractable form, we define
Ax(x)= D cos (w. To, x)), sin(wi Te Te. ..... cos( To To,x)
(9)
called learnable RFF of k then Eq. (8) becomes e (()) (Te_ To, = AA(z)AA(z')) The ex- pression with similar form is also given in 44], with the difference that have added learnable parts. For Y, we define the corresponding symbols by substituting ls for 1 and x for y. Also, for convenience, default to keeping Y and X the same number of samples D from here on. Then the
HSIC with learnable RFF pairs can be obtained by replacing k, in Eq. (1) to u 1// v!!0) Also, the
corresponding estimator with sample Z can be obtained by replacing K. L in Eq. (2) to the matrices
where Ax == [Ax(11): (I,)) M)x and so as define for Ay. As a result,
1 HAY n
1
HSIC ( = n12
HAy
I AYell π2
(10)
where Axe = HAX. == HAy. The time complexity is analyzed as follows. Since the computation of the mapping Te depends the specific design, here we default to analyzing the kemne case shown in Tab. In this case, computing A xx Ay requires (nD(d, + dy)) time. Then calculate A Xe: Aye cost (nD). After that, calculate HSIC (2) cost O(n))). Hence, the overall time complexity is (nD(dd dy + D)), i.e. the running time is linear with n.
4.2 Linear-time Optimization Objective
Next, we model the behavior of (Z) to obtain an optimization objective for maximizing the power of the test. By utilizing the property that HSIC (Z) is a V-statistic, we can extend the results [14 Theorem 2] for HSIC, as shown in the following proposition with the proof given in the Appendix. To simplify, we denote (z,, y:) as 2 to represent the i-th sample and denote (n()) (To Tw) as k(w) and w²(a) (To To.Bu) ((m)
Proposition (Asymptotics). Let (())) 1 H ((....)) ( leu + ((ا)((ي) 2xlW))1 where the sum represents all ordered quadruples (1, u, v, w) drawn without replacement from from (4,5,,,)) Then, Under the null hypothesis Ho. HSIC.(Z) coverages in distribution to
(L..,,,))
nHSIC (2) S Σ Axl {(n(Zz))=
Ju J. Dajer ( (=x)dF=.. 21
(11)
where x²1: X22- ... are independent xi variates and x the solution to the eigenvalue problem as in the right of Eq. [1]). Also, under the alternative Hi, HSIC converges in distribution as
n (HSIC (7) EzHSSC. ((0, oZ = 16 E, (Ejg,
(w) (Ez 1 )² (12)
(w))
with the simplified notation Ejgg.= == Egj and Ez == E E
According to Proposition I the power of the test with HSIC can be formulated by
Py, (nHSIC,, rw) + /.E,HSIC.,)Z) Tw
(13)
Vio
where the standard normal CDF and ru is the threshold, i.e. (1 a) quantile of distribution given in Eq. (11) that exactly controls Type I error rate to the nominal level a. Hence, maximize the power of the test, a natural criterion is E estimation which can be computed in linear time.
rul/(Vnow). Next, we provide its
5

---

We first consider obtaining the estimator of the numerator part. For the term E2HSIC, we can estimate with (2) as in Eq. (10). The estimation of the threshold rw poses challenge. primarily stemming from the lack of an explicit expression for the distribution of the infinite sum of chi-square variables. One avenue to address this challenge involves employing the permutation method [2] to simulate the distribution under Ha. However, this method necessitates a significant number of shuffles to accurately approximate the distribution. Furthermore, even with the imple- mentation of parallel schemes, it incurs memory costs proportional to the number of permutations, rendering it impractical for resource-constrained scenarios. Here, we adopt a lightweight approach in practice, leveraging the gamma approximation proposed by [4]. A gamma distribution is uniquely determined by its first and second-order moments. For these two moments, we present their corresponding Ameer-time estimators in Theorem [ As result, we can obtain the (1 a) -quantile of the gamma distribution, denoted as Co. with estimated parameters = / Vo. = Vo & in linear time. Formally, with the term E and Vo defined in Theorem
1
Ca is calculated by
Ho: nHSIC, x7-1e x/8
C Vo
Vo
e I(>)
BTT(T) ,
dx = a,
(14)
where r(.) is the gamma function. By combining the way to estimate the gradients of ca. 33 we enable it for gradient-based optimization with automatic differentiation framework. As result, obtain a linear-time differentiable estimator of the numerator part.
Theorem (Linear- Time Estimators). Under Ho. the estimators of mean and variance with bias of O(n to Ez(nHSIC_ (Z) and Varz (nrzIIHSIC..(0 ( denote as Eg and Vo, respectively, are given by
Eo: = A Xe A
2n(n (n 5)
Ay.)
Vo = (n () 2) -3
1)2
n²
(15)
where ()² is the entry-wise matrix power. Both Eo and Vo can be calculated in O(nD²) time.
For the remain term ow we estimate with ã. that ~ == 16 [6 E.G E Ejq, (w) - (Z)]
To calculate Ejgrr Aage the straightforward way to compute each item hig which requires total Onn*) of computation. Here we provide a way to enable it to be calculated in linear time by obtaining a matrix expression. The main result given by
Σ J.g.r
(w) Gigr = + + (I"C) (1'BJC, - -nE; - nF, - nD: - I'D],
(16)
where the definition of variables A to F with the calculation cost given in the Fig. 1 and the derivation of Eq. (16) is given in the Appendix. By checking the complexity of the remaining matrix operations in Eq. (16). all the elements with index i can be calculated in O(nD²). Combining the results obtained before that HSIC (Z) can also be calculated in On thus calculating the
term T. cost (n) time. As a result, we obtain the overall thear-time optimization objective == [HSIC Ca/n/ /a/nn//w, which is a clear contrast to the existing quadratic- sandratic-tmmeeee schemes [30].
AfArloxo
[Ax (AGAVA?))
B B
Time Complexity:
OlnD")
O
(Ax(A31)) C= [Av(A
AAx F (A (xx1
O(n)
Figure 1: The diagram shows the definition of the quantities in Eq. (16). with styles representing the time complexity of the computational process in the current box. @: the element-wiss product.
4.3 The Overall Learning Framework
After obtaining the differentiable optimization objective J, we can perform the training process end-to-end. In this process, the overfitting issues may happen especially with insufficient samples, which could influence both Type I and II errors. If we use the same sample for testing, the Type I errors may be uncontrollable (22] when the overfitting issues happen. To address this, we adopt the split scheme as in 24 18) to allow our tests to maintain validity (controllable Type errors). The split ratio set to 0.5 to facilitate the balance between the two. Apart from controlling Type errors, we still want to mitigate overfitting issues much possible in order to generalize the optimized

---

Fourier feature pairs on test data thus improving the power of our tests. To this end, we select smooth function classes control the model complexity (e.g., as measured by the VC dimension), specifically in this paper, we consider the two classes in Tab. and implement them for experiments later. One is the choice of Gaussian classes that optimize the global scale, and the other we consider Mahalanobis classes and set E to be 1i ...... aa) for optimization, which corresponds to optimizing the scale in each dimension (which allows to capture high-frequency signals such as the edge in the image). These smooth choices also bring the advantage of interpretability (30] and it is experimentally proven that this simple choice is already able to handle most of the cases in different settings.
More discussion about split strategy. Currently, there are two major classes of approaches for adaptive independence tests. One involves selecting kernels from a finite/countable set (discrete scenario) and the other involves performing kernel parameter searches in continuous space (con- tinuous scenario). For the former case, some methods [2 32 control Type errors by applying techniques from the selective inference literature without data splitting. However, these methods cannot be directly applied To the best of our knowledge, both our scheme and existing methods [24] [8] rely on data splitting for the continuous case. Designing methods to control Type errors in the continuous case without sample splitting remains challenging and significant problem for future research.
continuous scenario due to the uncountable set of kernels involved.
Algorithm. Our algorithm is outlined in Alg. [ As pro-ressssnng step, we split the data into the training data z and the testing data n (Line 1). The test contains two phases: 1) We learn the Fourier feature pairs with Adam (2I] optimizer using full batches on Z (Lines 2-7). 2) With the learned Fourier feature pairs, we calculate the test statistic and threshold (Lines 8-10) to determine the independence (Lines 11) on Ztz The overall time complexity O (dn.(ddz + dg + D)) and
the space cost is (n((2 + d, + D)) for storing the data as well as the Fourier feature pairs.
Algorithm 1 The learning and testing framework
Input: samples Z of X, Y. significance level a, the number of Fourier feature D.
Output: X IL Y or X K- J.Y.Y. Y.
1: Split the data as 2 = 2r U Sampling {w;)) D/2 = (WWk):W.g)) D/2 with p(w).
2: <] Learning significant Fourier feature pairs on Z²r
3: Initialize parameters 0k. 02, set learning rate e, and set iteration steps T.
4: for t = 2, T do
5: Obtain learnable Fourier feature pairs Ax, Ay with parameters 0x, Ot and {wr} D/2
6: Calculate criterion with x: Ay then optimize with (0k, 0t) +- (0x, B1) + cV (B.
7: end for
8: After training. obtain optimized parameters 07, 07
9: < Testing with learned Fourier feature pairs on Ztc
10: Calculate the statistic "'"HSIC.. (Z't), threshold va (7th) with parameters 0% 0f and {w;) D/2
11: Return X 4 Y (Z I n "SSC holds, otherwise X JLL Y.
Theoretical Results
We first give the uniform bound results ball in parameter space which guarantees the conver- gence of our optimizing objective thus ensuring its effectiveness in modeling test power.
Theorem 2 (Uniform Bound). Let 0g, Or parameterize To To, in Banach spaces of dimension de, di- And To.. To, are Lipschitz to the parameters Ok, Ot with the non-negative constant La,, Tú, respectively. Let O be set of (0x, 0t) for which aw 2 c >> O with a positive constant e and ||0x]| < Ro., 1/0ll < Ra.- Let r denote the threshold, i.e., (1 aqquunteee for the distribution in Eq. 17) and (m)
be the threshold with sample size n. Let (wiksj w1))) D/2 be the samplings of frequency with the sampling number D. Also, we define Rws, := sup, | ll, Ru,, := sup, || ll. == max(de. di} and Ew = (Z). Then with probability at least 1 we have
Ew rw /n
EzEu -ra/n
~ -00(11
log n +
Ru, La + Ruy RayLi)) In
1)
sup (6..0))E
log 6
+ d
Ow
Vn
7

---

Next, we show the consistency of the tests, ie. the power of the test tends to 1 as the sample size increases. Let the U-statistic of ( be (Z then we have the following results. Theorem 3 (Consistency). Let og of be the parameters after learning, Zhe be the test samples of size no, when EzHSIC (Z'c) ( > 0, then the probability of the Type II error
P PType II error) Pr, (mHHSSC
( (Z S $1110007, 02 ((m-1/3).
(17)
Let the mapping functions with learned parameters 0g O7 be Tep, Tep and the corresponding range space be compact subsets of BRd,, RR respectively. Also, the diameters of two range spaces are denoted by diam((Tz) ), diami (To;)) respectively. Les ((wk): D/2 be the frequency samplings with their second moment denoted by o :- (w où, == Eprtw) (ws))))))) Additionally, we denote E. == HHIC(H,,YY Y). then under Hi, we have EzHSIC (Z > 0 with any constant probability when D = 2
drg +d
log owg "ug.dam(TTa diamttt Top
This result can be understood in two parts, The first one is about consistency, i.c., the Type II error rate tends to 0 at the rate of m 1/2 when condition EzHSIC (Z*r) > 0 holds. The second part provides the condition when HzHII (2 > 0 holds, which requires sufficiently many frequency samplings. The theorem shows that the large value of the criterion HSIC(X, Y) helps to reduce the required D. According to the results discussed in Sec. there is an improvement in the criterion by finding the more significant features and thus helps reduce the required D. To summarize, the significant features further help to guarantee the consistency of the test under the efficient requirements (smaller D). All proofs as well as additional results are given in the Appendix.
Performance Evaluation
We compare the following tests: distance-based statistic dCor 33). the original HSIC QHSIC [1], the copula-based method RDC (26), the three variants of HSIC NyHSIC [44. FHSIC 44, BH- SIC [44 and HSICAge gg 32), NFSIC [18 introduced in Sec. | Among them, dCor and QHSIC are On²) tests. RDC is calculated in (n nz) time and the rest are (n)) tests. A detailed description of the comparing methods is given in the Appendix. For our methods, We provide two variants as mentioned in Sec. 4.3 We name the Gaussian class case as LFHSIC-G, and name the Mahalanobis class case (and set Σ diagonal matrix) LFHSIC-M. Additionally, for the comparative meth- ods 30 that are relevant to us, due to their high time overhead and therefore inability to handle some settings of evaluation, we separately provide a comparison with our method under certain feasible experimental settings, the results are given in the Appendix.
Experimental setup. The significance level is set to 0.05. We Gaussian kernels for both X and Y in all kernel-based methods. And QHSIC, RDC, NyHSIC, FHSIC, BHSIC are all with the kernel width being set to the Euclidean distance median of the samples. The number of random features D for FHSIC, LFHSIC-G/M the number of induced variables for NyHSIC, the block size for BHSIC well as the number of sub-diagonals R for HSICAgg are all kept consistent recommended in 44 32 for fair evaluation. Parameter settings for the rest of the methods follow the defaults in the code. More details of the setups given in the Appendix.
Evaluation protocol. We evaluate on four synthetic datasets 18 30 and two real datasets 44 30
Synthetic datasets consist of Sine Dependency (SD). Sinusoid (Sin), Gaussian Sign (GSign), and independent subspace analysis (ISA) dataset [1]. On real data, we introduce high-dimensional image data and another music dataset to evaluate the capability of all methods in different data scenarios. Unless otherwise specified, we perform 100 repeated randomized experiments and report the average result of test power default. More details of the generating process of each dataset and the details of the evaluation (including running time) are provided in the Appendix.
6.1 Results on Synthetic Datasets
Settings of SD, Sin, and GSign Dataset. The Sin data corresponds to the example in Sec. 3 that requires the method to focus on differences in specific frequencies. SD, is dependent solely on the first two dimensions of X. In contrast. in GSign, Y is independent of any proper subset of X
8

---

Average Results
Sine Dependency ISD)
Sinusoid (Sin)
Gaussian Sign (GSign)
0.25
Ayerage powert 1)
Average test powert ?) Average test powert ?)
Average test powert
Type lerror ratet
0.20
6.8
6.0
0.8
6.15
0.5
8.6
0.6
0.10
0.05
0.2
0.2
0.2
0.00
0.0
0.0
0.0
Sin
G5ign
2000
3000
3500
2000
3000
2000
3000
6000
Type lerrrratttl S
0.25
Average test powert
1.0
1.0
2..
Average test powert
0.20
8.8
0.0
0.0
9.6
0.6
0.6
0.10
0.4
0.4
0.05
0.
6.2
0.00
50
Sin Datasets
GSign
0.0
2000
25.00
3000
3500
4000
0.0
1000
1500
2000
2500
3000
2000
4000 5000 6000 3000
Sample size
Sample size
Sample size
PHSIC BHSIC
HSICAga NPSIC
LFHSIC-G LFHSIC-M
OHSIC
NyHSIC
----
Figure 2: Top: (D = 100). Below: (D = 500). Left: The average Type error rate on SD, Sin, and
GSign datasets. The other three plots: The results of average test power on these three datasets.
Samp:10000, Dim:16, D:300
Samp:60000, Dim:32, D:300
Samp:10000, Dim:16, D:500
Samp:66000, Dim:32, D:500
1.0
1.0
1.0
1.0
Average test testtpppn powert
0.6
Pagaage test power
8.8
Average test power
8.8
Average test powert
6.8
X
0.6
0.6
3.6
6.6
0.4
0.4
8.4
6.4
0.2
0.2
62-
0.50 Angle(
1.00
Angle(xm/44)
Angleixm/4)
Angleixmm/4
- RDC
NyHSIC
BHSIC
-
FHSIC
HSICAga
-E--
NFSIC
LFHSIC
- ----
LPHSIC
Figure The average test power v.s. the rotation angle of each method on the ISA dataset.
but dependent on X as a whole. Therefore, it requires the method to learn important local/global features based on the characteristies of the data improve the test power. For SD and GSign, set the dimension of X as 4 and 5, respectively, and the dimension of Y is 1 for both. For Sin, we set the frequency parameter w For calculating the Type error rate, we evaluate using samples (n = 2000) obtained by permutation for all three datasets.
The results for D 100 and D 500 are shown in Fig. 2 Except for NFSIC and BHSIC, all the other methods succeed in controlling the Type error rate & 0.05. LFHSIC-M/G, NFHSIC, and HSICAgg perform much better than other methods due to their ability to obtain more appropriate kernels/features for testing. LFHSIC-G/M -CM performs on both settings of D and has a more significant advantage over the others when D is small, implying the optimization objective can still be successfully optimized and the criterion is still powerful under high-speed requirements. In addition, as the sample size increases the test power of LFHSIC-G/M is gradually converging to 1 in both settings, which corroborates the results of Theorem 3
Performance.
Settings of ISA Dataset (Large Scale). We set dimension (of both X, Y) and sample size as = 16, n = 10000 and d = 32, n = 60000, then evaluate the average test power with angle parameter 0 E [0, n /4] Note that larger angle signifies stronger dependency. The quadratic-time methods are not involved in the evaluation due to their inability to handle large-scale settings. For HSICAgg under the challenging setting n 60000, d 32, the memory space required for parallel implementation leads to memory overflow and hence the results are not given.
The results for D 300 and D = 500 are shown in Fig. 3 The results obtained at = reflect the Type I error rate. All methods successfully control the Type I error rate S 0.05. LFHSIC-M stably outperforms other methods significantly as the angle increases. Method (LFHSIC-G) that simply optimizes the global bandwidth performs worse as d increases, corroborating the need for more flexible kernel designs for more challenging tasks. Furthermore, comparing the
Performance.

---

Results 3Dshapes
Sample size: 500
Sample size: 1000
Average test power( (
Average error rate
0.8
RDC
oCor
QHSIC
HSiCAgg
NFSIC
BHSIC
Average test powert
NyHSIC
LFHSIC-G
0.6
PHSIC
LFHSIC-M
0.4
0.2
0.2
0.2
1.00
0.05
0.0
Type error
Type error
0.0
dCor
OMSIC
RDC NyHSic
Friic
BHSiC
HSiCAgo
Wrstc LFHSIC-G LFHSiC-
dCor OHSIC
RDC
NyHSiC
Fisic
BHSIC HSiiAgg NPSIC LFVSIC
LANSIC-M
Figure 4: The results two real data. Left: 3DShapes. Right two: MSD Dataset.
results under different settings of D, our method LFHSIC-M performs consistently well and exhibits progressively better performance as increases.
6.2 Results on Real Data
Settings of Two Real Data. The first real dataset used is high-dimensional image dataset 3Dshapes in [30]. In our experiments, we vectorize image X a vector with dimension 64 x x3 12, 288. The sample size is set as 128. We add standard Gaussian noise NoO 1) to the angle Y to make the setting more challenging. The Type error rate is evaluated by the samples obtained by permutation. Besides, we consider the Million Song Data (MSD) as the second real dataset. The first dimension represents the year of release of each song and is referred to as variable Y. The remaining 90- dimensional features (e.g., mean timbre and timbre covariance) constitute variable X. We follow the recommended setting [44), i.e., disturbing each entry of the X with an independent Gaussian noise (0, 1000). For this dataset MSD, in order to fully utilize the data, we randomly select n E {500, 1000} samples as the training set and other n samples from the remaining data 100 times for the evaluation and obtain the average result. The above training and testing processes are repeated 10 times to evaluate the robustness of the optimization scheme.
The results of two real data with D = 10 are presented in Fig. For the results on 3Dshapes (shown in the left of Fig. 4. all methods except BHSIC and NFSIC control the Type I eroor well. The linear-time test has relatively lower power compared to the quadratic-time test except for LFHSIC-M, proving that its more significant features obtained in high-dimensional scenarios enable it to achieve outstanding performance even in scenarios with high approximation requirements (D = 10). Similar conclusions can drawn from the MSD dataset (shown in the right of Fig. 4 Additionally, the results for NFSIC and LFHSIC-G/M with different sample sizes indicate increased robustness the optimization as the sample size increases (reflected in the reduction of variance), and the more flexible design also contributes to this (comparing LFHSIC-M and LFHSIC-G), thus can be more effectively applied to real-world scenarios.
Performance.
7 Conclusion
In this paper, we propose a novel method to efficiently learn significant Fourier feature pairs for maximizing the power of HSIC-based independence tests. By integrating learnable Fourier feature module, we improve the flexibility of existing configurations and design new criterion. The proposed linear-time optimization objective accurately models the power of the test and can be trained end-to- end in a data-driven manner, ensuring both effectiveness and efficiency. Both theoretical results and experimental results show the effectiveness of our proposed method. Future work includes further improving the sampling method in the frequency domain.
Acknowledgments and Disclosure of Funding
This work was supported by National Natural Science Foundation (NSFC) (62372116), and National Key Research and Development Program of China (2021YFC3340302 and YFC333333))))
10

---

References
[1] Albert, M., Laurent, B., Marrel, A., and Meynaoui, A. (2022). Adaptive test of independence based hsic measures, The Annals of Statistics, 50(2):85-8879
[2] Arcones, M. A. and Gine, E. (1992). On the bootstrap of and statistics. The Annals of Statistics, pages
[3] Bach, F. R. and Jordan, M. L. (2002) Kernel independent component analysis. Journal of machine learning research, 3(Jul):1
[4] Bertin-Mahieux, T. (2011). http://oorrg...442///5555000
YearPredictionMSD
UCT Machine Learning Repository.
DOE:
[5] Burgess, C. and Kim, H. (2018). 3d shapes dataset. http:///gghhhbooommmmmmmmm////as
[6] Camps-Vally Valls, G., Mooij, J., and Scholkopf, B. (2010). Remote sensing feature selection by kernel dependence measures. IEEE Geoscience and Remote Sensing Letters, 7(3):587-591.
[7] Chatterjee, S. (2021). A new coefficient of correlation. Journal of the American Statistical Association, 2666
[8] Chwialkowski, K. P., Ramdas, A., Sejdinovic, D., and Gretton, A. (2015). Fast two-sample testing with analytic representations of probability measures. Advances in Neural Information Processing Systems, 28.
[9] Cohen, I,, Huang, Y., Chen, J., Benesty, J., Benesty, J., Chen, J., Huang, Y., and Cohen, I. (2009). Pearson correlation coefficient. Noise reduction in speeck processing, pages 1-4.
[10] Fukumizu, K., Gretton, A., Schölkopf, B., and Sriperumbudur, B. K. (2008). Characteristic kemels on groups and semigroups. Advances in neural information processing systems, 21.
[11] Gönen, M. and Alpaydı,, E. (2011). Multiple kernel learning algorithms. The Journal of Machine Learning Research, 12:2211- 1-2268.
[12] Gretton, A. (2015). A simpler condition for consistency of kernel independence test. arXiv preprint arXtv//501.01103
[13] Gretton, A., Borgwardt, K., Rasch, M., Schölkopf, B., and Smola, A. (2006). A kernel method for the two-sampl-problem. Advances in neural information processing systemx, 19.
[14] Gretton, A., Fukumizu, K., Teo, C., Song, I.., Schölkopf, B., and Smola, A. (2007). A kemel statistical test of independence. Advances in neural information processing systems, 20.
[15] Gretton, A., Smola, A., Bousquet, O., Herbrich, R., Belitski, A., Augath, M., Murayama, Y., Pauls, J., Schölkopf, B., and Logothetis, N. (2005). Kernel constrained covariance for dependence measurement. In International Workshop Artificial Intelligence and Statistics, pages 112-119. PMLR.
[16] Hoyer, P., Janzing, D., Mooij, J. M.. Peters, J., and Schölkopf, B. (2008). Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21.
[17] Jitkrittum, W. Szabó, Z., Chwialkowski, K. P., and Gretton. A. (2016). Interpretable distribution features with maximum testing power. Advances in Neural Information Processing Systems, 29.
[18] Jitkrittum, W., Szabó. Z., and Gretton, A. (2017), An adaptive test of independence with analytic kernel embeddings. In International Conference Machine Learning, pages 1742 1751. PMLR.
[19] Kalinke, F. and Szabo, Z. (2024). The minimax rate of hsic estimation for crassation-invariant kemels. arXiv preprint arxii:2403.0772
[20] Kim, 1. and Schrab, A. (2023). Differentially private permutation tests: Applications to kernel methods. arXiv preprint 11X1:23100.9943.
[21] Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint 412.v:141..6980.
[22] Kübler, J.. Jitkrittum, W., Schölkopf, B., and Muandet. K. (2020). Learning kernel tests without data splitting. Advances in Neural Information Processing Systems, 33:6245-6255
[23] Li. Y., Pogodin, R.. Sutherland, D. J., and Gretton, A. (2021). Self-supervised learning with kernel dependence maximization. Advances in Neural Information Processing Systems, 34:15543- 15556.
11

---

[24] Liu, F., Xu, W., Lu, J. Zhang, G., Gretton, A., and Sutherland, D. J. (2020). Learning deep kernels for non non-parmmetii two-sample tests. In International conference on machine leurning, pages 6316-6326. PMLR.
[25] Liu, I.,, Pal, S., and Harchaoui, Z. (2022). Entropy regularized optimal transport independence criterion.
In International Conference Artificial Intelligence and Statistics, pages 11247-11279, PMLR.
[26] Lopez-Paz, D., Hennig, P., and Schölkopf. B. (2013). The randomized dependence coefficient. Advances in neural information processing systems, 26.
[27] Podkopaev, A. and Ramdas, A. (2024). Sequential predictive two-sample and independence testing. Advances in Neural Information Processing Systems, 36.
[28] Rahimi, A. and Recht, B. (2007). Random features for large-scale kernel machines. Advances in neural information processing systems, 20.
[29] Ramdas, A., Reddi, S. J., Póczos, B., Singh, A., and Wasserman, L. (2015). On the decreasing power of kernel and distance based nonparametric hypothesis tests in high dimensions. In Pruceedings of the AAAI Conference on Artificial Intelligence, volume 29.
[30] Ren, Y., Xia, Y., Zhang, H., Guan, J., and Zhou, S. (2024). Learning adaptive kemnlss for statistical independence tests. In International Conference on Artificial Intelligence and Statistics, pages 2502. PMLR.
[31] Ren, Y., Zhang, H., Xia, Y., Guan, J., and Zhou, S. (2023). Multi-level wavelet mapping correlation for statistical dependence measurement: methodology and performance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37(5), pages 6499-6500
[32] Schrab, A., Kim, I., Guedj, B., and Gretton, A. (2022). Efficient aggregated kernel tests using incomplete u-statistics. Advances in Neural Information Processing Systems, 11118881188777
[33] Sejdinovic, D., Sriperumbudur, B., Gretton, A., and Fukumizu, K. (2013). Equivalence of distance-hased and rkhs-based statistics in hypothesis testing. The annals of statistics, pages 2263-2299
[34] Serfling, R. J. (2009). Approximation theorems of mathematical statistics. John Wiley & Sons.
[35] Shekhar, S., Kim, L,, and Ramdas, (2023). permutation-free kernel independence test. Journal of Machine Learning Research, 24(369):1-68.
[36] Sriperumbudur, K., Gretton, A., Fukumizu, K., Schölkopf,, B., and Lanckriet, G. R. (2010). Hilbert space embeddings and metrics on probability measures. The Journal of Machine Learning Research, 11:1517-1561.
[37] Sutherland, D. J. and Schneider, J. (2015). On the error of random fourier features. arXiv preprint arXiv:1506.00 02785.
[38] Sutherland, D. J., Tung, H.-Y., Strathmann, H., De, S., Ramdas, A., Smola, A., and Gretton, (2016). Generative models and model criticism via optimized maximum mean discrepancy. arXiv preprint arXiv:/6/ 1.04488.
[39] Székely, G., Rizzo, M., and Bakirov, N. (2007). Mcasuring and testing dependence by correlation of distances. Annals of Statistics, 356622779--794.
[40] Székely, G. J. and Rizzo, M. L. (2013). The distance correlation t-test of independence in high dimension. Journal of Multivariate Analysis, 117:193-213.
[41] Vershynin, R. (2018.. High-dimensional probability An introduction with applications in data science, volume 47. Cambridge university press.
[42] Wang, Z., Zhan, Z., Gong, Y., Shao, Y., loannidis, S., Wang, Y., and Dy, J. (2023). Dualhsic: Hsic- bottleneck and alignment for continual learning. In International Conference Machine Learning, pages 36578-36592. PMLR
[43] Zhang, K., Peters, J., Janzing, D., and Schölkopf, B. (2012). Kemel-hased conditional independence test and application in causal discovery. arXiv preprint arXiv: 1202.3775.
[44] Zhang, Q. Filippi, S., Gretton, A., and Sejdinovie, D. (2018). Large-scar scale keree methods for independence testing. Statistics and Computing, 18:113 13-130.
[45] Zhang, T., Zhang, Y., and Zhou, T. (2024). Statistical insights into hsic in high dimensions. Advances in Neural Information Processing Systems, 36.
12

---

Appendix Organization
Section A
List of Symbols and Notations.
Section
B
Assumptions.
Section
Some Auxiliary Lemma.
Section
Proof of Proposition
Section P
Proof of Theorem [
Section Calculation of Eq. (16)
Section Proof of Theorem
Section H
Proof of Theorem
Section
Smoothness of Optimization Objective.
Section Details of Experiment Setup.
Section Additional Experiment Results.
Section
Limitations and Broader Impacts.
A
List of Symbols and Notations
big O notion
0
small O notion
i.i.d. IR
independent and identically distributed the set of real numbers
B(R)
Borel o-algebra on R marginal distribution of X
Fx
Fxy
joint distribution of X, Y distribution function of X expectation of X
Fx
E[X
Var(X)
variance of X
X LLY
random variables X, Y are independent
X KK Y
random variables X, Y are not independent the set of all r-tulles drawn without replacement from the set {1,...,.1) n1
(
number of k-combinations of elements number of permutations, define as [n= ml
(n)
Tr(-)
the trace of a square matrix an vector of all ones
H
centering matrix define H I 11T element-wing product element-wise power
n
2)
4
convergence in distribution the product symbol of measure the product symbol of topological space covering number with radii for space O the Fourier transform, Fourier inverse transform
Ø
N(O,r)
F.F-1
B Assumptions
The following are the assumptions required. We denote the parameter spaces 02, 02 as θs, O,
(a) The mapping functions To. To, are Lipschitz to the parameters 02, 0z. i.e. for all x E X. E e and for all 0g. 0' θç, Or, 0f E Oi
Te. (x) To: (=)ll< La 110x 0,11. T (v) Toy( L ||0: - 0/
(18)
with the nonnegative Lipschitz constant Lx, Lt-
(b) The range of the mapping functions Toy To, are bounded.
(c) The parameters 6u. 0₂ lie in Banach spaces of dimension d,. di respectively. Also, the parameters fr are bounded by Rog Ra, respectively, i.e., ||0x Ra, ||0:11 < Ra.
13

---

C Some Auxiliary Lemma
C.1 Useful Expression
In this part, we give a useful expression for jjr for the subsequent proof. By the definition, we have (
1 Σ (..-g.))
(t,u,,,a)) Mi tu + k/wa ((m) - 22 4tx We simplify it by setting t = i, u = i,
((w))(())
lijer = 4:
(w)
and w i in turn. Then we can show that Higgr is equal to
(
(ollyle) in + (
(w) (()) fer
(A (w)) (w)
2k (w)) )(,))
+
+ ki oow
4!
4!
(u,vww)
(1,1,2)
(19)
(1.
(1.rrr)
(Nlea) lew + (() 24!w) (())
(ke tu + kie (()
2k (w)))
+
4!
(3,1,,0)
By the definition, k/Ww) = w/(
(Ta, 2t To, Ax (xx)xxxxxx is symmetric, i.e. k(w k!ee
And so as (uw). Hence we can merge the identical items (marked with the same color). As result,
(igg.) Σ
(ig.r)
n Migor
(w)
(2
( Leu
+ ((
(x(
(2
(k(
and
(u,v,ar)
(C,01,0))
(20)
(1.g.r
1 (1.g.r)
+
4!
(2
(W) tu
+ 2k (w)
- 2k (w)) ((m))
4!
(w) (( (2k
to
(ta,w))
(L,u,))
We will use Eq.
20
many times in subsequent proofs.
C.2 Properties of Learnable Random Fourier Feature
Under the assumption (a) RFFs (lW)) (w) are Lipschitz to the parameters 0g. Formally,
Lemma 1. (Lipschitz Property of Fourier Feature). Let ToL To, be the mapping functions of X, Y that are Lipschitz to the parameters Oμ, Ot with the non-negative constant Lxs Li, respectively. Let (Wk:j:Wtz))) D/2 be the samplings of frequency with the sampling number D. Also, define Rus sup, |wweill ; Rw, sup, ||wlll then for the RFFs (/) 10
(w) with mapping functions
To To, and frequency samplings [WRes wir) ) for all 0z, Bg E Ox, 01,0% Oi we have
D/2 p for all (z, x') X X, (v. y x y and
11 (A..z) 1/11)) (A (Ar,r))) 11 S 2R,. Lx 110 0%ll.
(w)
(21)
11 (A (vvrr) )- (A ('''') < 2R,,, La 110, 0i11,
where De,a/ == To x - To A/..r == Tog x Toç x' and D , A are defined by analogy.
Proof. We prove the result for sh only since the proof for (w) can be obtained in the same way. We start by recall the definition Vi
= 3 Epa cos(wif A.,z). Then
D/2
D12
(Am,ar) - (
(A (.. =
2
Σ
cos (wFt Rij
A
2
Σ cos cos A
D
D
j=l
jml
(22)
D/2
cos
k:j Aewer)
cos(w)))))) A x.r""))
D
j=1
Since the cosine function is bounded by 1, by the mean value theorem, for fixed j, we have
cos Ar.rr) cos(wTT T A x. Il S W Ae.ar WT,
(23)
14

---

Then according to the Cauchy- Cauchy-Schwarz inequality.
| Ar.r' W A S l[wks || ||Ar, 2
(24)
By the definition of A Z,,z' and the Lipschitz property of the mapping functions To., Top, we have
A a. |1 (To. x To 2²)
(Toz x To,
(25)
S T Toy æ=1 1T Tay x' s 2Lx -10x 102--11-.
Combining the above results, we complete the proof.
Under the assumption (b) we can obtain the uniform convergence property as follows.
Lemma 2. (Uniform Convergence of Fourier Features). Let the mapping function of X. Y with parameters 0g. Bt be Te.. To,, and the corresponding range space be compact subset of Rd Reyy, respectively. Also, the diameter of two range spaces denoted by diam((Te) (iam((Te)) respectively. Let (wi:).Wos)) D/2 be the samplings of frequency with the sampling number D, then for the RFFs with mapping functions To To, and frequency samplings {Wk..j W::)) )) j==1 we have
Ow, [w, To.))
2
De2
sup (a k(x, x')| 2 E S 28
exp
A(dT, + +2) +2))
L
(26)
Tu,,iam(Tin)
2
De2
sup (A(()) - Iy,. 2 s 28
exp
4(dT, + 2)
u.y/Ey
where the second moment of frequency samplings o == Ep (w (y d ;= (w)( (
Proof. Based on the derivation of RFFs in Sec. 4.1 We can view it as the frequency sampling process is performed after the range space is obtained. Since the convergence bounds of the sampling process can be obtained directly through the results of [28] Claim I]. by replacing the input space Claim 1] to the range space here, then this part of the proof can be completed.
in [28
Remark, Combining the technique in 37 the constants in bounds can be further improved.
C.3 Approximation Error Bound
Let HSIC(() (2), also denoted as c(u) be the U-statistic that corresponding to HSIC,, i.e., HSIC(") (Z) =- [π0]4 (e.j- Rijar The population value of HSIC!") (Z) is given by Ez (u)
(w)
which can be viewed as the result obtained after a frequency sampling approximation on HSIC(X, Y)
performed. The bound of approximation error is given by the following Lemma.
Lemma 3. (Approximation Error Bound). For simplify, we denote Ax(x))"A((a)) A(t) M as
((w)(x, (I,x'), x'), ((m) (y, s/), respectively. Then we have
Ez (IIC(X,Y) WEE
11 (/ (g. k(x, x'),,,")(,,))))) (27)
sup
Proof. We first represent E in the form corresponding to Eq. i.e.
(w) E Ex ExX (W()) (x, X') (Y, Y") Exx (w( (X, X')] Eyr [1 (V,
(28)
2E Ex (x, X') (Y, Y')].
Taking one of the items example and comparing it the corresponding item in Eq. 1..
ExY. Exk(w) (x, X' 1( (Y,Y") -
(Y)]
f Y / (x (X. x' (V) - k(x, X'))'"'Y"'""""""" dPP x'''
(29)
(k((W) (x, x' 2 (y. v/ k(o, (1),, v')l-
sup 8. v.y.'
The results can be obtained for the other terms in a similar way, which completes the proof.
15

---

D Proof of Proposition 1
In this section, we give proof of the Proposition 1 We first restate the Proposition There.
Proposition (Asymptotics). Let higgr Ti > (13-9.))
(1,u.v.w) kin y(u) (()))((
+ kiew ((m) -2 (()) where the
sum represents all ordered quadruples (t, u. U, w) drawn without replacement from (i,j.q,r). Then, Under the null hypothesis Ho. HSIC coverages in distribution to
nHSIC 4 Σ AxXI \rg((2))
h hijor (Z) ddF 2q18))
(30)
where 221:XP2 are independent x² variates and dS is the solution to the eigenvalue problem as in the right of Eq. (30g. Also, under the alternative Hi, HSIC. (Z) converges in distribution as
n (IIIIC. (2) EzHSIC,((Z)) N(0, 0Z), o 16 (Ej ( (Ezh ) (31)
with the simplified notation Ejgg,r Bayi and Ez E
Proof. The proof is mainly based on [3 Chapter 5]. A proof for a similar result has been given in [14] Theorem 1,2]. The difference is that consider the asymptotic distributions of HSIC (Z) that used learnable RFF thus is a function of frequency samplings while they consider HSIC, (Z). Thus some steps need be modified.
Step 1: we show that HSIC (Z) is a V-statistic, this can be done since it can be expressed as HSIC... + Eid..r ((0)) To facilitate the conclusions in 34 for the U-statistic, we define the U-statistic HSIC (n)a E(s.aar) Aagr that corresponds (Z).
Step 2: Then prove the result under Ho. To begin with, first show that Ejg.r (w) 0 with (w)
(r) ig under Ho. According to Eq. (20). we calculate M
(iggr)
(1.g.r
E Ejig. (w)
Mjar
2
a (WW)(w)) + Ni 1ow k/(w) (())(())))))))))))))))))))))())
2
E
(2/1) (w))
4!
4!
(u,,),n)
(f,
(f.g.r)
(f.g.r)
2
E
((w)) Ei (keu leu + k(w))lw) )ww)
2
Σ
E E
(w))
4!
4!
(1,a,.)
(t,u,))
E ph (w) ((0))
+ ((W) (w)) (00))
E til (w)
(ki
(w))(
2
2
Df (())(( (w)
+ k ((1)) (()))(
Euu (k (())((())
(32)
where we define simplified notions Bidudett whose superscript indicates the restriction. For u,o,
readability, we will require additional notations: E,k(a) (w) = E and E, := E k (the notations for Y is defined by analogy). Under Ho. X and Y are independence. Hence
(w) 2E, a. uor -E,h! E,
((m)
E,,( E. (w)
E,k, (()) E,, E.,K!"')
(,,(W)
(33)
+ E. k 1 E ((4) ((,)
+ E E
(w) (. Eyy(" E BAlWE,, E,, 0.
Then combining the results 34 Section 5.5.2], we can prove Eq. (30).
Step 3: Next we prove the asymptotic distribution under H4. We only need to show that [HSIC,.
HSIC(") (2)l (11nn). By the definition of k((),, ,(44), we can check that [k(=]] < 1, [(()) < 1 for all t, u, thus |h higg < 4 for all i,j. r. Hence we have
HSIC (2) HSIC (x) (2)l < ntat (n)4
1
1 1)
-~ O(1/n). 4m010)))
(34)
n
(n)4
Combining the results 34 Section 5.5. we can prove Eq.
(1)
16

---

E Proof of Theorem I
In this section, we give proof of the Theorem We first restate the Theorem I
There.
Theorem Linear-Time Estimators), Under Ho. the estimators of mean and variance with bias of to [n[nHSIC [2) and Varz|nHSIC.,(22 (2),, denote as Eu and Vo, respectively, are given by
1) O(n
Eo : . 1
2n - 4) (n- - 5) [1' (xx
(11" $1]
Vo = (n 1) 2) 1
(n (n- 1)2
n2
(35)
where ()² is the entrywise matrix power. Both &g and Vo can be calculated in O(nD2) time.
Proof. We first prove the part of the mean. Recall the definition of (Z), we have HSIC
/t Enj.gr Ezh When (, E i2. then we ligr = by performing the same analysis as in Eqs. (32 and 33 Then we consider the case where exactly two elements of i, i g, are the same, for total of (w) 6n(n (n - 2) terms. By the symmetry of "igrr the expectation of these terms all take the same
पर Eijgg h Hence Ez (HSIC,
1
can show that under Ho. Eijigr (w)
value, and here we take (w) as example. According to Eq. (0 we can represent h (w)
stgr as
(i.g.r)
(i.g.r)
11 (w) ligr
Σ
(k
(ol + ((1))(
Σ
(n
(u,),.))
(t,0,w)
(36)
2 (2.9.7)
(E.g.r)
(w0) 1/m
(w)
(w)
(w))
(())
2
+
(Kiu
4!
4!
(1N6,))
(1,26,0)
Under Ho. X and Y are independence. Take the expectation on both sides, we have
12E, q. 1 sigr (2 + 4E,k!1) E, (2E,((0) + 4E, (, k(W + 2E, + 2E h ((w) (E ) - (2E, + EE
(W))
(6E, Byy + (2E, + ( E,)(w)
(37)
(2E,,(( (w) + AE (E, (ig((w),, E,y (()) (GE, keW Ey((w) = -
2 En E, + kl B Ew))
where we define additional notation (. E E k/ww) (the notation for Y is defined by analogy) and use k:g 1 1. Hence in this case, the sum of the contributions of all terms to Ez (HHSI,,, (Z)] is (1 -- klw - E,y(()
(, + (1/n). For the remaining terms, i.e., the case where we can conclude that the at least three j. 9, r are equal, combined with the boundedness of h hjgrr sum of their contributions is (1//n). As result, we have shown that
Ez IHHSSC (Z)) (1 E., E (1 E,,(()) + O(n
(38)
The unbiased estimators of En,((,), (,! are given by 1s 17 - 1 (Ay
I,,
respectively. Hence under Ho, we obtain the estimator of mean with bias of O(n as
A I, nnn 1)
1 (A AT - L.) n(n 1)
1 1 A
(39)
(n - 1)2
Next, we prove the part of the variance. We start by calculating Varz|nHSIC!" (2)), where the U- statistic HSIC!") (Z) (1)a E(higgr hlw) According to the results 34 Section 5.2.1, Lemma A], we have
-1 4
4(" 1(m=²)
6(
(arlHSII((
Co
Ci
Co 0n) (40)
17

---

where == E, (E un )² and 62 Et, (E ( Under Ho, when (i.j.g.)) i1, (w) 0 by performing the same analysis as in Eqs. (2) and (33 thus 0.
show that E Eg.gr
For calculating S2. we mainly focus on the term Ey.nh We use Eq.
20 again,
(1g.r)
(1ggrr
(w) 12h
( + (( ((a))(
(Re (())
Ejgr
(t,2),0)
(41)
(Kea
(w)) tEu + ((w))(() (w)) )()))()))))
(Kea (w)
(
(L,N,w)
(f,0,))
Under Ho. X and Y are independence. Take the expectation Egr on both sides, we have (w)
12E, q. lpgr
13gr = (2k iy + AE (2 Eyg
(w) E E + (2
(1))
E E + 4E,
(w) B. Eyyli))
+ 2 (4) (W) + 2E k!! (0))
-22// E
+ 2 ki E 2E k (w) By
+ (4Eak) (w)
+ 2E
+ [E,
(w)
+ 22 (bnb(w)! (42)
(2Egk) (w) E
+ 2 Ey (w) + 2E (w) E (w))
h2 E (w)
+ 2
(w) Ey (w) + 2E, (w) E (Np
(w) E,h, = =2(kg))
(w) E + E E. (w)
(w)
15 - E,y,0) - Eyy!au + E,y(
(w)
where we define additional notation Eyk(w) E k/w) E,k, (w) Ei k juj
(w)
(the notations for
Y are defined by analogy). For simplify, we denote k(r)) kis E.ck!() Ezb, Ey and
(o (54) -Ey! Enyg + (E,,(w), Hence combining Eq. 440 have 2n(n 4) 5) VarlnHSIC! ( (2)] (n 1)(n 2) - cuf Ea On (43)
E.,
Since under Hy. the bias lead by the difference terms between (ISIC("(() and HSIC (2) vanish faster than Eq. 443). hence the variance of HSIC (Z) identical. the following part, we consider
the empirical estimate of the leading term in Eq. (43). We estimate k.(w) with estimation of Es,, (K(42) ) is given by
then the
E(AxoAdd = A 2.) nt
(())(a))) - - - 2 1
(44)
n
where we define notions A, = /. Eu= (x().) Since computing the value of 1T (Ax requires O(r²) time complexity, we transform it into a more computationally tractable form. We perform the following calculating as
1 A '1 Tr(Ax T = TTAA
= -1
(45) Recall the definition of Axe := [AA that can be calculated in O(nD) time, thus the term [A] AxeAxelxx can be calculated in O(nD + nD2) time. As a result, we obtain the estimator (A (AA.AAx Ax.) x 21][1" (AfcAr.))
for the term Eig (k )² E,, (1())( )² that can be calculated in OnD22) time. The only thing left to do is determine the bias of the estimator. For readable,
we define 2/10) = 1h))) ((O) = 1 E. (w) and ((0))) = En,o k(w)
then by removing the terms
with i = j. a estimate with difference Onn 1) to Eq. (44) is given by
1
(w) R(w) Ri)0) + R(a))
Rig
(46)
n1
18

---

By comparing the difference between the expectation of Eq. (46) and E,y (k we can show that this error is bound by O(1/n). We illustrate this by taking one of the cross terms example and the other terms by analogy, as shown in the following,
E
E
k k(a))
n(n
1)
n
Q.
(47)
Σ
R(w) for
+0(m E.pi E Eih(( + O(n
(n)4
(5.g.,a)eiz
Similarly, we can obtain the results for E Ei, (1er))) j2. As result, we have shown that Vo a estimator of (mHzCCHS with bias Onn thus complete the whole proof.
F
Calculation of Eq. (16)
Here, we give the computational details of Eq. (16). We mark colors to indicate correspondences. According to Eq.
20
we can calculate Ejggr
1 as
Σ
(w) 134
Σ
(ki (w))(()) ii
+ (/4)) ((w)
(w) ((w)((w) 100
Σ
J.g.
M,0,0n
M,,,
(48)
k/
(1))
2
2 t
f,
We can further represent Eq. in matrices form
(w)
2
(AxA -A
iigor
J.g.r
+RIIAxAAAAA)
(49)
Next, by variable substitution, we obtain the result as
1 [n1"A1+ (I"C)B, (17 nE, nn, nD, 1 12D]
Σ (w) igr
J.g.r
(50)
where the definition of variables A to F with the calculation cost are given in the Fig. I convenience, we re-show the diagram here for reference.
For
A AjArlax
(ATAr)ATloN
[xx (ATArA))") Ioo
D= C/C
Time Complexity:
OlnD")
O
A$1 p... pA D.i
(A C== [Av(A)1)]ss
[Ax(A) (A
Figure 5: The diagram shows the definition of the quantities, with styles representing the time complexity of the computational process in the current box. G: the element-wise product.
The computational complexity of each step is illustrated in Fig. 5. We explain some steps here. As a start, recall that the size of A xx, Ay are both D. Therefore time complexity OnnD2) is required compute A A Ay by matrix multiplication operation. Further multiplying the obtained [A AyAAyp with AT requires O(nD²) time complexity. Next, since both Ax and (A (ATAy Ay AT)T are size n x D, the elemental product operation requires a time complexity way, we can check the time complexity for each remained step. After getting the variables A to F. since 1 ( A1, A all can be calculated (nD) and 1 I, 1 C, I''D all can be calculated in (n), we conclude that the results with index in Eq. (50) can be obtained in O(nD²) time.
(nD)). a similar
19

---

G Proof of Theorem 2
In this section, we give proof of the Theorem We first restate the Theorem 2 here.
Theorem 2 (Uniform Bound). Let Oz. Ot parameterize Tay To, in Banach spaces of dimension dæ, di- And To. To, are Lipschitz to the parameters Os, Ot with the non-negative constant Lx,, Lu, respectively. Let Or be a set of (0x, 0t) for which aw 2 c > O with a positive constant e. and [|0x.1| < Ro. |0:| I Rs. Let r denote the threshold, i..,, (1 a) quqantlle for the distribution in Eq. [7] and r())
be the threshold with sample size n. Let {(wk.g.
p/2 be the samplings of frequency with the sampling number D. Also, we define Buy == sup, |W Rui :- sup, || |l, dg = max(dx di3
and Ew = (Z). Then with probability at least 1 8. we have
Ew r //
EzEn- - -T//n / |
o 20 ((V
log n + ds
+ Rus La + R Li Ruulu) vn
sup ())e.)
72 log
Ow
n
Proof. We take a similar roadmap of proof as 30 and extend it to our optimization objective. The roadmap of the proof is as follows: we first obtain the convergence results (with sample size n) for each estimator with fixed parameters O2, 0z, and then extend the results to the entire parameter space via e-net arguments. We begin the proof of the first part, which is based on bounded differences inequality (McDiarmid's inequality) [4 Theorem 2.9.1].
Bound of س E-Ewl Recall the definition of &w HS) 1 Eigggg h (w) 'igrr By the definition of k(o) _(4), we have [k!=)] S 1, 1,44 S for all t, u, thus [h!/0) S for all i.j.g. Now we begin by showing the bounded differences property of h sggr Concretely, we replace the first sample 21 = (21, /1) with 2/ = (a4 v/) and keep the remaining samples the same. The obtained samples are named as Z' Then the difference terms between h 1 and the new substitution ((w) can only happen in the case that at least one of j. q. r is equal to I. For the case that only one subscript is 1 (here take i = 1 for example), combining Eq. (20), we have
Σ i.g.r
Σ ((W) 2 (n - 1) - 2) - 3) 6. 16 = 8(n 1)(n 2) - 3). (51) j.q.r
ljgr
4!
The whole contributes of remaining terms that at least two i, q, r are less than (nn-2) thus
(w) lj9r
Σ
(w) Aoor 4-
Σ
Σ M +0( = O(n 11). (52)
jjor
nd
nt
C....
J.g.r
j.g.
Hence HSIC.. satisfy the bounded differences property with Onn Using McDiarmid's inequality, for fixed Oo, 01, with probability at least 1 òd there exist a universal constant C₁ such that
1 log 3
[ww EEEw Ci CiV
(53)
Bound of (r(00) rwll As (n) is the (1 (1-al ai) of the distribution of new with sample size n under Ho. according to the Eq. (5) when n is large enough, there exist a universal constant C2 such that
2 log |EZEIl S C2y
log 1 1og
1/n S Ciyy
(54)
n
a
n Cx
where the last inequation is because EzE. (( under Ho (see Theorem for a detailed explanation). Hence |r(6r) O(Vnlog(1/a)) Also, by definition Te is constant related to a.
Bound of [03 031. In this part, We first obtain the bound of 1 - -Ezō01 then obtain the bound of E E 0.1- As before we start by showing the bounded variance property of o We replace 21 (f1,81 with z (w'. ví) and keep the remaining samples the same. The obtained samples are named as z'. For readable, we denote 03 with sample Z, Z' as 63 (Z), og (Z') respectively.
Recall the definition 03 == 1. Ejg.r (in )2 HSIC
Since | S 4, we have
1 n
2 1
Σ
8 T
Σ
1 (
K (w)
1
(55)
J.g.r
J.g.r
J.g.r
20

---

I
E
E
(w)
8
h
(w) biggr
(56)
nd
f.j.a.
Again, the difference terms between h higgrr and the new substitution h 'ger can only happen in the case that at least one of J. q. r is equal to 1. Hence, Eqs. 55 and (56) are both O(n=1). As result, o satisfy the bounded differences property with bound On n Using McDiarmid's inequality, with
probability at least 5, there exist a universal constant C3 such that 1
Ez
< C3v 1 log ?.
Next we obtain the bound of [Ez - oal. We rewrite Eg as
o 16
1
Σ
EI "ig
Σ "jgre""'grr"
Elb ( (2) (egge
n
(57)
"jgrj'g'r'
By adding further restrictions that i, v. q, r, ,','',,''' r' are all different, we can obtain the correspond- ing expression for o.. Hence the difference between them can only happen when at least one subscript j',, q', in j. r'
is equal to Combining |n |// S 4, we have [Ezō o?l O(n
c-net arguments. Next, we prove the second part with c-net arguments. Take the parameter example. We choose a cover with A TR) points {p:) (7)))) such that for any point p E O₁, we have min; ||p - pill I тк. According to [4] Proposition 4.2. 12]. by comparing the volumes, we have NN(O. rx) I (4Re,/ra)) As for the parameter space O of 8, we can also obtain a cover with (V(O,, r)) points that NV I (4Re//r)) Here, we set тк 4 / Vv, AR / Vn, thus (V rk) S (vn)ds, (.) (Vn)d,, Then combining the Lipschitz property as shown in Lemma we have with probability at least 1 -- 6,
space O2 of 0₂
2N by (()m))))))))
E EzEu S sCI sup (0,,,)EE.
log
&8R La Th + +8R,, Lan
2 + (ds + di) 2n
log
32 Re 32 La Re:
$ SC n
log 5
Vn +
vn
Hence when is large enough, there exists positive constant Cs. with probability at least
6,
1 + (d+ + di) log
Rw L Re,
Vn + Run Ia Re,
sup I E S Cs (8)
V log 8
+
(58)
Vn
Similar, when n is large enough, there exists a positive constant Cg. with probability at least
log z (de + d)) log Rwy LeRe
Ruw Lilie,
sup (9,,
-
ك Ca
+
(59)
Vn
Vn
Overall Bound. Now we combine the previously obtained results. We have
E -100 /n 0-
EzEn -wwn E.
11
EzE
Fw
(n)
Tw
+ EZE rw/nll
O
no
Since on 2c, Gw c, according to Eq. (59). we can make T.. c/2 happen by assigning probability
budget 0/2 when n is large enough. Also, combining Eq. (54). EzEw| < and rw is a constant related a, then with n large enough, there exist positive constants Cs, Co.
E 1w /n
EzEw -r//n ow
2 S.. - E
Cs
1
1
Co 2
log
2
(60)
Note that we need to pay for probability budget 5/2 for the above conclusion to hold. Then by taking the supremum both sides in Eq. (60) and assigning the remained probability budget 8/2 to Eqs. (58) and (59). we can show that when n is large enough, with probability at least 1 - 6,
E. -
(m) /n
EzE Tw/n
sup (8).))
Tw
(61)
log + (d+ + di) logn
Rw,, To Re, + Ruy L Re,
3 n
n
Vn
thus complete the proof.
21

---

H Proof of Theorem
In this section, we give proof of the Theorem We first restate the Theorem here.
Theorem 3 (Consistency).. Let f 0f be the parameters after learning, Z be the testing samples of size m, when EzHSIC (Z > O, then the probability of Type error
(Type II error)= = Pri (mHSIC (Z 3 Sr 0i 0i)~~ (mm-1/2)
(62)
Let the mapping functions with learned parameters 0g. of be Toz: Top and the corresponding range space be compact subset of RATz, " RdT,, respectively. Also, the diameter of two range spaces is denoted by diam(Top (T;:) ), diamm (To;): ), respectively. Let :[:)] be the frequency samplings with their second moment denoted by our := ==pp(ww)ul
Additionally, denote E. HSIC(X,,) Y), then under H1. we have EyHSIC (Z'c) > 0 with any constant log oun diami Tog dia,,
on == E (w
probability when 2 dTa +d
Eu
Proof. The proof consists of two parts, we first give the rate of convergence of Type II error under condition EzHSIC (zte) ( > O, and next for condition EzHSIC (Z > 0 we give lower bound on the number of frequency samplings required for to hold. To simplify, we denote the U-statistic HSIC(") (Zte) gd,) in this proof. We begin to prove the first part. With the learned parameters 6% f7, the probability of the Type II error given by
IP Type II error) = IHt, (mEw~ S 101m0100 01)
(63)
Combing the result of the difference between a and c!St) as shown in Eq. 334 we have
PHi (mE. S r (m)) 0h. 07
Prt. (me(") < <)(m) C 0% 01).
(64)
where Co is positive constant. To apply the rate of convergence of the Central Limit Theorem, rewrite the right equation in Eq. (64) as
VmieL"
EZES") (m)) //mm VmEEz + Co/ fo//mm/ 4o
PHi
0% 07
(65)
40
where the standard deviation (defined in Proposition D a > 0 under Hg. Then according to the results in [34, Section 5.5.1 Theorem B]. there exist nonnegative constant C1 such that
P (Type II error) s //m VmEEgS Co/vm
(m) Fw
C 1 3/2
(66)
40
mm
where un Eiiitar [n(e < oc. When m is large enough, we further have
P Type II error) क (C2 CaymEE C1/Vm) +Cs vm
(67)
where C2, Cg. C2 are positive constants and using (m) (m2 we prove in Eq. 54p. Hence ((w)
when EzEl") (u) > 0, the leading term VmEzzl" decrease as m increase. Further, to obtain the
decrease rate when m close to infinity, we consider the asymptotic expansion (when x close to negative infinity) for the function ((x) as given by
((x)
e
1+
Σ
1)th 1.3 3- 5... (2n 10n-11 1) (2x²)"
(68)
20
n=l
thus @ ((22 CaymEz (w) + Ca/Vm)=
1/2). (m22) As result, the decreasing rate is least
0112), We have so far completed the first part of the proof, and we next begin the second part of the proof, i.c. obtain the number of frequency samplings required for the condition Eze(") > 0 to
1/2)..
22

---

hold. For simplify. we denote (1) (x Ar(1)) Ac()') as (x, (()) (v. v)) respectively. Then according Lemma 2 we have
Ow,, Ow, diam (ow.diam(To)) (loam((Toz)
De2
P
sup
|k(W] (x, (x,
S 28
cxp
4(dT, + +2)
(69)
De
P
sup (y, 2 < 28 Lvy'Ey
exp
A(dT, + 2)
Also, we denote the bounds in Eq. 669 as 82 (e, D) 8g ()., respectively. Next we get the bound
between EzEw and HSIC(X, Y). According to Lemma the bound is given by
E2 HSIC(X,Y)) < 44
sup E.
[k(W) (x, (l)
k(a, x (')((/)/))
(70)
Since by the definition, for all (x,2²) E X X, (v.8') y x V we have (k(W) (x,,'') $ 1,
(y. $ 1, [k(x, x') s 1, [[. y') S 1. Hence we have
(ll) (z. x ( (u.y' y') - k(z, at [v v/ S (x, x') - k(x,2')1 + (v. 1(y 11)) (71)
Combining the results of Eqs. 77 and 71 we obtain
(229)) (OOO)-HIICH HSIC(X, Y) 4. sup
[k((=] (ar, k(r x') +4 sup
(1()) v/) 1(v.//)) (72)
x,,'EX'
v.y'Ey'
Combining the results as shown Eq. 669 and allocating the probability budget e, we have
P sup E.
E2 E(w)
HISIC(X,Y)1 55.(e/8, + 6,(c/8, D).
(73)
By setting Eu/2, and since & O under H1, we conclude that Ezgd constant probability when D Ω dr, tdT
0 holds with any
log Tue diam Tog to diam diam(To;
<a
&u
In the proof of Theorem 3, we obtain the convergence bound of the statistic Ez convergence result for its estimation can also be obtained, as shown the following Corollary.
(u) Actually, the
Corollary (Approximation Error Bound of (ISIC.,Z's)) Maintaining the same conditions and notions as in Theorem 3, we have the uniform convergence bound of HSIC as
P
HHSICu(Z')) HSICA(Z 2 { XXX
sup
S ōn(e/88 (14/8,,)) D) + 6y(e/8,
(74)
Proof. By the definition, we have for all i, q,
(w)
S 1, |1!ي) < |ky - 1, [451 S 1, thus
1 or higbgrl
(w)
(w)
Bey || |Rig ( lgrl I |k!0 kayl + [T(0)) lprl-
(75)
Then according the results as shown in Eq.
699 we have for all j,
(w) 1e ((0) kigharl 2 5 (E)2,
P
sup B.N
(76)
2112 EX
Recall the definition of h (w) 1 Σ (1.iaar))
h 11
(t, (/W) (ww) ((w) - (w) (()) and further define (w)
the corresponding hijor Σ (,)) keedee + kendon 2kuolsvr then for all i,
IP sup
In
(w) iigr
hizgrl 26 5n(e/8, + 8y(e/8, D).
(77)
ey
After that, using the expressions that we obtained before, i.e., HSIC (Z = + Endgr Mo) and
HZe), = 2 Enjaa hijgrs we obtain the final bound that
P sup
HSIC, (Z')) 26 < 5,(1/8, D) 5, D).
(78)
2"EXxy
and thus complete the proof.
23

---

I Smoothness of Optimization Objective
We first prove the Lipschitz property for some functions. For ease of reference, we re-list here the def- initions of the terms that related to the optimization objective: Ew == HSIC = /े Enj.e Niggr
- == 16 E Ej.g.r k HSIC (2) and où == 16 E, (E g. ( (Ez (w) The Lipschitz property of these terms are shown as follows.
sgore)
Lemma 4 (Lipschitz Property of of Ew: EzEw. Cn ob). Maintaining the same conditions and notions as in Lemma we have the following Lipschitz property
(0k, 01) - (0,, 01)l I &R Lus 1 - 0/6l + R Jn. 110 - Bill,
(O,, 01] Ez (2 (0%,01)) 0111 S &R La ||0 0% + &R Li ||0 Bi1,,
(79)
(0,, 01) 62 01) S Rw,, I.k 100 0% + 1024 R,,, I |10 0ill,
1o2 01) o² (0% 81) & 1024 Lx 110p - 6%,l + 1024R L1 ||0 - Bill.
where we use the symbol Ew (0sz 01) denote Ew with the parameter 0z, 02 and the others by analogy.
Proof. We start by obtaining the result of (w) for all i. Since for all i, g.r.
M (Ox ) (0t) k//0) (OW)2 (001s | (0x) k. (0+1++ (0))
(0))
(80)
where the property [R.(²) S 1 and (//2)) I 1 are used. According the Lemma we have
(w) by (0L) (w) ij (0w)== 2 Run. I+ 110 - 0/ll, ( (0:) - (09) Ru, La 1|0: 6ill 1 E (3.3...))
(81)
Combing the definition that h hig = 41 (1,a,,))))
((w))(W) + k/w [( - 2 ((4) then
Mod (Ox, B:) - h now (6%, 87] S &Ru, La 110p f/ll - 8R L 110: fll
(82)
Also, combining the definition of &w == HSIC (Z) = no Eiggg Ensarr blody we obtain
(0k: 01) (6%: 0() S 8R Ls =10 0/11 + SR,, Li 10: 8111-
(83)
By using E2l5w (Ox: 0:]] - (2 8/] < Ez B2l1Ew (Ok: 01) - (6/. 1))l we have
EE (0p, 0:]] Ez (0,, 0]] 8R Lx 11 0% + 8 & Li 110 0'll-
(84)
For the results of 02 o. we first proof the following results. For all i,j, r, '', d' r', we have
[ (Ok, 01) 01) (0x. 0t) (god (0%, 00 (0%:
< 4 p (On, 0t) jor (%,, 011 + 4 / (0z, 01)
(w)
(w) p (0 0,)
(85)
< 64R Lu 110g 0%1l + 64R La |10: 0/1
where the first inequality holds due to property (w)
< 4. Then we use the expression
0 = 16
Σ
(w) Bige o'
Σ
(86)
n
and combine the results in Eq. (85). As result, we obtain that
(0,, 0:) a3 (0,,
0)1 < 1024R Lx 110, - 0/1l + 1024 Li 110 0'11-
(87)
In a similar way, we can obtain the corresponding expression of oă as
2 16 Exianss of . hig / - Biiinnn 1 (w) (w)
(88)
Then we obtain a similar result before, i.e.,
(0,, 01) - (0%, 03) S Rw La 110 0211 + 1024 L- 110 - 0,1
(89)
which completes the proof.
24

---

Also for the term associated with the estimated threshold (recall that it is computed from the first two moments), we obtain the following properties of Eg, Vo defined in Theorem I
Lemma 5 (Lipschitz Property of of &g. Vo). Maintaining the same conditions and notions as in Lemma we have the following Lipschitz property
(0k. O1) - Eo,,,, 8i1 S 20 Lx -10 0/1l + 20 L: 10, 0ill:
(90)
[V0(Os, B1) (o( 81) - 128C Rw, L -10 8/1l + 128C Rw, Iu 10: 0ill,
where the constant (n(n) = (n-1)) 1)2 and (1(n) == 1) (m= (0))n))((nm)))) 2)(m33)
?
(n(n-4)(nn1) (n
Proof. The expression in Theorem | while easy to compute, is not suitable for this part of our proof. We begin by obtaining equivalent expressions for Ep, Vo- According to Eq. (39), we have
1r(AxAx - 1
(A A I,)1
E =
nnnn 1)
n(n - 1)
(91)
17 (A(AxA)) n²
(Ay A
Co
n²
And for Vo, we use Eq. (5 and obtain
20
Vo=
[Tr(A T
HA
AT
(92)
2
Also, we define h Jggr
1 Σ
+ kew (w) (w) 2k k that corresponding to h (w) (idi...) keu kew
=
1
tjor
and also define h (0)
lggr
Σ
(6.g9.))
tu
((w) (W) ((w) [(m) 2 (()) Then can further rewrite
= Eiigo "ig and for Y by analogy. Then the properties of hi can also be obtained for hig and (1(0) e.g. I S 4, 4. < for all i,J.4, v. Next we start to prove the Lipschitz property of Ea, Vo- For Eo, according to Eq. (81 and
the term for as HAx
(w)
combining the results 0 S 12 A X S n² and that for Y. we can show that
Co n
Cu n
Eo(O2, 01) Eo(6%, 801 -
Σ b
1j (0x)
kggg (0))
Σ 0.
((w) or
(0) - (6)))
(93)
< 2C Rug La |10, 0/1l + 2Co Ruy Ln
|10 0il-=
where 1s
Ei. k/(0) by definition and so as for Y. And for Vo. we can prove that
Po(OR, 01)
Vo00%' 07)
20
<
Σ
|n (Ox: 0z) 2 (On, 01) - nig (%, 01) 0,1
(94)
n
128C Rw, La
||0,- 0,1l + 128C; Ru, L ||0: 0/11
where the last inequation obtained similar to Eq. 85)) thus completes the proof.
The following results extend the results in 30 to the more general case (we only restrict the mapping functions to satisfy the Lipsehitz property, and thus include the Gaussian kernel case of their proof). Theorem 4 (Smoothness of Optimization Objective). Let the sample of size n. be Z, and with small positive constant c, let the set of the parameters be O == {(Ox, 01)lo 2 Vo 2 c, E,E 2 c}, then there exist nonnegative constant L such that V (1) || < L on O., where the optimization objective J == (Z) - -Ca/n//ā, / a is that we used in practice.
Proof. According to Lemma 4 we have shown that HSIC (Z), T. both fits the Lipschitz condition. Also, according to Lemma 5 we have shown that Eo. Vo are also Lipschitz with respect to 0g. f Since the threshold CN is completely determined by these two moments, combining the smoothness property of the mapping from two moments to thresholds as analyzed in [30 Theorem 2), we obtain that eg is also Lipschitz with respect to Oz, O2 on +., As a result, we complete the entire proof based on the Lipschitz property of composite mappings.
Remark. Eo and Vo are positive is almost satisfied in practice since according to the definition only Ay.) 21 need to be greater than 0.
[1" A 1|1 A 1 and [1"(A), (A) Axx) (AT
25

---

J Details of Experiment Setup
In this section, we give an introduction to the comparison methods in our experiments and provide the implementation details of each method.
J.1 Details of Comparison Methods
The methods of comparison used in the experiment are described below.
dCor 13
An independence test that is based on the distance covariance.
QHSIC [1:
The original quadratic-time HSIC independence test.
The randomized dependence coefficient that measures the independence using the canonical correlation between finite set of random features of the copula.
RDC 26
NyHSIC
44
variant of HSIC that uses the Nyström method approximate kernels.
FHSIC
44
A variant of HSIC that uses the random Fourier feature approximate kernlls.
BHSIC 44 A variant of HSIC with the block- based statistic.
HSICAgg
An aggregated kernel test with the incomplete statistic of HSIC.
A test uses the normalized version of the finite independence criterion and chooses features on a hold-out validation set to optimize a lower bound on the test power.
NFSIC 18:
Below are the GitHuub URLs for each comparison method.
dCor:
http:s//pppp.orr//pppjstcccc
RDC:
NyHSIC: hwtp:////ss//..oco////////////// FHSIC: http://whhh..iiiio/cc/crrerrrrrr BHSIC: httpg//:sss/aaaacccoo//////////a
NFSIC: hBtc://pwsgggta.ooo/////aaaaaaas
Time Complexity. Among them, dCor and QHSIC are the tests quadratic complexity with sample size i.e., (n²). RDC is calculated in log n) and the rest are linear-time tests, i.e., O(n).
Threshold. For dCor, QHSIC, RDC, NyHSIC, FHSIC, and BHSIC, we permute the samples 100 times to simulate the null distribution and compute the threshold. The thresholds for the remaining methods are obtained by asymptotic null distribution, i.e., we set the test threshold to the a)- quantile of x² (J) for NFSIC and obtain the test threshold of LFHSIC-G/M by gamma approximation.
Details of Setup. The number of random features for FHSIC, LFHSIC-G/M, the number of induced variables for NyHSIC, the block size for BHSIC and the number of sub-diagonals R for HSICAgg all kept consistent recommended in 44 for fair evaluation. Specifically, set the number of random mappings in RDC to 20 to ensure compatibility with large-scale datasets. The test location parameter J of NFHSIC is blindly increasing J may lead to loss of power as shown in [18] and can significantly escalate time costs due its cubic time complexity O(Ja). In the optimization step, for stabilizing the training, in the implementation of NFSIC we determine the initial bandwidth by searching the best from 25 bandwidth combinations (including the median bandwidth combination). For LFHSIC-G/M, to be fair, we perform the same grid search on SD, Sin, and GSign datasets. In other experiments, we still use the median bandwidth as initialization for LFHSIC-G/M Also, the maximum number of iterations for the optimization is set to 100 for NFSIC and LFHSIC-G/M. The default learning rate of the optimization of LFHSIC- G/M is set as 0.05 in all the experiments. As for HSICAgg, the default implementation of the predefined 25 pairs of bandwidths in its code is used. For synthetic data, we set the split ratio to 0.5 for NFSIC and LFHSIC-G/M, i.e., we randomly sample half of the data for training and use the remaining for independence testing, while the other methods use all data for testing. For real MSD data, we divide small portion of the data for training and then extract 100 random subsets of the remaining data (disjoint from the training set) for evaluation.
default 10, since differs from other approximation methods that
26

---

0.0 J.2 Details of Datasets
The details of the four synthetic datasets and two real datasets are described below.
Sine Dependency (SD): In this model, X follows a d-dimension multivariate normal distribution (0, Ta). and Y is defined as 20 sin (4x + x2))+ +Z, where X; is the i-th dimension of X, and Z (O, 1) represents independent noise. Notably, when d > 2, Y exhibits nonlinear relationship solely with the first two dimensions of X.
Sinusoid (Sin): This model introduces a localized alteration in the probability density function
Pay over x V == [-т, π specified as (X, ~ (z,((z8) y) x 1+ sin(wx) sin(wy), where w denotes the frequency. Increasing the frequency enhances the similarity between the sampled data and that drawn from Uniform{[ (- n, π)²), thereby augmenting the challenge of detecting dependency with limited sample sizes. An example visualization is shown the left of Fig.
Gaussian Sign (GSign): In this model, X follows d-dimension multivariate normal distribution No Ia), and expressed as Z IT sgn( X;), where sgn(+) represents the sign function, X; denotes the i-th dimension of X, and Z AN(,, 1) independent of X. The challenge lies Y being independent of any proper subset of X but dependent on as a whole, underscoring the importance of considering all dimensions of X simultaneously in independence testing.
ISA Dataset. We construct the data through the following steps: First, we generate i.i.d samples of two univariate random variables with a mixture of Gaussian model, i.e. | 0.01)
[1,, ). Second, we mix these random variables using rotation matrix parameterized by an angle 9, which varies from 0 to 7/4. A zero angle implies independence between the data, while a larger angle signifies stronger dependency. Third, we append noise with a distribution of (O, Ja-1) to each of the mixtures. Finally, we multiply an independent random d- dimensional orthogonal matrix to obtain vectors dependent across all observed dimensions. The resulting random variables and Y are dependent but uncorrelated. When is greater than 1, the problem is associated with the independent subspace analysis (ISA) problem [14]. For the case 1, = x 1/10, an example visualization is shown in the middle of Fig.
3DShapes Dataset. This dataset [S] comprises images depicting 3D scenes, complete with additional features like shadows and backgrounds. It encompasses six fundamental latent factors: floor hue, wall hue, object hue, object scale, object shape, and orientation, all adjustable to generate corresponding images. Orientation is treated as dependency factor for independence testing, where we test the dependency between the image X and its orientation Y. To heighten the challenge, maintain the object shape ball, minimizing the apparent orientation feature compared to other shapes like squares, while randomizing the remaining factors. An example visualization given on the right side of Fig. 6
Million Song Dataset. The dataset, a subset of the Million Song Data 4 comprises 515, 345 songs with 91 91-dimensional features. The first dimension represents the release year of each song, designated as variable Y. while the remaining features (e.g., timbre average and timbre covariance) form variable X. Our objective is to identify the dependency between X and Y.
n= 5,00000,00 W =2
n 1000, m/10
YIOvientation)
2
Fioor hus
Wail Taae
X0rragel
Object shape Qualt)
-2
-2
-2.5
2.5
-2
X
Figure 6: Examples of visualization of samples from different datasets. The two plots the left correspond to the samples and their contour under Sin dataset (n = 5000, w = 2), and ISA dataset (n 1000, d = 1, π/ /0),, respectively. Right: a visualization of the causal diagram of the data generation process and some generated examples.
Million Song Data subset:
ics wusssuuci htt.://cww.....eaaaaa...aaeeeeaa
27

---

K Additional Experiment Results
In this section, we provide additional experimental results, mainly including the visualization results on the Sin synthetic dataset, the results with comparing methods (as explained in the main paper, due to the high time overhead therefore do not participate in the evaluation the main paper) well the running time of each method.
K.1 The visualization results on the Sin model
We provide the visualization results the Sin synthetic dataset to illustrate the performance of our optimization objective for the example mentioned in the main paper. The results are shown in Fig. where the setup follows our experiments (n 2000, w 5, D 100). For visualization, the negative of our optimization objective J is shown. As can be seen, our optimization objective guides to letting the bandwidth adapt improve the test power, and here with bandwidths around 0.2 (corresponding to the theoretical optimal solution in our main paper) indicate better power, thus corroborating the validity of our optimization objective. Also, notice that the landscape is smooth over a wide range as demonstrated in Theorem 4 and thus contributes to non-convex optimization.
see that regions
n 2000,
-2
X
Figure 7: The visualization results on the Sin model. Left: the samples with n =2000, w = 5. The visualization of the landscape of the negative of our optimization objective (D 100).
K.2 Additional experimental comparisons
As mentioned in the main paper, the method") 30 is not involved in the comparison because it takes too much time to run in some settings. Here, we compare it with ours under some feasible settings to illustrate the improvement of method power-runtime trade-offs. The methods using Gaussian kernel with global width and Gaussian kernel with widths each dimension (corresponding with ours) are employed, referred to QHSIC-O and QHSIC-W, W, respectively. For fairness, the same grid search procedure is employed as the initialization of the optimization. We perform the evaluation on the SD data and plot the results of the test power over time shown in Fig. g Also. for our methods, we provide the results under the setting D = 100 and = 500 as in the main paper. The experiments are conducted with the same equipment, specifically 6-core CPU with 3080 GPU.
Results. Our test consistently results in better power-runtime tradeoff at different D settings. At D 100, one test can be completed in less than second when the sample size 6000. As D increases (D = 500), the number of samples required to achieve the same power decreases, but the increase in D leads to overhead in runtime, and overall our test is still completed in a few seconds. In contrast, even though QHSIC-O/W requires fewer samples to reach the same power than our tests, the runtime rises rapidly the sample size increases. When 1000, it already takes more than 10s to perform a test. When n = 3000, it needs nearly a minute to perform a test, which may greatly limit the practical application.
'The code is downloaded from httppp///ggtaab...mmmm///iiiiiia
28

---

1.0
n=4000
Test power (T)
n=4000
66000
X-x
n=4000
n=3000
0.8
n=2000
0.6
4=4000p
n=1000
QHSIC-W
LFHSIC-G D=100
0.4
n=200
LFHSIC- M D=100
LFHSIC-G D-500
n=1000
*
LFHSIC-M D=500
0.2
0.7
1.0
2.0
3.0
5.0
10.0
20.0
40.0
60.0
Average running time (s)
Figure 8: Time-power trade-off curves the SD dataset.
K.3 Running Time
In this part, we evaluate the running time of each method on ISA datasets d = 10. We set D = 100 and plot the results of the running time versus sample size n as shown Fig. 9 Shown on the left are the results of tests with (n)) and On log n) time complexity. Since the quadratic time complexity test cannot handle large-scale inputs of 100,000 sample size (excessive runtime and large memory overhead to store the kernel matrix), we evaluate them separately on the right. The experiments are all conducted on the same equipment, specifically a 14-core CPU with 4090 GPU.
RDC
200
dcor
Running time (s)
50
NyHSIC
BHSIC
Running time (5)
QHSIC-O
QHSIC
40
FHSIC
150
QHSIC-W
H5iCAge
LFHSIC-G
30
NESIC
100
-X- LFHSIC-M
LFHSIC-G
LFHSIC.M
50
10
0
0-
20000
40000
60000
80000
100000
2000
4000
Sample size
Sample size
Figure 9: The running time curves with sample size the ISA dataset (d 10).
Results. The experimental results on the left show that our method is faster than other methods with optimizable options (HSICAgg and NFSIC), and can complete test within 10 seconds even with 100, 000 samples. Even though HSICAgg uses parallelism to optimize the computational efficiency of the scheme, the actual implementation of the parallelism high time overhead for single practical test. For the results the right, it can be seen that the quadratic complexity methods face dramatic increase in time overhead as the sample size rises, and this is especially severe for the methods (QHSIC-O/W) that need to be optimized since the optimizing objective needs to perform multiple squared complexity operations. In contrast, our linear-time learning objective allows us to handle huge data samples very efficiently.
mone-consuming, and hence leads to
L Limitations and Broader Impacts
Limitations. According to the experimental results in the main paper as well as in the Appendix, no one method is better than the others in all settings, it is important to choose several appropriate tests for real scenarios and summarize their results order to obtain a more reliable conclusion.
Broader Impacts. This work proposes novel framework for independence testing. The proposed linear-time optimization objective can be trained end-to-end in a data-driven manner, ensuring both effectiveness and efficiency in high-dimensional and large-scale scenarios. This could be beneficial for developing more reliable downstream algorithms in a variety of areas, including causal discovery, feature selection, and deep learning.
29

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: I've clearly stated the contribution.
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is 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: See the Sec. D in the Appendix.
30

---

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 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 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 few datasets 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 of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers penalize honesty concerning limitations.
will be specifically instructed
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: See Sec. in the main paper. Also, the summarized assumptions and the proofs are provided in Appendix.
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.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide the details to reproduce the main experimental results, please See Sec. D in Appendix, and we also provide the experimental data/code in the supplemental
material.
Guidelines:
31

---

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 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 specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a 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-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide the experimental data/code in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
wow.eeuuubissiooooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "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 NeurlPS code and data submission guidelines (https c/tpps.cc/public//uue
CodeeSumiiii wwabbbmssssiinii ssionPolicyy 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 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).
32

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
we provide the details. See Sec. Jin Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. 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: [Yes]
Justification: The experimental results are accompanied by statistical significance tests. See Sec, D
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence 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 library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 96% CI, if the hypothesis of Normality 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 range (e.g. negative еттог 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 the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide sufficient information on the computer resources. See Sec. Appendix.
K
in
Guidelines:
The answer NA means that the paper does not include experiments.
33

---

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 compute required for each of the individual experimental runs well 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://pe..aaaaapcoooooo/o/aaaaa
Answer: [Yes]
Justification: I read it.
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 of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See the Sec. L in the Appendix.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.. 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 unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: [TODO]
34

---

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 challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
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: [Yes]
Justification:
We cite the methods used and list the URLs of the comparison methods.
Guidelines:
The answer NA means that the paper does not 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 used and, 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 (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paaerssithcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should 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 assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or 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, if applicable, as well details about compensation (if any)?
35

---

Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: 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 (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does 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.
36


Reviews:
[{"review_id": "9ORZODHwBf", "reviewer": "Reviewer_X3Av", "summary": "The paper presents a novel consistent estimator for HSIC, which is computationally efficient, and tries to maximize the testing power under controlled type-1 error. The idea is to begin with a known relation between HSIC and Fourier-based distance between the relevant characteristic functions. The estimator can be understood as a sample based approximation of this. For standard kernels, it is noted that the distribution from which the samples need to be generated is from a Gaussian. In general, it is assumed that a transformation of variables converts this distribution as a standard Gaussian. It is shown that this estimator has linear computational complexity, for given transformation parameters.\n\nFurther, it is proposed to learn the transformation's parameters (which in turn is same as learning the kernel parameters). And the objective for learning is proposed to be maximizing test power under controlled t1error. To this end, using asymptotic convergence arguments, an expression for this objective is analytically arrived at (prop1). It is discussed how to estimate this objective again in linear time (theorem1). Consistency of this objective and the overall estimator are are proved in theorems 2,3.\n\nSimulations on synthetic and benchmarks datasets show the improved test power and computational complexity when compared with existing baselines.", "questions": "few minor comments:\n\n1. notations at places is a bit confusing: e.g., line 121, 146 w_x means different etc.\n\n\n--- after reading the author responses and other reviews I increase my score.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The idea of sample based estimation of the Fourier-characteristic function based HSIC equivalent seems novel. This is also interesting because it leads to linear time complexity.", "weaknesses": "1. It would have been nice if the introduction section had more description of the methodology at an intuitive level. Currently, most of the introduction is motivation, related work and the actual methodology is restricted to one small para. This would give the reader a intuitive understanding and help to understand the later sections easily. Without this it took me some effort to understand what is happening in the overall methodology. (I may be still missing some important points?)\n\n2. The derivations and the main algorithm in section 4.2,4.3 have a very close resemblance with [30] https://proceedings.mlr.press/v238/ren24a/ren24a.pdf . This significantly weakens the contribution and novelty. More importantly, main details in this section could have been cited from [30] or postponed to Appendix. The current presentation seems to give an impression that the sections are entirely new.\n\n3. Since [30] is a close methodology, empirical comparison with it seems to be crucial. However this seems missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. We’ve made a point-point response to your comments. We hope that our feedback can clarify most of your concerns or misunderstandings, and we are looking forward to further discussing with you on any issues about our work.  \n\n***W1***: It would have been nice if the introduction section had more description of the methodology at an intuitive level. Currently, most of the introduction is motivation, related work and the actual methodology is restricted to one small para. This would give the reader a intuitive understanding and help to understand the later sections easily. Without this it took me some effort to understand what is happening in the overall methodology. (I may be still missing some important points?)\n\n***Response to W1***: Thanks for the suggestion. Actually, combining the last two paras of our Introduction section, you can get a deeper and more complete understanding of our work. Anyway, we will add a more detailed introduction to our method in the Introduction section of the revised manuscript. \n\n***W2***: The derivations and the main algorithm in section 4.2,4.3 have a very close resemblance with [30] https://proceedings.mlr.press/v238/ren24a/ren24a.pdf . This significantly weakens the contribution and novelty. More importantly, main details in this section could have been cited from [30] or postponed to Appendix. The current presentation seems to give an impression that the sections are entirely new.\n\n***Response to W2***: Our paper and [30] may appear some similarity in presentation and writing style, this is primarily due to their goals are all to maximize the power of the test, a concept also applied to other tasks as in [1]. However, presentation and writing style are not necessarily relevant to contribution and novelty. Actually, there are **significant differences between our work and [30]**.\n\nFirst of all, the motivations of the two works are different: [30] focuses on solving the kernel learning problem but retains a time and space complexity of O(n^2), thus cannot used in large scale setting. In contrast, **our work aims not only to solve kernel learning but also to ensure that the final test can efficiently handles large-scale data, as outlined in the introduction (lines 44-47).**\n\nSecondly, their methods are different. Our method involves **designing both new statistics and criteria for kernel learning.** For example, while [30] derives results based on the asymptotic distribution of HSIC_b , our work is based on HSIC_w. \n\nThirdly, our method has a **significant advantage over [30]**: the criteria used in [30] have a complexity of O(n^2) in both time and memory, whereas our criteria for learning are designed to have a complexity of O(n). This is a significant advance! This makes our method can efficiently handling large-scale datasets.\n\n[1] Liu, F., Xu, W., Lu, J., Zhang, G., Gretton, A., and Sutherland, D. J. (2020). Learning deep kernels for non-parametric two-sample tests. In: International Conference on Machine Learning (ICML 2020), pages 6316–6326. PMLR.   \n\n***W3***: Since [30] is a close methodology, empirical comparison with it seems to be crucial. However this seems missing.\n\n***Response to W3***: As we pointed out above, our work and [30] addressed the same problem, but they are different methods with different contributions. And actually, we HAVE conducted extensive empirical comparison between our method and [30]. Please check Lines 260-262 in Section 6: \"Additionally, for the comparative methods [30] relevant to us, due to their high time overhead and inability to handle some evaluation settings, we separately provide a comparison with our method under certain feasible experimental settings. The results are given in the Appendix.\" .\n\n**Due to space limit, we moved the detailed empirical comparison results to Appendix K2 and K3.** Our conclusion is that \"Our test consistently results in a better power-runtime tradeoff at different D settings.\" (Appendix K2, line 855). The key advantage of our method over [30] is in computational efficiency: our criterion for learning has a time complexity of O(n) compared to their O(n^2), and our method requires O(n) storage versus their O(n^2). \n\nAs shown in Appendix K3, their method takes over 200 seconds for one test with a sample size of 5000. Given the need to evaluate methods on larger settings (ISA 10000, 60000) with 100 repeats to determine the rate of type I and type II errors, [30] cannot handle these settings. In fact, when n=60000, the memory required to store the kernel matrix of size 60000x60000 in [30] is impractical for general devices. In contrast, our test can \"complete a test within 10 seconds even with 100,000 samples.\" (Appendix K3, lines 870-890), enabling us to handle large datasets very efficiently.\n\n***Minor Comments***: notations at places is a bit confusing: e.g., line 121, 146 w_x means different etc.\n\n***Response***: Thanks for pointing this out, we will add some details to explain in the new version.", "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": "s3hOT1DPtu", "reviewer": "Reviewer_gka3", "summary": "The paper proposes a novel method of estimating HSIC to determine the independence of two random variables. The original formulation HSIC_b is reformulated and approximated using Monte Carlo integration, HSIC_w, with frequency samples. This reformulation was not derived by the authors but was borrowed from previous literature. The authors’ contribution is the sampling of frequencies proportionally to the inverse Fourier transform of kernel functions.", "questions": "Could you provide a detailed description of the objective J, Type I error, and test power used in the paper?\n\nPlease explain if we can use k(Tx_1, Tx_2) instead of using the proposed method.", "limitations": "The authors presented an interesting algorithm, but there are several notions that are unclear.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The formulations derived in the paper are mostly reasonable. When the inverse transform of the kernel resembles the equation of well-known density functions, HSIC can be approximated using frequency samples. For that kind of kernels, Gaussian (or Mahalanobis) and Laplace kernels are introduced. For other kernels, it is not clear whether their inverse Fourier transformations can result in the form of well-defined probability density functions. Even for Laplace kernel, domain of w_d is not provided, and its density function for frequency sampling is not well-defined.\n\nOriginally, the calculation of a pair of samples could be calculated using a single equation, but it is designed to be calculated using samples. It looks like an unnecessary additional cost, but the calculation of nxn matrix multiplications finally have been converted into the calculation of DxD matrix multiplications as in Eq. 10, and I enjoyed reading the conversion of the equation. The matrix multiplication for the calculation of original HSIC costs O(n^3) with the number of data n, but the proposed method provided an algorithm O(nD^3) with the number of frequency samples D. The calculation should significantly reduce the cost at the expense of the accuracy.", "weaknesses": "The proposed estimation is novel, but there are several downsides of the paper. \n\nMany explanations are simply provided without proper self-contained information. First, the purpose of constructing criterion J is unclear. The introduction of $c_\\alpha$ is unclear. Second, the definition of Type I error for evaluation is not provided. Type I error is for the false positives. What is the definition of positive decisions in the experiment? What is the test power in the experiment? Those concepts are used without definition.\n\nThe authors used neural networks for T_\\theta x. Conventional HSIC can also use similar transformation of x. For example, k(T_\\theta x, T_\\theta x’) can be calculated directly with a learned transformation T_\\theta x. The results do not necessarily support the superiority of the calculation in the frequency domain.\n\nIn the experiments, I expected to see the consistency of the proposed estimator with large D, which is not provided.\n\nIn theory, the convergence is derived for E[HSIC_w], not for HSIC_b. \n\nMinor comments:\nIn the last line of Algorithm 1, HSIC_b should be HSIC_w.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed comments. We’ve made a point-point response to your comments. We would appreciate that you can check our feedback. We hope our feedback can clarify most of your concerns, and we are looking forward to your further questions.  \n\n***W1***: About criterion J , $c_\\alpha$, Type I error, and test power.\n***Q1***: need a detailed description of J and concepts.\n\n***Response to W1, Q1***: \n\n1) *About the purpose of constructing criterion J and $c_\\alpha$*\n\n**Note that the purpose of constructing J was clearly described in Sec. 4.2 (lines 161-162): “Next, we model the behavior of $\\text{HSIC}_\\omega(Z)$ to obtain an optimization objective for maximizing the power of the test.” Furthermore, the derivation of J is according to the motivation for constructing J (Section 4.2).** Here, we make a summary of the derivation process.\n\nBy the definition of test power, we first model the power theoretically as in Sec. 4.2 (lines 166-172), which have three terms. We then try to obtain an estimate, which is actually the criterion J defined in line 203.\nThe criterion J consists of three main terms:\na) Estimate of the Statistic: the term is an estimate of the test statistic, as given in lines 177-178, Sec. 4.2.\nb) **Threshold $c_\\alpha$: This term is used as the threshold for the test to control type I error and is calculated using the two moments of the distribution under the null hypothesis H0. (lines 185-190, Sec. 4.2).**\nc) Variance Estimate under H1: The remaining term is the estimate of the variance of the distribution under the alternative hypothesis H1 as given in line 194, Sec. 4.2.\n\nAfter defining J, we use it for learning the parameterized kernel as described in Alg. 1 (lines 4-7, Sec. 4.3). This process ensures that the kernel is optimized to enhance the power of the independence test while controlling for Type I error.\n \n2) *About Type I/II error and test power*\n\nActually, **Type I/II errors and the test power are ordinary concepts in independence tests, and we describe these concepts in Sec. 2 (lines 78-80)**: “Two types of errors may occur in this procedure. Type I error occurs when $\\mathcal{H}_0$ is falsely rejected, while Type II error happens when $\\mathcal{H}_0$ is incorrect but not rejected. A good test needs to control Type I error while maximizing the testing power (1-Type II error).” and their evaluation can also be implemented according to the definitions provided.\n\nIn experiments, we evaluate Type I/II error and test power, as follows:\n\n**Type II error evaluation**: 1. Generate Dependent Samples: Create pairs X and Y that are dependent. 2. Test Execution: Record the results—*0* if the test return \"X is independent with Y\", *1* otherwise. 3. Calculate Error Rate: Repeat 100 times, and compute the mean. If 20 out of 100 results is *0*, the Type II error rate is 0.2.\n\n**Test power evaluation**: The test power, therefore, is 1− Type II error rate, which in this case is 0.8.\n\n**Type I error evaluation**: 1. Generate Independent Samples: Create pairs X and Y that are independent. 2. Test Execution: Record the results of the test—*0* if the test return \"X is independent with Y\", *1* otherwise. 3. Calculate Error Rate: Repeat 100 times. If 5 out of 100 results is *1*, the Type I error rate is 0.05.\n\n***W2, Q2***: About k(T_\\theta x, T_\\theta x’). \n\n***Response to W2, Q2***: Absolutely, the idea you mentioned is NOT acceptable, as it **has the same time and space complexity O(n^2) as the \"conventional HSIC\". In contrast, our method has linear complexity, due to our calculation in the frequency domain.**\n\nSpecifically, after obtaining T_{\\theta} through our learning process with the criterion J, our next goal is to use it for computing the statistic for the independence test. \n\nIn your idea, by computing k(T_\\theta x, T_\\theta x’) and estimating it with samples to get the statistic. **This will result in a complexity of O(n^2) in both time and memory, similar to the \"conventional HSIC\".** \n\nIn contrast, **performing calculations in the frequency domain provides significant benefits.** Specifically, it allows us to compute the statistic (as in our Eq. (10)) with a complexity of O(n) in both time and memory. This advantage clearly demonstrates the superiority of our frequency domain approach. \n\nAdditionally, we should **point out that your question presupposes the acquisition of learned T. However, accomplishing this step efficiently is also a major contribution of our paper.** Furthermore, our criterion for learning T is designed to straightforwardly model the test power of our statistic, making it a better match compared to your method.\n\n***W3***: about the consistency.\n\n***Response to W3***: Actually, **the consistency of the test has already provided in the experiments. In the experiments (Sec. 6.1, Lines 292-293)**, we state that “In addition, as the sample size increases, the test power of LFHSIC-G/M is gradually converging to 1 in both settings, which corroborates the results of Theorem 3.” This observation conforms to the consistency of our test.\n\nTo be more detailed, **the consistency of test is defined as “the power of the test tending to 1 as the sample size increases” (Line 235).** The theoretical result of consistency is provided in Theorem 3 (Line 237). This theorem formally concludes that under certain conditions (D is sufficient large), our test can reliably detect dependencies as the number of samples grows, ensuring that the test power approaches 1.\n\n***W4***: In theory, the convergence is derived for E[HSIC_w], not for HSIC_b.\n\n***Response to W4***: Actually, in theoretical analysis, we **derived that HSIC_w converges to E[HSIC_w] as in Line 601, and derived that HSIC_w converges to HSIC_b as in Corollary 1 (Line 686)**. Additionally, the relationship between E[HSIC_w] and E[HSIC_b] can be derived since |E[HSIC_w]−E[HSIC_b]|≤E|HSIC_w - HSIC_b|. \n\n***Response to minor comments***: Thanks for pointing this out, we will fix it in the revised version.", "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": "LD45UEG7cK", "reviewer": "Reviewer_uRf4", "summary": "The authors propose to extend RFF with parametric transforms of the Fourier features of shift invariant kernels. A path similar to the seminal work of Gretton et al 2007 is followed, where the proposed $\\text{HSIC}_\\omega$ statistic is shown to converge in distribution to a Gaussian with the true mean (under the null). Then, linear time estimates of the first two moments are provided, which are needed in vanilla HSIC to analytically compute an approximation to the critical region.", "questions": "I had difficulty following the implications of Theorem 2, given its (reasonably) over-packed formulation and I believe that a couple more sentences explaining the involved quantities would make it easier to read.", "limitations": "This work is limited to translation invariant kernels which can be expressed as an integral using the spectral measure, as well as the dataset splitting issue.\n\nA brief discussion could improve the proposed work by making these issues explicit.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 1, "strengths": "This is a work that has the potential to be a seminal paper in the field of conditional independent testing for large scale data.\n\nThe major improvement is the ability to incorporate modern learning methods in the well-established HSIC framework, while controlling the typically quadratic complexity.\n\nThe claims come with a concentration bound of the proposed statistic, linear time 1st and 2nd moment estimators, a uniform (upper) bound for the convergence of the optimisation and a probabilistic upper bound of Type II error given a lower bound on the dimension, that depends on the dataset.\n\nThis is a simple idea but the supporting theory is far from trivial.", "weaknesses": "The main weakness of this method is its limitation to translation invariant kernels, which is, however, quite a usual case.\n\nAnother weakness is that the dataset must be split in two parts to avoid the selective inference problem.\n\nFinally, as an extension of HSIC, this method most likely also suffers from some hindrances in the latter, for instance that the Null distribution (or, in specific, the necessary quantile) has to be empirically approximated, say using bootstrapping, or a possibly looser bound needs to be used.\n\nSome comments:\n* Table 1 needs some more space around it to avoid confusion.\n* ln 51: statistics\n* $\\xi_\\omega$ needs to be defined in  Theorem 2, and for completeness also $\\sigma_\\omega$, $\\hat\\sigma_\\omega$.\nPerhaps these could be added in the Appendix as a per-lemma symbol table?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive comments on our work. In what follows, we tried to respond to your concerns, and hope that this feedback is helpful for clear up your concerns.  \n\n***W1***: The main weakness of this method is its limitation to translation invariant kernels, which is, however, quite a usual case.\n\n***Response to W1***: Translation-invariant is a common and practical assumption, which is primarily used to ensure the characteristic property [1] of the kernel and as a prerequisite for using frequency-domain approximations. However, this assumption can be relaxed in some cases. For example, in the case of deep kernel [2], which may lack translation invariance. [2] demonstrates that the kernel's characteristic is preserved when the neural network meets certain assumptions. In our case (see lines 139-141, section 4.2), the theoretical properties are also guaranteed under similar assumptions about the feature map T (the notion is in line 139 Section 4.1).\n\nRegarding the necessity of this assumption under frequency-domain approximation, our framework (line 139-142 Section 4.1) provides a relaxation. We can use T to handle the non-translation-invariant part, while performing frequency-domain approximations on the translation-invariant part to achieve speedup. Thus, this assumption can be relaxed for specific data scenarios by using our framework in conjunction with a specific model design.\n\n***W2***: Another weakness is that the dataset must be split in two parts to avoid the selective inference problem.\n\n***Response to W2***: The splitting strategy has an advantage of being able to address the overfitting issue and effectively control Type I errors, ensuring the validity of the test (section 4.3, lines 207-209).\n\nCurrently, alternative approaches are designed for two main scenarios: one involves selecting kernels from a finite/countable set (referred to as the discrete scenario) and the other involves performing kernel parameter searches in a continuous space (referred to as the continuous scenario). For the discrete scenario, some methods [3,4] control Type I errors by applying techniques from the selective inference literature. However, these methods cannot be applied to a continuous scenario due to the uncountable set of kernels involved. To the best of our knowledge, both our scheme and existing methods [2,5] rely on data splitting for the continuous case. Designing methods to control Type I errors in the continuous case without sample splitting is an intriguing problem, which is our future work.\n\nThe following references are cited in the our paper. \n\n[1] Sriperumbudur, B. K., Gretton, A., Fukumizu, K., Schölkopf, B., and Lanckriet, G. R. (2010). Hilbert space embeddings and metrics on probability measures. The Journal of Machine Learning Research, 11:1517–1561\n\n[2] Liu, F., Xu, W., Lu, J., Zhang, G., Gretton, A., and Sutherland, D. J. (2020). Learning deep kernels for non-parametric two-sample tests. In: International Conference on Machine Learning (ICML 2020), pages 6316–6326. PMLR. \n\n[3] Kübler, J., Jitkrittum, W., Schölkopf, B., and Muandet, K. (2020). Learning kernel tests without data splitting. Advances in Neural Information Processing Systems, 33:6245–6255.\n\n[4] Schrab, A., Kim, I., Guedj, B., and Gretton, A. (2022). Efficient aggregated kernel tests using incomplete u-statistics. Advances in Neural Information Processing Systems, 35:18793–18807.\n\n[5] Jitkrittum, W., Szabó, Z., and Gretton, A. (2017). An adaptive test of independence with analytic kernel embeddings. In International Conference on Machine Learning, pages 1742–1751. PMLR.\n\n***W3***: Finally, as an extension of HSIC, this method most likely also suffers from some hindrances in the latter, for instance that the Null distribution (or, in specific, the necessary quantile) has to be empirically approximated, say using bootstrapping, or a possibly looser bound needs to be used.\n\n***Response to W3***: Yes, most current HSIC variants, including our method, require empirical approximation to determine the threshold. One possible reason is that the HSIC statistic is not normalized, necessitating the computation of certain distributional parameters of the asymptotic distribution under H0, such as the mean and variance. Exploring how to integrate our framework with the development of new statistics to bypass this issue is an interesting issue for future work.\n\n***Response to the comments for writing***: Thanks for your suggestions, we will fix these issues in the revised version.\n\n***Questions***:\nI had difficulty following the implications of Theorem 2, given its (reasonably) over-packed formulation and I believe that a couple more sentences explaining the involved quantities would make it easier to read.\n\n***Response to questions***: Theorem 2 can be divided into two key results. The portion in lines 237-239 addresses the first result, which states that the test power converges to 1, indicating that the test is consistent under the condition $\\mathbf{E}_Z\\text{HSIC}^{(u)}_{\\omega}(Z^{te})>0$. The second part, detailed in lines 239-244, examines the conditions under which this requirement is met, which necessitates sufficient frequency sampling. Overall, with adequate frequency sampling, our test guarantees consistency (lines 245-251). I hope this will make it easier for you to understand the implications of Theorem 2.\n\nAnyway, we will revise Theorem 2 to make it easier to be understood in the revised manuscript.\n\n\n***Limitations***:\nThis work is limited to translation invariant kernels which can be expressed as an integral using the spectral measure, as well as the dataset splitting issue.\nA brief discussion could improve the proposed work by making these issues explicit.\n\n***Response***：see our response to W1.", "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: This paper takes the Fourier perspective on the popular HSIC criteria, leading to a linear time computable novel criteria. All the reviewers agree that the work is quite novel. It will be great if the authors handle the apprehensions raised by the reviewers appropriately in their final version, if the paper is eventually accepted. I feel the linear computation aspect is perhaps what distinguishes the work from the others and needs to be highlighted appropriately.
Decision: Accept (poster)