acceptodds
Under review as a conference paper at ICLR 2027

Defensive Boosting for Online Probabilistic Forecasting

Abstract

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class , 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 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 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 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 strong predictive performance coupled with orders-of-magnitude faster runtime.

Primary area:
learning theory
Keywords:
boosting, online learning, multicalibration, calibration

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_53QdOpenReview ↗
Rating
4(+2)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the following online probabilistic forecasting setting (I’ll deviate slightly from the paper’s notation for clarity).

For time t=1,…Tt = 1, \ldots T, a learner will receive a stream of instances xtx_t and will be asked to predict its binary label f(xt)∈{−1,+1}f(x_t) \in \{-1, +1\} with respect to the target function ff. In particular, the learner predicts μt∈[−1,+1]\mu_t \in [-1,+1], and incurs a loss ℓt=(f(xt)−μt)2\ell_t = (f(x_t) - \mu_t)^2 related to the Brier score. We will care about average loss 1T∑ℓt\frac{1}{T} \sum \ell_t.

For the algorithm and for the analysis, the learner is also provided access to a (weak) class H\mathcal{H}, which consists of functions h:X→[−1,+1]h : \mathcal{X} \to [-1,+1].

There are two types of guarantees that existing works have shown. One style of guarantee ensures that the online learner is competitive against the best model in H\mathcal{H} (or, the best model in the convex hull of H\mathcal{H}, etc.). Of course, this doesn’t say too much if there is not already an average model that performs well on the prediction problem at hand.

A second style of guarantee is a “conditional” one: assuming that the class H\mathcal{H} is in some sense well-suited to learning ff, then the average loss can be driven to zero. The sense of well-suitedness is that H\mathcal{H} is “weakly smooth boostable” with respect to ff and the data sequence. Intuitively, this means that if we restrict ourselves to predicting on say any constant fraction of the data sequence, there is a model h∈Hh \in \mathcal{H} that performs slightly better than random guessing. Under this condition, there is a way to aggregate these weak models in H\mathcal{H} into a strong model that achieves arbitrarily little loss.

Thus, the first guarantee is concerned with relative loss, while the second is concerned with absolute loss (although it holds conditionally). This work shows that it is possible to achieve both guarantees at the same time. They also point out that these two guarantees do not imply each other: smooth boostability does not imply that a model in the convex hull does well, and good comparative performance to H\mathcal{H} does not guarantee good absolute performance.

Critical strengths

The problem is fundamental and the result is quite interesting. I liked the overall message of the paper a lot.

Critical weaknesses

The main issue for me is the clarity of the writing. It took quite some effort to understand what the goal of the paper was. Unfortunately, I still do not understand the algorithm or the analysis, although I tried for a while to parse it. I think major copy editing is needed.

Some suggestions:

  1. Consider avoid using both the 0/1- and +1/-1-binary classification notation. It was not easy to keep track of double the notation.
  2. The introduction is not very gentle. The paragraph (ln 052) starting at the bottom of the first page "Online weak-to-strong boosting..." was rather confusing. Especially the last two sentences of that paragraph.
  3. Can you (re)-introduce the formal objects in your analysis in a more centralized way? The definitions are spread out and hard to find.
  4. First Informal Theorem: perhaps say that ff just comes from the convex hull of H\mathcal{H}? I know that this doesn't capture the full generality of Theorem 3.1, but the index over jj was confusing. Is H\mathcal{H} necessarily a finite model class?
  5. Informal Proposition: this was also very interesting, and possibly worth expanding more. It may be nice for a reader to get a simple example, especially when smooth boosting does not imply the existence of a good weighted model.
  6. Can you provide a higher-level description of your algorithm? I don't understand what the scalar learners are. Also, is h^t\hat{h}_t a scalar in line 3 of the algorithm? Why are mentioning the computational complexity of finding a root of FtF_t?
  7. Is it possible to say something about why standard approaches to getting either guarantees do not get both? Are there simple examples that illustrate, and help explain/motivate your Defensive Boosting algorithm?
  8. I was intrigued by the paragraph at the bottom of page 4 ("The algorithm has one problem-dependent online primitive..."). I don't understand it, except that it is saying that the guarantee in Theorem 2.3 has the bound ST\sqrt{S_T} instead of T\sqrt{T}.
Questions for authors

If it is possible to succinctly do so, can you think about how to improve the exposition around the algorithm and analysis? The result seems like a really nice contribution. I'm curious (a) why existing algorithms fail to achieve both guarantees (or, why wouldn't an algorithm "naturally" achieve both), and (b) can you motivate how you discovered your algorithm/provide any sort of intuition for your analysis? Also, minor question: do you need the probabilistic forecasting setting, or does the result also work for regression?

