🤖 machine learning

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

This paper introduces a simple Dirichlet Follow-the-Leader forecaster that achieves optimal regret rates for both bounded and smooth proper losses in simultaneous multiclass U-calibration, thereby closing the previously known dimension-dependent gaps in existing self-concordant perturbation methods.

Original authors: Pahan Dewasurendra

Published 2026-08-10

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Pahan Dewasurendra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a weather forecaster, but with a twist: you don't know who is listening to your forecast, or what they care about. Maybe one listener is a farmer who gets paid only if you predict rain perfectly, while another is a solar panel owner who only cares if you predict sunshine. In the world of machine learning, this is called "U-calibration." It's the ultimate test of a predictor: can you make a single sequence of guesses that works well for everyone, no matter how they measure "good"?

For a long time, scientists thought this was a game of trade-offs. If you tried to be perfect for the farmer (who deals with sudden, sharp changes in weather), you might stumble when predicting for the solar owner (who prefers smooth, gradual shifts). It was like trying to wear shoes that are both perfect for running on jagged rocks and perfect for gliding on ice; usually, you had to pick one and suffer on the other. The big question was: Is there a magic pair of shoes that handles both terrains perfectly at the same time?

This paper says, "Yes, there is." The author, Pahan Dewasurendra, introduces a surprisingly simple method called "Dirichlet Follow-the-Leader." Think of it as a chef who, after tasting a soup, doesn't just guess the next ingredient based on a rigid recipe. Instead, the chef grabs a handful of the ingredients they've already used, tosses them into a blender with a little bit of randomness (like a fresh shake of the pot), and serves that as the next guess. This method, which is essentially a fresh "Bayesian bootstrap" of past outcomes, manages to close the gap between the two difficult terrains. It proves that you don't need complex, heavy machinery to adapt to every type of loss function; you just need to look at the history of what happened and draw a new prediction from that history, weighted by how often each outcome has appeared. The result is a forecaster that is mathematically proven to be optimal for both the "rocky" and "icy" terrains simultaneously, without needing to know in advance which terrain the listener prefers.

The Problem: The "One-Size-Fits-None" Dilemma

Imagine you are playing a game where you have to predict which of $K$ different colored balls will be drawn next. After each guess, you find out the true color. But here's the catch: you don't know the rules of the game. The "score" you get for being right depends on a secret formula chosen by an opponent.

Some formulas are "rough." They punish you heavily if you are even slightly wrong, like a cliff edge. Others are "smooth." They forgive small mistakes, like a gentle slope. For years, researchers knew how to build a predictor that was great at the rough cliffs (getting a score that improves as $\sqrt{T}$ , where $T$ is the number of rounds) and another that was great at the gentle slopes (getting a score that improves as $\log T$ ). But when they tried to combine them into one "super-predictor" that could handle any formula, they hit a wall. The best they could do was a clumsy compromise that was slower than necessary, with a penalty that grew with the number of colors ( $K$ ) in a messy way. It was like trying to drive a car that was both a race car and a tank; the result was a slow, heavy vehicle that wasn't great at either.

The Solution: The "Fresh Bootstrap" Chef

The paper introduces a new strategy that is shockingly simple. Instead of using complex math to smooth out the rough edges or sharpen the soft ones, the algorithm does this:

Keep a Tally: Every time a color is drawn, the algorithm adds a "count" to that color's bucket.
The Magic Draw: To make the next prediction, the algorithm doesn't just pick the most common color. Instead, it treats the current counts as a recipe. It draws a new prediction from a "Dirichlet distribution" based on those counts.

To visualize this, imagine you have a bag of marbles representing the colors you've seen so far. If you've seen Red 5 times and Blue 3 times, you put 5 Red marbles and 3 Blue marbles in a bag. Now, to make your next guess, you reach in, pull out a handful of marbles, and see what the "average" color of that handful looks like. But here's the twist: every single time you make a guess, you reset the bag with the current counts and pull a fresh handful. You don't keep the marbles you pulled; you just use the idea of that handful to make your prediction.

This is what the author calls a "fresh Bayesian bootstrap." It's like a chef who, after every meal, takes the ingredients they've used, shakes them up in a new bowl, and serves a slightly different version of the dish. Because the shake-up is random but based on the history, the prediction naturally hovers around the "Follow-the-Leader" (the most common outcome) but wobbles just enough to explore other options.

Why It Works: The Two Secrets

The brilliance of this paper lies in proving why this simple "shake-up" works for both rough and smooth games. The author discovered two hidden geometric facts that make this possible:

