- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the task of producing a sequence of forecasts (online) that are "U-calibrated": that simultaneously have low regret under all bounded, proper losses. The authors show that a randomized version of the naive counting-based "follow-the-leader" baseline achieves optimal worst-case regret bounds for both smooth and non-smooth losses. The algorithm has several additional advantages: it is very simple (practically classical), is horizon-free, has no hyperparameters, etc.
Critical strengths
The method is very simple and intuitive, and while I haven't line-by-lined the proof (this is not my subfield), it's very easy to see how this sidesteps the shortcomings of the vanilla follow-the-leader algorithm. It overcomes the shortcomings of previous (more complex) attempts at the same problem.
Critical weaknesses
Though this is clearly a nice contribution to this particular subfield, as an outsider, I'm not immediately convinced of the importance of this problem framing. Regret is characterized relative to a fixed hindsight minimizer with no context, which seems a little silly to me without the assumption that events are iid. Compare to something like online omniprediction, which uses a much richer baseline and approximates the real-world forecasting problem more closely. On top of that, catering to non-smooth losses like this at the expense of increasing variance and e.g. squared loss isn't a free win, exactly. Overall, I'm a little torn.
I think, given that this paper only claims "pseudo-U calibration," it should tone down its use of the word "simultaneous." The guarantee here really isn't; it does not exclude that there is always some fixed fraction of downstream agents that have high regret.
I suppose it would be nice for the sanity check in Appendix B to include some experiments that vary K, but this is obviously not critical.
Questions for authors
How large do you think the gap between this and true U-calibration is?
2 comments
Thanks for this. While I still believe that other formulations would be more interesting, this does solve the problem it sets out to solve. I'll raise my score (I wish it were possible to not raise it by a whole 50%, but that's a different question).
Thank you for the review! Your concerns raise three distinctions that we can explain more clearly:
(1) Comparator and non-i.i.d. outcomes
One motivation for this comparator is its decision-theoretic interpretation. Consider a downstream user with any fixed bounded decision loss L(a,y) who chooses a(p) to minimize expected loss under forecast p. The induced loss ℓ(p,y)=L(a(p),y) is proper. Its hindsight comparator is exactly the user's best fixed action: Tf(qT)=mina∑t=1TL(a,yt). Thus the guarantee compares acting on the forecasts with the best constant decision chosen after seeing the entire outcome sequence. This comparison is meaningful even when outcomes change adversarially, and no i.i.d. or stationarity assumption is used. This is the decision-theoretic foundation of Kleinberg et al. (2023). Nonsmooth proper losses arise naturally here because a user's optimal action can change abruptly as a forecast crosses a decision threshold.
(2) Cost of randomization
We agree that adding variance is not free, and we do not claim pointwise dominance over empirical FTL. Theorem 1 quantifies its cost for every bounded Euclidean β-smooth proper loss: Regℓ(T)≤RegℓFTL(T)+2β(HT−1). For squared loss, the excess expected loss is exactly one half of the sum of the Dirichlet trace variances. These variances are at most 1/t, so the total added cost is logarithmic and independent of K. The same forecasts attain the optimal worst-case logarithmic rate for smooth losses and the optimal square-root rate over all bounded proper losses. Empirical FTL alone can incur linear regret for a bounded nonsmooth proper loss.
(3) Simultaneity and true U-calibration
We agree that a supremum of expected regrets differs from the expectation of a supremum. Our main guarantee is pseudo-U-calibration, using the same expected-regret criterion as Luo et al. (2024) and Frongillo et al. We use "simultaneous" to describe one algorithm, with no knowledge of the loss or smoothness, satisfying both families of bounds. It does not assert a single realized guarantee over the unrestricted infinite loss class.
Corollary 5 additionally provides a population guarantee beyond per-agent expectation. For any fixed collection of M bounded proper losses, with probability at least 1−δ, every member satisfies Regℓ(T)≤BT+2Tlog(M/δ), where BT=2ST+2∑i:Ni>0Ni. Thus, for any fixed finite population and fixed K, all users have sublinear realized regret with high probability. In particular, the guarantee applies to the whole prescribed population on a common high-probability event, rather than only to one user selected in advance.
Again, thank you so much for the review!