Defensive Boosting for Online Probabilistic Forecasting

The paper studies online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. "On each round t of an online probabilistic forecasting problem, an adversary reveals a context xt ∈ X, the learner announces a probability pt ∈ [0, 1] for the binary outcome Yt ∈ 0, 1, and the outcome is then revealed. The sequence may be arbitrary and adaptive to the learner's past predictions; we make no distributional assumptions. The forecast is scored by the Brier score (Yt − pt)2: the squared-error proper scoring rule, minimized in expectation by the true conditional probability that Yt = 1."

The paper addresses a gap between two existing approaches to online boosting:

1. Online gradient boosting (Beygelzimer et al., 2015a) "treats boosting as online convex optimization over combinations of weak hypotheses. Run with squared loss, it guarantees Brier score competitive with the best predictor in the convex hull of H, or more generally in the norm-bounded span. This guarantee is assumption free in that it holds on every sequence — but of course there is no guarantee that there is an accurate predictor in the span."

2. Online weak-to-strong boosting (Beygelzimer et al., 2015b; Chen et al., 2012) "instead obtains the 'AdaBoost phenomenon' in the online setting under a smooth weak-learning condition: every sufficiently smooth reweighting of the examples, meaning one whose weight is not concentrated on too few examples, admits a hypothesis with edge γ over random guessing... When the condition holds down to the smoothness needed for the target accuracy, boosting drives classification error to zero. The resulting classification accuracy can far exceed what squared-loss competition with the span of H alone guarantees. But when the weak-learning condition fails, these algorithms promise little, and their natural output is a weighted vote over an ensemble of predictors rather than a probability."

The central question: "whether a single, natural, efficient online algorithm, outputting probability forecasts, can enjoy both guarantees at once: the unconditional comparator guarantee of gradient boosting, and the conditional weak-to-strong guarantee of classification boosting."

The authors answer affirmatively with the Defensive Booster (Algorithm 1), built as a black-box reduction from an online learning algorithm for the weak class H.

On every adaptive sequence, for every f in the Λ-norm-bounded span of H, define qf(x) = (1 + f(x))/2. Then... BT ≤ (1/T)Σ(Yt − qf(xt))2 + O(Λ/√T). The bound is second-order — the regret term scales with the forecaster's own Brier score rather than with T — yielding a fast O(1/T) bound in the realizable span case (Corollary 4.2).

"If the realized transcript satisfies the (ρ, γ)-smooth weak-learning condition — every reweighting wt ∈ [0, 1] of the realized rounds with average weight at least ρ admits some h ∈ H with normalized edge at least γ — then the forecaster's Brier score and randomized classification error (1/T)ΣYt − pt are both at most max ρ, Õ(1/(γ2T)). Consequently, for any target ε > 0, if the weak-learning condition holds with ρ = O(ε), then both errors are at most ε after T = Õ(1/(γ2ε)) rounds."

"If the forecaster's error remains large for long enough, its mistake weights wt = Yt − pt form a hard-core witness: a smooth reweighting of the realized rounds on which every weak hypothesis has low edge. Thus persistent error explicitly certifies that the weak-learning condition fails on the realized transcript."

"A variant using O(log T) active copies of the same weak-class oracle satisfies both guarantees, up to polylogarithmic factors, simultaneously on every contiguous interval. On each interval it competes with the best span comparator for that interval; if the smooth weak-learning condition holds on the interval, it obtains the strong-learning guarantee there. It also localizes the certificate above: whenever error remains large on an interval, the mistake weights restricted to that interval form a local hard-core witness."

"Neither guarantee implies the other. In one direction, for arbitrarily small constants γ > 0, there are binary-valued weak classes and transcripts on which every reweighting has edge at least γ — so the weak-to-strong guarantee forces vanishing Brier score and randomized error — yet every score induced by the span has squared loss bounded below by a constant. For every fixed coefficient-norm budget, a constant lower bound also remains after clipping the scores to valid probabilities. Conversely, there are transcripts with an arbitrarily small-loss comparator in the span but a smooth reweighting on which every weak hypothesis has zero edge, so the smooth weak-learning condition fails."

The key insight is operationalizing the dual view of boosting. The paper explains: "Existing online weak-to-strong boosting operationalizes the primal view: run many copies of the weak learner in parallel and learn a weighted combination of their predictions. We operationalize the dual view. Our forecaster never forms an ensemble: it maintains one online learner for H and two scalar adaptive-gradient states, for a per-round cost of one oracle call plus O(1) arithmetic."

