Online Conformal Prediction Beyond Feedback

Abstract:Online conformal prediction (OCP) provides theoretically principled uncertainty quantification for arbitrary black-box classifiers and non-i.i.d. data streams by constructing prediction sets that are guaranteed to contain the true label at a user-specified frequency. OCP usually updates prediction sets using feedback from previously deployed predictions. We instead study an OCP setting *beyond feedback*: on each round, the learner can *either* output a prediction set *or* query the correct label, but not both. Thus, no deployed prediction is ever evaluated directly. We reduce this problem to a partial monitoring game in which prediction actions return no observation and a separate query action reveals the label. To solve this game, we develop *OCP with queries* (OCPQ), a label-efficient forecasting algorithm designed for this beyond-feedback setting. Using an adequate reward construction, for any black-box classifier and any (non-i.i.d.) oblivious data stream of length $T$, OCPQ has $O(T^{2/3})$ expected regret and expected coverage of at least $\beta-O(T^{-1/3})$ for a user-defined $\beta$, while querying only an expected $T^{-1/3}$ fraction of rounds. This provides coverage comparable to bandit-based OCP methods while requiring no feedback from deployed predictions. Experiments on real-world datasets demonstrate the effectiveness of our approach.

Machine Learning (cs.LG)

arXiv:2608.07139 [cs.LG]

(or arXiv:2608.07139v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2608.07139 Focus to learn more arXiv-issued DOI via DataCite

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.