STAT 597

Homework #2, due Sunday, February 23, 2025

Question 1: (McDiarmid’s inequality) Let X1 , . . . , Xn be independent X -valued random variables

drawn from P. Let g : X n → R be such that

sup |g(x1 , . . . , xi , xi+1 , . . . , xn ) ↑ g(x1 , . . . , x→i , xi+1 , . . . , xn )| ↓ ci , ↔ i = 1, . . . , n.

x1 ,...,xn ,x→i

Then 2
↑ !n2ω
Pn ({(X1 , . . . , Xn ) : g(X1 , . . . , Xn ) ↑ Eg(X1 , . . . , Xn ) ↗ ω}) ↓ e c2
i=1 i (1)
and 2
↑ !n2ω
Pn ({(X1 , . . . , Xn ) : |g(X1 , . . . , Xn ) ↑ Eg(X1 , . . . , Xn )| ↗ ω}) ↓ 2e c2
i=1 i . (2)

In the following, we prove the above inequalities.

(a) Show that E [Vi |X1 , . . . , Xi↑1 ] = 0 where

Vi := E [g(X1 , . . . , Xn )|X1 , . . . , Xi ] ↑ E [g(X1 , . . . , Xn )|X1 , . . . , Xi↑1 ] ,

i.e., V1 , . . . , Vn is a martingale di!erence sequence.

(b) Show that Li ↓ Vi ↓ Ui where Ui ↑Li ↓ ci , i = 1 . . . , n. (Hint: Since Vi is a function of (X1 , . . . , Xi ),
we can choose Ui and Vi as the sup and inf of Vi over Xi ).
! " ε2 c 2
i
(c) Using the lemma to prove Hoe!ding’s inequality, show that E eωVi |X1 , . . . , Xi↑1 ↓ e 8 .
! " ε2
!n 2
i=1 ci
(d) Using (c), show that E eω(g(X1 ,...,Xn )↑Eg(X1 ,...,Xn )) ↓ e 8 .
(e) Using Cherno! bounding technique, prove (1). Using (1), prove (2).

