A simpler proof of McAllester’s PAC-Bayes result

For conceptual convenience, Let’s just talk about the “unrealizable case”. In other words, the “bad event” for a concept is the event that its empirical error is far from its true error. Specifically, let’s define:

• err(c) is the true error of c, and êrr(c) is the empirical error of c.

• badness(c) = |err(c) − êrr(c)|.

• “c is ϵ-bad” if badness(c) > ϵ.

• ε(δ, m) = \sqrt{\frac{ln(2/δ)}{2m}}.

I will begin with a weaker version of McAllester’s Theorem 2, which is easy to prove and I found to be very helpful in thinking conceptually about it. McAllester then uses a cool trick to get his stronger result. I will give a much uglier but conceptually easier way to do that part.

Theorem 1 For any measure P over concepts, for any δ > 0, for any p > 0, with probability 1 − δ over the selection of an IID sample S of m instances, all measurable sets U with P (U) = p satisfy

E_{c∈U}[badness(c)] < \sqrt{\frac{ln(1/p) + ln(2/δ) + ln(m)}{2m}} + \frac{1}{m}

Proof. Fix some concept c and some δ′. Hoeffding’s bound tells us Pr_{S}[c is ε(δ′, m)-bad] < δ′. Since this is true for any given c, it is certainly true for any fixed distribution over c’s. Specifically, define the random variable B_{δ′} to be the weight (under P) of concepts c that are ε(δ′, m)-bad. Then, E_{S}[B_{δ′}] < δ′.

Markov’s inequality therefore says that for any given δ, Pr_{S}[B_{δ′} > δ′/δ] < δ. In other words, we expect only a δ′-measure of concepts to be ε(δ′, m)-bad, and it is unlikely we will see a huge amount more than that.

Good. So, now all we need to do is set δ′ = δp/m. I.e., in words, the probability (over S) that the weight of ε(δp/m, m)-bad concepts is greater than p/m is at most δ. This means that with probability 1 − δ, all sets U of measure p behave well. Formally, with probability 1 − δ, for any set U with measure p, at most a measure δp/m subset of U consists of ε(δp/m, m)-bad concepts. Therefore,

E_{c∈U}[badness(c)] ≤ 1/m + [1 − 1/m] · ε(δp/m, m)

and we are done.

The above theorem is weaker than McAllester’s because it requires us to commit to the measure of U in advance. What we really want is a theorem that allows us to pick p after the sample is drawn. The essence of the difficulty is that we are examining a 0-1 random variable “is c bad or not”. McAllester uses a neat trick of defining a smoother random variable f_{c} = 2e^{−2badness(c)^{2}m} with the property that Pr_{S}[f_{c} < δ] < δ, and working directly with that.

However, here is an uglier thing we can do. We can make the above theorem hold simultaneously for the m values of p in {1, 1/2, 1/4, …, 1/2^{m}} by just replacing “δ” with “δ/m” in the bound (equivalently, this puts a factor of 2 in front of the “ln m” term). Now I claim that we can make it hold simultaneously for all values of p with the cost of replacing the ln(1/p) term with ln(2/p). In particular, if U has P (U) < 1/2^{m} then the theorem is vacuous so we don’t care. On the other hand, if 1/2^{i} < P (U) < 1/2^{i−1} then just apply the theorem to the set U′ ⊂ U consisting of the measure-(1/2^{i}) worst concepts in U (or actually any set U′ of measure 1/2^{i} such that E_{c∈U′}[badness(c)] ≥ E_{c∈U}[badness(c)].