Defensive Boosting for Online Probabilistic Forecasting

Overview§

The paper introduces the Defensive Booster, an online probabilistic forecasting algorithm for binary outcomes chosen by an adaptive adversary. It unifies two previously separate online boosting paradigms: online gradient boosting (which competes with the best predictor in the span of a weak hypothesis class $H$ in terms of Brier score) and online weak-to-strong boosting (which drives classification error to zero under a weak-learning condition). The Defensive Booster obtains both guarantees simultaneously on every sequence, using only a single weak learner, and is orders of magnitude faster than prior ensemble-based methods.

Core Methodology§

The algorithm operationalizes the dual view of boosting: boosting can be seen both as functional gradient descent (primal) and as finding a distribution (dual) on which weak learners have low edge. The key insight is a defensive forecasting mechanism that maintains a distribution over past examples. If a learner's randomized classification error remains high, the induced distribution becomes a hard-core certificate — a smooth reweighting on which every weak hypothesis has low edge — proving that the weak-learning condition fails.

The algorithm updates a weight vector $w_t$ over past rounds. At each round $t$:

1. Receive instance $x_t$ from adversary.
2. Query the weak learner with weights $w_t$ to obtain hypothesis $h_t \in H$.
3. Predict $\hat{y}_t = \sigma(u_t)$ where $u_t$ is an aggregated score (e.g., sum of weak learner outputs), and $\sigma$ is the logistic sigmoid.
4. Observe binary outcome $y_t$.
5. Update weights multiplicatively: $w_{t+1}(i) \propto w_t(i) \cdot e^{-\eta (h_t(x_i) - y_i)}$ for all previous rounds $i$, and add a new weight for the current round.

The algorithm is strongly adaptive: it maintains a hierarchical set of intervals and runs a base version on each, achieving guarantees on every time interval.

Theoretical Guarantees§

For any sequence of length $T$, with probability at least $1-\delta$ (over the learner's internal randomness), the Defensive Booster achieves:

$$ \sum_{t=1}^T (\hat{y}_t - y_t)^2 \leq \min_{f \in \text{span}(H)} \sum_{t=1}^T (f(x_t) - y_t)^2 + O\left(\sqrt{T \log T} + \log\frac{1}{\delta}\right) $$

Simultaneously, if the transcript satisfies the smooth weak-learning condition (i.e., there exists a $\gamma$-edge weak learner over a reweighted distribution), then the algorithm's Brier score and average classification error are bounded by:

$$ \frac{1}{T} \sum_{t=1}^T (\hat{y}_t - y_t)^2 \leq \frac{1}{T} \sum_{t=1}^T \mathbb{1}[\hat{y}_t \neq y_t] \leq \epsilon + O\left(\sqrt{\frac{\log T}{T}}\right) $$

where $\epsilon$ depends on the weak-learning condition strength.

Code Sketch§

A simplified PyTorch-like implementation of the core update:

import torch

def defensive_booster_predict(weak_learner, X, y, eta=0.1, T=1000):
    # Maintain weights over past rounds
    W = torch.ones(1)  # initial weight for round 1
    u = 0.0  # cumulative score
    
    for t in range(T):
        x_t = X[t]
        # Get weak hypothesis output
        h_t = weak_learner.predict(x_t)  # scalar in [-1, 1]
        u += eta * h_t
        p = torch.sigmoid(torch.tensor(u)).item()
        
        # Observe true label
        y_t = y[t]
        
        # Update weights: w_{t+1}(i) = w_t(i) * exp(-eta * h_t(x_i) * y_i)
        # In practice, store past examples and weights, then reweight
        W = W * torch.exp(-eta * h_t * y_t).item()
        W = torch.cat([W, torch.ones(1)])
        
        yield p

In practice, the algorithm uses a more sophisticated reweighting that avoids storing all past data via a reservoir or online convex optimization tricks, but the essence is a multiplicative weights update where the weak learner is trained on the reweighted past examples.

Experimental Results§

The Defensive Booster is evaluated on synthetic and real data streams. It matches or improves Brier score over prior online gradient boosting methods (e.g., Online Gradient Boosting, Weak-to-Strong Boosting) while being orders of magnitude faster — often 10-1000x speedup — because it uses a single weak learner instead of an ensemble. On several benchmarks (e.g., credit card fraud detection, electricity demand), it reduces both log loss and classification error.

Significance§

The paper provides a clean theoretical unification of two disjoint boosting paradigms and demonstrates that defensive forecasting is a powerful algorithmic primitive. The practical benefits—efficiency, single learner, and dual guarantees—make it an attractive choice for streaming prediction tasks where adversarial robustness is desired.