Defensive Boosting for Online Probabilistic Forecasting

Defensive Boosting for Online Probabilistic Forecasting Georgy Noarov

Aaron Roth

arXiv:2608.13554v1 [cs.LG] 13 Aug 2026

Abstract We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class H, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of H on every sequence — but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weaklearning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of H at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the dual view of boosting: When the Defensive Booster’s randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees and provides local hard-core certificates on every time interval. 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. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

1

Introduction

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. We study this problem through the lens of boosting. The learner is given an online learning algorithm for simple, “weak” probability predictors and wants to make forecasts that are more accurate than any weak learner can make alone. There are two established ways to turn an online weak learner into a stronger one, and they come with incomparable guarantees. To put both guarantees in common notation, encode a weak prediction q(x) ∈ [0, 1] as h(x) = 2q(x)−1 ∈ [−1, 1], and let H denote the resulting class; likewise, encode Yt as σt = 2Yt − 1. This normalization is useful for binary classification because it expresses classification advantage as correlation between h(xt ) and σt . 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 1

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. 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. P With the encoding P above, the edge of h under weights wt is its normalized weighted correlation | t wt σt h(xt )|/ t wt . For a binary-valued weak learner, edge γ is equivalent, after possibly flipping its sign, to weighted classification error at most (1 − γ)/2. 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. This paper asks 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.

1.1

Our results

We answer affirmatively with a simple, efficient algorithm — the Defensive Booster (Algorithm 1) — built as P a black-box reduction from an online learning algorithm for the weak class H. Write 2 −1 BT = T t≤T (Yt − pt ) for its average Brier score. Our main guarantees, stated informally, follow. First, we unconditionally obtain the same guarantee as online gradient boosting, at the same rate: Informal Theorem (Gradient-boosting-style span guarantee; Theorem 4.1). On every adaptive sequence, for every f in the Λ-norm-bounded span of H, define qf (x) = (1 + f (x))/2. Then   T 1X Λ 2 BT ≤ (Yt − qf (xt )) + O √ . T T t=1 Here qf = (1 + f )/2 reverses the affine encoding above and, for a general span comparator, is an unrestricted real-valued score. The actual 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). Next, we simultaneously obtain the guarantee of online weak-to-strong boosting, transforming a smooth weak-learning condition into perfect classification with the same γ, ε dependence that is optimal in the weak-online-learning model of Beygelzimer et al. (2015b): Informal Theorem (Weak-to-strong boosting guarantee; Corollary 4.5). 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 P the forecaster’s Brier score and randomized classification error T1 Tt=1 |Yt − pt | are both at most max{ρ, Õ(1/(γ 2 T ))}. Consequently, for any target ε > 0, if the weak-learning condition holds with ρ = O(ε), then both errors are at most ε after T = Õ(1/(γ 2 ε)) rounds. Thresholding each forecast at 1/2 gives a deterministic classifier whose average 0/1 error is at most twice the randomized error. 2

The weak-to-strong guarantee has a complementary certificate (Theorem 4.4). 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. Both guarantees can also be made strongly adaptive. 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 (Section 5). 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. Because the interval may be chosen after observing the transcript, this identifies where and when the smooth weak-learning condition fails, even if the condition holds on the full sequence. The two guarantees are genuinely different: neither implies the other, and prior work that provides either guarantee in isolation does not provide both. Informal Proposition (Separation; Appendix B). 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. We also evaluate the Defensive Booster empirically (Section 6): on synthetic datasets engineered to favor either gradient boosting or weak-to-strong classification boosting, and on four real binary prediction datasets. The stronger baseline family depends on the instance: gradient boosting can substantially outperform weak-to-strong boosting, and vice versa. On every instance, the Defensive Booster is competitive with, and often outperforms, the stronger baseline, while the ensemble baselines take 20–66× as much time per round: it maintains one online weak learner, whereas they each maintain 100. A more naive alternative is to run instances of each kind of comparison booster in parallel and combine their probability forecasts with an online aggregator such as multiplicative weights. We include this method as a baseline. It must run every constituent booster, while the Defensive Booster runs one weak-class learner. Moreover, aggregation by Brier loss gives a weaker classification-error P −1 guarantee: a Brier guarantee controls randomized classification error only through T t |Yt − √ √ pt | ≤ BT , so an O(ε) Brier guarantee yields only O( ε) randomized error, whereas the Defensive Booster directly guarantees O(ε) under the smooth weak-learning condition. The aggregation scheme also provides no hard-core witness. Finally, we note that our algorithm also handles arbitrary bounded real-valued outcomes, and its squared-loss span guarantee holds unchanged, just as it does in the binary setting. Appendix D describes this in more detail, and evaluates this extension on three chronological regression streams.

1.2

Technique: playing the dual side of the boosting game

The boosting game and its two views. In the batch setting, weak-to-strong boosting can be viewed as a zero-sum game between a learner player, who plays distributions over the weak class H, and a data player, who plays reweightings of the dataset (Freund and Schapire, 1996). A winning strategy for the learner player is a distribution over weak hypotheses whose weighted majority vote 3

attains perfect classification. A winning strategy for the data player is a hard-core distribution: a reweighting of the data on which no weak hypothesis has nontrivial edge (Impagliazzo, 1995). The weak learning assumption says that the data player has no sufficiently smooth winning strategy, and minimax duality then supplies a winning majority vote for the learner player. 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 (Beygelzimer et al., 2015b; Chen et al., 2012). 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. It makes probability forecasts that are — in particular — multiaccurate with respect to H (Hébert-Johnson et al., 2018; Kim et al., 2019): no weak hypothesis correlates with its forecast residuals. Multiaccuracy implies that weighting each round by the forecaster’s randomized prediction error yields a hard-core distribution for H. This is the same correlation-to-hard-core principle underlying the complexity-theoretic regularity lemma of Trevisan et al. (2009) — see also recent work deriving related guarantees from strengthenings of multiaccuracy like calibrated multiaccuracy and multicalibration (Casacuberta et al., 2024, 2025). If the prediction error is high, the weights are large on average and so this hard-core distribution is smooth in the standard boosting sense. If the smooth weak-learning condition holds — weak hypotheses have nontrivial edge on every smooth reweighting — no such distribution exists. By contrapositive, the randomized classification error must be low. The remainder of this subsection makes each step concrete. Defensive forecasting with orthogonality auditors. Using the encoding above, write µt = 2pt − 1 for the signed forecast and rt = σt − µt = 2(Yt − pt ) for the residual. The design principle is defensive forecasting (Vovk et al., 2005b): 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. We use two kinds of auditors. A weak-class auditor enforces multiaccuracy with respect to H: hypotheses h ∈ H should have small empirical correlation with the residuals rt . A self-auditor enforces self-orthogonality: the forecast µt itself should have small empirical correlation with its own residuals. Self-orthogonality is implied by, but substantially weaker than calibration, which is important, as calibration is impossible to obtain in the online setting at the rates we desire (Dagan et al., 2025; Qiao and Valiant, 2021). An adaptive-gradient procedure 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); this is a simple instantiation of the more general P framework recently introduced byPFarina and Perdomo (2026). On every sequence, sup √h∈H | t h(xt )rt | — multiaccuracy — and | t µt rt | — self-orthogonality — are each at most A ST + B, P with its own constants determined by the corresponding online-learning primitive, where ST = t rt2 is the residual energy (Theorem 3.3). High error yields a smooth hard-core witness. 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 σtP= 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

4

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. By contrapositive, the forecaster must have sufficiently low error to avoid this contradiction, and this is what turns the weak-learning condi√ tion into a strong-learning guarantee. The self-bounding form of the certificate (error term ST , with ST ≤ 4T ρw ) turns this qualitative contradiction into the target 1/(γ 2 ε) rate (Theorem 4.4). Self-orthogonality is not used in this part of the argument; the hard-core conclusion follows from multiaccuracy alone. Adding self-orthogonality gives the span guarantee. On the other hand, 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 (see e.g. its use in (Kearns et al., 2025)). 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. Self-orthogonality is one additional scalar constraint, enforced by one additional auditor at no cost in the rate, and the result is Brier loss competitive with the best predictor in the span on every sequence (Theorem 4.1). Empirical preview. Figure 1 previews the real-data behavior for both binary probability forecasting and bounded regression; the main comparisons are in Section 6, and the full protocol and additional experiments are in Appendices C–E. The binary baselines are OGB (Beygelzimer et al., 2015a) for online gradient boosting; Online BBM and AdaBoost.OL (Beygelzimer et al., 2015b) and OSBoost (Chen et al., 2012) for online weak-to-strong boosting; and a Brier-loss aggregator that combines the four ensemble forecasts by multiplicative weights. The regression comparison is with OGB, the baseline providing the corresponding squared-loss span guarantee. Organization. Section 2 defines the setting, the weak-class oracle, and the fixed scalar update. Section 3 gives the algorithm and the multiaccuracy/self-orthogonality certificate. Section 4 derives the Brier/span guarantee, the hard-core mistake weighting, and the weak-to-strong corollary. Section 5 gives a strongly adaptive variant whose guarantees hold on every interval. Section 6 reports synthetic and real-data experiments, and Section 7 discusses related work. Appendix B proves that the two guarantees are incomparable. Appendix C gives complete details for the binary prediction experiments. Appendix D extends the algorithm and its squared-loss span guarantee to bounded real-valued outcomes, and reports the regression experiments. Finally, Appendix E evaluates the strongly adaptive variant.

2

Setting and algorithmic ingredients

The interaction is adversarial and sequential. On round t, the environment reveals a context xt ∈ X . The learner predicts pt ∈ [0, 1], interpreted as the probability of outcome 1. The environment then reveals Yt ∈ {0, 1}, and the learner suffers Brier loss (Yt − pt )2 . The sequence may be adaptive to the learner’s past predictions. We use binary outcomes for the probability and classification interpretations; Appendix D generalizes to outcomes in [0, 1]. The weak class H uses the [−1, 1] encoding introduced above and consists of functions h : X → [−1, 1]. We write σt = 2Yt − 1,

µt = 2pt − 1, 5

rt = σt − µt = 2(Yt − pt ).

Figure 1: Empirical preview (details in Section 6). Top: For each of four naturally ordered real binary streams, each method’s Brier loss is divided by the smallest loss among the methods shown. The Defensive Booster has the lowest Brier loss on Electricity and Occupancy, where it substantially outperforms even the 400-learner aggregator. It essentially ties the aggregator and OGB on Airlines and is within .0010 of the aggregator on Bank, while maintaining one weak-class learner. The hardlabel unboosted classifier is omitted for scale and reported in Table 1. Bottom (see Appendix D.1): On three chronological bounded-regression streams, mean squared error is divided by the smaller loss of the Defensive Booster and OGB. The Defensive Booster reduces mean squared error by 17–29% while maintaining one weak learner rather than 100. In both panels lower is better, dashed lines mark the best plotted value, and parentheses give the number of maintained online weak learners. Thus µt is the [−1, 1]-scaled forecast corresponding to the probability forecast pt . Definition 2.1 (Multiaccuracy and self-orthogonality). For a realized forecast sequence, let rt = σt − µt denote the residual. The forecasts are α-multiaccurate with respect to H if sup

T X

h(xt )rt ≤ α.

h∈H t=1

They are β-self-orthogonal if T X

µt rt ≤ β.

t=1

6

After the affine encoding above, these are empirical versions of the squared-loss orthogonality conditions used in e.g. Kearns et al. (2025): multiaccuracy tests the residuals against an external class of functions, while self-orthogonality tests the residuals against the forecast itself. We assume H is symmetric: if h ∈ H, then −h ∈ H. Otherwise one replaces H by H ∪ (−H) and runs the weak learner on both signs. Definition 2.2 (Norm-bounded span). For Λ ≥ 0, the Λ-norm-bounded span of H is   m m   X X spanΛ (H) = f = αj hj : m < ∞, hj ∈ H, |αj | ≤ Λ .   j=1

j=1

The convex hull of H is contained in span1 (H). For every span comparator f , write qf (x) =

1 + f (x) . 2

This is the affine rescaling of f to the {0, 1} outcome scale on which Brier loss is measured. Since f need not take values in [−1, 1], qf need not lie in [0, 1]. The algorithm has one problem-dependent online primitive: a weak-class oracle for H. We ask for a second-order regret guarantee, meaning√that regret scales with the square root of the cumulative squared coefficients rather than with T . The coefficients supplied to the oracle will be thePforecaster’s residuals, so this gives a certificate whose error scales with the residual energy ST = t (σt − µt )2 itself. This self-bounding√structure produces the 1/(γ 2 ε) weak-to-strong sample complexity in Corollary 4.5; a first-order T guarantee would give only 1/(γ 2 ε2 ). The former dependence matches the rate shown optimal in the prior weak-online-learning model (Beygelzimer et al., 2015b), although our oracle model is stronger. Definition 2.3 (Second-order weak-class oracle). A second-order weak-class oracle for H has fixed constants aH , bH ≥ 0. On round t, after observing xt but before seeing a coefficient ct ∈ [−2, 2], it outputs b ht ∈ [−1, 1]. For every horizon T and every resulting sequence, it guarantees v u T T T uX X X sup ct h(xt ) − ctb ht ≤ aH t c2t + bH . (1) h∈H t=1

t=1

t=1

The loss-minimization convention is obtained by replacing ct by −ct . The assumption has standard instantiations. If H is finite, a second-order experts algorithm p with one expert per h ∈ H gives aH = O( log |H|) and bH = O(log |H|) (Cesa-Bianchi et al., 2007). More generally, adaptive or scale-free online linear optimization over conv(H) gives datadependent regret in terms of cumulative gradient norms (Kivinen et al., 2004; Orabona and Pál, 2018; Zinkevich, 2003). For example, for the RKHS ball HB = {x 7→ ⟨u, ϕ(x)⟩ : ∥u∥ ≤ B} with qP 2 ∥ϕ(x)∥ ≤ κ and Bκ ≤ 1, these methods give O(Bκ t ct ) regret up to lower-order terms. All remaining online machinery is class independent. We use two copies of the following fixed one-dimensional routine. Definition 2.4 (Scalar adaptive OGD). Initialize a1 = 0 and V0 = 4. On round t, output at ∈ [−1, 1]. After observing a coefficient gt ∈ [−2, 2], update   gt at+1 = Π[−1,1] at + √ , Vt = Vt−1 + gt2 , Vt−1 where Π[−1,1] denotes Euclidean projection onto [−1, 1]. 7

