acceptodds
Under review as a conference paper at ICLR 2027

Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration

Abstract

Can a single proper multiclass forecaster attain the minimax-optimal worst-case pseudo-U-calibration rate over all bounded proper losses? Can it do so while retaining the optimal logarithmic dependence on for every bounded Euclidean-smooth proper loss? Recent work gave the first simultaneous guarantee, but its bounds are roughly in the worst case and include an additional term for smooth losses. We show that both dimension losses are unnecessary. A one-line, horizon-free Dirichlet forecaster achieves the optimal rates. After observing class counts , draw the next prediction from , on the face of classes seen so far. This is a fresh Bayesian bootstrap of the outcomes. The analysis rests on an exact identity: averaging any bounded proper loss under equals a discrete derivative of its Dirichlet-averaged Bayes risk. The identity makes the be-the-perturbed-leader term telescope to a nonpositive Jensen gap. A one-count likelihood ratio then bounds stability by the inverse square root of that class's count. The resulting single, horizon-free algorithm satisfies For every bounded -smooth proper loss , Here is the number of observed classes. A class-aggregation reduction shows that the dimension-capped rate is minimax-optimal up to constants in every regime with , and known smooth-loss lower bounds match the logarithmic dependence on of the second bound. The proof covers nondifferentiable losses and changes of the active simplex face.

Primary area:
learning theory
Keywords:
online learning, probabilistic forecasting, U-calibration, proper losses, Dirichlet distribution, Bayesian bootstrap, regret minimization, learning theory

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.50 over 4 reviews, above 99% of the others.
Reviewer_3RxAOpenReview ↗
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

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)L(a,y) who chooses a(p)a(p) to minimize expected loss under forecast pp. The induced loss ℓ(p,y)=L(a(p),y)\ell(p,y)=L(a(p),y) is proper. Its hindsight comparator is exactly the user's best fixed action: Tf(qT)=min⁡a∑t=1TL(a,yt).T f(q_T)=\min_a\sum_{t=1}^T L(a,y_t). 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 β\beta-smooth proper loss: Reg⁡ℓ(T)≤Reg⁡ℓFTL(T)+β2(HT−1).\operatorname{Reg}_{\ell}(T)\leq\operatorname{Reg}^{\mathrm{FTL}}_{\ell}(T)+\frac{\beta}{2}(H_T-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/t1/t, so the total added cost is logarithmic and independent of KK. 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 MM bounded proper losses, with probability at least 1−δ1-\delta, every member satisfies Reg⁡^ℓ(T)≤BT+2Tlog⁡(M/δ),\widehat{\operatorname{Reg}}_{\ell}(T)\leq B_T+\sqrt{2T\log(M/\delta)}, where BT=2ST+2∑i:Ni>0NiB_T=2S_T+2\sum_{i:N_i>0}\sqrt{N_i}. Thus, for any fixed finite population and fixed KK, 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!

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).

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

The paper gives a single, horizon-free multiclass forecaster that achieves minimax-optimal worst-case pseudo-U-calibration while retaining logarithmic expected regret for every bounded Euclidean-smooth proper loss. The forecaster is "Dirichlet Follow-the-Leader." At each round after initialization, the algorithm draws a fresh forecast from the Dirichlet distribution whose parameters are the historical class counts, restricted to the face of previously observed classes. The central technical contribution is a count-deletion identity for the Dirichlet-averaged Bayes risk. This identity makes the be-the-perturbed-leader contribution telescope to a nonpositive Jensen gap. One-count total variation controls general bounded losses, while centering and Dirichlet covariance control smooth losses. The resulting bounds are frequency-sensitive, and the paper also supplies an all-regime minimax reduction and finite-family high-probability guarantees.

