Exploring the Noise Robustness of Online Conformal Prediction

We sincerely appreciate the reviewer’s constructive suggestions and address the raised issues below. (W for weakness, Q for question)

Assumption on a known noise rate [W1]

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

Moreover, 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:

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

Lack generalization to other noise mechanisms [W2]

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

SAOCP on clean data is undercover [Q1]

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

The counterintuitive results in Proposition 3.1 [Q2]

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

References

[1] Liu T, et al. Classification with noisy labels by importance reweighting. TPAMI 2015.

[2] Yu X, et al. An efficient and provable approach for mixture proportion estimation using linear independence assumption. CVPR 2018.

[3] Li X, et al. Provably end-to-end label-noise learning without anchor points. ICML 2021.

[4] Xia X, et al. Are anchor points really indispensable in label-noise learning? NIPS 2019.

[5] Han B, et al. Co-teaching: Robust training of deep neural networks with extremely noisy labels. NIPS 2018

[6] Wei H, et al. Combating noisy labels by agreement: A joint training method with co-regularization. CVPR 2020.

[7] Yu X, et al. How does disagreement help generalization against label corruption? ICML 2019.

[8] Xia X, et al. Sample selection with uncertainty of losses for learning with noisy labels[J]. arXiv preprint 2021.

[9] Xia X, et al. Combating noisy labels with sample selection by mining high-discrepancy examples. CVPR 2023.

[10] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024.

[11] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023.

Thank you for your prompt feedback and valuable suggestion. In the final version, we will include the performance of the proposed method with estimated noise rates in all main figures and tables. We believe this would enhance the significance and contribution of this work by highlighting its practical applicability.

Thank you for the insightful review. We provide point-by-point responses to these questions. (W for weakness, Q for question)

Assumptions in Section 2 [Q1]

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

Connection between proposition 3.1 and the results by Einbinder et al, 2024 [Q2]

Thank 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 $\frac{1}{T}\sum\_{t=1}^T1\\{Y_t\notin\mathcal{C}(X_t)\\}\leq\alpha$ which aligns with the conclusion from [1].

Limitation of Proposition 4.1 [Q3]

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

References

[1] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024.

We sincerely thank the reviewer for the constructive feedback. We reply to these concerns point by point. (W for weakness, Q for question)

Justification for optimizing the coverage over clean labels $Y_t$ [W1]

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

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

Assumption of knowing the noise distribution [W2, Q3]

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

Moreover, 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:

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

The distributional assumption of data points [Q1]

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

Measure of the expected deviation [Q2]

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

References

[1] Einbinder B S, et al. Conformal prediction is robust to label noise. arXiv preprint 2022.

[2] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024.

[3] Sesia M, et al. Adaptive conformal classification with noisy labels. JRSSB 2024.

[4] Penso C, et al. Noise-robust conformal prediction for medical image classification. International Workshop on Machine Learning in Medical Imaging. 2024.

[5] Feldman S, et al. Robust conformal prediction using privileged information. NIPS 2024.

[6] Penso C, et al. Estimating the Conformal Prediction Threshold from Noisy Labels. arXiv preprint 2025.

[7] Bortolotti T, et al. Noise-Adaptive Conformal Classification with Marginal Coverage. arXiv preprint 2025.

[8] Nagarajan Nataraja, et al. Learning with noisy labels. NIPS 2013.

[9] Changlong Wu, et al. Information-theoretic limits of online classification with noisy labels. NIPS 2024.

[10] Han B, et al. Co-teaching: Robust training of deep neural networks with extremely noisy labels. NIPS 2018

[11] Wei H, et al. Combating noisy labels by agreement: A joint training method with co-regularization. CVPR 2020.

[12] Yu X, et al. How does disagreement help generalization against label corruption? ICML 2019.

[13] Xia X, et al. Sample selection with uncertainty of losses for learning with noisy labels[J]. arXiv preprint 2021.

[14] Xia X, et al. Combating noisy labels with sample selection by mining high-discrepancy examples. CVPR 2023.

[15] Liu T, et al. Classification with noisy labels by importance reweighting. TPAMI 2015.

[16] Yu X, et al. An efficient and provable approach for mixture proportion estimation using linear independence assumption. CVPR 2018.

[17] Li X, et al. Provably end-to-end label-noise learning without anchor points. ICML 2021.

[18] Xia X, et al. Are anchor points really indispensable in label-noise learning? NIPS 2019.

[19] Gibbs I, et al. Adaptive conformal inference under distribution shift. NIPS 2021.

[20] Gibbs I, et al. Conformal inference for online prediction with arbitrary distribution shifts. JMLR 2024.

[21] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023.

The practical importance of noise robustness in conformal prediction [W1]

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

The effect of errors in $\epsilon$ on the method [W2 & Q2]

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

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

Moreover, 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:

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 is not precisely estimated.

The limitation of the slow convergence rate [W3]

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

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

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

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

The method fails to provide the finite-sample coverage guarantee [W4]

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

The sample size for an accurate correction [Q1]

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