1. The "Count Stability" for Rough Games
For the rough, cliff-edge formulas, the key is stability. If a color has appeared many times (say, 100 times), the "shake-up" is very small. The algorithm is confident. If a color has only appeared once, the shake-up is huge, allowing the algorithm to be flexible. The paper proves a specific mathematical identity: the average loss of this "shake-up" prediction is exactly equal to a specific difference in the "Bayes risk" (the best possible score). This identity makes the math "telescope," meaning all the messy middle terms cancel out, leaving only a tiny, manageable error. The error shrinks as the square root of the number of times a class has been seen ( $1/\sqrt{m}$ ). This is exactly the right speed to handle the rough cliffs.

2. The "Centered Radius" for Smooth Games
For the smooth, gentle-slope formulas, the key is that the prediction shouldn't wander too far from the truth. The "shake-up" prediction has a special property: its average is exactly the "Follow-the-Leader" (the empirical average), and its "radius" (how far it can stray) shrinks perfectly as $1/t$ (where $t$ is the time step). This means that for smooth formulas, the algorithm behaves almost exactly like a perfect learner, with the error shrinking logarithmically ( $\log T$ ).

The Result: Closing the Gap

The paper proves that this single, simple algorithm achieves the best possible performance for both types of games at the same time.

For any bounded proper loss (the rough cliffs): The regret (the score gap between the algorithm and the best possible hindsight) is at most $4\sqrt{S_T T}$ , where $S_T$ is the number of distinct outcomes seen so far. This is the fastest possible rate.
For any $\beta$ -smooth proper loss (the gentle slopes): The regret is at most $\frac{5}{2}\beta(1 + \log T)$ . This is also the fastest possible rate.

Crucially, the algorithm doesn't need to know in advance whether the game is rough or smooth. It doesn't need a "learning rate" to tune, nor does it need to know how many rounds ( $T$ ) will be played. It just looks at the history, shakes the bag, and predicts.

What It Rules Out

The paper explicitly rules out the idea that you need complex, dimension-dependent penalties to get this result. Previous methods used "self-concordant perturbations" that added a penalty term growing with $K^{5/4}$ , making them slow when there were many colors. This paper shows that such a penalty is unnecessary; the geometry of the Dirichlet distribution handles the complexity naturally.

It also clarifies that while the algorithm is optimal in "expected regret" (the average performance over many runs of the game), it does not claim to be optimal for the "worst-case regret" across all possible loss functions simultaneously in a single run (which would require a much stronger, and likely impossible, guarantee). However, for the standard definition of U-calibration used in the field, this is the gold standard.

The Takeaway

In the end, this paper is a reminder that sometimes the most powerful tools are the simplest. By simply re-sampling the past with a fresh, random twist, the "Dirichlet Follow-the-Leader" algorithm manages to be the perfect chameleon. It adapts to the jagged rocks and the smooth ice without ever needing to change its shoes. It proves that the trade-off between handling rough and smooth losses wasn't a fundamental law of the universe, but just a gap in our understanding of how to shake the bag.

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

1. Problem Statement

The paper addresses the challenge of simultaneous multiclass U-calibration in online learning. The goal is to design a single forecaster that achieves optimal regret rates across two distinct regimes of proper loss functions:

Bounded Proper Losses: The forecaster must minimize worst-case regret for any bounded proper loss (including non-differentiable, polyhedral, or V-shaped losses).
Smooth Proper Losses: The forecaster must simultaneously adapt to smooth proper losses (specifically $\beta$ -smooth losses), achieving logarithmic regret rates similar to Follow-the-Leader (FTL).

Prior work established that while optimal rates exist for each regime individually, a single algorithm achieving both simultaneously was an open question. Recent approaches using self-concordant perturbations (Frongillo et al., 2026) came close but left two significant "gaps":

A dimension gap in the worst-case rate: $O(K^{5/4}\sqrt{T})$ instead of the optimal $O(\sqrt{KT})$ .
An additive gap in the smooth rate: An extra term of $O(\beta\sqrt{K}\log K)$ preventing pure logarithmic adaptation.

The paper asks whether a single, horizon-free algorithm can close both gaps to achieve simultaneous optimality.

2. Methodology

The proposed solution is a simple, one-line algorithm called Dirichlet Follow-the-Leader (Dir-FTL).

