Empirical Processes-Maximal Inequalities and Chaining

Empirical Processes: Maximal Inequalities and Chaining Moulinath Banerjee October 7, 2010 1 Maximal Inequalities The notes here are based on Section 8.1 of Kosorok’s book and Chapter 2.2 of van der Vaart and Wellner and should be read in accompaniment with these texts. Orlicz norms: Let ψ be a nondecreasing convex function with ψ(0) = 0 and X a random variable. Define the Orlicz norm corresponding to Ψ as:     |X| ≤1 . kXkΨ = inf C > 0 : E ψ C It can be checked that this is a valid norm (on the set of random variables for which the left side of the above display is finite). Of special interest to us will be the Orlicz norms corresponding to the functions {ψp : p ≥ 1} where ψp (x) = exp(xp ) − 1. Lemma 8.1 of Kosorok (2008) provides a necessary and sufficient condition for the ψp Orlicz norm to be finite in terms of the tail-behavior of X. As a consequence of this lemma, if P (|X| > x) ≤ K exp(−C xp ) for some constants C, K > 0, then  kXkψp ≤ 1+K C 1/p . (1.1) The Orlicz norm of the maximum of finitely many random variables can be bounded by the maximum of the individual Orlicz norms. This is the content of the next lemma which will be eventually seen to play an important role in controlling the oscillations of separable stochastic processes. Lemma 1.1 Let ψ be a convex, nondecreasing, nonzero function with ψ(0) = 0 and such that, for every M > 0, lim supx,y→∞ ψ(x) ψ(y)/ψ(cxy) < ∞ for some constant 0 < c < ∞. Then, for any 1 random variables X1 , X2 , . . . , Xm , k max Xi kψ ≤ K ψ −1 (m) max kXi kψ , 1≤i≤m 1≤i≤m with the constant K depending only on ψ. The Orlicz norms of interest to us all satisfy the conditions of the above lemma. Sketch of proof: The proof starts by consider ‘special’ ψ’s for which ψ(1) ≤ 1/2 and ψ(x) ψ(y) ≤ ψ(cxy) for all x, y ≥ 1. For such ψ’s an argument involving some algebra (see Page 130 of Kosorok) and the definition of the Orlicz norm and the concavity of the strictly increasing function ψ −1 shows the desired inequality with K = 2c. The generalization rests on the fact that for any ψ in the statement of the lemma, one can find constants 0 < σ < 1 and τ > 0 such that φ(x) = σ ψ(τ x) is a ‘special’ ψ. However the constant c for the φ just constructed above could be different from the constant c appearing in the limsup condition for ψ; however the new c still continues to depend only on ψ. The proof is completed by invoking the established result for the φ Orlicz norm and then translating this to what it means for the ψ Orlicz norm using the inequalities in Problem 8.5.3 (a), (b) of Kosorok. Exercise: Exercise 8.5.3 of Kosorok. Our next goal is to develop a maximal inequality for the Orlicz norm of the supremum of (possibly) uncountably many increments of a separable stochastic process X(t) using the above maximal inequality as a core tool. Bounds on such suprema will be developed in terms of the packing/ covering numbers of the indexing set T of the stochastic process with respect to semimetrics that are at least as strong as the one induced by the ψ norm. It will be seen that such bounds translate to bounds on the modulus of continuity for sub-Gaussian processes in terms of integrals of appropriate covering/packing numbers. Because the behavior of the modulus of continuity plays a central role in the convergence of processes in l∞ (T ) and empirical processes are a special case, it turns out that useful sufficient conditions for the distributional convergence of the empirical process can be obtained in terms of the so-callede ‘entropy integrals’, which are integrals involving the logarithms of the covering numbers. To develop a bound for the Orlicz 2 norm of the supremum in the first sentence of this paragraph, the trick is to construct a countably dense subset of T such that the supremum restricted to the countably dense subset equals the actual supremum and then to approximate the Orlicz norm of this restricted supremum by those of suprema over finite increasing subsets that approximate the countable set. The suprema over the finite increasing subsets can be handled by Lemma 1.1. Before proceeding further, two definitons. Sub-Gaussian processes: A stochastic process {X(t) : t ∈ T } will be called sub-Gaussian with respect to some semi-metric d on T if: 1 P (|X(t) − X(s)| > x) ≤ 2 exp(− x2 /d2 (s, t)) , forall s, t ∈ T . 2 There is nothing sacred about the constants 2 and 1/2 on the right side of the inequality as the following exercise demonstrates. Exercise: Suppose that P (|X(t) − X(s)| > x) ≤ K exp(−C x2 /d2 (s, t)) for all s, t, for positive constants K and C. Then the process is sub-Gaussian for a multiple of the distance d. (Exercise 14 on Page 106 of VDVW) Separable processes: A stochastic process X(t) is called separable if there exists a countable subset T? ⊂ T such that supt∈T inf s∈T? |X(s) − X(t)| = 0 almost surely. The next theorem gives the general maximal inequality. Theorem 1.1 Let ψ satisfy the conditions of Lemma 1.1 and let {X(t) : t ∈ T } be a separable stochastic process such that kX(s) − X(t)kψ ≤ r d(s, t) for some constant r and some semimetric d. Suppose also that D(, d) < ∞ for every  > 0. Then, for any η, δ > 0, Z sup |X(s) − X(t)| d(s,t)≤δ ≤K η ψ −1 (D(, d)) d + δ ψ −1  (D (η, d)) , 2 0 ψ for a finite constant K depending only on ψ and r. Furthermore: Z diam T sup |X(s) − X(t)| d(s,t)≤δ ≤ 2K 0 ψ 3 ψ −1 (D(, d)) d . Proof: Since D(, d) is finite for every positive , T is totally bounded with respect to d. We will construct a countably dense subset T∞ of T such that sups,t∈T∞ ;d(s,t)≤δ |X(s) − X(t)| is almost surely equal to sups,t∈T ;d(s,t)≤δ |X(s) − X(t)|. sups,t∈T∞ d(s,t)≤δ |X(s) − X(t)| ψ Then it suffices to find a bound on . The set T∞ = ∪∞ 0 Tk where T0 ⊂ T1 ⊂ T2 ⊂ . . . and Tj is a finite set of points satisfying the property that d(s, t) > η 2−j for every s 6= t ∈ Tj . Furthermore Tj is maximal in the sense that no points can be added to this set without violating the separation condition in the previous sentence. Note that the cardinality of Tj cannot be larger than D(η 2−j , d), so that each Tj is finite. We then construct the chains in the following manner: For every point tj+1 ∈ Tj+1 , find a point tj ∈ Tj such that d(tj , tj+1 ) ≤ η 2−j and ‘attach’ these points by a link. Then start with tj to get a tj−1 in similar fashion and proceed all the way back up to a t0 ∈ T0 . Note that the linkages are possible: if tj+1 ∈ Tj then tj can be taken to be tj+1 itself; if not, there has to be at least one point in Tj whose d-distance from tj+1 is no larger than η 2−j , for if not, Tj would not have been maximal in the first place. Our first goal is to control, for every k, Ek ≡ |X(s) − X(t)| sup . s,t∈Tk+1 ;d(s,t)≤δ ψ Note that the sup over a finite set is really a max. If s0 (s) and t0 (t) denote the end-points of the chains starting at s and t, it is not difficult to see that: Ek ≤ sup |(X(s) − X(s0 (s)) − (X(t) − X(t0 (t))| s,t∈Tk+1 ;d(s,t)≤δ + ψ sup |X(s0 (s)) − X(t0 (t))| s,t∈Tk+1 ;d(s,t)≤δ . ψ We now focus on the second term, say II with the first term being denoted I. Note that the number of pairs (s0 (s), t0 (t)) is no larger than D2 (η, d). For each such pair, select a unique ancestor for s0 (s), say s? , and a unique ancestor for t0 (t), say t? in Tk+1 (note that there can be multiple ancestors for a particular s0 (s) or a t0 (t)) such that d(s? , t? ) < δ. We have: |X(s0 (s)) − X(t0 (t))| ≤ |(X(s0 (s)) − X(s? )) − (X(t0 (t)) − X(t? )| + |X(s? ) − X(t? )| . Hence, II ≤ sup |(X(s0 (s)) − X(s? )) − (X(t0 (t)) − X(t? ))| s,t∈Tk+1 ;d(s,t)≤δ + ψ sup |X(s? ) − X(t? )| s,t∈Tk+1 ;d(s,t)≤δ Using Lemma 1.1, the second term in the above display can be bounded by a ψ-dependent constant C times ψ −1 (D2 (η, d)) δ, using the fact that the number of variables involved in the supremum in 4 . ψ the second term is at most D2 (η, d) and the fact that kX(s? ) − X(t? )kψ is atmost r δ. Both the first term in the above display and I are bounded by sup |(X(s) − X(s0 (s)) − (X(t) − X(t0 (t))| s,t∈Tk+1 ψ Rη and this term can be shown to be dominated by 4 K0 0 η Z Ek ≡ sup |X(s) − X(t)| s,t∈Tk+1 ;d(s,t)≤δ ≤ 8 K0 ψ −1 (D(, d)) d. It follows that: ψ −1 (D(, d)) d + C δ ψ −1 (D2 (η, d)) . 0 ψ Note that the right side does not depend on k. Since sups,t∈Tk+1 ;d(s,t)≤δ |X(s) − X(t)| increases to sups,t∈Tinf ;d(s,t)≤δ |X(s) − X(t)|, by monotone convergence for Orlicz norms (if random variables Yn ’s increase to Y , the Orlicz norm of Yn increases to that of Y ; see problem 6 on Page 105 of VDVW) we conclude that: Z E∞ ≡ sup |X(s) − X(t)| s,t∈T∞ ;d(s,t)≤δ ≤ 8 K0 η ψ −1 (D(, d)) d + C δ ψ −1 (D2 (η, d)) , 0 ψ which readily implies the first conclusion of the theorem. The second conclusion of the theorem follows by choosing δ = η = diam T and noting that then D(η, d) = D2 (η, d) = 1 and using the monotonicity of ψ −1 . The argument justifying the equality of the supremum over T and T∞ is the content of the following lemma. However, for some stochastic processes the equality follows from a more direct argument. For example, if you know that the paths of X are almost surely continuous with respect to d, the equality is immediate. 2 Lemma 1.2 sup s,t∈T∞ ;d(s,t)≤δ |X(s) − X(t)| = sup s,t∈T ;d(s,t)≤δ ψ |X(s) − X(t)| a.s. ψ This lemma, as well as Lemma 1.3 below depend on Exercise 8.5.5. of Kosorok stated below. Exercise 8.5.5 (Kosorok): Let ψ satisfy the conditions of Lemma 1.1. Show that for any sequence of random variables Xn , kXn kψ → 0 implies that Xn →P 0. (Hint: lim inf x→∞ x−1 ψ(x) > 0.) Proof of lemma: Since X was assumed separable, there exists a countable susbet of T , say T? , such that on a set Ω? with P (Ω? ) = 1, supt∈T inf s∈T? |X(s) − X(t)| = 0. Now, fix a point in t. If d(t, tn ) goes to 0, the conditions of the theorem guarantee that kX(t) − X(tn )kψ goes to 0. By the exercise above X(tn ) converges to X(t) almost surely along a subsequence. Now, consider the (countably dense) subset T∞ of T that we used in the chaining argument. For each t ∈ T? , 5 there is a (t–dependent) sequence tn in T∞ converging to t, which implies that for some subsequence {tnk }, Xtnk converges to X(t) on a set Ωt with P (Ωt ) = 1. Let Ω̃ = Ω? ∩ (∩t∈T? Ωt ). This set has probability 1 and on this set , supt∈T inf s∈T∞ |X(s) − X(t)| = 0. To show this last inequality, it suffices to show that for any fixed t ∈ T , , inf s∈T∞ |X(s) − X(t)| = 0 for ω ∈ Ω̃. Consider such an ω. Given any pre-assigned positive , there exists t? ∈ T? such that |X(t) − X(t? | < /2. For this t? , there exists a t∞ ∈ Tinf such that |X(t? ) − X(t∞ )| < /2, by virtue of the fact that ω ∈ Ωt? . It follows that |X(t) − X(t∞ )| < , which implies what we sought to show. 2 Addendum to proof of Theorem : We show that: Z sup |(X(s) − X(s0 (s)) − (X(t) − X(t0 (t))| s,t∈Tk+1 ≤ 4 K0 η ψ −1 (D(, d)) d . 0 ψ In what follows we abbreviate s0 (s) and t0 (t) to s0 and t0 respectively. Now, for any s, t ∈ Tk+1 , |(X(s) − X(s0 )) − (X(t) − X(t0 ))| = k X (X(sj+1 ) − X(sj )) − j=0 ≤ 2 k X (X(tj+1 ) − X(tj ))| j=0 k X max j=0 (u,v)∈Links(j+1,j) |X(u) − X(v)| ; note that the right side of the above display continues to remain an upper bound if we insert a supremum over all (s, t) ∈ Tk+1 before the left side. Hence, Ak ≡ sup |(X(s) − X(s0 (s)) − (X(t) − X(t0 (t))| s,t∈Tk+1 ≤2 ψ k X j=0 max (u,v)∈Links(j+1,j) |X(u) − X(v)| . Ψ Each term inside the sum on the right side, being the Orlicz norm of the maximum of finitely many random variables can be bounded using Lemma 1.1; for the j’th term in the sum there are at most D(η 2−(j+1) ) links involved and the Orlicz norm of each |X(u) − X(v)| is at most rη2−j . Conclude that for some constant K0 , Ak ≤ K0 k X ψ −1 (D(η 2−(j+1) , d)) η 2−j j=0 = 4K0 k X ψ −1 (D(η 2−(j+1) , d)) η 2−j+2 j=0 i η η η −1 ψ (D(η/2, d)) + ψ −1 (D(η/4, d)) + ψ −1 (D(η/8, d)) + . . . 4 8 16  1 −1 1 −1 1 ≤ 4K0 η ψ (D(η/2, d)) + ψ (D(η/4, d)) + ψ −1 (D(η/8, d)) + . . . 2 4 8 = 4K0 6 Z ≤ 4K0 η Z = 4K0 0 1 1 ψ −1 (D(ηu, d)) du ψ −1 (D(, d)) d , 0 and we are done. 2 An important corollary of the above theorem is Corollary 2.2.8. of VDVW (Corollary 8.5 of Kosorok) which constructs a bound on the expected modulus of continuity of a separable sub-Gaussian process X in terms of the logarithms of its packing numbers. The corollary says that: ! E |X(s) − X(t)| sup Z ≤K δ p log D(, d) d . 0 s,t∈T∞ ;d(s,t)≤δ Below, we provide an an argument. Since the process X is sub-Gaussian with respect to d, we can apply inequality (1.1) to conclude that kX(s) − X(t)}ψ2 . d(s, t) and we can apply the Theorem p 2 above with ψ(x) = ψ2 (x) = ex − 1. Also choose η = δ. Note that ψ2−1 (m) = log(1 + m). We thus obtain: Z |X(s) − X(t)| sup s,t∈T∞ ;d(s,t)≤δ . δ p log(1 + D(, d))d + δ p log(1 + D2 (δ, d)) . 0 ψ2 First consider the case that δ < diam(T ). In this case D(, d) ≥ 2 for all  ≤ δ. For m ≥ 2, we p √ √ have 1 + m ≤ m2 and hence log(1 + m) ≤ 2 log m. Using this fact, it is easy to see that at the expense of introducing a larger (universal) constant, we have: Z sup s,t∈T∞ ;d(s,t)≤δ |X(s) − X(t)| . ψ2 δ Z q p ( log D(, d)d + δ log D δ, d) . 0 δ p log D(, d)d , 0 since D(, d) is decreasing in . When δ = diam(T ), the first term in the display preceding the last can still be dominated, up to a universal constant, by the extreme right expression of the above display (when  = diam(T ), D(, d) = 1 but this is at a single point and does not cause a √ problem). The second term in the above display is simply log 2 diam(T ) which is no larger than RT p log D(, d)d, since for  < diam(T ), D(, d) ≥ 2. Finally, one uses the fact that the L2 norm 0 is less than a constant times the ψ2 norm; see, for example, Problem 4 on page 105 of VDVW. Also note that the above inequality can also be written in terms of an integral involving the entropy number (the log of the covering number) for a tweaked universal constant. If for some δ = δ0 , the integral on the right side of the above display converges, the DCT shows that the expected 7 modulus of continuity of X goes to 0 as δ goes to 0. The above inequality will play an important role in establishing a Donsker theorem later on where a sufficient condition for a class of functions to be Donsker will be developed in terms of the finiteness of an entropy integral. The technique will involve bounding the modulus of conitnuity of the empirical process Gn as n increases. By a symmetrization technique to be discussed shortly, the expected modulus of continuity can be dominated by an analogous quantity corresponding to a symmetrized version of the empirical process using independent Rademacher variables. This latter quantity can be controlled well using the above inequality as the symmetrized version of the empirical process is sub-Gaussian for the L2 (Pn ) semimetric. The next lemma provides a sufficient condition for the process {X(t) : t ∈ T } to induce a tight Borel probability measure on l∞ (T ) in terms of the packing numbers D(, d). Lemma 1.3 Consider the stochastic process X as defined in Theorem 1. Also, let ψ be as above Rη and let D(, d) be finite for all positive . Further, assume that 0 0 ψ −1 (D(, d)) d < ∞ for some η0 > 0. Then, the process X induces a tight Borel probability measure on l(T ). Proof: By the last (assumed) condition, it follows that Rη 0 ψ −1 (D(, d)) d → 0 as η → 0. By the first conclusion of Theorem 1 it then follows that as δ → 0, supd(s,t)≤δ |X(s) − X(t)| (why?) and therefore, by Exercise 8.5.5 of Kosorok, supd(s,t)≤δ |X(s) − X(t)| →?P ψ →0 0. By Exercise 17 on Page 106 of VDVW, conclude that almost all sample paths of X are uniformly continuous with respect to d. Sinc D(, d) is finite for all d, (T, d) is totally bounded (and diam T is finite). It is easy to see (using the total boundedness of T and the almost sure uniform continuity of the sample paths of X) that almost all sample paths of X(t) are bounded. Then, by Proposition 0 of the previous set of notes, the conclusion of the lemma follows directly. Solution to Exercise 8.5.5. of Kosorok (2008): Since ψ is an increasing convex non- zero function with ψ(0) = 0, there exists x0 > 0 such that φ(x0 ) > 0. Take any x > x0 . By convexity: ψ(x0 ) − ψ(0) ψ(x) − ψ(x0 ) ψ(x0 ) = ≤ , x0 x0 − 0 x − x0 which readily implies that ψ(x) x − x0 ψ(x0 ) ≥ × . x x x0 8 Taking liminfs on either side then readily yields the conclusion that lim inf x→∞ ψ(x)/x > 0. This proves the hint. Without loss of generality we take Xn ’s to be positive. Now, let cn denote the ψ-Orlicz norm of Xn . We have, for any M > 0, 1 ≥ E[ψ(Xn /cn )] = E(ψ(Xn /cn ) 1(Xn /cn ≤ M )) + E(ψ(Xn /cn ) 1(Xn /cn > M )) . Now, choose M so large that u > M implies that ψ(x)/x ≥ λ for some λ > 0. By the statement in the hint, this can be achieved. Conclude that: 1 ≥ E(λ (Xn /cn ) 1(Xn > cn M )) and therefore cn ≥ λ E(Xn 1(Xn > cn M )) , showing that the term on the right side goes to 0. Now E(Xn ) = E(Xn 1(Xn ≤ cn M )) + E(Xn 1(Xn > cn M )) ≤ cn M + E(Xn 1(Xn > cn M )) → 0 , which implies convergence in probability. 2 Partial solution to Problem 8.5.3 of Kosorok (2008) – going from ψ to φ: By 0 assumption there exist K, K 0 > 1 such that for all x, y ≥ K, ψ(x)ψ(y) ≤ K ψ(cxy). Note that if this holds for some pair (K, K 0 ) it will hold for any other pair that is component-wise larger than this pair. Thus, for all x, y ≥ 1, 0 ψ(Kx) ψ(Ky) ≤ K ψ(cK 2 xy) . Now, we seek σ, τ > 0 and σ ≤ 1 such that φ(x) = σ ψ(τ x) satisfies φ(1) ≤ 1/2 and φ(x)φ(y) ≤ φ(c̃xy) for all x, y ≥ 1, where c̃ > 0 depends solely on ψ. This last condition, after some simple algebra, translates to: ψ(τ x)ψ(τ y) ≤ 1 ψ(c̃τ xy) . σ We also need σ ψ(τ ) ≤ 1/2. So choose τ = K, σ strictly smaller than the minimum of 1/2 ψ(K) and 1/K 0 and c̃ = c K. These choices immediately ensure that the desired conditions on φ are met and note that c̃ still depends completely on the function ψ. 9