A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

“A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting” by Yoav Freund and Robert E. Schapire of AT&T Labs appeared in the Journal of Computer and System Sciences in August 1997, after an extended abstract at the Second European Conference on Computational Learning Theory (EuroCOLT) in Barcelona in March 1995. It has two halves. The first studies an on-line problem: how to spread a fixed stake over $N$ options, round after round, so that the total loss is not much worse than that of the best option in hindsight. It answers with a multiplicative-weight algorithm called Hedge($\beta$) and proves bounds for it. The second half turns that algorithm around to obtain AdaBoost, a boosting algorithm that, unlike its predecessors, needs no advance knowledge of how good the weak learner is. The paper proves that AdaBoost’s training error falls exponentially when every weak hypothesis beats chance, bounds the VC dimension of its output, and gives extensions to multiclass problems (AdaBoost.M1 and AdaBoost.M2) and to regression (AdaBoost.R). It received the 2003 Gödel Prize.

The method as it is used today, with labels $\pm 1$, the exponential-loss and margin explanations, gradient boosting and boosted detectors, is covered in the boosting article; this article covers the paper. The typeset journal article could not be read: ScienceDirect served it only behind a bot challenge, and no archived copy of the PDF was found. Everything below comes from the authors’ manuscript dated 19 December 1996, which both authors host on their web pages and whose footnote states that it appeared in the journal. Section, theorem, equation and figure numbers are the manuscript’s, and page numbers within the journal’s 119–139 are not given.

Problem

Weak learning and the earlier boosters

In the PAC model, which the paper reviews in §4, a strong learning algorithm must reach any error $\epsilon$ with probability $1 - \delta$ in time polynomial in $1/\epsilon$, $1/\delta$ and the size of the problem; a weak one only needs error at most $\tfrac{1}{2} - \gamma$ for some $\gamma > 0$. Schapire (1990) had shown that any weak learner can be boosted into a strong one, and Freund’s boost-by-majority algorithm had made the conversion considerably more efficient. The boosting article tells this history. Freund and Schapire name the practical weakness of boost-by-majority: it needs the weak learner’s worst-case edge $\gamma$ in advance. That edge is rarely known, varies from one reweighted distribution to the next, and the algorithm gains nothing from weak hypotheses that do better than the assumed $\tfrac{1}{2} - \gamma$.

On-line allocation

The paper opens with a gambler who lets friends bet on his behalf and wants to divide each race’s stake among them so that his season’s winnings come close to what the luckiest friend would have won. Formally (§1), an allocator chooses a distribution $\mathbf{p}^t$ over $N$ strategies at each step $t = 1, \dots, T$; an environment, possibly adversarial and possibly aware of $\mathbf{p}^t$, then assigns each strategy a loss $\ell_i^t \in [0, 1]$, and the allocator suffers the mixture loss $\mathbf{p}^t \cdot \boldsymbol{\ell}^t$. The goal is a small net loss

$$L_A - \min_i L_i, \qquad L_A = \sum_{t=1}^{T} \mathbf{p}^t \cdot \boldsymbol{\ell}^t, \quad L_i = \sum_{t=1}^{T} \ell_i^t .$$

Littlestone and Warmuth’s weighted majority algorithm and the work of Cesa-Bianchi and colleagues on predicting with expert advice had proved such bounds for binary decisions with a $\{0, 1\}$ loss. The paper’s aim was bounds for any bounded loss over any decision and outcome spaces, slightly weaker in special cases but far more general.

Contribution

1. Hedge($\beta$) (Figure 1, §2), a direct generalization of weighted majority to the allocation problem, with loss bounds (Lemma 1, Theorem 2, Equations 7–12), a proof that its constants are optimal (Theorem 3, proved in the appendix using Vovk’s results), and applications (§3).
2. AdaBoost (Figure 2, §4.1), derived by reducing boosting to on-line allocation in reverse. The paper explains the name: unlike earlier algorithms, it adjusts adaptively to the errors of the weak hypotheses.
3. A training-error bound that uses every weak hypothesis (Theorem 6), not just the worst, and that needs no prior knowledge of the edge.
4. A generalization analysis (§4.3): a bound on the VC dimension of AdaBoost’s final hypotheses (Theorem 8), with structural risk minimization or a validation set to choose the number of rounds.
5. Extensions (§5): AdaBoost.M1 and AdaBoost.M2 for $k$ classes and AdaBoost.R for regression, each analysed by a reduction to the binary algorithm.

