  Although randomized smoothing has demonstrated high certified robustness and
superior scalability to other certified defenses, the high computational
overhead of the robustness certification bottlenecks the practical
applicability, as it depends heavily on the large sample approximation for
estimating the confidence interval. In existing works, the sample size for the
confidence interval is universally set and agnostic to the input for
prediction. This Input-Agnostic Sampling (IAS) scheme may yield a poor Average
Certified Radius (ACR)-runtime trade-off which calls for improvement. In this
paper, we propose Input-Specific Sampling (ISS) acceleration to achieve the
cost-effectiveness for robustness certification, in an adaptive way of reducing
the sampling size based on the input characteristic. Furthermore, our method
universally controls the certified radius decline from the ISS sample size
reduction. The empirical results on CIFAR-10 and ImageNet show that ISS can
speed up the certification by more than three times at a limited cost of 0.05
certified radius. Meanwhile, ISS surpasses IAS on the average certified radius
across the extensive hyperparameter settings. Specifically, ISS achieves
ACR=0.958 on ImageNet ($\sigma=1.0$) in 250 minutes, compared to ACR=0.917 by
IAS under the same condition. We release our code in
\url{https://github.com/roy-ch/Input-Specific-Certification}.

Computer Vision and Pattern Recognition