Sub-Gaussian Random Variables

Chapter 1 Sub-Gaussian Random Variables 1.1 GAUSSIAN TAILS AND MGF Recall that a random variable X ∈ IR has Gaussian distribution iff it has a density p with respect to the Lebesgue measure on IR given by ( (x − µ)2 ) 1 p(x) = √ exp − , 2σ 2 2πσ 2 x ∈ IR , where µ = IE(X) ∈ IR and σ 2 = var(X) > 0 are the mean and variance of X. We write X ∼ N (µ, σ 2 ). Note that X = σZ + µ for Z ∼ N (0, 1) (called standard Gaussian) and where the equality holds in distribution. Clearly, this distribution has unbounded support but it is well known that it has almost bounded support in the following sense: IP(|X − µ| ≤ 3σ) ≃ 0.997. This is due to the fast decay of the tails of p as |x| → ∞ (see Figure 1.1). This decay can be quantified using the following proposition (Mills inequality). Proposition 1.1. Let X be a Gaussian random variable with mean µ and variance σ 2 then for any t > 0, it holds t2 1 e− 2σ2 IP(X − µ > t) ≤ √ . 2π t By symmetry we also have t2 1 e− 2σ2 IP(X − µ < −t) ≤ √ . 2π t Figure 1.1. Probabilities of falling within 1, 2, and 3 standard deviations close to the mean in a Gaussian distribution. Source http://www.openintro.org/ and t2 IP(|X − µ| > t) ≤ 2 e− 2σ2 . π t Proof. Note that it is sufficient to prove the theorem for µ = 0 and σ 2 = 1 by simple translation and rescaling. We get for Z ∼ N (0, 1), 1 ∞ ( x2 ) 1 dx exp − IP(Z > t) = √ 2 2π t 1 ∞ ( x2 ) x 1 dx ≤ √ exp − 2 2π t t 1 ∞ ( x2 ) ∂ 1 dx = √ − exp − ∂x 2 t 2π t 1 = √ exp(−t2 /2) . t 2π The second inequality follows from symmetry and the last one using the union bound: IP(|Z| > t) = IP({Z > t} ∪ {Z < −t}) ≤ IP(Z > t) + IP(Z < −t) = 2IP(Z > t) . The fact that a Gaussian random variable Z has tails that decay to zero exponentially fast can also be seen in the moment generating function (MGF) M : s → M (s) = IE[exp(sZ)] . Indeed in the case of a standard Gaussian random variable, we have 1 z2 1 √ M (s) = IE[exp(sZ)] = esz e− 2 dz 2π 1 (z−s)2 s2 1 =√ e− 2 + 2 dz 2π =e s2 2 . ( It follows that if X ∼ N (µ, σ 2 ), then IE[exp(sX)] = exp sµ + σ2 s2 2 ) . 1.2 SUB-GAUSSIAN RANDOM VARIABLES AND CHERNOFF BOUNDS Definition and first properties Gaussian tails are practical when controlling the tail of an average of inde­ pendent random recall that if X1 , . . . , Xn are i.i.d N (µ, σ 2 ), �n variables. Indeed, 1 2 ¯ then X = n i=1 Xi ∼ N (µ, σ /n). Using Lemma 1.3 below for example, we get 2) ( ¯ − µ| > t) ≤ 2 exp − nt . IP(|X 2σ 2 Equating the right-hand side with some confidence level δ > 0, we find that with probability at least1 1 − δ, r r [ 2 log(2/δ) 2 log(2/δ) µ ∈ X̄ − σ , X̄ + σ , (1.1) n n This is almost the confidence interval that you used in introductory statistics. The only difference is that we used an approximation for the Gaussian tail whereas statistical tables or software use a much more accurate computation. Figure 1.2 shows the ration of the width of the confidence interval to that of the confidence interval computer by the software R. It turns out that intervals of the same form can be also derived for non-Gaussian random variables as long as they have sub-Gaussian tails. Definition 1.2. A random variable X ∈ IR is said to be sub-Gaussian with variance proxy σ2 if IE[X] = 0 and its moment generating function satisfies IE[exp(sX)] ≤ exp ( σ 2 s2 ) 2 , ∀ s ∈ IR . (1.2) In this case we write X ∼ subG(σ 2 ). Note that subG(σ 2 ) denotes a class of distributions rather than a distribution. Therefore, we abuse notation when writing X ∼ subG(σ 2 ). More generally, we can talk about sub-Gaussian random vectors and ma­ trices. A random vector X ∈ IRd is said to be sub-Gaussian with variance 1 We will often commit the statement “at least” for brevity Figure 1.2. Width of confidence intervals from exact computation in R (red dashed) and (1.1) (solid black). proxy σ 2 if IE[X] = 0 and u⊤ X is sub-Gaussian with variance proxy σ 2 for any unit vector u ∈ S d−1 . In this case we write X ∼ subGd (σ 2 ). A ran­ dom matrix X ∈ IRd×T is said to be sub-Gaussian with variance proxy σ 2 if IE[X] = 0 and u⊤ Xv is sub-Gaussian with variance proxy σ 2 for any unit vectors u ∈ S d−1 , v ∈ S T −1 . In this case we write X ∼ subGd×T (σ 2 ). This property can equivalently be expressed in terms of bounds on the tail of the random variable X. Lemma 1.3. Let X ∼ subG(σ 2 ). Then for any t > 0, it holds ( t2 ) IP[X > t] ≤ exp − 2 , 2σ and ( t2 ) IP[X < −t] ≤ exp − 2 . 2σ (1.3) Proof. Assume first that X ∼ subG(σ 2 ). We will employ a very useful technique called Chernoff bound that allows to to translate a bound on the moment generating function into a tail bound. Using Markov’s inequality, we have for any s > 0, ) IE esX ( . IP(X > t) ≤ IP esX > est ≤ est Next we use the fact that X is sub-Gaussian to get IP(X > t) ≤ e σ 2 s2 2 −st . The above inequality holds for any s > 0 so to make it the tightest possible, we 2 2 minimize with respect to s > 0. Solving φ′ (s) = 0, where φ(s) = σ 2s − st, we t2 find that inf s>0 φ(s) = − 2σ 2 . This proves the first part of (1.3). The second inequality in this equation follows in the same manner (recall that (1.2) holds for any s ∈ IR). Moments Recall that the absolute moments of Z ∼ N (0, σ 2 ) are given by (k + 1) 1 IE[|Z|k ] = √ (2σ 2 )k/2 Γ π 2 where Γ(·) denote the Gamma function defined by 1 ∞ Γ(t) = xt−1 e−x dx , t > 0 . 0 The next lemma shows that the tail bounds of Lemma 1.3 are sufficient to show that the absolute moments of X ∼ subG(σ 2 ) can be bounded by those of Z ∼ N (0, σ 2 ) up to multiplicative constants. Lemma 1.4. Let X be a random variable such that ( t2 ) IP[|X| > t] ≤ 2 exp − 2 , 2σ then for any positive integer k ≥ 1, IE[|X|k ] ≤ (2σ 2 )k/2 kΓ(k/2) . In particular, √ and IE[|X|] ≤ σ 2π . √ ( IE[|X|k ])1/k ≤ σe1/e k , k ≥ 2. Proof. IE[|X|k ] = 1 ∞ 0 = 1 ∞ 0 ≤2 1 IP(|X|k > t)dt IP(|X| > t1/k )dt ∞ t2/k e− 2σ2 dt 0 = (2σ 2 )k/2 k 1 ∞ e−u uk/2−1 du , 0 2 k/2 = (2σ ) kΓ(k/2) u= t2/k 2σ 2 The second statement follows from Γ(k/2) ≤ (k/2)k/2 and k 1/k ≤ e1/e for any k ≥ 2. It yields r √ )1/k ( 2 k/2 2σ 2 k 1/k ≤k (2σ ) kΓ(k/2) ≤ e1/e σ k . 2 √ √ Moreover, for k = 1, we have 2Γ(1/2) = 2π. Using moments, we can prove the following reciprocal to Lemma 1.3. Lemma 1.5. If (1.3) holds, then for any s > 0, it holds IE[exp(sX)] ≤ e4σ 2 2 s . As a result, we will sometimes write X ∼ subG(σ 2 ) when it satisfies (1.3). Proof. We use the Taylor expansion of the exponential function as follows. Observe that by the dominated convergence theorem ∞ �   sk IE[|X|k ] IE esX ≤ 1 + k! ≤1+ =1+ k=2 ∞ � k=2 ∞ � k=1 (2σ 2 s2 )k/2 kΓ(k/2) k! ∞ (2σ 2 s2 )k 2kΓ(k) � (2σ 2 s2 )k+1/2 (2k + 1)Γ(k + 1/2) + (2k)! (2k + 1)! k=1 ∞ )� (2σ 2 s2 )k k! ≤ 1 + 2 + 2σ 2 s2 (2k)! k=1 r ∞ ( σ 2 s2 ) � (2σ 2 s2 )k ≤1+ 1+ k! 2 k=1 r 2 2 σ 2 s2 2σ2 s2 = e2σ s + (e − 1) 2 2 2 ≤ e4σ s . ( √ 2(k!)2 ≤ (2k)! From the above Lemma, we see that sub-Gaussian random variables can be equivalently defined from their tail bounds and their moment generating functions, up to constants. Sums of independent sub-Gaussian random variables Recall that if X1 , . . . , Xn are i.i.d N (0, σ 2 ), then for any a ∈ IRn , n � i=1 ai Xi ∼ N (0, |a|22 σ 2 ). If we only care about the tails, this property is preserved for sub-Gaussian random variables. Theorem 1.6. Let X = (X1 , . . . , Xn ) be a vector of independent sub-Gaussian random variables that have variance proxy σ 2 . Then, the random vector X is sub-Gaussian with variance proxy σ 2 . Proof. Let u ∈ S n−1 be a unit vector, then ⊤ IE[esu X ]= n � i=1 IE[esui Xi ] ≤ n � e σ2 s2 u2 i 2 =e σ2 s2 |u|2 2 2 =e σ 2 s2 2 . i=1 Using a Chernoff bound, we immediately get the following corollary Corollary 1.7. Let X1 , . . . , Xn be n independent random variables such that Xi ∼ subG(σ 2 ). Then for any a ∈ IRn , we have IP n [� i=1 and IP n [� i=1 i ( ai Xi > t ≤ exp − t2 2σ 2 |a|22 i ( ai Xi < −t ≤ exp − ) t2 2σ 2 |a|22 , ) Of special interest Pnis the case where ai = 1/n for all i. Then, we get that � the average X̄ = n1 i=1 Xi , satisfies nt2 ¯ > t) ≤ e− 2σ2 IP(X nt2 ¯ < −t) ≤ e− 2σ2 and IP(X just like for the Gaussian average. Hoeffding’s inequality The class of subGaussian random variables is actually quite large. Indeed, Hoeffding’s lemma below implies that all randdom variables that are bounded uniformly are actually subGaussian with a variance proxy that depends on the size of their support. Lemma 1.8 (Hoeffding’s lemma (1963)). Let X be a random variable such that IE(X) = 0 and X ∈ [a, b] almost surely. Then, for any s ∈ IR, it holds IE[esX ] ≤ e 2 In particular, X ∼ subG( (b−a) ). 4 s2 (b−a)2 8 . Proof. Define ψ(s) = log IE[esX ], and observe that and we can readily compute � �2 IE[X 2 esX ] IE[XesX ] IE[XesX ] ′′ ψ ′ (s) = , (s) = − . ψ IE[esX ] IE[esX ] IE[esX ] Thus ψ ′′ (s) can be interpreted as the variance of the random variable X under esX the probability measure dQ = IE[e sX ] dIP. But since X ∈ [a, b] almost surely, we have, under any probability, [( ( a + b) a + b )2 i (b − a)2 ≤ . var(X) = var X − ≤ IE X − 2 2 4 The fundamental theorem of calculus yields 1 s1 µ s2 (b − a)2 ψ(s) = ψ ′′ (ρ) dρ dµ ≤ 8 0 0 using ψ(0) = log 1 = 0 and ψ ′ (0) = IEX = 0. Using a Chernoff bound, we get the following (extremely useful) result. Theorem 1.9 (Hoeffding’s inequality). Let X1 , . . . , Xn be n independent ran­ dom variables such that almost surely, Let X̄ = and 1 n P �n Xi ∈ [ai , bi ] , i=1 ∀ i. Xi , then for any t > 0, ( ) 2n2 t2 ¯ − IE(X) ¯ > t) ≤ exp − P �n IP(X , 2 i=1 (bi − ai ) ( ) 2 n 2 t2 ¯ − IE(X) ¯ < −t) ≤ exp − P �n IP(X . 2 i=1 (bi − ai ) Note that Hoeffding’s lemma is for any bounded random variables. For example, if one knows that X is a Rademacher random variable. Then IE(esX ) = es + e−s s2 = cosh(s) ≤ e 2 2 Note that 2 is the best possible constant in the above approximation. For such variables a = −1, b = 1, IE(X) = 0 so Hoeffding’s lemma yields IE(esX ) ≤ e s2 2 . Hoeffding’s inequality is very general but there is a price to pay for this gen­ erality. Indeed, if the random variables have small variance, we would like to see it reflected in the exponential tail bound (like for the Gaussian case) but the variance does not appear in Hoeffding’s inequality. We need a more refined inequality. 1.3 SUB-EXPONENTIAL RANDOM VARIABLES What can we say when a centered random variable is not sub-Gaussian? A typical example is the double exponential (or Laplace) distribution with parameter 1, denoted by Lap(1). Let X ∼ Lap(1) and observe that IP(|X| > t) = e−t , t ≥ 0. In particular, the tails of this distribution do not decay as fast as the Gaussian 2 ones (that decay as e−t /2 ). Such tails are said to be heavier than Gaussian. This tail behavior is also captured by the moment generating function of X. Indeed, we have   1 IE esX = if |s| < 1 , 1 − s2 and is not defined for s ≥ 1. It turns out that a rather week condition on the moment generating function is enough to partially reproduce some of the bounds that we have proved for sub-Gaussian random variables. Observe that for X ∼ Lap(1)   2 IE esX ≤ e2s if |s| < 1/2 , In particular, the Laplace distribution has its moment generating distribution that is bounded by that of a Gaussian in a neighborhood of 0 but does not even exist away from zero. It turns out that all distributions that have tails at least as heavy as that of a Laplace distribution satisfy such a property. Lemma 1.10. Let X be a centered random variable such that IP(|X| > t) ≤ 2e−2t/λ for some λ > 0. Then, for any positive integer k ≥ 1, IE[|X|k ] ≤ λk k! . Moreover, ( IE[|X|k ])1/k ≤ 2λk , and the moment generating function of X satisfies   2 2 IE esX ≤ e2s λ , Proof. IE[|X|k ] = = 1 ∞ 10 ∞ 0 ≤ 1 ∞ 1 . 2λ IP(|X|k > t)dt IP(|X| > t1/k )dt 2e− 2t1/k λ 0 = 2(λ/2)k k 1 dt ∞ e−u uk−1 du , 0 k ∀|s| ≤ ≤ λ kΓ(k) = λk k! u= 2t1/k λ The second statement follows from Γ(k) ≤ k k and k 1/k ≤ e1/e ≤ 2 for any k ≥ 1. It yields ( k )1/k λ kΓ(k) ≤ 2λk . To control the MGF of X, we use the Taylor expansion of the exponential function as follows. Observe that by the dominated convergence theorem, for any s such that |s| ≤ 1/2λ ∞ � X   |s|k IE[|X|k ] IE esX ≤ 1 + k! k=2 ≤1+ ∞ X � (|s|λ)k k=2 = 1 + s2 λ2 ∞ X � (|s|λ)k k=0 ≤ 1 + 2s2 λ2 2 ≤ e2s |s| ≤ 1 2λ λ2 This leads to the following definition Definition 1.11. A random variable X is said to be sub-exponential with parameter λ (denoted X ∼ subE(λ)) if IE[X] = 0 and its moment generating function satisfies   2 2 1 IE esX ≤ es λ /2 , ∀|s| ≤ . λ A simple and useful example of of a sub-exponential random variable is given in the next lemma. Lemma 1.12. Let X ∼ subG(σ 2 ) then the random variable Z = X 2 − IE[X 2] is sub-exponential: Z ∼ subE(16σ 2 ). Proof. We have, by the dominated convergence theorem, IE[e sZ  k ∞ � X sk IE X 2 − IE[X 2 ] ]=1+ k! k=2 ( ) ∞ X � sk 2k−1 IE[X 2k ] + (IE[X 2 ])k ≤1+ k! ≤1+ ≤1+ k=2 ∞ X � k=2 ∞ X � k=2 sk 4k IE[X 2k ] 2(k!) (Jensen) (Jensen again) sk 4k 2(2σ 2 )k k! 2(k!) = 1 + (8sσ 2 )2 ∞ X � (Lemma 1.4) (8sσ 2 )k k=0 = 1 + 128s2 σ 4 2 ≤ e128s σ4 for |s| ≤ 1 16σ 2 . Sub-exponential random variables also give rise to exponential deviation inequalities such as Corollary 1.7 (Chernoff bound) or Theorem 1.9 (Hoeffd­ ing’s inequality) for weighted sums of independent sub-exponential random variables. The significant difference here is that the larger deviations are con­ trolled in by a weaker bound. Berstein’s inequality Theorem 1.13 (Bernstein’s inequality). Let X1 , . . . , Xn be independent ran­ dom variables such that IE(Xi ) = 0 and Xi ∼ subE(λ). Define n X̄ = � 1X Xi , n i=1 Then for any t > 0 we have �  �  2 ¯ > t) ∨ IP(X ¯ < −t) ≤ exp − n ( t ∧ t ) . IP(X 2 λ2 λ Proof. Without loss of generality, assume that λ = 1 (we can always replace Xi by Xi /λ and t by t/λ. Next, using a Chernoff bound, we get for any s > 0 ¯ > t) ≤ IP(X n Y � i=1   IE esXi e−snt .   2 Next, if |s| ≤ 1, then IE esXi ≤ es /2 by definition of sub-exponential distri­ butions. It yields 2 ¯ > t) ≤ e ns2 −snt IP(X Choosing s = 1 ∧ t yields n 2 ¯ > t) ≤ e− 2 (t IP(X ∧t) ¯ < −t) which concludes the proof. We obtain the same bound for IP(X Note that usually, Bernstein’s inequality refers to a slightly more precise result that is qualitatively the same as the one above: it exhibits a Gaussian 2 2 tail e−nt /(2λ ) and an exponential tail e−nt/(2λ) . See for example Theorem 2.10 in [BLM13]. 1.4 MAXIMAL INEQUALITIES The exponential inequalities of the previous section are valid for linear com­ binations of independent random variables, and in particular, for the average X̄. In many instances, we will be interested in controlling the maximum over the parameters of such linear combinations (this is because of empirical risk minimization). The purpose of this section is to present such results. Maximum over a finite set We begin by the simplest case possible: the maximum over a finite set. Theorem 1.14. Let X1 , . . . , XN be N random variables such that Xi ∼ subG(σ 2 ). Then � � IE[ max Xi ] ≤ σ 2 log(N ) , and IE[ max |Xi |] ≤ σ 2 log(2N ) 1≤i≤N 1≤i≤N Moreover, for any t > 0, IP ( ) t2 max Xi > t ≤ N e− 2σ2 , 1≤i≤N and IP ( ) t2 max |Xi | > t ≤ 2N e− 2σ2 1≤i≤N Note that the random variables in this theorem need not be independent. Proof. For any s > 0,  1  IE log es max1≤i≤N Xi s   1 ≤ log IE es max1≤i≤N Xi s   1 = log IE max esXi 1≤i≤N s X �   1 IE esXi ≤ log s IE[ max Xi ] = 1≤i≤N (by Jensen) 1≤i≤N X σ 2 s2 � 1 ≤ log e 2 s 1≤i≤N log N σ2 s = + s 2 � Taking s = 2(log N )/σ 2 yields the first inequality in expectation. The first inequality in probability is obtained by a simple union bound: ( ) ( ) IP max Xi > t = IP {Xi > t} 1≤i≤N 1≤i≤N ≤ � X IP(Xi > t) 1≤i≤N t2 ≤ N e− 2σ2 , where we used Lemma 1.3 in the last inequality. The remaining two inequalities follow trivially by noting that max |Xi | = max Xi , 1≤i≤N 1≤i≤2N where XN +i = −Xi for i = 1, . . . , N . Extending these results to a maximum over an infinite set may be impossi­ ble. For example, if one is given an infinite sequence of i.i.d N (0, σ 2 ) random variables X1 , X2 , . . . ,, then for any N ≥ 1, we have for any t > 0, IP( max Xi < t) = [IP(X1 < t)]N → 0 , 1≤i≤N N → ∞. On the opposite side of the picture, if all the Xi s are equal to the same random variable X, we have for any t > 0, IP( max Xi < t) = IP(X1 < t) > 0 1≤i≤N ∀N ≥ 1. In the Gaussian case, lower bounds are also available. They illustrate the effect of the correlation between the Xi s Examples from statistics have structure and we encounter many examples where a maximum of random variables over an infinite set is in fact finite. This is due to the fact that the random variable that we are considering are not independent from each other. In the rest of this section, we review some of these examples. Maximum over a convex polytope We use the definition of a polytope from [Gru03]: a convex polytope P is a compact set with a finite number of vertices V(P) called extreme points. It satisfies P = conv(V(P)), where conv(V(P)) denotes the convex hull of the vertices of P. Let X ∈ IRd be a random vector and consider the (infinite) family of random variables F = {θ⊤ X : θ ∈ P} , where P ⊂ IRd is a polytope with N vertices. While the family F is infinite, the maximum over F can be reduced to the a finite maximum using the following useful lemma. Lemma 1.15. Consider a linear form x → c⊤ x, x, c ∈ IRd . Then for any convex polytope P ⊂ IRd , max c⊤ x = max c⊤ x x∈P x∈V(P) where V(P) denotes the set of vertices of P. Proof. Assume that V(P) = {v1 , . . . , vN }. For any x ∈ P = conv(V(P)), there exist nonnegative numbers λ1 , . . . λN that sum up to 1 and such that x = λ1 v1 + · · · + λN vN . Thus c⊤ x = c⊤ N (X � i=1 It yields N N ) � � X X λi max c⊤ x = max c⊤ x . λi c⊤ vi ≤ λi vi = i=1 x∈V(P) i=1 x∈V(P) max c⊤ x ≤ max c⊤ x ≤ max c⊤ x x∈P x∈P x∈V(P) so the two quantities are equal. It immediately yields the following theorem Theorem 1.16. Let P be a polytope with N vertices v (1) , . . . , v (N ) ∈ IRd and let X ∈ IRd be a random vector such that, [v (i) ]⊤ X, i = 1, . . . , N are sub-Gaussian random variables with variance proxy σ 2 . Then � � and IE[max |θ⊤ X|] ≤ σ 2 log(2N ) . IE[max θ⊤ X] ≤ σ 2 log(N ) , θ∈P Moreover, for any t > 0, ( ) t2 IP max θ⊤ X > t ≤ N e− 2σ2 , θ∈P θ∈P and ( ) t2 IP max |θ⊤ X| > t ≤ 2N e− 2σ2 θ∈P Of particular interests are polytopes that have a small number of vertices. A primary example is the ℓ1 ball of IRd defined for any radius R > 0, by d { � X B1 = x ∈ IRd : |xi | ≤ 1} . i=1 Indeed, it has exactly 2d vertices. Maximum over the ℓ2 ball Recall that the unit ℓ2 ball of IRd is defined by the set of vectors u that have Euclidean norm |u|2 at most 1. Formally, it is defined by d { } � X B2 = x ∈ IRd : x2i ≤ 1 . i=1 Clearly, this ball is not a polytope and yet, we can control the maximum of random variables indexed by B2 . This is due to the fact that there exists a finite subset of B2 such that the maximum over this finite set is of the same order as the maximum over the entire ball. Definition 1.17. Fix K ⊂ IRd and ε > 0. A set N is called an ε-net of K with respect to a distance d(·, ·) on IRd , if N ⊂ K and for any z ∈ K, there exists x ∈ N such that d(x, z) ≤ ε. Therefore, if N is an ε-net of K with respect to norm 1 · 1, then every point of K is at distance at most ε from a point in N . Clearly, every compact set admits a finite ε-net. The following lemma gives an upper bound on the size of the smallest ε-net of B2 . Lemma 1.18. Fix ε ∈ (0, 1). Then the unit Euclidean ball B2 has an ε-net N with respect to the Euclidean distance of cardinality |N | ≤ (3/ε)d Proof. Consider the following iterative construction if the ε-net. Choose x1 = 0. For any i ≥ 2, take any xi to be any x ∈ B2 such that |x − xj |2 > ε for all j < i. If no such x exists, stop the procedure. Clearly, this will create an ε-net. We now control its size. Observe that since |x− y|2 > ε for all x, y ∈ N , the Euclidean balls centered at x ∈ N and with radius ε/2 are disjoint. Moreover, z∈N ε ε {z + B2 } ⊂ (1 + )B2 2 2 where {z + εB2 } = {z + εx , x ∈ B2 }. Thus, measuring volumes, we get ( ) X � ( ) ( ) ε ε ε vol (1 + )B2 ≥ vol vol {z + B2 } {z + B2 } = 2 2 2 z∈N z∈N This is equivalent to ε ε (1 + )d ≥ |N |( )d . 2 2 Therefore, we get the following bound ( 2 )d ( 3 )d ≤ . |N | ≤ 1 + ε ε Theorem 1.19. Let X ∈ IRd be a sub-Gaussian random vector with variance proxy σ 2 . Then √ IE[max θ⊤ X] = IE[max |θ⊤ X|] ≤ 4σ d . θ∈B2 θ∈B2 Moreover, for any δ > 0, with probability 1 − δ, it holds � √ max θ⊤ X = max |θ⊤ X| ≤ 4σ d + 2σ 2 log(1/δ) . θ∈B2 θ∈B2 Proof. Let N be a 1/2-net of B2 with respect to the Euclidean norm that satisfies |N | ≤ 6d . Next, observe that for every θ ∈ B2 , there exists z ∈ N and x such that |x|2 ≤ 1/2 and θ = z + x. Therefore, max θ⊤ X ≤ max z ⊤ X + max x⊤ X 1 z∈N θ∈B2 But max x⊤ X = 1 x∈ 2 B2 x∈ 2 B2 1 max x⊤ X 2 x∈B2 Therefore, using Theorem 1.14, we get √ � � IE[max θ⊤ X] ≤ 2IE[max z ⊤ X] ≤ 2σ 2 log(|N |) ≤ 2σ 2(log 6)d ≤ 4σ d . z∈N θ∈B2 The bound with high probability, follows because ( ) ( ) t2 t2 IP max θ⊤ X > t ≤ IP 2 max z ⊤ X > t ≤ |N |e− 8σ2 ≤ 6d e− 8σ2 . θ∈B2 z∈N To conclude the proof, we find t such that t2 e− 8σ2 +d log(6) ≤ δ ⇔ t2 ≥ 8 log(6)σ 2 d + 8σ 2 log(1/δ) . � � √ Therefore, it is sufficient to take t = 8 log(6)σ d + 2σ 2 log(1/δ) .