Certified Training: Small Boxes are All You Need. (arXiv:2210.04871v2 [cs.LG] UPDATED)

To obtain, deterministic guarantees of adversarial robustness, specialized
training methods are used. We propose, SABR, a novel such certified training
method, based on the key insight that propagating interval bounds for a small
but carefully selected subset of the adversarial input region is sufficient to
approximate the worst-case loss over the whole region while significantly
reducing approximation errors. We show in an extensive empirical evaluation
that SABR outperforms existing certified defenses in terms of both standard and
certifiable accuracies across perturbation magnitudes and datasets, pointing to
a new class of certified training methods promising to alleviate the
robustness-accuracy trade-off.