  Randomized smoothing is a technique for providing provable robustness
guarantees against adversarial attacks while making minimal assumptions about a
classifier. This method relies on taking a majority vote of any base classifier
over multiple noise-perturbed inputs to obtain a smoothed classifier, and it
remains the tool of choice to certify deep and complex neural network models.
Nonetheless, non-trivial performance of such smoothed classifier crucially
depends on the base model being trained on noise-augmented data, i.e., on a
smoothed input distribution. While widely adopted in practice, it is still
unclear how this noisy training of the base classifier precisely affects the
risk of the robust smoothed classifier, leading to heuristics and tricks that
are poorly understood. In this work we analyze these trade-offs theoretically
in a binary classification setting, proving that these common observations are
not universal. We show that, without making stronger distributional
assumptions, no benefit can be expected from predictors trained with
noise-augmentation, and we further characterize distributions where such
benefit is obtained. Our analysis has direct implications to the practical
deployment of randomized smoothing, and we illustrate some of these via
experiments on CIFAR-10 and MNIST, as well as on synthetic datasets.
