Data dependent frequency sensitivity of convolutional neural networks
Authors: Charles Godfrey
Elise Bishoff
Myles McKay
Davis Brown
Grayson Jorgenson
Henry Kvinge
Eleanor Byler
Venue: Submitted to ICLR 2023 (2023)
Keywords: deep learning
convolutional neural networks
sparsity
matrix factorization
robustness

Abstract: It is widely acknowledged that trained convolutional neural networks (CNNs) have different levels of sensitivity to signals of different frequency. In particular, a number of empirical studies have documented CNNs sensitivity to low-frequency signals. In this work  we show with theory and experiments that this observed sensitivity is a consequence of the frequency distribution of natural images, which is known to have most of its power concentrated in low-to-mid frequencies. Our theoretical analysis relies on representations of the layers of a CNN in frequency space, an idea that has previously been used to accelerate computations and study implicit bias of network training algorithms, but to the best of our knowledge has not been applied in the domain of model robustness. 

Under review as a conference paper at ICLR 2023
REGULARIZED LINEAR CONVOLUTIONAL NETWORKS INHERIT FREQUENCY SENSITIVITY FROM IMAGE STATISTICS
Anonymous authors Paper under double-blind review
ABSTRACT
It is widely acknowledged that trained convolutional neural networks (CNNs) have different levels of sensitivity to signals of different frequency. In particular, a number of empirical studies have documented CNNs sensitivity to low-frequency signals. In this work we show with theory and experiments that this observed sensitivity is consequence of the frequency distribution of natural images, which is known to have most of its power concentrated in cow-to-mid frequencies. Our theoretical analysis relies on representations of the layers of CNN in frequency space, an idea that has previously been used to accelerate computations and study implicit bias of network training algorithms, but to the best of our knowledge has not been applied in the domain of model robustness.
INTRODUCTION
Since their rise to prominence in the early 1990s, convolutional neural networks (CNNs) have formed the backbone of image and video recognition, object detection, and speech to text systems (Lecun et al., 1998). The success of CNNs has largely been attributed to their "hard priors" " of spatial translation invariance and local receptive fields (Goodfellow et al., 2016, $9.3). On the other hand, more recent research has revealed number of less desirable and potentially data-dependent biases of CNNs, such as a tendency to make predictions on the basis of texture features (Geirhos et al., 2019). Moreover, it has been repeatedly observed that CNNs are sensitive to perturbations in targeted ranges of the Fourier frequency spectrum (Guo al., 2019; Sharma al., 2019) and further investigation has shown that these frequency ranges are dependent on training data (Yin et al., 2019; Bernhard et al., 2021; Abello et al., 2021; ;; Maiya et al., 2022). In this work, we provide mathematical explanation for these frequency space phenomena, showing with theory and experiments that neural network training causes CNNs to be most sensitive to frequencies that are prevalent in the training data distribution.
Our theoretical results rely on representing an idealized CNN in frequency space, a strategy we borrow from (Gunasekar et al., 2018). This representation is built on the classical convolution theorem,
i .t:
(1.1)
where & and vē denote the Fourier transform of r and w respectively, and * denotes a convolution. Equation 1.1 demonstrates that a Fourier transform converts convolutions into products. As such, in "cartoon" representation of CNN in frequency space, the convolution layers become coordinate-wis multiplications more precise description is presented in section 3). This suggests that in the presence of some form of decay, the weights ú for high-power frequencies in the training data distribution will grow during training, while weights corresponding to low-power frequencies the training data will be suppressed. The resulting uneven magnitude of the weights 인 across frequencies can thus account for the observed uneven perturbation -enssiiiiisssiiiiiittt... of CNNs in frequency space. We formalize this argument for linear CNNs (without biases) in sections 3 and 4.
One interesting feature of the framework set up in section is that the discrete Fourier transform (DFT) representation of a linear CNN is precisely feedforward network with block diagonal weight matrices, where each block corresponds to frequency index. We show in theorem 4.9 that learning objective for such network of depth L with fo-mrrm penalty on weights is equivalent to

---

Under review as a conference paper at ICLR 2023
objective for the associated linear model with an lp penalty the singular values of each of its blocks, i.c. each frequency index - this result is new for CNNs with multiple channels and outputs. In particular, the latter penalty is highly sparsity encouraiin...... suggesting depth increases these linearly-activated CNNs have an even stronger incentive to prioritize frequencies present in the training data.
has long been known that the frequency content of natural images is concentrated in low-to-mid frequencies, in the sense that the power in Fourier frequency ff is well-described by 1/l/|a for coefficient a R 1 (Lee et al., 2001). Hence, when specialized to training data distributions of natural images, our results explain findings that CNNs are more susceptible to low frequency perturbations in practice (Guo et al., 2019; Sharma et al., 2019).
We use our theoretical results derive specific predictions: CNN frequency sensitivity aligns with the frequency content of training data, and deeper models, as well as models trained with substantial weight decay, exhibit frequency sensitivity more closely reflecting the statisties of the underlying images. We confirm these predictions for nonlinear CNNs trained on the CIFARIO and ImageNette datasets. Figure shows our experimental results for a variety of CNN models trained on CIFARIO I0 as well as variant of CIFAR1O preprocessed with high pass filtering (more experimental details will be provided in section 5).
To the best of our knowledge, ours is the first work to connect the following research threads (see section 2 for further discussion):
equivalences between linear neural networks and sparse linear models, classical data-dependent "shrinkage" properties of sparse linear models, statistical properties of natural images, and sensitivity of CNNs to perturbations in certain frequency ranges.
2 RELATED WORK
The following a brief synopsis of work most closely related to this paper; a more through survey can be found in appendix A.
(Guo al., 2019) found that adversarial perturbations constrained to low frequency Fourier components allowed for greater query efficiency and higher transfcrability between different neural networks, and (Sharma et al., 2019) demonstrated that constraining to high or midrange frequencies did not produce similar effects. (Jo & Bengio, 2017), (Yin et al., 2019), (Bernhard et al., 2021), (Abello et al., 2021) and (Maiya et al., 2022) all found in one way another that model frequency sensitivity depends the underlying training data. Our work began as an attempt to explain this phenomenon mathematically.
Perturbations in frequency components:
Implicit bias and representation cost of CNNs: Our analysis of (linear) convolutional networks leverages prior work on implicit bias and representational cost of CNNs, especially (Gunasekar et al., 2018). There was found that for a linear CNN trained on binary linear classification task with exponential loss, with linear effective predictor 3, the Fourier transformed predictor 3 converges (in direction) to a first-order stationary point of
1 min 2 1111// such that y" 8" xn 2 1 for all n.
(2.1)
Our general setup in section 3 closely follows these authors', and our theorem 4.9 partially confirms a suspicion of (Gunasckar et al., 2018, $6) that "with multiple outputs, as more layers are added, even fully connected networks exhibit shrinking sparsity penalty on the singular values of the effective linear matrix predictor..."
While the above result describes a form of implicit regularization imposed by gradient descent, we instead consider explicit regularization imposed by auxiliary &, norm penalties in objective functions, and prove equivalences of minimization problems. In this sense our analysis is technically more closely related to that of (Dai et al., 2021), which considers parametrized families of functions f(z w) and defines the representation cost of a function g(æ) appearing in the parametric family as
R(g)= min (lwl2 [ w)) = g(x) for all x).
(2.2)
2

---

