Exploring the Noise Robustness of Online Conformal Prediction
Authors: HuaJun Xi
Kangdao Liu
Hao Zeng
Wenguang Sun
Hongxin Wei
Venue: NeurIPS 2025 poster ()
Keywords: Trustworthy Machine Learning
Conformal Prediction
Uncertainty Quantification
Primary area: general_machine_learning

Abstract: Conformal prediction is an emerging technique for uncertainty quantification that constructs prediction sets guaranteed to contain the true label with a predefined probability. 
Recent work develops online conformal prediction methods that adaptively construct prediction sets to accommodate distribution shifts. 
However, existing algorithms typically assume *perfect label accuracy* which rarely holds in practice. 
In this work, we investigate the robustness of online conformal prediction under uniform label noise with a known noise rate. 
We show that label noise causes a persistent gap between the actual mis-coverage rate and the desired rate $\alpha$, leading to either overestimated or underestimated coverage guarantees. 
To address this issue, we propose a novel loss function *robust pinball loss*, which provides an unbiased estimate of clean pinball loss without requiring ground-truth labels.
Theoretically, we demonstrate that robust pinball loss enables online conformal prediction to eliminate the coverage gap under uniform label noise, achieving a convergence rate of $\mathcal{O}(T^{-1/2})$ for both empirical and expected coverage errors (i.e., absolute deviation of the empirical and expected mis-coverage rate from the target level $\alpha$).
This loss offers a general solution to the uniform label noise, and is complementary to existing online conformal prediction methods.
Extensive experiments demonstrate that the proposed loss enhances the noise robustness of various online conformal prediction methods by achieving a precise coverage guarantee.

