Sparse correlation and the Central Limit Theorem

Back when I was a PhD student working on generalisations of GEE, I was interested in ‘sparse’ correlations, defined by ‘most’ small sets of observations being independent. One way to get this structure is from crossed clustering variables; another is for the basic units in your analysis to be pairs (or larger tuples) of observations. If you drew a graph with the variables as vertices, and connected correlated variables, then two subsets of the variables would be independent of each other if there was no edge between them.

To see what this implies in large samples, consider a balanced incomplete multi-rater experiment with $K$ raters and $D$ objects to be rated, in which each rater rates $1 < d \leq D$ of the objects and each object is rated by $1 < k \leq K$ of the raters. The number of ratings is $n = K d = k D$ . Two ratings are connected by an edge in the dependence graph if they share a rating or share a rating. The maximal degree of the graph is $M = k + d - 1$ . We are interested in the case where $K$ and $D$ are both large.

Consider a simple parametric random-effects model for the rating $Y_{i j}$ by rater $i$ of object $j$ $Y_{i j} = μ + a_{i} + b_{j} + ϵ_{i j}$ where $μ$ is a fixed constant, $a_{i} \sim N (0, σ_{a}^{2})$ , $b_{j} \sim N (0, σ_{b}^{2})$ , and $ϵ_{i j} \sim N (0, σ_{ϵ}^{2})$ . The variance of $S_{n} = \sum_{i j} Y_{i j}$ is $σ_{n}^{2} = n σ_{ϵ}^{2} + K d^{2} σ_{a}^{2} + k^{2} D σ_{b}^{2} = n σ_{ϵ}^{2} + n d σ_{a}^{2} + n k σ_{b}^{2} .$

The ratio $σ_{n}^{2} / M n$ will be bounded above and bounded away from zero if $σ_{a}^{2}$ and $σ_{b}^{2}$ are both non-zero, and we will have $S_{n} / n = {\bar{X}}_{n} \overset{p}{\to} μ$ as long as $K, D \to \infty$ .

Now, let’s look at a scaled version of ${\bar{X}}_{n} - μ$ . We can’t just scale it by $\sqrt{n}$ as in the independent setting, because the variance of ${\bar{X}}_{n}$ is $O (M / n)$ rather than $O (1 / n)$ . We can still hope for $\sqrt{\frac{n}{σ_{n}^{2}}} ({\bar{X}}_{n} - μ) \overset{d}{\to} N (0, 1),$ since at least it’s the right size. In the simple multi-rater case it certainly works.

Encouragingly, we get the same sort of limit if we have $M$ identical copies of each of $m$ independent items, as another way to get sparse correlation.

Proving it?

The first thing I tried was to see if the moments of ${\bar{X}}_{n}$ did anything helpful. I thought I had a proof, in fact, but it was wrong. The idea does work if you do it with cumulants; Svente Janson did it correctly, ten years earlier, and published it under the title Normal Convergence by Higher Semiinvariants with Applications to Sums of Dependent Random Variables and Random Graphs. I hadn’t found it in searching, and no-one I talked to at the time had heard of it.

The second thing I tried was to adapt a Central Limit Theorem for random fields by Xavier Guyon, which I’d already used in my thesis. The proof uses something called Stein’s Method, and involves a counting bound on ‘close’ pairs of pairs of observations and a long-range weak dependence bound on ‘distant’ pairs of pairs. I could just dump the ‘distant’ part of the proof and make it work for sparse correlation. Success!!

Nicole Mayer-Hamblett and I had a manuscript about asymptotics for sparsely-correlated generalised linear models, with some nice examples, and we got revision requests from a journal and then neither of us had time to do the revision. Then I worked out how to prove an exponential tail bound for sparse correlation and sent it off to a probability journal. They thought it was maybe ok, but that I needed to look up something called graph-structured dependence in the probability literature. That turned out to be the same Central Limit Theorem proof that I had (only a bit tidier and with an explicit error bound) and had already been published. In 1989. Sigh.

The Theorem

Let $X_{1}, \dots, X_{n}$ be random variables such that $E [X_{i}^{4}] < \infty$ , $E [X_{i}] = 0$ , $σ^{2} = v a r [\sum_{i} X_{i}]$ and define $S = \sum_{i} X_{i} / σ$ . Let $M$ be the maximal degree of a dependency graph for the $X_{i}$ . Then for $Z$ a standard Normal variable $d_{W} (S, Z) \leq \frac{M^{2}}{σ^{3}} \sum_{i} E | X_{i}^{3} | + \frac{\sqrt{28} M^{3 / 2}}{\sqrt{π} σ^{2}} \sqrt{\sum_{i} E | X_{i}^{4} |}$ where $d_{W}$ is the Wasserstein distance.

Scaling

The example of the parametric inter-rater experiment suggests that $M / n \to 0$ should be enough for a central limit theorem, but the actual theorem seems to require a stronger condition. If the $X_{i}$ were identically distributed and $σ^{2}$ scaled as $n$ , the first term would have order $O (M^{2} n / n^{3 / 2})$ and we would need $M^{2} n^{- 1 / 2} \to 0$ . However, in the setup of the inter-rater experiment, if the rater and object variance components are non-zero, we actually have $σ^{2}$ scaling as $n M$ , so $σ^{3}$ scales as $M^{3 / 2} n^{3 / 2}$ . The first term in the bound is $O (M^{1 / 2} n^{- 1 / 2})$ and $M / n \to 0$ is indeed sufficient.

Janson’s result using cumulants instead of Stein’s method doesn’t need the extra variance components to be non-zero, but it does impose stronger conditions on the tails of the $X_{i}$ .

When working on asymptotic distributions for mixed-model parameters I’m reasonably happy to assume that true variance components are positive – if instead they are on the boundary of the parameter space, special arguments will be needed in any case. The variance assumptions are more of a concern when the graph-structured dependence is induced by sampling rather than by a model for the outcome.