Certifying Robustness by Betting

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-$n$ 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 $\alpha$ 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.