Instance-Adaptive Online Multiclass Multicalibration
We study online multiclass multicalibration over $T$ rounds, and give an algorithm with beyond-worst-case guarantees. With $n$ possible outcomes, forecasts lie in a simplex of dimension $d=n-1$. In the worst case, cumulative $\ell_1$ multicalibration error scales with $\widetildeΘ(T^{(d+1)/(d+2)})$, which becomes untenable once $d$ exceeds a small constant. Our algorithm adapts to the geometry of the realized sequence: if the sequence of adversarially selected outcome means lies in an affine subspace of dimension $s$, it obtains error $\widetilde O(n^{1/(s+2)}T^{(s+1)/(s+2)})$ with high probability. The algorithm adapts to this structure without knowing the subspace or its dimension. For ...
| Authors | Zhiming Huang, Jamie Morgenstern, Aaron Roth et al. |
|---|---|
| Primary category | cs.LG |
| Published | 11 October 2026 |
| Last updated at source | 11 October 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 14 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.