Method

Hedge($\beta$) and its bounds

Hedge keeps a nonnegative weight $w_i^t$ per strategy, starting from any initial weights that sum to one (the paper suggests reading them as a prior; uniform weights $1/N$ are the default). Each round it allocates in proportion to the weights and then multiplies each weight by $\beta$ raised to that strategy’s loss:

$$\mathbf{p}^t = \frac{\mathbf{w}^t}{\sum_{i=1}^{N} w_i^t}, \qquad w_i^{t+1} = w_i^t \, \beta^{\ell_i^t}, \qquad \beta \in [0, 1].$$

The analysis bounds the total weight from both sides. Since $\beta^{r} \le 1 - (1 - \beta) r$ for $r \in [0, 1]$, each round multiplies the total weight by at most $1 - (1 - \beta)\,\mathbf{p}^t \cdot \boldsymbol{\ell}^t$, which gives Lemma 1, $\ln \sum_i w_i^{T+1} \le -(1 - \beta) L_{\mathrm{Hedge}(\beta)}$. From below, strategy $i$ alone keeps weight $w_i^1 \beta^{L_i}$. Together (Theorem 2, Equation 7):

$$L_{\mathrm{Hedge}(\beta)} \le \frac{-\ln w_i^1 - L_i \ln \beta}{1 - \beta} \quad \text{for every } i, \qquad\text{so with } w_i^1 = \tfrac{1}{N}: \quad L_{\mathrm{Hedge}(\beta)} \le \frac{\min_i L_i \ln(1/\beta) + \ln N}{1 - \beta} \;\; (9).$$

The bound grows only logarithmically with $N$. Equation (8) generalizes it to sets of strategies, which the authors note handles infinite and even uncountable collections. Writing Equation (9) as $c \min_i L_i + a \ln N$ with $c = \ln(1/\beta)/(1 - \beta)$ and $a = 1/(1 - \beta)$ (Equation 10), Theorem 3 shows that any algorithm with a bound of that form for every $N$ must, for each $\beta \in (0, 1)$, have $c \ge \ln(1/\beta)/(1 - \beta)$ or $a \ge 1/(1 - \beta)$, so no algorithm improves both of Hedge’s constants at once.

For choosing $\beta$ (§2.2), Lemma 4 sets $\beta = g(\tilde{L}/\tilde{R})$ with $g(z) = 1/(1 + \sqrt{2/z})$, where $\tilde{L}$ is a prior bound on the best strategy’s loss; with $\tilde{R} = \ln N$ this gives Equation (11),

$$L_{\mathrm{Hedge}(\beta)} \le \min_i L_i + \sqrt{2 \tilde{L} \ln N} + \ln N .$$

When only the number of rounds is known, $\tilde{L} = T$ works, and the average net loss per round falls as $O(\sqrt{(\ln N)/T})$, or roughly $O((\ln N)/T)$ when the prior bound $\tilde{L}$ is near zero. The paper notes, citing Cesa-Bianchi et al., that the square-root term cannot be improved by more than a constant factor in general.

Section 3 applies the bound to an expert setting with a decision space $\Delta$, an outcome space $\Omega$ and a loss $\lambda: \Delta \times \Omega \to [0, 1]$ (Theorem 5): $k$-ary sequence prediction, repeated matrix games such as rock, paper, scissors, where the average loss per round is at most the value of the game plus a term that vanishes as $T$ grows, even when the learner does not know the game, and prediction of points in $\mathbb{R}^n$ under any loss that is convex in the prediction, including Cover’s log loss for universal portfolios.

From Hedge to boosting

Section 4.1 sets up batch boosting “by sampling” (Freund’s term): a fixed training set of $N$ examples $(x_i, y_i)$ with $y_i \in \{0, 1\}$, and a distribution $D$ over them, ordinarily uniform, under which the final hypothesis should have low error. The weak learner receives a distribution each round and may return a real-valued hypothesis $h_t: X \to [0, 1]$, read as the probability of predicting 1, so that its error is the expected absolute difference from the label. A footnote notes that a learner that cannot use weights can be fed a resampled training set instead.

