Sharp estimate on the supremum of a class of sums of small i.i.d. random variables.

Péter Major

2015. október 7.

Formulation of the problem, motivation, and methods to solve it 2

The problem: 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 be given on the space (X , X) with some nice properties, such that ∫ f (x)μ( dx) = 0 and sup_{x∈X} |f (x)| ≤ 1 for all elements f ∈ F. 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 ) > x) for all numbers x > 0

of the supremum of these sums.

An important 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 above probability is small only if x is larger than this concentration point. An important and hard part of the problem is to find a good level above which this probability begins to decrease radically. This means a good estimate on value of the concentration point. This is the hardest part of the problem.

(We want to give an estimate on the concentration point with the accuracy of a universal multiplying constant.)

Our motivations to study this problem 4

Motivation 1.: Dudley’s theory of uniform central limit theorem. Given a nice class of functions F and a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n} prove that the class of normalized sums S_{n}(f ) = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f (ξ_{j}), f ∈ F, satisfy some sort of functional limit theorem. Crucial point of the proof: Show that sup_{f ,f′∈F′} S_{n}(f − f′) is small if F′ ⊂ F, and F′ has the property that E[f (ξ_{1}) − f′(ξ_{1})]^{2} < δ with a small δ > 0 for all f , f′ ∈ F′. We have formulated a natural generalization of this problem, where we may consider δ_{n} → 0 as n → ∞ instead of a fixed δ > 0.

Motivation 2.: To get good limit theorems for so-called non-parametric maximum likelihood estimates it is useful to prove sharp estimates on the tail distribution of the supremum of multiple integrals with respect to normalized empirical distibution functions, i.e. of expressions of the form:

sup_{f ∈F} ∫ ⋯ ∫ f (x_{1}, …, x_{k})

\sqrt{n}(dF_{n}(x_{1}) − dF (x_{1})) … \sqrt{n}(dF_{n}(x_{k}) − dF (x_{k})),

where F is a distribution function F_{n} is the empirical distribution function of an F distributed sample, and F is a nice class of functions of k variables. (See my lecture note On the estimation of multiple random integrals and U-statistics.) Here we investigate this problem for k = 1.

The Gaussian version of the problem 6

The sums S_{n}(f ) = \frac{1}{\sqrt{n}} ∑_{j=1}^{n}f (ξ_{j}) satisfy the central limit theorem.

Hence it is natural to consider a Gaussian version of our problem. We want to understand what kind of results and methods suggests the result of this Gaussian version. The Gaussian problem: Let η_{t}, Eη_{t} = 0, t ∈ T , be a countable set of random variables with (jointly) Gaussian distribution. Put d_{2}(s, t) = [E(η_{s} − η_{t})^{2}]^{1/2}, s, t ∈ T . Then d_{2}(s, t) is a metric on the parameter set T . Give a good estimate on the probability P (sup_{t∈T} η_{t} > x) for all numbers x > 0 with the help of the function d_{2}(s, t).

The result about the Gaussian problem 7

There is a simple and natural method, called the chaining argument to study this problem. It yields the following result. Theorem. Let η_{t}, t ∈ T , be a set of Gaussian random variables indexed by a countable set T . Assume that Eη_{t} = 0, Eη_{t}^{2} ≤ σ^{2} with some 0 ≤ σ ≤ 1 for all t ∈ T , and the metric d_{2}(s, t) = [E(η_{s} − η_{t})^{2}]^{1/2}, s, t ∈ T , has the following property. There exist some constants L ≥ 1 and D ≥ 1 such that for all 0 ≤ ε ≤ 1 a subset {t_{1}, …, t_{P}} ⊂ T can be found with cardinality P ≤ Dε^{−L} for which min_{1≤j≤P} d_{2}(t, t_{j}) ≤ ε for all t ∈ T . Then the inequality

P ( sup_{T ∈T} |η_{t}| ≥ u) ≤ C(D + 1) exp\{−\frac{1}{256} (\frac{u}{σ} )^{2}\}

if u ≥ ML^{1/2}σ log^{1/2} \frac{2}{σ}

holds with some universal constants C > 0 and M > 0.

A comparison of our problem with the above result 8

In our problem F plays the role of the parameter set T , and d_{2}(f , g)^{2} = E(S_{n}(f − g)^{2}) = ∫ [f (x) − g(x)]^{2}μ( dx), f , g ∈ F. The previous theorem also holds if the random variables η_{t}, t ∈ T , are non-Gaussian, but they satisfy the Gaussian type inequality

P(|η_{t} − η_{s}| > u) ≤ C_{1}e^{−C_{2}u^{2}/d_{2}(s,t)^{2}} for all s, t ∈ T and u > 0

