Abstract: We introduce a family of algorithms for online conformal prediction with coverage guarantees for both adversarial and stochastic data. In the adversarial setting, we establish the standard guarantee: over time, a pre-specified target fraction of confidence sets cover the ground truth. For stochastic data, we provide a guarantee at every time instead of just on average over time: the probability that a confidence set covers the ground truth—conditioned on past observations—converges to a pre-specified target when the conditional quantiles of the errors are a linear function of past data. Complementary to our theory, our experiments spanning over $15$ datasets suggest that the performance improvement of our methods over baselines grows with the magnitude of the data’s dependence, even when baselines are tuned on the test set. We put these findings to the test by pre-registering an experiment for electricity demand forecasting in Texas, where our algorithms achieve over a $10$\% reduction in confidence set sizes, a more than a $30$\% improvement in quantile and absolute losses with respect to the observed errors, and significant outcomes on all $78$ out of $78$ pre-registered hypotheses. We provide documentation for the pypi package implementing our algorithms here: \url{https://conformalopt.readthedocs.io/}.

Lay Summary:

Accurate predictions with reliable uncertainty estimates are crucial, but existing approaches to quantify this uncertainty rely on assumptions that are either too strong to be widely applicable, or too weak to provide robust guarantees. We developed new prediction algorithms that produce uncertainty estimates ("confidence intervals") guaranteed to capture the true outcome at a specified rate, which are adaptive to both unpredictable and highly correlated datasets. In real-world tests—such as forecasting electricity demand in Texas—our methods provided significantly improved confidence intervals compared to existing techniques. This improvement grows larger when data points are more correlated over time. To encourage practical adoption, we offer open-source tools that let anyone easily apply our methods.