acceptodds
Under review as a conference paper at ICLR 2027

Trust No Single Noise Model: Certified Active Dataset Repair

Abstract

A recorded label is an imperfect observation of the label we want, separated from it by a corruption process that recurs across records and can be modelled, so that a small audit budget repairs some records directly and, through the model, others indirectly. But the noisy labels alone do not identify that process: several models fit the same data and prescribe different audits and repairs, and existing methods commit to one and offer no guarantee when it is wrong. We treat the problem as a game: nature picks one corruption model from a declared set of candidates; the learner chooses audits sequentially and then corrects the unaudited labels. Solving the game yields a repaired dataset with a certificate, the largest error expected to remain under any candidate, computable without gold labels. The minimax value is the Bayes value under a least-favourable weighting of the candidates, which makes the game solvable by dynamic programming, and choosing audits one at a time can be arbitrarily worse than planning the sequence. On the CIFAR-10H test set the minimax policy attains the lowest certified risk at every budget among 23 arms, including eight published cleaners: every cleaner's certified risk stays above 5% while ours falls from 5.4% to 0.9%, at a price of about one point of true error against a Bayesian weighting.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
label noise, active label cleaning, dataset repair, minimax, distributionally robust decision making, Bayesian experimental design, certified risk

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TPVfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The CARD treats active dataset repair as a game over candidate conditional corruption laws. It defines worst-case expected residual error, relates the exact finite game to a least-favourable Bayesian mixture, and studies minimax, posterior, and tempered policies. Five image datasets, 23 arms, menu ablations, and small exact-planning episodes evaluate repair quality and model-relative certificates.

Critical strengths

The strength of the paper is its explicit distinction between model-set coverage and policy weighting. The finite-game formulation, Hedge-based bounds, and comparison between planning and greedy acquisition provide a coherent treatment of robust expected repair risk, while the authors acknowledge the approximation limits of the dataset-scale implementation. The evaluation is also broad, with informative controls covering published cleaners under both their native repair rules and a shared repair engine, alternative weightings, different candidate menus, and exact two-step planning episodes. I appreciate that the authors report increases in realized error and cases where it exceeds the certificate, rather than presenting only favorable certificate values. This makes the practical tradeoffs easier to assess.

Critical weaknesses

My main concern is the interpretation of the certificate. A bound on expected risk is not a confidence bound on realized error: even a correctly specified Bernoulli model with expected loss 0.1 can realize loss 1. Consequently, the reported 18/25 and 24/25 counts do not establish calibrated coverage for the released dataset. The guarantee also depends on the true conditional law belonging to the candidate hull, a condition that neither model weighting nor agreement with an observed error rate can verify. There is also a gap between the exact-game guarantees and the dataset-scale implementation. One-step replanning is a heuristic rather than an exact full-horizon best response, so the minimax bracket does not establish optimality for the deployed policy. The menu-size ablation needs clarification as well: Section 4.2 describes certification over all 24 laws, whereas Figure 3 and Appendix D.3 report menu-24 certificates over the original 16-law subset. Those values cannot establish a guarantee over the expanded uncertainty set. Finally, the experimental comparisons do not fully isolate the benefit of robust audit placement. Using ALC’s ranking with CARD’s repair engine recovers most of the headline CIFAR-10H improvement, suggesting that much of the gain comes from repair. Moreover, Appendix E uses a static ALC variant with frozen posteriors because the original update loop relies on a retired training stack. The shared-repair controls are informative, but they do not replace a comparison against a fully functioning adaptive baseline.

Questions for authors

What are the menu-24 certificates when the maximum is computed over all 24 laws, rather than the 16-law subset? What measurable optimization guarantee, if any, applies to the dataset-scale receding-horizon policy? How much advantage remains after matching the repair engine and using a functioning adaptive ALC baseline? Can existing results isolate robust acquisition gains from repair gains and the static-baseline adaptation?

4 comments

We thank the reviewer for the detailed comments.

1. Expected error and realised error.

