Boosting stops treating all errors alike: separate false-positive and false-negative guarantees get a geometric boostability line
Synopsis
Classical boosting theory counts all mistakes as one total, treating false positives and false negatives the same. A new formulation writes a weak learner's guarantee as a set of false-positive/false-negative error pairs and shows that whether that set can be boosted to arbitrarily high accuracy depends on whether its convex hull intersects the set of points reachable by random guessing. On this basis there is no middle ground between boostable and non-boostable, and boosting proceeds without knowing the set in advance.
Interpretation
Boosting theory can now handle weak learners whose false positives and false negatives are measured separately, rather than only their sum. Classical boosting only guarantees that a weak learner with total error slightly below one half can be amplified into a strong learner with arbitrarily small error, treating both error types alike. For any set of error pairs, the guarantee is not boostable when its convex hull intersects the set of points reachable by random guessing, and is boostable to arbitrarily high overall accuracy otherwise; the classical case and the recent singleton case both fall under this criterion as special cases.
Deciding boostability rests on a geometric boundary rather than checking learners one by one. Previously only the total-error guarantee and the singleton error-pair guarantee on either side of a specific threshold were known to be boostable or not. The criterion is whether the convex hull of the error-pair set intersects the random-guess-reachable set, and the classical boosting margin parameter corresponds to the distance from the set to that point set.
Boosting can be carried out adaptively without knowing the error-pair set, the hypothesis class, or the geometric margin. AdaBoost does not need the margin parameter in advance, but this adaptivity had not been extended to set-valued error guarantees. The algorithm estimates the separating direction by binary search during its run, and its number of weak-learner calls and sample complexity stay within small constant factors of AdaBoost.
Perspective
The scope is weak-learning guarantees described by sets of false-positive/false-negative error pairs within the PAC learning framework; the results are theorems giving a boostable versus non-boostable dichotomy, accompanied by an adaptive boosting algorithm and a confidence-amplification procedure.
Confidence amplification relies on a centerpoint argument and needs more than a certain fraction of successful calls to hold; the source raises whether this is an inherent limitation of confidence amplification in this setting or an artifact of the centerpoint approach, leaving it open.