Research map / Bandits and online learning / Online convex optimization and games
Simultaneous Swap Regret Minimization via KL-Calibration
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.
Introduces (pseudo) KL-Calibration, shows it equals (pseudo) swap regret of log loss, and gives non-constructive and explicit Blum-Mansour-based algorithms achieving Õ(T^{1/3}) bounds for simultaneous swap regret over proper-loss classes.
Problem
Online probabilistic forecasting of binary outcomes with calibration guarantees strong enough for downstream loss minimization; existing l2-calibration and pseudo swap regret results cover only smooth losses and lack actual (non-pseudo) swap regret bounds.
Approach
Define KL-Calibration as a calibration measure whose Bregman-divergence form equals swap regret of log loss; a non-uniform discretization and a new randomized rounding for log loss make Blum-Mansour with exponentially weighted online optimization achieve Õ(T^{1/3}) pseudo KL-calibration, implying simultaneous swap regret bounds for a broad class of proper losses.
Key results
- Non-constructive algorithm achieves E[KLCal] = O(T^{1/3} (log T)^{5/3}), implying simultaneous expected swap regret bounds for log loss and classes L_2 and L_G.
- Explicit BM-based algorithm achieves pseudo KL-calibration O(T^{1/3} (log T)^{2/3}) with K=(T/log T)^{1/3}.
- High-probability l2-calibration bound O(T^{1/3} (log T)^{-1/3} log(T/delta)) for the explicit algorithm, the first sub-sqrt(T) high-probability bound for l2-calibration via an efficient algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use non-uniform discretization and a minimax-based algorithm | KL-Calibration existence algorithm · Online binary calibration | expected KL-Calibration error: \cO(T^{\frac{1}{3}} (\log T) ^ {\frac{5}{3}}) | Helped |
| Use non-uniform discretization and randomized rounding for log loss | Blum-Mansour for log loss · Online binary calibration | pseudo KL-Calibration error: \cO\bigc{T^{\frac{1}{3}} (\log T) ^ {\frac{2}{3}}} | Helped |
| Use non-uniform discretization and randomized rounding instead of the cited prior approach | Blum-Mansour for log loss · Online binary calibration, log loss | pseudo swap regret: \cO(T^{\frac{1}{3}} (\log T) ^ {\frac{2}{3}}) | Helped |
| Use the KL-Calibration bound for smooth proper losses | KL-Calibration existence algorithm · Online binary calibration, bounded proper losses with twice continuously differentiable univariate form | expected maximum swap regret: \cO(T^{\frac{1}{3}} (\log T) ^ {\frac{5}{3}}) | Helped |
| Use the explicit Blum-Mansour algorithm with randomized rounding | Blum-Mansour for log loss · Online binary calibration, bounded proper losses with twice continuously differentiable univariate form | pseudo maximum swap regret: \cO(T^{\frac{1}{3}} (\log T) ^ {\frac{2}{3}}) | Helped |
| Replace uniform discretization with the specified non-uniform discretization | KL-Calibration existence algorithm · Online binary calibration, log loss | swap regret | Helped |
| Use the proposed randomized rounding instead of rounding to the nearest grid point or the cited rounding procedure | Blum-Mansour for log loss · Online binary calibration, log loss | change in expected loss: \cO\bigc{\frac{1}{K^{2}}} | Helped |
| Use scaled online gradient descent for each external-regret algorithm instead of EWOO | Algorithm of the cited prior work · Online binary calibration, bounded proper losses with G-smooth univariate form | computational efficiency | Helped |
Limitations
- Non-constructive proof for the expected KL-calibration bound; no explicit algorithm for high-probability KLCal.
- T^{2/3} dependence for general bounded proper losses outside L_2 and L_G.
- Algorithm requires knowledge of horizon T unless doubling trick is used.
Experimental setup
Metrics: KL-calibration error pseudo KL-calibration error swap regret l2-calibration error
Baselines: Fishelson et al. (2025) pseudo swap regret algorithm l1-calibration algorithms Follow-the-Leader for U-calibration Azuma-Hoeffding analysis
Builds on: Blum-Mansour reduction Fishelson et al. 2025 pseudo swap regret of squared loss Gopalan et al. swap regret simultaneous calibration exponentially weighted online optimization
Closest papers by meaning
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.91)
- Testable and Actionable Calibration for Full Swap Regret (NeurIPS 2026 · similarity 0.89)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.86)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.85)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.85)
- Cumulative Regret Analysis of the Piyavskii–Shubert Algorithm and Its Variants for Global Optimization (AAAI 2024 · similarity 0.85)
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.