  It is a common saying that testing for conditional independence, i.e.,
testing whether whether two random vectors $X$ and $Y$ are independent, given
$Z$, is a hard statistical problem if $Z$ is a continuous random variable (or
vector). In this paper, we prove that conditional independence is indeed a
particularly difficult hypothesis to test for. Valid statistical tests are
required to have a size that is smaller than a predefined significance level,
and different tests usually have power against a different class of
alternatives. We prove that a valid test for conditional independence does not
have power against any alternative.
  Given the non-existence of a uniformly valid conditional independence test,
we argue that tests must be designed so their suitability for a particular
problem may be judged easily. To address this need, we propose in the case
where $X$ and $Y$ are univariate to nonlinearly regress $X$ on $Z$, and $Y$ on
$Z$ and then compute a test statistic based on the sample covariance between
the residuals, which we call the generalised covariance measure (GCM). We prove
that validity of this form of test relies almost entirely on the weak
requirement that the regression procedures are able to estimate the conditional
means $X$ given $Z$, and $Y$ given $Z$, at a slow rate. We extend the
methodology to handle settings where $X$ and $Y$ may be multivariate or even
high-dimensional. While our general procedure can be tailored to the setting at
hand by combining it with any regression technique, we develop the theoretical
guarantees for kernel ridge regression. A simulation study shows that the test
based on GCM is competitive with state of the art conditional independence
tests. Code is available as the R package GeneralisedCovarianceMeasure on CRAN.
