PaperlayerView exact revision on arXiv

Source-linked AI summary

Defensive Boosting for Online Probabilistic Forecasting

Georgy Noarov, Aaron Roth

arXiv:2608.13554v1cs.LGcs.CCcs.DSstat.ML

TL;DR

Online probabilistic forecasting needs one efficient booster that combines span-competitive Brier performance with weak-to-strong classification guarantees. The Defensive Booster achieves both through defensive forecasting, including an O(1/T) bound in the realizable span case and weak-learning guarantees at the target rate.

  • Problem

    Existing online boosting methods separately provide span-competitive Brier guarantees or weak-to-strong classification guarantees, leaving their combination as an open forecasting objective.

  • Method

    The Defensive Booster is a simple black-box reduction that uses defensive forecasting with weak-class and self-orthogonality auditors.

  • Results

    The method matches gradient-boosting-style span guarantees, achieves an O(1/T) bound in realizable cases, and converts smooth weak learning into strong classification at the target rate.

  • Takeaways & Limitations

    The approach provides a unified, efficient route to both probabilistic forecasting and weak-to-strong boosting guarantees.

  • Takeaways & Limitations

    The analysis assumes a symmetric weak class H, while its weak-to-strong guarantee is conditional on a (ρ, γ)-smooth weak-learning condition.

Abstract

from arXiv · show

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 weak-learning 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 algorithm'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 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

The Defensive Booster is a single-oracle online forecasting algorithm that combines unconditional span-comparator guarantees with conditional weak-to-strong classification guarantees on adaptive sequences. It also provides hard-core failure certificates, strongly adaptive interval guarantees, and extensions beyond binary outcomes.

  • Main guarantees: The Defensive Booster simultaneously matches online gradient boosting on every adaptive sequence and achieves weak-to-strong guarantees whenever the realized transcript satisfies smooth weak learnability.These guarantees are incomparable, so neither the span comparator nor the weak-learning condition subsumes the other.
  • Span guarantee: On every adaptive sequence, its Brier score competes with every predictor induced by the Λ-norm-bounded span of H at the same rate as online gradient boosting.The second-order bound yields O(1/T) in the realizable span case.
  • Weak-to-strong guarantee: Under the (ρ, γ)-smooth weak-learning condition, both Brier score and randomized classification error are at most max{ρ, ˜O(1/(γ^2T))}.If ρ = O(ε), both errors reach ε after ˜O(1/(γ^2ε)) rounds; thresholding forecasts at 1/2 gives deterministic error at most twice the randomized error.
  • Failure certificate: Persistent large error yields an ex-post hard-core certificate: mistake weights form a smooth reweighting on which every weak hypothesis has low edge, certifying failure of the weak-learning condition.The certificate uses the dual view of boosting and turns the weak-learning condition into a contradiction when error remains high.
  • Extensions: A strongly adaptive variant uses O(log T) active oracle copies to provide both guarantees, up to polylogarithmic factors, on every contiguous interval.The algorithm also preserves the squared-loss span guarantee for arbitrary bounded real-valued outcomes and evaluates that extension on chronological regression streams.
  • Method and efficiency: Unlike ensemble-based online boosting, the Defensive Booster maintains one weak learner and two scalar adaptive-gradient states, requiring one oracle call plus O(1) arithmetic per round.Its forecasts are probability-valued and operationalize the dual view rather than combining many weak-learner copies.

2 Setting and algorithmic ingredients

