Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration
Pahan Dewasurendra
cs.LG
Submitted: 2026-08-07
Updated: 2026-08-10
License: http://creativecommons.org/licenses/by/4.0/
The gist: Can one forecaster attain the optimal regret rate for every bounded proper loss and also adapt to every smooth proper loss? Recent work answered this up to a dimension gap.
Terminology
Abstract
Can one forecaster attain the optimal regret rate for every bounded proper loss and also adapt to every smooth proper loss? Recent work answered this up to a dimension gap. Its self-concordant perturbation gives roughly K 5/4 sqrt T worst-case regret and incurs an additional beta sqrt K K for beta-smooth losses. We close both gaps with a one-line forecaster. After observing class counts c t-1, draw the next prediction from Dir(c t-1), 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 Dir(alpha) 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 E Reg at most 4 sqrt S T T at most 4 sqrt K T and E Reg at most 5 over 2 beta(1+ T) for every beta-smooth proper loss. Here S T is the number of observed classes. Known lower bounds show that both rates are optimal in their nontrivial regimes. The proof covers nondifferentiable losses and changes of the active simplex face.
Sources
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks