  Deep Neural Networks, despite their great success in diverse domains, are
provably sensitive to small perturbations on correctly classified examples and
lead to erroneous predictions. Recently, it was proposed that this behavior can
be combatted by optimizing the worst case loss function over all possible
substitutions of training examples. However, this can be prone to weighing
unlikely substitutions higher, limiting the accuracy gain. In this paper, we
study adversarial robustness through randomized perturbations, which has two
immediate advantages: (1) by ensuring that substitution likelihood is weighted
by the proximity to the original word, we circumvent optimizing the worst case
guarantees and achieve performance gains; and (2) the calibrated randomness
imparts differentially-private model training, which additionally improves
robustness against adversarial attacks on the model outputs. Our approach uses
a novel density-based mechanism based on truncated Gumbel noise, which ensures
training on substitutions of both rare and dense words in the vocabulary while
maintaining semantic similarity for model robustness.
