Research
Instance-Adaptive Online Multiclass Multicalibration
arXiv:2610.15954v1 Announce Type: new Abstract: We study online multiclass multicalibration over T rounds, and give an algorithm with beyond-worst-case guarantees. With n possible outcomes, forecasts
arXiv:2610.15954v1 Announce Type: new 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 widetildeTheta(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 Tge nge2, this rate is minimax optimal up to polylogarithmic factors. For a stochastic instance with a fixed conditional mean, the bound specializes to widetilde O(sqrt{nT}), giving a square-root dependence on the horizon.
Related
- Instance-Adaptive Online Multicalibration
- High-Dimensional Calibration from Swap Regret
- Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon
Source: arXiv cs.LG | 2026-10-14