The paper studies sequential Brier forecasting against an adaptive adversary, using a [−1,1] encoding to formulate multiaccuracy and self-orthogonality. Its algorithmic toolkit assumes a symmetric weak class with a second-order oracle and uses scalar adaptive OGD for the remaining one-dimensional updates.

  • Online forecasting: On each round, the adversary reveals x_t, the learner predicts p_t ∈ [0,1], then observes binary Y_t and incurs Brier loss (Y_t − p_t)^2.The sequence may adapt to the learner’s past predictions; the binary setup supports both probability and classification interpretations.
  • Weak class and comparators: The weak class H contains functions X → [−1,1] and is assumed symmetric; otherwise the learner augments it with negated hypotheses and runs on both signs.The framework also defines norm-bounded spans and rescales span comparators to the probability scale, although the resulting forecasts need not lie in [0,1].
  • Forecast representation: The [−1,1] encoding sets σ_t = 2Y_t − 1, μ_t = 2p_t − 1, and residual r_t = σ_t − μ_t = 2(Y_t − p_t).Multiaccuracy tests residuals against H, while self-orthogonality tests them against the forecast itself.
  • Weak-class oracle: The sole problem-dependent primitive is a second-order weak-class oracle whose regret scales with the square root of cumulative squared coefficients, here supplied by forecast residuals.This self-bounding residual-energy structure yields a 1/(γ^2ε) weak-to-strong sample complexity, versus 1/(γ^2ε^2) for a first-order guarantee, matching the prior model’s optimal rate despite using a stronger oracle model [Beygelzimer et al., 2015b].
  • Class-independent machinery: All remaining online machinery is class-independent: the method uses two copies of scalar adaptive OGD, which projects updates onto [−1,1] and satisfies a second-order scalar regret bound.The routine initializes a_1 = 0 and V_0 = 4; finite classes admit second-order experts implementations, while broader classes can use adaptive or scale-free online linear optimization.

3 The Defensive Booster

The Defensive Booster combines one weak-class oracle with two scalar adaptive-OGD states and computes each forecast by an exact one-dimensional root rule. This construction yields second-order multiaccuracy and self-orthogonality guarantees on every adaptive binary sequence while avoiding an explicit weak-hypothesis ensemble.

  • Algorithm: The Defensive Booster combines a weak-class oracle with self-auditor state S and auditor-aggregation state A, using only one-dimensional scalar adaptive OGD routines.S establishes self-orthogonality, while A aggregates the weak-class and self auditors.
  • Algorithm: Each round, it forms the affine function F_t(µ)=q_H,t b_H,t+q_S,t θ_t µ, selects µ_t by the root rule, and forecasts p_t=(1+µ_t)/2.The root is computable in constant time, so each round requires one oracle prediction/update plus O(1) arithmetic.
  • Algorithm: The forecast is a probability produced directly by an exact affine root, not a linear combination or weighted vote of weak hypotheses.The method is described as a deterministic one-dimensional instance of the online-learning and variational-inequality framework of Farina and Perdomo (2026).
  • Guarantees: The root rule makes the aggregated auditor gain nonpositive on every round, allowing endpoint comparisons to control both weak-class and self-auditor cumulative gains.The two endpoint comparators correspond to always selecting the weak-class auditor or always selecting the self auditor.
  • Guarantees: Theorem 3.3 establishes second-order multiaccuracy with respect to H and self-orthogonality, with constants A_H=a_H+4, B_H=b_H+8, A_S=8, and B_S=16.The theorem applies to every adaptive sequence with binary labels, with the displayed multiaccuracy rate involving √S_T+B_H.

4 Main guarantees

The section establishes parallel Brier/span-regret and hard-core weak-to-strong guarantees: the former holds on every adaptive sequence, while the latter applies when the realized transcript satisfies smooth weak learning. The key bridge is that the Booster’s mistake weighting has low edge unless its Brier and classification errors are already small.

  • 4.1 Brier/span guarantee: The Defensive Booster achieves the Brier/span guarantee for every adaptive binary sequence and every f ∈spanΛ(H), also covering conv(H) when Λ = 1.
  • 4.1 Brier/span guarantee: When the comparator has zero loss, the resulting Brier loss satisfies BT = O((C^2 + D)/T).
  • 4.2 Hard-core mistake weighting: The smooth weak-learning condition is ex post, and its bounded smooth reweightings are equivalent to the smooth distributions used by SmoothBoost and hard-core constructions.
  • 4.2 Hard-core mistake weighting: Theorem 4.4 shows that the Booster’s randomized mistake weighting yields a hard-core certificate through an edge bound against every h ∈H.The weighting is wt = |Yt − pt|, so the certificate concerns the algorithm’s own realized mistakes.
  • 4.3 Weak-to-strong rate: Under the (ρ0, γ0)-smooth weak-learning condition, Brier, randomized classification, and thresholded deterministic classification errors are all at most ε up to constants.The threshold classifier’s average classification error is at most 2ρw; achieving target error ε requires smoothness ρ0 = O(ε), with 1/(γ0^2ε) dependence when BH is logarithmic or lower order.

