- 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 , a learner will receive a stream of instances and will be asked to predict its binary label with respect to the target function . In particular, the learner predicts , and incurs a loss related to the Brier score. We will care about average loss .
For the algorithm and for the analysis, the learner is also provided access to a (weak) class , which consists of functions .
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 (or, the best model in the convex hull of , 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 is in some sense well-suited to learning , then the average loss can be driven to zero. The sense of well-suitedness is that is “weakly smooth boostable” with respect to 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 that performs slightly better than random guessing. Under this condition, there is a way to aggregate these weak models in 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 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:
- Consider avoid using both the 0/1- and +1/-1-binary classification notation. It was not easy to keep track of double the notation.
- 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.
- Can you (re)-introduce the formal objects in your analysis in a more centralized way? The definitions are spread out and hard to find.
- First Informal Theorem: perhaps say that just comes from the convex hull of ? I know that this doesn't capture the full generality of Theorem 3.1, but the index over was confusing. Is necessarily a finite model class?
- 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.
- Can you provide a higher-level description of your algorithm? I don't understand what the scalar learners are. Also, is a scalar in line 3 of the algorithm? Why are mentioning the computational complexity of finding a root of ?
- 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?
- 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 instead of .
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 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).
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.
Thanks!
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 Yt, the probability is pt, and their centered versions are σt=2Yt−1 and μt=2pt−1. There is only one prediction; its rescaled residual is rt=2(Yt−pt).
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 0. Yet the best unrestricted linear combination of votes has Brier loss 1/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 δ of rounds, where they disagree and each is right half the time. Their average forecast has Brier loss only δ/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/2, while the correct prediction of 1/2 has loss only 1/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] 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 on fair coins and full DB scores .2502.
8. Why second order? Ordinary O(T) regret suffices for both qualitative guarantees. Second-order regret reduces the number of rounds sufficient for randomized error ε from O(1/ε2) to O(1/ε). It also gives 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, 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.