Under review as a conference paper at ICLR 2023
(a) Actuall models of varying depth.
(b) ConvActuully models of depth 4 trained with varying weight decay.
(c) VGG models of varying depth.
-12
(d) VGG 11 models trained with varying weight decay.
(e) Myrtle CNN models trained with varying weight decay.
r] of frequency sensitivities of CNNs trained on (CFFRI,I post protepsee by dividing each curve by its integral. taking logarithms and smoothing by averaging with 3 neighbors on either side. Bottom row: frequency statistics of (hpf- OCIFARIO 10 for comparison. See section 5 for further details.
Figure 1: Radial averages E (x)
[(t.j]]
3

---

Under review as a conference paper at ICLR 2023
While this approach lacks the intimate connection with the gradient descent algorithms used train modern neural networks, it comes with some benefits: for example, results regarding representation cost are agnostic to the choice of primary loss function (e.g. squared error, cross entropy, contrastive losses).
Data-dependent bias: Perhaps the work most closely related ours is that of (Hacohen & Weinshall, 2022) on principal component bias, where is shown that rates of convergence deep (and wide) linear networks are governed by the spectrum of the input data covariance matrix.
3 THE DISCRETE FOURIER TRANSFORM OF CNN
In this section we fix the notation and structures we will be working with. We define class of idealized, linear convolutional networks and derive a useful representation of these networks in the frequency space via the discrete Fourier transform.
Consider linear, feedforward 2D-CNN (ax of the form
RCXH w' X RC2XXxW
RR CLL-IXIXW
WT.TT I K (3.1)
where w denotes the convolution operation between tensors w/ RCX//XWXCC-11 and r 1 XXX defined by
(w' r)eij
E
Σ w comdd
(3.2)
m+m =(ntt'
and wT.Tz x denotes a contraction (a.k.a. Einstein summation) of the tensor w Rx XCt-1 with the tensor E I over the last 3 indices (the (-)" denotes a transpose operation described momentarily). Explicitly,
(w xT)
Σ
wkmnt Pimn-
(3.3)
Lmn.
Thus, the model eq. (3.1) has weights RRCIHHWXCL- for = 1,..., T. - and R X XW XCL-1,
Remarks 3.4. For tensors with at least indices (such as x and the weights wi above) we will always use the transpose notation- -?' to denote reversing the second and third tensor indices, which will always be the 2D spatial indices. For matrices and vectors will be used according to standard practice. In eq. (3.3) the transpose ensures that the indices in Einstein sums move from "inside out" as is standard practice.
Equivalently, wL.Tz x can be described as usual matrix product Wy vec(x) where vec(z) is the vectorization (flattening) of x and w is obtained by flattening the last tensor indices of wt (compatibly with those of x dictated by eq. (3.3)). Hence it represents typical "flatten and then apply a linear layer" architecture component. Our reason for adopting the tensor contraction perspective is that it is more amenable to the Fourier analysis described below.
Note that in this network the number of channels is allowed vary but the heights and widths remain fixed, and that we use full H x W convolutions throughout as opposed to the local (e.g. 3 x 3) convolutions often occurring practice.
Given an array & E Cxxxxx we may consider its discrete Fourier transform (DFT) 4, whose entries computed
2 mi
2 nj).
Lesj
Temn exp(
(3.5)
VHW
H
W
Similarly, for an array w E CCX the DFT defined to
2T
2
Wrijd
Wemnd exp(
mi
W n.))
(3.6)
VHW
H
77,30
In what follows the DFT will always be taken with respect to the two spatial dimensions and no others. The mapping x + & defines an orthogonal linear transformation of x In addition,
it satisfies the following properties:
4

---

Under review as a conference paper at ICLR 2023
Lemma 3.7 (Cf. (Kiani et al., 2022, Lem. C.2)).
W x u 4 for E IR CIXXXWXLLL E TR CLXHWX (convolution theorem) w² x = a for BRCXHXWXLLI,, R R (Parseval's theorem).
(3.8)
(3.9)
Explicitly, the products on the right hand sides of eqs. (3.8) and (3.9) are defined as
(w - D)as = Σ ass and (w 8)r
Σ d.s.j
WaidBai respectively.
(3.10)
Remark 3.11. In the terminology of CNNs, this says that the DFT converts full H x W convolutions to spatially pointwise matrix multiplications, and preserves dot products.
Our first lemma is mild generalization (Gunasekar et al., 2018, Lem. 3); we defer all proofs to appendix D.
Lemma 3.12. The CNN f(x) is functionally equivalent to the network f()) defined as
CCHHWW E, CXXHW .'' CCXXHXW - CCC-IXHXW Wh. CK (3.13)
where the first map
denotes the DFT H
4 REGULARIZED CNN OPTIMIZATION PROBLEMS IN FREQUENCY SPACE
Consider a learning problem described as follows; given dataset D = ((*", (""","") E RC x R i ... N). and loss function L: (RK)* x (RRK) + IR, we seek weights w solving the le- fz-regularized minimization problem
min (((((=))) (V ( + + Σ not or equivalently given lemma 3.12,
6
(4.1)
min C(( (v ) +
Σ 16
This setup allows a wide variety of loss functions. the experiments of section and appendix B we consider two important special case: first, supervised-style empirical risk minimization with respect to sample-wist loss function É IRK x I2 IR (in our experiments, cross entropy), where
Σ ((((z)),v') N n=1
(4.2)
Second, contrastive losses such as the alignment and uniformity objective of (Wang Isola, 2020), which encourages the features f(x") to be closely aligned with their corresponding "labels" y", and the set of features [x(")) to be uniformly distributed on the unit sphere SK-1 C R
According to lemma 3.12,
- - T.. (w 10
(4.3)
In the case where the numbers of channels C, Cr,..., CL-1 1 are all 1 and the number of classes K = 1, networks of this form were studied in (Tibshirani, 2021) where they were termed "simply connected." In the where the the number of classes K 1 but the numbers of channels C may be larger, such networks were studied in (Gunasekar et al., 2018). Of course, eq. (4.3) is just an over-parametrized linear function. We can describe it more succinctly by introducing new tensor XXXXXC such that f()) j.. With little manipulation of eq. (4.3), we can obtain formula for e in terms of the Wy for 1 = L. Lemma 4.4.
u L.T
(4.5)
The following theorem shows that the regularization term of eq. (4.1), which penalizes the & normo of the factors ú'. is equivalent to penalty using more sparsity-encouraging norms of To state need definition.
5

---

Under review as a conference paper at ICLR 2023
Definition 4.6 (Schatten p-norms). Let A (aiz) M(n x n, C) be square matrix and let A = UDVT be singular value decomposition of A, where U, V E (n) and D diag(X) is non non-negative diagonal matrix with diagonal entries Ai...., An 2 0. For any p > the Schatten p-norm of A is
|| = 3 ((PP). X2
(4.7)
Remark 4.8. In the case p p= 2, the 2-norm of definition 4.6 agrees with the usual Euclidean 2-norm Ei aigl 13)à, since left (resp. right) multiplication by unitary matrix U (resp. V) preserves the Euclidean 2-norms of the columns (resp. rows) of A.
Theorem 4.9. The optimization problem eq. (4.1) is equivalent to an optimizationn problem for of the form
min C((6T="))) 1 (vr)) + AL E(16))1))
(4.10)
where' Big denotes the C matrix obtained by fixing the spatial indices of é (Deija).
and the min is laken over the space of lensors è such that each matrix Gig has rank at most min(C, Ci...., Cr...,,, K}.
The essential ingredient of our proof is a generalized con-commutative Hölder inequality.
Lemma 4.11. If B M(m n, C) is malrix with complex entries, A1,..., As composable sequence of complex matrices such that A5, ... A = B and Σi 1 where p,...., P.,,"" r >> 0 are positive real numbers,
|B| I
(4.12)
Such inequalities are not new: in the 6), and in the case L = 2 it is an exercise in (Bhatia, 1996). However, we suspect (and our proof of theorem 4.9 suggests) that lemma 4.11 underpins many existing results on implicit bias and representation costs of (linear) neural networks, such as those of (Gunasekar et al., 2018; Yun et al., 2021; Dai et al., 2021; Lawrence et al., 2022; Jagadeesan et al., 2022).
lemma 4.11 follows from (Dixmier, 1953, Thm.
In the case where the numbers of channels C, Ci.... CL-1 are all 1 and and the number of outputs K 1, and where the loss is squared error, the problem eq. (0. reduces to
min
1 N
0 AL Σ
0zyl +
(4.13)
The sum in the regularization term of eq. (4.13) is |0 where 2 in particular when L = 1, eq. (3) is a ridge regression problem (Hastie et al., 2001; Tibshirani & Wasserman) and when L = 2 (the one hidden layer case) eq. (4.13) is LASSO problem. We can analyze these two tractable cases to obtain qualitative predictions which will be tested empirically in section 5. Since the qualitative predictions from both cases similar, devote the following section ridge, and defer LASSO to appendix C.
4.1 L = 1: RIDGE REGRESSION
In this case, eq. (4.13) is the usual ridge regression objective; the closed-form solution is
1 X x ATY
(A + N
(4.14)
N
where X is N x C H x W batch tensor with "rows" the 4n and the entries of Y are the y" (see e.g. (Hastic et al., 2001)). When = this reduces to the usual (unpenalized) least squares solution tLS = (XTX) - XTY, and substituting XTY = X X0LS is in eq. (4.14) we obtain
(A
x X Xiis N
1
1 N
(4.15)
by abuse of notation for which we beg your forgiveness.

---

Under review as a conference paper at ICLR 2023
where strietly speaking X X is tensor product of X with itself in which we contract over the batch index of length N, hence is shape x H x C x x W.
The frequency properties of images enter into the structure of the symmetric tensor 1. X X, which (if the dataset 'D is centered, i.e. preprocessed by subtracting the mean 1 x" IN) serves as generalized N
N
covariance matrix for the frequency space representation of D. To ease notation, let t 8 X, and suppose that
Taij
if (c, (, = (())))")
Ewhoel'' 2
(4.16)
0 otherwise.
In other words, proper covariances between distinct frequency components are negligible and we retain only the variances, i.e. the diagonal entries of the covariance matrix. In fig. we demonstrate that this assumption is not unrealistic in the case where X is dataset of natural images.
With the assumption of eq. (4.16), eq. (4.15) reduces to
Tetj 0LS, = + A ULS,cis for all cij.
(4.17)
À + Taij
Equation (4.17) is an instance of the classic fact that ridge regression shrinks coefficients more in directions low input variance. In words, Teij is the variance of training images Fourier component cij, and eq. (4.17) says [رay) shrinks more when the variance Teij is low; in the limiting case Teij + the coefficient beis + 0 as well.
Returning the subject of frequency sensitivity, observe that dei is the directional derivative of with respect to the cij-th Fourier component.
Proposition 4.18 (Data-dependent frequency sensitivity, == With the notations and assumptions introduced above, the magnitude of the directional derivative of f with respect to the cij-th Fourier component scales with and according to
Empirically it has been found that for natural distributions of images the variances Taij follow power law of the form Teij R +12- (Lee et al., 2001; Baradad et al., 2021). Under this model, eq. (4.17) becomes
jaj 1+ (1:10 + 15]3) ULSS for all cij.
(4.19)
that is. sensitivity is monotonically decreasing with respect to both frequency magnitude and the regularization coefficient. This is consistent with findings that CNNs trained on natural images are vulnerable to low frequency perturbations (Guo et al., 2019; Sharma et al., 2019).
5 EXPERIMENTS
When L > 2 (that is, when there are more than convolutional layers), the p "norm" of eq. (4.10) non-convex (hence the quotes), and in the limit as L - oo the norms appearing in eq. (4.10) converge to the Schatten 0- D-"nomm," which is simply the number of non-O singular values of matrix.?
Moreover, we see that the regularization coefficient of eq. (4.10 (4.10) is effectively multiplied by L.
Even in the case where K = so that è is vector, it is known that solving eq. (4.10) for L > is NP-hard (Chen et al., 2017), so we have no hope of finding closed form solutions as in section 4.1. However, we can use the analysis in section 4 to derive three testable hypotheses:
CNN frequency sensitivity depends on the frequency content of training data (proposi- tion 4.18).
II. The fact that the regularization term of eq. (4.10) becomes more sparsity-encouraging as L increases suggests that the data- data-dependent frequency sensitivity observed in section 4.1 and appendix C becomes even more pronounced as the number of convolutional layers increases.
In particular, under this approximation Tey is independent of c.
II the special case where K 1 the regularization term in eq. (4.10) is the penalty of the subset selection problem in the field of sparse linear models.
7

---

Under review as a conference paper at ICLR 2023
113
(a)
(b)
(a) Standard deviations of image datasets along Fourier basis vectors: in the notation above, these are the y Licci (viewed in log scale as RGB images). The origin corresponds to the lowest frequency basis vectors (i.e. constant images). (b) Same as (a), but with the addition of high pass filtering removing frequency indices (i,j) with ji] < 8 (we also experiment with higher frequency cutoff on ImageNette in appendix B).
Figure 2:
III. Moreover, the functional forms of eqs. (4.17) and (C.7) suggest that the data-dependent frequency sensitivity will increase monotonically with the weight decay parameter X.
We empirically validate these hypotheses with experiments using CNNs trained on multiple datasets. The datasets used in these experiments are CIFARIO 10 (Krizhevsky, 2009), ImageNette (the 10 easiest classes from ImageNet (Deng et al., 2009)) (FastAl, 2019), and synthetic images generated using the wavelet marginal model (WMM) of (Baradad et al., 2021). The later dataset is of interest since the generative model is explicitly designed to capture the frequency statisties of natural images, and allows for varying the exponents a and /3 in the power law Taij R .13 described above. Figure 2a display the variances CIFARIO, ImageNette and their high pass filtered variants in frequency space; for those of the WMM datasets see fig. 3. In addition, we experiment with high pass filtered versions of the CIFAR 10 and ImageNette datasets, which we refer as hpf-CIFAN 10 and metelmt respectively; the frequency space statistics of these are shown in fig. 2b. For implementation details we refer to appendix B. We can further summarize the data displayed in figs. 2a and 2b by averaging over circles with varying radii r, i.e. computing expectations E V jiecis [i. r). to obtain the frequency magnitude statistics curves shown in fig. (see appendix B.2 for implementation details). From this point forward we focus on such curves with respect to frequency magnitude.
The CNNs used in these experiments are ConvActually (a CNN that closely approximates eq. (3.1), the differences being the addition of biases and ReLU non-linearities) Myrtle CNN (a small feed- forward CNN known to achieve high performance on CIFARIO 10 obtained from (Page)). VVG (a family of CIFARIO VGGs (Simonyan Zisserman, 2015) obtained from (Fu, 2017) and ImageNet VGGs from (Marcel & Rodriguez, 2010)), ResNet (a family of CIFAR10 ResNets (He et al., 2016) obtained from (Team, 2021)), and AlexNet (a small AlexNet (Krizhevsky al., 2012) adapted to contrastive training obtained from (Baradad et al., 2021)) For more detailed descriptions of datasets and model architectures we refer to appendices B. and B.5.
We measure frequency sensitivity of CNN I in terms of the magnitudes of the directional derivatives ( where εæi is the cij-th Fourier basis vector. These magnitudes are averaged over all the input images in the relevant validation set, and as in the case of image statistics we can average them over circles of varying radii, i.c. compute expectations E'| v.. fxx) e Realllle [(i, = r] (see appendix B.3 for implementation details). By "data-dependent frequency sensitivity" the extent to which the frequency sensitivity of a CNN f reflects the statistics of the images it was trained on. Figures 1, 2a, 3 and show that the variance of DFTed CIFARIO. ImageNette and WMM images is heavily concentrated at low frequencies, in agreement with the power law form Teij [ described in section 4.5 Hence in the absence of any modifications to the underlying images, we expect that training on this data will emphasize sensitivity of f to perturbations along the lowest frequency Fourier basis vectors, with the effect increasing along with model depth and the weight decay parameter A. On the other hand, the variance of hpf-CIFAR10 10 and hpf- Impe-eeteeette is concentrated in mid-range frequencies, and here expect training will emphasize sensitivity of to perturbations along mid range Fourier hasis vectors (again with more pronounced effect as depth/A increase).
mean
"This was inspired by the experiments of (Jo & Bengio, 2017) and (Yin et al., 2019).
'In the of WMM this is by design.
8

---

Under review as a conference paper at ICLR 2023
5.1
FREQUENCY SENSITIVITY AND DEPTH
Figure la shows sensitivity of ConvActually models of varying depth to perturbations of varying DFT frequency magnitudes. These curves illustrate that as depth increases, frequency sensitivity (r) Eety [(.jj) =r] more and more closely matches the frequency magnitude statistics El EiveSices j), = of the training data set, both in the case of natural and high pass filtered images hence, these empirical results corroborate hypotheses I. and II.. Figure Ic shows results of a similar experiment with VGG models of varying depth; models trained on natural images have sensitivity generally decreasing with frequency magnitude, whereas those trained on high pass filtered data have "U" shaped sensitivity curves with minima near the filter cutoff, corroborating hypothesis I.. Here it is not clear whether models trained on natural images follow that pattern predicted by II. (the deepest models are less sensitive to both low and high frequencies), however when trained on high pass filtered images deeper models do seem to most closely follow the frequency statistics of the dataset. Figure includes similar experiment with VGG models of varying depth trained on Meage)emaeeNette.
5.2 FREQUENCY SENSITIVITY AND WEIGHT DECAY
Figure 1b shows radial frequency sensitivity curves for Conv models of depth 4 trained on (hpf-)CIFAR10 10 with varying weight decay coefficient A. We see that as À increases, model frequency sensitivity more and more closely reflects the statisties of the training data images, corroborating hypotheses I. and III.. Figure 1b shows results for a similar experiment with Myrtle CNNs, with similar conclusion. Figure shows results for VGG models trained with varying weight decay on (maf-)Mmaeeeette.
5.3
IMPACT OF THE LEARNING OBJECTIVE
So far, our analysis and experiments have only shown that the regularization term in eq. (4.1) encourages CNN gradients with respect to spatial Fourier basis vectors to reflect the frequency statistics of the training data. is of course possible that the first term of eq. (4.1) defining the learning objective overwhelms the regularization term resulting in different model frequency sensitivity. In fig. 8 we show this occurs in CNNs trained on WMM synthetic data with an alignment and uniformity contrastive loss; see appendix B.4 for a possible explanation in the framework of sections 3 and 4,
6 LIMITATIONS AND OPEN QUESTIONS
In order to obtain an optimization problem with some level of analytical tractibility, we made many simplifying assumptions in sections and 4, most notably omitting nonlinearities from our idcalized CNNs. While the experimental results of section 5 illustrate that multiple predictions derived from sections 3 and 4 hold true for CNNs more closely resembling those used in practice trained with supervised learning, fig. shows that hypotheses I-III can fail in the presence of residual connections see appendix B.4 for further discussion. As previously mentioned, fig. 8 shows that a contrastive alignment and uniformity learning objective results in far different CNN representations.
Perhaps more significantly, must be emphasized that model sensitivity as measured by gradients represents very small corner of broader picture of model robustness (or lack therof). For example, it does not encompass model behaviour on corruptions (see e.g. (Hendrycks & Dietterich, 2019)) or shifted distributions (see e.g. (Recht et al., 2019)).
REFERENCES
Antonio A. Abello, Roberto Hirata, and Zhangyang Wang. Dissecting the high- high-frequency bias in convolutional neural networks. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 863 871, 2021. doi: 10. 10..1099/.
.00096.
Manel Baradad, Jonas Wulff, Tongzhou Wang, Phillip Isola, and Antonio Torralba. Learning to see by looking at noise. In A. Beygelzimer, Y. Dauphin. P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:/ tttpps://ppeneee /pppnreven....... n forum? d=RQU1 dd=gg018g7NN70

---

Under review as a conference paper at ICLR 2023
Rémi Bernhard, Pierre-Alain Moëllic, Martial Mermillod, Yannick Bourrier, Romain Cohendet, Miguel Solinas, and Marina Reyboz. Impact of spatial frequency based constraints on adversarial robustness. In 2021 International Joint Conference Neural Networks (IJCNN), pp. 1-8, 2021. doi: 10.1 1091009/CNN523387 2201 .534307.
Rajendra Bhatia. Matrix Analysis. Springer Science & Business Media, November 1996. ISBN 178-0-387-94846-1.
Yichen Chen, Dongdong Ge, Mengdi Wang. Zizhuo Wang, Yinyu Ye, and Hao Yin. Strong NP- hardness for sparse optimization with concave penalty functions. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pp. 140-747. PMLR, 06-11 Aug 2017. URL https: http///pccceeeineeee/ee/e//e/see mml pre.sppess.ee /vwssvv////// htt///////cceenn html.
Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks: Analysis and design. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: //opps////peeeviee. net/forue die2didd330 3 jABdbC8.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Ieee, 2009.
James Diffenderfer, Brian R Bartoldson, Shreya Chaganti, Jize Zhang, and Bhavya Kailkhura. A winning hand: Compressing deep networks can improve outtof-diittibuution robustness. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https://opeerrett XygAOypoTR.
net forummidk
Jacques Dixmier. Formes linéaires sur un anneau d' d'opérateurs. Bulletin de la Société Mathématique de France, 81:9-39, 1953. doi: 10.24033/bsmf. 1436.
FastAl. imagenette.
woom//astai/mmageeeeeeeeeeeeeeee 2019.
Cheng-Yang Fu. pytorch-vgg-cifar10. https: com/ wwwp./////ccc/.u///////ao
gytorch-vgg--o cigg-cifarl.. 2017.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A. Wichmann, and Wieland Brendel. Imagenet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness. In International Conference on Learning Representations, 2019. URL httpt:tt///// wpt.reveeeee.eeee// net. hetts/fformmidd-yyhhhh 6O9KX.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Leurning. MIT Press, 2016. http: // www.deeppeeeennndeeeeeeoe org.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Chuan Guo, Jared S. Frank, and Kilian Q. Weinberger. Low Frequency Adversarial Perturbation. In UAI, 2019.
Guy Hacohen and Daphna Weinshall. Principal components bias in over-parameterriee linear models, and its manifestation in deep neural networks. Journal of Machine Learning Research, 23(155): 1-46, 2022. URL http:// jmlr. org. http://apppp/////2///pppp 221//1119991111 html.
Trevor J. Hastie, Robert Tibshirani, and Jerome H. Friedman. The elements of statistical learning: Data mining, inference, and prediction, 2nd edition. In Springer Series in Statistics, 2001.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEFE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2023
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. In International Conference on Learning Representations, 2019.
URL http:p:s///ppeeeeeewwee net wore//ormmmmmmmm dtt.:oooddddddtdtttt11ee-ee
Nicholas J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008. ISBN 978-0-898716-46-77
Meena Jagadeesan, Ilya Razenshteyn, and Suriya Gunasekar. Inductive bias of multi-channel linear convolutional networks with bounded weight norm. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 2276-2325. PMLR, 02-05 Jul 2022. URL https: https://prrroooe /proceed ngs. mlr. walrspres////
jagadessan22a html..
Jason Jo and Yoshua Bengio. Measuring the tendency of cnns to learn surface statistical regularities. CoRR, abs/1711. 11561, 2017. URL htttht/pp//aaeet org/ abs 111/1/11.1111 11561.
Bobak Kiani, Randall Balestriero, Yann LeCun, and Seth Lloyd. ProjUNN: efficient method for training deep networks with unitary matrices. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL
https: http///pppeeeeeeeeeeeeeeeeeeeeee nett forum? d=nEJMdzdBcTI.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Wein- berger (eds.), Advances Neural Information Processing Systems, volume 25. Curran Asso- ciates, Inc., 2012. URL https: http:ss:///occeeeeeeee c399862d3b9d644 (aaee/666666446662222444488888 -at.reee2222assssaaaee.eereee
meurips cc/ppppe//211/// file/
Hannah Lawrence, Bobak Kiani, Kristian G. Georgiev, and Andrew K. Dienes. Implicit Bias of Linear Equivariant Networks. In Proceedings of the 39th International Conference on Machine Learning, pp. 12096-12125. PMLR, June 2022.
Guillaume Leclere, Andrew Ilyas, Logan Engstrom, Sung Min Park, Hadi Salman, and Aleksander Madry. ffev. https:
pestps:/ggitie /ttpttbbtttt.tt/////// com/ http///bffff/ffff/// 2022. commit XXXXXXX.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6(11):2278-2322 1998. doi: 10.1109/5.72679.
Ann B. Lee, David Mumford, and Jinggang Huang. Occlusion Models for Natural Images: Statistical Study of Scale-Invariant Dead Leaves Model. International Journal of Computer Vision, 41(1):35 January 2001. ISSN 1573-1405. doi: 10.1023/A:101 1190015675.
Kaifeng Lyu and Jian Li. Gradient Descent Maximizes the Margin of Homogeneous Neural Networks, December 2020.
Shishira Maiya, Max Ehrlich, Vatsal Agarwal, Ser-Nam Lim, Tom Goldstein, and Abhinav Shrivas- tava. A frequency perspective adversarial robustness. 2022. URL httpss:/ net/forund 1== 7d=7gRc
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-vision package of torch. In Proceedings of the 18th ACM International Conference Multimedia, MM '10, pp. 1485-1488, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 978 1781666559336. doi: 10.1 10.1145/1873951.18888 1874254.. URL https: / www.oo../....o.o.. 1.00..1444444 1145/ 815///177999 375911 1874254.
Michael Mathieu, Mikael Henaff, and Yann LeCun. Fast training of convolutional networks through ffts: International conference learning representations (icl:2014), cbls, april 2014. January 2014. 2nd International Conference on Learning Representations, ICLR 2014: Conference date: 14-04-2014 Through 16-04-2014.
David Page. How to Train Your ResNet.
URL
https: https://nyttlleaa//eeemn
fow-to-train-your--rr
11

---

Under review as a conference paper at ICLR 2023
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bus E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019, URL http: /paptt:://pppp....pppps nwwrips wwtpppppccpppppppp/pppp 9015-pytorch-an--mpeee htt.ar/eeeeeeeeaaaaarerrereeeeee pdf.
Harry Pratt, Bryan M. Williams, Frans Coenen, and Yalin Zheng. Fenn: Fourier convolutional neural networks. In ECML/KKDD, 2017.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Dräxler, Min Lin, Fred A. Hamprecht, Yoshua Bengio, and Aaron C. Courville. On the spectral bias of neural networks. In ICML, 2019.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do ImageNet elassifiers generalize to ImageNet? In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 5389-5400, PMLR, 09-15 Jun 2019. URL https: ppt.eedinee...... mlr. mlr.press/ w9t. 9a. html.
Yash Sharma, G. Ding. and Marcus A. Brubaker. On the Effectiveness of Low Frequency Perturba- tions. 2019. doi: 10.24963lijeai221194777
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Jiachen Sun, Akshay Mehra, Bhavya Kailkhura, Pin-Yu Chen, Dan Hendrycks, Jihun Hamm, and Z. Morley Mao. A spectral view of randomized smoothing under common corruptions: Bench- marking and improving certified robustness. In Shai Avidan, Gabriel Brostow, Moustapha Cissé, Giovanni Maria Farinella, and Tal Hassner (eds.), Computer Vision ECCV 2022 - 17th European Conference, Tel Aviv, Isruel, October 23-27, 2022, Proceedings, Part IV, volume 13664 of Lecture doi: 10. 10.10079973--333311977----3333 URL https:://// / / /doi org/ /10 1007 00000079777800-111777711-----111
Notes in Computer Science, pp. 654 671. Springer, 2022.
The Mosaic ML Team. composer. https://github hompper...tppp///aaat.oo.ooo/oaa http:///aaaammmmmoooomm////////
Ryan Tibshirani and Larry Wasserman. Sparsity, the Lasso, and Friends. pp. 34.
Ryan Tibshirani. Equivalences Between Sparse Models and Neural Networks, pp. 2021. URL cmu. wdt.rryanttss//////e/oeaaaaa httpa////.....yaaaaa/////aaaesse http:///waaattbo//ppp////ssss//a wttpsrssssppsstttnnom.mmm pdf.
https:
Nicolas Vasilache, Jeff Johnson, Michael Mathieu, Soumith Chintala, Serkan Piantino, and Yann LeCun. Fast convolutional nets with fbfft: A gpu performance evaluation. January 2015. 3rd International Conference on Learning Representations, ICLR 2015; Conference date: 07-05-2015 Through 09-05-2015.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity the hypersphere. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pp. 9929-9939. PMLR, 13-18 Jul 2020. URL
https: http:///coceeeneeeee/eee wwe.s.ppress/... saress/vill v119/ wwwivv/iwawneeee wang20k html.
Lechao Xiao. Eigenspace restructuring: principle of space and frequency in neural networks. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 4888 1888-494,, PMLR, 02-05 Jul 2022. URL https:tpps... httptttpps/ppppeeeeeeeeee http:///ecocccccpceeeceo mlr prwss/ httss//////iii///./ html.
Lechao Xiao and Jeffrey Pennington. Precise learning curves and higher-order scaling limits for dot product kernel regression, 2022. URL https: www.viivvvvv....vo....aaavvv wwwpvvoorrrgaboooo /2205. 18466.
12

---

Under review as a conference paper at ICLR 2023
Dong Yin, Raphael Gontijo Lopes. Jonathon Shlens, Ekin Dogus Cubuk, and Justin Gilmer. A fourier perspective on model robustness in computer vision. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' AAlhé-Bucc Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 13255-13265, 2019. URL tttps:tppo.. / http:///oooceeeeeeeee/eeeee/ecce nwwrips....... httpsssssss.p....pppee////// 305b57f6addd 00100003bb71 4908 6677 6c74c0053 0037700007700770000000
Abstract html.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, March 2021.
Xiaohan Zhu, Zhen Cui, Tong Zhang, Yong Li, and Jian Yang. Going deeper in frequeney convolu- tional neural network: A theoretical perspective. ArXiv, abs/2108.05699, 2021.
A RELATED WORK IN GREATER DETAIL
CNN sensitivity to Fourier frequency components: (Jo & Bengio, 2017) computed transfer accuracy of image classifiers trained on data preprocessed with various Fourier filtering schemes (c.g. train on low pass filtered images, test unfiltered images or vice versa). They found significant generalization gaps, suggesting that models trained on images with different frequency content learned different patterns.
(Guo et al., 2019) proposed algorithms for generating adversarial perturbations constrained to low frequency Fourier components, finding that they allowed for greater query efficiency and higher transferability between different neural networks. (Sharma et al., 2019) demonstrated empirically that constraining to high midrange frequencies did not produce similar effects, suggesting convolutional networks trained on natural images exhibit a particular sensitivity to low frequency perturbations.
(Yin et al., 2019) showed different types of corruptions of natural images (e.g. blur, noise, fog) have different effects when viewed in frequency space, and models trained with different augmentation strategies (e.g. adversarial training, gaussian noise augmentation) exhibit different sensitivities to perturbations along Fourier frequency components. (Diffenderfer et al., 2021) investigates the relationship between frequency sensitivity and natural corruption robustness for models compressed with various weight pruning techniques, and introduces ensembling algorithms where the frequency statisties of test image are compared to those of various image augmentation methods, and models trained on the augmentations most spectrally similar to the test image are used in inference. (Sun et al., 2022) designs an augmentation procedure that explicitly introduces variation in both the amplitude and phase of the DFT of input images, finding it improves certified robustness and robustness and common corruptions. (Bernhard al., 2021) investigated the extent to which constraining models to use only the lowest (or highest) Fourier frequency components of input data provided perturbation robustness, also finding significant variability across datasets. (Abello al., 2021) tested the extent to which CNNs relied on various frequency bands by measuring model error on inputs where certain frequencies were removed, again finding a striking amount of variability across datasets. (Maiya et al., 2022) analyzed the sensitivity of networks to perturbations in various frequencies, finding significant variation across variety of datasets and model architectures. All of these works suggest that model frequency sensitivity depends heavily on the underlying training data. our work began as an attempt to explain this phenomenon mathematically.
Our analysis of (linear) convolutional networks leverages prior work on implicit bias and representational cost of CNNs, especially (Gunasckar et al., 2018). There it was found that for linear mne-dimensional convolutional network where inputs and all hidden layers have one channel (in the notation of section 3, C = C1 _.... = CL-1 = K = 1) trained on binary linear classification task with exponential loss, with linear effective predictor 3, the Fourier transformed predictor 3 converges in direction a first-order stationary point of an optimization problem of the form
Implicit bias and representation cost of CNNs:
1 min プ 1812 such that y² 3T x > 1 for all
(A.1)
A generalization to arbitrary group equivaraiva CNNs (of which the usual CNNs are a special case) appears in (Lawrence et al., 2022, Thm. 1)- while we suspect that some of our results generalize
13

---

Under review as a conference paper at ICLR 2023
to more general equivariant networks we leave that to future work. For generalizations in different directions see (Lyu & Li, 2020; Yun et al., 2021), and for additional follow up work see (Jagadeesan et al., 2022). Our general setup in section 3 closely follows these authors', and our theorem 4.9 partially confirms a suspicion of (Gunasekar et al., 2018, $6) that "with multiple outputs, as more layers are added, even fully connected networks exhibit shrinking sparsity penalty on the singular values of the effective linear matrix predictor... ..."
While the aforementioned works study the implicil regularization imposed by gradient descent, we instead consider explicit regularization imposed by auxiliary E norm penalties in objective functions, and prove equivalences of minimization problems. In this sense our analysis perhaps more closely related to that of (Dai et al., 2021), which considers parametrized families of functions f(z, w) and defines the representation cost of a function ((x) appearing in the parametric family as
R(g) min [ [(x, w) - g(x) for all x).
(A.2)
While this approach lacks the intimate connection with the gradient descent algorithms used to train modern neural networks, it comes with some benefits: for example, results regarding representation cost are agnostic to the choice of per-sample loss function (in particular they apply to both squared
error and cross entropy loss). In the case where the number of channels C = C1 =... = CL-1
(but the number of outputs may be 1), theorem 4.9 can be deduced from (Dai et al., 2021, Thm. 3).
Lastly, while in this paper we focus on spatial frequency properties of image data, there is a large and growing body of work on the impact of frequency properties of training data more broadly interpreted. (Rahaman et al., 2019) gave a formula for the continuous Fourier transform of a ReLU network f: IR" + R. and showed in a range of experiments that ReLU networks learn low frequency modes of input data first. (Xiao, 2022) proves theoretical results on low frequency components being learned first for networks II, S - R products of spheres, where the role of frequency is played by spherical harmonic indices (see also (Xiao & Pennington, 2022) for some related results).
Perhaps the work most closely related to ours is that of (Hacohen & Weinshall, 2022) on principal component bias, where it is shown that rates of convergence in deep (and wide) linear networks are governed by the spectrum of the input data covariance matrix. (Hacohen & Weinshall, 2022) also includes experiments connecting PC bias with spectral bias (learning low frequency modes first, as in the preceding paragraph) and phenomenon known as learning order consistency. However, is worth noting that in their work there is no explicit theoretical analysis of CNNs and no consideration of the statistics of natural images in Fourier frequency space.
(Zhu et al., 2021; Pratt et al., 2017; Mathieu et al., 2014; Vasilache et al., 2015) all, in one way or another, leverage frequency space representations of convolutions to accellerate computations, e.g. neural network training. Since this is not our main focus, we omit a more detailed synopsis.
Other applications of Fourier transformed CNNs:
B EXPERIMENTAL DETAILS
B.1 DATASETS
Figure 3 illustrraes the frequency content of the image datasets used in this paper.
For CIFARIO we use canonical train/test splits (imported using (Marcel & Rodriguez, 2010)).
As described at (FastAl, 2019),
Imagenette is subset of 10 easily classified classes from Imagenet (tench, English springer, cassette player, chain saw, church, French horn, garbage truck, gas pump, golf ball, parachute).
We use the "full size" version of the dataset with standard (224- b24-by-224) ImageNet preprocessing.
We implement high pass filtering by passing each image x through the following preprocessing steps (before any other preprocessing other than loading a JPEG image file as a tensor): (i) take the DFT á, (ii) multiply with a mask m where maij = 0 if [1]. S some fixed threshold, and 1
"They also prove result for shallow ReI.U networks.
14

---

Under review as a conference paper at ICLR 2023
Figure 3: Top row: Standard deviations of image datasets (including those generated by the wavelet marginal model) along Fourier basis vectors: in the notation above, these are the VEjiocij (viewed in log scale as RGB images). The origin corresponds the lowest frequency basis vectors (i.e. constant images). Bottom row: Same data as the top row, further processed by taking radial averages F Eijioni (1, = r], and smoothing by averaging with three nearest neighbors on either side; shown in log-log-scale.
otherwise, (iii) applying the inverse DFT. For both CIFARIO and ImageNette, our threshold is 8 pixels. This means that while 25% of frequency indices are filtered out for CIFAR 10, only about 0. 0.13% are filtered for ImageNette. The motivation for this approach was to remove a similar amount of absolute frequency content in both cases; we also experimented with a threshold of 112 in the case of ImageNette, resulting in removal of 25% of frequency indices in both cases, and results of these experiments are shown in fig. 6.
We use the wavelet marginal model dataset generated using the implementation in (Baradad et al., 2021) details of this model are described in (Baradad et al., 2021, $3.3). The generated images are of resolution 128-by-128 they are preprocessed with downsampling to 96-by-96 and cropping to 64-by-64. For further preprocessing details we refer to (Baradad et al., 2021, $4).
All pipelines described in this paper implement the standard preprocessing step of subtracting the mean RGB value of the training dataset, and dividing by the standard deviation of the training set RGB values. Note that this does not flatten the variances of the image distributions in frequency space displayed in figs. 1 and 5 - in fact, it (provably) only impacts the variance of the Oth Fourier component, corresponding constant images. Ensuring that the variance in each Fourier component is (approximately) 1 would require the far less standard preprocessing step to each image æ consisting of (i) apply the DFT to get ât, (ii) subtract jú, where is the mean of the DFTed images in the training dataset (not just the mean of their RGB values)," (iii) divide by the standard deviation â of the DFTed images in the training dataset, and finally (iv) apply the inverse DFT. It should be emphasized that f and & have the same shape as x, e.g. (3, 32, 32) for the CIFARIO dataset. The only work we are aware of that implements such preprocessing on images is (Hacohen & Weinshall, 2022, see $4), though of course there may be others.
B.2 COVARIANCE MATRICES OF DFTED IMAGE DATASETS
In this section we provide further details on our computations of (co)variances and standard deviations of DFTed image datasets.
To compute the covariances Ejsce'ey' for fig. 4, we begin with a dataset of natural images, say X. We subtract its mean RGB pixel value (a vector RR3) and divide by the standard deviation of RGB pixel values (also vector in R3) is standard. We next apply the DFT to every image in X, to obtain DFTed dataset X. We then compute the mean fi of the images in X, not the RGB pixel values- - this is a 3 x H x W tensor, where H, W are the heights/width of the images in X (e.g., 32 for CIFARIO). 10). This mean is then subtracted from X to obtain a centered dataset. Next, we sample batches of size B, say , 2 from X (these are tensors of shape B x C x H x W). For each
batch, we subtract the mean, contract over the batch index and divide by B obtain an estimate for
'Here we assume that the lowest frequency component is at the origin, so the low frequency components are zeroed out and the high frequency ones pass through. $ Forr example, in the case of ImageNet these are the canonical [0.485, 0 0.456, C. 4.60 and [0. 229,
0. 224, 0 0.225] respectively.
"Euivalently j is the DFT of the mean training image.
15

---

Under review as a conference paper at ICLR 2023
230
03
(a)
(b)
Figure 4: Testing the assumption of eq. (4.16) on the CIFARIO dataset. (a) Average covariance entry norm [ (c, = r] plotted with respect to = [(i,j) (i', (b) Same as (a), except the i. part of the distance is computed modularly, i.c. on the discrete torus Z/H x Z/W instead of the discrete square {0,.... H - 1} x {O...., W - 1 For more details see appendix
Σ, say like so:
B
1
1
$ =
s (is A); explicitly Eiieetiy = (is -))
(an.jic
B
B b=1
b=1
(B.1)
Finally, we average over entire dataset's worth of batches to get our final estimate of Vt
To estimate the expectations El E[Eeeee Fy I [l i, (c, (']==
r]. we average absolute values E over all indices i' satisfying ((c, (c, "')"" The number of such entries
varies significantly with r, which why we have not explicitly written down the average. We compute "modular" distances, i.e. distances on the discrete torus, using the formulae
d'i, min min H mod H), H ((h h mod dww, w') min minn[(w w mo''modW WI, IW - ((w w/ mo)
(B.2)
and finally d((c,,, w). (d, h', w')) Vc- d²)2 d(h, h2)² + d(w, w²)2
In fig. 2a, we begin with dataset of natural images, say X. We subtract its mean RGB pixel value (a vector in R33) and divide by the standard deviation of RGB pixel values (also a vector in R as standard. We next apply the DFT to every image X, to obtain a DFTed dataset X. We then compute the standard deviation of the images X, not the RGB pixel values - this is 3 x x W tensor, where H, W are the heights/widths of the images in X (e.g.. 32 for CIFARI0).
B.3 GRADIENT SENSITIVITY IMAGES
To compute the sensitvity curves in figs. 1,5,7 and 8, we subsample 5,000 images from the underlying validation dataset the case of CIFARI0 and WMM use the entire validation dataset in the case of ImageNette. For each such image x, we compute the DFT â, and then backpropagate gradients through the composition & + 2 = r f(x). The result is a C' x H x W x K Jacobian matrix expressing the derivative
with respect to Fourier basis vectors. We take &g norms over the class index (corresponding to K) to obtain a C x H x W gradient norm image, with c, h, w component V vvf(() ( Finally, we average these gradient norms over the (subsampled in the case of CIFARIO and WMM) dataset.
Next, we average radially much as we did in fig. 4. Given an expected gradient norm image
P[[Va](x)) obtained as above, we further average over all indices eij such that v ?22 + j2 = Again, the number of such indices is highly variable.
To provide error estimates, for each set trained model weights and each image dataset, we compute radial frequency sensitivity curves in the paragraph above, apply post-processing consisting of:
Dividing the curve by its integral (to obtain probability distribution)"
10
this results in comparison between models that is scale invariant, that is, we want to compare the shapes of frequency sensitivity curves, their overall magnitudes
16

---

Under review as a conference paper at ICLR 2023
(a) VGG models of varying depth.
(b) VGG 11 models trained with varying levels of decay.
Figure 5: Radial averages V (x) (ile (| = r] of frequency sensitivities of VGG models
trained on ImageNette and its high pass filtered variant, post processed as discussed in appendix B.3. Bottom row: frequency statistics of ImageNette and its high pass filtered variant for comparison.
Taking the logarithm of the resulting probability distribution. This step is motivated by the empirical observation that the variance of Fourier transformed images follows power law with respect to frequency magnitude.
Smoothing by averaging with 3 nearest neighbors each side. This step is motivated by the aforementioned highly variable number of DFT frequency indices corresponding to a given radius, which means that some radius values correspond to average over far fewer samples which as a result has high variance. A possible alternative would have been to bin radii, thus averaging over DFT components with frequency magnitudes in a small interval. However, the automatic binning strategies we tried yielded bins that were too large, giving an undesirably low resolution view of frequency sensitivity curves.
We then repeat the entire pipeline above for 5 sets of model weights trained from independent random initializations, to obtain curves, and display the standard deviation of their y-values. For more details on our training procedures, see appendix B.5.
B.4 MORE EXPERIMENTAL RESULTS
Figure 5 shows radial frequency sensitivity curves from experiments training VGGs with variable depth and weight decay on ImageNette, with and without high pass filtering. Here we do see significant differences between models trained natural vs. high pass filtered images, including in the later case (small) local peaks in near the filter cutoff, however the effect of filtering is not nearly as noticeable in the CIFAR10 experiments of fig. 1.
Moreover, effects of depth and decay are not as dramatic in these experiments, although we do see the curves corresponding high depth/decay for VGGs trained on natural images dropping off most severely at high frequencies, and in the case of high pass filtered images deep VGGs are the least sensitive in the low frequency range (where the training images have variance).
17

---

Under review as a conference paper at ICLR 2023
Figure 6: VGGs trained on hmf-ImaaeeNette with a larger cutoff (removing 25% of frequency indices).
Interestingly, we see a range of frequency radii, roughly r E [10, 100), where the ImageNette frequency statisties exhibit significant noise around the overall power law pattern, and it does appear that all VGG models concentrate frequency sensitivity in this range, and more with greater depth/decay. It would be interesting to understand what sorts of natural image features contribute to the observed noise in the r E [10, 100) range, and if they are for some reason useful to the ImageNette classification task.
Figure shows a similar experiment with VGGs trained on (hpf-) ImageNNee,, but with high-pass threshold of 112, so that 25% of frequency indices are discarded. Here the differences between CNNs trained on natural and high pass filtered images are (not surprisingly) more dramatic, and the effect of decay on VGG 1 Is trained on hpf ImageNetee is especially pronounced. It is (at best) unclear whether the results for VGGs of variable depth trained on hpf-ImageNettt support hypothesis II. (depth).
Figure 7 shows radial frequency sensitivity curves from experiments training ResNets with variable depth and weight decay on CIFAR1O, with and without high pass filtering. The frequency sensitivity curves are clearly different when trained on natural images (where they drop off at the highest frequencies) versus high pass filtered images (where they have a "U""shape similar to those of the VGG models trained on high pass filtered CIFARI 10 in fig. 1). These observations seems somewhat consistent with hypothesis I. (data-dependent frequency sensitivity). However, the trends with depth and decay do not conform with hypotheses II. III. (depth, decay): is difficult to trends in the depth experiment, and in the decay experiment the frequency sensitivity curves seem to become more increasing as decay increases, rather than adhering the frequency content of the dataset. It is not immediately clear to the authors what causes this behavior - further investigation would be an interesting direction for future work.
Lastly, fig. 8 shows frequency sensitivity curves for AlexNets trained with alignment and uniformity loss (Wang& & Isola, 2020) on synthetic data generated by the wavelet marginal model (WMM) of (Baradad et al., 2021) with varying a parameter; to be specific, for simplicity we set = 3 in the power law Tely T These results initially surprised us: for all a the variance of the synthetic data is concentrated in low frequencies (fig. 3), with the level of concentration decreasing as increases (i.e. as a increases, the frequency curve of the synthetic data spreads out). However, for all AlexNets trained on WMM data the frequency sensitivity curves increase with frequency magnitude, with slope roughly increasing with respect od!
18

---

Under review as a conference paper at ICLR 2023
(a) ResNet models of varying depth.
Aeganry
Smpouny
(b) ResNet models trained with varying levels decay.
Figure Radial averages V (x)) &eigl [i,))) of varying depth (top row) and decay (middle row) trained on CIFARIO 10 and its high pass filtered variant. Post processing is as discussed in appendix B.3.
= r] of frequency sensitivities of ResNet models
66000
alpha 1.00e-02
alpha 1.00c-01
6.25
alpha 5.00e-01
alpha 1.00a+00
gradient sensitivity
-6.50
alpha 1.50e+00
alpha 2.00e 00
aipha 2.50e+00
-6.75
alpha 3. 3.00e+00
-7.00
-7.25
-7.50
-7.7
frequency radius
Figure 8: Radial averages E V.V..fe fz) ēesyl (i.j)] = r] of frequency sensitivities of unsupervised AlexNet models trained with alignment and uniformity loss on data generated by WMM models with varying a parameter. Post-processing as discussed in appendix B.3.
19

---

Under review as a conference paper at ICLR 2023
This result, which shows that CNNs trained with contrastive learning objectives respond quite differently to the statistics of their training data, admits a simple explanation in terms of sections and 4.
Indeed, the uniformity part of the objective encourages the set vectors
(f(x²) 0 1
(B.3)
to be uniformly distributed the unit sphere Sk-1 C IR Suppose now for the sake of simplicity that that the vectors 8 = (# are normally distributed and their covariance matrix E is diagonal, with diagonal entries of the form
Feij
(B.4)
1
Then the feature vectors f(1²t) =T are also normally distributed, with covariance matrix
6 Σ
+ 1 6
(B.5)
Here as above biy a K C matrix, so each o is indeed a K K positive semi-definite matrix, and in cases of interest where C & K it will have very low rank. Considering eq. (B.5), we see for example that if C < K and the 6iy are of roughly constant magnitude, then the covariance of the features ((**) will be dominated by the terms
1/ 5 D2y T
bg for small ij
(B.6)
making it impossible for the f((")) to be uniformly distributed on the unit sphere. It seems that perhaps the only way for such uniform distribution to occur for the magnitudes of the 6y to increase with the frequency magnitude ((t,j),, in such way as to offset the denominator |d| + [/1%. We do have a proof of this fact (it seems such a proof would have involve analysis of the functional form of the contrastive loss in (Wang & Isola, 2020), which we have not carried out), but it does offer one potential explanation fig. At the risk of being overzealous, the above discussion would suggest that
|gyl < |d|
+ 101%
(B.7)
ie. the norm of the gradient of f with respect to the ij-th DFT basis vector, follows power law in a, and indeed in fig. 8, where these gradient norms are plotted with respect to frequency magnitude on a log-log scale, see slope roughly increasing with
B.5 MODEL ARCHITECTURES, TRAINING PARAMETERS AND VALIDATION ACCURACIES
Recall that our CNNs are
ConvActually A CNN that closely approximates eq. (3.1), the differences being the addition of biases and ReLU non-linearities. This is accomplished by applying convolutions with 32 x 32 kernels (i.e., kernels of the same size as the input images) with circular padding. Myrtle CNN small feed-forward CNN known achieve high performance on CIFARIO obtained from (Page). This CNN has small kernels, ReLU non-linearities and max-pooling, as well as exponentially varying channel dimension.
VVG A family of 10 VGGs obtained from (Fu, 2017) and ImageNet VGGs from (Marcel & Rodriguez, 2010).
ResNet A family of CIFAR10 10 ResNets (He et al., 2016) obtained from (Team, 2021).
AlexNet small AlexNet adapted to contrastive training obtained from (Baradad et al., 2021).
Tables and 2 describe training hyperparameters. In all experiments we optimize using stochastic gradient descent (SGD) with momentum 0.9, using a "reduce on plateau" learning rate schedule where the learning rate is multiplied by 0.1 after "patience" epochs without 1% improvement in validation accuracy, where "patience" some fixed integer (i.e., a hyperparameter); we use patience= 20 throughout. This schedule proceeds until either minimum learning rate (in all of our experiments, 10 9) or a maximum number epochs is hit, at which point training stops. We use the Py Torch library (Paszke et al., 2019) cluster environment with Nvidia GPUs.
20

---

min Under review as a conference paper at ICLR 2023
All models are trained on CIFARIO except the ImageNette VGGs and AlexNets. The ImageNette VGGs are optimized as above, with the exception that we use distributed training on 8 GPUs (the batch size of 256 corresponds to batch of size 32 on each GPU). The AlexNets are trained using an unsupervised alignment and uniformity objective as described (Baradad et al., 2021, $4, &A); we the official implementation of (Baradad al., 2021). For CIFAR10 and ImageNette, same hyperparameters when training on natural and high pass filtered images.
the
For each model architecture and choice of hyperparameters, i.e. instance appearing in tables and 2, and each training dataset, we train 5 models from different random weight initializations. Efficiently training this many CNNs was facilitated by the excellent FFCV library (Leclere al., 2022).
arch. family
depth
batch size
initial Ir
decay
Conv Actually
1024
10
10 10*+linspace (-5,
-1, 4)
Myrtle CNN
N/A
512
10-2
10**linspace (-5,
-2, 10)
CIFAR VGG
11
256
10-2
10**linspace (-5,
-2, 10)
ImageNette VGG
11
256
1.250 x 10-3
10**1inspace (-5,
2, 3)
ResNet
512
10-1
10 10**1inspace (-5,
2, 10)
Table 1: Hyperparameters of CNNs of variable decay used in the experiments of section 5.2. all cases, the maximum number of epochs was 500.
arch. family
depth
batch size
initial Ir
max epochs
Conv Actually
1,2,4,8
1024
10-4
500
CIFAR VGG
11, 13, 16, 19
256
10-2
500
ImageNette VGG
11. 13, 16, 19
256
1.250
10-3
500
ResNet
9, 20, 56
512
10-1
200
Table 2: Hyperparameters of CNNs of variable depth used in the experiments of section 5.1. all
cases weight decay was 10-5
C L = 2: LASSO PARAMETER SHRINKING AND SELECTION
When G = 1 for all / and L = 1, we may simplify eqs. (4.10) and (4.13) to
1 Y 80 + 21/0/1
(C.1)
# N
where X and Y are as in section 4.1. The optimality criterion for eq. (4.10) becomes (see e.g. (Tibshirani & Wasserman))
(x 1 X
(C.2)
N
where Viol is the sub-gradient of the -noom::
= (i,)
if # 0 if 0 = 0.
(V))))s
(C.3)
[ [-11
Except for the AlexNets trained WMM data.
21

---

Under review as a conference paper at ICLR 2023
When À = 0 this again reduces to the unpenalized least squares solution êLS (XTX)-1X* -YY
and substituting this in eq. (C.2) we obtain
N (X Xo XT X AV = 0.
1
(C.4)
N
we again make the assumption that X "diagonal" as eq. (4.16), eq. (C.2) simplifies to
d Getsl for all cij,
Toiy )1, +
(C.5)
where strictly speaking
d(acip doeis
is subgradient as eq. (C.3). From this we conclude
= ors
A_ sign( (eij)s
if degg # 0 Goig =
Dcki
Tesp
for all cij
(C.6)
E [ir,s,cts
Tess" ULS.ct) Tesy
(the second case is equivalent to: if the LASSO solution eety 0, it must be that the least squares solution satisfies / I
In the case where sign(Oci)) sign(OLs,cij), obtain
Fess
particularly nice conclusion:
|eay = |
for all cij
(C.7)
Teij
Proposition C.8 Detendepen frequency sensitivity, == 2). With the notations and assumptions introduced above, the magnitude of the directional derivative of f with respect the cij-th Fourier component is linear in X with slope -1
Tell
If we again plug in the empirically determined power law observed in natural imagery, Toij R 7 6 eq. (C.7) becomes
A (1i) 151 for all cij-
(C.9)
7
Here, the sensitivity decreases monotonically with respect to both frequency magnitude and the regularization coefficient X. Note that compared to eq. (4.19) from section 4, eq. (C.9) implies greater shrinking effect when [eeyll < 1, and less shrinking when [eayl > 1. We conjecture that shrinkage due |éaig 1 is the dominant effect, due the initial distribution of weights in modern neural networks, which are often sampled from uniform or normal distributions with variance < (e.g., according to He initialization; He al., 2016).
D PROOFS
D.1 PROOF OF LEMMAS 3.7, 3.12 AND 4.4
Proof of lemma 3.7. For direct proof of the convolution part, see (Kiani et al., 2022, Lem. C.2).
We reduce to the "single channel" cases of these formulae (C² Ci-1 1), which take to be well known. For the purposes of legibility, in this proof we denote the DFT (eqs. (3.5) and (3.6)) by F.
For the convolution part we must apply the DFT to eq. (3.2). Let W We....d denote the single channel tensor obtained by fixing the input/output channels to indices c, d and similarly let Td,... be the single channel tensor fixing the input channel to index d. Then by interchanging the order sums
(w x) x) =
Σ
(Σ
W WenndRdm'n'
mttmm inn
Σ
Wemnddfdm'n
(D.1)
=i
Σ "(wee (We....d & Id...
12This remark applies generally to LASSO vs. ridge regression, and is perhaps most easily explained by comparing the derivatives of [z]] and ?
22

---

Under review as a conference paper at ICLR 2023
In other words, (w e).... Ed We We..... Id... Now linearity of the DFT gives
F((10 a )))...) Fl ra...) Σ F(we....))))) F(xa....
(D.2)
where on the right hand side we've applied the standard single channel convolution theorem. But this means
F(w * x)es = Σ F())oisa(()aa
(D.3)
desired.
Our proof of the Parseval identity is similar: we start with eq. (3.3), that is, (wTx)x
Eimm, 1mm- With notation above, we write
(w x)
Σ
Euf W
(D.4)
1,
where each term on the right hand side is an ordinary inner product of single channel signals. Taking the Parseval identity for these well known, we get
(w=x) z)x F(w)) F(w))
F(x),... Σ L,m,a
F(w) Imn
(D.5)
as desired.
Proof of lemmas 3.12 and 4.4. We proceed by induction on L. In the base case where lemma 3.12 is equivalent to Parseval's theorem eq. (3.9). So, suppose L > O. We may decompose as a convolution followed by linear CNN of the form eq. (3.1), say g. with one fewer layers. Explicitly, has weights W2..... wi and
f()) g(W1 * v.).
(D.6)
By inductive hypothesis, we may assume that
I-
g(wi x) g(wi x) = i L,T
(II
Wr (.. Wi x.)
(D.7)
[=1
Applying the convolution theorem eq. (3.8) obtain
W1 # 2aj = 10 11.... 2f...
(D.8)
completes the proof.
Proof of lemma 4.4. For each weight wt let wy denote the C₁ x Ct-1 matrix obtained by fixing the spatial indices of r ij. Unpacking definitions,
-1²--11 -1 ..... 20 +) = - ---
why Lij and so
Wi
tiI (iob-1 - w² 2). ΣΣ (w Jdd (wit) 16--... why Brs)
(D.9)
We can recognize the inside sum as performing a matrix product of of with vit -w why Bag- Since matrix multiplication is associative, just well multiply the vit first and then act on the vector æ.y. Thus
L-1 L-1 ........................... 2 ( (na 1
ΣΣ L-11 =6-1 ... ... od (aaz)a (D.10)
(wit wis
1.j d
Now recognize the right hand side (w+
166-1 in T it, as claimed.
23

---

Under review as a conference paper at ICLR 2023
D.2 PROOFS OF THEOREM 4.9 AND LEMMA 4.
Recall we aim to prove: the optimization problem
min C(((() 16--1_16-111111111-11 1 ( ) _ )==))==>>>>)) +
Σ
kodgle
(D.11)
equivalent to the following optimization problem for the product U...s -IT WL-t....y
min C
C(( ;n) (=1) - AL Σ (1
(D.12)
where the minima runs over the space of tensors 0 such that each matrix Big has rank at most min ,, CL-1, K). We proceed by a series of reductions; as first step we observe
min C(((())))))))))))) 1h-1, 1 w " (y"))= A "0
(D.13)
= min
min
L( &ny 1== (y" ) + A
kit
2
#4.84-
1,4,J
and hence theorem 4.9 will follow if we can prove
E( min 1 L
Σ
(D.14)
where the min on the right hand side over all Φ such that with uh--1 1 w6--1... w² ô. We can make life slightly simpler by noticing eq. (D.14) decomposes over the i index, and will follow from
1 (166,) min 7, Σ
bui for all i,
(D.15)
which we will show in lemma D.18 note that at this point we are arriving at a statement about norms of matrix products and can dispense with the baggage of i, indices and's. To formally state that lemma, we introduce a convenient definition.
Definition D.16. sequence of matrices A E M(1 X nı, .)....,A. AL M(mL nL. C) is composable if and only if
mi = n441 for I - I.....I.-1
(D.17)
In other words, A Ar is composable if and only if the product A A.. A, makes sense.
Lemma D.18. If E M(m x C) is a matrix with complex entries and T. E N is a non-negative integer, then
(I min [IA - min DAAE
(D.19)
where both minima are taken over all composable sequences of complex matrices Ai...., Ar. such that A₁ ... A. B.
We first deal with the elementary aspects of lemma D.18: will suffice show that whenever Ar ... A B,
(1
1
Σ A and that
(D.20)
L
(I
, Arl3
Σ
(D.21)
for some composable sequence Ai...., A such that A A1 = B. As noted in (Gunasekar et al., 2018) the second inequality of eq. (D.20) is simply the arithmetic- geeemeiie mean inequality E Ryn- Furthermore, we can obtain eq. (D.21) using the singular value decomposition of B: let B USV* where, letting min n). U Urr, m) and V E r
...
applied to |A, 2....... A
24

---

Under review as a conference paper at ICLR 2023
unitary and S diag( \1,
A1..... ................................ N,), where A 2 0 for all i. We may decompose B into L factors
like
L-1
B = (USt)
III st) (stV",
(D.22)
and by unitary invariance of the C2 (a. Frobenius) norm,
L-1
4-1 -sst
1 2 st
+
Σ
+
Istiv
Σ 1 +
1st
(D.23)
1=1
1=1
=
We now note that by definition 4.6,
(I) B|| S )² Σ Adl 2 and on the other hand
(D.24)
|st 1 E
that combining eqs. (D.23) and (D.24) gives eq. (D.21) for the composable sequence of eq. (D.22).
remains to prove the first inequality of eq. (D.20) this a special case of the non-commutative generalized Hölder inequality lemma 4.11. In fact will prove slightly more general statement to state it we need a couple more definitions:
Definition D.25. For (not necessarily square) complex matrix E M(m x n, C),
| == A
(D.26)
where A is the conjugate transpose of A.
The matrix [A] is Hermitian and positive semi-definite, and often referred to as the polar part of A. Given any Hermitian matrix H and complex number explicitly it can be defined as diag(A})U* where H = U (),)( H. We next define unitary invariant norms spaces of matrices. For technical reasons to be encountered shortly, we actually introduce fumilies of norms compatible with the natural inclusions M (m x n, C) C Mmm' n', C) for m' m, n' 2
may form the matrix /1;;
diagonalization of
Definition D.27 (ef. (Bhatia, 1996, SIV)). A compatible family of matrix norms is function
||-|::
II m.nEN
M(m x n, C) - Rgo
(D.28)
such that
(i) the restriction of ||-|| to M (m x n, C) is a norm (in the sense of functional analysis) for all m, E N, and
(ii) whenever m 2 m, n' 2 and à: M(m n, C) M(m x n', C) is the "upper left block inclusion" sending
+ 0 0
(D.29)
we have [|((A)]I = ||||.
compatible family of norms is unitary invariant if and only if for any A M(m x n, C) and any unitary matrices U E (mm) and V e (())
JUAVT ||A|]]
(D.30)
We will show below that for any p > 0 the Schatten p-norms form a unitary invariant compatible family.
F.gg in the polar decomposition (Higham, 2008, $8).
25

---

Under review as a conference paper at ICLR 2023
Lemma D.31. B M(m n, Cn is matrix with complex entries, Ai...., AL is composable sequence of complex matrices such that Ag...A B and Σ, - where PI...., PL > are positive real numbers, then for every unitary invariant compatible family of norms ||
B| $ III I|
(D.32)
We note that this non-commutative generalized Hölder inequality is tton-commutative" since we work with products of matrices opposed inner products of vectors, and "generalized" since consider lp exponents where pp
p; > 1. To be specific, lemma 4.11 11 is the case of lemma D.31
where the unitary invariant compatible family of norms || consists of the C₁ norms and p4 for all i. Here we are implicitly using the relationship between Schatten norms
| (IIAA111))* for all A E Mm n, C).p> 0.
(D.33)
As mentioned in section 4, when L = 2 lemma D.31 is (Bhatia, 1996, Exercise IV.2.7). In the case of Schatten norms, it is essentially derived in the course of the proof of (Dai et al., 2021, Thm. 1). Below, we solve (Bhatia, 1996, Exercise IV:2.7) and show that the case L 2 follows by induction." !5
We first address a subtle difference between lemma D.31 and the setup of (Bhatia, 1996) (and indeed most work on matrix analysis). (Bhatia, 1996) considers square matrices throughout, whereas in lemma D.31 we allow all matrices to be rectangular - this is essential in our applications, since neural networks have variable width (even if made CNNs of section 3 "constant width" by requiring C C2 Thankfully, there simple trick that allows us reduce to the case of square matrices. Say A, E Mmm x ni) as in definition D.16, and let
= Ct.11, the first and last layers would still change width in general).
N == max(mm.......... m., R1, : n
(D.34)
Since N my nu by definition, for each matrix A we may define new block diagonal matrix
A 0
0
A
(D.35)
(that is, we push A, to the top left comee). Note that by definition D.16 and the hypotheses of lemma D.31 m = m,," n = nn and a straightforward inspection of the mechanics of block diagonal matrix multiplication shows
B 0 0
ÅL A ... À
B
(D.36)
Now AI....,A, As and B are all square, and to reduce the square case it will suffice to argue that
|| 1 || for all and |||||||| B|[||]
(D.37)
Since by hypothesis ||=|| is a compatible family of unitary invariant norms, it will suffice to show that
[A pcc
0
0
AA.
(D.38)
0
and this follows from the identities
A
0
A
0 0
A
0 0
Н
0
[== 0 0
0
=
and
0
0
=
0
(D.39)
valid for any complex matrix A, Hermitian matrix H and complex number z, the proofs of which we omit.
Before continuing with the proof of lemma D.31, we pause to verify that Schatten norms are indeed a unitary invariant compatible family. In doing so we prove lemma that will be of further use in the sequel.
14 "Which is simply the sum of the singular values (sometimes called the frace norm). We beg forgiveness for posting a Springer GTM exercise solution on the internet.
26

---

Under review as a conference paper at ICLR 2023
Definition D.40. A compatible family of guage functions is a function Φb [I, R -> Rz0 such that
(i) for each n E N the restriction of d R is norm (in the sense of functional analysis) and
(ii) whenever n' 2 π and IR + EF is the inclusion mapping (#1...., Fn) Zn. (I.....;
..... . 0). we have (((()) (z))
A compatible family of guage functions is symmetric if and only if for each E N the restriction of to IR" is invariant under the action of matrices of the form PD where P is permutation and D diagonal, with diagonal entries in {=1}.
Lemma D.41 (cf. (Bhatia, 1996, Thm. IV.2.1)). There is a natural one-to-one correspondence between unitary invariant compatible families of matrix norms and symmetric compatible families of guage functions.
Proof. Given unitary invariant compatible family of matrix norms || a symmetric compatible family of guage functions & can be defined using the maps
diag
M(n x C) 1-11
R
20:
(D.42)
compatibility of Φ comes from compatibility of ||- and the identity "diag or = o diag" (suitably interpreted), and symmetry of & follows from the identity diag (Dgg) = (PD) diag(r)(PD)) for matrices PD as above, the fact such matrices PD are unitary and unitary invariance of ||
Conversely, given symmetric compatible family of guage functions & one may define unitary invariant compatible family of matrix norms ||-|| as || == (s(()) where s(A) denotes the singular values of A. Compatibility comes from the fact that the singular values of block diagonal matrix
A1
0
A2
are the concatenation of s(A)) and sA22,, and unitary invariance follows from the fact that singular values unitary invariant up to permutations (and & is symmetric). The proof that the maps || M (m x n, C) + 2 are indeed norms is as in (Bhatia, 1996, Thm. IV.2.1).
It can be verified that these maps mutual inverses we omit this final step.
Corollary D.43. For any > 0 the Schatten p-norms form a unitary invariant compatible family of matrix norms.
Proof. By definition, || = =E, (AA)) i.e. the lp norm of the singular values of A. By lemma D.41 it suffices to show that the -p-norms form a symmetric compatible family this is straightforward and omitted.
We now resume proving lemma D.31, first in the case L = 2 (later we will prove the general case by induction). Recall that at this point we have reduced the case where all matrices in sight are x n for some fixed E N. so in particular we are dealing with fixed unitary invariant norm (no further need for compatible families). By the above lemma, ||A|| (ss)))) for some symmetric guage function + for all A E M( x n. C). By (Bhatia, 1996, Thm. IV.2.5),
A2) <n (A))'s(A2))
(D.44)
where <.m denotes weak submajorization. Now the "strongly isotone" property of the symmetric guage function & implies
((s(AAA))") < ((s(AA)'s(A)))))
(D.45)
We need a generalized Hölder inequality for symmetric guage functions.
Lemma D.46 ((Bhatia, 1996, Ex. IV.1.7)). PL, > 0 and Pı
1 1 then for every symmetric
Pa y.
guage function + : R" R2o and every y RR" we have
(abs(( - )² < (
(D.47)
where abs denotes the coordinatewise absolute value.
27

---

Under review as a conference paper at ICLR 2023
Proof. Apply the regular Hölder inequality (Bhatia, 1996, Thm. IV.1.6) to the vectors
abs(2) y = abs(y)" (coordinatewise r-th powers) with the exponents pi = p1/r, p2 = P2/1
(note that P1 P2
P2 1) to obtain
((abs(r-))) = ( (abb((--))) -)) - (abs(i))) A ((bbs(ū)))) ((abs(x)))) m o (abs( yy) n3 )²
(D.48)
where in the last equality we have just used the definitions of ã, G. pi and p2. Taking r-th roots completes the proof.
Now applying lemma D.46 eq. (D.45) gives
(ss(A1A2))) I (ss((s) I (((
(D.49)
(the first inequality is just taking r-th roots of eq. (D.45), the second applying lemma D.46). Using the identity (((A))) s(A),, we finally obtain
| P.
A2 12 Pz
(D.50)
which is lemma D.31 when L = 2.
Now suppose and assume by inductive hypothesis that lemma D.31 holds for all smaller values of L. Define
(D.51)
q P
(note that
1 + 1/4 7). pc
..). By the L = 2 case of lemma D.31
A| (Ar-1... (A))I= < |||
PL ||| -.. A.Il
(D.52)
and by inductive hypothesis
A 1 < II i= 1 11
(D.53)
28


Reviews:
[{"review_id": "xcqJQd16YmW", "reviewer": "Reviewer_pf5x", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors study the sensitivity of convolutional networks (CNNs) to perturbations in frequency components of input images. The authors consider linear convolutional networks. By applying the Fourier transform, in some simple settings, the problems can be reduced to,  essentially, a linear regression (or lasso). Then, tools from linear models (e.g. eigen-decomposition) can be applied to compute the closed-form predictor, which can be used to analyze how sensitive the linear predictor is to perturbation in different Fourier modes. ", "summary_of_the_review": "update \n\nI thank the authors for improving the paper. In particular, the current form of theorem 4.9, if correct, is much stronger than the previous version. As such, I increase my score accordingly. However, I am not comfortable accepting the paper at the moment for the reasons below. 1. the paper is still in the linear convolutional setting, aka, Tibshirani, Gunasekar, etc., though the improvement is not as obvious as the previous version. 2. There are some significant changes in the main text of the paper, as well as the main result Theorem 4.9. Because of so, I would prefer the paper to go through a new review process with the proof of Lemma 4.11 carefully checked. \n\n\n------------------------------\n\n\nOverall, the paper has several interesting observations. However, the contribution is incremental and does not go beyond existing work much, e.g., Tibshirani, Gunasekar, etc. The setting only covers some simple cases of linear convolutional networks. The obtained insights (e.g., sparsity, the predictor is more sensitive to low-frequency mode) seem not that new and can be derived from (deep) linear models. ", "strength_and_weaknesses": "# Strength \n\n- The problem studied in this paper is quite interesting. \n- The paper is relatively easy to follow. \n\n# Weaknesses\n\n- The setting is quite simple. The authors study linear convolutional networks, which is not that different from linear models. \n\n- Even for linear convolutional networks, the analysis is only restricted to a couple of simple cases (Theorem 4.9). E.g., channel size all equal to 1 or the depth L\\leq 2. The general, more practical setting (e.g., multiple channels), which required new ideas beyond basic Fourier transforms, is not covered in the paper. \n\n- The reliance on Fourier transform also requires the kernel size ( 3 by 3 in practice) to be the same as the image size (e.g., 32 by 32 for Cifar 10). This restriction reduced the interest and relevance of the approach. Finding minimizers in the frequency domain  \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pQUGu8vpRgs", "reviewer": "Reviewer_yP96", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "It is unclear what concrete contributions of this paper are. The paper does have quite a lot of equations, but it is hard to say that the derivations are upon a good problem. Experiments are severely lacking.", "summary_of_the_review": "I vote for rejection because the significance of the analysis is low.\n", "strength_and_weaknesses": "Strength: lots of derivations.\n\nWeakness: lack of experiments and competing results.\n\nOne fundamental issue: it has been long known that CNNs train better with whitened images -- which is equivalent to equalizing the images in the frequency domain beforehand. There is no room for sensitivity once proper preprocessing is done. The analysis of this paper seems irrelevant and may be in a wrong direction.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "SOhhSRP_TNY", "reviewer": "Reviewer_bWYa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This work proposes a theoretical explanation for the observation of imbalanced frequency sensitivity in CNNs. The paper studies linear CNNs under weight penalties, and derives justification for the dependence of such CNNs' frequency sensitivity on the distribution of power in the data spectrum. Two empirical experiments involving actual non-linear CNNs trained on CIFAR are provided to support some predictions of the proposed theory, namely that adding more layers and increasing weight decay coefficient will both emphasize frequency sensitivity of CNNs to lower frequency components.", "summary_of_the_review": "The paper provides a theory explaining how linear CNNs under certain assumptions and weight penalties tend to have an inductive bias reflecting the spectral composition of the input data. However, the very restricted theorem, and lack of extensive empirical experiments supporting the theorem and the main claim, limits the paper’s significance and validity.", "strength_and_weaknesses": "**Strengths**\n\nThe paper posits an interesting theorem, and motivates it sufficiently well with some prior evidence. The writing is mostly clear, although the format is wrong. While I don’t think the main claim of the paper is correct, the much more restricted claim that is actually proved is interesting and can help explain some observations in practice.\n\n**Weaknesses**\n\nI have the following concerns/questions about the paper:\n\n1) The main result in theorem 4.9 concerns a very specific case of linear CNNs, and as the paper itself points out is a quite straightforward extension of Tibshirani 2021. Now this in itself is not an issue, what becomes an issue is that the paper does not go much beyond this extension, for example considering the effect of size-limited filters and also the more complicated case of simple ReLU non-linearities, which would make the theory much more substantial.\n\n2) The theoretical results really show the sensitivity caused by the norm penalties, rather than the CNN itself, since removing the penalties (lambda=0) will result in a “non-sensitive” CNN. In other words, the simplification of CNN structure has stripped it off its many inductive biases, and as a result exposing the inductive bias due to norm penalties, which are well-known already (although not explicitly discussed in the spectrum as far as I know). So it is misleading to claim “CNNs inherit frequency sensitivity from image statistics” where the theory only shows this happening due to norm penalties when CNN is extremely simplified.\n\n3) As the paper itself points out in Section 6, the empirical experiments only on a low-frequency prominent dataset (CIFAR) do not provide any evidence for the main claim of the paper: “CNNs inherit frequency sensitivity from image statistics”. Repeating these experiments on datasets where different frequency bands are prominent (which are trivial to construct) are a strict requirement to support the main claim. Also, the empirical results should always report error bars to show statistical significance of the results (no figure currently shows error bars).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject