Improved Online Conformal Prediction via Strongly Adaptive Online Learning

Aadyot BhatnagarHuan WangCaiming XiongYu Bai

article2023ICML110 citations

Proposes a strongly adaptive online conformal prediction framework that maintains multiple localized experts to guarantee valid coverage and near-optimal regret across all time intervals simultaneously, improving uncertainty quantification under dynamic distribution shifts.

Listen

Modern machine learning models are widely deployed in high-stakes environments where understanding prediction uncertainty is essential for managing risk and ensuring safety. A standard way to express this uncertainty is through prediction sets—such as confidence intervals for numerical forecasts or candidate label groups for classification—that aim to cover the true outcome with a user-defined target rate (such as 90%). However, standard conformal prediction methods rely on the assumption that data points are independent and identically distributed. In real-world dynamic environments, such as live time series feeds or changing visual conditions, data distributions shift unpredictably over time, causing traditional uncertainty estimates to produce invalid coverage or overly broad, uninformative intervals.

The article develops and evaluates new online conformal prediction methods designed to provide robust, localized uncertainty quantification under arbitrary distribution shifts. Specifically, it introduces Strongly Adaptive Online Conformal Prediction (SAOCP) and Scale-Free Online Gradient Descent (SF-OGD) to guarantee valid coverage and minimal prediction regret simultaneously across all continuous time windows of any duration.

To accomplish this, the authors adapt advanced online learning concepts into a sequential calibration framework. SAOCP operates as a meta-algorithm managing multiple base learners, where each expert learner handles a localized active time interval rather than the entire data history. The individual experts are instantiated using SF-OGD, an algorithm that dynamically adjusts its learning rate according to past gradient sizes. The authors evaluate this framework mathematically, establishing near-optimal regret bounds, and test it empirically across more than 5,100 real-world time series datasets (including industrial, demographic, financial, and banking data) as well as perturbed image datasets under sudden and gradual corruptions.

The findings show that SAOCP consistently matches the target coverage rate while maintaining superior local stability compared to existing methods. In time series forecasting, SAOCP achieved the lowest or second-lowest local coverage error and interval width across diverse underlying models, preventing large miscoverage spikes during sudden shifts. In image classification benchmarks, both SAOCP and SF-OGD adapted significantly faster to abrupt changes in corruption levels than baseline approaches, with SAOCP delivering equivalent or better coverage using noticeably smaller prediction set sizes.

These results demonstrate that online calibration can maintain reliable uncertainty bounds in non-stationary real-world environments without sacrificing prediction efficiency. By maintaining localized experts, systems can prevent critical short-term safety failures caused by delayed adaptation to shifts. Organizations can also avoid the trade-off of using excessively wide, uninformative prediction sets to compensate for unknown distribution drift.

Organizations deploying machine learning in streaming or changing environments should implement localized adaptive calibration, particularly direct radius tracking methods like SAOCP, to enhance system reliability. For future development, technical teams should evaluate these methods in live pilot workflows, explore extended coverage bounds under varied real-world assumptions, and determine optimal interval weighting when integrating with existing ensemble architectures.

The analysis assumes bounded prediction radii and mild distributional regularity conditions for theoretical coverage guarantees. While empirical performance remained robust across thousands of benchmarks, teams should exercise standard caution and validate operational bounds when applying these algorithms to heavily tailed or unconstrained domain outputs.

Salesforce online learning online conformal prediction strongly adaptive online learning adaptive conformal inference

arXiv: 2302.07869

Paper: Adaptive Conformal Predictions for Time Series, Margaux Zaffran et al. (2022). It introduces adaptive conformal inference and online expert aggregation over update rates for non-exchangeable time series, providing the foundational calibration paradigm that the source optimizes via strongly adaptive learning.
Paper: A tutorial on conformal prediction, Glenn Shafer et al. (2007). It provides the foundational tutorial on online conformal prediction and sequential validity guarantees upon which the source's distribution-shift extensions are built.
Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). It details the core principles and regret bounds of online convex optimization and online gradient descent that the source directly adapts for localized calibration.
Paper: Distribution-Free Predictive Inference for Regression, Jing Lei et al. (2016). It establishes distribution-free predictive inference and finite-sample coverage properties for regression that the source adapts to dynamic online streams.
Paper: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund et al. (1997). It establishes the theoretical foundations of multi-expert online learning and multiplicative update schemes utilized in the source's meta-algorithm architecture.
Paper: Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift, Yaniv Ovadia et al. (2019). It benchmarks predictive uncertainty degradation across severe dataset shifts, motivating the source's focus on robust, localized calibration.

Paper: Conformal Inference for Online Prediction with Arbitrary Distribution Shifts, Isaac Gibbs et al. (2024). It develops dynamically-tuned adaptive conformal inference to guarantee local coverage under arbitrary distribution shifts without pre-tuned parameters, directly continuing the source's line of inquiry.
Paper: Replicable Conformal Prediction, Marios Papamichalis et al. (2026). It extends conformal prediction theory to ensure replicability and stability across calibrations, advancing post-hoc calibration guarantees in dynamic deployments.

Cover for Improved Online Conformal Prediction via Strongly Adaptive Online Learning

Abstract

We study the problem of uncertainty quantification via prediction sets, in an online setting where the data distribution may vary arbitrarily over time. Recent work develops online conformal prediction techniques that leverage regret minimization algorithms from the online learning literature to learn prediction sets with approximately valid coverage and small regret. However, standard regret minimization could be insufficient for handling changing environments, where performance guarantees may be desired not only over the full time horizon but also in all (sub-)intervals of time. We develop new online conformal prediction methods that minimize the strongly adaptive regret, which measures the worst-case regret over all intervals of a fixed length. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously, and approximately valid coverage. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks, such as time series forecasting and image classification under distribution shift.