Exploring the Noise Robustness of Online Conformal Prediction
Huajun Xi', Kangdao Liu!?, Hao Zeng', Wenguang Sun', Hongxin Wei
'Dppartment of Statisties and Data Science, Southern University of Science and Technology *Department of Computer and Information Science, University of Macau Center for Data Science, Zhejiang University
Abstract
Conformal prediction is emerging technique for uncertainty quantification that constructs prediction sets guaranteed to contain the true label with a predefined probability. Recent work develops online conformal prediction methods that adaptively construct prediction sets to accommodate distribution shifts. However, existing algorithms typically assume perfect label accuracy which rarely holds practice. In this work, we investigate the robustness of online conformal prediction under uniform label noise with known noise rate. We show that label noise causes persistent gap between the actual mis-coverage rate and the desired rate a, leading to either overestimated or underestimated coverage guarantees. To address this issue, we propose a novel loss function robusi pinball loss, which provides an unbiased estimate of clean pinball loss without requiring ground-truth labels. Theoretically, we demonstrate that robust pinball loss enables online conformal prediction climinate the coverage gap under uniform label noise, achieving a convergence rate of 1 for both empirical and expected coverage errors (i.e., absolute deviation of the empirical and expected mis-coverage rate from the target level a). This loss offers a general solution to the uniform label noise, and is complementary to existing online conformal prediction methods. Extensive experiments demonstrate that robust pinball loss enhances the noise robustness of various online conformal prediction methods by achieving precise coverage guarantee and improved efficiency.
1 Introduction
in high-stakes domains, such as autonomous driving [1] and medical diagnostics [2]. It is crucial to ensure the reliability of model predictions these contexts, as wrong predictions can result serious consequences. While various techniques have been developed for uncertainty estimation, including confidence calibration [3] and Bayesian neural networks [4], they typically lack rigorous theoretical guarantees. Conformal prediction addresses this limitation by establishing a systematic framework construct prediction sets with provable coverage guarantee [5, 6, 7, 8J. Notably, this framework requires no parametric assumptions about the data distribution and can be applied any black-box predictor, which makes a powerful technique for uncertainty quantification.
Machine learning techniques are revolutionizing
Recent research extends conformal prediction to online setting where the data arrives in a sequential order [9, 10. 11, 12, 13. 14]. These methods provably achieve the desired coverage property under arbitrary distributional changes. However, previous studies typically assume perfect label accuracy, an assumption that seldom holds true practice due the common occurrence of noisy labels in online learning [15, 16, 17]. Recent work [18] proves that online conformal prediction can achieve
"oorrespondence to: Hongxin Wei <weihxesustech.commm edu. en>
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

conservative coverage guarantee under uniform label noise, leading to unnecessarily large prediction sets. However, their analysis relies on a strong distributional assumption of non-conformity score and cannot quantify the specific deviation of coverage guarantees. These limitations motivate us to establish a general theoretical framework for this problem and develop a noise-robust algorithm that maintains precise coverage guarantees while producing small prediction sets.
In this work, we present general theoretical framework for analyzing how uniform label noise affects the performance of standard online conformal prediction, i.c., adaptive conformal inference (dubbed ACI) [9]. Notably, our theoretical results are independent of the distributional assumptions on the non-conte con-oonfrry scores made in the previous work [18]. In particular, we demonstrate that label noise causes a persistent gap between the actual mis-coverage rate and the desired rate a, with higher noise rates resulting in larger gaps. This gap can lead to either overestimated or underestimated coverage guarantees, which depend on the size of the prediction sets (see Proposition 3.1).
To address this challenge, we propose a novel loss function robust pinball loss, which provides an unbiased estimate of clean pinball loss value without requiring access ground-truth labels. Specifically, we construct the robust pinball loss as weighted combination of the pinball loss computed with respect to noisy scores and the pinball loss with scores of all classes. We prove that this loss is equivalent to the pinball loss under clean labels in expectation. Theoretically, we demonstrate that robust pinball loss enables ACI to eliminate the coverage gap under uniform label noise. It achieves a convergence rate of ((T-1/2) for both empirical and expected coverage errors (i.e., absolute deviation of the empirical and expected mis-coverage rate from the target level a). Notably, our robust pinball loss offers general solution to the uniform label noise, and is complementary to existing online conformal prediction methods.
To verify the effectiveness of the robust pinball loss, we conduct extensive experiments on CIFAR- 100 [19] and ImageNet [20] with synthetic uniform label noise. In particular, we integrate the proposed loss into ACI with constant [9] and dynamic learning rates [12], and strongly adaptive online conformal prediction [11]. Empirical results show that the robust pinball loss enhances the noise robustness of online conformal prediction by eliminating the coverage gap caused by the label noise. Thus, these methods achieve both long-run coverage and local coverage rate that are close to the target 1 a, and improved prediction set efficiency. For example, = 0.1, noise rate 0.15 and dynamic learning rate, ACI with the standard pinball loss deviates from the target coverage level of 0.9, exhibiting a coverage gap of 8.372% and an average set size of 171.2. In contrast, ACI equipped with the robust pinball loss achieves a negligible coverage gap of 0.183% and prediction set size of 13.10. In summary, our method consistently enhances the noise robustness of various online conformal prediction methods by achieving a precise coverage guarantee and improved efficiency.
ImageNet with error rate
We summarize our contributions as follows:
We present a general theoretical framework for analyzing the effect of uniform label noise the coverage of online conformal prediction. Our theoretical results are independent of the distributional assumptions made in the previous work [18).
To address the issue of label noise, we propose a novel loss function robius pinball loss that enhances the noise robustness of online conformal prediction. This loss is complementary to online conformal prediction algorithms and can be scamlessly integrated with these methods.
We empirically validate that our method can be applied to various online conformal predic- tion methods and non-conformity score functions. It is straightforward to implement and does not require sophisticated changes to the framework of online conformal prediction.
2 Preliminary
Online conformal prediction. We study the problem of generating prediction sets in online clas- sification where the data arrives in a sequential order [9, 12]. Formally, we consider a sequence of data points (X,,
N which are sampled from joint distribution Pxy over the in- put space X C Rdd, and the label space y {1...., K). In online conformal prediction, the goal is to construct prediction sets (x,),, t E N+. that provides precise coverage guarantee: limy-+t0 $ ΣT= 1 (Y, & Cx(X.)) = a, where (0, 1) denotes user-specified error rate.
2

---

At each time step t, we construct a prediction set Cx(X,) by
(X2) = (y E E S(X,, x)
(I)
where it a data-driven threshold, and S X' x y + R denotes a non-conformity score function that measures the deviation between a data sample and the training data. For example, given pre-trained classifier f: X + I the LAC score [21] is defined as S(x, Y) 1) = (x)X), where (x) = (J()) denotes the softmax probability of instance X for class Y. and a is the softmax function. For notation shorthand, we use S, to denote the random variable S S(x, Y,) and use Styy to denote S(X,, y) for given class y Y. Following previous work [12, 22]. we will assume that the non-conformity score function is bounded, and the threshold is specifically initialized:
Assumption 2.1. The score is bounded by S(,, +) E [0, 1]. Assumption 2.2. The threshold initialized by E [0,
In online conformal prediction, a representative method is adaptive conformal inference (ACI) [9], which updates the threshold fz with pinball loss:
4-a (T. s) = a(T - s)1{r 2 s)
+ + a1- -)) S S}},
where r denotes a threshold and 8 is non-conformity score. As the label Y; of X, is observed after model prediction, the threshold is then updated via online gradient descent:
i++1 = ft V=,41a(fe, S,) = ft + (1 (Y, & Cx(X))] a)
where (T, denotes the gradient of pinball loss w.r.t the threshold т, and v) > is the learning rate. The optimization will increase the threshold the prediction set Co (X,) fails encompass the label Y, resulting in more conservative predictions in future instances (and vice versa).
We use the empirical coverage error and the expected coverage error to evaluate the coverage performance. The empirical coverage error measures the absolute deviation the mis-coverage rate from the target level a, while the expected coverage quantifies the absolute deviation in expectation. In particular, for any E N we define
T
T Σ P(Y & (G())-
Σ 1 & C(X)) a EXEIT(T) (T) = T
T
Uniform Label noise. In this paper, we focus on the issue of noisy labels in online learning, a common occurrence in the real world. This is primarily due to the dynamic nature of real-time data streams and the potential for human eтror or sensor malfunctions during label collection. Let (X,, Y,) be the data sequence with label noise, and S, S(X,, Y2) be the noisy non-conformity score. In this work, we focus on the setting of uniform label noise [18, 23], i.c., the correct label is replaced by label that is randomly sampled from the K classes with fixed probability E (0, 1):
Y Y= Y, (U 2 c) + (U Sc
where U uniformly distributed over [0, 1]. and uniformly sampled from the set of classes y. We assume the probability (i.e., the noise rate) is known, in alignment with prior works [18, 23, 24]. This assumption is practical as the noise rate can be estimated from historical data [25, 26, 27].
Recent work [18] investigates the noise robustness of online conformal prediction under uniform label noise, with a strong distributional assumption. Their analysis demonstrates that noisy labels will lead to conservative long-ru -un coverage guarantee, with the assumption that noisy score distribution
stochastically dominates the clean score distribution, i.c., IP { < $ < P (S < s} Vs E F. The
distributional assumption too strong to ensure valid coverage under general cases. Moreover, their analysis fails to quantify the specific deviation of coverage guarantees. These limitations motivate us to establish a general theoretical framework for this problem and develop a noise-robust. algorithm for online conformal prediction.
3 The impact of label noise on online conformal prediction
In this section, we theoretically analyze the impacts of uniform label noise on ACI [9]. In this case, the threshold f; is updated by
4+ 5. 17 V V (fr, St),
(3)
3

---

where S₁ is the noisy non-conformity score. As shown in Eq. (3), the essence of online conformal prediction is to update the threshold 7, with the gradient of pinball loss. However, the gradient estimates can be biased if the observed labels are corrupted. Formally, with high probability:
Vi,41a Si) + (f, St).
This bias in gradient estimation can result in two potential consequences: conformal predictors may either fail to maintain the desired coverage or suffer from reduced efficiency (i.e., generating large prediction sets). We formalize these consequences in the following proposition:
Proposition 3.1. Consider online conformal prediction under uniform label noise with noise rate E (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (3), then for any d E (0, 1) and T E N+ the following bound holds with probability at least
T
1 T
(Y, & C(X)) 2
A
B
c
E t=1
(1
1 (1-a)
* EIIG((001).
T
1
T
1=1
where
2 A
2oo (!)
44)
1 ( + 1 1
and B=
-
Interpretation.
The proof is provided in Appendix E. In Proposition 3.1, evaluate the long-run
mis-coverage rate using 7 Ei (Y, C.(X))) Our analysis shows that label noise introduces coverage gap of
T
1 T Σ (1 (1-a) 1=1
6
K - EIIC((I)I)
between the actual mis-coverage rate and desired mis-coverage rate a (the term 4 + B will diminish
VT T
and eventually approach zero, as T increases). In particular, the effect of label noise on the coverage guarantee can manifest in two distinct scenarios, depending on the prediction set size:
When the prediction sets are small such that E [X,)())) S K(1 - a), label noise can
result in over-coverage of prediction sets: + Eie (Y & C((x)) S a. In this scenario, a higher noise rate e results in a larger coverage gap.
When the prediction sets are large such that E (x.)l 2 ((1 label noise causes under-coverage of prediction sets. This situation generally occurs only when the model significantly underperforms on the task, which is uncommon practical applications (See details in Appendix B.3)).
Empirical verification. To verify our theoretical result, we compare the performance of ACI under different noise rates. In particular, we compute the long-run coverage, defined as Cov(T') T +Σ 1 (Y, E (X.)), under noise rate (0.05, 0. 0.15), with ResNet18 model CIFAR- 100 and ImageNet datasets. We employ LAC score [21] to generate prediction sets with error rate 0.1, and noisy labels update the threshold with constant learning rate 17 0.05. The experimental results in Figure validate our theoretical analysis: label noise introduces discrepancies between the actual and target coverage rates 1 a, with higher noise rates resulting in more pronounced coverage gap.
Overall, our results show that label noise significantly impacts the coverage guarantee of online conformal prediction. The size of the prediction set determines whether coverage inflated or deflated, and the noise rate controls how much coverage is changed. In the following, we introduce robust pinball loss, which addresses the issue of label noise.
4 Method
4.1 Robust pinball loss
Our theoretical analysis establishes that biased gradient estimates arising from label noise can significantly impact the coverage properties of online conformal prediction. Therefore, the key

---

0.99
0.99
Long-run Coverage
0.93
Long-run
0.90
0.90
0.87
noise rate 0.05
0.87
noise rate - 0.05
noise rate 0.1
noise rate 0.1
1-4
0.81
1-2
4000
6000
10000
20000
30000
40000
Time
(a) CIFAR-100
(b) ImageNet
Figure Performance ACI [9] with a constant learning rate 77 0.05 under different noise rates, using & on CIFAR-100 and ImageNet datasets. The results validate that label noise introduces coverage gap, with higher noise rates resulting in more pronouneed gap.
challenge of the noisy setting lies in how to obtain unbiased gradient estimates without requiring ground-truth labels. In this work, we propose novel loss function robust pinball loss, which provides unbiased estimate the clean pinball loss value without requiring access ground -ouuh labels. We begin by developing the intuition behind how to approximate the clean pinball loss under uniform label noise.
Consider a data sample (X,Y) with noisy label Y, we denote the clean non-conformity score as S = S(X,)) Y), the noisy score Š = S(X, Y), and the score for an arbitrary class y E ) as Sy S(X,y). Under uniform label noise with noise rate (0, 1), the distributions of these
scores have the following relationship: P {S S s} - { | x(ंo E ( S s). for an arbitrary number R. We formally establish this equation in Lemma F.1 with rigorous proof. This correlation motivates the following approximation:
K Σ
{ K(1-6) I-E
1 (S 5
1s, s}.
y=1
The above decomposition suggests that the clean pinball loss can be approximated by replacing its indicator function with the above expression. Inspired by this, we propose the robust pinball loss as:
K
( K(1
1 1-
Σ (T,
The following theoretical properties demonstrate how this loss function mitigates label noise bias: Proposition 4.1. The robust pinball loss defined in Eq. (4) satisfies the following two properties:
S, (1)Es (T- S)] Eg,s, (, 8,1,,k
E2)Es (T. = Es.sy V ( (5
The proof can found in Appendix E.2. In Proposition 4.1, the first property ensures that robust pinball loss matches the expected value of the true pinball loss, while the second guarantees that the gradients of both losses have the same expectation. These properties establish that updating the threshold with robust pinball loss is equivalent to updating with clean pinball loss in expectation.
Interpretation.
In summary, Proposition 4.1 establishes the validity of our robust pinball loss in expectation. Notably, our robust pinball loss offers a general solution to the uniform label noise, and is complementary to existing online conformal prediction methods. In the following sections, loss to ACI with constant [9] and dynamic learning rates [12]. We will show that by updating the threshold with the proposed loss, ACI climinates the coverage gap caused by the label noise.
apply the robust pinball
5

---

4.2 Convergence with constant learning rate
We now analyze the convergence the coverage rate of ACI under uniform label noise with constant learning rate schedule [9]. In particular, we update the threshold of ACI with respect to the robust pinball loss:
To+1= 7
Vi, Vi.11a (Fes St, (
K 11 (S.. I fr) (1 - a)].
= fi - 1 1 3 21 (1 (1-
+1
K(1 c) y=1
(5)
For notation shorthand, denote:
VV 4-a] Es, V S.).
E
V 1 = S.. V St, (S
1
We first present the results for expected coverage
Proposition 4.2. Under the same assumptions in Proposition 3.1, when updating the threshold according to Eq. (5), then for any ò E (0, 1) and T N+, the following bound holds with probability at least 5:
(x) I 1og(2/5)
6 1 (--a a 1-c) T -
-
VT
Proof Sketch.
The proof (in Appendix E.3) relies on the following decomposition:
T
T
T
T
ExEr((T) =
V
<
+ h-a
1=1
(8)
Part (a) converges to zero in probability at rate ((T-1/2) by the Azuma-Hoeffding inequality, and part (b) achieves a convergence rate of O(T-1) following standard online conformal prediction theory. Combining the two parts establishes the desired upper bound.
Building on Proposition 4.2, we now provide an upper bound for the empirical coverage error:
Proposition 4.3. Under the same assumptions in Proposition 3.1, when updating the threshold according to Eq. (5), then for any E (0, 1) and E N+, the following bound holds with probability at least 8:
- <
1 VT
(--++I-) T
EmErr(T)
2 2
+
1 1
Proof Sketch. The proof (detailed in Appendix E.4) employs a similar decomposition:
EmEr((T) Σ V V
<
Σ V
Σ E [
+
Σ [
(a)
The analysis shows that both terms achieve OTT-1/2) convergence: part (a) through the
Azuma-Hoeffäle inequality, and part (b) via Proposition 4.2.
Remark 4.4. It is worth noting that method achieves O(T-1/2) convergence rate for empirical coverage еттоr even in the absence of noise (i.c., = 0), which is slightly slower than the O(T-1) rate achieved by standard online conformal prediction theory [9. 12]. This because our analysis relies martingale- based concentration to handle label noise, leading to the OTT-1/2) rate.
4.3 Convergence with dynamic learning rate
Recent work [12) highlights a limitation of constant learning rates: while coverage holds on average over time, the instantaneous coverage rate Cov(ft) IP (S < ft) would exhibit substantial temporal

---

variability (see Proposition 1 in [12]). Thus, they extend ACI to dynamic learning rate schedule where T can change over time for updating the threshold. In this section, we apply the robust pinball loss to the dynamic learning rate schedule. Specifically, we update the threshold by:
Fo+1 "/e Va, 11 (Tes St, (St.))==1)
K Σ y=1
= ft - -
1 1 S. s S - -(1 (1-a) + K(1 - c)
[S f/) (1 11-aj) a)]
(6)
For the convergence of coverage rate, theoretical results show that, under dynamic learning rate, NR-OCP achieves convergence rates of EmCovVErr(T) = O(T-1/2) and ExCovErr(T))
O(T-1/2). The proofs are presented in Appendix E.S and E.6.
Proposition 4.5. Under the same assumptions in Proposition 3.1, when updating the threshold according to Eq. (6), then for any E (0, and T N+, the following bound holds with probability at least 6:
ExErr(T) S log(2/0) 1-c
[ max
1 1
Σ
T
n
+
+
T ISAST-1
The
VT
1
Proposition 4.6. Under the same assumptions Proposition 3.1, when updating the threshold
according to Eg. (6), then for any å E (0, and T E Nt, the following bound holds with probability at least 6:
EmErr(T) < 2-6 E c
4
(
" 1
T Σ
2og
VT +
max 1515T-1
1/
T
In Proposition 4.5 and 4.6, establish that for any sequence of learning rates that satisfies the condition Σ 1n - /T as T - +00, both expected and empirical coverage errors asymptotically vanish with a convergence rate of (TT-)/)). Therefore, by applying our method, the long-term coverage rate would approach the desired target level of -
Online learning theory (see Theorem 2.13 of [28]) established that ACI achieves regret bound:
T (fr, St) - min Σ (T, = O
T
Reg(T) = Σ 4n
with optimally chosen ne. which serves as helpful measure alongside coverage [11]. We provide regret analysis for our method in Appendix B.I. In addition, we formally establish the convergence of ft towards the global minima Appendix B.2 by extending the standard convergence analysis of stochastic gradient descent (see Theorem 5.3 in [29]).
5
Experiments
5.1 Experimental setups
Datasets and setup. We evaluate the performance of NR-OCP under uniform label noise. The experiments include both constant 0.05 and dynamic learning rates = 1/1-/2+t with 0.1, following prior work [12]). We use CIFAR-100 [19] and ImageNet [20] datasets with synthetic label noise. On ImageNet, use four pre-trained classifiers from Visch [30] ResNet18, ResNet50 [31], 1enseNet121 [32] and VGG 16 [33]. On CIFAR- 100, we train these models for 200 epochs using SGD with momentum of 0.9, weight decay of 0.0005, and batch size of 128. We set the initial learning rate as 0. and reduce by a factor of 5 at 60, 120 and 160 epochs.
Conformal prediction algorithms. We integrate the robust pinball loss into ACI with constant [9] and dynamic learning rates [12], and strongly adaptive online conformal prediction [11]. We apply LAC [21], APS [34], RAPS [35] and SAPS [36] to generate prediction sets. A detailed description of these non-conformity scores provided in Appendix B.4. In addition, we use error
rates {0.1, 0.05} in experiments.
7

---

Long-run Coverage
3.45
0.82
0.2
3.9
0.79
2004
0.70
4000
0.2
168
Time
t
Time
Time E
Local Coverage
3.31
6.5
0.4
0.65
0.87
0.9
1093
#003
8500
13800
0.70
2200
4000
4000
5000
10600
022
2009
4200
6900
30300
Time t
Time E
Time
(a) ACI-constant
(b) ACI-dynamic
(c) SAOCP
Figure 2: Long-run coverage and local coverage performance of various methods under uniform noisy labels with noise rate e = 0.05. We apply robust pinball loss to ACI with (a) constant [9] and (b) dynamic learning rate [12], and (c) SAOCP [11]. We employ LAC to generate prediction sets with a = 0.1, using ResNet18 on CIFARI00. "Baseline" and "Clean" denote the online conformal prediction with standard pinball loss, using noisy and clean labels.
Metries. We employ four evaluation metrics: long-run coveruge (Cov), local coverage (LocalCov), coverage gap (CovGap) and prediction set size (Size). We use long-ru coverage and local coverage to present the dynamics of coverage during the optimization. Formally, for any T E N
T-L
Cov(T) = T Σ I
LocalCov (T)
Σ t=T
Σ
(VEGG())))
I
In particular, long-run coverage measures the coverage rate the first T 'ime steps, while local coverage is over an interval with length L. In the experiments, we employ length of = 200. Besides, the coverage gap and the prediction set size computed over the full test set, indicating the final performance of the online conformal prediction method. Formally, given a test dataset Itest-
CovGap
1
E 1 E E - - ao) Size
Σ (c((x)))
Trast
[rest]
1EI
tEIxes
Small prediction sets preferred they can provide precise predictions, thereby enabling accurate human decision-making in real-world scenarios [37].
5.2 Main results
Robust pinball loss enhances the noise robustness of existing online conformal prediction methods. figure 2, we apply robust pinball loss ACI with constant [9] and dynamic learning rate [12], and SAOCP [11]. We evaluate these methods with long-run coverage and local coverage. We use the LAC score and a ResNet18 model on CIFAR 100, with error rate a = 0.1 and noise rate 0.05. The results demonstrate that the proposed robust pinball loss enables these methods to achieve long-run coverage and local coverage close to the target coverage rate of a. summary, the empirical results highlight the versatility of our robust pinball loss, demonstrating its potential to enhance the noise robustness across diverse algorithms.
Robust pinball loss is effective across various settings. In Table 1, we incorporate robust pinball loss into ACI with constant [9] and dynamic learning rate [12], under different noise rate e, error rate a and non-conformity scores. We evaluate the prediction sets with coverage gap and prediction set size. Due space constraints, we report the average performance across four non-conformity score functions. The performance on each score function is provided in Appendix B.5, The results

---

Table 1: Average performance of different methods under uniform noisy labels across 4 score functions, using ResNet18. The performance on each score function is provided in Appendix B.5. "Baseline" denotes the ACI with standard pinball loss. We include two learning rate schedules: constant learning rate y 0.05 and dynamic learning rates n 1/tl/2+o where 0.1. "!" indicates smaller values are better and Bold numbers are superior results.
CIFAR100
ImageNet
I.R Schedule Error rate Method
Cov
Size 4
CovGap((*) J
Size
a: 0.1 a 0.05
a
0.1
a 0.05
0 0.1
0.05
a
0.1
0.05
Baseline
3,942
2.867
11.93
30.66
4.163
3.289
101.0
231.7
0.05
Ours 0.386
0.183
7.786
16.54
0.084
0.272
67.37
143.3
Constant
Baseline
7.139
3.753
21.81
46.93
7.509
4.068
178.4
389.7
0.1
Ours 0.270
0.428
8.815
17.96
0.095
0,194
81.87
157.3
Baseline
8.032
4.147
36.95
59,92
8,566
4.348
318.0
513.2
0.15
Ours 0.520
0.395
9.396
19.41
0.198
0.144
90.52
163.4
0.05
Baseline
4.106
2.780
6.527
21.97
4.498
2.584
31.15
128.1
Ours 0.170
0.658
2.958
10.95
0.120
0,242
7.502
47.41
Dynamic
0.1
Baseline
7.414
3.733
18.18
37.18
7.249
3,595
99.54
214.9
Ours 0.414
0.217
3.361
12.01
0.079
0.321
10.34
67.03
Baseline
8.403
4,211
29.41
48.24
8.372
4.127
171.2
274.9
0.15
Ours
0.214
0.195
4.065
12.98
0.183
0,256
13.10
78.64
show that robust pinball loss allows ACI to eliminate the coverage gap, achieving precise coverage guarantees while significantly improving the long-run efficiency of prediction sets, For example, on ImageNet with error rate a = 0.1, noise rate = 0.15 and dynamic learning rate, ACI employing the robust pinball loss achieves negligible coverage gap of 183% and prediction set size of 13. 10. We report additional results on various models in Appendix B.6. Overall, the robust pinball loss is effective across different settings, including various label noise, error rate, confooooormtty score functions, and model architectures.
In real-world scenarios where the noise rate could be unknown, it can be estimated from historical data [25, 26, 27]. In Appendix C, we leverage an existing approach to estimate the noise rate. Then, we employ this estimated noise rate our method. We show that in this circumstance, the robust pinball loss can improve the noise robustness of online conformal prediction algorithms.
6 Conclusion
In this work, we investigate the robustness of online conformal prediction under uniform label noise with a known noise rate, in both constant and dynamic learning rate schedules. Our theoretical analysis shows that the presence of label noise causes a deviation between the actual and desired mis-coverage rate a, with higher noise rates resulting in larger gaps. To address this issue, we propose novel loss function robust pinball loss, which provides loss without requiring ground-truth labels. We theoretically establish that this loss equivalent to the pinball loss under clean labels in expectation. In our theoretical analysis, we show that robust pinball loss enables online conformal prediction to climinate the coverage gap caused by the label noise, achieving a convergence rate of (T221/2) for both empirical and expected coverage errors under uniform label noise. This loss offers a general solution to the uniform label noise, and is complementary to existing online conformal prediction methods. Extensive experiments demonstrate that the proposed loss enhances the noise robustness of various online conformal prediction methods by eliminating the coverage gap caused by the label noise. Notably, our loss function is effective across different label noise, error rate, non-conformity score functions, and model architectures.
unbiased estimate of clean pinball
Linitation. As the first step to explore the label noise issue online conformal prediction, our analysis and method are limited to the setting of uniform noisy labels with known noise rate. We believe it will be interesting to develop online conformal prediction algorithms that are robust to various types of label noise with fewer assumptions in the future.

---

Acknowledgements
This research is supported by the Shenzhen Fundamental Research Program (Grant No. (1112022080700188000000 We gratefully acknowledge the support of the Center for Compu- tational Science and Engineering at the Southern University of Science and Technology for our research.
References
[1] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp. Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint arXiv:1604.072 2016.
[2] Rich Caruana, Yin Lou, Johannes Gehrke, Paul Koch, Marc Sturm, and Noemie Elhadad. Intelligible models for healthcare: Predicting pncumonia risk and hospital 30-day readmission. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015.
[3] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. Doina Precup and Yee Whye Tch, editors, Proceedings of the 34th International Conference Machine Learning, 2017.
[4] Ralph C Smith. Uncertainty quantification: theory, implementation, and applications. Siam, 2013.
[5] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer, 2005.
[6] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 2008.
[7] Vineeth Balasubramanian, Shen-Shyang Ho, and Vladimir Vovk. Conformal prediction for reliable machine learning: theory, adaptations and applications. Newnes, 2014.
[8] Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends@ in Machine Learning, 2023.
[9] Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 2021.
[10] Shai Feldman, Liran Ringel, Stephen Bates, and Yaniv Romano. Achieving risk control in online learning settings. Transactions on Machine Learning Research, 2023.
[11] Aadyot Bhatnagar, Huan Wang, Caiming Xiong, and Yu Bai. Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learning, 2023.
[12] Anastasios Nikolas Angelopoulos, Rina Barber, and Stephen Bates. Online conformal prediction with decaying step sizes. In Forty-first International Conference on Machine Learning, 2024.
[13] Isaac Gibbs and Emmanuel J Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research. 2024.
[14] Erfan Hajihashemi and Yanning Shen. Multi-model ensemble conformal prediction in dynamic environments. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[15) Shai DaviD Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In The 22nd Conference on Learning Theory, 2009.
[16] Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems, 2013.
10

---

[17] Changlong Wu, Ananth Grama, and Wojciech Szpankowski. Information -heeoeti limits of online classification with noisy labels. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[18] Bat-Sheva Einbinder, Shai Feldman, Stephen Bates, Anastasios N Angelopoulos, Asaf Gendler, and Yaniv Romano. Label noise robustness of conformal prediction. Journal of Machine Leurning Research, 2024.
[19] A Krizhevsky. Learning multiple layers of features from tiny images. Master's 's thesis, University of Tront, 2009.
[20] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition. leee, 2009.
[21] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 2019.
[22] Shayan Kiyani. George Pappas, and Hamed Hassani. Conformal prediction with learned features. In Forty-first International Conference on Machine Learning, 2024.
[23] Coby Penso and Jacob Goldberger. A conformal prediction score that is robust to label noise. arXiv preprint arXiv:2405.02644 2024.
[24] Matteo Sesia, YX Rachel Wang, and Xin Tong. Adaptive conformal classification with noisy labels. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2024.
[25] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on pattern analysis and machine intelligence, 38(3):447-411, 2015
[26] Xiyu Yu, Tongliang Liu, Mingming Gong, Kayhan Batmanghelich, and Dacheng Tao. An efficient and provable approach for mixture proportion estimation using linear independence as- sumption. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages
2018.
[27] Hongxin Wei, Lei Feng, Xiangyu Chen, and Bo An. Combating noisy labels by agreement: A joint training method with co-regularization. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.
[28] Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv:1912.132211 2019.
[29] Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023.
[30] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang. Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, 2019.
[31] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
[32] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4700-4708, 2017.
[33] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
11

---

[34] Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. In Hugo Larochelle. Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-TTien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, 2020.
[35] Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Un- certainty sets for image classifiers using conformal prediction. In 9th International Conference on Learning Representations, 2021.
[36] Kexin Huang, Ying Jin, Emmanuel J. Candès, and Jure Leskovee. Uncertainty quantification over graph with conformalized graph neural networks. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Infor- mation Processing Systems 36: Annual Conference on Neural Information Processing Systems, 2023.
[37] Jesse C. Cresswell, Yi Sui, Bhargava Kumar, and Noël Vouitsis. Conformal prediction sets improve human decision making. In Forty-first International Conference on Machine Learning, 2024.
[38] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Tapio Elomaa, Heikki Mannila, and Hannu Toivonen, editors, Machine Learning: ECML 2002, 13th European Conference on Machine Learning, 2002.
[39] Jing Lei and Larry Wasserman, Distribution- prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2014.
[40] Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. In Hugo I Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, 2020.
[41] Jianguo Huang, HuaJun Xi, Linjun Zhang, Huaxiu Yao. Yue Qiu, and Hongxin Wei. Conformal prediction for deep classifier via label ranking. In Forty-first International Conference on Machine Learning, 2024.
[42] Kangdao Liu, Hao Zeng, Jianguo Huang, Huiping Zhuang, Chi-Man Vong, and Hongxin Wei. C-adapter: Adapting deep classifiers for efficient conformal prediction sets. arXiv preprint arXiv.2410.09408, 2024.
[43] Leying Guan and Robert Tibshirani. Prediction and outlier detection in classification problems. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2022.
[44] Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. The Annals of Statistics. 2023.
[45] Ziyi Liang, Matteo Sesia, and Wenguang Sun. Integrative conformal p-values for out-of- distribution testing with labelled outliers. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2024.
[46] Yu Gui, Ying Jin, and Zhimei Ren. Conformal alignment: Knowing when trust foundation models with guarantees. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[47] John Cherian, Isaac Gibbs, and Emmanuel Candes. Large language model validity via enhanced conformal prediction methods. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[48] Heeseung Bang, Aditya Dave, and Andreas A Malikopoulos. Safe merging in mixed traffic with confidence. arXiv preprint arXiv:2403.05742, 2024.
[49] Christian Moya, Amirhossein Mollaali, Zecheng Zhang, Lu Lu, and Guang Lin. Conformalized- deeponet: distribution-frre framework for uncertainty quantification in deep operator net- 2024.
works. arXiv preprint
12

---

[50] Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning, 2018.
[51] Peng Zhao, Yan-Feng Xie, Lijun Zhang, and thi-Hua Zhou. Efficient methods for non-stationary online learning. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information P Processing Systems, 2022.
[52] Terry Anderson. The theory and practice of online learning. Athabasca University, 2008.
[53] Joi L Moore, Camille Dickson-Deane, and Krista Galyen. e-learning, online learning, and distance learning environments: Are they the same? The Internet and higher education, 2011.
[54] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2016.
[55] Vandana Singh and Alexander Thurman. How many ways can we define online learning? systematic literature review of definitions of online learning (1988-2018) American Journal of Distance Education, 2019.
[56] Steven CH Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: comprehensive survey, Neurocomputing. 2021.
[57] Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, 2019.
[58] Pengfei Chen, Junjie Ye, Guangyong Chen, Jingwei Zhao, and Pheng-Ann Heng. Beyond class-conditional assumption: A primary attempt combat instance- cestance-dependent label noise. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[59] Hongxin Wei, Lue Tao, Renchunzi Xie, and Bo An. Open-set label noise can improve robustness against inherent label noise. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems, 2021.
[60] Yichen Wu, Jun Shu, Qi Xie, Qian Zhao, and Deyu Meng. Learning to purify noisy labels via meta soft label corrector. In Thirty-Fifth AAAI Conference Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, 2021.
[61] Xuefeng Li, Tongliang Liu, Bo Han, Gang Niu, and Masashi Sugiyama. Provably end-to- end label-noise learning without anchor points. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, 2021.
[62] Zhaowei Zhu, Jialu Wang, and Yang Liu. Beyond images: Label noise transition matrix estimation for tasks with lower-quality features. In International Conference on Machine Learning, 2022.
[63] Hongxin Wei, Huiping Zhuang, Renchunzi Xie, Lei Feng, Gang Niu, Bo An, and Yixuan Li. Mitigating memorization of noisy labels by clipping the model prediction. In International Conference on Machine Learning, 2023.
[64] Hao Chen. Jindong Wang, Ankit Shah, Ran Tao, Hongxin Wei, Xing Xie, Masashi Sugiyama, and Bhiksha Raj. Understanding and mitigating the label noise in pre-training on downstream tasks. In The Twelfth International Conference on Learning Representations, 2024.
[65] Hongfu Gao, Feipeng Zhang, Wenyu Jiang, Jun Shu, Feng Zheng, and Hongxin Wei. On the noise robustness of in-context learning for text generation. The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
(66] Ingo Steinwart and Andreas Christmann. Estimating conditional quantiles with the help of the pinball loss. Bernoulli, 2011.
13

---

[67] Kwang- Swang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Artificial Intelligence and Statisties, pages 943-951. PMLR, 2017.
[68] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50-60 69, 2018.
14

---

A Related work
Conformal prediction [38, 5] is statistical framework for uncertainty qualification. In the literature, many conformal prediction methods have been proposed across various domains, such as regression [39, 40], image classification [35, 41, 42], outlier detection [43, 44, 45], and large language models [46, 47]. Conformal prediction is also deployed in other real-world applications, such as human-in- the-loop decision-making [37], automated vehicles [48], and scientific computation [49]. In what follows, we introduce the most related works in two settings: online learning and noise robustness.
Online conformal prediction. Conventional conformal prediction algorithms provide coverage guarantees under assumption of data exchangeability. However, real-world online scenarios, the data distribution may evolve over time, violating the exchangeability assumption [50, 51]. To address this challenge, recent research develops online conformal prediction methods that adaptively construct prediction sets to accommodate distribution shift [9, 10, 11, 12, 13, 14]. Building online convex optimization techniques [52, 53, 54, 55, 56, 28], these methods employ online gradient descent with pinball loss to provably achieve desired coverage under arbitrary distributional changes [9]. Still, these algorithms typically assume perfect label accuracy, an assumption that rarely holds in practice, given the prevalence of noisy labels in online learning [15, 16, 17]. In this work, theoretically show that label noise can significantly affect the long-run mis-coverage rate through biased pinball loss gradients, leading to either inflated or deflated coverage guarantee.
Noise-robust conformal prediction. The issue of label noise has been a common challenge in machine learning with extensive studies [57, 27, 58, 59, 60, 61, 62, 63, 64, 65J. In the context of conformal prediction, recent works develop noise-robust conformal prediction algorithms for both uniform noise [23] and noise transition matrix [24]. The most relevant work [18] shows that online conformal prediction maintains valid coverage when noisy scores stochastically dominate clean scores. Our analysis extends this work by removing the assumption noisy and clean scores, offering a more general theoretical framework for understanding the impact of uniform label noise.
B Additional results
B.1 Regret analysis
As [11] demonstrates, regret serves helpful performance measure alongside coverage. In particu- lar, it can identify algorithms that achieve valid coverage guarantees through impractical means. For example, prediction
that alternate between empty and full sets with frequencies {a, 1 a} satisfy coverage bounds on any distribution but have linear regret on simple distributions (see detailed proof in Appendix A.2 of [I]J). Drawing from standard online learning theory (see Theorem 2.13. of (28]), we analyze the regret bound for our method. Let Tx = arg min; Σt= l-"a7" Se, {St. K define the regret
y= 1). and
T
Reg (T)
Σ (I-a(fi, (Suple 11-a("", 3t, (St. 15 [=1
This leads to the following regret bound (the proof is provided in Appendix ??):
Proposition B.1. Consider online conformal prediction under uniform label noise with noise rate e E (0, Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (6), for any T E N+, have:
1(1+ max Tht IS1ST-1
1
1+c) 1-e)
2
E
2
7 2
(T)
<
+
27/T
Example 1: constant learning rate. following regret bound:
With a constant learning rate 1/, = 17, our method yields the
1 Reg(T) < 7)
( 1+6
2
Tn
+ 1- +
This linear regret aligns with the observation in [12]: the constant learning rate schedule, while providing valid coverage on average, lead to significant temporal variability in Coverage(f,) (see Proposition in [12]). The linear regret bound provides additional theoretical justification for this instability.
15

---

Example 2: decaying learning rate. Suppose the proposed method updates the threshold with a decaying learning rate schedule: - e 17)) Vt, where no E R. The incquality
Σi 1/v1 S T follows that
1+ 2 T-e
(Tg(T)
2
1 +
1/0
VT
1
This sublinear regret bound (VVT) implies that the decaying learning rate schedule achieves superior convergence compared to the linear regret of constant learning rates.
B.2 Convergence analysis of fz
We analyze the convergence of method toward global minima by combining the convergence analysis of SGD (see Theorem 5.3 in [29]) and self-calibration inequality of pinball loss (see Theorem 2.7. in [66]). Following [66], we first establish assumptions the distribution of S. Let
:= 2$ - 1 E [0. 1]. with y denoting the 1 1 quantile of ft This indicates that 7 2r - 1, where is the quantile of S. We make the following assumption:
Assumption B.2. There exists constants > 0, 2. and Eo such that P P(R 5} 2
b 6/ 2 holds for all [T 60: + so].
Furthermore, let 8 = b/(q 1) and 8 = 3(2ca) This leads to the following proposition (the
proof is provided Appendix ??):
Proposition B.3. Consider online conformal prediction under uniform label noise with noise rale E (0, 1). Given Assumptions 2.1, 2.2 and B.2, when updating the threshold according to Eq. (6),
for any N+, we have:
7- 7/" 9(1 9)
1
(ni
ΣT
-== Tİ l+t T
2
280
2
2
t=
11e
2t=1
T
Th
where 7 ET note/ Et= 77.
B.3 Why does standard online conformal prediction rarely exhibit under-coverage under label noise?
As established in Proposition 3.1, the label noise introduces gap of +
1 Σ ((1-a) a) 1 (X.))) between the actual mis-coverage rate and desired mis- coverage rate a. This result indicates that when the prediction sets are sufficiently large such that (1-a)= < [C,
high noise rate decreases this upper bound, resulting under-coverage
prediction sets, i... $ ΣT 1fY, & C(X,)) 2 a. However, this scenario only arises when E [X,,) > K(1 a). To illustrate, considering CIFAR-I00 with K 100 classes and error rate 0.1, under-coverage would require E (X,)) with random predictions. Moreover, in such extreme cases, as a) 1 E (X,) approaches 0, the coverage gap becomes negligible, resulting in coverage rates that approximate the desired 1 a. We verify this empirically Figure where we implement online conformal prediction using untrained, randomly initialized ResNer18 model on CIFAR-10 and CIFAR- 1IFAR-100 with noise rates 6 0.05, 0.1, 0.15. The results confirm that even in this extreme scenario, the coverage gap remains negligible, with coverage rates approaching the desired 0.9.
]] 2 90, condition that remains improbable even
16

---

0.39
0.99
Long-run Coverage
0.93
0.93
0.30
0.99
0.07
mise
0.87
nolse
nolse
nolte 0.15
nolse
0.83
0.41
1-0
Time
Time
(a) CIFAR-10
(b) CIFAR-100
Figure 3: Performance of standard online conformal prediction under different noise rates, with ResNet18 model on CIFAR-10 10 and CIFAR-100 datasets. We use noisy labels to update the threshold with decaying learning rates t) 1/t1/2+5 where 0.1.
B.4 Common non-conformity scores
Adaptive Prediction Set (APS). [34] In the APS method, the non-conformity score of data pair (x, y) is calculated by accumulating the sorted softmax probability, defined as:
SArs(a, v) = (1) + .... + (xe)
where (1)) (a),, (2)) (()) (a) are sorted softmax probabilities in descending order, and o(y. (x)) denotes the order of (2))), i.e., the softmax probability for the ground-truth label y. In addition, the term u is an independent random variable that follows uniform distribution on [0, 1].
Regularized Adaptive Prediction Set (RAPS). [35] The non-conformity score function of RAPS encourages small set size by adding penalty, as formally defined below:
SnAPS(æ, = (x)) + .... u- (a)) + A (o(u:=(x)) -ireg)"
where (z)+ max(0, kreg controls the number of penalized classes, and À is the penalty term.
Sorted Adaptive Prediction Set (SAPS). [36] Recall that APS calculates the non-conformity score by accumulating the sorted softmax values descending order. However, the softmax probabilities typically exhibit long-tailed distribution, allowing for easy inclusion of those tail classes in the prediction sets. To alleviate this issue, SAPS discards all the probability values except for the maximum softmax probability when computing the non-conformity score. Formally, the non- conformity score SAPS for data pair (z, y) can be calculated as
u #mar(x) if (xx)) = Amaz (x) (oly, (())) 2+ w) else,
Saapa U. y. =
where À is hyperparameter representing the weight of ranking information, #maz (2) denotes maximum softmax probability and u is uniform random variable.
B.5 Additional experiments on different non-conformity score functions
We evaluate NR-OCP (Ours) against the standard online conformal prediction (Baseline) that updates threshold with noisy labels for both constant and dynamic learning rate schedules (see Eq. (3)). We use LAC (Table 2), APS (Table 3), RAPS (Table 4) and SAPS (Table 5) scores to generate prediction sets with error rates a E 0.05), and employ noise rates e E (0.05, 0.1, detailed description of these non-conformity scores is provided in Appendix B.4.
17

---

Table 2: Performance of different methods under uniform noisy labels with LAC score, using ResNet18. 8. 'Baseline' denotes the standard online conformal prediction methods. We include two learning rate schedules: constant learning rate 1) = 0.05 and dynamic learning rates 1te 1/t1/2-s where 0.1. " indicates smaller values better and Bold numbers are superior results.
CIFAR
ImageNet
LR Schedule
Error rate
Method
CovGap($%)
Size
CovGap($8
Size
0.00
Raseline
31.61
2.747
Ours
0.289
0.122
22.78
47.31
0.018
0.138
254.7
530.6
Constaut
0.1
Baseline
4.911
2.967
43.03
67.58
4,578
2,656
488.1
707.6
Ours
0.056
0,189
26.57
54,18
0.027
0.156
312.4
584.9
Baseline
6.056
3,533
54.11
75.06
5.791
3,200
571.5
759.3
0.378
0.344
28.39
57.53
0.251
346.7
603.4
0.05
Baseline
3,978
2,833
11.54
41.75
4.333
2,889
81.27
391.8
Ours
0.089
0.067
4,290
26.56
0.031
0.020
16.46
150.5
Dynamic
0.1
Buseline
6.756
3.844
30.07
60.17
6,960
3,933
284.6
600.2
0.233
5.394
0.091
27.76
0.15
Baseline
7,844
4.289
42.69
70.67
8.098
4.276
447.9
704.4
Ours
0.456
0.067
8.389
33,60
0.131
0.138
38.89
272.5
Table 3: Performance of different methods under uniform noisy labels with APS score, using ResNet18. 'Baseline' denotes the standard online conformal prediction methods. We include two learning rate schedules: constant learning rate 7) = 0.05 and dynamic learning rates i 1/21/2-6 where 5 0.1. "L" indicates smaller values are better and Bold numbers are superior results.
CIFAR100
ImageNet
LR Schedule Eriee
Methol
CovGap(S))
Size
CovGap(5%)
Size
0.05
0.1
0.05
0.05
0.05
0.05
Baseline
4.556
2,933
5,822
21.17
4.728
3.508
13.35
79.88
Constaut
Ours 2.667
0.31
2.788
6.763
0.144
0.211
4,879
14.09
0.1
Baseline
7.511
3.822
15.71
37.19
8.402
4.388
67.25
224.2
1,333
2,661
0.119
0.15
Baseline
8,533
29.76
9.380
4.644
Ours 0.500
0,233
2.915
6.813
0,288
0.139
4.787
14.71
0.05
Buseline
4.000
2.433
4.693
13.03
4.157
2.122
11.31
31.38
Ours
0.278
0,466
2.427
5.475
0.108
0.255
4,431
13.36
namiic
Baseline
7,211
3,366
11.14
6.791
3.137
27.78
54.14
Ours
0.400
0.456
2,716
5.515
0.028
0.277
4.513
13.30
0.15
Baseline
8.288
3.911
19.62
31.19
7.928
3.675
47.88
80.33
Ours
0.188
0.211
2.479
5.790
0.264
0,088
4.321
14.03
Table 4: Performance of different methods under uniform noisy labels with RAPS score, using ResNet18. 'Baseline" denotes the standard online conformal prediction methods. We include two learning rate schedules: constant learning rate 7 0.05 and dynamic learning rates n) 1/t!/2-e where E = 0.1. "I" indicates smaller values are better and Bold numbers are superior results.
CIFAR
ImagoNet
Schedule rate
Method
CovGap(SS)
Size
CovGap(%)
Size J
a 0.1 a
0.05
a
0.1
a
0.05
a- 0.1
0.05
a 0.1
0.05
0.05
Bascline
3.978
3.533
5.275
26.71
4.716
4.509
13.73
164.7
Ours
0.533
0.089
2.911
6,265
0.051
0.673
5:217
14.21
Coustcat
Ruseline
7,656
4.278
15.25
50.25
8.689
4.84
85.19
395.5
3.126
0.15
Baseline
8.896
4.467
36.03
62.27
9.733
4.933
305.6
576.3
Ours 0.489
0.560
3,500
7.693
0.224
0.227
5.616
19.81
0.05
Buseline
4.322
3.254
4,883
19.42
4.642
3.457
12.57
60.94
2.586
0.067
Dynanic
Baseline
8.378
19.68
8.084
4.311
54.42
153.7
Ours
0.756
0.122
2,891
5.942
0.009
0.140
4.381
14.67
0.15
Baseline
9.022
4,600
33,87
57.87
9.256
4.978
133.3
239.8
Ours
0.011
0,440
2,821
5.290
0.231
0.264
4,578
15.59
18

---

Table 5: Performance of different methods under uniform noisy labels with SAPS score, using ResNet18. 'Baseline' denotes the standard online conformal prediction methods. We include two learning rate schedules: constant learning rate 1) = 0.05 and dynamic learning rates T 1/t1/2-e where 0.1. " indicates smaller values better and Bold numbers are superior results.
CIFAR100
ImageNet
Schedule Error rale
Method
Cov
Size L
CovGap(SS)
Size
0.1
0.05
0.1
0.05
0.1
0.05
0.1
0.05
Baseline
4.489
3,100
4.982
17.92
4,462
3.537
12.53
83.04
0.05
Ours
0.455
0.211
2.604
5,810
0.124
0.067
4.702
14.32
Constant
0.1
Baseline
8.478
3.944
13.25
32.71
8,368
4.389
73.14
231.5
Ours
0.533
0.955
2.701
4.987
0.102
5.013
15.37
Baseline
8.644
4,400
27.89
50.73
9,360
4,613
202.3
361.7
0.15
Ours 0.711
0.444
2.778
5.609
0.029
0.135
4.971
15.68
Baseline
4.122
2,600
4.992
13.68
4.859
1.866
13.46
28. 28.28
Ours
0.078
1.889
2.528
6.417
0.275
0.615
4.813
12.06
Dynamic
Baseline
7.311
3.322
11.84
22.19
7.162
3.000
31.37
51.64
Ours 0.267
0.067
2.444
6.218
0.186
0,553
4.715
12.23
0.15
Baseline
8.456
4.044
21.44
3.577
55.78
Ours
0.200
0.063
2.602
7.230
0.104
0,515
4.594
12.43
B.6 Additional experiments different model architectures
We evaluate NR-OCP (Ours) against the standard online conformal prediction (Baseline) that updates the threshold with noisy labels for both constant and dynamic learning rate schedules (see Eq. (3) and Eq. (??)), employing ResNet50 (Table 6), DenseNet121 (Table 7), and VGG16 (Table 8). We LAC scores generate prediction sets with error rates {0.1, 0.05), and employ noise rates e E (0.05, 0.1, 0.15).
Table 6: Performance of different methods under uniform noisy labels with LAC score, using ResNet50. 'Baseline' denotes the standard online conformal prediction methods. We include two learning rate schedules: constant learning rate 7) = 0.05 and dynamic learning rates t 1/2 where 0.1. "I" indicates smaller values better and Bold numbers are superior results.
CIFAR100
ImageNet
LR Schedule
Error rate
Method
Cov
Size
Cov
Size
0.1
0.05
0.1
0.05
0.1
0.05
0.05
Baseline
3.244
1.783
28.58
$6.08
3.226
1.982
294.4
575.7
0.05
Ours 0.033
0.089
16.26
0.073
0.035
188.5
466.8
Constant
0.1
Baseline
5.267
2,879
42.09
67.25
5,326
2.935
425.9
674.2
Ours 0.125
0.122
17.88
49.06
0.231
0.067
241.1
506.4
0.15
Baseline
6,369
3,445
53.34
74.03
6,584
3,453
531.4
758.5
Ours 0.223
0.216
21.62
50.14
0.202
0.056
263.1
549.4
Baseline
4.166
2.724
10.91
41.95
4.397
3.104
44.86
361.8
Ours
0.115
0.189
3.120
18.35
0.082
0.048
8,377
96.68
Dynamic
Baseline
6.984
3.921
30.09
61.96
7.279
4.073
232.8
582.4
Ours 0.205
0.310
4.143
27.87
0.113
0.178
10.83
170.2
0.15
Baseline
4.223
43.90
4.453
417.9
Ours 0.244
0.043
4.368
27.81
0.133
0.059
21.98
178.0
19

---

Table 7: Performance of different methods under uniform noisy labels with LAC score, using DenseNet121. 'Baseline' denotes the standard online conformal prediction methods. We include two learning rate schedules: constant learning rate 1) = 0.05 and dynamic learning rates 1tt 1/t1/2- where 0.1. " indicates smaller values better and Bold numbers are superior results.
CIFAR100
ImageNet
Schedule Error rale
Method
Cov
Size L
CovGap(SS)
Size
0.1
0.05
0.1
0.05
0.1
0.05
0.1
0.05
Baseline
3,978
3,533
5.275
26.71
4.716
4,509
13.73
164.7
0.05
Ours 0.533
0.089
2.971
6.265
0.051
0.673
5.217
14.21
Constant
0.1
Baseline
7.656
4.278
15.25
50.25
8.689
4.84
85.19
395.5
Ours 0.356
0.200
3.126
6.370
0.184
0.271
5.264
14.76
Baseline
8.896
4.467
36.03
62.27
9,733
4,933
305.6
576.3
0.15
Ours 0.489
0.560
3.500
7.693
0.224
0.227
5.616
19.81
Baseline
4.322
3.254
4.883
19.42
4.642
3.457
12.57
60.94
Ours
0.233
0.211
2.586
5.344
0.067
0.078
4.305
13.73
Dynamic
Baseline
8.378
4,400
19.68
44.43
8.084
4.311
54.42
153.7
Ours
0.756
0.122
2.891
5,942
0.009
0.140
4,381
14.67
0.15
Baseline
33.87
4.978
133.3
239.8
Ours 0.011
0.440
2.821
5,290
0,231
0,264
4.578
15.59
Table 8: Performance of different methods under uniform noisy labels with LAC score, using VGG16. 'Baseline' denotes the standard online conformal prediction methods. We include two learning rate schedules: constant learning 1) 0.05 and dynamic learning rates n/: 1/14/2+e where & 0.1. "L" indicates smaller values are better and Bold numbers are superior results.
CIFAR100
ImageNet
LR Schedule Enor rate
Method
CovGap($$)
Size 4
Cov
Size
a= 0.1
0.05
a
0.05
0.1
= 0.05
a
0.1 a 0.05
Baseline
1,911
L,33
51.13
73.03
3.164
1.995
297.8
565.3
Ours
0.078
0.144
43,50
67.97
0.002
0.031
206.6
488.1
Constant
Baseline
3,474
L.700
58.08
76.44
4.878
2.975
439.8
669.4
0.1
Ours 0.224
0.267
45,48
68.28
0.217
0.119
229.4
511.2
0.15
Baseline
2.411
64.16
80.16
3.626
544.2
Ours 0.300
0,189
44.43
71.81
0.168
0,004
281.9
551.3
= 0.05
Baseline 2.678
1,388
40,96
66.81
4.608
3.044
51.64
374,1
Ours 0.244
0.004
28.92
$9.26
0.062
0.013
5.316
112.7
Dynumic
0.1
Baseline 4.189
2.567
50.40
74.38
7.142
4.067
244.4
580.6
Ours 0.289
0.133
30.81
61.08
0.195
0.071
10.65
152.1
0.15
Baseline
5.733
3.044
60.46
78.65
8,413
4.451
432.2
708.9
0.440
0.144
35.67
63.38
0.119
0.282
18.39
224.6
C The impact of misestimated noise rate on NR-OCP
In this section, we conduct an additional experiment where the noise rate is unknown and needs to be estimated. In particular, we apply an existing algorithm [61] to estimate the noise rate without access to clean data during the training of the trained model. Then, we employ this estimated noise rate our method for online conformal prediction. The experiments are conducted on CIFAR- 10 dataset, using ResNet18 model with noise rates E {0.11 0.2, 0.3). We employ LAC score to generate prediction sets and use a constant learning rate 7 = 0.05. The results demonstrate that our method consistently achieves much lower coverage gaps and smaller prediction sets compared to the baseline. This highlights the robustness and applicability of our method even when the noise rate not precisely estimated.
20

---

Table
Noise rate
Estimated Noise rate
Method
CovGap (%)
Size
Baseline
6.99
2.47
0.1
0.09
Ours
0.82
0.94
Baseline
8.72
5.41
c= 0.2
0.23
Ours
1.67
0.98
Baseline Ours
9.04
6.72
6 = 0.3
0.26
2.32
1.15
D Additional information Strongly adaptive online conformal prediction
D.1 Strongly adaptive online conformal prediction
The SAOCP algorithm leverages techniques for minimizing the strongly adaptive regret [67] to perform online conformal prediction. In particular, SAOCP is a meta-algorithm that manages multiple experts, where each expert is itself arbitrary online learning algorithm taking charge of its own active interval that has a finite lifetime. At each E [T]. SAOCP instantiates a new expert A, with active interval (t, l L(l) 1], where I(() is the lifetime:
L(I) max {2" :l = 0 (mod )"
n
where g Σد1 is multiplier for the lifetime of each expert. It can be shown that at most g log, t experts are active at any time under the choice of L(t) in (7), resulting in a total runtime of O(T log T) for SAOCP when g ((1). At each time t, the threshold fg is obtained by aggregating the predictions of the active experts.
Σ
Pi
(EAtiive(t)
where the weight (eig) is computed by the coin betting scheme [67, 68].
Choice of expert. SAOCP employs Scale-Free OGD (dubbed SF-OGD) [68] as its expert. In particular, SF-OGD is variant of OGD that decays its effective learning rate based cumulative past gradient norms.
D.2 Noise-robust strongly adaptive online conformal prediction
In the following, we present a pseudo-algorithm of NR-SAOCP, The essence of this method is to update the threshold with our robust pinball loss. In Algorithm 1, we demonstrate how NR-SAOCP manages multiple experts to update the threshold. In Algorithm we present how each expert updates the corresponding threshold.
21

---

Algorithm Noise-Robust Strongly Adaptive Online Conformal Prediction (NR-SAOCP)
Require: Target coverage 1 - E (0, 1), initial threshold to-
1: for 1= 1,..... T do
2: Initialize new expert A, NR-SF-OGD(a + a; 1/v3: t Q--1) (Algorithm 2), and
set weight Whet 0
3: Compute active set (t) {i E [T] t L(i) S 1 {). where L(t) defined in Eq. (7)
4: Compute prior probability T; x x [ 1 ACt)ve( compute un-normalized probability P4 - [ for all i E [4] normalize p/ |لاl| if ||l|| >> 0, else Update the threshold f, = EieAcive(t) P:
5:
6: Observe input X, and construct prediction set (Xt, as in Eq. (1)
7:
Observe true label S(X,, y) for all y E y
Y, compute non-conformity score S, S(X,, Yo) and St.
8: for E Active(t) do
9: Update expert A, with robust pinball loss and obtain next predicted radius #441
Compute
[i(fe St. (Sty) ) ) - [( Se. (Sty)y 1K (i Se, (St.p 1 - 1(f1 St, [
if W1,5 > 0
9i.t
if Wa,s S 0
where 7 the robust pinball loss defined in Eq. (4).
Update expert weight wi,++1 = - (E)= (1 E1
11:
12: end for
13: end for
Algorithm 2 Noise-Robust Scale-Free Online Gradient Descent (NR-SF-OGD)
Require: (0, 1), learning rate r 0, initial threshold f E IR
1: for 2 1 do
2: Observe input X, and construct prediction set (x,) as in Eq. (1)
3: Observe true label Y, E V, compute non-conformity score S. = S(X,, Yi) and St, =
S(X,,)) y) for all y E y
4: Update the threshold:
Vi, (fr, Sr. (S 1
741 7t
E - 1V.[(f S₁, S 1 113
where is the robust pinball loss defined in Eq. (4).
5: end for
E
Omitted proofs
E. Proof for Proposition 3.1
Lemma E.1. Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (3), for
any T E N+, we have
-on S + S + (1 10--00 -a)
Proof. We prove this by induction. First, we know f E [0, 1] by assumption, which indicates that
Eq. (8) satisfied at f = 1. Then, we assume that Eq, (8) holds for = T, and we will show that iтii lies in this range. Consider three cases:
Case 1. Fr [0, 1). we have
(0)
कт îr- n Vt.4-al S.)
E
[-an, 1+ (1 a)ml
22

---

where (a) is because Vr,1i-a(fi, St) E [a - 1,
Case 2. Consider the case where îr E [1, + (1 a)nl. The assumption that S E [0, [0.1] implies
1 { ft 0. Thus, we have
-1 ( { fej + + +a=a a
which follows that
1a E - -,a, + (1 - - C cl 1 + (1 - a)n] TT+1 = fy - n (at St) = -r
Case 3. Consider the case where βr I-an, 0]. The assumption that $ [0, 1] implies
1 { $ it } 1. Thus, we have
Va.h-a(fe, -1 ( tt +a=-1+a
which follows that
fr+1 fT 7 V (ft, b. n a) E [--am, (1 (1- a)n) C [-an, 1 (1 a)n]
Combining three cases, we can conclude that
-an S ft - 1 (1-a
Proposition E.2 (Restatement of Proposition 3.1). Consider online conformal prediction under
uniform label noise with noise rate e E (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (3), for any ö E (0, 1) and T N+ the following bound holds with probability at least 8:
2 -
4
1
T-c + 11+1-a) 1
-
(Y, E C(X,)
2
'T
1
Σ
(1 (1-a) a) - * 1(
1
+ T-c T
Proof. Consider the gradient of clean pinball loss:
Σ V l -a (1)
V 4 1- (T.
Σ
Es V T. 4. (T,, +
Es 1 (Te, S.)
T
V h- (1)
Σ
Es [V 1- (Tc,
Eg 11, (7e, St)
(4)
Part (a): Lemma F.3 gives us that
T
T
()) ())²1
8
P
Σ Es,
S:) - Σ
St)
2T
21
2
1=1
Part (b): Recall that the expected gradient of the clean pinball loss satisfies
Es [V, S,) = P {S, < 7 - (1 a)
K
(a)
1
P p( 5t < } K(1 - c)
c
Σ
PiS S <ti - -(1 aa)
y=1
K
(p(3) S, S } - (1 -11-a))
c
Σ y=1
P. P(St. S ftt (1 (1-a)
1 6
T-e
K
1
Eg, V a (ft, ST)
(tt,
1
B [x.)) (1 (1-
1
T-c
K
23

---

where (a) comes from Lemma F.1. In addition, Lemma F.3 implies that
(4) )1)
6 2
P ss. (v,l1-a(th, (f, St) S 222Tog
2
Thus, we can derive an upper bound for (b) as follows
Es V S]]
T
Es
(tel1-a(fe:
Σ
(1-a)
(1
1
T
Eg
17 Fr.. 5) -
Σ
T
+ V
Σ
T
Vi,li-a(fi.
c T
Σ
(a-
- =
1
1
1=1
1=1
T
T
T
Σ
Eş
V 1 1- (t.. 5)
Σ
Σ
1 V
V
1=1
[=1
t=1
T
(1-a) 1 E(((x)))
Σ
t=1
5
log
( (
+
Σ
V
S)
e + +I Σ (1-a)
- R =(((())))
1
1
Then, we derive an upper bound for (c). The update rule (Eq. (3)) gives us that
i+ = - 1 St)
( S.) = (fr ft41).
Accumulating from t t T and taking absolute value gives
T (f,, = Σ | (+. fe+1) = 1 rra s
(a) 1 - (1+ a))) =
Σ
17
"
77
where (a) follows from the assumption that न [0, and Lemma E.I. Thus, we have
T Σ Es (V/liaaa S) < 1
)
4 +
1 I ( +1 + - - Σ (1-
(1- 1
2T log
1=1
By taking union bound and combining two parts, can obtain that
T
4
[ (111-))
V 4 (Te, St) S
log
+
2T log
+ --c 17
1-c c
T
1 K
+
E.
(C((Xe)) (1 (1)
1=1
log (
+ 1 1-c
(1 +1 a
Σ
T
(1-a)
1
1
1 c
K
holds with at least
8 probability. Recall that
V Vn St) = Σ (1 < ne) (1- Σ
(1(
Σ
(Y, $ C(X)))
t=1
t=1
24

---

We can conclude that
T Σ
2-c
1
1 (= +1 +1 -a) a)
1 -
a T
(%,
cx())))) 2
2 2oo
5)
vT
+ - c 11
-
T
+
e
Σ
(1-a)
1 B (c(()))))
1 1
T
t=l
E.2 Proof for Proposition 4.1
Proposition E.3 (Restatement of Proposition 4.1). The robust pinball loss defined in Eq. (4) satisfies the following two properties:
(1)Es [I- S)] Es,s, (T S. (,
22)Bs (T, ST] = =s,,,
V Vrli-a(T, S, (S (5
Proof. The property (1): We begin by proving the first property. Taking expectation pinball loss gives
Es (T,a = Es |a(T S) 2 5)+ (1- (1 SH
= arp (T 2 5} - a L'' sPP {S= ds - (1- (T - 0) L sP (S =8]ds ds
po { S T
6 p ST} -a J 8 { { S r
6 PP 15 ST) ds
+
+
1_
1-t
(a)
(
(1 a1-
1 p { [_
+
P(S>
+ +(1 (1-a) a) f (i-e (1-Pp33>1 5
P 7}
1 1-
1
(c)
(d)
Part (a):
K K(1
1
pp
+ c P($ {}}
--
=ar
1- p s S
1
+
Σ y=l
P (s, ST)
1-
K
a7 1-c {$$ +
é
Σ 1 (Sy S x+)
Eg,,,
K(1 - c)
y=1
Part (b):
a ..' ( (1-
p [ P
6 1 P( P(S ds =a 50
1 P { [T + K(1 - c) y=1
K P(Sy St) ds
S
eS
K
= -Bs,sy
1| { 7 + K(1 - c)
Σ
11 1 S
1-c
y=l
Part (c):
K Σ 1=1
(1 - a)7
{ 5 (
1
pp
) 7
+ -
P(S 7} >} = (1 a)T
| 1-c
p [(} + K(1 -
P P( >
1--
Eg S,
(1-
1- 1 |
|
e
Σ 1 ([S,)1) ]
K
K(1 - E)
y=1
25

---

Part (d):
(1 - a) L 8
P(3 > r
1 ds
e
+
1-t
= (1 - a) L/ 8
PP {
+
6
Σ
k
pl > zT) ds
K(1 e) y=1
Egss, (1 a)
(
1- 1--
$
{{3>)}
esy
Σ
k
11 1 > 71
K(1 - c)
y=l
Combining (a), (b), (c), and (d), we can conclude that Es (411-o(T, (T, S]]
= =Bs,s
at
c
Σ
K
- [T)
1s, [T1
1- [
3
{
cS,
Σ
K
1 s
1 1--
K(1 - c) 8=1
K(1 - c)
y=1
K
E5,s,
(1 (1-
1 1
{ r]
Σ
1 t|
1-E
K(1
y=1
5
1 { r] + k(1 eS, Σ (115,1]] |
+ (1 11aa) a)
1-6
y=1
1
(a(T= 5111 { s 7 + (1 - -
- 7) {"> +}} +
E
1
K
(o(T= - 5)11 (S, ST) - (1- 1) > :1)
E
Σ
K(1 c)
y=1
K
1 1 (T, 5)+ K(1 c) (T)
Σ y=1
E
1 c
(,, =Bs.s,
The property (2): We proceed by proving the second property, which demonstrates that the expected gradient of the robust pinball loss (computed using noise and random scores) equals the expected gradient of the true pinball loss. Consider the gradient of robust pinball loss:
Es.s,
Vrli- S, (8,1,
Es,s,
1-E 2 $ {
a
Σ y=1
K
QE
1 1 Sy)
1 a
1 1 < 5] 5)+ + Σ
K
(1- a)e 1 { < 8
K(1 - t)
K(1 - c)
y=1
P p 2 $)
Σ
K
at
pfr 2 [,)
1 1- a p
(7
(r < $
+ Σ
a)
p(r < (t,)
I-c
K(1 - c)
1-6
K(1 - c)
y=1
y=1
= =oP (r 2 5) - (1 - TP (T < <}
Es (T,)-
E.3 Proof for Proposition 4.2
Lemma E.4. Consider online conformal prediction under uniform label noise with noise rate
e EE (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (5), for any
8 E (0, 1) and T E N+, we have
am
< tr $ 1 - am +
(9)
1-e
1 1-e
26

---

Proof. We prove this by induction. First, we know f1 E [0, 1] by assumption, which indicates that Eq. (9) satisfied at f 1. Then, we assume that Eq. (9) holds for T, and we will show that TT+1 lies in this range. Consider three cases:
Case 1. If ,r [0, 1}, have
r+ tr n V-rlial(fr ST, (5tx))=)))
(a)
E
-an
en 1-
1 an + 1-6
where (a) follows from Lemma F.2.
Case 2. Consider the case where îr E [1, + on) 1/((1 -)]. The assumption that ST, St.y E [0,
implies
{ ST S (r) (St.y S fr) 1. Thus, we have
K
V 1 (fT,, Sr, (St.g) ]x=
pr ST
Σ
aE
11 f 2 Star.
1 1- a 1|
{ pr 2 5r]
1 -
K(1 - c)
1 - 6
y=1
k
(1 aiE K c)
1 ( Styy
y
k
ae
= a.
1 1
K [1 k)
y=1
which follows that
FT+1 -T 17 la ST, (S = .T -1par
1 ma, 1 77 1-c c 077 1-c
o7 + 1-c
- Case 3. Consider the case where îr l-an-enn(1 - 0]. The assumption that 3, E [0.1]
implies 1 {3 < +r} = 1 {s, < fr} = 0. Thus, we have
V V (fr, |k
1-1)) 1
pr Sr) Σ
11 for 2 St,
1 1- || { Fr ST)
K(1 -
K
(1 aae
11 { 2 St,y
K(1 c)
ym
K a)c
a
fr < <
Σ
= =a --1,
1 - E
K(1 e)
y=1
which follows that
fr+1 = fr - 17 V (fr, Sr {St,) = fr + 111 - a) E
en
+ 7 a), n1 ai)
-07]
1 1-6 c
ET]
- 0m) + 1
C
(11)
1-
Combining three cases, we can conclude that
oT 1-c <
5
02
+
1-c
Proposition E.5 (Restatement of Proposition 4.2). Consider online conformal prediction under uniform label noise with noise rate (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (5), for any 5 E (0, and T E N+, the following bound holds with probability at least 8:
1og(2/8)
a + 6 - 1
1 1
ExErr(T)= S
T
1-
VT
11
27

---

Proof. The update rule of the threshold is gives us that
1 - - rtt1)-
F++1 = f. -) Vi,li-a(tr, St, (St. )
= (f St, St, (Scn)==1)
1
Accumulating from t 1 to = T" and taking absolute value gives
T
T - (tr - f0t2) + f+1ll S
Σ
Vn.i-aafee (St )=
Σ
an + en
+
7
1
t=1
t=1
where (a) follows from the assumption that éI [0, and Lemma E.4. In addition, Lemma F.5 gives us that
T
T Σ
v log (2Tlog(2/0)
Σ
E
(St
V4,11- (5 1 1 1
21-5
Se.
tm
Thus, with at least - ô probability, we have
Es S
Villi-a Se, (StN) 1x
V V (fr, Se, (
V 70 ( +
Σ
V 1 Se, (
T
T
T
E SL.
V - (fc, (5
+
Σ
V Sr {5 1
1=1
t=1
V
2T log(2/8) +
1-c
1
Applying the second property in Proposition 4.1, we have
T
T
T Σ
Σ Es.s,
Es. V (f.. 5-)1= Σ
p - f.) (1 -a)
=
which implies that with at least 1 - probability,
[P (Y, $ C.(.)) - al]
Σ
T
[S. S f -11-011-00 (1- (1-a)]
v 2T log(2/8)
1
1-6
11
1 1-e
(10)
Therefore, we can conclude that
T
I log(2/8)
+ ---a+ (
)
1
Ex)rr(T) = P P(Y (
1 -
VT
17 1-e)
T
holds with at least 8 probability.
E.4 Proof for Proposition 4.3
Proposition F.6 (Restatement of Proposition 4.3). Consider online conformal prediction under uniform label noise with noise rate e (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (5), for any å E (0, 1) and T N+, the following bound holds with probability at least
2 2oo
(t) VT -a-at 1 = 1
1
(m) 1 e
T
Proof. Lemma F.3 gives that
4 St) S 2T
2 8 7 }
P
Es. (5.
Σ
$1
2
[=]
28

---

Follows from Proposition 4.2 (see Eq. (10)), we know
T Σ Es, ( St)l = Σ Egs,, (7,
T
(5,
2T (4/0)
+
1
+
6
1-6
71
holds with at least
8/2 probability. addition, recall that
Σ
Vahhaa(f, =
Σ I (St S n - (1 a)]
Thus, by union bound, we can obtain that with at least probability 1 - 8,
T
T
T
T
V V= (ft,
V -
Σ
Es,
+ (t,
Es, (
t=1
1=1
V 1 1-a ( S1) Σ
Es, V 1 - (Fr, (tt,,
+
Σ Es, 1- Sc)l
27 log(4/8)
$
log
+
a +
1 1-c
1 - e
-
44
4
2T
a +
1 -
8
1 1-c c
Recall that
T
Σ
11 & c(X))) al
Σ
-t)
-
Σ
V v (
1=1
Therefore, we can conclude that
1 Σ
1
EmErr(T)
146 Cx(x)))
V Viliaaate
T
T
t=1
6 - - c cV
()
()
(1-a+
6 )
2og
+
a
VT
11
1 1-6) T
holds with at least
8 probability.
E.5 Proof for Proposition 4.5
Proposition E.7 (Restatement of Proposition 4.5), Consider online conformal prediction under uniform label noise with noise rate (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (6), for any å E (0, 1) and N+, the following bound holds with probability at least 8:
log (2/0)
1
1+c
ExErr(T) S V
1-e VT
+
151ST-1
max Th
I --c
Σ t=1
n
T
29

---

Proof. Define 7%% = 0:
T
Vi, 1 -oo (fe, Se, (5t
Σ 111
1
( Vallia(fe Se, (S (5m }-m)
T
T
(77 - -)-z)
Σ
(f (5 1k
x=1
1/1 1 ) (ीr - -t)
f1t
t=1
|r trl
T Σ
1+
+
max 1S1ST-1
Tt
Me
m-
where (a) comes from the update rule (Eq. (6)), (b) is due to triangle inequality, and (c) follows from Lemma ??. In addition, Lemma F.5 gives us that
T
(fr, S1, (5 1K 1 V 2T (2/()
Σ
E
[V V Se, ( S.y
V 11,1-a(t (fr,
2 21-6
1 -
Thus, with at least 1 - ô probability, we have
V Ss,
Sc, [
Si.
Vo (fer Sr, { وسم
Vo (5 +
Σ
V ffrlia(ft So (
t=1
T
T
T
E
SS..
(Fr, Se, (St.u]
V (fe,
(S.
+
Σ
V 1 (fr, Sr 15
1=1
1=1
t=1
27 (2g()
(1
1 1+c
max 155TT-1
Tt 1
mh
7-
1-c
Applying the second property in Proposition 4.1, we have
T
T
T
Σ Es,s, (
= Σ Es. (V.l1-a
Σ
PS. < 4 - -1 (1-
which implies that with at least 1 - probability,
(Y, $ c.(x))) - a]
Σ IP (SS S -t (1 a)l
/ 27 (2/())))
11 max 1515T-1
1 1+c
Σ
T
7)t
1-c
1
(11)
Therefore, we can conclude that
T Σ
log(2/8)
+ [11
1 + c
T
1 T
ExErr(T) = P (Y, & c.(x,))
<
max
m
T
1-e VT
15157-1
1
t=1
holds with at least - 8 probability.
30

---

E.6 Proof for Proposition 4.6
Proposition E.8 (Restatement of Proposition 4.6), Consider online conformal prediction under uniform label noise with noise rule (0,1) 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (6), for any ö E (0,1) and Nt, the following bound holds with probability at least 8:
T Σ 1h
EmErr(T)
- 1- -
2 log
+
(1+
max 1
T
1+6 1
nr-1l
vT
T
Proof. Lemma F.3 gives that
P Es.
Σ
T
St)l
T Σ
( (fr, St) S
27
)
1
2
2
t=1
Follows from Proposition 4.5 (see Eq. (11)), we know
T
Σ Es. (+ S.)l
Σ Es. s. S.
v 2T (2/()/6) -
1
T
1+
max T/
1 Mi
Σ
7-1
1S1T
t=1
holds with at least 8/2 probability. In addition, recall that
Σ V S.) = Σ [ S n. (1-a)
Thus, by union bound, we can obtain that with at least probability 1-
T
V +. 4 S.)
V (f1
-
Σ
Es. 4, (+t +
Es. (v,
T
rr ( S1)
Es. t. 1 (fr,
+
Σ Ess V v. 1 1-a 1-, St]l
2T log
+
2T log(2/8)
+ 1+
max
1/e
+
Σ
T
17 - 7-11
1-e
15157-1
1-e
1=1
2 -
2T ( - 3-(1+
1+6)
T
T)
Σ
Inc
Mo
1 1-c
1315T-1
1-c
1=1
Recall that
T Σ
En $ (xx)) aa
- -
Σ
V
1=1
Therefore, conclude that
EmErr(T)
T (Yr & c((x))
V
T
T
< 1 2 log
2 c
4
1+
max
1 c -
Σ
17
-1
VT
111ST-1
T
1=1
holds with at least - 8 probability.
31

---

E.7 Proof for Proposition B.1
Proposition E.9 (Restatement of Proposition B.1). Consider online conformal prediction under uniform label noise with noise rate e E (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. for any T E N+, we have:
max T/ 1 211(11 (1+ Σ (h (St, (St - a- St, (Sto))=)) S 2115
1 1-c)
1 1+6)
+(1+ c
1
Σ 7 t=1
ISiST-1"
Proof. The update rule (Eq. (2)) gives us that
(f++1 -T")² (fr- T²) + (T - f.)
Se, (Str) + +1² (Volii-a Se, (5tm)
Recall that the robust pinball loss is defined as
K Σ
(T,0(,, = 1 - -
(T)
K(1
() y=1
Since pinball loss is convex, robust pinball loss inherits the convexity property. Thus, we have
(r" - --)-))- V Sc, (5w s a=aat", St (St l1-a(ft, St, ( p=11)
follows that
(f++1-"))* - -T²)² S (fr - --)= + -1 (I Se, (Shn)))))))) 1k - T (fr, Sr, (r. (Sr ) +
(12)
ni. (v (ft, Se, (8th)) 1x
Following from Lemma F.2, we have
(vrii-atto St, (Stm)1=11) )
< 1 + 6 2
Dividing this inequality by n) and summing over 1,,,
T provides
i1-a (fr, Se, (2) - T- S,,, (8
1
T
1
(ft. - -2-
1
(fe+1 - +-)²) +
1+
2
T
1/
21Tt.
2111.
1-e)
2
1=1
T-1
2 T
(f1 - -²)2
(fr41-7") - 72)2 +
1
(fz - ++)+ +
(1+c)
Σ m
2
27)
21
27++1
2mp
1-c)
t=1
1=1
Lemma F.4 gives us that
1 1+,)² 2
(fr (+==
1+
max
T)
151ST-1
1 1- c
which follows that
(fr, Se, (Stw) - , (8. 1kk }(=))
1+ max Th
i-e)
1+c)
2
1
2111 )
(1
1+
max Th I
T-e)
1 + c
2
+
2 T ne
Σ
2/
1SSST-1
211T
1
max 7 1+
1+c) 151"7-1
2
+
11-c
1 + E
2
Σ
T
n
2nT
1
2
1=1
32

---

E,8
Proof for Proposition B.3
Lemma E.10. Under Assumption B.2, the pinball loss satisfies
f - + q(1 -q)
1
E (f,)) - -1)
25D
Proof. We employ the proof technique from Lemma C.4 in [1]]. The Assumption B.2 gives us that
P (R = 3} 2 bl9 7/8-2
( = f} 2 2h 2 - -)19-2
? = 27 -1
By Theorem 2.7 of [66], we have
(1) 10--400 11-a7 Ri)) 1/9
I9 > 2/-1//////// 1/2. (E (9, (1 R))) 1/ =2 [((1 (g(1-)) 9)
1
EE (111a(9;4
250
Since |8 -1 2 -
T| and 11 (9,1() = lt
(f, S), we can obtain
| 1 9(1 9)
1
E (f, [T,
250
Proposition E.11 (Restatement of Proposition B.3). Consider online conformal prediction under
uniform label noise with noise rate E (0, 1). Given Assumptions 2.1, 2.2 and B.2, when updating the threshold according to Eq. (6). for any T E N+, we have:
< q(1 9)
1
(A -2)
E T
m
1 c 2
F T1-
+
250
2 2Σ 11=1 176
Σ
1-
1/1
T where 7 -E / Σ T/C
Proof. We begin our proof from Eq. (12):
(f++1-1 - -)²² S (fr - r)² + 2m:
-0 (Ti-a(T, Sc, ( - I1-aa 3e, (S (Sw 1) n
(V 3r (5t.w
By taking expectation condition on (X,, Yi) (or equivalently on S, and (S 1 ,). and applying Lemma F.2 and Proposition 4. we have
(1tc)
E [( - - < (fz - - 2np (I E ((. +
i-c
By rearranging and taking expectation, we have
1 c 1 - E
2
2n: 7n--BB (E S) (T, S))) s E [(te - --) - [(f41 +-) +
Summing over 1,2, ... provides
T Σ m
1 +
2 M (1.40tt - - (T, (1 s (A
-2 E [[fe+] - ---) +
1-c
1=1
< (A -²)² + 1 + 2
m
Let us denote 7 :: ΣT Mete/ Σ
The Applying Jensen's 's inequality and dividing both sides by
2 1t=1 M 1h gives
T
E 14-a (7, - 11-0 (T, S)] <
Tle
(E (E 5)
(T,
T
11t
A 7 T-2²
ΣT - nr
1+t 2
2 > Th
Σ 1/t
1-6
33

---

Continuing from Lemma E.10, we can conclude that
7 - 7/% < q(1 q)
1
i - r
21 np
2
(
280
2
>
11
-
F Helpful lemmas
Lemma F.1. The distribution of the true non-conformity score, noise non-conformity score, and scores of all classes satisfy the following relationship:
(1) - s}
IP
5 ==
Σ
P[S,
s}
K(1 -6
y=1
K
(2)
P {$ {
Σ (S, Ss):
1-c
K(1 c)
K
(3) = 1-c P | of
Σ
K(1 - y=1
where S, S, and Sy denote the true score, noisy score, and score for class y respectively.
Proof. (1):
p
=| . s)
P = 8) - s|$ S..SsSS.P(s.. $} =
- (1- (S = (e + cP =
which follows that
K
- = 1 -
1
p S = 8
{S= = 8)
1-6 {
$ 8]
Σ
P P(
1 -
K(1
y=1
(2):
+/S=))==($..b333::=====$$$$$ s $}
= (1- [[
which follows that
K
PSS
1
p
E
P
[8
p $ <
Σ
P (S, S
1-6
1-c
1-6
K(1 6)
(3):
= s)p=s(ppp51 $}
= =PSS> (|
= (1 - -11-00P55-3++<p($52}
which follows that
K Σ
PSS> = P
8 ()
1 1-c
| p
E P (8 8)
$ >
P (S,
-
1-c
K(1 c) y=1
34

---

Lemma F2. The gradient of robust pinball loss can be bounded as follows
6 a-1- < --
a-1
V S a + 1-6
(13)
Proof. Consider the gradient of robust pinball loss:
ac
a
K
(1 a)
1
1 1
7 <
K(l 1 ff < Sy)
K(1
1
(0)
(c)
(b)
(d)
Due to fact that 1 {.} E [0, 1], we can bound each part as follows:
Part (a):
a 1 1
8 E
0,
1 1-6 E
Part (b):
Σ y=1
1 1 Sy}
0.
06
K(1 - c)
c
Part (c):
1
1-a
(f < 8) E
0, 1-e
1 -
Part (d):
K (1 1
0. (1 - a)c
Σ
K(1 1 < Sy) E
e
Combining four parts, we can conclude that
(1 ate
(F, (5)) S
0 0+
a +
6
(f, (S 2 1
ae
1
+ a
1
Lemma F33 With at least probability 1-8, 8, we have
T Es. S+)
I
Σ
Σ
v
Si) S
21 log
4
5
t=1
1=1
Proof. Define
T
YT = Σ Es, V (fr, St)] 1=1
(f..
Σ
V + 4 -a (fr, St);
Dr Y1 Y- V+hha (fc, S.) V S.).
Now, will verify that {Yr is martingale, and {Dr} is bounded martingale difference sequence.
Due to the definition of [Yr). we have
Es, (Y Yy Es. [Dr + Yr-1 .Y] Es, Yr-i.... .Y]+ Yr-1 Yr-1.
where the last equality follows from the definition of {Dr} In addition, have
Es. 1 5,) = P (S, < + (1 a. [a 1,
35

---

and Eq. (13) gives us that
Dr = Es, 1o St)l Vall-a Si) E [-1,11].
Therefore, by applying Azuma Hoeffdin''ssssss inequality, can have
T D
x²²
St = P
Σ Es. (f) Σ Vali-aafe,
Er
211220200 11-22xxp
2exp
2T
==1
Using r = v '2 log( 4/6), we have
T
T
Es, Val S:)l
Σ
St) S
4 2T
{
8
Lemma F4. Consider online conformal prediction under uniform label noise with noise rate
E (0, 1). Given Assumptions 2.1 and 2.2, when updating the threshold according to Eq. (6), for any
E N+, we have
-i-e-a
max Tt a - S fr S 11
max T/ 1887--1
(14)
1SST--1
1-6)
for all T E N
Proof. We prove this by induction. First, we know fi E [0, 1] by assumption, which indicates that Eq. (14) is satisfied ( 1. Then, assume that Eq. (14) holds for = T, and will show that FT41 lies in this range. Consider three cases:
Case 1. If fr [0, 1], have
PT+1 = Fr - -fr Vay a- (Tr, ST,
1K
(a)
1r (a (a+
1-c ,1 m8 aa-1
_
max 1t (a E
(1-c-a)
1
max ?i.
1515T-1
1SIST-1
where (a) follows from Eq. (13).
Case 2. Consider the case where îr E [1, maxIgisT- (1/(1 -) - The assumption
that S7, Sr.y E [0, 1] implies 1 Sr < îr
= 1 [S < frr = 1. Thus, we have
K Σ
V 1 (fr, (fr, (St. 1 1
pr 2 Sr
aE
11 (or 2 St.yy
1 a l| Fr 2 8r)
1
K(1 ))
1
y=
K
(1 a)e
1 { S
K(1 - t)
m
ac
a.
1
K [ - c)
which follows that
fr+1 न. - V (fr, ST, (St 1K = îT. TTa
1
7/
E
T/T,, 1
max 1/ 15157-1
1-e
c
1
c
max T)
a
.
max
T/
1155T-1
1
15:5T-1
1-
36

---

Case 3. Consider the case where fr E |- max
The assumption that
S. E [0, 1] implies 1 { - 5r
= [5, 1 frr = 0. Thus, we have
K
V (fr, ST, (St.) 1
{ रr ST
aE
11 ( 2 Stay
1 1- ||
{
{ Fr 2 ST)
--
K(1
1 -
K
(1 a)c
1 f+r 2 St,s
K[1 -
y=1
-
(T 5} + Σ
(1 a)c
1,
1- c
K(1 - E)
y=1
which follows that Fr+1 = .r - 1r Vo ST, (8t = pr + T/T : (1 (1-a)
+ +T- (1 a).0 + + (1 - a)
E
max 7/ :
a
1
1 1-
a E
1 (1- - )
c
max ?)t
1 +
max T/P 15tTT-1
1515T-1
Combining three cases, we can conclude that
max Ti (a+ 1 < fr 11 1
1
max M1
a
ISSTT-1
1 -
Lemma F.S. With at least probubility 1 - 8, we have
T
v 22 log(2/6)
Eg St. (t, (t....
St, (St
1-6
Proof. Define
T Y1 = Σ
T
E Sey
Vi,11aaf (Ft, Se, (St.v) 1 )ym
Σ
V V,,hia((1 St, (St. ik
1=1
Dr = YT Yr-1 = =Es,s.. V Va (Fr, Sc, (Sr.y) ( |=11 - V Vi S., (S
Now, we will verify that {Yr} is martingale, and {Dr} is a bounded martingale difference sequence. Due to the definition of {Yr), we have
Es,, (T-1, Yi] E.s,,., [Dr - Y.j Es.s. [Dr(Yr VY] + Yr-1 Vr-1,
where the last equality follows from the definition of [Dr}. In addition, we have
Ss.. [ V St, (St)))=))) E [ax 1,
and Lemma F.2 gives us that
Dr Es. V V=,l-a(ft, St (Stw))=))) - V V+lh-a St, (m
1- 1-c'1 1
Therefore, by applying Azuma-Hoeffdinggs inequality, we can have
D
<2 = P
E Bg..s. / 11.41-a(tu Se, ( - Σ v ( (S
Sr
t=1
1=1
[r(1-e)) - e)]
(r(1
> 1 - 2exp
27
37

---

Using (2 log(2/6)) 1/2 /(1 c), we have
27 (og((/6))
Σ E8 S... ( St 15 / 1)
Σ Vi, Vi,li-a(feo Se, (Stobe
1 21-6.
--6 6
38

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction summarize the paper's key contributions: theoretical analysis of the impact of label noise; 2. method to climinate this impact; 3. Extensive evaluation of the method.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
39

---

Justification:
We discuss the limitation in the Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We clearly present the assumptions made in the theoretical results. All the proofs can be found in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have listed all the information needed in Section 5.
Guidelines:
40

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We include example code in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Beteiii/guudds//ooeSuue seabbbmissiooooocccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n ctt.pss.cc/pubiccuuuuuuu gesds//////eeeeeee/e /CodeSubmian ss cessoonooll. onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
41

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the details for reproducing the main experimental results are presented in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information is provided in Section 5.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
42

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /ttp://eeri.....eeeee ctess.c//// wwtpcccccppccaeeeeeeeeeecc www.heeiieeeeieeeccccecccceeeeee ines?
Answer: [Yes]
Justification: This paper is aligned with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: impacts.
This paper focuses on online conformal prediction, and it has no societal
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: All the datasets and models available online.
Guidelines:
43

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All the creators or original owners of assets are properly credited.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
44

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
45


Reviews:
[{"review_id": "jUoL4quI6r", "reviewer": "Reviewer_v3zM", "summary": "This paper studies the robustness of online conformal prediction methods in the presence\nof uniform label noise. The authors demonstrate that standard online conformal\nalgorithms, specifically ACI and its variants, can exhibit systematic coverage distortion\nwhen labels are noisy, resulting from biased gradient updates due to corrupted supervision.\nTo address this, the authors propose a robust pinball loss, designed to be an\nunbiased estimator of the true clean pinball loss. Theoretical results show that this loss\neliminates the bias and leads to convergence of the coverage error at rate $\\mathcal{O}(T^{-1/2})$\nThe method is tested on CIFAR-100 and ImageNet under various noise level, with both\nconstant and dynamic learning rates, and across several conformity score functions.", "questions": "1. How much sample size is needed before the expectation-based correction becomes\naccurate in practice?\n2. How sensitive is performance to moderate misspecification in $\\epsilon$? Could it be estimated\nadaptively online?\n3. Would the approach generalize to class-conditional or instance-dependent label\nnoise?", "limitations": "See above weakenesses", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The authors provide clear bounds showing how label noise affects coverage (Proposition 3.1), and they construct a principled loss correction (robust pinball loss) with matching expectations and gradients (Proposition 4.1).\n\n2. The results span multiple datasets (CIFAR-100, ImageNet), multiple online conformal methods (ACI, SAOCP), and several conformity scores. The performance gains are consistent.\n\n3. The robust pinball loss integrates cleanly with existing online conformal frameworks and doesn’t require major algorithmic changes.\n\nWeaknesses:\n\n1. The paper introduces the noise robustness issue briefly, without thoroughly justifying why this is a practical concern. Adding real-world scenarios where label noise impacts conformal prediction would help clarify the significance.\n\n2. The method assumes that the noise rate $\\epsilon$ is known or at least accurately estimated.\nHowever, there is limited discussion of how sensitive the method is to errors in $\\epsilon$\nand how these errors affect the theoretical guarantees.\n\n3. The robust methold maintains an $O\\left(T^{-1 / 2}\\right)$ convergence rate even when $\\epsilon=0$, which is worse than the $O\\left(T^{-1}\\right)$ rate available to the standard online conformal method.\n\n4. A major advantage of conformal methods is their finite-sample, distribution-free guarantee.\nHowever, the robust pinball loss relies on matching expectations for both the\nloss value and its gradient (Proposition 4.1). As a result, the theoretical guarantees\nare asymptotic (e.g., convergence in expectation), and no finite-sample coverage\nguarantee is preserved. This undermines one of the foundational motivations for\nusing the conformal prediction method.", "was_revised": false, "final_justification": "", "rebuttal": "> The practical importance of noise robustness in conformal prediction [W1]\n\nThank you for the suggestion. While most supervised learning tasks assume the provided labels reflect the ground truth, this assumption is often violated in the real world. For example, in medical imaging classification [4], label noise frequently emerges from subjective interpretations—for instance, when clinicians disagree on the malignancy of skin lesions. As introduced in the related work (Appendix A), the issue of label noise has been a common challenge in machine learning research, including conformal prediction [1-7]. In this work, we show that label noise can result in overly conservative prediction sets that include too many possible outcomes, thereby reducing their practical utility in decision-making (See Proposition 3.1 and Figure 1). This highlights the practical significance of addressing label noise in online conformal prediction. We will include the task importance in Section 2 of the final version.\n\n> The effect of errors in $\\epsilon$ on the method [W2 & Q2]\n\nThank you for raising the important point. In Appendix C, we evaluated the impact of misestimated noise rate on NR-OCP. Results in Figure 4 illustrate that overestimating the noise rate results in undercoverage, while underestimation yields conservative coverage with unnecessarily large prediction sets. Moreover, a small estimation error would reduce the coverage gap. Thus, it is recommended for practitioners to use a relatively low noise rate when the noise rate cannot be accurately estimated. \n\nIn the literature of label-noise learning, many methods [8,9] leverage a small validation set of clean examples for estimating the noise rate. In real-world applications (including online settings), collecting a limited number of clean samples for noise rate estimation is often practicable. Additionally, some approaches [10,11] estimate the noise rate without requiring clean labels during training. Thus, such techniques make it reasonable to assume a known noise rate, which is widely recognized in the literature of label-noise learning [12-16].\n\nMoreover, we clarify that our method improves the performance even when the noise rate is not precisely estimated, as validated in Appendix C. To fully address this concern, we conduct an additional experiment where the noise rate is unknown and needs to be estimated. In particular, we apply an existing algorithm [8] to estimate the noise rate without access to clean data during the training of the pre-trained model. Then, we employ this estimated noise rate in our method for online conformal prediction. The experiments are conducted on CIFAR-10 dataset, using ResNet18 model with noise rate $\\epsilon\\in\\{0.1,0.2,0.3\\}$. We employ LAC score to generate prediction sets and use a constant learning rate $\\eta=0.05$. The results are shown in the table below:\n| Noise rate | Estimated Noise rate | Method   | CovGap (%) | Size |\n|------------|----------------------|----------|------------|------|\n| $\\epsilon=0.1$ | $\\hat{\\epsilon}=0.09$     | Baseline | 6.99       | 2.47 |\n|                |                     | Ours     | 0.82       | 0.94 |\n| $\\epsilon=0.2$ |  $\\hat{\\epsilon}=0.23$  | Baseline | 8.72       | 5.41 |\n|                |                     | Ours     | 1.67       | 0.98 |\n| $\\epsilon=0.3$ |  $\\hat{\\epsilon}=0.26$  | Baseline | 9.04       | 6.72 |\n|                |                     | Ours     | 2.32       | 1.15 |\n\nThe results demonstrate that our method consistently achieves much lower coverage gaps and smaller prediction sets compared to the baseline. This highlights the robustness and applicability of our method even when the noise rate is not precisely estimated. \n\n> The limitation of the slow convergence rate [W3]\n\nWe thank the reviewer for their insightful comment. As stated in Propositions 4.2 and 4.3, we prove that our robust method achieves convergence with a rate of  ($\\mathcal{O}(T^{-1/2})$), which is slightly slower than standard online CP. However, we respectfully argue that the slightly slower convergence rate of our robust method is not a critical limitation in the context of online learning, and we provide the following clarifications to address this concern. \n\nFirst, our primary contribution is to eliminate the coverage gap under noisy conditions, where the standard online conformal method fails. The robust method is specifically designed to handle noisy settings, ensuring reliable convergence to the target coverage even in the presence of noise. As shown in Figure 2, our method converges rapidly to the target coverage in practice, highlighting the robust method’s advantages in noisy environments.\n\nSecond, in online learning, the practical significance of a slightly slower convergence rate, such as $\\mathcal{O}(T^{-1/2})$, is often outweighed by the need for robustness and adaptability. The robust method’s ability to maintain consistent performance across a range of noise levels offers a substantial advantage in terms of reliability and applicability. The trade-off in convergence speed is thus justified by the method’s ability to address challenging, non-idealized settings, which aligns with the primary motivation of our work.\n\nLastly, we also emphasize that the theoretical results of convergence are presented to demonstrate the robustness and versatility of our approach, rather than to compete solely on convergence speed in idealized settings.\n\n> The method fails to provide the finite-sample coverage guarantee [W4]\n\nThank you for raising this concern. We'd like to clarify that the framework of online conformal prediction (OCP) [17-20] aims to provide **asymptotic validity** in more general, potentially non-exchangeable, online settings, while split conformal prediction provides **finite-sample marginal coverage** under exchangeability assumptions. It's important to note that online conformal prediction makes no assumption on data distribution, which makes it impossible to achieve finite-sample coverage guarantee. Specifically, OCP aims to guarantee that the coverage error $|\\frac{1}{T}\\sum_{t=1}^T1\\{Y_t\\notin\\mathcal{C}_t(X_t)\\}-\\alpha|$ converges to zero as $T\\to\\infty$, which is widely accepted in the online setting of conformal prediction. In this way, online conformal prediction can effectively handle dynamic environment where distribution shifts exist, while providing valid coverage guarantee [17].\n\n> The sample size for an accurate correction [Q1]\n\nThank you for the question. In online learning, the sample size corresponds to the time step $T$, where a larger $T$ results in more accumulated samples. Theoretically, our method's convergence rate (see Propositions 4.2 and 4.3) requires $T \\geq \\frac{1}{(1-\\epsilon)\\beta^2}$ to achieve an error ExErr($T$)$\\leq\\beta$, where $\\beta$ is an arbitrary small tolerance and $\\epsilon$ is the noise rate. Experimentally, Figure 2 demonstrates that our method achieves a negligible coverage gap at approximately 2,000 time steps (or samples) with a constant learning rate and 1,000 time steps (or samples) with a dynamic learning rate.\n\n> Generalize to class-conditional or instance-dependent settings [Q3]\n\nWe thank the reviewer for their insightful question. While our method does not directly extend to complex label noise settings, we emphasize that label noise remains a novel and underexplored challenge in conformal prediction, particularly in the online setting. As noted in Appendix A, the most relevant prior work [2] focuses solely on uniform noise in conformal prediction, only analyzing the overcoverage issue in online settings. In contrast, our work is the first to specifically tackle label noise in online conformal prediction, establishing a foundational step for future research in this area. We hope this highlights the significance of our contribution.\n\n### References\n[1] Einbinder B S, et al. Conformal prediction is robust to label noise. arXiv preprint 2022.\n\n[2] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024.\n\n[3] Sesia M, et al. Adaptive conformal classification with noisy labels. JRSSB 2024.\n\n[4] Penso C, et al. Noise-robust conformal prediction for medical image classification. International Workshop on Machine Learning in Medical Imaging. 2024.\n\n[5] Feldman S, et al. Robust conformal prediction using privileged information. NIPS 2024.\n\n[6] Penso C, et al. Estimating the Conformal Prediction Threshold from Noisy Labels. arXiv preprint 2025.\n\n[7] Bortolotti T, et al. Noise-Adaptive Conformal Classification with Marginal Coverage. arXiv preprint 2025.\n\n[8] Li X, et al. Provably end-to-end label-noise learning without anchor points. ICML 2021.\n\n[9] Xia X, et al. Are anchor points really indispensable in label-noise learning? NIPS 2019.\n\n[10] Yu X, et al. An efficient and provable approach for mixture proportion estimation using linear independence assumption. CVPR 2018.\n\n[11] Liu T, et al. Classification with noisy labels by importance reweighting. TPAMI 2015.\n\n[12] Han B, et al. Co-teaching: Robust training of deep neural networks with extremely noisy labels. NIPS 2018\n\n[13] Wei H, et al. Combating noisy labels by agreement: A joint training method with co-regularization. CVPR 2020.\n\n[14] Yu X, et al. How does disagreement help generalization against label corruption? ICML 2019.\n\n[15] Xia X, et al. Sample selection with uncertainty of losses for learning with noisy labels[J]. arXiv preprint 2021.\n\n[16] Xia X, et al. Combating noisy labels with sample selection by mining high-discrepancy examples. CVPR 2023.\n\n[17] Gibbs I, et al. Adaptive conformal inference under distribution shift. NIPS 2021.\n\n[18] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023.\n\n[19] Gibbs I, et al. Conformal inference for online prediction with arbitrary distribution shifts. JMLR 2024.\n\n[20] Angelopoulos A N, et al. Online conformal prediction with decaying step sizes. ICML 2024."}, {"review_id": "TfymXo7h1y", "reviewer": "Reviewer_ZVis", "summary": "This paper looks at the online conformal prediction problem.  Arbitrary points $(X_t, Y_t) \\in \\mathcal{X} \\times [K]$ arrive one by one, and the goal of the algorithm is, upon seeing $X_t$ to provide a confidence set $C_t \\subseteq [K]$ for $Y_t$, such that the sequence of confidence sets achieves coverage $1 - \\alpha$ on average over the whole sequence, i.e. \n$$ \\lim_{T \\rightarrow \\infty} \\frac{1}{T}\\sum_{i = 1}^T \\mathbb{P} [ Y_t \\in C_t ] \\rightarrow 1- \\alpha. $$\nOnce the algorithm outputs $C_t$, the true $Y_t$ is revealed to the algorithm.\n\nThey study this problem under the model of uniform label noise.  That is, instead of seeing $Y_t$, the algorithm is shown $\\tilde{Y}_t$, where $\\tilde{Y}_t$ is $Y_t$ with probability $1 - \\varepsilon$ and $\\tilde{Y} \\sim \\text{Unif}[K]$ with probability $\\varepsilon$, for a known value of $\\varepsilon$.  The goal is still to provide coverage with respect to the original $Y_t$, rather than the observed $\\tilde{Y}_t$.  \n\nThey show that existing online conformal prediction methods do not meet this guarantee. Existing online conformal methods work by estimating the top $1 - \\alpha$ quantile of the score function, and outputting the interval from 0 to this quantile.  However, the quantiles of the scores computed from the observed $\\tilde{Y}_t$ are not the same as the quantiles of the scores computed from the true $Y_t$, and therefore will achieve coverage over the $\\tilde{Y}_t$ and not necessarily the $Y_t$s.\n  To tackle this problem, they design a new loss function called the robust pinball loss, that allows them to estimate quantiles of the data robust to the known noise distribution.  This allows them to estimate the quantile of the scores if they had been computed according to the $Y_t$s.", "questions": "- Line 84: Are the datapoints $(X_t, Y_t)$ drawn i.i.d., or is the whole sequence drawn from a joint distribution?\n- Line 108: Why is the correct measure to consider the absolute value of the expected deviation rather than the expectation of the absolute deviation?  That is, why is \n$$\\text{ExErr}(T) = \\left| \\frac{1}{T} \\mathbb{P} [Y_t \\notin C_t(X_t) ] - \\alpha \\right|$$\nrather than \n$$\\text{ExErr}(T) = \\frac{1}{T} \\left|\\mathbb{P} [Y_t \\notin C_t(X_t) ] - \\alpha \\right|$$?\n\n- Line 177: \"This assumption is practical as the noise rate can be estimated from historical data\": is this true when you are never given access to the $Y_t$?  Or does this assume that for the historical data you have access to the true $Y_t$?  If this can be estimated without access to the true $Y_t$, is there a way to do this on the fly on the prefix of the stream, and then use this value of $\\varepsilon$ on the suffix of the stream?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 3, "strengths_and_weaknesses": "**Strengths** \\\nIt is nice that the formulation does not impose any structure on the score function.  This gives an elegant way to push forward the error from the label noise to the error in the score function.  \n\n**Weaknesses**\nI think this model requires more justification.  Why is it a good objective to consider error of predicting the $Y_t$ rather than the $\\tilde{Y}_t$?  \n\nI would interpret the online model as being one where the $\\tilde{Y}_t$ are thought of as being both the training examples and the test examples.  In that interpretation, it makes sense the coverage of a predictor should also be measured against the $\\tilde{Y}_t$ (test distribution) as well, which standard online conformal prediction would do out of the box.  Why does it make sense to instead optimize the coverage over the $Y_t$?  Can this coverage can even be estimated from samples? If the trained regression model is not very accurate, is it possible to know whether the uncertainty arises from the regression model being a bad fit, or whether it is due to noise in the labels? (See the example given below.)  Could you provide an example where it would be useful to have coverage against the unknown $Y_t$, which are never revealed to you?\n\nThe assumption that the noise distribution is known is very strong, since the motivation of conformal prediction (and especially online conformal prediction) to design distribution-free methods.  I appreciate that the authors acknowledge this in their conclusion, and hope that this result is a first step toward removing this strong assumption.  However, I am not convinced that this is actually possible.  \n\nThe most general form of such a result might be to achieve this in the setting of distributionally robust optimization: where the noise $\\tilde{Y}$ can be drawn from an arbitrary unknown distribution.   For this (strong) model of noise robustness, I believe that you can construct the following simple lower bound.  Suppose you are seeing $X_t = 0$ which are all the same, and $\\tilde{Y}_t$ that are $\\tilde{Y}_t = 1$ with probability $1 - \\varepsilon$, and $\\tilde{Y}_t \\sim \\text{Unif}[K]$ with probability $\\varepsilon$.  Then from these samples, it is impossible to know whether it is the case that \n- $Y_t = 1$ deterministically, and the label noise is uniform \n- OR $Y_t = 1$ w.p. $1 - \\frac{\\varepsilon}{1 - \\varepsilon}$, $Y_t \\sim \\text{Unif}[K]$ w.p. $\\frac{\\varepsilon}{1 - \\varepsilon}$, and the noise is $\\tilde{Y} = 1$ deterministically.  \nSuppose the noise level satisfies $\\alpha/K < \\varepsilon < \\alpha$.  Then in the first case, there exists a a conformal set of size 1, containing just the label 1, that captures $Y_t = 1$ with probability $\\ge 1 - \\alpha$.  But in the second case, we require a conformal set of bigger size to capture $1 - \\alpha$ of $Y_t$.  This suggests to me that it is not possible to design such a method for unknown noise distributions.  \nIf this is true, then this means that such a model is restricted to providing results for settings where the noise distribution is known, which seems like a very strong assumption.  Is there a more benign class of noise distributions that you hope can be targeted?  \n\nBecause of this modeling issue, I have given the submission a low score in significance.  Please let me know if there is some modeling consideration that I have not considered or misunderstood.  \n\nPlease see \"questions\" for more detailed technical questions, mostly related to the modeling of this problem.", "was_revised": true, "final_justification": "I appreciate the authors thoughtful and thorough responses to my concerns.  I am satisfied with their justification of the known error rate, and the model where coverage is measure with respect to the unseen $Y$ values.  Thus I raise my score to 4: weak accept. \n\nThe main thing standing in the way of my raising the score beyond this is that I am still not convinced that these ideas can be extended beyond this very stylized error model.  For example, if the noise is not uniform, I believe a similar strategy would require a method to raise the threshold so much that the prediction sets would be very large and uninformative.  I see this as a fundamental drawback, as in practice, we don't expect noise to be drawn from a known distribution that is independent of the data.", "rebuttal": "We sincerely thank the reviewer for the constructive feedback. We reply to these concerns point by point. (**W** for weakness, **Q** for question)\n\n> Justification for optimizing the coverage over clean labels $Y_t$ [W1]\n\nThank you for this insightful comment. The issue of label noise has been a common challenge in machine learning research, including conformal prediction [1–7] and online learning [8,9]. In conformal prediction, a line of work [1–7] aim to provide coverage guarantee with respect to clean labels: $\\mathbb{P}\\\\{Y\\in\\mathcal{C}\\_{noisy}(X)\\\\}\\geq1-\\alpha$, such as Corollary 6 in [2], Theorem 2 in [3], and Theorem 3.5 in [6]. Similarly, in online learning, prior work [8,9] investigate the setting where the learner observes noisy labels but still seeks to minimize the error with respect to the true labels, providing upper bounds on: $\\mathbb{E}_{(X,Y)}[1\\\\{f(X)\\neq Y\\\\}]$, such as Theorem 3 of [8] and Theorem 1 of [9]. In line with these efforts, our work is designed to provide coverage guarantees for the true labels, rather than the observed noisy labels.\n\nTo demonstrate the practical necessity for this purpose, let us consider an online fraud detection system that classifies transactions as either fraudulent or legitimate. Due to human oversight or ambiguity in spending behavior, the training labels may occasionally be incorrect, leading to label noise, for instance, legitimate transactions mislabeled as fraudulent. If a conformal predictor guarantees coverage only against these noisy observed labels $\\tilde{Y}_t$, then its prediction sets may fail to cover the true transaction status $Y_t$. This could harm the reliability of the system, resulting in unnecessary account freezes or missed fraud. We hope this clarifies the practical significance of providing guarantee for true labels.\n\n> Assumption of knowing the noise distribution [W2, Q3]\n\nThank you for this thoughtful comment. In this work, we focus on the setting of uniform label noise as a first step towards noise robustness of online conformal prediction. Then, our assumption is that the noise rate can be estimated from the historical data in Section 2, which is widely recognized in the literature of label-noise learning [10-14]. In particular, some methods [15,16] can estimate the noise rate with a small subset of clean label data, while others [17,18] conduct this estimation directly during training without access to clean labels. These techniques complement our method, making it reasonable to assume a known noise rate. \n\nMoreover, we clarify that our method improves the performance even when the noise rate is not precisely estimated, as validated in Appendix C. To fully address this concern, we conduct an additional experiment where the noise rate is unknown and needs to be estimated. In particular, we apply an existing algorithm [17] to estimate the noise rate without access to clean data during the training of the pre-trained model. Then, we employ this estimated noise rate in our method for online conformal prediction. The experiments are conducted on CIFAR-10 dataset, using ResNet18 model with noise rate $\\epsilon\\in\\{0.1,0.2,0.3\\}$. We employ LAC score to generate prediction sets and use a constant learning rate $\\eta=0.05$. The results are shown in the table below:\n| Noise rate | Estimated Noise rate | Method   | CovGap (%) | Size |\n|------------|----------------------|----------|------------|------|\n| $\\epsilon=0.1$ | $\\hat{\\epsilon}=0.09$     | Baseline | 6.99       | 2.47 |\n|                |                     | Ours     | 0.82       | 0.94 |\n| $\\epsilon=0.2$ |  $\\hat{\\epsilon}=0.23$  | Baseline | 8.72       | 5.41 |\n|                |                     | Ours     | 1.67       | 0.98 |\n| $\\epsilon=0.3$ |  $\\hat{\\epsilon}=0.26$  | Baseline | 9.04       | 6.72 |\n|                |                     | Ours     | 2.32       | 1.15 |\n\nThe results demonstrate that our method consistently achieves much lower coverage gap and smaller prediction sets compared to the baseline. This highlights the robustness and applicability of our method even when the noise rate is not precisely estimated. \n\n> The distributional assumption of data points [Q1]\n\nFollowing the framework of online conformal prediction [19-21], we do not assume that the data samples are i.i.d. sampled. Therefore, the data points can be drawn from an arbitrary distribution.\n\n> Measure of the expected deviation [Q2]\n\nThank you for raising the question. This work aligns with prior research in online conformal prediction, which provides theoretical guarantees with respect to this metric—for example, in the discussion following Proposition 4.1 in [19], Theorem 6 in [20], and Theorem C.3 in [21].\n\n### References\n[1] Einbinder B S, et al. Conformal prediction is robust to label noise. arXiv preprint 2022.\n\n[2] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024.\n\n[3] Sesia M, et al. Adaptive conformal classification with noisy labels. JRSSB 2024.\n\n[4] Penso C, et al. Noise-robust conformal prediction for medical image classification. International Workshop on Machine Learning in Medical Imaging. 2024.\n\n[5] Feldman S, et al. Robust conformal prediction using privileged information. NIPS 2024.\n\n[6] Penso C, et al. Estimating the Conformal Prediction Threshold from Noisy Labels. arXiv preprint 2025.\n\n[7] Bortolotti T, et al. Noise-Adaptive Conformal Classification with Marginal Coverage. arXiv preprint 2025.\n\n[8] Nagarajan Nataraja, et al. Learning with noisy labels. NIPS 2013.\n\n[9] Changlong Wu, et al. Information-theoretic limits of online classification with noisy labels. NIPS 2024.\n\n[10] Han B, et al. Co-teaching: Robust training of deep neural networks with extremely noisy labels. NIPS 2018\n\n[11] Wei H, et al. Combating noisy labels by agreement: A joint training method with co-regularization. CVPR 2020.\n\n[12] Yu X, et al. How does disagreement help generalization against label corruption? ICML 2019.\n\n[13] Xia X, et al. Sample selection with uncertainty of losses for learning with noisy labels[J]. arXiv preprint 2021.\n\n[14] Xia X, et al. Combating noisy labels with sample selection by mining high-discrepancy examples. CVPR 2023.\n\n[15] Liu T, et al. Classification with noisy labels by importance reweighting. TPAMI 2015.\n\n[16] Yu X, et al. An efficient and provable approach for mixture proportion estimation using linear independence assumption. CVPR 2018.\n\n[17] Li X, et al. Provably end-to-end label-noise learning without anchor points. ICML 2021.\n\n[18] Xia X, et al. Are anchor points really indispensable in label-noise learning? NIPS 2019.\n\n[19] Gibbs I, et al. Adaptive conformal inference under distribution shift. NIPS 2021.\n\n[20] Gibbs I, et al. Conformal inference for online prediction with arbitrary distribution shifts. JMLR 2024.\n\n[21] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023."}, {"review_id": "vD4PgwqQem", "reviewer": "Reviewer_E9Fq", "summary": "This paper studies online conformal prediction under uniform label noise. In online conformal prediction, given data sampled from a joint distribution that arrives in a sequential order, the goal is to compute a prediction set for each step such that the average coverage rate reaches the desired level. In the uniform label noise setting, with a fixed probability epsilon, the label of a data point is replaced by a label sampled uniformly at random from the label space. \n\nIn this paper, they first show that under uniform label noise, the vanilla adaptive conformal inference (ACI) method has a coverage gap, which is not necessarily diminishing. This shows that the ACI may have over-coverage or under-coverage depending on the expected size of the prediction sets.\n\nThey then propose a modified ACI with robust pinball loss. They show that this new conformal method achieves a diminishing expected coverage error and empirical coverage error with convergence rate O(T^{-1/2}) in both constant and dynamic learning rate settings. \n\nMoreover, for dynamic learning rate, by choosing a decaying learning rate, their method can achieve an O(T^{1/2}) regret bound. \nThey evaluate their method on CIFAR-10 and ImageNet datasets and show that their method achieves the desired coverage with diminishing coverage gap while the baseline method has a coverage gap.", "questions": "1. A small question about assumptions 2.1 and 2.2: how do the results depend on these assumptions? Would a bounded score and threshold be enough?\n\n2. Is there any connection between proposition 3.1 and the results for conservative coverage in previous work by Einbinder et al, 2024? For example, can we observe their results from the expected size of the prediction sets by adding the same distributional assumptions here?\n\n3. Does Proposition 4.1 fail to hold under other label noise settings? If so, is this the primary limitation preventing the extension of the robust pinball loss to more general forms of label noise?", "limitations": "Yes, the authors mention that the current method is limited to uniform label noise with a known noise rate. They also mention the extension to other noise models with fewer assumptions as one future direction.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper shows that the vanilla ACI method may provide conservative prediction sets with over-coverage under the uniform label noise. Their bound relates the coverage gap to the expected size of the prediction sets. Although previous work by Einbinder, Feldman, Bates, Angelopoulos, Gendler, and Romano (2024) observes that ACI obtains conservative prediction sets, they require distributional assumptions that the noisy score distribution stochastically dominates the clean score distribution. While this paper does not require distributional assumptions.\n\n2.\tThey develop a new conformal method by using robust pinball loss and show that this method has a diminishing coverage gap with rate O(T^{-1/2}). They show that in expectation, the robust pinball loss under label noise is the same as the pinball loss for clean data and also has the same expected gradient as the pinball loss.\n\n3.\tTheir experiments show that the proposed method achieves the desired coverage with diminishing coverage gap on real-world datasets, which validates their theoretical results.\n\nOverall, I think this paper provides very interesting observations and new conformal methods for online conformal prediction under uniform label noise.", "was_revised": true, "final_justification": "After reviewing the rebuttal, I would like to maintain my score and express my support for accepting this paper. As other reviewers have pointed out, the paper relies on the assumption that the noise rate is known. While I agree that this assumption is strong, I believe the paper provides valuable insights and may inspire future work that explores more general noise settings.", "rebuttal": "Thank you for the insightful review. We provide point-by-point responses to these questions. (**W** for weakness, **Q** for question)\n\n> Assumptions in Section 2 [Q1]\n\nThank you for the question. A bounded score and threshold are sufficient to achieve the desired coverage guarantees. The specific upper bound in these assumptions primarily impacts the constant in the coverage rate, but does not fundamentally alter the coverage guarantee of the method.\n\n> Connection between proposition 3.1 and the results by Einbinder et al, 2024 [Q2]\n\nThank you for the insightful question. There is indeed a connection between Proposition 3.1 and the results for conservative coverage in [1]. In particular, Corollary 6 in [1] relies on the assumption that $\\mathcal{C}_{noisy}$ contains the most likely (correct) labels. In this case, the model is effectively accurate, and the prediction sets remain small. Our Proposition 3.1 shows that when the prediction sets are small, label noise can result in over-coverage of prediction sets\n$$\\frac{1}{T}\\sum\\_{t=1}^T1\\\\{Y_t\\notin\\mathcal{C}(X_t)\\\\}\\leq\\alpha$$\nwhich aligns with the conclusion from [1].\n\n> Limitation of Proposition 4.1 [Q3]\n\nThank you for your thoughtful question. Proposition 4.1 is derived under the assumption of a uniform label noise, and it may not hold in more general label noise settings. This is indeed a primary limitation in extending the robust pinball loss to handle more complex label noise. We believe that extending our framework to handle more general label noise, such as noise transition matrix, is a promising avenue for future research.\n\n### References\n[1] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024."}, {"review_id": "LnoV0yD0B2", "reviewer": "Reviewer_SDzf", "summary": "This paper proposes a new online conformal prediction method designed to be robust against uniform label noise, based on minimizing the robust pinball loss. The authors provide convergence analysis under both constant and dynamic learning rates. Extensive experiments demonstrate the effectiveness of the proposed approach, particularly when the noise rate is known.", "questions": "Aside from the weaknees, I have two minor questions.\n\nQ1: In Figure 2 (C), the method based on clean data is undercover, can the author explain this?\n\nQ2: In Proposition 3.1., the result seems counterintuitive: if the prediction set $C_t(X_t)$ for each $t$ is infinite, then the left term should be $\\alpha$ as the miscoverage is $0$, and the right term is $-\\infty$ since the prediction size is infinity. Then it leads to $\\alpha\\leq-\\infty$, which is strange.", "limitations": "yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: The paper introduces a novel approach for online conformal prediction under label noise, with rigorous theoretical analysis supporting the proposed method.\n\nWeakness 1: The primary limitation of the paper is its reliance on the assumption that the noise rate $\\epsilon$ is known. In practice, this information is rarely available. The authors should at least propose a method for estimating the noise rate and provide empirical results using the estimated values. Without this, the practical applicability of the method is significantly limited.\n\nWeakness 2: The main idea is highly specific to the noise mechanism to make it possible for the computation of the distribution of score function. This makes the proposed approach restricted to the uniform label noise setting, lacking generalization to other mechanism.", "was_revised": true, "final_justification": "I raise my score from 3 to 4 as the author provides the practical implementation of their approach by using an estimated noise rate.", "rebuttal": "We sincerely appreciate the reviewer’s constructive suggestions and address the raised issues below. (**W** for weakness, **Q** for question)\n\n> Assumption on a known noise rate [W1]\n\nThank you for highlighting the concern. In the literature of label-noise learning, many methods [1,2] are proposed to leverage a small validation set of clean examples for estimating the noise ratio. Additionally, some approaches [3,4] estimate the noise rate without requiring clean labels during training. Such techniques make it reasonable to assume a known noise rate, which is widely recognized in the literature of label-noise learning [5-9].\n\nMoreover, we clarify that our method improves the performance even when the noise rate is not precisely estimated, as validated in Appendix C. To fully address this concern, we conduct an additional experiment where the noise rate is unknown and needs to be estimated. In particular, we apply an existing algorithm [3] to estimate the noise rate without access to clean data during the training of the pre-trained model. Then, we employ this estimated noise rate in our method for online conformal prediction. The experiments are conducted on CIFAR-10 dataset, using ResNet18 model with noise rate $\\epsilon\\in\\{0.1,0.2,0.3\\}$. We employ LAC score to generate prediction sets and use a constant learning rate $\\eta=0.05$. The results are shown in the table below:\n| Noise rate | Estimated Noise rate | Method   | CovGap (%) | Size |\n|------------|----------------------|----------|------------|------|\n| $\\epsilon=0.1$ | $\\hat{\\epsilon}=0.09$     | Baseline | 6.99       | 2.47 |\n|                |                     | Ours     | 0.82       | 0.94 |\n| $\\epsilon=0.2$ |  $\\hat{\\epsilon}=0.23$  | Baseline | 8.72       | 5.41 |\n|                |                     | Ours     | 1.67       | 0.98 |\n| $\\epsilon=0.3$ |  $\\hat{\\epsilon}=0.26$  | Baseline | 9.04       | 6.72 |\n|                |                     | Ours     | 2.32       | 1.15 |\n\nThe results demonstrate that our method consistently achieves much lower coverage gap and smaller prediction sets compared to the baseline. This highlights the robustness and applicability of our method even when the noise rate is not precisely estimated. \n\n> Lack generalization to other noise mechanisms [W2]\n\nThank you for highlighting this important point. We would like to emphasize that label noise is still a novel and underexplored challenge in conformal prediction, particularly in the online setting. As noted in Appendix A, the most relevant prior work [10] focuses solely on uniform noise in conformal prediction, only analyzing the overcoverage issue in online settings. In contrast, our work stands out as the first to specifically tackle label noise in online conformal prediction. While the current method is specific to uniform noise, it opens the door for extensions to more general noise mechanisms such as class-conditional label noise. Designing such extensions is a promising and important direction for future research. We hope this clarifies the significance of our work as a starting point in the field of noise-robust online conformal prediction.\n\n> SAOCP on clean data is undercover [Q1]\n\nThank you for pointing this out. The under-coverage observed in Figure 2 $($C$)$ is a characteristic of the SAOCP method. A similar phenomenon is also noted in Tables 1 and 2 of the SAOCP manuscript [6], where the final coverage is around 0.88, which is slightly lower than the target coverage of 0.9.\n\n> The counterintuitive results in Proposition 3.1 [Q2]\n\nThank you for the insightful question. In this work, we focus on online conformal prediction in multi-class classification (with K classes), where the maximum set size is the class number: $|\\mathcal{C}_t(X_t)| \\leq K$. In this online setting, the set size cannot always remain the maximum value $K$ for each time step $t$. This is because the threshold will be updated and decreased by online gradient descent at the next time step $t+1$, if the prediction set contains the true label at the time step $t$ (See Eq.(2)). Consequently, the prediction set size will be decreased until the true label is excluded. Therefore, the set size cannot always be infinite or $K$ for each t in online conformal prediction, so it would not lead to the counterintuitive results.\n\n### References\n[1] Liu T, et al. Classification with noisy labels by importance reweighting. TPAMI 2015.\n\n[2] Yu X, et al. An efficient and provable approach for mixture proportion estimation using linear independence assumption. CVPR 2018.\n\n[3] Li X, et al. Provably end-to-end label-noise learning without anchor points. ICML 2021.\n\n[4] Xia X, et al. Are anchor points really indispensable in label-noise learning? NIPS 2019.\n\n[5] Han B, et al. Co-teaching: Robust training of deep neural networks with extremely noisy labels. NIPS 2018\n\n[6] Wei H, et al. Combating noisy labels by agreement: A joint training method with co-regularization. CVPR 2020.\n\n[7] Yu X, et al. How does disagreement help generalization against label corruption? ICML 2019.\n\n[8] Xia X, et al. Sample selection with uncertainty of losses for learning with noisy labels[J]. arXiv preprint 2021.\n\n[9] Xia X, et al. Combating noisy labels with sample selection by mining high-discrepancy examples. CVPR 2023.\n\n[10] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024.\n\n[11] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023."}]

Author rebuttal:

Meta-review: This paper investigates the robustness of online conformal prediction methods in the presence of uniform label noise. The authors show that standard online conformal algorithms, including ACI and its variants, can suffer from systematic coverage distortion when labels are noisy, due to biased gradient updates caused by corrupted supervision. To mitigate this issue, they propose a robust pinball loss that serves as an unbiased estimator of the true clean pinball loss.

I thank the authors for their thorough responses and additional experimental results. Based on the reviewers' discussions (including those with the authors) and my own evaluation, I believe the results of this paper are novel and of interest to the ICML community. While some reviewers expressed concerns that the work may be quite limited to this specific noise mechanism, I believe that some assumption about the noise is indeed necessary, and uniformity is a reasonable choice. However, in my opinion, the assumption that the noise power is known precisely might be too strong and somewhat limiting. Therefore, I would recommend that the authors explore whether knowing only an upper bound on the variance would suffice for their algorithms and results.
Decision: Accept (poster)