# Understanding the robustness difference between stochastic gradient descent
and adaptive gradient methods

Avery Ma<EMAIL_ADDRESS>
University of Toronto
Vector Institute Yangchen Pan<EMAIL_ADDRESS>
University of Oxford Amir-massoud Farahmand<EMAIL_ADDRESS>
University of Toronto
Vector Institute

###### Abstract

Stochastic gradient descent (SGD) and adaptive gradient methods, such as Adam
and RMSProp, have been widely used in training deep neural networks. We
empirically show that while the difference between the standard generalization
performance of models trained using these methods is small, those trained
using SGD exhibit far greater robustness under input perturbations. Notably,
our investigation demonstrates the presence of irrelevant frequencies in
natural datasets, where alterations do not affect models’ generalization
performance. However, models trained with adaptive methods show sensitivity to
these changes, suggesting that their use of irrelevant frequencies can lead to
solutions sensitive to perturbations. To better understand this difference, we
study the learning dynamics of gradient descent (GD) and sign gradient descent
(signGD) on a synthetic dataset that mirrors natural signals. With a three-
dimensional input space, the models optimized with GD and signGD have standard
risks close to zero but vary in their adversarial risks. Our result shows that
linear models’ robustness to $\ell_{2}$-norm bounded changes is inversely
proportional to the model parameters’ weight norm: a smaller weight norm
implies better robustness. In the context of deep learning, our experiments
show that SGD-trained neural networks have smaller Lipschitz constants,
explaining the better robustness to input perturbations than those trained
with adaptive gradient methods. Our source code is available at
https://github.com/averyma/opt-robust.

##  1 Introduction

Adaptive gradient methods, such as Adam (Kingma & Ba, 2015) and RMSProp
(Hinton et al., 2012), are a family of popular techniques to optimize machine
learning (ML) algorithms. They are an extension of the traditional gradient
descent method, which uses the gradient of a differentiable objective function
to update the model’s parameters in the direction that improves the objective.
To speed up the optimization procedure, the adaptive gradient methods
introduce a coordinate-wise learning rate to adjust the update for each
parameter based on its individual gradient. Previous empirical work
investigates the difference in the standard generalization between models
trained using SGD and adaptive gradient methods (Wilson et al., 2017; Agarwal
et al., 2020), while recent efforts have focused on understanding the implicit
bias of SGD (Gunasekar et al., 2017; Soudry et al., 2018; Lyu & Li, 2020) and
adaptive gradient algorithms (Qian & Qian, 2019; Wang et al., 2021).

Nevertheless, our result shows that in practice such a gap in the standard
generalization is relatively small, in contrast to the difference between the
robustness of models trained using those algorithms. While more ML-based
systems are deployed in the real world, the models’ robustness, their ability
to maintain their performance when faced with noisy or corrupted inputs, has
become an important criterion. There is a large volume of literature on
developing specialized methods to improve the robustness of neural networks
(Silva & Najafirad, 2020), yet practitioners still simply use standard methods
to train their models. In fact, a recent survey shows that only 3 of the 28
organizations have developed their ML-based systems with the improvement in
robustness in mind (Kumar et al., 2020). Therefore, this motivates us to
understand the effect of optimizers on the robustness of models obtained in
the standard training regime. In particular, we focus on models trained using
SGD and adaptive gradient methods. Note that our primary focus lies in
understanding the robustness difference, and robustification falls outside the
scope of our work.

Figure 1: Comparison between models trained using SGD, Adam, and RMSProp
across seven benchmark datasets. Each colored triplet denotes models on the
same dataset. Models trained by different algorithms have similar standard
generalization performance, but there is a distinct robustness difference as
measured by the test data accuracy under Gaussian noise, $\ell_{2}$ and
$\ell_{\infty}$ bounded adversarial perturbations (Croce & Hein, 2020).
Results are averaged over three independent model initializations and
trainings.

###  1.1 The Robustness Difference between Models Trained by Different
Algorithms

As a first step, we compare how models, trained with SGD, Adam, and RMSProp,
differ in their standard generalization and robustness on seven benchmark
datasets (LeCun, 1998; Xiao et al., 2017; Krizhevsky & Hinton, 2009; Netzer et
al., 2011; Howard, ; Fei-Fei et al., 2004). In our experiments, we evaluate
standard generalization using the accuracy of the trained classifier on the
original test dataset. To measure robustness, we consider the classification
accuracy on the test dataset perturbed by Gaussian noise, $\ell_{2}$ and
$\ell_{\infty}$ bounded adversarial perturbations (Croce & Hein, 2020). We
follow the default Pytorch configuration to train all the models and sweep
through a wide range of learning rates. The final model is selected with the
highest validation accuracy. Models are trained in a vanilla setting in which
data augmentations are limited to random flipping. Additional discussions on
batch normalization (Ioffe & Szegedy, 2015), data augmentation, optimization
schedules, and network designs are detailed in Appendix B. Appendix C presents
comprehensive results from the experiment depicted in Figure 1, including the
approach for selecting perturbations for each dataset. While our primary
experiments are centered around models based on convolutional neural networks,
within the computer vision domain, we also extend our analysis to include
results from experiments on Vision Transformers (Dosovitskiy et al., 2021) and
an audio dataset (Warden, 2018). The results of these additional experiments
are consistent with the findings presented in this section and are detailed in
Appendix C. Additionally, visualizations of the perturbations can be found in
Appendix G.

Figure 1 compares the models trained with SGD and the adaptive gradient
methods, pointing to two important observations. First, the relatively small
vertical differences among the three models, on a given dataset, show that the
models have similar standard generalization performance despite being trained
by different algorithms. On the other hand, we observe, under all three types
of perturbations, a large horizontal span with SGD always positioned on the
far right side among the three. This indicates that models trained by SGD
significantly outperform models trained by the other two in terms of their
robustness against perturbations.

###  1.2 Contributions

Previous optimization work often studies how the structure of the dataset
affects the dynamics of learning. For example, some focus on a dataset with
different feature strengths (Amari et al., 2021; Pezeshki et al., 2021), while
others assume a linearly separable dataset (Wilson et al., 2017; Gunasekar et
al., 2017; Soudry et al., 2018). In our work, we investigate how the frequency
characteristics of the dataset impact the robustness of models trained by SGD
and adaptive gradient methods. We make the following contributions:

  * •

We demonstrate that natural datasets contain irrelevant frequencies, which,
when removed, have negligible effects on standard generalization performance
(Sec. 3.1).

  * •

We also observe that neural networks trained by different algorithms can have
very different robustness against perturbations in the direction of the
irrelevant frequencies (Sec. 3.2).

  * •

Those observations lead to our claim that models only need to learn how to
correctly use relevant information in the data to optimize the training
objective, and because their use of the irrelevant information is under-
constrained, it can lead to solutions sensitive to perturbations (Sec. 3).

  * •

Our analysis of linear models on least square regression shows that linear
models’ robustness to $\ell_{2}$-norm bounded changes is inversely
proportional to the model parameters’ weight norm: a smaller weight norm
implies better robustness (Sec. 4.1).

  * •

We study the learning dynamics of GD and signGD, a memory-free version of Adam
and RMSProp, with linear models. With a three-dimensional input space, the
analysis shows that models optimized with GD exhibit a smaller weight norm
compared to their signGD counterparts (Sec. 4.2).

  * •

To generalize this result in the deep learning setting, we demonstrate that
neural networks trained by Adam and RMSProp often have a larger Lispchitz
constant and, consequently, are more prone to perturbations (Sec. 5).

Specifically, in the analysis of linear models, we design a least square
regression task using a synthetic dataset whose frequency representation
mimics the natural datasets. This setting allows us to i) mathematically
define the standard and adversarial population risks, ii) design a learning
task that has multiple optima for the standard population risk, each with a
different adversarial risk, and iii) theoretically analyze the learning
dynamics of various algorithms.

##  2 Background

In this section, we briefly review the essential background to help understand
our work. Specifically, we discuss formulations of adaptive gradient methods,
previous work on the adversarial robustness of the model, and methods of
representing signals in the frequency domain.

###  2.1 Optimizations with Adaptive Gradient Algorithms

Consider the empirical risk minimization problem with an objective of the form
$\mathcal{L}(w)=\frac{1}{N}\sum_{n=1}^{N}\ell(X_{n},Y_{n};w)$, where
$w\in\mathbb{R}^{d}$ is a vector of weights of a model,
$\\{(X_{n},Y_{n})\\}_{n=1}^{N}$ is the training dataset and $\ell(x,y;w)$ is
the point-wise loss quantifying the performance of the model on data point
$(x,y)$. A common approach in training machine learning models is to reduce
the loss via SGD which iteratively updates the model based on a mini-batch of
data points drawn uniformly and independently from the training set:

$g(w)=\frac{1}{|\mathcal{B}|}\sum_{n\in\mathcal{B}}\nabla_{w}\ell(X_{n},Y_{n};w),$
(1)

where $\mathcal{B}\subset\left\\{1,...,N\right\\}$ denotes the minibatch and
has a size of $|\mathcal{B}|\ll N$. The update rule of SGD is
$w(t+1)=w(t)-\eta(t)g(w(t))$, where $\eta(t)\in\mathbb{R}^{+}$ denotes the
learning rate.111From this point forward, subscripts denote vector/matrix
coordinates, and numbers in parentheses denote update iterations unless
otherwise specified.

A family of adaptive gradient methods has been used to accelerate training by
updating the model parameters based on a coordinate-wise scaling of the
original gradients. Methods such as Adam and RMSprop have demonstrated
significant acceleration in training deep neural networks (Wilson et al.,
2017). Many adaptive gradient methods can be written as

$\displaystyle m(t+1)$ $\displaystyle=\beta_{1}g(w(t))+(1-\beta_{1})m(t)$
$\displaystyle v(t+1)$ $\displaystyle=\beta_{2}g(w(t))^{2}+(1-\beta_{2})v(t)$
$\displaystyle w(t+1)$
$\displaystyle=w(t)-\eta(t)\frac{m(t+1)}{\sqrt{v(t+1)}+{\epsilon}},$ (2)

where $g(w(t))$ is the stochastic estimate of gradient used by SGD (1), $m$
and $v$ are the first and second-order memory terms with their strength
specified by $\beta_{1}$ and $\beta_{2}$, and ${\epsilon}$ is a small constant
used to avoid division-by-zero. Such a general form has been widely used to
study the dynamics of adaptive gradient algorithm (Wilson et al., 2017; da
Silva & Gazeau, 2020; Ma et al., 2022b). For example, Adam corresponds to
$\beta_{1},\beta_{2}\in(0,1)$, and RMSProp is recovered when $\beta_{1}=1$ and
$\beta_{2}\in(0,1)$. Notice that such updates rely on the history of past
gradients, and this makes the precise understanding and analysis of adaptive
gradient methods more challenging (Duchi et al., 2011). Recent work analyzes
the learning dynamics of adaptive gradient methods by separately considering
the direction and the magnitude of the update (Kingma & Ba, 2015; Balles &
Hennig, 2018; Ma et al., 2022b). As a simple example, to demonstrate how
adaptive gradient methods can potentially accelerate learning compared to the
vanilla SGD, consider a memory-free version of (2.1) with
$\beta_{1}=\beta_{2}=1$ and ${\epsilon}=0$. It is easy to see that the update
rule in (2.1) becomes sign gradient descent:

$\displaystyle w(t+1)$
$\displaystyle=w(t)-\eta(t)\operatorname{sign}(g(w(t)))$
$\displaystyle=w(t)-\vec{\eta}(t)\odot g(w(t)),$ (3)

where $\odot$ denotes Hadamard product, $\vec{\eta}(t)\in\mathbb{R}^{d}$ is a
coordinate-wise learning rate based on the absolute value of the weight, i.e.,
$\vec{\eta}(t)=\frac{\eta(t)}{|g(w(t))|}$. Therefore, $\vec{\eta}(t)$ accounts
for the magnitude of the weight and a larger learning rate is used for
parameters with smaller gradients.

In general, gradient-sign-based optimization methods are not successful in
training deep learning models (Riedmiller & Braun, 1993; Ma et al., 2022b),
nevertheless, methods such as signGD can shed light on the learning dynamics
of adaptive gradient methods (Karimi et al., 2016; Balles & Hennig, 2018;
Moulay et al., 2019). For example, recent work by Ma et al. (2022b) studies
the behavior of adaptive gradient algorithms in the continuous-time limit.
They demonstrate that under a fixed $\beta_{1}$ and $\beta_{2}$, the memory
effect for both Adam and RMSprop diminishes and the continuous-time limit of
the two algorithms follows the dynamics of signGD flow. In this work, the deep
learning models on which we observe the robustness difference are trained
using Adam and RMSProp, with the exception of Sec. 4, where we focus on
signGD, a memory-free version of Adam and RMSProp, and gradient descent to
help us understand the robustness gap between models trained using SGD and
adaptive gradient methods in a simple setting.

###  2.2 Robustness of ML Models

An important assumption of most modern ML models is that samples from the
training and testing dataset are independent and identically distributed
(i.i.d.); however, samples collected in the real world rarely come from an
identical distribution as the training data, as they are often subject to
noise. It is known that ML models can achieve impressive success on the
original testing dataset, but exhibit a sharp drop in performance under
perturbations (Szegedy et al., 2014). Such an observation has posed concerns
about the potential vulnerabilities for real-world ML applications such as
healthcare (Qayyum et al., 2020), autonomous driving (Deng et al., 2020) and
audio systems (Li et al., 2020). Models’ robustness performance has become an
important secondary metric in the empirical evaluation of new training
methods, such as data augmentations (Zhang et al., 2018; Hendrycks et al.,
2020; Verma et al., 2019; Ma et al., 2022a) and robust optimization techniques
(Zhai et al., 2021). Generally, the robustness property of models is assessed
by examining the model performance under multiple perturbations (Ding et al.,
2020; Shen et al., 2021; Kuang et al., 2018). A wide variety of approaches
have been proposed to improve the robustness of the model through
regularizations (Goodfellow et al., 2015; Simon-Gabriel et al., 2019; Wen et
al., 2020; Ma et al., 2020; Foret et al., 2021; Wei et al., 2023), data
augmentation (Madry et al., 2018; Rebuffi et al., 2021; Gowal et al., 2021; Ma
et al., 2022a), and novel network architectures (Wu et al., 2021; Ma et al.,
2021; Huang et al., 2021). However, most industry practitioners are yet to
come to terms with improving security in developing ML systems (Kumar et al.,
2020). Since SGD, Adam, and RMSProp have been the go-to optimizer in both
academic and industrial settings, this motivates us to understand the
robustness of models trained by them and built on the standard training
pipelines, i.e., minimizing some losses on the original training set.

###  2.3 Frequency Representation of Signals

Natural signals are highly structured (Schwartz & Simoncelli, 2001). They
often consist of statistically significant (or insignificant) patterns with a
large amount of predictability (or redundancy). Such a phenomenon has been
observed in both natural images (Ruderman, 1994; Simoncelli, 1997; Huang &
Mumford, 1999) and natural audio signals (McAulay & Quatieri, 1986; Attias &
Schreiner, 1996; Turner, 2010). To understand the structure of signals and
identify patterns from them, one technique is to decompose the signal into
multiples of “harmonics” or “overtones”: a superposition of periodic waves
with varying amplitudes and in varying phases. For example, Fourier (1822)
first proposed to analyze complicated heat equations using well-understood
trigonometric functions, a method now called the Fourier transformation. This
new representation allows us to precisely study the structure and the
magnitude of any repeating patterns presented in the original waveform. For
the understanding of digital signals, such a process is called discrete-time
signal processing (Oppenheim et al., 2001).

