Pith. sign in

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 →

arxiv 2501.12749 v2 pith:DBC367ZV submitted 2025-01-22 cs.LG cs.AIstat.ML

classification cs.LGcs.AIstat.ML MSC 62G1562H30
keywords conformalpredictionlabelnoisesetscoverageguaranteemanyclassesfinite-samplecorrectionuniformDvoretzky-Kiefer-Wolfowitzinequality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Conformal prediction normally calibrates its threshold on a clean labeled set. Under uniform label noise with known rate $\epsilon$, this paper claims the clean-label coverage function $F^c(q)$ can be recovered from noisy scores using the mixture identity $F^n(q)=(1-\epsilon)F^c(q)+\epsilon F^r(q)$, where $F^r(q)$ is the probability that a uniformly random label falls in the prediction set. The associated finite-sample correction $\Delta=\sqrt{\log(4/\delta)/(2nh^2)}$, with $h=(1-\epsilon)/(1+\epsilon)$, does not depend on the number of classes $k$, so the coverage guarantee $p(y\in C_q(x))\ge 1-\alpha$ remains nontrivial for classifiers with hundreds or thousands of classes. This matters because prior noisy-label conformal methods had corrections growing with $k$ and became vacuous, returning all classes as the prediction set. Empirically the proposed NACP method keeps set sizes close to the clean-label baseline while covering around 90\% to 94\% at target 90\% across CIFAR-100, Tiny-ImageNet, and ImageNet.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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

0 steps flagged · score 0.0 of 10

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 1 free parameters · 4 assumptions · 0 invented entities

The central claim relies on the uniform noise model with a known epsilon, the exchangeability assumption of standard CP, and, in the proof, on an unverified application of the DKW inequality to \hat F^r. The only input parameter is the noise level epsilon.

free parameters (1)
  • epsilon (noise level) = known in experiments: 0.2
    The uniform noise model in Eq. (4) requires the noise rate epsilon. The method and theorem treat it as known; if estimated, the coverage guarantee ignores estimation error. In experiments it is injected.
assumptions (4)
  • standard math Calibration and test data are i.i.d. (exchangeability)
    Standard CP assumption invoked throughout, e.g., Theorem 5.
  • domain assumption Uniform label noise model: p(tilde y = j | y = i) = 1{i=j}(1-epsilon) + epsilon/k, with noise independent of x
    Eq. (4), Section 3.1. This is the core noise model; the k-independent bound holds only under it.
  • domain assumption The noise level epsilon is known exactly
    Algorithm 1 takes epsilon as input; Theorem 5 uses it as a fixed constant. No error analysis for estimated epsilon.
  • ad hoc to paper DKW inequality with Massart constant applies to \hat F^r
    Lemma 4 assumes DKW applies to \hat F^r(q) = (1/n) sum |C_q(x_i)|/k, treating it as an empirical CDF; this is not an empirical CDF, so the assumption is unsupported.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2501.12749 by the authors.

Figure 1
Figure 1. Correction terms ∆ of NACP, ACNL and CRCP as a function of the calibration [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Robust Conformal Outlier Detection under Contaminated Reference Data

    stat.ML 2025-02 accept novelty 6.0 of 10

    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

26 extracted references · 21 canonical work pages · cited by 1 Pith paper

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

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

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

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

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

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

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

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

Show all 26 references
  1. [9]

    Learning multiple layers of features from tiny images

    Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.