Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design

• URL: http://arxiv.org/abs/2607.21480v1
• Date: Thu, 23 Jul 2026 16:21:30 GMT
• Title: Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design
• Abstract summary: We study how many audit labels are needed to certify, with finite-sample validity, that this missed relevant mass is small.<n>We first show that no procedure using only labels from inside the candidate set can certify any non-trivial bound on the missed mass.<n>We develop an exact finite-sample toolkit, using binomial and hypergeometric inversion rather than approximation, that certifies missed mass.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An initial high-recall stage in an empirical pipeline decides which items pass to later review, labelling, or modelling, and relevant items it misses are lost to every subsequent stage. We study how many audit labels are needed to certify, with finite-sample validity, that this missed relevant mass is small, and our main results characterise the label complexity of this problem. We first show that no procedure using only labels from inside the candidate set can certify any non-trivial bound on the missed mass: the audit must sample the excluded pool, the only region where unrecovered relevant items can lie. We then prove a matching finite-corpus lower bound. Any valid audit that certifies fewer than $m$ missed relevant items with high probability when none are present, even if adaptive and permitted to label the entire included pool, must inspect on the order of $N_0/m$ excluded-pool labels. Excluded-pool auditing is therefore minimax rate-optimal, not merely convenient, for missed-mass certification in the zero-miss regime. Building on this characterisation, we develop an exact finite-sample toolkit, using binomial and hypergeometric inversion rather than asymptotic approximation, that certifies missed mass, converts it to recall through a two-pool design, certifies pre-specified families of nested candidate generators simultaneously, and produces stress-test certificates against declared perturbation mechanisms. These certificates can be paired with observable review burden to select the least burdensome pre-specified candidate generator meeting a missed-mass target. Every guarantee holds under one discipline: the candidate generator, or the pre-specified family from which it is selected, and the audit rule are fixed before the certification labels are examined.

Related papers

• Certifying Model Upgrades with Slice-Wise Non-Regression and Incumbent Fallback [2.8716825293247665]
  We study checkpoint selection subject to non-regression tolerances relative to a retained incumbent.<n>We give a reproducible release procedure that separates candidate search from independent, paired evaluation.<n>A joint release decision does not require a slice-count Bonferroni penalty, although certification power can still decrease with the number of slices.
  arXiv  Detail & Related papers  (2026-09-12T05:00:50Z)
• NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision [0.9475982252982437]
  We introduce Natural Language PAC, a framework that uses a fixed model's thresholded decoding law to define admissible labels and candidate targets.<n>In a frozen Qwen2.5--3B audit, one prespecified prompt yields a positive model-relative certificate, whereas a paraphrase and exact-rule controls yield zero.
  arXiv  Detail & Related papers  (2026-07-09T21:53:00Z)
• Unified Approach for Weakly Supervised Multicalibration [6.557328947642346]
  Multicalibration requires predicted scores to agree with label probabilities across rich families of subgroups and score-dependent tests.<n>Existing methods require clean input-label pairs for evaluation and post-processing.<n>We propose a unified framework for estimating and correcting multicalibration under weak supervision.
  arXiv  Detail & Related papers  (2026-05-11T01:30:09Z)
• Toward Patch Robustness Certification and Detection for Deep Learning Systems Beyond Consistent Samples [3.914395669991103]
  This paper proposes HiCert, a novel masking-based certified detection technique.<n>It certifies significantly more benign samples, including those inconsistent and consistent.<n>It achieves significantly higher accuracy on those samples without warnings and a significantly lower false silent ratio.
  arXiv  Detail & Related papers  (2025-12-05T20:02:09Z)
• Rethinking Consistent Multi-Label Classification under Inexact Supervision [60.79309683889278]
  In partial multi-label learning, each instance is annotated with a candidate label set, among which only some labels are relevant.<n>In complementary multi-label learning, each instance is annotated with complementary labels indicating the classes to which the instance does not belong.
  arXiv  Detail & Related papers  (2025-10-05T08:30:32Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  A key challenge in machine learning is the prevalence of one-sided feedback.<n>We introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels.<n>We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• The Decisive Power of Indecision: Low-Variance Risk-Limiting Audits and Election Contestation via Marginal Mark Recording [51.82772358241505]
  Risk-limiting audits (RLAs) are techniques for verifying the outcomes of large elections. We define new families of audits that improve efficiency and offer advances in statistical power. New audits are enabled by revisiting the standard notion of a cast-vote record so that it can declare multiple possible mark interpretations.
  arXiv  Detail & Related papers  (2024-02-09T16:23:54Z)
• Appeal: Allow Mislabeled Samples the Chance to be Rectified in Partial Label Learning [55.4510979153023]
  In partial label learning (PLL), each instance is associated with a set of candidate labels among which only one is ground-truth. To help these mislabeled samples "appeal," we propose the first appeal-based framework.
  arXiv  Detail & Related papers  (2023-12-18T09:09:52Z)
• A Majority Invariant Approach to Patch Robustness Certification for Deep Learning Models [2.6499018693213316]
  MajorCert finds all possible label sets manipulatable by the same patch region on the same sample. It enumerates their combinations element-wise, and then checks whether the majority invariant of all these combinations is intact to certify samples.
  arXiv  Detail & Related papers  (2023-08-01T11:05:13Z)
• Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis [74.85187027051879]
  We show that it is possible to approximate the optimal certificate with arbitrary precision, by probing the decision boundary with several noise distributions. This result fosters further research on classifier-specific certification and demonstrates that randomized smoothing is still worth investigating.
  arXiv  Detail & Related papers  (2022-06-03T17:48:54Z)
• One Positive Label is Sufficient: Single-Positive Multi-Label Learning with Label Enhancement [71.9401831465908]
  We investigate single-positive multi-label learning (SPMLL) where each example is annotated with only one relevant label. A novel method named proposed, i.e., Single-positive MultI-label learning with Label Enhancement, is proposed. Experiments on benchmark datasets validate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2022-06-01T14:26:30Z)
• Learning with Proper Partial Labels [87.65718705642819]
  Partial-label learning is a kind of weakly-supervised learning with inexact labels. We show that this proper partial-label learning framework includes many previous partial-label learning settings. We then derive a unified unbiased estimator of the classification risk.
  arXiv  Detail & Related papers  (2021-12-23T01:37:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.