Many discrete harmonic transformations exist, such as the discrete Fourier
transform, the discrete cosine transform (DCT) (Ahmed et al., 1974) and the
wavelet transform (Mallat, 1999). The analysis in this work utilizes the type-
II DCT, but other techniques can be applied as well and we expect similar
results. Concretely, consider a $d$-dimensional signal $x\in\mathbb{R}^{d}$ in
the spatial domain. The same signal can be alternatively represented as a
discrete sum of amplitudes multiplied by its cosine harmonics:
$\tilde{x}_{k}=\sum_{j=0}^{d-1}x_{j}\cos\left[\frac{\pi}{d}\left(j+\frac{1}{2}\right)k\right]$
for $k=0,...,d-1$, where the transformed signal $\tilde{x}$ has a frequency-
domain representation.222Indices range from $0$ to $d-1$, as zero-frequency is
commonly used to refer to a signal with a constant everywhere. Because DCT is
linear, it can be carried out using a matrix operation, i.e., $\tilde{x}=Cx$,
where $C$ is a $d\times d$ DCT transformation matrix with values specified by

$C_{kj}^{(d)}=\sqrt{\frac{\alpha_{k}}{d}}\cos\left[\frac{\pi}{d}\left(j+\frac{1}{2}\right)k\right],$
(4)

where $\alpha_{0}=1$ and $\alpha_{k}=2$ for $k>0$. In particular, $\tilde{x}$
can be written as a matrix-vector product between the transformation matrix
$C$ and the column vector $x$:

$\begin{bmatrix}\tilde{x}_{0}\\\ \tilde{x}_{1}\\\ \vdots\\\
\tilde{x}_{d-1}\end{bmatrix}=\begin{bmatrix}\sqrt{\frac{1}{d}}&\sqrt{\frac{1}{d}}&\cdots&\sqrt{\frac{1}{d}}\\\
\sqrt{\frac{2}{d}}\cos\frac{\pi(2(0)+1)(1)}{2d}&\sqrt{\frac{2}{d}}\cos\frac{\pi(2(1)+1)(1)}{2d}&\cdots&\sqrt{\frac{2}{d}}\cos\frac{\pi(2(d-1)+1)(1)}{2d}\\\
\vdots&\vdots&\vdots&\vdots\\\
\sqrt{\frac{2}{d}}\cos\frac{\pi(2(0)+1)(d-1)}{2d}&\sqrt{\frac{2}{d}}\cos\frac{\pi(2(1)+1)(d-1)}{2d}&\cdots&\sqrt{\frac{2}{d}}\cos\frac{\pi(2(d-1)+1)(d-1)}{2d}\end{bmatrix}\begin{bmatrix}x_{0}\\\
x_{1}\\\ \vdots\\\ x_{d-1}\end{bmatrix}.$ (5)

Notice that $C$ is a real orthogonal matrix whose rows consists of periodic
cosine bases with increasing frequencies. Therefore, the absolute value of
$\tilde{x}$ at a particular dimension indicates the magnitudes of the
corresponding basis function, and a higher dimension in $\tilde{x}$ means the
basis function is of higher frequency. Another important property of DCT is
its invertibility. That is, signals in the frequency domain can be converted
back to the spatial-temporal domain via the inverse DCT (iDCT):
$x=C^{-1}\tilde{x}=C^{\top}\tilde{x}$. In the example above, we discussed one-
dimensional DCT which is applied to vectors and is used in the linear analysis
in Sec. 4. Transformations on images require two-dimensional DCT and can be
done using $\tilde{x}=CxC^{\top}$, where $x,\tilde{x}\in\mathbb{R}^{d\times
d}$, and $C$ is defined in (4); and the inverse two-dimensional DCT is
$x=C^{\top}\tilde{x}C$. For more details on two-dimensional DCT, we refer the
reader to Pennebaker & Mitchell (1992).

Previous work analyzes the sensitivity of neural network classifiers by
examining the frequency characteristics of various types of perturbations,
with an emphasis on understanding how data augmentation affects the robustness
of the model (Yin et al., 2019). In our work, the frequency interpretation of
signals is an integral part of understanding the robustness difference between
models trained by SGD and adaptive gradient methods. This perspective allows
us to study the structure of complex signals using well-understood periodic
basis functions such as cosines and understand the energy distribution of
signals by examining the amplitude of the basis function. In particular, the
energy of a discrete signal $x$ is defined as
$E(x)=\sum_{i=0}^{d-1}|x_{i}|^{2}$, and by Parseval’s theorem, is equivalent
to the sum of squared amplitudes across all the bases, i.e.,
$E(x)=E(\tilde{x})=\sum_{i=0}^{d-1}|\tilde{x}_{i}|^{2}$. Natural images are
primarily made of low-frequency signals333We will always use the term “high”
or “low” frequency on a relative scale.: a high concentration of energy in the
low-frequency harmonics renders the amplitude of the higher-frequency
harmonics almost negligible (Tolhurst et al., 1992; Schaaf & Hateren, 1996),
as shown in Figure 8 in Appendix G. Moreover, we show in Sec. 3.1 that there
exist frequencies in natural datasets, which if removed from the training
data, do not affect the standard generalization performance of the model.
Based on this observation, in Sec. 4, we construct a synthetic dataset that
mimics the characteristics of natural signals, and it allows us to study the
learning dynamics of various optimization algorithms in a controlled setting.

##  3 A Claim on How Models Use Irrelevant Frequencies

Why do models trained by different optimization algorithms behave similarly in
the standard setting where the training and the test inputs are i.i.d., while
they perform drastically differently when faced with noisy or corrupted data?
To answer this question, we first observe that there is irrelevant information
in the natural dataset (Observation I), and attenuating them from the training
input has negligible effects on the standard generalization of the model. This
leads to our claim:

######  Claim 3.1.

To optimize the standard training objective, models only need to learn how to
correctly use relevant information in the data. Their use of irrelevant
information in the data, however, is under-constrained and can lead to
solutions sensitive to perturbations.

Because of this, by targeting the perturbations toward the subset of the
signal that contains irrelevant information, we notice that models trained by
different algorithms exhibit very different performance changes (Observation
II).

###  3.1 Observation I: Irrelevant Frequencies in Natural Signals

Previous work demonstrated that the magnitude of the frequency components in
natural images decreases as the frequency increases, and this decrease follows
a $\frac{1}{f^{2}}$ relationship (Ruderman, 1994; Wainwright & Simoncelli,
1999). In Figure 8 of Appendix G, we make the observation on several common
vision datasets that the distribution of spectral energy heavily concentrates
at the low end of the frequency spectrum and decays quickly towards higher
frequencies. The spectral sensitivity of the human eyes is limited (Gross,
2005), so patterns with low magnitudes and high frequencies are not important
from the perspective of human observers, as they appear to us as nearly
invisible and unintuitive information in the scene (Schwartz & Simoncelli,
2001; Schwartz, 2004). For machines, image-processing methods have long
exploited the fact that most of the content-defining information in natural
images is represented in low frequencies, and the high-frequency signal is
redundant, irrelevant, and is often associated with noise (Wallace, 1991; Guo
et al., 2020; Sharma et al., 2019).

Similarly, the notion of irrelevant frequencies also exists when training a
neural network classifier. One way to illustrate this is by taking a
supervised learning task, removing the irrelevant information from the
training input, and then assessing the model’s performance using the original
test data. We observe that when modifying the training dataset by removing
subsets of the signal with low spectral energy (Figure 2a) or high frequencies
(Figure 2b), there is a negligible effect on models’ classification accuracy
on the original test data. In Appendix D, we explain how images are modified
in detail, and visualizations of the modified images are included in Appendix
G. In both settings after reducing more than half of the DCT basis vectors to
zeroes in the training data, the model’s generalization ability remains
strong. This observation suggests there is a considerable amount of irrelevant
information in naturally occurring data from the perspective of a neural
network classifier, and such information is often featured with low spectrum
energy or lives at the high end of the frequency spectrum.

(a) Parts of the signal with low spectral energy is irrelevant.

(b) Parts of the signal with high-frequency basis is irrelevant.

Figure 2: Irrelevant frequencies exist in the natural data. Accuracy on the
original test set remains high when the training inputs are modified by
removing parts of the signal with a) low spectrum energy and b) high
frequencies. Stars represent test accuracy on models trained using the
original training input. In setting a), training images are filtered based on
the magnitude of the DCT basis. Specifically, parts of the image with DCT
bases that have a magnitude in the bottom $\frac{p}{100}$-th percentile are
removed, so a large $p$ means more information is discarded. In setting b),
training images are low-pass filtered, and $p$ denotes the percentage of the
high-frequency components that are discarded in the training data. We explain
the formulation of the two settings in Appendix D. Examples of the modified
inputs are included in Appendix G.

This observation leads to the first part of Claim 3.1. That is, models only
need to learn how to correctly use the crucial class-defining information from
the training data to optimize the training objective. On the other hand, the
extent to which they utilize irrelevant information in the data is not well-
regulated. This can be problematic and lead to solutions sensitive to
perturbations. In Sec. 4, we validate Claim 3.1 using a linear regression
analysis with a synthetic dataset that contains irrelevant information. We
demonstrate there exist multiple optima of the training objective and those
solutions can all correctly use the relevant information in the data, but the
way they exclude irrelevant information from computing the output is
different. Specifically, a robust model disregards irrelevant information by
assigning a weight of zero to it, but a non-robust model has certain non-zero
weights which, when combined with the irrelevant information in the input,
yield a net-zero effect in the output. In this case, although the two models
are indistinguishable under the original training objective, the non-robust
model will experience a reduction in model performance should this irrelevant
information become corrupted at test time.

###  3.2 Observation II: Model Robustness along Irrelevant Frequencies

Let us now focus on the second part of the claim. If models’ responses to
perturbations along the irrelevant frequencies explain their robustness
difference, then we should expect a similar accuracy drop between models when
perturbations are along relevant frequencies, but a much larger accuracy drop
on less robust models when test inputs are perturbed along irrelevant
frequencies. Consider the robustness of the models when the test data are
corrupted with Gaussian noise: the perturbation along each spatial dimension
is i.i.d and drawn from a zero-mean Gaussian distribution with finite
variance. This type of noise is commonly referred to as the additive white
Gaussian noise, where white refers to the property that the noise has uniform
power across the frequency spectrum (Diebold, 1998). Nevertheless, the
previous discussion suggests that noise along different frequencies does not
have an equal impact on the models’ output. To verify this, we assess the
impact on model accuracy by perturbing only specific frequency ranges of the
test inputs with band-limited Gaussian noise.

To construct the band-limited Gaussian noise, we first follow the previous
work (Wang et al., 2020) to group DCT basis vectors based on their distance to
the 0-frequency DC term and divide the entire DCT spectrum into ten bands
where each band occupies the same number of DCT bases. This is to ensure an
identical $\ell_{2}$ norm among all the perturbations. Denote the binary mask
of the $i$-th band by using $M^{(i)}\in\left\\{0,1\right\\}^{d\times d}$, its
corresponding band-limited Gaussian noise is $\Delta
x^{(i)}=C^{\top}(M^{(i)}\odot\delta)C$, where
$\delta\sim\mathcal{N}(0,\sigma^{2}I_{d\times d})$ and $C$ is the DCT
transformation matrix defined in (4). Figure 3 illustrates how the frequency
bases are grouped into ten equally sized bands and examples of the band-
limited Gaussian noise. Denote the perturbations by using $\Delta x^{(i)}$,
with $\Delta x^{(0)}$ and $\Delta x^{(9)}$ representing the lowest and the
highest band, respectively. To investigate the effect of the perturbation
$\Delta x^{(i)}$ on the models, we measure the change in classification
accuracy when the test inputs are perturbed by $\Delta x^{(i)}$:

$\frac{1}{N}\sum_{n=1}^{N}\mathbb{I}\left\\{F(X_{n})=Y_{n}\right\\}-\frac{1}{NK}\sum_{n=1}^{N}\sum_{k=1}^{K}\mathbb{I}\left\\{F(X_{n}+\Delta
x^{(i)}_{k})=Y_{n}\right\\},$ (6)

where $F$ is a neural network classifier, $\\{(X_{n},Y_{n})\\}_{n=1}^{N}$
represents the test dataset, each test input is perturbed by i.i.d sampled
$\Delta x^{(i)}_{k}$ and the subscript $k$ is used to differentiate between
$K$ instances of the randomly sampled noise; and we use $K=10$ in our
experiments. It is important to realize in (6) that the additive noise $\Delta
x$ is applied to the spatial signal $X$, although we are limiting the
frequency band of the noise.

Figure 3: Visualization of the band-limited Gaussian perturbations. The DCT
spectrum is divided into ten equally sized bands to generate band-limited
Gaussian perturbations. Denote them by using $\Delta x^{(i)}$, where
$i\in\left\\{0,1,...,9\right\\}$. The frequency represented in the spectrum
plot increases from the top-left (lowest frequency) to the bottom-right corner
(highest frequency). Therefore, as the band moves towards higher frequencies,
perturbations exhibit more high-frequency checkerboard patterns.

(a)  (b)  (c)

Figure 4: The effect of band-limited Gaussian perturbations on the model.
Perturbations from the lowest band, i.e., $\Delta x^{(0)}$, have a similar
effect on all the models, despite being trained by different algorithms and
exhibiting different robustness properties. On the other hand, models’
responses vary significantly when the perturbation focuses on higher frequency
bands. The results are averaged over three independently initialized and
trained models, and the shaded area indicates the standard error among the
three models.

Figure 4 demonstrates how the classification accuracy degrades under different
band-limited Gaussian noises on MNIST, CIFAR100, and Imagenette; and results
on the other datasets are included in Appendix G. First, notice that the
perturbation from the lowest band $\Delta x^{(0)}$ has a similar impact on all
the models regardless of the algorithm they are trained by. There is however a
noticeable difference in how models trained by SGD and adaptive gradient
methods respond to perturbations from higher frequency bands. On models
trained by SGD, the flattened curve implies that the effect of high-frequency
perturbations on the generalization performance quickly diminishes to zero,
suggesting that models are not sensitive to changes along the dimensions of
irrelevant frequencies. Contrarily on models trained by the two adaptive
gradient methods, we observe a difference in the way models respond to
perturbations of higher frequency bands. On CIFAR100, for example, the two
models are highly vulnerable to Gaussian perturbations from bands 5 to 7. This
observation shows that when models, during their training phase, do not have
mechanisms in place to limit their use of irrelevant frequencies, their
performance can be compromised if data along irrelevant frequencies become
corrupted at test time.

One can also observe that models’ responses to high-frequency Gaussian
perturbations varies among datasets. This can be attributed to the fact that
(ir-)relevant frequencies are most likely going to be a unique characteristic
for a particular dataset. We do not expect a dataset that solely consists of
hand-written digits to share the same (ir-)relevant frequencies as one that
consists of real-world objects. Moreover, the dimension (image resolution) of
inputs for a given dataset matters, as a higher dimension potentially can
allow more irrelevant frequencies. Therefore, we emphasize that the goal of
our work is not to identify the exact (ir-)relevant frequencies among
datasets. Rather, the analysis is built on the presence of irrelevant
frequencies in the dataset, especially towards the higher end of the frequency
spectrum, and how models differ in their robustness when trained by different
algorithms. In the next section, we investigate the reason for such a
robustness difference by studying how the irrelevant frequencies affect the
learning dynamics of GD and signGD under a synthetic linear regression task.

##  4 Linear Regression Analysis with an Over-parameterized Model

In this section, we study the learning dynamics of GD and signGD on least
squares regression with linear models to understand why models trained using
the two algorithms have the same standard generalization performance but
exhibit different robustness against perturbations. On a synthetic dataset
that emulates the energy distribution of natural datasets in the frequency
domain, we design a learning task that has multiple optima for the standard
population risk, each with a different adversarial risk. We analyze the weight
adaptation under GD and signGD in both spatial and frequency domains and show
that training with signGD can result in larger weights associated with
irrelevant frequencies, resulting in models with a higher adversarial risk.
Our result verifies claim 3.1. We report the main results here and defer the
full derivations to Appendix E.

###  4.1 Problem Setup

