Optimal Weak to Strong Learning
Authors: Kasper Green Larsen
Martin Ritzert
Venue: NeurIPS 2022 Accept (2022)
Keywords: boosting
weak learning
sample complexity
lower bound

Abstract: The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We present a new algorithm that constructs a strong learner from a weak learner, but uses less training data than AdaBoost and all other weak to strong learners to achieve the same generalization bounds. A sample complexity lower bound shows that our new algorithm uses the minimum possible amount of training data and is thus optimal. Hence, this work settles the sample complexity of the classic problem of constructing a strong learner from a weak learner.

Optimal Weak to Strong Learning
Kasper Green Larsen Department of Computer Science Aarhus University Aarhus, Denmark larsenθcs. au. dk
Martin Ritzert
Department Computer Science Aarhus University
Aarhus, Denmark ri ritzertëcs au. da.dk
Abstract
The classic algorithm AdaBoost allows to convert weak learner, that is an al- gorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We present a new algorithm that constructs a strong learner from weak learner but uses less training data than AdaBoost and all other weak to strong learners achieve the same generalization bounds. A sample complexity lower bound shows that our new algorithm uses the minimum possible amount of training data and is thus optimal. Hence, this work settles the sample complexity the classic problem of constructing strong learner from weak learner.
Introduction
The field of boosting has been started from a classic question in learning theory asking whether classifiers that are just slightly better than random guessing can be used to create classifier with arbitrarily high accuracy when given enough training data. This question was initially asked by Kearns and Valiant [15 [6] and ignited the line of research that eventually lead to the development of AdaBoost 77 the prototype boosting algorithm to date. AdaBoost carefully combines the predictions of several inaccurate classifiers trained with focus on different parts of the training data to come up with voting classifier that performs well everywhere.
We quantify the performance an inaccurate learner by its advantage y over random guessing. Said loosely, a y-weak learner will correctly classify new data points with probability at least 1 1/2 12 In contrast, given 0 E, 1 and enough training data strong learner outputs with probability 1 1 over the choice of the training data and possible random choices of the algorithm a hypothesis that correctly classifies new data points with probability least 8. The number of samples m(e, 6) such that the learning algorithm achieves the desired accuracy and confidence levels is called the sample complexity. The sample complexity is the key metric for the performance of strong learner and depends on the weak learner's 's advantage y, the weak learner's 's flexibility measured in terms of the VC-dimension, as well as & and Essentially, a construction with low sample complexity makes the most out of the available training data.
AdaBoost 7 is the classic algorithm for constructing strong learner from y-weak learner. If the weak learner outputs hypothesis from base set of hypotheses H, then AdaBoost constructs strong learner by taking weighted majority vote among several hypotheses hj..... .., from H. Each of these hypotheses is obtained by invoking the y-eka learning algorithm on differently weighted versions of set of training samples The number of samples required by AdaBoost for strong learning depends both on the advantage of the weak learner and the complexity of the hypothesis set H. If we let d denote the VC-dimension of H, i.e. the cardinality of the largest set data points .d. such that every classification of x1.....dd can be realized by hypothesis h e H, then it
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is known that AdaBoost is a strong learner, which for error and failure probability 6, requires
ddIn(I(<y)) In(d/(e)) Ey²
In In(1/6)
8
samples. This sample complexity state-of- of-the-ar for producing strong learner from a y-weak learner. However, is this the best possible sample complexity? This is the main question we ask and answer this work.
First, we present a new algorithm for constructing a strong learner from a weak learner and prove that it requires only
o d In 1/0)
BY
samples. In addition to improving over AdaBoost by two logarithmic factors, we complement our new algorithm by a lower bound, showing that any algorithm for converting y-weak learner to strong learner requires
d In(1/0) EY²
Ω
samples. Combining these two results, we have tight bound on the sample complexity of weak to strong learning. In the remainder of the section, we give more formal introduction to weak and strong learning as well as present our main results and survey previous work.
1.1 Weak and strong learning
Consider binary classification task in which there is unknown concept X (-1,1) assigning labels to ground set X. The goal is to learn or approximate c to high accuracy. Formally, we assume that there an unknown but fixed data distribution 2 over X. learning algorithm then receives set S i.i.d. samples xI..... Xm from D together with their labels c(x)).... , c(x)) and produces hypothesis with h based on and the labels. To measure how well Ι approximates c, is assumed that new data point is drawn from the same unknown distribution D. and the goal is to minimize the probability mispredicting the label of We say that learning algorithm a weak learner if it satisfies the following:
Definition 1. Let X - 1-1, be set of concepts and A a learning algoritium. We say that A y-weak learner for C, if there is constant ó6 < and an integer mo E IN, such that for every distribution D over X and every concept e E C, when given from together with their labels c(x1)...., ..(,),,..,c((m)))) it holds with probability least do over the sample S and the randomness of A, that A outputs hypothesis h X 1-1, such that
i.i.d. samples $ = .1..... Xmo
Lo(h)
Pr [h(x) # c(x)] 1/2-y. x-D
y-weak learner thus achieves an advantage of y over random guessing when given mo samples. Note that A knows neither the distribution D, nor the concrete concept C but achieves the advantage for all and c. We remark that in several textbooks (e-g. Mohri al. (18) a weak learner needs work for any arbitrary 5 O while Definition onnly requires the existence of some 6g. Thus, every weak learner satisfying the definition Mohri et al. also satisfies Definition making our results more general.
In contrast to a weak learner, a strong learner can obtain arbitrarily high accuracy:
Definition Let C X {-1, 1} be a set of concepts and A learning algorithm. We say that A is strong learner for C, if for all 0 < ε, < 1, there is some number m m(6 5) such that for every distribution D over X and every concept e C. when given
m(E, 5) i..dd samples S = from D logether with their labels c(x1)..... c(x)), , it holds with probubility at least 1 over the sample S and the randomness of A, that A outputs hypothesis h X - (-1,1)
such that
(h(h)
Pr [M(x) # c(x)] E. x-D

---

The definition of strong learner is essentially identical to the classic notion of (e, 6)-PAC learning in the realizable setting. Unlike the y-weak learner, we here require the learner to output classifier with arbitrarily high accuracy (& small) and confidence (8 small) when given enough samples S.
Kearns and Valiant 15 16 asked whether one can always obtain a strong learner when given access only to a y-weak learner for a y > O. This was answered affirmatively by Schapire [21]] and is the motivation behind the design of AdaBoost 77]. If we let denote the set of hypotheses that y-weak learner may output from, then AdaBoost returns a voting classifier f(x) = sign -i= arhh; (x)) where each h1 E H the output of the y-weak learner when trained on some carefully weighted version of the training set S and each is realevalued weight. In terms of sample complexity m(e, 6), the number of samples stated in Eg. (Dis sufficient for AdaBoost. There are several ways prove this. For instance, it can be argued that when given m samples, AdaBoost combines only = Oy In) hypotheses hi...... h, from H in order to produce an f that perfectly classifies all the training data S, i.e. f(x,) c(x;) for all x; S. Using that the class He can generate at most O 0((2)) ) distinet classifications of points (i.e. its growth function is bounded by this), one can intuitively invoke classic generalization bounds for PAC-learning the realizable case to conclude that the hypothesis satisfies
In(1/5) LD(f) S 0 Id ln(m/d) + In((//6 = oo ( In(m/d) In ( p
(2)
y2m
m
m
with probability least 1 8 over S (and potentially the randomness of the weak learner). Using [f) = & and solving Eq. (2) mn gives the sample complexity stated in [Bq. (1) This is the best sample complexity bound of any weak to strong learner prior to this work.
Our main upper bound result is new algorithm with better sample complexity than AdaBoost and other weak to strong learners. It guarantees the following:
Theorem 1. Assume we are given access to y-weak learner for some 0 < < 1/2, using a base hypothesis set H S X - (-1, I} of VC-dimension d. Then there is a universal constant a > 0 and an algorithm A, such that A is a strong learner with sample complexity m(e, 8) satisfying
Idy
In(1//) E
m(s,))
We remark that it is often required that strong learner runs in polynomial time given a polynomial- time weak learner. This is indeed the case for our new algorithm.
Next, we complement our algorithm from Theorem by the following lower bound:
Theorem 2. There is a universal constant a > such that for all integers E N and every 2dd < y < 1/80, there is a finite set X. a concept class C c X - {-1.1} and a hypothesis set H C X - 1-
} of VC-dimension at most d. such that for every (E. with O < E < and 0 6 5 < 1/3, there is a distribution D over X such that the following holds:
1. For every c C and every distribution D' over X, there is an h E H with Prx-zy [h(x) # c(x)] S 1/2-7. - y,
2. For any algorithm A, there is a concept C E C such that A requires at least
dy 2 In(1/0)
m 2 a
6
samples S and labels c(S) to guarantee (D(hs)= s with probability at least 1 - - over S, where hy is the hypothesis produced by A on S and c(S).
The first statement of Thcorem says that the concept class C can be y-weakly Iearned. The second point then states that any learner requires many samples as new algorithm. Moreover, the lower bound does not require the algorithm to even use a y-weak learner, nor does it need to run in polynomial time for the lower bound to apply. Furthermore, the algorithm is even allowed to use the full knowledge of the set C and the distribution D. The only thing it does not know is which concept E C provides the labels c(S) to the training samples. The lower bound thus matches our upper bound except possibly for very small y < 2- We comment further on this case in Section 5
In the next section, we present the overall ideas in our new algorithm, well as a new generalization bound for voting classifiers that is key to our algorithm. Finally, we sketch the main ideas in the lower bound. Due to the space requirements, several proofs have been moved to the supplementary material.
3

---

1.2 Main ideas and voting classifiers
One of the key building blocks in our new algorithm voting classifiers. To formally introduce voting classifiers, define from a hypothesis set H S X - {-1, the set of all convex combinations A(H) of hypotheses in H. That is, A(H) contains all functions f of the form f(x) = Σi (x)1(x) with 0; > 0 and Σ; 0i = 1. AdaBoost can be thought of as producing voting classifier g(x) sign(f(x)) for an f E A(H) by appropriate normalization of the weights uses.
Classic work on understanding the surprisingly high accuracy of AdaBoost introduced the notion of margins [2]. For a function f E AHH), and a sample x with label y, the margin of f on yx (x) Notice that the margin is positive if and only if (x)) correctly predicts the label of x. It was empirically observed that AdaBoost produces voting classifiers g(x) sign(f(x)) where has large margins. This inspired multiple generalization bounds based on the margins of voting classifier. considering both the minimum and the k-th margin [2
y) is
19 20 [7]. The simplest
bound when all margins are assumed to be at least y, is Breiman's 's min margin bound:
Theorem 3 (Breiman A. Let c E
{-1, be an unknown concept, H E x (-1,1)
hypothesis set of VC-dimension d and D an arbitrary distribution over X. With probability at least
1 over a sei of m samples S D"n, holds for every voting classifier gxx) = si))( with
f A(H) satisfying (x) 2 y on all e S, that:
(g)()) = d ddIn(m/ d) In
y²m
The resemblance to the generalization performance of AdaBoost in Eq. (2) is no coincidence. Indeed, a small twist to AdaBoost, presented in the AdaBoost,, algorithm [20]. ensures that the voting classifier produced by AdaBoost, from y-weak learner has all margins at least y/2. This gives an alternative way of obtaining the previous best sample complexity in Eg.. (1) We remark that more refined generalization bounds based on margins exist, such the k-th margin bound by Gao and Zhou [8] which is known to be near-tight
[10]. These bounds take the whole sequence of margins
cxx) fx;) of all samples X, E S into account, not only the smallest. However, none of these bounds leads to better generalization from a y-weak learner.
We note that the notion of margins has not only been considered in the context of boosting algorithms but also plays a key role in understanding the generalization performance of Support Vector Machines, e.g. the recent works [14 [1] giving tight SVM generalization bounds in terms of margins.
In our new algorithm, we make use of voting classifier with good margins as a subroutine. Concretely, we invoke AdaBoost,, to obtain margins of at least y/2 on all training samples. At first sight, this seems to incur logarithmic losses, at least if the analysis by Breiman is tight. Morcover, Grønlund et al. [9] proved generalization lower bound showing that there voting classifiers with margins on all training samples, but where at least one of the logarithmic factors in the generalization bound must occur. To circumvent this, we first notice that the lower bound only applies when is sufficiently larger than dy We carefully exploit this loophole and prove a new generalization bound for voting classifiers:
Theorem 4. Letc + 1) be an unknown concept, H S - (-1, a hypothesis set of VC-dimension d and D arbitrary distribution over X. There is a universal constant O, such that with probability at least 1 1-8 5 over a set of m 2 a(dy-2 2 + In(1/5) samples S ~ D'm, every voting classifier g(x) signn (fx)) with f E ((H) satisfying cxx) 2 y on all x S achieves
Lo(g) S 200
The value 1/200 is arbitrary and chosen to match the requirements in the proof of Theorem Notice how new generalization bound avoids the logarithmic factors when aiming merely at generalization error 1/200. Breiman's 's bound would only guarantee that d 1n-2In(1)))) In(1/y) In(d/y) samples suffice for such a generalization error. While the focus of previous work generalization bounds was not on the constant error case, we remark that any obvious approaches to modify the previous proofs could perhaps remove the In m factor but not the In(m/d) factor. The In(m/ dd factor turns into (In(1/))) when solving for m in d in(m/dd dy² = 1/200 and is insufficient for our purpose.
With the new generalization bound on hand, we can now construct our algorithm for producing a strong learner from a y-weak learner. Here we use template the sample optimal algorithm by

---

Hanneke [3 for PAC learning in the realizable case (which improved over a previous near- pear- result by Simon (22)) Given training set S, his algorithm carefully constructs number of sub-samples S2........ Sk of S and trains a hypothesis h; on each S; using empirical risk minimization. As the final classifier, he returns the voter g(x) sign((1/R) Σ/= (xx()))
For our new algorithm, use Hanneke's 's approach to construct sub-samples St...., Sy of a training set S. We then run AdaBoost, on each S; to produce a voting classifier gi(x) = sign(fi(x) for an Si E A(H) with margins 7/2 on all samples in Sz. We finally return the voter h(x) sign((1/k) Σ (x())). Our algorithm thus returns majority of majorities.
To prove that our algorithm achieves the desired sample complexity m (e, 6) claimed in Theorem we then revisit Hanneke's ' proof and show that it suffices for his argument that the base learning algorithm (in his case empirical risk minimization, in our case AdaBoost,, achieves an error of at most 1/200 when given samples. If this is the case, then his proof can be modified to show that the final error of the output voter drops to (T/m). Plugging in the r = a + In(1/5) from our new generalization bound in Theorem 4 completes the proof.
Let us remark that a lower bound by Grønlund et p shows the existence of a voting classifier with simultaneously large margins and a generalization error with an additional log-factor. It is thus conceivable that simple majority vote is not sufficient and a majority of majorities is indeed necessary, although the lower bound only guarantees the existence of a 'bad' voter with good margins and not that all such voters are 'bad'.
In the following, we start by proving our new generalization bound (Theormm 4) in Section 2 We then proceed in Section 3 to present our new algorithm and sketch the proof that gives the guarantees in Theorem Finally, in Section 4 we give the proof ideas of the lower bound in Theorem 2
2 New margin-based generalization bounds for voting classifiers
In this section, we prove the new generalization bound stated in Theorem 4] For ease of notation, write that D is distribution over X x 1-1, (and not just distribution over X) and implicitly assume that the label of each x E X is c(x) for the unknown concept c. Moreover, for a voting classifier gxx) fx))( with f e A(H), we simply refer to f as the voting classifier and just remark that one needs to take the sign to make a prediction. Finally, we think of the sample S as a set of pairs (xy, y;) with x E X and y; = c(x;) (1,
The key step in the proof of Theorem 4 is to analyze the generalization performance for a voting classifier obtained by combining randomly drawn hypotheses among the hypotheses h....., h, making up a voting classifier f = Σ, ar,h; from A(H). We then relate that to the generalization performance of itself. Formally, we define distribution f.x for every f and look at random hypothesis from D ftr- We start by defining this distribution.
Let f(x) Σn 0x,((x) E A(H) be voting classifier. Let Dy be the distribution over H (the base hypotheses used in f) where has probability a'h Consider drawing i.i.d. hypotheses hi..... hn from Dj and then throwing away each Hy independently with probability 1/2. Let r' be the number of remaining hypotheses, denote them ... hr, and let g = 1 Σ h4. One can think of g as a sub- sub-sampled version of f with replacement. Denote by D the distribution over g.
Key properties of Dy.r- In the following, we analyze how a random g from D behaves and show that while it behaves similar to f it produces with good probability predictions that are big in absolute value (even if (x) = O). The proofs of the following three lemmas are given the supplementary material. First, we note that predictions made by random g are often close to those made by ʃ and then observe that g rarely makes predictions g(x) that are small in absolute value.
Lemma 1. For any E X, any f E A(H), and any μ > O: Dy, (lf(x)) g((x) 2 #l] 5e H//132
Lemma 2. For any E X, any f E A(H), and any 1/r: Prg-D,, [lg(x)] S μ1] S 2μvF.
Lemma 2 states that even f(x) x 0 for an unseen sample x, g(x) will still be large with good probability. Thus we can think of g as having large margins (perhaps negative) also on unseen data. This is crucial for bounding the generalization error. The proof follows from an invocation of Erdös' improved Littlewood- Offoorr lemma (6].
5

---

As the last property, we look at the out out-of-sample and in-sample error of a random 8 and start with relating the generalization error of f that of random g. To formalize this, define for any distribution D, the loss L'D (f) == Pf(x.y)-D.g- Dzg- [)g(x) s 0] and when writing L/(() we implicitly assume S to also denote the uniform distribution over all (x, E S. We then have:
Lemma 3. For any distribution 2 over X x (-1, 1), any 2 36 and any voting classifier f E A(H) for hypothesis set 'H c X (-1,1), we have [f( s x3.5%) (f).
Moreover, if f has margins y on all training samples (x, E S, then is correct on most of S provided that we set big enough:
Lemma 4. Let S be set of m samples in X {-1,1) 1} and assume ff is a voting classifier with yf((x) 2 y for all (x. y) E S. For t 2 1024y we have (f) s 1/1200..
Proof. By Lemma I holds for all (x, E S. that If(x) - gx)] 2 y with probability at most 5 - < 5e 32 < 1/1200. Since (x y, this implies sign(g = sign(f(x)) y.
The last ingredient for the proof of Theorem 4 is to relate I'(S) and (f). For the proof we use Lemma 2 to infer that with good probability [g(x)] 2)(),, i.c has large absolute value. We use this to argue that sign(g) g) often belongs to a class with small VC-dimension and then apply a growth-function argument relate (f) and L'D (f). Formally, we prove the following lemma.
Let D be an arbitrary distribution over X x (-1,1) and let H c X - (-1,1) be hypothesis set of VC-dimension There is a universal constant a > 0 such that for any I E IN and any m atd, it holds that:
Lemma 5.
Pr S
sup
- 1200 s exp(-m/a).
FEA(H)
Before we prove Lemma 5) we show how to use it to prove Theorem 4 Since we are only aiming to
prove the generalization of voting classifiers f with (x) 2 for all samples (x. y) E S. Lemma 4 tells us that such f have small (f) when 2 1024y We thus fix 1024y and get that exp(-m/a) over the
(f) < 1/ 1200 from Lemma 4 By Lemma 5 with probability at least s 1/1200 and thus (f) I 1/600. Finally, Lemma gives us that Lf(f) S (f) for all f E A(H). Together we thus have (f) Σ 1/600 = LD(f) & 1/200 for any m 2 and 2 a' d'dy where a' > 0 is a universal constant. By observing that a exp(-m/a) 8 for a ln(a//), this completes the proof of Theorem 4 What remains is thus to prove Lemma 5 which we do in the remainder of this section.
sample S, we have for f E A(H) that
2.1 Relating (f) and (f)
The last remaining step to show Theorem is thus to relate L) to L.) i.e. to prove Lemma In the proof, rely the classic approach for showing generalization for classes H of bounded VC-dimension and introduce a ghost set that only exists for the sake of analysis. In addition to the sample S, we thus consider ghost set S' of another m i..d. samples from D. This allows to prove:
Lemma 6. For m 2 2400 any I and any f. it holds that:
10) - -'0 1200 Pr sup S SEA(H)
2 Pr
- -C fEa(H)
sup
S.S'
200
As the proof is standard, it can be found in the supplementary material.
We thus only need to bound Prs.s/ [sup (L's()) -1'(0)))%(())) 1/2400]. To do this, consider drawing a data set P of 2m i..d. samples from D and then drawing as a set of m uniform samples from P without replacement and letting S' be the remaining samples. Then S and S' have the same distribution as if they were drawn as two independent sets of m i.i.d. samples each. From here on, we thus think of and S' being sampled via P.
Now consider fixed set in the support of Dam and define (H, P) as the set of voting classifiers A(H) for which ((lxxx)=lll(()) z μ] 1- These are the voting classifiers that make

