New U-Calibration Algorithm Simultaneously Optimizes Regret for All Losses
Researchers crack long-standing trade-off: optimal regret for both general and smooth loss functions.
U-calibration aims to create online forecasting algorithms that guarantee low regret simultaneously for all proper loss functions, regardless of which downstream agent uses the predictions. Existing algorithms were worst-case optimal, achieving O(√T) regret for any bounded proper loss, but they failed to adapt to easier losses: even for smooth losses like squared loss, they incurred Ω(√T) regret instead of the optimal O(log T). This inability to exploit smoothness was a significant limitation in practice.
In a paper accepted at COLT 2026, Frongillo, Luo, Mehta, and Schneider introduce a new algorithm that finally overcomes this barrier. Their approach uses a novel variant of Follow-the-Perturbed-Leader (FTPL) that applies perturbations directly in the prediction space with self-concordant noise. The algorithm achieves simultaneously optimal regret: Õ(√T) for all bounded proper losses and O(log T) for all bounded smooth proper losses. It also attains logarithmic regret for losses that are smooth relative to the log-barrier, including non-Lipschitz examples. The analysis departs substantially from prior FTPL work due to the complex noise structure and may be of independent interest for online learning and game theory.
- Achieves O(√T) worst-case regret for all bounded proper losses and O(log T) for smooth losses, resolving a known trade-off
- Novel FTPL variant applies self-concordant noise directly in prediction space, enabling adaptation to easier loss functions
- Also handles non-Lipschitz losses that are smooth relative to the log-barrier, extending practical applicability
Why It Matters
Online forecasting algorithms can now adapt to data difficulty, improving calibration efficiency for real-world AI systems.