The Relationship between No-Regret Learning and Online Conformal Prediction
This work addresses theoretical gaps in online conformal prediction for researchers and practitioners needing robust uncertainty quantification in adversarial environments.
The paper investigates the relationship between no-regret learning and online conformal prediction, showing that standard regret guarantees fail for adversarial or group-conditional coverage, but a tight connection exists between threshold calibrated coverage and swap-regret, enabling group-conditional guarantees in adversarial settings.
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 perturbed 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] (arXiv:2106.00170).