Lemma 2.5 (Second-order scalar regret). Scalar adaptive OGD satisfies, for every a ∈ [−1, 1], v v u u T T T u uX X X t 2 (a − at )gt ≤ 4 4 + gt ≤ 4t gt2 + 8. t=1

t=1

t=1

The proof is given in Appendix A.1.

3

The Defensive Booster

The Defensive Booster combines the weak-class oracle with two copies of the fixed scalar adaptiveOGD routine. The only forecasting step is a one-dimensional root rule on the signed mean µt . The labels of the two scalar states describe their roles: S controls the self-auditor used to establish self-orthogonality, while A aggregates the weak-class and self auditors. Definition 3.1 (Root rule). For a continuous function F : [−1, 1] → R, let Root(F ) be any point selected as follows: (i) if F has a zero in [−1, 1], return any such zero; (ii) if F is positive throughout [−1, 1], return 1; (iii) if F is negative throughout [−1, 1], return −1. Continuity ensures that exactly one of these cases applies. Lemma 3.2 (Root sign property). For every continuous F : [−1, 1] → R, every signed label σ ∈ [−1, 1], and µ = Root(F ), F (µ)(σ − µ) ≤ 0. Proof. If F (µ) = 0, the claim is immediate. If F is positive throughout the interval, then µ = 1 and σ − µ ≤ 0. If F is negative throughout, then µ = −1 and σ − µ ≥ 0. Algorithm 1 Defensive Booster 1: 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 (Definition 2.4). 2: for t = 1, 2, . . . do 3: Observe xt . Obtain b ht ∈ [−1, 1] from the weak oracle, θt ∈ [−1, 1] from S, and λt ∈ [−1, 1] from A. 4: Set qH,t = (1 + λt )/2 and qS,t = (1 − λt )/2. 5: Form Ft (µ) = qH,tb ht + qS,t θt µ and set µt = Root(Ft ). ▷ Definition 3.1 6: Forecast pt = (1 + µt )/2. 7: Observe Yt ∈ {0, 1}; set σt = 2Yt − 1 and rt = σt − µt . 8: Set zH,t = b ht rt , zS,t = θt µt rt , ut = µt rt , and vt = (zH,t − zS,t )/2. 9: Update the weak-class oracle with ct = rt , update S with ut , and update A with vt . 10: end for Since Ft is affine, the root is computed in constant time: return −qH,tb ht /(qS,t θt ) when this ratio is defined and lies in [−1, 1], return 0 when Ft is identically zero, and otherwise return the endpoint prescribed by Definition 3.1. The per-round cost is one oracle prediction/update plus 8

O(1) arithmetic. The resulting forecast need not be a linear combination or weighted vote of weak hypotheses: the algorithm predicts a probability directly rather than maintaining an explicit ensemble. The algorithm can be viewed as a simple one-dimensional, deterministic instance of the online-learning and variational-inequality framework of Farina and Perdomo (2026): their forecastdependent variational inequality is solved here by an exact root of the affine function Ft . Multiaccuracy and self-orthogonality guarantees. The weak-class and self auditors have gains zH,t = b ht rt and zS,t = θt µt rt . The scalar state A chooses their convex weights: writing vt = (zH,t − zS,t )/2, its two endpoint comparators λ = 1 and λ = −1 correspond exactly to always selecting the weak-class auditor and the self auditor, respectively. The root rule makes the resulting weighted gain nonpositive on every round, regardless of the label. Lemma 2.5 therefore forces each auditor’s cumulative gain to be small. The weak-class oracle transfers this to multiaccuracy, while the scalar state S transfers √ the self-auditor bound to self-orthogonality. Since |ut |, |vt | ≤ |rt |, every error term scales with ST . Theorem 3.3 (Second-order multiaccuracy and self-orthogonality). For every adaptive sequence with Yt ∈ {0, 1}, let T T X X ST = (σt − µt )2 = 4 (Yt − pt )2 . t=1

t=1

√

The Defensive Booster (Algorithm 1) is (AH ST + BH )-multiaccurate with respect to H: T X

sup

h(xt )(σt − µt ) ≤ AH

p ST + BH

h∈H t=1

√ and (AS ST + BS )-self-orthogonal: T X

µt (σt − µt ) ≤ AS

p ST + BS ,

BH = bH + 8,

AS = 8,

t=1

where AH = aH + 4, Proof. Let z̄t =

zH,t + zS,t , 2

vt =

BS = 16.

zH,t − zS,t . 2

The gain selected by A is z̄t + λt vt = qH,t zH,t + qS,t zS,t = Ft (µt )(σt − µt ) ≤ 0 by Lemma 3.2. Competing in Lemma 2.5 with λ = 1 and λ = −1 gives, respectively, v u T T T u X X X t zH,t − (z̄t + λt vt ) ≤ 4 4 + vt2 t=1

t=1

t=1

and the same bound with zS,t in place of zH,t . Since |vt | ≤ |rt | and the selected cumulative gain is nonpositive, T T X X p zH,t , (2) zS,t ≤ 4 ST + 8. t=1

t=1

9

The weak-class oracle is updated with ct = rt . Hence, for every h ∈ H, T X

h(xt )rt ≤

t=1

T X

b ht rt + aH

p p ST + bH ≤ (aH + 4) ST + bH + 8.

t=1

Symmetry of H gives the absolute-value multiaccuracy bound. For self-orthogonality, S is updated with ut = µt rt . For every θ ∈ [−1, 1], Lemma 2.5 and (2) give v u T T T u X X X p t θµ r ≤ θ µ r +4 4+ µ2 r2 ≤ 8 S + 16. t t

t t t

t=1

T

t=1

Taking the supremum over θ ∈ [−1, 1] yields |

4

t t

t=1

P

t µt rt |.

Main guarantees

This section derives the paper’s guarantees from the two inequalities in Theorem 3.3. They are parallel consequences, not consequences of one another: the hard-core statement uses multiaccuracy alone, whereas the span statement also uses self-orthogonality. Section 4.1 gives the Brier/spanregret guarantee, which holds on every sequence. Section 4.2 shows that the multiaccuracy bound controls the edge of the forecaster’s own mistake weighting. Section 4.3 turns the edge bound into the weak-to-strong boosting statement. Appendix B gives examples showing that the two guarantees are incomparable.

4.1

Brier/span-regret guarantee

Theorem 4.1 (Brier/span guarantee). For every adaptive binary sequence, the predictions of the Defensive Booster (Algorithm 1) satisfy, for every f ∈ spanΛ (H), BT :=

T

T

t=1

t=1

1X ΛBH + BS 1X ΛAH + AS p √ BT + (Yt − pt )2 ≤ (Yt − qf (xt ))2 + . T T 2T T

In particular, since BT ≤ 1, T

BT ≤

ΛAH + AS ΛBH + BS 1X √ (Yt − qf (xt ))2 + + . T 2T T t=1

The same bound holds for every f ∈ conv(H) with Λ = 1. Proof. Let rt = σt − µt . Convexity of µ 7→ (σt − µ)2 gives (σt − µt )2 ≤ (σt − f (xt ))2 + 2rt (f (xt ) − µt ). If f =

Pm

j=1 αj hj with

P

j |αj | ≤ Λ, Theorem 3.3 gives T X

f (xt )rt ≤ Λ(AH

t=1

10

p ST + BH ).

The same theorem gives | convexity inequality gives ST ≤

P

t µt rt | ≤ AS

T X

√

ST + BS . Substituting these two bounds into the signed

(σt − f (xt ))2 + 2(ΛAH + AS )

p ST + 2(ΛBH + BS ).

t=1

Divide by 4T and use ST = 4T BT and (σt − f (xt ))2 = 4(Yt − qf (xt ))2 . Since BT ≤ 1, the second bound follows. Corollary 4.2 (Low-loss span guarantee). In the setting of Theorem 4.1, write T

1X Bf = (Yt − qf (xt ))2 , T

C = ΛAH + AS ,

D = ΛBH + BS .

t=1

Then

r BT ≤ Bf + C

Bf 3C 2 3D + + . T 2T 4T

In particular, if Bf = 0, then BT = O((C 2 + D)/T ). The proof is given in Appendix A.2.

4.2

The hard-core mistake weighting

Definition 4.3 (Reweighting, smoothness, and edge). A reweighting of the realized transcript is a sequence wt ∈ [0, 1]. Its density is T 1X ρ(w) = wt . T t=1 P For ρ > 0, the reweighting is ρ-smooth if ρ(w) ≥ ρ. When t wt > 0, its normalized edge against H is PT t=1 wt σt h(xt ) edgeH (w) = sup . PT w h∈H t t=1 For ρ, γ > 0, the transcript satisfies the (ρ, γ)-smooth weak-learning condition if every ρ-smooth reweighting w has edgeH (w) ≥ γ. When H ⊆ {−1, +1}X is a class of binary-valued classifiers, let PT errw (h) =

t=1 wt 1{h(xt ) ̸= σt } PT t=1 wt

denote the weighted error of h ∈ H. Its normalized weighted correlation is 1 − 2 errw (h). Because errw (−h) = 1 − errw (h), |1 − 2 errw (h)| = 1 − 2 min{errw (h), errw (−h)}. Thus the absolute value in the edge compares h with the classifier −h obtained by flipping all of h’s predictions. In particular, edgeH (w) ≥ γ means that, for some h ∈ H, either h or −h has weighted error at most (1 − γ)/2. If H is closed under negation, both orientations are members of H.

11

Relation to smooth distributions. The condition in Definition 4.3 is ex post: it is a property of the realized transcript, not an input to the forecaster. If w is ρ-smooth, then its normalization wt Dw (t) = P s ws is a distribution on the rounds satisfying Dw (t) ≤ 1/(ρT ). Conversely, any distribution D on [T ] with D(t) ≤ 1/(ρT ) is represented by the ρ-smooth reweighting wt = ρT D(t). Thus bounded smooth reweightings are exactly the unnormalized form of the smooth distributions used by SmoothBoost (Servedio, 2003) and in boosting-based hard-core constructions (Barak et al., 2009; Klivans and Servedio, 2003). The Defensive Booster does not maintain a distribution over past rounds or train separate weak learners on different reweightings. It sends the current signed residual 2(Yt −pt ) to one weak-class learner, as required to obtain multiaccuracy. The sequence wt = |Yt − pt | is interpreted only after the fact as the witness analyzed below. Theorem 4.4 (Hard-core mistake weighting). Let p1 , . . . , pT be the probability forecasts of the Defensive Booster, and let T 1X BT = (Yt − pt )2 . T t=1

Define the randomized mistake weights T

wt = Yt (1 − pt ) + (1 − Yt )pt = |Yt − pt |,

ρw =

1X wt . T t=1

Then wt ∈ [0, 1], T

1X 2 wt ≤ ρw , BT = T t=1

and every h ∈ H satisfies √ T 1X AH T BT + BH /2 wt σt h(xt ) ≤ . T T t=1

Consequently, if ρw > 0 then √ AH T BT + BH /2 edgeH (w) ≤ . T ρw Proof. Since Yt ∈ {0, 1} and pt ∈ [0, 1], wt ∈ [0, 1] and (Yt − pt )2 = wt2 . Hence BT = T −1 ρw . The key identity is σt − µt wt σt = Yt − pt = . 2 The multiaccuracy part of Theorem 3.3 therefore implies, for every h ∈ H, √ T T 1X 1 X AH T BT + BH /2 wt σt h(xt ) = h(xt )(σt − µt ) ≤ , T 2T T t=1

t=1

because ST = 4T BT . Dividing by ρw gives the normalized edge bound when ρw > 0. 12

2 t wt ≤

P

4.3

The smooth weak-learning condition gives classification boosting

The smooth weak-learning condition turns the hard-core alternative around. If no sufficiently smooth small-edge weighting exists, the algorithm’s own mistake weighting cannot be smooth. Corollary 4.5 (Second-order weak-to-strong rate). Let ρ0 , γ0 > 0. If the realized transcript satisfies P −1 2 the (ρ0 , γ0 )-smooth weak-learning condition for t (Yt − pt ) and PH, then the Brier loss BT = T −1 the randomized classification error ρw = T t |Yt − pt | both satisfy   4A2H BH . BT , ρw ≤ max ρ0 , 2 , γ0 T γ0 T The deterministic threshold classifier Ybt = 1{pt ≥ 1/2}, with arbitrary tie-breaking at pt = 1/2, has average classification error at most 2ρw . Proof idea. If the mistake weighting is not ρ0 -smooth, then its density ρw is already below ρ0 , as is BT . Otherwise, the smooth weak-learning condition lower-bounds its edge by γ0 , whereas Theorem 4.4 upper-bounds the same edge in terms of BT and ρw . Solving the two resulting inequalities gives the stated bounds. Thresholding adds at most a factor of two because every threshold mistake has |Yt − pt | ≥ 1/2. The complete calculation is given in Appendix A.2. Taking ρ0 to be a sufficiently small constant multiple of ε and  2  AH BH T =Ω 2 + γ0 ε γ0 ε gives Brier loss, randomized classification error, and deterministic classification error for the thresholded classifier at most ε, up to constants. Thus the smooth weak-learning condition must hold at smoothness ρ0 = O(ε) for a target error ε. When BH is logarithmic or lower order, this is the usual 1/(γ02 ε) dependence. The lower bound of Beygelzimer et al. (2015b) shows that this dependence is unavoidable in their weak-online-learning model, up to logarithmic and excess-loss terms.

5

Boosting on every interval

The preceding guarantees average over the full horizon. We now give a strongly adaptive variant: one forecast sequence satisfies the same two guarantees, up to polylogarithmic factors, on every contiguous interval. The construction uses a standard second-order specialist reduction. We state the reduction first because preserving dependence on the local residual energy is essential; an ordip nary O( |I|) interval-regret bound would lose the optimal weak-to-strong rate and get a 1/(γ02 ε2 ) dependence instead. Proposition 5.1 (Second-order interval wrapper). Fix a horizon T . Suppose an online learner B, whenever started fresh, outputs zt ∈ [−1, 1] and, for every comparator sequence z ⋆ = (zt⋆ )t in a fixed class and every coefficient sequence ct ∈ [−2, 2], satisfies v u n n X uX ⋆ ct (zt − zt ) ≤ at c2t + b. t=1

