Research map / Learning theory and algorithms / Sample complexity
Improved Bounds for Swap Multicalibration and Swap Omniprediction
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 an efficient algorithm achieving Õ(T^{1/3}) ℓ2-swap multicalibration against bounded linear functions, which propagates to Õ(T^{2/3}) ℓ1-swap multicalibration and swap omniprediction for convex Lipschitz losses, and improved sample complexities in the distributional setting.
Problem
Efficiently achieving low swap multicalibration and swap omniprediction error in the online and distributional settings, where prior best bounds for linear-function classes and convex Lipschitz losses were much weaker (e.g., T^{3/4} for ℓ2-swap multicalibration, T^{7/8} for swap omniprediction).
Approach
Reduce ℓ2-swap multicalibration to pseudo contextual swap regret (defined over conditional distributions rather than realized predictions), minimize it deterministically with a Blum-Mansour reduction over N+1 external-regret learners (each an online Newton step over linear functions with randomized rounding), then convert back with a Freedman-based martingale argument; the same algorithm propagate
Key results
- Achieves Õ(T^{1/3} d^{2/3}) ℓ2-swap multicalibration error against linear functions, answering the open problem of Garg et al. (2024) about Õ(√T).
- Achieves Õ(T^{2/3}) ℓ1-swap multicalibration and swap omniprediction error for convex Lipschitz losses, improving the prior Õ(T^{7/8}).
- Sample complexities: Õ(ε^{-3}) for swap omniprediction, Õ(ε^{-2.5}) for swap agnostic learning and ℓ2-swap multicalibration, Õ(ε^{-5}) for ℓ1-swap multicalibration (improving ε^{-10}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed algorithm instead of the previous best-known method | Online contextual swap regret · Online contextual swap regret | regret: $\tilde{\cO}(T^{\frac{3}{4}})$ -> $\tilde{\cO}(T^{\frac{3}{5}})$ | Helped |
| Use the proposed algorithm instead of the previous best-known method | Online ℓ₂-swap multicalibration · Online ℓ₂-swap multicalibration | error: $\tilde{\cO}(T^{\frac{3}{4}})$ -> $\tilde{\cO}(T^{\frac{1}{3}})$ | Helped |
| Use the proposed algorithm instead of the previous best-known method | Online ℓ₁-swap multicalibration · Online ℓ₁-swap multicalibration | error: $\tilde{\cO}(T^{\frac{7}{8}})$ -> $\tilde{\cO}(T^{\frac{2}{3}})$ | Helped |
| Use the proposed algorithm instead of the previous best-known method | Online swap omniprediction · Online swap omniprediction | error: $\tilde{\cO}(T^{\frac{7}{8}})$ -> $\tilde{\cO}(T^{\frac{2}{3}})$ | Helped |
| Use the proposed algorithm instead of the previous best-known method | Distributional swap agnostic learning · Distributional swap agnostic learning | sample complexity: $\tilde{\cO}(\varepsilon ^ {-5})$ -> $\tilde{\cO}(\varepsilon ^ {-2.5})$ | Helped |
| Use the proposed algorithm instead of the previous best-known method | Distributional ℓ₂-swap multicalibration · Distributional ℓ₂-swap multicalibration | sample complexity: $\tilde{\cO}(\varepsilon ^ {-5})$ -> $\tilde{\cO}(\varepsilon ^ {-2.5})$ | Helped |
| Use the proposed algorithm instead of the previous best-known method | Distributional ℓ₁-swap multicalibration · Distributional ℓ₁-swap multicalibration | sample complexity: $\tilde{\cO}(\varepsilon ^ {-10})$ -> $\tilde{\cO}(\varepsilon ^ {-5})$ | Helped |
| Use the proposed algorithm instead of the previous best-known method | Distributional swap omniprediction · Distributional swap omniprediction | sample complexity: $\tilde{\cO}(\varepsilon ^ {-10})$ -> $\tilde{\cO}(\varepsilon ^ {-3})$ | Helped |
Surprising findings
- ℓ2-swap multicalibration against linear functions achieves the same rate as ℓ2-calibration (T^{1/3}), despite being a stronger notion.
Limitations
- Results are for linear/affine function classes and convex Lipschitz losses; extension to arbitrary hypothesis or loss classes is open.
- Analysis assumes an oblivious adversary, though it is said to generalize to adaptive adversaries.
- Contextual swap regret bound of Õ(T^{3/5}) is not the best achievable; a different discretization gives T^{2/3} in the remark.
Experimental setup
Metrics: swap multicalibration error swap omniprediction error contextual swap regret sample complexity
Baselines: Garg et al. (2024) swap multicalibration bound Garg et al. (2024) swap omniprediction bound Gopalan et al. (2022) multicalibration
Builds on: Blum-Mansour reduction Online Newton Step Freedman's inequality Garg et al. (2024) contextual swap regret reduction
Closest papers by meaning
- Multigroup Fairness and Omniprediction: Separations and Equivalences (NeurIPS 2026 · similarity 0.87)
- Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.87)
- Instance-Adaptive Online Multicalibration (NeurIPS 2026 · similarity 0.86)
- Discretization-free Multicalibration through Loss Minimization over Tree Ensembles (NeurIPS 2025 · similarity 0.86)
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.85)
- Simultaneous Swap Regret Minimization via KL-Calibration (NeurIPS 2025 · 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.