Research map / Bandits and online learning / Online convex optimization and games
Improved and Oracle-Efficient Online $\ell_1$-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 direct reduction from online l1-multicalibration to a product-reward online learning problem (OLPO), yielding O~(T^-1/3) information-theoretic rates for finite/covered groups and O~(T^-1/4) oracle-efficient rates using one offline oracle call per round.
Problem
Online l1-multicalibration across many groups in adversarial settings: prior methods go through l2/l_inf guarantees and lose rate, and most algorithms scale linearly in the group class size.
Approach
Reduce online l1-multicalibration to an online linear-product optimization problem (OLPO), linearize it via a mixed-norm expanded action space with OLO instances plus multiplicative weights, and adapt generalized FTPL with a Boolean-hypercube action set so that a single offline multicalibration-evaluation oracle call per round suffices.
Key results
- Finite-group online l1-multicalibration achieves E[K] = O(B T^-1/3 sqrt(log(6T|H|))) in time linear in |H|.
- Infinite classes covered by an beta-cover give O(B T^-1/3 sqrt(log(6T|H_beta|))) + beta, e.g. bounded linear functions in d dims with runtime O((B sqrt T)^d).
- Oracle-efficient algorithm achieves O~(T^-1/4 sqrt(log T)) using a single offline oracle call per round under transductive or small-separator assumptions with binary-valued groups.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the direct linearized OLPO method instead of transferring an ℓ∞-multicalibration guarantee to ℓ1 | Online ℓ1-multicalibration for finite H · Online ℓ1-multicalibration | error rate: \widetilde{O}( T^{-1/4} ) -> O\left(BT^{-1/3}\sqrt{\log(6T|\mathcal{H}|)}\right) | Helped |
| Use the offline-oracle OLPO algorithm instead of the prior online-regression-oracle method | Oracle-efficient online multicalibration · Oracle-efficient online multicalibration | error rate: \widetilde{O}( T^{-1/8} ) -> \widetilde{O}\big(T^{-1/4} \sqrt{\log (T)}\big) | Helped |
| Use a β-cover of the hypothesis class and transfer its guarantee using the 1-Lipschitz property | Linearized OLPO · Online ℓ1-multicalibration, infinite H | expected ℓ1-multicalibration error: O\left(BT^{-1/3}\sqrt{\log(6T|\mathcal{H}_{\beta}|)}\right) + \beta | Mixed |
Surprising findings
- The improved rate for finite groups is claimed to be obtainable with a worst-case regret bound, without requiring a small-loss bound or min-max optimization, as an alternative to a concurrent Theorem 3.4 approach.
Limitations
- Oracle-efficient guarantee requires binary-valued groups and transductive or small-separator context assumptions.
- Oracle-efficient rate has linear dependence on M (discretization), giving T^-1/4 instead of T^-1/3.
- Infinite-class bounds incur curse of dimensionality in covering numbers (e.g. convex functions with d>2).
Experimental setup
Metrics: expected online l1-multicalibration error
Baselines: online l_inf multicalibration (T^-1/4 rate) oracle-efficient online regression multicalibration (T^-1/8) Theorem 3.4 small-loss expert framework
Builds on: generalized FTPL online gradient descent multiplicative weights Blackwell approachability calibration reduction
Closest papers by meaning
- Instance-Adaptive Online Multicalibration (NeurIPS 2026 · similarity 0.91)
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.88)
- Improved Bounds for Swap Multicalibration and Swap Omniprediction (NeurIPS 2025 · similarity 0.87)
- Discretization-free Multicalibration through Loss Minimization over Tree Ensembles (NeurIPS 2025 · similarity 0.85)
- Divide et Calibra: Multiclass Local Calibration via Vector Quantization (NeurIPS 2026 · 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.