Derivation of Information-Theoretically Optimal Adversarial Attacks with
  Applications to Robust Machine Learning
  We consider the theoretical problem of designing an optimal adversarial
attack on a decision system that maximally degrades the achievable performance
of the system as measured by the mutual information between the degraded signal
and the label of interest. This problem is motivated by the existence of
adversarial examples for machine learning classifiers. By adopting an
information theoretic perspective, we seek to identify conditions under which
adversarial vulnerability is unavoidable i.e. even optimally designed
classifiers will be vulnerable to small adversarial perturbations. We present
derivations of the optimal adversarial attacks for discrete and continuous
signals of interest, i.e., finding the optimal perturbation distributions to
minimize the mutual information between the degraded signal and a signal
following a continuous or discrete distribution. In addition, we show that it
is much harder to achieve adversarial attacks for minimizing mutual information
when multiple redundant copies of the input signal are available. This provides
additional support to the recently proposed ``feature compression" hypothesis
as an explanation for the adversarial vulnerability of deep learning
classifiers. We also report on results from computational experiments to
illustrate our theoretical results.