I think it is worthwhile to give the result a more careful treatment. For that reason, I'll recommend a weak reject. If the authors can significantly clean up the write up, I would really like to see this paper published at some point.

3 comments

Thank you for your expositional suggestions; we've rewritten the introduction, and your proposed distinction between an unconditional relative guarantee and a conditional absolute one is now our starting point.

1-4. Notation, definitions, and the first two guarantees. We now start with probabilities and state the comparator result first for the convex hull: on any sequence, DB competes with the best fixed weighted average of weak probability forecasts. The class may be infinite. The formal theorem also allows signed coefficients and gives bounds scaling with their norm. The weak-to-strong guarantee asks a different question: if we emphasize any sufficiently large part of the stream by reweighting the rounds, can some weak rule still beat random guessing? We define the weights and edge before stating how this condition bounds error. We kept signed notation because it simplifies correlations. Section 2 introduces the centered variables together: the observed label is YtY_t, the probability is ptp_t, and their centered versions are σt=2Yt−1\sigma_t=2Y_t-1 and μt=2pt−1\mu_t=2p_t-1. There is only one prediction; its rescaled residual is rt=2(Yt−pt)r_t=2(Y_t-p_t).

5 and 7. Why doesn't one guarantee imply the other? We now give an example of this in the intro. Briefly: imagine that three weak learners give three binary votes, with all eight patterns equally frequent, and that the true label is equal to their majority vote. On every round at least two votes are correct; consequently under every reweighting some vote is right at least two-thirds of the time, giving nontrivial edge. Thus weak-to-strong learning guarantees that error must be driven to 00. Yet the best unrestricted linear combination of votes has Brier loss 1/161/16: a span-regret bound alone does not imply vanishing loss. Conversely, imagine two weak learners that agree on the correct label on all but a fraction δ\delta of rounds, where they disagree and each is right half the time. Their average forecast has Brier loss only δ/4\delta/4, but neither rule has an edge on the reweighting that puts all weight on the disagreement rounds. Section 1 now gives both examples.

6. How we arrived at the algorithm, and what the scalars do. There is a simple algorithm for obtaining multiaccuracy alone. Simply take the weak learner's prediction on the current example, and then use its sign as a binary-valued forecast. The prediction's correlation with the residual is never positive: the residual is zero when the forecast is correct and has the opposite sign of the prediction when wrong. The learner's regret bound then prevents any weak rule from accumulating much residual correlation. For binary labels the residual is the signed label times the mistake probability, up to a factor of two. So if the forecaster often errs, its own mistake weights give a large reweighting on which no rule has appreciable edge. This is the weak-to-strong guarantee in contrapositive form. But these forecasts are unsuitable for noisy labels. At an extreme, consider independent random binary labels: every binary forecast has expected Brier loss 1/21/2, while the correct prediction of 1/21/2 has loss only 1/41/4. Thus we need more than multiaccuracy to get the span guarantee. Expanding squared loss tells us what is missing: control of the forecast's correlation with its own residual, which is exactly what we add. Combining both guarantees together is what the scalar learners do.

The first scalar learner chooses a coefficient in [−1,1][-1,1] to test self-correlation in either direction. The second chooses how much weight to give this test versus the weak learner's test; its regret to putting all the weight on either one prevents a large correlation from going unnoticed. The combined test is an affine function of the proposed forecast. We can set it to zero before seeing the label, or choose a safe endpoint if there is no zero. Section 2 now derives Algorithm 1 in this order, and Table 1 tests the need for self-orthogonality directly: the multiaccuracy-only benchmark scores .5004.5004 on fair coins and full DB scores .2502.2502.

8. Why second order? Ordinary O(T)O(\sqrt T) regret suffices for both qualitative guarantees. Second-order regret reduces the number of rounds sufficient for randomized error ε\varepsilon from O(1/ε2)O(1/\varepsilon^2) to O~(1/ε)\widetilde O(1/\varepsilon). It also gives O(1/T)O(1/T) Brier loss for a fixed perfect span comparator.

Regression. The algorithm can be run on bounded regression tasks without modification, and its span guarantee still holds. The binary weak-to-strong proof uses an extra identity, (2Yt−1)∣Yt−pt∣=Yt−pt(2Y_t-1)|Y_t-p_t|=Y_t-p_t, which need not hold for real-valued labels. Appendix G states the bounded-regression result with this distinction and compares predictors on three ordered regression datasets.

