Source-linked AI summary
The Randomized Dependence Coefficient
David Lopez-Paz, Philipp Hennig, Bernhard Schölkopf
TL;DR
Measuring nonlinear dependence is difficult because standard measures cover limited association patterns and many nonlinear alternatives are computationally demanding. The paper introduces RDC, a scalable estimator of HGR based on nonlinear copula projections and canonical correlation. RDC is invariant to marginal transformations, applies to arbitrary-dimensional variables, performs well empirically, and is easy to implement, while its nonlinear feature family remains an unavoidable assumption.
Problem
Standard dependence measures cover limited association patterns, while HGR’s infinite-dimensional optimization is not computable.
Method
RDC estimates HGR using random nonlinear projections of empirical copula transformations followed by maximal canonical correlation.
Results
RDC is invariant to monotonically increasing marginal transformations, supports arbitrary-dimensional variables, has O(n log n) sample-size cost, and performs well empirically.
Takeaways & Limitations
RDC is a lightweight dependence measure that is scalable to very large datasets and easy to adapt to concrete problems.
Takeaways & Limitations
The choice of nonlinearities is an unavoidable assumption, and selecting their family and distribution requires prior assumptions about the data typically analyzed.
Abstract
from arXiv · showhide
We introduce the Randomized Dependence Coefficient (RDC), a measure of non-linear dependence between random variables of arbitrary dimension based on the Hirschfeld-Gebelein-Rényi Maximum Correlation Coefficient. RDC is defined in terms of correlation of random non-linear copula projections; it is invariant with respect to marginal distribution transformations, has low computational cost and is easy to implement: just five lines of R code, included at the end of the paper.
1 Introduction
Dependence measures such as Pearson’s rho, Spearman’s rank, and Kendall’s tau are efficient but cover limited association patterns. The paper develops RDC to address the computational and scalability challenges of nonlinear dependence measurement.
- Classical measures efficiently capture linear or monotonically increasing associations but not the broader range of nonlinear patterns.
- Existing nonlinear measures broaden the detectable association patterns but often require at least quadratic computational cost in sample size.
- RDC estimates HGR by correlating random nonlinear projections of empirical copula transformations.
- RDC is invariant to monotonically increasing marginal transformations and supports random variables of arbitrary dimension.
- RDC has O(n log n) sample-size cost and can be implemented in five lines of R code.
2 Hirschfeld-Gebelein-R´enyi’s Maximum Correlation Coefficient
Rényi proposed seven properties for dependence measures, and HGR satisfies them. However, HGR’s infinite-dimensional optimization is not computable, motivating RDC as a scalable estimator with the same structure.
- Rényi’s seven properties require dependence measures to be broadly defined, symmetric, bounded between 0 and 1, and zero exactly under independence.
- The properties also require invariance under bijective Borel-measurable transformations and value one when either variable is a measurable function of the other.
- For jointly Gaussian variables, Rényi’s seventh property identifies the dependence measure with the absolute Pearson correlation.
- HGR satisfies all seven properties and is defined as the supremum of Pearson correlation over finite-variance Borel-measurable transformations.
- Because HGR optimizes over an infinite-dimensional function space, it is not computable and requires a scalable estimator such as RDC.
3 Randomized Dependence Coefficient
RDC estimates nonlinear dependence by applying random nonlinear projections to empirical copula transformations and taking their largest canonical correlation. The procedure preserves dependence while removing marginal-form effects, with computational costs dominated by copula estimation in the typical large-sample setting.
- 3 Randomized Dependence Coefficient: RDC computes dependence from the largest canonical correlation between random nonlinear projections of two samples’ copula transformations.Its pipeline consists of copula transformation, random nonlinear projection, and canonical-correlation computation.
- 3.1 Estimation of Copula-Transformations: The copula transformation maps each marginal through its cumulative distribution function, producing uniform marginals while preserving the original dependence structure.Empirical copula transformations estimate these mappings from multivariate samples.
- 3.1 Estimation of Copula-Transformations: Empirical copula transformations converge to the true transformation as sample size increases, while computing them requires O(dn log(n)) operations.The convergence result is based on the Massart-Dvoretzky-Kiefer-Wolfowitz inequality.
- 3.2 Generation of Random Non-Linear Projections: Random nonlinear feature expansions allow subsequent linear methods to capture nonlinear dependencies in the original data.The feature family is an unavoidable assumption; the paper uses sine and cosine projections with random parameters.
- 3.3 Computation of Canonical Correlations: CCA selects linear combinations of the augmented copula features whose projections have maximal correlation.The largest canonical correlation is the supremum over correlations between linear projections, with CCA costing O((p + q)^2n).
4 Properties of RDC
RDC combines random nonlinear copula projections with canonical correlation to provide a scalable estimator related to HGR. Its properties include near-linearithmic sample complexity, an implementation in R, and explicit approximation conditions and limitations.
- Computational complexity: O((p+q)n log n+kn log(pq)+k^2n) ≈ O(n log n) is RDC’s computational cost in the typical large-n, large-dimensional, small-k setting.The cost is dominated by computing the copula transformations.
- Ease of implementation: An R implementation of RDC is included in Appendix A.
- Relationship to the HGR coefficient: RDC’s relationship to HGR is not guaranteed to provide a consistent or efficient estimator, motivating examination of finite-sample behavior.The paper explicitly questions consistency and efficiency and reports that a simple experiment shows RDC is not an exact finite-sample substitute for HGR.
- Relationship to the HGR coefficient: Under the RKHS assumption for the optimal transformations, the approximation bound combines finite-sample CCA error with random-feature approximation error.The transformations are assumed to lie in an RKHS with a bounded shift-invariant positive semi-definite kernel; the sample size is n and the number of random features is k.
- Relationship to other estimators: RDC becomes equivalent to KCCA only with infinitely many sine/cosine features, matching Fourier sampling, and omitted copula transformations; k ≥ n requires regularization.
- Relationship to other estimators: Table 1 compares dependence measures by nonlinear scope, dimensionality, marginal invariance, statistic range, Rényi properties, and parameter requirements.
5 Experimental Results
Experiments evaluate RDC on synthetic dependence patterns, running times, feature selection, and scalar association estimates. RDC performs well across varied non-linear patterns and feature-selection datasets, while remaining computationally efficient.
- Experimental setup: The experiments validate RDC against non-linear dependence measures on synthetic and real-world data, omitting KCCA in some cases because of prohibitive running times.RDC uses k = 10 random features, with larger values available when computational budgets permit.
- Resistance to additive noise: RDC shows good performance on non-functional associations under increasing additive Gaussian noise, including circles and mixtures of sinusoidal waves.It performs worse for linear associations because of noise overfitting and for step functions because sine/cosine projections impose a smoothness prior.
- Running times: Running times are averaged over 100 runs for independent scalar samples spanning sample sizes {10^3, . . . , 10^6}.Compiled C implementations are used for Pearson’s ρ, ACE, dCor and MIC, whereas RDC and several kernel methods use interpreted R code.
- Value of statistic in [0, 1]: RDC, ACE, dCor, MIC, Pearson’s ρ, Spearman’s rank and Kendall’s τ are compared on 14 scalar bivariate associations.RDC scores near one on proposed dependent associations and near zero on the independent association.
- Feature selection in real-world data: RDC performs best in most real-world feature-selection datasets, with much lower running time than its contenders.The experiments summarize performance as the number of selected features increases.
6 Conclusion
The conclusion presents RDC as a lightweight, multivariate non-linear dependence measure constructed in the spirit of HGR. It reports good empirical performance, scalability to very large datasets, and adaptability to concrete problems.
- 6 Conclusion: RDC is presented as a lightweight non-linear dependence measure for multivariate random samples.Its construction follows the finite-dimensional estimator perspective of the HGR maximum correlation coefficient.
- 6 Conclusion: The conclusion states that RDC performs well empirically, scales to very large datasets, and is easy to adapt to concrete problems.
- 6 Conclusion: RDC’s empirical evaluation includes power under increasing noise and estimates across several bivariate association patterns.The referenced figures summarize synthetic-data behavior and dependence estimates for multiple measures.
A R Source Code
The R source code implements RDC by transforming samples through empirical copulas, applying random sine/cosine projections, and returning the first canonical correlation.
- A R Source Code: The function signature rdc <- function(x,y,k,s) takes two inputs and projection parameters k and s.
- A R Source Code: The code applies empirical CDF transformations, appends an intercept, and generates random projection matrices for both samples.The projection matrices have k columns and Gaussian entries with scale parameter s.
- A R Source Code: RDC computes sine and cosine features for each projected copula and returns the first canonical correlation.