Lecture 13: Talagrand's Concentration Inequality

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.265/15.070J Lecture 13 Concentration Inequalities and Applications Content. 1 Talagrand’s inequality Let (Ωi , Fi , µi ) be probability spaces (i = 1, ..., n). Let µ = µ1 ... µn be product measure on X = Ω1 × ... × Ωn . Let x = (x1 , ..., xn ) ∈ X be a point in this product space. Hamming distance over X: d(x, y) = |{i ≤ i ≤ n : xi = yi }| = n n 1{xi =yi } i=1 α-weighted Hamming distance over X for a ∈ Rn+ : da (x, y) = n n ai 1{xi =yi } i=1 � Also |a| = a2i . Control-distance from a set: for set A ⊆ X, and x ∈ X: c DA (x) = sup da (x, A) = inf{da (x, y) : y ∈ A} |a|=1 Theorem 1 (Talagrand). For every measurable non-emply set A and productmeasure µ, 1 c 2 1 exp( (DA ) )dµ ≤ 4 µ(A) In particular, c ≥ t}) ≤ µ({DA 1 t2 exp(− ) µ(A) 4 1 2 2.1 Application of Talagrand’s Inequality Concentration of Lipschitz functions. Let F : X → R for product space X = Ω1 × ... × Ωn such that for every x ∈ X, there exists a ≡ a(x) ∈ Rn+ with |a| = 1 so that for each y ∈ Y , F (x) ≤ F (y) + da (x, y) (1) Why does every 1-Lipschitz function is essentially like (1)? Consider a 1-Lipschitz function f : X → R such that n |f (x) − f (y)| ≤ |xi − yi | (defined on Ωi ) for all x, y ∈ X. i Let di = maxx,y∈Ω |xi − yi |. We assume di is bounded for all i. Then, n n |f (x) − f (y)| ≤ |xi − yi | ≤ 1{xi 6=yi } di i i Therefore, d f (x) − f (y) n di q �P �P 1{xi 6=yi } = da (x, y) with ai = q q �Pi ≤ 2 2 d2i i i di i di �P q f (x) 2 Thus F (x) = ||d|| where ||d|| = 2 i di . 2 c (x), Let A = {F ≤ m}. By definition of DA c DA (x) = sup da (x, A) ≥ da (x, y) a:|a|=1 for a given a such that |a| = 1 and y ∈ A. Now for any y ∈ A, by definition F (y) ≤ m. Then, c F (x) ≤ F (y) + da (x, y) ≤ m + DA (x) c (x) ≥ r}. By Talagrand’s inequality, for which implies {F ≥ m + r} ⊆ {DA any r ≥ 0, c P({f ≥ m + r}) ≤ P({DA ≥ r}) ≤ r2 1 exp(− ) 4 P(A) That is, P({F ≤ m})P({F ≥ m + r}) ≤ exp(− 2 r2 ) 4 (2) The median of F , mF is precisely such that 1 1 P(F ≤ mF ) ≥ , P(F ≥ mF ) ≥ 2 2 Choose m = mF , m = mF − r in (2) to obtain: P(F ≥ mF + r) ≤ 2 exp(− r2 r2 ), P(F ≤ mF − r) ≤ 2 exp(− ) 4 4 Thus, P(|F − mF | ≥ r) ≤ 4 exp(− (3) r2 ) 4 2.2 Further Application for Linear Functions Consider the independent random variables Y1 , ..., Yn on some probability space (Ω, F, P). Let the constants (ui , vi ), 1 ≤ i ≤ n such that ui ≤ Yi ≤ vi P Set Z = supt∈T < t, Y >≡ ni=1 ti Yi where T is some finite, countable or compact set of vectors in R+ . We would be interested in situations where n σ 2 = sup t2i (vi − ui )2 ≤ ∞ t∈T i We wish to apply (3) to this setting by choosing F (x) = sup < t, x > t∈T where x ∈ X and X = ni=1 [ui , vi ]. Given that T is compact, F (x) =< t∗ (x), x > for some t = t∗ (x) ∈ T , given x. F (x) = n n t i xi ≤ i=1 n ti yi + i ≤ n i n |ti ||yi − xi | i t i yi + n |ti |(vi − ui )1(yi =x 6 i ) (let di = |ti |(vi − ui )) . i ˜ y > +( ≤ sup < t, ˜ t∈T n di 1(yi = 6 xi ))||d||2 ||d||2 i = F (y) + da (x, y)||d||2 (where let σ = ||d||2 = sup t∈T = F (y) + σda (x, y) n t2i (vi − ui )2 ) (4) 3 By selection of f ≡ σ1 F , (3) can be applied to f : P(|f − mf | ≥ r) ≤ 4 exp(− r2 ) 4 2 Let r = σγ , then P(|σf − σmf | ≥ γ) ≤ 4 exp(− 4γσ2 ). That is, P(|F − mF | ≥ γ) ≤ 4 exp(− γ2 ) 4σ 2 Now, Z ∞ P(F ≥ s)ds (assume t ≡ 0 ∈ T ) Z0 mF Z ∞ ≤ 1ds + P(F ≥ mF + γ)dγ 0 0 Z ∞ γ ≤ mF + 2 exp(− 2 )dγ 4σ 0 Z ∞ γ2 ≤ mF + 2 exp(− 2 )dγ 4σ 0 Z ∞ √ 1 γ2 √ = mF + 2 8πσ 2 exp(− 2 )dγ 4σ 2π4σ 2 0 √ = mF + 2 2πσ E[F ] = Thus, √ |E[F ] − mF | ≤ 2 2πσ 2.3 More Intricate Application Longest increasing subsequence: Let X1 , ..., Xn be points in [0, 1] chosen independently as a product measure. Let Ln (X1 , ..., Xn ) be the length of longest increasing subsequence. (Note that Ln (·) is not obviously Lipschitz). Talagrand’s inequality implies its concentra­ tion. Lemma 1. Let mn be median of Ln . Then for any r > 0, we have P(Ln ≥ mn + r) ≤ 2 exp(− r2 ) 4(mn + r) P(Ln ≤ mn − r) ≤ 2 exp(− 4 r2 ) 4mn Proof. Let us start by establishing first inequality. Select A = {Ln ≤ mn }. Clearly, by definition P(A) ≥ 12 . For a x such that Ln (x) > mn , (i.e. x ∈ A), consider any y ∈ A. Now, let set I ⊆ [n] be indices that give rise to longest increasing subsequence in x: i.e. say I = {i1 , ..., ip } then xi1 < xi2 < ... < xip and p is the maximum length of any such increasing subsequence of x. Let J = {i ∈ I : xi 6= yi } for given y. Since I\J is an index set that corresponds to a increasing subsequence of y (since for i ∈ I\J; xi = yi and I is index set of increasing subsequence of I); we have that (using fact that Ln (y) ≤ mn as y ∈ A) |I\J| ≤ mn That is, Ln (x) = |I| ≤ |I\J| + |J| n 1(xi 6= yi ) ≤ Ln (y) + i∈I ≤ Ln (y) + n n ( 1 ( Ln (x)[ 1(i ∈ I)1(xi 6= yi )] L (x) n i=1 Define ai (x) = ⎧ ⎨√ 1 , Ln (x) ⎩0, if i ∈ I o.w. Then |a| = 1 since |I| = Ln (x) by definition, and hence, ( ( c Ln (x) ≤ Ln (y) + Ln (x)da (x, y) ≤ mn + Ln (x)DA (x) Equivalently, c DA (x) ≥ Ln (x) − mn ( Ln (x) For x such that Ln (x) ≥ mn + r, the RHS of ahove is minimal when Ln (x) = mn + r. Therefore, we have c DA (x) ≥ Ln (x) − mn ( Ln (x) For x such that Ln (x) ≥ mn + r, the RHS of above is minimal when Ln (x) = mn + r. Therefore, we have r c DA (x) ≥ √ mn + r 5 That is c Ln (x) ≥ mn + r ⇒ DA (x) ≥ √ r mn + r for A = {Ln ≤ mn } Putting these together, we have c ≥√ P(Ln ≥ mn + r) ≤ P(DA r mn + r 1 r2 exp(− ) 2P (A) 4(mn + r) )≤ But P(A) = P(Ln ≤ mn ) ≥ 12 , we have that P(Ln ≥ mn + r) ≤ 2 exp(− r2 ) 4(mn + r) To establish lower bound, replace argument of the above with x such that Ln (x) ≥ s + u, A = {Ln ≤ s}. Then we obtain, c DA (x) ≥ √ u s+u Select s = mn − r, u = r. Then whenever x is such that Ln (x) ≥ s + u = mn and for A = {Ln ≤ s} = {Ln ≤ mn − r}. r c DA (x) ≥ √ mn Thus, c P(Ln ≥ mn ) ≤ P(DA ≥ r 1 r2 )≤ exp(− ) P(Ln ≤ mn − r) 4mn mn which implies P(Ln ≤ mn − r) ≤ 2 exp(− r2 ) 4mn This completes the proof. 3 Proof of Talagrand’s Inequality c (x) = sup Preparation. Given set A, x ∈ X: DA (da (x, A) = inf y∈A da (x, y)). a∈Rn + Let UA (x) = {s ∈ {0, 1}n : ∃y ∈ A with s £ 1(x 6= y)} = {1(x 6= y) : y ∈ A} 6 and let n VA (x) = Convex-hull(UA (x)) = { αs S : n αs = 1, αs ≥ 0 for all s ∈ UA (x)} s∈UA (x) Thus, 6 x) = 0 ∈ UA (x) ⇔ 0 ∈ VA (x) x ∈ A ⇔ 1(x = It can therefore be checked that Lemma 2. c DA (x) = d(0, VA (x)) ≡ |y| inf y∈VA (x) c (x) ≤ inf Proof. (i) DA y∈VA (x) |y|: since inf y∈VA (x) (y) is achieved, let Z be such that |Z| = inf y∈VA (x) |y|. Now for any a ∈ Rn+ , |a| = 1: a · y ≤ a · z ≤ |a||z| = |z| inf y∈VA (x) Since inf y∈VA (x) a · y is linear programming, the minimum is achieved at an extreme point. That is, there exists s ∈ UA (x) such that a·y = inf y∈VA (x) inf s∈UA (x) a · s = inf da (x, y) for some y ∈ A. y∈A Since this is true for all a, it follows that, sup inf da (x, y) ≤ |z| ≡ y∈A |a|=1,a∈Rn + |y| inf y∈VA (x) c (x) ≥ inf (ii) DA y∈VA (x) |y|: Let z be the one achieving minimum P 2 in VA (x). Then due to convexity of the objective (equivalently |y|2 = yi = f (y)) and of the domain, we have for any y ∈ VA (x), vf (z)(y − z) ≥ 0 for any y ∈ VA (x). vf (z) = v(z · z) = 2z. Therefore the condition implies (y − z)z ≥ 0 ⇔ y · z ≥ z · z = |z|2 ⇒ y · Thus, for a = z |z| z ≥ |z| |z| ∈ Rn+ , |a| = 1, we have that inf a · y ≥ |z| y∈VA (x) But for any given a, inf y∈VA (x) a · y = inf s∈UA (x) a · s = da (x, A) as explained before. That is, supa:|a|=1 da (x, A) ≥ |z| = inf y∈VA (x) |y|. This completes the proof. 7 Now we are ready to establish the inequality of Talagrand. The proof is via induction. Consider n = 1, given set A. Now, c (x) = DA 0, for x ∈ A 1, for x ∈ /A inf da (x, y) = inf 1(x 6= y) = sup y∈A a∈Rn + ,|a|=1 y∈A Then, Z Z 2 exp(D /4)dP = Z exp(0)dP + exp(1/4)dP Ac A = P (A) + e1/4 (1 − P (A)) = e1/4 − (e1/4 − 1)P (A) ≤ 1 P (A) (5) Let f (x) = e1/4 −(e1/4 −1)x and g(x) = x1 . Because f (x) is a decreasing func­ tion of x, g(x) is a decreasing convex function. Thus, the result if established for n = 1. Induction hypothesis. Let it hold for some n. We shall assume for ease of the proof that Ω1 = Ω2 = ... = Ωn = ... = Ω. L Let A ⊂ Ωn+1 . Let B be its projection on Ωn . Let A(ω), ω ∈ Ω be section of A along ω: if x ∈ Ωn , ω ∈ Ω then z = (x, ω) ∈ Ωn+1 . We observe the following: if s ∈ UA(ω) (x), then (s, 0) ∈ UA (z). Because, for some y ∈ Ωn such that 6 y). Therefore, (s, 0) = (1(x = 6 y), 1(ω = 6 ω)) = 1(z = 6 (y, ω) ∈ A, s = 1(x = (y, ω)) where (y, ω) ∈ A. Further, if t ∈ UB (x), then (t, 1) ∈ UA (z). This is because of the following: B = {x̃ ∈ Ωn : (x̃, ω̃) ∈ A for some ω̃ ∈ Ω}. Now if t ∈ UB (x), then ∃ y ∈ B such that t = 1(x 6= y). Now (t, 1) = (1(x 6= y), 1(ω̃ 6= ω)) = 1(z 6= (y, ω̃)) as long as there exists ω̃ so that (y, ω̃) ∈ A and 6 ω. ω̃ = Given this, it follows that if ξ ∈ VA(ω) (x), ζ ∈ VB (x), and θ ∈ [0, 1], then ((θξ + (1 − θ)ζ), 1 − θ) ∈ VA (z). Recall that c (z)2 = DA inf |y|2 ≤ (1 − θ)2 + |θξ + (1 − θ)ζ|2 y∈VA (z) ≤ (1 − θ)2 + θ|ξ|2 + (1 − θ)|ζ|2 (6) Therefore, c (z)2 ≤ (1 − θ)2 + θ DA inf ξ∈VA(ω) (x) |ξ|2 + (1 − θ) inf ζ∈VB (x) c c = (1 − θ)2 + θDA(ω) (x)2 + (1 − θ)DB (x)2 8 |ζ|2 By Hölder’s inequality, and the induction hypothesis, for ∀ω ∈ Ω, Z c 2 eDA (x,ω) /4 dP (x) Ωn Z ≤ exp c (1 − θ)2 + θDA ( ω) c (x) (x)2 + (1 − θ)DB 4 Ωn (1 − θ)2 ≤ exp( ) 4 Z exp( c θDA(ω) (x)2 4 Ωn X ) exp( - dP (x) c (x)2 (1 − θ)DB ) dP (x) 4 Y θ)2 (1 − )E[X · Y ] 4 1 1 (1 − θ)2 ≤ exp( : θ ∈ [0, 1]) )E[X p ]1/p E[Y q ]1/q , (for p = , q = 4 θ 1−θ Z θ Z (1 − θ)2 c c = exp( ) exp(DA(ω) (x)2 /4)dP (x) exp(DB (x)2 /4)dP (x) 4 n n Ω Ω (1 − θ)2 1 1 ≤ exp( )( )θ ( )1−θ by induction hypothesis. 4 P (A(ω)) P (B) = exp( = exp (1 − θ)2 4 1 P (B) P (A(ω)) P (B) −θ (7) (7) is true for any θ ∈ [0, 1], so for tightest upper bound, we shall optimize. 2 −θ ≤ 2 − u. Claim: for any u ∈ [0, 1], inf θ∈[0,1] exp( (1−θ) 4 )u Therefore, (7) reduces to ≤ 1 P (A(ω)) (2 − ) P (B) P (B) Therefore, Dc (x, ω)2 exp( A )dP (x)dµ(ω) 4 Ωn+1 Z 1 P(A(ω)) ≤ (2 − )dµ(ω) P(B) Ω P(B) N 1 (P µ)(A) ≤ (2 − ) P(B) P(B) 1 N ≤ , (since u(2 − u) ≤ 1 for all u ∈ R) (P µ)(A) Z (8) This completes the proof of Talagrand’s inequality. ' Claim: f (u) = u(2 − u) ⇒ f (u) = 2 − 2u ⇒ u∗ = 1 ⇒ maxu f (u) = 9 1−θ f (1) = 1. 2 −θ ≤ 2 − u: Proof. To establish: inf θ∈[0,1] exp( (1−θ) 4 )u if u ≥ e−1/2 : θ = 1 + 2 log u ⇒ 1−θ 2 = − log u ⇒ 2 u −θ −θ log u − log u −2 log u =e =e e . Thus, exp( (1−θ)2 4 = log2 (u) and (1 − θ)2 −θ )u = exp(log2 u − 2 log2 u − log u) = exp(− log u − log2 u) u We have that 1 1 1 1 ≥ u ≥ e−1/2 ⇒ 0 ≥ log u ≥ − ⇒ 0 ≤ − log u ≤ , 0 ≤ log2 u ≤ 2 2 4 and ' f (x) = −x − x2 : x ∈ [−1/2, 0]; f (x) = −1 − 2x ≤ 0 for x ∈ [−1/2, 0] Thus, − log u − log2 u ≤ 1 1 1 1 − ≤ ⇒ exp(− log u − log2 u) ≤ 2 4 4 4 1 and for u ≥ e− 2 which implies that 2 − u ≥ exp(− log u − log2 u). 10