Topics

online learning

Keywords

online conformal prediction strongly adaptive online learning adaptive conformal inference adaptive regret minimization dynamic regret prediction intervals prediction sets online gradient descent

1. Introduction
1.1. Related work
2. Preliminaries
3. Strongly Adaptive Online Conformal Prediction
4. Theory
4.1. Strongly Adaptive Regret
4.2. Coverage
5. Experiments
5.1. Time Series Forecasting
5.2. Image Classification Under Distribution Shift
6. Conclusion
References
A. Basic Properties of Online Conformal Prediction Algorithms
A.1. Properties of SF-OGD
A.2. Example of 'Trivial' Algorithm with Coverage Guarantee
B. Proofs for Section 4
B.1. Proof of Proposition 4.1
B.2. Dynamic Regret for SAOCP
B.3. Proof of Theorem 4.2
B.4. Coverage of SAOCP
B.4.1. DISCUSSIONS & SF-OGD AS A SPECIAL CASE
C. Distribution-Aware Coverage Guarantees for SAOCP
D. Additional Time Series Experiments
E. Additional Experimental Details
F. Time Series Experiments with Ensemble Models
G. Image Classification on ImageNet/ImageNet-C

Knowls

Knowl 1 — Strongly Adaptive Online Conformal Prediction Algorithm
algorithm
Strongly Adaptive Online Conformal Prediction (SAOCP) is a meta-algorithm that maintains multiple online learning experts, each active over a geometrically scheduled finite time interval, to adaptively adjust the prediction set radius $\hat{s}_t$ in online conformal prediction tasks.

At each step $t \in [T]$ , a new expert $\mathcal{A}_t$ running Scale-Free Online Gradient Descent (SF-OGD) is initialized with lifetime $L(t) = g \cdot \max_{n \in \mathbb{Z}} \{2^n : t \equiv 0 \pmod{2^n}\}$ , where $g \in \mathbb{Z}_{\ge 1}$ is a lifetime multiplier. The active set of experts at time $t$ is $\text{Active}(t) = \{i \in [t] : t - L(i) < i \le t\}$ . The algorithm assigns prior probabilities $\pi_i \propto i^{-2} (1 + \lfloor \log_2 i \rfloor)^{-1} \mathbb{I}[i \in \text{Active}(t)]$ and computes betting weights $w_{t,i}$ via a coin betting scheme to construct normalized mixture weights $p_{t,i}$ . The overall radius prediction $\hat{s}_t$ is the weighted combination of the active experts' predictions. With $g = \Theta(1)$ , at most $g \lfloor \log_2 t \rfloor$ experts are active simultaneously, yielding a total time complexity of $\mathcal{O}(T \log T)$ over horizon $T$ .
Input: Target coverage level $1 - \alpha \in (0, 1)$ , maximum radius bound $D > 0$ , lifetime multiplier $g \in \mathbb{Z}_{\ge 1}$
for $t = 1, \dots, T$ do
    Initialize new expert $\mathcal{A}_t = \text{SF-OGD}(\alpha, \eta = D/\sqrt{3}, \hat{s}_1 = \hat{s}_{t-1})$ and set weight $w_{t,t} = 0$
    Compute active set $\text{Active}(t) = \{i \in [t] : t - L(i) < i \le t\}$ where $L(i) = g \cdot \max_{n \in \mathbb{Z}} \{2^n : i \equiv 0 \pmod{2^n}\}$
    Compute prior $\pi_i \propto i^{-2} (1 + \lfloor \log_2 i \rfloor)^{-1} \mathbb{I}[i \in \text{Active}(t)]$
    Compute unnormalized probabilities $\hat{p}_i = \pi_i [w_{t,i}]_+$ for all $i \in [t]$
    if $\|\hat{p}\|_1 > 0$ then
         $p_t = \hat{p} / \|\hat{p}\|_1$
    else
         $p_t = \pi$
    if $t = 1$ then
         $\hat{s}_t = 0$
    else
         $\hat{s}_t = \sum_{i \in \text{Active}(t)} p_{t,i} \hat{s}_{i,t}$
    Observe input $X_t \in \mathcal{X}$ and return prediction set $\hat{C}_t(X_t, \hat{s}_t)$
    Observe true label $Y_t \in \mathcal{Y}$ , compute true radius $S_t = \inf\{s \in \mathbb{R} : Y_t \in \hat{C}_t(X_t, s)\}$ , and loss $\ell^{(t)}(\cdot) = \ell_{1-\alpha}(S_t, \cdot)$
    for $i \in \text{Active}(t)$ do
        Update expert $\mathcal{A}_i$ with $(X_t, Y_t)$ to obtain radius $\hat{s}_{i, t+1}$
        if $w_{i,t} > 0$ then
             $g_{i,t} = \frac{1}{D} (\ell^{(t)}(\hat{s}_t) - \ell^{(t)}(\hat{s}_{i,t}))$
        else
             $g_{i,t} = \frac{1}{D} [\ell^{(t)}(\hat{s}_t) - \ell^{(t)}(\hat{s}_{i,t})]_+$
        Update expert weight $w_{i, t+1} = \frac{1}{t - i + 1} (\sum_{j=i}^t g_{i,j}) (1 + \sum_{j=i}^t w_{i,j} g_{i,j})$
Knowl 2 — Scale-Free Online Gradient Descent for Online Conformal Prediction
algorithm
Scale-Free Online Gradient Descent (SF-OGD) adaptively tunes the conformal prediction radius parameter $\hat{s}_t$ without requiring a fixed time horizon or manual learning rate schedule, scaling the effective step size by the cumulative norm of past subgradients.

