Optimization-based Online Conformal Prediction for Multi-step Forecasting

Abstract

Conformal prediction (CP) provides distribution-free coverage guarantees, making it well suited for uncertainty quantification in time series forecasting. However, existing methods often struggle with multi-step settings: they either calibrate horizons independently---ignoring temporal correlations---or enforce strict simultaneous coverage, resulting in overly conservative intervals. In this work, we propose O${}^2$CP: Optimization-Based Online Conformal Prediction, a framework that augments a broad family of online CP methods with cross-horizon optimization while preserving their long-term coverage guarantees. We first characterize this family of methods, showing that long-term coverage is preserved as long as, at each forecast horizon, the selected control variable remains within an admissible set around the method's nominal output. Building on this result, O${}^2$CP uses a two-layer design: the first layer constructs these admissible sets from the underlying online CP updates, and the second performs constrained optimization across horizons within them, jointly modeling the cross-horizon distributions to minimize a user-specified objective. Extensive experiments on real-world datasets---including autonomous driving, climate forecasting, and public health---demonstrate that O${}^2$CP consistently outperforms state-of-the-art baselines, achieving target coverage with significantly sharper prediction intervals and reduced regret over long horizons.