  Discrete adversarial attacks are symbolic perturbations to a language input
that preserve the output label but lead to a prediction error. While such
attacks have been extensively explored for the purpose of evaluating model
robustness, their utility for improving robustness has been limited to offline
augmentation only, i.e., given a trained model, attacks are used to generate
perturbed (adversarial) examples, and the model is re-trained exactly once. In
this work, we address this gap and leverage discrete attacks for online
augmentation, where adversarial examples are generated at every step, adapting
to the changing nature of the model. We also consider efficient attacks based
on random sampling, that unlike prior work are not based on expensive
search-based procedures. As a second contribution, we provide a general
formulation for multiple search-based attacks from past work, and propose a new
attack based on best-first search. Surprisingly, we find that random sampling
leads to impressive gains in robustness, outperforming the commonly-used
offline augmentation, while leading to a speedup at training time of ~10x.
Furthermore, online augmentation with search-based attacks justifies the higher
training cost, significantly improving robustness on three datasets. Last, we
show that our proposed algorithm substantially improves robustness compared to
prior methods.
