Online Conformal Prediction via Universal Portfolio Algorithms
This addresses the need for robust, tunable prediction intervals in online settings, offering a practical improvement over existing methods.
The paper tackles the problem of online conformal prediction (OCP) by developing a parameter-free method called UP-OCP that achieves strong finite-time bounds on miscoverage, even for polynomially growing predictions, and experiments show it delivers consistently better size/coverage trade-offs than prior baselines.
Online conformal prediction (OCP) seeks prediction intervals that achieve long-run $1-α$ coverage for arbitrary (possibly adversarial) data streams, while remaining as informative as possible. Existing OCP methods often require manual learning-rate tuning to work well, and may also require algorithm-specific analyses. Here, we develop a general regret-to-coverage theory for interval-valued OCP based on the $(1-α)$-pinball loss. Our first contribution is to identify \emph{linearized regret} as a key notion, showing that controlling it implies coverage bounds for any online algorithm. This relies on a black-box reduction that depends only on the Fenchel conjugate of an upper bound on the linearized regret. Building on this theory, we propose UP-OCP, a parameter-free method for OCP, via a reduction to a two-asset portfolio selection problem, leveraging universal portfolio algorithms. We show strong finite-time bounds on the miscoverage of UP-OCP, even for polynomially growing predictions. Extensive experiments support that UP-OCP delivers consistently better size/coverage trade-offs than prior online conformal baselines.