Classical dependence measures such as Pearson correlation, Spearman's $\rho$,
and Kendall's $\tau$ can detect only monotonic or linear dependence. To
overcome these limitations, Szekely et al.(2007) proposed distance covariance
as a weighted $L_2$ distance between the joint characteristic function and the
product of marginal distributions. The distance covariance is $0$ if and only
if two random vectors ${X}$ and ${Y}$ are independent. This measure has the
power to detect the presence of a dependence structure when the sample size is
large enough. They further showed that the sample distance covariance can be
calculated simply from modified Euclidean distances, which typically requires
$\mathcal{O}(n^2)$ cost. The quadratic computing time greatly limits the
application of distance covariance to large data. In this paper, we present a
simple exact $\mathcal{O}(n\log(n))$ algorithm to calculate the sample distance
covariance between two univariate random variables. The proposed method
essentially consists of two sorting steps, so it is easy to implement.
Empirical results show that the proposed algorithm is significantly faster than
state-of-the-art methods. The algorithm's speed will enable researchers to
explore complicated dependence structures in large datasets.

本文提出了一个简单的算法，用于计算两个一元随机变量之间的距离协方差。该算法基本上包括两个排序步骤，时间复杂度为 $O (nlog (n))$，比现有技术更快速。该算法的速度可以帮助研究人员探索大型数据集中复杂的依赖结构。

一种快速计算距离相关性的算法

A fast algorithm for computing distance correlation

We propose a framework to analyze and quantify the bias in adaptive data
analysis. It generalizes that proposed by Russo and Zou'15, applying to
measurements whose moment generating function exists, measurements with a
finite $p$-norm, and measurements in general Orlicz spaces. We introduce a new
class of dependence measures which retain key properties of mutual information
while more effectively quantifying the exploration bias for heavy tailed
distributions. We provide examples of cases where our bounds are nearly tight
in situations where the original framework of Russo and Zou'15 does not apply.

提出了一种分析和量化自适应数据分析中偏差的方法，引入了一种新的依赖度量，同时保留了互信息的关键性质，并更有效地量化了具有重尾分布的探索偏差。

一般测量的依赖性度量约束探索偏差

Dependence Measures Bounding the Exploration Bias for General  Measurements

A new computationally efficient dependence measure, and an adaptive
statistical test of independence, are proposed. The dependence measure is the
difference between analytic embeddings of the joint distribution and the
product of the marginals, evaluated at a finite set of locations (features).
These features are chosen so as to maximize a lower bound on the test power,
resulting in a test that is data-efficient, and that runs in linear time (with
respect to the sample size n). The optimized features can be interpreted as
evidence to reject the null hypothesis, indicating regions in the joint domain
where the joint distribution and the product of the marginals differ most.
Consistency of the independence test is established, for an appropriate choice
of features. In real-world benchmarks, independence tests using the optimized
features perform comparably to the state-of-the-art quadratic-time HSIC test,
and outperform competing O(n) and O(n log n) tests.

提出了一种新的计算有效的依赖度量和自适应统计独立性检验方法，其特点是数据高效运行时间为线性，并且在真实基准中表现良好。

具有分析核嵌入的独立性自适应测试

An Adaptive Test of Independence with Analytic Kernel Embeddings

Reshef et al. recently proposed a new statistical measure, the "maximal
information coefficient" (MIC), for quantifying arbitrary dependencies between
pairs of stochastic quantities. MIC is based on mutual information, a
fundamental quantity in information theory that is widely understood to serve
this need. MIC, however, is not an estimate of mutual information. Indeed, it
was claimed that MIC possesses a desirable mathematical property called
"equitability" that mutual information lacks. This was not proven; instead it
was argued solely through the analysis of simulated data. Here we show that
this claim, in fact, is incorrect. First we offer mathematical proof that no
(non-trivial) dependence measure satisfies the definition of equitability
proposed by Reshef et al.. We then propose a self-consistent and more general
definition of equitability that follows naturally from the Data Processing
Inequality. Mutual information satisfies this new definition of equitability
while MIC does not. Finally, we show that the simulation evidence offered by
Reshef et al. was artifactual. We conclude that estimating mutual information
is not only practical for many real-world applications, but also provides a
natural solution to the problem of quantifying associations in large data sets.

提出了一种新的统计量 —— 最大信息系数 (MIC)，用于量化随机数量对之间的任意依赖关系，但证明了 MIC 不满足平等性定义。因此，我们提出了自洽且更普遍的平等性定义，并表明互信息满足这一新的定义，而 MIC 则不满足。最后，证明了 Reshef 等人提供的模拟证据是人为的。因此，我们得出结论，估计互信息不仅在许多实际应用中是可行的，而且还提供了一个自然的解决方案来量化大数据集中的相关性问题。