At each time step $t$ , the algorithm outputs a prediction set $\hat{C}_t(X_t, \hat{s}_t)$ parameterized by radius $\hat{s}_t$ . Upon observing the true label $Y_t$ and determining whether miscoverage occurred ( $\text{err}_t = \mathbb{I}[Y_t \notin \hat{C}_t(X_t, \hat{s}_t)]$ ), the subgradient of the pinball loss $\nabla \ell^{(t)}(\hat{s}_t) = \alpha - \text{err}_t$ is evaluated. SF-OGD updates the radius according to:

$\hat{s}_{t+1} = \hat{s}_t - \eta \frac{\nabla \ell^{(t)}(\hat{s}_t)}{\sqrt{\sum_{i=1}^t \|\nabla \ell^{(i)}(\hat{s}_i)\|_2^2}} = \hat{s}_t + \eta \frac{\text{err}_t - \alpha}{\sqrt{\sum_{i=1}^t (\text{err}_i - \alpha)^2}}$
Input: Target miscoverage rate $\alpha \in (0, 1)$ , learning rate parameter $\eta > 0$ , initialization $\hat{s}_1 \in \mathbb{R}$
for $t = 1, 2, \dots$ do
    Observe input $X_t \in \mathcal{X}$
    Return prediction set $\hat{C}_t(X_t, \hat{s}_t)$
    Observe true label $Y_t \in \mathcal{Y}$ and compute $S_t = \inf\{s \in \mathbb{R} : Y_t \in \hat{C}_t(X_t, s)\}$
    Evaluate subgradient $\nabla \ell^{(t)}(\hat{s}_t) = \alpha - \mathbb{I}[Y_t \notin \hat{C}_t(X_t, \hat{s}_t)]$
    Update predicted radius $\hat{s}_{t+1} = \hat{s}_t - \eta \frac{\nabla \ell^{(t)}(\hat{s}_t)}{\sqrt{\sum_{i=1}^t \|\nabla \ell^{(i)}(\hat{s}_i)\|_2^2}}$
Knowl 3 — Strongly Adaptive Regret Bound for SAOCP
theoretical result
Let the true radius $S_t = \inf\{s \in \mathbb{R} : Y_t \in \hat{C}_t(X_t, s)\}$ be bounded such that $S_t \in [0, D]$ almost surely for all $t \in [T]$ . For any interval length $k \in [T]$ , the strongly adaptive regret of an algorithm over horizon $T$ is defined as:

$\text{SAReg}(T, k) := \max_{[\tau, \tau+k-1] \subseteq [T]} \left( \sum_{t=\tau}^{\tau+k-1} \ell_{1-\alpha}(S_t, \hat{s}_t) - \inf_{s^\star \in \mathbb{R}} \sum_{t=\tau}^{\tau+k-1} \ell_{1-\alpha}(S_t, s^\star) \right)$

where $\ell_{1-\alpha}(S_t, s) = \max\{(1 - \alpha)(S_t - s), \alpha(s - S_t)\}$ is the pinball loss.

The Strongly Adaptive Online Conformal Prediction algorithm (SAOCP), instantiated with Scale-Free Online Gradient Descent (SF-OGD) base experts with base learning rate $\eta = D/\sqrt{3}$ , achieves the strongly adaptive regret bound:

$\text{SAReg}(T, k) \le 15D \sqrt{k (\log T + 1)} = \tilde{\mathcal{O}}(D\sqrt{k})$

simultaneously for all interval lengths $k \in [T]$ . This rate is near-optimal in $k$ up to logarithmic factors in $T$ , matching the $\Omega(D\sqrt{k})$ lower bound for online convex optimization on intervals of length $k$ .
Knowl 4 — Distribution-Free Coverage Error Bound for SF-OGD
theoretical result
Suppose the true radii satisfy $S_t = \inf\{s \in \mathbb{R} : Y_t \in \hat{C}_t(X_t, s)\} \in [0, D]$ almost surely for all $t \in [T]$ , and prediction sets $\hat{C}_t(x, s)$ are nested in $s$ . Scale-Free Online Gradient Descent (SF-OGD) initialized at $\hat{s}_1 \in [0, D]$ with learning rate $\eta = \Theta(D)$ guarantees that for any time horizon $T \ge 1$ , without requiring any distributional or exchangeability assumptions on $(X_t, Y_t)$ :

$\text{CovErr}(T) := \left| \frac{1}{T} \sum_{t=1}^T \text{err}_t - \alpha \right| \le \mathcal{O}\left(\alpha^{-2} T^{-1/4} \log T\right)$

where $\text{err}_t = \mathbb{I}[Y_t \notin \hat{C}_t(X_t, \hat{s}_t)]$ indicates miscoverage at time step $t$ , and $\alpha \in (0, 1)$ is the target miscoverage level.
Knowl 5 — Distribution-Aware Interval Coverage and Quantile Estimation Bounds for SAOCP
theoretical result
Let $\mathcal{F}_t = \sigma(\{(X_i, \hat{s}_i, S_i)\}_{i=1}^{t-1}, X_t)$ denote the history up to the arrival of $X_t$ . Suppose the true radii $S_t \in [0, D]$ satisfy:
1. Density upper bound: For each $t \in [T]$ , the conditional density $f_t$ of $S_t \mid \mathcal{F}_t$ satisfies $f_t(s) \le L/D$ for all $s \in [0, D]$ for some constant $L > 0$ .
2. Density lower bound: For each $t \in [T]$ , with probability 1, there exist constants $b > 0, q \ge 2, \Delta_t > 0$ such that $f_t(s) \ge \frac{2b}{D} \left|\frac{2(s - s_t^\star)}{D}\right|^{q-2}$ for all $s \in [s_t^\star - \Delta_t, s_t^\star + \Delta_t]$ , where $s_t^\star = Q_{1-\alpha}(S_t \mid \mathcal{F}_t)$ is the $(1-\alpha)$ -conditional quantile.
For any sub-interval $I = [\tau, \tau+k-1] \subseteq [T]$ , let $\Delta_I = \min_{t \in I} \Delta_t$ and define the interval quantile variation:

