The Relationship Between No-Regret Learning and Online Conformal Prediction

Ramya Ramalingam, Shayan Kiyani, Aaron Roth
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:51060-51078, 2025.

Abstract

Existing algorithms for online conformal prediction—guaranteeing marginal coverage in adversarial settings—are variants of online gradient descent (OGD), but their analyses of worst-case coverage do not follow from the regret guarantee of OGD. What is the relationship between no-regret learning and online conformal prediction? We observe that although standard regret guarantees imply marginal coverage in i.i.d. settings, this connection fails as soon as we either move to adversarial environments or ask for group conditional coverage. On the other hand, we show a tight connection between threshold calibrated coverage and swap-regret in adversarial settings, which extends to group-conditional (multi-valid) coverage. We also show that algorithms in the follow the regularized leader family of no regret learning algorithms (which includes online gradient descent) can be used to give group-conditional coverage guarantees in adversarial settings for arbitrary grouping functions. Via this connection we analyze and conduct experiments using a multi-group generalization of the ACI algorithm of Gibbs & Candes (2021).

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-ramalingam25a, title = {The Relationship Between No-Regret Learning and Online Conformal Prediction}, author = {Ramalingam, Ramya and Kiyani, Shayan and Roth, Aaron}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {51060--51078}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/ramalingam25a/ramalingam25a.pdf}, url = {https://proceedings.mlr.press/v267/ramalingam25a.html}, abstract = {Existing algorithms for online conformal prediction—guaranteeing marginal coverage in adversarial settings—are variants of online gradient descent (OGD), but their analyses of worst-case coverage do not follow from the regret guarantee of OGD. What is the relationship between no-regret learning and online conformal prediction? We observe that although standard regret guarantees imply marginal coverage in i.i.d. settings, this connection fails as soon as we either move to adversarial environments or ask for group conditional coverage. On the other hand, we show a tight connection between threshold calibrated coverage and swap-regret in adversarial settings, which extends to group-conditional (multi-valid) coverage. We also show that algorithms in the follow the regularized leader family of no regret learning algorithms (which includes online gradient descent) can be used to give group-conditional coverage guarantees in adversarial settings for arbitrary grouping functions. Via this connection we analyze and conduct experiments using a multi-group generalization of the ACI algorithm of Gibbs & Candes (2021).} }
Endnote
%0 Conference Paper %T The Relationship Between No-Regret Learning and Online Conformal Prediction %A Ramya Ramalingam %A Shayan Kiyani %A Aaron Roth %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-ramalingam25a %I PMLR %P 51060--51078 %U https://proceedings.mlr.press/v267/ramalingam25a.html %V 267 %X Existing algorithms for online conformal prediction—guaranteeing marginal coverage in adversarial settings—are variants of online gradient descent (OGD), but their analyses of worst-case coverage do not follow from the regret guarantee of OGD. What is the relationship between no-regret learning and online conformal prediction? We observe that although standard regret guarantees imply marginal coverage in i.i.d. settings, this connection fails as soon as we either move to adversarial environments or ask for group conditional coverage. On the other hand, we show a tight connection between threshold calibrated coverage and swap-regret in adversarial settings, which extends to group-conditional (multi-valid) coverage. We also show that algorithms in the follow the regularized leader family of no regret learning algorithms (which includes online gradient descent) can be used to give group-conditional coverage guarantees in adversarial settings for arbitrary grouping functions. Via this connection we analyze and conduct experiments using a multi-group generalization of the ACI algorithm of Gibbs & Candes (2021).
APA
Ramalingam, R., Kiyani, S. & Roth, A.. (2025). The Relationship Between No-Regret Learning and Online Conformal Prediction. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:51060-51078 Available from https://proceedings.mlr.press/v267/ramalingam25a.html.

Related Material