# Local Convolutions Cause an Implicit Bias towards High Frequency Adversarial
Examples

Josue Ortega Caro  Department of Neuroscience
Baylor College of Medicine
Houston, TX, 77030  Quantitative and Computational Bioscience Program
Baylor College of Medicine
Houston, TX, 70030  Correspondence to<EMAIL_ADDRESS>Yilong Ju  Department of
Computer Science
Rice University
Houston, TX, 77005  Ryan Pyle  Department of Neuroscience
Baylor College of Medicine
Houston, TX, 77030  Sourav Dey  Manifold AI  Wieland Brendel  University of
Tübingen
Germany
Fabio Anselmi  Department of Neuroscience
Baylor College of Medicine
Houston, TX, 77030  Ankit B Patel  Department of Neuroscience
Baylor College of Medicine
Houston, TX, 77030  Department of Electrical and Computer Engineering
Rice University
Houston, TX, 70005

###### Abstract

Adversarial Attacks are still a significant challenge for neural networks.
Recent work has shown that adversarial perturbations typically contain high-
frequency features, but the root cause of this phenomenon remains unknown.
Inspired by theoretical work on _linear full-width convolutional models_ , we
hypothesize that the _local (i.e. bounded-width) convolutional operations_
commonly used in current neural networks are implicitly biased to learn high
frequency features, and that this is one of the root causes of high frequency
adversarial examples. To test this hypothesis, we analyzed the impact of
different choices of linear and nonlinear architectures on the implicit bias
of the learned features and the adversarial perturbations, in both spatial and
frequency domains. We find that the high-frequency adversarial perturbations
are critically dependent on the convolution operation because the spatially-
limited nature of local convolutions induces an implicit bias towards high
frequency features. The explanation for the latter involves the Fourier
Uncertainty Principle: a spatially-limited (local in the space domain) filter
cannot also be frequency-limited (local in the frequency domain). Furthermore,
using larger convolution kernel sizes or avoiding convolutions (e.g. by using
Vision Transformers architecture) significantly reduces this high frequency
bias, but not the overall susceptibility to attacks. Looking forward, our work
strongly suggests that understanding and controlling the implicit bias of
architectures will be essential for achieving adversarial robustness.

## Introduction

Despite the enormous progress in training neural networks to solve hard tasks,
they remain surprisingly and stubbornly sensitive to imperceptibly small
worst-case perturbations known as adversarial examples. This lack of
robustness has sparked many theories [1, 2, 3, 4, 5, 6, 7, 8, 9], but a
unified theoretical explanation of the nature of adversarial examples is still
lacking.

Recent work has shown that commonly found adversarial examples for state-of-
the-art convolutional neural networks are mainly composed of high frequency
information[10]. In addition, they found that adversarial perturbations of
naturally trained models tend to be higher frequency as compared to those of
adversarially trained models. Furthermore, Wang et al, 2020, found that high
frequency features are necessary for high generalization performance of state-
of-the-art convolutional models[11]. These results lead to different theories
for understanding robustness and generalization of neural networks through a
frequency lense. For example, Universal Adversarial Perturbations (UAPs) is a
method to compute what directions in input space are neural networks sensitive
to[12]. They found that convolutional neural networks were sensitive to noise
in the Fourier Basis. Other work such as Neural Anisotropic Directions (NADs)
found linearly separable directions for which a neural network might be able
classify an input[13, 14]. This is evidence that a frequency-based
understanding of model robustness might be an important step towards building
robust, interpretable models. A natural question arises: Why frequencies, as
opposed to some other basis?

Figure 1: The Implicit Fourier Regularization (IFR) Hypothesis. Model
parametrization and weight initialization induces an implicit optimization
bias. This leads to different learned features $\beta$ and therefore,
different adversarial perturbations $\delta$. In particular, implicit
regularization in the frequency domain, directly caused by the translation
invariance of the convolution operation, is necessary for the evolution of
frequency-based features. Furthermore, the spatially-limited nature of common
local convolutional operations encourages the learned features $\beta$ to
possess energy in higher frequencies.

Here we propose an answer to this question that relies on the concept of
implicit bias. The idea behind implicit bias is that the loss landscape of an
overparameterized network has infinitely many global minima, and which global
minimum one converges to after training depends on many factors, including the
choice of model architecture/parametrization [15, 16], initialization scheme
[17] and optimization algorithm [18, 19, 20]. The implicit bias of state-of-
the-art models has been shown to play a critical role in the generalization of
deep neural networks [21, 22]. Recent theoretical work [15] on $L$-layer _deep
linear networks_ has revealed that (i) fully connected layers induce a depth-
independent ridge ($\ell_{2}$) regularizer in the spatial domain whereas,
surprisingly, _full-width convolutional layers_ induce a depth-dependent
sparsity ($\ell_{2/L}$) regularizer in the frequency domain. Linear full-width
convolutional models are different from the high-performance convolutional
neural networks (CNNs) used in practice. Nonetheless, we hypothesised that
similar mechanisms might play a role for _deep nonlinear models with local
convolutions_ , meaning that the high frequency nature of commonly-found
adversarial perturbations is due to the implicit bias induced by the specific
architectural choice. More formally, we propose the Implicit Fourier
Regularization (IFR) hypothesis (see Figure 1):

Implicit regularization in frequency domain, directly caused by the
translation invariance and spatially limited nature of bounded-width
convolutions, yields a strong bias towards high frequency features and
adversarial perturbations.

The IFR hypothesis can be decomposed into three parts, and we will provide
evidence for each later on in the paper. First, convolutions, due to their
translation invariant nature, induce an implicit bias promoting sparsity in
the Fourier domain for nonlinear CNNs with full-width convolutions (thereby
extending theoretical results on linear models [15]). Second, restricting to
bounded-width (spatially limited/localized) convolutions changes the implicit
bias, encouraging the linear features to possess more energy in high
frequencies; this arises because a space-limited filter cannot also be band-
limited, a mathematical consequence of the Fourier Uncertainty Principle.
Third, the high frequency features learned by the model in turn induce high
frequency adversarial perturbations.

## Experimental Results

Impact of Model Parametrization on Adversarial Perturbations. Recent
theoretical work [15] has shown that shallow linear convolutional neural
networks ($L$ full-width circular convolutional linear layers followed by one
fully connected linear layer) induce an implicit sparsity-promoting
regularizer in the Fourier domain. Specifically, the regularizer is:
$\mathcal{R}_{FWC}(\beta_{L})=\|\widehat{\beta_{L}}\|_{\frac{2}{L}}$ where
$\widehat{\beta}_{L}:=\mathcal{F}\beta_{L}$ is the Discrete Fourier Transform
(DFT) of the end-to-end linear transformation $\beta_{L}:=\prod_{i}^{L}W_{i}$
represented by the linear network and $L$ is the number of layers. If the
implicit bias affects the features learned by the model, could it also alter
the nature of the adversarial perturbations?