$\text{Var}_I := \sum_{t=\tau}^{\tau+k-1} \mathbb{E}\left[ \left( \frac{s_t^\star}{D} - \frac{1}{k D} \sum_{i=\tau}^{\tau+k-1} \mathbb{E}[s_i^\star \mid \mathcal{F}_\tau] \right)^2 \right]$

Then SAOCP achieves an average quantile estimation error of:

$\frac{1}{|I|} \sum_{t \in I} \mathbb{E}\left[ \left| \frac{\hat{s}_t - s_t^\star}{D} \right| \right] \le \mathcal{O}\left( \frac{1}{b^{1/q}} \frac{D}{\Delta_I} \left( \frac{\log T}{|I|} \right)^{1/(2q)} \right) + \mathcal{O}\left( \frac{L^{1/q}}{b^{1/q}} \frac{D}{\Delta_I} \left( \frac{\text{Var}_I}{|I|} \right)^{1/q} \right)$

and an average interval miscoverage error of:

$\frac{1}{|I|} \sum_{t \in I} \left| \mathbb{P}(Y_t \in \hat{C}_t(X_t)) - (1 - \alpha) \right| \le \mathcal{O}\left( \frac{L}{b^{1/q}} \frac{D}{\Delta_I} \left( \frac{\log T}{|I|} \right)^{1/(2q)} \right) + \mathcal{O}\left( \frac{L^{1 + 1/q}}{b^{1/q}} \frac{D}{\Delta_I} \left( \frac{\text{Var}_I}{|I|} \right)^{1/q} \right)$
Knowl 6 — Dynamic Regret Bound for SAOCP
theoretical result
For true radii $S_t \in [0, D]$ almost surely, SAOCP achieves a worst-case dynamic regret bound on any sub-interval $[\tau, \tau+k-1] \subseteq [T]$ of length $k \in [T]$ with respect to the pinball loss $\ell^{(t)}(\cdot) = \ell_{1-\alpha}(S_t, \cdot)$ :

$\sum_{t=\tau}^{\tau+k-1} \ell^{(t)}(\hat{s}_t) - \min_{s^\star_{\tau:\tau+k-1}} \sum_{t=\tau}^{\tau+k-1} \ell^{(t)}(s^\star_t) = \sum_{t=\tau}^{\tau+k-1} \left[ \ell^{(t)}(\hat{s}_t) - \ell^{(t)}(S_t) \right] \le \tilde{\mathcal{O}}\left( D \left[ V_{[\tau, \tau+k-1]}^{1/3} k^{2/3} + \sqrt{k} \right] \right)$

where $V_{[\tau, \tau+k-1]} := \sum_{t=\tau+1}^{\tau+k-1} |S_t - S_{t-1}|$ is the path length of the true radii sequence over the sub-interval. On an average per-step basis over $[\tau, \tau+k-1]$ , this yields:

$\frac{1}{k} \sum_{t=\tau}^{\tau+k-1} \left[ \ell^{(t)}(\hat{s}_t) - \ell^{(t)}(S_t) \right] \le \tilde{\mathcal{O}}\left( D \left[ \left(\frac{V_{[\tau, \tau+k-1]}}{k}\right)^{1/3} + \frac{1}{\sqrt{k}} \right] \right)$

simultaneously for all interval lengths $k$ and starting steps $\tau$ .
Knowl 7 — Distribution-Free Coverage Error Bound for Randomized SAOCP
theoretical result
Consider a randomized version of SAOCP where at each time step $t$ , the predicted radius is set by sampling an expert index $i \sim p_t \in \Delta([t])$ and outputting $\hat{s}_t = \hat{s}_{t,i}$ . The expected miscoverage error at step $t$ is $\widetilde{\text{err}}_t := \sum_{i=1}^t p_{t,i} \mathbb{I}[\hat{s}_{t,i} < S_t]$ .

For any $T \ge 1$ , the empirical miscoverage error satisfies:

$\left| \frac{1}{T} \sum_{t=1}^T \widetilde{\text{err}}_t - \alpha \right| \le \mathcal{O}\left( \inf_{\beta \in (1/2, 1)} \left( T^{1/2-\beta} + T^{\beta-1} S_\beta(T) \right) \right)$

where $S_\beta(T) := 1 + \sum_{j=2}^{\lceil T^{1-\beta} \rceil} \max_{t \in G_j} \sum_{i=1}^t \left| p_{t,i} - p_{t_{j-1},i} \frac{G_{i:t_{j-1}}^i}{G_{i:t}^i} \right|$ , $\{G_j\}_{j=1}^{\lceil T^{1-\beta} \rceil}$ is an even partition of $[T]$ into contiguous groups of size at most $\lceil T^\beta \rceil$ , and $G_{i:t}^i := \sqrt{\sum_{\tau=i}^t (\text{err}_{\tau,i} - \alpha)^2}$ denotes the cumulative subgradient norm experienced by expert $\mathcal{A}_i$ up to step $t$ .
Knowl 8 — Online Conformal Prediction Parameterization and Quantile Loss Formulation
definition
In online conformal prediction, examples $(X_t, Y_t) \in \mathcal{X} \times \mathcal{Y}$ arrive sequentially for $t = 1, \dots, T$ . Before observing $Y_t$ , the learner predicts a set $\hat{C}_t(X_t) \subset \mathcal{Y}$ from a parameterized family of nested sets $\mathcal{C}_t = \{\hat{C}_t(x, s)\}_{x \in \mathcal{X}, s \in \mathbb{R}}$ , where $s \le s'$ implies $\hat{C}_t(x, s) \subseteq \hat{C}_t(x, s')$ .

