acceptodds
Under review as a conference paper at ICLR 2027

Certifying Robustness by Betting

Abstract

Randomized smoothing provides strong robustness certificates, but often requires tens of thousands of Monte Carlo evaluations per input. Adapting this computational budget to each input requires sequentially valid inference, since fixed- Monte Carlo confidence bounds generally do not retain their nominal guarantees under repeated inspection or data-dependent stopping. We formulate certification as a sequential hypothesis-testing problem in which the null corresponds to failure of the population-level certificate. For mean, mean–variance, and discretized-CDF certificates, we construct predictable bounded witnesses whose betting products form e-processes, thereby controlling false certification at any level under arbitrary stopping. We also design reverse information projection (RIPr) guided e-processes that show modest additional sampling gains over standard constructions. Experiments on CIFAR-10 and ImageNet attribute most small-budget gains to direct certificate witnesses rather than monitoring alone. Finally, we introduce a validity-preserving futility rule that terminates uncertifiable inputs early, applies to any of these procedures, and abandons a certifiable input only with probability bounded by its own error level. The rule significantly reduces the mean evaluation cost for every method, including the baselines, with no observed loss of certificates in the reported experiments.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Robustness, Certificates, Randomized Smoothing, E-Process, Anytime-Valid

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_fWgDOpenReview ↗
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
  1. 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.
  2. The validity arguments appear correct. The proofs are not checked thoroughly.
Critical weaknesses
  1. 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.
  2. Most of the techniques used in building the e-processes are established in Voracek (2024) and Cullen et al (2026).
  3. 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
  1. 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?

  2. Can the authors characterize conditions under which the variance and CDF witnesses consistently approach an efficient oracle design?

2 comments

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=104n=10^4. A sequential procedure does not choose nn, 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=100n=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 nn 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 α\alpha 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=100n=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.

  • NP: the direct witness. The witness is fixed, so RIPr ties with it.
  • VC: the direct witness with the quadratic-Kelly stake. RIPr adds 0.5–0.9 points at n=100n=100 at no wall-clock cost.
  • CDF: the direct witness at the main operating point (ρ=1/2\rho=1/2). The projection pays for itself only when one model evaluation costs about 44 ms or more (§ D.3). At large radii (ρ=3\rho=3), use RIPr: it is the only compared arm that certifies.

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 PP. We write g⋆g^\star 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−1log⁡Kt→g⋆t^{-1}\log\mathcal K_t\to g^\star almost surely), if:

  1. the cell probabilities of PP are all positive and lie in the alternative;
  2. the design rule is continuous there (automatic for CDF; for VC it needs a unique maximizing boundary point);
  3. refits continue.

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/α1/\alpha a median 8–11% later than the oracle design.

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.

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

The paper studies how using anytime-valid inference and eprocess techniques, current requirement on the number of samples for Monte Carlo estimation in Randomized smoothing can be reduced. The experiments show now only better certificates at smaller sample sizes with the proposed e-process methods, but also better certified accuracy and radius tradeoffs.

Critical strengths

The advances as compared to recent work Cullen et al 2026 is that this paper generalizes the eprocess methods to VC and CDF certificates.

Critical weaknesses

None.

Questions for authors

Minor suggestion, I believe if the authors can add background section for eprocess, it would help the reader who are familiar with RS but not familiar with eprocess follow better.

2 comments

We thank the reviewer for reading our paper and for the suggestion, which we have followed. The revision adds a background section on e-processes (§ A.1). It covers e-processes, Ville's inequality, why a fixed-nn bound cannot be inspected repeatedly, and the relation to confidence sequences. A figure there (Figure 5) shows the failure of repeated inspection at our operating point. The new Figure 1 (§1) may also help readers who know randomized smoothing but not e-processes: it shows the betting test next to the plug-in procedure.

I appreciate the authors making revision according to my suggestion. I am inclined to main my evaluation.

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

The manuscript introduces E-Cert, which is a betting-based method that reduces the sampling cost of randomized-smoothing certification and achieves good performance across benchmarks.

Critical strengths

The manuscript offers a computation problem and shows some theoretical guarantees for several certificate types etc.

Critical weaknesses

W1. Motivation of the paper needs to be clearer. In addition, motivation-related figures are needed to demonstrate what previous studies do not address and what this paper aims to address. W2. To demonstrate the effectiveness and generalizability of their method, the authors should evaluate their approach on medical benchmarks e.g., NIH-CXR, MIMIC-CXR etc. W3. The manuscript lacks sufficient performance comparisons with recent baselines e.g., HYCAS [1], HySCAN [2], ARS [3], DRS [4], which are needed to assess the approach effectiveness and generalization. W4. Further evaluation using other backbones instead of ResNet family.

[1] Certified vs. Empirical Adversarial Robustness via Hybrid Convolutions with Attention Stochasticity, ICLR, 2026

[2] Does a Hybrid Space-Aware Randomized Defense Improve Empirical and Certified Adversarial Robustness?, ICML 2026

[3] Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences, NeurIPS, 2024

[4] Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing, ICLR 2024

Questions for authors

See Weaknesses.

2 comments

We thank the reviewer for the time spent on our paper and for the suggestions. We answer each point below.

W1 (motivation and motivation figure). We agree and have added a schematic as the new Figure 1 (§1). It shows the existing procedure next to ours.

Existing procedures certify by estimation. They compute a confidence bound for each statistic the certificate reads, substitute the bounds at their worst case, and compare the resulting lower bound with the threshold. This is done at a fixed nn (Cohen et al. 2019 and later work) or with confidence sequences. The sequential methods built for smoothing handle the hard-label mean only (Voráček 2024; Cullen et al. 2026).