t=1

Set LT = log(4T ),

MT = 2 ⌈log2 (2T )⌉ . 13

There is a wrapper SA(B) whose output zet ∈ [−1, 1] satisfies, simultaneously for every interval I ⊆ [T ] and every comparator z ⋆ , sX X ⋆ c2t + βT (b), ct (zt − zet ) ≤ αT (a) (3) t∈I

t∈I

where, for a universal constant C0 , p
p αT (a) = MT a + C0 LT ,

βT (b) = MT b + C0 LT .

The wrapper maintains at most 1 + ⌈log2 T ⌉ active copies of B per round. The wrapper combines fresh copies of B on dyadic intervals with a second-order confidence-rated experts algorithm. Its standard proof is given in Appendix A.3. Apply Proposition 5.1 separately to the weak-class oracle and to the two scalar routines S and A in Algorithm 1; use their aggregate outputs in the same root rule and feed the wrappers the same coefficients as before. Call the resulting forecaster the strongly adaptive Defensive Booster. int int int Let aint H , bH denote the coefficients in (3) for the weak-class wrapper, and let asc , bsc denote them for either scalar wrapper. Since scalar adaptive OGD has fresh-run constants a = 4 and b = 8, Proposition 5.1 gives the explicit values aint H = αT (aH ),

bint H = βT (bH ),

aint sc = αT (4),

bint sc = βT (8).

Theorem 5.2 (Interval certificate). For every adaptive binary sequence, the strongly adaptive Defensive Booster satisfies, simultaneously for every interval I ⊆ [T ], sup

X

h∈H t∈I

where SI =

P

h(xt )rt ≤ Aint H

p

int SI + BH ,

X

µt rt ≤ Aint S

p SI + BSint ,

t∈I

2 t∈I rt and int int Aint H = aH + asc ,

int int BH = bint H + bsc ,

int Aint S = 2asc ,

BSint = 2bint sc .

The proof repeats the argument of Theorem 3.3 using the interval-regret bounds of Proposition 5.1; details are given in Appendix A.3. Corollary 5.3 (Strongly adaptive boosting). For an interval I ⊆ [T ], let n = |I| and define BI =

1X (Yt − pt )2 , n

ρI =

t∈I

1X |Yt − pt |. n t∈I

The interval mistake weights wt = |Yt − pt | form a local hard-core witness: if ρI > 0, then P √ int /2 Aint nBI + BH t∈I wt σt h(xt ) H P sup ≤ . nρI h∈H t∈I wt Simultaneously for every interval I: (i) for every f ∈ spanΛ (H), BI ≤

int p int + B int ΛAint ΛBH 1X H√+ AS S (Yt − qf (xt ))2 + BI + ; n 2n n t∈I

14

(ii) for any ρ0 , γ0 > 0, if every weighting w ∈ [0, 1]I with n−1

P

t∈I wt ≥ ρ0 satisfies

P sup h∈H

then

t∈I wt σt h(xt )

P

t∈I wt

≥ γ0 ,

 2 B int  4(Aint H ) BI , ρI ≤ max ρ0 , , H . γ0 n γ02 n

The threshold classifier has error at most 2ρI on I. The corollary follows by applying the proofs of Theorem 4.1, Theorem 4.4, and Corollary 4.5 on I, with Theorem 5.2 in place of the full-horizon certificate. Thus, for fixed oracle constants, a target interval error ε requires n = O(log2 (T )/(γ02 ε)) when the local weak-learning condition holds with ρ0 = O(ε), while the span-regret guarantee holds without any weak-learning condition. Since the bounds hold simultaneously, the interval and its span comparator may be selected after observing the transcript. No assumption is made about rounds outside I. The price for this simultaneous interval guarantee is the explicit logarithmic factors in Proposition 5.1 and at most 1+⌈log2 T ⌉ active weak-class oracle copies; the basic Defensive Booster retains its guarantee while maintaining one weak-class oracle. Structurally, one forecast sequence therefore produces a family of data-dependent local hard-core witnesses: whenever error remains high on an interval, the mistake weights on that interval identify a smooth distribution on which the entire weak class has small edge. This conclusion goes beyond interval comparator regret by identifying where and when weak learnability fails; it does not require the algorithm to detect a change point or explicitly construct a hard subset. Figure 14 in Appendix E visualizes the density and weak-class edge of these local witnesses across interval endpoints and time scales on a stream with known change points.

6

Experiments

We compare the Defensive Booster with online gradient boosting, online weak-to-strong boosting, and the more naive Brier aggregator strategy on controlled synthetic streams and four naturally ordered real datasets. The synthetic streams separately test settings in which the span contains an informative predictor and settings in which the smooth weak-learning condition holds. The real streams test performance on naturally ordered binary data; Appendix D.1 separately evaluates three chronological regression datasets. Across the binary experiments, the Defensive Booster’s Brier loss is competitive with the best baseline on each dataset and often improves upon it substantially, while the gradient boosting and weak-to-strong boosting ensemble baselines take 20–66× as much time per round. The Brier-loss aggregator over the four ensembles is yet more expensive and does not close the gap on the two real streams where the Defensive Booster performs best. Protocol. We compare eight methods. Two unboosted controls isolate the benefit of aggregation by simply running the learning algorithm that the boosting techniques take as input: Unboosted reg. performs online squared-loss regression over the weak class, while Unboosted cls. runs the online classifier used as the base learner by the classification boosters. Four ensemble baselines represent the two boosting traditions. OGB is online gradient boosting (Beygelzimer et al., 2015a); Online BBM is the rate-optimal online boost-by-majority algorithm; AdaBoost.OL is the adaptive logistic-loss algorithm from the same paper (Beygelzimer et al., 2015b); and OSBoost is online SmoothBoost (Chen et al., 2012). The Brier aggregator combines the forecasts of 15

these four ensembles by exponential weighting under Brier loss. The Defensive Booster and each unboosted control maintain one online learner over the weak class; each boosting baseline maintains an ensemble of N = 100 such learners, and the aggregator must run all four ensembles, for a total of 400. We evaluate deterministic 0/1 classification error, Brier loss, and randomized classification P error T −1 t |Yt − pt |. Online BBM and Unboosted cls. output hard labels, which we view as probabilities in {0, 1} when computing Brier loss and randomized error. Consequently, all three metrics coincide for these two methods. AdaBoost.OL randomizes over its partial ensembles; we report its probability of predicting one. Its randomized-error score is therefore the expected classification error of the original randomized output, while its Brier score evaluates that probability directly. We fix all hyperparameters before examining performance and do not tune them separately for each stream. In particular, Online BBM and OSBoost use the analytically guaranteed weak-learning advantage on controlled synthetic streams where one is known, and the fixed target classification advantage γ = .1 on all other streams. All synthetic results use T = 3000 and report means over 20 seeds. We process each real dataset stream once in its recorded order, without shuffling. Appendix C gives the complete details including algorithm hyperparameter settings, data generators and preprocessing steps, standard errors, and runtime tables. Code, public-data loaders, and exact reproduction commands are available at https://github.com/aaroth/defensive-boosting. We use two synthetic streams to isolate the two guarantees. To test the weak-to-strong guarantee, we use the binary aggregation stream. The weak class contains 200 binary hypotheses, arranged as 100 opposite pairs {±hj }100 j=1 . The algorithms see all 200 binary predictions in random order and are not told which orientation in each pair is useful. Signed labels are balanced and randomly ordered. There is a hidden choice of one orientation from each pair such that all 100 chosen rules are correct on half the rounds; on each remaining round exactly 58 are correct and 42 are incorrect, in a cyclically balanced pattern. 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. Averaging over the chosen orientations shows that every nonzero reweighting admits a displayed rule with edge at least .16. Adding negations and hiding the orientations does not change the span, so the symmetry calculation in Proposition B.1 shows that every fixed affine span score has Brier loss at least (1 − .16)2 /(8(1 + .162 )) = .0860. The stream thus directly instantiates the separation between span prediction and weak-to-strong aggregation. To test the span guarantee, we use the random-label mixture stream. Here the contexts are normalized vectors in R30 and the weak class is the infinite Euclidean linear class H = {x 7→ ⟨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. Uniform weighting over the randomlabel rounds is smooth and, with high probability, has low edge, so the smooth weak-learning condition fails for any constant target edge; nevertheless, the linear span remains informative on the structured rounds. These streams are deliberately favorable to different baseline families. On the binary aggregation stream, the Bayes classification error is zero and the weak-to-strong boosters approach it. On the random-label mixture stream, OGB is the strongest baseline in Brier loss and approaches the least-squares span benchmark, whereas the classification boosters incur substantially larger Brier loss. Each stream is therefore tailored to one baseline family. The test is whether the Defensive Booster approaches the stronger baseline on each stream while improving on the other family. Figure 2 shows deterministic classification error on the binary aggregation stream and Brier loss on the random-label mixture.

16

Figure 2: The two baseline families excel on complementary streams, and the Defensive Booster tracks the better family in each. Left: cumulative 0/1 error on the binary aggregation stream. Online BBM, AdaBoost.OL, and OSBoost approach zero, while OGB retains positive error; the Defensive Booster also approaches zero and is within .0001 of the Brier aggregator’s final mean. Right: cumulative Brier loss on the random-label mixture. OGB has the lowest baseline loss, while the weak-to-strong boosters remain higher; the Defensive Booster tracks OGB. The Brier aggregator tracks the better family in both panels by running all four 100-learner ensembles, whereas the Defensive Booster maintains one learner. Curves are means over 20 seeds. The hard-label unboosted classifier is omitted from the Brier panel for scale and reported in Table 3. Results. On the binary aggregation stream at T = 3000, 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. On the random-label mixture stream, 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 Brier aggregator reaches .1937 by running all four ensembles. Thus the Defensive Booster remains competitive with OGB on a sequence where the weak-to-strong guarantee does not apply. The full synthetic table in Appendix C.2 includes standard errors and three additional streams: a planted weak rule among decoys, an infinite linear weak class, and random labels. The random-label mixture stream also lets us inspect the hard-core guarantee directly. Figure 3 tracks the Defensive Booster’s multiaccuracy and self-orthogonality errors, together with the density of its mistake weighting and the weak class’s edge under that weighting. The two errors and the class edge decay while the density remains nontrivial, so the mistake weights form the smooth, low-edge witness predicted by Theorem 4.4.

17

Figure 3: Multiaccuracy, self-orthogonality, and hard-core diagnostics on the random-label mixture stream, averaged over 20 seeds. The first two panels show the cumulative multiaccuracy and self-orthogonality correlations from Theorem 3.3, divided by the current round t; the last two show the density and edgeH (w), the weak-class edge under the mistake weighting wt = |Yt − pt |. Randomized error remains nontrivial because of the random-label component, but edgeH (w) decays: the forecaster’s mistakes are the smooth low-edge witness predicted by Theorem 4.4. One learner versus an ensemble. Each unboosted control and the Defensive Booster have running time scaling as CH + O(1) per round, where CH is the running time of one weak-learner prediction and update. OGB, Online BBM, AdaBoost.OL, and OSBoost have per-round running time N CH + O(N ) with N learners; OSBoost also projects its combiner onto a simplex. The Brier aggregator runs all four ensemble boosters. Figure 4 compares prediction quality as the ensemble size varies. On this stream, the Defensive Booster has lower Brier loss and randomized error than each N = 100 ensemble and the Brier aggregator. In our implementation, the N = 100 methods take 20–66 times as much wall-clock time per round across the synthetic and real experiments. Absolute constants are implementation-dependent, but the difference in the number of maintained weak learners is part of the algorithms themselves.

Figure 4: Prediction quality as a function of the total number of maintained weak learners on the binary aggregation stream. OGB, Online BBM, AdaBoost.OL, and OSBoost use N ∈ {1, 5, 20, 100} learners; the Brier aggregator at each setting runs all four ensembles and is therefore plotted at 4N . The Defensive Booster and the unboosted controls each maintain one learner, so their performance appears as a horizontal line. The hard-label unboosted classifier is omitted from the Brier panel for scale. With one learner, the Defensive Booster achieves Brier loss and randomized error below the 100-learner ensembles and their aggregator.

18

Real-world data streams. We next evaluate the algorithms on four public binary data streams, each processed in its recorded order. Bank Marketing predicts whether a client subscribes to a term deposit (Moro et al., 2014); Electricity predicts price movement in the New South Wales electricity market (Harries, 1999; MOA, 2011); Airlines predicts flight delays (MOA, 2011); and Occupancy predicts whether an office is occupied from contemporaneous sensor measurements (Candanedo and Feldheim, 2016). Figure 1 compares each method’s final Brier loss with the best observed loss on that stream, and Table 1 reports the absolute averages. 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. AdaBoost.OL has the lowest classification errors on Electricity and the lowest randomized 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 . Both unboosted controls are substantially worse on Electricity and Occupancy, showing that the gains come from the Defensive Booster’s aggregation rather than merely from maintaining fewer learners. Complete preprocessing, cumulative curves, classification and randomized errors, and runtimes appear in Appendix C.3. Dataset Bank Electricity Airlines Occupancy

Defensive .0800 .0772 .2094 .0071

Unboosted reg. .0845 .1957 .2190 .0396

Unboosted cls. .1091 .3669 .3901 .0961

OGB .0791 .1516 .2094 .0159

BBM .1026 .2010 .3411 .0138

AdaBoost.OL .1046 .1007 .3417 .0103

OSBoost .1679 .1167 .2354 .0406

Brier agg. .0790 .1006 .2094 .0101

