Suppose we have access to $n$ empirical observations of two random variables X,Y and we want to know - are X,Y independent? One way to answer this is to compute empirical versions of various statistical quantities like covariance and mutual information. However, because all we have access to is a finite number ($n$) of empirical observations, we might simply get unlucky. Can we guarantee that our test accuracy increases rapidly with $n$? The Hilbert Schmidt Independence Criterion (HSIC) proposed by Gretton, Bousquet, Smola and Scholkopft resolves this issue by providing an estimate of dependence that provably gets more accurate at a $1/\sqrt{n}$ rate. In this talk, I will describe (following Gretton et al. in http://www.gatsby.ucl.ac.uk/~gretton/papers/GreBouSmoSch05.pdf) how HSIC arises quite naturally as a kernel invariant version of the covariance estimate and also allude to some later applications of HSIC.
