Toward Simultaneously Optimal Regret in U-Calibration

Rafael Frongillo, Haipeng Luo, Nishant A. Mehta, Jon Schneider
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2503-2534, 2026.

Abstract

U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal $O(\sqrt{T})$ regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur $\Omega(\sqrt{T})$ regret instead of the optimal $O(\log T)$ regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves $\tilde O(\sqrt{T})$ regret for every bounded proper loss and $O(\log T)$ regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using \emph{self-concordant noise}. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-frongillo26a, title = {Toward Simultaneously Optimal Regret in U-Calibration}, author = {Frongillo, Rafael and Luo, Haipeng and Mehta, Nishant A. and Schneider, Jon}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {2503--2534}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/frongillo26a/frongillo26a.pdf}, url = {https://proceedings.mlr.press/v336/frongillo26a.html}, abstract = {U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal $O(\sqrt{T})$ regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur $\Omega(\sqrt{T})$ regret instead of the optimal $O(\log T)$ regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves $\tilde O(\sqrt{T})$ regret for every bounded proper loss and $O(\log T)$ regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using \emph{self-concordant noise}. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.} }
Endnote
%0 Conference Paper %T Toward Simultaneously Optimal Regret in U-Calibration %A Rafael Frongillo %A Haipeng Luo %A Nishant A. Mehta %A Jon Schneider %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-frongillo26a %I PMLR %P 2503--2534 %U https://proceedings.mlr.press/v336/frongillo26a.html %V 336 %X U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal $O(\sqrt{T})$ regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur $\Omega(\sqrt{T})$ regret instead of the optimal $O(\log T)$ regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves $\tilde O(\sqrt{T})$ regret for every bounded proper loss and $O(\log T)$ regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using \emph{self-concordant noise}. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.
APA
Frongillo, R., Luo, H., Mehta, N.A. & Schneider, J.. (2026). Toward Simultaneously Optimal Regret in U-Calibration. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:2503-2534 Available from https://proceedings.mlr.press/v336/frongillo26a.html.

Related Material