Confirming [15] results and relationship to adversarial perturbations. To test
our hypothesis, we selected the two model parametrizations considered in [15],
namely fully connected and full-width convolutional models. In addition, we
used shallow (one hidden layer) and deep (three hidden layers) versions of
these models, along with linear and nonlinear activation functions. These
models were trained on CIFAR-10 dataset [23] (MIT) using PyTorch [24]
(performance in Supp. Table 7).

Our goal here is to understand the relationship between the learned features
$\beta$ learned by these models and their corresponding adversarial
perturbations $\delta$ (See Methods for details). In Figure 2, we can see the
average Fourier spectrum of the adversarial perturbations ($\widehat{\delta}$)
for PGD-Linf [25] and the average Fourier spectrum of the input-output weight
visualization ($\widehat{\beta}$). We observe that the full-width
convolutional model (FWC) has a sparser spectrum of $\beta$ compared to the
fully connected model (FC), and when the model has more layers this difference
increases (Deep FWC vs Deep FC). This is experimental confirmation of the
theoretical result in [15] for linear models. Furthermore, to quantify the
different sparsity levels of the two models, we measure the $\ell_{1}$ and
$\ell_{2}$ norm of the Fourier spectrum of $\beta$ for both the shallow and
deep full-width and fully connected models (See Sup. Fig 6). We observe that
the relationship between model parametrization and spectrum holds for the
spectrum of the adversarial perturbations $\widehat{\delta}$, where the full-
width convolutional model has a sparse adversarial spectrum compared to the
fully connected model. This was confirmed quantitatively by computing their
Spearman correlation (see Supp. Table 3). These results also hold for the
other attacks (see Supp. Figure 8, 9).

However, in contrast with theory, which predicts that $\delta\propto\beta$ for
linear models, we instead find correlations $<1$ [26, 7]. This is because a
successful adversarial attack requires only a minimal perturbation of the
input such that the output category changes, therefore, an adversarial might
not use all features directions but only a selected few. As a consequence, the
correlation between $\beta$ and $\delta$ need not be maximal.

Next, we tested if the implicit regularizer has the same properties for
nonlinear models. As we observe in Figure 2, the full-width convolutional
model has a sparse spectrum of both $\beta$ and $\delta$ compared to the fully
connected model. This shows that the implicit regularizer due to the model
holds for both linear and nonlinear models.

Figure 2: Average Frequency Spectrum of adversarial perturbation
($\widehat{\delta}$) and input-output weights ($\widehat{\beta}$) for Fully
Connected (FC), Full-Width Convolutional (FWC), Locally Connected (LC) and
Bounded-Width Convolutional (BWC) models for PGD-Linf Attack. We can observe
the correlation between the input-output weights and the adversarial
perturbations for each model. This results also hold for different attacks
(See Sup. Figures 8, 9)

Expanding to Bounded-Width Convolutional Models. One limitation of this theory
is that full-width convolutional layers are not often used in common state-of-
the-art architectures. Bounded-width convolutional models are instead usually
employed, which have smaller kernel sizes than the width of the input. Given
this, we asked: what is the effect of the bounded-width convolutional model in
$\widehat{\beta}$ and $\widehat{\delta}$?

To answer this question, we trained a bounded-width convolutional model and
generated both $\widehat{\beta}$ and $\widehat{\delta}$ with the same
procedure as the previous section. In Figure 2, we can see that the bounded-
width convolutional models (both linear and nonlinear) contain high frequency
components in $\widehat{\delta}$. This is further exacerbated by depth in the
Deep Bounded-Width model (DBWC). Moreover, we observe that the $\beta$
corresponding to the bounded-width convolutional model is as sparse or less
sparse (more dense) compared to the full-width counterpart (see Supp. Figure
6). Given that the theory [15] only specifies a bias towards
$\ell_{\frac{2}{L}}$-sparsity in the frequency domain (support can consist of
low or high frequencies), then why do we observe so much more concentration of
energy in the higher frequencies of the bounded-width convolutional model but
not the full-width convolutional model? Our experiments suggest that this is
due to the spatial locality constraint imposed in the bounded-width
convolutions. We propose a theoretical explanation via the Fourier Uncertainty
Principle – a space-limited kernel cannot be band-limited in frequency domain
– as the origin of frequency dispersion. This reasoning can be made rigorous
for a bounded-width linear convolutional model by a simple and straightforward
extension of the results of Gunasekar et al, 2018 along with the invocation of
energy concentration Uncertainty Principle. This results in the following
theorem:

######  Theorem 1.

Let $\beta:=\star_{l=1}^{L-1}w_{l}$ be the end to end linear predictor. Then
spatially concentrating the energy of each convolutional filter
$w_{l}\in\mathbb{R}^{D}$ results in an increased concentration of energy in
high frequencies for $\widehat{\beta}$.

Here we informally present the key steps of the proof. A rigorous mathematical
treatment can be found in the Appendix D. The key intuition is that, due to
the Fourier Uncertainty Principle, decreasing the support of the convolutional
filter $w_{l}$ causes an increase of its high frequency energy content. What
is the effect of this high-frequency shift on the end-to-end linear predictor
$\beta$? Since it is a product of convolutions, the Discrete Fourier transform
of $\beta$ is the Hadamard product of the Discrete Fourier transforms of the
convolutional filters (see also Lemma 3 in Gunasekar et al, 2018). Taking the
$\ell_{2}$ norm of $\beta$ and using a norm inequality on the Hadamard product
finally shows that
$\|\widehat{\beta}\|_{2}\leq\prod_{l=1}^{L}\|\widehat{w}_{l}\|_{2}$. In words,
decreasing the support of the per-layer convolutional filters results in an
increase in the high frequencies energy content of $\beta$. Further, as we
reduce the convolutional filters support, the result of the optimization
problem for the implicit regularizer will only increase in cost, since less
degrees of freedom are available for the solution. In summary, all else being
equal, reducing the convolutional kernel size causes/induces a bias towards
more concentration of energy in higher frequencies in $\beta$.

We directly tested our theory on the same models proposed by Gunasekar 2018
but with varying kernel sizes (3 by 3, 7 by 7, 11 by 11, 15 by 15, 21 by 21,
and 32 by 32), with 1 or 3 hidden layers same as our original results, and
train them on Grayscale CIFAR10. This was to keep the number of hidden
channels equal to the number of input channels. Then we computed the frequency
spectrum of $w_{l}$ and the cumulative weights up to layer l, $\beta_{l}$.
Next we computed the $\kappa_{high}$, which is the fraction of energy outside
of an interval $[-\frac{k}{2},+\frac{k}{2}]$ divided by the total energy for
each kernel. In Supp. Figure 7(a), we observe that the fraction of energy is a
function of the kernel size, where for smaller $k$ $\kappa_{high}$ is higher.
Furthermore, as the model goes deeper, we can see that this difference is
further exacerbated. We can observe this phenomenon both for deeper models and
during training (See Supp. Figure 7(b)).

