  Several recent results provide theoretical insights into the phenomena of
adversarial examples. Existing results, however, are often limited due to a gap
between the simplicity of the models studied and the complexity of those
deployed in practice. In this work, we strike a better balance by considering a
model that involves learning a representation while at the same time giving a
precise generalization bound and a robustness certificate. We focus on the
hypothesis class obtained by combining a sparsity-promoting encoder coupled
with a linear classifier, and show an interesting interplay between the
expressivity and stability of the (supervised) representation map and a notion
of margin in the feature space. We bound the robust risk (to $\ell_2$-bounded
perturbations) of hypotheses parameterized by dictionaries that achieve a mild
encoder gap on training data. Furthermore, we provide a robustness certificate
for end-to-end classification. We demonstrate the applicability of our analysis
by computing certified accuracy on real data, and compare with other
alternatives for certified robustness.