Table 1: Average online Brier loss on four real binary streams processed in recorded order; lower is better. No dataset is shuffled. The hard-label methods Unboosted cls. and BBM are scored as 0/1 probability forecasts. Bold marks the lowest unrounded value in each row. The Brier aggregator runs OGB, Online BBM, AdaBoost.OL, and OSBoost, for a total of 400 weak learners. The Defensive Booster is best on Electricity and Occupancy, essentially ties OGB and the aggregator on Airlines, and is within .0010 of the aggregator on Bank. Regression beyond binary outcomes. Appendix D.1 evaluates the bounded-outcome extension on three chronological regression datasets. Relative to 100-stage OGB, the Defensive Booster lowers normalized mean squared error by 18% on Appliance Energy, 29% on Bike Demand, and 17% on Interstate Traffic, while maintaining one weak learner rather than 100; OGB takes 65–70× as much wall-clock time per round in our implementation. The synthetic streams isolate the strengths of the two baseline families: OGB is strongest when an informative span comparator is available, while the classification boosters are strongest when the smooth weak-learning condition holds. We use the same tuning protocol for every method rather than retuning each method on each stream. The Defensive Booster remains competitive on both streams, uses one online learner, and its mistake weights expose the smooth, low-edge witness measured in Figure 3. Appendix E evaluates the strongly adaptive variant of the Defensive Booster from Section 5. On the four original real streams, its 16–20 weak-class learners, active at different time scales, make it slower than the basic Defensive Booster. It remains 3–10× faster than the 100-learner ensembles and further reduces both forecasting and classification error on Electricity, Airlines, and Occupancy (Table 5). On the INSECTS optical-sensor benchmark, whose released streams have controlled abrupt, gradual, incremental, and recurring distribution shifts, the same adaptive variant improves both errors on four of five drift patterns and essentially ties the basic method on the fifth (Table 7).

19

7

Related work

Our work connects to multiple streams of prior work. The most directly relevant to our application is prior work on online boosting, which is where the baseline algorithms in our experiments are drawn from: Online gradient boosting. Beygelzimer et al. (2015a) start from an online linear-loss learner for H and use N copies to compete with conv(H) or a norm-bounded span under smooth convex losses. Hu et al. (2017) study gradient boosting on i.i.d. data streams and extend their analysis to adversarial streams under a stronger edge assumption; Hazan and Singh (2021) use a multiplicative weak learner to obtain regret to a convex hull in online convex optimization. Our Brier/span guarantee is closest to the first of these in the squared-loss case: it competes with unrestricted realvalued scores in a norm-bounded span. Under the same online-linear-oracle primitive, however, the Defensive Booster uses one weak-class learner rather than an N -stage ensemble. Online weak-to-strong boosting. Oza and Russell (2001) initiated work on practical online bagging and boosting methods. The closest classification predecessor to our work is Chen et al. (2012), who adapt SmoothBoost to online binary boosting using smooth distributions. Beygelzimer et al. (2015b) give the rate-optimal online boosting algorithm, Online BBM, under weak online learnability assumptions. They also prove matching lower bounds: in their model, the optimal sample-complexity dependence for error ε is 1/(γ 2 ε) up to logarithmic and excess-loss terms. Our algorithm matches this γ, ε dependence. It also uses only one online linear oracle over H rather than many parallel weak learners. These papers make different weak-oracle assumptions. Chen et al. and Beygelzimer et al. assume that the online learner’s own predictions have a fixed positive edge over random guessing on every admissible stream—with smooth importance weights in the former case—up to an excess-loss term. Brukhim et al. (2020) instead assume a multiplicative agnostic oracle that obtains a fixed fraction of the best correlation in H, and boost it to regret against the best h ∈ H. Our primitive is instead a no-regret learning algorithm for H under linear losses: it need not have any absolute edge, but it competes with every h ∈ H on the realized residual losses. Thus H is the final comparator class in the agnostic framework of Brukhim et al., whereas here it supplies weak directions that are aggregated into forecasts competing with span(H); positive edge enters separately through our ex-post smooth weak-learning condition. AdaBoost as loss optimization. In the offline setting, weak-to-strong boosting algorithms such as AdaBoost have also been analyzed through the lens of loss minimization. Mason et al. (1999) place boosting inside the broader view of functional gradient descent. Mukherjee et al. (2013) show that AdaBoost converges to the infimum empirical exponential loss over additive combinations of weak hypotheses, without assuming weak learnability or a finite minimizer. This is analogous to our span-regret guarantee: both retain a span-optimization interpretation when weak learning assumptions fail. The objective and setting differ: their guarantee is batch optimization of exponential margin loss over scores, while ours is an online pathwise Brier-regret guarantee for probability forecasts. Exponential loss rewards large margins and does not by itself produce calibrated probabilities; empirically, Niculescu-Mizil and Caruana (2005) show that boosted outputs can have poor squared error and cross-entropy because they are not well-calibrated posterior probabilities. Strong adaptivity. Strongly adaptive online learning asks for low regret on every contiguous interval. Generic geometric-cover reductions obtain this guarantee from a standard online learner with

20

O(log T ) active copies (Daniely et al., 2015); second-order confidence bounds preserve dependence on local gradient energy (Cutkosky, 2020; Gaillard et al., 2014). The “adaptive” online booster of Beygelzimer et al. (2015b) is parameter-free rather than strongly adaptive in this interval sense. Section 5 applies the strongly adaptive machinery inside the Defensive Booster’s auditors, preserving both interval span regret and the guarantee that persistent interval error yields a smooth, low-edge mistake weighting. The defensive-forecasting construction therefore extends to strong adaptivity through standard online-learning machinery. Smooth boosting and hard-core sets. Smooth distributions are central in smooth boosting (Servedio, 2003); Gavinsky (2003) develops smooth adaptive boosting in the agnostic setting. The minimax view of boosting goes back to Freund and Schapire (1996). The connection between boosting and hard-core construction starts from Impagliazzo (1995) and was made algorithmic by Klivans and Servedio (2003) and Barak et al. (2009). Our reweightings are the online transcript analogue of these smooth distributions. Multicalibration, multiaccuracy, and loss minimization. Multicalibration was introduced by Hébert-Johnson et al. (2018); multiaccuracy was isolated as a black-box correction criterion by Kim et al. (2019). Outcome indistinguishability and omniprediction turn stronger prediction certificates into simultaneous downstream loss guarantees (Dwork et al., 2021; Gopalan et al., 2022, 2023). Globus-Harris et al. (2023) characterize when batch multicalibration boosts squaredloss regression to Bayes optimality. Kearns et al. (2025) use the weaker pair of conditions used here for loss minimization: multiaccuracy and self-orthogonality. Multicalibration and hard-core measures. Our weak-to-strong guarantee uses the connection between multiaccuracy and hard-core measures that appears in the complexity-theoretic regularity lemma of Trevisan et al. (2009). Stronger variants derive hard-core measures from multicalibration (Casacuberta et al., 2024) or calibrated multiaccuracy (Casacuberta et al., 2025). Our proof requires only multiaccuracy. This is √ important online: adversarial sequential calibration error cannot generally be bounded at the O( T ) scale achieved here (Collina et al., 2026; Dagan et al., 2025; Qiao and Valiant, 2021). Defensive forecasting. Our algorithm is developed in the defensive forecasting framework which chooses probabilities that prevent continuous “skeptic” strategies from increasing their capital by betting against the forecasts (Vovk et al., 2005a,b). Vovk (2007) shows that defensive forecasting also handles continuous “second-guessing” experts whose advice depends on the learner’s current forecast; the affine test Ft in our root rule has this form. Many online calibration and multicalibration algorithms can be interpreted in this framework (Bastani et al., 2022; Garg et al., 2024; Ghuge et al., 2025; Gupta et al., 2022; Hu et al., 2026; Noarov and Roth, 2023; Noarov et al., 2025; Perdomo and Recht, 2025). In a recent general result, Farina and Perdomo (2026) give generic reductions from online multicalibration to a no-regret learner plus an expected variational-inequality solver and recover traditional defensive-forecasting algorithms as special cases. The affine root step in Algorithm 1 is a deterministic one-dimensional instance of their framework. To our knowledge, ours is the first online boosting theorem obtained this way. Its additional structure yields the span guarantee and the hard-core mistake weighting.

21

Acknowledgments The authors used AI tools, specifically GPT 5.6 Pro, and GPT 5.6 in the Codex environment in the development of this paper. All of the final theorems and proofs are written and verified by the authors. The code for the empirical evaluation was written via GPT 5.6 Codex.

References Boaz Barak, Moritz Hardt, and Satyen Kale. The uniform hardcore lemma via approximate bregman projections. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1193–1200. SIAM, 2009. doi: 10.1137/1.9781611973068.129. URL https://epubs.siam.org/doi/10.1137/1.9781611973068.129. Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 29362–29373. Curran Associates, Inc., 2022. doi: 10.52202/068431-2129. URL https://proceedings.neurips.cc/paper_files/paper/2022/ hash/bcdaaa1aec3ae2aa39542acefdec4e4b-Abstract-Conference.html. Alina Beygelzimer, Elad Hazan, Satyen Kale, and Haipeng Luo. Online gradient boosting. In Advances in Neural Information Processing Systems 28, pages 2458–2466, 2015a. URL https://proceedings.neurips.cc/paper/2015/hash/ 0a1bf96b7165e962e90cb14648c9462d-Abstract.html. Alina Beygelzimer, Satyen Kale, and Haipeng Luo. Optimal and adaptive algorithms for online boosting. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2323–2331, Lille, France, 07–09 Jul 2015b. PMLR. URL https://proceedings.mlr.press/ v37/beygelzimer15.html. Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. Online agnostic boosting via regret minimization. In Advances in Neural Information Processing Systems 33, pages 644–654, 2020. URL https://proceedings.neurips.cc/paper/2020/hash/ 07168af6cb0ef9f78dae15739dd73255-Abstract.html. Luis Candanedo. Appliances energy prediction. UCI Machine Learning Repository, 2017. URL https://archive.ics.uci.edu/dataset/374/appliances+energy+prediction. Luis M. Candanedo and Véronique Feldheim. Accurate occupancy detection of an office room from light, temperature, humidity and CO2 measurements using statistical learning models. Energy and Buildings, 112:28–39, 2016. doi: 10.1016/j.enbuild.2015.11.071. URL https://doi.org/10. 1016/j.enbuild.2015.11.071. Sı́lvia Casacuberta, Cynthia Dwork, and Salil Vadhan. Complexity-theoretic implications of multicalibration. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1071–1082. ACM, 2024. doi: 10.1145/3618260.3649748. URL https://doi.org/10.1145/ 3618260.3649748. Sı́lvia Casacuberta, Parikshit Gopalan, Varun Kanade, and Omer Reingold. How global calibration strengthens multiaccuracy. In Proceedings of the 66th IEEE Symposium on Foundations of 22

Computer Science, pages 1198–1227. IEEE, 2025. doi: 10.1109/FOCS63196.2025.00063. URL https://doi.org/10.1109/FOCS63196.2025.00063. Nicolò Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2–3):321–352, 2007. doi: 10.1007/s10994-006-5001-7. URL https://link.springer.com/article/10.1007/ s10994-006-5001-7. Shang-Tse Chen, Hsuan-Tien Lin, and Chi-Jen Lu. An online boosting algorithm with theoretical justifications. In John Langford and Joelle Pineau, editors, Proceedings of the 29th International Conference on Machine Learning, pages 1007–1014. Omnipress, 2012. URL https://icml.cc/ 2012/papers/538.pdf. Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth. Optimal lower bounds for online multicalibration. arXiv preprint arXiv:2601.05245, 2026. URL https://arxiv.org/abs/2601. 05245. Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2250–2259. PMLR, 2020. URL https://proceedings.mlr.press/v119/cutkosky20a.html. Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, and Princewill Okoroafor. Breaking the T 2/3 barrier for sequential calibration. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2007–2018, 2025. doi: 10.1145/3717823.3718178. URL https://doi.org/10.1145/3717823.3718178. Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1405–1411. PMLR, 2015. URL https://proceedings.mlr.press/v37/daniely15.html. Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Outcome indistinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1095–1108. ACM, 2021. doi: 10.1145/3406325.3451064. URL https://doi. org/10.1145/3406325.3451064. Hadi Fanaee-T. Bike sharing. UCI Machine Learning Repository, 2013. URL https://archive. ics.uci.edu/dataset/275/bike+sharing+dataset. Gabriele Farina and Juan Carlos Perdomo. An efficient black-box reduction from online learning to multicalibration, and a new route to Φ-regret minimization. arXiv preprint arXiv:2604.19592, 2026. URL https://arxiv.org/abs/2604.19592. Yoav Freund and Robert E. Schapire. Game theory, on-line prediction and boosting. In Proceedings of the Ninth Annual Conference on Computational Learning Theory, pages 325–332. ACM Press, 1996. doi: 10.1145/238061.238163. URL https://doi.org/10.1145/238061.238163. Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of the 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 176–196. PMLR, 2014. URL https://proceedings.mlr.press/v35/gaillard14.html. 23

Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2725–2792. SIAM, 2024. doi: 10.1137/1.9781611977912.98. URL https://epubs.siam.org/doi/10.1137/1.9781611977912.98. Dmitry Gavinsky. Optimally-smooth adaptive boosting and application to agnostic learning. Journal of Machine Learning Research, 4:101–117, 2003. URL https://www.jmlr.org/papers/v4/ gavinsky03a.html. Rohan Ghuge, Vidya Muthukumar, and Sahil Singla. Improved and oracle-efficient online ℓ1 multicalibration. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 19437–19457. PMLR, 2025. URL https://proceedings.mlr.press/v267/ ghuge25a.html. Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Multicalibration as boosting for regression. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11459–11492. PMLR, 2023. URL https://proceedings.mlr.press/v202/globus-harris23a.html. Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In 13th Innovations in Theoretical Computer Science Conference, volume 215 of Leibniz International Proceedings in Informatics, pages 79:1–79:21. Schloss Dagstuhl–LeibnizZentrum für Informatik, 2022. doi: 10.4230/LIPIcs.ITCS.2022.79. URL https://drops. dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.79. Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistinguishability. In 14th Innovations in Theoretical Computer Science Conference, volume 251 of Leibniz International Proceedings in Informatics, pages 60:1– 60:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPIcs.ITCS.2023. 60. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.60. Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online multivalid learning: Means, moments, and prediction intervals. In 13th Innovations in Theoretical Computer Science Conference, volume 215 of Leibniz International Proceedings in Informatics, pages 82:1–82:24. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022. doi: 10.4230/LIPIcs.ITCS.2022.82. URL https://drops.dagstuhl.de/entities/document/ 10.4230/LIPIcs.ITCS.2022.82. Michael Harries. Splice-2 comparative evaluation: Electricity pricing. Technical Report 9905, School of Computer Science and Engineering, University of New South Wales, 1999. URL https: //cgi.cse.unsw.edu.au/~reports/. Elad Hazan and Karan Singh. Boosting for online convex optimization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 4140–4149. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/hazan21a.html. Ursula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In Proceedings of the 35th International 24

Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1939–1948. PMLR, 2018. URL https://proceedings.mlr.press/v80/hebert-johnson18a. html. John Hogue. Metro interstate traffic volume. UCI Machine Learning Repository, 2019. URL https://archive.ics.uci.edu/dataset/492/metro+interstate+traffic+volume. Hanzhang Hu, Wen Sun, Arun Venkatraman, Martial Hebert, and Andrew Bagnell. Gradient boosting on stochastic data streams. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 595–603. PMLR, 2017. URL https://proceedings.mlr. press/v54/hu17a.html. Lunjia Hu, Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Efficient swap multicalibration of elicitable properties. In Steve Hanneke and Tor Lattimore, editors, Proceedings of Thirty Ninth Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 3314–3348. PMLR, 29 Jun–03 Jul 2026. URL https://proceedings.mlr.press/v336/hu26b. html. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 538–545. IEEE Computer Society, 1995. doi: 10.1109/SFCS.1995.492584. URL https://doi.org/10.1109/SFCS.1995. 492584. Michael Kearns, Aaron Roth, and Emily Ryu. Networked information aggregation via machine learning. arXiv preprint arXiv:2507.09683, 2025. URL https://arxiv.org/abs/2507.09683. Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247–254. ACM, 2019. doi: 10.1145/3306618.3314287. URL https://doi.org/ 10.1145/3306618.3314287. Jyrki Kivinen, Alexander J. Smola, and Robert C. Williamson. Online learning with kernels. IEEE Transactions on Signal Processing, 52(8):2165–2176, 2004. doi: 10.1109/TSP.2004.830991. Adam R. Klivans and Rocco A. Servedio. Boosting and hard-core set construction. Machine Learning, 51(3):217–238, 2003. doi: 10.1023/A:1022949332276. URL https://link.springer. com/article/10.1023/A:1022949332276. Llew Mason, Jonathan Baxter, Peter L. Bartlett, and Marcus R. Frean. Boosting algorithms as gradient descent. In Advances in Neural Information Processing Systems 12, pages 512–518. MIT Press, 1999. URL https://proceedings.neurips.cc/paper/1999/hash/ 96a93ba89a5b5c6c226e49b88973f46e-Abstract.html. MOA. Massive online analysis datasets. Dataset repository, August 2011. URL https://moa.cms. waikato.ac.nz/datasets/. Accessed 2026-07-02. Sérgio Moro, Paulo Rita, and Paulo Cortez. Bank marketing. UCI Machine Learning Repository, 2014. URL https://archive.ics.uci.edu/dataset/222/bank+marketing. Indraneel Mukherjee, Cynthia Rudin, and Robert E. Schapire. The rate of convergence of AdaBoost. Journal of Machine Learning Research, 14(70):2315–2347, 2013. URL https://www.jmlr.org/ papers/v14/mukherjee13b.html. 25

