New Method Improves Online Conformal Prediction Guarantees

This paper presents a novel online learning framework designed to enhance conformal prediction, particularly in scenarios involving distribution shifts. Traditional adaptive conformal inference (ACI) methods, while standard, exhibit several drawbacks. These include only controlling signed long-run coverage error, which can obscure persistent miscoverage, offering no guarantees on prediction-set size, and using fixed hindsight benchmarks for efficiency that become irrelevant with shifting data distributions. The proposed framework tackles these issues by simultaneously ensuring absolute, non-cancelling coverage violation control and prediction-set efficiency against a dynamically evolving benchmark. It covers fully adversarial settings using projected online gradient descent on pinball loss, deriving guarantees without strong distributional or convexity assumptions. For stochastic settings, a sliding-window quantile tracker is introduced, achieving rate-optimal performance. In covariate-dependent stochastic scenarios, a partitioned ACI algorithm tracks a function-valued oracle threshold, providing robust coverage and efficiency guarantees.