Algorithm: At each time step $t \geq 2$ , after observing the cumulative count vector of outcomes $c_{t-1}$ , the forecaster draws the next prediction $P_t$ from a Dirichlet distribution parameterized by these counts:
$P_t \sim \text{Dir}(c_{t-1})$
Zero-count coordinates are fixed at zero, meaning the distribution lives on the face of the simplex spanned by classes observed so far. This is equivalent to a fresh Bayesian bootstrap of the observed outcomes (Rubin, 1981).
Core Analytical Tool: The analysis relies on a novel exact identity (Lemma 2) connecting the expected loss under a Dirichlet distribution to the Bayes risk. For a proper loss $\ell$ with concave Bayes risk $f$ , and $F(\alpha) = \mathbb{E}_{P \sim \text{Dir}(\alpha)}[f(P)]$ , the identity states:
$\mathbb{E}_{P \sim \text{Dir}(\alpha)}[\ell(P, e_j)] = nF(\alpha) - (n-1)F(\alpha - e_j)$
where $n = \sum \alpha_i$ and $\alpha_j \geq 1$ .
Regret Decomposition: The proof decomposes the regret into two components:
1. Perturbed-Leader Term: Using the identity above, the cumulative loss of the perturbed leader telescopes to a non-positive Jensen gap ( $T(F(c_T) - f(c_T/T)) \leq 0$ ).
2. Stability Term: The difference between consecutive predictions is bounded using the Total Variation (TV) distance between Dirichlet distributions with parameters differing by a single count.

3. Key Contributions

The paper makes three primary technical contributions:

A Horizon-Free, Simultaneously Optimal Algorithm: It introduces Dir-FTL, which requires no learning rate, horizon parameter, or smoothness parameter. It achieves optimal rates for both bounded and smooth losses simultaneously.
The Count-Deletion Identity: It proves the exact identity (Equation 1) for arbitrary bounded proper losses, handling non-differentiable Bayes risks, zero-count coordinates, and singular cases ( $\alpha_j=1$ ). This identity transforms the perturbation analysis into a telescoping sum.
Geometric Separation of Regimes: It isolates two geometric facts that allow simultaneous adaptation:
- Nonsmooth Loss Control: The one-count Dirichlet total variation scales as $O(1/\sqrt{m})$ (where $m$ is the count of a class), providing the necessary stability for discontinuous losses.
- Smooth Loss Control: The centered covariance of the Dirichlet distribution scales as $O(1/t)$ , providing the necessary centering for smooth losses without requiring a separate path-length penalty.

4. Results

The paper establishes the following regret bounds for Algorithm 1 (where $S_T$ is the number of distinct outcomes observed, $K$ is the number of classes, and $T$ is the time horizon):

Worst-Case (Bounded Proper Losses):
$\sup_{\ell \in \mathcal{L}} \mathbb{E}[\text{Reg}_\ell(T)] \leq 4\sqrt{S_T T} \leq 4\sqrt{KT}$
This matches the known $\Theta(\sqrt{KT})$ lower bound for multiclass pseudo-U-calibration (Luo et al., 2024).
Smooth Losses ( $\beta$ -smooth):
$\mathbb{E}[\text{Reg}_\ell(T)] \leq \frac{5}{2}\beta H_T \leq \frac{5}{2}\beta(1 + \log T)$
This matches the $\Omega(\log T)$ lower bound for squared loss and removes the additive $O(\beta\sqrt{K}\log K)$ term found in previous work.

These rates are optimal in their respective nontrivial regimes up to universal constants.

5. Significance and Claims

The paper claims to resolve the question of whether simultaneous optimality is possible, answering affirmatively. Its significance lies in:

Closing Dimension Gaps: It eliminates the $K^{5/4}$ factor and the additive $\sqrt{K}$ term in the regret bounds, showing that the previous trade-offs were geometric rather than information-theoretic.
Simplicity: It demonstrates that a classical Bayesian bootstrap (Dirichlet sampling) is sufficient for adversarial U-calibration, removing the need for complex self-concordant perturbations.
Unified Analysis: It provides a single, short analysis that covers both differentiable and non-differentiable losses, as well as changes in the active simplex face.

Limitations:
The author explicitly notes that their result controls the expected pseudo-U-calibration ( $\sup_\ell \mathbb{E}[\text{Reg}_\ell]$ ), not the stronger actual U-calibration ( $\mathbb{E}[\sup_\ell \text{Reg}_\ell]$ ) over the infinite class of all proper losses. Additionally, the result does not extend to losses smooth relative to a log barrier, where Euclidean Dirichlet covariance may not be the appropriate measure.