Independence Testing for Temporal Data
Authors: Cencheng Shen
Jaewon Chung
Ronak Mehta
Ting Xu
Joshua T Vogelstein
Venue: Accepted by TMLR ()

Abstract: Temporal data are increasingly prevalent in modern data science. A fundamental question is whether two time series are related or not. Existing approaches often have limitations, such as relying on parametric assumptions, detecting only linear associations, and requiring multiple tests and corrections. While many non-parametric and universally consistent dependence measures have recently been proposed, directly applying them to temporal data can inflate the p-value and result in an invalid test. To address these challenges, this paper introduces the temporal dependence statistic with block permutation to test independence between temporal data. Under proper assumptions, the proposed procedure is asymptotically valid and universally consistent for testing independence between stationary time series, and capable of estimating the optimal dependence lag that maximizes the dependence. Moreover, it is compatible with a rich family of distance and kernel based dependence measures, eliminates the need for multiple testing, and exhibits excellent testing power in various simulation settings.

Published in Transactions on Machine Learning Research (05/2024)
Independence Testing for Temporal Data
Cencheng Shen
shene Gudel. edu
Deportment of Applied Economics and Statistics University of Delawore
Jaewon Chung
jlc0jhuu edu
Deportment of Biomedical Engineering
Johns Hopkins University
Ronak Mehta
vonakdm edu
Department of Statistics University of Washington
Ting Xu Child Mind Institute
Ting.Xu Xu@chhlddiidddorg
Joshua T. Vogelstein
jovo edu
Department of Biomedical Engineering Johns Hopkins University
Reviewed on OpenReview: https: oppprevvee. net/ forum? id= juIaPQINcC
Abstract
Temporal data are increasingly prevalent in modern data science. A fundamental question whether two time series are related or not. Existing approaches often have limitations, such as relying on parametric assumptions, detecting only linear associations, and requiring multiple tests and corrections. While many non-parametric and universally consistent de- pendence measures have recently been proposed, directly applying them to temporal data can inflate the p-value and result in invalid test. To address these challenges, this paper introduces the temporal dependence statistic with block permutation to test indo- pendence between temporal data. Under proper assumptions, the proposed procedure is asymptotically valid and universally consistent for testing independence between station- ary time scrics, and capable of estimating the optimal dependence lag that maximizes the dependence. Moreover, it is compatible with a rich family of distance and kernel based de- pendence measures, eliminates the need for multiple testing, and exhibits excellent testing power in various simulation settings.
1 Introduction
Temporal data, often referred to as time series, finds wide applications across diverse domains, such as func- tional magnetic resonance imaging (FMRI) neuroscicnce, dynamic social networks in sociology, financial indices, etc. In a broader context, temporal data can be seen as type of structural data characterized by inherent underlying patterns. When dealing with temporal data, fundamental problem is to determine the presence of relationship between two jointly observed time scries.
In the context. of standard independent and identically distributed (i.i.d.) data, where observations (X,, Y2)....... (X,, Yx) are drawn independently and identically from the joint distribution Fxy, the question simplifics whether the underlying random variables X and are independent, i.c., Fxy Fx Fy. Many recent dependence measures have been proposed tackle this problem, aiming to achieve valid and universally consistent independence testing. These methods include distance correlation (Szekely et. al.

---

Published in Transactions on Machine Learning Research (05/2024)
2007
Szekely & Rizzo 2009
2014).
Hilbert-Schmide independence criterion |Gretton et al. 2005
Gretton
& Gyorfi 2010
Gretton et al. 2012), multiscale graph correlation (Vogelstein et al. 2019 Shen et al. 2020:
Lee et al. 2019 and many others (Heller et al. 2013 Zhu et al., 2017 Pan et al. 2020
However, the standard testing framework is not applicable to structured data such as time scries, because the 1.i.d. assumption often does not. hold. As a result, standard testing procedures like the permutation test are known produce inflated p-values and are thus unsuitable for testing structured data |Guillot & Rousset
2013 DiCiccio & Romano 2017). Existing rescarch on testing independence for temporal data is limited, often relying on linear measures such as autocorrelation and cross- corselcorrel which may overlook potential nonlinear relationships (Wang et al. 2021). A commonly made assumption is to consider the sample data as stationary, meaning that the joint distribution of (X,, Yz-r) depends only on the lag l and not on any specific time index t. Approaches for addressing the instantaneous time problem, where the goal is to detect whether X, and Y2 are independent, have been explored in Chwialkowski Gretton (2014). Morcover, [Chiallowski ct al. (2014) investigates the problem of testing between X, and Y for cach lag I separately, employing multiple lesting techniques.
In this paper, we propose an aggregated temporal statistic and utilize block permutation procedure to ex- tend the scope of independence testing beyond the ii.d. assumption. Given a standard dependence mcasure such as distance correlation, our method first calculates a set of cross dependence statistics. These stat isties not only facilitate the estimation of the optimal dependence lag, but also enable the computation of the temporal dependence statistic as a weighted aggregation of all cross dependence statistics. Subsequently, we employ block permutation procedure derive a p-value for hypothesis testing. Under proper assump- tions regarding the choice of the dependence measure, the joint distribution of the temporal data, and the parameters of the block permutation, establish the asymptotic properties of the temporal dependence, and prove the asymptotic validity and universal consistency of our method. Notably, the proposed temporal dependence method is non-maramtt and does not require multiple testing.
Numerically, we show that the proposed approach yields satisfactory testing power when applied to simulated time series with small sample sizes. It compatible with various dependence measure choices, and numeri- cally superior and more versatile than previously proposed time series testing procedures. Additionally, we present the results of two real-data experiments, utilizing the proposed method to analyze neural connectiv- ity based on IMRI data, as well as uncovering interesting temporal dependencies between the general stock market and low-beta stocks.
2 Method
2.1
Hypothesis for Testing Temporal Dependence
Given the joint sample data {(Xi, Yi),.., (Xn, Yn),, let = (X,,.,,, E and Ý = (Y,,.,, e Rax= represent each individual sample data. Here, p and q denote the dimensions and are positive integers, and n is the sample size.
Suppose (X, Y) is strictly stationary, meaning the distribution at any set of indices remains the same. We can represent the distributions of X, and Y, at any point as Fx and Fy, and represent the distribution of (X,, Yi-1) as Fxy_, for each lag 1 2 0.
We aim to test the following independence hypothesis between X and Y:
Ho : FXY_, Fx Fy for each 1 (0, 1,,1,.. ...,, I.) HA FXY # Fy for some / E (0, 1,..,...,) T.).
Here, I is a non-negative integer denoting the maximum lag under consideration. Essentially, the null hypothesis states that X, independent of present and past values of Y,-1 for all of / = O,..., L. In contrast, the alternative hypothesis suggests (X, Y_) are dependent for at least one I in the range of [o, LJ. This setting is, in fact, a generalization of the standard i.id. setting, where it was assumed that (X1, Vi), (X2, Y2,.... (8,YY,) i.i.d. Fxy, and the null hypothesis simplifies to FxY FxFy because there
2

---

Published in Transactions on Machine Learning Research (05/2024)
is no possible dependence other than = 0. Hence, our subsequent method and theory for testing two time series are also applicable when only one of them is time series when both are standard i..dd data. Moreover, they are applicable to any general structured data that can be assumed stationary.
2.2 Main Algorithm
The proposed method consists of four steps: computation of the cross-lag dependence statistics, estimation of the optimal dependence lag, computation of temporal dependence statistic, and block permulation to obtain the p-value for testing purposes. Details regarding the choice of the dependence measure, block permutation, and computational complexity are discussed in the following subscctions.
Input:
Two jointly-sampled datasets represented as X Rex* and Y E R a given choice of sample dependence measure Tu(::-) 12x= R E, and three positive integers: the lag limit L, the number of blocks B, and the number of random permutations R.
--),,1 = D,. Here, 8-) Step 1: Compute the set of cross dependence sample statistics {Tx (x,(XXy-1),, denotes the sample data with lags apart, which consists (n - 1) pairs observations:
(x [(X1+t Ki), (X2t1, V2), ..... (Xn, Yn-1))-
Step 2: Estimate the optimal dependence lag:
- 1 -n (X,,,
Ż' arg max [E n
Here, the weight (m=²) simply weights each cross dependence statistic based on the number of observations it uses.
Step 3: Compute the temporal dependence sample statistic:
Tx 8)
72 1--
(x,
1=0
Step 4: Compute the p-value using block permutation:
p-val= Σ (TT,(( TT )))R
where I(-) is the 0-1 indicator function, and πy a randomly generated block permutation for each
Output:
The temporal dependence statistic T, the corresponding p-value, and the estimated optimal depen- dence lag D
The mull hypothesis is rejected if the p-value is less than a pre-specified Type error level, such as 0.05.
2.3 Choice of Dependence Measure
While the algorithm can accommodate any dependence mcasure as the choice of (.))) it is essential for the chosen measure to be vell-behaved and satisfy the required assumptions outlined in Section 3.1 This ensures consistency in detecting dependence between temporal data, both terms performance and subsequent thoory. In our experiments, we employed distance correlation, Hilbert-Schmidt independence criterion, and multiscale graph correlation. All of these measures meet the necessary assumptions, and the resulting tests appear valid and consistent in numerical experiments.
3

---

Published in Transactions on Machine Learning Research (05/2024)
As the proposed temporal statistic is essentially an aggregation of the underlying dependence measure, its effectiveness in capturing dependence is contingent upon the choice of dependence measure. It is well known that each dependence measure has its own unique strengths. Therefore, our usage of distance and kernel based statistics in this paper should be viewed as an illustration of the validity and consistency properties of the proposed temporal lest.
Some examples of other dependence measures include correlation coefficients (Fukumizu et al. 2007 Bieß
mann et al. 2010
Chatterjee's rank correlation [Chatterjee 2021 Shi et al. 2021 2022). the HHG method
[Heller et al.,
2013
2016
projection correlation (Zhu et al., 2017). , ball covariance (Pan et al. 2020
well as recent high-dnmensional dependence statistics (Zhu et al. 2020 Huang & Huo 2022: Shen & Dong,
2024 Xu et al.)
2024
Zhou et al., 2024). All of these dependence measures can be directly incorporated
into our temporal testing framework by simply modifying the cross-dependence statistics in Step 1. Such
adaptations may offer better testing power for certain dependence structures.
For instance, using the correlation coefficient with block permutation will only detect linear associations in temporal data, while universally consistent dependence measure can detect all possible dependencies with sufficiently large sample size; dependence measures that are better at detecting nonlinear or high-dimensional dependencies in standard i.idd. data will also perform better under such dependencies in the case of temporal data, requiring a smaller sample size to achieve perfect testing power; rank-based dependence measures can be more robust against data noise.
2.4 The Block Permutation Test
The standard permutation test is widely used for independence testing GGod 2005 In a standard permu- tation, π-)) randomly permutes the indices 1,2...., resulting in Y, and X that are mostly independent (except. for a few indices that do not change position, which are asymptotically negligible as n increases). Given sufficienlly many random permutations, this process allows the permuted test statistics to estimate the true null distribution.
However, the above is only true under the standard i.i.d. setting, and it no longer holds when there exists structural dependence within the sample sequence, such when (X,, Yi) are dependent with (X,-1) Y1-)). Specifically, the permuled statistics would under-estimate the true null distribution, leading to an inflation
of the testing power. This issue has been noted in Guillot & Rousset (0013); DiCiccio & Romano (0117). which can affect any dependence mcasure that relics on the standard permutation test.
To ensure validity of the lest, we employ a block permutation procedure (Politis 2003) denoted as Tn()),
where denotes the number of blocks. The construction of T-(-) proceeds as follows:
We partition the index list into B consecutive blocks. For j = 1...., B, block j consists of indices
n Note that for the last block, the last few indices may exceed n, in which case the indices wrap around and restart from 1.
By = 1 +1, n * (j 1) +) + 2,..,, n + -
(j
As an example, consider a sample size of 100 and B 20 blocks, with each block containing 5 indices. Then the first block would be YY, Ys), the second block would be (Yo, Y,,.., Yio), etc. During the block permutation process, each block is shifted to another position. For instance, the first block might be permuted to the fourth block, resulting in #1(1 16, (2) = 17, Tz3) = 18, TB(1) = 19, TB(1) = 20. This shufllin of blocks ensures a randomized distribution of data while maintaining the block structure.
2.5 Parameter Choice and Computational Complexity
The choice of the maximum lag, denoted as L, is typically determined based on subject mat ter considerations. For example, if the signal from one region of the brain can only influence another region within a range of 20 time steps, then sctting L 20 would be appropriate. Similarly, when collecting daily stock trading data for two stocks, choosing L 30 indicates that we are examining the dependence structure within the past month.
4

---

Published in Transactions on Machine Learning Research (05/2024)
As for the number of blocks, used B 20 in experiments, which is sufficient for our purposes. For the number of permutation, used R = 1000 replicates. Assuming that the dependence measure can be computed in (n²²) time complexity (which is the case for distance correlation), the temporal independence test has a time complexity of (n22R))
3 Supporting Theory
In this section, we establish the asymplotic properties of the lest statistics and the resulting lests, which include asymptotic convergence, validity, and consistency. We begin by outlining the necessary assumptions for the theoretical results, followed by detailed elaborations on each assumption. All theorem proofs can found in the Appendix Section B.
3.1 Assumptions
The observed data {(X,, 1-) strictly stationary, non-constant, and the underlying distribution Fxy-, has finite moments for any lag 2
There exists maximum dependence lag M such that for all 1 2 M, the two time series are almost independent for large n, so are each time series within itself:
sup Fxx_ Fx 0
sup Fxx_, FxFx| = 0 1
sup BurlBry.. Fy Fy 0 1
The maximum dependence lag M and the maximum lag under consideration L are non -egateet integers that satisfics 2 and L o(n), i.c., they may inercase together with n but at slower pace.
As the sample size increases, both the number of blocks B and the number of observations per block B increase to infinity. Moreover, 2 M for sufficiently large n.
The sample dependence measure has the following form:
(x E Ei= (i(jj)
n12
where each 7n (i.j) is function of V, Yy). and remaining sample pairs may also be used but with weight of O(1nn).
In the standard ii.d. setting where (X1, Y1), (X2, Y2).... (Xn, Yn) Lid Fxy, there exists popula- tion statistic Y) defined solely based on the joint distribution Fxy. When i + j. each term in the sample statistic satisfies:
B(m((i,)) = o(1)
Moreover, the population statistic r(X.Y) Y) is non-negative and equals if and only if X and Y are independent, i.e., Fxy Fxly.
The first assumption is a common one in time series research. The key distinction from the standard i..d. setting is that the samples are no longer independent, but remain identically distributed. For non- stationary data, there exist many common techniques to remove trends and process them into approximately stationary processes (Cleveland et al. 1990 Hastie et al. 22099 Enders 2010 Shummwa & Stoffer 2010 Box
et al. 2015 Some examples include differencing, where one computes the difference wetween consecutive
5

---

Published in Transactions on Machine Learning Research (05/2024)
observations; detrending via linear regression polynomial fitting and subtracting the trend component from the original series; seasonal adjustment by decomposition; log square root, / Box-Cox transformation to stabilize variance; smoothing via moving averages to reduce noise and short-term fluctuations; filtering to remove specific frequencies from the data.
The second and third assumptions require that the time series exhibit independence for sufficiently large lags beyond M, and that the maximum lag to be examined, L, must be no less than M. Such an assumption shares similarity with the mixing property, where stochastic process is mixing if its values at widely-
separated times asymptotically independent (Pham & Tran 1985 McDonald et al.) 2011 Ziemann &
Tu 2022). Hence, our results can also be considered approximately true for mixing time scries.
The fourth assumption imposes a regularity condition on block permutation. In theory, choices for B can be log(n) or vn, while a practical choice like B = 20 sufficient for our simulations. This resembles the Bayes optimal condition for K-nearest-ncighborr, where K is roquired to increase to infinity but slower than n.
The remaining assumptions regarding the dependence measure satisfied by variety of distance and kernel measures that have been recently proposed. For example, distance covariance satisfies the two assumptions, with
The (i.j) (d(X,, - px, μx, + XxX(d(X - by; - MY, Jy
Here, d(s,-) is the Euclidean distance, μxx, denotes the mcan of all distance pairs relative to X; within X, and ax is the mean of the whole pairwise distance matrices of X. Furthermore, the population distance covariance is defined in terms of characteristic functions and equals if and only if Fxy = Fx in the standard ii.d. settings. Indeed, many dependence measures that are universal consistent in the standard i.i.d. setting satisfy this assumption. For example, the Hilbert-Schmict independence criterion utilizes the same formulation (Shen & Vogelstein 2021 Sejdinovic et al., 2013 on the Gaussian kernel. Additionally, the unbiased distance covariance and distance correlation, well as the multiscale graph correlation truncated version of distance correlation where large distance pairs may be unused also satisfy this assumption.
3.2 Convergence of the Sample Statistics
We begin by proving the convergence of the sample cross dependence to the population cross dependence: Theorem 1. The cross dependence sample statistic satisfies:
B(Tn(( V-1)) - - Vx1, o(1), Var(T (x = 0
=0
n- -0
Therefore, for each {0,..., L}, we have
(2. 32 T(X.Y-1)
probability.
Theorem shows that both the bias and variance of the cross dependence statistic diminish to 0 the sample size n increases. Consequently, this guarantees that the aggregated temporal dependence statistic and the estimated optimal lag also converge to their corresponding population forms in probability. Theorem 2. The temporal dependence sample statistic satisfies:
T (
7 (X,Y-1)
I=0
The estimated optimal dependence lag satisfies:
1. 20000
arg max T(X, V-1)- IE [0

---

Published in Transactions on Machine Learning Research (05/2024)
3.3 Validity and Consistency for Testing Temporal Independence
In this subsection establish the validity and consistency of the method. Specifically, if X and Y are independent, the power of the test equals the Type 1 error level a. Conversely, if X and Y are dependent, the power of the test converges to 1, and the method can consistently detect any dependence.
Given Tx(X,, ()) as the observed lest statistic, let Fr (2) be the empirical distributiin of the block-permuted statistics (T,(X, Yxg)),
}}, and denote Zn,o the critical value where:
Fry (Z) =
The following theorem establishes the asymptotic validity of our block permutation test: Theorem 3 (Asymptotic Validity). Under the null hypothesis that X and Y are independent for all lags E [0, L), the test statistic satisfies:
Tx( 0.
Moreover, the block- poick-pemmstation test asymptolically valid, i.e.,
Pro f) 2 2n.a) "0 a.
The next theorem proves that the method universally consistent against any alternative.
Theorem (Testing Consistency). Under the alternative hypothesss that X and Y are dependent for some lag E [0, L), the test statistic satisfies
T (x c>0.
Moreover, the block-permmutatinn test is asymptotically consistent, i.c.,
Prob(TT, (T, 2 2n,a) "0 1.
4 Simulations
We estimated the testing power of the proposed approach through simulations various temporal de- pendence structures. Specifically, we considered three different implenentations of the proposed temporal dependence statistic, which utilized distance correlation (DCorr), Hilbert-Schmidt independence criterion (HSIC), and multiscale graph correlation (MGC). For comparison, we included ShiftHSIC (Chwialkowski & Gretton 2014h, WildHSIC (Chwialkowski et al. 2014), and the widely recognized Ljung-Box test (Ljung & Box 1978) using traditional corssscorrclssions. Each simulation was repeated 300 times, with 1000 permu- falions and Type 1 error level of 0.05 used compute the p-values. The testing power measured by how often the p-value is lower than 0.05 out of the 300 Monte-Carlo simulations, Analysis of ShiftHSIC and WildHSIC was performed using MATLAB code and wildBootstrap
4.1 Testing Power Evaluation
Independence First, check the validity of the tests by generating two independent, stationary autore- gressive time series with lag of one:
X2 Y
X Y
X
E
+
77
Herc, (c,7)) are standard normal noise terms. As shown Figure the proposed methods maintain a testing power close to a = 0.05 across varying and d, regardless of statistic used.

---

Published in Transactions on Machine Learning Research (05/2024)
Independent (R(1)
1.0
Rejection Probability
0.8
0.6
0.4
0.2
0.0
10
50
150
200
0.2
0.4
0.6
0.8
Sample Size
AR Coefficient
MGC
DCorr
Ljung-Box
HSIC
Wild HSIC
Shift HSIC
Figure 1: This figure illustrates the validity of the tests using two independent time series. In the left panel, the testing power is computed as the sample size increases, with an AR coefficient of ø = 0.5. The right panel keeps the sample size at n = 1200 while varying the AR cocfficient á, with the noise variance appropriately adjusted by (1 - dd²), based on the same simulation as Chwialkowski & Grelton (014)) The dashed black line represents the significance level a 0.05.
Linear Dependence Next, we assess our methods' ability to capture linear relationships the following simulation:
X₂ Y2
X
+
Y
T/:
As this represents straightforward linear relationship, the Ljung-Boo Box test, based auto-correlation, is expected to perform best. This is indeed the case in the left panel of Figure Our proposed methods using DCorr, MGC, and HSIC follow closely, quickly converging to perfect power around n 100. In contrast, the other competitors do not perform well this scenario. This not surprising, as the ShiftHSIC method is designed to detect whether X₃ and Y are dependent at lag O, whereas the lincar dependence here is of lag 1. The WildHSIC method used a wild bootstrap method to estimate the null distribution, which can be inaccurate small sample size.
Nonlinear Dependence The next simulation considers a nonlinear dependent model:
X Y
TeYi-1 1/2
In the right panel of Figure 2 our proposed methods utilizing DCorr, MGC, and HSIC demonstrate superior performance compared to other competing methods. Notably, the HSIC and MGC implementations exhibit better finite-sample power, as these two dependence measures are better at identifying nonlinear relationships than DCorr. In contrast, all other tests fail to detect dependence this scenario.
Extinct Gaussian This simulation uses the same extinct Gaussian process from Chwialkowski Grefton 2014h, where
Xx Y
X Y
[ Th
+
and we set 1200. Here, the (c),7) m6) pair are dependent and drawn from an Extinct Gaussian distribution with two additional parameters: (extinction rate) and (radius). Both variables are initially drawn from independent standard normal, and U sampled from standard uniform. If either ei +/ > r or > e holds, then (G.7%) are returned; otherwise, they are discarded and the process repeated. In this process, the dependence between & and f) increases with extinction rate e. Therefore, we expect power to increase with the extinction rate, which is indeed the case shown in Figure 3 While all methods, except Ljung-Boz,
8

---

Published in Transactions on Machine Learning Research (05/2024)
Correlated AR(1)
Nonlinear Lag(1)
1.0
Rejection Probability
0.8
0.6
0.4
0.2
0.0
10
50
100
150
200
10
50
100
150
200
Sample Size
MGC
DCorr
Ljung-Box
HSIC
Wild HSIC
Shift HSIC
Figure The testing power for linear (left panel) and nonlinear (right panel) simulations based on 300 replicates.
are consistent and eventually achieve perfect power, our proposed method using MGC stands out as the best performer.
Extinct Gaussian Process
1.0
Rejection Probabtility
0.8
0.6
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0
Extinction Rate
MGC
DCorr
Ljung-Box
HSIC
Wild HSIC
Shift HSIC
Figure 3: The testing power for the extinct gaussian simulation based on 300 replicates.
4.2 Optimal Dependence Lag Estimation
In this subsection, we evaluate the method's performance in estimating the optimal dependence lag in both linear and nonlinear settings. The linear setting
X Y2
Φ1
X
Φ
X,_3
[ez
Φ1
0
Y
Y
ne
where we set 63 = 0.8 > Φ1 = 0.1 such that the true optimal dependence lag equals 3. The nonlinear simulation
X
E,Yi
Y2
17t
9

---

Published in Transactions on Machine Learning Research (05/2024)
In both simulations, the true optimal dependence lag equals 3. Figure shows that the proposed method using eir DCorr or MGC consistently estimates the optimal dependence lag as the sample size increases, and MGC outperforms DCorr in the nonlinear setting.
4.3 Multivariate Simulations
In this subsection, revisit the testing power and dependence lag estimation in both linear and nonlin- car settings, maintaining fixed sample size of 100 and increasing the dimensionality to evaluate performance for multivariate data.
For testing power evaluation, we use the following multivariate linear setting:
X Y2
0
oD 0
X Y
Ce
+
ΦD
[
where o 0.65, D E RPxP diagonal matrix where the elements are Da 1/6, and 6t, qt are standard normal of dimension p. In similar manner, we use the following multivariate nonlinear setting:
X2 Yg
D(a P Y(-1) 1/1
where @ denotes element-wise multiplication. We intentionally design the matrix D as decaying weight, reflecting a meaningful multivariate simulation where additional dimensions contain weaker dependence signals.
Figure T illustrates the testing power as dimensionality increases. At a fixed sample size, all testing powers gradually decrease as p increases. The proposed method using any of MGC, DCorr, or HSIC maintains relatively stable power with slow degradation in the case of linear dependence. The same trend is observed for nonlinear dependence, although the degradation is faster, with the MGC statistic performing the best. It is worth emphasizing that due to the consistent property, if we fix p and let increase, the testing power for our method shall increase to 1.
Similarly, we extend the optimal lag estimation into the following two multivariate settings:
X, ØID
D
X Y
D3D
X,-3 Y
C2
+
Y,
DgD
Th
X,
D(E -2-3)
Y,
11t
where Φ1 0.1 and Φ3 0.65. These settings similar to those in Section 4.2 with the addition of increasing dimension and D. The true optimal lag remains 3. The estimation accuracy, shown in Figure 6. demonstrates successful detection at small with accuracy gradually degrading as increases.
5
Real Data
5.1
Analyzing Connectivity in the Human Brain
This study is based on data from an individual (Subject ID: 100307) of the Human Connectome Project (HCP), which can be downloaded online The human cortex is parcellated into 180 parcels per hemisphere using the HCP multi-modal parcellation atlas (Glasser et al., 2016). For this study, 22 parcels were selected as regions of interest (ROTs), representing various locations across the cortex. These parcels are denoted as (1)) ...., cortical surface. Averaging the vertices within parcel yields a univariate time series (m)) = (x(")... ""...,(""))
x1))....,(22)) (22), Each parcel consists of a contiguous set of vertices whose fMRI signal projected on the
where n = 1200 in this particular case. The selected ROIs, their parcel number in the HCP multi-modal parcellation Glasser et al. 2016), , and assigned network are listed in Table
httpss///www.hmaacccccctttooe http://cttttttoorees/////////eee http://tt///pppuuuuuuuuaaaaaaaaa
10

---

Published in Transactions on Machine Learning Research (05/2024)
Correlated AR(3): Distribution of Optimal Lag Estimates
n
n
0.8-
DCar--X
0.6
0.2
Frequency
0.0
1.0
0.6
MGC-X
0.4
0.2
0.0
2
8
10
2
4
10
10
Lag
Nonlinear Lag 3: Distribution of Optimal Lag Estimates
1.0
DCom-X
0.6
Frequency
0.0
1.0
0.6
MGC-X
0.4
0.0
2
Lag
This figure displays the performance of proposed method using both MGC and DCorr for estimating the optimal dependence lag i in lincar and nonlincar relationships. The colored bar above lag shows the empirical frequency of i- = j, with red representing MGC and purple representing DCorr. The probability estimated based on 100 trials. The first row shows DCorr estimation performance at sample sizes n = 15, 30, 60 for linear relationships, while the second row shows the MGC performance on the same data. The third row displays DCorr estimation for nonlinear relationships, and the last row presents the same for MGC.
Figure 4:
11

---

Published in Transactions on Machine Learning Research (05/2024)
A)
Correlated VAR(1)
Nonlinear Lag(1)
1.0
Rejection Probability bility
0.8
0.6-
0.4
0.0
20
40
60
80
100
5
10
15
20
Dimensions
Dimensions
MGC
DCor
HSIC
Wild HSIC
Shift HSIC
Figure 5: This figure shows the testing power for multivariate simulations, with constant sample size of
100 while increasing the dimensionality.
B)
Correlated VAR(3)
Nonlinear Lag(3)
Lag Estimation ation Accuracy
1.0
0.8
0.6
0.4
0.2
0.0
20
40
60
80
100
5
10
15
20
Dimensions
Dimensions
MGC
DCorr
HSIC
Figure This figure shows the accuracy of estimating the true optimal lag in multivariate simulations, maintaining constant sample size of 100 while increasing the dimensionality. Note that in the left panel, the lines representing DCorr and HSIC overlap due to their almost identical performance.
12

---

Published in Transactions on Machine Learning Research (05/2024)
ROI ID
Network
Shorthand
Parcel Key
Parcel Name
Default Mode Network
DMN
150
PGi
Default Mode Network
DMN
65
p32pr
20
Default Mode Network
DMN
161
32pd
21
Default Mode Network
DMN
132
TEla
22
Default Mode Network
DMN
71
9p
6
Dorsal Attention Network
dAtt
96
6a
7
Dorsal Attention Network
dAtt
117
API
Dorsal Attention Network
dAtt
50
MIP
Dorsal Attention Network
dAtt
143
PGp
10
Ventral Attention Network
vAtt
109
MI
11
Ventral Attention Network
vAtt.
148
PF
12
Ventral Attention Network
vAtt
60
p32pr
13
Ventral Attention Network
vAtt
38
23c
Visual Network
Visual
V1
Visual Network
Visual
23
MT
Visual Network
Visual
18
FFC
16
FrontoParietal Network
FP
83
p9-46v
17
FrontoParietal Network
FP
149
PFm
14
Limbic Network
Limbie
135
TF
15
Limbic Network
Limbic
93
OFC
4
Somatomotor Network
SM
53
3a
5
Somatomotor Network
SM
24
A1
Table 1: This table displays the parcellation information for the parcels used in our analysis. They are listed based on the numeric order they appear Figure 7
Optimal Lag
p-Value
DMN
GAIZ
WALE
Visual
FP
Limbic
SH
DWN
dAA
vAl:
Viuul
Limbic
SM
0.01
0.02
DMN
0.03
dATT
D
0.06
10
10
0.18
Misual
0.32
10
10
0.56
30
0
D
Figure 7: This displays the results of applying the temporal dependence method using MGC to resting-state [MRT data.
As the temporal dependence method using MGC performed well in our simulations, we simply use the MGC im- plementation in this analysis. In the left, panel of Figure 7 we present, the optimal dependence lag for each interdependency, ranging up to L = 10. Meanwhile, the right panel of F displays displays the log-scale v-values of temporal dependence for cach pair of parcels. Generally, we observe strong relationships with small lags within the same region, such an optimal lag of usually within the 'DMN' region with significant p-values. In contrast, inter-region dependencies are less significant and typically exist at longer lags.
13

---

Published in Transactions on Machine Learning Research (05/2024)
5.2 Discovering Temporal Dependence Structure of Low-Beta Stocks
In this experiment, we apply the proposed methodology to analyze the financial market and uncover inter- esting nonlinear dependencies between low-beta stocks and the S&P 500. In the US financial market, it is well-known that almost all stocks are linearly related to the broad market. A commonly used statistic to measure this association is the beta value, which quantifies a stock's volatility relative to the market (S&P 500). Beta is defined as the covariance between an individual stock and the general market, divided by the variance of the general market, and utilizes the rate of return per month rather than the stock price. A beta less than 1 suggests that the stock is less volatile than the market, while a beta greater than 1 indicates higher volatility.
Low-beta stocks are an interesting concept in investing, defined by having a relatively small beta value, typically around 0.5 or less. These stocks tend to have lower correlations with market movements compared to high-beta stocks and are often associated with companies that have stable earnings, strong cash flows, and less uncertainty about their future prospects. Therefore, low-beta stocks can play a valuable role in a well- diversífied investment portfolio by providing stability, reducing risk, and potentially enhancing long-term performance. Moreover, with the right strategy, stocks with low volatility can generate high risk-adjusted returns (Blitz & Vliet 2007 Frazzini & Pedersen 2014
We collected weekly closing stock prices from January 1, 2014, to May 1, 2014, using Yahoo Finance data, for the S&P 500 ETF (the benchmark) and 10 individual stocks, as shown in Figure In addition to NVDA, AAPL, and MSFT, which are mega cap stocks and were included for comparison purposes, the remaining stocks are commonly found in low-beta portfolios. Given the high volatility of daily stock prices, we chose to collect the closing price per week, and process each stock's weekly price into rates of return to make the data resemble stalionary sequence.
As the stock market is highly related and linear relationships are dominant among stocks, we chose to use Pearson correlation and distance correlation as our choice of dependence mcasures. For each choice, we computed the cross-dependence measures between each individual stock and the S&P 500 from lag 0 to 4. Subsequently, we computed the aggregated temporal statistic, followed by optimal lag estimation and p-value computation using block permutations. The sample size is n = 538, and the number of blocks is 20. Therefore, our aim is to test the existence of temporal dependence between each individual stock and the general market, from concurrent testing to lag of up to 1 month.
For each individual stock, the aggregated test always yielded a significant result, with a p-value of 0 and an optimal lag of 0 in every case. This indicates that all individual stocks are dependent on the general market, with the strongest dependence observed at concurrent (lag 0) intervals. This outcome is not surprising, as even a beta of 0.3 readily implics a significant lincar relationship at lag O.
Next, we examine the cross-lag dependence structure and their individual p-values in block-permutation, as reported in Figure 9 We first consider the Pearson correlation: the lag concurrent testing statistic is very similar to the beta value of each stock, all of which have significant p-values of 0. On the other hand, all other lags have insignificant p-values, suggesting there is no linear relationship beyond lag O. Namely, the S&P 500 price this week has no linear effect on itself next week or any individual stock next week, e.g., a high return of +2% this week does not always imply another +2% next week.
Inspecting the distance correlation measure yields interesting new insights: the general market, the three mega-cap stocks, and a few low-beta stocks are actually dependent on the general market at lag and beyond. Since the Pearson correlation indicates the lack of a linear relationship, this dependence must be nonlinear, which is weakened the lag increases. This insight aligns with empirical experience: for example, high return of +2% this week may indicate that the next week will be volatile, potentially resulting in another week of high return or a significant pullback from the highs. Such dependence constitutes a nonlinear association, while the linear association could be almost O. This type of volatility is often utilized in option trading and holds promise for future applications.
Finally, Jasuo reveal that some low-beta stocks, such as T, JNJ, WMT, and LLY, exhibit independence from the general market. beyond the concurrent lag O. This insight suggests that these stocks could be ideal
14

---

Published in Transactions on Machine Learning Research (05/2024)
Company
Stock Symbol
Beta (5 Year Monthly)
SP500 ETF
SPY
Nvidia
NVDA
1.75
Apple Inc
AAPL
1.26
Microsoft
MSFT
0.89
AT&T Inc
0.7
Pfizer Inc
PFE
0.58
Coca Cola
KO
0.57
Johnson & Johnson
JNJ
0.55
Walmart Inc
WMT
0.49
Procter & Gamble
PG
0.42
Eli Lily
LLY
0.37
Rate of Return (10 Year Weekly)
20.00%
0.00%
SPY
3/1/201
1/raa
1/2/2077
13/20/1
3/300221
1220022
1/1/2024
-20.00%
SPY
Nvidia
AAPL
MSFT
PFE
KO
JNJ
WMT
LLY
Figure 8: This figure shows the selected stocks, their current beta, and their rate of return over 10 years on a weekly basis.
candidates for portfolio that offers temporal independence, rather than just a lack of linear relationship. from the general market.
6 Conclusion
This paper introduces new independence testing procedure for temporal data. The method combined the strengths of nonparametric dependence measures, the specialized cross-lag statistic for time series, and the block permutation procedure. As a result, provides an asymptotically valid and universally consistent approach with outstanding numerical performance. While the exposition of this manuscript focused on time series data, this work marks important step in extending independence lesting to structural data beyond the realm of standard i.i.d. data, making them more attractive and broadly applicable.
There are several avenues for future rescarch that warrant exploration. Firstly, although we have demon- strated the asymptotic validity of the block permutation test, its computational elficiency remains a challenge when dealing with large sample sizes. Recent studies (Zhang et al. 2018 Shen et al. 2022 have investi- gated faster testing procedures by approximating the mill distribution of distance and kernel correlations under the standard i.i.d. setting. Extending such approaches structural data could significantly enhance computational scalability.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Cross Pearson Corretation with SP500
P-Value by Block Permutation
Lag 0
Lag
Lag.
Lag
Lag4
Lag
Lag
Lag
Lag
Lag
SP500 ETF
1.0000
0.0117
-0.0335
00.9600
0.0454
0.782
0.484
0.172
0.286
Mridia
0.5937
0.0148
0.0055
4.0185
0.0347
D
0.73
0.914
0.594
0.382
Apple Inc
0. 0.6691
-0.0195
-0.0079
0.0081
0.0686
0
0.658
0.858
0.832
0.124
Microsoft
0.7177
0.0247
0.0361
0.0429
0.0541
0.584
0.44
0.274
0.202
AT&T Inc
0.3787
0.0677
0.0355
0.0270
0.0155
D
0.13
0.398
0.52
0.686
Piizer Inc.
0.4482
0.0706
-0.0357
4.0087
0.0383
D
0.13
0.448
0.812
0.44
Coca Cola
0.5024
-0.0577
-0.0866
0.0755
0.0062
0.87
0.124
0.074
0.954
Johrson & Johnson
0.4910
0.0132
00.0536
0.0116
0.0381
0.782
0.188
0.706
0.396
Walmaart Inc
0.3845
0.0608
0.0242
0.0165
0.0742
0.144
0.612
0.966
0.08
Procter Gamble
0.4163
-0.0196
-0.0543
0.0284
0.0326
0.662
0.202
0.584
0.486
Lily
0.2877
0.0032
-0.0395
0.0030
0.0914
0.946
0.402
0.982
0.036
Cross Distance Corretation with SP500
P-Vatue by Block Permutation
Lag 0
Lag
Lag
Lag
Lag4
Lago
Lag
Lag
Lag
Lag4
SP500 ETF
1.0000
0.0175
0.0114
0.0102
0.0061
0
0.008
0.004
0.022
Nvdia
0.3264
0.0088
0.0046
0.0059
0.0005
0.014
0.052
0.042
0.364
Apple Inc.
0.3755
0.0115
0.0018
0.0047
0.0016
0.006
0.172
0.064
0.186
Micresoft
0.4556
0.0088
0.0013
0.0020
0.0020
0.00
0.288
0.14
0.146
AT&T Inc
0.1092
0.0022
-0,0009
0.0018
0.0010
0.19
0.56
0.746
0.302
Plizer Inc
0.1419
0.0071
0.0054
0.0009
0.0007
0.03
0.032
0.572
0.554
Coca Cola
0.1409
0.0056
0.0033
00.0199
-0.0021
0
0.03
0.094
0.788
0.816
Johnson & Johnson
0.1808
0.0030
0.0036
-0.0012
-0.0005
0
0.152
0.094
0.588
0.496
Welmerrthn Inc
0.1123
0.0028
-0.0010
0.0004
0.0035
0.12
0.572
0.478
0.112
Procter Gamble
0. 1.008
0.0086
0.0052
-0.005
-0.0029
0.036
0.024
0.518
0.918
Eiiyy
0.0639
0.0026
0.0052
0.0036
0.0028
0.15
0.05
0.312
0.114
Figure This figure shows the cross-correlation between each individual stock and the S&PP 500, using Pearson correlation at the top and distance correlation at the bottom, for lags from 0 to 4, along with the corresponding p-values. Significant correlations, where larger values are better, are marked in green, while significant p-values, where smaller values are better, are marked in red.
Secondly, dependence measures are commonly employed in dimension reduction techniques, such as screening FFan & Lv 2008 Li et al. 2012), especially in high-dimensional data settings. However, little attention has been given to the temporal domain. While it is straightforward to utilize dependence measures for dinension reduction in multivariate time series, delving into their theoretical properties and their relationships with other standard tools, such as independence component analysis, could provide valuable insights.
Thirdly, causal inference in time series data is an important lask (Haule et al. 2010 Winkler el al. 2016 While it is widely recognized that correlation does not imply causality, recent research has demonstrated the utility of dependence and conditional dependence tests in causal inference (Cai et al. 2022 Laumann al. 2.23 Therefore, extending this framework to encompass conditional independence and causal inference may significantly vancece the understanding of causal inference in time series data.
Acknowledgment
This work was supported by the National Institutes of Health award RFIMH128696 and RO1MH120482. the National Science Foundation award 1921310 and DMS-2113090 and the Defense Advanced Research Projects Agency (DARPA) Lifelong Learning Machines program through contract FA8650-18-2-7834 The authors would like to thank Sambit Panda, Hayden Helm, Benjamin Podigo, and Bijan Varjavand for thoir help and discussions in preparation of the paper. The authors also exlend thanks the action editor for the expert handling of the manuscript and to the anonymous reviewers for their valuable suggestions improve the paper.
References
F. Bießmaan,, F. C. Meinecke, A. Gretton, A. Rauch, G. Rainer, N. K. Logothetis, and K. Müller. Temporal kernel CCA and its application in multimodal neuronal data analysis. Machine Learning, 79:5-27 2010.
16

---

Published in Transactions on Machine Learning Research (05/2024)
D. Blitz and P. Vliet. The volatility effect: Lower risk without lower return. The Journal of Portfolio Management, 34(1):12-17, 2007.
G. E. P. Box, G. M. Jenkins, G. C. Reinsel, and G. M. Ljung. Time Series Anolysis: Forecasling and Control. John Wiley & Sons, 2015.
Z. Cai, R. Li, and Y. Zhang. A distribution free conditional independence test with applications to causal discovery. Journal of Machine Learning Research, 23:1-41, 2022.
S. Chatterjee. new coefficient of correlation. Journal of the American Statistical Association, 116(536): 2009 2022, 2021.
Chwialkowski and A. Gretton. kernel independence test for random processes. In 31st International Conference on Machine Learning, pp. 1422-1430, 2014.
K. Chwialkowski, D. Sejdinovic, and A. Gretton. A wild bootstrap for degenerate kernel tests. In Advances in neural information processing systems, pp. 3608 3616, 2014.
R. B. Cleveland, W. S. Cleveland, J. F. McRae, and T. Terpenning. Stl: A seasonal-trend decomposition procedure based on loess. Journal of Official Statistics, 6(1):3-73, 1990.
C. J. DiCiecio and J. P. Romano. Robust permutation tests for correlation and regression coefficients. Journal of the Americon Statistical Association, 1126519):1111-1220, 2017.
W. Enders. Applied Econometric Time Series. John Wiley & Sons, 2010.
J. Fan and J. Lv. Sure independence screening for ultrahigh dimensional feature space. Journal of the Royal Statistical Society: Series B, 70(5):849 1849-911, 2008.
A. Frazzini and L. Pedersen. Betting against beta. Journal of Financial Economics, 111(1):1-25, January 2014.
Fukumizu, F. R. Bach, and A. Gretton. Statistical consistency of kernel canonical correlation analysis. Journal of Machine Learning Research, 8:361 383, 2007.
M. Glasser, T. Coalson, E. Robinson, C. Hacker, J. Harwell, E. Yacoub, K. Uğurbil, J. Andersson, C. Beck- mann, M. Jenkinson, S. Smith, and D. Van Essen. A multi-modal parcellation of human cerebral cortex. Nature, 536:171 178, 2016.
P. Good. Permutation, Parometric, and Bootstrap Tests of Hypotheses. Springer, 2005.
A. Gretton and L. Gyorfi. Consistent nonparametric tests of independence. Journal of Machine Learning Research, 11:1391-1423, 2010.
A. Gretton, R. Herbrich, A. Smola, O. Bousquet, and B. Scholkopf. Kernel methods for measuring indepen- dence. Journal of Machine Learning Research, 6:2075 2129, 2005.
A. Gretton, K. Borgwardt, M. Rasch, B. Scholkopf, and A. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13:723-773, 2012.
G. Guillot and F. Rousset. Dismantling the mantel tests. Methods in Ecology and Evolution, 4(4):336 344, 2013.
T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science & Business Media, 2009.
S. Haufe, K. Müller, G. Nolte, and N. Krämer. Sparse causal discovery in multivariate time scries. In Proceedings of Workshop on Causalily: Objectives and Assessment al NIPS 2008, volume 6, pp. 97 106, 2010.
R. Heller, Y. Heller, and M. Gorfine. consistent multivariate test of association based on ranks of distances. Biomelrika, 100(2):503 510, 2013.
17

---

Published in Transactions on Machine Learning Research (05/2024)
R. Heller, Y. Heller, S. Kaufman, B. Brill, and M. Gorfine. Consistent distribution-free k-sample and independence tests for univariate random variables. Journal of Machine Learning Research, 17(29):1-544 2016.
C. Huang and X. Huo. A statistically and numerically efficient. independence test based random projections and distance covariance. Frontiers in Applied Mathematics and Statistics, 7:779841, 2022.
F. Laumann, J. Kügelgen, J. Park, B. Schölkopf, and M. Barahona. Kernel-based independence tests for causal structure learning on functional data. Entropy, 25(12):1597, 2023.
Y. Lee, C. Shen, C. E. Pricbe, and J. T. Vogelstein. Network dependence testing via diffusion maps and distance-based correlations. Biometriku, 106(4):857 873, 2019.
R. Li, W. Zhong, and L. Zhu. Feature screening via distance correlation learning. Journal of American Stalistical Associalion, 107:1 177:1129-10 1021129-11100 1139, 2012.
G. M. Ljung and G. E. Box. On a measure of a lack of fit. in time series models. Biometrika, 65(2): 297 303, 1978.
D. McDonald, C. Shalizi, and M. Schervish. Estimating beta-mixing coefficients. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 516 524, 2011.
W. Pan, X. Wang, H. Zhang, H. Zhu, and J. Zhu. Ball covariance: A generic mcasure of dependence in banach space. Journal of the American Statistical Association, 115(529):307-317, 2020.
T. D. Pham and L. T. Tran. Some mixing properties of time series models. Stochastic Processes and their Applications, 19(2):297-30) 1985.
D. Politis. The impact of bootstrap methods on time series analysis. Statistical Science, 18(2):219-25) 2003.
D. Sejdinovie, B. Sriperumbudur, A. Gretton, and K. Fukumizu. Equivalence of distance-based and rkhs- based statistics in hypothesis testing. Annals of Statistics, 41(5):2223-2) 2291, 2013.
C. Shen and Y. Dong. High-dimensional independence testing via maximum and average distance correla- tions. Xiv preprint arXi::2001.01995 2024.
C. Shen and J. T. Vogelstein. The exact equivalence of distance and kernel methods in hypothesis testing. AStA Advonces Statistical Analysis, 105(3):385-4033 2021.
C. Shen, C. E. Priebe, and J. T. Vogelstein. From distance correlation to multiscale graph correlation. Journal of the Americun Statistical Association, 115(529):280 291, 2020.
C. Shen, S. Panda, and J. T. Vogelstein. The chi-square test of distance correlation. Journal of Computational and Graphical Statistics, 31(1):254-200 2022.
Shi, M. Drton, and Han. azadkia--hatttrrjee's conditional dependence coefficient, 2021.
H. Shi, M. Drton, and F. Han. On the power of chatterjoe's rank correlation. Biometrika, 109(2):317-333, 2022.
R. H. Shumway and D. S. Stoffer. Time Series Analysis and Its Applications: With R Ezamples. Springer Science & Business Media, 2010.
G. Szekely and M. Rizzo. Brownian distance covariance. Annols of Applied Statistics, 3(4): 113113333133, 2009.
G. Szekely and M. Rizzo. Partial distance correlation with methods for dissimilarities. Annals of Statistics, 22(6):238222444 24122 2014.
G. Szekely, M. Rizzo, and N. Bakirov. Measuring and testing independence by correlation of distances. Annals of Statistics, 35(6):2769 2794, 2007.
18

---

Published in Transactions on Machine Learning Research (05/2024)
J. T. Vogelstein, Q. Wang, E. Bridgeford, C. E. Priebe, M. Maggioni, and C. Shen. Discovering and deciphering relationships across disparate data modalities. eLife, 8ee41690, 2019.
G. Wang, W. Li, and K. Zhu. New HSIC-based tests for independence between two stationary multivariate time series. Statistica Sinica, (1):)22 -000,,000,,0000 2021.
I. Winkler, D. Panknin, D. Bartz, K. Mülle, and S. Haufe. Validity of time reversal for testing granger causality, IEEE Transactions on Signal Processing, 64((1))2774 2760, 2016.
K. Xu, Y. Zhou, L. Zhu, and R. Li. Reducing multivariate independence testing to two bivariate means comparisons. arXiv preprint arXic:2402. 160553 2024.
Q Zhang, S. Filippi, A. Gretton, and D. Sejdinovic. Large-scale kernel methods for independence testing, Statistics and Computing, 28(1):113-130) 2018.
Y. Zhou, K. Xu, L. Zhu, and R. Li. Rank-based indices for testing independence between two high- dimensional vectors. The Annals of Stalislies, 52(1))184 206, 2024.
C. Zhu, S. Yao, X. Zhang, and X. Shao. Distance- Distance-based and rkhs-based dependence metrics in high dimension. The Annals of Stabistics, 48(6))3366 3394, 2020.
L. Zhu, K. Xu, R. Li, and W. Zhong. Projection correlation between two random vectors. Biometrika, 104 (4):829 843, 2017.
Ziemann and Tu. Learning with little mixing. In Aduances Neural Information Processing Systems, volume 35, pp. 4626 4637, 2022.
19

---

Published in Transactions on Machine Learning Research (05/2024)
APPENDIX
A Assumptions
We begin by revisiling the theoretical assumplions listed in the main paper:
The observed data {(X,, 1 is strictly stationary, non-constant, and the underlying distribution Fxy_, has finite moments for any lag 2 0.
There exists maximum dependence lag M such that for all 2 M, the two time series are almost independent for large n, so are each time series within itself:
sup Pux/ FxPy| 0 1
sup Fxx_, FxFx 0
7
sup FYY_, Fy 0 -
The maximum dependence lag M and the maximum lag under consideration L are non non-negative integers that satisfics 2 M and L= o(n), i.e., they may inerease together with n but at slower pace.
As the sample size n increases, both the number of blocks B and the number of observations per n increase to infinity. Morcover, 2 M for sufficiently large n.
block B
The sample dependence measure has the following form:
To (),88 Σ ii Ei= (i,j))
n²
where each Yn (1. a function of (X,, x, Yú, Yj), and remaining sample pairs may also be used but with weight of O(1/n).
In the standard i.i.d. setting where (X1, Yi); (X2, Y2).... (Xn, Yn) i.d. Fxy, there exists popula- tion statistic Y) defined solely based on the joint distribution Fxy. Each term in the sample statistic satisfies:
= -(X,
Moreover, the population statistic r(X, Y) non-negative and equals and only if X and Y are independent, i.e., Fxy Fy.
B Theorem Proofs
Theorem 1. The cross dependence sample statistic satisfies:
(x, o(1)
(x, = -
Therefore, for each E (0.... L), we have
Ta (x,Y_) 3330 7(X,Y-1)
in probability.

---

Published in Transactions on Machine Learning Research (05/2024)
Proof. First, applying the assumptions on the dependence measure to the cross dependence statistics yields:
Tn v-1 Lim 2j 7n-1(i,) (n 1)2 B( (1,3)) (X, + o(1).
Here, each (i is a function (X,, X,, 1-1, Yj-1), and remaining sample pairs like (Xu, Xu, Yws Yx) may also be used but with a weight of O(1/n).
As expectations additive, it immediately follows that
Ei Ej=1+1 E(mn-1(i,))
((T,(XXX_1))
11-22
E 2i44 > 2j-141 (T(X +1)1
(n=
= o(1).
Next, the variance equals
Var(T. (X, Cou(Ei=11 Ej=41 Va (i,]() Eu-141 Ex 7n (n-(u,,)) (n 1)1
Therefore, it suffices to consider each covariance term Cou(Tn--(i,1),, To In- u)), and there are (n 1)a such terms.
When both lu u--i M and IV jl M, the maximum dependent lag possible, we have
(ou(7n-((4,5), 7 v)) 0 n )-
Otherwise it is
Cou(7n-1(i,5)) m (1) O(1).
There are a total of O((n - (n - M) covariance terms of magnitude O ((__),, while the remaining 1)3) covariance terms are of magnitude 0(1). Consequently, as M o(n), we have
Var(T, (X, O((n - (n My² 0 ( + O((n 1)3) 0(1) (n (n- 1)a
0
which converges to 0 n increases.
With the expectation converging the population statistic and the variance approaching 0, conclude that
Tm (X,, " T(X,Y-1)
in probability.
Theorem 2. The temporal dependence sample statistic satisfies:
I. T T(X, Y
T p)
1=0
The estimated optimal dependence lag satisfies:
1. 2000
arg max T(X, Y-1).
[E(0.2]
2

---

Published in Transactions on Machine Learning Research (05/2024)
Proof. By Theorem each (x(,,Y-1) converges to T(X, Y-1) with variance of 0 ( ((n-)):
Recall the definition of the temporal dependence statistic Tn (X,, as
1
Tn f)
n
Im
Then the expectation satisfies
B(TT(X,V)) = Σ
11 T(X,Y-1) +
1=0
(x Y-1)
1=0
by noting Chat L is fixed and the weight n-t converges Moreover, the variance satisfies
L
(X, 0 n-L
which also converges to 0. Consequently,
Σ (X)Y-1)
Imo
in probability.
Similarly, the estimated optimal dependence lag satisfies
n2 n- (x, Y-1)
i arg max LE(0,2] 72
no max 7(X, Y-1) [E
in probability.
Theorem 3 (Asymptotic Validity). Under the null hypothesis that X and y are independent for all lags E [0, L), the test statistic satisfies:
T) 0.
Moreover, the permutttrttnnoionn test is asymptotically valid, i.c., Prob(T,((x88) 2 zn,a) "00 a.
Proof. By Theorem we have
Ta(X, n Σ T(X,Y_)) Y-1).
1=0
From the assumption of the population measure, when X, and Y, are independent for all lags 1 E [0, L}, we must have
T(X,Y-))= =0
for all 1 E [0, LJ. As result,
Tx,X, "2000
3

---

Published in Transactions on Machine Learning Research (05/2024)
To establish the asymptotic validity of the block permutation test, it suffices to prove that when X and Y are independent, we have:
sup supl (x( - PTyl " 0.
In other words, the true mull distribution and the permuted distribution asymptotically the same, then it follows that under the null hypothesis:
PTo Y) 2 2n.a) 4 a.
Here, T)) is a function of (X,, j,, Yu, Yo) for u, = 1, and the permuted statistic T, (X, (X,Y))) is the same function but on (Xi, Xj, Yu, Yv)), where u' and v' represent the permuted indices of and Therefore, it suffices to prove that under the null hypothesis, the distribution of (X,,Xj; Yu' Yv' converges to the distribution of (X,, Xj, Y,) for sufficiently large Note that under the standard i.d. setting, these two distributions are identical under the null hypothesis where X and are independent.
We first consider the case where both u and belong to the same block. In this case, and v' will also be the same block and differ by the same lag difference. Furthermore, due to the stationary assumption, FY..,, = Fyr. Now, as we are examining the null distribution where X and Y are independent, follows Chat
Yx,., Fx,xx Pr.. Fx,,x,Fr,,,y Y
Namely, X,. Yo) and X,, Yw,, Y are identically distributed in this case.
Next we examine the case where u and v belong to different blocks. Given our assumption of a maximum dependence lag M, uu > M and ju' - -01 > M for the permuted indices, we can establish the following:
sup Y...Y. Fx..x,,,....1
sup Xx,,x, FY, Fx,,,, Fy
Ssup Fx,,,, (Fy..Yo Fy, Fv.)) + sup/Fx..x, Fv, Fy,)I
+ supl Fx x, (Fv, - Fr..),)l
= =(1)
Here, the first and third terms are (1) as per our maximum dependence lag assumption, while the second term exactly 0 because the marginals within the brackets remain identical before and after permutation. Consequently, in this case, (X,, Yu, Y,) is asymptotically equivalent in distribution XX, Yu, Ye)..
Finally, in the case where and v belong to different blocks, there are two additional possibilities: either Iu 1-wl vl < M or u/= S M. In either case, we longer have exact distribution equivalence nor asymptotic equivalence. The number of instances where (X,, Yu, Yv) does not match XX, Y., Yyr in distribution is at most O), which equals o(n²) by our assumption on M and B.
Therefore, laking all the above arguments together, as the sample size n goes to infinity, we have:
Fx,,,,y,,,, - 0) + for any random block permutation æв satisfying our assumption. As the result,
Prob(suplFy..0..3 Fr.,(XP.g)) 0) 1.
Namely, the sample statistic and the bock-permuted statistic have asymptotically the same distribution, and the test is asymptotically valid.
Theorem (Testing Consistency). Under the alternative hypothesis that X and Y are dependent for some lag E [0, L), the test statistic satisfies
T,, "0 c> 0.
Moreover, the block- pereupeemttttion test asymptotically consistent, i.c.,
Prob(T,, (x, Zn.a) n "=00 1.
4

---

Published in Transactions on Machine Learning Research (05/2024)
Proof. From the assumption the dependence measure, when there exists at least one lag / such that the two time series are dependent, must have:
7 (X,Y_1) c-t 0.
As all other cross dependence sample statistics are non-negative, it follows that
Tn Σ c110
To prove consistency under the permutation test, it suffices to show that any type 1 error level a, when the two time series are dependent for some lag, the p-valuc of sample dependence mcasure is less than a as the sample size approaches infinity. Note that Theorem 8 in Shen et. al. (2020) proved consistency of standard permutation test between two i..d. sample data, and the follow-on proof has similar steps but with significant adjustment for the block permutation procedure.
In the block permutation test, the p-value be expressed follows:
Prob(T.. R > T, (X,
B
Prob(T. (X, )n > (x((XY)) is a partial derangement of size w)
X Prob(partial derangement of size w).
This expression conditions on the block permutation being a partial derangement of size w E [0, B), where w = 0 implics that TB a derangement where no two blocks remain in their original positions, and w = B means that тB does not permute any blocks.
As B oo, from the basic property of derangement we have
Prob(partial derangement of size w) c //w.
Because T,(X, + 0 under dependence, it suffices to prove that for any c 0,
B Prob Prob (T,(X, VTa) ) cl partial derangement of size w)/wi ww! + 0.
lim 11000
(1)
We decompose the above summations into two different cases. The first case when is of fixed size, then X and Yx are asymptotically independent. This is because, for fixed w, the number of observations that are not moved is fixed and asymptotically goes to 0, and all remaining blocks are shifted to different positions. By the maximum dependence lag M, which is o(n), and the number of samples per block being larger than M, the block permutation makes all other observation pairs asymplotically independent. Therefore, given i.j, and j being their block-permutee indices, we must have
sup Ex.,Xy - Fx,,x, Frg.ry, o(1)
so long - > M and - > M, which asymptotically holds for all blocks who moved the block position. Therefore, when w is fixed size, X and Yx are asymptotically independent, and we have
T,(X, +
as the sample statistic converges to the population, and the population statistic equals under independence.
The other case is the remaining partial derangements 7y of increasing size w, but these partial derangements occur with probability converging to 0. Formally, for any 0, there exists B, such that
1/wl < a/2.
B1+1
_nnbbers
5

---

Published in Transactions on Machine Learning Research (05/2024)
B
This is because Σ 1/w! is bounded above and converges to e. Then back to the first case, we can find w== B2 B1 such that for any w S B1 and all B B2,
(ro,(Tn(XX cl partial derangement of size w) < a:2.
Therefore, for all B B2:
B
e
1
( > cl partial derangement of size w) w)/w!
==0
Bi
< e
0x 2/ol + +e Σ
1/w!
1==0
w0 B +1
Thus the convergence Equation 1
holds.
In conclusion, any type error level O, the p-value of the temporal dependence sample statistic under the block permutation test will eventually be less than increases. Therefore, the proposed test is consistent against all dependencies with finite second moments, and its testing power converges to when the time series X and Y are dependent.


Reviews:
[{"review_id": "v3yZbwoPJY", "reviewer": "Reviewer_xdHS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the paper is well-written and easy to follow. The proposed method is a welcomed addition to existing literature.\nWeaknesses: Some theoretical proofs may need to be modified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new permutation test for independence between two (multi-variate) time series. Since the test is permutation-based, various existing correlation measures can be used for testing. Theoretical justifications as well as numerical examination of the proposed method are given, and the results are interesting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I notice that although the methodology is described for multi-variate time series, all examples given in the simulation study and real data analysis are bivariate. It would also be interesting to show how the testing power changes as the dimension increases in the simulation study. For the real data analysis, one can also test for independence between different networks, in addition to ROIs.\n\n2. I have some doubts about the proof of Theorem~3, where the authors state that \"it suffices to prove that under the null hypothesis, $(X_i, X_j, Y_u, Y_v)$ and $(X_i, X_j, Y_{u′}, Y_{v′} )$ are identically distributed \". However, the randomness of the permutation test statistic comes from the random permutation while conditioned on the observed data. I don't think such an argument will hold. Perhaps the proof can be modified similarly to those in [1], for example.\n\nReferences:\n\n[1] DiCiccio, C. J., & Romano, J. P. (2017). Robust permutation tests for correlation and regression coefficients. Journal of the American Statistical Association, 112(519), 1211-1220.", "broader_impact_concerns": "No concern here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7mk3nyigLd", "reviewer": "Reviewer_fn2g", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* Testing independence for time series is a relevant and interesting topic\n* The experimental evaluation included several synthetic and one real world data set\n* Block permutations could be a feasible approach to independence testing in this scenario\n* The proposed algorithm is intuitive and simple. It can leverage different dependence statistics. \n\n## Weaknesses\n* *Non-stationarity assumption*: One of the main assumptions of the proposed algorithm is stationarity of the data. Almost all other algorithms in the statistical learning literature rest on that assumption, so it's a standard assumption. But in this particular setting, time series with potentially slow frequencies (in particular frequencies slower than the Nyquist frequency of the signals in the data), this assumption could deserve some more attention. If there were trends / slow oscillations in the data, the stationarity between the blocks could be violated; or at least these variations in the data could affect the dependence measures. Often time series methods employ some preprocessing, such as temporal difference operators, to reduce these effects. I would assume that in some cases similar techniques could make sense for the proposed method as well? \n* *Lag estimation*: An important step in the proposed algorithm is the identification of the correct lag. The size of the blocks and the autocorrelation structure of the data are intimately related to this estimation process. It would be great to see how the proposed approach performs in more realistic and controlled conditions, where there are multivariate time series with more complex temporal dynamics governing the dependency structure between the two time series. \n* *Experimental evaluation*: The experimental evaluation is well done in some parts, and I do appreciate the synthetic data experiments, which are simple but highlight some main aspects. However there seems to be a substantial gap between the synthetic data experiments (univariate, very simple temporal dependency, no autocorrelation structure) and the real world data (multivariate, very complex spatiotemporal dependencies, strong autocorrelation structure). Especially for time series data with few samples and very high dimensionality, the proposed methods should be very robust to noise and confounding factors in the autocorrelation structure. \n* *Related work*: While the work appears interesting, there seems to be several fields of research relevant to this work. I don't think it's necessary to reference all of these below, but a quick literature research surfaced a number of scientific communities that have worked on the very problem discussed in the present study from a theoretical side as well as on the application side (fMRI data):\n    \n    * **ICA**: There appears to be a a lot for work in the ML community around independence of time series in the Independent Component Analysis (ICA) community (see e.g. [Independent component analysis: algorithms and applications](https://www.sciencedirect.com/science/article/abs/pii/S0893608000000265)). Some other factor model based approaches also use the idea of temporal embeddings, which is similar to the lagged time series approach in the present study [Temporal Kernel CCA](https://link.springer.com/article/10.1007/s10994-009-5153-3)\n    * **Mixing**: The notion of mixing processes has been investigated for some time in the statistics community - these references are not meant to be representative, I just picked some that appeared relevant top the application scenario and that highlight the lines of work: [SOME MIXING PROPERTIES OF TIME SERIES MODELS](https://d1wqtxts1xzle7.cloudfront.net/69497400/0304-4149_2885_2990031-620210912-26917-167rbdn-libre.pdf?1631501125=&response-content-disposition=inline%3B+filename%3DSome_mixing_properties_of_time_series_mo.pdf&Expires=1710414657&Signature=aJgJw5OqipMAnhUSm9SgTGGHbK2pUCEt9Aann6JEh2fNofSs57~6louo6n3aknFiHRo6~8SlMXbFJxI1-YSiCCtz~wSWdJpSAG2xrke2UfGK8ayU1h~Yh2MpUZsb5GycQxh6Kd0TOiKBuaI7d8jHun8Ub5xednO3H1WSlURBbcKa4j2h7DkjiTMoIR8f9BOXJQA6oaRvD85-afY9jbikFAiGPZPrCuL1ID5Zesx~Omok3KrHEOWnc~9EdllV1KqrT3TerMn-ZlM73sNBhXeXsIGXtKTnblNjdtzpYFv~81j~Jx1iXJvAhs~tiErPn4deVQ5uVKFlyz~UlxtzSOx0FA__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA), [Estimating beta-mixing coefficients](https://proceedings.mlr.press/v15/mcdonald11a.html), [Learning with little mixing](https://proceedings.neurips.cc/paper_files/paper/2022/hash/1dc9fbdb6b4d9955ad377cb983232c9f-Abstract-Conference.html), [A Note on Mixing in High Dimensional Time Series](https://arxiv.org/abs/1911.10648)\n    * **Causality** The methods developed in econometrics and applied to neuroimaging data appear to be relevant to the problem tackled here, too. My understanding was that some of these often used methods don't really work on real world neuroimaging data, mostly due to low specificity / testing power and high noise of neuroimaging data, see also [A critical assessment of connectivity measures for EEG data: A simulation study](https://www.sciencedirect.com/science/article/abs/pii/S1053811912009469), [Sparse causal discovery in multivariate time series](https://proceedings.mlr.press/v6/haufe10a), [Validity of Time Reversal for Testing Granger Causality](https://ieeexplore..ieee.org/abstract/document/7412766)\n    * **ICA for neuroimaging/fMRI** There seems to be a substantial body of literature on ICA for fMRI, which could be discussed or at least compared against, see e.g. [Blind Source Separation of Multiple Signal Sources of fMRI Data Sets Using Independent Component Analysis](https://journals.lww.com/jcat/fulltext/1999/03000/blind_source_separation_of_multiple_signal_sources.16.aspx) or [Validating the independent components of neuroimaging time series via clustering and visualization](https://www.sciencedirect.com/science/article/pii/S1053811904001661)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors present an approach to statistical testing of independence for time series data. Building on previous work on non-parametric independence testing, the proposed approach consists of a sequence of steps which themselves have been well established, but in their composition would be interesting as a simple and modular approach to time series testing. The theoretical part of the work could be discussed better in light of the existing literature, in its present form the manuscript seems to have a rather small focus. As for the experimental evaluation there seems to be a bit of a gap betwen the rather simple set of simulation studies (univariate, very simple temporal dependency, no autocorrelation structure) followed by an experiment on fMRI data  (multivariate, very complex spatiotemporal dependencies, strong autocorrelation structure).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "For a better assessment of the pros and cons of the proposed method, it would be great if the authors could:\n\n* embed the work a bit better in existing literature and discuss connections with other approaches / theoretical work\n* work on the experimental evaluation:\n    * try to close the gap between simulation and real world data by considering multivariate data that has similar characteristics as the fMRI data, more realistic noise and autocorrelation structure\n    * maybe compare with existing methods for the same application scenario", "broader_impact_concerns": "Testing for independence is an important tool that could be used in a variety of scenarios once published in a standard package. The impact of methods that do not correctly identify independence could be broad, hence assessment under realistic conditions would be important.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "i82YJrejZt", "reviewer": "Reviewer_WM9r", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*:\n- explicit assumptions\n- simple method\n- clear presentation\n- strong theoretical results\n\n*Weaknesses*:\n- some terminology/notation inconsistencies and typos", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a simple but powerful independence test for structured data, with clearly stated assumptions, good theoretical guarantees, and corroborative experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "*Critical*:\n- None!\n\n*Suggested*: (in order of appearance)\n- be consistent with either \"time-series\" or preferably \"time series\" \n- \"... can inflate the p-value and result in [an] invalid test.\"\n- \"... fMRI data reveals various temporal [dependences]...\"\n- add discussion of xi correlation/Chatterjee's coefficient (e.g., take a look at Azadkia and Chatterjee (2021) and Shi, Drton, Han (2021))\n- \"criterion\" instead of \"Criterion\" when writing out HSIC\n- \"The proposed method consists [of] four steps:\" \n- consistently use  \"Type I error\" instead of \"type 1\" or \"type-1\"\n- write \"number of blocks\" instead of \"block size\"\n- remove extra \")\" in third sentence of Section 3.3 \n- be consistent with \"p-value\" vs \"*p*-value\"", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The findings in the paper are backed up both by theoretical developments and a diverse of empirical results. This area of research is important in many applied domains and has connections to many subfields of machine learning.
Decision: Accept (poster)