Thank you to the authors for the thoughtful response. I've read all the other reviews and responses as well. My main concern was with the exposition of the material. I really hope the authors will do as they say and improve their presentation, since I think the contents of this paper is worth making more accessible. I'll adjust my score from a 2 weak reject to a 4 accept (I chose 4 over 3 to give a less ambiguous signal to the AC).

AuthorsOpenReview ↗

New exposition in the revision

Thanks --- we really appreciate it. You can see our new intro/exposition in the revision we've submitted. We hope it is much improved. If there are parts of it that are still confusing we welcome more feedback --- our goal is to make the paper easy for others to read/enjoy.

Reviewer_AfGtOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The authors proposes a new boosting algorithm for online probabilistic forecasting. They claim the method achieves two theoretical guarantees that previously hold in isolation (the one of online gradient boosting and weak-to-strong boosting). The algorithm is presented as highly efficient.

Critical strengths

If true, the authors unify two strong boosting guarantees into one, efficient online algorithm. That is, they claim unifying the unconditional span regret guarantee (typical of online gradient boosting) with the conditional weak-to-strong guarantee (typical of AdaBoost). Moreover, when one of then fail---the weak-learning condition---the algorithm explicit this failure by producing a hard-core witness which might be of independent interest. The proposed method is also interestingly tested.

Critical weaknesses

To have an informal introduction is really nice and is indeed quite clear up until Section 1.2 which is really difficult to parse. There, dense technical jargon are used without definition / before formal definition (e.g., "In the batch setting, weak-to-strong boosting can be viewed as a zero-sum game a learner player, who plays distributions over the weak class H, and a data player, who plays reweightings of the dataset"; "multiaccuracy auditors", "self-orthogonality", "variational-inequality framework"). Moreover, it seems like Section 1.2 and 6 have substential overlap.

Consequently, it would significantly improve readability to transfer element of the positioning to section 6 and transfer technnical elements to a proper in-depth technical discussion in Section 3 and 4 so that we can effectively assess soundness of the arguments and understand the novelty of the analysis.

Questions for authors
  • Classic online boosting (e.g., Chen et al. and Beygelzimer et al) requires only an oracle with a small edge γ\gamma over random guessing, whereas Algorithm 1 requires a second-order no-regret online linear oracle over H\mathcal{H} (Equation 1). For discrete base classes, guaranteeing sublinear regret against H\mathcal{H} typically requires tracking weights over the entire hypothesis class. In such settings, doesn't replacing an ensemble of NN simple weak learners with a single no-regret oracle simply push the ensemble complexity inside the oracle itself?
  • Can the proposed defensive forecasting framework, particularly the one-dimensional affine root-finding rule, be generalized to accommodate other proper scoring rules beyond the Brier score? Would this impact the efficiency of the proposed algorithm?
  • A lot of experimental details are deferred to Appendix D. For instance, the authors state that "OGB was run with stage step η=(log⁡N)/N\eta = (\log N) / N, as suggested by their theoretical discussion". Given the noted sensitivity in Figures 8 of OGB to the learning rate, how confident are you that the fixed-parameter evaluation protocol does not inflate the Defensive Booster's relative performance?

I would be willing to increase my score depending on the authors’ responses, their willingness to improve the accessibility of the manuscript, and upon validation of the soundness of the theorems.

2 comments

Thank you for identifying where the introduction was hard to follow and for asking whether our results extend beyond Brier loss. We rewrote the introduction and added Appendix H, which extends both guarantees to differentiable convex binary proper losses.

W1. Exposition and the proof idea. We've rewritten the introduction so that it is no longer focused on technical explanation to a boosting expert (the old discussion of minimax games and dual certificates), and is hopefully a clearer exposition to a broader set of readers. Section 1 now states the two guarantees and illustrates their difference through a concrete example. Section 2 introduces the quantities the algorithm controls before introducing the technique for controlling them. Briefly, a rule that systematically predicts the learner's residuals can exploit errors in the forecasts. Preventing this gives multiaccuracy which is what suffices for a hard-core witness. A squared-loss comparison requires not just multiaccuracy but controlling the correlation with the forecast itself. Controlling this is the role of the scalar learners. Algorithm 1 now spells out each update and is preceded by a worked example. Section 3 then derives each guarantee from the corresponding correlations; the comparisons to other frameworks are in Section 6.