Alexandru Niculescu-Mizil and Richard A. Caruana. Obtaining calibrated probabilities from boosting. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pages 413–420, 2005. URL https://arxiv.org/abs/1207.1403. Georgy Noarov and Aaron Roth. The statistical scope of multicalibration. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 26283–26310. PMLR, 2023. URL https:// proceedings.mlr.press/v202/noarov23a.html. Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional prediction for sequential decision making. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon LacosteJulien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 46762–46783. PMLR, 2025. URL https://proceedings.mlr.press/ v267/noarov25b.html. Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716: 50–69, 2018. doi: 10.1016/j.tcs.2017.11.021. URL https://doi.org/10.1016/j.tcs.2017.11. 021. Nikunj C. Oza and Stuart J. Russell. Online bagging and boosting. In Thomas S. Richardson and Tommi S. Jaakkola, editors, Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, volume R3 of Proceedings of Machine Learning Research, pages 229–236. PMLR, 2001. URL https://proceedings.mlr.press/r3/oza01a.html. Reissued by PMLR on 31 March 2021. Juan Carlos Perdomo and Benjamin Recht. In defense of defensive forecasting. arXiv preprint arXiv:2506.11848, 2025. URL https://arxiv.org/abs/2506.11848. Mingda Qiao and Gregory Valiant. Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 456–466, 2021. doi: 10.1145/3406325.3451050. URL https://doi.org/10.1145/3406325.3451050. Rocco A. Servedio. Smooth boosting and learning with malicious noise. Journal of Machine Learning Research, 4:633–648, 2003. URL https://www.jmlr.org/papers/v4/servedio03a. html. Vinicius M. A. Souza, Denis M. dos Reis, André G. Maletzke, and Gustavo E. A. P. A. Batista. Challenges in benchmarking stream learning algorithms with real-world data. Data Mining and Knowledge Discovery, 34(6):1805–1858, 2020. doi: 10.1007/s10618-020-00698-5. URL https: //doi.org/10.1007/s10618-020-00698-5. Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pages 126–136. IEEE, 2009. URL https://people.seas.harvard. edu/~salil/research/regularity-abs.html. Vladimir Vovk. Defensive forecasting for optimal prediction with expert advice. Technical Report Working Paper 20, Game-Theoretic Probability and Finance Project, August 2007. URL https: //arxiv.org/abs/0708.1503. 26

Vladimir Vovk, Ilia Nouretdinov, Akimichi Takemura, and Glenn Shafer. Defensive forecasting for linear protocols. In Algorithmic Learning Theory, 16th International Conference, ALT 2005, volume 3734 of Lecture Notes in Computer Science, pages 459–473. Springer, 2005a. doi: 10. 1007/11564089 35. Vladimir Vovk, Akimichi Takemura, and Glenn Shafer. Defensive forecasting. In Robert G. Cowell and Zoubin Ghahramani, editors, Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, volume R5 of Proceedings of Machine Learning Research, pages 365– 372. PMLR, 2005b. URL https://proceedings.mlr.press/r5/vovk05a.html. Reissued by PMLR on 30 March 2021. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. Technical Report CMU-CS-03-110, Carnegie Mellon University, 2003. URL https://www.cs.cmu. edu/~maz/publications/techconvex.pdf.

27

A

Deferred proofs

This appendix contains proofs of the standard online-learning tools and routine consequences used in the main text.

A.1

Scalar second-order regret

√ Proof of Lemma 2.5. Let ηt = 1/ Vt−1 . Nonexpansiveness of projection gives gt (a − at ) ≤

(a − at )2 − (a − at+1 )2 ηt gt2 + . 2ηt 2

Because η√t is nonincreasing and the diameter of [−1, 1] is 2, the sum of the first terms is at most 2/ηT ≤ 2 VT . Moreover, gt2 ≤ 4 ≤ Vt−1 , and hence s ! p  5 p  p p gt2 Vt √ = 1+ Vt − Vt−1 ≤ Vt − Vt−1 . Vt−1 2 Vt−1 √ Thus the sum of the second terms is at most 54 VT . Adding the two contributions gives T X t=1

Finally,

A.2

√

4+x≤2+

√

  p 13 p 5 p VT = VT ≤ 4 VT . (a − at )gt ≤ 2 + 4 4

x gives the final inequality.

Consequences of the full-horizon certificate

Proof of Corollary 4.2. Theorem 4.1 gives C p D BT ≤ Bf + √ . BT + 2T T √ √ Let x = BT , a = C/ T , and d = D/(2T ). For u = x, u2 ≤ Bf + au + d,



so

u−

a 2 a2 ≤ Bf + d + . 2 4

Taking the positive square root gives a u≤ + 2

r Bf + d +

a2 . 4

Hence

p p 3 3 x ≤ Bf + d + a2 + a Bf + d ≤ Bf + a Bf + a2 + d, 2 2 √ √ p p 2 where the last inequality uses Bf + d ≤ Bf + d and a d ≤ (a + d)/2. Substituting the definitions of a and d proves the claim. Proof of Corollary 4.5. Let wt = |Yt − pt |. If ρw < ρ0 , then Theorem 4.4 gives BT ≤ ρw < ρ0 , and the randomized-error bound is immediate. Now suppose ρw ≥ ρ0 . The smooth weak-learning condition applies to w, while Theorem 4.4 gives √ AH T BT + BH /2 γ0 ≤ edgeH (w) ≤ . T ρw 28

Since BT ≤ ρw , we have

BH AH + . γ0 ≤ √ 2T BT T BT

P The denominator is nonzero: ρw ≥ ρ0 > 0 implies that some wt > 0, and hence BT = T −1 t wt2 > 0. If both BT > 4A2H /(γ02 T ) and BT > BH /(γ0 T ) held, then the two terms on the right would each be strictly smaller than γ0 /2, a contradiction. This proves the stated bound on BT . For the randomized-error bound, combine the edge inequality with BT ≤ ρw : √ AH BH AH T ρw + BH /2 =√ + . γ0 ≤ T ρw 2T ρw T ρw √ Writing u = ρw , this becomes BH AH u2 ≤ √ u + . 2γ0 T γ0 T If both u2 > 4A2H /(γ02 T ) and u2 > BH /(γ0 T ) held, the right side would be strictly smaller than u2 , again a contradiction. This proves the randomized-error bound. Finally, if Ybt ̸= Yt then |Yt − pt | ≥ 1/2. Averaging shows that the deterministic threshold error is at most 2ρw .

A.3

Strongly adaptive extension

Proof of Proposition 5.1. Pad [T ] to the next power of two and let J be its canonical family of dyadic intervals. The family has fewer than 4T members, at most 1 + ⌈log2 T ⌉ of which contain any round, and every interval I ⊆ [T ] is a disjoint union of at most MT members of J (Daniely et al., 2015). Start one copy BJ at the left endpoint of each J ∈ J and run it only on J. Aggregate the active copies with a second-order confidence-rated experts algorithm, treating membership in J as expert J’s confidence. To see that the P standard guarantee applies, let qJ,t be the algorithm’s weights on the active intervals and set zet = J qJ,t zJ,t . Map the linear gain to the loss 2 − ct zJ,t ℓJ,t = ∈ [0, 1]. 4 The confidence-regret reduction and second-order excess-loss bound of Gaillard et al. (2014) give, for every J ∈ J ,   s X X ct (zJ,t − zet ) ≤ C0  LT c2t + LT  , t∈J

t∈J

for a universal constant C0 . Here we assign a uniform prior to the fewer than 4T dyadic specialists. A geometric grid of learning rates, if needed, contributes only O(log log T ), P which is absorbed by C0 LT . The loss range used in the second-order bound is valid because |ℓJ,t − J ′ qJ ′ ,t ℓJ ′ ,t | ≤ |ct |/2. Now partition an arbitrary I into J1 , . . . , Jm ∈ J . On each block, insert the prediction of BJj between the comparator and the wrapper. The fresh-run guarantee and the preceding confidenceregret bound give   sX s m X X X a c2t + b + C0 LT c2t + C0 LT  ct (zt⋆ − zet ) ≤ j=1

t∈I

≤

p

t∈Jj

MT a + C 0

t∈Jj

p LT

s
X t∈I

29

c2t + MT b + C0 LT ,

where the last step uses Cauchy–Schwarz and m ≤ MT . Only the 1 + ⌈log2 T ⌉ copies associated with intervals containing the current round are active. This proves (3). Advance knowledge of T is not essential. Partition time into epochs [2j , 2j+1 − 1] and run the fixed-horizon construction afresh in each epoch. Any interval up to time T meets at most 1+⌈log2 T ⌉ epochs. p Summing the fixed-horizon bounds over those pieces and applying Cauchy–Schwarz adds a factor 1 + ⌈log2 T ⌉ to the coefficient of the second-order term and a factor 1 + ⌈log2 T ⌉ to the additive term. At any time only the wrapper for the current epoch is active. Proof of Theorem 5.2. Fix an interval I. The root sign property holds separately on every round, so the aggregated auditor gain is nonpositive on I. Interval regret for the wrapped A against its two endpoint comparators therefore gives X X p zH,t , zS,t ≤ aint SI + bint sc sc . t∈I

t∈I

For every h ∈ H, interval regret for the wrapped weak-class oracle then gives X X p p int int h(xt )rt ≤ zH,t + aint SI + bint SI + B H . H H ≤ AH t∈I

t∈I

Symmetry of H gives the absolute value. Similarly, for θ ∈ {−1, 1}, interval regret for the wrapped S gives sX X X p int int θµt rt ≤ zS,t + asc µ2t rt2 + bint SI + BSint . sc ≤ AS t∈I

t∈I

t∈I

Taking both signs proves the self-orthogonality inequality.

B

Separation: the guarantees are incomparable

The Brier/span and weak-to-strong guarantees do not imply one another. Proposition B.1 gives a transcript on which every reweighting has positive weak-class edge, yet every real-valued score induced by the span has constant squared loss. The construction exploits a basic difference between the guarantees: squared loss depends on the numerical values of a score, whereas weak-to-strong boosting can exploit its sign. Proposition B.2 gives the converse separation: a small subset of uninformative rounds defeats the smooth weak-learning condition even though a span comparator has small squared loss. Proposition B.1 (Separation). For every γ ∈ (0, 1) and η > 0, there are a number δ ∈ [γ, min{γ + η, 1}), a symmetric binary-valued class H, and a transcript (xt , Yt )t≤T such that: P (i) every reweighting w ∈ [0, 1]T with t wt > 0 has edgeH (w) ≥ δ; in particular the (ρ, γ)-smooth weak-learning condition holds for every ρ > 0; (ii) no single hypothesis is correct on every round, but a uniform average of hypotheses in H has positive signed margin on every round and therefore classifies the transcript perfectly; (iii) every affine score qf (x) = (1 + f (x))/2 induced by the span of H, with no range or norm constraint, has average squared loss at least (1 − δ)2 /(8(1 + δ 2 )).

30

