REVIEW 2 major objections 4 minor 1 cited by
Conformal Prediction of Classifiers with Many Classes based on Noisy Labels
T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Noisy-label conformal prediction can be calibrated from noisy labels alone, with a finite-sample correction independent of the number of classes $k$, so coverage guarantees survive at large scale.
desk verdict Useful empirical method with an honest comparison to prior work, but the k-independent coverage bound is unsupported because Lemma 4 misapplies DKW. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the coverage function $F(q)=p(S(x,y)\le q)$, defined for clean labels, noisy labels, and uniformly random labels. The noise model gives the mixture $F^n(q)=(1-\epsilon)F^c(q)+\epsilon F^r(q)$, which the algorithm inverts as $\hat F^c(q)=(\hat F^n(q)-\epsilon \hat F^r(q))/(1-\epsilon)$, estimating $\hat F^n$ from the noisy calibration scores and $\hat F^r$ from average prediction-set sizes $|C_q(x_i)|/k$. Theorem 5's guarantee is carried by a DKW-based uniform bound on $|\hat F^c(q)-F^c(q)|$ that produces $\Delta$, after which the standard conformal quantile argument applies.
What would settle it
For a fixed synthetic score distribution, compute the actual tail probability of $\sup_q |\hat F^r(q)-F^r(q)|$ over many noisy calibration sets of size $n$ and compare it to the DKW bound $2\exp(-2nh^2\Delta^2)$ used in Lemma 4; a counterexample where the empirical tail exceeds the bound would invalidate Theorem 5.
Extended reading notes
Core claim
Under the uniform noise model $p(\tilde y=j\mid y=i)=(1-\epsilon)\mathbf{1}\{i=j\}+\epsilon/k$, the paper establishes a finite-sample coverage guarantee for conformal prediction on noisy calibration data: choose a threshold $q$ with $\hat F^c(q)\ge 1-\alpha+\Delta$, where $\Delta=\sqrt{\log(4/\delta)/(2nh^2)}$ and $h=(1-\epsilon)/(1+\epsilon)$; then with probability at least $1-\delta$ over the noisy calibration set, the clean-label coverage satisfies $p(y\in C_q(x))\ge 1-\alpha$. The correction term $\Delta$ is independent of the class count $k$, which is the paper's main distinguishing result relative to earlier noisy-label conformal guarantees. The same framework extends to general known invertible noise matrices through the trace identity $F^c(q)=\operatorname{Tr}(M_q P^{-1})$, with the uniform-noise estimator as a special case.
Load-bearing premise
The argument assumes that the DKW concentration inequality, which applies to empirical cumulative distribution functions, can also bound the deviation of $\hat F^r(q)$, an average of exact conditional probabilities $|C_q(x_i)|/k$; if that step fails, Theorem 5's coverage guarantee has no proof.
Editorial extensions
If this is right
- A practitioner who knows the uniform noise rate can set conformal thresholds from the noisy calibration set alone, with no need to collect a clean calibration set.
- Because $\Delta$ does not grow with $k$, the guaranteed threshold remains below the threshold that returns every class, even at 1000 classes; the paper shows ACNL and CRCP become vacuous on CIFAR-100, Tiny-ImageNet, and ImageNet at $\epsilon=0.2$.
- As the noisy calibration size $n$ grows, $\Delta$ shrinks to zero, so the selected threshold converges to the threshold one would use with clean labels.
- For a general known invertible noise matrix $P$, the same inversion via $\hat F^c(q)=\operatorname{Tr}(\hat M_q P^{-1})$ extends the procedure beyond uniform noise.
- The experiments report that the unadjusted version already reaches the target coverage, indicating the derived bound is conservative in practice.
Reading between the lines
- If Lemma 4's application of the DKW inequality is invalid, as suspected because $\hat F^r(q)$ is an average of exact conditional probabilities rather than an empirical CDF, Theorem 5's formal guarantee is unproved, although the estimator and its empirical coverage could still be sound.
- The $k$-independent correction is specific to uniform noise; for class-dependent noise the same general matrix argument would need per-class sample sizes, and the finite-sample correction would plausibly grow with $k$ again.
- The same coverage-function identity could be turned around to estimate the noise rate $\epsilon$ from an unlabeled prediction set by comparing $\hat F^n(q)$ and $\hat F^r(q)$ over multiple thresholds.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies split conformal prediction when the calibration labels are noisy. For uniform label noise with known rate ε, the authors use the decomposition F^n(q)=(1−ε)F^c(q)+εF^r(q) (Eq. (5)), estimate F^c by \hat F^c(q)=(\hat F^n(q)−ε\hat F^r(q))/(1−ε) (Eq. (8)), and set the conformal threshold by inverting \hat F^c. The main theoretical contribution is Theorem 5, which gives a high-probability coverage guarantee with correction Δ(n,ε,δ)=sqrt(log(4/δ)/(2nh^2)), h=(1−ε)/(1+ε), independent of the number of classes k. The paper also bounds the NACP threshold between two noisy-score quantiles (Theorem 2), compares set sizes with Noisy-CP (Theorem 3), extends the estimator to a general invertible noise matrix (Section 3.4), and reports experiments on CIFAR-10/100, Tiny-ImageNet, and ImageNet with APS, RAPS, and HPS scores.
Significance. If the finite-sample guarantee were fully established, NACP would be a useful contribution: its correction term is the only one among the compared methods that remains non-vacuous for k=100–1000, and the experiments show that NACP produces much smaller prediction sets than ACNL/CRCP while meeting the adjusted coverage target. The paper compares with prior methods fairly, releases code, and studies multiple architectures. The main caveat is that the proof of Lemma 4, which is the basis of Theorem 5, is not valid as written, so the k-independent coverage guarantee is not yet established.
major comments (2)
- [Section 3.3, Lemma 4 and Theorem 5] The proof of Lemma 4 applies the Dvoretzky–Kiefer–Wolfowitz inequality to \hat F^r(q) = (1/n) \sum_i |C_q(x_i)|/k as though it were an empirical CDF of n iid observations. It is not: for each q it is the sample average of the conditional probabilities P(S(x_i,u) \le q | x_i), and q indexes a class of functions rather than being the argument of n iid scalar draws. If the nk scores {S(x_i,y)} are pooled, the values are dependent within each x_i, so DKW with sample size n cannot be invoked. Since the uniform bound (12) is the only step that converts \hat F^c(q) \ge 1−α+Δ into F^c(q) \ge 1−α in Theorem 5, the headline k-independent finite-sample guarantee is unproved as written. A correct proof would need a uniform tail bound for the empirical process {q ↦ (1/n)\sum_i (|C_q(x_i)|/k − F^r(q))}, for example through VC or bracketing arguments; such a bound may recover the O(1/√n) rate and k-independence, but the constants and the form of Δ in Lemma 4 are not justified by the cited DKW theorem.
- [Algorithm 1 and Section 3.3] There is an inconsistency between the procedure guaranteed by Theorem 5 and the procedure stated in Algorithm 1. Theorem 5 requires selecting q with \hat F^c(q) \ge 1−α+Δ, while Algorithm 1 line 4 searches for \hat F^c(q)=1−α and line 6 phrases the guarantee as p(y∈C_q(x)) \ge 1−α−Δ. The surrounding text says the user should adjust α by Δ, but the experimental section does not state whether the reported NACP results use α−Δ or α as the input; the ImageNet APS row in Table 1 (coverage 91.9 with α=0.1 and Δ=0.019) suggests the adjusted target was used. The pseudocode and the experiment description should be aligned and made explicit so that the claimed guarantee can be applied and reproduced.
minor comments (4)
- [Theorem 3] The statement of Theorem 3 says q \le \tilde q iff \hat F^r(\tilde q) \le 1−α, but the proof derives the condition \hat F^r(q) \le 1−α. Because \hat F^r is nondecreasing, the printed condition is sufficient but not necessary; the if-and-only-if should be corrected.
- [Theorem 5] The proof of Theorem 5 uses F^c(q)=p(S(x,y)<q), while F^c was defined as p(y∈C_q(x))=p(S(x,y)≤q); for discrete scores this strict/weak distinction matters and should be handled with standard tie-breaking or by stating a convention.
- [Section 3.1] The selection rule for q is not fully specified because \hat F^c is a difference of two monotone functions and need not be monotone; the paper should state the exact rule (for example, the smallest grid value with \hat F^c(q) \ge 1−α) rather than only saying that a grid search is used.
- [Section 4] The authors correctly acknowledge that the k-independence of Δ is specific to uniform noise and that no finite-sample correction is effective for a general noise matrix; this limitation could be stated more prominently in the abstract.
Circularity Check
No circularity: the finite-sample guarantee is derived from DKW and the stated noise model, not from fitting the target coverage or from load-bearing self-citation.
full rationale
The derivation chain is self-contained. The paper estimates F^n(q) from noisy calibration scores (Eq. 6) and F^r(q) from prediction-set sizes (Eq. 7), then obtains the clean coverage estimator \(F^c(q)\) by algebraically inverting the noise model in Eq. (5), which is a stated modeling assumption rather than a fitted output. The correction \(Delta\) in Lemma 4 is computed from the DKW inequality via a union bound, and Theorem 5 is the standard conformal argument that a high-probability uniform bound on |F^c - \(\hat F^c\)| converts the adjusted target 1 - \(alpha\) + \(Delta\) into the desired coverage. No parameter is fitted to the target coverage, and no load-bearing step is justified by self-citation: the self-citations in the introduction are contextual, and the threshold estimator shared with Sesia et al. and Clarkson et al. is explicitly acknowledged and compared rather than silently imported. The flagged concern that \(\hat F^r(q)\) is an average of conditional probabilities rather than a genuine empirical CDF, so DKW does not directly apply, is a mathematical-validity concern about the proof, not a circularity: it does not make the conclusion equal to an input by construction. The paper's own remark that the bound is empirically over-conservative and that the unadjusted method already reaches the desired coverage is a stated limitation, not a circular step.
Assumptions & free parameters
free parameters (1)
- epsilon (noise level) =
known in experiments: 0.2
assumptions (4)
- standard math Calibration and test data are i.i.d. (exchangeability)
- domain assumption Uniform label noise model: p(tilde y = j | y = i) = 1{i=j}(1-epsilon) + epsilon/k, with noise independent of x
- domain assumption The noise level epsilon is known exactly
- ad hoc to paper DKW inequality with Massart constant applies to \hat F^r
Cite this review
Pith. "Pith review of Conformal Prediction of Classifiers with Many Classes based on Noisy Labels." pith.science (2026). https://pith.science/paper/DBC367ZV
@misc{pith2026250112749,
author = {Pith},
title = {Pith review of: Conformal Prediction of Classifiers with Many Classes based on Noisy Labels},
year = {2026},
howpublished = {\url{https://pith.science/paper/DBC367ZV}},
note = {Machine review of arXiv:2501.12749}
}
read the original abstract
Conformal Prediction (CP) controls the prediction uncertainty of classification systems by producing a small prediction set, ensuring a predetermined probability that the true class lies within this set. This is commonly done by defining a score, based on the model predictions, and setting a threshold on this score using a validation set. In this study, we address the problem of CP calibration when we only have access to a calibration set with noisy labels. We show how we can estimate the noise-free conformal threshold based on the noisy labeled data. We derive a finite sample coverage guarantee for uniform noise that remains effective even in tasks with a large number of classes. We dub our approach Noise-Aware Conformal Prediction (NACP). We illustrate the performance of the proposed results on several standard image classification datasets with a large number of classes.
Figures
Forward citations
Cited by 1 Pith paper
-
Robust Conformal Outlier Detection under Contaminated Reference Data
Label-Trim, an active-labeling method that verifies and removes suspicious points from a contaminated calibration set, recovers power lost to contamination in conformal outlier detection while keeping type-I error nea...
Reference graph
Works this paper leans on
-
[1]
Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I Jordan
Anastasios N. Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I Jordan. Uncertainty sets for image classifiers using conformal prediction. International Conference on Learning Representations (ICLR), 2021
work page 2021
-
[2]
Conformal prediction: A gentle introduction
Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends in Machine Learning, 16 0 (4): 0 494--591, 2023
work page 2023
-
[3]
Split conformal prediction under data contamination
Jase Clarkson, Wenkai Xu, Mihai i Cucuringu, and Gesine Reinert. Split conformal prediction under data contamination. In Proceedings of the Symposium on Conformal and Probabilistic Prediction with Applications, 2024
work page 2024
-
[4]
Imagenet: A large-scale hierarchical image database
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009
work page 2009
-
[5]
Conformal prediction is robust to label noise
Bat-Sheva Einbinder, Stephen Bates, Anastasios N Angelopoulos, Asaf Gendler, and Yaniv Romano. Conformal prediction is robust to label noise. arXiv preprint arXiv:2209.14295, 2022
arXiv 2022
-
[6]
Deep learning with label differential privacy
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. In Advances in Neural Information Processing Systems (NeurIPs), 2021
work page 2021
-
[7]
On calibration of modern neural networks
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning (ICML), 2017
work page 2017
-
[8]
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016
work page 2016
Show all 26 references
-
[9]
Learning multiple layers of features from tiny images
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009
2009
-
[10]
Provably end-to-end label-noise learning without anchor points
Xuefeng Li, Tongliang Liu, Bo Han, Gang Niu, and Masashi Sugiyama. Provably end-to-end label-noise learning without anchor points. In International Conference on Machine Learning (ICML), 2021
2021
-
[11]
A holistic view of label noise transition matrix in deep learning and beyond
Yong Lin, Renjie Pi, Weizhong Zhang, Xiaobo Xia, Jiahui Gao, Xiao Zhou, Tongliang Liu, and Bo Han. A holistic view of label noise transition matrix in deep learning and beyond. In International Conference on Learning Representations (ICLR), 2023
2023
-
[12]
Improving trustworthiness of AI disease severity rating in medical imaging with ordinal conformal prediction sets
Charles Lu, Anastasios N Angelopoulos, and Stuart Pomerantz. Improving trustworthiness of AI disease severity rating in medical imaging with ordinal conformal prediction sets. In International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI), 2022 a
2022
-
[13]
Fair conformal predictors for applications in medical imaging
Charles Lu, Andr \'e anne Lemay, Ken Chang, Katharina H \"o bel, and Jayashree Kalpathy-Cramer. Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022 b
2022
-
[14]
The tight constant in the D voretzky- K iefer- W olfowitz inequality
Pascal Massart. The tight constant in the D voretzky- K iefer- W olfowitz inequality. The Annals of Probability, pages 1269--1283, 1990
1990
-
[15]
Estimating diagnostic uncertainty in artificial intelligence assisted pathology using conformal prediction
Henrik Olsson, Kimmo Kartasalo, Nita Mulliqi, et al. Estimating diagnostic uncertainty in artificial intelligence assisted pathology using conformal prediction. Nature Communications, 13 0 (1): 0 7761, 2022
2022
-
[16]
A conformal prediction score that is robust to label noise
Coby Penso and Jacob Goldberger. A conformal prediction score that is robust to label noise. In MICCAI Int. Workshop on Machine Learning in Medical Imaging (MLMI), 2024
2024
-
[17]
Confidence calibration of a medical imaging classification system that is robust to label noise
Coby Penso, Lior Frenkel, and Jacob Goldberger. Confidence calibration of a medical imaging classification system that is robust to label noise. IEEE Transactions on Medical Imaging, 43 0 (6): 0 2050--2060, 2024
2024
-
[18]
Privacy-preserving conformal prediction under local differential privacy
Coby Penso, Bar Mahpud, Jacob Goldberger, and Or Sheffet. Privacy-preserving conformal prediction under local differential privacy. In Proceedings of the Symposium on Conformal and Probabilistic Prediction with Applications, 2025
2025
-
[19]
Classification with valid and adaptive coverage
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 2020
2020
-
[20]
Adaptive conformal classification with noisy labels
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
2024
-
[21]
Learning from noisy labels with deep neural networks: A survey
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems, pages 1--19, 2022
2022
-
[22]
Algorithmic learning in a random world, volume 29
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005
2005
-
[23]
Robust medical image classification from noisy labeled data with global and local representation guided co-training
Cheng Xue, Lequan Yu, Pengfei Chen, Qi Dou, and Pheng-Ann Heng. Robust medical image classification from noisy labeled data with global and local representation guided co-training. IEEE Transactions on Medical Imaging, 41 0 (6): 0 1371--1382, 2022
2022
-
[24]
Learning noise transition matrix from only noisy labels via total variation regularization
Yivan Zhang, Gang Niu, and Masashi Sugiyama. Learning noise transition matrix from only noisy labels via total variation regularization. In International Conference on Machine Learning (ICML), 2021
2021
-
[25]
, " * write output.state after.block = add.period write
ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...
-
[26]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.