Critical strengths
  1. Natural and clean algorithm, solving a concrete and meaningful gap in the literature. It needs only class counts and Gamma sampling, with no loss-specific optimization, horizon, learning rate, or smoothness parameter. For proper multiclass forecasts, Frongillo et al. (2026) obtain approximately O~(K5/4T)\widetilde O(K^{5/4}\sqrt T) worst-case regret and O(βlog⁡T+βKlog⁡K)O(\beta\log T+\beta\sqrt K\log K) smooth-loss regret, and explicitly leave the optimal dimension dependence open. The present result improves the former to the optimal O(min⁡{K,T}T)O(\sqrt{\min\{K,T\}T}) rate and removes the additional dimension-dependent term from the latter.

  2. The central identity provides a new unifying argument. With F(α)=EDir⁡(α)f(P)F(\alpha)=\mathbb E_{\operatorname{Dir}(\alpha)}f(P), Lemma 2 states

=nF(\alpha)-(n-1)F(\alpha-e_j).$$ This converts the perturbed-leader term into an exact telescoping potential. Combining that identity with coordinate-wise count stability explains both the optimal worst-case rate and the frequency-sensitive refinement. The smooth-loss argument then uses the same distribution through its centered second moment, rather than requiring another algorithm.
Critical weaknesses
  1. Numerical results are somewhat limited. Table 1 is entirely binary. It illustrates the two growth rates, but not the dependence on KK, the active support, or class-frequency imbalance that is central to the contribution. A small multiclass experiment would improve the paper's accessibility and show how the simple implementation behaves when new classes appear.
Questions for authors
  1. Can you add a small multiclass example varying the support size or class imbalance, with FTL and geometric-count FTPL as reference algorithms?
1 comment

Thank you for the review and the suggestion! We have added multiclass comparisons in Appendix C.2-C.3, with Figure 1, Table 2, and code in the supplement. We hope these additions make the two regret regimes and the effects of support and new-class arrivals easier to see alongside the theoretical analysis.

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

This paper studies simultaneous multiclass pseudo-U-calibration over K outcomes. It shows that Dirichlet Follow-the-Leader (Dirichlet FTL)—which simply draws P_t ∼ Dir(c_(t-1)) on the active simplex face—simultaneously achieves minimax-optimal PUCal_T ≤ 4√(min {K, T}T) across all bounded proper losses ℓ ∈ [-1,1] and Reg_ℓ(T) ≤ (5/2)β(1 + log T) across all Euclidean β-smooth proper losses. This resolves the dimension gaps of Frongillo et al. (2026) (O~(K5/4T)\widetilde{O}(K^{5/4}\sqrt{T}) and O(β log T + β√K log K)) without knowing T, K, β or using an optimization oracle.

Critical strengths
  • Optimal Dimension Dependence via a Parameter-Free Rule: Removes the K^(3/4) worst-case factor and the additive β√K log K smooth-loss penalty of Frongillo et al. (2026), replacing self-concordant barrier optimization with a single closed-form draw P_t ∼ Dir(c_(t-1)).
  • Loss-Uniform Count-Deletion Identity (Lemma 2): Using Savage's representation (D_(e_j - p)f(p) = ℓ(p, e_j) - f(p)) and integration by parts on the active face to show EP∼Dir⁡(α)[ℓ(P,ej)]=nF(α)−(n−1)F(α−ej)\mathbb{E}_{P \sim \operatorname{Dir}(\alpha)}[\ell(P, e_j)] = nF(\alpha) - (n-1)F(\alpha - e_j) is a clean, non-trivial identity. It telescopes the BTL term into a nonpositive Jensen gap for any proper loss, leaving only O(1/√m) one-count TV stability for nonsmooth losses and O(1/t) centered trace variance for smooth losses.
Critical weaknesses
  • Euclidean Smoothness Excludes Barrier-Smooth / Log-Loss Settings: Because P_t is supported on the active face Δ_A (assigning zero mass to unseen classes) and the proof relies on Euclidean variance E∥Pt−qt−1∥22≤1/t\mathbb{E}\|P_t - q_{t-1}\|_2^2 \le 1/t, the O(log T) guarantee only holds for losses with bounded Euclidean smoothness β on Δ_K, excluding losses smooth relative to the log barrier (which Frongillo et al., 2026 cover).
  • Pseudo-U-Calibration vs. True U-Calibration: The Θ(√(min {K,T}T)) bound controls sup⁡ℓ∈LE[Regℓ(T)]\sup_{\ell \in \mathcal{L}} \mathbb{E}[\text{Reg}_\ell(T)] rather than E[sup⁡ℓ∈LReg^ℓ(T)]\mathbb{E}[\sup_{\ell \in \mathcal{L}} \widehat{\text{Reg}}_\ell(T)]. High-probability bounds in Corollary 5 require ε-covering numbers that scale exponentially in K for the full class of proper losses.
