Last week I was reading Active Learning via Perfect Selective Classification by El-Yaniv and Wiener, and came across a neat result due to Hug and Reitzner that they use in some of their bounds for active learning on Gaussian distributions.
The setup is the following : let be jointly Gaussian vectors with distribution in . The convex hull of these points is called a Gaussian polytope. This is a random polytope of course, and we can ask various things about their shape : what is the distribution of the number of vertices, or the number of -faces? Let be the number of -faces Distributions are hard, but for general the expected number of faces (as ) is given by
where is the internal angle of a regular -simplex at one of its -dimensional faces. What Hug and Reitzner show is a bound on the variance (which then El-Yaniv and Plan use in a Chebyshev bound) : there exists a constant such that
So the variance of the number of -faces can be upper bounded by something that does not depend at all on the actual value of . In fact, they show that
in probability as . That is, appropriately normalized, the number of faces converges to a constant.
To me this result was initially surprising, but after some more thought it makes a bit more sense. If you give me a cloud of Gaussian points, then I need points to define a -face. The formula for the mean says that if I chose a random set of points, then approximately fraction of them will form a real -face of the polytope. This also explains why the simplex-related quantity appears — points that are on “opposite sides” of the sphere (the level sets of the density) are not going to form a face together. As this fraction will change, but effectively the rate of growth in the number of faces with is , regardless of .
I’m not sure where this result will be useful for me (yet!) but it seemed like something that the technically-minded readers of the blog would find interesting as well.