Role of Translation Invariance in the frequency spectrum of $\beta$ and
$\delta$. Next, to further investigate the origin of the high frequency bias,
we asked: Is the effect of the bounded-width convolutional model also present
in a model with only local kernels but not translation invariance (i.e. no
shared weights)? For this we trained a locally connected model with same
kernel size on CIFAR10. In Figure 2 we observe that the locally connected
models (LC and DLC) do not have as much energy in the higher frequencies,
particularly for the deep models. This shows that local connectivity alone is
not sufficient to bias the model towards learning high frequency features;
translation invariance is also required. Thus, local convolutions are
necessary to obtain bias towards high frequency features, and therefore
adversarial perturbations. Importantly, we found the same results for
CIFAR100, which has image statistics similar to CIFAR10. However, we did not
for MNIST, which has no useful high frequency information (See Supp. Figure
5). This shows that an interaction between the implicit bias (induced by the
model parametrization) and the dataset statistics is essential for high
frequency features to be learned.

Figure 3: Steganography experiment. Class specific information $\eta_{class}$
introduced into Fourier Spectrum of training set image
($\widehat{\widetilde{x}}=\widehat{x}+\eta_{\textrm{class}}\>:\>\eta_{\textrm{class}}=M_{\textrm{class}}\odot(\epsilon*N_{\textrm{class}}),N_{\textrm{class}}\sim\mathcal{N}(0,1),M_{\textrm{class}}\sim\textrm{Bernoulli}(\rho)$).
Models with sparse frequency regularizer (Full-Width and Bounded-Width
Convolutional models) should take more advantage of hidden shortcut features
in the dataset, therefore leading to higher test accuracy.

Testing different implicit bias via the Injection of Hidden Shortcut Features.
Given that the theory in Gunasekar et al, 2018 doesn’t extend to the implicit
regularization for nonlinear convolutional models, and our results on the
relationship of $\widehat{\beta}$ and $\widehat{\delta}$, we decided to
directly test if the nonlinear bounded-width convolutional model is able to
capture sparse frequency-based information in the dataset, thus confirming
that the sparse implicit regularization theory also holds for nonlinear
models.

To test our hypothesis, we take inspiration from the field of steganography
which focuses on hiding shortcut features in images that are visually
undetectable by humans [27]. We introduced a class-correlated sparse shortcut
feature into every CIFAR-10 train and test set image (See Figure 3). Our
hypothesis is that these class-dependent shortcut features will be mostly
useful for model parametrizations that have an implicit regularizer that is
sparse in the frequency domain. Therefore the model with the right implicit
bias should achieve higher test accuracy (For generation of the shortcut
features see Methods).

Table 1: Performance on CIFAR-10 on base vs frequency-based dataset , mean $\pm$ std over 5 trials each. | Baseline | $\epsilon=.25,\rho=.2$ | $\epsilon=.25,\rho=.1$
---|---|---|---
Fully Connected Linear | 40.8 $\pm$ .070 | 53.26 $\pm$ .075 | 45.27 $\pm$ 1.14
Fully Connected Nonlinear | 48.5 $\pm$ .084 | 59.6 $\pm$ .223 | 54.93 $\pm$ .497
Full Width Convolutional Linear | 41.8 $\pm$ .124 | 70.3 $\pm$ .805 | 79.6 $\pm$ 1.35
Full Width Convolutional Nonlinear | 52.4 $\pm$ 2.89 | 79.5 $\pm$ .912 | 87.2 $\pm$ 1.26
Bounded Width Convolutional Linear | 41.8 $\pm$ .046 | 97.28 $\pm$ .604 | 92.33 $\pm$ .679
Bounded Width Convolutional Nonlinear | 56.7 $\pm$ .489 | 98.8 $\pm$ .850 | 97.8 $\pm$ .475

Table 1 shows the test accuracy of each linear and nonlinear model with the
new dataset and different levels of sparsity. We can observe that both the
full-width and bounded-width models have higher performance than baseline with
this new dataset. However, the fully connected model, having a different bias,
cannot take full advantage of the class-dependent shortcut feature introduced
into the dataset. This experiment reveals that the implicit regularizer for
sparsity in the frequency domain is present in both linear and nonlinear
convolutional models.

In addition to these results, we tested the high frequency bias of the
bounded-width parametrization. By performing a new variant of the hidden
features experiment, we now localize the information in the low, medium, or
high frequencies by introducing the same class-dependent signal in concentric
rings in those corresponding frequencies on the spectrum of the training and
testing set of CIFAR10 (See Methods).

Table 2: Performance on CIFAR-10 on base vs frequency-based dataset. Low Frequency $(\epsilon=0.5)$, Medium Frequency $(\epsilon=5e-02)$ and High Frequency $(\epsilon=5e-04)$. Different $\epsilon$’s were chosen to match the signal to noise ratio of those frequencies bands and make the task as difficult as possible. Standard Deviation was calculated over 5 runs. Models | Low Frequency | Medium Frequency | High Frequency
---|---|---|---
Full-Width Convolution (L=1) | 100.0 | 41.03 | 41.38
Full-Width Convolution (L=3) | 100.0 | 39.80 | 40.97
Bounded-Width Convolution (L=1) | 100.0 | 49.99 | 53.60
Bounded-Width Convolution (L=3) | 100.0 | 94.17 | 98.47
Fully Connected (L=1) | 99.78 | 41.45 | 41.38
Fully Connected (L=3) | 100.0 | 46.37 | 41.21
Locally Connected (L=1) | 100.0 | 44.39 | 46.23
Locally Connected (L=3) | 100.0 | 47.36 | 54.73

In Table 2, we can see the performance of the linear models with this new
frequency-based class-dependent features. We observe that all models are able
to use the low-frequency shortcut features in order to perform the task.
Furthermore, when the cheat signal is introduced in the medium and high
frequencies the full-width convolutional, fully connected, and locally
connected models have a much more difficult time in selecting this signal.
Where the Bounded-Width Convolutional Model is able to perform the best in
medium and high frequencies compared to the other models and this difference
is also maintained with larger depth.

Vision Transformers do not exhibit a high frequency bias. Since local
convolutions cause a bias towards high frequency features and adversarial
perturbations, it is natural to ask: Are high-performance deep models without
convolutions less biased towards high-frequency features? One possible
architecture is the Vision Transformer (ViT), which has performed on par with
convolution-based architectures in many tasks including object recognition
[28]. Furthermore, recent work has shown that ViTs can be more robust to high
frequency adversarial perturbations than ResNets [29].