with some constants C_{1} > 0 and C_{2} > 0. What is the case in our problem? Some classical results (e.g. Bernstein’s inequality) provide the above inequality under some restriction, (e.g. if u ≤ const.\sqrt{n}d_{2}^{2}(s, t)), but it may not hold without such a restriction. (See my lecture note On the estimation of multiple random integrals and U-statistics, Chapter 3.)

To get results similar to the Gaussian case for sums of bounded i.i.d. random variables some additional restriction has to be imposed, and the proof requires new ideas. I know of two approaches. Approach 1. Due to Talagrand. Define the metric d_{∞}(f , g) = sup_{x∈X} |f (x) − g)x)|, f , g ∈ F, and introduce the additional condition that there exist some constants D ≥ 1 and L ≥ 1 such that for all 0 ≤ ε ≤ 1 P ≤ D(n^{−1/2}ε)^{−L} functions f_{j} ∈ F, 1 ≤ j ≤ P, can be found for which min_{1≤j≤P} d_{∞}(f , f_{j}) ≤ ε for all f ∈ F. This condition together with the condition on the metric d_{2}(·, ·) in the theorem about the Gaussian version imply a similar estimate. Talagrand proved a stronger result formulated with a different terminology in his book The generic chaining.

The proof is based on an appropriate version of the chaining argument. In the proof we exploit that if the terms of a sum of independent random variables have a very small bound in the supremum norm, then the tail distribution of the sum has a good Gaussian upper bound even at high levels.

Talagrand found interesting applications of his result, but there are important models where it does not work.

Example where Talagrand’s result cannot be applied. Let (X , X) be the unit interval [0, 1] with the Borel σ-algebra, let ξ_{1}, …, ξ_{n} be i.i.d. random variables on [0, 1] with uniform distribution. Put F = {f_{a,b}(x)}, where 0 ≤ a < b ≤ a + σ^{2} with a small number σ^{2} > 0, a, b are rational numbers, and f_{a,b}(x) = I_{a,b}(x) − (b − a), where I_{a,b}(·) is the indicator function of the interval (a, b).

This example satisfies the conditions we imposed for our models, and the condition imposed on the metric d_{2}(·, ·) with parameters L and D which have an upper bound not depending on σ^{2}, but the d_{∞}(·, ·) metric behaves badly. But all functions f_{a,b} are far from each other in the supremum norm. To handle such models we introduce a different method.

Approach 2. (Based on a Vapnik–Červonenkis type argument.) We formulate an additional condition on F with the help of a notion called the class of functions with polynomially increasing covering numbers instead of the condition about the behaviour of the d_{∞} metric. We prove results with its help.

We give the definition of a class of functions with polynomially increasing covering numbers in two steps. 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.

There is a good estimate for the probability of P(sup_{f ∈F} |S_{n}(f ) > x) if the class of functions F has polynomially increasing covering numbers with some parameter D ≥ 1 and L ≥ 1. See On the estimation of multiple random integrals and U-statistics, Theorem 4.1. This result describes fairly well when we can get such a good estimate in our problem as in its Gaussian counterpart.

The proof is based on some ideas of K. S. Alexander, and applies the so-called symmetrization argument. It says that under some not too restrictive conditions sup_{f ∈F} ∑_{j=1}^{n} f (ξ_{j}) has a similar tail distibution as its randomized version sup_{f ∈F} ∑_{j=1}^{n} ε_{j}f (ξ_{j}), where ε_{1}, …, ε_{n} are i.i.d. random variables, independent also of the random variables ξ_{j}, and P(ε_{1} = 1) = P(ε_{1} = −1) = \frac{1}{2}. The symmetrized version sup_{f ∈F} ∑_{j=1}^{n} ε_{j}f (ξ_{j}) can be better handled than the original expression, and this is exploited in the symmetrization argument..

Nevertheless, this technique gives a weak estimate if Ef (ξ_{1})^{2} ≤ σ^{2} for all f ∈ F with a very small σ^{2}. In this case the above mentioned Theorem 4.1 in my lecture note does not give a sharp estimate. Our goal is to give a sharp estimate in all cases. It turned out that the next result, the main result of the paper under discussion, plays a crucial role in achieving this goal. Here is this result.

