Does majority-vote boost weak learners to strong learners?

A learner is a function mapping finite vectors with elements in $$X\times\{0, 1\}$$ onto binary functions on $$X$$. Given a set $$H$$ of binary functions on $$X$$, we say that:

1. A learner $$(\delta, \epsilon)$$-weakly learns $$H$$ if there exists an $$n$$ such that no matter the probability distribution on $$X$$ or the true function $$h\in H$$, when given $$n$$ datapoints, the algorithm outputs a hypothesis within $$\epsilon$$ of $$h$$ with probability at least $$1-\delta$$. Here "within $$\epsilon$$ of $$h$$" is understood in the sense of zero-one loss (probability of differing on a random input).

2. A learner strongly learns $$H$$ if for any $$\delta > 0, \epsilon > 0$$ it weakly learns $$H$$.

Whether we can take a weak learner and "boost" it to a strong learner is a classic problem. One obvious way of trying to do so is to use majority vote: run the weak learner $$m$$ times on $$m$$ independent batches of $$n$$ datapoints, and predict $$h(x)$$ to be the majority prediction of all the different hypotheses you got. Does majority vote boost weak learners to strong ones?

On page 5 of Kearns 1988, a classic paper cited by the paper that introduced boosting (Schapire 1990), Kearns gives a counterexample involving learning boolean monomials. However, Kearns is working in a different, oracle-based formalism in which a learner calls an oracle to get data and chooses how much data it wants, rather than being given $$n$$ datapoints. It seems to me Kearns' counterexample fails only because the weak learner he considers is specifically designed to "give up too early" and stop looking for more data. Indeed, Kearns' weak learner is actually a strong learner in our formalism.

In the formalism described above, is there a sufficiently small $$(\delta, \epsilon)$$ such that any $$(\delta, \epsilon)$$-weak learner is boosted to a strong learner by majority vote?

No, majority boosting does not boost weak learners in the "fixed sample size" formalism. There are arbitrarily strong weak learners which fail to be boosted to strong learners by the majority method.

Briefly, the counter-example is:

• Consider the hypothesis class $$H$$ of "threshold" binary functions on $$[0, 1]$$, that is, functions for which there exists a $$t$$ such that $$f(x)=0$$ for $$x and $$1$$ otherwise. For clarity, I will describe a value of $$1$$ as "black" and a value of $$0$$ as "white".
• Define the algorithm $$W_k$$ to take $$k$$ points and return a hypothesis according to the following rules. If all the points are black, the algorithm returns the constant black function and similarly if all points are white. Otherwise, the algorithm takes the largest white point and the smallest black point, and returns the function with threshold their midpoint. If given more than $$k$$ points, $$W_k$$ ignores all but the first $$k$$ and if given fewer, it returns some dummy hypothesis.

For all $$k$$, $$W_k$$ is a weak learner, and in the sense defined in the question, for any $$\delta > 0, \epsilon > 0$$, there is some $$k$$ such that $$W_k$$ is a $$(\delta, \epsilon)$$-weak learner. However, majority vote fails to boost any one of them to a strong learner.

Proposition. For any $$k$$, $$W_k$$ is not boosted by majority voting.

Proof. We must find an $$\epsilon$$ such that majority voting cannot make the probability of greater than $$\epsilon$$ loss go to zero. That is, we must find a $$\delta$$ such that for any $$n$$ we must find a learning problem such that the probability of greater than $$\epsilon$$ loss for that problem, with $$n$$ datapoints, is at least $$\delta$$.

Therefore, fix $$k$$. Let $$\epsilon$$ be small enough that $$(1-\epsilon)^k>0.9$$ . Consider a learning problem which lands in the black region with probability $$1-\epsilon$$, and in the white region with probability $$\epsilon$$. When we run $$W_k$$ on this problem, we have probability $$(1-\epsilon)^k>0.9$$ of getting only black points and therefore returning the black function, which will have loss $$\epsilon$$.

Now suppose we apply the majority method to $$W_k$$ on $$n$$ batches, for the above learning problem. For each of the $$n$$ independent runs of $$W_k$$, we have probability $$(1-\epsilon)^k$$ of getting the all-black hypothesis. What is the probability of the majority of hypotheses being black? It's at least equal to $$P(B_n > \frac n2)$$, where $$B_n\sim \mathcal B(n, (1-\epsilon)^k)$$. No matter how high $$n$$ gets, this will always be at least fifty percent. Therefore, for this learning problem, for any $$n$$, the probability of a loss of $$\epsilon$$ or greater is at least $$0.5$$. ∎

Proof that $$W_k$$ is a weak learner. In fact we can show that $$W$$, the algorithm which consists in running $$W_k$$ when given $$k$$ datapoints, is a strong learner. This is a general method of constructing weak learners: take a strong learner and ignore all but the first $$k$$ datapoints for some $$k$$.

Fix a given loss $$\epsilon$$. Fix a given true function and distribution on $$[0, 1]$$. We will estimate the probability of our algorithm returning a loss at most $$\epsilon$$ when it has $$n$$ datapoints. We must show this probability converges to $$1$$ as $$n\to\infty$$.

Let $$t$$ be the threshold. We will construct an interval $$[a, b]$$, with $$a and $$b\geq t$$ (note carefully the strict and unstrict inequalities) having the following properties, where $$P$$ is the input distribution: $$P((a, b)) < \epsilon \\ p=P([a, t)) > 0 \\ q=P([t, b]) > 0 \tag{1}$$ Again, exactly which intervals are open and half-open is important, a necessary technical wrinkle to account for the possibility that $$t$$ might be a point mass. To construct this interval, we will begin by constructing $$a$$. We can find an $$a$$ such that $$[a, t)$$ is arbitrarily small by continuity of probability. Therefore there is at least one $$a$$ such that $$P((a, t))<\frac\epsilon 3$$. Let $$a$$ be the infinimum of all such values. Again by continuity we have $$P((a, t))<\frac\epsilon 2$$, and invoking continuity one final time, if $$P([a, t))$$ were $$0$$, $$a$$ would not be the infinimum. This establishes: $$P((a, t))<\frac\epsilon 2, P([a, t))>0$$ Now, if $$t$$ is a point mass, setting $$b=t$$ satisfies $$(1)$$. Otherwise, we can repeat exactly the same argument as above to find $$b>0$$ such that $$P([t, b])>0$$ and $$P([t, b))=P((t, b))<\frac \epsilon 2$$. Such a $$b$$ will satisfy $$(1)$$.

With the interval $$[a, b]$$ constructed, the argument is straight-forward. When at least one sample falls in $$[a, t)$$ and at least one sample falls in $$[t, b]$$, their midpoint must fall in $$(a, b)$$. When the midpoint is in $$(a, b)$$, the set of points misclassified by the hypothesis is a subset of $$(a, b)$$, and since $$P((a, b))<\epsilon$$ this implies the loss is also strictly less than $$\epsilon$$. The probability of this occurring is (recalling the definitions of $$p$$ and $$q$$ from $$(1)$$): $$1 - (1 - p - q)^n$$ and this value goes to zero as $$n\to\infty$$. ∎