Bagging is an Optimal PAC Learner (Extended Abstract)

1 Introduction

PAC learning, or probably approximately correct learning [Valiant, 1984], is the most classic theoretical model for studying classification problems in supervised learning. For binary classification in the realizable setting, the goal is to design a learning algorithm that with probability 1 - δ over a random training data set, outputs a hypothesis that mispredicts the label of a new random sample with probability at most ε. More formally, one assumes that samples come from an input domain X and that there is an unknown concept c : X → {-1, 1}

alizable setting means that c belongs to a predefined concept class C ⊆ X → {-1, 1} and that the correct label of any x ∈ X is always c(x).

For the above learning task, a learning algorithm A receives a training data set S of m i.i.d. samples (x1, c(x1)), . . . , (xm, c(xm)) where each xi is drawn independently from an unknown data distribution D over X . From The most natural learning algorithm for the above is empirical risk minimization (ERM). Here a learning algorithm simply outputs an arbitrary hypothesis/concept hS ∈ C that correctly predicts the labels of the training data, i.e. it has hS(xi) = c(xi) for all (xi, c(xi)) ∈ S. Clearly such a hypothesis exists since c ∈ C. Such a learning algorithm is referred to as a proper learner as it outputs a hypothesis/concept from the concept class C. ERM is known to obtain a sample complexity of O(ε-1 (d lg(1/ε) + lg(1/δ))) [Vapnik, 1982; Blumer et al., 1989]. Moreover, it can be shown that this analysis cannot be tightened, i.e. there are distributions D and concept classes C where any proper learner needs Ω(ε-1 (d lg(1/ε) + lg(1/δ))) samples [Auer and Ortner, 2004]. However, a PAC learning algorithm is not necessarily required to output a hypothesis h ∈ C. That better strategies might exist may seem counter-intuitive at first, since we are promised that the unknown concept c lies in C. Nonetheless, the strongest known lower bounds for arbitrary PAC learning algorithms only show that Ω(ε-1 (d+lg(1/δ))) samples are necessary [Blumer et al., 1989; Ehrenfeucht et al., 1989]. This leaves a gap of a factor lg(1/ε) between ERM and the lower bound for arbitrary algorithms.

∗Original paper [Larsen, 2023] appeared at COLT'23.

Despite its centrality, closing this gap remained a big open problem for more than thirty years. Finally, in 2016, Hanneke [2016] built on ideas by Simon [2015] and presented an algorithm with an asymptotically optimal sample complexity of M(ε, δ) = O(ε-1 (d + lg(1/δ))). His algorithm is based on constructing a number of subsets Si ⊂ S of the training data S with carefully designed overlaps between the Si's (see Section 2). He then runs ERM on each Si to obtain hypotheses hSi ∈ C and finally outputs the hypothesis fS taking the majority vote fS(x) = sign(∑i hSi (x)) among the hSi 's.

While being a major theoretical breakthrough, Hanneke's algorithm has unfortunately not had any significant practical impact. One explanation is that it requires a rather large number of sub-samples Si. Concretely, with optimal m = Θ(ε-1 (d + lg(1/δ))) samples, it requires mlg4 3 ≈ m0.79 sub-samples of linear size |Si| = Ω(m), resulting in a somewhat slow learning algorithm.

Our Contribution. In this work, we present an alternative optimal PAC learner in the realizable setting. Surprisingly, our algorithm is not new, but actually pre-dates Hanneke's algorithm by twenty years. Concretely, we show that the heuristic known as bagging (bootstrap aggregation) by Breiman [1996], also gives an optimal PAC learner. Bagging, and its slightly more involved extension known as random forest [Breiman, 2001], have proved very efficient in practice and are classic topics in introduction to machine learning courses.

In bagging, for t iterations, we sample a subset Si of n independent and uniform samples with replacement from S. We then run ERM on each Si to produce hypotheses hSi ∈ C and finally output the hypothesis fS1,...,St taking the majority vote fS1,...,St (x) = sign(∑i hSi (x)) among the hSi 's. The sub-samples Si are referred to as bootstrap samples.

While being similar to Hanneke's algorithm, it is simpler to construct the subsets Si, and also, we show that it suffices with just t = O(lg(m/δ)) bootstrap samples of size n for any 0.02m ≤ n ≤ m, which should be compared to Hanneke's algorithm requiring m0.79 subsets (where m is optimal Θ(ε-1 (d+lg(1/δ)))). For ease of notation, let Dc denote the distribution of a pair (x, c(x)) with x ∼ D. Our result is then formalized in the following theorem