---

predictions of large absolute value on most of both S and S' (if à < 1/2). The crucial point, and the whole reason for introducing g, is that regardless of what f is, random g ~ Da often lies in the set (H,, P):
Lemma 7. For any data set P. parameters 0 < 0 < and and every μ S 6/(9600))), we have Pig-Dy,18 & (H, P)] s 1/4800.
Proof. Define an indicator X; for each (xi, yi) P takinng the value 1 lg - By Lemma 2 we
have EI x,1 < |P] 2 < IP| 6/4800. By Markov's inequality Pr[E, X; 2 6|P1] s 1/4800. O
If we had just considered f. we had no way of arguing that f makes predictions of large absolute value on S", since the only promise we are given is that it does so on S. That g makes predictions of large absolute value even outside of S is crucial for bounding the generalization error in the following.
Let us now define (P) sign (HH, P)) which means that À (P) contains all the hypotheses that are obtained by voting classifiers in (H,, P) when taking the sign. Since g is in A (H,, P) except with probability 1 1/8800 by Lemma 7 we can prove:
Lemma 8. For any O < 5 < I, every and every μ s 6/(9600 we have
Pr sup S.S' SEA(H)
- > 2400
- sup 2up2 exp ( 2m/9600²).
Again, the proof of the lemma can be found in the supplementary material. What Lemma 8 gives us, is that it relates the generalization error to the growth function |Â% (P)). The key point is that Â (P) was obtained from voting classifiers with predictions of large absolute value on all but a fraction of points in P. This implies that we can bound the VC-dimension of Å (P) when restricted to the point set P using Rademacher complexity:
Lemma 9. Let H be hypothesis set of VC-dimension d. For any ö, > O and point set P, we have that the largest subset P of P that (P) sign (H,, P)) can shatter, has size at most |P'| = d' < max(26)P) 4a? dd),, where a > 0 is a universal constant.
Proof. Recall that the VC-dimension of H is d. Thus the Rademacher complexity of for any point set P' is:
Σ M(x)or(s)) < a PP'
E Trep'(-11)
sup hes
|PT
xxep
for a universal constant a > 0 (see e.g.
23 l). Assume P' C P with |P'| d' can be shattered. Fix any labeling o E p' - 1). Let h E (P(P)) ()) be the hypothesis generating the dichotomy or (which exists since P' is shattered). Since ho E A (P), there must be some E A (H, P) such that least 6| Z IP2 points x E P' for which [x)x) 2 μu. This means that (1/IP') Σxep g(x)o 2 (1/2)μ. But g(x) is convex combination of hypotheses from H, hence there is also hypothesis h E HH for which (1/) Ever (x)) 2 (1/2)μ. Since this holds for all o. by the bound on the Rademacher complexity, we conclude a (d/lP'1> > (1/2)μ = |P'| < 4a² u d. We thus conclude that the largest set that A (P) can shatter, has size less than max max [2 4a 2d).
ho sign(g) on the point set P'. If [P'] Pl. then by definition of A (HH P), there
We remark that it was crucial to introduce the random hypothesis g, since all we are promised about the original hypothesis ʃ is that it has large margins on S, i.e. on only half the points in P. That case would correspond to 5 = 1/2 in Lemma 9 Jndd would mean that we could potentially shatter all of P. In order for the bound to be useful, we thus need 5 & 1/2 and thus large margins much more than half of P (which we get by using 8)
For 0 5 < of samples m satisfies m 2 max (a²2x 2400²] where a is the constant from Lemma 9. By Lemma 8 we have
be determined, let us now fix μ 5/(9600V) and assume that the number
Pr S.S"
sup fEA(H)
-
2400 s sup 2) exp(-2m/9600'
7

---

Algorithm 1: Bub-Sample(A, B) (Hanneke [3]
Input: Sets and B |A] s then
// stop when is too small to recurse
return AUA
3 else
Let Ao denote the first [A| 3[|A//4J elements of A,
1/ split evenly recurse in leave-one-out fashion
A1 the next L|A|/4J elements,
A2 the next [|A]/4] elements, and
A3 the remaining LIA]/4] elements.
return Sub-Sample( Ag. A3UA3UB) Sub-Sample((A An, A UAJUB) U Sub-Sample(Ap) (A, A U)
Algorithm 2: Optimal weak-to-strong learner
Input: Set S of samples.
[CI..... Cx} Sub-Sample(S,0)
// create highly overlapping subsamples of S // run AdaBoost; on all those sub sub-samples // return unweighted majority vote
for I....,KK do
h; (C,)
return /xxx sign Σ (x)).
Lemma gives us that the largest subset pr S P that (P) shatters has size at most d' max P| dd. By our assumption on m. the term PI 45m is at least 4c²y d and thus P||PI 46m takes the maximum in the bound on d'. By the Sauer-Shelah lemma, we have that (P)) s 46ōm-1 (2m)). For ö s 1/4, this most (45m) (eo-1/2)4ōm) exp (48m In(e8 /2)).
As conclusion we have:
1 Pr sup (0 001> 2400 S,S'
s 2exp(40m In(eo- exp( (10002mm996 2mm/9600))
EEA(H)
Let us now fix 5 10-10 We then have
exp (45m In(eo- 12)) exp( exp(-2m/96000)
= exp (m (6 In(eo /2) 2/ 2/9600²))
s exp (-m/10*)
where the last step is a numerical calculation. By Lemma 6 this in turn implies:
Pr sup SEA(H))
Lb)
1200 4exp(-m/10
Since we only required m 2 max(a pa 2d/6, 2400 for m 2 a' for large enough constant a' > 0. This completes the proof of Lemma and thus also finishes the proof of Theorem
2d/6,2222440 and we had μ = 6/ 6/(900V)), this satisfied
Weak to strong learning
In this section, we give algorithm for obtaining strong learner from y-weak learner with optimal sample complexity and sketch the main proof idea.
The algorithm obtaining the guarantees of Theorem is as follows: Let म, be an algorithm that on sample S outputs a classifier g = sign(f), where is voting classifier with margins least y/2 on all samples in such as AdaBoost,, (20). Given set S of m i.i.d. samples from an unknown distribution D, we run R. on number samples CI, C2.... C₁ C obtaining hypotheses h1 h2,.... hi- We then return the (unweighted) majority vote among hi...., h2 as our final hypothesis h". The subsets C; are chosen by algorithm Sub-Sample (shown in Algooggrt T) as in the optimal PAC learning algorithm by Hanneke [13] The final algorithm (Algorithm 2) calls A, on all subsets

---

returned by A Algorthhmm I and returns the majority vote. Note that the final hypothesis returned by Algorithm 2 is a majority of majorities since A, already returns a voting classifier. Let us also remark that in Theorem 4] we have a failure probability 60 > O, while the analysis of AdaBoost assumes 6y = 0, i.e. that the weak learner always achieves an advantage of at least y. one knows y in advance, this is not an issue as AdaBoost, only calls the weak learner on distributions over the training data 5 and one can thus compute the advantage from the training data. After in expectation 1/(1 0o) invocations of the weak learner, we thus get hypothesis with advantage y.
In total there are k = 3 (logg = m 0.79 calls to the weak learner, each with a sub-sample of linear size. Since AdaBoost, runs in polynomial time on its input, given that the weak learner is polynomial, Algorithm 2 is polynomial under the same condition.
The formal proof that Algorrihmm 2 has the guarantees of Theorem 1 is given in the supplementary material due to space constraints. It follows the proof of Hanneke [13] pretty much uneventfully, although carefully using that a generalization error of 1/200 suffices for each call of A, The key observation is that each of the recursively generated sub-samples in Anggorihh I leaves out a subset A, of the training data, whereas the two other recursive calls always include all of A, in their sub-samples. If one considers a hypothesis h trained on the data leaving out A,, then A, serves as an independent sample from D. This implies that if h has large error probability over D, then many of the samples in A; will be classified incorrectly by h. Now, since the two other recursive calls always include A;, any hypothesis h trained on sub-sample from those calls will have margin at least y/2 on all points misclassified by h in A; But the generalization bound in Theorem 2 then implies that h' makes mistake only with probability 1/200 on the conditional distribution ) It errs). Thus, the probability that they both err at the same time is at most the probability that h errs, times 1/200. Applying this reasoning inductively gives the conclusion that it is very unlikely that the majority of all trained hypotheses err at the same time which then finishes the proof.
Lower bound
In this section, we sketch the proof of of 2 which gives a lower bound that matches the sample complexity from [heorem 1] The full proof is given in the supplementary material. Informally, Theorem says that there exists weakly learnable concept class such that the hypothesis A(S) of any learning algorithm A satisfies
d In In(1/8) y2m
ED(A(S) 2 a
m
Here, the term In(1/5)/ follows from previous work. particular, we could let C = H and invoke the tight lower bounds for PAC-lcarning in the realizable setting (5).
Thus, we let 5 1/3 and only prove that the loss of (S)) is least ay) with probability 1/3 over S when [S] = m for some weakly learnable concept class C. This proof uses construction from Grønlund et al. [ to obtain a hypothesis set H over domain u = ady-2 such that constant fraction of all concepts in X - {-1, 1} can be y-weakly learned from H. We then create a distribution D where the first point x1 sampled with probability 1- (//(m) and with the remaining probability, we receive uniform sample among .2. The key point is that we only expect to see + m u/(4m) = u/4 distinet points from X in a sample of cardinality m. Thus, if we consider a random concept that can be y-weakly learned, the labels it assigns to points not in the sample are almost uniform random and independent. This in turn implics that the best any algorithm A can do is to guess the labels of points in X \ S. In that way, A fails with constant probability if we condition on receiving a sample other than x]- This happens with probability u/(4m)= = 4ady-2 / and the lower bound follows.
(xI..... of cardinality
To formally carry out the intuitive argument above, we first argue that for a random concept c e C, the Shannon entropy of is high, even conditioned on S and the labels c(S). Secondly, we argue that if ASS) has a small error probability under D, then it must be the case that the hypothesis AS)) reveals a lot of information about c, i.e. the entropy of is small conditioned on A()) Since AS)) a function of S and c(S), the same holds if we condition on and c(S). This contradicts that has high entropy and thus we conclude that A(S) cannot have a small error probability.

