aiqbench analysis
This arXiv paper gives an online learning algorithm for multiclass multicalibration whose error adapts to the hidden structure of the outcome sequence. If the outcome means lie near a low-dimensional affine subspace, the error bound improves, and the authors claim it is minimax optimal up to polylog factors. Readers working on calibrated forecasting or uncertainty quantification should note that the guarantees are theoretical and that the stochastic special case, $\widetilde O(\sqrt{nT})$, is the most practically relevant result.
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 lie in a simplex of dimension $d=n-1$. In the worst case, cumulative $\ell_1$ multicalibration error scales with $\widetilde\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 $\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 $T\ge n\ge2$, 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.
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 $\widetilde\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 $\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 $T\ge n\ge2$, 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.
Machine Learning (cs.LG)
arXiv:2610.15954 [cs.LG]
(or arXiv:2610.15954v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.15954 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 222 words
Related coverage
DSevolve: Enabling Real-Time Adaptive Scheduling on Dynamic Flexible Job Shop with LLM-Evolved Heuristic Portfolios
arXiv · Jul 29, 2026
An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $\Phi$-Regret Minimization
arXiv · Aug 5, 2026
ANCHOR: Error-Controlled Adaptive Numerical Correction for Neural Operator Time Marching
arXiv · Jun 16, 2026
Provably Efficient Offline-to-Online Value Adaptation with General Function Approximation
arXiv · Oct 9, 2026