The surprise, in the authors’ words a “dual” relationship (§4.2), is how the reduction runs. One might expect weak hypotheses to play the strategies and training examples the trials. In AdaBoost it is the reverse: the examples are the strategies, the rounds are the weak hypotheses, and the loss of example $i$ in round $t$ is

$$\ell_i^t = 1 - |h_t(x_i) - y_i| ,$$

which is small when $h_t$ is wrong on $x_i$. Hedge moves weight towards strategies that do well; AdaBoost therefore moves weight towards examples the weak hypotheses get wrong.

The paper first applies Hedge directly. If every weak hypothesis has error at most $\tfrac{1}{2} - \gamma$ with $\gamma$ known, Hedge with $\beta = 1 - \gamma$ and an unweighted majority vote has error at most $e^{-T\gamma^2/2}$. AdaBoost improves on this in two ways: a sharper choice of $\beta$ and a better bound, and no need to know $\gamma$. It measures each $\epsilon_t$ and sets $\beta_t$ from it, so that a more accurate hypothesis both changes the distribution more and gets a larger vote.

AdaBoost as printed

Figure 2 of the manuscript, in the paper’s notation:

1. Set $w_i^1 = D(i)$.
2. For $t = 1, \dots, T$: normalize, $\mathbf{p}^t = \mathbf{w}^t / \sum_i w_i^t$; call the weak learner with $\mathbf{p}^t$ and get $h_t: X \to [0, 1]$; compute its error $\epsilon_t = \sum_{i} p_i^t \, |h_t(x_i) - y_i|$; set $\beta_t = \epsilon_t / (1 - \epsilon_t)$; update $w_i^{t+1} = w_i^t \, \beta_t^{\,1 - |h_t(x_i) - y_i|}$.
3. Output

$$h_f(x) = \begin{cases} 1 & \text{if } \sum_{t=1}^{T} \left(\log \frac{1}{\beta_t}\right) h_t(x) \ge \frac{1}{2} \sum_{t=1}^{T} \log \frac{1}{\beta_t}, \\ 0 & \text{otherwise.} \end{cases}$$

