Understanding Machine Learning: From Theory to Algorithms

418 PAC-Bayes

2.• Suppose thatHis a finite hypothesis class, set the prior to be uniform over

H, and set the posterior to beQ(hS) = 1 for somehSandQ(h) = 0 for

all otherh∈H. Show that

LD(hS)≤LS(h) +

√

ln(|H|) + ln(m/δ)

2(m−1)

.

Compare to the bounds we derived using uniform convergence.

• Derive a bound similar to the Occam bound given in Chapter 7 using the
  PAC-Bayes bound