However, certificates that read more than the mean are not addressed. The mean–variance (VC) and CDF certificates need more bounds, and each bound is loose at small nn. At small budgets, this costs more than the extra statistic gains. Table 1 shows it at n=100n=100 on CIFAR-10: the plug-ins certify fewer inputs with VC than with NP (44.0% vs. 49.2% with confidence sequences, 28.4% vs. 36.7% with fixed-nn bounds), although VC certifies more at n=104n=10^4. Our procedure has no estimation step. It tests the certificate condition directly: it bets against the null that the certificate fails, and certifies when the capital reaches 1/α1/\alpha. This is one test at level α\alpha, and no statistic is bounded. At n=100n=100, it certifies 54.2% with VC and 51.1% with NP.

W2 and W3 (medical benchmarks; comparison with recent methods). We answer these two points together. Our paper changes the estimation step of randomized smoothing. It does not change the classifier or the certificate.

Each of [1]–[4] defines a new population certificate. ARS and DRS change the smoothing scheme; HyCAS and HySCAN change the architecture. All four then estimate the certificate at a fixed nn. ARS, DRS, and HySCAN use Cohen et al.'s procedure: class selection, then a binomial lower confidence bound at a prespecified nn. HyCAS runs the same procedure next to a Lipschitz margin certificate on expected logits, which it estimates with fixed-nn confidence bounds over the network's internal randomness. The binomial bound is the step our tests replace. So our method can be combined with these methods; it is not an alternative to them. With our e-process in place of the fixed-nn bound, their certificate is unchanged, and the sample size adapts to the input. The Lipschitz certificate of HyCAS estimates a logit margin instead of a [0,1][0,1] score, and we do not cover it. We say this in §2 and in a new paragraph of § K.

The same applies to the medical benchmarks. [1] [2] propose classifiers, and the behaviour of a classifier depends on the dataset, so they evaluate on NIH-CXR, HAM10000 and similar data. The input to our estimation step is the stream of scores Xt∈[0,1]X_t\in[0,1] that a base classifier produces under perturbation. A dataset enters only through the distribution PP of these scores. NIH-CXR and MIMIC-CXR also differ in structure. They are multi-label: an image can carry up to fourteen findings, each with its own binary output, and evaluation is per label. Our tests apply to each label's score as they are (§4). The argmax test (§6) and certified accuracy (§7) assume one label per image and need a per-label counterpart, which we leave for future work.

In the paper we vary the score distribution directly. We use six base classifiers across three noise levels (§ G), two training methods (§ H.7), a diffusion-denoised ViT (§ H.10), hard-label and soft-score outputs (§ D.4, I), and normalized radii from ρ=1/8\rho=1/8 to 44. The two datasets are the standard of this line of work (Cohen et al. 2019; Kumar et al. 2020; Horváth et al. 2022; Delattre et al. 2025; Cullen et al. 2026).

W4 (backbones). We have added a base classifier that contains no ResNet: the diffusion-denoised classifier of Carlini et al. (2023), a diffusion UNet followed by a ViT-B/16. A new subsection (§ H.10, Table 22) compares it with the ResNet-110 on CIFAR-10 at n=102n=10^2, 10310^3 and 10410^4. On this classifier, E-Cert-R is the best procedure, or tied for the best, at every certificate and budget. The small-budget gap is larger than on the ResNet: at n=100n=100 the fixed-nn plug-in certifies 0% with NP or VC, and E-Cert-R certifies 57.1% and 65.1%.

On the soundness score. Could the reviewer point us to the specific concern behind the soundness rating? The four weaknesses concern scope and evaluation. If a theorem or an experiment is in doubt, we would like to address it directly.

Dear reviewer,

As the deadline approaches, we would appreciate confirmation of whether our response has addressed your concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We thank the reviewers for their time. The revision makes the changes below. They are marked in blue in the PDF, a lighter blue than the links and citations.

Main text

  • New Figure 1 (§1): a schematic of the existing plug-in procedure and ours, with the certified accuracy of each at n=100n=100. The last sentence of the second paragraph of §1 is sharpened to match. [czAD W1]
  • §1 and §4 point to the new background section on e-processes. [aM2y Q]
  • §2: a sentence that relates certificate-design methods (ARS, DRS, HyCAS, HySCAN) to the estimation step studied here. [czAD W3] The description of Voráček (2024) and Cullen et al. (2026) now reads "Both test the hard-label mean." [fWgD W2]
  • §8: a paragraph on when the sampling saving matters and which procedure to use for each certificate. [fWgD W1, Q1]

Appendix

  • A roadmap table that lists the question each appendix section answers. [fWgD W3]
  • § A.1: a background section on e-processes, with a figure on repeated inspection (Figure 5). [aM2y Q]
  • § B.4: Proposition 8, with sufficient conditions under which the fitted design attains the oracle growth rate, and an experiment on the real streams (Figure 6). [fWgD Q2] One step in the proof of Proposition 7 is corrected; its statement is unchanged.
  • § D: the capital of E-Cert-P for the CDF certificate is written out as a formula. § D.1 describes the new base classifier.
  • § H.10, Table 22: a third base classifier with no ResNet in it, a diffusion-denoised ViT. [czAD W4] The statements in § H.7, H.9 and J on untested architectures are updated to match.
  • § K: a paragraph on certificate design versus certificate estimation [czAD W3], and credit to Horváth et al. (2022) for early abstention in smoothing [fWgD W2].
  • Five references are added.

Numbering. The former Figures 1–3 are now Figures 2–4, and later figures move up by three. The former § A.1–A.4 are now A.2–A.5. Tables from the former Table 22 on move up by one, and the former Proposition 8 is Proposition 9. A page break is added before §7.1. The other differences in the PDF diff come from this renumbering and from page shifts.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.