HOW CLOSE IS THE NORMAL DISTRIBUTION?
One of the first things you learn in probability is that the average has a distribution that is approximately Normal. More precisely, if are iid with mean and variance then
and means “convergence in distribution.”
1. How Close?
But how close is the distribution of to the Normal? The usual answer is given by the Berry-Esseen theorem which says that
where is the cdf of a Normal(0,1) and . This is good news; the Normal approximation is accurate and so, for example, confidence intervals based on the Normal approximation can be expected to be accurate too.
But these days we are often interested in high dimensional problems. In that case, we might be interested, not in one mean, but in many means. Is there still a good guarantee for closeness to the Normal limit?
Consider random vectors with mean vector and covariance matrix . We’d like to say that is close to where and . We allow the dimension grow with .
One of the best results I know of is due to Bentkus (2003) who proved that
where is the class of convex sets and . We expect that so the error is of order . This means that we must have to make the error go to 0 as .
2. Ramping Up The Dimension
So far we need to justify the Normal approximation which is a serious restriction. Most of the current results in high dimensional inference, such as the lasso, do not place such as severe restriction on the dimension. Can we do better than this?
Yes. Right now we are witnessing a revolution in Normal approximations thanks to Stein’s method link.
This is a method for bounding the distance from Normal approximations invented by Charles Stein in 1972.
Although the method is 40 years old, there has recently been an explosion of interest in the method. Two excellent references are the book by Chen, Goldstein and Shao (2012) and the review article by Nathan Ross which can be found here.
An example of the power of this method is the very recent paper by Victor Chernozhukov, Denis Chetverikov and Kengo Kato. They showed that, if we restrict to rectangles rather than convex sets, then
as long as . (In fact, they use a lot of tricks besides Stein’s method but Stein’s method plays a key role).
This is an astounding improvement. We only need to be smaller than instead of .
The restriction to rectangles is not so bad; it leads immediately to a confidence rectangle for the mean, for example. The authors show that their results can be used to derive further results for bootstrapping, for high-dimensional regression and for hypothesis testing.
I think we are seeing the beginning of a new wave of results on high dimensional Berry-Esseen theorems. I will do a post in the future on Stein’s method.
Bentkus, Vidmantas. (2003). On the dependence of the Berry-Esseen bound on dimension. Journal of Statistical Planning and Inference, 385-402.
Chen, Louis Goldstein, Larry and Shao, Qi-Man. (2010). Normal approximation by Stein’s method. Springer.
Victor Chernozhukov, Denis Chetverikov and Kengo Kato. (2012). Central Limit Theorems and Multiplier Bootstrap when p is much larger than n. http://arxiv.org/abs/1212.6906.
Ross, Nathan. (2011). Fundamentals of Stein’s method. Probability Surveys, 8, 210-293.
Stein, Charles. (1986), Approximate computation of expectations. Lecture Notes-Monograph Series 7.