(a)

(b)

Figure 4: Radial Energy of the Adversarial Perturbations of Vision Transformer
and Local Vision Transformer models. (a) All Vision Transformer models (vit-2,
vit-4, vit-8) have more energy in lower frequencies than ResNet18. (b) Locally
Connected model’s (vitloc-2, vitloc-4, vitloc-8) spectrum have more energy in
lower frequencies compared to their standard ViT counterpart.

We hypothesize that the lack of convolutional operations in ViTs is
responsible for this greater robustness to high frequency attacks. In order to
test this, we trained a ViT with different patch sizes on CIFAR-10 (See Supp.
Sec. B.4 for training details). All of these models achieved about 80$\%$ test
accuracy. Then, we attacked these models with a PGD-Linf attack, the same used
earlier in the paper. In Figure 4(a), we observe the average frequency
spectrum of ViTs with different word/patch sizes ($2\times 2$, $4\times 4$,
$8\times 8$), as compared to a ResNet18 with similar test accuracy (we stopped
the training when the model had near 80% test accuracy). We observe that all
of the ViTs have more energy in the lower frequencies than the ResNet18. This
strongly suggests that the robustness to high frequency attacks shown in [29]
might be due to the lack of convolution layers. Furthermore, we observe that
different patch/word sizes also have an impact on the spectrum, with smaller
word sizes producing higher frequency spectra. This is consistent with the
theoretical and empirical results comparing full-width and bounded-width
convolutional models.

However, as others have suggested [30], some layers of the ViT can still be
interpreted as convolutional layers, so the model is not entirely convolution-
free. In particular, the first embedding layer is shared across all image
patches, and therefore can be interpreted as a convolutional layer with stride
equal to the patch/kernel size. This leads us to ask: Can we remove this layer
and shift the energy spectrum to even lower frequencies? To test this we
defined a new ViT architecture in which we removed the weight sharing in the
first layer patch embedding by using a locally connected layer with the same
kernel size and stride as the convolutional version, so that each patch has
independent weights. We call this architecture the Visual Local Transformer
(ViTLoc). Then, we trained this architecture on CIFAR-10 (see Performance in
Sup. Table 7) and computed its adversarial perturbations. In Figure 4(b), we
observe that every ViTLoc model has a lower frequency spectrum than its ViT
counterpart. This is more evidence that avoiding the convolutional
parametrization, even in very complex state-of-the-art models, can reduce the
high frequency bias, and therefore, high frequency adversarial perturbations.

## Conclusions

We provide both empirical as well as theoretical evidence that one of the
causes of the high-frequency adversarial examples is the bounded-width
convolutional architecture of modern high-performance CNNs. To this end, we
first showed that theoretical results in deep linear full-width convolutional
models [15] extend to nonlinear models. In line with these results, we find
that the Vision Transformer architecture, which features almost no explicit
convolutions, is less biased towards high frequencies. We demonstrated that by
removing one of the only convolutional layers in the model (Local Vision
Transformer Architecture), this bias can be reduced even further. We think
this is important because ViT, similar to ResNets, have multiple components
such as Norm Layers, Skip Connections, Attention, etc, that should affect the
implicit bias of the model. However, we found that the linear layer
parametrization seem to be crucial to the nature of the features learned and
therefore for the adversarial perturbations.

Second, we derived new theoretical results for the implicit bias of deep
linear bounded-width convolutions, showing that such networks are biased
towards high-frequency features. Furthermore, compared to other theories that
try to understand the right basis for model generalization [12, 13, 14], our
work relates this back to the optimization bias due to model parametrization.
We thinks this is a more general framework for understanding why certain
neural networks (convolutional neural networks) pick frequency-based features
compared to features in other basis. Our work does not claim that all
adversarial perturbations contain only high-frequency components. Instead, we
show that architectures with local convolutions can be successfully attacked
by perturbations that contain more energy in the high frequencies as compared
to non-local architectures (e.g. fully connected, locally connected, and
Vision Transformers).

Moreover, by a novel steganography experiment, we could clearly confirm that
this bias extends to nonlinear models, and that it strongly influences what
features can be learned by the models. We think is a new and exciting
directions to probe the ability of the model to generalize along any basis not
just Fourier. In addition, our work has shown that adversarial perturbations
can be an important technique to understand what are the features been learned
by a neural networks. This is even the case while the model is learning. In
Supplementary Section C, we have shown that the F-principle, which dictates
the dynamics of features learned by a neural network are also reflected in the
adversarial perturbations found for a model. This is further indication that
adversarial analysis will be beneficial for understanding how neural networks
operate.

Finally, much work about generalization and adversarial attacks has been
centered around bias in datasets[11, 9], however, here we show that attention
needs to be paid to bias caused by architectural choices as well. This work is
just the start of stablishing the relationship between implicit bias due to
model parametrization and the robustness of neural networks to different kinds
of input perturbations. We believe this understanding can help drive models
towards the most useful set of features and reduce the adversarial
susceptibility of modern neural networks.

## Acknowledgments

This research has been funded by the NSF NeuroNex program through grant
DBI-1707400. This research was also supported by Intelligence Advanced
Research Projects Activity (IARPA) via Department of Interior/Interior
Business Center (DoI/IBC) contract number D16PC00003. The U.S. Government is
authorized to reproduce and distribute reprints for Governmental purposes
notwithstanding any copyright annotation thereon. Disclaimer: The views and
conclusions contained herein are those of the authors and should not be
interpreted as necessarily representing the official policies or endorsements,
either expressed or implied, of IARPA, DoI/IBC, or the U.S. Government.

## Methods

Neural Network Training. Each architecture was defined by the number of hidden
layers, and nonlinearities (See Supp Table 6). In terms of hyperparameters, we
tuned the maximum learning rates for each model by starting from a base
learning rate of $0.1$, and then, if there were visible failures during
training (most commonly, the model converging to chance performance), we
adjusted the learning rate up/down by a factor of $10$ or $50$. Amongst the
model architectures we explored, the only hyper-parameter that was tuned was
the learning rate. The final values of the learning rates after search are
detailed in Table 9. In addition, all the models were trained with linearly
decaying learning rate follow $0.3$ factor for each epoch and resetting the
learning rate back to max when you trained the model at least $20$ epochs. All
the models were trained on a single GTX $1080$ Ti for at least $40$ epochs
($30$ to $120$ GPU minutes), and we choose the epoch with the highest accuracy
for further experiments (see hyperparameters of training and accuracy on Supp
Sec. B.4)

Adversarial Attack Generation. We used the Foolbox package [31] (MIT license)
to generate adversarial perturbations $\delta$ for every example in the test
set for a fully trained model (PGD-Linf, PGD-L2, PGD-L1[32], BB-Linf and BB-L2
[33]). Finally, we computed the 2-D Discrete Fourier spectrum
$\widehat{\delta}:=\mathcal{F}\delta$ of the perturbation $\delta$. Details of
the attacks are available in Supp. Table 12.

$\beta$ Calculation and Toeplitz Matrix. For the computation of $\beta$, we
used two different methods. For the linear models, we transformed the weights
of every architecture into their matrix form. For example for the
convolutional operation, we generated a Toeplitz matrix per convolutional
filter and then calculated the dot product of the first $l$ matrices to get
the $\beta_{l}$ (or for all $l=1,\cdots,L$ to get the input-output function
$\beta$). For the nonlinear models, because the nonlinearities does not allow
us to use the weights directly, we decided to use a proxy, the saliency map.
Saliency Map is the gradient ($\frac{df}{dx}$) of the function ($f(x)$) with
respect to the input image ($x$). In the linear case, these gradients are
exactly the weights of the function $\beta$ (up to a constant), which we
confirmed using the Toeplitz computation above. For the nonlinear models,
because the weights used changed per example, the gradient gave us a good
approximation of those weights.

Generation of Hidden Shortcut Features. For each class, we sampled a $3\times
32\times 32$ matrix of scalars from a standard Gaussian distribution with mean
of 0 and standard deviation of 1 ($N_{class}$). Then we multiplied this matrix
by a scalar factor $\epsilon$, which was selected via hyperparameter search.
Next, we generated a masking matrix ($M_{class}$) of the same size, $3\times
32\times 32$. For the sparse shorcut feature experiment this matrix was
generated from a Bernoulli distribution with an specific average sparsity
level $\rho$. For the frequency-based class dependent features, we selected an
upper and lower bound radii as a factor of the max frequency ($0.1$ and $0.2$;
$0.4$ and $0.5$; and $0.8$ and $0.9$ for the low, medium and high frequencies
respectively). These were the ranges used to produce the masking matrix
$M_{class}$. Next, we computed the hardmard product of $M_{class}$ with
$N_{class}$. Then, this class-specific shortcut feature was added into the
Fourier spectrum of CIFAR-10 train and test images corresponding to their
respective classes. The mathematical definitions are as follows:

$\displaystyle N_{\textrm{class}}$ $\displaystyle\sim\mathcal{N}(0,1)$
$\displaystyle M_{class}$
$\displaystyle=\begin{cases}\mbox{Sparse}&M_{\textrm{class}}\sim\textrm{Bernoulli}(\rho)\\\
\mbox{Frequency}&M_{\textrm{class}}=\begin{cases}\mbox{Inside frequency
range}&$1$\\\ \mbox{Outside frequency range}&$0$\\\ \end{cases}\end{cases}$
$\displaystyle\eta_{\textrm{class}}$
$\displaystyle=M_{\textrm{class}}\odot(\epsilon*N_{\textrm{class}}),\;\;\;\;\;\;\widehat{\widetilde{x}}=\widehat{x}+\eta_{\textrm{class}}.$

## References

  * Gilmer et al. [2018] Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian Goodfellow.  Adversarial spheres.  _arXiv preprint arXiv:1801.02774_ , 2018.
  * Mahloujifar et al. [2019] Saeed Mahloujifar, Dimitrios I Diochnos, and Mohammad Mahmoody.  The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 4536–4543, 2019.
  * Tanay and Griffin [2016] Thomas Tanay and Lewis Griffin.  A boundary tilting persepective on the phenomenon of adversarial examples.  _arXiv preprint arXiv:1608.07690_ , 2016.
  * Ford et al. [2019] Nic Ford, Justin Gilmer, Nicolas Carlini, and Dogus Cubuk.  Adversarial examples are a natural consequence of test error in noise.  _arXiv preprint arXiv:1901.10513_ , 2019.
  * Fawzi et al. [2018] Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi.  Adversarial vulnerability for any classifier.  In _Advances in Neural Information Processing Systems_ , pages 1178–1187, 2018.
  * Bubeck et al. [2018] Sébastien Bubeck, Eric Price, and Ilya Razenshteyn.  Adversarial examples from computational constraints.  _arXiv preprint arXiv:1805.10204_ , 2018.
  * Goodfellow et al. [2014] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014.
  * Schmidt et al. [2018] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry.  Adversarially robust generalization requires more data.  In _Advances in Neural Information Processing Systems_ , pages 5014–5026, 2018.
  * Ilyas et al. [2019] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry.  Adversarial examples are not bugs, they are features.  In _Advances in Neural Information Processing Systems_ , pages 125–136, 2019.
  * Yin et al. [2019] Dong Yin, Raphael Gontijo Lopes, Jon Shlens, Ekin Dogus Cubuk, and Justin Gilmer.  A fourier perspective on model robustness in computer vision.  In _Advances in Neural Information Processing Systems_ , pages 13255–13265, 2019.
  * Wang et al. [2020] Haohan Wang, Xindi Wu, Zeyi Huang, and Eric P Xing.  High-frequency component helps explain the generalization of convolutional neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8684–8694, 2020.
  * Tsuzuku and Sato [2019] Yusuke Tsuzuku and Issei Sato.  On the structural sensitivity of deep convolutional networks to the directions of fourier basis functions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 51–60, 2019.
  * Ortiz-Jimenez et al. [2020a] Guillermo Ortiz-Jimenez, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard.  Hold me tight! influence of discriminative features on deep network boundaries.  _arXiv preprint arXiv:2002.06349_ , 2020a.
  * Ortiz-Jimenez et al. [2020b] Guillermo Ortiz-Jimenez, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard.  Neural anisotropy directions.  _arXiv preprint arXiv:2006.09717_ , 2020b.
  * Gunasekar et al. [2018] Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro.  Implicit bias of gradient descent on linear convolutional networks.  In _Advances in Neural Information Processing Systems_ , pages 9461–9471, 2018.
  * Yun et al. [2020] Chulhee Yun, Shankar Krishnan, and Hossein Mobahi.  A unifying view on implicit bias in training linear neural networks.  _arXiv preprint arXiv:2010.02501_ , 2020.
  * Sahs et al. [2020a] Justin Sahs, Aneel Damaraju, Ryan Pyle, Onur Tavaslioglu, Josue Ortega Caro, Hao Yang Lu, and Ankit Patel.  A functional characterization of randomly initialized gradient descent in deep re{lu} networks, 2020a.  URL https://openreview.net/forum?id=BJl9PRVKDS.
  * Williams et al. [2019] Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna.  Gradient dynamics of shallow univariate relu networks.  In _Advances in Neural Information Processing Systems_ , pages 8376–8385, 2019.
  * Woodworth et al. [2020] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro.  Kernel and rich regimes in overparametrized models.  _arXiv preprint arXiv:2002.09277_ , 2020.
  * Sahs et al. [2020b] Justin Sahs, Ryan Pyle, Aneel Damaraju, Josue Ortega Caro, Onur Tavaslioglu, Andy Lu, and Ankit Patel.  Shallow univariate relu networks as splines: Initialization, loss surface, hessian, & gradient flow dynamics.  _arXiv preprint arXiv:2008.01772_ , 2020b.
  * Li et al. [2019] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora.  Enhanced convolutional neural tangent kernels.  _arXiv preprint arXiv:1911.00809_ , 2019.
  * Arora et al. [2019] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  In _Advances in Neural Information Processing Systems_ , pages 8139–8148, 2019.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32:8026–8037, 2019.
  * Madry et al. [2017] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Goh [2019] Gabriel Goh.  A discussion of ’adversarial examples are not bugs, they are features’: Two examples of useful, non-robust features.  _Distill_ , 2019.  doi: 10.23915/distill.00019.3.  https://distill.pub/2019/advex-bugs-discussion/response-3.
  * Cheddad et al. [2010] Abbas Cheddad, Joan Condell, Kevin Curran, and Paul Mc Kevitt.  Digital image steganography: Survey and analysis of current methods.  _Signal processing_ , 90(3):727–752, 2010.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Shao et al. [2021] Rulin Shao, Zhouxing Shi, Jinfeng Yi, Pin-Yu Chen, and Cho-Jui Hsieh.  On the adversarial robustness of visual transformers.  _arXiv preprint arXiv:2103.15670_ , 2021.
  * Chen et al. [2021] Zhengsu Chen, Lingxi Xie, Jianwei Niu, Xuefeng Liu, Longhui Wei, and Qi Tian.  Visformer: The vision-friendly transformer.  _arXiv preprint arXiv:2104.12533_ , 2021.
  * Rauber et al. [2017] Jonas Rauber, Wieland Brendel, and Matthias Bethge.  Foolbox: A python toolbox to benchmark the robustness of machine learning models.  _arXiv preprint arXiv:1707.04131_ , 2017.
  * Kurakin et al. [2016] Alexey Kurakin, Ian Goodfellow, and Samy Bengio.  Adversarial examples in the physical world.  _arXiv preprint arXiv:1607.02533_ , 2016.
  * Brendel et al. [2019] Wieland Brendel, Jonas Rauber, Matthias Kümmerer, Ivan Ustyuzhaninov, and Matthias Bethge.  Accurate, reliable and fast robustness evaluation.  In _Advances in Neural Information Processing Systems_ , pages 12861–12871, 2019.
  * Xu et al. [2019] Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao.  Training behavior of deep neural network in frequency domain.  In _International Conference on Neural Information Processing_ , pages 264–274. Springer, 2019.
  * Ghobber and Jaming [2011] Saifallah Ghobber and Philippe Jaming.  On uncertainty principles in the finite dimensional setting.  _Linear algebra and its applications_ , 435(4):751–768, 2011.

