Research map / Bandits and online learning / Online convex optimization and games
Instance-Adaptive Online Multicalibration
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 single efficient online multicalibration algorithm (dynamic dyadic bins with sleeping-experts AdaNormalHedge wrapper) whose error adapts to instance structure, recovering O~(T^{2/3}) worst case, O~(sqrt(JT)) for J-piecewise stationary marginal means, and tight threshold-complexity dependence.
Problem
Online multicalibration and calibration rates are known only in the worst case (T^{2/3}); it is unclear whether instance-dependent rates interpolating between sqrt(T) on easy instances and T^{2/3} exist.
Approach
Adaptively refine a dyadic grid of prediction values (splitting an interval once its accumulated play reaches L/w^2), choose mixed forecasts via a weighted feasibility LP, and drive per-interval bias control with a sleeping-experts AdaNormalHedge wrapper; error is bounded by the number of leaves in the refinement tree, which is controlled by threshold-representability of contextual score approxima
Key results
- Worst-case bound O~(T^{2/3}) recovered; marginal stochastic setting gives O~(sqrt T)
- Piecewise-stationary marginal with J segments gives O~(sqrt(JT))
- Threshold-complexity dependence shown tight up to log factors via parameterized Walsh lower bound Omega~(sqrt(T Gamma))
Limitations
- Efficient only for explicitly represented finite group families
- Lower bound for threshold complexity relies on parameterized Walsh instance and is proof-sketched
- Marginal-calibration results restricted to ECE-type metric in this version
Experimental setup
Metrics: multicalibration error marginal calibration error (ECE-style sum)
Baselines: worst-case T^{2/3} online multicalibration algorithms Walsh lower-bound instance
Builds on: AdaNormalHedge Freedman inequality zooming algorithms
Closest papers by meaning
- Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.91)
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.87)
- Improved Bounds for Swap Multicalibration and Swap Omniprediction (NeurIPS 2025 · similarity 0.86)
- Discretization-free Multicalibration through Loss Minimization over Tree Ensembles (NeurIPS 2025 · similarity 0.85)
- An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions (ICML 2025 · similarity 0.84)
- Bridging Multicalibration and Out-of-distribution Generalization Beyond Covariate Shift (NeurIPS 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.