CS229 Supplemental Lecture notes Hoeffding’s inequality

1 CS229 Supplemental Lecture notesHoeffding s inequalityJohn Duchi1 Basic probability boundsA basic question in probability, statistics, and machine learning is the fol-lowing: given a random variableZwith expectationE[Z], how likely isZtobe close to its expectation? And more precisely, how close is it likely to be?With that in mind, these notes give a few tools for computing bounds of theformP(Z E[Z] +t) andP(Z E[Z] t)(1)fort first bound is perhaps the most basic of all probability inequalities,and it is known as Markov s inequality . Given its basic-ness, it is perhapsunsurprising that its proof is essentially only one 1(Markov s inequality ).LetZ 0be a non-negative randomvariable. Then for allt 0,P(Z t) E[Z] note thatP(Z t) =E[1{Z t}], and that ifZ t, then itmust be the case thatZ/t 1 1{Z t}, while ifZ < t, then we still haveZ/t 0 =1{Z t}. ThusP(Z t) =E[1{Z t}] E[Zt]=E[Z]t,as all other bounds on the probabilities (1) are variations onMarkov s inequality .

2 The first variation uses second moments the variance of a random variable rather than simply its mean, and is knownas Cheby-shev s 2(Chebyshev s inequality ).LetZbe any random variable withVar(Z)< . ThenP(Z E[Z] +torZ E[Z] t) Var(Z)t2fort result is an immediate consequence of Markov s inequality . Wenote that ifZ E[Z] +t, then certainly we have (Z E[Z])2 t2, andsimilarly ifZ E[Z] twe have (Z E[Z])2 t2. ThusP(Z E[Z] +torZ E[Z] t) =P((Z E[Z])2 t2)(i) E[(Z E[Z])2]t2=Var(Z)t2,where step (i) is Markov s nice consequence of Chebyshev s inequality is that averages of randomvariables with finite variance converge to their mean. Let usgive an exampleof this fact. Suppose thatZiare and satisfyE[Zi] = 0. ThenE[Zi] = 0,while if we define Z=1n ni=1 ZithenVar( Z) =E[(1nn i=1Zi)2]=1n2 i,j nE[ZiZj] =1n2n i=1E[Z2i] =Var(Z1) particular, for anyt 0 we haveP( 1nn i=1Zi t) Var(Z1)nt2,so thatP(| Z| t) 0 for anyt > Moment generating functionsOften, we would like sharper even exponential bounds on the probabilitythat a random variableZexceeds its expectation by much.

3 With that inmind, we need a stronger condition than finite variance, for which momentgenerating functions are natural candidates. (Conveniently, they also playnicely with sums, as we will see.) Recall that for a random variableZ, themoment generating functionofZis the functionMZ( ) :=E[exp( Z)],(2)which may be infinite for some . Chernoff boundsChernoff bounds use of moment generating functions in an essential way togive exponential deviation 3(Chernoff bounds).LetZbe any random variable. Then foranyt 0,P(Z E[Z] +t) min 0E[e (Z E[Z])]e t= min 0MZ E[Z]( )e tandP(Z E[Z] t) min 0E[e (E[Z] Z)]e t= min 0ME[Z] Z( )e only prove the first inequality , as the second is completely iden-tical. We use Markov s inequality . For any >0, we haveZ E[Z] +tifand only ife Z e E[Z]+ t, ore (Z E[Z]) e t. Thus, we haveP(Z E[Z] t) =P(e (Z E[Z]) e t)(i) E[e (Z E[Z])]e t,where the inequality (i) follows from Markov s our choice of >0 did not matter, we can take the best one by minizing the rightside ofthe bound.

4 (And noting that certainly the bound holds at = 0.)3 The important result is that Chernoff bounds play nicely with sum-mations, which is a consequence of the moment generating function. Let usassume thatZiare independent. Then we have thatMZ1+ +Zn( ) =n i=1 MZi( ),which we see becauseE[exp( n i=1Zi)]=E[n i=1exp( Zi)]=n i=1E[exp( Zi)],by of the independence of theZi. This means that when we calculate aChernoff bound of a sum of variables, we need only calculate the momentgenerating function foroneof them. Indeed, suppose thatZiare and(for simplicity) mean zero. ThenP(n i=1Zi t) ni=1E[exp( Zi)]e t= (E[e Z1])ne t,by the Chernoff Moment generating function examplesNow we give several examples of moment generating functions,which enableus to give a few nice deviation inequalities as a result. For all of our examples,we will have very convienent bounds of the formMZ( ) =E[e Z] exp(C2 22)for all R,for someC R(which depends on the distribution ofZ); this form isverynice for applying Chernoff begin with the classical normal distribution, whereZ N(0, 2).