Question 2: (Covering # numbers) (a) Let N (F, ω, Lr (µ)) be the ω-covering number of F w.r.t. Lr -
norm, i.e., ↘f ↘Lr (µ) := X |f (x)|r dµ(x) where µ is a finite non-negative measure on X . Show that for any
r

1 ↓ r ↓ q ↓ ≃,
N (F, µ1/r (X )ω, Lr (µ)) ↓ N (F, µ1/q (X )ω, Lq (µ)).
This means for any probability measure µ,

N (F, ω, Lr (µ)) ↓ N (F, ω, Lq (µ)).

(b) Let $ % &

%
F = fε : Rd → R % |fε (x) ↑ fϑ (x)| ↓ g(x)ε(ϑ, ϖ) : ϑ ⇐ A ,

where A is a metric space endowed with metric ε. Show that

N (F, ↘g↘Lp (Rd ) ω, Lp (Rd )) ↓ N (A, ω, ε).

(Discussion: F consists of functions parametrized by ϑ such that these functions are Lipschitz w.r.t. ϑ
with ϑ taking values in a metric space (A, ε). The result shows that the covering number of F is controlled
by the covering number of A.)

(c) Exploring the idea in (b), obtain an estimate on N (F, ω, ↘ · ↘↓ ) for

$ 2
&
F = fϖ (x) = e↑ϖ↔x↔ , x ⇐ [0, 1]d : ϱ ⇐ (0, a] .

1
(Hint: You can use the inequality |ey ↑ 1| ↓ |y|e|y| , y ⇐ R. If you use it, prove it!! )

d
Question 3: (Symmetrization) Let X, X → ⇒ P. Show that f (X) ↑ f (X → ) = ω(f (X) ↑ f (X → )) where
ω is a Rademacher r.v. and f is any real-valued function.

Question 4: (Rademacher average) (a) Let X1 , . . . , Xn be X -valued independent random variables

drawn from P and F be a class of real-valued functions on X . Define F (x) := supf ↗F |f (x)| and ↘F ↘↓ :=
supx↗X |F (x). Let X := (X1 , . . . , Xn ) and ω := (ω1 , . . . , ωn ) where ωi ’s are Rademacher random variables
that are independent of X. Prove that for any ϑ > 0, with probability at least 1 ↑ e↑ε over the choice of
X, % n % % n % (
%1 ' % %1 ' % 2ϑ ↘F ↘2↓
% % % %
E sup % ωi f (Xi )% ↓ Eω|X sup % ωi f (Xi )% +
f ↗F % n i=1
% f ↗F % n i=1
% n
and % n % % n % (
%1 ' % %1 ' % 2ϑ ↘F ↘2↓
% % % %
Eω|X sup % ωi f (Xi )% ↓ E sup % ωi f (Xi )% + .
f ↗F % n i=1 % f ↗F % n i=1 % n
(b) Show that
) ( *
log 2 supX1 ,...,Xn N (F, ω, Lq (Pn ))
Rn (F) ↓ inf ω + ↘F ↘↓
ϱ>0 2n
and ) ( *
log 2E[N (F, ω, Lq (Pn ))]
E[Rn (F)] ↓ inf ω + ↘F ↘↓
ϱ>0 2n
+ ,n -1/q
for any q > 1 where ↘f ↑ g↘Lq (Pn ) := n1 i=1 |f (Xi ) ↑ g(Xi )|q . (Hint: Finish the covering number
argument for Rademacher averages that we did in the class. For the second inequality, just apply expecta-
tions on both sides of the inequality that I gave in the class before taking the infimum, and argue through
Jensen’s inequality and then take the infimum.)

(c) Show that % n %

%' % ⇑
% %
Eω % ωi % ↓ n.
% %
i=1

(Hint: Use Jensen’s inequality)

(d) Show that .

% n %
%1 ' % ς//' n
% %
Rn (A) := Eω sup % ωi ⇓a, bi ⇔2 % ↓  ↘bi ↘22 ,
a↗A % n i=1 % n
i=1

where A := {a ⇐ Rd : ↘a↘2 ↓ ς} and a := (a1 , . . . , ad ). This means, if all bi ’s are bounded in 2-norm,
Rn (A) behaves as n↑1/2 .
(Discussion: In general, Rademacher averages are di”cult to compute and we saw some sophisticated
techniques to handle this quantity. However, without requiring any such techniques, it can be shown that
Rn (A) behaves as above. The key is that the coe”cients of ωi are of the inner product form and A is a
2-norm ball in a Euclidean space. This result is in fact more generally valid for A being a Hilbert space.)
(Hint: Use Cauchy-Schwartz and the idea in (c))

(e) Using (d), show that if h is uniformly bounded, then

↘h↘↓
Rn (F + h) ↓ Rn (F) + ⇑ ,
n
where F + h := {f + h : f ⇐ F}.

2
#) :

ETg(x)/ +
iss] =
E(E(gix)(Y]/ (Y) +

E[g(x))T(y)] E(Eig(x)(T 1x)](Y) =

so
Elvi/Xe ,
....
Xive]
=

EYE(gix1 ....,
xn)(x2 .
- -

xi] Elg(Xa -

,
- - -

-
Xn)(Xa . . Xi -
-])xz ,
.
- -

, xi - 2)
=
Elgixe .. ---

xn))xz .
. . .
.
xi c) E(g(x z
-

,
. . . ,
xn))xz ,
- -

-, Xi -a)
= 0 .

(b) Let Li =

i Vix ,
...,
Xi)

Ui
=
Vi Xe Xi
Sup
...,
,

Obviously L :
= V: =
Ui

Mi-Vi =

suyVi
-

int Vi
=Sup /Vi(X
..., Xi) -

Vis(X ... Xi s

- Sup(ETq(X ..., xn)(X -

Xi] -

Ex
= Sup /Elgix ...., Xi ,
Xi =
Xo
,
Xi - XpX ...., Xi !
Elgixe Xive Xi Xt Xite
-Xu )(X2 Xia)
-
= -

,
..., ,
, . : >

Jensensup/gx-Xi ,
Xi =
Xi XieXe)-gXXie XiX , , XitXX x ..

=sup(X .
= Ci
(2) E(V /Xe : . ..., Xie) = 0
.
Li = Vi =
Ui

then Elex/Xc ,
--- Xie) -Lis = e
ex(g(X2 xn) Eg(x ....,
Xn)) EleV)
.... -

El
,

(d) =

* V:
Exe Exalte (e / Xa
Xne)
:"
= ,
..... Xan , .... Xare
.

=
Exa ..... xoe(e ExalXe-xme(ex/X2 ,
. .
.

,
Xa-a)
X-s)e
Exc
S
=>
.....

=
exer
i
Exc ...., Xa Exore(X ..... xe(eV(X2 , ...,
Xaw)
=.
= e
(e) ↑"19(X2 ,
...,
Xn)
-

Eg(X ,
:"

, Xn) = 8)
x (g(x2 ... Xn) Eg(X2. ---,
Xn)) *

)
-

Ple - e (1-0)
(g(x2 Xn) Eg(X2
Xn))
. . .
↑
-
-

e-XE(e
. ,
. ,

-
I = eC
-
29

Similarly ,
P"(-g(X2 ,
-

> Xn)
-

fEq(X ...., Xalk-s =

sop" (19(X ,
....
xn) -

Egixe ...., Xn)(78)

P(g(X xe) Eq(Xx Xn) 9) + pol Xn) Xn)( = a)
=
g(Xa , 1 Eg(x2
-

.,
-

,
-
.,
. - -

...,
. -
.
. .

=> 2 e-
Q2 :

(a) It suffices to show :

every m
*
#)-cover
of F w .
r .
t .

(M) is

also
a
+
IX)8-cover of F wor .

L"(M)
*
↓ f-F ,
suppose If is the
representative off in
mess of of wort. .
(
(M)
* * *
then
((x1f =

g1 dMixs) =
m (4)9 .

Let x = F B,
B =
E ,
* +
+
= 1 ,
a ,
> 1

*
Let hixs /fixs-gfix) kx 2 Alla 1SxH-8/duxs)
= ·
=
,
=

Using Holder inequality, )(hx > kx)/dnxs KalallkIp =

duxs) Mix
+
so .
Self-e +Mix =
1) x
(f -

g+1 =
Mix)9v
+ =
S If-8 + /dumxs ( (x)E
=
m
Thus ,
197 f-F) :
forms a
+
IX)8-cover
of E w .
r .
t .

L.
(b)
Suppose B is a S-cover
ofA wort. .

P.
Thus FfzeF ,
EnEB ,
st .

P(2 9) eq , .

*
1) fe-tellecres =

(x Item-ty) (dmix))
=
((x19()P12 n)("duxs) .

=
((x(g(x)/PqPdmix))
=

1181/IR) 9 .

Sty : [B] from a

118//p 2 -

cover
of F W . r . .
t

(PIRA)
*

↓ IF .

11/LCRA , 8 ,
LPR 1) = N (A ,
2 ,

9)

gig) ye" 22
12) for y 20 let + 1
= -

g'(y) yet non-decreasing function

in
=
zo , gly) is a
.
y

gly) = 810) = .
0

so yes = et-1 .

Similarly we can show that-ye"-c-ea

So let-1) = 1y1e .
FyEI
=

((62 62)

/e- - e-GX
- -

62)/1X/
S

= 11x11ea1x11 p(62
-

.
62)
Let g(x) =
1x1Ream 1191lo = dead

From1D1 ,
we can have :

↓(F . deads , 11 .

10) < N((0 ,

ad ,
a ,
P) =
[*] + &

so N (F ,
9 , 11 /1)
-

>
-

Fed +
#f At ER
:
-

↑ (c) fix)
-