5 Boosting on every interval

The strongly adaptive Defensive Booster extends both forecasting guarantees from the full horizon to every contiguous interval, up to polylogarithmic factors. It preserves local weak-to-strong rates while retaining span-regret without weak-learning assumptions, at the cost of logarithmic overhead and multiple active oracle copies.

  • Interval wrapper: The second-order specialist wrapper preserves dependence on local residual energy, avoiding the rate loss that an ordinary O(|I|) interval-regret bound would cause.It combines fresh learners on dyadic intervals with a second-order confidence-rated experts algorithm.
  • Implementation: The wrapper maintains at most 1 + ⌈log_2 T⌉ active copies of the weak learner per round, imposing explicit logarithmic overhead.The same wrapper is applied separately to the weak-class oracle and both scalar routines.
  • Strongly adaptive Defensive Booster: Theorem 5.2 provides simultaneous interval certificates for every adaptive binary sequence and every interval I, extending the Defensive Booster’s two guarantees beyond the full horizon.The construction applies a second-order interval wrapper to the weak-class oracle and scalar routines, then reuses the original root rule.
  • Strongly adaptive boosting: On every interval, mistake weights form a local hard-core witness when ρ_I > 0, while the threshold classifier has error at most 2ρ_I.These conclusions follow by applying the full-horizon certificate arguments locally on I.
  • Strongly adaptive boosting: When the local weak-learning condition holds with ρ_0 = O(ε), target interval error ε requires n = O(log^2(T)/(γ_0^2ε)); span-regret remains unconditional.The guarantees hold simultaneously, so the interval and span comparator can be selected after observing the transcript, without assumptions outside I.

6 Experiments

Experiments show that the Defensive Booster tracks the stronger baseline family on complementary synthetic streams while using one learner, and its mistake weights exhibit the predicted smooth, low-edge hard-core witness. It also retains competitive predictive performance under a fixed, non-stream-specific tuning protocol.

  • Protocol: The experiments compare the Defensive Booster with online gradient boosting, online weak-to-strong boosting, the Brier aggregator, and unboosted controls on two controlled synthetic streams and four naturally ordered real datasets.The synthetic streams separately test the span guarantee and the smooth weak-learning condition; real streams are processed in recorded order.
  • Results: The Defensive Booster reaches .0026 classification error and .0018 Brier loss on the binary aggregation stream, outperforming OGB and every individual ensemble while using one learner rather than 100.OGB has .0331 error; the Brier aggregator’s loss is .0025.
  • Results: On the random-label mixture, the Defensive Booster’s .1965 Brier loss remains close to OGB’s .1933 and beats all weak-to-strong boosters, showing competitiveness when their guarantee does not apply.The Brier aggregator reaches .1937 while OSBoost, AdaBoost.OL, and Online BBM reach .2467, .2708, and .2963.
  • Results: On the random-label mixture, multiaccuracy and self-orthogonality errors and weak-class edge decay while mistake-weight density remains nontrivial, producing the predicted smooth, low-edge witness.The diagnostics are averaged over 20 seeds, and randomized error remains nontrivial because of the random-label component.
  • One learner versus an ensemble: The Defensive Booster and unboosted controls scale as CH + O(1) per round, whereas each ensemble baseline costs NCH + O(N), and the Brier aggregator runs all four ensembles.Each boosting baseline maintains N = 100 learners in the reported protocol, while the aggregator therefore runs 400 learners.
  • Results: Across the synthetic streams, OGB is strongest when an informative span comparator exists, classification boosters are strongest under smooth weak learning, and the Defensive Booster remains competitive on both under common tuning.All synthetic results use T = 3000 and means over 20 seeds; real streams are processed once without shuffling.