Consider a linear model $f(x,w)=\left\langle\,w\,,\,x\,\right\rangle$ with
$x,w\in\mathbb{R}^{d}$, where $w$ and $x$ are the weight and the signal
represented in the spatial domain, respectively. Since the DCT transformation
matrix $C$ is an orthogonal matrix whose rows and columns are unit vectors, an
alternative way to represent this model is:

$f(x,w)=\left\langle\,w\,,\,x\,\right\rangle=w^{\top}x=w^{\top}C^{\top}Cx=\left\langle\,\tilde{w}\,,\,\tilde{x}\,\right\rangle=f(\tilde{x},\tilde{w}),$

where $\tilde{w}$ and $\tilde{x}$ are the exact same weight and signal but are
now represented in the frequency domain. This means that for linear models,
computing the output of the model can be carried out in either domain as long
as we use the matching representation of the signal and the weight. The goal
of the linear analysis is to study the learning dynamics of different
algorithms in a synthetic and controlled environment where one can clearly
define the frequency-domain signal-target (ir)relevance to help understand the
behavior of models in more complex settings. For this reason, let
$\tilde{w}^{*}$ denote the frequency-domain representation of the true model
that is used to interact with the input $\tilde{x}$ and generate the target:
$y=\tilde{x}^{\top}\tilde{w}^{*}$, where
$\tilde{w}^{*}=(\tilde{w}_{0}^{*},\tilde{w}_{2}^{*},\dotsc,\tilde{w}_{d-1}^{*})^{\top}$.
We consider the squared error pointwise loss, which can be equally formulated
in both domains:

$\begin{aligned} \ell(x,y;w)&=\frac{1}{2}\left|f(x,w)-y\right|^{2}\\\
&=\frac{1}{2}\left|\left\langle\,x\,,\,w\,\right\rangle-\left\langle\,x\,,\,w^{*}\,\right\rangle\right|^{2}\end{aligned}\qquad\qquad\text{and}\qquad\qquad\begin{aligned}
\ell(\tilde{x},y;\tilde{w})&=\frac{1}{2}\left|f(\tilde{x},\tilde{w})-y\right|^{2}\\\
&=\frac{1}{2}\left|\left\langle\,\tilde{x}\,,\,\tilde{w}\,\right\rangle-\left\langle\,\tilde{x}\,,\,\tilde{w}^{*}\,\right\rangle\right|^{2}.\end{aligned}$

Denote the error between the learned weight and the true weight at iteration
$t$ by $e(t)=w(t)-w^{*}$, and the standard risk by
$\mathcal{R}_{\text{s}}(w)={\mathbb{E}}\left[\ell(X,Y;w)\right]$. In a similar
way, those terms can be represented in the frequency domain as
$\tilde{e}(t)=\tilde{w}(t)-\tilde{w}^{*}$ and
$\mathcal{R}_{\text{s}}(\tilde{w})={\mathbb{E}}\left[\ell(\tilde{X},Y;\tilde{w})\right]$.
Now we are ready to explain the design philosophy behind the synthetic
dataset, the structure of the true model $\tilde{w}^{*}$, and particularly,
with regard to robustness, the ideal model that minimizes the effect of
perturbations.

Suppose that $\tilde{X}$ follows a Gaussian distribution
$\mathcal{N}(\tilde{\mu},\tilde{\Sigma})$. For analytical tractability, we
consider $\tilde{\mu}=0$ and a diagonal structure of $\tilde{\Sigma}$, i.e.,
$\tilde{\Sigma}=\mathop{\textrm{diag}}(\tilde{\sigma}^{2}_{0},...,\tilde{\sigma}^{2}_{d-1})$.
This implies that in the spatial domain, $X$ follows a Gaussian distribution
$\mathcal{N}(0,\Sigma)$ where $\Sigma=C^{\top}\tilde{\Sigma}C$. In Appendix
E.1, we provide examples of the spatial-domain structure of the data, when we
define the distribution directly in the frequency domain. In Sec. 3, we
demonstrate that natural datasets exhibit a particular energy profile where
signals contain irrelevant information represented by high-frequency and low-
amplitude waves. To emulate this setting with a synthetic dataset, we define
frequencies that are (ir)relevant in generating the target. Let
$\mathbb{I}_{\text{irrel}}\subseteq\\{1,2,...,d-1\\}$ and
$\mathbb{I}_{\text{rel}}=\\{0,1,2,...,d-1\\}-\mathbb{I}_{\text{irrel}}$ denote
the set of irrelevant and relevant frequencies, respectively. Recall that the
goal is to make high-frequency components of the dataset irrelevant, so we
exclude the DC term ($0\notin\mathbb{I}_{\text{irrel}}$) when considering
irrelevant frequencies, as it is the lowest frequency possible. Next, we
specify the energy distribution of the synthetic dataset. The expected energy
of a random signal following such a distribution is

${\mathbb{E}}\left[E(\tilde{X})\right]={\mathbb{E}}\left[\sum_{i=0}^{d-1}|\tilde{X}_{i}|^{2}\right]=\sum_{i=0}^{d-1}{\mathbb{E}}\left[\tilde{X}_{i}^{2}\right]=\sum_{i=0}^{d-1}\tilde{\sigma}_{i}^{2}.$
(7)

We assume that $\tilde{\sigma}^{2}_{i}=0$ if $i\in\mathbb{I}_{\text{irrel}}$,
meaning the irrelevant frequencies of the data from the synthetic dataset have
zero energy contributions. The purpose of this is to imitate the behavior of
real-world datasets, where the high-frequency components have a negligible
impact on the overall energy of the signal.

To see how having irrelevant frequencies affect the structure of the true
model, notice that the definition of the synthetic dataset implies
$\tilde{X}_{i}=0$ for all $i\in\mathbb{I}_{\text{irrel}}$. This means that the
true target value does not depend on those irrelevant frequencies. Clearly,
this linear model is over-paramaterized because one only needs to specify
$\tilde{w}^{*}_{i}$ for all $i\in\mathbb{I}_{\text{rel}}$ to establish the
signal-target relationship.

The objective of the standard risk with such a synthetic dataset is not
strictly convex, i.e., there are multiple minimizers with zero standard risk,
as the value of $\tilde{w}_{i}^{*}$ for all $i\in\mathbb{I}_{\text{irrel}}$
has no impact on the model output. For clarity, let us define
$\tilde{\mathcal{W}}^{*}=\left\\{\,\tilde{w}^{*}\,:\,\mathcal{R}_{s}(\tilde{w}^{*})=0\,\right\\}$
as the set that includes all standard risk minimizers. Having multiple
standard risk minimizers is the result of over-parametrization; however, there
is a unique solution that achieves zero standard risk and makes the model
immune to any perturbations parallel to the directions of the irrelevant
frequencies, and it corresponds to having zero weight at irrelevant
frequencies: $\tilde{w}_{i}^{*}=0$ for all $i\in\mathbb{I}_{\text{irrel}}$:
Define such a robust standard risk minimizer as
$\tilde{w}^{\text{R}}\in\tilde{\mathcal{W}}^{*}$, we have

$\tilde{w}_{i}^{\text{R}}\triangleq\left\\{\begin{matrix}[l]\tilde{w}_{i}^{*}&\text{for
all}\quad i\in\mathbb{I}_{\text{rel}}\\\
0&\text{otherwise}.\end{matrix}\right.$ (8)

Note that we use $\tilde{w}^{*}$ to denote any arbitrary standard minimizers
in $\tilde{\mathcal{W}}^{*}$. To see why $\tilde{w}^{\text{R}}$ is the most
robust standard minimizer, we introduce the adversarial risk to capture the
worst-case performance of the model under an $\ell_{2}$-constrained
perturbation. Similar to the squared error loss, the adversarial risk can also
be equally formulated in both domains:

$\begin{aligned}
\mathcal{R}_{\text{a}}(w)\triangleq\mathbb{E}_{(X,Y)}\biggl{[}\max_{||\Delta
x||_{2}\leq{\epsilon}}\ell(X+\Delta
x,Y;w)\biggr{]}\end{aligned}\qquad\text{and}\qquad\begin{aligned}
\mathcal{R}_{\text{a}}(\tilde{w})\triangleq\mathbb{E}_{(\tilde{X},Y)}\biggl{[}\max_{||\Delta\tilde{x}||_{2}\leq{\epsilon}}\ell(\tilde{X}+\Delta\tilde{x},Y;\tilde{w})\biggr{]},\end{aligned}$

where the $\ell_{2}$-constraint with a size of ${\epsilon}$ has an equivalent
effect in both domains. To understand the adversarial risk from a frequency-
domain perspective, let us focus on $\mathcal{R}_{\text{a}}(\tilde{w})$:

$\mathcal{R}_{\text{a}}(\tilde{w})=\mathbb{E}_{\tilde{X}}\biggl{[}\underset{||\Delta\tilde{x}||_{2}\leq{\epsilon}}{\max}\frac{1}{2}\left|\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle+\left\langle\,\Delta\tilde{x}\,,\,\tilde{w}\,\right\rangle\right|^{2}\biggr{]},$
(9)

where we focus on the expectation over $\tilde{X}$, as $Y$ is replaced with
$\left\langle\,\tilde{X}\,,\,\tilde{w}^{*}\,\right\rangle$. Notice that the
maximization is inside the expectation. This means that we are finding a
separate perturbation for each input. Therefore, the maximizer,
$\Delta\tilde{x}^{*}$, of a given $\tilde{X}$ within the expectation in (9) is

$\Delta\tilde{x}^{*}\triangleq\underset{||\Delta\tilde{x}||_{2}\leq{\epsilon}}{\operatorname*{arg\,max}}\frac{1}{2}\left|\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle+\left\langle\,\Delta\tilde{x}\,,\,\tilde{w}\,\right\rangle\right|^{2}={\epsilon}\operatorname{sign}[\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle]\frac{\tilde{w}}{||\tilde{w}||_{2}}.$
(10)

Now knowing the worst-case perturbation to any $\tilde{X}$, we can continue
the derivation in (9) with

$\displaystyle\mathcal{R}_{\text{a}}(\tilde{w})$
$\displaystyle=\frac{1}{2}\mathbb{E}_{\tilde{X}}\biggl{[}\left|\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle+{\epsilon}\operatorname{sign}[\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle]\left\|\tilde{w}\right\|_{2}\right|^{2}\biggr{]}$
$\displaystyle=\frac{1}{2}\sum_{i\in\mathbb{I}_{\text{rel}}}\tilde{\sigma}_{i}^{2}(\tilde{w}_{i}-\tilde{w}_{i}^{*})^{2}+{\epsilon}\sqrt{\frac{2}{\pi}\sum_{i\in\mathbb{I}_{\text{rel}}}\tilde{\sigma}_{i}^{2}(\tilde{w}_{i}-\tilde{w}_{i}^{*})^{2}}\left\|\tilde{w}\right\|_{2}+\frac{{\epsilon}^{2}}{2}\left\|\tilde{w}\right\|_{2}^{2}.$
(11)

Finding the exact minimizer to (4.1) is more involved. Without doing that
however, it is obvious that for an arbitrary standard risk minimizer
$\tilde{w}^{*}$ from $\tilde{\mathcal{W}}^{*}$, we can evaluate (4.1) at
$\tilde{w}^{*}$ and obtain its the adversarial risk as

$\mathcal{R}_{\text{a}}(\tilde{w}^{*})=\frac{{\epsilon}^{2}}{2}||\tilde{w}^{*}||_{2}^{2},$
(12)

where the first two terms in (4.1) become zero at any fixed standard risk
minimizer. This shows that the robustness of the standard risk minimizers
against $\ell_{2}$-bounded perturbations is inversely proportional to the norm
of the linear model. That is, a smaller norm implies better robustness. Recall
that when evaluating the standard risk of the model, the weights associated
with irrelevant frequencies do not matter, since they are never used in
computing the output of the model. On the contrary, the
$||\tilde{w}^{*}||_{2}^{2}$ term in (12) implies that those weights matter
when considering the robustness of the model under perturbations. It is not
difficult to see that the minimum adversarial risk can be achieved on a unique
standard risk minimizer $\tilde{w}^{\text{R}}$ (8).

Therefore, in the over-parameterized linear regression setting, a standard
risk minimizer with a minimum norm is preferred when considering the
robustness of the model, and a model with zero weight at irrelevant
frequencies is the most robust solution among the standard risk minimizers.
With this example, we verify Claim 3.1. While standard risk minimizers can
correctly use the relevant information of the data, their use of irrelevant
information is under-constrained. This can result in significant weight
assigned to irrelevant frequencies, making models more susceptible to
perturbations.

Next, we study the learning dynamics of GD and signGD and demonstrate that the
solutions found by GD and signGD differ in the weight of the irrelevant
frequencies. This causes the solutions found by the two algorithms to have a
similar standard population risk, but behave very differently under
perturbations.

###  4.2 Analysis on the Learning Dynamics of GD and signGD

We now analyze the weight adaptation of a linear model under GD and signGD,
and experimentally verify our results. Our analysis shows that for the over-
parameterized linear model, GD finds solutions with a standard risk of exactly
zero, and signGD finds solutions with a standard risk close to zero. However,
they have different robustness properties. In the presence of irrelevant
frequencies, GD is more likely to converge to a solution that is less
sensitive to perturbations along the direction of irrelevant frequencies,
whereas signGD is more likely to converge to solutions that are more prone to
such perturbations.

####  4.2.1 GD Dynamics

Let us start with GD in the spatial domain. Suppose that we initialize the
weights in the spatial domain as $w(0)=W\sim N(0,\Sigma_{W})$ where
$\Sigma_{W}\in\mathbb{R}^{d\times d}$. Similar to how both $\tilde{X}$ and $X$
follow a Gaussian distribution, the frequency representation of the
initialized weight also follows a Gaussian distribution:
$\tilde{w}(0)=\tilde{W}\sim\mathcal{N}(0,\tilde{\Sigma}_{W})$ where
$\tilde{\Sigma}_{W}=C\Sigma_{W}C^{\top}$. To train the model, we use GD on the
population risk:

$w(t+1)\leftarrow w(t)-\eta\nabla_{w}\mathcal{R}_{\text{s}}(w(t)).$ (13)

The gradient computed using the population risk is
$\nabla_{w}\mathcal{R}_{\text{s}}(w(t))={\mathbb{E}}\left[XX^{\top}\right]e(t)=\Sigma
e(t)$, and the learning dynamics of GD in the spatial domain can be captured
using:

$e(t+1)=w(t+1)-w^{*}=w(t)-w^{*}-\eta\Sigma e(t)=(I-\eta\Sigma)^{t+1}e(0).$
(14)

This shows that the learned weight converges to the optimal weight $w^{*}$ at
a rate depending on $\Sigma$. To see the GD dynamics in the frequency domain,
we can simply perform DCT on both sides of (14):

$\tilde{e}(t+1)=C(I-\eta\Sigma)^{t+1}e(0)=(I-\eta\tilde{\Sigma})^{t+1}\tilde{e}(0),$
(15)

where $\tilde{\Sigma}$ is the covariance of $\tilde{x}$. It is easy to see
that no weight adaptation happens for the irrelevant frequencies because
$\tilde{\sigma}_{i}^{2}=0$ for all $i\in\mathbb{I}_{\text{irrel}}$. As
$\tilde{\Sigma}$ is diagonal, choosing the learning rate $\eta$ such that
$\eta\max_{i\in\left\\{0,\dotsc,d-1\right\\}}\tilde{\Sigma}_{ii}<1$, we get
that the asymptotic solution is

$\bm{\tilde{w}}_{i}^{\text{GD}}\triangleq\lim_{t\rightarrow\infty}\tilde{w}_{i}(t)=\left\\{\begin{matrix}[l]\tilde{w}_{i}^{*}&\text{for
all}\quad i\in\mathbb{I}_{\text{rel}}\\\
\tilde{w}_{i}(0)&\text{otherwise}.\end{matrix}\right.$ (16)

That is, the initial random weights at the irrelevant frequencies do not
change. Using (12), we have

$\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{GD}})=\frac{{\epsilon}^{2}}{2}||\bm{\tilde{w}}^{\text{GD}}||_{2}^{2}=\frac{{\epsilon}^{2}}{2}\left\\{\sum_{i\in\mathbb{I}_{\text{rel}}}\tilde{w}^{*2}_{i}+\sum_{j\in\mathbb{I}_{\text{irrel}}}\tilde{w}_{j}(0)^{2}\right\\}.$
(17)