The algorithm is built on defensive forecasting principles: rather than minimizing a loss, the forecaster chooses pt so that a designated family of statistical tests — auditors — cannot accumulate evidence that the forecasts differ from true probabilities. Two types of auditors are used:

1. Weak-class auditor: enforces multiaccuracy with respect to H: hypotheses h ∈ H should have small empirical correlation with the residuals rt.

2. Self-auditor: enforces self-orthogonality: the forecast µt itself should have small empirical correlation with its own residuals.

The algorithm maintains "a convex combination of the auditors, which we call the aggregated auditor. On each round the forecast µt is chosen by a one-dimensional root rule: a point where the aggregated auditor gain, viewed as a function of the forecast, changes sign, so that the realized gain is nonpositive no matter how the label is realized (Lemma 3.2)."

The key theoretical guarantee (Theorem 3.3) shows that "On every sequence, sup h∈H Σ t h(xt)rt — multiaccuracy — and Σ t µt rt — self-orthogonality — are each at most A√ST + B, with its own constants determined by the corresponding online-learning primitive, where ST = Σ t rt2 is the residual energy."

The hard-core argument works as follows: "The residuals describe the forecaster's own randomized classification mistakes. Identify the forecast pt with the randomized classifier that predicts 1 with probability pt. Its conditional mistake probability is wt = Yt − pt, and these mistake weights satisfy the key identity wtσt = rt/2. Interpret wt as weights for a reweighting of the transcript. Their 'density' ρw = T−1Σ t wt is exactly the randomized classification error, while the identity converts multiaccuracy into an edge bound for the mistake weighting: no weak hypothesis correlates nontrivially with it. So if the forecaster's randomized error is large enough for w to be smooth, then w is a smooth reweighting of the transcript on which no weak learner has nontrivial 'edge' over random guessing — exactly the kind of winning strategy for the data player that the smooth weak-learning condition rules out."

For the span guarantee: "it is known that multiaccuracy with respect to H together with self-orthogonality gives squared error competitive with every model in the span of H: these are exactly the first-order optimality conditions for squared loss... For a span comparator f, the excess squared loss of our forecasts over f is controlled by two correlation terms: the residuals against f, which multiaccuracy bounds because f is a linear combination of weak hypotheses, and the residuals against our own forecasts, which self-orthogonality bounds."

The Defensive Booster (Algorithm 1) works as follows:

• Initialize the weak-class oracle over H and two independent copies S (the self-auditor state) and A (the auditor-aggregation state) of scalar adaptive OGD.

• On each round: "Observe xt. Obtain ĥt ∈ [−1, 1] from the weak oracle, θt ∈ [−1, 1] from S, and λt ∈ [−1, 1] from A. Set qH,t = (1 + λt)/2 and qS,t = (1 − λt)/2. Form Ft(µ) = qH,tĥt + qS,tθtµ and set µt = Root(Ft). Forecast pt = (1 + µt)/2."

• After observing Yt: Set σt = 2Yt − 1 and rt = σt − µt. Set zH,t = ĥtrt, zS,t = θtµtrt, ut = µtrt, and vt = (zH,t − zS,t)/2. Update the weak-class oracle with ct = rt, update S with ut, and update A with vt.

The algorithm is very efficient: Since Ft is affine, the root is computed in constant time... The per-round cost is one oracle prediction/update plus O(1) arithmetic.

The algorithm requires a second-order weak-class oracle for H (Definition 2.3): On round t, after observing xt but before seeing a coefficient ct ∈ [−2, 2], it outputs ĥt ∈ [−1, 1]. For every horizon T and every resulting sequence, it guarantees sup h∈H Σ ct h(xt) − Σ ct ĥt ≤ aH√(Σ c2t) + bH.

The paper notes: "The assumption has standard instantiations. If H is finite, a second-order experts algorithm with one expert per h ∈ H gives aH = O(√logH) and bH = O(logH). More generally, adaptive or scale-free online linear optimization over conv(H) gives data-dependent regret in terms of cumulative gradient norms."

The paper evaluates the Defensive Booster on synthetic and real data streams:

