Abstract
We study the problem of uncertainty quantification via prediction sets, in anonline setting where the data distribution may vary arbitrarily over time.Recent work develops online conformal prediction techniques that leverageregret minimization algorithms from the online learning literature to learnprediction sets with approximately valid coverage and small regret. However,standard regret minimization could be insufficient for handling changingenvironments, where performance guarantees may be desired not only over thefull time horizon but also in all (sub-)intervals of time. We develop newonline conformal prediction methods that minimize the strongly adaptive regret,which measures the worst-case regret over all intervals of a fixed length. Weprove that our methods achieve near-optimal strongly adaptive regret for allinterval lengths simultaneously, and approximately valid coverage. Experimentsshow that our methods consistently obtain better coverage and smallerprediction sets than existing methods on real-world tasks, such as time seriesforecasting and image classification under distribution shift.