We agree that a bound on expected risk is not a bound on realised error. The certificate is defined in the paper as a bound on expected error (Section 2), not as a confidence bound, and we did not intend the 18/25 and 24/25 counts as a coverage guarantee. But we did write that the certificate "covers" the realised error, and we agree that this needs a statement about realised error. We add it (Proposition B.4): a 95% certificate, defined as the largest error that any noise model in the menu considers plausible at the 95% level. If the true noise process is in the menu, the realised error exceeds it at most 5% of the time. A textbook concentration bound might not apply here, since in our noise models the errors of one annotator can be correlated, so we compute the 95% certificate by simulation from each noise model. Table 2 now shows both certificates. The realised error is below the original certificate in 18 of 25 minimax cases and below the 95% certificate in 25 of 25. We no longer call these counts coverage.

2. Verifying the menu.

We agree that the data cannot verify whether the true process is in the menu. This is true of every guarantee that rests on a model. Every label-cleaning method assumes some structure in the noise, and most assume one (Goswami et al., 2023, Section 3). Ours assumes a menu of noise models instead of a single one, which is the point of the paper; the certificate is stated relative to the menu throughout. What we add is a check that can expose a wrong menu without gold labels, from a few hundred random audits (Section 2, App. D.10); how it works and how often it catches a wrong menu are in our reply to Reviewer kJtn. The paper also now reports Clothing1M as a dataset on which the menu is wrong.

3. Question 2.

We agree that one-step replanning is a heuristic, and the paper does not claim optimality at dataset scale. Section 3 presents the dataset-scale policy as one-step replanning, and Theorem B.4 of the submission (Theorem B.5 in the revised PDF) shows that one-step rules can be arbitrarily worse than exact planning. Section 3 now says this in one explicit sentence. However, the certificate is computed after the audits, so it is valid for any policy, including this one. Where the exact game can be solved (small episodes), exact planning lowers the certified risk by about 6% of its value on CIFAR-10H (0.0006 on 0.0100; App. C.6). We do not claim that this carries over to dataset scale.

4. Question 1.

We agree that the menu-24 certificates must be computed over all 24 noise models, not 16, and we have corrected this everywhere. Over all 24 noise models:

Budget0.25%0.5%1%2%5%
Dopanim, certificate %33.530.527.226.023.6
Dopanim, realised %24.925.124.322.619.8
CIFAR-10H, certificate %7.67.67.87.75.7
CIFAR-10H, realised %1.71.51.20.80.3

The certificate holds at every budget, so the claim of Section 4.3(c) stands. One number changes: the larger menu costs 1.7 to 6.1 points of certificate on Dopanim (we had written 1.7 to 3.4).

5. Questions 3 and 4.

CARD has three parts: a rule that places the audits, a repair that uses every noise model in the menu, and a certificate. Any placement rule can be combined with our repair and certificate, which is why the paper reports each baseline "with our repair". We built the adaptive ALC you asked for (ALC's selection rule unchanged, its model refit after every round of audits, within the paper's protocol of fixed image features). It matches the static version within 0.3 points at every budget.

Error (%) with 1% of records audited (all budgets: Table 13):

DatasetAdaptive ALC, its own repairAdaptive ALC placement + our repairCARD-minimaxDifference of the last two (95% interval)
Development set16.25.24.21.1 lower for CARD (0.9 to 1.3)
CIFAR-10H4.42.52.00.5 lower for CARD (0.4 to 0.5)
Dopanim32.522.424.01.6 higher for CARD (0.5 to 2.7)

Repair. Repairing with the whole menu, the core idea of the paper, lowers ALC's error by 2 to 11 points in the table above, on its own.

Placement. With the same repair, our placement lowers the error further on the development set at every budget (1.0 to 2.4 points) and on CIFAR-10H; on Dopanim ALC's placement is ahead at 1% and ours at 5%. The larger difference is in the certificate. ALC audits the records most likely to be wrong, which corrects errors quickly but reveals little about how each source behaves. Consistent with this, its certificate stays large: 15.6 to 19.0% on the development set against 11.4 to 15.2% for CARD-minimax, and 6.0 to 6.4% on CIFAR-10H against 0.9 to 5.4%.

Dear Reviewer,

we would be grateful to know whether our reply and the revised PDF (changes in blue) address your concerns. We are happy to clarify anything in the remaining days of the discussion.

