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

# Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration
Source: [https://arxiv.org/html/2608.06656](https://arxiv.org/html/2608.06656)
###### 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 roughlyK5/4​TK^\{5/4\}\\sqrt\{T\}worst\-case regret and incurs an additionalβ​K​log⁡K\\beta\\sqrt\{K\}\\log Kforβ\\beta\-smooth losses\. We close both gaps with a one\-line forecaster\. After observing class countsct−1c\_\{t\-1\}, draw the next prediction fromDir⁡\(ct−1\)\\operatorname\{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 underDir⁡\(α\)\\operatorname\{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

supℓ𝔼​Regℓ\\displaystyle\\sup\_\{\\ell\}\\mathbb\{E\}\\operatorname\{Reg\}\_\{\\ell\}≤4​ST​T≤4​K​T,\\displaystyle\\leq 4\\sqrt\{S\_\{T\}T\}\\leq 4\\sqrt\{KT\},𝔼​Regℓ\\displaystyle\\mathbb\{E\}\\operatorname\{Reg\}\_\{\\ell\}≤52​β​\(1\+log⁡T\)for everyβ\-smooth properℓ\.\\displaystyle\\leq\\tfrac\{5\}\{2\}\\beta\(1\+\\log T\)\\quad\\text\{for every $\\beta$\-smooth proper $\\ell$\.\}HereSTS\_\{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\.

## 1Introduction

A probabilistic forecast is often consumed by an agent whose downstream utility is unknown to the forecaster\. Proper losses capture this uncertainty: each proper loss corresponds to a way of valuing probabilistic predictions, and truthful prediction minimizes expected loss\. U\-calibration asks for one online sequence of forecasts with low regret under every bounded proper loss\(Kleinberget al\.,[2023](https://arxiv.org/html/2608.06656#bib.bib1)\)\. This requirement is substantially stronger than optimizing a fixed score such as Brier loss\.

ForKKoutcomes,Luoet al\.\([2024](https://arxiv.org/html/2608.06656#bib.bib2)\)established the optimalΘ​\(K​T\)\\Theta\(\\sqrt\{KT\}\)worst\-case pseudo\-U\-calibration rate\. Their optimal forecaster does not adapt to easier scores\. In particular, it can incurΩ​\(T\)\\Omega\(\\sqrt\{T\}\)regret on squared loss even though Follow\-the\-Leader \(FTL\) has logarithmic regret\. Very recent work showed that this conflict is not fundamental\(Frongilloet al\.,[2026](https://arxiv.org/html/2608.06656#bib.bib3)\)\. A carefully shaped self\-concordant perturbation simultaneously gives logarithmic regret on smooth scores and sublinear regret on all proper scores\. Its bounds leave two linked gaps\. The general rate isO~​\(K5/4​T\)\\widetilde\{O\}\(K^\{5/4\}\\sqrt\{T\}\)rather thanO​\(K​T\)O\(\\sqrt\{KT\}\), and the smooth rate contains an additiveO​\(β​K​log⁡K\)O\(\\beta\\sqrt\{K\}\\log K\)term\. The paper explicitly asks whether simultaneous optimality is possible\.

We answer this question affirmatively\. Letct=∑s≤tysc\_\{t\}=\\sum\_\{s\\leq t\}y\_\{s\}be the vector of outcome counts\. At timet≥2t\\geq 2, independently sample

Pt∼Dir⁡\(ct−1\)\.P\_\{t\}\\sim\\operatorname\{Dir\}\(c\_\{t\-1\}\)\.Zero count coordinates are fixed at zero, so the distribution lives on the face spanned by classes observed so far\. Equivalently, assign independent Gamma weights to the observed outcomes and normalize\. Thus the algorithm is exactly a fresh Bayesian bootstrap\(Rubin,[1981](https://arxiv.org/html/2608.06656#bib.bib4)\)\. It requires no horizon, smoothness parameter, learning rate, or optimization oracle\. The Bayesian\-bootstrap draw itself is classical\. Our claims concern its new adversarial proper\-loss analysis and simultaneous regret guarantees\.

The main proof is not a generic posterior\-sampling argument\. Ifffis the concave Bayes risk of a proper loss andF​\(α\)=𝔼P∼Dir⁡\(α\)​f​\(P\)F\(\\alpha\)=\\mathbb\{E\}\_\{P\\sim\\operatorname\{Dir\}\(\\alpha\)\}f\(P\), we prove

𝔼P∼Dir⁡\(α\)​ℓ​\(P,ej\)=n​F​\(α\)−\(n−1\)​F​\(α−ej\),n=∑iαi\.\\mathbb\{E\}\_\{P\\sim\\operatorname\{Dir\}\(\\alpha\)\}\\ell\(P,e\_\{j\}\)=nF\(\\alpha\)\-\(n\-1\)F\(\\alpha\-e\_\{j\}\),\\qquad n=\\sum\_\{i\}\\alpha\_\{i\}\.\(1\)This identity applies to arbitrary bounded proper losses, including polyhedral and V\-shaped losses\. It turns the perturbed\-leader contribution intoT​\(F​\(cT\)−f​\(cT/T\)\)≤0T\(F\(c\_\{T\}\)\-f\(c\_\{T\}/T\)\)\\leq 0\. The remaining stability term compares two Dirichlet laws whose parameters differ by one count\. Their likelihood ratio is linear in one coordinate, which gives stabilityO​\(1/m\)O\(1/\\sqrt\{m\}\)when that coordinate has appearedmmtimes\. Summing separately within each class producesO​\(∑iNi\)=O​\(K​T\)O\(\\sum\_\{i\}\\sqrt\{N\_\{i\}\}\)=O\(\\sqrt\{KT\}\)\.

The same distribution is automatically adapted to smooth losses\. Its mean is empirical FTL and its squared radius is at most1/t1/t\. Centering removes the first\-order smoothness term, leavingO​\(β/t\)O\(\\beta/t\)\. A short semiconcavity argument also gives an explicit2​β​HT2\\beta H\_\{T\}FTL bound under the one\-sided smoothness definition used in prior work\.

Our contributions are:

- •We give one efficient, horizon\-free forecaster with4​ST​T≤4​K​T4\\sqrt\{S\_\{T\}T\}\\leq 4\\sqrt\{KT\}expected regret for every bounded proper loss and simultaneousO​\(β​log⁡T\)O\(\\beta\\log T\)regret for every boundedβ\\beta\-smooth proper loss\.
- •We prove the count\-deletion identity in \([1](https://arxiv.org/html/2608.06656#S1.Ex4)\), including nondifferentiable Bayes risks, zero count coordinates, and the singular caseαj=1\\alpha\_\{j\}=1\.
- •We isolate two exact geometric facts behind simultaneous adaptation: one\-count Dirichlet total variation controls nonsmooth loss, while centered covariance controls smooth loss\.

We emphasize the quantifier\. Our result controlssupℓ𝔼​Regℓ\\sup\_\{\\ell\}\\mathbb\{E\}\\operatorname\{Reg\}\_\{\\ell\}, called pseudo\-U\-calibration\. It does not claim the stronger𝔼​supℓRegℓ\\mathbb\{E\}\\sup\_\{\\ell\}\\operatorname\{Reg\}\_\{\\ell\}for the infinite class of all proper losses\. This is the same expected\-regret criterion studied byFrongilloet al\.\([2026](https://arxiv.org/html/2608.06656#bib.bib3)\)\.

## 2Setting and algorithm

Lete1,…,eKe\_\{1\},\\ldots,e\_\{K\}denote the vertices ofΔK\\Delta\_\{K\}\. At roundtt, a forecaster chooses a possibly randomPt∈ΔKP\_\{t\}\\in\\Delta\_\{K\}, then observes an outcomeyt∈\{e1,…,eK\}y\_\{t\}\\in\\\{e\_\{1\},\\ldots,e\_\{K\}\\\}\. We first state results for an oblivious outcome sequence\. Appendix[A](https://arxiv.org/html/2608.06656#A1)gives the standard extension to a nonanticipating adaptive adversary when fresh randomness is used each round\.

A lossℓ:ΔK×\{ei\}i=1K→\[−1,1\]\\ell:\\Delta\_\{K\}\\times\\\{e\_\{i\}\\\}\_\{i=1\}^\{K\}\\to\[\-1,1\]is*proper*if

p∈arg⁡minq∈ΔK⁡𝔼Y∼p​ℓ​\(q,Y\)for every​p∈ΔK\.p\\in\\arg\\min\_\{q\\in\\Delta\_\{K\}\}\\mathbb\{E\}\_\{Y\\sim p\}\\ell\(q,Y\)\\quad\\text\{for every \}p\\in\\Delta\_\{K\}\.For an outcome sequence, propriety makes its empirical distributionqT=T−1​∑tytq\_\{T\}=T^\{\-1\}\\sum\_\{t\}y\_\{t\}a hindsight minimizer\. Define

Regℓ⁡\(T\)=𝔼​∑t=1Tℓ​\(Pt,yt\)−T​f​\(qT\),f​\(p\)=∑ipi​ℓ​\(p,ei\)\.\\operatorname\{Reg\}\_\{\\ell\}\(T\)=\\mathbb\{E\}\\sum\_\{t=1\}^\{T\}\\ell\(P\_\{t\},y\_\{t\}\)\-Tf\(q\_\{T\}\),\\qquad f\(p\)=\\sum\_\{i\}p\_\{i\}\\ell\(p,e\_\{i\}\)\.The expectation is over the forecaster\. Letℒ\\mathcal\{L\}be all proper losses with range in\[−1,1\]\[\-1,1\]and letPUCalT=supℓ∈ℒRegℓ⁡\(T\)\\operatorname\{PUCal\}\_\{T\}=\\sup\_\{\\ell\\in\\mathcal\{L\}\}\\operatorname\{Reg\}\_\{\\ell\}\(T\)\.

FollowingFrongilloet al\.\([2026](https://arxiv.org/html/2608.06656#bib.bib3)\), a differentiable loss isβ\\beta\-smooth when

ℓ​\(q,y\)−ℓ​\(p,y\)≤⟨∇pℓ​\(p,y\),q−p⟩\+β2​‖q−p‖22\\ell\(q,y\)\-\\ell\(p,y\)\\leq\\langle\\nabla\_\{p\}\\ell\(p,y\),q\-p\\rangle\+\\frac\{\\beta\}\{2\}\\\|q\-p\\\|\_\{2\}^\{2\}\(2\)for everyp,q∈ΔKp,q\\in\\Delta\_\{K\}and outcomeyy\. Gradients and differentiability on the closed simplex are understood relative to its affine hull, including one\-sided differentiability on boundary faces\.

For a nonnegative parameter vectorα\\alpha, writeA=\{i:αi\>0\}A=\\\{i:\\alpha\_\{i\}\>0\\\}\. We defineDir⁡\(α\)\\operatorname\{Dir\}\(\\alpha\)on the faceΔA\\Delta\_\{A\}by drawing independentGi∼Gamma​\(αi,1\)G\_\{i\}\\sim\\mathrm\{Gamma\}\(\\alpha\_\{i\},1\)fori∈Ai\\in A, settingPi=Gi/∑k∈AGkP\_\{i\}=G\_\{i\}/\\sum\_\{k\\in A\}G\_\{k\}, and settingPi=0P\_\{i\}=0outsideAA\.

Algorithm 1Dirichlet Follow\-the\-Leader1:Initialize

c0=0c\_\{0\}=0and predict

P1=\(1/K,…,1/K\)P\_\{1\}=\(1/K,\\ldots,1/K\)\.

2:for

t=1,2,…,Tt=1,2,\\ldots,Tdo

3:if

t≥2t\\geq 2then

4:Draw

Pt∼Dir⁡\(ct−1\)P\_\{t\}\\sim\\operatorname\{Dir\}\(c\_\{t\-1\}\)independently of past draws\.

5:endif

6:Observe

yty\_\{t\}and set

ct=ct−1\+ytc\_\{t\}=c\_\{t\-1\}\+y\_\{t\}\.

7:endfor

###### Theorem 1\(Simultaneously optimal regret\)\.

For everyK,T≥1K,T\\geq 1, letSTS\_\{T\}be the number of distinct outcomes observed\. Algorithm[1](https://arxiv.org/html/2608.06656#alg1)satisfies

PUCalT≤4​ST​T≤4​min⁡\{K,T\}​T\.\\operatorname\{PUCal\}\_\{T\}\\leq 4\\sqrt\{S\_\{T\}T\}\\leq 4\\sqrt\{\\min\\\{K,T\\\}T\}\.Simultaneously, for everyβ\\beta\-smoothℓ∈ℒ\\ell\\in\\mathcal\{L\},

Regℓ⁡\(T\)≤52​β​HT≤52​β​\(1\+log⁡T\),\\operatorname\{Reg\}\_\{\\ell\}\(T\)\\leq\\frac\{5\}\{2\}\\beta H\_\{T\}\\leq\\frac\{5\}\{2\}\\beta\(1\+\\log T\),whereHT=∑t=1T1/tH\_\{T\}=\\sum\_\{t=1\}^\{T\}1/t\.

ForK≤TK\\leq T, theK​T\\sqrt\{KT\}worst\-case rate is matched by the multiclass V\-shaped lower bound ofLuoet al\.\([2024](https://arxiv.org/html/2608.06656#bib.bib2)\)\. Squared loss gives anΩ​\(log⁡T\)\\Omega\(\\log T\)lower bound for the smooth subclass\. Hence both worst\-case rates in Theorem[1](https://arxiv.org/html/2608.06656#Thmtheorem1)are optimal up to universal constants in their nontrivial regimes\. The support\-sensitive refinement is an additional instance\-dependent guarantee\.

## 3A Dirichlet identity for every proper loss

Writeℓp=\(ℓ​\(p,e1\),…,ℓ​\(p,eK\)\)\\ell\_\{p\}=\(\\ell\(p,e\_\{1\}\),\\ldots,\\ell\(p,e\_\{K\}\)\)\. Propriety gives

f​\(q\)≤⟨q,ℓp⟩,f​\(p\)=⟨p,ℓp⟩\.f\(q\)\\leq\\langle q,\\ell\_\{p\}\\rangle,\\qquad f\(p\)=\\langle p,\\ell\_\{p\}\\rangle\.\(3\)Thusffis concave andℓp\\ell\_\{p\}is a supergradient representation\. Since‖ℓp‖∞≤1\\\|\\ell\_\{p\}\\\|\_\{\\infty\}\\leq 1, applying \([3](https://arxiv.org/html/2608.06656#S3.Ex10)\) in both directions also gives

\|f​\(p\)−f​\(q\)\|≤‖p−q‖1\.\|f\(p\)\-f\(q\)\|\\leq\\\|p\-q\\\|\_\{1\}\.\(4\)
###### Lemma 2\(Count deletion\)\.

Letα≥0\\alpha\\geq 0, letn=∑iαin=\\sum\_\{i\}\\alpha\_\{i\}, and supposeαj≥1\\alpha\_\{j\}\\geq 1\. ForF​\(α\)=𝔼P∼Dir⁡\(α\)​f​\(P\)F\(\\alpha\)=\\mathbb\{E\}\_\{P\\sim\\operatorname\{Dir\}\(\\alpha\)\}f\(P\),

𝔼P∼Dir⁡\(α\)​ℓ​\(P,ej\)=n​F​\(α\)−\(n−1\)​F​\(α−ej\)\.\\mathbb\{E\}\_\{P\\sim\\operatorname\{Dir\}\(\\alpha\)\}\\ell\(P,e\_\{j\}\)=nF\(\\alpha\)\-\(n\-1\)F\(\\alpha\-e\_\{j\}\)\.The statement uses the active\-face convention above\. Whenn=1n=1, the second term is zero\.

###### Proof\.

First supposeαj\>1\\alpha\_\{j\}\>1and work relative to the active face\. A concave function is differentiable almost everywhere on the relative interior\. At each suchpp, \([3](https://arxiv.org/html/2608.06656#S3.Ex10)\) makes the tangent component ofℓp\\ell\_\{p\}the unique supergradient offf\. Therefore

ℓ​\(p,ej\)=f​\(p\)\+Dej−p​f​\(p\)\\ell\(p,e\_\{j\}\)=f\(p\)\+D\_\{e\_\{j\}\-p\}f\(p\)\(5\)almost everywhere\.

Letρα\\rho\_\{\\alpha\}be the Dirichlet density and setv​\(p\)=ej−pv\(p\)=e\_\{j\}\-p\. A direct calculation on the active face gives

div⁡v\+Dv​log⁡ρα=αj−1pj−\(n−1\)\.\\operatorname\{div\}v\+D\_\{v\}\\log\\rho\_\{\\alpha\}=\\frac\{\\alpha\_\{j\}\-1\}\{p\_\{j\}\}\-\(n\-1\)\.The boundary flux vanishes\. At a facepi=0p\_\{i\}=0withi≠ji\\neq j, the normal componentvi=−piv\_\{i\}=\-p\_\{i\}cancels the possible density singularity\. Atpj=0p\_\{j\}=0, the assumptionαj\>1\\alpha\_\{j\}\>1makes the flux vanish\. Integration by parts and \([5](https://arxiv.org/html/2608.06656#S3.Ex13)\) now yield

𝔼α​Dv​f​\(P\)\\displaystyle\\mathbb\{E\}\_\{\\alpha\}D\_\{v\}f\(P\)=\(n−1\)​F​\(α\)−\(αj−1\)​𝔼α​f​\(P\)Pj,\\displaystyle=\(n\-1\)F\(\\alpha\)\-\(\\alpha\_\{j\}\-1\)\\mathbb\{E\}\_\{\\alpha\}\\frac\{f\(P\)\}\{P\_\{j\}\},\(αj−1\)​𝔼α​f​\(P\)Pj\\displaystyle\(\\alpha\_\{j\}\-1\)\\mathbb\{E\}\_\{\\alpha\}\\frac\{f\(P\)\}\{P\_\{j\}\}=\(n−1\)​F​\(α−ej\),\\displaystyle=\(n\-1\)F\(\\alpha\-e\_\{j\}\),where the second equality is the ratio of Dirichlet normalizers\. Combining the two displays proves the claim forαj\>1\\alpha\_\{j\}\>1\.

Ifαj=1\\alpha\_\{j\}=1, apply the proved identity toα\+ε​ej\\alpha\+\\varepsilon e\_\{j\}and letε↓0\\varepsilon\\downarrow 0\. The first Dirichlet law converges in total variation, which is enough for the possibly discontinuous bounded functionℓ​\(⋅,ej\)\\ell\(\\cdot,e\_\{j\}\)\. After deleting one count, the law with parameterε\\varepsilonin coordinatejjconverges weakly to the lower\-dimensional face\. Equation \([4](https://arxiv.org/html/2608.06656#S3.Ex11)\) makesffcontinuous, so its expectations converge\. The casen=1n=1is immediate fromℓ​\(ej,ej\)=f​\(ej\)\\ell\(e\_\{j\},e\_\{j\}\)=f\(e\_\{j\}\)\. ∎

The distinction between total variation and weak convergence in the last paragraph matters\. A bounded proper loss can jump across a decision boundary, while its Bayes risk remains continuous\.

## 4Worst\-case analysis

For analysis, after observing roundtt, draw a ghost predictionQt\+1∼Dir⁡\(ct\)Q\_\{t\+1\}\\sim\\operatorname\{Dir\}\(c\_\{t\}\)\. For any fixed loss,

Regℓ⁡\(T\)\\displaystyle\\operatorname\{Reg\}\_\{\\ell\}\(T\)=∑t=1T𝔼​\[ℓ​\(Pt,yt\)−ℓ​\(Qt\+1,yt\)\]\\displaystyle=\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\\ell\(P\_\{t\},y\_\{t\}\)\-\\ell\(Q\_\{t\+1\},y\_\{t\}\)\]\+∑t=1T𝔼​ℓ​\(Qt\+1,yt\)−T​f​\(qT\)\.\\displaystyle\\quad\+\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\\ell\(Q\_\{t\+1\},y\_\{t\}\)\-Tf\(q\_\{T\}\)\.\(6\)Ifyt=ejy\_\{t\}=e\_\{j\}, Lemma[2](https://arxiv.org/html/2608.06656#Thmtheorem2)gives

𝔼​ℓ​\(Qt\+1,yt\)=t​F​\(ct\)−\(t−1\)​F​\(ct−1\)\.\\mathbb\{E\}\\ell\(Q\_\{t\+1\},y\_\{t\}\)=tF\(c\_\{t\}\)\-\(t\-1\)F\(c\_\{t\-1\}\)\.The second line of \([6](https://arxiv.org/html/2608.06656#S4.Ex18)\) therefore telescopes to

T​\{F​\(cT\)−f​\(qT\)\}≤0,T\\\{F\(c\_\{T\}\)\-f\(q\_\{T\}\)\\\}\\leq 0,because𝔼​QT\+1=qT\\mathbb\{E\}Q\_\{T\+1\}=q\_\{T\}andffis concave\.

It remains to control stability\. The next elementary estimate is where the coordinate adaptivity enters\.

###### Lemma 3\(One\-count stability\)\.

Letc≥0c\\geq 0,n=∑icin=\\sum\_\{i\}c\_\{i\}, andcj=m\>0c\_\{j\}=m\>0\. Then

TV⁡\(Dir⁡\(c\),Dir⁡\(c\+ej\)\)≤12​n−mm​\(n\+1\)≤12​m\.\\operatorname\{TV\}\(\\operatorname\{Dir\}\(c\),\\operatorname\{Dir\}\(c\+e\_\{j\}\)\)\\leq\\frac\{1\}\{2\}\\sqrt\{\\frac\{n\-m\}\{m\(n\+1\)\}\}\\leq\\frac\{1\}\{2\\sqrt\{m\}\}\.

###### Proof\.

On their common active face, the likelihood ratio is

d​Dir⁡\(c\+ej\)d​Dir⁡\(c\)​\(p\)=n​pjm\.\\frac\{d\\operatorname\{Dir\}\(c\+e\_\{j\}\)\}\{d\\operatorname\{Dir\}\(c\)\}\(p\)=\\frac\{np\_\{j\}\}\{m\}\.Consequently,

TV⁡\(Dir⁡\(c\),Dir⁡\(c\+ej\)\)=12​𝔼P∼Dir⁡\(c\)​\|n​Pjm−1\|\.\\operatorname\{TV\}\(\\operatorname\{Dir\}\(c\),\\operatorname\{Dir\}\(c\+e\_\{j\}\)\)=\\frac\{1\}\{2\}\\mathbb\{E\}\_\{P\\sim\\operatorname\{Dir\}\(c\)\}\\left\|\\frac\{nP\_\{j\}\}\{m\}\-1\\right\|\.Cauchy–Schwarz andVar⁡\(Pj\)=m​\(n−m\)/\(n2​\(n\+1\)\)\\operatorname\{Var\}\(P\_\{j\}\)=m\(n\-m\)/\(n^\{2\}\(n\+1\)\)prove both inequalities\. Whenb=n−m\>0b=n\-m\>0, direct integration at the likelihood\-ratio crossingpj=m/np\_\{j\}=m/nalso gives the exact expression

TV=\(m/n\)m​\(1−m/n\)bm​B​\(m,b\)\.\\operatorname\{TV\}=\\frac\{\(m/n\)^\{m\}\(1\-m/n\)^\{b\}\}\{mB\(m,b\)\}\.Forb=0b=0, both laws are the same point mass and the distance is zero\. ∎

If classjjhas appearedm\>0m\>0times before roundtt, the range\[−1,1\]\[\-1,1\]and Lemma[3](https://arxiv.org/html/2608.06656#Thmtheorem3)bound the corresponding stability term by2​TV≤1/m2\\operatorname\{TV\}\\leq 1/\\sqrt\{m\}\. If it is the first appearance, the supports differ and the trivial bound is22\. LetNi=cT,iN\_\{i\}=c\_\{T,i\}andS=\|\{i:Ni\>0\}\|S=\|\\\{i:N\_\{i\}\>0\\\}\|\. Equations \([6](https://arxiv.org/html/2608.06656#S4.Ex18)\) and \([4](https://arxiv.org/html/2608.06656#S4.Ex20)\) give

Regℓ⁡\(T\)\\displaystyle\\operatorname\{Reg\}\_\{\\ell\}\(T\)≤2​S\+∑i=1K∑m=1Ni−11m\\displaystyle\\leq 2S\+\\sum\_\{i=1\}^\{K\}\\sum\_\{m=1\}^\{N\_\{i\}\-1\}\\frac\{1\}\{\\sqrt\{m\}\}≤2​S\+2​∑i:Ni\>0Ni\\displaystyle\\leq 2S\+2\\sum\_\{i:N\_\{i\}\>0\}\\sqrt\{N\_\{i\}\}≤2​S\+2​S​T≤4​S​T,\\displaystyle\\leq 2S\+2\\sqrt\{ST\}\\leq 4\\sqrt\{ST\},whereS≤TS\\leq TimpliesS≤S​TS\\leq\\sqrt\{ST\}\. The bound is independent ofℓ\\ell, so taking the supremum proves the first part of Theorem[1](https://arxiv.org/html/2608.06656#Thmtheorem1)\.

## 5Smooth\-loss adaptation

Fort≥2t\\geq 2, Dirichlet moments give

𝔼​Pt=qt−1,𝔼​‖Pt−qt−1‖22=1−‖qt−1‖22t≤1t\.\\mathbb\{E\}P\_\{t\}=q\_\{t\-1\},\\qquad\\mathbb\{E\}\\\|P\_\{t\}\-q\_\{t\-1\}\\\|\_\{2\}^\{2\}=\\frac\{1\-\\\|q\_\{t\-1\}\\\|\_\{2\}^\{2\}\}\{t\}\\leq\\frac\{1\}\{t\}\.\(8\)Setq0=P1q\_\{0\}=P\_\{1\}for convenience\. Applying \([2](https://arxiv.org/html/2608.06656#S2.Ex7)\), taking expectations, and using centering yields

𝔼​\[ℓ​\(Pt,yt\)−ℓ​\(qt−1,yt\)\]≤β2​t,t≥2\.\\mathbb\{E\}\[\\ell\(P\_\{t\},y\_\{t\}\)\-\\ell\(q\_\{t\-1\},y\_\{t\}\)\]\\leq\\frac\{\\beta\}\{2t\},\\qquad t\\geq 2\.\(9\)
For completeness, we prove the FTL estimate under precisely the one\-sided definition \([2](https://arxiv.org/html/2608.06656#S2.Ex7)\)\. This avoids assuming that \([2](https://arxiv.org/html/2608.06656#S2.Ex7)\) implies full gradient Lipschitzness\.

###### Lemma 4\(Smooth proper\-loss FTL\)\.

For every differentiable proper loss satisfying \([2](https://arxiv.org/html/2608.06656#S2.Ex7)\), empirical FTL satisfies

∑t=1Tℓ​\(qt−1,yt\)−T​f​\(qT\)≤2​β​HT\.\\sum\_\{t=1\}^\{T\}\\ell\(q\_\{t\-1\},y\_\{t\}\)\-Tf\(q\_\{T\}\)\\leq 2\\beta H\_\{T\}\.

###### Proof\.

We first establish an endpoint condition from propriety and boundary differentiability\. Fixi≠ji\\neq jand setqε=\(1−ε\)​ej\+ε​eiq\_\{\\varepsilon\}=\(1\-\\varepsilon\)e\_\{j\}\+\\varepsilon e\_\{i\}\. Properness atqεq\_\{\\varepsilon\}, comparing the truthful prediction witheje\_\{j\}, says

\(1−ε\)​ℓ​\(qε,ej\)\+ε​ℓ​\(qε,ei\)≤\(1−ε\)​ℓ​\(ej,ej\)\+ε​ℓ​\(ej,ei\)\.\(1\-\\varepsilon\)\\ell\(q\_\{\\varepsilon\},e\_\{j\}\)\+\\varepsilon\\ell\(q\_\{\\varepsilon\},e\_\{i\}\)\\leq\(1\-\\varepsilon\)\\ell\(e\_\{j\},e\_\{j\}\)\+\\varepsilon\\ell\(e\_\{j\},e\_\{i\}\)\.Expanding at zero givesDei−ej​ℓ​\(ej,ej\)≤0D\_\{e\_\{i\}\-e\_\{j\}\}\\ell\(e\_\{j\},e\_\{j\}\)\\leq 0\. Propriety ateje\_\{j\}also says thateje\_\{j\}globally minimizesℓ​\(⋅,ej\)\\ell\(\\cdot,e\_\{j\}\), so the reverse inequality holds\. Thus every tangent derivative ofℓ​\(⋅,ej\)\\ell\(\\cdot,e\_\{j\}\)ateje\_\{j\}is zero\.

Fixp∈ΔKp\\in\\Delta\_\{K\}, writed=‖ej−p‖2d=\\\|e\_\{j\}\-p\\\|\_\{2\}, and defineϕ​\(s\)=ℓ​\(\(1−s\)​p\+s​ej,ej\)\\phi\(s\)=\\ell\(\(1\-s\)p\+se\_\{j\},e\_\{j\}\)\. Equation \([2](https://arxiv.org/html/2608.06656#S2.Ex7)\) is equivalent to concavity ofh​\(s\)=ϕ​\(s\)−\(β​d2/2\)​s2h\(s\)=\\phi\(s\)\-\(\\beta d^\{2\}/2\)s^\{2\}\. Sinceϕ′​\(1\)=0\\phi^\{\\prime\}\(1\)=0, monotonicity of the derivative ofhhgives, fors<1s<1,

ϕ′​\(s\)−β​d2​s=h′​\(s\)≥h′​\(1\)=−β​d2\.\\phi^\{\\prime\}\(s\)\-\\beta d^\{2\}s=h^\{\\prime\}\(s\)\\geq h^\{\\prime\}\(1\)=\-\\beta d^\{2\}\.Henceϕ′​\(s\)≥−β​d2​\(1−s\)\\phi^\{\\prime\}\(s\)\\geq\-\\beta d^\{2\}\(1\-s\)\. The FTL update after outcomeeje\_\{j\}isqt=\(1−1/t\)​qt−1\+ej/tq\_\{t\}=\(1\-1/t\)q\_\{t\-1\}\+e\_\{j\}/t\. Integrating from0to1/t1/tgives

ℓ​\(qt−1,ej\)−ℓ​\(qt,ej\)≤β​‖ej−qt−1‖22t≤2​βt\.\\ell\(q\_\{t\-1\},e\_\{j\}\)\-\\ell\(q\_\{t\},e\_\{j\}\)\\leq\\frac\{\\beta\\\|e\_\{j\}\-q\_\{t\-1\}\\\|\_\{2\}^\{2\}\}\{t\}\\leq\\frac\{2\\beta\}\{t\}\.The standard be\-the\-leader inequality∑tℓ​\(qt,yt\)≤T​f​\(qT\)\\sum\_\{t\}\\ell\(q\_\{t\},y\_\{t\}\)\\leq Tf\(q\_\{T\}\)and summation prove the result\. ∎

Adding \([9](https://arxiv.org/html/2608.06656#S5.Ex30)\) to Lemma[4](https://arxiv.org/html/2608.06656#Thmtheorem4)gives at most2​β​HT\+\(β/2\)​\(HT−1\)≤\(5​β/2\)​HT2\\beta H\_\{T\}\+\(\\beta/2\)\(H\_\{T\}\-1\)\\leq\(5\\beta/2\)H\_\{T\}, completing Theorem[1](https://arxiv.org/html/2608.06656#Thmtheorem1)\.

## 6Related work and interpretation

### U\-calibration\.

Kleinberget al\.\([2023](https://arxiv.org/html/2608.06656#bib.bib1)\)introduced U\-calibration for binary outcomes and connected it to unknown downstream agents\.Luoet al\.\([2024](https://arxiv.org/html/2608.06656#bib.bib2)\)obtained the optimalΘ​\(K​T\)\\Theta\(\\sqrt\{KT\}\)multiclass pseudo\-U\-calibration rate, proved the V\-shaped lower bound, and identified loss classes on which FTL is logarithmic\. Their worst\-case\-optimal perturbed leader is not adaptive to smooth losses\.Frongilloet al\.\([2026](https://arxiv.org/html/2608.06656#bib.bib3)\)introduced a self\-concordant prediction\-space perturbation that adapts to smooth and log\-barrier\-smooth losses\. For the classes considered here, its bounds are approximatelyK5/4​TK^\{5/4\}\\sqrt\{T\}andβ​log⁡T\+β​K​log⁡K\\beta\\log T\+\\beta\\sqrt\{K\}\\log K\. Our result removes these dimension gaps\. Calibeating, omniprediction, and swap\-regret results study related universal downstream guarantees with different benchmarks\(Roth and Shi,[2024](https://arxiv.org/html/2608.06656#bib.bib9); Chenet al\.,[2026](https://arxiv.org/html/2608.06656#bib.bib10)\)\.

### Perturbation and posterior sampling\.

Follow\-the\-Perturbed\-Leader is classical\(Kalai and Vempala,[2005](https://arxiv.org/html/2608.06656#bib.bib6); Cesa\-Bianchi and Lugosi,[2006](https://arxiv.org/html/2608.06656#bib.bib7)\)\. Fresh perturbations also yield the standard nonanticipating adaptive\-adversary extension\(Hutter and Poland,[2005](https://arxiv.org/html/2608.06656#bib.bib5)\)\. Algorithm[1](https://arxiv.org/html/2608.06656#alg1)can instead be viewed as posterior sampling for a categorical model under the limiting zero\-mass Dirichlet prior, or as Rubin’s Bayesian bootstrap\. Dirichlet\-weighted loss minimization appears in the loss\-likelihood bootstrap\(Lyddonet al\.,[2019](https://arxiv.org/html/2608.06656#bib.bib11)\), and normalized random weights have also been maintained in online Bayesian bagging\(Lee and Clyde,[2004](https://arxiv.org/html/2608.06656#bib.bib12)\)\. Dirichlet Bayes mixtures are classical in universal coding under log loss\(Watanabeet al\.,[2013](https://arxiv.org/html/2608.06656#bib.bib8)\), while size\-biased Dirichlet integral identities are classical probability machinery\(Last,[2020](https://arxiv.org/html/2608.06656#bib.bib13)\)\. None of these works gives adversarial regret for an unknown proper loss\. Our contribution is the loss\-uniform count\-deletion specialization, its telescoping use, and the simultaneously optimal guarantees, not the bootstrap draw itself\.

### Why Dirichlet geometry fits both regimes\.

The updatec↦c\+ejc\\mapsto c\+e\_\{j\}has likelihood ration​pj/cjnp\_\{j\}/c\_\{j\}, so its total variation automatically scales with the number of previous appearances of the updated class\. This is the right geometry for discontinuous proper losses\. At the same time,

Cov⁡\(Pt\)=diag⁡\(qt−1\)−qt−1​qt−1⊤t,\\operatorname\{Cov\}\(P\_\{t\}\)=\\frac\{\\operatorname\{diag\}\(q\_\{t\-1\}\)\-q\_\{t\-1\}q\_\{t\-1\}^\{\\top\}\}\{t\},which has the centeredO​\(1/t\)O\(1/t\)radius needed for smooth losses\. The exact identity in Lemma[2](https://arxiv.org/html/2608.06656#Thmtheorem2)is what lets these two local facts control global regret without a separate perturbed\-leader path\-length penalty\.

## 7Limitations and conclusion

Our theorem resolves simultaneous optimality for bounded proper losses and the smooth subclass under the expected\-regret criterion\. It does not control actual U\-calibration𝔼​supℓ∈ℒRegℓ\\mathbb\{E\}\\sup\_\{\\ell\\in\\mathcal\{L\}\}\\operatorname\{Reg\}\_\{\\ell\}over the entire infinite class\. Moving the supremum inside expectation requires complexity control or a different argument\. We also do not address the broader class of losses smooth relative to a log barrier, where Euclidean Dirichlet covariance need not be the right measure\.

The result shows that the previous tradeoff was geometric rather than information\-theoretic\. A Bayesian\-bootstrap sample of empirical FTL has exactly the count stability needed by nonsmooth scores and exactly the centering needed by smooth scores\. The count\-deletion identity makes those two properties compatible in one short analysis\.

## References

- N\. Cesa\-Bianchi and G\. Lugosi \(2006\)Prediction, learning, and games\.Cambridge University Press\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px2.p1.1)\.
- Y\. Chen, Z\. Huang, M\. I\. Jordan, and H\. Luo \(2026\)Calibeating made simple\.InConference on Learning Theory,pp\. 1373–1398\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px1.p1.3)\.
- R\. Frongillo, H\. Luo, N\. A\. Mehta, and J\. Schneider \(2026\)Toward simultaneously optimal regret in u\-calibration\.InConference on Learning Theory,Note:arXiv:2606\.18527Cited by:[§1](https://arxiv.org/html/2608.06656#S1.p2.6),[§1](https://arxiv.org/html/2608.06656#S1.p7.2),[§2](https://arxiv.org/html/2608.06656#S2.p3.1),[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px1.p1.3)\.
- M\. Hutter and J\. Poland \(2005\)Adaptive online prediction by following the perturbed leader\.Journal of Machine Learning Research6\(22\),pp\. 639–660\.Cited by:[Appendix A](https://arxiv.org/html/2608.06656#A1.p1.2),[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px2.p1.1)\.
- A\. Kalai and S\. Vempala \(2005\)Efficient algorithms for online decision problems\.Journal of Computer and System Sciences71\(3\),pp\. 291–307\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px2.p1.1)\.
- B\. Kleinberg, R\. Paes Leme, J\. Schneider, and Y\. Teng \(2023\)U\-calibration: forecasting for an unknown agent\.InConference on Learning Theory,pp\. 5143–5145\.Cited by:[§1](https://arxiv.org/html/2608.06656#S1.p1.1),[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px1.p1.3)\.
- G\. Last \(2020\)An integral characterization of the dirichlet process\.Journal of Theoretical Probability33\(2\),pp\. 918–930\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px2.p1.1)\.
- H\. K\. H\. Lee and M\. A\. Clyde \(2004\)Lossless online bayesian bagging\.Journal of Machine Learning Research5,pp\. 143–151\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px2.p1.1)\.
- H\. Luo, S\. Senapati, and V\. Sharan \(2024\)Optimal multiclass u\-calibration error and beyond\.Advances in Neural Information Processing Systems37,pp\. 7521–7551\.Cited by:[§1](https://arxiv.org/html/2608.06656#S1.p2.6),[§2](https://arxiv.org/html/2608.06656#S2.p5.3),[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px1.p1.3)\.
- S\. P\. Lyddon, C\. C\. Holmes, and S\. G\. Walker \(2019\)General bayesian updating and the loss\-likelihood bootstrap\.Biometrika106\(2\),pp\. 465–478\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px2.p1.1)\.
- A\. Roth and M\. Shi \(2024\)Forecasting for swap regret for all downstream agents\.InACM Conference on Economics and Computation,pp\. 466–488\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px1.p1.3)\.
- D\. B\. Rubin \(1981\)The bayesian bootstrap\.The Annals of Statistics9\(1\),pp\. 130–134\.Cited by:[§1](https://arxiv.org/html/2608.06656#S1.p3.3)\.
- K\. Watanabe, T\. Roos, and P\. Myllymäki \(2013\)Achievability of asymptotic minimax regret in online and batch prediction\.InAsian Conference on Machine Learning,pp\. 181–196\.Cited by:[§6](https://arxiv.org/html/2608.06656#S6.SS0.SSS0.Px2.p1.1)\.

## AI use statement

Generative AI tools were used to assist with proofs and language editing\.

## Appendix AAdaptive outcomes

The main text assumes a fixed outcome sequence\. The same expected bounds hold for a nonanticipating adaptive adversary that may depend on past predictions but not on the fresh drawPtP\_\{t\}\. Condition on the history before the round and on the selected outcome\. Given the current count vector,PtP\_\{t\}is a fresh Dirichlet draw, so the one\-step identity and stability bounds hold conditionally\. Summing conditional expectations gives the same telescoping count potential along the realized count path\. This is the usual fresh\-randomization reduction for perturbed leader\(Hutter and Poland,[2005](https://arxiv.org/html/2608.06656#bib.bib5)\)\. No guarantee is possible against an adversary that observes the current randomized forecast before choosing the same\-round outcome under this protocol\.

## Appendix BAdditional boundary details for Lemma[2](https://arxiv.org/html/2608.06656#Thmtheorem2)

We record a standard approximation that makes the nonsmooth integration by parts fully formal\. Restrictffto the relative interior of the active face\. It is concave and Lipschitz by \([4](https://arxiv.org/html/2608.06656#S3.Ex11)\)\. Convolve it on compact subsets with a smooth mollifier, apply integration by parts to the smooth approximants, and then exhaust the face\. The directional derivatives of a concave Lipschitz function converge almost everywhere and are uniformly bounded in tangent directions\. Dominated convergence applies to every term whenαj\>1\\alpha\_\{j\}\>1\. The boundary flux estimate in the main proof is uniform under this exhaustion\.

Forαj=1\\alpha\_\{j\}=1, writeα\(ε\)=α\+ε​ej\\alpha^\{\(\\varepsilon\)\}=\\alpha\+\\varepsilon e\_\{j\}\. On the common active face, the densities ofDir⁡\(α\(ε\)\)\\operatorname\{Dir\}\(\\alpha^\{\(\\varepsilon\)\}\)converge inL1L^\{1\}to that ofDir⁡\(α\)\\operatorname\{Dir\}\(\\alpha\), hence in total variation\. After deletingeje\_\{j\}, the marginal coordinatePjP\_\{j\}has a Beta distribution with first parameterε\\varepsilonand therefore converges to zero in probability\. Conditional proportions of the remaining coordinates have distributionDir⁡\(α−j\)\\operatorname\{Dir\}\(\\alpha\_\{\-j\}\)\. This proves weak convergence to the deleted face\. Boundedness handles the left side and continuity offfhandles the right side\.

## Appendix CSanity checks

A supplementary script evaluates the identity for Brier, spherical, binary V\-shaped, and multiclass polyhedral proper losses\. It also checks the likelihood\-ratio total\-variation bound and exhaustively enumerates all binary outcome sequences throughT=8T=8\. The smooth Brier identities are also checked in closed form\. These calculations are not used by any proof\.