##  Appendix A Supplementary Material

###  A.1 Figures

Figure 5: Adversarial Spectrum for: Fully Connected, Deep Fully Connected,
Full-Width Convolutional, Deep Full-Width Convolutional, Locally Connected,
Deep Fully Connected, Bounded-Width Convolutional, Deep Bounded Width
Convolutional models for MNIST (Linear Models), CIFAR100 (Linear Models) and
CIFAR100 (NonLinear Models). Both CIFAR100 results are similar to the CIFAR10
experiments. No difference between MNIST models, which reflects that MNIST is
mainly composed of low frequency features

Figure 6: Comparison of Adversarial Perturbation Norms
$\|\widehat{\delta}\|_{p}$ for $p=1,2$ for different linear and nonlinear
models. The relations between norms of nonlinear models mirror and accentuate
those of linear models. See Results for detailed comparisons.

(a)

(b)

Figure 7: Concentration of energy $\kappa_{high}$ for $\kappa_{r}$ = 15 for
each $\beta_{l}$ for all $l$ versus kernel size (3,7,9,11,15, 21, or 32). All
models were trained for 40 epochs on Grayscale CIFAR10. (a) One hidden layer
models (b) Three hidden layer models.  Figure 8: Average Adversarial
Perturbation Fourier Spectrum for Fully Connected, Full-Width, Locally
Connected and Bounded-Width Linear models. Figure 9: Average Adversarial
Perturbation Fourier Spectrum for Fully Connected, Full-Width, Locally
Connected and Bounded-Width NonLinear models.

###  A.2 Tables

Table 3: Spearman Correlation between Fourier spectrum of Delta and Beta for different models. | Spearman Correlation of $\widehat{\beta}$ and $\widehat{\delta}$
---|---
Model | Linear Model | Nonlinear Model
Fully Connected | 0.353 | 0.439
Deep Fully Connected | 0.343 | 0.504
Full Width Convolutional | 0.276 | 0.327
Deep Full Width Convolutional | 0.272 | 0.452
Locally Connected Linear | 0.240 | 0.275
Bounded Width Convolutional | 0.266 | 0.371
Deep Bounded Width Convolutional | 0.306 | 0.344
Table 4: Frequency-Domain Norms of Predictor $\widehat{\beta}$ and Adv. Pert. $\widehat{\delta}$ for Linear Models. With Equivalent performance (See Sup Figure 7), Convolutional Models have smaller $\|\widehat{\beta}\|_{1}$, supporting the implicit Fourier hypothesis. Model | $\|\widehat{\delta}\|_{2}$ | $\|\widehat{\delta}\|_{1}$ | $\|\widehat{\beta}\|_{2}$ | $\|\widehat{\beta}\|_{1}$
---|---|---|---|---
Fully Connected |  20.77 $\pm$ 1.23 |  505.95 $\pm$ 32.22 |  546.89 $\pm$ 43.37 |  2232.46 $\pm$ 166.27
Full Width Convolution |  17.52 $\pm$ 1.56 |  376.31 $\pm$ 32.66 |  544.83 $\pm$ 42.40 |  1598.37 $\pm$ 181.44
Bounded Width Convolution |  20.65 $\pm$ 1.09 |  556.32 $\pm$ 32.64 |  500.67 $\pm$ 47.46 |  2623.04 $\pm$ 331.42
Deep Fully Connected |  20.83 $\pm$ 1.25 |  503.92 $\pm$ 32.62 |  554.16 $\pm$ 38.95 |  2168.06 $\pm$ 134.07
Deep Full Width Convolution |  17.13 $\pm$ 1.68 |  265.40 $\pm$ 41.72 |  522.99 $\pm$ 39.72 |  1417.68 $\pm$ 213.91
Deep Bounded Width Convolution |  20.57 $\pm$ 0.94 |  550.30 $\pm$ 29.71 |  498.52 $\pm$ 47.15 |  2392.09 $\pm$ 278.55
Table 5: Frequency-Domain Norms of Adv. Pert. $\widehat{\delta}$ for Nonlinear Models. With similar performance (Supp. Table 4), Full Width and Bounded Width convolutional models produce adversarial attacks with smaller $\|\widehat{\delta}\|_{1}$. Model | $\|\widehat{\delta}\|_{2}$ | $\|\widehat{\delta}\|_{1}$
---|---|---
Fully Connected |  22.06 $\pm$ 1.35 |  534.34 $\pm$ 35.93
Locally Connected |  22.32 $\pm$ 1.13 |  587.61 $\pm$ 29.89
Full Width Convolution |  20.57 $\pm$ 1.11 |  405.49 $\pm$ 34.16
Bounded Width Convolution |  24.63 $\pm$ 1.36 |  665.22 $\pm$ 38.55
Shallow ResNet |  26.36 $\pm$ 0.74 |  709.06 $\pm$ 20.76
VGG19 |  23.32 $\pm$ 0.99 |  650.73 $\pm$ 27.87
ResNet18 |  22.42 $\pm$ 0.91 |  626.60 $\pm$ 25.40