Thank you for your time.

Reviewer_TPVfOpenReview ↗

Response to author

Thank you for the detailed response and the revised experiments. Recomputing the certificates over all 24 noise models resolves my concern about the menu-size comparison. The adaptive ALC baseline with a shared repair engine also addresses my attribution question. It shows that the repair engine accounts for much of the reduction in realized error and that the additional benefit of CARD’s audit placement varies by dataset and budget. The revised text also clarifies the scope of the guarantee for the deployed one-step policy.

My main remaining concern is how to interpret the new 95% certificate on real datasets. Its guarantee depends on the true corruption process being represented in the candidate menu. The 25 reported cases in which realized error fell below the certificate leave that assumption unverified. For the proposed random-audit check, can you quantify how likely it is to detect menu misspecification large enough to compromise the certificate, and how many gold-label audits that would require? This would help readers assess when they can rely on the certificate in practice and how much of the audit budget that assessment would consume.

thank you for your comment. I believe the remaining question can be answered quantitatively:

The check rejects the menu when the errors found among n random records exceed what the most pessimistic noise model in the menu considers plausible at the 95% level. Its power depends on one quantity only: the gap between the true error rate of the released dataset and the rate the menu expects. This is exactly the misspecification that matters for the certificate. A menu that is wrong in a way that does not raise the error above the certified level leaves the certificate valid.

For a given gap, the number of random audits follows from a one-sided binomial test at the 5% level:

Error rate the menu expectsCertificate too low byAudits for 80% powerAudits for 90% power
10%10 points78110
10%5 points278393
10%2 points1,5282,172
25%10 points132186
25%5 points501720
25%2 points3,0314,234

On the Clothing1M release (certificate 24.7%, realised error 32.6%) this calculation predicts rejection in 45%, 67% and 97% of draws with 80, 160 and 400 records. We measured 43%, 71% and 94% (App. D.10). The 8-model menu of the ablation, whose certificate is too low by 10 points, was rejected in every draw.

What this means for a practitioner.

  1. The cost is fixed and small. The numbers above do not grow with the dataset: about 300 to 500 random audits detect a certificate that is too low by 5 points with 80% power, which is under 1% of a 50,000-record dataset.
  2. A passed check is informative. With 400 random audits, a release that passes rules out, with about 90% power, a certificate that is too low by more than about 5 points at a 10% error level. A reader can therefore attach a concrete tolerance to the certificate: "valid up to a gap of X points", with X read from the table for the audits spent.
  3. The check is optional and separate from the repair budget. The certificate itself is available from the first audit; the check is the additional step for releases where an independent safeguard on the menu is wanted, and the table tells the user in advance what that step costs.

We will add the table and the reading in point 2 to App. D.10, so that readers can choose the number of check audits for the tolerance they need.

Reviewer_TV9YOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CARD, which models dataset repair as a sequence of audits under a set of candidate corruption models. It connects minimax expected loss to Beyasian planning under the worst-case mixture of these candidate models, and then evaluates scalable one-step policies with minimax, posterior, and tempered weights on five image datasets.

Critical strengths
  1. The motivation is clear and reasonable. Rather than relying on one noise model, the paper bounds the residual error over a declared menu of models, without gold labels, and the bound holds for any audit-and-repair method. This is the primary reason that make me lean toward acceptance.
  2. Experimental results validate the premise that committing to one noise model is costly. On the dev set, about 100 audits placed against the whole menu reach lower error rate than 2k+ audits placed by the single-model rule.
Critical weaknesses
  1. The paper's proposed certificate often fails to cover the true error. The minimax certificate falls short in 7 of the 15 dataset-budget pairs outside the dev set and CIFAR-10H (Table 2). On Clothing1M at the 0.25% budget, the posterior certificate misses by around 8 points, so according to the paper's own argument, the menu excludes the true noise process there. This is the primary weakness I identify.
Questions for authors

Clarification: Coverage compares a bound on expected error with a single realized error. How many of the 7 settings minimax misses remain when the sampling noise in the realized error is taken into account?

3 comments