Generalize to class-conditional or instance-dependent settings [Q3]

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

References

[1] Einbinder B S, et al. Conformal prediction is robust to label noise. arXiv preprint 2022.

[2] Einbinder B S, et al. Label noise robustness of conformal prediction. JMLR 2024.

[3] Sesia M, et al. Adaptive conformal classification with noisy labels. JRSSB 2024.

[4] Penso C, et al. Noise-robust conformal prediction for medical image classification. International Workshop on Machine Learning in Medical Imaging. 2024.

[5] Feldman S, et al. Robust conformal prediction using privileged information. NIPS 2024.

[6] Penso C, et al. Estimating the Conformal Prediction Threshold from Noisy Labels. arXiv preprint 2025.

[7] Bortolotti T, et al. Noise-Adaptive Conformal Classification with Marginal Coverage. arXiv preprint 2025.

[8] Li X, et al. Provably end-to-end label-noise learning without anchor points. ICML 2021.

[9] Xia X, et al. Are anchor points really indispensable in label-noise learning? NIPS 2019.

[10] Yu X, et al. An efficient and provable approach for mixture proportion estimation using linear independence assumption. CVPR 2018.

[11] Liu T, et al. Classification with noisy labels by importance reweighting. TPAMI 2015.

[12] Han B, et al. Co-teaching: Robust training of deep neural networks with extremely noisy labels. NIPS 2018

[13] Wei H, et al. Combating noisy labels by agreement: A joint training method with co-regularization. CVPR 2020.

[14] Yu X, et al. How does disagreement help generalization against label corruption? ICML 2019.

[15] Xia X, et al. Sample selection with uncertainty of losses for learning with noisy labels[J]. arXiv preprint 2021.

[16] Xia X, et al. Combating noisy labels with sample selection by mining high-discrepancy examples. CVPR 2023.

[17] Gibbs I, et al. Adaptive conformal inference under distribution shift. NIPS 2021.

[18] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023.

[19] Gibbs I, et al. Conformal inference for online prediction with arbitrary distribution shifts. JMLR 2024.

[20] Angelopoulos A N, et al. Online conformal prediction with decaying step sizes. ICML 2024.

Thank you for the detailed feedback. We are glad that some earlier concerns have been effectively addressed during our discussion. Below, we provide an in-depth response to the remaining points.

1. How the estimation error affects the coverage.

Thank you for highlighting the concern, also raised by Reviewers ZVis and SDzf. As noted in our response to W2&Q2, we can leverage established techniques from label-noise learning to estimate the noise rate effectively. In the rebuttal, we presented experiments with estimated noise rates demonstrating the practicality of this approach, which has addressed the concerns of Reviewers ZVis and SDzf. We agree that noise rate estimation may introduce uncertainty, potentially causing a coverage gap in conformal prediction. In Appendix C, we empirically evaluated the impact of misestimated noise rates on NR-OCP, showing that smaller estimation errors result in reduced coverage gaps.

Here, we provide a theoretical analysis to explain this observation. Suppose the true noise rate is $\epsilon$, and the estimated noise rate is $\hat{\epsilon}$. For pinball loss $l_{1-\alpha}(\cdot,\cdot)$, we denote

We employ the following decomposition:

Azuma–Hoeffding inequality establishes that part (a) and (b) converge to zero with rate $\mathcal{O}(T^{-1/2})$, and part (d) achieves a convergence rate of $\mathcal{O}(T^{-1})$ following standard online conformal prediction theory. Then, we derive a bound for part (c):

Now assume that $\hat{\epsilon}=\epsilon+\Delta$. Then, we have

Therefore, we can conclude that

This result shows that a larger estimation error, $\Delta$, increases the coverage gap, consistent with our empirical observations. The theoretical analysis clearly illustrates how the estimation error impacts coverage, enhancing the understanding of our method in practical scenarios. Thank you again for the feedback, and we believe the additional analysis largely improves the quality and comprehensiveness of this work.

2. Loss of finite-sample guarantees

We thank the reviewer for noting this limitation. We clarify that the asymptotic coverage guarantees are inherent to standard online conformal prediction (OCP) and not introduced by our work. Specifically, even with the clean pinball loss (assuming access to clean labels), standard online CP provides only asymptotic coverage in the online setting. This is a well-known property of OCP [1-4], and our robust pinball loss does not alter this. In particular, we can check the proof sketch of Prop. 4.2:

• Part (a) quantifies the deviation between the gradients of the robust and clean pinball losses. It converges to zero at a rate of $\mathcal{O}(T^{-1/2})$, ensuring our method addresses the problem of label noise.
• Part (b) leverages standard results from online CP, which yield asymptotic coverage guarantees with a convergence rate of $\mathcal{O}(T^{-1})$, as shown in prior work [1,2].

In this work, we aim to address the label noise issue in OCP, which inherently provides only asymptotic guarantees. While exploring finite-sample guarantees for OCP is a promising future direction, this does not diminish the significance of our contributions in this work.