Sharp tail distribution estimates for the supremum of a class of sums of i.i.d. random variables.

Péter Major

2015. október 22.

The problem we are interested in 2

Let ξ_{1}, …, ξ_{n} be a sequence of i.i.d. random variables with some distribution μ on a measurable space (X , X). Let a class of functions F consisting of countably many functions be given on the space (X , X) with the properties ∫ f (x)μ( dx) = 0, sup_{x∈X} |f (x)| ≤ 1 and ∫ f (x)^{2}μ( dx) ≤ σ^{2} with some 0 < σ ≤ 1 for all elements f ∈ F. Let F be a class of functions with polynomially increasing covering numbers with exponent L ≥ 1 and parameter D ≥ 1. (I recall the definition of this notion later.) Define the normalized sums S_{n}(f ) = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f (ξ_{j}) for all f ∈ F, and give a good estimate on the tail distribution

P (sup_{f ∈F} S_{n}(f ) > v) for all numbers v > 0

of the supremum of these sums. This estimate may depend on σ, L and D.

An additional remark: By an important result, called the concentration inequality, the distribution of this supremum is concentrated in a small neighbourhood of a concentration point. As a consequence, the tail distribution we are investigating is small only if v is larger than this concentration point. In our estimation we want to find a good level above which this tail distribution begins to decrease radically. This is a hard and important part of our problem.

I recall the definition of classes of functions with polynomially incerasing covering numbers together with the exponent L and parameter D of these classes. I do it in two steps. This notion is a useful version of the Vapnik–Červonenkis classes, when we are working with classes of functions instead of classes of sets.

Definition of a class of functions with polynomially increasing covering numbers 4

First step of the definition.

Definition of uniform covering numbers with respect to L_{1}-norm. Let a measurable space (X , X) be given together with a class of measurable, real valued functions F on this space. The uniform covering number of this class of functions at level ε, ε > 0, with respect to the L_{1}-norm is sup_{ν} N (ε, F, L_{1}(ν)), where the supremum is taken for all probability measures ν on the space (X , X), and N (ε, F, L_{1}(ν)) is the smallest integer m for which there exist some functions f_{j} ∈ F, 1 ≤ j ≤ m, such that min_{1≤j≤m} ∫ |f − f_{j}| dν ≤ ε for all f ∈ F.

Second step of the definition.

Definition of a class of functions with polynomially increasing covering numbers. We say that a class of functions F has polynomially increasing covering numbers with parameter D and exponent L if the inequality

sup_{ν} N (ε, F, L_{1}(ν)) ≤ Dε^{−L}

holds for all 0 < ε ≤ 1 with the number sup_{ν} N (ε, F, L_{1}(ν)) introduced in the previous definition.

First I discuss an example which indicates what kind of results we can expect in our problem. We are mainly interested in the case when the exponent L and the parameter D are bounded (by a number not depending on σ^{2}), and σ^{2} may be very small.

A useful example 6

Example. Take a sequence of independent, uniformly distributed random variables ξ_{1}, …, ξ_{n} on the unit interval [0, 1], fix a number 0 ≤ σ^{2} ≤ 1, and define a class of functions F_{σ} and F̄_{σ} as set of functions defined on the unit interval [0, 1] in the following way. F_{σ} = \{f_{1}, …, f_{k}\}, and F̄ = \{f̄_{1}, …, f̄_{k}\} with k = k(σ) = [\frac{1}{σ^{2}} ], where [·] denotes integer part, and f̄_{j}(x) = f̄_{j}(x|σ) = 1 if x ∈ [(j − 1)σ^{2}, jσ^{2}), f̄_{j}(x) = f̄_{j}(x|σ) = 0 if x ∉ [(j − 1)σ^{2}, jσ^{2}), 1 ≤ j ≤ k, and f_{j}(x) = f_{j}(x|σ) = f̄_{j}(x) − σ^{2}, 1 ≤ j ≤ n. Give a good estimate on P_{n}(v) = P(sup_{j} S_{n}(f_{j}) > v).

F satisfies our conditions. It is a class of functions with polynomially increasing covering numbers with exponent L and parameter D which do not depend on σ^{2}, and the parameter σ^{2} introduced in the model is an upper bound for all ∫ f_{j}(x)^{2}μ( dx).

Our first question: For which numbers is P_{n}(v) much smaller than 1? Answer to this question:

