Computer Science > Machine Learning
Title:A Matching Lower Bound for Online Smooth Calibration
Abstract:We study smooth calibration error in sequential binary prediction, a measure of how far probabilistic forecasts are from being calibrated that is robust to small perturbations of the forecasts. The minimax smooth calibration error is known to lie between $\Omega(T^{1/3})$ and $O(\sqrt T)$(Qiao and Zheng, 2024), where $T$ is the number of rounds. We close this gap for both adaptive and oblivious adversaries. We construct an adaptive adversary whose outcome mean moves with the forecaster's cumulative residual, which makes compensating for past residuals costly and forces every forecaster to incur $\Omega(\sqrt T)$ expected smooth calibration error. Simulating this adversary against the forecaster's average prediction yields an oblivious adversary with the same guarantee. These lower bounds match the known $O(\sqrt T)$ upper bound up to universal constants, and are therefore minimax optimal. Our results also imply matching $\Theta(\sqrt T)$ bounds for calibration distance and lower calibration distance. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.
| Subjects: | Machine Learning (cs.LG) ; Machine Learning (stat.ML) |
|---|---|
| Cite as: | arXiv:2611.16097 [cs.LG] |
| (or arXiv:2611.16097v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.16097 arXiv-issued DOI via DataCite |
Submission history
Access Paper:
- HTML (experimental)
Additional Features
- Audio Summary
Current browse context:
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
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.