Q1. Does one oracle hide the cost of an ensemble? One oracle need not be cheap. Our finite-class implementation maintains a weight for each of the mm rules. For a linear class we maintain one parameter vector; for a ball in a reproducing kernel Hilbert space (RKHS), we can use kernel evaluations without enumerating functions. The cleanest comparison is with Online Gradient Boosting (Beygelzimer et al., 2015): given the same online linear-loss learner, DB runs it once per round, while OGB runs a copy at each stage. Both implementations use the same second-order primitive in our experiments. As you point out, classical classification boosters can use an edge oracle; the one-versus-many comparison holds the underlying learner fixed. Ordinary O(T)O(\sqrt T) regret already gives worst-case average span regret O(1/T)O(1/\sqrt T) for a fixed norm bound and suffices for weak-to-strong boosting. What a second-order regret bound gives us is it reduces the sufficient rounds for randomized error ε\varepsilon from O(1/ε2)O(1/\varepsilon^2) to O~(1/ε)\widetilde O(1/\varepsilon) and sharpens span regret when a comparator has small loss.

Q2. Other proper losses and efficiency. Yes: the root stays affine. Our new Proposition H.1 treats any fixed convex differentiable binary proper loss with ∂pℓ(p,y)=a(p)(p−y)\partial_p\ell(p,y)=a(p)(p-y) and 0<m≤a(p)≤M0<m\le a(p)\le M. Multiply each update's residual by a(pt)/Ma(p_t)/M. This positive factor does not change the sign of the aggregate gain, so the same explicit root works; no extra weak learner or numerical search is needed. The weighted residual is proportional to the negative loss gradient, giving span regret against scores that yield probabilities. The new mistake weights are a(pt)∣Yt−pt∣/Ma(p_t)|Y_t-p_t|/M, so their average is at least m/Mm/M times randomized error. This preserves the weak-to-strong rate up to a loss-dependent factor. Details are in Appendix H.

Q3. Could the fixed learning rate disadvantage OGB? Yes. We now show both its default log⁡(N)/N\log(N)/N and a step selected on earlier rounds separately at N=5,20,100N=5,20,100. In an experiment in which the label is perfectly determined by a majority vote of three weak learners, default OGB-100 is essentially perfect (3.1⋅10−73.1\cdot10^{-7} Brier), while the validation-selected step scores .05876.05876. On an example with a 100-rule vote the ranking reverses: tuning improves .01769.01769 to .00009.00009. We now report both. On the changing stream, adaptive OGB-100 selects its default step on every seed at both horizons. It nearly matches adaptive DB at 30,000 rounds (.1695.1695 vs. .1682.1682), taking 14.714.7 times as long even after we optimized its implementation with vectorization.

Thanks to the authors for their answer, which largely address my concerns. The major one was the exposition of Section 1, and I appreciate the the effort of the authors to rewrite it. Consequently, I will raise my score.

Reviewer_fb7JOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes Defensive Booster, an online probabilistic forecasting algorithm that uses a single second-order no-regret learner and two scalar updates. Its main theoretical result establishes multiaccuracy and self-orthogonality guarantees, which lead to (1) a second-order Brier regret bound against the linear span of the weak hypothesis class, and (2) a weak-to-strong learning guarantee with an explicit hard-core witness when the weak-learning condition fails. The authors also extend the method to strongly adaptive learning and evaluate it on synthetic and real-world data against several online boosting baselines.

Critical strengths
  • The method requires only one weak learner, and the main guarantees follow from a concise argument. I found no issues with the main derivations.
  • Obtaining both span-based regret and weak-to-strong guarantees from the same algorithm is appealing. The online hard-core witness is particularly interesting.
  • The self-bounding analysis gives improved rates, including an O(1/T) regret rate in the realizable setting.
  • The separation results clarify why the two guarantees are incomparable, and the synthetic experiments directly illustrate these cases.
Critical weaknesses
  • All real-data experiments use linear weak learners, while the finite-class synthetic experiments use coordinate rules. Their spans are linear hypothesis spaces, so the experiments mainly compare optimization strategies rather than the benefits of combining nonlinear weak learners. Experiments with decision stumps or shallow trees would make the empirical claims more convincing.
  • The unboosted baseline is restricted to the unit ball, while the Defensive Booster effectively learns an additional scaling factor. Table 2 suggests that the optimal linear predictors require substantially larger norms, which may explain the large performance gap. I would like to see stronger single-model baselines, such as online ridge regression, VAW, or online logistic regression. Comparisons with existing online multiaccuracy methods would also be useful.
  • The reported 20–70× speedup depends heavily on using 100 learners for the baselines, although Figure 9 suggests that some achieve similar performance with far fewer learners. Moreover, the Defensive Booster does not consistently outperform baselines on classification error, even when it performs well on Brier loss. The abstract should make this distinction clearer.
  • While this paper focuses on probabilistic forecasting, it provides no calibration diagnostics. Real-data experiments are also reported without variability estimates, making small differences difficult to interpret.