An estimate on the function P_{n}(v) in the models of the above example. A number C̄ > 0 can be chosen in such a way that for all δ > 0 there is an index n_{0}(δ) such that for all sample sizes n ≥ n_{0}(δ) and numbers 0 ≤ σ ≤ 1 the inequality

P_{n}(û(σ)) = P ( sup_{f ∈F_{σ}} |S_{n}(f )| ≥ û(σ)) ≥ 1 − δ,

holds with 1.) û(σ) = \frac{C̄}{\sqrt{n}} if σ^{2} ≤ n^{−400},

2.) û(σ) = \frac{C̄}{\sqrt{n}} _{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} if n^{−400} < σ^{2} ≤ \frac{log n}{8n}, and

3.) û(σ) = C̄σ log^{1/2} \frac{2}{σ} if \frac{log n}{8n} ≤ σ^{2} ≤ 1.

This result says that we cannot get a good estimate on the probability we are interested for v ≤ û(σ). First I explain this result, then I discuss what we can say if v > û(σ).

In case 3.) of this example σ^{2} is relatively large. In this case the S_{n}(f ) behaves similarly to the Gaussian case, (like a functional of a Brownian bridge), and similar estimates hold for the tail distribution of sup_{f ∈F} S_{n}(f ) as in the corresponding Gaussian model. But to get such a good estimate we need this condition. K. S. Alexander also observed this fact in his research.

In case 2.) S_{n}(f ) does not have a good Gaussian, but has a good Poissonian approximation. This provides a slightly weaker estimate than in case 1.), since the Poissonian tail distribution tends to zero slower at ∞ than the Gaussian one. Here we explained what we get in this case.

In case 1.) we considered the case when σ^{2} is very small. Here we exploited the trivial fact that if we take an arbitrary partition of the probability space a sample point gets into one of the elements of the partition. In this case this observation provides the right estimate.

The next Theorem (the main result of this paper) states that in the general case we get an estimate suggested by the above example. Actually the situation is somewhat more complex, since we also consider the case when the parameters L and D may be large.

We can get a good estimate on P(sup_{f ∈F} |S_{n}(f )| > v) only if v > û(σ). We also want to find the tail distribution in this case. Bernstein’s and Bennett’s inequality suggest the upper bound e^{−C\sqrt{n}log(v/\sqrt{n}σ^{2}} if v ≥ const. \sqrt{n}σ^{2} and e^{−Cv^{2}/σ^{2}} if v ≤ const. \sqrt{n}σ^{2}. (See my lecture note On the estimation of multiple random integrals an U-statistics).

In cases 1.) and 2.) û(σ) ≥ const.\sqrt{n}σ^{2}, and the Theorem gives the estimate we expect. Case 3.) is more complex. In the Theorem we give the estimate we expect if v ≥ const. \sqrt{n}σ^{2}. (The situation is somewhat more difficult, because we also deal with the case when the parameters L and D are large.) In Case 3.) it is possible that û(σ) < v ≤ const. \sqrt{n}σ^{2}. We prove the (Gaussian) estimate we expect in this case in an Extension of the Theorem.

Theorem. Let a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n}, n ≥ 2, with values in (X , X) with some distribution μ and a countable class of functions F on the same space (X , X) with polynomially increasing covering numbers with exponent L ≥ 1 and parameter D ≥ 1 be given. Let the functions f ∈ F satisfy the relations sup_{x∈X} |f (x)| ≤ 1, ∫ f (x)μ( dx) = 0, and ∫ f^{2}(x)μ( dx) ≤ σ^{2} with some number 0 ≤ σ^{2} ≤ 1 for all f ∈ F. The normalized sums S_{n}(f ), f ∈ F, satisfy the inequality

P (sup_{f ∈F} |S_{n}(f )| ≥ v)≤ C_{1}e^{−C_{2} \sqrt{n}v log(v/\sqrt{n}σ^{2}} for all v ≥ u(σ)

with some universal constants C_{j} > 0, 1 ≤ j ≤ 5, if one of the following conditions is satisfied. 1.) σ^{2} ≤ \frac{1}{n^{400}} , and u(σ) = \frac{C_{3}}{\sqrt{n}}(L + \frac{log D}{log n}),

2.) \frac{1}{n^{400}} < σ^{2} ≤ \frac{log n}{8n}, and u(σ) = \frac{C_{4}}{\sqrt{n}} (L_{\frac{log n}{log( \frac{log n}{nσ^{2}} )}} + logD),

