Recertifying decisions via e-closure: uniform improvements of conformal risk control and randomized e-BH
Abstract
Statistical procedures often control expected loss at a prescribed level while leaving part of their risk budget unused. Building on the e-value representation of risk-controlled decisions and the e-closure principle for multiple testing, we formulate recertification, a general paradigm for improving procedures by exploiting computable slack in their validity certificates. A valid procedure's losses normalized by their risk budgets form a state-indexed e-value collection; conversely, decisions whose normalized losses are bounded by this collection inherit its risk guarantees. Recertification uses distributional structure to quantify slack, enlarge the certifying e-values while preserving validity, and construct less conservative decisions. We develop two applications. For conformal risk control (CRC) with a known loss family, recertification redistributes unused risk budget among the held-out points of each hypothetical augmented sample. The resulting controller is valid under every finite exchangeable law and no more conservative than CRC on any calibration sample. For convex losses on an interval of actions, repeated recertification converges geometrically to an admissible controller. For false discovery rate control with arbitrarily dependent e-values, recertification exploits unused conditional budgets in randomized e-BH. It yields a closed-form randomized procedure whose rejection set contains that of randomized e-BH for every realization of the shared randomization and whose expected number of rejections is maximal subject to the same conditional budget constraints. Recertifying with the larger e-collection of closed e-BH gives a second closed-form procedure whose rejection set contains that of the first. Experiments on CIFAR-100 hierarchical classification and multiple testing simulations demonstrate improved budget utilization, informativeness and power over the baselines.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper proposes a novel "recertification" framework that uniformly improves conformal risk control and randomized e-BH procedures by exploiting unused risk budget in e-value certificates. It provides rigorous theoretical guarantees, including geometric convergence to admissible controllers for convex losses and closed-form power improvements for multiple testing, supported by targeted experiments on CIFAR-100 and simulations.
Methodology
The paper introduces "recertification," a general paradigm for improving statistical decision procedures by exploiting slack in their validity certificates (e-values). The core contribution is a rigorous theoretical framework that maps valid procedures to e-value collections and vice versa, allowing the construction of less conservative decisions by enlarging these e-values while preserving validity guarantees. The authors apply this to Conformal Risk Control (CRC) and randomized e-BH (Benjamini-Hochberg) procedures. For CRC, they prove that repeated recertification converges geometrically to an admissible controller under convexity assumptions. For multiple testing, they derive closed-form randomized procedures (RU-eBH and RC-eBH) that uniformly dominate existing baselines in power. The methodology is mathematically dense but logically sound, leveraging the e-closure principle effectively.
Results & evaluation
The experimental section is limited but appropriate for a theory-heavy paper. It includes simulations for multiple testing showing power gains over e-BH and U-eBH, and a real-data study on CIFAR-100 hierarchical classification. The CIFAR-100 results demonstrate improved budget utilization and informativeness compared to standard CRC and envelope CRC. However, the scope of empirical validation is narrow, focusing primarily on one classification task and synthetic multiple testing scenarios, lacking broader benchmarks or large-scale real-world applications that would typically be expected for a high-impact ML paper.
Reproducibility
The paper provides clear algorithmic descriptions (Algorithm 1) and theoretical conditions for validity. The use of standard datasets (CIFAR-100) and well-defined baselines (CRC, e-BH) aids reproducibility. However, the text is truncated in the provided input, and specific hyperparameters or code availability are not explicitly confirmed in the visible portion, though the mathematical definitions are precise enough for implementation.
Limitations
The primary limitation is the computational cost of repeated recertification, which can be expensive for high-dimensional or individual-score based baselines, as noted in the "Computation" section. The admissibility results rely on convexity or specific finite-space conditions, which may not hold for all practical loss functions. Additionally, the empirical evaluation is relatively small-scale, limiting the generalizability of the observed performance gains to other domains.
Broader impact
This work has significant potential to influence the field of conformal prediction and multiple testing by providing a systematic way to reduce conservatism in statistical guarantees. It bridges decision theory and e-value methodology, offering a template for improving other risk-controlled procedures. The uniform improvement guarantees are particularly valuable for applications requiring strict error control, such as medical diagnosis or autonomous systems. The paper proposes a novel "recertification" framework that uniformly improves conformal risk control and randomized e-BH procedures by exploiting unused risk budget in e-value certificates. It provides rigorous theoretical guarantees, including geometric convergence to admissible controllers for convex losses and closed-form power improvements for multiple testing, supported by targeted experiments on CIFAR-100 and simulations.
Author of this paper? Send a correction.