Anytime-Valid Randomized Smoothing Certificates

Randomized smoothing converts noisy model evaluations into robustness certificates, at the cost of a large number of samples $n$. Fixed-$n$ Monte Carlo confidence bounds do not retain their nominal error control when repeatedly inspected and stopped at first certification. We cast certification as sequential testing of the bad null that the population certificate fails. Predictable bounded witnesses yield e-processes for mean, mean--variance, and discretized cumulative-distribution-function (CDF) certificates, controlling false certification under arbitrary stopping. Past-only reverse-information-projection (RIPr) guidance selects legal witnesses and stakes, while support-wide conditions supply validity. Our experiments show that the proposed methods achieve higher certified accuracy than fixed-$n$ bounds, particularly at low sampling budgets, and certify using fewer samples on average than both a staged look-ahead baseline and an anytime-valid plug-in baseline. These results highlight the benefits of designing custom e-processes for certification.