5 Then we haveE[exp( Z)] = exp( 2 22),4which one obtains via a calculation that we omit. (You shouldwork this outif you are curious!)A second example is known as a Rademacher random variable, ortherandom sign variable. LetS= 1 with probability12andS= 1 withprobability12. Then we claim thatE[e S] exp( 22)for all R.(3)To see inequality (3), we use the Taylor expansion of the exponential function,that is, thatex= k=0xkk!. Note thatE[Sk] = 0 wheneverkis odd, whileE[Sk] = 1 wheneverkis even. Then we haveE[e S] = k=0 kE[Sk]k!= k=0,2,4,.. kk!= k=0 2k(2k)!.Finally, we use that (2k)! 2k k! for allk= 0,1,2, .., so thatE[e S] k=0( 2)k2k k!= k=0( 22)k1k!= exp( 22).Let us apply inequality (3) in a Chernoff bound to see how largea sum random signs is likely to have that ifZ= ni=1Si, whereSi { 1}is a random sign, thenE[Z] = 0. By the Chernoff bound, it becomes immediately clear thatP(Z t) E[e Z]e t=E[e S1]ne t exp(n 22)e the Chernoff bound technique, we may minimize this in 0,which is equivalent to findingmin 0{n 22 t}.

6 Luckily, this is a convenient function to minimize: taking derivatives andsetting to zero, we haven t= 0, or =t/n, which givesP(Z t) exp( t22n).5In particular, takingt= 2nlog1 , we haveP(n i=1Si 2nlog1 ) .SoZ= ni=1Si=O( n) with extremely high probability the sum ofnindependent random signs is essentially never larger thanO( n).3 Hoeffding s lemma and Hoeffding s inequal-ityHoeffding s inequality is a powerful technique perhaps the most importantinequality in learning theory for bounding the probability that sums ofbounded random variables are too large or too small. We will state theinequality, and then we will prove a weakened version of it based on ourmoment generating function calculations 4(Hoeffding s inequality ).LetZ1, .. , Znbe independent boundedrandom variables withZi [a, b]for alli, where < a b < . ThenP(1nn i=1(Zi E[Zi]) t) exp( 2nt2(b a)2)andP(1nn i=1(Zi E[Zi]) t) exp( 2nt2(b a)2)for allt prove Theorem 4 by using a combination of (1) Chernoff bounds and(2) a classic lemma known as Hoeffding s lemma, which we now 5(Hoeffding s lemma).

7 LetZbe a bounded random variable withZ [a, b]. ThenE[exp( (Z E[Z]))] exp( 2(b a)28)for all prove a slightly weaker version of this lemma with a factorof 2instead of 8 using our random sign moment generating bound and an inequal-ity known asJensen s inequality (we will see this very important inequalitylater in our derivation of the EM algorithm). Jensen s inequality states thefollowing: iff:R Ris aconvexfunction, meaning thatfis bowl-shaped,thenf(E[Z]) E[f(Z)].The simplest way to remember this inequality is to think off(t) =t2, andnote that ifE[Z] = 0 thenf(E[Z]) = 0, while we generally haveE[Z2]> any case,f(t) = exp(t) andf(t) = exp( t) are convex use a clever technique in probability theory known assymmetrizationto give our result (you are not expected to know this, but it isa very commontechnique in probability theory, machine learning, and statistics, so it isgood to have seen). First, letZ be an independent copy ofZwith thesame distribution, so thatZ [a, b] andE[Z ] =E[Z], butZandZ areindependent.

8 ThenEZ[exp( (Z EZ[Z]))] =EZ[exp( (Z EZ [Z ]))](i) EZ[EZ exp( (Z Z ))],whereEZandEZ indicate expectations taken with respect toZandZ .Here, step (i) uses Jensen s inequality applied tof(x) =e x. Now, we haveE[exp( (Z E[Z]))] E[exp ( (Z Z ))].Now, we note a curious fact: the differenceZ Z is symmetric about zero,so that ifS { 1,1}is a random sign variable, thenS(Z Z ) has exactlythe same distribution asZ Z . So we haveEZ,Z [exp( (Z Z ))] =EZ,Z ,S[exp( S(Z Z ))]=EZ,Z [ES[exp( S(Z Z ))|Z, Z ]].Now we use inequality (3) on the moment generating function ofthe randomsign, which gives thatES[exp( S(Z Z ))|Z, Z ] exp( 2(Z Z )22).But of course, by assumption we have|Z Z | (b a), so (Z Z )2 (b a) givesEZ,Z [exp( (Z Z ))] exp( 2(b a)22).7 This is the result (except with a factor of 2 instead of 8).Now we use Hoeffding s lemma to prove Theorem 4, giving only the uppertail ( the probability that1n ni=1(Zi E[Zi]) t) as the lower tail hasa similar proof. We use the Chernoff bound technique, which immediatelytells us thatP(1nn i=1(Zi E[Zi]) t)=P(n i=1(Zi E[Zi]) nt) E[exp( n i=1(Zi E[Zi]))]e nt=(n i=1E[e (Zi E[Zi])])e nt(i) (n i=1e 2(b a)28)e ntwhere inequality (i) is Hoeffding s Lemma (Lemma 5).

9 Rewriting this slightlyand minimzing over 0, we haveP(1nn i=1(Zi E[Zi]) t) min 0exp(n 2(b a)28 nt)= exp( 2nt2(b a)2),as