A weak learner may be only slightly better than a coin flip. Boosting can turn that advantage into arbitrarily small error, but one qualification is essential: the advantage must persist on the changing distributions used by the booster. A training-error calculation alone does not provide this distributional guarantee. Here we prove the guarantee directly under an explicit weak-learning assumption, then show how to sample the changing distributions from the original source.
Definition 6.2.1
(Weak learner with edge )
Let be an unknown distribution on an instance space , and let an unknown target from a concept class of measurable maps supply the label . All rules and weights below are measurable. Fix . A weak learner with edge has the following distribution-free realizable guarantee: for every , every distribution on labeled by that target, and every , given independent labeled samples from , it outputs a rule such that
with probability at least , over its sample and its independent internal randomness. The sample bound does not depend on the particular or , and the learner is not given except through labeled examples. The guarantee must hold for every reweighted encountered below. We assume each output can be evaluated when requested; computational complexity depends on the weak learner and its representation.
Population boosting with a fixed positive step
Put
Start with . In round , use the distribution whose density relative to is
obtain a rule , and set . Every is a probability distribution: the weight is positive and bounded, and . The final prediction is the sign of , with any fixed tie rule. In our analysis a zero margin is counted as an error, so the bound covers every such tie rule.
Theorem 6.2.2
(Exponential reduction of population error)
If every selected rule has error at most , then
This is a deterministic implication for the realized rules and the actual distribution . It requires neither a finite hypothesis class nor an empirical generalization step.
Proof
(The exponential potential shrinks on every good round)
Let . The change of measure in (2) gives , so
The inequality uses and . The displayed value follows from the definition of . Since , multiplication gives . Whenever , , proving the first inequality in (3). Finally .
Proof X-ray
Why this is a population statement
Each is defined from the true , and the weak edge in (1) is a true error. The potential is an expectation under , not a training average. The rules may be selected adaptively; after their selection, the deterministic inequality applies whenever every selected rule satisfies its own edge condition. The next step explains how to obtain the required samples without knowing a density for .
Sampling an adaptive reweighted distribution
At the start of round , the already selected are fixed by the preceding transcript. Draw fresh labeled examples from . For each proposal, independently accept it with probability
This probability lies in because . Repeat until examples have been accepted. The unknown normalizer is not required to implement (4).
Theorem 6.2.3
(Rejection sampling and an explicit proposal cap)
Conditional on the preceding transcript, the accepted examples are independent draws from . Their acceptance probability is
Each round uses exactly accepted examples. For the uncapped procedure, the expected total number of original proposals over rounds is at most . Consequently, for , the cap
is exceeded with probability at most .
Proof
(Condition first, then average over the adaptive history)
For any measurable , a proposal lands in and is accepted with probability
Dividing by its total acceptance probability yields . Independent proposals and independent acceptance coins make successive accepted examples independent with this same conditional law. Also , so (5) follows.
Conditional on the history, each acceptance is geometric with success probability , so acceptances use expected proposals. This bound holds for every history, including histories with an unsuccessful weak rule. Taking expectations and summing proves the total expectation bound. Markov's inequality applied to the uncapped procedure proves (6). Writing for the uncapped proposal count, the abort event is : an implementation aborts if it would exceed ; on the complementary event it exactly matches the uncapped procedure.
Worked example 6.2.4
(Two rounds of rejection sampling)
Let with , , target at both points, and . Then and . In round 1, and . Suppose is correct at and wrong at , so . Then gives at and at , and .
In round 2 the acceptance probabilities in (4) are and . The overall acceptance probability is , which agrees with and respects the lower bound from (5). Among accepted examples the fraction at is . This equals computed directly from (2): .
Common mistake
(The acceptance probability must not exceed one)
Accepting a proposal with probability looks like the natural way to realize (2), but this number can exceed one: in the example above at . The factor in (4) rescales all weights by the same constant so that the largest one is at most . This does not change , because only ratios of acceptance probabilities matter, and it is why the unknown normalizer never has to be computed.
A strong learner and its assumptions
Choose
for , and use accepted examples in each round. Run the capped procedure (6); on abort, output any fixed rule.
Theorem 6.2.5
(Weak-to-strong guarantee with confidence)
For every and every , under the stated distribution-free weak-learning assumption the returned classifier has -error at most with probability at least . Its original-example usage is at most even on an abort.
Conditional on any preceding transcript, rejection sampling provides fresh independent examples. The weak learner therefore fails its edge condition with conditional probability at most , even though was chosen adaptively. Averaging over the transcript and taking a union bound makes the chance of any failed round at most . In the uncapped thought experiment, the proposal cap is exceeded with probability at most . On the intersection of the complementary events, (3) gives error at most . The capped algorithm agrees with the thought experiment there. A union bound proves the theorem; no independence between these two failure events is needed.
For a fixed edge , and is polynomial in . Thus (6) is polynomial in and if the weak learner's sample and computation costs are polynomial in the corresponding parameters and its rules can be evaluated efficiently. The displayed rejection bound is deliberately crude; it is not an optimal boosting sample complexity. If varies, the exponent in that polynomial depends on , so no uniform polynomial dependence on is claimed.
Worked example 6.2.6
(How crude the proposal cap is)
Take and . Then , and . The potential bound is . In the worst case allowed by (5), however, the last round may need proposals per accepted example. The boundary case is the first round: , so , every proposal is accepted and . The analysis is correct, but the cap (6) is a proof device, not a practical estimate of cost.
Worked example 6.2.7
(Three rules, each missing a different point)
Let and let the concept class contain the two constant targets and . For each point let one of predict there and at the other two. Use the six-rule hypothesis class , which contains no constant rule. For either target and every distribution , at least one point has mass at most ; the matching rule with the appropriate sign has error at most . Thus this class has a distribution-free edge for both targets, though no individual rule is perfect.
For example choose . A fresh-sample empirical-error minimizer over these six rules is a weak learner with edge : uniform Hoeffding bounds show that suffices for all six empirical errors to be within of their true errors with probability at least . The selected rule's true error is at most . The unweighted majority of is perfect for the positive target; the majority of their negatives is perfect for the negative target. Thus a combination can succeed when no individual rule does.
Counterexample mode
An edge only on the original distribution is not enough
Let , , with target at both points. A rule that is correct at and wrong at has -error . Repeating only this rule never fixes its error: every positive-weight majority of copies of is again . Under the reweighting (2), the relative weight of grows by each round, and its probability tends to one. Eventually has no positive edge on the distribution requested by the booster. A weak guarantee only for cannot be substituted for (1).
Practice with solutions
Quick check
(A single potential step: if a rule has error , derive .)
Split the expectation over correct and incorrect points.
Solution · Answer
Correct points have and contribute ; incorrect points have and contribute . Therefore the ratio is .
Quick check
(Number of rounds: with and target error , find the displayed sufficient .)
Use .
Solution · Answer
, so . This is sufficient, not necessarily the minimum number of rounds.
Quick check
(No infinite coefficient is needed: what happens if one chosen rule has zero error?)
Evaluate the round factor at .
Solution · Answer
Its round factor is . The fixed remains finite and the update is defined. This avoids the division-by-zero issue of a data-dependent coefficient that uses the exact error.
Quick check
(Adaptive confidence: why is the bound valid when later depend on earlier random rules?)
Condition on the transcript before round .
Solution · Answer
Conditional on every preceding transcript, the round- failure probability is at most . Taking expectation makes its unconditional probability at most . A union bound then gives without assuming that round failures are independent.
Quick check
(A cap is not an expected value: why does an expected proposal bound alone not give a deterministic sample cap?)
A nonnegative random variable can exceed its mean.
Solution · Answer
A nonnegative random variable can exceed its expectation. Markov's inequality turns the bound into a high-probability cap: with as in (6), the ideal procedure exceeds with probability at most . Aborting at makes the actual resource use deterministic while charging that event to the failure probability.