CS 6106: Statistical Learning Theory Spring 2025

Lecture 2 — 10th Jan

Lecturer: Avishek Ghosh Scribe: Sagar Singh

2.1 Recall
We saw in the last class that a r.v like

1 n
Z = sup
f ∈F
∑ f (Xi) − E[ f (X)]
n i=1

is important in understanding the generalization error of a machine learning algorithm. This

motivates us to study the following:

• Concentration inequalities; Show that Z is close to E[Z]

• Control of E[Z] through techniques like symmetriztion, chaining etc.

2.2 Concentration of measure

We will assume that the function f ∈ F are bounded, i.e.

sup | f (x)| 6 B ∀ f ∈ F,
x

for some positive constant B.

Theorem 2.1 (McDiarmid’s Bounded Difference Inequality). Consider independent random

variables X1 , X2 , . . . , Xn where Xi ∈ Xi for all i. Also let g : X1 × X2 × · · · × Xn → R satisfy the
bounded differences property below:

g(x1 , x2 , . . . , xi , . . . , xn ) − g(x1 , x2 , . . . , xi0 , . . . , xn ) 6 ci ∀ xi ∈ Xi and ∀ i = 1, 2, . . . , n

Then, for any t > 0, we have

2t 2
 
P(g(X1 , X2 , . . . , Xn ) − E[g(X1 , X2 , . . . , Xn )] > t) 6 exp − n 2 ,
∑i=1 ci
2t 2
 
P(g(X1 , X2 , . . . , Xn ) − E[g(X1 , X2 , . . . , Xn )] 6 −t) 6 exp − n 2 .
∑i=1 ci

2-1
CS 6106 Lecture 2 — 10th Jan Spring 2025

Remark: The bounded differences inequality states that a function that is not too sensitive
on any of its arguments concentrates.
To apply McDiarmid’s inequality to Z.
1 n
Z = sup
f ∈F
∑ f (Xi) − E[ f (X)]
n i=1
we construct,
1 n
g(x1 , x2 , . . . , xi , . . . , xn ) = sup
f ∈F
∑ f (xi) − E[ f (X)]
n i=1
1 n f (xi0 )
g(x1 , x2 , . . . , xi0 , . . . , xn ) = sup ∑ f (x j ) + − E[ f (X)]
f ∈F n j6=i n

1 n
f (xi0 ) f (xi )
= sup ∑ f (x j ) − E[ f (X)] + −
f ∈F n j=1 n n
.
Using triangle inequality, we have
1 n
f (xi0 ) f (xi )
6 sup
f ∈F n
∑ f (x j ) − E[ f (X)] + fsup
∈F n
−
n
,
j=1
f (xi0 ) f (xi )
6 g(x1 , x2 , . . . , xi , . . . , xn ) + sup + sup .
f ∈F n f ∈F n
therefore we have shown that,
2B
g(x1 , x2 , . . . , xi , . . . , xn ) − g(x1 , x2 , . . . , xi0 , . . . , xn ) 6
. . . (ci )
n
Interchange the role of xi and xi0 to get the other inequality. So g(.) satisfies the bounded
differences property with ci = 2B
n ∀ i = 1, 2, . . . , n. then by McDiarmid’s inequality, we have
2t 2
 
P (Z − E[Z] > t) 6 exp − n 2
∑i=1 ci
!
2t 2
6 exp −
2
∑ni=1 2B n
nt 2
 
6 exp − 2 .
2B
Lets take δ = exp( −nt ), then with probability atleast 1 − δ , we have,
2
2B2
s  
2 1
Z 6 E[Z] + B log
n δ

2-2
CS 6106 Lecture 2 — 10th Jan Spring 2025

Similarly, we can show that w.p > 1 − δ

s  
2 1
Z > E[Z] − B log
n δ

Next we will prove the following inequalities towards a proof of the Bounded difference
inequality:

2.3 Hoeffding’s inequality

Suppose X1 , X2 , . . . , Xn are independent random variables such that Xi ∈ [ai , bi ] ∀ i. Then for
any t > 0, we have
n
−2t 2
 
P( ∑ (Xi − E[Xi ]) > t) 6 exp
i=1 ∑ni=1 (bi − ai )2
and also
n
−2t 2
 
P( ∑ (Xi − E[Xi ]) 6 −t) 6 exp
i=1 ∑ni=1 (bi − ai )2

Proof: Let S = ∑ni=1 (Xi − E[Xi ]). Fix λ > 0.

Then we have,

P(S > t) 6 P(eλ S > eλ t )

eλ S
6 E[ ]
eλ t
6 e−λ t E[eλ S ]
6 exp (−λ t + Ψs (λ ))

 
where Ψs (λ ) = log E[eλ S ] is the log moment generating function of S.

Ψs (λ ) = log(E[eλ S ])
n
= log(∏ E[eλ (Xi −E[Xi ]) ])
i=1
n
= ∑ log(E[eλ (Xi −E[Xi ]) ])
i=1
n
= ∑ ΨXi −E[X] (λ )
i=1

2-3
CS 6106 Lecture 2 — 10th Jan Spring 2025

Let U = Xi −E[X], we need to bound ΨU (λ ). Note that E[U] = 0 and ai −E[Xi ] 6 U 6 bi −E[Xi ]
a.s.
Using Taylor expansion of ΨU (λ ) we have,

λ 2 00 0
0
ΨU (λ ) = ΨU (0) + λ ΨU (0) + Ψ (λ ) where 0 6 λ 0 6 λ ,
2 U
ΨU (0) = 0,
0 d
ΨU (λ ) = log E[eλ U ]
dλ
1
= E[Ueλ U ]
E[eλ U ]
00 d Ueλ U
ΨU (λ 0 ) = E[ λ U ]
d λ E[e ]
! !2
U 2 eλ U Ueλ U
= E[ ] − E[ ] .
E[eλ U ] E[(eλ U )]

Consider a random variable V whose density w.r.t U is eλ U

E[eλ U ]
, then we have,

00
ΨU (λ ) = E[V 2 ] − (E[V ])2 = var(V ) > 0

now since ai − E[Xi ] 6 V 6 bi − E[Xi ] a.s, we have

(bi − ai )2
var(V ) 6
4
therefore,
λ 2 00 0 λ 2 (bi − ai )2
Ψs (λ ) = ΨU (λ ) 6
2 8
Substituting this above we get,
!
n
λ 2 (bi − ai )2
P(S > t) 6 exp −λ t + ∑
i=1 8

optimize over λ to get the result with λ ∗ = 4t

∑ni=1 (bi −ai )2
. To get in the reverse direction use
the same argument with −Yi = Xi . 

2-4
Bibliography

[1] Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cam-

bridge University Press, 1 edition, February 2019.