Concentration Inequalities, Scalar and Matrix Versions

4 Concentration Inequalities, Scalar and Matrix Versions 4.1 Large Deviation Inequalities Concentration and large deviations inequalities are among the most useful tools when understanding the performance of some algorithms. In a nutshell they control the probability of a random variable being very far from its expectation. The simplest such inequality is Markov’s inequality: Theorem 4.1 (Markov’s Inequality) Let X ≥ 0 be a non-negative random variable with E[X] < ∞. Then, E[X] Prob{X > t} ≤ . (31) t Proof. Let t > 0. Define a random variable Yt as  0 if X ≤ t Yt = t if X > t Clearly, Yt ≤ X, hence E[Yt ] ≤ E[X], and t Prob{X > t} = E[Yt ] ≤ E[X], 2 concluding the proof. Markov’s inequality can be used to obtain many more concentration inequalities. Chebyshev’s inequality is a simple inequality that control fluctuations from the mean. Theorem 4.2 (Chebyshev’s inequality) Let X be a random variable with E[X 2 ] < ∞. Then, Prob{|X − EX| > t} ≤ Var(X) . t2 Proof. Apply Markov’s inequality to the random variable (X − E[X])2 to get:   E (X − EX)2 Var(X) 2 2 = . Prob{|X − EX | > t} = Prob{(X − EX) > t } ≤ t2 t2 4.1.1 2 Sums of independent random variables In what follows we’ll show two useful inequalities involving sums of independent random variables. The intuitive idea is that if we have a sum of independent random variables X = X1 + · · · + Xn , where Xi are iid centered random variables, then while the value of X can be of order O(n) it will very √ likely be of order O( n) (note that this is the order of its standard deviation). The inequalities that √ follow are ways of very precisely controlling the probability of X being larger than O( n). While we could use, for example, Chebyshev’s inequality for this, in the inequalities that follow the probabilities will be exponentially small, rather than quadratic, which will be crucial in many applications to come. Theorem 4.3 (Hoeffding’s Inequality) Let X1 , X2 , . . . , Xn be independent bounded random variables, i.e., |Xi | ≤ a and E[Xi ] = 0. Then, ( n )   X t2 . Prob Xi > t ≤ 2 exp − 2na2 i=1 √ The inequality implies that fluctuations larger than O ( n) have small probability. For example, √ 2 for t = a 2n log n we get that the probability is at most P n. Proof. We first get a probability bound for the event ni=1 Xi > t. The proof, again, will follow from Markov. Since we want an exponentially small probability, we use a classical trick that involves exponentiating with any λ > 0 and then choosing the optimal λ. ( n ) ( n ) X X Prob Xi > t = Prob Xi > t (32) i=1 i=1 n Pn o = Prob eλ i=1 Xi > eλt E[eλ ≤ = e−tλ Pn i=1 etλ n Y Xi ] E[eλXi ], (33) i=1 where the penultimate step follows from Markov’s inequality and the last equality follows from independence of the Xi ’s. We now use the fact that |Xi | ≤ a to bound E[eλXi ]. Because the function f (x) = eλx is convex, eλx ≤ a + x λa a − x −λa e + e , 2a 2a for all x ∈ [−a, a]. Since, for all i, E[Xi ] = 0 we get    a + Xi λa a − Xi −λa 1  λa λXi e + e ≤ e + e−λa = cosh(λa) E[e ] ≤ E 2a 2a 2 Note that15 cosh(x) ≤ ex 2 /2 Hence, for all x ∈ R , 2 /2 E[eλXi ] ≤ E[e(λXi ) 2 /2 ] ≤ e(λa) . Together with (32), this gives Prob ( n X i=1 ) Xi > t ≤ e−tλ 2 /2 e(λa) i=1 −tλ n(λa)2 /2 = e 15 n Y This follows immediately from the Taylor expansions: cosh(x) = e x2n n=0 (2n)! , P∞ 2 ex /2 = x2n n=0 2n n! , P∞ and (2n)! ≥ 2n n!. This inequality holds for any choice of λ ≥ 0, so we choose the value of λ that minimizes   (λa)2 min n − tλ λ 2 Differentiating readily shows that the minimizer is given by λ= t , na2 which satisfies λ > 0. For this choice of λ, 1 n(λa) /2 − tλ = n 2  t2 t2 − 2 2 2a a  =− t2 2na2 Thus, Prob ( n X ) Xi > t t2 ≤ e− 2na2 i=1 By using the same argument on Pn i=1 (−Xi ), ( Prob n X and union bounding over the two events we get, ) Xi > t t2 ≤ 2e− 2na2 i=1 2 Remark 4.4 Let’s say that we have random   −1 0 ri =  1 variables r1 , . . . , rn i.i.d. distributed as with probability p/2 with probability 1 − p with probability p/2. Then, E(ri ) = 0 and |ri | ≤ 1 so Hoeffding’s inequality gives: ( n )  2 X t Prob ri > t ≤ 2 exp − . 2n i=1 P Intuitively, the smallest p is the more concentrated | ni=1 ri | should be, however Hoeffding’s inequality does not capture this behavior. P A natural way to quantify this intuition is by noting that the variance of ni=1 ri depends on p as Var(ri ) = p. The inequality that follows, Bernstein’s inequality, uses the variance of the summands to improve over Hoeffding’s inequality. The way this is going to be achieved is by strengthening the proof above, more specifically in step (33) we will use the bound on the variance to get a better estimate on E[eλXi ] essentially  2  by 2 2 k 2 k−2 = σa2 ak . realizing that if Xi is centered, EXi = σ , and |Xi | ≤ a then, for k ≥ 2, EXi ≤ σ a Theorem 4.5 (Bernstein’s Inequality) Let X1 , X2 , . . . , Xn be independent centered bounded random variables, i.e., |Xi | ≤ a and E[Xi ] = 0, with variance E[Xi2 ] = σ 2 . Then, ! ( n ) X t2 . Prob Xi > t ≤ 2 exp − 2nσ 2 + 32 at i=1 Remark 4.6 Before proving Bernstein’s Inequality, note that on the example of Remark 4.4 we get ! ( n ) X t2 Prob , ri > t ≤ 2 exp − 2np + 32 t i=1 which exhibits a dependence on p and, for small values of p is considerably smaller than what Hoeffding’s inequality gives. Proof. As before, we will prove ( n X ) ! t2 Prob Xi > t ≤ exp − , 2nσ 2 + 23 at i=1 P and then union bound with the same result for − ni=1 Xi , to prove the Theorem. For any λ > 0 we have ) ( n P X Xi > t = Prob{eλ Xi > eλt } Prob i=1 P E[eλ Xi ] ≤ eλt n Y = e−λt E[eλXi ] i=1 Now comes the source of the improvement over Hoeffding’s, " # ∞ X λm Xim λXi E[e ] = E 1 + λXi + m! m=2 ∞ X λm am−2 σ 2 ≤ 1+ m! = 1+ m=2 ∞ σ2 X a2 m=2 (λa)m m!  σ2  = 1 + 2 eλa − 1 − λa a Therefore, Prob ( n X i=1 ) Xi > t ≤e −λt   n σ 2  λa 1 + 2 e − 1 − λa a ex , We will use a few simple inequalities (that can be easily proved with calculus) such as16 1 + x ≤ for all x ∈ R. This means that,  σ 2 λa σ2  1 + 2 eλa − 1 − λa ≤ e a2 (e −1−λa) , a which readily implies ( n ) X nσ 2 λa Prob Xi > t ≤ e−λt e a2 (e −1−λa) . i=1 As before, we try to find the value of λ > 0 that minimizes   nσ 2 λa min −λt + 2 (e − 1 − λa) λ a Differentiation gives nσ 2 (aeλa − a) = 0 a2 which implies that the optimal choice of λ is given by   1 at ∗ λ = log 1 + a nσ 2 −t + If we set u= at , nσ 2 (34) then λ∗ = a1 log(1 + u). Now, the value of the minimum is given by −λ∗ t + nσ 2 λ∗ a nσ 2 ∗ (e − 1 − λ a) = − [(1 + u) log(1 + u) − u] . a2 a2 Which means that, Prob ( n X ) Xi > t i=1   nσ 2 ≤ exp − 2 {(1 + u) log(1 + u) − u} a The rest of the proof follows by noting that, for every u > 0, u (1 + u) log(1 + u) − u ≥ 2 2 , u + 3 (35) which implies: Prob ( n X i=1 ) Xi > t nσ 2 ≤ exp − 2 a 2 u u + ! 2 3 t2 = exp − 2nσ 2 + 23 at ! . 2 16 In fact y = 1 + x is a tangent line to the graph of f (x) = ex . 4.2 Gaussian Concentration One of the most important results in concentration of measure is Gaussian concentration, although being a concentration result specific for normally distributed random variables, it will be very useful throughout these lectures. Intuitively it says that if F : Rn → R is a function that is stable in terms of its input then F (g) is very well concentrated around its mean, where g ∈ N (0, I). More precisely: Theorem 4.7 (Gaussian Concentration) Let X = [X1 , . . . , Xn ]T be a vector with i.i.d. standard Gaussian entries and F : Rn → R a σ-Lipschitz function (i.e.: |F (x) − F (y)| ≤ σkx − yk, for all x, y ∈ Rn ). Then, for every t ≥ 0   t2 Prob {|F (X) − EF (X)| ≥ t} ≤ 2 exp − 2 . 2σ For the sake of simplicity we will show the proof for a slightly  weaker  bound (in terms of the constant 2 t2 inside the exponent): Prob {|F (X) − EF (X)| ≥ t} ≤ 2 exp − π2 σ2 . This exposition follows closely the proof of Theorem 2.1.12 in [Tao12] and the original argument is due to Maurey and Pisier. For a proof with the optimal constants see, for example, Theorem 3.25 in these notes [vH14]. We will also assume the function F is smooth — this is actually not a restriction, as a limiting argument can generalize the result from smooth functions to general Lipschitz functions. Proof. If F is smooth, then it is easy to see that the Lipschitz property implies that, for every x ∈ Rn , k∇F (x)k2 ≤ σ. By subtracting a constant to F , we can assume that EF (X) = 0. Also, it is enough to show a one-sided bound   2 t2 Prob {F (X) − EF (X) ≥ t} ≤ exp − 2 2 , π σ since obtaining the same bound for −F (X) and taking a union bound would gives the result. We start by using the same idea as in the proof of the large deviation inequalities above; for any λ > 0, Markov’s inequality implies that Prob {F (X) ≥ t} = Prob {exp (λF (X)) ≥ exp (λt)} E [exp (λF (X))] ≤ exp (λt) This means we need to upper bound E [exp (λF (X))] using a bound on k∇F k. The idea is to introduce a random independent copy Y of X. Since exp (λ·) is convex, Jensen’s inequality implies that E [exp (−λF (Y ))] ≥ exp (−EλF (Y )) = exp(0) = 1. Hence, since X and Y are independent, E [exp (λ [F (X) − F (Y )])] = E [exp (λF (X))] E [exp (−λF (Y ))] ≥ E [exp (λF (X))] Now we use the Fundamental Theorem of Calculus in a circular arc from X to Y : Z π 2 ∂ F (X) − F (Y ) = F (Y cos θ + X sin θ) dθ. 0 ∂θ The advantage of using the circular arc is that, for any θ, Xθ := Y cos θ + X sin θ is another random variable with the same distribution. Also, its derivative with respect to θ, Xθ0 = −Y sin θ + X cos θ also is. Moreover, Xθ and Xθ0 are independent. In fact, note that h i T E Xθ Xθ0 = E [Y cos θ + X sin θ] [−Y sin θ + X cos θ]T = 0. We use Jensen’s again (with respect to the integral now) to get: ! Z π/2 ∂ π 1 exp (λ [F (X) − F (Y )]) = exp λ F (Xθ ) dθ 2 π/2 0 ∂θ   Z π/2 1 π ∂ ≤ exp λ F (Xθ ) dθ π/2 0 2 ∂θ Using the chain rule, 2 exp (λ [F (X) − F (Y )]) ≤ π Z π/2  π  exp λ ∇F (Xθ ) · Xθ0 dθ, 2 π/2   π E exp λ ∇F (Xθ ) · Xθ0 dθ, 2 0 and taking expectations E exp (λ [F (X) − F (Y )]) ≤ 2 π Z 0 If we condition on Xθ , since λ π2 ∇F (Xθ ) ≤ λ π2 σ, λ π2 ∇F (Xθ ) · Xθ0 is a gaussian random variable
2 with variance at most λ π2 σ . This directly implies that, for every value of Xθ      π 1 π 2 0 EXθ0 exp λ ∇F (Xθ ) · Xθ ≤ exp λ σ 2 2 2 Taking expectation now in Xθ , and putting everything together, gives    1 π 2 E [exp (λF (X))] ≤ exp λ σ , 2 2 which means that    π 2 1 Prob {F (X) ≥ t} ≤ exp λ σ − λt , 2 2
2 Optimizing for λ gives λ∗ = π2 σt2 , which gives  2 t2 Prob {F (X) ≥ t} ≤ exp − 2 2 . π σ  2 4.2.1 Spectral norm of a Wigner Matrix We give an illustrative example of the utility of Gaussian concentration. Let W ∈ Rn×n be a standard Gaussian Wigner matrix, a symmetric matrix with (otherwise) independent gaussian entries, the offdiagonal entries have unit variance and the diagonal entries have variance 2. kW k depends on n(n+1) 2 √ independent (standard) gaussian random variables and it is easy to see that it is a 2-Lipschitz function of these variables, since kW (1) k − kW (2) k ≤ W (1) − W (2) ≤ W (1) − W (2) F . The symmetry of the matrix and the variance 2 of the diagonal entries are responsible for an extra √ factor of 2. Using Gaussian Concentration (Theorem 4.7) we immediately get  2 t Prob {kW k ≥ EkW k + t} ≤ exp − . 4 √ Since17 EkW k ≤ 2 n we get Proposition 4.8 Let W ∈ Rn×n be a standard Gaussian Wigner matrix, a symmetric matrix with (otherwise) independent gaussian entries, the off-diagonal entries have unit variance and the diagonal entries have variance 2. Then,  2  √ t Prob kW k ≥ 2 n + t ≤ exp − . 4 √ Note that this gives an extremely precise control of the fluctuations of kW k. In fact, for t = 2 log n this gives   n o p √ 4 log n 1 Prob kW k ≥ 2 n + 2 log n ≤ exp − = . 4 n 4.2.2 Talagrand’s concentration inequality A remarkable result by Talagrand [Tal95], Talangrad’s concentration inequality, provides an analogue of Gaussian concentration to bounded random variables. Theorem 4.9 (Talangrand concentration inequality, Theorem 2.1.13 [Tao12]) Let K > 0, and let X1 , . . . , Xn be independent bounded random variables, |Xi | ≤ K for all 1 ≤ i ≤ n. Let F : Rn → R be a σ-Lipschitz and convex function. Then, for any t ≥ 0,   t2 Prob {|F (X) − E [F (X)]| ≥ tK} ≤ c1 exp −c2 2 , σ for positive constants c1 , and c2 . Other useful similar inequalities (with explicit constants) are available in [Mas00]. 17 √ It is an excellent exercise to prove EkW k ≤ 2 n using Slepian’s inequality. 4.3 Other useful large deviation inequalities This Section contains, without proof, some scalar large deviation inequalities that I have found useful. 4.3.1 Additive Chernoff Bound The additive Chernoff bound, also known as Chernoff-Hoeffding theorem concerns Bernoulli random variables. Theorem 4.10 Given 0 < p < 1 and X1 , . . . , Xn i.i.d. random variables distributed as Bernoulli(p) random variable (meaning that it is 1 with probability p and 0 with probability 1 − p), then, for any ε > 0: ( n ) " p+ε  1−p−ε #n 1−p 1X p • Prob Xi ≥ p + ε ≤ n p+ε 1−p−ε i=1 ( • Prob n 1X Xi ≤ p − ε n i=1 4.3.2 ) " ≤ p p−ε p−ε  1−p 1−p+ε 1−p+ε #n Multiplicative Chernoff Bound There is also a multiplicative version (see, for example Lemma 2.3.3. in [Dur06]), which is particularly useful. Theorem 4.11 Let X1 , . . . , Xn be independent random variables taking values P is {0, 1} (meaning they are Bernoulli distributed but not necessarily identically distributed). Let µ = E ni=1 Xi , then, for any δ > 0: µ  eδ • Prob {X > (1 + δ )µ} < (1 + δ)(1+δ) µ  e−δ • Prob {X < (1 − δ)µ} < (1 − δ)(1−δ) 4.3.3 Deviation bounds on χ2 variables A particularly useful deviation inequality is Lemma 1 in Laurent and Massart [LM00]: Theorem 4.12 (Lemma 1 in Laurent and Massart [LM00]) Let X1 , . . . , Xn be i.i.d. standard gaussian random variables (N (0, 1)), and a1 , . . . , an non-negative numbers. Let Z= n X
ak Xk2 − 1 . k=1 The following inequalities hold for any t > 0: √ • Prob {Z ≥ 2kak2 x + 2kak∞ x} ≤ exp(−x), √ • Prob {Z ≤ −2kak2 x} ≤ exp(−x), P where kak22 = nk=1 a2k and kak∞ = max1≤k≤n |ak |. Note that if ak = 1, for all k, then Z is a χ2 with n degrees of freedom, so this theorem immediately gives a deviation inequality for χ2 random variables. 4.4 Matrix Concentration In many important applications, some of which we will see in the proceeding lectures, one needs to use a matrix version of the inequalities above. Given {Xk }nk=1 independent random symmetric d × d matrices one is interested in deviation inequalities for ! n X Xk . λmax k=1 For example, a very useful adaptation of Bernstein’s inequality exists for this setting. Theorem 4.13 (Theorem 1.4 in [Tro12]) Let {Xk }nk=1 be a sequence of independent random symmetric d × d matrices. Assume that each Xk satisfies: EXk = 0 and λmax (Xk ) ≤ R almost surely. Then, for all t ≥ 0, ( Prob λmax n X ! Xk ) ≥t ≤ d · exp k=1 −t2 2σ 2 + 23 Rt ! 2 where σ = n X E Xk2
. k=1 Note that kAk denotes the spectral norm of A. In what follows we will state and prove various matrix concentration results, somewhat similar to Theorem 4.13. Motivated by the derivation of Proposition 4.8, that allowed us to easily transform bounds on the expected spectral norm of a random matrix into tail bounds, we will mostly focus on bounding the expected spectral norm. Tropp’s monograph [Tro15b] is a nice introduction to matrix concentration and includes a proof of Theorem 4.13 as well as many other useful inequalities. A particularly important inequality of this type is for gaussian series, it is intimately related to the non-commutative Khintchine inequality [Pis03], and for that reason we will often refer to it as Non-commutative Khintchine (see, for example, (4.9) in [Tro12]). Theorem 4.14 (Non-commutative Khintchine (NCK)) Let A1 , . . . , An ∈ Rd×d be symmetric matrices and g1 , . . . , gn ∼ N (0, 1) i.i.d., then: E n X  1 2 gk Ak ≤ 2 + 2 log(2d) σ, k=1 where 2 σ = n X k=1 2 A2k . (36) k that, akin to Proposition 4.8, we can also use Gaussian Concentration to get a tail bound on PNote n g k=1 k Ak k. We consider the function n X F : Rn → gk Ak . k=1 We now estimate its Lipschitz constant; let g, h ∈ Rn then n X g k Ak − k=1 n X hk Ak n X ≤ k=1 ! − gk Ak k=1 n X n X ! hk Ak k=1 (gk − hk )Ak = k=1 = = ≤ max v n X T v: kvk=1 v: kvk=1 (gk − hk )Ak v k=1 n X max ! (gk − hk ) v T Ak v
k=1 v v u n u n X u uX 2 t (gk − hk ) t (v T Ak v)2 max v: kvk=1 k=1 k=1 v u n X u t max (v T Ak v)2 kg − hk2 , = v: kv k=1 k=1 where the first inequality made use of the triangular inequality and the last one of the Cauchy-Schwarz inequality. This motivates us to define a new parameter, the weak variance σ∗ . Definition 4.15 (Weak Variance (see, for example, [Tro15b])) Given A1 , . . . , An ∈ Rd×d symmetric matrices. We define the weak variance parameter as σ∗2 = max v: kvk=1 n X v T Ak v
2 . k=1 This means that, using Gaussian concentration (and setting t = uσ∗ ), we have ( n )   1  X 1 2 2 Prob gk Ak ≥ 2 + 2 log(2d) σ + uσ∗ ≤ exp − u . 2 (37) k=1 P This means that although the expected value of k nk=1 gk Ak k is controlled by the parameter σ, its fluctuations seem to be controlled by σ∗ . We compare the two quantities in the following Proposition. Proposition 4.16 Given A1 , . . . , An ∈ Rd×d symmetric matrices, recall that v v u n u 2 n u X X u t 2 t σ= max (v T Ak v)2 . Ak and σ∗ = v: kvk=1 k=1 k=1 We have σ∗ ≤ σ. Proof. Using the Cauchy-Schwarz inequality, σ∗2 = = ≤ = = n X max v: kvk=1 v: kvk=1 max max n X = kAk vk2 k=1 n X v: kvk=1 (kv kkAk v k)2 k=1 n X v: kvk=1
2 v T [Ak v] k=1 n X v: kv k=1
2 k=1 n X max max v T Ak v v T A2k v k=1 A2k k=1 2 = σ . 2 4.5 Optimality of matrix concentration result for gaussian series The following simple calculation is suggestive that the parameter σ in Theorem 4.14 is indeed the P correct parameter to understand E k nk=1 gk Ak k. E n X 2 gk Ak = E k=1 n X !2 = E max v T g k Ak v: kvk=1 k=1 ≥ max Ev v: kvk=1 T n X k=1 n X !2 g k Ak !2 g k Ak v k=1 v = max v v: kvk=1 T n X ! A2k v = σ2 (38) k=1 But a natural question is whether the logarithmic term is needed. Motivated by this question we’ll explore a couple of examples. Example 4.17 We can write a d × d Wigner matrix W as a gaussian series, by taking Aij for i ≤ j defined as Aij = ei eTj + ej eTi , if i = 6 j, and √ Aii = 2ei eTi . √ P It is not difficult to see that, in this case, i≤j A2ij = (d + 1)Id×d , meaning that σ = d + 1. This means that Theorem 4.14 gives us p EkW k . d log d, √ however, we know that EkW k  d, meaning that the bound given by NCK (Theorem 4.14) is, in this case, suboptimal by a logarithmic factor.18 The next example will show that the logarithmic factor is in fact needed in some examples P Example 4.18 Consider Ak = ek eTk ∈ Rd×d for k = 1, . . . , d. The matrix nk=1 gk Ak corresponds to a diagonal matrix with independent standard gaussian random variables as √ diagonal entries, and so it’s spectral norm is given by maxk |gk |. It is known that max1≤k≤d |gk |  log d. On the other hand, a direct calculation shows that σ = 1. This shows that the logarithmic factor cannot, in general, be removed. This motivates the question of trying to understand when is P it that the extra dimensional factor n gk Ak has independent entries is needed. For both these examples, the resulting matrix X = k=1 (except for the fact that it is symmetric). The case of independent entries [RS13, Seg00, Lat05, BvH15] is now somewhat understood: Theorem 4.19 ([BvH15]) If X is a d × d random symmetric matrix with gaussian independent entries (except for the symmetry constraint) whose entry i, j has variance b2ij then v u d X p u EkXk . t max b2ij + max |bij | log d. 1≤i≤d j=1 ij Remark 4.20 X in the theorem above can be written in terms of a Gaussian series by taking
Aij = bij ei eTj + ej eTi , for i < j and Aii = bii ei eTi . One can then compute σ and σ∗ : 2 σ = max 1≤i≤d d X b2ij and σ∗2  b2ij . j=1 This means that, when the random matrix in NCK (Theorem 4.14) has negative entries (modulo symmetry) then p (39) EkXk . σ + log dσ∗ . 18 By a  b we mean a . b and a & b. Theorem 4.19 together with a recent improvement of Theorem 4.14 by Tropp [Tro15c]19 motivate the bold possibility of (39) holding in more generality. Conjecture 4.21 Let A1 , . . . , An ∈ Rd×d be symmetric matrices and g1 , . . . , gn ∼ N (0, 1) i.i.d., then: E n X 1 gk Ak . σ + (log d) 2 σ∗ , k=1 While it may very will be that this Conjecture 4.21 is false, no counter example is known, up to date. Open Problem 4.1 (Improvement on Non-Commutative Khintchine Inequality) Prove or disprove Conjecture 4.21. I would also be pretty excited to see interesting examples that satisfy the bound in Conjecture 4.21 while such a bound would not trivially follow from Theorems 4.14 or 4.19. 4.5.1 An interesting observation regarding random matrices with independent matrices For the in n depoendent entries setting, Theorem 4.19 is tight (up to constants) for a wide range of variance profiles b2ij – the details are available as Corollary 3.15 in [BvH15]; the basic idea is that if the i≤j largest variance is comparable to the variance of a sufficient number of entries, then the bound in Theorem 4.19 is tight up to constants. n o However, the situation is not as well understood when the variance profiles b2ij are arbitrary. i≤j Since the spectral norm of a matrix is always at least the `2 norm of a row, the following lower bound holds (for X a symmetric random matrix with independent gaussian entries): EkXk ≥ E max kXek k2 . k Observations in papers of Latala [Lat05] and Riemer and Schutt [RS13], together with the results in [BvH15], motivate the conjecture that this lower bound is always tight (up to constants). Open Problem 4.2 (Latala-Riemer-Schutt) Given X a symmetric random matrix with independent gaussian entries, is the following true? EkXk . E max kXek k2 . k The results in [BvH15] answer this in the positive for a large range of variance profiles, but not in full√generality. Recently, van Handel [vH15] proved this conjecture in the positive with an extra factor of log log d. More precisely, that p EkXk . log log dE max kXek k2 , k where d is the number of rows (and columns) of X. 19 We briefly discuss this improvement in Remark 4.32 4.6 A matrix concentration inequality for Rademacher Series In what follows, we closely follow [Tro15a] and present an elementary proof of a few useful matrix concentration inequalities. We start with a Master Theorem of sorts for Rademacher series (the Rademacher analogue of Theorem 4.14) Theorem 4.22 Let H1 , . . . , Hn ∈ Rd×d be symmetric matrices and ε1 , . . . , εn i.i.d. Rademacher random variables (meaning = +1 with probability 1/2 and = −1 with probability 1/2), then: E n X  εk Hk ≤ 1 + 2dlog(d)e 1 2 σ, k=1 where 2 σ = n X 2 Hk2 (40) . k=1 Before proving this theorem, we take first a small detour in discrepancy theory followed by derivations, using this theorem, of a couple of useful matrix concentration inequalities. 4.6.1 A small detour on discrepancy theory The following conjecture appears in a nice blog post of Raghu Meka [Mek14]. Conjecture 4.23 [Matrix Six-Deviations Suffice] There exists a universal constant C such that, for any choice of n symmetric matrices H1 , . . . , Hn ∈ Rn×n satisfying kHk k ≤ 1 (for all k = 1, . . . , n), there exists ε1 , . . . , εn ∈ {±1} such that n X √ εk Hk ≤ C n. k=1 Open Problem 4.3 Prove or disprove Conjecture 4.23. Note that, when the matrices Hk are diagonal, this problem corresponds to Spencer’s Six Standard Deviations Suffice Theorem [Spe85]. Remark 4.24 Also, using Theorem 4.22, it is easy to show that if one picks εi as i.i.d. Rademacher random variables, then√with positive probability (via the probabilistic method) the inequality will be satisfied with an extra log n term. In fact one has v v u n u n n X u X p p p uX √ 2 t εk Hk . log n Hk ≤ log nt kHk k2 ≤ log n n. E k=1 k=1 k=1 Remark 4.25 Remark 4.24 motivates asking whether Conjecture 4.23 can be strengthened to ask for ε1 , . . . , εn such that 1 n n 2 X X 2 εk Hk . Hk . (41) k=1 k=1 4.6.2 Back to matrix concentration Using Theorem 4.22, we’ll prove the following Theorem. Theorem 4.26 Let T1 , . . . , Tn ∈ Rd×d be random independent positive semidefinite matrices, then   1  1 2 n n 2 X X p 2 Ti ≤  ETi + C(d) E max kTi k  , E i=1 i i=1 where C(d) := 4 + 8dlog de. (42) A key step in the proof of Theorem 4.26 is an idea that is extremely useful in Probability, the trick of symmetrization. For this reason we isolate it in a lemma. Lemma 4.27 (Symmetrization) Let T1 , . . . , Tn be independent random matrices (note that they don’t necessarily need to be positive semidefinite, for the sake of this lemma) and ε1 , . . . , εn random i.i.d. Rademacher random variables (independent also from the matrices). Then E n X n X Ti ≤ i=1 n X ETi + 2E i=1 εi Ti i=1 Proof. Triangular inequality gives E n X Ti ≤ i=1 n X ETi + E i=1 n X (Ti − ETi ) . i=1 Let us now introduce, for each i, a random matrix Ti0 identically distributed to Ti and independent (all 2n matrices are independent). Then E n X (Ti − ETi ) = ET i=1 n  X h i Ti − ETi − ETi0 Ti0 − ETi0 Ti0 i=1 = ET ET 0 n X Ti − Ti0
≤E i=1 n X Ti − Ti0
, i=1 where we use the notation Ea to mean that the expectation is taken with respect to the variable a and the last step follows from Jensen’s inequality with respect to ET 0 . Since Ti − Ti0 is a symmetric random variable, it is identically distributed to εi (Ti − Ti0 ) which gives E n X Ti − Ti0 i=1 concluding the proof.
=E n X i=1 εi Ti − Ti0
≤E n X i=1 εi Ti + E n X i=1 εi Ti0 = 2E n X εi Ti , i=1 2 Proof. [of Theorem 4.26] Using Lemma 4.27 and Theorem 4.22 we get E n X Ti ≤ n X ETi i=1 i=1 1 2 n X p + C(d)E Ti2 i=1 The trick now is to make a term like the one in the LHS appear in the RHS. For that we start by noting (you can see Fact 2.3 in [Tro15a] for an elementary proof) that, since Ti  0, n X Ti2 n X ≤ max kTi k i i=1 Ti . i=1 This means that E n X n X Ti ≤ ETi i i=1 i=1 1 2   1 X n p 2  + C(d)E max kTi k Ti  . i=1 Further applying the Cauchy-Schwarz inequality for E gives, E n X Ti ≤ i=1 n X ETi + 1 2 C(d) E max kTi k  p i i=1 E n X !1 2 Ti , i=1 P Now that the term E k ni=1 Ti k appears in the RHS, the proof can be finished with a simple application of the quadratic formula (see Section 6.1. in [Tro15a] for details). 2 We now show an inequality for general symmetric matrices Theorem 4.28 Let Y1 , . . . , Yn ∈ Rd×d be random independent positive semidefinite matrices, then E n X Yi ≤ p C(d)σ + C(d)L, EYi2 and L2 = E max kYi k2 i=1 where, 2 σ = n X (43) i i=1 and, as in (42), C(d) := 4 + 8dlog de. Proof. Using Symmetrization (Lemma 4.27) and Theorem 4.22, we get E n X i=1 " Yi ≤ 2EY Eε n X i=1 # εi Yi n X p ≤ C(d)E Yi2 i=1 1 2 . Jensen’s inequality gives E n X 1 2 Yi2 ≤ i=1 E !1 n X 2 Yi2 , i=1 2 and the proof can be concluded by noting that Yi2  0 and using Theorem 4.26. Remark 4.29 (The rectangular case) One can extend Theorem 4.28 to general rectangular matrices S1 , . . . , Sn ∈ Rd1 ×d2 by setting   0 Si Yi = , SiT 0 and noting that Yi2  = 0 SiT Si 0 2 Si SiT 0  = 0 T Si Si  = max  SiT Si , Si SiT . We defer the details to [Tro15a] In order to prove Theorem 4.22, we will use an AM-GM like inequality for matrices for which, unlike the one on Open Problem 0.2. in [Ban15d], an elementary proof is known. Lemma 4.30 Given symmetric matrices H, W, Y ∈ Rd×d and non-negative integers r, q satisfying q ≤ 2r,     
 Tr HW q HY 2r−q + Tr HW 2r−q HY q ≤ Tr H 2 W 2r + Y 2r , and summing over q gives 2r X  q Tr HW HY 2r−q  q=0  ≤ 2r + 1 2  
 Tr H 2 W 2r + Y 2r We refer to Fact 2.4 in [Tro15a] for an elementary proof but note that it is a matrix analogue to the inequality, µθ λ1−θ + µ1−θ λθ ≤ λ + θ for µ, λ ≥ 0 and 0 ≤ θ ≤ 1, which can be easily shown by adding two AM-GM inequalities µθ λ1−θ ≤ θµ + (1 − θ)λ and µ1−θ λθ ≤ (1 − θ)µ + θλ. Proof. [of Theorem 4.22] P Let X = nk=1 εk Hk , then for any positive integer p, EkXk ≤ EkXk2p
1 2p = EkX 2p k
1 2p ≤ E Tr X 2p
1 2p , where the first inequality follows from Jensen’s inequality and the last from X 2p  0 and the observation that the trace of a positive semidefinite matrix is at least its spectral norm. In the sequel, we upper bound E Tr X 2p . We introduce X+i and X−i as X conditioned on εi being, respectively +1 or −1. More precisely X X X+i = Hi + εj Hj and X−i = −Hi + εj Hj . j= 6 i j6=i Then, we have n X   E Tr X 2p = E Tr XX 2p−1 = E Tr εi Hi X 2p−1 . i=1  Note that Eεi Tr εi Hi X  2p−1 h  i 2p−1 2p−1 = 21 Tr Hi X+i − X−i , this means that E Tr X 2p = n i X 1 h  2p−1 2p−1 − X− , E Tr Hi X+i i 2 i=1 where the expectation can be taken over εj for j = 6 i. 2p−1 2p−1 Now we rewrite X+i − X−i as a telescopic sum: 2p−1 2p−1 X+i − X−i = 2X p−2 q 2p−2−q X+i (X+i − X−i ) X−i . q=0 Which gives E Tr X 2p n 2p−2 i X X 1 h q 2p−2−q = E Tr Hi X+i (X+i − X−i ) X− . i 2 i=1 q=0 Since X+i − X−i = 2Hi we get E Tr X 2p = p−2 n 2X X h i q 2p−2−q E Tr Hi X+i . Hi X−i (44) i=1 q=0 We now make use of Lemma 4.30 to get20 to get E Tr X 2p ≤ n X 2p − 1 i=1 20 2 h  i 2p−2 2p−2 E Tr Hi2 X+i + X−i . See Remark 4.32 regarding the suboptimality of this step. (45) Hence, n X i=1 2p − 1 2p−2 2p−2 + X− E Tr Hi2 X+i i 2 h  i = (2p − 1) n X   E Tr Hi2 2p−2 2p−2 X+i + X−i 2 i=1 = (2p − 1) = (2p − 1) n X i=1 n X      E Tr Hi2 Eεi X 2p−2   E Tr Hi2 X 2p−2 i=1 " = (2p − 1)E Tr n X ! Hi2 # X 2p−2 i=1 Since X 2p−2  0 we have " n ! # n X X 2 2p−2 Tr Hi X ≤ Hi2 Tr X 2p−2 = σ 2 Tr X 2p−2 , (46) i=1 i=1 which gives E Tr X 2p ≤ σ 2 (2p − 1)E Tr X 2p−2 . (47) Applying this inequality, recursively, we get E Tr X 2p ≤ [(2p − 1)(2p − 3) · · · (3)(1)] σ 2p E Tr X 0 = (2p − 1)!!σ 2p d Hence, EkXk ≤ E Tr X 2p
1 1 1 ≤ [(2p − 1)!!] 2p σd 2p .  p Taking p = dlog de and using the fact that (2p − 1)!! ≤ 2p+1 (see [Tro15a] for an elementary proof e consisting essentially of taking logarithms and comparing the sum with an integral) we get 1  1 1 2dlog de + 1 2 σd 2dlog de ≤ (2dlog de + 1) 2 σ. EkXk ≤ e 2 2p Remark 4.31 A similar argument can be used to prove Theorem 4.14 (the gaussian series case) based on gaussian integration by parts, see Section 7.2. in [Tro15c]. Remark 4.32 Note that, up until the step from (44) to (45) all steps are equalities suggesting that this step may be the lossy step responsible by the suboptimal dimensional P 2 factor in several cases (although (46) can also potentially be lossy, it is not uncommon that Hi is a multiple of the identity matrix, which would render this step also an equality). In fact, Joel Tropp [Tro15c] recently proved an improvement over the NCK inequality that, essentially, consists in replacing inequality (45) with a tighter argument. In a nutshell, the idea is that, if the Hi ’s are non-commutative, most summands in (44) are actually expected to be smaller than the ones corresponding to q = 0 and q = 2p − 2, which are the ones that appear in (45). 4.7 4.7.1 Other Open Problems Oblivious Sparse Norm-Approximating Projections There is an interesting random matrix problem related to Oblivious Sparse Norm-Approximating Projections [NN], a form of dimension reduction useful for fast linear algebra. In a nutshell, The idea is to try to find random matrices Π that achieve dimension reduction, meaning Π ∈ Rm×n with m  n, and that preserve the norm of every point in a certain subspace [NN], moreover, for the sake of computational efficiency, these matrices should be sparse (to allow for faster matrix-vector multiplication). In some sense, this is a generalization of the ideas of the Johnson-Lindenstrauss Lemma and Gordon’s Escape through the Mesh Theorem that we will discuss next Section. Open Problem 4.4 (OSNAP [NN]) Let s ≤ d ≤ m ≤ n. 1. Let Π ∈ Rm×n be a random matrix with i.i.d. entries δri σri Πri = √ , s where σri is a Rademacher random variable and ( √1 with probability s δri = 0 with probability s m 1− s m Prove or disprove: there exist positive universal constants c1 and c2 such that For any U ∈ Rn×d for which U T U = Id×d  Prob (ΠU )T (ΠU ) − I ≥ ε < δ, for m ≥ c1 d+log( 1δ ) ε2 and s ≥ c2 log( dδ ) . ε2 2. Same setting as in (1) but conditioning on m X δri = s, for all i, r=1 meaning that each column of Π has exactly s non-zero elements, rather than on average. The conjecture is then slightly different: Prove or disprove: there exist positive universal constants c1 and c2 such that For any U ∈ Rn×d for which U T U = Id×d  Prob (ΠU )T (ΠU ) − I ≥ ε < δ, for m ≥ c1 d+log( 1δ ) ε2 and s ≥ c2 log( dδ ) . ε 3. The conjecture in (1) but for the specific choice of U :   Id×d U= . 0(n−d)×d In this case, the object in question is a sum of rank 1 independent matrices. More precisely, z1 , . . . , zm ∈ Rd (corresponding to the first d coordinates of each of the m rows of Π) are i.i.d. random vectors with i.i.d. entries  1 s   − √s with probability 2m s 0 with probability 1 − m (zk )j =  s  √1 with probability 2m s 1 Note that Ezk zkT = m Id×d . The conjecture is then that, there exists c1 and c2 positive universal constants such that ) ( m X  T T Prob zk zk − Ezk zk ≥ ε < δ, k=1 for m ≥ c1 d+log( ε2 1 δ ) and s ≥ c2 log( ε2 d δ ) . I think this would is an interesting question even for fixed δ, for say δ = 0.1, or even simply understand the value of m X   T E zk zk − Ezk zkT . k=1 4.7.2 k-lifts of graphs Given a graph G, on n nodes and with max-degree ∆, and an integer k ≥ 2 a random k lift G⊗k of G is a graph on kn nodes obtained by replacing each edge of G by a random k × k bipartite matching. More precisely, the adjacency matrix A⊗k of G⊗k is a nk × nk matrix with k × k blocks given by A⊗k ij = Aij Πij , where Πij is uniformly randomly drawn from the set of permutations on k elements, and all the edges are independent, except for the fact that Πij = Πji . In other words, X
Aij ei eTj ⊗ Πij + ej eTi ⊗ ΠTij , A⊗k = i < j where ⊗ corresponds to the Kronecker product. Note that   1 ⊗k EA = A ⊗ J , k where J = 11T is the all-ones matrix. Open Problem 4.5 (Random k-lifts of graphs) Give a tight upperbound to E A⊗k − EA⊗k . p Oliveira [Oli10] gives a bound that is essentially of the form ∆ log(nk), while the results in [ABG12] suggest that one may expect more concentration for large k. It is worth noting that the case of k = 2 can essentially be reduced to a problem where the entries of the random matrix are independent and the results in [BvH15] can be applied to, in some case, remove the logarithmic factor. 4.8 Another open problem Feige [Fei05] posed the following remarkable conjecture (see also [Sam66, Sam69, Sam68]) Conjecture 4.33 Given n independent random variables X1 , . . . , Xn s.t., for all i, Xi ≥ 0 and EXi = 1 we have ! n X Prob Xi ≥ n + 1 ≤ 1 − e−1 i=1 Note that, if Xi are i.i.d. andXi = nn + 1 with probability 1/(n + 1) and Xi = 0 otherwise, then Pn n Prob ( i=1 Xi ≥ n + 1) = 1 − n+1 ≈ 1 − e−1 . Open Problem 4.6 Prove or disprove Conjecture 4.33.21 21 We thank Francisco Unda and Philippe Rigollet for suggesting this problem.