The true radius $S_t$ is the minimal parameter value that covers the observed label:

$S_t := \inf\{s \in \mathbb{R} : Y_t \in \hat{C}_t(X_t, s)\}$

Given target coverage level $1 - \alpha$ , radius prediction is framed as minimizing the $(1-\alpha)$ -quantile loss (pinball loss):

$\ell^{(t)}(\hat{s}) = \ell_{1-\alpha}(S_t, \hat{s}) := \max\{(1 - \alpha)(S_t - \hat{s}), \alpha(\hat{s} - S_t)\}$

with subgradient:

$\nabla \ell^{(t)}(\hat{s}_t) = \alpha - \mathbb{I}[\hat{s}_t < S_t] = \alpha - \mathbb{I}[Y_t \notin \hat{C}_t(X_t, \hat{s}_t)] = \alpha - \text{err}_t$

where $\text{err}_t \in \{0, 1\}$ indicates whether a coverage error occurred at time step $t$ .

Knowl 9 — Empirical Comparison on Time Series Forecasting Benchmarks

data/table

The empirical performance of online conformal prediction algorithms was evaluated on multi-horizon time series forecasting across M4 Competition datasets (Hourly with 414 time series, Daily with 4227 time series) at target coverage $1-\alpha = 0.90$ . The metrics include overall empirical coverage, median prediction interval width, worst-case local coverage error $\text{LCE}_k = \max_{[\tau, \tau+k-1] \subseteq [1, T]} |\alpha - \frac{1}{k}\sum_{t=\tau}^{\tau+k-1} \text{err}_t|$ , and strongly adaptive regret $\text{SAReg}_k$ , all evaluated with window length $k = 20$ .

	M4 Hourly (LGBM Base Predictor, MAE = 0.06)				M4 Daily (LGBM Base Predictor, MAE = 0.13)
Method	Coverage	Width	$\text{LCE}_{20}$	$\text{SAReg}_{20}$	Coverage	Width	$\text{LCE}_{20}$	$\text{SAReg}_{20}$
SCP	.844	.127	.252	.017	.769	.184	.466	.031
NExCP	.875	.134	.197	.013	.818	.183	.420	.015
FACI	.866	.113	.180	.009	.846	.169	.308	.008
SF-OGD	.889	.138	.154	.011	.873	.173	.246	.011
FACI-S	.883	.128	.163	.010	.875	.169	.240	.010
SAOCP	.882	.121	.143	.009	.869	.162	.213	.007

SAOCP consistently achieves empirical global coverage within the acceptable range $(0.85, 0.95)$ while obtaining the lowest worst-case local coverage error $\text{LCE}_{20}$ and strongly adaptive regret $\text{SAReg}_{20}$ across base predictors (LGBM, ARIMA, Prophet). Methods predicting $\hat{s}_{t+1}$ directly in radius space (SAOCP, SF-OGD, FACI-S) maintain valid coverage when base predictors have higher MAE, whereas methods predicting score quantiles (SCP, NExCP, FACI) experience significant coverage drops on M4 Daily.

Knowl 10 — Local Coverage and Prediction Set Adaptability Under Image Distribution Shifts
empirical result
When evaluated on image classification under structured distribution shifts using a pre-trained ResNet-50 classifier on TinyImageNet-C and ImageNet-C across 15 corruption types with severity levels 0 through 5, SAOCP and SF-OGD maintain local coverage closest to the 90% nominal target ( $1-\alpha = 0.9$ ) across both sudden shifts (alternating between severity 0 and 5 every 500 steps) and gradual shifts (increasing severity from 0 to 5).

Prediction sets are constructed via regularized Adaptive Prediction Sets: $\hat{C}_t(X_t) = \{y : S_t(X_t, y) \le \hat{s}_t\}$ , where $S_t(x, y) = \lambda \sqrt{[k_y - k_{\text{reg}}]_+} + U_t \hat{f}_y(x) + \sum_{i=1}^{k_y - 1} \hat{f}_{\pi(i)}(x)$ with $U_t \sim \text{Unif}[0, 1]$ . Under sudden shifts on TinyImageNet-C, SAOCP achieves a worst-case local coverage error $\text{LCE}_{100} = 0.06$ , compared to 0.07 for SF-OGD, 0.11 for FACI-S, 0.16 for FACI, 0.13 for NExCP, and 0.58 for SCP. SAOCP adapts set sizes rapidly at transition points without lagging behind changes in oracle set size.

Coverage note — Omitted material includes intermediate technical lemmas from the appendix (such as bounded iterate lemmas, power-mean inequalities, and detailed coin betting derivation steps) that exist solely to prove the primary theorems, as well as extended table repetitions across additional datasets (M4 Weekly, NN5 Daily, EnbPI ensembles) whose quantitative findings mirror those captured in the representative time series and image classification knowls.

References

