Sparsity-based Defense against Adversarial Attacks on Linear Classifiers

These perturbations can be designed to be barely noticeable to the human eye, but can cause large classification errors in state of the art deep networks. While it is tempting to speculate that this vulnerability arises from the complex, nonlinear nature of deep networks, a more plausible explanation is that it is due to the excessive linearity of such networks [3-6]. When we take a linear combination of the components of a high-dimensional input, small, adversarially chosen, perturbations of each component can add up to a large perturbation at the output. Complex operations such as a rectified linear unit (ReLU) operating beyond its bias, or a sigmoid in its linear region, together with operations such as max pooling or average pooling, when cascaded through multiple stages, still amount to an approximately linear combination of the input. Of course, the coefficients of the linear combination exhibit some dependence on the input, but these can be viewed as on-off switches rather than a change in the value of the coefficients: for example, whether the input is such that a ReLU unit is operating in its linear region, or the identity of the argument of the maximum in a max pooling unit. This motivates us to take a step back in this paper, and study adversarial perturbations in the simplest possible setting: a linear classifier.