We thank the reviewer for their precise questions.

First, none of the seven shortfalls remains once sampling noise is taken into account. We checked in two ways (Table 15).

  1. Without any noise model. A 95% bootstrap interval of the realised error contains the certificate in all seven cases.
  2. With the menu. The certificate bounds the expected error. We add its 95% version (Proposition B.4): the largest error that any noise model in the menu considers plausible at the 95% level. All seven realised errors lie below it.
Dataset, budgetRealised %Certificate %Shortfall95% interval of realised95% certificate %
Dopanim 0.5%25.124.40.721.8 to 28.329.0
Dopanim 1%24.022.11.921.0 to 26.525.2
Dopanim 2%22.922.50.420.0 to 25.425.3
LabelMe 0.5%21.821.60.120.0 to 23.725.7
LabelMe 2%19.018.50.517.3 to 21.021.7
LabelMe 5%16.315.90.414.7 to 18.018.0
Clothing1M 0.25%29.528.31.224.7 to 34.034.7

Table 2 of the revised paper now shows the 95% certificate next to the original one. With it, the minimax certificate holds in 25 of 25 cases (18 before).

We agree that Clothing1M at 0.25% with posterior weighting misses by about 8 points and we edited the paper to explicitly state this. The realised error is 32.6%, the certificate is 24.7% and its 95% version is 28.6%, so this miss is not sampling noise: it is four points beyond what any noise model in the menu considers plausible. The reason is visible in the run: after 20 audits the method still placed almost all its weight on noise models that are wrong for this dataset; after 40 audits it has moved to the better one and the error drops to 21.4% (see also our last point in response to Reviewer kJtn)

We also add a check that does not need gold labels (details in our reply to Reviewer kJtn): audit a few hundred random records and compare with what the menu considers plausible. On this Clothing1M release it rejects the menu in 43%, 71% and 94% of draws with 80, 160 and 400 random records.

Dear Reviewer,

we would be grateful to know whether our reply and the revised PDF (changes in blue) address your concerns. We are happy to clarify anything in the remaining days of the discussion.

Thank you for your time.

Reviewer_TV9YOpenReview ↗

Response to rebuttal

We thank the authors for their rebuttal responses. The authors' clarification and additional experiments have addressed most of my concerns, so I decide to maintain my score.

Reviewer_kJtnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a new approach for repairing noisy labels in a dataset and proposes the idea of a “certified” remaining error. The main concept is to introduce multiple noise models (called a menu) and treat the repair process as a game against nature. The scenario is as follows: a few examples are checked by a trusted oracle, the remaining labels are repaired, and the method then generates a certificate reporting the largest expected remaining error across all candidate models. The paper compares three weighting strategies for the candidate models and evaluates the method on five noisy-label image datasets.

Critical strengths

The paper presents an interesting idea and has several positive aspects:

  • Estimating how many label errors remain after repair is a very practical question.
  • Utilizing multiple candidates, rather than relying on a single noise model, is a well-motivated idea that can offer significant benefits given a good set of candidates.
Critical weaknesses

The paper also has a few points that could be improved or clarified:

  • The approach may depend strongly on how the menu is designed, yet there is insufficient guidance on how to construct it. For example, the 16 candidates are combinations of four components, meaning they share the same basic structure. Noise falling outside of these structural assumptions may not be captured by any combination. The ablation studies show how sensitive the results are; for instance, removing one family of candidates increases the error from about 4% to 14.3%. It would be great if the paper could provide a more concrete and practical way to verify the menu’s reliability.
  • Furthermore, the practical usefulness of the proposed approach is somewhat unclear. The certificate often seems a bit loose (e.g., a 14.8% certificate vs. a 4.3% actual error for CARD-minimax on the development set). On CIFAR-10H, the minimax weighting yields a tighter certificate than the posterior weighting, but at the cost of data quality. Additionally, while the menu-based certificate seems most useful when the budget is small, coverage failures (i.e., the certificate falling below the actual error) occur on the datasets with smaller budgets. Thus, it would be helpful to discuss the practical value of this approach in real-world applications.
Questions for authors

The questions are merged in the above weaknesses section.

2 comments