With Boolean hypotheses and $\epsilon_t < \tfrac{1}{2}$, a correct example’s weight is multiplied by $\beta_t < 1$ and a mistake’s weight is left alone, which after normalization raises the share of the mistakes. A footnote states that the update exactly removes the advantage of the last hypothesis: its error under $\mathbf{p}^{t+1}$ is exactly $\tfrac{1}{2}$. The vote $\log(1/\beta_t) = \ln((1 - \epsilon_t)/\epsilon_t)$ is twice the $\alpha_t$ of the $\pm 1$ form in the boosting article, and writing a Boolean $h_t$ as $(1 + h'_t)/2$ with $h'_t \in \{-1, +1\}$ turns the threshold rule into $\sum_t \alpha_t h'_t(x) \ge 0$; by our arithmetic the two forms make the same predictions, with ties going to label 1. The figure writes $\log$ and the text $\ln$; the base cancels from the threshold.

The paper points out that AdaBoost sums the weak hypotheses’ probabilistic predictions rather than taking a majority of rounded ones, the combination that Drucker, Schapire and Simard had found better in practice with neural networks but which had lacked a justification.

The training-error bound

Theorem 6 (Equation 14): if the weak learner returns hypotheses with errors $\epsilon_1, \dots, \epsilon_T$, the error of $h_f$ under $D$ satisfies

$$\epsilon = \Pr_{i \sim D}\left[h_f(x_i) \ne y_i\right] \le 2^T \prod_{t=1}^{T} \sqrt{\epsilon_t (1 - \epsilon_t)} .$$

The proof follows Lemma 1 and Theorem 2. Each round multiplies the total weight by at most $1 - (1 - \epsilon_t)(1 - \beta_t)$ (Equations 15–16); an example on which $h_f$ errs keeps a final weight of at least $D(i) \left(\prod_t \beta_t\right)^{1/2}$ (Equations 17–19); hence $\epsilon \le \prod_t \left(1 - (1 - \epsilon_t)(1 - \beta_t)\right)/\sqrt{\beta_t}$ (Equation 20), and minimizing each factor gives $\beta_t = \epsilon_t/(1 - \epsilon_t)$ and Equation (14). The paper notes that the theorem holds even if some $\epsilon_t \ge \tfrac{1}{2}$. With $\epsilon_t = \tfrac{1}{2} - \gamma_t$ (Equations 21–22),

$$\epsilon \le \prod_{t=1}^{T} \sqrt{1 - 4\gamma_t^2} = \exp\Big(-\sum_{t=1}^{T} \mathrm{KL}\big(\tfrac{1}{2} \,\|\, \tfrac{1}{2} - \gamma_t\big)\Big) \le \exp\Big(-2 \sum_{t=1}^{T} \gamma_t^2\Big),$$

and for equal edges $\epsilon \le (1 - 4\gamma^2)^{T/2} \le e^{-2T\gamma^2}$, a form of the Chernoff bound with the same asymptotic behaviour as boost-by-majority’s. Equation (23) turns this into a number of rounds, $T = \left\lceil \ln(1/\epsilon) / \mathrm{KL}(\tfrac{1}{2} \| \tfrac{1}{2} - \gamma) \right\rceil \le \left\lceil \ln(1/\epsilon)/(2\gamma^2) \right\rceil$. The authors stress that the bound improves when any weak hypothesis improves, while earlier bounds depended only on the weakest one, which matters because the weak learner’s error is expected to grow as the distributions drift away from the target.

Section 4.5 shows that replacing the hard threshold by a soft one, a function $F$ of the normalized vote with $F(1 - r) = 1 - F(r)$ and a bound on $F(r)$ that a particular sigmoid satisfies, halves the bound to $2^{T-1} \prod_t \sqrt{\epsilon_t(1 - \epsilon_t)}$ (Theorem 9), with the output read as a randomized prediction.

Generalization

Theorem 6 is about the training sample. For the error on new examples, §4.3 quotes Vapnik’s uniform-convergence theorem (Theorem 7: with probability at least $1 - \delta$, every hypothesis in a class of VC dimension $d$ has empirical and true errors within $2\sqrt{(d(\ln(2N/d) + 1) + \ln(9/\delta))/N}$) and proves Theorem 8: if the weak hypotheses come from a class of VC dimension $d \ge 2$, the linear thresholds of $T$ of them, which include AdaBoost’s output after $T$ rounds, have VC dimension at most

$$2(d + 1)(T + 1) \log_2\big(e(T + 1)\big).$$

The proof views $h_f$ as a two-layer network and applies a counting result of Baum and Haussler. To choose $T$, the paper describes structural risk minimization with these bounds and warns that they may be loose and so pick too few rounds; its simple alternative is to hold out a validation set and take the $T$ with the lowest validation error. The next paragraph already records the observation that would later need explaining: initial experiments by the authors and by Drucker and Cortes indicated that AdaBoost tends not to overfit, its generalization error often continuing to drop, or at least not rising, after hundreds of rounds.

Section 4.4 adds a Bayesian reading. If the weak hypotheses’ mistakes are independent of each other and of the label, the Bayes-optimal combination of $\{0, 1\}$-valued hypotheses with errors $\epsilon_t$, after adding a constant hypothesis to account for the prior, is exactly AdaBoost’s weighted vote; the authors suggest AdaBoost as a principled alternative to this naive-Bayes rule when the independence assumption is not justified.

Multiclass and regression

AdaBoost.M1 (Figure 3, §5.1) is the direct extension to labels $Y = \{1, \dots, k\}$: the error becomes $\epsilon_t = \sum_i p_i^t [\![h_t(x_i) \ne y_i]\!]$, the loop aborts if $\epsilon_t > \tfrac{1}{2}$, and the output is the label with the largest total vote $\sum_t \log(1/\beta_t) [\![h_t(x) = y]\!]$. Theorem 10 gives the same bound as Theorem 6 when each $\epsilon_t \le \tfrac{1}{2}$, by a reduction to the binary algorithm. The authors note that error below one half is much stronger than beating random guessing, whose error is $1 - 1/k$, when $k > 2$, and show that with error rate as the only measure the difficulty is unavoidable: a learner that recognizes label 2 but guesses between 0 and 1 is right at least half the time but cannot be boosted. Their second example is from optical character recognition: a weak learner may easily tell a “7” from a “0” but not from a “9”.

AdaBoost.M2 (Figure 4, §5.2) lets the weak hypotheses say more. A hypothesis $h: X \times Y \to [0, 1]$ gives a degree of belief for every label, and is judged by a pseudo-loss that averages, with a label weighting $q(i, y)$ supplied by the booster, how often it would fail to tell the correct label $y_i$ from each wrong label $y$:

$$\mathrm{ploss}_q(h, i) = \frac{1}{2}\Big(1 - h(x_i, y_i) + \sum_{y \ne y_i} q(i, y)\, h(x_i, y)\Big).$$

The booster keeps a weight for every pair of example and wrong label, so it can steer the weak learner both towards hard examples and towards the wrong labels hardest to rule out. Any uninformative hypothesis has pseudo-loss $\tfrac{1}{2}$, so beating $\tfrac{1}{2}$ is a weak, chance-relative requirement, and Theorem 11 bounds the error by $(k - 1) 2^T \prod_t \sqrt{\epsilon_t (1 - \epsilon_t)}$. The paper notes that this bound is weaker than M1’s, and reports, citing its authors’ own experiments (Freund and Schapire, 1996), that pseudo-loss helped most with very restricted weak learners and made little difference with decision trees. It also mentions the alternative of reducing a multiclass problem to binary ones with error-correcting output codes.

AdaBoost.R (Figure 5, §5.3) handles $Y = [0, 1]$ with squared error. Each example becomes a continuum of binary questions, “is $y_i$ above or below $y$?”, weighted so that the binary error in the reduced problem is proportional to the squared error, with a constant between 1 and 2. The weights are piecewise-linear functions of $y$ and can be stored exactly; the final hypothesis is a weighted median of the weak predictions; Theorem 12 (Equation 26) gives the bound of Equation (14) for the mean squared error. The authors note as a drawback that no trivial weak hypothesis has loss exactly $\tfrac{1}{2}$, sketch a confidence-rated fix, and say that other bounded losses, zero at the true label and differentiable and monotone on either side of it, need only a change of the initial weights.

Results

The paper has no experiments of its own. Its results are the theorems above. Of AdaBoost’s empirical record it says only that successful experiments had been run since its introduction, by the authors (the ICML 1996 paper “Experiments with a New Boosting Algorithm”), by Drucker and Cortes, by Jackson and Craven, by Quinlan and by Breiman, and that the early experiments showed little overfitting.

Hedge’s bounds are worst-case guarantees, and the example below shows how they compare with an actual run. It turns Hedge loose on a stream of 2,000 synthetic $16 \times 16$ grayscale patches, about half of which contain a slightly brighter disc at a random position. The 64 “experts” are fixed rules, each predicting “disc” when one random rectangle is brighter on average than another, and each loss is 1 for a wrong label. The script compares Hedge’s loss with the best expert’s in hindsight for the paper’s choice $\beta = g(T/\ln N)$ and for two fixed values, together with Equations (9) and (11). It uses NumPy 2.3.5 and runs in about 2 seconds.

import numpy as np

S = 16                                            # patch size (pixels)
yy, xx = np.mgrid[0:S, 0:S] + 0.5

def patch(disc, rng):
    """Background of random brightness with Gaussian noise; with label 1 it also holds
    a slightly brighter disc of random radius and position."""
    img = np.full((S, S), rng.uniform(0.3, 0.7))
    if disc:
        r, (cy, cx) = rng.uniform(3, 5), S / 2 + rng.uniform(-3, 3, 2)
        img[(yy - cy) ** 2 + (xx - cx) ** 2 <= r * r] += rng.uniform(0.05, 0.2)
    return img + rng.normal(0, 0.1, (S, S))

def experts(N, rng):
    """N fixed rules, each 'disc' when one rectangle is brighter on average than another."""
    rects = []
    for _ in range(N):
        pair = []
        for _ in range(2):
            h, w = rng.integers(2, 7, 2)
            pair.append((rng.integers(0, S - h + 1), rng.integers(0, S - w + 1), h, w))
        rects.append(pair)
    def predict(img):
        m = [[img[y:y + h, x:x + w].mean() for y, x, h, w in pair] for pair in rects]
        return np.array([float(a > b) for a, b in m])
    return predict

def hedge(losses, beta):
    """Hedge(beta), Figure 1: uniform initial weights, w_i <- w_i * beta**loss_i."""
    w = np.full(losses.shape[1], 1 / losses.shape[1])
    total = 0.0
    for l in losses:
        p = w / w.sum()                           # allocation p^t
        total += p @ l                            # mixture loss p^t . l^t
        w = w * beta ** l
    return total

g = lambda z: 1 / (1 + np.sqrt(2 / z))            # Lemma 4
T, N = 2000, 64
beta = g(T / np.log(N))                           # L~ = T, the choice when only T is known
print(f"T = {T} patches, N = {N} experts, loss 1 for a wrong label, beta* = g(T/ln N) = {beta:.4f}")
print("            cumulative loss          loss minus the best expert's")
print("seed  best expert  mean expert   Hedge(beta*)  bound (9)  bound (11)  Hedge(0.5)  Hedge(0.99)")
for seed in range(5):
    rng = np.random.default_rng(seed)
    predict = experts(N, rng)
    labels = rng.random(T) < 0.5
    losses = np.array([np.abs(predict(patch(d, rng)) - d) for d in labels])  # T x N, in {0, 1}
    L = losses.sum(0)                             # cumulative loss of each expert
    b9 = (L.min() * np.log(1 / beta) + np.log(N)) / (1 - beta)
    b11 = L.min() + np.sqrt(2 * T * np.log(N)) + np.log(N)
    print(f"{seed:4d}  {L.min():11.0f}  {L.mean():11.1f}   " + "  ".join(
        f"{v - L.min():{w}.1f}" for v, w in ((hedge(losses, beta), 12), (b9, 9), (b11, 10),
                                            (hedge(losses, 0.5), 10), (hedge(losses, 0.99), 11))))

Output:

T = 2000 patches, N = 64 experts, loss 1 for a wrong label, beta* = g(T/ln N) = 0.9394
            cumulative loss          loss minus the best expert's
seed  best expert  mean expert   Hedge(beta*)  bound (9)  bound (11)  Hedge(0.5)  Hedge(0.99)
   0          535        987.8           70.2       85.5       133.1        11.6        249.5
   1          591       1031.0           68.3       87.3       133.1        37.9        246.3
   2          564       1025.7           72.1       86.5       133.1        12.2        271.4
   3          564        996.0           61.5       86.5       133.1        16.1        222.0
   4          553        999.0           61.7       86.1       133.1        28.7        240.8

Most rules are useless, with an average loss near 1,000 of 2,000, and the best of them still errs on 535–591 patches. With the paper’s $\beta$, Hedge ends 61.5–72.1 mistakes above the best rule on every seed, inside the hindsight bound (9), which allows 85.5–87.3, and the bound (11), which allows 133.1 knowing only $T$ and $N$. Dividing the stake equally, whose loss is the mean expert’s, would have cost 432–462 more than the best rule (the mean minus the best column). The bounds hold for any sequence, including one chosen by an adversary, and that is what they pay for: on this stationary stream a much smaller $\beta = 0.5$, which abandons bad rules quickly, comes within 11.6–37.9 mistakes of the best rule, while $\beta = 0.99$ moves so slowly that it loses 222.0–271.4 more. This is our reading of five runs, not a claim of the paper, which recommends tuning $\beta$ from prior knowledge of the problem (§2.2).

Versions

EuroCOLT 1995. The extended abstract appeared in the proceedings of EuroCOLT ’95 (Springer, pages 23–37), with the authors at AT&T Bell Laboratories. Its title is misspelled “desicion-theoretic” in the publisher’s page and in Crossref. We could not read its text, which Springer does not offer freely. Its abstract, as the publisher’s page gives it, covers on-line allocation, the applications and the new boosting algorithm; the manuscript’s abstract adds a sentence on extending the boosting algorithm to labels from a finite set or a bounded interval of the real line. Whether the conference text already contained AdaBoost.M1, M2 or R was not checked.

Journal of Computer and System Sciences 55(1), 1997. The cited version. The manuscript of 19 December 1996 has 35 pages: sections 1–5, the acknowledgments, 26 references and an appendix with the proof of Theorem 3. Whether the typeset article differs from it was not checked.

Naming. In the paper, AdaBoost is the binary algorithm with $\{0, 1\}$ labels and AdaBoost.M1 its first multiclass extension. Later accounts attach the M1 name to the binary algorithm: The Elements of Statistical Learning (§10.1) presents the two-class algorithm with labels $\pm 1$ as the algorithm Freund and Schapire (1997) called “AdaBoost.M1”, and Friedman, Hastie and Tibshirani (2000) describe their Discrete AdaBoost as essentially AdaBoost.M1 for binary data. With $k = 2$ and Boolean weak hypotheses the two coincide, apart from AdaBoost.M1 stopping when $\epsilon_t > \tfrac{1}{2}$ and the handling of ties (our reading of Figures 2 and 3).

Impact

Freund and Schapire received the 2003 Gödel Prize for this paper. The prize citation on ACM SIGACT’s page says the paper introduced AdaBoost and credits the algorithm’s elegance, simple implementation, wide applicability and striking success in reducing errors on benchmarks even though its theoretical assumptions are not known to hold; it adds that the algorithm set off an explosion of research in statistics, artificial intelligence, experimental machine learning and data mining.

Schapire (2013) calls AdaBoost the first practical boosting algorithm, and the paper’s analysis became the starting point for the explanations that followed. The VC analysis of §4.3 predicts that test error must eventually rise with the number of rounds; Schapire, Freund, Bartlett and Lee (1998) note that Quinlan and Breiman pointed out experiments contradicting this, in which test error kept falling after training error reached zero, and proposed in its place a bound based on the margins of the training examples that does not grow with $T$. Breiman, as Schapire (2013) credits him, first observed that AdaBoost’s choices minimize the exponential loss; Friedman, Hastie and Tibshirani (2000) developed this into a statistical view of boosting as forward stagewise additive modelling, and the view of boosting as functional gradient descent, which Schapire attributes to Mason and colleagues and to Friedman, extended it to other losses and to regression. The boosting article covers these explanations.

In computer vision the paper’s main descendant is the face detector of Viola and Jones (2001), which used AdaBoost in the $\{0, 1\}$ form of Figure 2, with a weak learner restricted to one Haar-like feature per round so that boosting also selected features, and placed the boosted classifiers in a cascade.

Limitations

• No experiments. The paper’s case for AdaBoost in practice rests on cited work.
• A training-set guarantee. Theorem 6 bounds error on the training distribution only, and is informative only while the weak learner keeps beating chance on every reweighted distribution, which the paper assumes rather than guarantees for any given hypothesis class. Its generalization bound grows with $T$, while the early experiments it reports showed little overfitting.
• Multiclass gaps. AdaBoost.M1 needs error below one half for $k > 2$, which the paper shows can be unattainable; AdaBoost.M2 needs a weak learner that minimizes a pseudo-loss, and its bound grows with $k - 1$. Some extensions are stated with their details omitted: confidence-rated hypotheses for AdaBoost.M1 and AdaBoost.R, and the factor-of-two improvement of the AdaBoost.M2 bound.
• Worst-case focus. Hedge’s bounds hold against an adversary, and the paper notes that superior algorithms or analyses are known in many of its specific applications.

Slips in the manuscript

By our reading of the manuscript, two statements are misprinted; the typeset version may differ.

• Example 3 (§3). The gap between Hedge’s average loss in a repeated game and the value of the game is said to decrease at the rate $O(1/\sqrt{T \log |\Delta|})$, which would shrink as the number of actions grows. Equation (12), with $N = |\Delta|$ and $\tilde{L} = T$, gives $O(\sqrt{(\log |\Delta|)/T})$.
• After Equation (22). The bound is described as a Chernoff bound on the probability that fewer than $T/2$ of $T$ coin tosses come up heads when heads has probability $\tfrac{1}{2} - \gamma$. That event is the likely one; $(1 - 4\gamma^2)^{T/2}$ bounds the probability of at least $T/2$ heads with that coin, or equivalently of fewer than $T/2$ heads when heads has probability $\tfrac{1}{2} + \gamma$.

What Came After

The repeated-game application of Hedge was developed in the authors’ COLT 1996 paper “Game Theory, On-Line Prediction and Boosting”, which the manuscript cites for details. For boosting, the line of work runs through the margin analysis of Schapire, Freund, Bartlett and Lee (1998), the statistical view of Friedman, Hastie and Tibshirani (2000), confidence-rated boosting, gradient boosting and the multiclass SAMME algorithm, all described in the boosting article, and into vision through boosted cascades for face detection and the Viola–Jones detector. Choosing the number of rounds on held-out data, the paper’s practical alternative to its own bounds, is also what The Elements of Statistical Learning recommends for gradient boosting (§10.12), by monitoring the error on a validation sample; cross-validation is the general form of the idea.