Theorem 1. There is a universal constant a > 0 such that for every 0 < δ < 1, every distribution D over an input domain X , every concept class C ⊆ X → {-1, 1} of VC-dimension d and every c ∈ C, if t ≥ 18 ln(2m/δ) and 0.02m ≤ n ≤ m, then it holds with probability at least 1 - δ over the random choice of a training set S ∼ Dm c and t bootstrap samples S1, . . . , St ⊂ S of size n, that the hypothesis fS1,...,St produced by bagging satisfies

Solving for m such that ε ≤ LD(g) gives a sample complexity of O(ε-1 (d+lg(1/δ)) as claimed. We remark that the constants 18 and 0.02 can be reduced at the cost of increasing the unspecified constant a.

In addition to providing an alternative and simpler algorithm for optimal PAC learning, we also believe there is much value in providing further theoretical justification for the wide practical success of bagging.

In Section 2, we first present Hanneke's optimal PAC learner and highlight the main ideas in his analysis. We then proceed to present a high-level overview of our proof of Theorem 1, which re-uses some of the ideas from Hanneke's proof.

2 Proof Overview

In this section, we first present Hanneke's PAC learning algorithm and discuss the main ideas in his analysis. We then

Algorithm 1: Sub-Sample(U, V ) Input: Two sets of training samples U, V . Result: Collection consisting of sub-samples. 1 if |U| < 4 then 2 return {U ∪ V }. 3 else 4 Partition U into 4 disjoint sets U0,U1,U2,U3 of |U|/4 samples each. 5 return ⋃3i=1 Sub-Sample(U0, V ∪ (⋃j∈{1,2,3}\{i} Uj )).

proceed to give a high-level overview of the keys ideas in our proof that bagging is also an optimal PAC learning algorithm. For completeness, we start by recalling the definition of Vapnik-Chervonenkis dimension [Vapnik and Chervonenkis, 1971], or VC-dimension for short.

A concept class C ⊆ X → {-1, 1} has VC-dimension d, where d is the largest integer such that there exists a set of d samples x1, . . . , xd ∈ X for which any labeling of the d samples can be realized by a concept c ∈ C. That is, |{(c(x1), . . . , c(xd)) : c ∈ C}| = 2d . Throughout the paper, we assume d ≥ 1 which is always true when C contains at least two distinct concepts. Also, as the reader may have observed, we consistently use bold face letters to denote random variables.

Hanneke's Algorithm and Analysis. As mentioned in Section 1, Hanneke's algorithm constructs a carefully selected collection of sub-samples of the training set S. These sub-samples are constructed by invoking Algorithm 1 as SubSample(S, ∅).

For simplicity, we have presented the Sub-Sample algorithm assuming that m is a power of 4.

Since |U| is reduced by a factor 4 in each recursive call and there are 3 such calls, we get that the total number of sub-samples produced is 3lg4 m = mlg4 3 ≈ m0.79 .

To analyse the hypothesis produced by invoking SubSample(S, ∅), running ERM on each produced sub-sample Si to produce hypotheses hSi and taking a majority vote fS(x) = sign(∑i hSi (x)), we zoom in on the recursive invocations of Sub-Sample(U, V). Such an invocation produces a number of sub-samples S1, . . . , St of U ∪ V ⊆ S. Letting hS1 , . . . , hSt denote the hypotheses obtained by running ERM on these sub-samples and f(U,V)(x) = sign(∑i hSi (x)) the majority vote among them, we prove by induction (with the base being the leaves of the recursion) that with probability at least 1-δ over U, it holds that LD(f(U,V)) ≤ a · (d + ln(1/δ))/|U| for a universal constant a > 0. If we can complete this inductive step, then the conclusion follows by examining the root invocation Sub-Sample(S, ∅).

The base case in the inductive proof is simply when a · (d + ln(1/δ))/|U| > 1. Here the conclusion follows trivially as we always have LD(f(U,V)) ≤ 1. For the inductive step, let f1,(U,V), f2,(U,V) and f3,(U,V) denote the majority voters produced by the three recursive calls SubSample(U0,V ∪ U2 ∪ U3), Sub-Sample(U0,V ∪ U1 ∪ U3) and Sub-Sample(U0,V ∪ U1 ∪ U2). Each of these have LD(fi,(U,V)) ≤ a·(d+ln(1/δ))/|Ui| = 4a·(d+ln(1/δ))/|U| by the induction hypothesis (except with some probability δ which we ignore here for simplicity). For short, we say that a hypothesis h errs on x if h(x) ̸= c(x). The crux of the argument is now to show that it is very unlikely that fi,(U,V) errs on a sample x ∼ D at the same time as a hypothesis hS′ trained on a sub-sample S′ produced by a recursive call j ̸= i also errs on x.

For this step, let us wlog. consider the majority vote f1,(U,V) (over hypotheses produced by ERM on SubSample(U0,V ∪ U2 ∪ U3)). Intuitively, if LD(f1,(U,V)) ≪ a·(d+ln(1/δ))/|U| then the hypotheses in f1,(U,V) contribute little to LD(f(U,V)). So assume instead LD(f1,(U,V)) ≈ 4a · (d + ln(1/δ))/|U|. Consider now some hypothesis hS′ obtained by running ERM on a sub-sample S′ produced by the recursive call Sub-Sample(U0,V ∪ U1 ∪ U3). The key observation and property of the Sub-Sample algorithm, is that all hypotheses in the majority vote f1,(U,V) have been trained on sub-samples that exclude all of U1. This means that the samples U1 are independent of f1,(U,V). When LD(f1,(U,V)) ≈ 4a · (d + ln(1/δ))/|U|, we will now see about |U1|4a · (d + ln(1/δ))/|U| = a · (d + ln(1/δ)) samples (x, c(x)) in U1 for which f1,(U,V)(x) ̸= c(x). The observation is that, conditioned on f1,(U,V), these samples are i.i.d. from the conditional distribution D(· | f1,(U,V) errs). The second key observation is that hS′ is obtained by ERM on a sub-sample S′ that includes all of U1 (we add U1 to V in both of the other recursive calls). Moreover, since we are in the realizable setting, we have hS′(x) = c(x) for every x ∈ U1. In particular, this holds for all the samples where f1,(U,V)(x) ̸= c(x). The classic sample complexity bounds for proper PAC learning in the realizable setting then implies that hS′ has LD(·|f1,(U,V) errs)(hS′) = O((d + ln(1/δ))/(a · (d + ln(1/δ)))) ≤ 1/200 for a sufficiently large. Note that this is under the conditional distribution D(· | f1,(U,V) errs). That is, hS′ rarely errs when f1,(U,V) errs. We thus get that Pr[f1,(U,V)(x) ̸= c(x) ∧ hS′(x) ̸= c(x)] = Pr[f1,(U,V)(x) ̸= c(x)] · Pr[hS′(x) ̸= c(x) | f1,(U,V)(x) ̸= c(x)] ≤ (a/50) · (d + ln(1/δ))/|U|. Since this holds for every fi,(U,V) and hS′ from a recursive call j ̸= i, we can now argue that LD(f(U,V)) ≪ a · (d + ln(1/δ))/|U|. To see this, note first that for f(U,V) to err on an x ∈ X , it must be the case that at least one fi,(U,V) also errs. Even in this case, since one recursive call only contributes a third of the hypotheses in the majority vote f(U,V), there must be many hypotheses hS′ (at least a 1/2 - 1/3 = 1/6 fraction of all hypotheses) trained from sub-samples S′ produced by the recursive calls j ̸= i that also err on x. But we have just argued that it is very unlikely that both fi,(U,V) and such an hS′ err at the same time. Formalizing this intuition completes the inductive proof.

Bagging Analysis. We now turn to presenting the key ideas in our proof of Theorem 1, i.e. that bagging is an optimal PAC learner. Along the way, we also discuss the issues we encounter towards establishing the result. Recall that in bagging with a training set S ∼ Dm c , we randomly sub-sample t bootstrap samples S1, . . . , St ⊂ S each consisting of n i.i.d. samples with replacement from S. We then run ERM on each Si to produce hypotheses hS1 , . . . , hSt and finally return the majority vote fS1,...,St (x) = sign(∑i hSi (x)). It will be convenient for us to think of fS1,...,St in a slightly different way. Concretely, we instead let fS1,...,St (x) = (1/t) ∑i hSi (x) be a voting classifier. Then sign(fS1,...,St (x)) ̸= c(x) if and only if fS1,...,St (x)c(x) ≤ 0. We thus seek to bound LD(fS1,...,St ) = Prx∼D[fS1,...,St (x)c(x) ≤ 0]. The motivation for thinking about fS1,...,St as a voting classifier, is that it allows us to re-use some of the ideas that appear in proving generalization bounds for AdaBoost [Freund and Schapire, 1997] and other voting classifiers.

We first observe that similarly to Hanneke's sub-sampling, if we look at just two hypotheses hSi and hSj with i ̸= j, then hSi is trained on a bootstrap sample Si leaving out a rather large portion of S. Furthermore, hSj will be trained on most of these left-out samples and thus one could again argue that it is unlikely that hSi and hSj err at the same time. Unfortunately, this line of argument fails when we start combining a non-constant number of hypotheses. In particular, with high probability over the bootstrap samples, the union of any set of ℓ bootstrap samples contains all but an exp(-Ω(ℓ))-fraction of S. This leaves very few samples that are independent of the hypotheses trained on such ℓ bootstrap samples. Trying to repeat Hanneke's argument unfortunately requires Ω(m) independent samples towards the last steps of an inductive proof. In a nutshell, what saves Hanneke's construction is that a third all sub-samples together still leave out a quarter of the training data. For bagging, such a property is just not true if we have more than a constant number of bootstrap samples.

Abandoning the hope of directly applying Hanneke's line of reasoning, we instead start by relating the performance of bagging to that of a particular voting classifier that is deterministically determined from a training set S, i.e. we get rid of the bootstrap samples. To formalize this, we first introduce some notation. From a training set S of m samples (x1, c(x1)), . . . , (xm, c(xm)) and a vector of n not necessarily distinct integers I = (i1, . . . , in) ∈ [m]n , let S(I) denote the bootstrap sample (xi1 , c(xi1 )), . . . , (xin , c(xin )). Then a random bootstrap sample Si from S has the same distribution as if we draw I uniformly from [m]n and let Si = S(I). Also, let hS(I) ∈ C denote the hypothesis resulting from running ERM on S(I). Finally, for a list of t vectors B = (I1, . . . , It) ∈ [m]n×t , we let fS,B = (1/t) ∑ti=1 hS(Ii) denote the voting classifier produced by bagging with bootstrap samples S(I1), . . . , S(It). Using the notation B ∼ [m]n×t to denote a uniform random B from [m]n×t we thus have that the hypothesis produced by bagging on S has the same distribution as fS,B.

Now consider the following voting classifier

That is, gS is the voting classifier averaging the predictions over all mn possible bootstrap samples of S. Of course one would never compute gS. Nonetheless, the performance of the random fS,B with B ∼ [m]n×t is closely related to that of gS. To see this, we introduce the notion of margins which are typically used in the study of generalization of voting classifiers, see e.g. the works [Bartlett et al., 1998; Gao and Zhou, 2013; Larsen and Ritzert, 2022]. For a sample x ∈ X and voting classifier f(x) = (1/t) ∑ti=1 hi(x), we say that f has margin f(x)c(x) on the sample x. Since each hi(x) is in {-1, 1}, we have the margin is a number between -1 and 1. Intuitively, 1 represents that all the hypotheses hi agree on the label of x and those predictions are correct. In general, a margin of γ implies that an α-fraction of the hypotheses hi are correct, where α - (1 - α) = γ ⇒ α = 1/2 + γ/2. For a margin 0 ≤ γ ≤ 1, define LγD (f) = Prx∼D[f(x)c(x) ≤ γ]. That is, LγD (f) is the probability over a random sample x from D that f has margin at most γ on x. We have LD(f) = L0D (f). With margins defined, we show that for every training set S = {(xi, c(xi))}mi=1 , if t = Ω(ln(m/δ)), then with probability 1 - δ over B ∼ [m]n×t , we have

What this gives us, is that it suffices to understand how often the voting classifier that averages over all possible bootstrap samples has margin at most 1/3. To see why (1) is true, notice that every hypothesis hS(Ii) in fS,B = (1/t) ∑ti=1 hS(Ii) is uniform random among the hypotheses averaged by gS. Hence for any x ∈ X where gS has margin more than 1/3, we have EIi∼[m]n[hS(Ii)(x)c(x)] > 1/3. A Chernoff bound and independence of the bootstrap samples implies that PrB∼[m]n×t [fS,B(x)c(x) ≤ 0] ≤ exp(-Ω(t)) ≤ δ/m. Using that this holds for every x with gS(x)c(x) > 1/3 establishes (1).

Our next step is to show that L1/3 D (gS) is small with high probability over S ∼ Dm c . For this, our key idea is to create groups of bootstrap samples S(I) with I ∈ [m]n . These groups have a structure similar to those produced by Hanneke's Sub-Sample procedure. We remark that these groups are only for the sake of analysis and are not part of the bagging algorithm.

For simplicity, let us for now assume that bagging produced samples without replacement instead of with replacement. To indicate this, we slightly abuse notation and let (mn ) denote all vectors I ∈ [m]n where all entries are distinct. Also, let us assume that n precisely equals the number of samples in each sub-sample created by Hanneke's SubSample (technically, this is n = m - ∑lg4 m-1 i=0 4i ). For a set S = (x1, c(x1)), . . . , (xm, c(xm)), let I denote the collection of all vectors I ∈ (mn ) such that S(I) is one of the subsamples produced by Sub-Sample(S, ∅). Note that I only depends on m, not on S itself. We now define buckets Ci of vectors I ∈ (mn ) (i.e. of vectors corresponding to bootstrap samples). For every permutation π of the indices 1, . . . ,m, we create a bucket Cπ. We add a vector I = (i1, . . . , in) ∈ (mn ) to Cπ if and only if π(I) = (π(i1), . . . , π(in)) is in I.

With these buckets defined, we now make several crucial observations. First, for any bucket Cπ, if S ∼ Dm c , then the joint distribution of the bootstrap samples S(I) with I ∈ Cπ is precisely the same as the joint distribution of the sub-samples produced by Sub-Sample(S, ∅). This holds since permuting the samples in S does not change their distribution. Hence for any bucket, Hanneke's analysis shows that the majority of hypotheses hS(I) with I ∈ Cπ rarely errs. More precisely, if we let fS,π = (1/|Cπ|) ∑I∈Cπ hS(I) then LD(fS,π) = O((d+ ln(1/δ))/m) with probability 1-δ over S. Here we need something slightly stronger, namely that L5/6 D (fS,π) = O((d + ln(1/δ))/m). Assume for now that this holds.

Next observe that if x ∈ X has gS(x)c(x) ≤ 1/3 for a training set S, then at least one third of the hypotheses hS(I) with I ∈ (mn ) err on x, i.e. hS(I) for I uniform in (mn ) errs on x with probability at least 1/3 (here we assume that gS averages over hS(I) with I ∈ (mn ), i.e. sampling without replacement instead of with). Symmetry now implies that every I ∈ (mn ) is included in equally many buckets and all buckets contain equally many vectors I. This observation implies that the uniform I ∼ (mn ) has the same distribution as if we first sample a uniform random bucket C and then sample a uniform random I from C. But then if hS(I) errs on x with probability at least 1/3, it must be the case that a constant fraction of the buckets Cπ have fS,π(x)c(x) ≤ 5/6. This intuitively gives us that with high probability over S, L1/3 D (gS) can only be a constant factor larger than L5/6 D (fS,π). But L5/6 D (fS,π) is O((d + ln(1/δ))/m) with high probability, establishing the same thing for L1/3 D (gS) as desired.

The above are the main ideas in the proof, though making the steps completely formal requires some care, see the full version [Larsen, 2023] for details.

3 Conclusion

In this work, we have shown that the classic bagging heuristic is an optimal PAC learner in the realizable setting if we sample just a logarithmic number of bootstrap samples.

Let us remark a small downside of bagging compared to Hanneke's algorithm. In his work, the number of sub-samples is independent of δ, whereas our result for bagging requires Ω(ln(m/δ)) sub-samples. Indeed, as bagging is a randomized algorithm, there will be some non-zero contribution to the failure probability due to the number of sub-samples (with some non-zero probability, all sub-samples are the same). We find it an interesting open problem whether the analysis can be tightened to yield a better dependency on δ in the number of sub-samples needed.

Finally, let us comment on the unspecified constant a > 0 in Theorem 1. In our proof, we did not attempt to minimize a and indeed it is rather ridiculous. With some care, one could certainly shave several orders of magnitude, but at the end of it, we still rely on Hanneke's proof which also does not have small constants. We believe that bagging actually provides quite good constants, but this would require a different proof strategy. At least our reduction to understanding L1/3 D (gS) is very tight and incurs almost no loss in the constant a. A starting point for improvements would be to find an alternative proof that L1/3 D (gS) is small with high probability over S.

Acknowledgments

Supported by Independent Research Fund Denmark (DFF) Sapere Aude Research Leader grant No 9064-00068B.