Comparing the standard risk minimizer found by GD with the robust standard
risk minimizer in (8), we notice that the GD solution is not the most robust
among all standard risk minimizers, as it is sensitive to perturbations along
irrelevant frequencies. Suppose that the initialized weight in the frequency
domain is randomly sampled from $\mathcal{N}(0,\sigma^{2}I_{d\times d})$, and
the signal-target relationship is determined by a handful of relevant
frequencies. Taking the expectation of (17) over the randomly initialized
weight, we have
$\mathbb{E}_{\tilde{w}(0)}\left[\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{GD}})\right]\approx
O({\epsilon}^{2}d\sigma^{2})$, so the adversarial risk can be quite
significant if there is a large number of irrelevant frequencies, i.e.,
$\left|\mathbb{I}_{\text{rel}}\right|\ll d$ and
$\left|\mathbb{I}_{\text{irrel}}\right|\approx d$.

This example shows that the GD solution is sensitive to initialization.
Because there is no mechanism in place to actively ensure that the weights
associated with these irrelevant frequencies become zero, GD is not forcing
the initial weights to go to zero at those frequencies. One solution is to
include the weight norm as a penalty term along with the original optimization
objective, but this can result in learning a biased solution. Another simple
fix is to initialize the weight at exactly 0. This robustifies the GD solution
by initializing those irrelevant weights at the most robust state.

####  4.2.2 SignGD Dynamics

Adaptive gradient algorithms like Adam and RMSProp utilize historical gradient
information as a momentum mechanism for updating model parameters, thereby
expediting the learning process. However, it is important to note that their
acceleration is not solely attributable to this feature, nor is their
adaptiveness limited to it. In (2.1), we have demonstrated how signGD, a
memory-free version of Adam and RMSProp, can adaptively adjust the update
using a coordinate-wise learning rate. Although signGD is not a suitable
choice for training deep neural networks (Riedmiller & Braun, 1993; Ma et al.,
2022b), examining its behavior can provide insights into the learning dynamics
of other adaptive gradient methods (Karimi et al., 2016; Balles & Hennig,
2018; Moulay et al., 2019). Additionally, in Sec. 4.2.3, we empirically
justify the use of signGD as a suitable alternative in understanding the
learning dynamics of Adam and RMSProp.

Again, let us start with signGD in the spatial domain. The update rule using
the population risk takes the sign of the gradient computed using the
population risk

$w(t+1)\leftarrow
w(t)-\eta\operatorname{sign}[\nabla_{w}\mathcal{R}_{\text{s}}(w)],$ (18)

and its learning dynamics in the spatial domain is

$e(t+1)=w(t+1)-w^{*}=e(t)-\eta\operatorname{sign}[\Sigma e(t)].$ (19)

Unlike the GD dynamics in (14), (19) shows that the behavior of signGD depends
on the sign of $\Sigma e(t)$, and this means that when $\left|[\Sigma
e(t)]_{i}\right|\ll 1$, training using signGD can accelerate the learning
along the $i$-th dimension. Although we can obtain $\Sigma$ from
$\Sigma=C^{\top}\tilde{\Sigma}C$, the structure of $\Sigma$ is subject to
variation based on $\tilde{\Sigma}$, so it is difficult to find an analytical
solution for the dynamics of the model trained under signGD, such as (14)
where we have a closed form for $e(t)$ as a function of $e(0)$ for models
trained under GD. This means that analyzing the signGD dynamics is limited to
studying its step-by-step update based on the sign of the entries in $\Sigma
e(t)$.

The signGD learning dynamics in the frequency domain can be obtained by taking
the DCT transformation on both sides of (19):

$\tilde{e}(t+1)=\tilde{e}(t)-\eta C\operatorname{sign}[\Sigma
e(t)]=\tilde{e}(t)-\eta
C\operatorname{sign}[C^{\top}\tilde{\Sigma}\tilde{e}(t)],$ (20)

where the error and the covariance terms inside of the sign are also
transformed into their frequency-domain representations. Equation 20 shows
that analyzing the behavior of signGD in the frequency domain requires knowing
the sign of the entries in $C^{\top}\tilde{\Sigma}\tilde{e}(t)$. This term can
be understood as an inverse DCT transformation of
$\tilde{\Sigma}\tilde{e}(t)$, and with a diagonal structure of
$\tilde{\Sigma}$, we know that
$\tilde{\Sigma}\tilde{e}(t)=\left[\tilde{\sigma}^{2}_{0},...,\tilde{\sigma}^{2}_{d-1}\right]^{\top}\odot\tilde{e}(t)$.
However, similar to the situation in (19), the sign of the entries in
$C^{\top}\tilde{\Sigma}\tilde{e}(t)$ is dependent on $\tilde{e}(t)$ at
different steps, so obtaining an analytical solution for the frequency-domain
dynamics is also challenging.

In both (19) and (20), we see that understanding the signGD dynamics for any
general $\tilde{\Sigma}$ can be complicated. Thus, we focus on a structure of
$\tilde{\Sigma}$ that simplifies the analysis but still allows us to
understand why training with signGD results in vulnerable models. In
particular, we consider a data distribution where
$\tilde{X}\sim\mathcal{N}(\tilde{\mu}=0,\tilde{\Sigma}=\mathop{\textrm{diag}}\left\\{\tilde{\sigma}_{0}^{2},\tilde{\sigma}_{1}^{2},0\right\\})$.
This definition implies that the data distribution contains irrelevant
information at the highest frequency basis and we have $\tilde{X}_{2}=0$ for
all datapoints.

Now, we continue with signGD learning dynamics in the frequency domain from
(20). Let us denote
$A(t)=\frac{\sqrt{3}}{3}\tilde{\sigma}_{0}^{2}\tilde{e}_{0}(t)$ and
$B(t)=\frac{\sqrt{2}}{2}\tilde{\sigma}_{1}^{2}\tilde{e}_{1}(t)$, and
$C=C^{(3)}$ follows the DCT transformation matrix defined in (4). With some
algebraic manipulation, we have

$\tilde{e}(t+1)=\tilde{e}(t)-\eta\begin{bmatrix}\frac{\sqrt{3}}{3}(\operatorname{sign}[A(t)+B(t)]+\operatorname{sign}[A(t)]+\operatorname{sign}[A(t)-B(t)])\\\
\frac{\sqrt{2}}{2}(\operatorname{sign}[A(t)+B(t)]-\operatorname{sign}[A(t)-B(t)])\\\
\frac{\sqrt{6}}{6}\operatorname{sign}[A(t)+B(t)]-\frac{\sqrt{6}}{3}\operatorname{sign}[A(t)]+\frac{\sqrt{6}}{6}\operatorname{sign}[A(t)-B(t)]\end{bmatrix},$
(21)

and we include its complete derivation in Appendix E.7. With this particular
choice of $\tilde{\Sigma}$, (21) shows that weight adaptation depends on the
sign of three terms: $A(t)$, $A(t)+B(t)$ and $A(t)-B(t)$. In Table 9 of
Appendix E.8, we study the learning dynamics of signGD by analyzing all 27
sign combinations and their corresponding updates. We report the main results
here and defer the detailed analysis to Appendix E.8.

With a constant learning rate of $\eta$, the asymptotic signGD solution
converges to an $O(\eta)$ neighborhood of the standard risk minimizer:

$\limsup_{t\rightarrow\infty}\left|\tilde{w}_{i}(t)-\tilde{w}_{i}^{*}\right|=O(\eta),$
(22)

where $i\in\left\\{0,1\right\\}$. In particular, we demonstrate that
$\tilde{w}_{0}$ oscillates in an $O(\eta)$ neighborhood of
$\tilde{w}_{0}^{*}$. Consider $T$ as the first iteration after which
$\tilde{w}_{0}$ starts oscillating, and define $\Delta\tilde{w}_{2}$ as the
sum of all the updates in $\tilde{w}_{2}$ up to the $T$-th iteration. The
limiting behavior of $\tilde{w}_{2}$ under signGD update is

$\limsup_{t\rightarrow\infty}\left|\tilde{w}_{2}(t)\right|=\left|\tilde{w}_{2}(T)+O(\eta)\right|=\left|\tilde{w}_{2}(0)+\Delta\tilde{w}_{2}+O(\eta)\right|,$
(23)

where $\tilde{w}_{2}(0)$ is the weight at initialization. This means that
after $T$ iterations, for all $t^{\prime}>T$, $\tilde{w}_{2}(t^{\prime})$
stays in an $O(\eta)$ neighborhood of $\tilde{w}_{2}(T)$. As such, we have the
asymptotic solution found by signGD:

$\bm{\tilde{w}}^{\text{signGD}}=[\tilde{w}_{0}^{*},\;\tilde{w}_{1}^{*},\;\tilde{w}_{2}(0)+\Delta\tilde{w}_{2}]^{\top}+O(\eta).$
(24)

From the perspective of training under the standard risk, the signGD solution
is close to the optimum. Specifically, its standard risk is

$\mathcal{R}_{\text{s}}(\bm{\tilde{w}}^{\text{signGD}})={\mathbb{E}}\left[\ell(\tilde{X},Y;\bm{\tilde{w}}^{\text{signGD}})\right]=\frac{1}{2}{\mathbb{E}}\left[\left\langle\,\tilde{X}\,,\,\bm{\tilde{w}}^{\text{signGD}}-\tilde{w}^{*}\,\right\rangle^{2}\right]=O((\tilde{\sigma}_{0}^{2}+\tilde{\sigma}_{1}^{2})\eta^{2}).$
(25)

Note that the standard risk of the GD solution is exactly zero; and by
choosing a sufficiently small learning rate $\eta$, the standard risk of the
signGD solution can also be close to zero as well. However, their adversarial
risks are very different. Specifically, the adversarial risk of the asymptotic
signGD solution is

$\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{signGD}})=\frac{{\epsilon}^{2}}{2}||\bm{\tilde{w}}^{\text{signGD}}||_{2}^{2}=\frac{{\epsilon}^{2}}{2}\left\\{\tilde{w}^{*2}_{0}+\tilde{w}^{*2}_{1}+\left(\tilde{w}_{2}(0)+\Delta\tilde{w}_{2}\right)^{2}\right\\}.$
(26)

We can compare it with the adversarial risk of the asymptotic solution found
by GD under the same setup:

$\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{GD}})=\frac{{\epsilon}^{2}}{2}\left\\{\tilde{w}^{*2}_{0}+\tilde{w}^{*2}_{1}+\tilde{w}_{2}(0)^{2}\right\\}.$
(27)

It can be observed that the main difference between the two adversarial risks
in (26) and (27) arises from the difference in weights learned at the
irrelevant frequency. Since their use of irrelevant frequency in the data is
under-constrained, neither algorithm can reduce $\tilde{w}_{2}$ to zero,
thereby neither solution is the most robust standard risk minimizer. As
discussed in Sec. 4.2.1, the GD solution is sensitive to weight
initialization. Before understanding the $\Delta\tilde{w}_{2}$ term in the
signGD solution, we first introduce two assumptions on the synthetic dataset
that serve to better emulate the distribution found in the natural dataset.
Consider a dataset with a strong task-relevant correlation between the
relevant frequency component of the data and the target, a realistic scenario
as we discussed in Sec. 3.2. In this case, $\left|\tilde{w}_{0}^{*}\right|$
and $\left|\tilde{w}_{1}^{*}\right|$ can be large. Additionally, with a weight
initialization around zero, such as in methods by He et al. (2015) and Glorot
& Bengio (2010), the initial error $\left|\tilde{e}_{0}(0)\right|$ and
$\left|\tilde{e}_{1}(0)\right|$ can be large and close to
$\left|\tilde{w}_{0}^{*}\right|$ and $\left|\tilde{w}_{1}^{*}\right|$ when
$\left|\tilde{w}_{0}^{*}\right|\gg\left|\tilde{w}_{0}(0)\right|$ and
$\left|\tilde{w}_{1}^{*}\right|\gg\left|\tilde{w}_{1}(0)\right|$. Moreover, it
is discussed in Sec. 3.1 and later supported empirically in Figure 8 of
Appendix G that the distribution of spectral energy heavily concentrates at
the low end of the frequency spectrum and decays quickly towards higher
frequencies. Since $\tilde{\sigma}^{2}_{i}$ is interpreted as the expected
energy of a random variable at the $i$-th frequency, it is reasonable to
expect that
$\frac{\tilde{\sigma}^{2}_{1}}{\tilde{\sigma}^{2}_{0}}<\frac{1}{3}$.

With the two assumptions, we demonstrate that $\Delta\tilde{w}_{2}$ is
proportional to $\left|\tilde{w}_{0}^{*}\right|$ or
$\left|\tilde{w}_{1}^{*}\right|$ depending on the initialization of
$\left|A(0)\right|$ and $\left|B(0)\right|$. In particular, we have