Questions for authors

Prior-Shifted Dirichlet for Barrier-Smooth Losses: If counts are initialized with a prior α₀ = ε1 so P_t ∼ Dir(c_(t-1) + ε1) stays in relint(Δ_K), Lemma 2 still holds on shifted counts. Can this recover O(log T) regret for losses smooth with respect to the log barrier Hessian diag(p)⁻¹, or does the boundary variance of Dir still break local norm compatibility?

1 comment

Thank you for the thoughtful review! Your positive-prior question leads to a logarithmic-regret guarantee beyond Euclidean smoothness, which we added as Proposition 7 in Appendix B.

The answer is yes for bounded proper losses that are twice continuously differentiable in the simplex interior. Let K≥2K\geq2 and h(p)=−∑ilog⁡pih(p)=-\sum_i\log p_i, whose Hessian is diag⁡(pi−2)\operatorname{diag}(p_i^{-2}). Suppose ∇2ℓ(p,ej)⪯β∇2h(p)\nabla^2\ell(p,e_j)\preceq\beta\nabla^2h(p) on tangent directions. For any fixed outcome sequence and any ε>0\varepsilon>0, fresh draws Pt∼Dir⁡(ct−1+ε1)P_t\sim\operatorname{Dir}(c_{t-1}+\varepsilon\mathbf1) achieve expected regret O((1+β)Klog⁡(T+1)+Kε)O((1+\beta)K\log(T+1)+K\varepsilon). The logarithmic bound is uniform over 0<ε≤10<\varepsilon\leq1, without an inverse-prior penalty. The proof yields logarithmic regret by comparing consecutive Dirichlet laws and applying the count-deletion identity.

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

U-calibration is the question of providing online forecasts that achieve sublinear regret against all proper scoring rules simultaneously. Kleinberg et al. first introduced this notion, showing that it is indeed possible to attain O(sqrt{T}) regret against all proper scoring rules. However, some scoring rules (like Brier score) are smooth and strongly convex, and it is possible to attain O(log T) rates against them individually. Recently, Frongillo et al. showed that there exist U-calibration algorithms that attain O(log T) rates against smooth losses while simultaneously attaining O(sqrt(T)) rates against bigger

This paper solves an open problem from Frongillo et al. in the multiclass setting (where the forecaster is predicting a distribution over K labels). Frongillo et al. establishes a worst-case bound of O(K^{5/4}sqrt(T)) regret against any bounded proper loss by using a self-concordant perturbation (while obtaining O(log T) rates against smooth proper losses). This paper solves an open question from Frongillo et al., by showing that the simple algorithm of sampling from the Dirichlet distribution initialized with the current counts obtains the minimax optimal O(sqrt(KT)) rates against any bounded proper loss.

Critical strengths

It is a very nice observation that sampling from the Dirichlet distribution gives strongly U-calibrated multiclass forecasters. In addition to tightening the existing bound of Frongillo et al., the proof in the multiclass case is greatly simplified (Dirichlet sampling really seems to be the "correct" algorithm for this problem).

Critical weaknesses

I found the paper dense and hard to read in several places. I think some of the proofs would benefit from cleaner rewriting and motivation (e.g. the count-deletion lemma, probably the key lemma in the paper, has a proof that is a little hard to follow, and also seems tricky to motivate. Similarly, I would have liked some understanding of why the Dirichlet forecaster is a natural choice of forecaster to consider in the first place.

Questions for authors

No questions.

1 comment

Thank you for the review and the helpful suggestions about presentation! We have expanded the motivation for Dirichlet sampling before Theorem 1 and added a potential based interpretation after the statement of Lemma 2. We have also rewritten the proof of Lemma 2 into three labeled steps with additional explanations of the directional derivative, density calculation, and boundary limit.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.