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<t$ 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<t$ 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$. ∎
