A Black-Box Reduction from Regret to Multi-Level Coverage

Online Conformal Prediction (OCP) sequentially constructs prediction sets whose average empirical coverage converges to a target level over time, for arbitrary, potentially adversarial datasets. In the multi-level setting of OCP, prediction sets are produced at $d$ coverage levels at once. Prior work showed that online gradient descent with lazy isotonic projections produces sets properly nested across levels, but with a $\sqrt{d}$ dependence in the per-level coverage convergence rate. Here, we both generalize and improve prior work. First, we show that lazy isotonic projections can be safely used for the construction of multi-level online conformal prediction sets from any online learning algorithm. Then, through a black-box reduction, we show that the linearized regret of the online algorithm itself automatically gives control over both per-level calibration and distributional consistency of multi-level predictions via Fenchel duality. Finally, by using the Weighted Interval Score, the standard scoring rule for assessing multi-level interval forecasts, we prove that these projections reduce both the size of the sets and their under-coverage. We show two instantiations of our theory, $p$-norm Online Mirror Descent and coordinate-wise Universal-Portfolio, both improving the dependence on the number of levels to $\sqrt{\log d}$ for the multi-OCP problem. Experiments on stock prices, electricity demand, and synthetic streams confirm consistent gains in coverage-width trade-offs over existing baselines.