7 Related work

The work connects defensive boosting to online gradient and weak-to-strong boosting, strongly adaptive learning, smooth boosting and hard-core constructions, multicalibration, and defensive forecasting. Its closest precedents motivate the span-regret, classification, interval-adaptive, and transcript-certificate aspects of the approach.

  • Online gradient boosting: Online gradient boosting uses multiple online learners to compete with convex hulls or norm-bounded spans, while related work studies gradient boosting on adversarial streams and convex-hull regret.Beygelzimer et al. (2015a) use N copies for smooth convex losses; Hu et al. (2017) extend analyses to adversarial streams under stronger edge assumptions; Hazan and Singh (2021) use a multiplicative weak learner.
  • Online weak-to-strong boosting: Online weak-to-strong boosting ranges from SmoothBoost-based methods to rate-optimal Online BBM under weak online learnability assumptions.Oza and Russell (2001) initiated practical online bagging and boosting; Chen et al. (2012) adapted SmoothBoost using smooth distributions; Beygelzimer et al. (2015b) provided Online BBM and matching lower bounds in their model.
  • Strong adaptivity: Strongly adaptive learning obtains low regret on every contiguous interval through geometric-cover reductions or local-energy confidence bounds, unlike parameter-free adaptivity.Daniely et al. (2015), Cutkosky (2020), and Gaillard et al. (2014) provide relevant machinery, while Beygelzimer et al. (2015b) is adaptive but not strongly adaptive in the interval sense.
  • Smooth boosting and hard-core sets: The paper’s smooth transcript reweightings relate boosting’s minimax and hard-core-set traditions, including smooth boosting, agnostic adaptive boosting, and algorithmic hard-core constructions.The cited foundations include Servedio (2003), Gavinsky (2003), Freund and Schapire (1996), Impagliazzo (1995), Klivans and Servedio (2003), and Barak et al. (2009).
  • Multicalibration and hard-core measures: Its weak-to-strong analysis uses the connection between multiaccuracy and hard-core measures, requiring only multiaccuracy rather than stronger calibrated variants.This connects to Trevisan et al. (2009), Casacuberta et al. (2024), and Casacuberta et al. (2025), while sequential adversarial calibration presents an online limitation.
  • Defensive forecasting: The algorithm is developed within defensive forecasting, where probabilities block continuous skeptic betting strategies and support second-guessing experts whose advice depends on the current forecast.Vovk et al. (2005a,b) introduced the framework, and Vovk (2007) established its second-guessing capability, matching the affine test used in the root rule.

A Deferred proofs … A.3 Strongly adaptive extension

