Understanding the robustness difference between stochastic gradient descent and adaptive gradient methods
Authors: Avery Ma
Yangchen Pan
Amir-massoud Farahmand
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (11/2023)
Understanding the robustness difference between stochastic gradient descent and adaptive gradient methods
Avery Ma University of Toronto Vector Institute
ama@cs.torontor
Yangchen Pan University of Orford
Sangchen.panm@enggoorr
Amir-massoud Farahmand
forahmand@@cs.trrnntto edu
Universily of Toronto Vector Institute
Reviewed on OpenReview: https: // openreview. net/ forum?? id= a ed8SkMaYFT
Abstract
Stochastic gradient descent (SGD) and adaptive gradicnt methods, such as Adam and RMSProp, have been widely used in training deep neural nerksr.s. 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 un- der input perturbations.. Notably, our investigation demonstrates the presence of irrele- vant 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 synthetic dataset that mirrors natural signals. With three-dimensionall 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 fz-norm bounded changes is inversely pro- portional 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 input per- turbations than those trained with adaptive gradient methods. Our source code is available at https://// //tbthb....tttt///// com/ wtt.l//.///aaa//eeee aaaaaaaeeraaaa/ae////a optar/bst...oo.....omooo
1 Introduction
Adaptive gradient methods, such as Adam (Kingma Ba, 2015) and RMSProp (Hinton et al., 2012), are family of popular techniques optimize machine learning (ML) algorithms. They are an extension of the traditional gradient descent method, which uses the gradient of 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 bordinate--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 (Gunasckar al., 2017: Soudry al., 2018; Lyu Li, 2020) and adaptive gradient algorithms (Qian & Qian, 2019; Wang al., 2021).

---