1. Binary aggregation stream: "The weak class contains 200 binary hypotheses, arranged as 100 opposite pairs ±hj... No single rule is perfect, and averaging all 200 displayed rules gives zero. The hidden average, however, has signed margin at least 2(.58) − 1 =.16 on every round and therefore classifies perfectly. Results: Online BBM reaches hard-prediction error.0041, AdaBoost.OL reaches.0042, and OSBoost reaches.0068. The Defensive Booster reaches.0026, compared with.0331 for OGB and.1829 for the unboosted classifier, while using one learner rather than 100. Its Brier loss is.0018, below every individual ensemble and the.0025 loss of the Brier aggregator."

2. Random-label mixture stream: "Here the contexts are normalized vectors in R30 and the weak class is the infinite Euclidean linear class H = x ↦ ⟨u, x⟩: ∥u∥2 ≤ 1. Independently on each round, with probability.65 the label follows a fixed noisy linear rule and with probability.35 it is an independent random bit. Results: OGB and the Defensive Booster have Brier losses.1933 and.1965, respectively, while OSBoost, AdaBoost.OL, and Online BBM have losses.2467,.2708, and.2963."

The paper evaluates on four public binary datasets: Bank Marketing, Electricity, Airlines, and Occupancy. Key findings: "The Defensive Booster has the lowest Brier loss on Electricity and Occupancy by a wide margin, and it also has the lowest deterministic error on Occupancy... On Bank, the Brier aggregator is best by.0010 over the Defensive Booster. On Airlines, the Defensive Booster, OGB, and the aggregator differ by less than 6·10−5."

The paper extends to bounded real-valued outcomes: the Defensive Booster's span guarantee is satisfied in the exact same way as in the binary setting. On three regression datasets (Appliance Energy, Bike Demand, Interstate Traffic): the Defensive Booster reduces normalized MSE relative to OGB by 18% on Appliance Energy, 29% on Bike Demand, and 17% on Interstate Traffic.

The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. The ensemble baselines take 20–66× as much time per round in the binary experiments, and OGB takes 65–70× as much wall-clock time per round in the regression experiments.

The paper connects to multiple research areas: online gradient boosting, online weak-to-strong boosting, AdaBoost as loss optimization, strong adaptivity, smooth boosting and hard-core sets, multicalibration/multiaccuracy/loss minimization, multicalibration and hard-core measures, and defensive forecasting. Notably: To our knowledge, ours is the first online boosting theorem obtained this way [through defensive forecasting]. Its additional structure yields the span guarantee and the hard-core mistake weighting.

Based on this paper, here are the specific improvements I can make to AI systems:

Improvement: I can build a forecaster that simultaneously guarantees (a) competitiveness with the best predictor in a hypothesis span (unconditional) and (b) strong learning when a smooth weak-learning condition holds (conditional), without needing to know which regime applies in advance.

What the improved system can do: An AI system that makes probability forecasts on arbitrary adversarial sequences, and provably performs well whether the data is easy (has a good linear combination of weak predictors) or structured (has weak learners with edge under smooth reweightings). It never fails catastrophically in either regime.

Improvement: I can implement a forecaster that continuously audits its own predictions against two families of tests (weak-class correlations and self-correlations), and when its error stays high, it explicitly outputs a reweighting of the data that certifies why it cannot do better.

Improvement: I can use the second-order regret bound (regret scales with the forecaster's own Brier score, not with T) to achieve O(1/T) convergence in realizable settings, rather than O(1/√T).

Improvement: I can run O(log T) active copies of the same weak-class oracle to achieve per-interval guarantees simultaneously on all contiguous time intervals, with only polylogarithmic overhead.

Improvement: I can replace the ensemble of many weak learners (used in prior online boosting) with a single online learner plus two scalar adaptive-gradient states, reducing per-round cost from O(K) oracle calls to O(1).

Improvement: I can extend the defensive boosting framework to bounded real-valued outcomes, preserving the span guarantee and achieving lower normalized MSE than online gradient boosting.

Improvement: I can detect when the smooth weak-learning condition fails (via the hard-core certificate) and automatically switch to a fallback strategy (e.g., span-based prediction) rather than continuing to boost blindly.

Improvement: I can enforce multiaccuracy with respect to the weak class and self-orthogonality simultaneously, which guarantees calibrated probability forecasts that are competitive with any span model.