  Randomized smoothing (RS) has successfully been used to improve the
robustness of predictions for deep neural networks (DNNs) by adding random
noise to create multiple variations of an input, followed by deciding the
consensus. To understand if an RS-enabled DNN is effective in the sampled input
domains, it is mandatory to sample data points within the operational design
domain, acquire the point-wise certificate regarding robustness radius, and
compare it with pre-defined acceptance criteria. Consequently, ensuring that a
point-wise robustness certificate for any given data point is obtained
relatively cost-effectively is crucial. This work demonstrates that reducing
the number of samples by one or two orders of magnitude can still enable the
computation of a slightly smaller robustness radius (commonly ~20% radius
reduction) with the same confidence. We provide the mathematical foundation for
explaining the phenomenon while experimentally showing promising results on the
standard CIFAR-10 and ImageNet datasets.