1.Angelopoulos, A. N. and Bates, S. A gentle introduction to conformal prediction and distribution-free uncertainty quantification, 2021. URL https://arxiv.org/abs/2107.07511.
2.Angelopoulos, A. N., Bates, S., Candes, E. J., Jordan, ` M. I., and Lei, L. Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint arXiv:2110.01052, 2021a.
3.Angelopoulos, A. N., Bates, S., Jordan, M., and Malik, J. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021b. URL https://openreview.net/forum?id=eNdiU_DbM9.
4.Angelopoulos, A. N., Bates, S., Fisch, A., Lei, L., and Schuster, T. Conformal risk control. arXiv preprint arXiv:2208.02814, 2022a.
5.Angelopoulos, A. N., Kohli, A. P., Bates, S., Jordan, M., Malik, J., Alshaabi, T., Upadhyayula, S., and Romano, Y. Image-to-image regression with distribution-free uncertainty quantification and applications in imaging. In International Conference on Machine Learning, pp. 717–730. PMLR, 2022b.
6.Bai, Y., Mei, S., Wang, H., Zhou, Y., and Xiong, C. Efficient and differentiable conformal prediction with general function classes. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=Ht85_jyihxp.
7.Barber, R. F., Candes, E. J., Ramdas, A., and Tibshi- ` rani, R. J. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486 – 507, 2021. doi: 10.1214/20-AOS1965. URL https://doi.org/10.1214/20-AOS1965.
8.Barber, R. F., Candes, E. J., Ramdas, A., and Tibshirani, ` R. J. Conformal prediction beyond exchangeability, 2022. URL https://arxiv.org/abs/2202.13415.
9.Bates, S., Angelopoulos, A., Lei, L., Malik, J., and Jordan, M. Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1–34, 2021.
10.Ben Taieb, S., Bontempi, G., Atiya, A. F., and Sorjamaa, A. A review and comparison of strategies for multi-step ahead time series forecasting based on the nn5 forecasting competition. Expert Systems with Applications, 39(8):7067–7083, 2012. ISSN 0957-4174. doi: https://doi.org/10.1016/j.eswa.2012.01.039. URL https://www.sciencedirect.com/science/article/pii/S0957417412000528.
11.Besbes, O., Gur, Y., and Zeevi, A. Non-stationary stochastic optimization. Operations research, 63(5):1227–1244, 2015.
12.Bhatnagar, A., Kassianik, P., Liu, C., Lan, T., Yang, W., Cassius, R., Sahoo, D., Arpit, D., Subramanian, S., Woo, G., Saha, A., Jagota, A. K., Gopalakrishnan, G., Singh, M., Krithika, K. C., Maddineni, S., Cho, D., Zong, B., Zhou, Y., Xiong, C., Savarese, S., Hoi, S., and Wang, H. Merlion: A machine learning library for time series. 2021. URL https://arxiv.org/abs/2109.09265.
13.Candes, E. J., Lei, L., and Ren, Z. Conformalized survival ` analysis, 2021. URL https://arxiv.org/abs/2103.09763.
14.Cauchois, M., Gupta, S., Ali, A., and Duchi, J. C. Robust validation: Confident predictions even when distributions shift, 2020. URL https://arxiv.org/abs/2008.04267.
15.Cauchois, M., Gupta, S., and Duchi, J. C. Knowing what you know: Valid and validated confidence sets in multiclass and multilabel prediction. J. Mach. Learn. Res., 22 (1), jul 2022. ISSN 1532-4435.
16.Chernozhukov, V., Wuthrich, K., and Yinchu, Z. Exact ¨ and robust conformal inference methods for predictive machine learning with dependent data. In Bubeck, S., Perchet, V., and Rigollet, P. (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 732–749. PMLR, 06–09 Jul 2018. URL https://proceedings.mlr.press/v75/chernozhukov18a.html.
17.Daniely, A., Gonen, A., and Shalev-Shwartz, S. Strongly adaptive online learning. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1405–1411, Lille, France, 07–09 Jul 2015. PMLR. URL https://proceedings.mlr.press/v37/daniely15.html.
18.Dashevskiy, M. and Luo, Z. Network traffic demand prediction with confidence. In IEEE GLOBECOM 2008 - 2008 IEEE Global Telecommunications Conference, pp. 1–5, 2008. doi: 10.1109/GLOCOM.2008.ECP.284.
19.Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248–255. Ieee, 2009.
20.Elsayed, S., Thyssens, D., Rashed, A., Jomaa, H. S., and Schmidt-Thieme, L. Do we really need deep learning models for time series forecasting?, 2021. URL https://arxiv.org/abs/2101.02118.
21.Fannjiang, C., Bates, S., Angelopoulos, A., Listgarten, J., and Jordan, M. I. Conformal prediction for the design problem. arXiv preprint arXiv:2202.03613, 2022.
22.Feldman, S., Ringel, L., Bates, S., and Romano, Y. Risk control for online learning models, 2022. URL https://arxiv.org/abs/2205.09095.
23.Gibbs, I. and Candes, E. Adaptive conformal inference ` under distribution shift. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https://openreview.net/forum?id=6vaActvpcp3.
24.Gibbs, I. and Candes, E. Conformal inference for online ` prediction with arbitrary distribution shifts, 2022. URL https://arxiv.org/abs/2208.08401.
25.Gupta, C., Kuchibhotla, A. K., and Ramdas, A. K. Nested conformal prediction and quantile out-of-bag ensemble methods. arXiv preprint arXiv:1910.10562, 2019.
26.Hazan, E. Introduction to Online Convex Optimization. MIT Press, Cambridge, MA, USA, 2022. ISBN 9780262046985.
27.He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770–778, 2016. doi: 10.1109/CVPR.2016.90.
28.Hendrycks, D. and Dietterich, T. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=HJz6tiCqYm.
29.Hendrycks, D., Mazeika, M., Wilson, D., and Gimpel, K. Using trusted data to train deep networks on labels corrupted by severe noise. Advances in neural information processing systems, 31, 2018.
30.Jun, K.-S., Orabona, F., Wright, S., and Willett, R. Improved Strongly Adaptive Online Learning using Coin Betting. In Singh, A. and Zhu, J. (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 943–951. PMLR, 20–22 Apr 2017. URL https://proceedings.mlr.press/v54/jun17a.html.
31.Kath, C. and Ziel, F. Conformal prediction interval estimation and applications to day-ahead and intraday power markets. International Journal of Forecasting, 37(2):777–799, 2021. ISSN 0169-2070. doi: https://doi.org/10.1016/j.ijforecast.2020.09.006. URL https://www.sciencedirect.com/science/article/pii/S0169207020301473.
32.Koenker, R. and Bassett Jr, G. Regression quantiles. Econometrica: journal of the Econometric Society, pp. 33–50, 1978.
33.Kwiatkowski, D., Phillips, P. C., Schmidt, P., and Shin, Y. Testing the null hypothesis of stationarity against the alternative of a unit root: How sure are we that economic time series have a unit root? Journal of Econometrics, 54(1):159–178, 1992. ISSN 0304-4076. doi: https://doi.org/10.1016/0304-4076(92)90104-Y. URL https://www.sciencedirect.com/science/article/pii/030440769290104Y.
34.Le, Y. and Yang, X. S. Tiny imagenet visual recognition challenge. 2015.
35.Lei, J. and Wasserman, L. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(1):71–96, 2014. doi: https://doi.org/10.1111/rssb.12021. URL https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/rssb.12021.
36.Lei, J., Robins, J., and Wasserman, L. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):278–287, 2013. doi: 10.1080/01621459.2012.751873. URL https://doi.org/10.1080/01621459.2012.751873. PMID: 25237208.
37.Makridakis, S., Spiliotis, E., and Assimakopoulos, V. The m4 competition: Results, findings, conclusion and way forward. International Journal of Forecasting, 34(4): 802–808, 2018.
38.Orabona, F. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019.
39.Orabona, F. and Pal, D. Coin betting and parameter-free on- ´ line learning. Advances in Neural Information Processing Systems, 29, 2016.
40.Orabona, F. and Pal, D. Scale-free online learning. ´ Theoretical Computer Science, 716:50–69, 2018. ISSN 0304-3975. doi: https://doi.org/10.1016/j.tcs.2017.11.021. URL https://www.sciencedirect.com/science/article/pii/S0304397517308514. Special Issue on ALT 2015.
41.Papadopoulos, H. Inductive conformal prediction: Theory and application to neural networks. In Fritzsche, P. (ed.), Tools in Artificial Intelligence, chapter 18. IntechOpen, Rijeka, 2008. doi: 10.5772/6078. URL https://doi.org/10.5772/6078.
42.Park, S., Bastani, O., Matni, N., and Lee, I. Pac confidence sets for deep neural networks via calibrated prediction. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=BJxVI04YvB.
43.Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024–8035. Curran Associates, Inc., 2019.
44.Pearce, T., Brintrup, A., Zaki, M., and Neely, A. High-quality prediction intervals for deep learning: A distribution-free, ensembled approach. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4075–4084. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/pearce18a.html.
45.Podkopaev, A. and Ramdas, A. Distribution-free uncertainty quantification for classification under label shift. In de Campos, C. and Maathuis, M. H. (eds.), Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 844–853. PMLR, 27–30 Jul 2021. URL https://proceedings.mlr.press/v161/podkopaev21a.html.
46.Romano, Y., Patterson, E., and Candes, E. Conformalized quantile regression. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., and ´ Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper/2019/file/5103c3584b063c431bd1268e9b5e76fb-Paper.pdf.
47.Romano, Y., Sesia, M., and Candes, E. J. Classification ` with valid and adaptive coverage. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
48.Shafer, G. and Vovk, V. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
49.Sousa, M., Tome, A. M., and Moreira, J. A general ´ framework for multi-step ahead adaptive conformal heteroscedastic time series forecasting, 2022. URL https://arxiv.org/abs/2207.14219.
50.Stankeviciute, K., M. Alaa, A., and van der Schaar, M. Conformal time-series forecasting. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 6216–6228. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper/2021/file/312f1ba2a72318edaaa995a67835fad5-Paper.pdf.
51.Steinwart, I. and Christmann, A. Estimating conditional quantiles with the help of the pinball loss. Bernoulli, 17 (1):211 – 225, 2011. doi: 10.3150/10-BEJ267. URL https://doi.org/10.3150/10-BEJ267.
52.Stutz, D., Dvijotham, K. D., Cemgil, A. T., and Doucet, A. Learning optimal conformal classifiers. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=t8O-4LKFVx.
53.Sun, S. and Yu, R. Copula conformal prediction for multi-step time series forecasting, 2022. URL https://arxiv.org/abs/2212.03281.
54.Taylor, S. J. and Letham, B. Forecasting at scale. PeerJ Preprints, 5(e3190v2), Sept 2017. doi: 10.7287/peerj.preprints.3190v2.
55.Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ramdas, A. Conformal prediction under covariate shift. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, ´ F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper/2019/file/8fb21ee7a2207526da55a679f0332de2-Paper.pdf.
56.Vovk, V. Conditional validity of inductive conformal predictors. In Hoi, S. C. H. and Buntine, W. (eds.), Proceedings of the Asian Conference on Machine Learning, volume 25 of Proceedings of Machine Learning Research, pp. 475–490, Singapore Management University, Singapore, 04–06 Nov 2012. PMLR. URL https://proceedings.mlr.press/v25/vovk12.html.
57.Vovk, V., Gammerman, A., and Saunders, C. Machinelearning applications of algorithmic randomness. In Proceedings of the Sixteenth International Conference on Machine Learning, ICML ’99, pp. 444–453, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606122.
58.Vovk, V., Gammerman, A., and Shafer, G. Algorithmic Learning in a Random World. Springer-Verlag, Berlin, Heidelberg, 2005. ISBN 0387001522.
59.Vovk, V., Nouretdinov, I., Manokhin, V., and Gammerman, A. Cross-conformal predictive distributions. In Gammerman, A., Vovk, V., Luo, Z., Smirnov, E., and Peeters, R. (eds.), Proceedings of the Seventh Workshop on Conformal and Probabilistic Prediction and Applications, volume 91 of Proceedings of Machine Learning Research, pp. 37–51. PMLR, 11–13 Jun 2018. URL https://proceedings.mlr.press/v91/vovk18a.html.
60.Wisniewski, W., Lindsay, D., and Lindsay, S. Application of conformal prediction interval estimations to market makers’ net positions. In Gammerman, A., Vovk, V., Luo, Z., Smirnov, E., and Cherubin, G. (eds.), Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications, volume 128 of Proceedings of Machine Learning Research, pp. 285–301. PMLR, 09–11 Sep 2020. URL https://proceedings.mlr.press/v128/wisniewski20a.html.
61.Xu, C. and Xie, Y. Conformal prediction interval for dynamic time-series. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11559–11569. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/xu21h.html.
62.Yang, Y. and Kuchibhotla, A. K. Finite-sample efficient conformal prediction, 2021. URL https://arxiv.org/abs/2104.13871.
63.Yang, Y., Kuchibhotla, A. K., and Tchetgen, E. T. Doubly robust calibration of prediction sets under covariate shift, 2022. URL https://arxiv.org/abs/2203.01761.
64.Zaffran, M., Feron, O., Goude, Y., Josse, J., and Dieuleveut, A. Adaptive conformal predictions for time series. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 25834–25866. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/zaffran22a.html.
65.Zhang, L., Yang, T., rong jin, and Zhou, Z.-H. Dynamic regret of strongly adaptive methods. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5882–5891. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/zhang18o.html.
66.Zhao, P. and Zhang, L. Improved analysis for dynamic regret of strongly convex and smooth functions. In Learning for Dynamics and Control, pp. 48–59. PMLR, 2021.
67.Zhao, P., Xie, Y.-F., Zhang, L., and Zhou, Z.-H. Efficient methods for non-stationary online learning. Advances in Neural Information Processing Systems, 35:11573–11585, 2022.
68.Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML’03, pp. 928–935. AAAI Press, 2003. ISBN 1577351894.

Citation

MLA

Bhatnagar, A., et al. “Improved Online Conformal Prediction via Strongly Adaptive Online Learning”. International Conference on Machine Learning, vol. 202, 2023, pp. 2337–63, https://proceedings.mlr.press/v202/bhatnagar23a.html.

APA

Bhatnagar, A., Wang, H., Xiong, C., & Bai, Y. (2023). Improved Online Conformal Prediction via Strongly Adaptive Online Learning. International Conference on Machine Learning, 202, 2337–2363. https://proceedings.mlr.press/v202/bhatnagar23a.html

Chicago

Bhatnagar, A., H. Wang, C. Xiong, and Y. Bai. 2023. “Improved Online Conformal Prediction via Strongly Adaptive Online Learning”. International Conference on Machine Learning 202: 2337–63. https://proceedings.mlr.press/v202/bhatnagar23a.html.

Harvard

Bhatnagar, A. et al. (2023) “Improved Online Conformal Prediction via Strongly Adaptive Online Learning”, International Conference on Machine Learning. PMLR, pp. 2337–2363. Available at: https://proceedings.mlr.press/v202/bhatnagar23a.html.

Vancouver

1. Bhatnagar A, Wang H, Xiong C, Bai Y (2023) Improved Online Conformal Prediction via Strongly Adaptive Online Learning. In: International Conference on Machine Learning. PMLR, pp 2337–2363

BibTeX

@InProceedings{pmlr-v202-bhatnagar23a,
  title = 	 {Improved Online Conformal Prediction via Strongly Adaptive Online Learning},
  author =       {Bhatnagar, Aadyot and Wang, Huan and Xiong, Caiming and Bai, Yu},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {2337--2363},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/bhatnagar23a/bhatnagar23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/bhatnagar23a.html},
  abstract = 	 {We study the problem of uncertainty quantification via prediction sets, in an online setting where the data distribution may vary arbitrarily over time. Recent work develops online conformal prediction techniques that leverage regret minimization algorithms from the online learning literature to learn prediction sets with approximately valid coverage and small regret. However, standard regret minimization is insufficient for handling changing environments, where performance guarantees may be desired not only over the full time horizon but also in all (sub-)intervals of time. We develop new online conformal prediction methods that minimize the strongly adaptive regret, which measures the worst-case regret over all intervals of a fixed length. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously, and approximately valid coverage. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks such as time series forecasting and image classification under distribution shift.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Improved Online Conformal Prediction via Strongly Adaptive Online Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Strongly Adaptive Online Conformal Prediction Algorithm

Knowl 2 — Scale-Free Online Gradient Descent for Online Conformal Prediction

Knowl 3 — Strongly Adaptive Regret Bound for SAOCP

Knowl 4 — Distribution-Free Coverage Error Bound for SF-OGD

Knowl 5 — Distribution-Aware Interval Coverage and Quantile Estimation Bounds for SAOCP

Knowl 6 — Dynamic Regret Bound for SAOCP

Knowl 7 — Distribution-Free Coverage Error Bound for Randomized SAOCP

Knowl 8 — Online Conformal Prediction Parameterization and Quantile Loss Formulation

Knowl 9 — Empirical Comparison on Time Series Forecasting Benchmarks

Knowl 10 — Local Coverage and Prediction Set Adaptability Under Image Distribution Shifts

References

Citation

BibTeX

Access the Paper