f(x)) =
t) P(s(f(x) f(x))
= -
= +, g =
m) +

↑ (a( f(x) -

f(x')) = t
, a =

2)

=
P(fix) -

f(x) = t ,
a =
1) +
P(f(x) -

f(x) =
-
t , g =
1)
=

P(fix) f(x) -
=
+) p(8 1) = +
P(fix) -

f(x)2 -

t)P18 -1) =

= P(fix1-f(x) =
+) + p(f(x)
-

f(x)) = =

+)
=
Ep(f(x) -

f(x'( = +) + & P(f(x) -

f(x) -
+ )

=
PIfix) -

f(x) =
+)
&
Thus ,
a (f(x)-f(x') f(x) f(x)
-
 Let Rn(F) =
Es Surfixis
RnIF)
Esp If
=> =

/RnIF) (Xa ,
. . .

,
Xive ,
Xi ,
Xith ,
-.., Xn)-RnIF) (Xa ,
"
,
Xive ,
Xi Xite
,
, ---Xn)
=
lEza (guf(x) -Sup
*

Elutixis-
=>

Esup Iii) - -
Easil fix) f
= -

=>
EXp(f(x) -

fixi
=
En (Sup(fixis +supfxls
= IF11s

McDiarmid
By inequality , 24

↓ x > o
,
PlRaIF)-EReIF(a) enElFo = ec
Let e = en = x =

F
# 20 ,
w .

p . at least -e , Rolf) = ERIF) +

Ef
Similarly ,
we can show PC-RnIF1-El-RulF)]> * ).

So
Es f(x) Ef(xis) +
JF2
(b) RnIF) =
Es1XsupIfx
=

EXSup Ii(fix)
-

Ef(x)) + gxs

EXSui(f(x)
-

Gill+E supx E-cover of

↑ went 11 -

119(Pr)

EaSupifix:)
-

Ef(xi)) + Rela-core of F wrtlps

②

supIi(f(x) If(x))) dersulp-gla

-

n lt-gfl a
=
sup
-su(H
-

g)(xis()
=
sup IIf -

If 12 (Pm)
fEF

E
=

We know Rol = glogz for finite class by

/logaSUCF
E
Rals-cover of F w o r .
t .

1 .

/Ap)) =
/Fla ·
,
S L
, 1)
2n

11F//log2NIF LELPul)
So we can get
:
RnIF) = 2 + .
C ,

2n

So Rn(F) <inf (8 +
llJlogIF L)))inf (atoJgPNFaEl 2n
,

By EJlogINVIF L Pal) J logzEINF LP

Jensen ,
,

2n

then .
ERn(F) > -
a +
E(IFIlo/log2NIF, LELP) (
1Fo/logzEINIF EPTI
>
-
2 + , c ,

2n

ERIF)-inf(8 IflogzEN E
So +
1
(Ell = Ea(1 1) :

*
Let Xo Xa . .., Xn d Bernoullike) G: 2X : -1
.
, , .

& Xi v Bin(n , El
i I
=

: Xin

Ec (vi) = 0

E (()") =
Vara (i) =
Vary (2Xi -

n) = n .

(i) n
, Easil =
Jn .

(d) It i ,
b :
>) bi/
-
/
5su H l
Rn(A) =

Easu ii

(Ec(i)1bi1)" =
Ea)(2 /11 :
bil ()
=
Es (11 bi +
Ea : /Thill) Bill (
= 11 : 1
+ / bill E(d : ) E(81)

= I billy

So RolA) =J bill
(e) Let F(x) Jif(xe) fixus) :

feFY
.
.
·
.
=
,

R IF + h) =

Eup(f(x) xi +

EIA)Su fixx
-

=
Rn(F) +
Eaa) hiXi))
Let A =
1) , bi =
h(Xi)

From Id 1 we can have :

Ex A /- xi)) =

Esup