##  Appendix B Experimental Details

###  B.1 Model Architecture

Table 6: Model Architectures Model Architecture |  $\\#$ Hidden Layers | Nonlinearity | Channels
---|---|---|---
Fully Connected | 1,3 | None, ReLU | 3072
Bounded Width Convolution | 1,3 | None, ReLU | 32
Full Width Convolution | 1,3 | None, ReLU | 32
Locally Connected | 1,3 | None, ReLU | 32

###  B.2 Model Performance

Table 7: Test Accuracy for all models trained on CIFAR-10. All linear models have similar performance. Nonlinear models exhibit more variability. Model Architecture | Test Accuracy
---|---
Fully Connected (Linear) | 41%
Locally Connected (Linear) | 35%
Full Width Convolution (Linear) | 41%
Bounded Width Convolution (Linear) | 41%
Deep Fully Connected (Linear) | 41%
Deep Full Width Convolution (Linear) | 36%
Deep Bounded Width Convolution (Linear) | 41%
Fully Connected (NonLinear) | 52%
Full-Width Convolution (NonLinear) | 52%
Locally Connected (NonLinear) | 54%
Bounded Width Convolution (NonLinear) | 63%
ViT-2 | 79.8%
ViT-4 | 80.1%
ViT-8 | 78.4%
ViTLoc-2 | 75.3%
ViTLoc-4 | 80.2%
ViTLoc-8 | 74.5%
ResNet18 | 92%

###  B.3 Adversarial Attack Success

Table 8: Adversarial Success for all models trained on CIFAR-10. All values are shown for PGD-Linf of B.5 Model Architecture | Adversarial Success (PGD-Linf)
---|---
Fully Connected (Linear) | 100.0%
Locally Connected (Linear) | 100.0%
Full Width Convolution (Linear) | 100.0%
Bounded Width Convolution (Linear) | 100.0%
Deep Fully Connected (Linear) | 100.0%
Deep Full Width Convolution (Linear) | 100.0%
Deep Bounded Width Convolution (Linear) | 100.0%
Fully Connected (NonLinear) | 100.0%
Full-Width Convolution (NonLinear) | 100.0%
Locally Connected (NonLinear) | 100.0%
Bounded Width Convolution (NonLinear) | 100.0%
ViT-2 | 100.0%
ViT-4 | 99.7%
ViT-8 | 100.0%
ViTLoc-2 | 100.0%
ViTLoc-4 | 100.0%
ViTLoc-8 | 99.9%
ResNet18 | 100.0%

All adversarial attacks were performed on a single GTX 1080 Ti for all 10
thousand testset images.

###  B.4 Training Hyperparameters

Table 9: Learning rates for the various models considered on CIFAR-10. All other hyper-parameters were fixed. Model Architecture | Learning Rate | Batch Size | Learning Rate Drop
---|---|---|---
Bounded Width Convolution | .01 | 128 | Yes
Fully Connected | .01 | 128 | Yes
Locally Connected | .01 | 128 | Yes
Full Width Convolution | .002 | 128 | Yes
Bounded Width Convolution | .002 | 128 | Yes
Table 10: Learning rates for the various models considered on CIFAR-100. All other hyper-parameters were fixed. Model Architecture | Learning Rate | Batch Size | Learning Rate Drop
---|---|---|---
Bounded Width Convolution | .01 | 128 | Yes
Fully Connected | .01 | 128 | Yes
Locally Connected | .01 | 128 | Yes
Full Width Convolution | .002 | 128 | Yes
Bounded Width Convolution | .002 | 128 | Yes
Table 11: Learning rates for the various models considered on MNIST. All other hyper-parameters were fixed. Model Architecture | Learning Rate | Batch Size | Learning Rate Drop
---|---|---|---
Bounded Width Convolution | .01 | 100 | Yes
Fully Connected | .01 | 100 | Yes
Locally Connected | .01 | 100 | Yes
Full Width Convolution | .002 | 100 | Yes
Bounded Width Convolution | .002 | 100 | Yes

###  B.5 Adversarial Attack Configurations

Table 12: Adversarial Attack hyperparameters Attack | Metric | Learning Rate | Number of Steps | Max Norm, $\epsilon$
---|---|---|---|---
Projected Gradient Descent | $L_{\infty}$ | 0.1 | 1000 | 8.0/255.0
Projected Gradient Descent | $L_{2}$ | 0.1 | 1000 | 2.0
Projected Gradient Descent | $L_{1}$ | 0.1 | 200 | 0.1
Brendel-Bethge Attack | $L_{\infty}$ | 1e-03 | 1000 | -
Brendel-Bethge Attack | $L_{2}$ | 1e-03 | 1000 | -

Learning Rates. All the models adversarial attacks were generated using the
configuration above with the Foolbox package [31].

##  Appendix C Dynamics of Adversarial Examples in Frequency Domain

We have observed that adversarial perturbations reflect the type of features
learned by the model. We propose that this is an interesting lens to
understand more broadly what are neural networks learning. For example, one
theory related to feature learning on neural networks is the F-principle [34].
This work found that deep neural networks first learned low frequency features
and then move towards high frequency features. Here we hypothesize that this
low to high frequency feature learning during training should be reflected on
the adversarial perturbations a model is sensitive to at any given point
during learning. This will be further evidence that adversarial perturbations
are a reflection of the function learned by the model but not just spurious
correlations. In order to test this hypothesis, we trained a ResNet18 model on
the CIFAR-10 dataset [23] (MIT) using PyTorch [24]. Then, we used the Foolbox
package [31] (MIT) to generate adversarial attacks for every example in the
test set for intermediate models during training, via an $\ell_{\infty}$
Projected Gradient Descent attack [32] (see Supplementary Sec. B.5). In Sup.
Figure 10, we see the evolution of the frequency spectrum of the adversarial
perturbations: early in training the adversarial perturbations tend to contain
low frequencies (with higher norms), and as training progresses, there is a
consistent evolution towards higher frequencies (with lower norms). Thus,
adversarial perturbations evolve through learning to higher frequencies and
lower amplitudes.