The appendix supplies proofs for the paper’s online-learning tools, full-horizon certificate consequences, and strongly adaptive extension. The adaptive construction uses dyadic specialist intervals and confidence-rated aggregation to establish interval guarantees and the self-orthogonality inequality.

  • A Deferred proofs: The appendix collects proofs of the standard online-learning tools and routine consequences used in the main text.
  • A.1 Scalar second-order regret: The scalar second-order regret proof uses a nonincreasing learning rate, projection nonexpansiveness, bounded gradients, and a final square-root inequality.It sets η_t = 1/√V_{t−1}, bounds the first terms by 2√V_T, and bounds the second terms using g_t^2 ≤ 4 ≤ V_{t−1}.
  • A.2 Consequences of the full-horizon certificate: The full-horizon certificate yields the stated randomized-error bound by splitting on whether the weighted residual average is below or above the weak-learning threshold.When the threshold is met, the smooth weak-learning condition and Theorem 4.4 provide the bound; otherwise the certificate directly controls the error.
  • A.2 Consequences of the full-horizon certificate: The same certificate also bounds deterministic threshold error by twice the weighted residual average, since every threshold mistake has residual magnitude at least 1/2.
  • A.3 Strongly adaptive extension: The strongly adaptive construction starts fresh booster copies on a canonical dyadic interval family containing fewer than 4T intervals, with at most 1 + ⌈log2 T⌉ active per round.An arbitrary interval is decomposed into at most M_T dyadic members, and active copies are aggregated by a second-order confidence-rated experts algorithm.
  • A.3 Strongly adaptive extension: Confidence-regret reduction and second-order excess-loss bounds combine the dyadic copies with interval comparators, using Cauchy–Schwarz to prove the strongly adaptive guarantee.
  • A.3 Strongly adaptive extension: Unknown horizons are handled by restarting the fixed-horizon construction on doubling epochs, adding logarithmic factors while keeping only the current epoch’s wrapper active.Any interval intersects at most 1 + ⌈log2 T⌉ epochs; the second-order and additive terms each receive a factor 1 + ⌈log2 T⌉.
  • A.3 Strongly adaptive extension: For every interval, the root sign property makes aggregated auditor gain nonpositive, while interval regret against endpoint, weak-oracle, and sign comparators establishes self-orthogonality.Taking both signs and using symmetry of H yields the absolute-value form of the inequality.

B Separation: the guarantees are incomparable · C Additional experimental details and results

The Brier/span and weak-to-strong guarantees are incomparable: either smooth weak learning can coexist with constant span loss, or a small uninformative subset can destroy weak learning while affecting average span loss little. The binary experiments separately measure these guarantees using Brier/span competition and randomized classification error.

  • B Separation: the guarantees are incomparable: The two guarantees are incomparable: positive weak-class edge under every reweighting can coexist with constant squared loss for every span-induced score.This contrast arises because squared loss depends on numerical scores, whereas weak-to-strong boosting can exploit their signs.
  • B Separation: the guarantees are incomparable: Under the first separation, a uniform hypothesis average classifies perfectly even though no single hypothesis is always correct, while every span score incurs nonzero loss.The average has positive signed margin on every round, but the best squared loss is (1−δ)^2/(8(1+δ^2)).
  • B Separation: the guarantees are incomparable: The first separation persists after clipping span scores with any fixed coefficient-norm budget: the transcript’s average Brier loss remains at least 1/(8(Λ + 1)^2) when δ ≤1/(2Λ).Clipping therefore does not eliminate the separation under bounded norms.
  • B Separation: the guarantees are incomparable: As δ approaches zero, the span’s best squared loss approaches 1/8 while the Defensive Booster’s Brier score and classification error vanish under smooth weak learning.Thus span-regret alone can permit constant loss on transcripts where the smooth weak-learning condition forces near-perfect prediction.
  • B Separation: the guarantees are incomparable: Conversely, the smooth weak-learning condition can fail on a subset of density m/T while the span comparator still achieves average squared loss m/(4T).The comparator predicts perfectly outside the subset and outputs probability 1/2 on it, so the subset contributes little when m/T is small.
  • B Separation: the guarantees are incomparable: The converse construction uses a reweighting supported on the exceptional subset whose weak-class edge is zero, proving failure of every smooth condition with ρ ≤ m/T.The same subset is where the two hypotheses disagree in opposite ways, while they agree with the labels elsewhere.
  • C Additional experimental details and results: The binary experiments separately evaluate span competition with Brier loss and an offline least-squares comparator, and weak-to-strong performance with randomized classification error.The latter equals the density of the forecaster’s mistake weighting; real streams preserve recorded example order, while regression and strongly adaptive experiments appear in Appendices D.1 and E.

C.1 Protocol and implementation

