The Relationship Between No-Regret Learning and Online Conformal Prediction

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).

Some learning algorithms are designed to work even in unpredictable environments by learning from mistakes over time to limit a quantity called regret - a technique known as no-regret learning. We noticed that some of these algorithms, although not originally designed for it, also perform well on a seemingly different task: generating prediction sets that reliably include the correct answer.In this paper, we explore when and why this connection holds. Our first finding is a close relationship between two properties: strong coverage guarantees for prediction sets, and a strong no-regret condition called swap regret. This means any algorithm that satisfies one will automatically satisfy the other. We then study a broad class of algorithms and show they simultaneously achieve weaker versions of both properties - but for different reasons, and without a tight link between them.Finally, we use these insights to develop a straightforward, easy-to-implement algorithm that produces prediction sets that are not only reliable overall, but also within any subgroups the user specifies - such as demographic categories of interest.