Research map / Bandits and online learning / Online convex optimization and games
High-Dimensional Calibration from Swap Regret
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.
Gives a unified analysis of TreeCal, a TreeSwap-based multi-dimensional calibration algorithm over arbitrary convex sets and norms, with calibration bounds via OLO regularizers and an exponential lower bound on 1/epsilon dependence.
Problem
Online calibration of multi-dimensional forecasts over an arbitrary convex set relative to an arbitrary norm, including how many rounds are needed to achieve epsilon calibration error.
Approach
Reduces norm-based calibration error to full swap regret via Bregman divergences of a strongly convex regularizer, and shows TreeSwap with Follow-The-Leader (equivalent to TreeCal, playing averages of past outcomes) bounds it by analyzing Be-The-Leader; the bound is tied to the optimal OLO regret rate.
Key results
- TreeCal achieves epsilon-calibration over arbitrary convex sets and norms after T = exp(O(rho/eps^2 log(...))) rounds, recovering d^{O(1/eps^2)} simplex bound for l1 norm.
- Squared-norm calibration error bound with only singly-exponential dependence on 1/epsilon: T >= exp(O(rho/eps ...)).
- Any l1-calibration algorithm over the d-simplex needs T >= exp(poly(1/eps)) rounds for d >= poly(1/eps), strengthening the d^{Omega(log 1/eps)} lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply TreeCal using the strongly convex regularizer rate associated with the action set and norm | TreeCal · Arbitrary bounded convex set | squared-norm calibration error: \mathsf{Cal}_T^{\norm{\cdot}^2} \leq \epsilon T; T \geq \exp\left(O\left(\frac{\mathsf{Rate}(\cP, \| \cdot \|)}{\epsilon | Helped |
| Use the negative entropy regularizer on the simplex | TreeCal · d-dimensional simplex, ℓ1 norm | calibration error: d^{O(\log(1/\epsilon)/\epsilon^2)} | Helped |
| Use the Euclidean regularizer on the ℓ2 ball | TreeCal · ℓ2 ball, ℓ2 norm | calibration error: \exp(O(\log(1/\epsilon)/\epsilon^2)) | Helped |
| Require calibration error at most εT against an oblivious adversary | Any online calibration algorithm · d-dimensional simplex, ℓ1 norm | required rounds lower bound: T \leq \exp(c \cdot \min \{ d^{1/14}, \epsilon^{-1/6} \}) | Hurt |
| Require calibration error at most εT | Any online calibration algorithm · Unit ℓ2 ball, ℓ2 norm | required rounds lower bound: \exp(\Omega(\min\{d^{1/14}, \epsilon^{-1/7}\})) | Hurt |
Surprising findings
- The lower bound shows exponential dependence on 1/epsilon is necessary, ruling out poly(1/eps) rates for l1 calibration with dimension-free-ish settings.
Limitations
- Bounds are exponential in rho/epsilon, so practical sample complexity is large
- Lower bound requires d at least poly(1/eps) and applies to oblivious adversaries
Experimental setup
Metrics: norm-based calibration error swap regret
Baselines: Foster-Vohra algorithm TreeCal of prior multi-class calibration work
Builds on: TreeSwap Foster-Vohra calibration Bregman divergence proper scoring rules
Closest papers by meaning
- Simultaneous Swap Regret Minimization via KL-Calibration (NeurIPS 2025 · similarity 0.91)
- Optimal Multiclass U-Calibration Error and Beyond (NeurIPS 2024 · similarity 0.88)
- Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.88)
- High-Dimensional Prediction for Sequential Decision Making (ICML 2025 · similarity 0.88)
- Instance-Adaptive Online Multicalibration (NeurIPS 2026 · similarity 0.87)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.86)
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.