- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper formulates certification as sequential hypothesis testing and constructs betting processes for mean, mean-variance, CDF based certificates. This procedure allows stopping as soon as evidence is sufficient while controlling false certification. It also introduces a futility rule that terminates uncertifiable inputs early. The strategy is extended to multi-class certification as well.
Critical strengths
- The empirical evaluation of the betting strategies is extensive. Very detailed ablations are conducted to establish the role of different components like witness, stake optimization, futility stopping, continuous monitoring etc. Runtimes are also reported. The entire analysis makes the findings more credible.
- The validity arguments appear correct. The proofs are not checked thoroughly.
Critical weaknesses
- CS certificate already looks like a strong baseline. While the improvement with the proposed betting e-processes is substantial for VC and CDF in small sampling budgets like 100, it is only marginal when n is 1000 or 10000. Since the small budget is anyway resulting in weak certified accuracy compared to larger n, it should be clarified when the sampling reduction provides a meaningful advantage over the CS baseline.
- Most of the techniques used in building the e-processes are established in Voracek (2024) and Cullen et al (2026).
- The appendix is long without a guideline to access it easily. I would have preferred a roadmap or a compact discussion of the results in the appendix to enable easy access. I think there are interesting results that are now buried in the appendix that need proper consolidation.
Questions for authors
-
While I think the results in the paper have merit, I am not sure what the practical recommendation is from the findings. Which procedure is recommended in practice for each certificate, given the small gains and substantial CDF overhead of projection?
-
Can the authors characterize conditions under which the variance and CDF witnesses consistently approach an efficient oracle design?
2 comments
Thank you for the response. My concerns are addressed, and I maintain a weak acceptance given the limited novelty of the techniques and limited practicality.
We thank the reviewer for the detailed reading of our paper and for the questions and suggestions. We respond to each point in turn.
W1 (when the gain over the CS baseline is meaningful). We agree that all consistent procedures converge at n=104. A sequential procedure does not choose n, though. It stops when its evidence suffices, so what matters is the number of evaluations per input. Over all 1,000 images, E-Cert-R’s median cost with VC is 57 vs. 143 evaluations for the CS plug-in on CIFAR-10, and 76 vs. 235 on ImageNet. With CDF, it is 55 vs. 169 and 75 vs. 219 (2.5–3.1× lower; Table 16). Small budgets also matter in practice. When a single evaluation is expensive, large-scale evaluations per input are often unaffordable.
The advantage is largest when the scores of an input are concentrated, and their mean is moderately above the threshold. The new experiment on a diffusion-denoised ViT shows this (§ H.10, Table 22). No image has a mean score above 0.85 there, and the scores are half as dispersed as on the ResNet-110. At n=100 with VC, E-Cert-R certifies 65.1% and the CS plug-in 25.8%; on the ResNet-110 the numbers are 54.2% and 44.0%. The plug-in must bound the variance, and at small n this bound is wide whatever the data. Our test gains evidence at a rate set by the margin relative to the spread of the scores (§ B.4).
W2 (relation to Voráček 2024 and Cullen et al. 2026). We agree. Most of the concepts are not ours. Betting e-processes, confidence sequences, reverse information projection, and the intersection–union test come from earlier work. So does futility stopping. It is standard in group-sequential trials, and Horváth et al. (2022) abstain early in smoothing with a bounded error. Voráček (2024) and Cullen et al. (2026) brought sequential testing to smoothing for the hard-label mean.
We bring these tools together and extend them beyond the hard-label mean. We add witnesses that test the VC and CDF certificates directly (§4). For the argmax, both works bound the top-class probability. Voráček’s § B notes a two-sequence variant that splits the error level. We test each pairwise null with one e-process and combine pairs by intersection–union, so α is not split (§6). Our futility rule bounds the certificate itself, so it covers VC, CDF, and the argmax (Prop. 3). On hard labels, we claim no gain: our cost matches the KT plug-in’s (§7.2). The gain is on soft scores. At n=100 with VC, a betting bound on mean and variance certifies 44.0/42.6% (CIFAR-10/ImageNet), and our witness certifies 53.2/50.6% (§7.1).
W3 (appendix roadmap). Agreed. The appendix now opens with a roadmap: a table that lists the question each appendix section answers.
Q1 (practical recommendation). The conclusion now has a paragraph on this. Below, the direct witness is the one built without the RIPr projection.
Q2 (approaching the oracle). Yes, in the new Proposition 8 (§ B.4). The oracle design is our design rule applied to the true cell probabilities of P. We write g⋆ for its expected log-capital growth per draw. The fitted design uses only past scores. It converges to the oracle design, and its capital grows at the same rate (t−1logKt→g⋆ almost surely), if:
The proposition is asymptotic and gives no rate. Figure 6 measures the rate on the real streams. The fitted design reaches a median 92–94% of the oracle growth after 4 scores and at least 99% after 16. It crosses 1/α a median 8–11% later than the oracle design.