Authors: Zhiming Huang, Jamie Morgenstern, Aaron Roth, Claire Jie Zhang
Organizations: Paul G. Allen School of Computer Science and Engineering, University of Washington · Amazon · Department of Computer and Information Sciences, University of Pennsylvania
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 ℓ1 multicalibration error scales with Θ(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 O(n1/(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≥n≥2, this rate is minimax optimal up to polylogarithmic factors. For a stochastic instance with a fixed conditional mean, the bound specializes to O(nT), giving a square-root dependence on the horizon.
Figures & tables
Figure 1: Blocks for one (g,a) pair, where Ej,r denotes the r -th block at level j in chronological order. Completed blocks E0,1,…,E0,4 form E1,1 . The open block E1,2 has received the summaries of E0,5,E0,6 . The block E0,7 is still collecting observations and has not been forwarded. Arrows add both weight and outcome sum.
Figure 2: Selecting pieces for one group–source pair. Both parents are complete, with comparators qi=qE1,i satisfying H(qi,zE1,i)≤w1 . Select E1,1 because q1 was available throughout it; replace E1,2 by its children because q2 was unavailable at its start. The blocks with thick outlines partition the observations. This selection is used only in the proof.
Paul G. Allen School of Computer Science and Engineering, University of Washington · Department of Computer and Information Sciences, University of Pennsylvania