Research map / Bandits and online learning / Online convex optimization and games
Optimal Multiclass U-Calibration Error and Beyond
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows the minimax optimal pseudo U-calibration error for online multiclass forecasting is Theta(sqrt(KT)) via FTPL with geometric noise plus a V-shaped-loss lower bound, and gives log T U-calibration for Lipschitz and decomposable proper losses using FTL.
Problem
Online multiclass probabilistic forecasting must simultaneously achieve low regret against all bounded proper losses (U-calibration error); the optimal rate was open after Kleinberg et al. (2023) gave O(K sqrt(T)).
Approach
Use FTPL with geometric (instead of uniform) noise on outcome counts, which works for all proper losses at once because the empirical risk minimizer for any proper loss is the mean; pair it with a V-shaped proper loss lower bound and show FTL achieves log T for Lipschitz and decomposable losses.
Key results
- FTPL with geometric noise achieves pseudo U-calibration error at most 4 sqrt(KT), improving the O(K sqrt(T)) bound of prior work.
- A V-shaped proper loss forces any algorithm to suffer Omega(sqrt(KT)) regret, so the optimal pseudo U-calibration error is Theta(sqrt(KT)).
- FTL achieves O(G log T) U-calibration error for G-Lipschitz proper losses and O(K log T) for decomposable losses, with a matching Omega(log T) lower bound for Lipschitz losses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace uniform perturbations with geometric noise | FTPL for online multiclass U-calibration · All bounded proper losses | pseudo U-calibration error: 𝒪(K√T) -> 4√(KT) | Helped |
| Use FTPL with geometric noise | Online multiclass U-calibration · All bounded proper losses, T ≥ 12K | pseudo U-calibration error: 4√(KT); Ω(√(KT)) | Mixed |
| Apply FTPL to a loss class with finite covering number | FTPL with geometric noise · Finite-cover loss classes | U-calibration error: 2 + 4εT + 4√(KT) + √(2T log(T · M(ℒ', ε; ‖.‖∞))) | Helped |
| Use Follow-the-Leader on G-Lipschitz proper losses | Online multiclass U-calibration · G-Lipschitz proper losses | U-calibration error: 2 + 2G log T | Helped |
| Use Follow-the-Leader on decomposable proper losses | Online multiclass U-calibration · Decomposable proper losses | U-calibration error: 2K + (K + 1)βℓ (1 + log T) | Helped |
| Use the decomposable-loss analysis for Tsallis losses with α ∈ (1,2) | Follow-the-Leader · Tsallis proper losses | regret: 𝒪(c̃K α(α-1) K² log T) | Helped |
| Use the local-Lipschitzness analysis instead of the decomposable-loss analysis | Follow-the-Leader on Tsallis losses with α ∈ (1,2) · Tsallis proper losses | regret: 𝒪(K + c̃Kα(α-1)T^(2 - α) log T) vs. 𝒪(c̃K α(α-1) K² log T) | Hurt |
| Use Follow-the-Leader on unrestricted bounded proper losses | Online multiclass U-calibration · General bounded proper losses | regret: Ω(T) | Hurt |
| Use an algorithm other than FTL for unrestricted bounded proper losses | Online multiclass U-calibration · General bounded proper losses | regret: FTL: Ω(T); FTPL: 4√(KT) | Helped |
Surprising findings
- FTL can suffer Omega(T) regret for a bounded proper loss, so deterministic leader-following is not generally sufficient.
- Global Lipschitzness is not necessary for the log T FTL bound; local Lipschitzness suffices.
Limitations
- Actual U-calibration error (sup inside expectation) optimal rate left open beyond pseudo version
- Results restricted to proper losses and non-contextual setting
Experimental setup
Metrics: pseudo U-calibration error U-calibration error regret
Baselines: Kleinberg et al. (2023) algorithm with O(K sqrt(T)) bound
Builds on: Kleinberg et al. (2023) U-calibration Daskalakis and Syrgkanis (2016) FTPL V-shaped loss (binary U-calibration)
Closest papers by meaning
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.88)
- Simultaneous Swap Regret Minimization via KL-Calibration (NeurIPS 2025 · similarity 0.85)
- Truthfulness of Calibration Measures (NeurIPS 2024 · similarity 0.84)
- Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.84)
- The Minimax Rate of Second-Order Calibration (NeurIPS 2026 · similarity 0.84)
- MaxEnt Loss: Constrained Maximum Entropy for Calibration under Out-of-Distribution Shift (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.