We thank the reviewer for their constructive comments. We address below the two points raised.

1. How should a menu be built, and how can it be checked?

The certificate is the largest expected error over the noise models in the menu. So adding a noise model can never make the certificate wrong; it can only make it larger. However, removing one can make it wrong. The ablation you quote shows that with one family removed, the error rises to 14.3% while the certificate reads 4% (Table 16).

We have updated Section 5 to include guidelines on how the menu should be built:

  1. Include every noise model that the way the data was collected makes plausible. The candidates are the noise structures the literature already distinguishes (Goswami et al., 2023, Section 3): uniform noise, class-dependent noise, noise that depends on the image, and error rates that differ between annotators.
  2. Include at least one truth model that was not trained on the labels being certified, for example a classifier trained on other data, labels from other annotators, or a small set checked by an expert. Without one, the check below is the main safeguard.
  3. Do not remove a noise model only to obtain a smaller certificate. If a smaller certificate is the goal, change the weighting, not the menu: minimax is built to make the certificate small, tempered to make the error small.

Checking the menu. We have added a check of the menu that needs no gold labels (Section 2 and App. D.10). Once the dataset is repaired, we pick a few hundred records at random and, before revealing their true labels, we ask each noise model in the menu how many errors it would expect to see among them. The most pessimistic answer, at the 95% level, becomes the threshold. Then we audit those records. If we find more errors than the threshold, none of our noise models can account for what we see, so the menu is wrong and the certificate should not be trusted. When the menu is right, this false alarm happens at most 5% of the time.

The records should be picked at random: auditing only records flagged as suspicious tells us nothing about the errors that were missed (Goswami et al., 2023, Section 4.3).

If the check fails, add the noise model family that was left out and recompute, or report the model-free bound from the same random records.

CaseRandom records auditedMenu rejected
Our 8-model ablation (certificate 10 points too low)434100%
Clothing1M (certificate 8 points too low)80 / 160 / 40043% / 71% / 94%
Releases with a correct certificateany size0 to 9%

Note that the check can show that a menu is wrong; it cannot prove that a menu is right. No procedure can: with one recorded label per record, several noise processes explain the same data equally well (Liu et al., 2023). This holds just as much for the single noise model that each existing cleaner assumes. The check also has a cost: it needs a few hundred random records whatever the size of the dataset, so it is meant for releases where these extra audits are affordable (stated in the paper).

2. Is the certificate useful in practice?

The gap you quoted (14.8% against 4.3%) is the price of not knowing which noise model is true, and not an estimation error. It comes from one family of noise models (Table 14), the same family whose removal breaks the certificate in the ablation above.

To discuss practical utility of this approach we compared with the simplest alternative: audit random records and compute a 95% Clopper-Pearson bound on the error rate from that sample alone, with no noise model (Table 17). The certificate is the smaller bound on CIFAR-10H and on the three small test sets at every budget (e.g. 5.4% against 9.0% on CIFAR-10H at the 0.25% budget). On the 43,000-record development set the random sample is the smaller bound once 0.5% of records are audited (13.9% against 15.3%). So the certificate is the better tool when only a few audits are affordable, which is the setting of the paper: if a large share of the records could be audited, one would consider a different semi-supervised approach instead.

We agree that minimax is tighter but costs accuracy on CIFAR-10H, and the paper states this explicitly: 2.0% error instead of 1.0% at the 1% budget, for a certificate about half as large. Our recommendation is unchanged: minimax when the bound must be signed, that is, when the dataset is handed to someone else and the stated error must hold whichever noise model is true; tempered otherwise.

The 7 shortfalls of the minimax certificate are between 0.1 and 1.9 points and all are within sampling noise (see our reply to Reviewer TV9Y). One failure is real: Clothing1M with 20 audits. Its labels were scraped from web text and it has no annotators, so it is the dataset furthest from the structure our menus assume. We now report it as a dataset on which the menu is wrong (Section 4.3(c), Limitations).

Dear Reviewer,

we would be grateful to know whether our reply and the revised PDF (changes in blue) address your concerns. We are happy to clarify anything in the remaining days of the discussion.

Thank you for your time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.