  Certifiable local robustness, which rigorously precludes small-norm
adversarial examples, has received significant attention as a means of
addressing security concerns in deep learning. However, for some classification
problems, local robustness is not a natural objective, even in the presence of
adversaries; for example, if an image contains two classes of subjects, the
correct label for the image may be considered arbitrary between the two, and
thus enforcing strict separation between them is unnecessary. In this work, we
introduce two relaxed safety properties for classifiers that address this
observation: (1) relaxed top-k robustness, which serves as the analogue of
top-k accuracy; and (2) affinity robustness, which specifies which sets of
labels must be separated by a robustness margin, and which can be
$\epsilon$-close in $\ell_p$ space. We show how to construct models that can be
efficiently certified against each relaxed robustness property, and trained
with very little overhead relative to standard gradient descent. Finally, we
demonstrate experimentally that these relaxed variants of robustness are
well-suited to several significant classification problems, leading to lower
rejection rates and higher certified accuracies than can be obtained when
certifying "standard" local robustness.