Questions for authors
  1. Is the forecast equivalent to a clipped, dynamically rescaled weak prediction, i.e., $ p_t=clip(c_t\hat h_t) $? If so, could the authors clarify this interpretation and explain how often degenerate cases $ \theta_t=0 $ or $ \lambda_t=1 $ occur?
  2. Could the authors include stronger single-model baselines, such as online ridge/VAW or logistic regression, with comparable norm flexibility? It would also be helpful to compare against boosting baselines at matched accuracy rather than a fixed ensemble size of 100.
  3. Can the method be evaluated with nonlinear weak learners, such as decision stumps or depth-2 trees? More generally, how practical is the required second-order online oracle for such classes without enumeration?
1 comment

Thank you for pushing us to strengthen the single model baselines; this was a real weakness of our prior experiments and implementing stronger baselines changed how we interpret the real-data results.

W1/Q3. Nonlinear weak learners and second-order regret. We now test 122 weak rules on synthetic streams and fixed decision stumps on Electricity and Occupancy. The boosters use the same threshold rules, and the direct models receive the rules' outputs as features. On both real streams DB beats all four 100-learner boosters on Brier loss (Table 3). Our finite-class oracle explicitly enumerates the rules. Ordinary O(T)O(\sqrt T) regret suffices for both qualitative guarantees; the second-order bound gives faster weak-to-strong boosting and sharper span regret when a comparator has small loss.

W2/Q2. Stronger single-model and multiaccuracy baselines. We added all three suggested regressors (logistic, ridge, and VAW), as well as squared-loss online regression with a validation-selected norm. Your concern about comparing only to a unit-ball predictor was well founded: with threshold rules, both direct regressions beat every booster on Electricity and Occupancy, even though DB is best among the boosters. Table 1 holds the online weak learner fixed and compares DB with the standard multiaccuracy-only construction, which omits self-orthogonality. Both achieve Brier loss below .0001.0001 on (realizable) majority labels, but on iid random labels the multiaccuracy-only benchmark scores .5004.5004 versus DB's .2502.2502 (optimal is .25.25). The additional constraint lets DB guarantee a squared-loss comparison even when the true conditional probabilities are neither 00 nor 11.

W3/Q2. Matched accuracy, runtime, and classification. Figure 2 varies ensemble size (5,20,1005,20,100); Table 5 reports loss alongside time and retained state. The closest accuracy comparison on the 30,000-round changing stream is adaptive DB versus adaptive online gradient boosting (OGB-100): .1682.1682 vs. .1695.1695 Brier at 72.672.6 vs. 1064.91064.9 microseconds per round. With only 20 stages, adaptive OGB is faster than its 100-stage version but has loss .1727.1727 at 256.2256.2 microseconds per round. We vectorized OGB across stages, checked its predictions against the stage-by-stage implementation, and batched the three classification boosters as well. DB maintains a substantial speed advantage but it is now more modest, so we removed the headline speedup from the abstract. Table 2 reports thresholded and randomized error separately from Brier loss: for example, AdaBoost.OL has slightly lower randomized error than basic DB (.3381.3381 vs. .3431.3431), despite its higher Brier loss.

W4. Calibration and uncertainty. Figure 6 plots calibration curves with counts per forecast bin. To tune the comparisons fairly, on each ordered real stream we now use the first 10% for training, the next 10% for hyperparameter selection, and the last 80% for evaluation, with online updates throughout. Table 7 reports paired loss differences across ten consecutive blocks of the evaluation period.

Q1. Is the forecast a clipped, rescaled weak prediction? Yes when the affine test a+bμa+b\mu has negative slope: the centered forecast is clip⁡[−1,1](−a/b)\operatorname{clip}_{[-1,1]}(-a/b). This held on every scored round of the original linear-oracle DB runs. Clipping to an endpoint was common (50.1% of rounds on Electricity and 89.2% on Occupancy); a zero slope did not occur in those scored segments. Equation (3) also specifies what happens outside that regime: choose an interior or endpoint root if one exists, the endpoint with the sign of the test if it has no root, and zero if the test is identically zero.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.