Main theorem. Let F be a finite or countable class of functions on a measurable space (X , X) which has polynomially increasing covering numbers with some parameter D ≥ 1 and exponent L ≥ 1, and sup_{x∈X} |f (x)| ≤ 1 for all f ∈ F. Let ξ_{1}, …, ξ_{n}, n ≥ 2, be a sequence of i.i.d. random variables with values in the space (X , X) with a distribution μ, and assume that the inequality ∫ |f (x)|μ( dx) ≤ ρ holds for all f ∈ F with a number 0 < ρ ≤ n^{−200}. Put S̄_{n}(f ) = S̄_{n}(f )(ξ_{1}, …, ξ_{n}) = ∑_{j=1}^{n} f (ξ_{j}) for all f ∈ F. The inequality

P (sup_{f ∈F} |S̄_{n}(f )| ≥ u) ≤ Dρ^{Cu} for all u > 41L

holds with some universal constant 1 > C > 0. We can choose e.g. C = \frac{1}{50}.

(The condition ∫ f (x)μ( dx) = 0 for all f ∈ F is not needed in this result.)

An example that may help to understand the content of the Main theorem 15

Let (X , X) be a finite set with N elements, μ the uniform distribution on it, (μ(A) = \frac{1}{N} · the number of elements in A.) Fix a number d ≥ 1 and let F be the set of indicator functions of the subsets of X containing at most d elements. Let ξ_{1}, …, ξ_{n} be i.i.d. random variables, and define S̄_{n}(f ) = ∑_{1≤j≤n} f (ξ_{j}) with their help.

Question: What can we say about P(sup_{f ∈F} S̄_{n}(f ) > u)?

We are interested in the case when \frac{n}{N} is small. It is clear that P(sup_{f ∈F} S̄_{n}(f ) ≥ u) = 1 if u ≤ d. If u > d, then this probability is a fast decreasing function of u. (See Section 1 of the paper for details.) On the other hand the indicator functions {x : f (x) = 1}, f ∈ F, constitute a (classical) example of Vapnik–Červonenkis classes.

The notion of class of functions with polynomially increasing covering numbers can be considered as a version of Vapnik–Červonenkis classes for classes of functions, and these two notions behave similarly. In particular, by some results the class of functions in the above example has polynomially increasing covering numbers with exponenent L = (1 + ε)d for all ε > 0 and appropriate D = D(ε). Some considerations show that the main theorem can be interpreted in the following way:

For a class of functions F with polynomially increasing covering numbers and the property that sup_{f ∈F} ∫ |f (x)|μ( dx) is very small the tail distribution of | sup_{f ∈F} S̄_{n}(f )| satisfies such an inequality that the above (simple) example suggests.

The real role of the Main theorem 17

We are interested in the Main theorem not for itself. It is interesting for us, because it yields a better application of the Vapnik–Červonenkis argument than the symmetrization method.

The condition ∫ |f (x)|μ( dx) ≤ ρ for all f ∈ F with 0 < ρ ≤ n^{−200} is not very restrictive. This (together with the existence of polynomially increasing covering numbers in our models) enables us to split up the class of functions F into the union of relatively few subsets F_{j}, 1 ≤ j ≤ M, (M ≤ n^{K} with some K > 0) in such a way that fixing some f_{j} ∈ F_{j} the tail distribution of sup_{f ∈F_{j}} |S̄_{n}(f − f_{j})| can be well bounded by means of the Main theorem.

Since we have to work only with polynomially many subsets F_{j} ⊂ F we can give a better, more complete solution of our problem. This is the topic of my paper Sharp tail distribution estimates for the supremum of a class of sums of i.i.d. random variables.

The main ideas of the proof 18

Let X be a finite set with 2^{k} elements with a large integer k, μ be the uniform distribution on X . Consider a model satisfying the conditions of the Main theorem with such an X and μ, and prove the estimate of the Main theorem for P(sup_{f ∈F} S̄_{n}(f )| ≥ n). We may assume that f (x) ≥ 0 for all x ∈ X and f ∈ F.

We prove first this special result in Theorem 1A and then the Main theorem with its help. We prove Theorem 1A with the help of an induction procedure for k with a large starting number k_{0}. The starting step of the induction is done in Lemma 3.1. To carry out our induction procedure we need a result formulated in Lemma 3.2. This states that if a class of functions F with polynomially increasing covering numbers on a set X of cardinality 2^{k} with a large number k has the property ∫ f (x)μ( dx) ≤ ρ for all f ∈ F with the uniform distribution μ on X , then this property is preserved for most subsets of X with cardinality 2^{k−1} if ρ is replaced by a slightly larger ρ̄.

