Instance-Adaptive Online Multiclass Multicalibration

Abstract

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 $\tilde{\Theta }(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 $\tilde{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 $T\ge n\ge 2$, this rate is minimax optimal up to polylogarithmic factors. For a stochastic instance with a fixed conditional mean, the bound specializes to $\tilde{O}(\sqrt{nT})$, giving a square-root dependence on the horizon.

arXiv comment52 pages