The comparison evaluates eight methods, including Defensive, strongly adaptive Defensive, unboosted controls, ensemble baselines, and a Brier aggregator. Implementations standardize probability outputs, use predeclared tuning and stream protocols, and compare substantially different computational costs.

  • Algorithms: The main comparison includes eight methods: Defensive, strongly adaptive Defensive, two unboosted controls, four ensemble baselines, and Brier aggregator.Defensive uses two class-independent scalar adaptive-OGD states; strongly adaptive Defensive maintains one weak learner at each active dyadic scale.
  • Algorithms: The unboosted controls isolate boosting’s contribution by pairing squared-loss regression over the weak class with the base online binary classifier used by three boosting baselines.Both controls maintain a single learner.
  • Algorithms: The ensemble baselines use 100 weak learners in the main comparison, while a Brier aggregator combines their probabilities with exponential weights and incurs at most 2 log 4 excess cumulative Brier loss.The learner-count sweep evaluates ensemble sizes N ∈ {1, 5, 20, 100}.
  • Experimental protocol: Experiments use one predeclared tuning rule per algorithm family; synthetic results average 20 seeds over T = 3000 rounds, whereas real streams retain chronological order and use one deterministic run.The experiments directory contains generators, loaders, implementations, and commands for every reported result.
  • Runtime: Defensive and unboosted controls cost CH + O(1) per round, while ensemble baselines cost NCH + O(N), with OSBoost adding O(N log N) simplex projection overhead.Here CH is the cost of one weak-class learner prediction/update, and main-comparison ensembles use N = 100.

C.2 Controlled synthetic streams

Controlled synthetic streams separate weak-learning-condition behavior from span-comparator behavior. The Defensive Booster aggregates effectively on binary aggregation and remains competitive on linear streams where the two guarantees diverge, using one weak learner.

  • Experimental design: The five streams distinguish smooth weak-learning-condition tests from span-competition tests: planted decoy and binary aggregation satisfy the condition, while the three linear streams include noisy labels or weak signal.The finite-class streams expose only vectors of weak-rule values, whereas the linear streams use the Euclidean unit ball.
  • Planted decoy: On planted decoy, where one hidden base rule is sign-perfect, the unboosted classifier and OSBoost identify it fastest, while the Defensive Booster also reaches low error.This stream tests identification within a large weak class rather than requiring boosting.
  • Linear streams: On the three linear streams, the Defensive Booster attains .0570 Brier loss versus .0900 for the offline span score on linear span and remains competitive with the better method families across comparisons.On random-label mixture, OGB, the unboosted regressor, and the Defensive Booster outperform classification-boosting baselines; OGB is strongest there, while the Defensive Booster is competitive with the better family in both comparisons.
  • Efficiency: The Defensive Booster achieves these comparisons with one online weak learner rather than an ensemble of 100 learners.Table 4 reports this efficiency under globally fixed tuning rules.

C.3 Naturally ordered real streams · D Extension to bounded real-valued outcomes

On chronological real-data streams, the Defensive Booster achieves the strongest Brier performance on Electricity and Occupancy while remaining competitive on Bank Marketing and Airlines. The method also extends unchanged to bounded real-valued outcomes, preserving its span and low-loss guarantees after affine encoding.

  • C.3 Naturally ordered real streams: The real-stream evaluation uses four public binary prediction streams in recorded chronological order: Bank Marketing, Electricity, Airlines, and Occupancy.All datasets use a 128-dimensional deterministic signed-hash representation and the Euclidean unit-ball weak class.
  • C.3 Naturally ordered real streams: The preprocessing is causal: current numeric values use preceding-context statistics, future features and labels never enter the representation, and Bank Marketing drops unavailable call duration.Rows include a bias feature and are normalized to unit norm; numeric values are standardized, clipped to five running standard deviations, and hashed.
  • C.3 Naturally ordered real streams: The Defensive Booster has the lowest Brier loss on Electricity and Occupancy; on Occupancy, its .007 loss is less than half OGB’s .016.Figure 10 reports substantially lower Brier loss than all six plotted baselines on Electricity and the lowest loss on Occupancy; the method also has the lowest deterministic error on Occupancy.
  • C.3 Naturally ordered real streams: AdaBoost.OL has the lowest randomized error on Occupancy and the lowest two classification errors on Electricity, matching its direct classification objective.The Defensive Booster instead targets probabilistic forecasting, and its Brier gains are not explained merely by maintaining fewer learners because both unboosted controls perform substantially worse on Electricity and Occupancy.
  • C.3 Naturally ordered real streams: The Brier aggregator is best on Bank Marketing by .0010, while OGB is smallest on Airlines, where the three methods differ by less than 6·10−5.On Bank Marketing, OGB and the Defensive Booster are close; on Airlines, the unboosted regressor is also competitive.
  • D Extension to bounded real-valued outcomes: For outcomes Y_t in [0,1], affine encoding σ_t = 2Y_t −1, μ_t = 2p_t −1, and r_t = 2(Y_t −p_t) lets the unchanged Defensive Booster operate on bounded regression streams.Any other fixed bounded interval reduces to this setting by affine rescaling.
  • D Extension to bounded real-valued outcomes: For every adaptive sequence with Y_t ∈[0,1], Proposition D.1 preserves the multiaccuracy and self-orthogonality guarantees of Theorem 3.3 and the corresponding average-squared-error low-loss conclusion.The proofs carry over unchanged because Lemma 3.2 permits σ_t ∈[−1,1] and the later argument uses the same certificate and squared-loss expansion.