$\left|\Delta\tilde{w}_{2}\right|\approx\left\\{\begin{matrix}[l]\sqrt{3}C\left|\tilde{w}_{0}^{*}\right|&\text{if}\quad\left|A(0)\right|<\left|B(0)\right|\\\
\frac{3\sqrt{2}\tilde{\sigma}^{2}_{1}}{2\tilde{\sigma}^{2}_{0}}C\left|\tilde{w}_{1}^{*}\right|&\text{if}\quad\left|A(0)\right|>\left|B(0)\right|,\end{matrix}\right.$
(28)

where $C\in[\frac{\sqrt{6}}{6},\frac{\sqrt{6}}{3}]$. To quantitatively
understand the robustness difference between solutions found by the two
algorithms, we consider the ratio between the adversarial risk of the standard
risk minimizers found by GD (27) and signGD (26) with a three-dimensional
input space. We observe that the solution found by signGD is more sensitive to
perturbations compared to the GD solution:

$\displaystyle\frac{\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{signGD}})}{\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{GD}})}$
$\displaystyle\approx\left\\{\begin{matrix}[l]1+C_{3}\frac{\tilde{w}^{*2}_{0}}{\tilde{w}^{*2}_{0}+\tilde{w}^{*2}_{1}}&\text{if}\quad\left|A(0)\right|<\left|B(0)\right|\\\
1+C_{4}\frac{\tilde{w}^{*2}_{1}}{\tilde{w}^{*2}_{0}+\tilde{w}^{*2}_{1}}&\text{if}\quad\left|A(0)\right|>\left|B(0)\right|,\end{matrix}\right.$
(29)

where $\frac{1}{2}\leq C_{3}\leq 2$ and
$\frac{3}{4}\frac{\tilde{\sigma}^{4}_{1}}{\tilde{\sigma}^{4}_{0}}\leq
C_{4}\leq 3\frac{\tilde{\sigma}^{4}_{1}}{\tilde{\sigma}^{4}_{0}}$. Given that
this ratio is always greater than 1, the linear model obtained through GD is
always more robust against $\ell_{2}$-bounded perturbations in comparison to
the model obtained from signGD.

####  4.2.3 Empirical Validation

(a) Dynamics of the error term

(b) The standard population risk $\mathcal{R}_{s}$ and the adversarial
population risk $\mathcal{R}_{a}$

Figure 5: Comparing (a) the learning dynamics, (b) the standard and
adversarial population risk of linear models trained by GD, Adam, RMSProp, and
signGD. We create a three-dimensional dataset created using
$(\tilde{\sigma}_{0}^{2},\tilde{\sigma}_{1}^{2},\tilde{\sigma}_{2}^{2})=(0.01,0.0025,0)$,
and $(\tilde{w}_{0}^{*},\tilde{w}_{1}^{*},\tilde{w}_{2}^{*})=(5,10,0)$. All
models are initialized with the same weight
$(\tilde{w}_{0}(0),\tilde{w}_{1}(0),\tilde{w}_{2}(0))=(0.01,-0.01,0.02)$ and
trained using a fixed learning rate of $0.01$. (a) Dynamics of the error term.
During the signGD training process, the error along the irrelevant frequency
grows until $\tilde{e}_{0}$ starts to oscillate around 0. In our example, the
green highlighted areas in the figure correspond to the iterations before
$\tilde{e}_{0}$ starts to oscillate, and the red areas show that the error
along the irrelevant frequency cannot be corrected. (b) The standard
population risk and the adversarial population risk (${\epsilon}=\sqrt{2}$).
We notice that despite all models can reach zero standard population risk,
their adversarial population risks are different. The adversarial population
risk of models trained by adaptive gradient methods is higher than the one
from the model trained by GD, indicating lower robustness.

To validate our analysis, in Figure 5 we create a three-dimensional dataset
using
$(\tilde{\sigma}_{0}^{2},\tilde{\sigma}_{1}^{2},\tilde{\sigma}_{2}^{2})=(0.01,0.0025,0)$,
and $(\tilde{w}_{0}^{*},\tilde{w}_{1}^{*},\tilde{w}_{0}^{*})=(5,10,0)$, and
compare the dynamics of the frequency-domain weight error on models trained by
GD, Adam, RMSProp, and signGD. All models are initialized with the same weight
and are trained using a fixed learning rate of $0.01$. At each training
iteration, we sample 1000 data points and compute the gradient based on the
sampled data. We want to clarify that even though we analyze the weight update
dynamics in both frequency and spatial domains, the actual training still
takes place in the spatial domain.

In (15), we show that the GD solution $\bm{\tilde{w}}^{\text{GD}}_{i}(t)$
converges to $\tilde{w}_{i}^{*}$ with a rate of
$1-\eta\tilde{\sigma}_{i}^{2}$. Therefore, when $\tilde{\sigma}_{i}^{2}$ is
small, learning can be particularly slow for weights associated with the
$i$-th frequency, as shown in Figure 5a. On the other hand, notice in Table 9
that $\left|\tilde{e}_{0}\right|$ gets reduced by at least
$\frac{\sqrt{3}}{3}$ regardless of the magnitude of $\tilde{\sigma}_{0}^{2}$
for signGD. This means that the magnitude of $\tilde{\sigma}_{i}^{2}$ does not
directly affect the convergence speed. Instead, the relative magnitude between
$A(t)$ and $B(t)$ determines the frequency which receives priority during the
learning process. As a result, we observe an acceleration for models trained
by signGD.

Next, we observe that the error trajectory for the model trained by signGD
closely resembles the one from the model trained by Adam for $\tilde{e}_{0}$
and $\tilde{e}_{1}$. In the analysis of signGD, we show that
$\left|\tilde{e}_{2}\right|$ increases till $\left|\tilde{e}_{0}\right|$
starts oscillating in $O(\eta)$. Figure 5a shows that this pattern can be
observed in models trained by Adam as well. This shows that signGD is a
suitable alternative to understanding the learning dynamics of models under
the proposed linear regression task. For models trained by GD, since there is
no update on the weight associated with the irrelevant frequency,
$\tilde{e}_{2}$ remains at the initialized value throughout training. To
demonstrate the weight adaptation under signGD, we divide the training into
two phases, as highlighted by two background colors. The green area indicates
that $\left|\tilde{e}_{0}\right|$ decreases and $\left|\tilde{e}_{2}\right|$
increases in the meanwhile. Once oscillation begins for
$\left|\tilde{e}_{0}\right|$, $\left|\tilde{e}_{2}\right|$ can no longer be
corrected. This behavior corresponds to the purple area in Figure 5a.

In Figure 5b, we compare the standard population risk and the adversarial
population risk of different models. We notice that despite all models
reaching near zero standard population risk, their adversarial population risk
is different. In particular, the adversarial population risk of models trained
by adaptive gradient methods is higher than the one from the model trained by
GD, indicating lower robustness. Choosing ${\epsilon}=\sqrt{2}$ in (12), the
adversarial risk of those standard risk minimizers is exactly the squared
$\ell_{2}$ norm of the weight. With our choice of initialization, the
resulting $\left|A(0)\right|$ and $\left|B(0)\right|$ are $0.0289$ and
$0.0177$ respectively. This means that the ratio between the two adversarial
risks is
$\frac{\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{signGD}})}{\mathcal{R}_{\text{a}}(\bm{\tilde{w}}^{\text{GD}})}\in[1.04,1.15]$
according to (29), and this aligns with the ratio of $1.146$ obtained
empirically from the experiments.

This simple problem illustrates how the optimization algorithms and an over-
parameterized model might interact, and learning with signGD can lead to a
solution that is more prone to perturbations. In this section, we focus on
analyzing the robustness of the solution from a frequency domain perspective,
that is, the behavior of $\tilde{w}$ with an input perturbation of
$\Delta\tilde{x}$. In Appendix E.9, we present a spatial interpretation of the
result and demonstrate how signals with irrelevant frequencies contain
spatially redundant dimensions.

##  5 Connecting the Norm of Linear Models to the Lipschitzness of Neural
Networks

The takeaway from the over-parameterized linear regression analysis is that
among all standard risk minimizers, the minimum norm solution is the most
robust one. That is, a smaller weight norm implies better robustness. This
suggests a connection between the weight norm and model robustness.
Nonetheless, the major limitation of the analysis is that it is designed for a
linear model. In this section, we generalize such a connection to the deep
learning setting and verify it using the robustness of neural networks trained
by different algorithms.

One major obstacle is that the notion of weight norm as defined for linear
models is not generally applicable to neural networks. However, we can still
relate the weight of a network to its sensitivity with respect to changes in
the input space. Consider a single-layer ReLU-activated feedforward network
with $x\in\mathbb{R}^{d}$ and $W\in\mathbb{R}^{D\times d}$. With a
perturbation of $\Delta x\in\mathbb{R}^{d}$ constrained by the vector
$\ell_{p}$-norm, the maximum change in the model output as measured by the
same norm can be bounded using

$\left\|\operatorname{ReLU}\left(W(x+\Delta
x)\right)-\operatorname{ReLU}\left(Wx\right)\right\|_{p}\leq\left\|W\Delta
x\right\|_{p}\leq\|W\|_{p}\left\|\Delta x\right\|_{p},$ (30)

where $\|W\|_{p}$ denotes the vector $\ell_{p}$-norm induced matrix norm of
the weight $W$ and is referred to as the Lipschitz constant of this single-
layer model.

Table 1: Comparing the upper bound on the Lipschitz constant and the averaged robust accuracy of neural networks trained by SGD, Adam, and RMSProp. We follow (Gouk et al., 2021) to compute the Lipschitz constants of each layer in isolation and multiply them together to establish an upper bound on the constant of the entire network. Notice that across all selected datasets, models trained by SGD have a considerably smaller upper bound compared to models trained by Adam and RMSProp. In Figure 1, we demonstrate the robustness of the neural networks under Gaussian noise, $\ell_{2}$ and $\ell_{\infty}$ bounded adversarial perturbations (Croce & Hein, 2020). Here, we average the accuracy across the perturbations and get a single score quantifying the model’s robustness. All results are averaged over three independently initialized and trained models.  | Dataset | MNIST | Fashion | CIFAR10 | CIFAR100 | SVHN | Caltech101 | Imagenette
---|---|---|---|---|---|---|---|---
$\prod_{i=1}^{l}L(\phi_{i})$ | SGD | 3.80 | 3.83 | 26.81 | 40.41 | 22.65 | 18.53 | 23.99
Adam | 5.75 | 8.12 | 28.70 | 41.87 | 30.45 | 26.20 | 28.55
RMSProp | 6.21 | 5.11 | 37.75 | 41.71 | 28.31 | 45.84 | 27.11
Averaged Robust Acc. | SGD | 77.97% | 77.95% | 63.21% | 55.65% | 69.08% | 71.42% | 67.59%
Adam | 65.64% | 67.60% | 57.71% | 45.25% | 65.60% | 55.03% | 58.86%
RMSProp | 63.54% | 71.34% | 56.47% | 47.55% | 65.37% | 53.16% | 57.98%
|  |  |  |  |  |  |  |

Consider the $\ell_{p}$ vector norm, for all $x_{1},x_{2}\in\mathbb{R}$, a
function $f$ is said to be Lipschitz continuous if
$||f(x_{1})-f(x_{2})||_{p}\leq L||x_{1}-x_{2}||_{p}$, for some real-valued
Lipschitz constant $L\geq 0$.444Any value of $L$ satisfying the Lipschitz
condition is considered a valid Lipschitz constant. For the sake of clarity,
we will refer to the smallest (optimal) Lipschitz constant as $L$. Indeed, the
Lipschitz constant of a function with respect to inputs captures how sensitive
the model is in relation to changes in the input space.

In the single-layer model example, its Lipschitz constant is exactly the
matrix norm of the weight. More generally, consider the feed-forward neural
network as a series of function compositions:

$f(x)=(\phi_{l}\circ\phi_{l-1}\circ\ldots\circ\phi_{1})(x),$

where each $\phi_{i}$ is a linear operation, an activation function, or a
pooling operation. A particularly useful property of the Lipschitz function is
that the composition of Lipschitz functions with Lipschitz constant $L_{1}$,
$L_{2}$, $...$, $L_{N}$ w.r.t. the same norm is also Lipschitz with an upper-
bound on the Lipschitz constant $L\leq L_{1}L_{2}...L_{N}$. Denoting the
Lipschitz constant of function $f$ as $L(f)$, we can establish an upper bound
on the Lipschitz constant for the entire feed-forward neural network using

$L(f)\leq\prod_{i=1}^{l}L(\phi_{i}).$ (31)

As such, for a multi-layer neural network that comprises repeated layers of
linear operation followed by non-linear activation, we can upper bound the
change in model output with respect to the change in the input space by
multiplying the operator norms of the weights. It is important to realize that
(31) is not a tight upper bound, and in fact, computing the exact Lipschitz
constant of the neural network is NP-hard (Virmaux & Scaman, 2018).
Nonetheless, this approach allows us to draw connections between the weight
and the robustness of the model in the context of neural networks.

Results in Sec. 4 indicate that linear models trained by signGD have larger
weight norms, indicating less robustness. Therefore, we expect in the deep
learning setting that neural networks trained by SGD are more robust, as they
have a smaller Lipschitz upper bound, as shown in Figure 1. To verify this, we
follow the techniques in Gouk et al. (2021) and compute an upper bound on the
Lipschitz constant of the same neural networks trained by SGD, Adam, and
RMSProp in Figure 1. Results are shown in Table 1. The result shows that
across all datasets and architectures, models trained by SGD have a smaller
upper bound on the Lipschitz constant compared to models trained by the two
adaptive gradient methods. In Figure 1, we demonstrate the robustness of the
neural networks under Gaussian noise, $\ell_{2}$ and $\ell_{\infty}$ bounded
adversarial perturbations (Croce & Hein, 2020). In Table 1, we average the
accuracy across the perturbations and get a single score quantifying the
model’s robustness. We observe that a smaller upper bound on the Lipschitz
constant of a neural network implies better robustness against perturbations.

##  6 Conclusions

In this paper, we highlighted the robustness difference between models trained
by SGD and adaptive gradient methods, particularly Adam and RMSProp. To
understand this phenomenon, we leveraged a frequency-domain analysis, and
demonstrated that natural datasets contain frequencies that are irrelevant to
minimizing the standard training loss. Empirically, through a band-limited
perturbation analysis on neural networks trained on common vision datasets, we
showed that models trained by the adaptive gradient method utilize the
statistics in the irrelevant frequency, and thus they experience a huge drop
in performance when the same statistics become corrupted. Analytically, on a
synthetic linear regression task where the dataset was designed to contain
target-irrelevant frequencies, we showed that while both GD and signGD can
find the solution with standard risks close to zero, the adversarial risk of
the asymptotic solution found by signGD can be larger than that of GD. Such
results from the linear analysis explained the observation in Figure 1 and
suggested that a smaller model parameters’ weight norms may indicate a larger
model robustness. Finally, in the deep learning setting, we showed that models
trained by SGD have a noticeably smaller Lipschitz constant than those trained
by Adam and RMSProp.

Our work has some limitations. First, when conducting a theoretical analysis
of various optimizers, we opted for signGD as a simpler alternative to Adam
and RMSProp. Second, our focus was primarily on linear models. However, it is
crucial to acknowledge that deep neural networks inherently possess non-linear
characteristics, which limit the depth of insights derived from linear models.
Therefore, one promising future direction is to incorporate tools such as
neural tangent kernels (Jacot et al., 2018), which provide a deeper
understanding of network dynamics.  Third, our analysis focuses on
optimization algorithms along with the standard objective function. We can
also study the effect of optimizer with alternative objectives that are
designed to improve the robustness of the model (Simon-Gabriel et al., 2019;
Wen et al., 2020; Ma et al., 2020; Foret et al., 2021). For instance, the
effect of adversarial training using perturbations similar to the Fast
Gradient Sign Method (FGSM) under the linear regression setup has been studied
by Ma et al. (2020). In linear classification, Wei et al. (2023) showed that
minimizing the sharpness-aware loss (SAM) (Foret et al., 2021) can lead to
robust models. Further discussions on this study can be found in Appendix F.
Another promising direction for future research is to analyze model robustness
by coupling various optimization algorithms with different optimization
objectives.

#### Acknowledgments

Avery Ma acknowledges the funding from the Natural Sciences and Engineering
Research Council (NSERC) through the Canada Graduate Scholarships – Doctoral
(CGS D) program. Amir-massoud Farahmand acknowledges the funding from the
CIFAR AI Chairs program, as well as the support of the NSERC through the
Discovery Grant program (2021-03701). Yangchen Pan acknowledges the support
from the Turing AI World Leading Fellow. Resources used in preparing this
research were provided, in part, by the Province of Ontario, the Government of
Canada through CIFAR, and companies sponsoring the Vector Institute. We would
like to also thank the members of the Adaptive Agents Lab who provided
feedback on a draft of this paper.