3.) \frac{log n}{8n} < σ^{2} ≤ 1, and u(σ) = \frac{C_{5}}{\sqrt{n}}(nσ^{2} + L logn + logD).

Next we consider the case σ^{2} ≥ \frac{log n}{8n} and \sqrt{n}σ^{2} ≥ v ≥ ū(σ) with some ū(σ) which has the same order of magnitude as û(σ). Actually this result was proved earlier.

Extension of the Theorem. Let us consider, similarly to the Theorem, a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n}, n ≥ 2, with values in a space (X , X) with some distribution μ which satisfies the conditions of the Theorem. In the case \frac{log n}{8n} < σ^{2} ≤ 1 the supremum of the normalized sums S_{n}(f ), f ∈ F, satisfies the inequality

P (sup_{f ∈F} |S_{n}(f )| ≥ v)≤ Ce^{−αv^{2}/σ^{2}}

with appropriate (universal) constants α > 0, C > 0 and C_{6} > 0 if \sqrt{n}σ^{2} ≥ v ≥ ū(σ), where ū(σ) is defined as ū(σ) = C_{6}σ(L^{3/4} log^{1/2} \frac{2}{σ} + (logD)^{1/2}).

The idea of the proof 12

We choose an appropriate number δ > 0, and choose by exploiting that F is a class of functions with polynomially increasing covering numbers m = Dδ^{−L} functions f_{j} ∈ F, 1 ≤ j ≤ m, and set of functions D_{j} ⊂ F in such a way that ∫ |g − f_{j}| dμ ≤ δ, if g ∈ D_{j} and ⋃_{j=1}^{m} D_{j} = F. We can write

P (sup_{f ∈F} |S_{n}(f )| ≥ v)  (1)

≤ P ( sup_{1≤j≤m}|S_{n}(f_{j})| ≥ \frac{v}{2}) + ∑_{j=1}^{m}P ( sup_{f ∈D_{j}} |S_{n}(f − f_{j})| ≥ \frac{v}{2}).

We choose δ > 0 in an appropriate way. Then we can give a good estimate on the second term of the sum at the right-hand side of (1) by means of my paper Sharp estimate on the supremum of a class of sums of small i.i.d. random variables. The first term can be estimated by means of the inequality

P ( sup_{1≤j≤m}|S_{n}(f_{j})| ≥ \frac{v}{2}) ≤ ∑_{j=1}^{m}P (|S_{n}(f_{j})| ≥ \frac{v}{2})

and Bennett’s inequality. The theorem can be proved in such a way.

The Extension of the Theorem can be proved similarly. Only in this case the first term at the right-hand side of (1) must be estimated in a different way. We exploit the properties of the class of functions G = {f_{1}, …, f_{m}}, and give a good estimate with the help of the chaining argument. (Observe that G is a class of functions with polynomially increasing covering numbers).

Some remarks on the problem 14

In a previous paper I gave a good estimate on the probability P(sup_{f ∈F} S_{n}(f ) > v) if F is a class of functions with polynomially increasing covering numbers consisting of functions bounded by 1, and ∫ |f (x)|μ( dx) ≤ ρ with a sufficiently small ρ. More precisely, ρ ≤ n^{−α} with an appropriate α > 1. Here μ denotes the distribution of the random variables we are working with.

This result played a crucial role in our investigation. It enabled us to reduce the problem to the case where we take the supremum for an appropriate finite subset of F, because it made possible to control the small contribution of the disregarded terms to the supremum we are investigating.

This approach is similar to the truncation technique applied in the proof of limit theorems, by which the small but irregular effect of the large terms is disregarded. Here a similar method is applied.

The chaining argument or a more refined version of it worked out by Talagrand enables us to handle the regular effects in similar problems. But the control of the small irregularities demands a different method. In earlier works the irregularities were controlled by means of a method called the symmetrization argument. In the present paper I could find a more powerful method that works under more general conditions.

The control of the irregular effects is a more general, open problem. Here we exploited that the class of functions we are working with has polynomially increasing covering numbers. Other models have other good properties, and we have to find the method to exploit them.

On the other hand, I consider a method to control the irregularities good only if I see models where it it gives new results. I met some generalizations of the symmetrization argument which demanded new complicated notions and arguments. But as I saw no real application of them I do not know whether they are useful.