---

Conclusion
Overall, we presented a new weak to strong learner with a sample complexity that removes two logarithmic factors from the best-known bound. By accompanying the algorithm with matching lower bound for all d and 2 < < 1/80, we showed that the achieved sample complexity of our algorithm is indeed optimal. Our algorithm uses the same sub-sampling technique Hanneke [ and computes a voting classifier with large margins for each sample for example with AdaBoost, (2)] The analysis of our algorithm uses generalization bound for voting classifiers with large margins.
Although we determined the exact sample complexity of weak to strong learning (up to multiplicative constants), there are a few connected open problems. Currently, our construction uses 31og, (m) m 0.79 many sub-samples of linear size as input AdaBoost,, For very large datasets, would be great to reduce the number and size of these calls. We conjecture that the most promising way to do so is to revisit Hanneke's 's optimal PAC learner and improve the sub-sampling strategy there. This could lead to an improvement for the realizable case as well as to faster
learners.
Next, the output of our algorithm simple voter could achieve the same bounds. We believe that majority of majorities is actually necessary. This supported by a lower bound showing that there are voters with large margin and poor generalization (paying a logarithmic factor) and thus the learning algorithm has to avoid this 'bad' voter. We currently see no indication of how a variant of AdaBoost could do that.
majority vote over majority voters. is unclear whether
For the regime of y < 2nd which our lower bound does not capture, is it possible to use fewer samples? A recent result by Alon et al. [1] might suggest so. Concretely, they show that if concept class C can be y-weak learned from a base hypothesis set H of VC-dimension d, then the VC-dimension C is no more than O (+2(==+2(()+))) where (-) hides factors only depending on d. Interestingly, the part (2d=1) becomes non-trivial precisely when our lower bound stops applying. i.e. when y < 2nd This could hint at possibly better dependency on y for < 2nd
We have new generalization bound for large-margin classifiers, which is better than the k-th margin bound (Gao and Zhou (8) for constant error. Can the k-th margin bound in general be improved. perhaps by one logarithmic factor? One of our key new ideas is the application of the Hifleoood-Oforr lemma which might also be helpful for the more general case of non-constant error.
Acknowledgments and Disclosure of Funding
This work was supported by the Digital Research Centre Denmark (DIREC) and by the Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No 9064-00068B.
References
[1] Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran. 2021. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021. ACM, 481-489.
[2] Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E Schapire. 1998. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics 26, 5 (1998), 1651-1686.
[3] Kristin P Bennett, Ayhan Demiriz, and John Shawe-Taylor. 2000. A column generation algorithm for boosting. In ICML. Citeseer, 65-72.
[4] Leo Breiman. 1999. Prediction games and arcing algorithms. Neural computation 11, 7 (1999), 1493-1517.
[5] Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. 1989. A general lower bound on the number of examples needed for learning. Information and Computation 82,
3 (1989), 247-261.
10

---

[6] Paul Erdós. 1945. On lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51, 12 (1945), 898 902.
[7] Yoav Freund and Robert E Schapire. 1997. A decision-theoretiic generalization of on-line learning and an application to boosting. Journal of computer and system sciences 55, 1 (1997), 119-139.
[8] Wei Gao and Zhi-Hua Zhou. 2013. On the doubt about margin explanation of boosting. Artificial Intelligence 203 (2013), 1-18.
[9] Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, and Jelani Nelson. 2019. Margin-based generalization lower bounds for boosted classifiers. Advances in Neural Information Processing Systems 32 (2019).
[10] Allan Grønlund, Lior Kamma, and Kasper Green Larsen. 2020. Margins are Insufficient for Explaining Gradient Boosting. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020).
[11] Allan Grønlund, Lior Kamma, and Kasper Green Larsen. 2020. Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. In Proceedings of the 37th International Conference Machine Learning, ICML. 2020 (Proceedings of Machine Learning Research, Vol. 119). PMLR, 3779-3788.
[12] Adam J Grove and Dale Schuurmans. 1998. Boosting in the limit: Maximizing the margin of learned ensembles. In AAAI/IAAI 692-699.
[13] Steve Hanneke. 2016. The optimal sample complexity of PAC learning. The Journal Machine Learning Research 17, 1 (2016), 1319-1333.
[14] Steve Hanneke and Arych Kontorovich. 2021. Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research, Vol. 132). PMLR, 697-721.
[15] Michael Kearns. 1988. Learning Boolean formulae or finite automata is as hard as factoring. Technical Report RR-14-88 Harvard University Aikem Computation Laboratory (1988).
[16] Michael Kearns and Leslie Valiant. 1994. Cryptographic limitations learning boolean formulae and finite automata. Journal of the ACM (JACM) 41, (1994), 67-95.
[17] Alexander Mathiasen, Kasper Green Larsen, and Allan Grønlund. 2019. Optimal minimal margin maximization with boosting. International Conference on Machine Learning. PMLR, 4392-4401.
[18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2018. Foundations of machine learning. MIT press.
[19] Gunnar Rätsch and Manfred Warmuth. 2002. Maximizing the margin with boosting. In International Conference on Computational Learning Theory. Springer, 334-350.
[20] Gunnar Rätsch, Manfred K Warmuth, and John Shawe-Taylor. 2005. Efficient Margin Maximiz- ing with Boosting. Journal of Machine Learning Research 6, 12 (2005).
[21] Robert E Schapire. 1990. The strength of weak learnability. Machine learning 5, (1990). 197-227.
[22] Hans U. Simon. 2015. An Almost Optimal PAC Algorithm. In Proceedings of The 28th Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 40). PMLR, Paris, France, 1552-1563.
[23] Jon Wellner et al. 2013. Weak convergence and empirical processes: with applications to statistics. Springer Science Business Media.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The main limitations are the
points we stated in the open questions paragraph of the conclusion
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work is purely theoretic (set within learning theory) and is thus not expected to impact
society outside of the scientific community
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Due to space con- straints, a large purt of the proofs had to be moved the supplementary material. still managed to present the largest part of the proof of our new generalization bound for classifiers with large margins within the main body of the paper.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "rAQ665oaUMc", "reviewer": "Reviewer_B3NF", "summary": "The paper provides a new weak to strong learning algorithm that has less sample complexity compared to the best known algorithms. It also proves that the new algorithm achieves the optimal sample complexity by driving a lower bound. The optimal sample complexity of weak to strong learning algorithms was unknown before this work, but this work settles the sample complexity of the classic problem\nof constructing a strong learner from a weak learner.", "questions": "I have a quick question regarding the definition of weak learning. In Definition 1, the confidence probability, $\\delta$, is a fixed constant. However, according to Definition 7.1 of \"Foundation of Machine Learning by M. Mohri\", the statement must hold for any arbitrary $\\delta>0$. Please give an explanation on these two different definitions.", "limitations": "The paper does not have any negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper solves an important open problem regarding the sample complexity of weak to strong learning algorithms by improving the sample complexity of AdaBoost by two logarithmic factors. For the theoretical analysis of the newly proposed algorithm, they also derive a new generalization bound for voting classifiers that improve the Breiman's result.\n\n- AdaBoost is a voting classifier. They justify that a simple majority vote is not sufficient for obtaining an optimal sample complexity and an algorithm based on a majority of majorities is indeed necessary.\n\n- The paper is well written and easy to follow.\n\n-It is of sufficient interest to the audience of NeurIPS.\n\n- I did not check the proof in the supplementary material but the technical proof seems to be sound.\n\nWeaknesses:\nThe paper does not have any experimental results. I recommend the authors to incorporate some experiments to compare the sample complexity of their algorithm to other weak to strong learning algorithms such as AdaBoost on real data sets. They can also move some of parts of the proof to the supplementary material and instead incorporate some experimental results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VGS5wud1WyK", "reviewer": "Reviewer_kJot", "summary": "This paper considers the number of training examples to build a strong learner from a weak learning algorithm.\nIt presents a new algorithm with a bound that is two logarithmic factors lower than the state of the art.\nIn addition, it includes a lower bound asymptotically matching the upper bound.\n\nThe algorithm uses a sub-sampling scheme from Hanneke.  On each of the many subsamples, a boosting algorithm runs a weak learner guaranteeing edge $\\gamma/2$ on the given sub-sample (where $\\gamma$ is the edge of the weak learning algorithm) to produce an intermediate voted hypothesis.  \nThese resulting intermediate hypotheses are then thresholded and majority (unweighted) voted to produce the final classifier.\n\nA new theorem (Theorem 6) is applied to show each subsample suffices for the thresholded intermediate hypotheses to have generalization error at most 1/200 (with high probability).   \n\n", "questions": "Are there situations where AdaBoost is known to require at least $\\Omega$(expression in (1) )  examples for strong learning?\nThis seems implied by the page 3 line 80 comment, but it is not stated precisely.  \n", "limitations": "yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It is very nice that the upper and lower bounds match asymptotically.\n\nAlthough only a minor limitation, it seems like Theorem 6 requires that the weak learners be classifiers rather “confidence rated”.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FAAItdFrcKh", "reviewer": "Reviewer_Zmra", "summary": "The paper presents a new algorithm that constructs a strong learner from a weak learner with less sample complexity than existing methods by two logarithmic factors. Matching upper and lower bounds for sample complexity shows that the algorithm is optimal up to multiplicative constants. In doing so, the algorithmic analysis uses a new generalization bound for voting classifiers with large margins. This work resolves open issues with respect to the sample complexity of the problem of constructing a strong learner from a weak learner.", "questions": "Is it possible to extend the work in the paper to address the few important related open theoretical problems? Or would a completely new approach be needed to address these open problems? The paper should at least discuss this.\n\nMaybe it is just a formatting issue, but it is somewhat strange to have the first theorem listed as Theorem 3 as a result of the two preceding definitions Definition 1 and Definition 2. Can this be fixed? I do not believe this is a NeurIPS standard.\n", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a theoretical contribution to an important problem in practice. This includes a new algorithm that constructs a strong learner from a weak learner using less training data than previous work, and showing that the algorithm is optimal up to multiplicative constants and resolves the sample complexity of the problem of constructing a strong learner from a weak learner.\n\nThe paper does not provide any empirical results that illustrate the theoretical results in practice, but this is not a major concern given the theoretical contribution of the paper. The paper leaves open a few important related theoretical problems, but the theoretical contributions are strong enough on their own.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept