Improved Online Conformal Prediction via Strongly Adaptive Online Learning

Aadyot Bhatnagar, Huan Wang, Caiming Xiong, Yu Bai
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:2337-2363, 2023.

Abstract

We study the problem of uncertainty quantification via prediction sets, in an online setting where the data distribution may vary arbitrarily over time. Recent work develops online conformal prediction techniques that leverage regret minimization algorithms from the online learning literature to learn prediction sets with approximately valid coverage and small regret. However, standard regret minimization is insufficient for handling changing environments, where performance guarantees may be desired not only over the full time horizon but also in all (sub-)intervals of time. We develop new online conformal prediction methods that minimize the strongly adaptive regret, which measures the worst-case regret over all intervals of a fixed length. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously, and approximately valid coverage. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks such as time series forecasting and image classification under distribution shift.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-bhatnagar23a, title = {Improved Online Conformal Prediction via Strongly Adaptive Online Learning}, author = {Bhatnagar, Aadyot and Wang, Huan and Xiong, Caiming and Bai, Yu}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {2337--2363}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/bhatnagar23a/bhatnagar23a.pdf}, url = {https://proceedings.mlr.press/v202/bhatnagar23a.html}, abstract = {We study the problem of uncertainty quantification via prediction sets, in an online setting where the data distribution may vary arbitrarily over time. Recent work develops online conformal prediction techniques that leverage regret minimization algorithms from the online learning literature to learn prediction sets with approximately valid coverage and small regret. However, standard regret minimization is insufficient for handling changing environments, where performance guarantees may be desired not only over the full time horizon but also in all (sub-)intervals of time. We develop new online conformal prediction methods that minimize the strongly adaptive regret, which measures the worst-case regret over all intervals of a fixed length. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously, and approximately valid coverage. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks such as time series forecasting and image classification under distribution shift.} }
Endnote
%0 Conference Paper %T Improved Online Conformal Prediction via Strongly Adaptive Online Learning %A Aadyot Bhatnagar %A Huan Wang %A Caiming Xiong %A Yu Bai %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-bhatnagar23a %I PMLR %P 2337--2363 %U https://proceedings.mlr.press/v202/bhatnagar23a.html %V 202 %X We study the problem of uncertainty quantification via prediction sets, in an online setting where the data distribution may vary arbitrarily over time. Recent work develops online conformal prediction techniques that leverage regret minimization algorithms from the online learning literature to learn prediction sets with approximately valid coverage and small regret. However, standard regret minimization is insufficient for handling changing environments, where performance guarantees may be desired not only over the full time horizon but also in all (sub-)intervals of time. We develop new online conformal prediction methods that minimize the strongly adaptive regret, which measures the worst-case regret over all intervals of a fixed length. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously, and approximately valid coverage. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks such as time series forecasting and image classification under distribution shift.
APA
Bhatnagar, A., Wang, H., Xiong, C. & Bai, Y.. (2023). Improved Online Conformal Prediction via Strongly Adaptive Online Learning. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:2337-2363 Available from https://proceedings.mlr.press/v202/bhatnagar23a.html.

Related Material