D.1 Regression experiments with bounded outcomes

Across three timestamp-ordered bounded-outcome regression streams, the Defensive Booster achieves the lowest final squared error, outperforming 100-learner online gradient boosting while using only one weak learner. Its advantage persists against unboosted and running-mean controls under a common chronological evaluation protocol.

  • Datasets: The experiments cover Appliance Energy, Bike Demand, and Interstate Traffic, with normalized MSE and original-unit RMSE differing only by a fixed scale factor and no outcome clipping.The three streams contain household appliance use, bike rentals, and westbound I-94 traffic volume with associated sensor, calendar, or weather measurements.
  • Experimental setup: The evaluation uses the first 10% of each chronologically ordered stream for initialization and reports predictions on the remaining 90%, with features standardized only from earlier rows.Contexts include calendar, sensor, and weather variables; Bike and Traffic also include targets observed one hour, one day, and one week earlier.
  • Experimental setup: All learned methods share a 128-dimensional normalized feature-hashed context, a unit-ball linear weak class, and fixed hyperparameters across datasets.The Defensive Booster uses one second-order linear oracle, whereas OGB maintains N = 100 such oracles.
  • Results: 18%, 29%, and 17% lower normalized MSE than OGB on Appliance Energy, Bike Demand, and Interstate Traffic, respectively, with the lowest final loss on every stream.Both controls are substantially worse on Bike and Traffic, so the gains are not explained by predicting the running mean or applying the shared weak learner once.

E Strongly adaptive experiments

Strong adaptivity improves performance under distribution shifts while retaining efficient online updates. It also produces local hard-core witnesses that connect interval-level forecasting behavior to weak-class edge conditions.

  • Real-stream comparison: 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, but increases Bank Brier loss from .0800 to .0807.
  • Implementation and efficiency: Strong adaptivity costs about six times the basic forecaster’s runtime but remains 3–10× faster than 100-learner ensembles on the original real streams.The adaptive implementation takes 85–89 microseconds per round on the real streams and 83–85 microseconds per round on INSECTS.
  • Real-stream comparison: The adaptive variant tracks the basic forecaster closely on Bank and Airlines, improves later high-loss Electricity segments, and favors adaptivity in Occupancy full-stream loss.These local comparisons use trailing 1,000-round Brier losses with the same window across datasets.
  • Controlled drift benchmark: Adaptive boosting lowers both metrics on four controlled-drift INSECTS streams, while differences on the continuously incremental stream are at most .0012.The adaptive implementation takes 83–85 microseconds per round.
  • Local hard-core witnesses: Local hard-core witnesses are identified by dense mistake weights paired with low normalized weak-class edge across trailing dyadic intervals.Figure 14 visualizes these witnesses on the abrupt INSECTS stream, with dotted lines marking five published change points.
Loading 2608.13554v1…