Tuo (Terence) Liu

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 √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 √(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.

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 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.

Dual averaging and gradient descent with their stochastic variants stand as the two canonical recipe books for first-order optimization: Every modern variant can be viewed as a descendant of one or the other. In the convex regime, these algorithms have been deeply studied, and we know that they are essentially equivalent in terms of theoretical guarantees. On the other hand, in the non-convex setting, the situation is drastically different: While we know that SGD can minimize the gradient of non-convex smooth functions, no finite-time complexity guarantee for Stochastic Dual Averaging (SDA) was known in the same setting. In this paper, we close this gap by a reduction that views SDA as SGD applied to a sequence of implicitly regularized objectives. We show that a tuned SDA exhibits a rate of convergence O(1/T + σ log T/√T), similar to that of SGD under the same assumptions. To our best knowledge, this is the first complete convergence theory for dual averaging on non-convex smooth stochastic problems without restrictive assumptions, closing a long-standing open problem in the field. Beyond the base algorithm, we also discuss ADA-DA, a variant that marries SDA with AdaGrad’s auto-scaling, which achieves the same rate without requiring knowledge of the noise variance.