This phenomenon is also confirmed in Sup. Figures 11(a) and 11(b). Here, we
observe the marginal radial and angular distributions $E(k_{r}),E(k_{\phi})$
of the energy spectrum $E(k_{r},k_{\phi}):=|\widehat{\delta}(k_{r}\cos
k_{\phi},k_{r}\sin k_{\phi})|_{\mathbb{C}}^{2}$, where $(k_{r},k_{\phi})$
denotes polar coordinates in the frequency domain. We also observe that (i)
the radial energy distribution shifts from low to high frequency, and (ii) the
angular energy distribution becomes more uniform (ring structure). The
evolution of the adversarial perturbations in the frequency domain shows an
optimization bias of state-of-the-art convolutional models to frequency-based
features.

Figure 10: Top: Dynamics of $\ell_{2}$ and $\ell_{\infty}$ norms of the
adversarial perturbations ($\delta$) during training of ResNet18. Over
training, adversarial perturbations become smaller in amplitude (the norm
increase after around 20 epochs is due to learning rate reset which decreases
performance). Bottom: Evolution of the adversarial perturbation spectrum
($\widehat{\delta}$) over training. The adversarial perturbation spectrum
evolves from low-frequencies to high frequencies as performance increases.

(a)

(b)

Figure 11: (a) Distribution of radial energy $k_{r}$ of the Fourier spectrum
of adversarial perturbations. (b) Distribution of angular energy $k_{\phi}$
(in degree) of the Fourier spectrum of adversarial perturbations. We observe
an evolution of adversarial perturbations over training from lower to higher
frequencies for the ResNet18 model, and from certain directions to all
directions uniformly.

##  Appendix D Formal Proofs of High Frequency Bias

See 1

###### Proof.

Let us first concentrate on a single convolutional filter
$w_{l}\in\mathbb{R}^{D}$. Given an arbitrary choice of frequency interval
$\Omega:=\\{-k,\ldots,0,\ldots,+k\\}$ and space interval
$S:=\\{-a,\ldots,0,\ldots,+a\\}$, we want to prove that reducing the energy
fraction in the complementary set $S^{c}$ implies that we must increase the
energy fraction in the complementary set $\Omega^{c}$. The result follows from
a direct application of the Uncertainty Principle for finite-dimensional
vector spaces, as shown e.g. in Ghobber-Jaming [35]. In particular let
$\\{\widehat{\boldsymbol{\beta}_{i}}\\}_{i=1}^{D}$ be the coefficients of the
Discrete Fourier Transform (DFT) From equation 1.2 in [35] we have

$\|w\|_{\ell^{2}(S^{c})}+\|\widehat{w}\|_{\ell^{2}(\Omega^{c})}\geq\|w\|_{2}C(S,\Omega)$
(1)

where $C(S,\Omega)$ is constant when the intervals $S,\Omega$ are fixed.
Dividing both sides of the inequality by $\|w\|_{2}$ we have

$\kappa(S^{c})+\widehat{\kappa}(\Omega^{c})\geq\textrm{const}$

where $\kappa(\mathcal{A}):=\|w\|_{\ell^{2}(\mathcal{A})}/\|w\|_{2}$ is the
spatial energy concentration of $w$ in the index set $\mathcal{A}$ and
$\widehat{\kappa}(\mathcal{B})$ is the analogous quantity for
$\widehat{w}_{l}$. Thus increasing the energy concentration in the spatial
interval $S$ will decrease it in $S^{c}$ and by the inequality above increases
$\kappa(\Omega^{c})$. In other words, considering $\Omega$ to be the low
frequencies, there will be an increase in the high frequency energy
concentration.

The reasoning above can be extended from a single convolutional filter to the
full end-to-end weights vector, $\beta:=\star_{l=1}^{L-1}w_{l}$, as follows.
Note first that, using the convolution theorem, the Discrete Fourier transform
of $\beta$ is the Hadamard product of the Discrete Fourier transforms of the
per-layer weights $w_{l}$ i.e.

$\widehat{\beta}=\widehat{w}_{L-1}\odot\cdots\odot\widehat{w}_{1}.$

Let us consider the Fourier energy in the low frequency $\Omega$:

$\widehat{\beta}_{\Omega}=\widehat{w}_{L-1,\Omega}\odot\cdots\odot\widehat{w}_{1,\Omega}.$

Taking the $\ell_{2}$ norm and using the inequality $\|a\odot
b\|_{2}\leq\|a\|_{2}\|b\|_{2}$ multiple times we can then write

$\kappa(\Omega,\beta)\leq\prod_{l=1}^{L-1}\kappa(\Omega,w_{l}).$

Let us now decrease the energy content in each spatial domain $S$ of the
filters $w_{l}$. By the reasoning above this will increase the energy content
in Fourier domain in the intervals $\Omega^{c}$ i.e. decrease each
$\kappa(\Omega,w_{l})$. By the last inequality this will decrease
$\kappa(\Omega,\beta)$, i.e. increase the energy in the high frequency domain
($\Omega^{c}$) in $\beta$. ∎

######  Lemma 2.

Concentrating the kernel energy in spatial domain increases the implicit
regularization term in the optimization in [Gunasekar]:

$\forall a\textquoteright<a:R_{BWC;a\textquoteright}(\beta)\geq
R_{BWC;a}(\beta)$

###### Proof.

Reducing filter size $K$ will increase energy in high freqs i.e. $\forall
K\textquoteright<K:\kappa_{high}(\beta;K\textquoteright)>\kappa_{high}(\beta;K)$.
This means that the space-limiting constraints only grow more stringent as we
reduce $K$, implying that the result of the optimization problem for the
implicit regularizer will only increase in cost i.e. $\forall
K\textquoteright<K:R_{BWC;K\textquoteright}(\beta)\geq R_{BWC;K}(\beta)$ for
any candidate linear predictor $\beta$. (Note that this does not refer to the
learned features $\beta^{*}$ which actually depends on the training data as
well). In summary, all else being equal, reducing the kernel size $K$
causes/induces a bias towards more concentration of energy in higher
frequencies in $\beta$. ∎

In summary reducing the kernel size causes/induces a bias towards more
concentration of energy in higher frequencies in $\beta$.