To prove Theorem 1A observe that sup_{f ∈F} S̄_{n}(f ) ≥ n if and only if there is some f ∈ F for which f (ξ_{j}) = 1 for all 1 ≤ j ≤ n. Hence to prove Theorem 1A we have to give a good estimate on the number of sequences (x_{l_{1}}, …, x_{l_{n}}) ∈ X^{n} such that x_{l_{j}} ∈ B_{f} = {x : f (x) = 1} for all 1 ≤ j ≤ n, and some f ∈ F. We prove such an estimate by means of induction with respect to k with the help of Lemma 3.2.

We assume that an appropriate estimate holds on the number of such sequences for classes of functions F with polynomially increasing covering numbers with exponent L ≥ 1 and parameter D ≥ 1 on a set X of cardinality 2^{k−1} if also the condition ∫ |f (x)|μ( dx) ≤ ρ_{k−1} holds for all f ∈ F with an appropriately chosen ρ_{k−1}. Then we prove the analogous result for parameter k with an appropriately chosen ρ_{k} by means of Lemma 3.2. We define for all functions f ∈ F and sets B ⊂ X of cardinality 2^{k−1} the function f_{B} as the restriction of f to B, and put F_{B} = {f_{B} : f ∈ F}.

Then by applying the inductional hypothesis for k − 1 for the sets B ⊂ X of cardinality 2^{k−1} with the classes of functions F_{B} and taking an average for all sets B of cardinality 2^{k−1} we get an estimate on the number of sequences (x_{l_{1}}, …, x_{l_{n}}) ∈ X^{n} with the requested properties. In this calculation we apply Lemma 3.2 and choose the constants ρ_{k} in an appropriate way. If we do this carefully, then we can carry out the induction procedure, and by letting k → ∞ we get the proof of Theorem 1A.

The crucial part of the problem is the proof of Lemma 3.2. Its main step is to show that ∫ (f_{B} − f_{X \B}) dμ is small with probability almost 1 for any f ∈ F, if we choose the set B randomly among the sets B ⊂ X of cardinality 2^{k−1}, and f_{B} denotes the restriction of f to the set B. This implies that ∫ f_{B} dμ_{B} ≤ ρ̄ with a number slightly larger than ρ with probability almost 1, where μ_{B} is the uniform distribution on B. With an appropriate choice of ρ̄ we can achieve that even sup_{f ∈F} ∫ f_{B} dμ_{B} ≤ ρ̄ with probability almost 1. Here we exploit that F has polynomially increasing covering numbers. The last inequality implies Lemma 3.2.

We can estimate the tail distribution of ∫ (f_{B} − f_{X \B}) dμ = 2^{−k}(∑_{x∈B} f (x) − ∑_{x∉B} f (x)), where B is a randomly chosen subset of X with cardinality 2^{k−1} by means of a method that appeared also in the proof of Lemma 3 of the paper Komlós–Major–Tusnády: An approximation of partial sums of independent rv’s and the sample DF. The method: Take a pairing (x_{l_{1}}, x_{l_{2}}),… (x_{l_{2^{k}} −1}, x_{l_{2^{k}}} ) of the set X , and define a random set B with 2^{k−1} elements by putting in each pair one randomly chosen element into the set B and the other one into the complementary set. We can well estimate the tail distribution of 2^{−k}(∑_{x∈B} f (x) − ∑_{x∉B} f (x)) if we choose only sets B obtained in such a way e.g. with the help of Hoeffding’s inequality. Then averaging for all possible pairings of X we can get the estimate we need to complete the proof of Lemma 2.2. Finally I briefly explain how to prove the Main theorem with the help of Theorem 1A.

First I give a good estimate on P(sup_{f ∈F} S̄_{n}(f ) > u) for all u > 0 under the conditions of Theorem 1A in Lemma 4.1. To prove this estimate I show that the event sup_{f ∈F} S̄_{n}(f ) > u may hold only if for some index j there is a relatively long sequence {l_{1}, …, l_{s}} ⊂ {1, …, n} such that f (ξ_{l_{1}}) ≥ 2^{−j},…, f (ξ_{l_{s}}) ≥ 2^{−j} for some f ∈ F. The probability of such an event can be well estimated with the help of Theorem 1A. Then a careful calculation provides the proof of Lemma 4.1.

The Main theorem is proved by means of Lemma 4.1. We can reduce the proof to the case when F is a finite set. If its cardinality is R, then we can approximate F = {f_{1}, …, f_{R}} with a class of functions G = {g_{1}, …, g_{R}} whose elements take only finitely many values, the μ-distribution of all events {g_{1}(x) = u_{1}, …, g_{R}(x) = u_{R}} is an integer multiplied by 2^{−k} with some number k, and the functions g_{j} are so close to the functions f_{j} that it is enough to prove the Main Theorem for G instead of F. On the other hand, this can be done with the help of Lemma 4.1.