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

2021
Views:

206

Pages:

2
Author:

varsepaib

Lecture 06 Bernstein’s inequality. 18.465 Last time we proved Bennett’s inequality: EX = 0, EX 2 = σ 2 , |X| < M = const, X1 , · · · , Xn independent copies of X, and t ≥ 0. Then P � n � � Xi ≥ t i=1 � � �� nσ 2 tM ≤ exp − 2 φ , nσ 2 M where φ(x) = (1 + x) log(1 + x) − x. If X is small, φ(x) = (1 + x)(x − x2 2 + · · · ) − x = x + x2 − x2 2 − x + ··· = x2 2 + ···. If X is large, φ(x) ∼ x log x. We can weaken the bound by decreasing φ(x). Take1 φ(x) = P � n � � Xi ≥ t = t2 . 2nσ 2 + 23 tM to obtain Bernstein’s inequality: � � � �� tM 2 nσ 2 nσ 2 ≤ exp − 2 tM M 2 + 23 nσ 2 � � 2 t = exp − 2 2nσ + 23 tM � i=1 where u = x2 2+ 23 x e−u Solve for t: 2 t2 − uM t − 2nσ 2 u = 0 3 � 1 u2 M 2 t = uM + + 2nσ 2 u. 3 9 Substituting, P � n � � Xi ≥ i=1 or P Using inequality √ a+b≤ � n � � Xi ≤ i=1 √ a+ u2 M 2 uM + 2nσ 2 u + 3 9 u2 M 2 uM + 2nσ 2 u + 3 9 � ≤ e−u � ≥ 1 − e−u √ P b, � n � Xi ≤ √ 2nσ 2 u i=1 2uM + 3 � ≥ 1 − e−u For non-centered Xi , replace Xi with Xi − EX or EX − Xi . Then |Xi − EX| ≤ 2M and so with high probability � (Xi − EX) ≤ √ 2nσ 2 u + 4uM . 3 Normalizing by n, 1� Xi − EX ≤ n � 1� EX − Xi ≤ n � and 1exercise: show that this is the best approximation 2σ 2 u 4uM + 3n n 2σ 2 u 4uM + . 3n n Lecture 06 Whenever � Bernstein’s inequality. 2σ 2 u n ≥ 4uM 3n , we have u ≤ nσ 2 8M 2 . So, | n1 � Xi − EX | � 18.465 � 2σ 2 u n for u � nσ 2 (range of normal deviations). This is predicted by the Central Limit Theorem (condition for CLT is nσ 2 → ∞). If nσ 2 does not go to inﬁnity, we get Poisson behavior. Recall from the last lecture that the we’re interested in concentration inequalities because we want to �n know P (f (X) �= Y ) while we only observe n1 i=1 I (f (Xi ) �= Yi ). In Bernstein’s inequality take �� Xi�� to be I(f (Xi ) �= Yi ). Then, since 2M = 1, we get n 1� I (f (Xi ) �= Yi ) ≤ EI(f (Xi ) �= Yi ) − n i=1 � 2P (f (Xi ) �= Yi ) (1 − P (f (Xi ) �= Yi ))u 2u + n 3n because EI(f (Xi ) �= Yi ) = P (f (Xi ) �= Yi ) = EI 2 and therefore Var(I) = σ 2 = EI 2 − (EI)2 . Thus, � n 1� 2P (f (Xi ) �= Yi ) u 2u P (f (Xi ) �= Yi ) ≤ I (f (Xi ) �= Yi ) + + n 3n n i=1 with probability at least 1 − e−u . When the training error is zero, � 2P (f (Xi ) �= Yi ) u 2u + . P (f (Xi ) �= Yi ) ≤ n 3n 2 If we forget about 2u/3n for a second, we obtain P (f (Xi ) �= Yi ) ≤ 2P (f (Xi ) �= Yi ) u/n and hence P (f (Xi ) �= Yi ) ≤ 2u . n The above zero-error rate is better than n−1/2 predicted by CLT.

Lecture 6: Bernstein’s Inequality

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock