Trace-Norm Adversarial Examples
  White box adversarial perturbations are sought via iterative optimization
algorithms most often minimizing an adversarial loss on a $l_p$ neighborhood of
the original image, the so-called distortion set. Constraining the adversarial
search with different norms results in disparately structured adversarial
examples. Here we explore several distortion sets with structure-enhancing
algorithms. These new structures for adversarial examples, yet pervasive in
optimization, are for instance a challenge for adversarial theoretical
certification which again provides only $l_p$ certificates. Because adversarial
robustness is still an empirical field, defense mechanisms should also
reasonably be evaluated against differently structured attacks. Besides, these
structured adversarial perturbations may allow for larger distortions size than
their $l_p$ counter-part while remaining imperceptible or perceptible as
natural slight distortions of the image. Finally, they allow some control on
the generation of the adversarial perturbation, like (localized) bluriness.