## References

  * Agarwal et al. (2020) Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Koren, and Cyril Zhang.  Disentangling adaptive gradient methods from learning rates.  _arXiv preprint arXiv:2002.11803_ , 2020.
  * Ahmed et al. (1974) Nasir Ahmed, T Natarajan, and Kamisetty R Rao.  Discrete cosine transform.  In _IEEE transactions on Computers_ , 1974.
  * Amari et al. (2021) Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu.  When does preconditioning help or hurt generalization?  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Attias & Schreiner (1996) Hagai Attias and Christoph Schreiner.  Temporal low-order statistics of natural sounds.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 1996.
  * Balles & Hennig (2018) Lukas Balles and Philipp Hennig.  Dissecting Adam: The sign, magnitude and variance of stochastic gradients.  In _International Conference on Machine Learning (ICML)_ , 2018.
  * Benz et al. (2021a) Philipp Benz, Chaoning Zhang, Adil Karjauv, and In So Kweon.  Revisiting batch normalization for improving corruption robustness.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2021a.
  * Benz et al. (2021b) Philipp Benz, Chaoning Zhang, and In So Kweon.  Batch normalization increases adversarial vulnerability and decreases adversarial transferability: A non-robust feature perspective.  In _Proceedings of the International Conference on Computer Vision (ICCV)_ , 2021b.
  * Croce & Hein (2020) Francesco Croce and Matthias Hein.  Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * da Silva & Gazeau (2020) André Belotto da Silva and Maxime Gazeau.  A general system of differential equations to model first-order adaptive algorithms.  In _Journal of Machine Learning Research (JMLR)_ , 2020.
  * Dai et al. (2017) Wei Dai, Chia Dai, Shuhui Qu, Juncheng Li, and Samarjit Das.  Very deep convolutional neural networks for raw waveforms.  In _IEEE International cConference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2017.
  * Deng et al. (2020) Yao Deng, Xi Zheng, Tianyi Zhang, Chen Chen, Guannan Lou, and Miryung Kim.  An analysis of adversarial attacks and defenses on autonomous driving models.  In _IEEE International Conference on Pervasive Computing and Communications (PerCom)_ , 2020.
  * Diebold (1998) Francis X Diebold.  _Elements of forecasting_.  Thomson South-Western, 1998.
  * Ding et al. (2020) Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang.  MMA training: Direct input space margin maximization through adversarial training.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  In _Journal of Machine Learning Research (JMLR)_ , 2011.
  * Fei-Fei et al. (2004) Li Fei-Fei, Rob Fergus, and Pietro Perona.  Learning generative visual models from few training examples: An incremental Bayesian approach tested on 101 object categories.  _Computer Vision and Pattern Recognition Workshop_ , 2004.
  * Foret et al. (2021) Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur.  Sharpness-aware minimization for efficiently improving generalization.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Fourier (1822) Joseph Fourier.  _Théorie analytique de la chaleur (The Analytic Theory of Heat)_.  1822\.
  * Glorot & Bengio (2010) Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2010.
  * Goodfellow et al. (2015) Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In _International Conference on Learning Representations (ICLR)_ , 2015.
  * Gouk et al. (2021) Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree.  Regularisation of neural networks by enforcing Lipschitz continuity.  _Machine Learning_ , 2021.
  * Gowal et al. (2021) Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A Mann.  Improving robustness using generated data.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Gross (2005) Herbert Gross.  _Handbook of Optical Systems: Fundamentals of Technical Optics_.  2005\.
  * Gunasekar et al. (2017) Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro.  Implicit regularization in matrix factorization.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2017.
  * Guo et al. (2020) Chuan Guo, Jared S Frank, and Kilian Q Weinberger.  Low frequency adversarial perturbation.  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)_ , 2020.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification.  In _Proceedings of the International Conference on Computer Vision (ICCV)_ , 2015.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2016.
  * Hendrycks et al. (2020) Dan Hendrycks, Norman Mu, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan.  AugMix: A simple data processing method to improve robustness and uncertainty.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Hinton et al. (2012) Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky.  Neural networks for machine learning lecture 6a: overview of mini-batch gradient descent.  2012\.
  * (30) Jeremy Howard.  Imagenette.  URL https://github.com/fastai/imagenette/.
  * Huang et al. (2021) Hanxun Huang, Yisen Wang, Sarah Erfani, Quanquan Gu, James Bailey, and Xingjun Ma.  Exploring architectural ingredients of adversarially robust deep neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Huang & Mumford (1999) Jinggang Huang and David Mumford.  Statistics of natural images and models.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 1999.
  * 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 (NeurIPS)_ , 2019.
  * Ioffe & Szegedy (2015) Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _International Conference on Machine Learning (ICML)_ , 2015.
  * Jacot et al. (2018) Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  2018\.
  * Karimi et al. (2016) Hamed Karimi, Julie Nutini, and Mark Schmidt.  Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2016.
  * Kingma & Ba (2015) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_ , 2015.
  * Krizhevsky & Hinton (2009) Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  2009\.
  * Kuang et al. (2018) Kun Kuang, Peng Cui, Susan Athey, Ruoxuan Xiong, and Bo Li.  Stable prediction across unknown environments.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018.
  * Kumar et al. (2020) Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comissoneru, Matt Swann, and Sharon Xia.  Adversarial machine learning-industry perspectives.  In _IEEE Security and Privacy Workshops (SPW)_ , 2020.
  * LeCun (1998) Yann LeCun.  The MNIST database of handwritten digits.  _http://yann. lecun. com/exdb/mnist/_ , 1998.
  * Li et al. (2020) Zhuohang Li, Cong Shi, Yi Xie, Jian Liu, Bo Yuan, and Yingying Chen.  Practical adversarial attacks against speaker recognition systems.  In _Proceedings of the 21st International Workshop on Mobile Computing Systems and Applications_ , 2020.
  * Lyu & Li (2020) Kaifeng Lyu and Jian Li.  Gradient descent maximizes the margin of homogeneous neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Ma et al. (2020) Avery Ma, Fartash Faghri, Nicolas Papernot, and Amir-massoud Farahmand.  SOAR: Second-order adversarial regularization.  _arXiv preprint arXiv:2004.01832_ , 2020.
  * Ma et al. (2021) Avery Ma, Aladin Virmaux, Kevin Scaman, and Juwei Lu.  Improving hierarchical adversarial robustness of deep neural networks.  _arXiv preprint arXiv:2102.09012_ , 2021.
  * Ma et al. (2022a) Avery Ma, Nikita Dvornik, Ran Zhang, Leila Pishdad, Konstantinos G Derpanis, and Afsaneh Fazly.  SAGE: Saliency-guided mixup with optimal rearrangements.  In _British Machine Vision Conference (BMVC)_ , 2022a.
  * Ma et al. (2022b) Chao Ma, Lei Wu, and Weinan E.  A qualitative study of the dynamic behavior for adaptive gradient algorithms.  In _Mathematical and Scientific Machine Learning (MSML)_ , 2022b.
  * Madry et al. (2018) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Mallat (1999) Stéphane Mallat.  _A wavelet tour of signal processing_.  Elsevier, 1999.
  * McAulay & Quatieri (1986) Robert McAulay and Thomas Quatieri.  Speech analysis/synthesis based on a sinusoidal representation.  In _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , 1986.
  * Moulay et al. (2019) Emmanuel Moulay, Vincent Léchappé, and Franck Plestan.  Properties of the sign gradient descent algorithms.  _Information Sciences_ , 2019.
  * Netzer et al. (2011) Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  In _Neurips Workshop on Deep Learning and Unsupervised Feature Learning_ , 2011.
  * Oppenheim et al. (2001) Alan V Oppenheim, John R Buck, and Ronald W Schafer.  _Discrete-time signal processing_.  Pearson, 2001.
  * Pennebaker & Mitchell (1992) William B Pennebaker and Joan L Mitchell.  _JPEG: Still image data compression standard_.  Springer Science & Business Media, 1992.
  * Pezeshki et al. (2021) Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron C Courville, Doina Precup, and Guillaume Lajoie.  Gradient starvation: A learning proclivity in neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Qayyum et al. (2020) Adnan Qayyum, Junaid Qadir, Muhammad Bilal, and Ala Al-Fuqaha.  Secure and robust machine learning for healthcare: A survey.  In _IEEE Reviews in Biomedical Engineering_ , 2020.
  * Qian & Qian (2019) Qian Qian and Xiaoyuan Qian.  The implicit bias of adagrad on separable data.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Rebuffi et al. (2021) Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Timothy Mann.  Data augmentation can improve robustness.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Reddi et al. (2018) Sashank J Reddi, Satyen Kale, and Sanjiv Kumar.  On the convergence of adam and beyond.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Riedmiller & Braun (1993) Martin Riedmiller and Heinrich Braun.  A direct adaptive method for faster backpropagation learning: The RPROP algorithm.  In _IEEE international conference on neural networks_ , 1993.
  * Ruderman (1994) Daniel L Ruderman.  The statistics of natural images.  _Network: computation in neural systems_ , 1994.
  * Schaaf & Hateren (1996) A. van der Schaaf and J.H. van Hateren.  Modelling the power spectra of natural images: statistics and information.  _Vision research_ , 1996.
  * Schwartz & Simoncelli (2001) Odelia Schwartz and Eero P Simoncelli.  Natural signal statistics and sensory gain control.  _Nature neuroscience_ , 2001.
  * Schwartz (2004) Steven H Schwartz.  _Visual perception: A clinical orientation_.  McGraw-Hill Medical Pub. Division, 2004.
  * Sharma et al. (2019) Yash Sharma, Gavin Weiguang Ding, and Marcus Brubaker.  On the effectiveness of low frequency perturbations.  In _Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI)_ , 2019.
  * Shen et al. (2021) Zheyan Shen, Jiashuo Liu, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui.  Towards out-of-distribution generalization: A survey.  _arXiv preprint arXiv:2108.13624_ , 2021.
  * Silva & Najafirad (2020) Samuel Henrique Silva and Peyman Najafirad.  Opportunities and challenges in deep learning adversarial robustness: A survey.  _arXiv preprint arXiv:2007.00753_ , 2020.
  * Simon-Gabriel et al. (2019) Carl-Johann Simon-Gabriel, Yann Ollivier, Leon Bottou, Bernhard Schölkopf, and David Lopez-Paz.  First-order adversarial vulnerability of neural networks and input dimension.  In _International Conference on Machine Learning (ICML)_ , 2019.
  * Simoncelli (1997) Eero P Simoncelli.  Statistical models for images: Compression, restoration and synthesis.  In _Conference on Signals, Systems, and Computers_ , 1997.
  * Soudry et al. (2018) Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  In _Journal of Machine Learning Research (JMLR)_ , 2018.
  * Steiner et al. (2022) Andreas Peter Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lucas Beyer.  How to train your vit? data, augmentation, and regularization in vision transformers.  In _Transactions on Machine Learning Research (TMLR)_ , 2022.
  * Szegedy et al. (2014) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2014.
  * Tolhurst et al. (1992) David J Tolhurst, Yoav Tadmor, and Tang Chao.  Amplitude spectra of natural images.  _Ophthalmic and Physiological Optics_ , 1992.
  * Turner (2010) Richard E Turner.  _Statistical models for natural sounds_.  PhD thesis, UCL (University College London), 2010.
  * Verma et al. (2019) Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio.  Manifold Mixup: Better representations by interpolating hidden states.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Virmaux & Scaman (2018) Aladin Virmaux and Kevin Scaman.  Lipschitz regularity of deep neural networks: analysis and efficient estimation.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2018.
  * Wainwright & Simoncelli (1999) Martin J Wainwright and Eero Simoncelli.  Scale mixtures of gaussians and the statistics of natural images.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 1999.
  * Wallace (1991) Gregory K Wallace.  The JPEG still picture compression standard.  _Communications of the ACM_ , 1991.
  * Wang et al. (2021) Bohan Wang, Qi Meng, Wei Chen, and Tie-Yan Liu.  The implicit bias for adaptive optimization algorithms on homogeneous neural networks.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * 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 Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Wang et al. (2022) Haotao Wang, Aston Zhang, Shuai Zheng, Xingjian Shi, Mu Li, and Zhangyang Wang.  Removing batch normalization boosts adversarial training.  In _International Conference on Machine Learning (ICML)_ , 2022.
  * Warden (2018) Pete Warden.  Speech commands: A dataset for limited-vocabulary speech recognition.  _arXiv preprint arXiv:1804.03209_ , 2018.
  * Wei et al. (2023) Zeming Wei, Jingyu Zhu, and Yihao Zhang.  Sharpness-aware minimization alone can improve adversarial robustness.  In _ICML Workshop on New Frontiers in Adversarial Machine Learning_ , 2023.
  * Wen et al. (2020) Yuxin Wen, Shuai Li, and Kui Jia.  Towards understanding the regularization of adversarial robustness on neural networks.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Wilson et al. (2017) Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht.  The marginal value of adaptive gradient methods in machine learning.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2017.
  * Wu et al. (2021) Boxi Wu, Jinghui Chen, Deng Cai, Xiaofei He, and Quanquan Gu.  Do wider neural networks really help adversarial robustness?  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Xiao et al. (2017) Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ , 2017.
  * 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 (NeurIPS)_ , 2019.
  * Zhai et al. (2021) Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar.  DORO: Distributional and outlier robust optimization.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Zhang et al. (2019) Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.  Theoretically principled trade-off between robustness and accuracy.  In _International Conference on Machine Learning (ICML)_ , 2019.
  * Zhang et al. (2018) Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  Mixup: Beyond empirical risk minimization.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Zhu et al. (2023) Haoran Zhu, Boyuan Chen, and Carter Yang.  Understanding why vit trains badly on small datasets: An intuitive perspective.  _arXiv preprint arXiv:2302.03751_ , 2023.

##  Appendix A Summary of the Supplementary Material

The supplementary material is organized as follows. In Appendix B, we first
describe the data augmentation, the exact optimization schedule, and the model
architectures used to train the models. In Appendix C, we describe the
complete generalization and robustness results in Table 3 and how they are
used to generate Figure 1. In Appendix D, we discuss how the training inputs
are modified when making the observations in Sec. 3. In Appendix E, we provide
additional detail on the linear analysis in Sec. 4. In Appendix F, we discuss
how our analysis relates to the sharpness-aware minimization (SAM). Finally,
in Appendix G, we provide additional figures including visualization of the
perturbed images, the modified images used in Sec. 3.1, and the frequency
sensitivity comparison in Sec. 3.2.

##  Appendix B Training Details

Data augmentation: In our paper, we study how the presence of irrelevant
information in the dataset affects the robustness of the model when trained by
different algorithms. We approach this problem from a frequency-domain
perspective. Specifically, we leverage the structure and energy profile of the
dataset in the frequency domain. While data augmentation methods are widely
used in training machine learning models to improve generalization and reduce
overfitting, understanding how those methods affect the datasets in the
frequency domain requires additional analysis tailored for each augmentation
method. Therefore, on FashionMNIST, CIFAR10, CIFAR100, Caltech101, and
Imagenette, training inputs are augmented with random horizontal flipping, a
method that does not change the frequency profile of the image.

Optimization schedule: For all models, we use the following default PyTorch
(v1.12.1) optimization settings. For SGD, we disable all of the following
mechanism: dampening, weight decay, and Nesterov. For Adam, we use the default
values of $\beta_{1}=0.9$ $\beta_{2}=0.999$, ${\epsilon}=10^{-8}$ and disable
weight decay and disable AMSgrad (Reddi et al., 2018). For RMSProp, we use
default values of $\alpha=0.99$, ${\epsilon}=10^{-8}$, and disable momentum
and disable centered RMSProp which normalizes the gradient by an estimation of
its variance. All models are trained for 200 epochs. In Table 2, we list the
initial learning rate. The learning rate decreases by a factor of 0.1 at epoch
100 and 150.

Table 2: Experiment setup: the initial learning rate and the definition of
neural networks in this paper.

Dataset Optimization Initial Learning Rate MNIST SGD 0.1 Adam 0.0005 RMSProp
0.0005 FashionMNIST SGD 0.1 Adam 0.0005 RMSProp 0.0005 CIFAR10 SGD 0.2 Adam
0.0002 RMSProp 0.0005 CIFAR100 SGD 0.3 Adam 0.0005 RMSProp 0.0005 SVHN SGD 0.2
Adam 0.0002 RMSProp 0.0002 Caltech101 SGD 0.05 Adam 0.0002 RMSProp 0.001
Imagenette SGD 0.1 Adam 0.0002 RMSProp 0.0002 Speech Commmands SGD 0.1 Adam
0.1 RMSProp 0.1 Dataset Structure MNIST FashionMnist Conv(1, 16, 4) - ReLU -
Conv(16, 32, 4) - ReLU - FN(21632, 100) - FN(100, 10) - SM(10) CIFAR10
CIFAR100 SVHN Caltech101 Imagenette PreActResNet18 (He et al., 2016) ViT-B/16
(Dosovitskiy et al., 2021) Speech Commands M5 (Dai et al., 2017)

Model architecture: For MNIST and FashionMNIST, we use a ReLU-activated, two-
layer convolutional neural network ending with two fully-connected layers. For
CIFAR10, CIFAR100, SVHN, Caltech101, and Imagenette, we use PreActResNet18 (He
et al., 2016) and Vision Transformers (ViT-B/16) (Dosovitskiy et al., 2021).
For the Speech Commands dataset (Warden, 2018), we use the M5 network
architecture defined by Dai et al. (2017). See Table 2 for details of all
architectures used in this paper. We denote Conv(i, o, k) as a convolution
layer having i input channels, o output channels with k by k filters, FN(i, o)
as a fully-connect layer with i input channels and o output channels, and
SM(o) as the soft-max layer with o output. The stride for all convolution
layers is 1. The main experiments in our work are centered around models based
on convolutional neural networks, within the computer vision domain.
Additional results from using ViT-B/16 and on the Speech Commands dataset can
be found in Table 5 and Table 6, respectively.

Batch normalization: We concentrate on a particular aspect of the training
process: the selection of optimizers. Our aim is to shed light on how this
critical component influences the robustness of trained models. It has been
recently shown that the use of batch normalization (BN) can also affect the
robustness of the model (Benz et al., 2021b; a; Wang et al., 2022).
Consequently, to maintain focus on the impact of optimizers, we have omitted
BN in the training phase for the experiments leading to the results in Figure
1 and the analysis in Sec. 3. However, to show that our conclusions remain
valid for models with BN, we have included additional results that incorporate
BN in Table 4.

Table 3: Results on standard generalization and robustness of models trained by SGD, Adam, and RMSProp. We evaluate the model robustness on the testing data perturbed using Gaussian perturbations, $\ell_{2}$ and $\ell_{\infty}$-bounded perturbations (Croce & Hein, 2020). We include various severity of perturbations to better capture the model robustness. Models trained by SGD are the most robust against the three types of perturbations across all datasets. The highlighted results are used in Figure 1, as they are in relatively similar ranges. Results are averaged over three independently initialized and trained models.  Dataset | Optimization | Test | Gaussian perturbations | $\ell_{2}$-bounded attack | $\ell_{\infty}$-bounded attack
---|---|---|---|---|---
$\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=0.7$ | ${\epsilon}=1.0$ | ${\epsilon}=0.05$ | ${\epsilon}=0.07$ | ${\epsilon}=0.1$
MNIST | SGD | 98.72 | 98.59 | 97.94 | 95.64 | 93.00 | 87.33 | 66.33 | 87.53 | 71.93 | 31.50
Adam | 99.05 | 98.86 | 96.76 | 89.33 | 92.33 | 86.00 | 54.67 | 85.40 | 52.93 | 8.77
RMSProp | 98.90 | 98.70 | 97.02 | 90.63 | 91.67 | 83.00 | 50.00 | 82.73 | 50.00 | 7.33
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.005$ | $\sigma^{2}=0.01$ | ${\epsilon}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=0.7$ | ${\epsilon}=0.01$ | ${\epsilon}=0.03$ | ${\epsilon}=0.05$
FashionMNIST | SGD | 91.20 | 90.49 | 87.78 | 84.30 | 82.33 | 24.33 | 12.33 | 67.23 | 22.30 | 4.17
Adam | 90.98 | 89.91 | 85.03 | 78.91 | 70.33 | 6.00 | 0.33 | 53.57 | 5.33 | 0.00
RMSProp | 91.15 | 90.09 | 85.23 | 78.69 | 72.67 | 15.93 | 4.67 | 62.67 | 16.33 | 1.67
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.005$ | $\sigma^{2}=0.007$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
CIFAR10 | SGD | 90.16 | 87.35 | 74.13 | 68.66 | 67.40 | 37.57 | 16.30 | 53.93 | 21.27 | 0.93
Adam | 90.73 | 86.93 | 67.50 | 58.54 | 64.03 | 29.60 | 11.10 | 50.57 | 13.93 | 0.20
RMSProp | 90.46 | 86.25 | 70.03 | 61.52 | 60.10 | 25.47 | 8.87 | 47.87 | 14.03 | 0.33
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.005$ | $\sigma^{2}=0.007$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
CIFAR100(top1) | SGD | 59.76 | 56.88 | 46.26 | 41.28 | 28.47 | 12.93 | 5.90 | 18.80 | 5.57 | 1.17
Adam | 61.10 | 55.30 | 31.54 | 24.92 | 24.30 | 7.13 | 1.87 | 14.43 | 2.47 | 0.33
RMSProp | 60.36 | 56.46 | 36.42 | 29.50 | 28.90 | 10.47 | 2.83 | 17.90 | 3.47 | 0.20
CIFAR100(top5) | SGD | 84.67 | 81.77 | 72.84 | 67.53 | 80.30 | 70.20 | 59.90 | 75.30 | 61.70 | 39.53
Adam | 85.41 | 81.37 | 58.11 | 49.54 | 80.53 | 66.73 | 52.77 | 74.70 | 53.70 | 33.43
RMSProp | 85.18 | 81.66 | 62.71 | 54.44 | 80.93 | 68.57 | 54.10 | 74.60 | 59.10 | 34.10
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.003$ | $\sigma^{2}=0.005$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
SVHN | SGD | 96.11 | 95.68 | 94.47 | 93.81 | 85.53 | 63.60 | 39.63 | 80.67 | 49.83 | 17.03
Adam | 96.48 | 96.03 | 94.04 | 91.46 | 80.77 | 57.83 | 35.93 | 78.93 | 47.50 | 12.43
RMSProp | 96.42 | 95.91 | 94.07 | 91.87 | 81.13 | 57.90 | 34.10 | 76.93 | 46.33 | 11.30
|  |  | $\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=1.0$ | ${\epsilon}=1.5$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
Caltech101(top1) | SGD | 70.80 | 68.13 | 57.67 | 43.46 | 58.77 | 47.03 | 35.17 | 48.27 | 27.87 | 4.70
Adam | 72.32 | 58.34 | 19.88 | 8.55 | 57.70 | 44.47 | 29.60 | 45.47 | 22.03 | 2.63
RMSProp | 73.82 | 69.38 | 51.34 | 33.17 | 37.80 | 11.30 | 2.80 | 14.77 | 1.93 | 0.03
Caltech101(top5) | SGD | 85.96 | 84.84 | 77.57 | 67.16 | 85.30 | 84.43 | 79.00 | 83.97 | 75.47 | 52.27
Adam | 88.08 | 79.48 | 38.55 | 19.67 | 82.03 | 80.67 | 77.63 | 83.97 | 72.07 | 45.87
RMSProp | 88.37 | 85.90 | 72.19 | 52.74 | 80.20 | 63.40 | 45.93 | 63.97 | 41.33 | 23.90
|  |  | $\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=1.0$ | ${\epsilon}=1.5$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
Imagenette | SGD | 89.44 | 84.83 | 67.23 | 50.21 | 70.70 | 44.13 | 21.33 | 47.23 | 14.33 | 0.37
Adam | 89.75 | 71.84 | 29.05 | 17.72 | 65.30 | 31.53 | 11.83 | 39.43 | 6.23 | 0.07
RMSProp | 89.77 | 73.25 | 28.28 | 17.16 | 62.30 | 30.27 | 11.27 | 38.40 | 6.20 | 0.03
|  |  |  |  |  |  |  |  |  |  |

##  Appendix C Results on Standard Generalization and Model Robustness

Main results: Table 3 summarizes the result on the standard generalization
ability and robustness properties of the models trained by SGD, Adam, and
RMSProp on seven vision datasets. All results are averaged over three
independently initialized and trained models. To evaluate standard
generalization, we measure the classification accuracy of the models on the
testing data. To capture model robustness, we measure the classification
accuracy of the models on the testing data perturbed using Gaussian
perturbations, $\ell_{2}$ and $\ell_{\infty}$-bounded perturbations (Croce &
Hein, 2020). Perturbations with varying degrees of severity are included in
the evaluation to ensure the observation of the robustness difference is not
limited to perturbations with any particular parameters. The degree of
severity is determined by the variance of the Gaussian perturbation and an
$\ell_{2}$ and $\ell_{\infty}$ norm for the attacks. We select those
parameters so the range of the accuracy differences between models is similar
across different datasets. Particularly, the highlighted results in Table 3
are in a similar range, so we use them to plot Figure 1. We also ensure that
the original image semantics remains in the perturbed images, and we provide a
visualization of the perturbed images in Figure 17 to 19.

Finally, for CIFAR100 and Caltech101, because of the large number of classes
in the dataset, we use the top-5 classification accuracy to plot Figure 1 as
the results are within a range similar to other datasets with 10 classes. The
observation of the similar standard generalization and different robustness
holds on both top-1 and top-5 accuracy.

###  C.1 Results on Models with Batch Normalization Enabled

When BN layers are activated in PreActResNet18, we observe that the models
exhibit similar standard generalization performance, yet the robustness
difference between SGD and adaptive gradient methods remains evident. This
observation is in line with the results presented in Table 3, where BN layers
are disabled. Notably, the accuracy of models with BN enabled is significantly
lower compared to their BN-disabled counterparts under almost all types of
perturbations, particularly under stronger perturbations. This finding aligns
with the results from the previous work (Benz et al., 2021b; a; Wang et al.,
2022).

Table 4: Results on standard generalization and robustness of models trained with BN enabled.  We follow the exact optimization configuration as the ones used in generating Table 3. The only modification is that BN is enabled.  Dataset | Optimization | Test | Gaussian perturbations | $\ell_{2}$-bounded attack | $\ell_{\infty}$-bounded attack
---|---|---|---|---|---
$\sigma^{2}=0.001$ | $\sigma^{2}=0.005$ | $\sigma^{2}=0.007$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
CIFAR10 | SGD | 92.24 | 86.91 | 55.23 | 43.29 | 64.84 | 27.86 | 6.96 | 48.64 | 9.14 | 0.04
Adam | 93.38 | 85.67 | 50.41 | 39.11 | 56.5 | 15.96 | 2.63 | 37.7 | 3.8 | 0
RMSProp | 93.57 | 86.97 | 52.09 | 39.86 | 55.93 | 15.16 | 2.23 | 37.7 | 3.76 | 0
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.005$ | $\sigma^{2}=0.007$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
CIFAR100 | SGD | 72.24 | 57.99 | 26.08 | 19.23 | 34.36 | 10.2 | 3.63 | 21.3 | 4.8 | 0.2
Adam | 71.36 | 55.85 | 24.55 | 18.23 | 27.56 | 6.66 | 1.73 | 15.26 | 2.9 | 0.23
RMSProp | 70.99 | 56.13 | 24.56 | 18.03 | 23.8 | 5.1 | 1.1 | 13.7 | 2 | 0.1
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.003$ | $\sigma^{2}=0.005$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
SVHN | SGD | 94.16 | 95.81 | 94.96 | 92.90 | 81.73 | 60.56 | 41.96 | 76.13 | 49.26 | 15.3
Adam | 96.62 | 96.09 | 93.96 | 91.19 | 80.13 | 47.76 | 21.86 | 72.36 | 32.76 | 4.36
RMSProp | 96.44 | 94.86 | 93.75 | 91.02 | 79.86 | 48.43 | 22.16 | 72.36 | 33.7 | 3.96
|  |  | $\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=1.0$ | ${\epsilon}=1.5$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
Caltech101 | SGD | 78.61 | 72.69 | 45.38 | 25.87 | 61.23 | 44.03 | 23.03 | 46.80 | 13.13 | 0.83
Adam | 79.58 | 62.21 | 21.08 | 10.35 | 56.76 | 34.46 | 13.06 | 37.3 | 5.66 | 0.23
RMSProp | 75.56 | 69.89 | 45.38 | 23.13 | 58.6 | 44.6 | 20.5 | 42.6 | 11.3 | 0.6
|  |  | $\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=1.0$ | ${\epsilon}=1.5$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
Imagenette | SGD | 89.35 | 76.67 | 46.18 | 28.27 | 73.43 | 42.96 | 17.56 | 48.93 | 14.33 | 0.03
Adam | 91.88 | 67.29 | 24.30 | 14.92 | 67.66 | 24.06 | 3.06 | 31.4 | 6.23 | 0
RMSProp | 91.93 | 67.02 | 23.79 | 15.43 | 68.76 | 26.1 | 4.1 | 33.66 | 6.20 | 0
|  |  |  |  |  |  |  |  |  |  |

###  C.2 Results on Vision Transformers

In addition to the network designs considered in Table 2, we extend our work
to ViT in order to verify whether similar observations can be drawn on other
neural network architectures.

It is important to note that the dataset utilized in our paper is
significantly smaller in size compared to larger datasets such as Imagenet and
JFT-300M. Recent research, such as the work by Zhu et al. (2023), has shown
that ViT tends to generalize poorly on small datasets when trained from
scratch. In particular, Zhu et al. (2023) empirically demonstrated that ViT
and ResNet learn distinct representations on small datasets while converging
to similar representations on larger datasets.

Therefore, we perform fine-tuning on a pre-trained ViT-B/16. Among the
datasets we considered, Imagenette is a 10-class subset of the Imagenet-1k
dataset, making it especially suitable for the fine-tuning task, since the
publicly available ViT checkpoint was pre-trained on Imagenet-1k. Also, it is
important to note that the pretrained models were originally trained using
Adam. In our fine-tuning process, we treat ViT as a feature extractor (i.e.,
no weight update on the transformer encoder), with a focus on fine-tuning the
Multi-Layer Perceptrons (MLP) head. Our approach follows prior work (Steiner
et al., 2022) and incorporates the three different optimizers, each fine-tuned
for 10 epochs. We initiated the fine-tuning process with an initial learning
rate of 0.01, followed by a cosine decay learning rate schedule and a linear
warmup. Throughout this process, we maintained a fixed batch size of 512.

To evaluate the robustness of the fine-tuned models, we maintained the exact
same perturbation strengths, including the variance of Gaussian noise and
${\epsilon}$ for adversarial perturbations, as used in Table 3. The results
can be found in Table 5. We draw three observations.

First, all models fine-tuned with the three different optimizers achieve near
$100\%$ test accuracy, a substantial improvement from the $89\%$ accuracy when
training from scratch using PreActResNet18. This significant boost in standard
generalization highlights the effectiveness of fine-tuning with ViT. Second,
we observe that the fine-tuned models exhibit a notable increase in robustness
to Gaussian noise. However, they are highly vulnerable to adversarial
perturbations. This observation is consistent with the results from existing
literature (Zhang et al., 2019), where a trade-off is often present between
standard accuracy and adversarial robustness. Finally, we make a similar
observation on the robustness difference between models fine-tuned with the
three optimizers, where models fine-tuned with SGD exhibited greater
robustness to both Gaussian noise and adversarial perturbations when compared
to models fine-tuned using Adam and RMSProp.

Table 5: Results on standard generalization and robustness of ViT-B/16 fined-tuned on the Imagenette dataset. Model | Optimization | Test | Gaussian perturbations | $\ell_{2}$-bounded attack | $\ell_{\infty}$-bounded attack
---|---|---|---|---|---
$\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=1.0$ | ${\epsilon}=1.5$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
ViT-b/16 | SGD | 99.18 | 99.05 | 96.16 | 91.25 | 6.2 | 0 | 0 | 1.3 | 0 | 0
Adam | 99.93 | 99.51 | 94.43 | 88.59 | 5.1 | 0 | 0 | 0.7 | 0 | 0
RMSProp | 99.92 | 99.54 | 95.38 | 89.91 | 5 | 0 | 0 | 0.8 | 0 | 0
|  |  |  |  |  |  |  |  |  |  |
Table 6: Results on standard generalization and robustness of models on an audio classification task on the Speech Commands dataset. Dataset | Optimization | Test | Gaussian perturbations | $\ell_{2}$-bounded attack | $\ell_{\infty}$-bounded attack
---|---|---|---|---|---
$\sigma^{2}=0.001$ | $\sigma^{2}=0.003$ | $\sigma^{2}=0.005$ | ${\epsilon}=0.01$ | ${\epsilon}=0.05$ | ${\epsilon}=0.1$ | ${\epsilon}=0.0001$ | ${\epsilon}=0.0005$ | ${\epsilon}=0.001$
Speech Commands | SGD | 85.14 | 55.76 | 39.88 | 33.42 | 70.01 | 20.31 | 9.81 | 75.6 | 36.71 | 13.47
Adam | 85.47 | 54.73 | 38.87 | 31.95 | 60.74 | 17.87 | 8.49 | 71.97 | 29.2 | 10.15
RMSProp | 84.67 | 52.37 | 36.59 | 27.94 | 59.57 | 19.04 | 8.88 | 70.50 | 30.95 | 11.01
|  |  |  |  |  |  |  |  |  |  |
Table 7: Results on standard generalization and robustness of models trained by SGD without and with momentum (0.9). Dataset | Optimization | Test | Gaussian perturbations | $\ell_{2}$-bounded attack | $\ell_{\infty}$-bounded attack
---|---|---|---|---|---
$\sigma^{2}=0.001$ | $\sigma^{2}=0.005$ | $\sigma^{2}=0.007$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
CIFAR10 | SGD | 90.16 | 87.35 | 74.13 | 68.66 | 67.40 | 37.57 | 16.30 | 53.93 | 21.27 | 0.93
SGD-m | 89.79 | 87.28 | 73.207 | 66.783 | 67.1 | 38.067 | 15.9 | 55.667 | 20.233 | 0.6333
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.005$ | $\sigma^{2}=0.007$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
CIFAR100 | SGD | 59.76 | 56.88 | 46.26 | 41.28 | 28.47 | 12.93 | 5.90 | 18.80 | 5.57 | 1.17
SGD-m | 56.08 | 55.03 | 44.97 | 40.03 | 29.2 | 12.4 | 5.7 | 19.7 | 6.5 | 0.8
|  |  | $\sigma^{2}=0.001$ | $\sigma^{2}=0.003$ | $\sigma^{2}=0.005$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
SVHN | SGD | 96.11 | 95.68 | 94.47 | 93.81 | 85.53 | 63.60 | 39.63 | 80.67 | 49.83 | 17.03
SGD-m | 96.14 | 95.71 | 94.44 | 92.80 | 82.7 | 60.53 | 39.03 | 77.33 | 49.26 | 15.96
|  |  | $\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=1.0$ | ${\epsilon}=1.5$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
Caltech101 | SGD | 70.80 | 68.13 | 57.67 | 43.46 | 58.77 | 47.03 | 35.17 | 48.27 | 27.87 | 4.70
SGD-m | 69.89 | 67.77 | 55.77 | 41.34 | 54.86 | 43.36 | 31.06 | 44.16 | 23.9 | 3.133
|  |  | $\sigma^{2}=0.01$ | $\sigma^{2}=0.05$ | $\sigma^{2}=0.1$ | ${\epsilon}=0.5$ | ${\epsilon}=1.0$ | ${\epsilon}=1.5$ | ${\epsilon}=\frac{1}{255}$ | ${\epsilon}=\frac{2}{255}$ | ${\epsilon}=\frac{4}{255}$
Imagenette | SGD | 89.44 | 84.83 | 67.23 | 50.21 | 70.70 | 44.13 | 21.33 | 47.23 | 14.33 | 0.37
SGD-m | 88.69 | 85.05 | 68.58 | 51.15 | 75.53 | 49.2 | 24.53 | 56.43 | 17.76 | 0.2
|  |  |  |  |  |  |  |  |  |  |

###  C.3 Results with an Audio Dataset

Besides the vision domain, we extend our work to the audio domain since audio
signals offer a frequency-based interpretation as well. We include additional
results in Table 6, which compare the standard generalization and robustness
properties of an audio classifier trained on the Speech Commands dataset
(Warden, 2018). We focus on the PreActResNet18 architectures and all models
are trained for 200 epochs, with an initial learning rate of 0.1 and learning
rate decay by a factor of 0.1 at epoch 100 and 150. We consider the accuracy
of models under Gaussian- and adversarially-perturbed test sets. Manual
verification was conducted to ensure that the noisy audio phrase could still
be recognizable.

Results demonstrate that despite similar test accuracy, the models trained
using SGD exhibit greater robustness when compared to the other two
optimization methods. These insights provide valuable context to the
generalizability of our initial observations, offering a more comprehensive
understanding of how optimizers perform in the context of different data
modalities.

###  C.4 Results with Momentum-enabled SGD

Additional results with momentum-enabled SGD (SGD-m) are included in Table 7.
We maintain the exact same optimization configuration as that is used for
generating the SGD results presented in Table 3, and the only variation is an
additional momentum term with a coefficient of $\beta=0.9$. The result shows
that models optimized by both vanilla SGD and SGD-m exhibit similar trends in
terms of generalization and robustness.

##  Appendix D Modifying the Training Inputs in Sec.3.1

We demonstrate irrelevant frequencies in two settings: i) DCT basis vectors
with a low magnitude are irrelevant and ii) high-frequency DCT bases are
irrelevant. In Figure 9 to 15, we visualize the original images and the
modified images used in Sec. 3.1.

To understand how the modified training images are generated, we use
$\Phi_{\text{nrg}}(x,p)$ with $0<p<100$ to denote the operation that modifies
the input image $x$ by removing the DCT basis vectors whose magnitudes are in
the bottom $\frac{p}{100}$-th percentile. We use $M_{\text{nrg}}(x,p)$ to
denote the binary mask used in the process. Consider an image
$x\in\mathbb{R}^{d\times d}$, the entire process can be formulated as

$\Phi_{\text{nrg}}(x,p)=C(\tilde{x}\odot M_{\text{nrg}}(x,p))C^{\top},$

where $\odot$ is the element-wise product and $C$ is the DCT transformation
matrix. The binary mask $M_{\text{nrg}}\in\left\\{0,1\right\\}^{d\times d}$ is
defined as

$M_{\text{nrg}}(x,p)=\left\\{\begin{matrix}[l]1&\text{if}\quad\left|\tilde{x}_{i,j}\right|>\phi({\tilde{x}},p)\\\
0&\text{otherwise},\end{matrix}\right.$

where $\phi({\tilde{x}},p)\in\mathbb{R}$ computes the $\frac{p}{100}$-th
percentile in $\left|\tilde{x}\right|$. Therefore, DCT basis vectors with a
magnitude smaller than the threshold are first discarded in $\tilde{x}$, and
then this filtered $\tilde{x}$ is converted back to the spatial domain.

Similarly, we use $\Phi_{\text{freq}}(x,p)$ to denote the operation that
modifies the input image $x$ by removing the DCT basis vectors whose frequency
are in the highest $\frac{p}{100}$-th percentile. We use $M_{\text{freq}}(p)$
to denote the binary mask used in the process. This operation can be
formulated as

$\Phi_{\text{freq}}(x,p)=C(\tilde{x}\odot M_{\text{freq}}(p))C^{\top},$

where $M_{\text{freq}}\in\left\\{0,1\right\\}^{d\times d}$ is defined as:

$M_{\text{freq}}(p)=\left\\{\begin{matrix}[l]1&\text{if}\quad
i^{2}+j^{2}>\frac{p}{100}\sqrt{2}d\\\ 0&\text{otherwise},\end{matrix}\right.$

and $i,j$ are frequency bases. Notice that $M_{\text{freq}}$ only depends on
the size of the image, whereas $M_{\text{nrg}}$ depends on the input $x$ since
we identify the threshold value in $\left|\tilde{x}\right|$. Examples of the
modified images and the modification process are shown in Appendix G.

##  Appendix E Linear Regression Analysis

###  E.1 Understanding the Synthetic Dataset

The goal of the linear analysis is to study the learning dynamics of different
algorithms on a synthetic dataset where one can clearly define the frequency-
domain signal-target (ir)relevance. This motivates us to directly define the
distribution of the input signal in the frequency domain. In Sec. 4, we
consider $\tilde{X}$ follows a Gaussian distribution
$\mathcal{N}(\tilde{\mu},\tilde{\Sigma})$, and for analytical tractability, we
consider $\tilde{\mu}=0$ and a diagonal structure of $\tilde{\Sigma}$, i.e.,
$\tilde{\Sigma}=\mathop{\textrm{diag}}(\tilde{\sigma}_{0}^{2},...,\tilde{\sigma}_{d-1}^{2})$.
Admittedly, it is quite unconventional to define the data distribution
directly in the frequency domain, so we provide a few examples in Table 8 to
illustrate the structure of the input data in both representations.

Table 8: Examples of the synthetic data distribution in the frequency and the spatial domain. $\tilde{\Sigma}$ | Frequency-domain Representation | Spatial-domain Representation
---|---|---
$\mathop{\textrm{diag}}\left\\{\tilde{\sigma}_{0}^{2},0,0\right\\}$ | $(\tilde{X}_{0},0,0)$ | $(\sqrt{\frac{1}{3}}\tilde{X}_{0},\sqrt{\frac{1}{3}}\tilde{X}_{0},\sqrt{\frac{1}{3}}\tilde{X}_{0})$
$\mathop{\textrm{diag}}\left\\{0,\tilde{\sigma}_{1}^{2},0\right\\}$ | $(0,\tilde{X}_{1},0)$ | $(\sqrt{\frac{1}{2}}\tilde{X}_{1},0,-\sqrt{\frac{1}{2}}\tilde{X}_{1})$
$\mathop{\textrm{diag}}\left\\{0,0,\tilde{\sigma}_{2}^{2}\right\\}$ | $(0,0,\tilde{X}_{2})$ | $(\sqrt{\frac{1}{6}}\tilde{X}_{2},-\sqrt{\frac{2}{3}}\tilde{X}_{2},+\sqrt{\frac{1}{6}}\tilde{X}_{2})$
$\mathop{\textrm{diag}}\left\\{0,\tilde{\sigma}_{1}^{2},\tilde{\sigma}_{2}^{2}\right\\}$ | $(0,\tilde{X}_{1},\tilde{X}_{2})$ | $(\sqrt{\frac{1}{2}}\tilde{X}_{1}+\sqrt{\frac{1}{6}}\tilde{X}_{2},-\sqrt{\frac{2}{3}}\tilde{X}_{2},-\sqrt{\frac{1}{2}}\tilde{X}_{1}+\sqrt{\frac{1}{6}}\tilde{X}_{2})$
$\mathop{\textrm{diag}}\left\\{\tilde{\sigma}_{0}^{2},0,\tilde{\sigma}_{2}^{2}\right\\}$ | $(\tilde{X}_{0},0,\tilde{X}_{2})$ | $(\sqrt{\frac{1}{3}}\tilde{X}_{0}+\sqrt{\frac{1}{6}}\tilde{X}_{2},\sqrt{\frac{1}{3}}\tilde{X}_{0}-\sqrt{\frac{2}{3}}\tilde{X}_{2},\sqrt{\frac{1}{3}}\tilde{X}_{0}+\sqrt{\frac{1}{6}}\tilde{X}_{2})$
$\mathop{\textrm{diag}}\left\\{\tilde{\sigma}_{0}^{2},\tilde{\sigma}_{0}^{2},0\right\\}$ | $(\tilde{X}_{0},\tilde{X}_{1},0)$ | $(\sqrt{\frac{1}{3}}\tilde{X}_{0}+\sqrt{\frac{1}{2}}\tilde{X}_{1},\sqrt{\frac{1}{3}}\tilde{X}_{0},\sqrt{\frac{1}{3}}\tilde{X}_{0}-\sqrt{\frac{1}{2}}\tilde{X}_{1})$
$\mathop{\textrm{diag}}\left\\{\tilde{\sigma}_{0}^{2},\tilde{\sigma}_{1}^{2},\tilde{\sigma}_{2}^{2}\right\\}$ | $(\tilde{X}_{0},\tilde{X}_{1},\tilde{X}_{2})$ | $(\sqrt{\frac{1}{3}}\tilde{X}_{0}+\sqrt{\frac{1}{2}}\tilde{X}_{1}+\sqrt{\frac{1}{6}}\tilde{X}_{2},\sqrt{\frac{1}{3}}\tilde{X}_{0}-\sqrt{\frac{2}{3}}\tilde{X}_{2},\sqrt{\frac{1}{3}}\tilde{X}_{0}-\sqrt{\frac{1}{2}}\tilde{X}_{1}+\sqrt{\frac{1}{6}}\tilde{X}_{2})$
|  |

Similar to Sec. 4.2.2, we focus on a low dimensional setting with $d=3$. The
first six rows in Table 8 represent the scenario when there are zero variances
in $\tilde{\Sigma}$. Notice the notion of irrelevant information in the data
is different in the two representations. In the frequency domain, an
irrelevant frequency indicates that the data has a value of zero at the
particular frequency. In the spatial domain, having irrelevant frequency means
that there are redundant dimensions in the spatial representation of the data
because the value of data at some dimensions can be fully predictable by
knowing the values of data at some other dimensions.

###  E.2 Derivation of Equation 9

The adversarial risk under an $\ell_{2}$-norm bounded perturbation with a size
of ${\epsilon}$ is

$\displaystyle\mathcal{R}_{\text{a}}(\tilde{w})$
$\displaystyle\triangleq\mathbb{E}_{(\tilde{X},Y)}\biggl{[}\max_{||\Delta\tilde{x}||_{2}\leq{\epsilon}}\ell(\tilde{X}+\Delta\tilde{x},Y;\tilde{w})\biggr{]}$
$\displaystyle=\mathbb{E}_{(\tilde{X},Y)}\biggl{[}\underset{||\Delta\tilde{x}||_{2}\leq{\epsilon}}{\max}\frac{1}{2}\left|f(\tilde{X}+\Delta\tilde{x},\tilde{w})-Y\right|^{2}\biggr{]}$
$\displaystyle=\mathbb{E}_{\tilde{X}}\biggl{[}\underset{||\Delta\tilde{x}||_{2}\leq{\epsilon}}{\max}\frac{1}{2}\left|\left\langle\,\tilde{X}+\Delta\tilde{x}\,,\,\tilde{w}\,\right\rangle-\left\langle\,\tilde{X}\,,\,\tilde{w}^{*}\,\right\rangle\right|^{2}\biggr{]}$
$\displaystyle=\mathbb{E}_{\tilde{X}}\biggl{[}\underset{||\Delta\tilde{x}||_{2}\leq{\epsilon}}{\max}\frac{1}{2}\left|\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle+\left\langle\,\Delta\tilde{x}\,,\,\tilde{w}\,\right\rangle\right|^{2}\biggr{]},$

where we focus on the expectation over $\tilde{X}$, as $Y$ is replaced with
$\left\langle\,\tilde{X}\,,\,\tilde{w}^{*}\,\right\rangle$.

###  E.3 Derivation of Equation 10

Given a r.v. $\tilde{X}$, we define $\Delta\tilde{x}^{*}$ to be the maximizer
of the term inside the expectation of (9):

$\Delta\tilde{x}^{*}\triangleq\underset{||\Delta\tilde{x}||_{2}\leq{\epsilon}}{\operatorname*{arg\,max}}\frac{1}{2}\left|\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle+\left\langle\,\Delta\tilde{x}\,,\,\tilde{w}\,\right\rangle\right|^{2}.$

To maximize this term, we need the two inner product terms to have the same
sign. This means

$\Delta\tilde{x}^{*}=\operatorname{sign}[\left\langle\,\tilde{X}\,,\,\tilde{w}-\tilde{w}^{*}\,\right\rangle]\underset{||\Delta\tilde{x}||_{2}\leq{\epsilon}}{\operatorname*{arg\,max}}\left|\left\langle\,\Delta\tilde{x}\,,\,\tilde{w}\,\right\rangle\right|^{2}.$

For the remaining argmax term, we can first use the Cauchy-Schwarz inequality
to obtain

$\max_{||\Delta\tilde{x}||_{2}\leq{\epsilon}}\left|\left\langle\,\Delta\tilde{x}\,,\,\tilde{w}\,\right\rangle\right|^{2}\leq\max_{||\Delta\tilde{x}||_{2}\leq{\epsilon}}\left\|\Delta\tilde{x}\right\|_{2}^{2}\left\|\tilde{w}\right\|_{2}^{2}={\epsilon}^{2}\left\|\tilde{w}\right\|_{2}^{2},$

which leads to