Proof. Choose an integer k large enough that 2/k < min{η, 1 − γ}, and set   (1 + γ)k 2r − k r= , δ= . 2 k Then k/2 < r < k and γ ≤ δ < min{γ + η, 1}. Let h1 , . . . , hk be binary-valued hypotheses and include their negations in H. All labels equal one, so σt = 1 on every round. The transcript has two equally large parts. On every context in the first part, set hj (xt ) = 1 for all j. The second part contains one context for each r-element subset A ⊆ [k], and on that context set ( 1, j ∈ A, hj (xA ) = −1, j ∈ / A.
Repeat the all-positive context kr times so that the two parts have equal size. At every context, k

1X σt hj (xt ) ≥ δ. k j=1

Consequently, for every reweighting w with positive mass, k

1X k

PT

j=1

t=1 wt σt hj (xt ) ≥ δ. PT t=1 wt

P Some hj must therefore have weighted edge at least δ, proving (i). The uniform average k −1 j hj equals 1 on the first part and δ on the second, so its sign is always correct. On the other hand, every hj equals −1 on a positive fraction of the second part because r < k. This proves (ii). P It remains to minimize squared loss over the span. Write f = kj=1 αj hj . The transcript and its squared-loss objective are invariant under permutations of the k coordinates. Averaging the coefficient vector over all permutations and using convexity therefore cannot increase loss. Hence an optimum has α1 = · · · = αk = b/k for some b ∈ R. Its signed score equals b on the first part and δb on the second, so its Brier loss is ψ(b) =

(1 − b)2 + (1 − δb)2 . 8

This is minimized at b⋆ = (1 + δ)/(1 + δ 2 ), where it equals (1 − δ)2 /(8(1 + δ 2 )). This proves (iii). The separation also survives clipping span P scores to the P probability range when the coefficient norm is bounded. Fix Λ ≥ 1, write f = j αj hj with j |αj | ≤ Λ, and clip f to [−1, 1] before converting it P to a probability. On the second half of the construction, the average of f over all r-subsets is δ j αj ≤ δΛ. For every u ∈ [−Λ, Λ], clip[−1,1] (u) ≤

2u + Λ − 1 . Λ+1

If δ ≤ 1/(2Λ), the average clipped signed score on this half is therefore at most Λ/(Λ + 1). Jensen’s inequality shows that these rounds have average Brier loss at least 1/(4(Λ + 1)2 ), and hence the full transcript has average Brier loss at least 1/(8(Λ + 1)2 ). In particular, clipping does not remove the separation for any fixed coefficient-norm budget. Moreover, perfect clipped prediction would

31

P require f (x ) ≥ 1 for every r-subset A; averaging these inequalities gives δ A j αj ≥ 1, and therefore P j |αj | ≥ 1/δ. As δ → 0, the span’s best squared loss approaches 1/8, while Corollary 4.5 forces the Defensive Booster’s Brier score and classification error to vanish as T grows. Thus a Brier/span-regret guarantee alone can leave constant squared loss on transcripts where the smooth weak-learning condition forces near-perfect prediction. The reverse implication fails for a different reason: a small set of rounds can support a zero-edge reweighting while contributing little to average squared loss. Proposition B.2 (Converse separation). For every T and every even m ∈ {2, . . . , T }, there is a symmetric binary-valued class H = {h1 , −h1 , h2 , −h2 } and a transcript (xt , Yt )t≤T such that: (i) the smooth weak-learning condition fails for every ρ ≤ m/T and every γ > 0; (ii) the span comparator P f = (h1 + h2 )/2 ∈ span1 (H) induces the score qf = (1 + f )/2 with average squared loss T −1 t (Yt − qf (xt ))2 = m/(4T ). Proof. Choose distinct contexts x1 , . . . , xT , arbitrary binary labels, and let R ⊆ {1, . . . , T } have size m. Split R into equal parts R1 and R2 . Outside R, set h1 (xt ) = h2 (xt ) = σt . On R1 , set (σt h1 (xt ), σt h2 (xt )) = (1, −1); on R2 , reverse these two values. Consider the reweighting wt = 1{t ∈ R}. It has density m/T , and T X

wt σt h1 (xt ) =

t=1

T X

wt σt h2 (xt ) = 0

t=1

and the same holds for their negations, so edgeH (w) = 0. Hence the (ρ, γ)-smooth weak-learning condition fails for every ρ ≤ m/T and every γ > 0. The comparator f = (h1 + h2 )/2 equals σt off R and zero on R. It therefore predicts perfectly off R and induces probability 1/2 on R, so each round in R contributes squared loss 1/4. Its average squared loss is therefore m/(4T ). The random-label mixture experiment in Section 6 instantiates the second separation qualitatively: the randomly labeled rounds support a smooth reweighting with small weak-class edge, while the structured rounds retain an informative least-squares span score.

C

Additional experimental details and results

This appendix section gives the complete protocol and additional results for the binary prediction experiments. The synthetic streams separately examine the two guarantees: Brier loss and an offline least-squares Pspan comparator measure competition with the span, while randomized classification error T −1 t |Yt − pt | measures weak-to-strong performance and equals the density of the forecaster’s mistake weighting. The real streams evaluate forecasting and classification performance on examples processed in their recorded order. Appendices D.1 and E report the regression and strongly adaptive experiments, respectively.

C.1

Protocol and implementation

Algorithms. The main comparison includes eight methods. Defensive implements the Defensive Booster (Algorithm 1), including the two class-independent scalar adaptive-OGD states in Definition 2.4. For the real and distribution-shift experiments, we additionally report Adaptive 32

Def., the strongly adaptive Defensive Booster from Section 5; it maintains one weak learner at each active dyadic scale. Section E gives its implementation details and local diagnostics. The two unboosted controls each maintain a single learner. Unboosted reg. performs online squared-loss regression over the same weak class, using online linear optimization on the squaredloss gradient. Unboosted cls. runs the online binary classifier used as the weak learner by Online BBM, AdaBoost.OL, and OSBoost; it isolates the benefit of boosting from that of the base classification algorithm. The four ensemble baselines each maintain 100 weak learners. OGB is the online gradient boosting algorithm of Beygelzimer et al. (2015a), specialized to one-dimensional signed squared loss, equivalently Brier loss up to a factor of four, and run with 100 boosting stages and stage step η = (log N )/N , as suggested by their theoretical discussion. In the learner-count sweep, the N = 1 endpoint uses the admissible step η = 1. Online BBM is the boost-by-majority algorithm of Beygelzimer et al. (2015b), the optimal-rate binary online classification booster; we run its importance-weighted version with 100 weak learners and the target advantage described below. Online BBM outputs hard binary predictions, so its Brier score in our tables is the Brier score of the induced 0/1 probability forecast. AdaBoost.OL is the adaptive logistic-loss booster from the same paper. We implement the importance-weighted version used in its experiments: projected online gradient descent learns each weak learner’s coefficient, and exponential weights aggregate the hard predictions of the partial ensembles. The algorithm’s probability of predicting one is used as its forecast. Thus its randomized-error score is the expected 0/1 error of the original randomized classifier, while its Brier score evaluates that probability forecast directly. AdaBoost.OL requires no target-edge parameter. OSBoost is the online SmoothBoost algorithm of Chen et al. (2012) with its online-convex-programming combiner and 100 weak learners, following the experimental convention in that paper. We use the target-selection rule below and importance-weighted updates as in their experiments. We include OSBoost because its smooth reweighting mechanism is especially close to the smooth-distribution mechanism analyzed here. The Online BBM/AdaBoost.OL paper and the OSBoost paper define γ as the amount by which weak classification error improves on 1/2; equivalently, a binary weak prediction has signed correlation 2γ. On a synthetic stream with a known guaranteed advantage, we supply that value rather than tune it from the observed results. Thus Online BBM and OSBoost use γ = .08 on binary aggregation, whose guaranteed correlation edge is .16, and γ = .1 on the other streams. This convention keeps the baselines’ classification parameter distinct from the correlation edge in our theorem. Finally, Brier aggregator runs OGB, Online BBM, AdaBoost.OL, and OSBoost in parallel. Before observing Yt , it predicts the weighted average of their four probabilities and, after observing Yt , multiplies each weight by exp{−(Yt − pt,i )2 /2}. Since Brier loss is 1/2-exp-concave on [0, 1], its cumulative Brier loss is at most that of the best constituent plus 2 log 4: for each binary outcome y, p 7→ exp(−(y − p)2 /2) is concave, so the standard exponential-weights potential argument applies to the weighted-average forecast. This baseline maintains all 400 constituent weak learners. To place all outputs on the same probability scale, we interpret each method’s signed score st ∈ [−1, 1] as the probability pt = (1 + st )/2. OGB projects its aggregate score to [−1, 1], OSBoost uses its simplex-weighted vote, AdaBoost.OL uses its exponential-weights randomization probability, and Unboosted cls. and Online BBM return st ∈ {−1, 1}; we apply no post-hoc calibration. Thus the reported Brier loss evaluates the probability induced directly by each online algorithm’s output. For each algorithm family, we use one predeclared tuning rule rather than optimizing parameters against the observed performance of each stream. In Defensive, both scalar states use Definition 2.4 with V0 = 4; no scalar learning rate is tuned. The linear-loss oracles used by De33

fensive, Unboosted reg., and every OGB stage are second-order. For a finite class with d base hypotheses, we run entropy-FTRL over its symmetric closure with s ( ) log(2d) P ηt = min .25, , 4 + s<t c2s where cs is the scalar multiplying the weak prediction in the round-s gain. For the Euclidean q linear P unit ball, we use projected adaptive gradient ascent with step .5/ 4 + s<t ∥cs xs ∥22 . These choices give the coefficient-energy regret bounds required by the theory. The finite classification learners used by Unboosted cls.,p Online BBM, AdaBoost.OL, and OSBoost instead share the horizonaware Hedge scale min{.5, 8 log(d)/T√}; their linear-class counterparts share the same weighted projected-perceptron update with a 1/ t step scale. All synthetic results average 20 random seeds with T = 3000 rounds, and tables report mean ± standard error. The real datasets have fixed chronological order and deterministic algorithm updates, so we report one run. We never shuffle a real stream: each example is predicted in its recorded order before it is used for the update. The experiments/ directory contains the generators, loaders, algorithm implementations, and commands used for every reported result. The synthetic streams are original controlled constructions rather than reproductions of prior benchmarks. Runtime. Let CH be the cost of one prediction/update for the online learner over the weak class. Each unboosted control and the Defensive Booster costs CH + O(1) per round. OGB, Online BBM, AdaBoost.OL, and OSBoost each cost N CH + O(N ) with N weak learners; OSBoost additionally pays an O(N log N ) simplex projection when the OCP combiner updates. We use N = 100 for all ensemble baselines in the main comparison, and additionally evaluate each ensemble baseline with N ∈ {1, 5, 20, 100} learners. The Brier aggregator runs all four ensembles and therefore costs 4N CH + O(N log N ) and maintains 4N weak learners.

C.2

Controlled synthetic streams

Synthetic streams. We use five streams to separate two questions: whether every smooth reweighting has a weak rule with positive edge, and whether the span contains an informative squared-loss comparator. The planted-decoy and binary aggregation streams satisfy the smooth weak-learning condition by construction. The three linear streams instead test span competition with noisy labels or weak signal. For the two finite-class streams, an algorithm uses a context only through the vector of weakrule values, so we generate that vector directly. Round t is represented by (h1 (xt ), . . . , hd (xt )), and the linear-loss oracle uses the symmetric closure of the coordinate rules. For the other three streams, the weak class is the Euclidean unit ball H = {x 7→ ⟨u, x⟩ : ∥u∥2 ≤ 1}. In planted decoy, σt is uniform on {−1, 1}, the useful rule is h1 (xt ) = st σt for an independent uniform st ∈ {.12, 1}, and the other 199 rule scores are independent uniform signs. Thus the 200 base rules (and their symmetric closure) contain a sign-perfect rule with edge at least .12 under every reweighting. In binary aggregation, the displayed weak class consists of 100 opposite pairs {±hj }100 j=1 , and signed labels are balanced and randomly ordered. One latent orientation from each pair is designated useful. On half the rounds all 100 useful orientations equal the signed label. On the remaining rounds, we cycle through 100 binary patterns: each pattern has 58 useful orientations correct and 42 incorrect, and every useful orientation occupies each position equally often. Independent sign flips and a column permutation hide the useful orientation in each pair; we also randomly permute 34

the rounds. The algorithms receive only the resulting vector of 200 weak-rule values. On every round, 100 1 X σt hj (xt ) ≥ .16. 100 j=1

Here the sum uses the latent useful orientation from each pair. After multiplying by any nonzero weights and averaging, at least one displayed rule has edge .16. No individual rule is perfect, and the average of all 200 displayed rules is identically zero, whereas the hidden average above has positive margin on every round. Adding the opposite rules, applying sign flips, and permuting the columns do not change the span. The same symmetry therefore yields an exact span obstruction. Averaging any coefficient vector over cyclic shifts cannot increase squared loss, so an optimal fixed span score assigns every latent useful orientation the same coefficient. Its signed score is b on the first half of the stream and .16b on the second half. Minimizing the resulting Brier loss gives (1 − b)2 + (1 − .16b)2 (1 − .16)2 = = .0860. b∈R 8 8(1 + .162 )

min

Thus the stream is a finite cyclic version of the binary separation in Proposition B.1: aggregation classifies perfectly, but every fixed affine span score has constant Brier loss. For the three linear streams, draw xt ∼ N (0, Id ) and normalize it to unit Euclidean norm; draw and normalize a fixed β ∼ N (0, Id ). In linear span, d = 40 and σt = sign(⟨β, xt ⟩ + ξt ) for ξt ∼ N (0, .022 ). In random-label mixture, d = 30 and the same model uses noise N (0, .052 ), but independently on 35% of rounds its label is replaced by a uniform random sign. The reweighting supported on the replaced labels has density close to .35, and because those labels are independent of the contexts, its weak-class edge tends to zero as T grows. The structured rounds still admit an informative linear score. In random labels, d = 30 and every signed label is an independent uniform sign. All draws are independent except where the construction explicitly shares σt or β. P Offline span diagnostic. For each realized synthetic transcript, let βb ∈ arg minβ t (σt − b x⟩)/2, whose average squared ⟨β, xt ⟩)2 . The induced real-valued prediction is qβb(x) = (1 + ⟨β, loss is exactly T T 1X 1 X 2 b xt ⟩)2 . (Yt − qβb(xt )) = (σt − ⟨β, T 4T t=1

t=1

We report this loss and a norm ΛLS witnessing membership in the comparator class of Theorem 4.1: b 1 for a finite coordinate class and ∥β∥ b 2 for the Euclidean linear ball. The score is not clipped, ∥β∥ so it is an unrestricted span comparator covered by Theorem 4.1. Because βb is fit after observing the full transcript, it is a diagnostic benchmark rather than an online algorithm. Figure 5 reports randomized classification error on the two streams satisfying the smooth weaklearning condition. Figure 6 reports Brier loss on the three linear streams. Tables 2 and 3 give the corresponding span benchmarks and complete numerical results.

35

Figure 5: Randomized classification error on the streams satisfying the smooth weak-learning condition. Left: on planted decoy, one base rule has the correct sign on every round but is hidden among 199 decoys; the unboosted classifier and OSBoost identify it fastest, and the Defensive Booster also reaches low error. Right: on binary aggregation, no individual rule is perfect and the average of all displayed rules is zero, but a hidden choice of one orientation from each opposite pair has positive margin. The Defensive Booster and the three weak-to-strong ensembles all attain low randomized error; the Defensive Booster uses one weak learner.

36

Figure 6: Brier loss on the three linear streams. Top left: on linear span, the span comparator is informative even though the smooth weak-learning condition can fail on near-margin examples. Top right: on random-label mixture, the structured rounds retain an informative span comparator; OGB, unboosted regression, and the Defensive Booster outperform the classification-boosting baselines. Bottom: on random labels, the Defensive Booster, unboosted regression, and OGB remain near the p = 1/2 Brier baseline. The hard-label unboosted classifier is omitted from these plots for scale and reported in Table 3. Stream Planted decoy Binary aggregation Linear span Random-label mixture Random labels

LS span squared loss .0887 ± .0004 .0860 ± .0000 .0900 ± .0003 .1847 ± .0007 .2472 ± .0001

ΛLS 2.982 ± .020 1.131 ± .000 5.084 ± .017 2.794 ± .018 .576 ± .013

Table 2: Offline least-squares span diagnostics, averaged over the same 20 seeds used for the online results. The score is not clipped. The reported ΛLS is the ℓ1 norm of the fitted coefficient vector for a finite class or the ℓ2 norm for the Euclidean linear class. Hence each row is an actual spanΛLS (H) comparator covered by Theorem 4.1.

37

Stream Planted decoy Planted decoy Planted decoy Planted decoy Planted decoy Planted decoy Planted decoy Planted decoy Binary aggregation Binary aggregation Binary aggregation Binary aggregation Binary aggregation Binary aggregation Binary aggregation Binary aggregation Linear span Linear span Linear span Linear span Linear span Linear span Linear span Linear span Random-label mixture Random-label mixture Random-label mixture Random-label mixture Random-label mixture Random-label mixture Random-label mixture Random-label mixture Random labels Random labels Random labels Random labels Random labels Random labels Random labels Random labels

Algorithm Defensive Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg. Defensive Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg. Defensive Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg. Defensive Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg. Defensive Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg.

0/1 .0166 ± .0008 .0072 ± .0004 .0065 ± .0003 .0162 ± .0005 .1185 ± .0008 .0147 ± .0004 .0073 ± .0003 .0096 ± .0005 .0026 ± .0006 .1026 ± .0013 .1829 ± .0028 .0331 ± .0009 .0041 ± .0002 .0042 ± .0004 .0068 ± .0007 .0025 ± .0002 .0744 ± .0007 .0952 ± .0010 .1233 ± .0015 .0866 ± .0010 .1002 ± .0014 .0966 ± .0011 .0849 ± .0011 .0815 ± .0011 .2667 ± .0017 .2671 ± .0017 .2789 ± .0018 .2656 ± .0013 .2963 ± .0021 .2758 ± .0022 .3260 ± .0024 .2658 ± .0013 .4980 ± .0020 .4970 ± .0016 .4978 ± .0015 .4968 ± .0019 .4971 ± .0025 .4983 ± .0020 .4994 ± .0024 .4966 ± .0018

Brier .0119 ± .0005 .0999 ± .0004 .0065 ± .0003 .0390 ± .0002 .1185 ± .0008 .0135 ± .0004 .0071 ± .0002 .0069 ± .0003 .0018 ± .0005 .0944 ± .0001 .1829 ± .0028 .0338 ± .0002 .0041 ± .0002 .0033 ± .0002 .0192 ± .0014 .0025 ± .0001 .0570 ± .0004 .1964 ± .0001 .1233 ± .0015 .0960 ± .0003 .1002 ± .0014 .0915 ± .0009 .0663 ± .0008 .0653 ± .0008 .1965 ± .0007 .2158 ± .0003 .2789 ± .0018 .1933 ± .0007 .2963 ± .0021 .2708 ± .0021 .2467 ± .0012 .1937 ± .0007 .2506 ± .0000 .2529 ± .0001 .4978 ± .0015 .2527 ± .0001 .4971 ± .0025 .4745 ± .0014 .3437 ± .0015 .2530 ± .0001

Rand. err. .0235 ± .0010 .2306 ± .0009 .0065 ± .0003 .1348 ± .0005 .1185 ± .0008 .0148 ± .0004 .0077 ± .0003 .0152 ± .0006 .0036 ± .0009 .2124 ± .0002 .1829 ± .0028 .0935 ± .0003 .0041 ± .0002 .0052 ± .0005 .0713 ± .0037 .0099 ± .0007 .1120 ± .0008 .4403 ± .0002 .1233 ± .0015 .2511 ± .0006 .1002 ± .0014 .0971 ± .0010 .0953 ± .0011 .1327 ± .0028 .3890 ± .0015 .4576 ± .0003 .2789 ± .0018 .3859 ± .0013 .2963 ± .0021 .2757 ± .0022 .3655 ± .0018 .3859 ± .0014 .4999 ± .0001 .4995 ± .0002 .4978 ± .0015 .4995 ± .0002 .4971 ± .0025 .4995 ± .0019 .4977 ± .0016 .4994 ± .0002

Table 3: Average online P performance over 20 random seeds, reported as mean ± standard error. “Rand. err.” is T −1 t |Yt − pt |, the error of the randomized classifier induced by the probability forecast. Unboosted cls. and BBM output hard labels, so their Brier and randomized-error entries equal their 0/1 error. Brier agg. combines the forecasts of OGB, BBM, AdaBoost.OL, and OSBoost before observing the current label, then updates its weights after the label is revealed; it therefore maintains 400 weak learners. AdaBoost.OL’s Brier entry scores its probability of predicting one, while its randomized-error entry is the expected 0/1 loss of its randomized classifier. Entries are rounded to four decimals. Online BBM is designed to output a hard majority prediction. To check whether its Brier results P are merely an artifact of that convention, we also score the normalized raw vote (1 + −1 N i ht,i (xt ))/2 as a probability. This diagnostic is not the output analyzed by the Online BBM theorem. Figure 7 shows that the normalized vote lowers planted-decoy Brier loss from .1185 to .0838, but remains far above the best forecasting methods. On binary aggregation, the hard output has Brier loss and randomized error .0041, while the normalized vote has Brier loss .0520 and randomized error .1562. Thus a softer output helps on planted decoy but hurts substantially on binary aggregation; it does not account for the main comparisons.

38

Figure 7: Online BBM’s specified hard output versus its normalized raw vote, averaged over 20 seeds. The vote is scored directly as a probability, with no post-hoc calibration. It improves Brier loss on planted decoy but worsens randomized error there; on binary aggregation, the specified hard output is substantially better under both metrics. Algorithm Unboosted reg. Unboosted cls. Defensive OGB BBM AdaBoost.OL OSBoost Brier aggregator

Weak learners 1 1 1 100 100 100 100 400

Seconds per stream .032 .030 .046 2.959 1.478 2.292 1.753 8.482

Microseconds per round 11 10 15 986 493 764 584 2827

Table 4: Runtime summary for the implementation used in the experiments. Wall-clock times are averages over all stream/seed runs, each with T = 3000 rounds. The exact constants are implementation-dependent, but the difference in maintained learners is structural: both unboosted controls and the Defensive Booster maintain one online learner, whereas the ensemble baselines maintain many weak learners in parallel. The Brier aggregator’s time is the sum of its four constituent ensembles because all must be run. Sensitivity to baseline parameters. The main experiments use one setting for each algorithm family on every stream. Figure 8 varies, one at a time, the OGB stage step, the classification learner’s Hedge rate, and the target-edge parameter on the binary aggregation stream. Each value is .25, .5, 1, 2, or 4 times the reported setting, and each point averages 10 seeds. OGB improves steadily with its stage step but has higher Brier loss than the Defensive Booster at every tested value. Online BBM is stable across both sweeps, and AdaBoost.OL has slightly lower randomized error than the Defensive Booster at the smallest tested learning rate. OSBoost is substantially more sensitive to both its classification learning rate and target edge. Thus the main comparison does not depend on a single narrow baseline setting, although the relative ordering of the lowest-error classification methods can change.

39

Figure 8: One-at-a-time parameter sensitivity on the binary aggregation stream. The dashed blue line is the parameter-free Defensive Booster. The middle and right panels show randomized classification error; the left panel shows Brier loss. Error bars are standard errors over 10 seeds. A target-edge multiplier above one deliberately overstates the edge guaranteed by the construction and is included as a misspecification check. Figure 9 repeats the same sixteen-fold sweep on Electricity and Occupancy, the two real streams on which the Defensive Booster has the largest advantage. It retains the lowest Brier loss under every tested setting. This check does not tune the reported results: the main tables continue to use multiplier one for every dataset.

Figure 9: One-at-a-time parameter sensitivity on the complete Electricity (top) and Occupancy (bottom) streams. Multipliers range from .25 to 4. The dashed blue line is the parameter-free Defensive Booster. Every panel shows final Brier loss; lower is better. AdaBoost.OL has no targetedge parameter and therefore appears only in the middle column.

40

Takeaways. The planted-decoy stream tests identification within a large weak class, but does not require boosting: one base rule already has the correct sign on every round. Accordingly, the unboosted classifier and OSBoost have the smallest errors, and the Defensive Booster also attains low Brier and randomized error. Unboosted regression has low threshold error but poor Brier and randomized error, illustrating why probability forecasting is stricter than threshold accuracy. The unrestricted least-squares span score has loss .0887, whereas the Defensive Booster reaches .0119; this weak-to-strong behavior is not explained by span fitting. The binary aggregation stream requires genuine aggregation: no individual binary rule is perfect, and averaging all displayed rules gives zero. A hidden choice of one orientation from each pair nevertheless classifies every round correctly. The unboosted classifier has error .1829, while the Defensive Booster reaches Brier loss .0018 and randomized error .0036 using one weak learner, despite the .0860 loss floor for fixed affine span scores. At N = 100, all three weak-to-strong ensembles also reach low hard error, but each has higher Brier loss and randomized error than the Defensive Booster. The ensemble-size comparison in Figure 4 shows how these values compare with each ensemble as its number of weak learners grows. The three linear streams in Figure 6 examine Brier loss when the smooth weak-learning condition need not hold. On linear span, the offline span score has loss .0900, and the Defensive Booster attains .0570. On random-label mixture, the randomly labeled rounds provide a smooth reweighting with small weak-class edge, while the structured rounds retain an informative span comparator. OGB, the unboosted regressor, and the Defensive Booster have substantially lower Brier loss than the unboosted classifier and the classification-boosting baselines. OSBoost and Online BBM remain more competitive in randomized error than in Brier loss because randomized error depends linearly on their signed margins. Figure 3 examines the random-label mixture more closely: the Defensive Booster’s multiaccuracy and self-orthogonality errors and the weak-class edge under its mistake weighting all decay, although the weighting retains nontrivial density. Finally, on random labels, no method has a real signal; the Defensive Booster, unboosted regressor, and OGB stay near the p = 1/2 Brier-loss baseline, while the unboosted classifier and the classification boosters have larger Brier loss. The weak-class edge under the Defensive Booster’s mistake weighting remains small. Under these globally fixed tuning rules, the classification boosters are strongest on the binary aggregation stream, while OGB is strongest on the random-label mixture. The Defensive Booster is competitive with the better family in both comparisons. Table 4 shows that it does so while maintaining one online weak learner rather than an ensemble of 100 learners.

C.3

Naturally ordered real streams

Data and preprocessing. We evaluate four public binary prediction streams in their recorded order. UCI Bank Marketing predicts whether a client subscribes to a term deposit (Moro et al., 2014); we use the date order supplied by the full dataset. The MOA Electricity stream (MOA, 2011) predicts price movement in the New South Wales electricity market; the data originate in Harries’s electricity-pricing study (Harries, 1999). The MOA Airlines stream predicts whether a flight is delayed (MOA, 2011). UCI Occupancy Detection (Candanedo and Feldheim, 2016) predicts whether an office is occupied from minute-level sensor measurements, which we merge by recorded timestamp. We do not shuffle any dataset: on each round the algorithm receives the next context, predicts, and then observes its label. We use a 128-dimensional deterministic signed-hash representation and the Euclidean unitball weak class for all four datasets. Each row includes a bias feature and is normalized to unit norm. Categorical values are hashed as indicators; numeric values are standardized using unlabeled covariates from earlier rounds, clipped to five running standard deviations, and then hashed. The 41

current numeric value is transformed using the mean and variance of that feature among preceding contexts and is incorporated into those statistics only afterward. Thus no feature or label from a future round enters the current representation. For Bank Marketing we drop call duration, which is unavailable before the outcome. Occupancy uses contemporaneous temperature, humidity, light, and CO2 measurements, the derived humidity ratio, and cyclic encodings of the recorded time and weekday. The Bank, Electricity, Airlines, and Occupancy runs use all 41,188, 45,312, 539,383, and 20,560 examples, respectively. Figure 10 plots cumulative average Brier loss over each stream. Table 5 reports the final Brier, deterministic, and randomized classification errors, together with runtime.

Figure 10: Cumulative average Brier loss on the real-data streams. Top left: on Bank Marketing, OGB and the Defensive Booster are close. Top right: on Electricity, the Defensive Booster has substantially lower Brier loss than all six plotted baselines. Bottom left: on Airlines, the Defensive Booster, OGB, and the Brier aggregator are nearly indistinguishable. Bottom right: on Occupancy, the Defensive Booster has the lowest Brier loss. Each curve is the average loss incurred up to that point while processing the dataset in recorded order. The hard-label unboosted classifier is omitted for scale and reported in Table 5.

42

Dataset Bank Bank Bank Bank Bank Bank Bank Bank Bank Electricity Electricity Electricity Electricity Electricity Electricity Electricity Electricity Electricity Airlines Airlines Airlines Airlines Airlines Airlines Airlines Airlines Airlines Occupancy Occupancy Occupancy Occupancy Occupancy Occupancy Occupancy Occupancy Occupancy

Algorithm Defensive Adaptive Def. Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg. Defensive Adaptive Def. Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg. Defensive Adaptive Def. Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg. Defensive Adaptive Def. Unboosted reg. Unboosted cls. OGB BBM AdaBoost.OL OSBoost Brier agg.

0/1 .103 .103 .103 .109 .102 .103 .106 .131 .102 .108 .085 .273 .367 .219 .201 .102 .111 .102 .332 .324 .348 .390 .332 .341 .342 .370 .332 .009 .007 .052 .096 .022 .014 .011 .015 .012

Brier .080 .081 .085 .109 .079 .103 .105 .168 .079 .077 .064 .196 .367 .152 .201 .101 .117 .101 .209 .207 .219 .390 .209 .341 .342 .235 .209 .007 .007 .040 .096 .016 .014 .010 .041 .010

Base .100 .100 .100 .100 .100 .100 .100 .100 .100 .244 .244 .244 .244 .244 .244 .244 .244 .244 .247 .247 .247 .247 .247 .247 .247 .247 .247 .178 .178 .178 .178 .178 .178 .178 .178 .178

Rand. err. .159 .159 .212 .109 .157 .103 .106 .387 .148 .154 .129 .422 .367 .310 .201 .102 .280 .102 .419 .413 .451 .390 .419 .341 .342 .480 .419 .014 .013 .120 .096 .033 .014 .011 .088 .016

µs/round 14 86 10 8 803 300 522 356 1981 15 86 11 8 807 329 526 349 2011 16 89 11 10 826 352 543 362 2082 14 85 9 8 838 288 536 382 2044

Table 5: Average online performance on the real-data streams. “Base” is the Brier loss of the best constant probability forecast on the evaluated dataset. Unboosted cls. and BBM report the Brier score of their hard binary predictions. Brier agg. runs all four ensemble baselines. Runtime is reported for the same implementation and machine as Table 4. The absolute times are implementation-dependent. The basic Defensive Booster maintains one weak-class learner, Adaptive Def. maintains one at each active dyadic scale (20 for Airlines, 17 for Bank and Electricity, and 16 for Occupancy), each ensemble baseline maintains 100, and the Brier aggregator maintains 400. Among the eight methods in the main comparison, the Defensive Booster has the lowest Brier loss on Electricity and Occupancy. On Occupancy its Brier loss .007 is less than half OGB’s .016; it also has the lowest deterministic error. AdaBoost.OL has the lowest randomized error on Occupancy and the lowest two classification errors on Electricity. These distinctions are consistent with the algorithms’ objectives: the Defensive Booster is designed to forecast probabilities,

43

while AdaBoost.OL directly optimizes classification. The Brier gains are not explained merely by maintaining fewer learners: both unboosted controls are substantially worse on Electricity and Occupancy. The Brier aggregator is best on Bank by .0010 over the Defensive Booster. On Airlines, OGB has the numerically smallest Brier loss, but it, the aggregator, and the Defensive Booster differ by less than 6 · 10−5 . The unboosted regressor is also competitive on these two streams, while the classification methods are worse on Brier loss. On Electricity and Occupancy, however, the Defensive Booster’s Brier loss is respectively 61% and 82% lower than the unboosted regressor’s. The Brier aggregator maintains 400 weak learners. On the four real streams, the N = 100 ensembles take 20–60× as much wall-clock time per round as the Defensive Booster, which maintains one weak learner; the Brier aggregator takes about 130–150× as much. The separate Brier and classification columns matter here: a boosted margin method can classify accurately without producing the most accurate probability forecasts.

D

Extension to bounded real-valued outcomes

It is evident that the Defensive Booster, as it is defined, does not require that the outcomes be binary; it can be applied essentially without modification in a regression setting with bounded scalar labels. We will now briefly state and discuss this natural extension: in a nutshell, the Defensive Booster’s span guarantee is satisfied in the exact same way as in the binary setting. Then, we will evaluate this extension on three chronological regression streams — in these experiments, the Defensive Booster has 17–29% lower normalized mean squared error than 100-stage online gradient boosting while maintaining one weak-class learner; OGB takes 65–70× as much wall-clock time per round in our implementation. To begin, suppose that Yt ∈ [0, 1] and that pt ∈ [0, 1] is interpreted as a prediction of the bounded outcome. Retain the affine encoding σt = 2Yt − 1,

µt = 2pt − 1,

rt = 2(Yt − pt ).

The Defensive Booster is unchanged; also note that outcomes in any other fixed bounded interval reduce to this setting by affine rescaling. It is now easy to see that the span guarantee remains the same. Proposition D.1 (Certificate and span guarantee for bounded outcomes). For every adaptive sequence with Yt ∈ [0, 1], the Defensive Booster satisfies the multiaccuracy and self-orthogonality guarantees of Theorem 3.3, with T X ST = 4 (Yt − pt )2 . t=1

In particular, writing L2,T

= T −1

2 t (Yt − pt ) , for every f ∈ spanΛ (H),

P

T

1X ΛAH + AS p ΛBH + BS √ L2,T ≤ (Yt − qf (xt ))2 + L2,T + . T 2T T t=1

The low-loss conclusion of Corollary 4.2 also holds with BT and Bf interpreted as the corresponding average squared errors. Proof. Lemma 3.2 already permits every σt ∈ [−1, 1]. The proof of Theorem 3.3 therefore applies unchanged. The proof of Theorem 4.1 then uses only that certificate and the same squared-loss expansion, so it also applies unchanged. 44

D.1

Regression experiments with bounded outcomes

We test the Defensive Booster beyond binary outcomes on three public regression datasets, processed in timestamp order. Appliance energy records household appliance use every ten minutes together with indoor and outdoor sensor measurements (Candanedo, 2017). Bike demand records hourly Capital Bikeshare rentals with calendar and weather variables (Fanaee-T, 2013). Interstate traffic records hourly westbound I-94 traffic volume with calendar and weather variables (Hogue, 2019). We normalize each target by a fixed upper bound R: 2000 Wh for Appliance Energy, 2000 rentals per hour for Bike Demand, and 10000 vehicles per hour for Interstate Traffic. We map a target Yt ∈ [0, R] to Yt /R ∈ [0, 1] and map a normalized forecast pt back to Rpt . Thus (Yt /R − pt )2 = (Yt − Rpt )2 /R2 , so normalized MSE and root mean squared error in the original units differ only by the fixed factor R. Every observed target lies in its stated interval, so this normalization clips no outcome. We use the first 10% of each stream as a common chronological initialization prefix and report losses on the remaining 90%. Thereafter, each algorithm receives the current context, predicts, observes the target, and updates. Numeric features are standardized using statistics from strictly earlier rows. Each context contains calendar variables and the available sensor or weather measurements. Bike and Traffic additionally use targets observed exactly one hour, one day, and one week earlier when those timestamps exist; Appliance Energy uses lags of ten minutes, one hour, and one day. We omit simultaneous light consumption and two random decoy columns from Appliance Energy. We omit the casual and registered rental counts from Bike because they sum to the target, and collapse duplicate weather reports at a Traffic timestamp. All learned methods (except the past-outcome mean baseline) receive the same 128-dimensional signed feature-hashed context, rescaled to have Euclidean norm at most one, and use the same unit-ball linear weak class. Algorithmic hyperparameters are fixed across datasets. The Defensive Booster maintains one second-order linear oracle; OGB maintains N = 100 such oracles and uses the stage step η = (log N )/N from the binary experiments. Two controls use either one unboosted squared-loss learner or the mean of targets observed before the current round. Figure 11 plots cumulative mean squared error on the normalized targets, and Table 6 reports final normalized MSE and root mean squared error in the original units.

Figure 11: Cumulative mean squared error after the common chronological initialization prefix. The Defensive Booster and unboosted control each maintain one weak-class learner, whereas online gradient boosting maintains 100. The Defensive Booster has the lowest final loss on all three streams. 45

Dataset Appliance energy Bike demand Interstate traffic

Rounds 17,762 15,642 36,518

Normalized MSE Defensive OGB .0013443 .0016461 .0013440 .0018824 .0038040 .0045762

Raw-unit RMSE Defensive OGB 73.330 81.145 73.322 86.773 616.769 676.473

OGB time / Defensive 64.7× 65.9× 69.6×

Table 6: Final regression performance after the common chronological initialization prefix; lower error is better. Raw-unit RMSE is measured in Wh, rentals per hour, and vehicles per hour, respectively. The final column is the ratio of OGB’s wall-clock time per round to the Defensive Booster’s on the same machine. Absolute runtimes depend on the implementation, whereas OGB’s 100 maintained weak-class learners versus the Defensive Booster’s one is an algorithmic difference. The Defensive Booster reduces normalized MSE relative to OGB by 18% on Appliance Energy, 29% on Bike Demand, and 17% on Interstate Traffic. On Bike and Traffic, both controls are substantially worse, so the improvement does not come merely from predicting the running mean or from applying the shared weak learner once. Thus the empirical advantage extends beyond binary outcomes: on each stream, the Defensive Booster obtains lower squared error than the 100-learner OGB ensemble while maintaining one weak-class learner.

E

Strongly adaptive experiments

We next compare the basic Defensive Booster with its strongly adaptive variant from Section 5. The implementation uses the canonical dyadic interval family and the Adapt-ML-Prod secondorder aggregation rule with the sleeping-expert confidence reduction of Gaillard et al. (2014). The weak-class and scalar states are vectorized across scales, which reduces implementation overhead without changing their updates. This variant introduces no dataset-specific parameter: the same second-order weak oracle and scalar routines are used at every scale. The Adaptive Def. rows in Table 5 report its full-stream performance. On Electricity, strong adaptivity lowers Brier loss from .0772 to .0644, deterministic error from .1077 to .0851, and randomized error from .1538 to .1289. It also lowers Airlines Brier loss from .2094 to .2066 and Occupancy Brier loss from .0071 to .0069; on Bank it increases Brier loss from .0800 to .0807. The adaptive implementation takes 85–89 microseconds per round, about six times the basic forecaster but still substantially less than the 100-learner ensembles in Table 5. Figure 12 compares the methods’ trailing-window losses and shows when these full-stream improvements occur.

46

Figure 12: Local performance of the basic and strongly adaptive Defensive Boosters on all four real streams. Each curve is the trailing 1,000-round Brier loss; the same window is fixed for every dataset. The adaptive variant tracks the basic forecaster closely on Bank and Airlines, while on Electricity it improves substantially during the later high-loss portions of the stream. Occupancy is mixed locally but favors the adaptive variant in full-stream loss. Table 5 reports the corresponding full-stream averages. Controlled drift benchmark. To isolate adaptation to distribution shift, we additionally use the INSECTS optical-sensor benchmark of Souza et al. (2020). Each example is an optical-sensor recording of mosquito flight. The benchmark orders these examples using a hidden temperature variable to produce known abrupt, incremental-gradual, and recurring drift patterns. We use all five balanced variants and preserve each released order. Because our setting is binary, we fix one target for the entire benchmark: recognize Aedes albopictus (either sex) versus Aedes aegypti or Culex quinquefasciatus. Each of the six source classes has equal frequency, so the binary target has positive rate 1/3. The 33 numeric signal features receive the same prefix-only standardization and row normalization as the other real streams. Neither algorithm is given the temperature, the drift type, or the change points. Table 7 reports full-stream performance for all five released orderings.

47

Drift pattern

Rounds

Abrupt Incremental-gradual Incremental-abrupt recurring Incremental recurring Incremental

52,848 24,150 79,986 79,986 57,018

Brier loss Basic Adaptive .1307 .1198 .0905 .0877 .0871 .0813 .0829 .0769 .1700 .1711

0/1 error Basic Adaptive .1905 .1697 .1321 .1235 .1231 .1148 .1151 .1064 .2535 .2547

Table 7: Average online performance on five controlled-drift INSECTS streams; lower is better. “Basic” is the Defensive Booster, which maintains one weak learner; “Adaptive” is its strongly adaptive variant. The binary task and all algorithmic choices are fixed across rows. The adaptive variant lowers both metrics on the four streams that combine abrupt, gradual, or recurring shifts. On the continuously incremental stream, the methods differ by at most .0012. The adaptive implementation takes 83–85 microseconds per round. On the four original real streams, Table 5 shows that the adaptive method is slower than the basic forecaster but remains 3–10× faster than the 100-learner ensembles. Figure 13 shows the local Brier losses around the published change points for two representative streams.

Figure 13: Local Brier loss on the abrupt and incremental-gradual INSECTS streams. Curves are trailing 1,000-round averages; dotted lines mark the change points published with the benchmark. The adaptive forecaster reduces several of the largest post-shift loss spikes. The interval guarantee also produces local hard-core witnesses. Figure 14 examines these witnesses on the abrupt INSECTS stream. For each selected endpoint t and dyadic length L, it computes the mistake weighting on the trailing interval I = [t − L + 1, t] and reports both quantities that define its hard-core quality: density and normalized weak-class edge.

48

Figure 14: Evolution of local hard-core witnesses for the strongly adaptive Defensive Booster on the abrupt INSECTS stream. Each pixel represents the mistake weights ws = |Ys − ps | on one trailing interval I = [t − L + 1, t]: the horizontal axis isPits endpoint t, and the vertical axis is its dyadic length L. The left panel gives the density |I|−1 s∈I ws ; the right gives edgeH (w). Bright regions on the left paired with dark regions on the right are smooth, low-edge local hard-core witnesses. Dotted lines mark the five published abrupt change points; white regions precede the first complete interval at a given scale.

49

Related documents

• Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselines#1144073
• Sharp Characterization of Bias in Post-Bandit Inference#1052257
• Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms#168335
• A robust machine learning framework for detecting temporal drift in financial fraud prevention.#659880
• Cost-Aware Best-LLM Identification using Dueling Feedback#1104559