Published in Transactions on Machine Learning Research (11/2023)
100.0
Standard test acc. (%%
97.5
SGD
MNIST
MNIST
MNIST
RMSProp
SVHN
95.0
SVHN
SVHN
Adam
92.5
CIFAR10
NashionMNIST
CIFARTO
PashIon
Fashion
CIFAR1O
90.0
Imagenette
Imagenatte
imagenette
87.5
Ca
Caltech101
Caltech101
85.0
82.5
CIFAR100
CIFAR100
CIFARI00
80.0
40
90 Acc. under Gaussian perturbations (%)
50
60
70
80
50
55
70 75
80 85
30
50 60
Acc. under by-ounded attacks (%)
Acc. under f.- f.-bounded attacks (%)
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 mcasured by the test data accuracy under Gaussian noise, lz and & bounded adversarial perturbations (Croce & Hein, 2020). Results are averaged over three independent model initializations and trainings.
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 large volume of literature on developing specialized methods to improve the robustness of neural networks (Silva & Najafira,, 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 MT-based systems with the improvement robustness 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 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.
1.1 The Robustness Difference between Models Trained by Different Algorithms
As first step, we compare how models, trained with SGD, Adam, and RMSProp, differ in their standard generalization and robustness 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, le and foo 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 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 datasct (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 impor- fant 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 al- gorithms. 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.
2

---

Published in Transactions on Machine Learning Research (11/2023)
1.2 Contributions
Previous optimization work often studies how the structure of the dataset affects the dynamics of learning. For example, some focus dataset with different feature strengths (Amari et al., 2021; Pezeshki et al., 2021), while others assume lincarly separable dataset (Wilson et al., 2017; Gunasckar et al., 2017; Soudry et al., 2018). In our work, we investigale how the frequency characteristies of the dalaset 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 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 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 lz- norm bounded changes 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 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 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 lask 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 different adversarial risk, and iii) theoretically analyze the learning dynamics of various algorithms.
2 Background
In this section, we brielly 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 = = EN E(Xn, Yas w). where w E Rd is a vector of weights of model, {(X,,, Y,)) the training dataset and f(x, y; we) is the point-wise loss quantifying the performance of the model on data point (x,z). A common approach in training machine learning models is to reduce the loss via SGD which iteratively updates the model based batch of data points drawn uniformly and independently from the training set:
g(w)= =
Σ nEB
e( Xn:w),
(1)
B
where B C {1...., N} denotes the minibatch and has a size of |B] < N. The update rule of SGD is (t + 1) = w(t) =((((((()((((())) where sy(t) E R+ denotes the learning rate."
From this point forward, subscripts denote vector taatorr/maan /atrrix coordinates, and numbers parentheses denote update iterations unless otherwise specified.
3

---

Published in Transactions on Machine Learning Research (11/2023)
A family of adaptive gradient methods has been used to accelerate training by updating the model parameters based on 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
+ + (1-111111)) m(t + 1) = (1 (1-))))(((
v(t 1) B2g(w(t))² + (1 - B2) m(l + 1)
w(t 1) :o(t) (t) V Vu( +
(2)
where g(w(t)) is the stochastic estimate of gradient used by SGD (1), and are the first and second- order memory terms with their strength specified by 31 and 82, and e is 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 31, B2 E (0, and RMSProp is recovered when 31 and B2 (0, 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) with 31 = 82 = 1 and e = O. It is easy to see that the update rule in (2) becomes sign gradient descent:
wit + 1) = w(() nn(() sign(g((((())
= w() - 7(t) o g(w())),
where @ denotes Hadamard product, 77()) Rdd is a coordinate-wise learning rate based the absolute value n(t)
of the weight, i.e., 7i() = Te(w(()]]] Therefore, 17(t) accounts for the magnitude of the weight and a larger learning rate is used for parameters with smaller gradients.
In general, gradient-sigu-bassd optimization methods are not successful 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) studics the behavior of adaptive gradient algorithms in the continuous-lime limit. They demonstrate that under fixed 31 and 82, the memory effect for both Adam and RMSprop diminishes and the contimuous-ting 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 bet models trained using SGD and adaptive gradient methods in simple setting.
2.2 Robustness of ML Models
An important asumption of most modern ML models is that samples from the training and testing dataset are independent and identically distributed f;: however, samples collected in the real world rarely come from an identical distribution as the traîning 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 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 asscssed 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
4

---

Published in Transactions on Machine Learning Research (11/2023)
(Goodfellow et al., 2015; Simon-Gabrie 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; Rebulfi 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 al., 2020). Since SGD, Adam, and RMSProp have been the go-lo optimizer and industrial settings, this motivates us 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.
both academic
2.3 Frequency Representation of Signals
Natural signals are highly structured (Schwartz & Simoncelli, 2001). They often consist of statistically signif- icant (or insignificant) patterns with a large amount of predictability (or redundancy). Such 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 under- stand the structure of signals and identify palterns 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 trigonometrie functions, a method now called the Fourier transformation. This new repre- sentation allows to precisely study the structure and the magnitude of any repeating patterns presented in the original waveform. For the understanding of digital signals, such process is called discrete-time signal processing (Oppenheim et al., 2001).
Many discrete harmonic transformations exist, such as the discrete Fourier transform, the discrete co- sine 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 simi- lar results. Concretely, consider d-dimensional signal E Rdd in the spatial domain. The same sig- nal can be alternatively represented d-1
discrete sum of amplitudes multiplied by its cosine harmonics: Ts Lj=0 I. cos [5 (j + 1)) k] for k- 0,..., 1, where the transformed signal T has a frequency-domain representation. Because DCT is linear, it can be carried out using matrix operation, ie., f Cx, where C is dx x DCT transformation matrix with values specified by
(d)
Ok cos -Vaa
d (
+ 1
j
where ag = 1 and = 2 for k > O. In particular, & can be written as a matrix-vector product between the transformation matrix C and the column vector x:
V m
1
ip
TD
i
V3 cos
+1()) 2d
cos
m
Vā cos
1)+1)(1)
Ij
2d
2d
(5)
8d-1
+1(--1 COS
+1 2d
[8-1
2d
cos
coS
2d
Notice that is a real orthogonal matrix whose rows consists of periodic cosine bases with increasing fre- quencies. Therefore, the absolute value of ă at particular dimension indicates the magnitudes of the corresponding basis function, and higher dimension in F 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 con- verted back to the ppatial-temport domain via the inverse DCT (iDCT): x = C- = C i. In the example above, we discussed que-dimensional DCT which is applied to vectors and is used in the linear analysis in Soc. 4. Transformations on images require two-dimensional DCT and can be done using = CrCT, where x, T E Rdaxd, and C' is defined in (4); and the inverse two-dinensional DCT is x = CT 5C. For more details on swo-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
Indices range from
frequenyyy commonly used refer to signal with constant everywhere.
5

---

Published in Transactions on Machine Learning Research (11/2023)
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) = Σiz |,,l1, and by Parsoval's theorem, is equivalent to the sum of squared amplitudes across all the bases, i.c., E(x) = E(²) = Ei=o | Natural images are primarily made of low-frequency signals.: a high concentration of energy in the low-frequency harmonics renders the amplitude of the higher- higher-frequency harmonics almost negligible (Tolhurst ct al., 1992; Schaaf & Hateren, 1996), as shown in Figure 8 in Appendix G. Morcover, 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 synthetic dataset that mimics the characteristics of natural signals, and it allows us to study the learning dynamics of various optimization algorithms in 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 ii.dd, 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 the standard generalization of the model. This leads to our claim:
Claim 3.1. To oplimize the slandard training objeclive, models only need to learn how to correctly use rele- vant information in the data. Their use of irrelevont information in the data, however, is under-construined and can lead to solutions sensitive to perturbations.
Because of this, by largeting the perturbations loward the subset of the signal that contains irrelevant information, we notice that models trained by different algorithms exhibit very different performance changes (Observation IT).
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 f 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), 80 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, imago-processine 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 datasct by removing subsets of the signal with low spectral energy (Figure 2a) or high frequencies (Figure 2b), there is negligible effect on models' classífication 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
We will always use the term "high" or "low" frequency on a relative scale.
6

---

Published in Transactions on Machine Learning Research (11/2023)
original test set (9%
original (%%
Accuracy on the
95
Accuracy on
90-
PAZNOMPRIST
90-
CIFARD
CIRAN1O0
85
SVINN
CaRtcch201
80
10
30
50
70
90
0
10
30
50
70
90
p: percentage DCT removed based magnitude
p: perceeettge DCT removed based frequency
a. Parts of the signal with low spectral energy irrelovant.
b. Parts of the signal with high-frequency basis 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 magnitude in the bottom - 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 discarded in the training data. We explain the formulation of the two scttings in Appendix D. Examples of the modified inputs are included in Appendix G.
neural network classifier, and such information is often featured with low spectrum energy or lives at the high end of the frequency spectrum.
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 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 non-robust model has certain non-zero weights which, when combined with the irrelevant information in the input, yield net-zero effect in the output. In this case, alt 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 should expect a similar accuracy drop between models when perturbations are along relevant frequencies, but 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 noisc, 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 model accuracy by perturbing only specific frequency ranges of the test inputs with band-limited Gaussian noise.
To construct the land-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 to ensure an identical & norm among all the perturbations. Denote the binary mask of the i-th band by using M E [0, 10 dxd its
7

---

Published in Transactions on Machine Learning Research (11/2023)
Dividing DCT spectrum into tan banis
Ax
Ax
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 Ax(1) where i E {0, 1...,.... 9}. 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 feeuufryeuency checkerboard patterns.
N1S5F: comiibutin
C-S contritation change
Imagenctic Pice carti bution change
prancs
00mu
Porturbed
Perurbed
Pettrbed frequency
Figure 4: The effect of band-limited Gaussian perturbations on the model. Perturbations from the lowest band, i.c., (r( have similar effect 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.
corresponding band-limited Gaussian noise is Az = CT CTMM O 08CC, where 6 ~ (O o² Laxa) 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 Ar(", with (z(") and (r!") representing the lowest and the highest band, respoctively. To investigate the effect of the perturbation (z on the models, we measure the change in classification accuracy when the test inputs are perturbed by Ar(");
N =Y NK
N K ΣΣ FF(( F Ax -Yn
Σ 1(F(x))= 2=1
(6)
1=
where F a neural network classifier, {(X,, Y,)) N represents the test dataset, cach test input is perturbed by i.i.d sampled Anl and the subscript & 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 Ar applied to the spatial signal X, although we are limiting the frequency band of the noise.
Figure 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 (z has similar impact on all the models regardless of the algorithm they are trained by. There is however 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 pert on the generalization performance quickly diminishes to zero, suggesting that models are not sensitive to changes along the dimensions of irrelevant froquencics. Contrarily on models trained by the two adaptive gradient methods, we observe difference in the way models respond to perturbations of higher frequency bands. On CIFAR100, for example, the two models highly vulnerable to Gaussian perturbations from bands 5 to
8

---

Published in Transactions on Machine Learning Research (11/2023)
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 freeuenyyy Gaussian perturbations varies among datasets. This can be attributed to the fact that (ir-)relevant frequencies are most likely going be a unique char- acteristic 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 dimen- sion (image resolution) of imputs for given dataset matters, 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 frequen- cies 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 robustness difference by studying how the irrelevant frequencies affect the learning dynamics of GD and signGD under synthetic linear regression task.
higher dimension potentially can allow
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 syuthetic dataset that emulates the energy distribution of natural datasots in the frequency domain, we design a learning task that has multiple optima for the standard population risk, each with 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) = (w, " x) with æ, w E Rd, 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, alternative way to represent this model is:
f(x, w) = (w, x) = --== C Cr (w, x) = f(ā, w)
where i and å 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 to study the learning dynamics of different algorithums in a synthetic and controlled environment where one can clearly define the frequency-domaie signal-target (er)relevance to help understand the behavior of models in more complex settings. For this reason, let ú" denote the frequency-domain representation of the true model that is used to interact with the input T and generate the target: ; wn, where w" = (wi ....... :.......;-)) " We consider the squared error pointwise loss, which can be equally formulated in both domains:
((1, y: w) =
2 (f w) - 2
( y: () = 2 lf w) yy?
and
2 (2x, w) - (xx, )²
(5,, w) - -ā, w0 \²2
Denole the error between the learned weight and the true weight at ileration by e(l) = (() - w", and the standard risk by R.(w) = E [[(X, Y: w)]. In a similar way, those terms can be represented in the frequency domain as a(t) = (t) " and R, (w) = E [((X, Y; w)). Now we are ready to explain the design philosophy behind the synthetic dataset, the structure of the true model w", and particularly, with regard to robustness, the ideal model that mininizes the effect of perturbations.
9

---

Published in Transactions on Machine Learning Research (11/2023)
Suppose that X follows Gaussian distribution (p, Σ). For analytical tractability, consider jı = 0 and diagonal structure of Σ, i.e,, E- = diag(o) ..., ...,0.. 02-1)- This implies that in the spatial domain, X follows Gaussian distribution [O, where = CTC. 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 particular energy profile where signals contain irrelevant information represented by high-frequu fighffrey and low-amplitude waves. To emulate this sctting with synthetic dataset, we define frequencies that are (irrvelevant in generating the target. Let Tirrel S (1, d d- }} and Irel = 1,,,,,.... d - 1} - lirell 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 & Irrll) when considering irrelevant frequencies, as it the lowest frequency possible. Next, we specity the energy distribution of the synthetic dataset. The expected energy of a random signal following such distribution is
E
E
-E
Σ of. 8=0
We assume that o3 if E Tirrel, mcaning the irrelevant frequencies of the data from the synthetic dataset have zero energy contributions. The purpose of this is to imitale 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 frequencics affect the structure of the true model, notice that the definition of the synthetic datasel implies X; = 0 for all E Thre This means that the true larget value does not depend those irrelevant frequencies. Clearly, this linear model is pverpaaraatterieed because one only needs to specify रे for all i E Leel to establish the signal-targe 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 ūā for all i E Tireel has no impact on the model output. For clarity, let us define V = " (w²) = }} as the set that includes all standard risk minimizers. Having multiple standard risk minimizers is the result of prreeertettriitinn: however, there a unique solution that achieves zero standard risk and makes the model immune any perturbations parallel to the directions of the irrelevant frequencies, and it corresponds to having zero weight at irrelevant frequencies: wi-- = 0 for all i E Timel: Define such robust slandard risk minimizer w E W", we have
i 0
for all E Hel otherwise.
Note that we use x² to denote any arbitrary standard minimizers in W To see why wt is the most robust standard minimizer, we introduce the adversarial risk to capture the worst-case performance of the model under an fzcoonstrained perturbation. Similar to the squared error loss, the adversarial risk can also be equally formulated in both domains:
Rw) A E(XY))
max f(X + Ar, Y:w) and Ra( 2 (8,)) |
max l(X Az, V: ||al|las
where the fg-oonstraint with a size of e has an equivalent effect in both domains. To understand the adversarial risk from a frequency-domat perspective, let us focus on R. (w)):
1 18, 50) + (At, { 2
(1) Ex
max |AAlllaSe
(9)
where we focus on the expectation over X, as Y is replaced with (8, - Notice that the maximization is inside the expectation. This means that we are finding separate perturbation for each input. Therefore, the maximizer, Att, of given X within the expectation in (9) is
1 X vh w0) + +(A w c sigul X v - w0 >1 i
A e arg max |Alll
|| 1
(10)
10

---

Published in Transactions on Machine Learning Research (11/2023)
Now knowing the worst-case perturbation to any X, can continue the derivation in (9) with
1
Ra (w) 2 Bx
(xx, v - =1") + esggu( X, v = -1=0011 111001121
2 Σ - | + 2
2² |100
Σ (ū - w;)² +
(11)
2
iehel
ichel
Finding the exact minimizer to (11) is more involved. Without doing that however, it is obvious that for an arbitrary standard risk minimizer x* from W", we can evaluate (11) at w" and obtain its the adversarial risk as
Ra (wwww)
2 1
(12)
where the first two terms in (11) become zero at any fixed standard risk minimizer. This shows that the robustness of the standard risk minimizers against Ey-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 || term in (12) implics 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 R (8).
Therefore, in the over-parameterized linear regression setting, a standard risk minimizer with minimum norm is preferred when considering the robustness of the model, and 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 the Learning Dynamics of GD and signGD
We now analyze the weight adaptation of linear model under GD and signGD, and experimentally verify our results. Our analysis shows that for the per-parameterized lincar 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 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 (0) = W (O, Ew) where Ew E Rdxd, Similar to how both X and X follow a Gaussian distribution, the frequency representation of the initialized weight also follows Gaussian distributiinn w() W NN Ew) where Ew CT To train the model, we use GD on the population risk:
w((l + 1) wi()= 1/V
t (x)(()).
(13)
The gradient computed using the population risk is V., Rs (w(()) = E [XX]] e(t) Ee(t), and the learning dynamics of GD in the spatial domain can be captured using:
e(t 1) w(t + "- w(t) -- m)(ett = (I (
(14)
This shows that the learned weight converges to the optimal weight w" at a rate depending on Σ. To see the GD dynamics in the frequency domain, we can simply perform DCT on both sides of (14):
E(L+1) + 1) - - +5))+12(0))
(15)
11

---

Published in Transactions on Machine Learning Research (11/2023)
where Σ is the covariance of ø. It is easy to see that no weight adaptation happens for the irrelevant frequencies because of 0 for all i E Tiree- As E is diagonal, choosing the learning rate v such that (o... 1-1 Ey < 1, we get that the asymptotic solution is
for all i 4el
lim (t = DD
(16)
(0)
otherwisc.
That is, the initial random weights at the irrelevant frequencies do not change. Using (12), we have
e² 18 GD
e²
R₂ R2
Σ jelinned
(0)
(17)
2
iEhco
Comparing the standard risk minimizer found by GD with the robust standard risk minimizer in (8), we notice that the GD solution not the most robust among all standard risk minimizers, as it is sensi- live to perturbations along irrelevant frequencies. Suppose that the initialized weight. in the frequency domain is randomly sampled from (1 Laxa), and the signal-targer relationship is determined by a hand- ful of relevant frequencies. Taking the expectation of (17) over the randomly initialized weight, we have Ex(o) [Ra (1) = O(e2do?), so the adversarial risk can be quite significant if there is large mumber of irrelevant frequencies, Le., [aal < and [Trrell] x d.
This example shows that the GD solution is sensitive to initialization. Because there 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 penalty term along with the original optimization objective, but this can result in learning biased solution. Another simple fix is to initialize the weight at exactly O. 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 not solely attributable to this feature, nor their adaptiveness limited to it. In (3), we have demonstrated how signGD, a memory-free version of Adam and RMSProp, can adaptively adjust the update using coordinate- learning rate. Although signGD is not 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 lcarning 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(1+ + 1) + w(l) - signn V Re (w)),
(18)
and its learning dynamics in the spatial domain is
e(t + 1) = w(t + 1) - w² = = miinn [Ee()].
(19)
Unlike the GD dynamics in (14), (19) shows that the behavior of signGD depends the sign of Ee(t), and this mcans that when [[Ee(t]] < 1, training using signGD can accelerate the lcarning along the i-th dimension. Although we can obtain Σ from Σ = CTEC, the structure of Σ is subject lo variation based on Σ, 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 byep-by-stop update based on the sign of the entries in Ee(t).
12

---

Published in Transactions on Machine Learning Research (11/2023)
The signGD learning dynamics in the frequency domain can be obtained by taking the DCT transformation on both sides of (19):
E(l + 1) =(1) ,/C sign[Se = E(l) - syC (igg((CTE((())
(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* Eε(t). This term can be understood as an inverse DCT transformation
of Eā(t), and with a diagonal structure of Σ, we know that εε(t)= = [ ..., [ + ē(t). However, similar to the situation in (19), the sign of the entries in C EE(() is dependent on ε(1) at different steps, so oblaining an analytical solution for the rreuencyydooaad dynamics is also challenging.
In both (19) and (20), we see that understanding the signGD dynamics for any general E can be complicatod. Thus, we focus on a structure of E that simplifies the analysis but still allows us to understand why training with signGD results in vulnerable models. In particular, we consider data distribution where X ~Nū 0,E = diag { of, 0}). This definition implies that the data distribution contains irrelevant information at the highest frequency basis and we have X₂ 0 for all datapoints.
Now, we continue with signGD learning dynamics in the frequency domain from (20). Let us denote A(t) = 23 G (t) and B(t) = x (fē2 and C = (33) follows the DCT transformation matrix defined in (4). With
3
some algebraic manipulation, we have
sign A(t) + B(t) + sign[A(t)] + sign(A(t)) B(t)))
3
a(t + 1) - "
L Asign[A(t) + - sign ((t)))
(21)
T
sign ((t) + B()) - v6 sign [A()) + /6 sign(A(t) - B(t)]
3
6
and we include its complete derivation in Appendix E.7. With this particular choice of Σ, (21) shows that weight adaptation depends on the sign of three terms: A(t), A(t) + Bt) and
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.S.
With a constant learning rate of n, the asymptotic signGD solution converges to an O(1) neighborhood of the standard risk minimizer:
lim sup (t)(t) - क, = O(n),
(22)
t-000
where i E 13. In particular, we demonstrate that wo oscillates in an O()) neighborhood of wう. Consider T as the first iteration after which wh starts oscillating, and define Ado as the sum of all the updates in W2 up to the T-th iteration. The limiting behavior of úh under signGD update is
sup [t)( (T) + O(r) = [ (0) + Adg + +(m)) t+000
(23)
where (0) is the weight at initialization. This means that after iterations, for all t' > T, m>2(t') stays an O()) neighborhood of (T)) As such, we have the asymptotic solution found by signGD:
v signCD = [ Wi, (0) + A + +01).
(24)
From the perspective of training under the standard risk, the signGD solution is close to the optimum. Specifically, its standard risk is
R siggGD E [((X, Y; t )
[x, - 2 E -
t signGD -w²) =0 + +
(25)
Note that the standard risk of the GD solution is exactly zero; and by choosing a sufficiently small learning rate y,, the standard risk of the signGD solution can also be close zero as well. However, their adversarial risks are very different. Specifically, the adversarial risk of the asymptotic signGD solution is
c²
2
Ra i (isnGDD
|| [ signGDD ?
+ 11 + (0)(() + Aw }
(26)
=
2
2
13

---

Published in Transactions on Machine Learning Research (11/2023)
We can compare it with the adversarial risk of the asymptotic solution found by GD under the same setup:
2² { u00 + wi + و (0))).
RS ( GD)
i
(27)
2
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 tyg 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 Awg term in the signGD solution, we first introduce two assumptions on the syuthetic datasct that serve to better emulate the distribution found in the natural datasct. Consider a dataset with a strong Lask-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, |á and [ can be large. Additionally, with weight initialization around zero, such as in methods by He et al. (2015) and Glorot & Bengio (2010), the initial error [0)) and [ē](0) can be large and close to [2bg] and |,āf| when [ >> [(v(0)) and |لp|| >> Wi (0)). 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 o² is interpreted as the expected energy of a random variable at the i-th frequency, is reasonable to expect that 3
With the two assumptions, we demonstrate that Aw2 is proportional to | or |ofl depending on the initialization of |A()] and [B(0)). In particular, we have
V3C [
|A())] < BB()] if [A(O)) > [BO)
if
Aw2 ~
3//22 250
Cluil
(28)
( where C l J. 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-dimennsonal input space. We observe that the solution found by GignGD is more sensitive to perturbations compared to the GD solution:
R₂ Ra(w (1g
1 C3
if |A(0)] < [B(O)
(29)
Ra
1 Ca on +
if |A(O)) > [B(O),
where 2 S C3 2 2 and 3 obtained through GD is always more robust against bo-bounded perturbations in comparison to the model obtained from SignGD,,
488 I C4 $ 30 Given that this ratio is always greater than 1, the linear model
4.2.3 Empirical Validation
To validate our analysis, in Figure we create a three-dimensional dalaset using (o) 03) (0.01, 0.0025, 0), and (wig, wf, wg)) (5, 10, 0), and compare the dynamics of the frequency-domain weight error models trained by GD, Adam, RMSProp, and signGD. All models are initialized with the same weight and are trained using fixed learning rate of 0.01. At each training iteration, 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.
sample 1000 data
In (15), we show that the GD solution (t)((t converges to ot with rate of 1 1- n Therefore, when o? 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 that |ēol gets reduced by at least y3 regardless the magnitude of of for GDg This means that the magnitude of o? does not directly affect the convergence speed. Instead, the relative magnitude between A(t) and B(t) determines the frequency which reccives priority during the learning process. As result, we observe an acceleration for models trained by signGD.
3
14

---

Published in Transactions on Machine Learning Research (11/2023)
10-
4-
(Aur))
14,00]
(u grows till begins oscillating around
GD
2-
Adam
cannot corrected
RMSProp
SignGD
10
104
10
207
10
105
100
10:
102
10
10
10
107
102
10a
10a
10
10
Training iteration 11)
Training iteration (O
Tra Training iteration (1)
8. Dynamics the error term
GD
150
Adam
123
RMSProp
100
Rg(0)
Ra(0)
SignGD
2
10
10
102
10a 10
10
10a
10
102
10a
10*
105
Training iteration (1)
Training iteration (U)
b. The standard population risk R2 and the adversarial population risk Ra
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 three-dimensional dataset created using (o8. of, )3) = (0.01, 0.0025, 0), and (vē V7, wz) = (5, 10, 0). All models are initialized with the same weight (w) wi (0), (0) = -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 ég starts oscillate around O. In our example, the green highlighted areas in the figure correspond to the iterations before ép starts to oscillate, and the red arcas show that the error along the irrelevant frequency cannot be corrected. (b) The standard population risk and the ad adversarial population risk (c = v2). 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.
Next, we observe that the error trajectory for the model trained by signGD closely resembles the one from the model trained by Adam for éσ and ěj. In the analysis of signGD, we show that |ē2] increases till [ěo] starts oscillating in O()). 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, E2 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 | decreases and |ě2l increases in the meanwhile. Once oscillation begins for |ēal. |ě2| 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 v2 in (12), the adversarial risk of those standard risk minimizers is exactly the squared E2 norm of the weight. With our choice of initialization, the resulting AA()) and [B(0) are 0.0289 and 0.0177 respectively. This mcans (G
that the ratio between the two adversarial risks is RR (WGD) [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, focus analyzing the robustness of the solution from frequency domain perspective, that is,
15

---

Published in Transactions on Machine Learning Research (11/2023)
Table I: Comparing the upper bound on the Lipschitz constant and the averaged robust accu- racy of neural networks trained by SGD, Adam, and RMSProp. We follow (Gouk al., 2021) compute the Lipschitz constants of each layer in isolation and multiply them together to establish an upper bound 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, &2 and foo bounded adversarial perturbations (Croce & Hein, 2020). Here, we average the accuracy across the perturbations and get 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
SGD
3.80
3.83
26.81
40.41
22.65
18.53
23.99
IT: ((b))
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
SGD
77.97%
77.95%
63.21%
55.65%
69.08%
71.42%
67.59%
Averaged
Robust Acc.
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%
the behavior of T with an input perturbation of At. 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 parameterizee linear regression analysis is that among all standard risk mini- mizers, the minimum norm solution is the most robust one. That is, a smaller weight norm implics better robustness. This suggests connection between the weight norm and model robustness. Nonetheless, the major limitation of the analysis is that it is designed for linear model. In this section, we generalize such 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 a network to its sensitivity with respect to changes in the input space. Consider a single-layer ReLU-activated foedforward network with Rd and W Dxd, With perturbation of Ar e Rd constrained by the vector f--norm, the maximum change in the model output as measured by the same norm can be bounded using
ReLU (w(x + Ar)) ReLU (W=)ll, - ||W I |[W]|p |Ar/|p
(30)
where ||W||p denotes the vector f norm induced matrix norm of the weight W and is referred to the Lipschitz constant of this single-layer model.
Consider the 4p vector norm, for all X1,02 E R, a function f is said to be Lipschitz continuous if (lf( - f(x2))l & L||m] - xzllps for some real-valued Lipschitz constant L 2 0.4 Indood, the Lipschitz constant of function with respect to inputs captures how sensitive the model is relation to changes in the input space.
In the single-layer model example, its Lipschitz constant is exactly the matrix norm of the weight. Morc generally, consider the feed-forward neural network as series of function compositions:
f(x) = (òr o 0 .... (z))
4 Anyy value of L. satisfying the Lipechita condition is considered valid Lipschita constant. For the sake clarity, we will refer the smallest, (optimal) Lipschitz constant as
16

---

Published in Transactions on Machine Learning Research (11/2023)
where each Oi is linear operation, an activation function, a pooling operation. A particularly useful property of the Lipschitz function is that the composition of Lipschitz functions with Lipschitz constant L1, L2, ... LN w.r.t. the same norm is also Lipschitz with an upper-bound on the Lipschitz constant L S L.. Denoting the Lipschitz constant of function ff as L(f), we can establish an upper bound on the Lipschitz constant for the entire weed-forward neural network using
I(O) - I(oi).
(31)
As such, for 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 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 RMSPrrp in Figure 1. Results are shown Table 1. The result shows that across all datasets and architectures, models trained by SGD have smaller upper bound on the Lipschitz constant compared
models trained by the two adaptive gradient methods. In Figure 1, we demonstrate the robustness of the neural networks under Gaussian noise, lz and & bounded adversarial perturbations (Croce & Hein, 2020). In Table 1, 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 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 irrelovant frequency, and thus they experience a huge drop in performance when the same statistics become corrupted. A Analytically, on a synthetic linear regression task where the dataset was designed 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 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 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 al., 2020; Forct 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). Tn
17

---

Published in Transactions on Machine Learning Research (11/2023)
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 ac- knowledges 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 AT World Leading Fellow. Resources used 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 also thank the members of the Adaptive Agents Lab who provided feedback on draft of this paper.
References
Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Koren, and Cyril Zhang. Disentangling adaptive gradient methods from learning rates. arXiv preprind or Xiv:20002. 1 11803, 2020.
Nasir Ahmed, T Natarajan, and Kamisetty R Rao. Discrete cosine transform. In IEEE transactions on Computers, 1974. 5
Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help hurt generalization? In International Conference on Learning Represenlations (ICLR), 2021. 3
Hagai Attias and Christoph Schreiner. Temporal low-order statistics of natural sounds. In Advances in Neural Information Processing Systems (NeurIPS), 1996. 5
Lukas Balles and Philipp Hennig. Dissecting Adam: In International Conference on Machine Learning (ICML), 2018. 4, 12
The sign, magnitude and variance of stochastic gradients.
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 Applications of Computer Vision (WACV), 2021a. 25
Philipp Benz, Chaoning Zhang, and So Kweon. Batch normalization increases adversarial vulncrability and decreases adversarial transferability: A non-robust feature perspective. In Proceedings of the International Conference on Computer Vision (ICCV), 2021b. 25
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In International Conference on Machine Learning (ICML), 2020. 2, 16, 17, 25, 26, 56, 57
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. 4
Wei Dai, Chia Dai, Shuhui Qu, Juncheng Li, and Samarjit Das. Very deep convolutional neural networks for raw waveforms. In IEEE International eConference on Acoustics, Speech and Signal Processing (ICASSP),
2017. 24,77 25
Yao Deng, Xi Zheng, Tianyi Zhang, Chen Chen, Guannan Lou, and Miryung Kim. An analysis of adversarial allacks and defenses on autonomous driving models. In IEEE International Conference on Pervasive Computing and Communications (PerCom), 2020. 4
Francis X Diebold. Elements of forecasting. Thomson South-Western, 1998. 7
18

---

Published in Transactions on Machine Learning Research (11/2023)
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. 4
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference Learning Representations (ICLR), 2021. 2, 24
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Journal of Machine Learning Reseorch (JMLR), 2011. 4
Li Fei-FFii, 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. 2
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations (ICLR), 2021. 5, 17, 18, 45
Joseph Fourier. Théorie analytique de la chaleur (The Analytic Theory of Heat). 1822. 5
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep leedforward neural networks.
In International Conference on Artificial Intelligence and Statistics (AISTATS), 2010. 14, 43
Tan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples.
In International Conference on Learning Representations (ICLR), 2015.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural networks by
enforcing Lipschitz contimuity. Machine Learning, 2021. 16, 17
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 (NewrIPS), 2021.
Herbert Gross. Handbook of Optical Systems: Fundamentals of Technical Optics. 2005.
Suriya Gunasckar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems (NeurIPS), 2017. 1,
Chuan Guo, Jared S Frank, and Kilian Q Weinberger. Low frequency adversarial perturbation. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAT), 2020. 6
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 Computer Vision (ICCV), 2015. 14, 43
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. 24
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 Leurning Represenlations (ICLR), 2020. 4
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a: overview of mini-batch gradient descent. 2012. 1
Jeremy Howard. Tmagenette. URL https////ggttbbbc.ffaaaaaaa////e
2
19

---

Published in Transactions on Machine Learning Research (11/2023)
Hanxun Huang, Yisen Wang, Sarah Erfani, Quanquan Gu, James Bailey, and Xingjun Ma. Exploring architectural ingredients of adversarially robust deep neural worksrks. In Aduances in Neural Information Processing Systems (N),rIPS), 2021.
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. 5
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry, Adversarial examples are not bugs, they are features. In Advonces in Neural Information Processing Systems (NewrIPS), 2019. 46
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), 2015. 2
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. 2018. 17
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the Fajjsee-nnassewwicn condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2016. 4, 12
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015. 1, 4
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009. 2
Kun Kuang, Peng Cui, Susan Athey, Ruoxuan Xiong, and Bo Li. Stable prediction across unknown envi- ronments. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018. 4
Ram Shankar Siva. Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comis- soneru, Matt Swann, and Sharon Xia. Adversarial machine learning-industry perspectives. In IEEE Security and Privacy Workshops (SPW), 2020. 2, 5
Yann LeCun. The MNIST database of handwritten digits. http://yann. lecun. htm//erdd//mnss//.m.. 1998.
Zhuohang Li, Cong Shi, 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. 4
Kaiseng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations (ICLR), 2020.
Avery Ma, Fartash Faghri, Nicolas Papernot, and Amir-massoud Farahmand. SOAR: Second-order adver- sarial regularization. arXiv preprint drXio:2004.01832 2020. 5, 17
Avery Ma, Aladin Virmaux, Kevin Scaman, and Juwei Lu. Improving hierarchical adversarial robustness of deep noural networks. arXiv preprint arXiv:2102.09012, 2021.
Avery Ma, Nikita Dvornik, Ran Zhang, Leila Pishdad, Konstantinos G Derpanis, and Afsaneh Fazly, SAGE: Saliency-guides mixup with optimal rearrangements. In British Machine Vision Conference (BMVC),
2022a. 4, 5
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. 4, 12
Alcksander Madry, Aleksandar Makclov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018. 5
Stéphane Mallat. A wavelet tour of signal processing. Elsevier, 1999. 5
20

---

Published in Transactions on Machine Learning Research (11/2023)
Robert McAulay and Thomas Quatieri. Speech analysis/syntheeis based on sinusoidal representation. In IEEE Transactions on Acoustics, Speech, and Signal Processing, 1986. 5
Emmanuel Moulay, Vincent Léchappé, and Franck Plestan. Properties of the sign gradient descent algo- rithms. Information Sciences, 2019. 4, 12, 32
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading dig- its in natural images with unsupervised feature learning. In Neurips Workshop on Deep Learnöng and Unsupervised Feature Learning, 2011.
Alan V Oppenheim, John R Buck, and Ronald W Schafor. Discrete-time signal processing. Pearson, 2001. 5
William B Pennebaker and Joan L Mitchell. JPEG: Still image data compression standard. Springer Science & Business Media, 1992. 5
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 (NewrIPS), 2021. 3
Adnan Qayyum, Junaid Qadir, Muhammad Bilal, and Ala Al-Fuqaha. Secure and robust machine learning for healthcare: A survey. In IEFE Reviews in Biomedical Engineering, 2020. 4
Qian Qian and Xiaoyuan Qian. The implicit bias of adagrad on separable data. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Sylvestre Alvise Rebufii, 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.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations (ICLR), 2018. 24
Martin Riedmiller and Heinrich Braun. A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In IEEE international conference neural networks, 1993. 4, 12
Daniel L Rnderman. The statistics of natural images. Network: computation in newral systems, 1994. 5, 6
A. van der Schaaf and J.H. van Hateren. Modelling the power spectra of natural images: statistics and information. Vision research, 1996.
Odelia Schwartz and Eero P Simoncelli. Natural signal statistics and sensory gain control. Nature neuro- science, 2001. 5, 6
Steven H Schwartz. Visual perceplion: A clinical orientation. McGraw-Hill Medical Pub. Division, 2004.
Yash Sharma, Gavin Weiguang Ding, and Marcus Brubaker. On the effectiveness of low frequency pertur- bations. In Proceedings of the International Joinl Conferences on Artificial Intelligence (IJCAT), 2019. 6
Zheyan Shen, Jiashuo Liu, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards out-of- distribution generalization: survey. arXiv preprint XrX:::2108. 19624, 2021.
Samuel Henrique Silva and Peyman Najafirad. Opportunities and challenges in deep learning adversarial robustness: A survey. arXiv preprint arXi::2007.00758, 2020. 2
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 Muchine Learning (ICML), 2019. 5. 17
Eero Simoncelli. Statistical models for images: Compression, restoration and synthesis. In Conference on Signals, Systems, and Computers, 1997.
21

---

Ophthalmic and Published in Transactions on Machine Learning Research (11/2023)
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. 1,
Andreas Peter Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lu- cas Beyer. How to train your vit? data, augmentation, and regularization in vision transformers. Transactions on Machine Learning Research (TMLR), 2022. 26
Christian Szegedy, Wojeiech Zaremba, Πlya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, In International Conference on Learning Representations (ICLR), 2014. 4
David J Tolhurst, Yoav Tadmor, and Tang Chao. Amplitude spectra of natural images. Physiologioal Oplics, 1992. 6
Richard E Turner. Statistical models for natural sounds. PhD thesis, UCL (University College London), 2010.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez- and Yoshua Bengio. Manifold Mixup: Better representations by interpolating hidden states. In International Conference on Learning Representations (ICLR), 2019. 4
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Newral Information Processing Systems (NewrIPS), 2018. 17
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. 6
Gregory Wallace. The JPEG still picture compression standard. Communications of the ACM, 1991. 6
Bohan Wang, Qi Meng, Wei Chen, and Tic-Yan Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In International Conference on Machine Learning (ICML), 2021.
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 IEFE Conference on Computer Vision and Pattern Recognition (CVPR), 2020. 7
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. 25
Pete Warden. Speech commands: dataset for limited-vocabulary speech recognition. arXio preprint arXiv:1804.0388 2018. 2, 24, 27
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. 18, 45, 46
Yuxin Wen, Shuai Li, and Kui Jia. Towards understanding the regularization of adversarial robustness neural networks. In International Conference on Machine Learning (ICML), 2020. 5, 17
Ashia C Wilson, Rebecca Roclofs, 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. 1, 3,
Boxi Wu, Jinghui Chen, Deng Cai, Xiaofei He, and Quanquan Gu. Do wider neural networks really help adversarial robustnoss? In Advances in Neural Information Processing Systems (NeurIPS), 2021. 5
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNISTT a novel image dataset for benchmarking machine learning algorithms. Xiv preprint 1 077.07777 2017. 2
22

---

Published in Transactions on Machine Learning Research (11/2023)
Dong Yin, Raphael Gontijo Lopes, Jon Shlens, Ekin Dogus Cubuk, and Justin Gilmer. A Fourier perspective model robustness in computer vision. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. DORO: Distributional and outlier robust optimization. In International Conference on Machine Learning (ICML), 2021. 4
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theo- retically principled trade-off between robustness and accuracy. In International Conference on Machine Learning (ICML), 2019. 27
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. Mixup: Beyond empirical risk minimization. In International Conference on Learning Representations (ICLR), 2018.
Haoran Zhu, Boyuan Chen, and Carter Yang. Understanding why vit trains badly on small datasets: An intuitive perspective. arXic preprint 03751, 2023. 25
23

---

Published in Transactions on Machine Learning Research (11/2023)
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 archilectures used to Irain 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 obscrvations 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.
B Training Details
Data augmentation: In our paper, we study how the presence of irrelevant information in the dataset affects the robustness 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 datascts in the frequency domain requires additional analysis (ailored 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 Py (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 B1 0.9 B2 0.999, e 10-8 and disable weight decay and disable AMSgrad (Reddi et al., 2018). For RMSProp, we default values of a 0.99, 10 and disable momentum and disable centered RMSProp which normalizes the gradient by 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
SGD
MNIST
Adam
0.0005
RMSProp
0.0005
SGDD
MNIST
Adam
0.0005
RMSProp
0.0005
Dataset
Structure
SGD
Conv(1, 16, 4) ReLU
CIFAR10
Adam
0.0002
MNIST PashionMnist
RMSProp
0.0005
Conv(16, 32, 4) ReLU-
FN(21632, 100) FN(100, 10) SM()
SGD
CIFAR100
Adam
0.0005
RMSProp
0.0005
CIFARIO
CI SVHN Caltech1u1
SGD
PesActResNet18 (He al., 2016) VIT-B/16 (Dosovitskly et al., 2021)
SVHN
Adam
0.0002
RMSProp
0.0002
Imagenette
SGD
0.05
Caltech101
Adam
0.0002
Speech Commands
M5 (Dai et al., 2017)
RMSProp
0.001
SGD
Imagenette
Adaun
0.0002
RMSProp
0.0002
SGD
Speech Commmands
Adamn
0.1
RMSProp
Model architecture: For MNIST and FashionMNISTT, we use a ReLU-activated, two-layer convolutional neural network ending with two fully-connected layers. For CIFAR10, CIFAR100, SVHN, Caltoch101, 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
24

---

Published in Transactions on Machine Learning Research (11/2023)
defined by Dai et al. (2017). See Table 2 for details of all architectures used in this paper. We denote Co o, k) as convolution layer having i input channels, output channels with & by & filters, FN(1, o) as 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 contered around models based on convolutional neural networks, within the compuler 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.
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.
Batch normalization: We concentrate
C Results on Standard Generalization and Model Robustness
Main results: Table 3 summarizes the result on the standard generalization ability and robustness proper- ties 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, l2 and -ooudddd 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 perturbation with any particular parameters. The degree of severity is determined by the variance of the Gaussian perturbation and an l and lo 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 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 gen- eralization 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 coun- terparts 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).
C.2 Results on Vision Transformers
In addition to the network designs considered in Table 2, extend our work to ViT in order to verify whether similar observations can be drawn on other neural network architectures.
It is important to nole 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 gencralize 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.
25

---

Published in Transactions on Machine Learning Research (11/2023)
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 perturba- tions, lg and -bunddd 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.
Gaussian perturbations
fg-bounded attack
Ex -ounded attack
Dataset
Optimization
Test
x²
0.01
a² 0.05
x² 0.1
0.5
0.7
1.0
0.05
0.07
0.1
SGD Adam
98.72
98.55
97.91
95.64
93.00
87.33
66.33
87,53
71.93
31.50
MNIST
99.05
98.86
96.76
89.33
92.33
86.00
54.67
85.40
52.93
8.77
RMSProp
98.90
98.77
97.02
90.63
91.07
83,00
50.00
82.73
50.00
7.33
o²
0.001
of 0.005
o² 0.01
0.1
0.5
0.7
0.01
0.03
0.05
SGD
91.20
90.49
87.78
84.30
82.33
24.33
12:33
67.23
22.30
4.17
FNSHionMNIST
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
72.67
15.93
4.67
62.67
16.33
1.67
a²
0.001
o² 0.005
o² 0.007
0.1
0.2
0.3
2005
25r
SGD
90.16
87.35
74.13
68.66
67.40
37.57
16.30
53.93
21. 27
0.93
CIFARIO
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
60.10
25.47
47.87
14.03
a²
0.001
0.005
o² 0.007
0.1
0.2
0.3
258
258
255
SGD
59.76
56.88
16.26
41.28
28.47
12.93
5.90
18.80
5.57
1.17
(IPAR100(top1)
Adam
61.10
55.30
31.51
24.92
21.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
SGD
84.67
81.77
72.84
67.53
80.30
70.20
59.90
75.30
61.70
39.53
c(P)R100((op5)
Adam
85,41
81.37
58.11
19.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
d²
0.001
0.003
0.005
0.1
0.2
0.3
SGD
96.11
95.68
94.47
93.81
85.53
63.60
39.63
80.67
49.83
17.03
SVHN
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
0.01
o² = 0.05
o" 0.1
0.5
< 1.0
= 1.5
253
23x
255
SGD
70.80
68.13
57.67
43.46
58.77
47.03
35.17 17
48.27
27.87
4.70
Caltech 10l Itop
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
SGD
85.96
84.84
77.57
67.16
85.30
844.43
79.00
83.97
75.47
52.27
(top))))01(top5))
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
63.97
41.33
23.90
8 0.01
a² 0.05
d² 0.1
0.5
1.0
1.5
255
235
SGD
89.41
84.83
67.23
50.21
70.70
44.13
21.33
17.23
14.33
0.37
Imagenette
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
Therefore, we perform fine-tuning on a pre-trained VTT-B/16. Among the datasets we considered, Imagenette is a 10-class subset of the Imagenet-1k 1k dataset, making it especially suitable for the fine-tuning task, since the publicly available ViT checkpoint was pre-trained on Imagenet-Ik. 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 e for adversarial perturbations, as used in Table 3. The results can be found in Table 5. We draw three observations.
26

---

Published in Transactions on Machine Learning Research (11/2023)
Table 4: Results on standard generalization and robustness of models trained with BN enabled. We follow the exact optimization configuration as the oncs used in generating Table The only modification is that BN is enabled.
Gaussian perturbations
fz-bounded attack
Ex -bouded attack
Dataset Optimization
Test
0,001 o² 0.005 o² 0.007
250
SGD
92.24
$6.91
55.23
43.29
64.84
27.86
6.96
48.64
9.14
0.04
CIFARIO
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
$5.93
15.16
2.23
37.7
3.76
0
x² 0.001
x² 0.005
a² 0.007
0.1
0.2
0.3
25p
255
205
SGD
72.24
57.99
26.08
19.23
34.36
10.2
3.63
21.3
4.8
0.2
CIFAR100
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
1.1
13.7
0.1
o² 0,001
of 0.003
o² 0.005
= 0.1
0.2
0.3
255
205
265
SGD
94.16
95.81
94.96
92.90
81.73
60.56
41.96
76.13
49.26
15.3
SVHN
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
22.16
3.96
a² 0.01
a² 0.05
a² 0.1
0.5
1.0
1.5
25r
265
SGD
78.61
72.69
45.38
25.87
61.23
44.03
23.03
46.80
13.
0.83
Caltech101
Adam
79.58
62.21
21.08
10.35
56.76
34.46
13.06
37.3
5.66
0.23
RMSPtop
75.56
69.89
45.38
41.6
20.5
42.6
0.6
o² 0.01
o² 0.05
o² = 0.1
0.5
1.0
< 1.5
255
205
SGD
89.35
76.67
46.18
28.27
73.43
42.96
17.56
48.95 93
14.33
0.03
Imagenctte
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
Table 5: Results on standard generalization and robustness of ViT-B/16 fined-tuned on the Imagenette dataset.
Gaussian perturbations
fg-bounded attack
Poo -ooudedd attack
Model
Optimization
Test
0.01
x²
o²
1.5
SGD
99.18
99.05
96.16
91.25
6.2
0
0
1.3
0
VIT-b/16
Adam
99.51
94.43
88.59
RMSProp
99.92
99.54
95.38
89.91
5
0
0
0.8
0
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 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 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 optimizors, where models finc-tuned with SGD cxhibited greater robustncss to both Gaussian noise and adversarial perturbations when compared to models fine-tund using Adam and RMSProp.
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 Table 6, which compare the standard generalization and robustness properties an audio classifier trained on the Speech Commands datasct (Warden, 2018). We focus on the NreActResNet18 architectures and all models are trained for 200 epochs, with an initial learning rate of 0.1 and learning rate decay by factor of 0.1 at epoch 100 and 150. We consider the accuracy of
27

---

Published in Transactions on Machine Learning Research (11/2023)
Table 6: Results on standard generalization and robustness of models on an audio classification task on the Speech Commands datasct.
Gaussian perturbations
fz-bounded attack
fooubdddded attack
Dataset
Optimization
0,001 o² 0.003
0.0001
0.0005
SGD
85.14
55.76
39.88
33.42
70.01
20.31
9.81
75.6
36.71
13.47
Speech
Commands
Adam
54.73
38.87
8.49
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).
Gaussian perturbations
bz-bounded attack
Ex -bounded attack
Dataset
Optimization
Test
0.001
x² 0.005 a² 0.007
0.1
0.2
0.3
250
SGD
90.16
87.35
71.13
68.66
67.40
37.57
16,30
53.93
21:27
0.93
CIFARIO
SGD-m
89.79
87.28
73.207
66.783
67.1
38.067
15.9
55.667
20.233
0.6333
o² 0.001
o² = 0.005 of = 0.007
== 0.1
<= 0.2
= 0.3
255
255
I55
SGD
59.76
56.88
5.90
5.57
1.17
CIFAR100
SGD-m
56.08
55.03
44.97
40.03
29.2
12.4
5.7
19.7
6.5
0.8
0.001
o² 0.003 o² 0.005
==
253
213
4
SGD
11
95.68
94.47
93.81
85.53
63.60
39.63
80.67
49.83
17.03
SVHN
SGD-m
96.14
95.71
94.44
77.33
15.96
x² 0.01
o² 0.05
a² = 0.1
= 0.5
1.0
< 1.5
253
258
255
SGD
70.80
68.13
57.67
43.46
58.77
47.03
35.17
48.27
27.87
4.70
Caltech101
SGD-m
69.89
67.77
55.77
41.34
54.86
43.36
31.06
44.16
23.9
3.133
0.01
a² 0.05
8² 0.1
= 0.5
1.0
6 1.5
= z
SGD
89.44
84,83
67.23
50.21
70.70
44.13
21.33
47:23
14.33
0.37
Imagenctte
SGD-m
85.05
68.58
0.2
models under Gaussian- and advvesariiall--peruubdd 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 robust- noss when compared to the other two optimization methods. Those 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-enable SGD (SGD-m) are included in Table 7. We maintain the exact same optimization configuration 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 8 0.9. The result shows that models optimized by both vanilla SGD and SGD-m exhibit similar trends in terms of generalization and robustness.
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 to 15, we visualize the original images and the modified images used in Sec. 3.1.
To understand how the modified training images generated, use Pngg(r, with 0 < p < 100 to denote the operation that modifies the input image by removing the DCT basis vectors whose magnitudes are in the bottom - th percentile. We use (ag((1 p) to denote the binary mask used in the process. Consider an image x E Rdxd the entire process can be formulated as
nrg (k. C(ā Marg (z. ())
28

---

Published in Transactions on Machine Learning Research (11/2023)
Table 8: Examples of the synthetic data distribution in the frequency and the spatial domain.
x
Proguency-domain Representation Spatial-domain Representation
ding
0.0.0.0}
0,0)
(138. V 8o, v380) (V /IX.)
diag
00.07.0}
[0, 01.
diag
[0,0,0]]
(0, X2)
(VAR, -V /382 (8a)
diag
00.09.02
(0, (1.xx))
(VEX, + V - 3882. - V + Vid
diag
{ [
0,)
+ V (ViX+
[:00 1382, / f (Fx (1a)
ding
{ 12 08.0
(No. 0)
(ViX, + v f v 380 / 18o v
diag 10). o7
X2)
(A (V + 1x |/2 f
f8. - +
where is the clement-wise product and C' the DCT transformation matrix. The binary mask Murg E {0, 1] axd is defined as
Marg( {0
|ل, ((..p)
otherwise,
where 6(ē; p) E R computes the 100 th percentile in |z). Therefore, DCT basis vectors with a magnitude smaller than the threshold are first discarded in I, and then this filtered is converted back to the spatial domain.
Similarly, we use (ate p) to denote the operation that modifies the input image r by removing the DCT basis vectors whose froquency in the highest s00-th percentile. We use Mrre(() to denote the binary mask used in the process. This operation be formulated as
freq (x,p) C(ă O Mtre(
where Mireq (0, 1]xd
dxd is defined
[1 if アナ
P T00
22d
Mirec (p)
0 otherwise,
and j are frequency bases. Notice that Mreq only depends on the size of the image, whereas Marg depends on the input x since we identify the threshold value in [š]. Examples of the modified images and the modification process are shown in Appendix G.
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 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 X follows a Gaussian distribution (ū, E.,, and for analytical tractability, we consider jı = and a diagonal structure of Σ, i.c., Σ = diag(ō), ..., _2-1). ). Admittodly, is quite unconventional define the data distribution directly in the frequency domain, so we provide few examples in Table 8 illustrate the structure of the input data in both representations.
Similar to Sec. 4.2.2, we focus on a low dimensional sctting with d = 3. The first six rows in Table 8 represent the scenario when there are zero variances in Σ. 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 value of zero 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 some dimensions can be fully predictable by knowing the values of data at some other dimensions.
29

---

Published in Transactions on Machine Learning Research (11/2023)
E.2 Derivation of Equation 9
The adversarial risk under an 62-norm bounded perturbation with a size of is
(w) & E
(X,))
max |AflI
f(X + Ai, Ai
f(x + Ad, ()) - 8/8
(X,))
max
|
=Rx
max |
1
K
8 + AT, 1 - X 23 )1²
2
1
{X, w いt + ( Aē, w 1)
= =Ex
max
||A0|||Se 2
where we focus on the expectation over X, as is replaced with ( (x, w²)
E.3 Derivation of Equation 10
Given a r.v. X, we define A to be the maximizer of the term inside the expectation of (9):
A arg max
K X w" ( x
|| ||Ae
2
To maximize this term, we need the two inner product terms to have the same sign. This means
AF = signlK X, i 16" )arg |aargmax/ K Ai, w w
|| base
For the remaining argmax term, we can first use the Cauchy-Schward inequality to obtain
1( A( w) ||a8|2Se
||
| 1 e² ||0b
max
max 2S
which leads to Finally, we have
arg max (( AT, 17 10) = c |
w
AF sign({ 8, Φ w0)) >)
110
E.4
Derivation of Equation 11
The adversarial risk is
1
Ra(w)=
Ex
{X, w w + +e esign( siign((X X, i w >||00||2
2
1
2 Ex
{x, i 0² 2c (x, to - w² |||01|1 |1
1
Σ
o: w/)² + +Bxx 1(8, to w >|
|
2
2
sEL.M
To compute the expectation, we first denote Z = EieLo 8,(w, w Because of 0 for all i E lerel this allows us to ignore those irrelevant frequencies in the summation in Z. This leads us to
Eg ( v 5 >1
= Ez |z|
30

---

Published in Transactions on Machine Learning Research (11/2023)
Since Z is linear combination of zero-mean Gaussian r.v.s, this makes it also zero-mean Gaussian r.V, T.e., B[ 0. The variance of Z is
2 E[ E
Σ
Σ
X1X,(10 - (1) m77)
Σ VElral
EEleal 1 &l
E
X2 2ū,²²
ichell
of (ig wi )
where the expectation on the cross-multiplication term is vero because X, and X, are independent. r.v.'.. This means Z N/ o3) with o3 Eielon oā((0; w Therefore, Exz |2| is the expectation of folded
normal distribution:
Ez 12 = oz
E.5 Derivations of the GD Dynamics: Equation 14 and Equation 15
The gradient computed using the population risk is (a = E [Xx]] e(t) Σe(t), and the learning dynamics of GD in the spatial domain can be captured using:
ct 1) w(t 1) w²
w(t) R. w"
w(t) w" TyEe(t)
=e(t) - I)Ee(()
(I 7)))e(t)
(T x1))+++((0))
This shows that the learned weight converges to the optimal weight w" at rate depending on E. To see the GD dynamics in the frequency domain, can simply perform DCT on both sides of (14):
a(L + 1) = C(T - -e))
= C(I -/)t)
C(1 -2)" E(0)
C(I 1/)) -C - nE)CTT(() E(0)
[C(T ( 1+1 2(0)
(1 1
(I (E=
where Σ is the covariance of a.
E.6
Derivation of the signGD Dynamics for any Σ: Equation 19 and Equation 20
The signGD learning dynamics in the spatial domain is
e(t + 1) w(t + 1) w"
w(t) sign V (w)] w
e(t) 7 sign (e())
31

---

Published in Transactions on Machine Learning Research (11/2023)
The signGD learning dynamics in the frequency domain obtained by taking the DCT transformation both sides of (19):
ē(t + =(t) n/C [igg(
ē(() np sign| (C ECCT((t)
a(() - n/C sign(C" (e()).
E.7 Derivation of the signGD Dynamics for Σ diag {ō), of. 0): Equation 21
To understand ē(L + 1) with our specific choice of Σ C ΣC and Σ diag {ot: of. 0}, first notice that the DCT transformation matrix = C(3) follows the definition in (4):
3
3
3
C=
COs
cos T
cos
STT
6
cos
COs π
cos
5xt 3
Denote / (o)o((t) and / (f)) by using A(t) and B(t), respectively. Putting it all together, we have:
e(t E(t) Cinninn IC T ECe(t))
= =(( - +/C sign |C SE(()
(t)
V 3
V
a(t) 1
sign
0
0
V
sign M FaBEo( + [afa
V
3
sign [V (
a(t)
"
sign V (oto(() v (1))
sign [A(1) + B())
3
a(t) 17
sign[A(t)]
sign[A(tt B(t)]
J3 [At) + B(t) + sign[A(t)] + sign(A(t) - B(t))
3
ē(t) -1
/ (sign ((t)) B(t) sign[A(t) B(t)))
2
/B
sign A(L B()) </6 sign(A()) (A(1] v sign(A(() B())
E.8 Understanding the Dynamics of signGD with Σ diag o oo 0}
Previous work has shown that for strictly convex problems with a unique minimum, the signGD solution converges to the minimum under sequence of decaying learning rate: lim4++00 r7()) 0 (Moulay et al, 2019). In this section, we follow Sec. 4.2.1 where the GD dynamics is studied under constant learning rate and investigate the behavior of signGD under a fixed 7, Compared to the asymptotic GD solution that converges exactly to the standard risk minimizer, we demonstrate that the asymptotic signGD solution converges to an O(r) neighborhood of the standard risk minimizer.
For the rest of this section, we first perform a partition- based analysis to study the learning dynamics of é and é in Appx. F.8.1. Proposition E.4 summarizes how the value of weight changes in different partitions,
32

---

Published in Transactions on Machine Learning Research (11/2023)
Table 9: Learning dynamics of signGD. The dynamics of the error term in the frequency domain can be written in tabular format and the exact update depends on the initialized weight (0) and the true model
w². We use A(t) and Bt) to denote v3 (t and v2 (t), respectively. Invalid sign combinations are denoted by using n/a.
3
No.
[
(ig[((()) + B(A) sign(A(t) B(t)
6(t 1)
[A( vs. [B(A]]
a(t) v3.0,0
[A(*] > [B(0]
2
1
a(1)
A
5
v2.
IA(1) [B(0]
800)
22
|A(0) [B(0)
8(1)
24 V2,
|4(0) < B(O)
n/a
n/a
n/a
n/a
a/a
n/a
6(1)
2/3 V2
|4(M - [B(
n/a
n/a
n/a
n/a
a/a
n/a
n/a
n/a
n/a
a(1) -
v2, Y
[A(+) < [B(0]
n/a
n/a
n/a
7
8(1) 4 22,
40
IA(1) < B(O)
8
6(1)
0,0
[A(+)] > (B(()
a(1)
V6
IA(0) [B({]]
n/a
n/a
10
8(0) 2 38
IA(1) [B(1)
a/a
a/a
n/a
n/a
n/a
n/a
a(A) 9 (0. v2,0
IA(1) < [B()]
n/a
n/a
n/a
12
8(8) 9 0. - -22.0
[A(3] < [B())
a/a
a/a
n/a
n/a
n/a
n/a
n/a
1/1
n/a
n/a
n/a
13
0
Optimal
[M(0] [B(0]
and the weight adaptation of ég and & is summarized Corollary F.6. Based on the corollary, we analyze the dynamics ě Appx. E.8.2. Lastly, we focus on the differences between the adversarial risk of solutions found by GD and signGD in Appx. E.8.3.
E.8.1 Dynamics of è and é, under signGD
With our choice of E, (21) shows that weight adaptation depends on the sign of three terms: A(1), A())+B()) and A(t) Bt)). This allows us study the lcarning dynamics of signGD by analyzing the three terms Table 9. There are 27 sign combinations in total; however, not all of them are valid. For example, consider the combination with sign[A(t)]
sign (A(t) + B(t) -1 Those two conditions imply that B(t) < 0 and [A(t)] < [B()),, and this means that sign[AD [A(t) - B()) must be positive. This makes the entry with sign[A(t) B()) = -1 invalid, as shown in the fifth row in Table 9, We denote those entries with invalid sign combinations as n/a.
Notice (21) that the weight adaptation under signGD depends on the dynamics of A(t) and B(t), and they are functions of (t) and (t) respectively, so let us first focus on understanding the weight adaptation at the first two frequency bases.
33

---

Published in Transactions on Machine Learning Research (11/2023)
There 13 possible updates in Table 9. Notice that the non-zero updates always in the direction to reduce [()( and | (()), and the step size depends on the magnitude of [A(!)] and [B())- To simplify the analysis, let us focus on the updates on A and B instead. For example, in updates 1 and 8, decreasing |ēol by v is equivalent to decreasing |A| by ozn-
2000 Now take note of the limited number of update magnitudes for |A], specifically oin. 3 and dgn which correspond to updating |dul by v 2v33 2y'",, and ya,, 77, respectively. Similarly, |B] has only two update din magnitudes, namely ofn and 2,, which correspond to updating (ēil with v2n and L2 2n, respectively. This observation leads to the following proposition.
"3
Proposition E.1. Suppose the initial weight w(() ~ μ are sampled from probability density μl, then neither A nor B (oo nor è1) can be reduced to exactly 0 almost surely.
Proof. Due to the limited number of update magnitudes, reducing |4| and [ to 0 requires their initial value to be exactly some integer multiplication of those updates. However, with the initial weight sampled from probability density μe, the probability of the initial values of A and B being the exact integer multiple of the possible update is O.
Next, we introduce the following lemma to understand the dynamics of A(t).
Lemma E.2. Consider the updale rule s(1 + +) = xx()) - sign(ar(1) (1) where x E R, A(t) E (Ai, A2.... ,max..,Ammx and 0 < A1 < D2 < <... < Amax. Then there exists such that |x(t)| S Amax. Moreover, whenever [x(t)] Amax, the rest of the sequence stays Amax-boundedd i.c., |x(t')| S Amax for all 0' 122.
Proof. In the following, we provide a proof for the case when x(0) > 0. A proof with xx0) < 0 can be done in similar way. The proof can be divided into two parts.
1. Let us denote the sequence of that [ax(t] & Amax-
x(t)} by (x(t)). First, we prove that there exists t such
If (r(()= > Amxx then 1) x() ((t) 2 (t) - A max > 0.
Consider {a(()) with x(t')= > Amax for all t' E f0, 1......... we have s(t' +1) = x(t) A(t) a(t'). This means that for any æ(t) > Amax, the sequence (a(t)) is decreasing.
We prove, by contradiction, that there exists & such that |z(t)] < Amax. Suppose that such & does not exist, then one of the two cases must happen.
1. xtt) > A max for all t.
3k such that z(0)= > x(1) > ... x(k) > Amaxi but æ(k + 1) < -
For case 1, since x(t) > Amax, we know that {x(t)} is decreasing and bounded from below, so we have
x(t) + x= 2 Amax as t > co. This means that lim sxt) = lim x(t + x².
Using the update rule, we have
lim x(t + 1) lim x(t) (t) sign(x(t)) +0
++000
= lim x(t) A(t)
1+000
= x (tt),
or x² = x² ------00 A(), which is impossible because A()) > 0.
For case 2, by the assumption the case, we have r(k: + 1) = x(k) A(k) < -Amaxs which is not possible
because xlk)== > A mmax
The same approach can be applied to prove the case when is initialized with negative value, i.e., x(0) 0.
34

---

Published in Transactions on Machine Learning Research (11/2023)
The first part of the proof shows that there exists t such that [z((t] Amax-
2. Next, we show that for any t such that |x(t)] S maxx we have |æ(tt + 1)1 < Amax..
When 0 I xt) I maxx we have
x(t + 1) = xz) A(t) -max and
=(t+1)= = x
- (t) S <x(t)= S Amax.
When - -axx S xxt)= - 0, we have
x(t + 1) = z (t) ((t) I Amax
and 11 =x(]) + A(t) 2 x(t) 2 A max.
This means that - max S (t + +1) Amxx, and this results holds for any t such that |zx(t) Amax-
To combine the two parts of the proof, consider the first of such 4, i.e., t= min {t [z((t] S Amax J. We can prove, by mathematical induction, that |z((t)] < Amax for all t' 2 t.
The following proposition describes the behavior of A(t) under signGD. Proposition E.3. There erists such that |A(t') S oदn for all t' >
Proof. Table 9 shows that there is always a non-zero update in the direction to reduce [A(t)), so we can define the dynamics of A(t) as
1) = A(1) - sign[A(()](())
{ [āān
2 kin). Lemma E.2 with Amax o proves the proposition.
where ((t)
{ 3 3
Proposition E.3 implics that once |A| drops below ozn, it remains below oदn for all future itcrations. Com- bining Proposition E.3 with the update directions of A in Table 9, we know that A will begin oscillating around zero. However, there are some limitations of Proposition E.3. First, we do not know when exactly the oscillation starts: whether starts immediately following the first itcration when |A] S oßn or from some iterations after it. Second, the characteristics of this oscillation (periodic or non-periodie) are un- known. Answers to these questions can improve our understanding of the behavior of A, and later become particularly useful in developing the asymptotic signGD solution of é2, which is important because it leads to the adversarial risk of the signGD solution.
Because the update for B(I) can be zero when [A(O] > |B(t),, Lemma F.2 is not suitable to understand the dynamics of B, as the lemma requires that all step sizes be greater than zero. Nevertheless, Proposition E.3 allows us to narrow down the range of A and we can partition the set of all possible values of A and B. By analyzing the dynamics of A and B in those partitions, we can develop the standard and adversarial population risk of the asymptotic signGD solution under constant learning rate 77-
Let us first divide the set of values of (A, B) into partitions based on the value of [A], and then divide those partitions into smaller subpartitions based on the relative magnitude of |A] and [B]. Such a partitioning process is illustrated in Figure 6.
R 1 ( 2 < |A| < o3n and B E 00)
R11 = ={A, (A, e R1 and |A| < |
R12 (AA (A, E R1 and
|A] > [B]}
R₂ =
= (4, B):
0i 3
< ||||
<
20 and B E (-o0, 00) } 3
R21 = {AA B3: (A, E Rg and
|A| < |b}
R22 = { BA, (A,B) Ra and
A > [B] and
AA+ + 03n [B] and | .दn [B]] }
Rz3 { (A, B) BA, Rs and
A > [B] and (I बदगा
< B or A |दप < [ },
35

---

Published in Transactions on Machine Learning Research (11/2023)
20
[AIt]] [8
R1
8
R12
Ro
R22
B(t)
R23
R31
R32
Ras
-8
R34
[iil |B()
-26in
-56n
-1880
108n
3o8n
66n
A(t)
Figure Analyzing the dynamics of and B by partitioning the set of values of (A, B) in I- hi x R. Such a set is first divided into partitions R1, R₂ and R3 based on the value of |A]. Then, we consider R. R22, R3i, R32, Ra3, R the stationary subpartitions, because once (A(L), B()) Ra the sequence remains in the stationary subpartitions. Also, consider RG {R R12, Rzi R23) as the transient subpartitions, because any (A(t), B(t)) e RG will soon enter one of the stationary subpartitions, that is, there exists t' 2 t such that ((()),B(t)) E R.. We consider of = of = 1 and 1 in this figure.
RR3 = (A. |A
and B (0) dh 3
R31 = (AA (A, E Rs and |A| > [B]}
R32 = { (A, B) UKEZ -fo t0} { (A, B) E Rg and |A] > B kopn }.
< c31 Rys (A, B) UkEZaad (A, E R3 and |A| + B + ko
3
Rz4 = R3 - (Ra1 U R32 U R33),
where Zodd and Zeven are the set of odd and even integers, respectively.
There are nine non-overlapping subpartitions. We call R2i, Rai Rı2, R3a and Ras the slationary subpar- titions and denote R, {R22, R3I. R32, Ra3, Rı1}. They are called stationary subpartitions because once (A(t), B(t)) E Ra, the sequence remains the stationary subpartition. On the other hand, we call R11, R12, R21, Res the transient subpartitions and denote R₂ = {R11. R12, R21, R23). They are called the transient subpartitions because any (A(I), B())) RS will enter of the stationary subpartitions, that is, there exists t' 2 such that (A(t', ((t)) E Re. The dynamics of A and B can be summarized in the following proposition.
Proposition E.4. Transient subpartitions: For each of R Re, consider such that (A(t), B(t)) R, then there exists t' such that (A(t'), B(t)) R,- The transition of (A(t), B(t)) from R, to R, happens at most iterations after t; specifically, it corresponds to the scenario of (A(t), B(t)) R11 B((++)) E R2s, (A(++ 2), B(t +2) E R21, and finally (A(t 3), Bit + 3)) E R3-
Stationary subpartitions: For each of R E R., consider such that (A(t), B()) E R. For any l' 2 t [ 20An and A(t') shows 2-periodic behavior switching between positive and negative signs, that is, for any E Zzo, we have A(t + 21) A(t) and sign(A(t + 20)) sign(A(t)) = -iign(Att (t+++) 2i 1)). To be more specific about each stationary subpartition, have
3
36

---

Published in Transactions on Machine Learning Research (11/2023)
1. For each of R E (Rzz, Rai), consider t such that (A(t),Btt) R. For any t' 2 t, [B(t)) oî and B(t') remains constand, that is, B((") (1))
For each of R E (Rs2, Ras), consider such that (A(t), R.
(a) There cxists t > t such that (A(t), B(t) E Ra1- Denote the smallest t as t².
(b) For any t' > t' 2 t, we have |B(t' + +1] = =B((t)] sign| [i())
(c) For any t' 2 8", [B(()) S कीn and B(t') remains constant, that is, B((") = B())
3. Consider t such that (A(t), B(t)) E R34-
(a) For any t' 2 t, (A(t)), B(()) remains in R34-
(b) There erists i > t such that for any i > t' 2 t, the sign of B(t!) remains constant.
(c) For any t' 2 i, IB((') I oin and B(t') shows 2-periodic behavior switching between positive and negative signs, that is, for any i E Ezo, we have B B(E-20) 21) = B(i and sign( 22)) = sign(B(t)) =- BBt + 2i 26+11 1)).
Proof. From Proposition E.3, we know that from arbitrary (A(0), B(0),, |A| will drop below øßn under the signGD update, which means that (A, B) must enter one of the subpartitions. This allows us to continue analyzing the behavior of (A(t), B(t)) by assuming it enters one of the subpartitions at iteration t.
Analysis of R1E For any (A(I), B()) in Ru1, we know that A(t + 1) A(I) - sigu (A()[
3" S.n. This means
33n that 3 < A( + 1)] <
25 3 so (A(t + 1), B(t + 1)) is in R2 and we can study its dynamics using Rs.
Analysis of R12: For any (A(t), B()) in R12, we know that A(t + 1) A(t) - sign(A(t)]ßßn This means Therefore, (A(t + 1), B(t + 1)) is in R3 and we can analyze its dynamics using R3 18
that [A(t 1) 3
C... This means that |A(t 1) 3" Therefore, (A(t 1), B(t + 1)) is in R3 and we can analyze its dynamics using R3.
Analysis of R21: For any ((t) in R21, we know that A(t+ A(t) sitn[A(tt)
Dynamics of (A, in Ruz and Rus: For any (A(t), B(t) in Re2 and R23, we have A(t + = A(t)
sign[A(t)]oß) and B(t + 1) = B(t), so we know that 0gn
3 < |A(t + 1) <
20hn
3
Analysis of Re2: For any (A(1), B()) in R22, we have A + 1)1 > B(L+ This means that
(A(t+ 1), B(t + 1)) remains in R22, and we have A(t+2) = A(t+ sign ((t++)))) and B(t+2) B(+11), which mcans that (A(t+ 2), B(t 2)) returns to the starting position at (A(t), B(t)) In fact, for any t' f'2 t. A(t') shows 2-periodic behavior switching between positive and negative signs and B(t') remains constant,
that is, for any E Zzo, we have A(t + 2i) A(t), sign(A(t + 21)) = sign (A()) B(t+21 + + 1) = B(t + 2i) = B().
sign(A(t++ + 2i + 1)), and
Analysis of R23: For any (A(t).B()) in Res, by the definition of subpartition, we have that [A(t + 1)1 < BB(t + 1)), so (A(t+ + 1), + 1)) is in Rai. This means that (A(t+ + 2), B(t + 2)) in Rs and we can analyze its dynamics using partition Rz.
Analysis of R3i: For any B(t)) in RaI, we know that A(t + 1) A(t) - sigg(((t)) and
B(t+1) + +) = B().. This means that 2480 < |A(t + 1)1 < o.n. Since [ 1)) > (B 1) = B(t)), we have that 2) = B 1) and A(t + 2) = A(t+1) - [
3
which means that (A(t - 2), B(t + 2)) Therefore, for any t' 2 t, A(t') shows 2-periodic behavior switching between positive and negative signs and B(')) remains constant, that is, for any i E Z2o, we have A(t+2i) A(t), (Atn(A(t+ + 20)) (At)(A(t)) = sign(A(t + 2i + 1)), and B(t+ 2i+ 1) B(t + 21) = B(t).
returns to the starting position at
Dynamics of A in Raz, Rys and Rsa: The behavior of A in Rs2, Ras and Res is the same. For any (A(I), B()) in (Ryz, Rea, Raa), we know that
A(t + 1) = A(t) - sign[A(t) .hn 3
and B(++ = B(t) - sign BBt))onn
(32)
37

---

Published in Transactions on Machine Learning Research (11/2023)
This means that |A(Z + 1)1 < sōn
3. so (A(I+1); B((+1)) remains in R3. For any L' 2 1, A(l") shows 2-periodie behavior switching between positive and negative signs, that is, for any i E Ezo, we have
A(t+22) A(t) and sig 21)) = sign( signn 2 + 1)).
(33)
The behavior of B is different across the three subpartitions, so analyze them separately.
Analysis of R32: Because all subpartitions are non-overigpping, for any (A(t), B(t)) in R32, there exists a unique & E Zeeen - {0} such that A(t) and B() satisfies [A(t)] > [tt) + kōfn)- Next, we show that starting from any (A(t), B()) in R32, after [k] iterations of signGD update, we have [A(t + [k|)] > |B(t+ + [&],, which means that (A(t + [k]). B(t + (a))) is in Rai.
This be proved by showing that |A(t+ + [R|) |A()) and |
B(tt) kō?nl- For any t' t, A(L') shows 2-periodic behavior, and because k is an even number, we have AA(t + |K|I = |A(t)]-
Since [Bt) + noinl > O and B 1) = B(t) - sign| (tt){fi, we know that the sign of B remains the same for the next |k| - updates. This means that
M4-1
B(t + [8] B(t)
Σ
sign(B(t i) (t) ||| sign (Bt))aF
By the definition of the subpartition, we have 0ōn k have opposite signs because & is non-zero even integer. Therefore, we have
B(t) fo and this is true if and only if B(t) and
B + [+]] = B(t) |k| sign(B(t)@
[t)) | (- sign (Al)oōn
= [tt) |A|] sign[k}oinn
= +Bt(t) + kōîn
Analysis of R3s: Similarly, for any (A(t), Bt)) in R33, there exists unique k Zodd such that A(t) and B(t) satisfies [A(t)] + [B(t) + köînj 23
3. Again, we show that starting from any B(t) in Ras, after [k|] iterations of signGD update, (A(t + [k]), Bt + [k()) is in Rai- This can be proved by showing that agn 3 - |A(()) I A( + [K|]| and [(t) + k = BB(t + [+)]
First, by using the same analysis of B(t) + kōînl in R32, we have B(t) + kōîn = [B + [k]]] Next, the behavior of A(t) follows (32), which means that for any t' 2 t, A(t') shows 2-periodic behavior, and because & is an odd number, we have |A(t + [R)) - A()) = |A + 11 A(1) ain
Also, we have |A(t + [k]) A(O S |A + [RD + |A())), which means that 2
B.n 3
S |A(t+ + [+]) + [A(t)), or
|A(t) S |A(t + [k]]]. Combining with the definition of the subpartition, we have
3
B(() + |Bl|| < Jo - IA(0) < |A(L+ + |A(++18))-
3
Therefore, starting from any (A(t), B(t)) in Ra3, after [R|] iterations of signGD updates, we have |A(t + [k]) >
B( + [k]], which together with the fact that |A(t + +K|] < 3
0y as shown before, implics that (A(t- +
k)), ((L+B(+++)) + (k)) is in R31.
Analysis of Rai: Finally, we prove, by contradiction, that for any (A(t), ((t)) in R&i, there is no t' > such that (A(t',, B(t")) in RaI- Suppose that ((t') enters RSI, then & e f' -t must be either an odd number or an even number. By the definition of the subpartition, if k is a non-zero even nunber, it means must be in Rag.
that (A(t), B())) must be in Rsg; whereas & is an odd number, it means that (A(t), Neither possible since all subpartitions are non-overlapping, so for any (A(t), B(t) in Ras, (A(t'), B(t')) remains in R&i for all t' This means that there will always be a non-zero update on B, and this allows to apply Lemma F.2. For any (A(I), B()) in R34, there exists such that [B(('] & ofn for all l' 2 t. 7
38

---

Published in Transactions on Machine Learning Research (11/2023)
Combining Proposition E.1 and the dynamics of (A, B) in the stationary subpartitions described in Propo- sition E.4, we have the following remark.
Remark E.5. The asymptotic solution of A oscillates in 1 26 2 which is tighter bound compared to the one in Proposition E.3. The asymptotic solution of B either remains constant in n.fnn,01) (1 and 2c in Proposition E.4) or oscillates 1-ōîn, o]n) (3c in Proposition E.4). Since A(t) and B(t) denote 3 (tea(t) v and 2 of (1), respectively, this means that lim supt (oo(t) 3 17 and lim supt [t) 22n
2v3
From the dynamics of (A, B) the transient subpartitions described in Proposition E.4, we have the following corollary.
Corollary E.6. Suppose that Eo enters [-v3n, /3n) at iteration t, then starts exhäbiting a 2-periodic oscillation at most 3 iterations after t. This means that the marimum difference between the number of posilive and negolive 's after ileration 2: (sign((())) = 1} (sign[A(()) = -1 S
E.8.2 Dynamics of 82 under signGD
We are now ready to analyze the dynamics of & through the behavior of en and εT Particularly, we demonstrate that. the final value of |ē2] affected by the magnitude [²)( and (ē (0). First, notice that the update direction along é2 follows the opposite of the sign of éo, and every iteration when [A(t)] s [B(t)), there is non-zero weight adaptation for éz. Once the oscillation begins for ēu, the dynamics of ê and ég become similar. Consider T the first iteration when Jēal drops below v3n. We then have
8
VV6 [(A(()) < [(())) 3
-V6
lim sup ((2(1))
62 (T) + 7
Σ
+I{IA(t) (B(D |BB(I sign (E)(())
1=++1
V6
< (()((T) + 3"
sign (en))o(t)
|=++1
2v6
$ (T) +
3 '7,
(34)
where we use Corollary E.6 to upper bound the absolute value of the summation of the sigu of êo after the T-th iteration in the last inequality. This means that after T iterations, é2 stays in an O(ÿ) neighborhood of (T();;; in other words, W2 stays in an O()) neighborhood of T2(T). Also, notice that (34) does not include [[A((t) > [B())} since ég is updated only when [A(t) S [B(t),, as shown in Table 9.
Define Aw2 as the sum of all the updates T2 up to the T-th iteration:
VV6 [[AA()) < (B(I)
3 + I[(A(()) B(O)) -V6 sigu [())
A Awa
(35)
which leads to
sup [t)(()) [T) 0()) = (0) + Au +())
(36)
where (0) is the weight at initialization.
Putting (36) together with Remark E.5, the asymptotic solution found by signGD is
t siguGD
[ Vī, (0) Awoz]] + O()).
(37)
39

---

Published in Transactions on Machine Learning Research (11/2023)
From the perspective of training under the standard risk, the signGD solution is close to the optimum. Specifically, its standard risk is
Rg (w
E [e(X, Y; ]
(x, t TrignGD - -
2
1 (E [x (wiisnGD x6 + E [Xi] (eofienca) -māj)
(38)
2
1
2 (d)0(1)) -3/((²²))
( + oî)n
where E [XxXi] = 0 in (38) due to the diagonality of Σ. Note that the standard risk of the GD solution is exactly zero; and by choosing a small learning rate the standard risk of the signGD solution can be close to zero as well. However, their adversarial risks are very different. Specifically, the adversarial risk of the asymptotic signGD solution
2² w G
2² {wog² + ui² + (#2(0) + Aw))) + 0(1)))
Ra ( (D
(39)
Consider a sufficiently small learning rate: & min (w6, wî, i2 + Aw2). This means that the contribution from O(n²) in Ra (inigDDD) negligible. Then the adversarial risk of the signGD solution becomes
2 = 2 (mo² + ww + (mz(0) + )
R. Ra
(40)
We can compare it with the adversarial risk of the asymptotic solution found by GD under the same setup:
e²
R10 GD
{wb + u² + m2(())
(41)
2
The main difference between the two adversarial risks in (40) and (41) is the difference in weights learned at the irrelevant frequency. Since their use irrelevant frequency in the data is under-constrained, neither algorithm can reduce W2 to zero, thereby neither solution the most robust standard risk minimizer. The GD solution is sensitive to weight initialization. To understand the Ado term in the signGD solution, first recall that T denotes the first iteration when (&ol drops below v3n (or |A| drops below oin), and from Corollary E.6 we know that Wh starts oscillation at most 3 iterations after T. Recall in (36) that O(1) has been utilized to account for the maximum sign variations, this means that we can consider oscillations which begin immediately after the T-th update. Suppose that is small so the sign of éo would not change before the oscillation starts, then we have
V6
+ +I[|A00) = [B())} -V6
Am72l
6 } sign [o)
3
-V6
-V6
H[A(() < (B(II) +1[]-(0)= (B())) |B(I)
6
which Icads to
| On Σ H(A(t) < [B()))
(42)
where C denotes some value between larger updates, respectively.
VB V6 and N/b which correspond to always using the smaller and the 6
40

---

Published in Transactions on Machine Learning Research (11/2023)
E.8.3 Dynamics of | under signGD
There are two factors that affect the magnitude of Σi= [[A((t) S [(t)) in (42): 1) the relative magnitudes between ob and of, and 2) the initial values of [Go| and [ or equivalently, the initial values of |A] and [B]. To analyze this, we divide the set of values of (IA(t),, |B())) into several partitions: the set of [0, nin x R and R x (in] is partitioned into P1 and P2. and the set [089. oo) x [o6n, oo) is partitioned differently based on the value of of. Consider line that travels through the point of (0ōn. Øôn)
and has slope of 3 3 understanding the position of (IA(0)), |B())) relative to such line can lead to the value of [B(T 1)], that
The ratio between o and of is particularly useful in analyzing | because
is, the value of |B| before the oscillation of |A| begins. Since [B] is updated only when |A| - [B, we have E T (IA(O)) [B(()) [B(0] 1001-1110 -1((--))
The definitions of partitions are
6/9
= = (A, B): |A| < }.
P2 P= B): >|A>> ,दn and [B] < oß4 }
When
88
3'
1
P3 { (A, Ji < |A| <
( + (35) oz))) }
P31 = (A, : (4, E P3 and ||| + .8. > B
P4 = (==((A,B) ..0 < <B] <
35
A
(35) - )ž) )
P4i = (A, : (A, E P4 and
B < | < 2561 }.
P12
(A, (A, Pa and A > B and 25 < |A|
B + (307 18)n
+ o6
3
When 3
86
Ps { (A, oinn< < |A| < [B]] Po { (A, oin < [B| < [
An illustration of partitions is provided in Figure 7, where the two plots demonstrate the two different ways The connection between the values of
of dividing the set of [ōön, oo) [ōōn, oo) based on the value of of (B())) and the size of Σ [[(A(()) (B(I) is summarized in the next proposition.
ag.
Proposition E.7. Denole T as the ileration when 1/ol drops below v3n- The value of ETD 1 [[A(t)) S [B(t))} depends on the relative magnitude between oß and oū, and the initial values of A and [B. Specifically, we have
B(O))) E (P))P) if ((((O))
T
if
[B(O)) E Pa and [[A(O)],IB(()))
I(A(()) $ [B(t))-
[B(O)]
28
if
TO and
(IA(0),, e P4 and
T
if
(IA(0),, E P. 26 and (IA(0),,1(())) e Pa.
[B
if
Proof.
We divide the analysis into two main parts: when > 1/2 and
#2 < 3. corresponding to the left and right 25
figures in Figure 7. For each case, analyze the behavior of (A, B) within the partition.
41

---

Published in Transactions on Machine Learning Research (11/2023)
5450
5R/1
1850
16/1
Pz
3050
365
[010)]
[010]
2050
Pa:
2861
P4z
85p
6/4
05n
205p
308n
408n
5din
8in
28in 305g
40%g
5050
[4121]
[ACC]]
Figure 7: Analyzing the value of Σt [IA))) [(OI) in (42) by partitioning the set of values of (IA(t),, (B()), and the relative magnitude between oe and of determines the partitions on Specifically, the analysis based on partitions Pt, Ps, P3. and Pa. when /े > 3 (left), and on PI, P2, Po and Po, when of <
which the analysis is based.
dg 3 (right). The three smaller subpartitions are subsets of the main partition, i.c., P31 C P3 and PaI. P42 C Pl, and they are used in the analysis of Pa- The value of Ei= [[A(()) S [B({] when (IA(O)), , IB())) is initialized in each partition is summarized in Proposition E.7. The two plots created with of of (left) and oō 9 (right), respectively. Note that those values are chosen for illustration purposes and do not affect the generality of the result. In both plots, z
o
the red dashed line corresponds to [B()) = 3 [A(t) - (33?- - on)n for |A(t)) E (dîn, oo), and the yellow dashed line corresponds [B([)] = |A()). The pink dashed line is parallel to the red dashed line with a horizontal gap of ößn.
Analysis of Pi: For any (IA(0)) (B())) ( in P1, since |A(0) is already below oßn, we have T = 1 because A remains in Pl. This means that 20 [[A(()) < [B(O]) = O.
Analysis of P2: For any (IA(0)), (B(())) in Pg, |A| deccrases until it drops below ogn, while [B] remains the same. This means that |A| remains smaller than [B], so we have [(]A(t)] < [B())]} = 0 for all t e T
[O,...,T--1 13. Therefore, we have E I (IA(0) S [B(())) = 0.
Next, the partitions of the set of (08n, oo) x 16,n, xo) are defined differently based on the values of compared ag 1. it is possible for any (IA(t), satisfying |A(t)) < [B(t).. there exists t' such that [A(t') [B(('). In other words, ([A),IB) can oscillate above and below the line defined by |A| [B], and this makes analyzing (42) difficult. However, when of
1 This is because when > 0.
to 3-
3.
}, any (IA(t)), [B(t))) that satisfies IA(() < [B()) will stay above the line defined by |A| = [B], and this means that |A] will always . get updated by 3 and [B] will always get updated by oî... Because of this different behavior, we analyze these two cases separately by defining different partitions. This corresponds to the left and right figures in > 3. the set of [aān, oo] x Iaōn oo] is partitioned into P3 and Pa.
Figure 7. When ai o6
Analysis of P3: By definition, any (IA(O)) [B()) in P3 satisfies 3 |A())) < (B(t) + (357 - ag)n. Starting from any (IA(O)), B(O))) in Ps, the values of |A| and [B] decrease at a rate of ] Jaßn and oîn, respectively, and this means that two sides of the inequality decrease at the same rate, Hence, the sequence (IA(t),, remains in P3 for all 0- < t < T 1. This means that [[A(()) < [(t)]] 1 for all t E fo...., T...,TT-. 1}. Therefore, we have I I (IA(t)) < [B())]] T.
Analysis of Pa: Since [IA(T-11) 1 of I < [B(I)] by considcring how any (B(())))B()))) in Pa is transitioned to (IA(T - 1)) [T - 1))) in Pt. Also, starting from any (A(tt),,((tt) in Pl, we know that [A(t)] IA(L+ + 1)] > 0 and [B(L) IB(L+ 1)] 2 0; hence, the transition from P. to Pt must. be described in
must. be in Ptş we can understand the value
42

---

Published in Transactions on Machine Learning Research (11/2023)
one of the following scenarios.
Transition to P2 then to Pi: In this case, the value of [B] must first drop below oßn. Since |B] decreases only when | - [B), this mcans that, regardless of the initial value of |A|, the same number of updates is
required to reduce [B()) to 08n, which is [B(0)-88n and in each update, the condition T [(A((t) - [B(I)) is satisfied.
8f
Transition to P1 directly: For any (IA(t)), (B())) in PA that satisfies [B()) > |A(t) (above the yellow dashed line in Figure 7), since the values of |4| and [B] decrease at a rate of 1
3 j06n and ofn, respectivcly,
(IA(t+ + |B(t + 1)1) cannot cross the red dashed line which has slope of 37 Now let us consider any (IA()),)1(()) in Pa that satisfies [B(t)] < [A(t) (below the yellow dashed line). In this case, |A] decreases
by o.n and the only scenario where ([A(T - -1)1, - 1))] ends up in Pi is when σîn < |A(TT - 2) < 20īn. That is, (IA(T-
2)]) is in P42. When this happens, we have oin < [BT 2) < 2:
and because there is no update in |B(T - -2),, we have oßn < |B - 1)I 228n. Therefore, we have E [(AA()) - [B())) E [BBU
[(00)-00") 0in
oin
Transition to Ps then to P1: Let us first consider the transition from P1 to P3. Consider l' such that (IA(O), , (B())) 1) is in P4 for 5 t' and ( is in P3. Following the above analysis (direct transition to Pi), we know that (IA(t' - 1 [B( - 1)1) must satisfy |A(t' - 1)] > |B(t' - 1)}, where t' - is the iteration before transitioning to P3. Also, we know that |A(t' IA(t'-1) > 20 otherwise ((A(t"), (((t)) would be in P1. The last condition for such a transition to happen is that the horizontal distance from B(t - 1 to the line of |B] 3 |A|- (307- - ob)n (the red dashed line) must be smaller than 857. That is, (IA(t' - 1)1, BB(L' - 1)1) is in P41, and (IA(t)),IB(())) is in Pai. After the transition to P3, the values of |A| and [B] decrease at a rate of 3007 and 8f respectively, and [B(T- 1)] has a range of [ōon, 26o7]. Therefore, we have EiD T (IA(1) < [B(O)) E - [B(O) -037
fjn
. 3: the set of [o do] x 1o oo] is partitioned into Ps and Po, as shown in the right figure of When < I
Figure 7.
Analysis of Ps: Starting from any (A(O)).B(())) in Ps, the values of |A| and [B] decrease at a rate 8² 1
of 3 joōn and afn, respectively. However, since
85 3 there will not be any S t t T - where <
LA(t) [B))]. This means that I I[(A(t) S [B(t)]} = for all t E {o,.... T 13. Therefore, have ETD [[A((t)] S [B(t)) T.
Analysis of Po: Starting from any (IA(O)), in Pe, the values of |A] decreases until it becomes smaller than [B(O)). Suppose that this happens at iteration t', that is, [A(t') < [B(0)). Starting from (IA(()), (B)))) (A(E)) in Po. |A| starts to decrease by ze mcans that (LA(t)), (B(())) stays in Ps for E {t'.... - 2}, until it gocs to P1 when |A(T 1)]
3 and [B] starts to decrease by oîn. Since 3
< 3 this
< 587.
Therefore, we know that the total change in |A] since 1'thh iteration is IA((') - .bn = [B(0)] - .bn. Since
|A| can only be updated by the amount of Zh in Ps, we have Et- [[A([) < (B(())) [8(0))5501
3
$0.0
We now use this analysis on the behavior of ΣT- ([A(t)) & [B(t)} to compute |Awzl, which plays a role in the adversarial risk of signGD, as shown in (40). For the initial values of (IA), [B]) to be in Pı and P2: the initial errors must be small. However, consider a datasct with a strong task-rclevant 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, |ağl| and |uوي can be large. Additionally, with weight initialization around zero, such as in methods by He et al. (2015) and Glorot & Bengio (2010), the initial error (oo(0)] and [², (0)l can be large (0)). Because of this, it is less likely for the initial values of [A()) and [B()) to be in the P1 partition in Proposition E.7.
and close to | and | when |لقي|| > [0)] and |قق|| > |ū,((),
Morcover, it is discussod in Sec. 3.1 and later supported empirically Figure 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 of is interpreted the expected energy of random variable at
43

---

Published in Transactions on Machine Learning Research (11/2023)
the i-th frequency, it reasonable to expect that initialization of (IA),1B) in Ps and Po-
of < 1 and this allows us further narrow down 88 3
The proportional relationship between the size of (42) and the magnitude of lēul and [ēi when ag and [B)) is initialized in Ps or Po can described in the following proposition.
Proposition E.8. Suppose that the ratio between og and of satisfies a
< 1.4 The magnitude of | depends on the initial values of leol and [ēil, and the resulting A(O) and [(O)]. Specifically, we have
V3C (2)( if 3v251 250
|A(O)) [(()] if IA(O)) [B(0),
Awp
(43)
Cle
where C VB /6 and neglect the contribution from n7-
Proof. From Proposition E.7, under the assumption that
0g
<
3
1
we have Σt= I {(A(()) [(())} = T
when [[A()),]B(O)) E Ps. and this means that A Cifl' from (42). This also implies that for {O....,T 1)
1}, we have [A(t)] < B(t) and |A(t)) [A(O)) } o
Since T is defined as the number of iteration required to reduce
|A(0) .zn. T [A(O] and we have 3000
|A(0) -581
-3 -3 (o( - oîn
A
CnT On
=0
3
C(v3 - 3n).
3
From Proposition E.7, when and (IA(0)), is in Ps, we have
[B)) म6
v2 x207 |
3v223 [0) 3n).
A A = C
30
1081
200
Since the initial error [ēn(0)] and |ē (0) are close to | and |ojll (43) can be writlen as
V3C
|A(O)] < [B(O) if |A(O)) [B(O)
A 2
3v 20
C
|wil|
(44)
Now we can consider the ratio between the adversarial risk of the standard risk minimizers found by GD (41) and signGD (40) with three-dimensional input space. We observe that the solution found by signGD is more sensitive to perturbations compared to the GD solution:
R₂ Rug R₂ (WGD)
w6 + 2 + (w (0) + 2222²
Ang u + 6r
11+
wg + wt² + (0
where we neglect the contribution from 2 (0) in the approximation since have assumed that the values of [āg| and | are large compared to the initialized weight (0))) This leads to
R₂( ( R₂ Ra (D)
C. if [A(O)] < [B(O] if [A(0)) > [B(0].
1 C1 0
C4 < g4 where }/2 5 Cg 2 and 3
44

---

Published in Transactions on Machine Learning Research (11/2023)
E.9 From Irrelevant Frequencies to Spatially Redundant Dimensions
We have demonstrated that when the use of irrelevant frequency is under-constrainee, optimizing the stan- dard training objective can lead to solutions with zero standard risk but are sensitive to perturbations. This section offers a spatial interpretation of the findings, where we illustrate that signals with irrelevant frequen- cies contain spatially redundant dimensions when transformed into the spatial domain. Both interpretations can be used to explain the vulnerability of the solutions.
To illustrate the concept of redundancy in the spatial domain, consider the synthetic dataset with the distribution defined in Sec. 4.2.2 and the data has structure of {(Xo, X1, 0)} in the frequency domain. Taking the DCT transformation of X, we see that the spatial representation of the same datasct is
{w/=0 + Va V
V3 xxx0 - ---V V2xi
where No and X1 are random variables with frequency interpretations. In the spatial domain, redundancy refers to the existence of dimensions that are highly correlated with each other. The example mentioned above illustrates that the presence of a single irrelevant frequency in the data distribution corresponds to the existence of one redundant dimension in the spatial domain. Specifically, within this three-dimensional dataset, it is possible to express any dimension as a linear combination of the values at the other two dimensions.
This translation between spectral irrelevance and spatial redundancy can also be observed in the learned weight. Consider standard risk minimizer w' = (m6 W7, 0), whose frequency-domain representation is
1 w² = 5 w + 2 w 0 13uh V wi)
3
Because of the irrelevance from u2 there are multiple other standard risk minimizers. In the spatial domain, this means w" + Wylli with W7 = (v Vs 3: Vov and any choice of Wi E R is still valid standard risk minimizer.5 5 When the model trained by signGD has large weight at W2, this implies large W2 for the weight in the spatial domain. Because Wy and w' are orthogonal, we have ||w" + 020bl11 = ||w/|l2 2/2 + /wp). therefore, the weight norm increases as W2 gets large, and from (12), models are more vulnerable.
Ii is important realize that having irrelevant frequencies merely sufficient condition for having spatially redundant features, but is not a necessary condition. For example, rearranging the dimensions of x and w" in the above example still preserves the spatial redundancy in the dataset, and there are still infinitely many standard risk minimizers. However, it no longer guarantees zero entries in ş and n*.
F Future Direction: Studying Model Robustness under Different Optimization Objectives
The Sharpness- Aware Minimization (SAM) objective, proposed by Foret et al. (2021), has demonstrated improvements in model robustness both in settings with noisy training labels and against adversarial per- turbations (Wei et al., 2023).
Understanding the dynamics of the sharpness-awaee loss, especially under different optimization algorithms, can be more involved. Without doing so, notice that the SAM objective in Foret et al. (2021) includes an & regularization term on the weight norm. That is, training with the SAM objective penalizes models for having large weight norms. This is in line with our findings presented in Sec. 4, where we demonstrate that minimum norm standard risk minimizer achieves the most robust standard risk minimizer.
Recent work by Wei et al. (2023) focused on linear models with classification and demonstrated that mini- mizing (SAM alone can lead to ad adversarially robust models. They designed synthetic dataset based on the
The (TT -5.--aa L/ vector the DCT basis for the di term, Le.. CT,0,0, m2) = .2 -V..V.V
45

---

Published in Transactions on Machine Learning Research (11/2023)
hypothesis of the robust and non-robust features (Ilyas et al., 2019), and theoretically demonstrated on the linear classification that minimizing the sharpness-aware loss alone can result in models with larger weight on the robust features.
An important distinction to highlight between our analysis and that of Wei et al. (2023) is that, while both work theoretically analyze the adversarial robustness of linear models, our work focuses on models obtained via different optimization algorithms, while Wei al. (2023) focuses on models under different optimization objectives. In our setting, under the same optimization objective, there exist multiple optimal solutions where their standard risks are identical, but their adversarial risks are different. On the other hand, in the setting of Wei et al. (2023), cach objective has its own optimal solution. These solutions differ not just in adversarial robustness but also in their standard generalization performance. The two directions optimization objectives and algorithms- are orthogonal, and the choice of an objective independent of the choice optimization algorithm. Understanding how models, trained under robustification objectives, behave when paired with various optimization algorithms is a promising avenue for future dircctions.
G Additional figures
In Figure 8, we visualize the energy distribution of various datasets containing natural images. Each dataset contains four plots. The (i,j) coordinate the first plot represents & 2 [mm( where N is the number of training images, on is the DCT transformation of Fn, and kn((s,) denotes the amplitude of the (i,j)-th basis in the n-th sample. In the second plot, visualize the diagonal values from the first plot:
{ I i=:....d-1 We observe across all datasets that there is high concentration of energy in the www-frquency harmonics and the amplitude of the higher-frequent frequency harmonics becomes almost negligible, Therefore, we repeat the first two plots in the natural log scale (log.). The (i, coordinate in the third plot represents
E log (+ In the fourth plot, we visualize { { Σ log [ i=
46

---

Published in Transactions on Machine Learning Research (11/2023)
Sowetral an datrbbuiin
Log scale spectral energy
Log scolo RoS mouatooao
20
38
20
23 Froquency
16
25
Frequeno
a. MNIST
neectrll energy dist fbutinn
Log scale spectral energy distrbbutio on
traniig
Lo0 scole mospitutt 500c000
38
20
39 15
10 35
Frequency
6.0 Frequency
FashionMNIST
Spectral enery dist tbution
Log spectral eneryy distbbat on
averages
16
30
16
20
25
36
29
38
36
25
Frequency
Frequency
CIFAR10
Snectrol energy dis rbution
Log spectral enery distnbat
Soreeea 100 0000 6m
10
16
20
16
15
25
22
15
25
0116t Frequency Bass
0.04h OCT frequancy
CIFAR100
Seectral enery reution weraped
Log spectrll eneryy disinbul
10
Maggitute
16
20
16
15
25
26
20
28
16
25
(11).
Froquency Bask
6.0.h DCT frequancy
e. SVHN
Seeztroi enengy dictributonn
Log scale spectral energy ditribution
Log SC0 moggn Bubl:
100
100
100
191
201
/10
0.044h Frequency Bants
1.04h DCT Trequency Sark
F. Caltech101
Spectral energy disinbution oveeaged training
Log scale spectral energy distibutton on
avergee
nouts
Log 220l masi POUCCC
50
Megn
2M
100
159
200
244
100
0.0 OCT Frequoncy Bosts
0.9 DCT Froquency Bod
g. Imagenette
Figure 8: Illsstatioon of the spectral energy distribution in natural data. Distribution of the spectral energy heavily concentrates at low frequencies and decays exponentially towards higher frequencies.
47

---

Published in Transactions on Machine Learning Research (11/2023)
lodji]
8
Original Image.
0uglx;
OuglX 70)
8
8
8
8
8
(xy
Pxylk
9xy/x, 901
0.0100
0.04
0.200
0.0075
0.03
0.075
03
0,050
0.10
0.05
0.1
MeglR 100
May 3.)
Magl2, 50)
Magl2, 70)
Mig 90)
1.0
1.0
1.0
0.6
0.6
0.6
0.6
0.6
0.4
0.4
0.4
04
04
0.0
0.0
0.0
0.0
0.0
OkngOk 10)
OnngOr, 30)
0xcoX 50)
Oscox, 70)
Osefx, 90)
8
8
8
8
8
OxefX 10)
X Oxvlx, 30)
Ix 4x 50J
Jx- 0w,,X 201| 10
|x 4 (r. 901| 10
03
0.6
0.075
0.10
0.15
04
0.050
0.30
02
0.025
Moag110)
May(G0)
Mcwg550
Moee990)
1.0
1.0
1.0
10
1.0
0.8
0.8
0.8
08
0.4
0.4
0.4
0.4
0.4
0.2
0.2
0.2
02
02
b. Modified Image.
Figure 9: Examples of modified images used in Obscrvation (MNIST) We use a threshold value of threshold {10, 30, 50, 70, 90} to modify images based on its magnitude of DCT basis and their freqequency basis. In a), we show the original image z and the magnitude of its DCT basis |o| in both linear and log scale. In b), we show images modified by removing DCT basis vectors whose magnitudes are in the bottom threshold percentage (row 1), the differences between the modified images and the original image (row 2), the binary mask used lo remove the DCT basis: black means removed (row 3), images modified by removing high-frequency DCT basis vectors (row 4), the differences between the modified images and the original image (row 5) and the binary mask used to remove the DCT basis: black means removed (row 6). Notice that the masks in row only depends on the dimension of the images, whereas the masks in row 3 differs from images to images.
48

---

Published in Transactions on Machine Learning Research (11/2023)
[4]
logl A]
7.
5.0
Original Image.
GwvgK, 10)
Owylk, 30)
Svelk, 50)
Ruoli, 70)
Oug 90)
Jx 0eglx.11 10] 10
X
0x 30) 10
X- 0k 50) 10
Ix 0uppi 701] x 10
[x 4wy/X, 901 900
0.006
0.003
0.10
0.3
0.02
02
0.003
0.
Mny(R,30)
90)
1.0
1.0
1.0
100
1.0
0.8
0.8
0.8
0.8
0.8
0.4
0.4
0.4
0.2
0.2
0.2
0.2
02
0xngX::10 100
0rug 30)
@rug 50)
Osegit 70)
Orogls 90)
4ca 501
Ox, 70]]
Ok,
0.15
0.4
0.04
0.2
0.3
0.10
0.02
02
0.01
Moel 110)
Min(330)
Myey550)
Movy(70)
Moea190)
0.8
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
06
0.0
6.0
0.0
0.0
0.0
Modified Image.
Figure 10: Examples of modified images used in Observation I. (FashionMNIST) We thresh- old value of threshold = {10, 30, 50, 70, 90} to modify images based on its magnitude of DCT basis and their freqequency basis. In a), we show the original image and the magnitude of its DCT basis | in both linear and log scale. In b), we show images modified by removing DCT basis vectors whose magnitudes are in the bottom threshold percentage (row 1), the differences between the modified images and the original image (row 2), the binary mask used to remove the DCT basis: black means removed (row 3), images mod- ified by removing high-frequency DCT basis vectors (row 4), the differences between the modified images and the original image (row 5) and the binary mask used to remove the DCT basis: black means removed (row 6). Notice that the masks row only depends on the dimension of the images, whercas the masks
row 3 differs from images to images.
49

---

Published in Transactions on Machine Learning Research (11/2023)
logjF]
Original Image.
Suplx
6x 10)
0k, 50] 10
[x - Rkylk, 50] 10
0ggl 703 x 10
9uglx 901| x100
0.03
0.6
0.8
0.4
088
0.01
0.2
0.025
02
MuglR, 10)
MuddR, 30)
Magf 50)
Mae 70)
Min 901
0.6
0.6
0.6
0.6
0.6
0.4
04
0.0
0.0
0.0
0.0
0.0
10)
OcedX, 30)
@zvlx, 50)
Oseox, 70)
@xcybx 901
x 0oegUx 10) 10
x 0r 30) 10
[x Ox 50)
x Orueft, 70)
Ix 0rug 90)
0.8
0.04
0.15
04
0.6
066
0.10
0.02
02
0.2
02
Mone(10)
M3,(30)
50)
Meng(70
Mce/900
1.0
1.0
1.0
1.0
0.6
0.6
0.6
0.6
0.4
0.4
04
0.4
04
b. Modified Image.
Figure 11: Examples of modified images used in Observation I. (CIFAR10) We use a threshold value of threshold {10, 30, 50, 70, 90} modify images based on its magnitude of DCT basis and their freqequency basis. In a), we show the original image and the magnitude of its DCT basis |o] in both linear and log scale. In b), we show images modified by removing DCT basis vectors whose magnitudes are in the bottom threshold percentage (row 1), the differences between the modified images and the original image (row 2), the binary mask used to remove the DCT basis: black means removed (row 3), images modified by removing high-frequency DCT basis vectors (row 4), the differences between the modified images and the original image (row 5) and the binary mask used to remove the DCT basis: black means removed (row 6). Notice that the masks in row only depends the dimension of the images, whereas the masks in row 3 differs from images to images.
50

---

Published in Transactions on Machine Learning Research (11/2023)
7.
30
25
Original Image.
Swyle, 10)
Gugg 30)
Ouyyx, 50)
Dualx, 70)
Quplx 90)
4xygX 1.)
0c,00.300 30]]
Oxglx 700
4ugfx. 201|
1.0
1.0
0.00
0.2
0.04
0.6
0.6
0.02
02
0.4
04
MRg 10)
MaglE. 30)
Megle 50)
Magbi 70)
May (R. 901
1.0
1.
0.8
0.8
0.8
0.8
088
0.4
0.2
0.2
02
0.
02
Oveg Cx. 10)
O 30)
Ozuplx 50)
Osudit 70)
@ruglt, 90)
Or, 90)
1.0
1.0
1.0
0.2
0.4
0.4
0.4
04
0.1
0.2
(10)
May(30) (36)
Maug 55)
Mex
Mcsg900)
0.8
0.8
0.8
0.8
0.8
0.6
0.2
0.2
0.2
0.2
02
b. Modified Image.
Figure 12: Examples of modified images used in Obscrvation I. (CIFAR100) We use a threshold value of threshold = (10, 30,50 50, 70, 90} to modify images based on its magnitude of DCT basis and their freqequency basis. In a), we show the original image and the magnitude of its DCT basis (ă| in both linear and log scale. b), we show images modified by removing DCT basis vectors whose magnitudes are in the bottom threshold percentage (row 1), the differences between the modified images and the original image (row 2), the binary mask used to remove the DCT basis: black means removed (row 3), images modified by removing high-frequency DCT basis vectors (row 4), the differences between the modified images and the original image (row 5) and the binary mask used to remove the DCT basis: black means removed (row 6). Notice that the masks in row only depends on the dimension of the images, whereas the masks row 3 differs from images to images.
51

---

Published in Transactions on Machine Learning Research (11/2023)
logji]
5
Original Image.
ftg 30)
OugiX, 70)
Oug (.
5
5
I
15
5
5
10]
10]|
0x.
4xyli,
9uy/x
0.015
0.100
0.04
0.010
0.6
0.050
0.005
02
Meg 10)
May12,30) 30)
Ma 50)
Magl2, 70)
Mig 90)
1.0
1.0
0.8
0.6
0.6
0.6
0.6
0.6
0.4
0.4
0.4
04
04
0.0
0.0
0.0
0.0
0.0
Ok,,O, 10)
OrngOr 30)
OxcuXt 50)
Oscobt, 70)
Ozefl,, 90)
5
5
5
5
5
9sefX 10)
X 9xvoX, 30)
I
4xe S0J
Ix (c 201|
[x 4 (r. 901)
0.02
0.075
0.
0.050
0.1
6.025
0.000
Moag110
M3n(30)
Mong550)
Move/70)
Moea990)
1.0
1.0
1.0
10
1.0
0.8
0.8
0.8
08
0.4
0.4
0.4
0.4
0.4
0.2
0.2
0.2
02
02
b. Modified Image.
Figure 13: Examples of modified images used in Observation I. (SVHN) We use a threshold value of threshold {10, 30,50, 70, 90} to modify images based on its magnitude of DCT basis and their freqequency basis. In a), we show the original image and the magnitude of its DCT basis |o| in both linear and log scale. In b), we show images modified by removing DCT basis vectors whose magnitudes are in the bottom threshold percentage (row 1), the differences between the modified images and the original image (row 2), the binary mask used lo remove the DCT basis: black means removed (row 3), images modified by removing high-frequency DCT basis vectors (row 4), the differences between the modified images and the original image (row 5) and the binary mask used to remove the DCT basis: black means removed (row 6). Notice that the masks in row only depends on the dimension of the images, whereas the masks in row 3 differs from images to images.
52

---

Published in Transactions on Machine Learning Research (11/2023)
[4]
Ingie
100
20
-1000
Original Image.
Suege 10)
SwygK, 30)
Rxylx, 50)
Oupli, 70)
Oug 90]
Jx 0eglx, 10] 10
Xx- 0r, 30) 10
00r 50) 10
Ix
0tgpl 701 10
[x 4wyfk 90]
c.ca
0.010
6.08
0.6
0.005
0.10
04
0.02
0.05
0.000
0.00
0.00
0.0
May|R,30)
Mup
1.0
1.0
1.0
1.0
1.0
0.8
0.8
0.8
0.8
0.8
0.4
0.4
0.4
0.4
0.2
0.2
0.2
02
02
9mgg (0)) 10)
0r 30)
0rug 50)
Osedit 70)
Orggis 90)
Ovedk,
4x 701|
Ok
0.4
1.0
1.0
0.04
0.3
6.15
0.2
0.4
04
0.05
0.2
02
Maal 110)
Mne(330)
Myey(50)
Moey(70)
Moeg190)
0.8
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
06
0.0
0.0
0.0
0.0
0.0
Modified Image.
Figure 14: Examples of modified images used in Observation I. (Caltech101) We threshold value threshold = (10, 30, 50, 70, 90} to modily images based on its magnitude of DCT basis and their fregequency basis. In a), we show the original image and the magnitude of its DCT basis | in both linear and log scale. In b), we show images modified by removing DCT basis vectors whose magnitudes are in the bottom threshold percentage (row 1), the differences between the modified images and the original image (row 2), the binary mask used to remove the DCT basis: black means removed (row 3), images modified by removing high-frequence DCT basis vectors (row 4), the differences between the modified images and the original image (row 5) and the binary mask used to remove the DCT basis: black means removed (row 6). Notice that the masks in row only depends on the dimension of the images, whereas the masks row 3 differs from images to images.
53

---

Published in Transactions on Machine Learning Research (11/2023)
logj4)
100
0.0
60
2.5
20
Original Image.
Gugglt 10)
Oxggx, 30)
Suglx, 50)
Puglx, 70)
Oug(K, 9G)
Jx - 0sgly,
10] [0]]
10
- 0r, 30) x00
- 0tr 50) 10
- 0upli 701| 10
- 4uyfit 901| x
0.015
0.3
0.4
0.6
0.010
04
0.1
02
0.000
0.00
0.0
May|R,30)
Muy12,
70)
90)
1.0
1.0
1.0
100
1.0
0.8
0.8
0.8
0.8
0.8
0.4
0.4
0.4
0.4
0.2
6.2
0.2
02
02
9rgg 10)
0rug 30)
Oruplt 50)
Oseekt 70)
Orugls 90)
Ox 701|
Okey
6.4
1.0
1.0
088
0.8
0.3
0.05
6.2
0.4
0.
02
02
Moel 110)
Min(330)
Myey(50)
Moey(70)
Moeg190)
0.8
0.8
0.8
0.8
0.8
0.6
0.6
0.6
066
066
0.0
6.0
0.0
0.0
0.0
Modified Image.
Figure 15: Examples of modified images used in Observation I. (Imagenette) We use threshold value threshold = (10, 30, 50, 70, 90} to modily images based on its magnitude of DCT basis and their froqequency basis. In a), we show the original image and the magnitude of its DCT basis |é] in both linear and log scale. In b), we show images modified by removing DCT basis vectors whose magnitudes are in the bottom threshold percentage (row 1), the differences between the modified images and the original image (row 2), the binary mask used to remove the DCT basis: black means removed (row 3), images modified by removing high-frequue frequenyy DCT basis vectors (row 4), the differences between the modified images and the original image (row 5) and the binary mask used to remove the DCT basis: black means removed (row 6). Notice that the masks in row only depends on the dimension of the images, whereas the masks row 3 differs from images to images.
54

---

Published in Transactions on Machine Learning Research (11/2023)
FashionMNI5T: Freq contribution to acc change
CIAR10: Freq contribution to acc change
bardd-ieitte penturtations 150
20.0
560
Accuracy perturbatin Iotorrattooo (%)
Accuncy under
17.5
Acam
Ace
15.0
22.5
20.0
Perturbed frequency band
Perturbed frequency band
SVHN: Freq contribution to acc change
Caltech101: Freq contribution to acc change
Arcuracy benc perturbatioee (16)
160
bonn: leniiemete perturtett bostions (96)
500
Adam
52
Accurscy
Perturbed frequency
Perturbed frequency band
Figure 16: The effect of band-limited Gaussian perturbations the model (additional figures). Perturbations from the lowest band, i.e., (x have similar effect 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.
MNIST
FashionMNIST
CIFAR10
CIFAR100
3
SVHN
Caltech101
Imagenette
Figure 17: Images perturbed by additive Gaussian white noise with different variance. For each dataset, we select the largest variance value from Table 3.
55

---

Published in Transactions on Machine Learning Research (11/2023)
Perturbed inputs based on SGD-trained model
Perturbed inputs based on Adam-trained model
Perturbed inputs based on RMSProp-trained model
Perturbed inputs based on SGD-trained model
Perturbed inputs based en Adam-trained model
Perturbed inputs based on iMMPPrp-traiined model
9
4
9
Le
Lee
Let
MNIST
PashionMNIST
Perturbed inputs based on SGD-trained model
Perturbed Inputs sased Adam-tra Ined model
Perturbed inputs based RMSProp-trained model
Perturbed Inputs based on SGD-trained model
Perturbed Inputs based en Adam-trained model
Perturbed Inputs based PMMsaro-traalned model
CIFAR10
CIFAR100
Perturbed inputs SGD-trained model
Perturbed Perturbed inputs based Adam-tralned model
Perturbed
Perturbed Perturbed
RMSPrap model
SGD-trained model
Adtam-trained model
PntsProp-trainee madel
5
5
10
500000004
SVHN
Caltech 1 01
Perturbed Inputs based SCD-tra ind model
Perturbed Inputs based on Adam-trainee model
Perturbed Inputs based on RMSProp-trained model
Imagenette
Figure 18: Images perturbed by f--norm bounded adversarial perturbation (Croce & Hein, 2020). We select the largest value from Table to generate Eg bounded perturbations for images in each dataset. We also compare perturbations generated using models trained by different algorithms.
56

---

Published in Transactions on Machine Learning Research (11/2023)
Perturbed inputs based on SGD-trained model
Perturbed inputs based on Adam-trained model
Perturbed inputs based on RMSProp-trained model
Perturbed inputs based on SGD-trained model
Perturbed inputs based on Adam-trained model
Perturbed inputs based on iMMPPro-tralined model
2
Lee
Lee
Let
MNIST
PashionMNIST
Perturbed inputs based on SGD-trained model
Perturbed Inputs sased Adam-tra Ined model
Perturbed inputs based RMSProp-trained model
Perturbed Inputs based on SGD-trained model
Perturbed Inputs based en Adam-trained model
Perturbed Inputs based PMMaaoo-traalned model
CIFAR10
CIFAR100
Perturbed inputs SGD-trained model
Perturbed Perturbed inputs based Adam-trained model RMSPrap model
Perturbed
Perturbed PMtSProp-trainee madel
SGD-trained model
Adtam-trained model
5
2
2
SVHN
Caltech M0lech1100 101
Perturbed Inputs based SCD-tra indd model
Perturbed Inputs based on Adam-trainee model
Perturbed Inputs based on RMSProp-trained model
Imagenette
Figure 19: Images perturbed by -nom bounded adversarial perturbation (Croce & Hein, 2020). We select the largest value from Table 3 to generate toc bounded perturbations for images in each dataset. We also compare perturbations generated using models trained by different algorithms.
57


Reviews:
[{"review_id": "a2xyVByZuU", "reviewer": "Reviewer_x5rV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written and well-motivated.\n- Studying the performance of various optimization methods is important.\n- The proposed existence of irrelevant frequencies is promising.\n\nWeaknesses\n- It is not clear if the results of this paper generalize to various neural network architectures, i.e., only convolutional neural networks (CNNs) have been studied. What about the performance on ViTs or even Diffusion models?\n- I am highly curious if a similar effect/observation can be observed for data with other modalities, e.g., language, audio, and graphs.\n- The results suggest that SGD is more robust than the adaptive optimization methods, but those adaptive methods generally lead to faster model convergence. I wonder if there is any optimization method that enjoys both properties.\n- How do SGD with momentum perform on the experimented tasks?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a thorough study of the generalization and robustness performance of various optimizers, e.g., SGD and the adaptive ones (mainly RMSProp and Adam). The main finding is that though those aforementioned optimizers perform similarly on generalization, their robustness performance varies a lot. The main claim is that such a finding is due to the irrelevant frequencies in natural datasets (mainly image datasets). Perturbations on those irrelevant frequencies affect different optimizers in different ways. Analysis was conducted on linear models and empirical results were demonstrated on both synthetic and real datasets to justify the claim and existence of the irrelevant frequencies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Adding experiments on model architectures beyond CNNs, e.g., ViT and stable diffusion.\n- Extend the current experiment to text data.\n- Adding discussion on the robustness and model convergence.\n- Add SGD with momentum as an additional optimization method.", "broader_impact_concerns": "I don't think there is any concern about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7bxn8iYg1r", "reviewer": "Reviewer_RKpr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. This paper is clearly written and well organized.\n2. The problem addressed in this paper is interesting. To the best of my knowledge, the gap in robustness under different optimizers is somewhat overlooked in this area, and this paper may attract interested audiences.\n3. The claims are supported by sufficient empirical and/or theoretical evidence. For empirical validation, the experiments are conducted on various datasets and illustrated with multiple figures.\n4. Although the theoretical analysis is conducted on a simple linear model, the author also attempts to extend the theoretical evidence to DNNs.\n5. The insight delivered by this paper is of significance because it can help the community better understand how optimizers affect robustness and further design better optimizers for improved robustness.\n\n## Weaknesses\n\n1. Exploring adversarial robustness with frequency is not a completely new idea [1,2]. In Section 3, the authors claim that there are irrelevant frequencies that exist in natural data, and the higher end of the frequency spectrum has a strong impact on robustness. However, some of the conclusions can already be drawn from [1,2]. Therefore, I suggest the authors narrow their contribution by clarifying which claims are supported by existing work, and which claims are completely new discoveries.\n2. It is still a bit confusing why the authors disable batch normalization (BN) in experiments. In Appendix B, the authors claim that \"the effect of BN on model robustness is still an active research topic, therefore it is important to remove such a factor from our analysis and focus on how the choice of optimization affects robustness\". However, in my opinion, enabling BN is also fair for comparison among different settings. Furthermore, there are also many papers that understand different factors for adversarial robustness simply leaving BN enabled as default, including but not limited to [3,4].\n3. The theoretical analysis is based on a linear **regression** model while this paper mainly discusses the robustness under **classification** task. I think there may exist some solution for bridging this gap.\n4. Following 3: the extension from linear model to DNNs is based on weight norm as a proxy. The reason behind this, \"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\", shows a confusing relation between weight norm, irrelevant frequency representation, and robustness. Specifically, what is the main factor discussed in this paper, the frequency representation or weight norm? I don't think mixing everything together gives a clear explanation.\n5. This paper only discusses the phenomenon under standard training. However, adversarial training (AT) [5], which has been considered as one of the most effective approaches to improve adversarial robustness of the model, also exhibits this property. In [6], it is shown that AT with SGD optimizer leads to better adversarial robustness than other optimizers. Can the theory in this paper also explain this phenomenon?\n6. Recent work [7] also shows that Sharpness-Aware Minimization [8], which is an optimizer that regularizes the sharpness of weight loss landscape, can lead to significantly higher adversarial robustness than SGD optimizer. Can the theory in this paper also explain this phenomenon?\n\n[1] High-frequency Component Helps Explain the Generalization of Convolutional Neural Networks. CVPR\n\n[2] A Fourier perspective on model robustness in computer vision. NeurIPS\n\n[3] Exploring Architectural Ingredients of Adversarially Robust Deep Neural Networks. NeurIPS\n\n[4] Data Augmentation Can Improve Robustness. NeurIPS\n\n[5] Towards deep learning models resistant to adversarial attacks. ICLR\n\n[6] Bag of tricks for adversarial training. ICLR\n\n[7] Sharpness-Aware Minimization Alone can Improve Adversarial Robustness. ICML Workshop\n\n[8] Sharpness-Aware Minimization for Efficiently Improving Generalization. ICLR", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to understand the phenomenon of models trained with different optimizers (SGD, Adam, RMSProp) exhibiting significant differences in robustness against various types of noise, including Gaussian noise and adversarial perturbations. To this end, the paper explores the connection between different optimizers and robustness through the lens of frequency representation. Specifically, the authors make the following claims: 1) There exist irrelevant frequencies in natural data; 2) the sensitivity along the irrelevant frequencies leads to differences in robustness; 3) SGD, and signGD as a special case of adaptive gradient methods (Adam and RMSProp), converge to different solutions with respect to different frequencies, hence leading to different levels of robustness. These claims are observed empirically, and (3) is analyzed theoretically based on a linear model. To further extend claim (3) from a linear model to deep neural networks (DNNs), the authors also investigate the relationship between the Lipschitz constant and robustness in DNNs. Overall, this paper provides a comprehensive insight into the connection between different optimizers, frequency representation, and weight norm in the context of robustness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please reconsider the claim on contributions in Section 3: which claims are supported by existing work, and which claims are completely new discoveries.\n2. Please justify why disabling BN layers or adding experiments with BN enabled.\n3. Please justify the validity of using weight norm as a proxy for analyzing DNNs.\n4. Please discuss the scalability of the theory in terms of AT and SAM.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "r8fEtzMGBy", "reviewer": "Reviewer_rUpq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper is very well-written. The logic of observations-> theory->experiments is very clear and attractive to readers.\n2. The perspective of studying the robustness of algorithms by frequencies of data is interesting to me, although I am not very familiar with state-of-the-art research on robustness.\n\nWeaknesses:\nSome minor points are not very clear and may be incorrect. Please see the section of Requested Changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies how the frequency characteristics of the dataset affect the robustness of models trained by SGD and adaptive gradient methods. This work first observes that the robustness is related to irrelevant frequencies, which are mainly high frequencies of the data, and then shows that different learning algorithms have different mechanisms when handling these data frequencies. The experiments support the findings and also indicate that regularization can further improve performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Figure 5a looks strange to me at first. I thought the error for $\\tilde{e}_0(t)$ and $\\tilde{e}_1(t)$ should be decreasing, but it seems not. Later I understood that it was because $\\tilde{w}_0(0)$ is smaller $\\tilde{w}^*_0$, and $\\tilde{w}_1(0)$ is smaller $\\tilde{w}^*_1$. I suggest changing the y-axis to $|\\tilde{e}_i(t)|$, where $i=0,1,2$ to avoid this confusion. \n2. For the relationship between the weight norm and the robustness, I am not sure whether this result is novel or not. I only know that such regularization can avoid overfitting. Is the improvement of robustness related to the reduction of overfitting? Some clarification of how such discussion differs from existing knowledge is helpful.\n3. For the last term of Equation 9, I thought it should be $<\\Delta \\tilde{x}, \\tilde{w}-\\tilde{w}^*>$ instead of $<\\Delta \\tilde{x}, \\tilde{w}>$?\n4. In this sentence, \"Finally, in the deep learning setting, we showed that models trained by SGD have a noticeably larger Lipschitz constant than those trained by Adam and RMSProp\", at the end of Section 6, I think it is a typo. SGD is shown to have a smaller Lipschitz constant as in Table 1, isn't it?", "broader_impact_concerns": "No such concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the robustness of neural networks under different training algorithms, including stochastic gradient descent (SGD) and adaptive gradient methods, followed by an in-depth analysis of gradient descent (GD) and sign gradient descent (signGD) methods. The results offer new theoretical insights into understanding the effect of optimization algorithms on the robustness of neural networks. All reviewers recommend acceptance for this paper, and I concur.

I also recommend Featured Certification for this submission, as the results provide new insights into understanding the fundamentals of robustness and gradient-based training methods.
Decision: Accept (poster)