University:
Massachusetts Institute of Technology
Course:
18.465 | Topics in Statistics: Statistical Learning Theory
Academic year:

2022
Views:

316

Pages:

3
Author:

opisivanetmi

Hoeffding’s inequality, Hoeffding-Chernoff inequality. Lecture 07 18.465 Let a1 , . . . , an ∈ R and let ε1 , . . . , εn be i.i.d. Rademacher random variables: P (εi = 1) = P (εi = −1) = 0.5. Theorem 7.1 (Hoeffding). For t ≥ 0, n X P ! εi ai ≥ t i=1 t2 ≤ exp − Pn 2 . 2 i=1 ai Proof. Similarly to the proof of Bennett’s inequality (Lecture 5), ! ! n n n X Y X −λt −λt εi ai = e E exp (λεi ai ) . εi ai ≥ t ≤ e E exp λ P i=1 i=1 Using inequality ex +e−x 2 ≤ ex 2 /2 i=1 (from Taylor expansion), we get λ2 a2 1 1 i E exp (λεi ai ) = eλai + e−λai ≤ e 2 . 2 2 Hence, we need to minimize the bound with respect to λ > 0: ! n X λ2 P n 2 P εi ai ≥ t ≤ e−λt e 2 i=1 ai . i=1 Setting derivative to zero, we obtain the result. Now we change variable: u = 2 2 t Pn 2 i=1 ai p . Then t = 2u Pn i=1 a2i . v   u n n X u X P εiai ≥ t2u a2i  ≤ e−u i=1 and i=1 v   u n n X u X εi ai ≤ t2u P a2i  ≥ 1 − e−u . i=1 Here i=1 Pn 2 i=1 εi ai ). i=1 ai = Var( Pn Rademacher sums will play important role in future. Consider again the problem of estiP mating n1 ni=1 f (Xi ) − Ef . We will see that by the Symmetrization technique, n n n 1X 1X 1X f (Xi ) − Ef ∼ f (Xi ) − f (Xi′). n i=1 n i=1 n i=1 Hoeffding’s inequality, Hoeffding-Chernoff inequality. Lecture 07 18.465 In fact, n E n n n 1X 1X 1X 1X f (Xi ) − Ef ≤ E f (Xi ) − f (Xi′ ) ≤ 2E f (Xi ) − Ef . n i=1 n i=1 n i=1 n i=1 The second inequality above follows by adding and subtracting Ef : n n 1X 1X E f (Xi ) − f (Xi′ ) n i=1 n i=1 n n 1X 1X ≤ E f (Xi ) − Ef + E f (Xi′ ) − Ef n i=1 n i=1 n 1X = 2E f (Xi ) − Ef n i=1 while for the first inequality we use Jensen’s inequality: n E 1X f (Xi ) − Ef n i=1 n = E n 1X 1X f (Xi ) − Ef (Xi′ ) n i=1 n i=1 n n 1X 1X f (Xi ) − Ef (Xi′ ) . ≤ EX EX ′ n i=1 n i=1 P P P Note that n1 ni=1 f (Xi )− n1 ni=1 Ef (Xi′ ) is equal in distribution to n1 ni=1 εi (f (Xi )−f (Xi′ )). We now prove Hoeffding-Chernoff Inequality: Theorem 7.2. Assume 0 ≤ Xi ≤ 1 and µ = EX. Then ! n X P Xi − µ ≥ t ≤ e−nD(µ+t,µ) i=1 where the KL-divergence D(p, q) = p log pq + (1 − p) log 1−p . 1−q Proof. Note that φ(x) = eλx is convex and so eλx = eλ(x·1+(1−x)·0) ≤ xeλ + (1 − x)eλ·0 = 1 − x + xeλ . Hence, EeλX = 1 − EX + EXeλ = 1 − µ + µeλ . Again, we minimize the following bound with respect to λ > 0: ! n X P P Xi ≥ n(µ + t) ≤ e−λn(µ+t) Eeλ Xi i=1 = e−λn(µ+t) EeλX n ≤ e−λn(µ+t) 1 − µ + µeλ n Hoeffding’s inequality, Hoeffding-Chernoff inequality. Lecture 07 18.465 Take derivative w.r.t. λ: −n(µ + t)e−λn(µ+t) (1 − µ + µeλ )n + n(1 − µ + µeλ )n−1 µeλ e−λn(µ+t) = 0 −(µ + t)(1 − µ + µeλ ) + µeλ = 0 (1 − µ)(µ + t) . eλ = µ(1 − µ − t) Substituting, P n X Xi ≥ n(µ + t) i=1 ! !n µ+t µ(1 − µ − t) (1 − µ)(µ + t) 1−µ+ (1 − µ)(µ + t) 1−µ−t ! µ+t 1−µ−t n µ 1−µ = µ+t 1−µ−t 1−µ−t µ+t , + (1 − µ − t) log = exp −n (µ + t) log µ 1−µ ≤ completing the proof. Moreover, ! ! n n X X P µ− Xi ≥ t = P Zi − µZ ≥ t ≤ e−nD(µz +t,µZ ) = e−nD(1−µX +t,1−µX ) i=1 i=1 where Zi = 1 − Xi (and thus µZ = 1 − µX ). If 0 < µ ≤ 1/2, D(1 − µ + t, 1 − µ) ≥ t2 . 2µ(1 − µ) Hence, we get P µ− n X Xi ≥ t i=1 Solving for t, P µ− n X i=1 ! Xi ≥ r nt2 ≤ e− 2µ(1−µ) = e−u . 2µ(1 − µ)u n ! ≤ e−u . If Xi = 0, 1, then µ = EX = P (X = 1) and Var(X) = µ(1 − µ).

Lecture 7: Hoeffding’s Inequality, Hoeffding-Chernoff Inequality

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock