On the Paradox of Certified Training. (arXiv:2102.06700v3 [cs.LG] UPDATED)

Certified defenses based on convex relaxations are an established technique
for training provably robust models. The key component is the choice of
relaxation, varying from simple intervals to tight polyhedra.
Counterintuitively, loose interval-based training often leads to higher
certified robustness than what can be achieved with tighter relaxations, which
is a well-known but poorly understood paradox. While recent works introduced
various improvements aiming to circumvent this issue in practice, the
fundamental problem of training models with high certified robustness remains …

arxiv paradox training