Tuning Frequency Bias in Neural Network Training with Nonuniform Data
Authors: Annan Yu
Yunan Yang
Alex Townsend
Venue: ICLR 2023 poster (2023)
Keywords: frequency bias
neural networks
training
nonuniform
Sobolev norms
Neural Tangent Kernel

Abstract: Small generalization errors of over-parameterized neural networks (NNs) can be partially explained by the frequency biasing phenomenon, where gradient-based algorithms minimize the low-frequency misfit before reducing the high-frequency residuals. Using the Neural Tangent Kernel (NTK), one can provide a theoretically rigorous analysis for training where data are drawn from constant or piecewise-constant probability densities. Since most training data sets are not drawn from such distributions, we use the NTK model and a data-dependent quadrature rule to theoretically quantify the frequency biasing of NN training given fully nonuniform data. By replacing the loss function with a carefully selected Sobolev norm, we can further amplify, dampen, counterbalance, or reverse the intrinsic frequency biasing in NN training.

Published as a conference paper at ICLR 2023
TUNING FREQUENCY BIAS IN NEURAL NETWORK TRAINING WITH NONUNIFORM DATA
Annan Yu
Yunan Yang
Alex Townsend Comell University
Cornell University ay2628corne11.. edu
ETH Zürich yyn 41 01 @0@ com
townsend@cornell.. edu
ABSTRACT
Small generalization errors of over-parameterized neural networks (NNs) can be partially explained by the frequency bias phenomenon, where gradient-based al- gorithms minimize the low-frequency misfit before reducing the high-frequency residuals. Using the Neural Tangent Kernel (NTK), one can provide theoretical analysis for training where data are drawn from constant or piecewise conssantt probability densities. Since most training data sets are not drawn from such distri- butions, we use the NTK model and a data-dependent quadrature rule to theoret- ically quantify the frequency bias of NN training given nonuniform data. By re- placing the loss function with a selected Sobolev norm, we can amplify or dampen the intrinsic frequency bias in NN training.
INTRODUCTION
Neural networks (NNs) are often trained in supervised learning on a small data set. They are ob- served to provide accurate predictions for a large number of test examples that not seen during training. A mystery is how training can achieve small generalization errors in an overparameterized NN and so-called "double-descent" risk curve (Belkin et al.. 2019). In recent years, potential answer has emerged called "frequency bias." " which is the phenomenon that in the early epochs of training, an overparameterized NN finds a low-frequency fit of the training data while higher fre- quencies are learned in later epochs (Rahaman et al. 2019 Yang & Salman, 2019 Xu 2020). In addition to generalization errors, it is often useful to understand the convergence rate for each spec- tral component of the data mismatch to study the robustness of the NN under noises. Currently, frequency bias is theoretically understood via the Neural Tangent Kernel (NTK) (Jacot et al. 2018) for uniform training data (Arora et al., 2019: Cao et al., 2019 Basri et al. 2019) and data distributed according to a Sexcewise-constane probability measure (Basri et al. 2020). However, most training data sets in practice are highly clustered and not uniform. Yet. frequency bias is still observed during NN training (Fridovich-Kel) et al.) 2021), )) even though the theory is absent. This paper proves that frequency bias is present when there is nonuniform training data by using a new viewpoint based on a data-dependent quadrature rule. We use this theory to propose new loss functions for NN training that accelerate its convergence and improve stability with respect to noise.
An NN function is a map N : Rd + IR given by
((x)) WNz a (W (WN--10 (-... (W20 (Wix + b2) +.... + b -1) + bNZ-
where W; E R.mxxm-11 are weights, ma = d, b, E Tm are biases, and N2 is the number of layers. Here, is the activation function applied entry-wise to vector, i.e., a(a); = oa,)) In this paper, we consider ReLU NNs, which are NNs for which a is the ReLU function given by ReLU(t)= max 0). Since ReLU(ad) aRRLU(()) for any a > O, we assume that the input of the NN is normalized so that x gd-1 To introduce continuous perspective, we assume that there an underlying target function 9 gd-1 F and the training samplers x, follow distribution (x)). Given training data {(x, y4) ) drawn from g. where x; E sd and = g(x;), our goal is to train the NN, in a way that robust when the sampling of y, from g(x;) is contaminated by noises, so that N uniformly approximates g on gd-1, One standard training procedure is a gradient-based optimization algorithm that minimizes the residual in the squared L (d(dp) norm, i.c.,
Ad {
Aa
4 W))
Jg--1 l9(x) - (x;; d)( ~
Σ 1y: - N(x;; W)l.
(1)
2
2n

---

Published as a conference paper at ICLR 2023
where Ad is the Lebesgue measure of the hypersphere S and W represents the weights and bias terms. Similar to most theoretical studies investigating frequency bias, we restrict ourselves to 2- 2-layer NNs (Arora et al. 2019: Basri et al., 2019 Su & Yang 2019 Cao et al. 2019).
To study NN training, it is common to consider the dynamics of ((W) as one optimizes the coef- ficients in W. For example, the gradient flow of the NN weights is given by dW
a+ at aw Define
the residual 2(x; W) = 9(xx- -x(x W). Applying gradient flow with the population loss gives us
dz(x; W) - Ad
{ K(x,x's W)a(x'; W)du(x'),
(2)
dt
ge-1
where K Kxx, x'; W) = ( ( @NIx(W) Under the assumptions that the weights do not oW
BW
change much during training. one can consider the NTK given the underlying time-independent
distribution of W, i.e., K (x,'xx)) x') = Ew ((x [)] (Du et al. 2018). Based on eq. (2).
one can understand the decay of the residual by studying the reproducing kemell Hilbert space (RKHS) through a spectral decomposition of the integral operator L defined by (Cz)(x)
Most results in the literature require y((x) be the uniform distribution over the sphere so that the cigenfunctions of L are spherical harmonics and the eigenvalues have explicit forms (Cao al., 2019; Basri et al. 2019 Scetbon & Harchaoui] 2021). These explicit for- mulas for the eigenvalues and eigenfunctions of 2 rely on the
K (x, xx)==("'ddjxxx""
theorem, which provides a formula allowing one to express an integral over hypersphere by an integral over an interval (See- ley] 1966). The frequency bias of NN training can be explained by the fact that low-degree spherical harmonic polynomials are eigenfunctions of L associated with large eigenvalues (Basri et al. 2019). Thus, for uniform training data, the optimization of the weights and biases of an NN tends to fit the low-frequency components of the residual first.
When y(() (x) is nonuniform, it is difficult to analyze the spectral properties of L and thus the frequency bias properties of NN training. Since the Funk-Hecke formula no longer holds, there are only a few special cases where frequency bias is understood (Williams & Rasmussen 2006 Sec. 4.3). Although one may derive asymptotic bounds for the eigenvalues (Widom) 1963] I 1964] Bach & Jordan 2002), it is hard to obtain formulas for the eigenfunctions, and one usually relies on numerical approxima-
tions (Baker) 1977). For the ReI.U-based NTT,, [Bsri et al. (2020) provided explicit eigenfunctions assuming that the p(x) is piecewise constant on S', but this analysis does not generalize to higher dimension. To study the frequency bias of NN training, one needs to understand both the eigenval- ues and eigenfunctions of L, and this remains a significant challenge for a general p(x) due to the formula.
absence of the
To overcome this challenge, we take a different point-of-view. While it is standard to discretize the integral in eq. ( using a Monte Carlo-like average, we discretize it using a data-dependent quadrature rule where the nodes are at the training data. That is, we investigate the frequency bias of NN training when minimizing the residual in the standard squared 1,2 norm:
1 f 2 ga- 19(x) - (xx: w)
1 Eelye crl: 1ali--Wi - W)
(W)
(3)
where CJ, .I....,, Cn are the quadrature weights associated with the (nonuniform) input data XI....,X, Xx- If X1, xi...., Xn, are drawn from a uniform distribution over the hypersphere, then one can select c, = As/n for 1 < < n;; otherwise, one can choose any quadrature weights so that the integration rule is accurate (see section 4.2) If xj...... X., are drawn independently at random from j(x),, then it is often reasonable select G 1/(np(x,)), where du(x) = p(x)dx. While Ct... Cr de- pend on X1, X,, the continuous expression for क5 (W) is always unaltered eq. ( Therefore, we can use the Funk-Hecke formula to analyze the eigenvalues and eigenfunctions of E defined by (x) = Iga K <xx x') xx)=(x'd'x',, revealing the frequency bias. We address that by choos- ing eq. (3) as a loss function instead of eq. (I), are enforcing the frequeecy bias of NN training. whereas eq. (1) does not ensure such spectral property (see Section for an illustration).
To further tune the NN frequency bias during training, we also propose to minimize the residual in a squared Sobolev H' norm for a carefully selected s E R. Unlike the La norm (the case of s 0), the H² norm for F 0 has its own frequency bias. For s 0. H² penalizes high frequencies more than low, while for s < 0, low frequencies are penalized the most. We implement the squared H² norm using quadrature rule, which induces a different integral operator L.. We
2

---

Published as a conference paper at ICLR 2023
analyze the cigenvalues and eigenfunctions of E. and consequently, the frequency bias in the NN training using the Funk- formula. Given our new understanding of frequency bias, we select that the Hd norm amplifies, dampens, counterbalances, or reverses the natural frequency bias from an overparameterized NN training.
Contributions. Here
three main contributions to analyzing and tuning NN frequency bias.
(1) From our quadrature point-of-view, we analyze the frequency bias in training a 2-layer overpa- rameterized ReLU NN with nonuniform training data. In Theorem we show that the theory of frequency bias in Basri et al. (2019) for uniform training data continues to hold in the nonuniform case up to quadrature errors. In Theorem
3
we provide control of the quadrature errors.
(2) We use our understanding of frequency bias to modify the usual squared T,² loss function to a squared 41 norm. By selecting s, we can amplify or dampen the intrinsic frequency bias in NN training, accelerate the convergence of gradient-based optimization procedures, and separate out noises of particular frequencies.
(3) A potential issue with the H norm is the difficulties of implementing with high- gigh-dimensional training data. Using an image dataset of dimension 28 784. we show how use an encoder- decoder architecture to implement a practical version of the squared H norm loss and adjust the frequency bias in NN training to suppress noises of different frequencies (see Figure
PRELIMINARIES AND NOTATION
For d > 1, let g: s IR be square-integrable function defined gd-1, The function g can be expressed in a spherical harmonic expansion given by
N(d.E)
g(x) = Σ Σ
(x)
ge.p = / / g(x))e
(4)
p=l
where Ve.p is the spherical harmonic basis function of degree l and order p Dai Xu 2013
Here, (d, E) is the number of spherical harmonic functions of degree E so that M(d, = I and
(d, E) (2E+d- ())22))((+--2))) for e' 1. The set (Y==)e20.1spSNidd is an orthonormal basis for F([+1]r(d-1)
(8d Let Hd be the span of Ndd.), and II = ① H.S. be the space of spherical harmonics of degree L.
Given distinct training data {x,} ). from Sd-1 and evaluations y; g(x)) for < i S our goal to understand the intrinsic frequency bias behavior of training a 2-layer ReLU NN given by
m a Re.LeL x 6,),
N(x)
ReLU(t) = ma)
(5)
where m is the number of hidden neurons, Wi..... Wm and a1...., 4m are weights, and bi...., bm are biases. We use the same setup as in (Basri al. 2020): assuming that (1) Wi,...y Wm are initialized independently and identically distributed (i..d.) from Gaussian random variables with covariance matrix ILI, where ε. 0, (2) the biases are initialized to and (3) 01.... am are initialized i.i.d. as +1 with probability and -1 otherwise, and {a,) are not updated during training.
We use a poudient-basede optimization scheme to train for the weights and biases and aim to minimize the residual defined by symmetric positive definite (SPD) matrix P, which can be written as
1
Pp W) / (y u) T P(y-uu -),
(6)
For example, we have P Agn 'I in eq. ( and P diag(er....... c,) in eq. (3). Recall that W represents all the weights and biases of the NN. Given the loss function, we train the NN based on the gradient descent algorithm:
where = (g(x)),... )x.)).,(x,)))) T and u = (N(x)) ((.,))..,NN .(x)))
Hp ( + - wr(k) 1I Ow,
00p
b, + (k) = -1 ab,
15r m, (7)
where lo is the iteration number and n > is the learning rate. The matrix P induces an inner product (E.C)p e Pc, which leads to fintt-ddimensional Hilbert space with the
3

---

Published as a conference paper at ICLR 2023
norm P (E. E)p. Given matrix A R define its operator norm ||A||p
supgER". [ AEllp. We also define a finite positive number that depends on P:
PP E
5 pp//pppi/g
Mp= sup Ellp $E ;=
sup (ER"\10)
sup (ERT\())
sup
PC (8)
( (TP1/2p1/2(
ÇER", p=
Note that by the third expression in eq.
8
we also have Mp= Tpp=I|a 1|/11/1/11/
P
Furthermore,
define the matrix T
E _ax= by
x x
(x, x, 1)(x arccos xx)x)
Hij E (0
x 2,0
4
Note that due to the introduction of the biases, H is slightly different than the one in (Du et al, 2018 Arora al. 2019). In fact, in contrast with (Du al., 2018), H defined in eq. (9) is SPD
regardless of the distribution of the training data, as shown in the supplementary material.
Proposition x1,...., "as....xxp, Xn are distinct, then H in eq. SPD.
As a consequence of Proposition 1 the matrix H has positive eigenvalues, which we denote by >n-1 2 Xo 0. In fact, let A ...
Then, H is self-adjoint in
(I2", :) (see appendix A) and can be diagonalized as
HPP = = --1pp///2/>pp///pppppp
P AVP1/2
(10)
where p1/22 = V-1AV is SPD and therefore diagonalizable. One can view o as coming from sampling continuous kernel 1 gd-1 g IR given by
((x: y) + 1)( arccos( (x, y)))
K (x) K
( ((x,))
(11)
4T
where (-.-) is the e inner- mondurp..duct... The eigenvalues and cigenfunctions of K are known explicitly via the Funk-Hecke formula (Basri et al. 2019):
K (Y), ( (x),
1 0.
(12)
The explicit formulas for μi with é > are given in the supplementary material. We find that L
for all l and μe is asymptotically Ol--d) for large e (Basri et al. 2019 Bietti & Mairal 2019).
3 TRAINING CONVERGENCE WITH A GENERAL LOSS FUNCTION
Given the NN model in eq. (5) and a general loss function &p in eq. (6) we are interested in the convergence rate of NN training. We study this by analyzing the convergence rate for each harmonic component. We start by presenting a convergence result that holds for any SPD matrix P. It says that up to an eтrоr e, which can be made arbitrarily small by taking λ small enough and large enough, the residual of the NN at the kth iteration approximately (I 21/HP))
Theorem 1. In eq. (5), suppose that Wi...., W. initialized i.i.d. from Gaussian random vari- ables with covariance matrix I,",, bh.-..,hh, bm are initialized to zero, and 01,..., am are initialized ii.d. as +1 with probability 1/2 and 1 otherwise. Suppose the NN is trained with training data (x1, v)) for S S n, loss function 4p in eq. (6) for a SPD matrix P, and the training procedure the gradient descent update rule eq. 77 with step size n. Let N2. be the NN function after the kth iteration and u(k)
(X)......... .No (x)), where No is the initial NN function. Let an accuracy goal 0 E a probability of failure 0
L, and a time span T 0 be given. Then, there exist consiants C1, C2 > 0 that depend only on the dimension d such that 0 < 1 S 1/(2Mmm)
(see eq. 8 C1cMp' V8/n, and satisfies
Man log(n/d) m 2 C22 2=22 (> =
MMn'
(20
2202+12122))
(13)
2²
then with probability 2 - 5, we have
y-u(k) = (I 2n P) + E(k),
OSKST.
(14)
Here, 0 follows eq. 9 y y (g(xx))...,xxxx))) (xx.)) and No is the smallest eigenvalue of H.P.
4

---

Published as a conference paper at ICLR 2023
We defer the proof to the supplementary material, which uses techniques from (Su & Yang 2019) The main idea behind the proof is that I 27 is close to the transition matrix for the residual y (() when m is large. By taking A small, we can control the size of u(0) and therefore obtain y y- (() R (I
u(0))= ~ (I 2y) y. As 1 decreases, the gradient descent algorithm gets closer to the gradient flow algorithm (Du et al. (018), which allows
more accurately quantity the frequency bias (see section Ap. For a fixed n. if is an eigenvector associated to Ao. then [I 2)
exp(- log((1 21y 1)) l| where log((1 2012a) is
(1//n). which is the case of eq. (T). then as shown in (Su & Yang. 2019 Thm. 2) and (Nguyen et al. 2021), we expect that
called the convergence rate (Su & Yang 2019). If we assume Amin (P)
- oc, there exists labeling y on the training data, depending on n, that makes the convergence rate vanish. However, as suggested by (Su & Yang) [2019] Cao et al.,
An + as n + oo. Hence,
2.19) for a fixed bandlimited target function g. its convergence rate in early epochs stays constant
as 71 co. We make similar observations in section
4 FREQUENCY BIAS WITH AN L2-BASED LOSS FUNCTION
The mean-squared loss function in eq. corresponds to setting c; = Aa/nn for S n in eq. (3)
When μ is uniform, eq. ① and eq. (3) equivalent; when μ nonuniform, we introduce quadra- ture rule with nodes X1:.. X,, and weights cI,.... On to approximate the L loss function eq. (3)
The weights are selected that for low-frequency functions f : - R, the quadrature error
-gd-1 =S0-. f(x)dxx - Σ Exf(x)
Ea(f) =
(15)
==1
relatively small]] [ reasonable quadrature rule has positive weights for numerical stability and A₂ so that it exactly integrates constants. The continuous squared 2 loss function based on the Lebesgue measure is then discretized be the square of a weighted discrete which is SPD as the q's are positive. For vector IR", we write || l| v Dev and set Craxs maxigign (c:).
satisfies Σe
l norm (see eq. (3). Hence, we take P De diag(ct,.....
We now apply Theorem I to study the frequency bias of NN training with the squared L loss eq. 3 We state these results in terms of quadrature errors. Recall our continuous setup where we assume that the training data is taken from function g : gd-1
E so that y; g(x,) for < i < We further assume that g is bandlimited with bandlimit L where g = go + ... + 9L and ge E Hy for 0 E T.. With 1 & i S n. j, 2 and 1 S p S (dd, f), we define quadrature errors (xi, (xi,)) .Y.p), 'S, = Ec
Eolo, Ye,), che. = E Ee
- EolK )9e)). (16)
We interpret ge = 0 when f > L and function products are interpreted as pointwise products.
4.1 A FREQUENCY-BASER FORMULA FOR THE TRAINING ERROR
We obtain similar result to Arora et al. 2019 Thm. 4.1) when using loss function & in eq. Instead of expressing the training error using the spectrum of H De. we directly relate the training error to the frequency components of g and the cigenvalues of the continuous kernel K'
Theorem 2. Under the same setup and assumptions of Theorem 7 let P = De and Mp = Cmmax
If gf g6-1 + R is a bandlimited function with bandlimit L and 1 27p4 > 0 for all 0 $ l E
(see eq. 12 then with probability 2 1 5 we have
Ily-u(k)lle- (1-2 2h +e (k))
(1
|Ea(b)] Se. O (17)
E=
where (k) and E2 satisfy
f.
I.
(e) <
(1 (1-2n11) 2nue)* cge
162l S
Σ max
A
| 1sisn
1= 2=
E=
IIn the case where we do not have good quadrature rule associated with {x we usually have very limited understanding of the spectral property of the target function given its values at (x:) assume the existence of good quadrature rule for theoretical purposes.
Hence, we
5

---

Published as a conference paper at ICLR 2023
The proof of Theorem 2 is postponed to the supplementary material. The idea is that by Theorem I
we know y u(k) (I DnHHDD)) ) y + (k()). Using Funk-Hecke formula and quadrature. we have that 1 2nj are roughly the eigenvalues of - 2n and Ye = (ge(x))......... Ir (x(x))) associated eigenvectors. Hence, y u(k) ~ E/ 2qpe)"ye. This can be made precise by introducing 62. Finally, up to some quadrature error E1, have (gj.gt) La 2 Aan "o,_"yy,, ye, which gives us eq. (17j. Since Σi=1 c = Ad, For fixed data distribution μa, we expect that Cmax that 17 does not decay close to the 2 norm of the residual function g Na.- Explicit formulas for the eigenvalues {u (see eq. 12 are given in (Basri et al. 2019). and it was shown that μ = O(E (Bietti & Mairal 2 demonstrates the frequency bias in NN training
(n==)) as +
oc. Up quadrature error, ly -ukk is
2019 Theorem
the rate of convergence for frequency 0 < & < L is 2njuu, which is close to 1 when É is large. As + O, we have (1 - 2n/ba)at/// + e 4pptt which gives the convergence rate for frequency i using gradient flow. Therefore, expect that NN training approximates the low-frequency content of g faster than its high-frequency one, which is similar to the case of training with uniform data (Basri et al.) 2019).
4.2
ESTIMATING THE QUADRATURE ERRORS
We now quantify the quadrature errors in Theorem 2 If we can design a quadrature rule at the training data X1 ,,...., Xn
such that the quadrature error satisfies
,,.,,,,,,
1/5 M(x)dxx ga-
(Echh)
Ec)((x)) Yn,e ||
h E nT E2
(18)
for some constant .nn 2 O, then we can bound the terms in eq. 16 We expect that for each fixed In. + as - 00 as this saying that integrals can be calculated more accurately for denser set of quadrature nodes. In practice, it can require large amount of training data to make Yn small when is large. Under the assumption that our quadrature rule satisfies eq. (18) with reasonably small To s when l is small, we can bound the quadrature errors appearing in Theorem 2
Theorem 3. Under the same assumptions of Theorem 2 and that the quadrature rule satis- fies eq. 18 there exist constants C1, C2 only depending on the dimension d such that the
terms 1s [k) and (E2) in Theorem satisfy
1e (k)) ( + L2 Lm
max |19ي1 OSiSL
|52| |s2l (7
OSISL
max 11gs
L
M
j=0
for all k 2 0, E 2 L. where g = 9o + Jr. with gj E H.J. and Va.t satisfies eq. 18
The proof is in the supplementary material. Theorem states that (k) and E2 can be made arbi- trarily small if the quadrature errors converge to 0 as the number of nodes - oo. In particular, if there is a sequence } that increases to oo such that the quadrature rule is exact for all functions h HI i.e., Ec (h) O, where L, of e1 (k) and E2 are both (1)e,, for fixed g. Without the quadrature being exact, still have nice convergence provided the quadrature errors are small, as the following corollary shows.
(see e.g. (Mhaskar et al. 2000)), the rates of convergence
Corollary 1. Suppose there exists sequence Ln + oo such that In,,, - 0 as n + cc. Then, for a fixed L 2 0, we have max [k)( [|all;; and max |E2l ||gl| - as n - cc.
Corollary I shows that as increases, the quadrature errors E1 (k) and E2 converge to zero. Moreover, this convergence is uniform in the sense that it does not depend on the specific choice of e HI. Here, we normalize e (k) and E2 by IIall; and || respectively, to obtain the "relative" quadrature errors that do not scale when g multiplied by a scalar (see
FREQUENCY BIAS WITH A SOBOLEV-NORN LOSS FUNCTION
The frequency bias during the training of an overparameterized NN has several consequences. In many situations, worse convergence rates for seghffreueency components of a function are benefi- cial since the NN training procedure is less sensitive the oscillatory noise in the data, acting as

---

Published as a conference paper at ICLR 2023
low-pass filter. This significantly improves the generalization enror of overparameterized NNs. However, in other situations, NN training struggles to accurately learn the high-freguh frequecyy content of 9, resulting in slow convergence. To precisely control the frequency bias of NN training, propose to train a NN with a loss function that has intrinsic spectral bias.
Let D' (S(d-1) be the space of distributions D'(S where L = (I+ --)) ) and A is the Laplace- Beltrami operator on the sphere. We follow (Barceló al. 2021) and define the spherical Sobolev space [[((dd1))= = D'(Sd-1): f E ( }]. equipped with a norm equivalent to eq. (1.24) in (Barceló et al. 2021).
gd-1, Given E RR consider L D'(5--1) -
N(d,E)
IM (8
= Σ
Σ
(1+
(19)
t= p=1
where fe, are the spherical harmonic coefficients of f (see eq. 44) and Nd,, E) is given in section 2
We propose to set the loss function to be 2 llg - -N H- -NI in replace of 1 91 -N in eq. (3). When 0, it reduces to the L norm. If s > 0, the high-frequene
2
spherical harmonic coefficients are amplified by (1 + 0)20. The high-frequency components of the residual are then penalized more in the loss function, and one can expect the NN training learn the high-frequency components faster with the squared H loss function than the case of eq. (3). Similarly, if 8 < 0, the high-frequency spherical harmonic coefficients are dampened by (1 + L)= and one expects the NN training captures the high-frequency components of the residual more slowly with the squared / loss function. However, when s < O, the training is more robust to the
noise in the data. By tuning the parameter s, we can control the frequency bias in NN training (see Theorem J). The choice of for a particular application can be determined from theory or by cross- volssvvali.
First, we justify that the residual function is indeed in H Since we assume that is bandlimited, g E H' for all E R. Proposition] 2 shows that we could consider 8 < <3/2 for ReL.U-based NNs.
Proposition 2. Suppose N S0-1 R is 2-layer ReLU NN (see eq. (5). Then, we have N E ($d1) for all & < 3/2. Moreover, if 2 3/2, N E H (Sd-1) aandd only if is affine.
The proof is deferred to the supplementary material. When 2 3/2, the residual function N- may not be in H However, we can still truncate the sum in eq. (9) to a maximum frequency l to train the NN, although the sum can no longer be interpreted as an approximation of some Sobolev norm at the continuous level. We discretize the Sobolev-based loss function as
fan (d.E)
(W) = 2
Σ 2=
Σ
()2
N)(x)))
2 = -2(y - (() u), (20)
p=1
where u and y follow eq.
6 and P. Eien 1 (2+ k. Pip I. and (ar.p);
e; YYY,,, We assume that P. is SPD, which requires that (Emax + +)² 2 n. Next, we present our convergence theorem for Sobolev training.
Theorem 4. Suppose E 11 and 4 is the loss function in eq.
20
where P. is SPD and max 2 L. for all 0 S E s L, then with
Under the assumptions of Theorem [ if 21pue(1 2)2s probability 2 8 over the random initialization, we have
I. y - u(k) Σ (1 2mpe(1 + +)20) +11
|E>(K)]lp, Se, 0 OSkST, (21)
E=
where yd (9 gx and E satisfies
L
(1+j)2s N(d.))
||a||lp $
> 0=
Mr Weille.. (<1)==e,
Σ oa C (e))))
(1+
p=1
Compared to Theorem Theorem 4 says that up to the level of quadrature errors, the convergence rate of the degree-f component is 21/ + z)2=. In particular, since μe = =O(E-d) there is an s* > 0, which depends on d, such that (1+ 2)2= iy can be bounded from above and below for all E 2 0 by positive constants that are independent of E. This means for any > s*. we expect to reverse the frequency bias behavior of NN training. Figur the reversal of frequency bias as increases from -1 to (see section 6.1
7

---

Published as a conference paper at ICLR 2023
number iterations
loss
CO8 0
epochs
frequency l
Figure 1: Left: the nonuniform data x (cos sin 8) on the unit circle S', Middle: the change of frequency loss for & = (blue), 5 (red) and 9 (yellow) against the number of iterations for loss function & (solid lines) and + (dashed lines). Right: the number iterations for the NN training to achieve fixed loss threshold in learning ge (x) = sin(f0) for 3 < < 10 given the loss function O The black line represents the ((e) rate based on the analysis in (Basri et 2019
ReLU NTK L
freq. bias
min. freq. bias
We O(e))
10
low-to-high freq. bias
10a
high-to-low freq. bias
10
10a
-0.5
8
Figure 2: Frequency bias during NN training with squared H loss function. The blue-to-red rain- bow corresponds to low-to-high frequency losses (.V(E) o(f) for the frequency index & ranging from (blue) (red) with nonuniform training data, respectively. Here, an overparameterized 2 2-layer ReLU NN (xx) is trained for 5000 epochs to learn function (xx) given the H loss with 4. The inversion of the rainbow demonstrates the reversal of frequency bias.
EXPERIMENTS AND DISCUSSION
This section presents three experiments with synthetic and real-world datasets to investigate the frequency bias of NN training using squared 2 loss and squared H loss. The first two experiments learn functions on g' and $², respectively. the third test, we train an autoencoder on the MNIST dataset for denoising task. One can find more details in the supplementary material.
6.1 LEARNING TRIGONOMETRIC POLYNOMTALS ON THE UNIT CIRCLE
First, we consider learning a function on $ We create a set
1140 nonuniform data {x, l
in Figure and compute the quadrature weights {cz in for the loss function & in eq. 3) by
solving a constrained quadratic program (see appendix
We train 2-layer ReLU NN to Tearn
g(x) = 00) Σi_1 sin(E0), where (cos 0, sin 0). We define the frequency loss [V(e)
(())
where N and Ô are the Fourier coefficients of N and g. respectively (see appendix F. In Figure
plot the frequency loss for & 5, 9 in different colors to illustrate how well the NN fits each frequency component. The solid and dashed lines correspond to the loss function +b in eq. ① and + in eq. 33, respectively. Our observations collaborate with the theoretical statements in Theorem 2 Figure also shows that it takes asymptotically ((22) iterations to learn the 7th frequency sin sin((0) given the loss function $. similar plot appears in Basri et al. (019) for uniform training data.
We also use the squared H norm the loss function to learn After 5000 epochs, we plot the frequency loss with ranging from (blue) to 9 (red) Figure 2 given different values. As increases, the higher-frequene components are learned faster. When > 2, the frequency bias reversed the sense that ones rather than low-frequency bias under the squared L loss (see Theorem 2). The gradually changing "rainbow" in Sishow that the smoothing property of an overparameterized NN can be compensated by the H loss function for large enough 8, corroborating Theorem
parts are learned faster than the lower- fweer-fre
8

---

Published as a conference paper at ICLR 2023
loss
loss
loss
epochs
epochs
epochs
Figure 3: Frequency losses for l' 4 (blue), 10 (red), and 20 (yellow), when learning a function on g using different squared Ha loss functions. Compared to low-frequency bias in the cases of
1 (left) and (middle), observe tigh-freuuency bias when 2.5 (right).
9
9
9
(a) blurred image
bb)
(c) = 0.0
(d) 5 1.0
9
9
9
(c) blurred image
(f) 8 1.0
(g) = 0.0
(h) 1.0
Figure 4:
Outputs of squared H loss-trained autoencoder on a typical test image when the input images are contaminated by low-frequency noise (top row) and high-frequency noise (bottom row).
6.2 LEARNING SPHERICAL HARMONICS ON THE UNIT SPHERE
Similar the previous example in St we design an experiment on $ We utilize a data set {x; Ti=l in (Wright & Michaels 2015), which comes with carefully designed positive quadra- ture weights {c) We test the squared H loss function NN training with target function g(x) = f=0.f even Ygo0 defined on 8 that involves many high-frequency components. The results are shown Figure 3 with different values. The natural low- wwwfrrquency bias the NN in the case of based training (i.c., $ 0) is enhanced when 1, and is totally reversed when 2.5.
>
6.3 AUTOENCODER ON THE MNIST DATASET
The idea of Sobolev training is also useful for high-dimensional training data. In Figure we present the results of the autoencoder for image denoising using the MNIST dataset (LeCun et al.) 2010). The outputs of the autoencoder are presented when trained with the squared H² norm as the loss function. We contaminate the dataset with random wow-frequency noise (top row) and high- frequency noise (bottom row). When high-free frehffreyency noise is present, the H loss function generally performs better with s < O, while the case of suffers from low-frequency noise. This corroborates discussion in Section [ In appendix G theoretically justify this phenomenon by studying the frequency bias in operator learning.
helps image deblurring when the input image
CONCLUSIONS
frequency bias phenomenon observed in NN training with nonuniform training data. Instead of the standard mean-squared loss function in eq. (Ι. we propose the use of a different loss function in eq. (3. which involves quadrature weights and has a natural continuous analog. With eq. (3). we rigorously analyze frequency bias with nonuniform training data using the Funk-Hecke formula. By changing the loss function to a squared L Lt-ty Sobolev norm, we can control the frequency bias in NN training, which accelerate NN training convergence and improve robustness under noises.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Aparna Gupte and Liu Zhang for discussions and some initial experiments. The work was supported by the National Science Foundation grants 2045646, as well as the Simon Foundation. Yang acknowledges support from Dr. Max Rössler, the Walter Haefner Foundation, and the ETH Zürich Foundation. We also gratefully thank the anonymous referees for their constructive comments, suggestions, and discussions.
DMS-1952757, and DMS-
REFERENCES
S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang. Fine-grt sinengraneed analysis of optimization and generaliza- tion for overparameterized two-layer neural networks. In Inter. Conf. Mach. Learn., pp. 322-332. PMLR, 2019.
A. Austin and L. N. Trefethen. Trigonometric interpolation and quadrature in perturbed points. SIAM J. Numer. Anal., 55(5):2113-2122) 2017. doi: 10.1 N0.1137/16M11077
R. Bach and M. Jordan. Kernel independent component analysis. J. Mach. Learn. Res., 3(Jul): 1-48, 2002.
C. T. H. Baker. The numerical treatment of integral equations. Oxford University Press, 1977.
J. A. Barceló, T. Luque, and S. Pérez-Esteva, Characterization of Sobolev spaces on the sphere. J. Math. Anal. Appl., 491(():1222400,, 2020.
A. Barceló, M. Folch-Gabayet, T. Luque, Pérez-Esteva, and M. C. Vilela. The Fourier extension operator of distributions in Sobolev spaces of the sphere and the Helmholtz equation. Proc. Roy. Soc. Edin. Sec. A: Math., 15 15666)1768-1788) 2021.
R. Basri, D. Jacobs, Y. Kasten, and S. Kritchman. The convergence rate of neural networks for learned functions of different frequencies. Adv. Neur. Info. Proc. Syst., 32, 2019.
R. Basri, M. Galun, A. Geifman, D. Jacobs, Y. Kasten, and S. Kritchman. Frequency bias in neural networks for input of non-uniform density. In Inter. Conf. Mach. Learn. pp. 685-694. PMLR, 2020.
M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical viri-veriance trade-off. Proc. Nat. Acad. Sci., 116(32):15849-1558 2019.
A. Bietti and J. Mairal, On the inductive bias of neural tangent kernels. Adv. Neur. Info. Proc. Syst., 32, 2019.
Y. Cao, Z. Fang, Y. Wu, D.-X. Zhou, and Q Gu. Towards understanding the spectral bias of deep learning, arXiv preprint arXiv:1912.011999 2019.
Chollet.
Building autoencoders in keras. http:::/bblog.krrasttooo bodiiiioooiinnnnggoooo
nutoencoders-innkeeaae
2016.
Dai and Y. Xu. Approximation theory and harmonic analysis on spheres and balls, volume 23. Springer, 2013.
S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks. Inter. Confer. Learn. Rep., 2018.
B. Engquist, K. Ren, and Y. Yang. The quadratic Wasserstein metric for inverse data matching. Inverse Problems, 36(5):055001, 2020.
S. Fridovich-Keil, R. Lontijo-Lopes, and R. Roelofs. Spectral bias in practice: The role of function frequency in generalization. arXiv preprint arXiv:21 2021.
W. Hoeffding. Probability inequalities for sums of bounded random variables. Amer. Stat. Assoc., 58:15 38:13-30, 1963.
10

---

Published as a conference paper at ICLR 2023
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Adv. Neur. Info. Proc. Syst. 31, 2018.
Kurbiel. Derivative of the softmax function and the categorical cross-entropy loss. 2021. hwrllatpss//ooaoccttaaccieeeeeee
Function and--on--d------- the categorical wrt.raoososssssssoooooeoea loss ffceefo08ldi
Y. LeCun, C. Cortes, and J. Burges. MNIST handwritten digit database. ATT Labs [Online). Available: http://yann.lecn..ccm http://aaa.eeeu...o///////////// 2, 2010.
S. Li. Concise formulas for the area and volume of hyperspherical cap. Asian J. Math. Stat., 4: 66-70, 2011.
H. N. Mhaskar, F. J. Narcowich, and D. Ward. Spherical Mareinkiewiez-Zygmudd inequalities and positive quadrature. Math. Comp., 70(23)):113-11334 2000.
Q. Nguyen, M. Mondelli, and G. Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In Inter. Conf. Mach. Learn. PMIR, 2021.
F. W. J. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark. NIST handbook of mathematical functions hardback and CD-ROM. Cambridge university press, 2010.
E. Parzen. On Estimation of a Probability Density Function and Mode. The Annals of Mathe- matical Statistics, 33(3): 1065 1076, 1962. doi: 10. (0.221440mm/117774477 URL https:
/ 20ti.or//10.111////// aoms /ol..ommm//77077777
N. Rahaman, A. Baratin, D. Arpit, Draxler, M. Lin, F. Hamprecht, Bengio, and A. Courville. On the spectral bias of neural networks. In Inter. Conf. Mach. Learn., pp. 5301-5310. PMLR, 2019.
M. Rosenblatt. Remarks on Some Nonparametric Estimates of a Density Function. The Annals of Mathematical Statistics, 27(3):832 837, 1956. doi: / URL https: 7/abi..rgg/10122///aaaa http://aoomm17777881//1
M. Scetbon and Z. Harchaoui. spectral analysis of dot-product kernels, Inter: Conf. Art. Intell. and Stat., pp. 3394-3402. PMLR, 2021.
R. T. Seeley. Spherical harmonics. Amer. Math. Mon., 73(4P2): 1966.
L. Su and P. Yang. On learning over-parameterized neural networks: A functional approximation perspective. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett (eds.), Adv. Neur. Info. Proc. Syst. volume 32. Curran Associates, Inc., 2019.
H. Widom. Asymptotic behavior of the eigenvalues of certain integral equations. Trans. Amer. Math. Soc., 109(2):27--295, 1963.
H. Widom. Asymptotic behavior of the eigenvalues of certain integral equations. II. Arch. Rat. Mech. Anal., 1733):15-222, 1964.
C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning. MIT press Cam- bridge, MA, 2006.
G. Wright and T. Michaels. Spherepts. httppp////gtthaao.o..o////a//pep 2015.
Z.-Q. J. Xu. Frequency principle: Fourier analysis sheds light on deep neural networks. Commun. Comput. Phys., 1745)177 2020.
G. Yang and H. Salman. A fine-grained spectral perspective on neural networks. arXiv preprint 1rXiv:1907.10599 2019,
A. Yu and A. Townsend. On the stability of unevenly spaced samples for interpolation and quadra- ture. arXiv preprint arXiv:2202.0472) 2022.
B. Zhu, J. Hu, Y. Lou, and Yang. Implicit regularization effects of the Sobolev norms in image processing. arXiv preprint arXiv:2109.00255, 2021.

---

Published as a conference paper at ICLR 2023
SUPPLEMENTARY MATERIAL
This is the supplementary material for the paper titled "Tuning Frequency Bias in Neural Network Training with Nonuniform Data." "
The supplementary material is organized as follows. In Appendix A we recall the notations used in the paper and introduce additional concepts for our analysis. Appendix we prove that H is symmetric and positive definite matrix. In Appendix [ we prove Theorem of the paper. while the proofs of results in Section 4 and Section 5 are given in Appendix [ and Appendix respectively. In Appendix [F] we provide further details of our three experiments. The observation made in the third experiment is then briefly justified in Appendix G in which we study frequency bias in general operator learning setting. In Appendix HH we formally discuss the computation of positive quadrature weights.
A PRELIMINARIES AND NOTATION
For d > 1, let g g R be square-integrable function defined on gd-1, The function has a spherical harmonic expansion given in Section We denote the space of harmonic functions of degree e by Hgg which is the span of {Yr,pp==1 M We further denote the space of spherical
harmonics of degree S l by I θi- Ht..
Given distinct training data fx, ) from Sd-1 and evaluations y; (xx,) for for <is n, our goal
to understand the intrinsic frequency bias behavior of training 2-layer ReLU NN given in eq. (5). It important for the theory that we initialize the weights as independently and identically distributed (iid) Gaussian random variables with a covariance matrix I the bias terms are initialized to zero, and the coefficients, i.e., 01,..... amm are initialized iid as +1 with probability 1/2 and - otherwise. During the training process, the values of { } are not updated.
We train with the loss function given in eq. (6) so that the gradient descent algorithm for NN training is given by eq. 77. An important object in understanding the frequency bias of NN training is the symmetric and positive definite matrix H E R in eq. (9.. Since H and are symmetric positive definite matrices (see Proposition 1. HoP has positive real eigenvalues. To see this, note that HoP H2pp//p1/2 = P 172 (p 1 p1/2)//1// This means that HoP and p'/2H<<p1/2 are similar. Since the matrix p'/"''''// is symmetric positive definite, HoP has positive eigenvalues. We denote the eigenvalues of H by An-1 2 Z A > O, which partially govern the frequency bias phenomena. It is worth mentioning that although H is not symmetric, is self-adjoint in the inner product space induced by P because
PH Sp (H*PE) PC= = P(H (E. (E.H'PPPpp
(22)
convenient to analyze the eigenvalues and eigenvectors of H via the zonal kernel K gd-1 x gd-1 RR given in eq. (1). The key is the Funk-Hecke formula (Seeley 1966).
Theorem (Funk-Hecke). Suppose K [-1,1] + is measurable and K(1) - (2) 3)/2 integrable on [-1, 1]. Then, for any f H have
1 S4- ())MEEdE (Aa [ -2) h(S). SES (23)
where Pe.a is the ultraspherical polynomial given by (-1)TT((d 1)/2) d²
Pt.a(t) 2'T + (d ( (2 31/2 de (1 - 22j-ae3-3-33112
(24)
Applying Theorem 5 we have that
[ K K* = noh(x), he heH..

---

Published as a conference paper at ICLR 2023
where Me 0, VL, given by (Basri et al. 2019)
10((0)
2
d=g
(-1)
1 ==0 0,
(d-1)
(d
1pp=
3p+1
1) 1) 1(2++]] + 4p
शेデ (22)
1,
101(0)
Cg ()
2(2--++1) + 2(2p-1+2]
2 r
2p 2p-(+2
22
8 even,
}01(0)
(p. E) (2(2p-++1) ( 22p-
(p-
3p-4-1
2 odd
for d 2 3, d odd, where
(-1) (d-11/2
l d-3
(2p)!
(+(() (d - () + (d- 1)/2)
-
p
(2p - 8)!
Here, the exclamation mark means factorial and () denotes the binomial coefficient.
Given x, wr, and b, in eq.
(5) write x J/ (x, 1) Sd and w, (wr, b,) E RR+11 Therefore,
have ReLU(w, x + b,) V2ROLU x) and the NN function be rewritten as
V2 Σ a Re..
(xx) vm
By replacing the expectation over random initialization of w by (t)), we define the instantiations of H the keth iteration by H(k),, where
(ky( _
(k)
[x] (M)20.7 (8)20))
(25)
m
where 1 is an indicator function.
B THE MATRIX H IS SYMMETRIC AND POSITIVE DEFINITE
Proposition ! |tatess that the matrix H defined by eq. symmetric and positive definite. While the symmetry of H is immediate from its closed-form expression, the fact that it is positive definite requires more detailed analysis. The proof idea is similar that of Theorem 3.1 of (Du et al., 2018), in which the matrix H is associated with 2-layer ReL.U NN without biases. However, our H is associated with a 2-layer ReLU NN with biases. While (Du et al. 2018) requires that no two training data points are parallel, we allow the existence of Xx, -Xia for some i and iz. To deal with this case, our proof employs a pair of nodes denoted by X;, ,
Proof of Proposition For measurable function f : Rd+11 we define norm of f as
|| = Ew-N [l.(w))l3
and let H be the space of measurable functions such that llfll 3o. It can be shown that H. is Hilbert space with respect to the inner product (f, (f,9)H H (.w [f(w) g[w]] (Du al. 2018). For each x,, 1 I i S n, we define the function Φ; by
Φ>(w) x (wTx,20) x.20
W Rd
Then, Φi E H for all i, and H = (ii, 25H We prove that H is positive definite by showing that ( is a linearly independent set in H.
To show (o a linearly independent set, we show that
01016 (w) + .... + a (en = for almost every w E Rdd
(26)
implies that = 0 for 1 <i < n. We fix some 1 < i assume that X = x Define the set D = {w E IRd w X, = 0} for E j S n. As
S and, without loss of generality,
Otherwise, if such iz does not exist, we can add an element Φ associated with -xi, to (o.) we show (2t) 1-+1 1 is linearly independent, then so is (o.)-11
2

---

Published as a conference paper at ICLR 2023
result, Dú, D Dig. Since each D, is hyperplane passing through the origin and D1, * Dj for any j * 11, 12, Ez E D,, such that z & Dj for any j * 11, 12. For a positive radius > 0, let Bn Biz, R) be the ball centered at of radius R. Define a partition of B into two sets denoted by B and BR (possibly missing subset of BR that has zero Lebesgue measure), where
B = (w& BR W X > 0} = {w E BR W Xi2 < 0},
B = w E BR w X12 < 0 = (w E BR w Xi2 > 0}.
Since Dj is closed for each 1 S E n, BR is eventually disjoint from Dj as R - O. Hence, we have
lim sup (z)(2) (w)] = 0, j j i 12, R-+ wEBR
where | denotes the Euclidean distance. Then, for any j + i1 12. we have
lim B
= o,)(2)
(Z),
lim n
By =
B
B
B
where |-|
denotes the Lebesgue measure of a set. Consequently, we find that
/ @y(W)dww) 0,
lim R-0
( [ n
1 + 21,
Now, consider the integral of di, and Oiz. We have
1
1
lim R-0
Φi (w)dw-
Φi (w)dw)
lim R-0
X;, dw
0dw
=Xi1
[ B)
|B
Bn
|B J
Bh
|B
Bn
1
1
1
lim R
Φi (w)dw
Φ5 (w)dw
lim
Odw
Si dw
B
[
BR
R-
|B BB
BR
BR
By applying these limiting expressions to Σj=1 ()0
O, we find that 0; Xi,
0;,x;; 0.
Since the last entries of both X1, and X; are 1/v2, we have ai 0i.. Thus, we have Oi 0 because Xi, * O. Since i is arbitrary, we showed that ag = for every S j S n, and the statement of the proposition follows.
is clear that the proof of Proposition iss also true if we assume that each entry of , is initialized from an iid sub-Gaussian distribution with zero mean and whose support is the entire R, and we update the definition of o according to eq. (9).
C THE CONVERGENCE OF NEURAL NETWORK TRAINING
In this section, we develop the theory for learning a NN with general loss function op defined by positive definite matrix P in eq. (6). In particular, we prove Theorem I which states that provided the learning rate is sufficiently small, the weights are initialized without too much variance, and the NN is sufficiently wide, then the residual in the first few epochs can be described with the matrix H
While proof is similar to that of (Su & Yang 2019), the argument is distinct in three essential
ways: (1) Our proof applies to any loss function defined by positive definite matrix P. which requires us to use different Hilbert space (IR" ( ))) (2) While the result in (Su & Yang 2019) bounds the residual using the minimum eigenvalue of H we estimate the residual as a matrix- vector product of (I- 2nH which allows us to analyze the training error using all eigen- values of H P. (3) We use different NN function that incorporates the bias terms and we do not assume that we initialize the weights in a way that makes No- 0.
Before we prove the theorem, we define some useful quantities. Let A be the set of indices such that the coefficients o, are initialized to and let B be the set initialized H(k) into two parts, where H(k) is defined in eq. (25). so that H(k) = H+ H (k) with
We then decompose
(+) =
1 x X3 m
Σ TEA
HTj(k)
- x X, Σ m
(K)
(R) 2.20 (w)( Txx 201
(R)(R) X,20
FEB
3

---

Published as a conference paper at ICLR 2023
Similarly, define two other matrices H (k) and H (k) as
x x (k) - m
Σ rEA
(k)
(k) 1 m
x X Σ rEB
w. (K+()))) (H( 7;,20
w. (R.(+)))2,200 w.(R) 8,20
Unfortunately, H (k) and H (k) are not necessarily symmetric and they differ from (k) and H (k) up to sign flips. To simplify the notation later, we also define two auxiliary matrices L(k) and M(k) as
L(k) = H (k) (K),
M(k) = H (k: H (1)
We now prove that I 21) (P)P is close to the transition matrix for the residual, up sign flips, i.e. y - u(k + 1) ~ -I-
(k) (I-2
u(k)).
Lemma 1. Let z(k) y (k) be the residual after the keth iteration. For any A: 2 0 and >> O, we have
[I [- (k) H (k) P) (1k)) s a(k + 1) s (I (I-27) (H* (A)) H (x:))) P) z(k),
where the inequalities entry-wiss
Proof. First, by the gradient descent update rule, we have
w,(k + 1) (.( = -1) ppp (w (W(()...... where the (d+ + 1) n Jacobian matrix given by Tu(k) Ow,
W. (k))
@u(k) @4p(u) Ow, Ou
Ow,
V2ar [ (xT (H)20)
X, 1l (x. (xTT2()))))))))
(27)
Vm
and the gradient of the loss function 4p defined in eq. (6) with respect is given by
@pp(u) PPy u(k)) - Pz(k),
(28)
du
which is a vector length n. Hence, it follows that
22na, (Pz(k)), X. Xp1 (p,(ppl.e (k)20))
w. w. 1) w.(k)
Vm
where (Pz(k)), denotes the pth element of Pz(k). Using the property of ReLU that (b - a)1 (a>0) s ReLU(b) ReLU((a) s (b - a) (0>0);
a, e R,
have
ReLU (wr(k + 1) x.)
ReLU (w,(k)
22
Σ (Pz(k)) x x (sT (10 (
S
v
m
p=1
and
ReLU (w, (k: + 1) Tx,) - ReLU (w.(k)
V2nar
2
(P2(k)) x Xx [x w. (1)00) (xT w.,200)))
m
p=1
4

---

Published as a conference paper at ICLR 2023
Hence, we have
V
(u(k + 1)), - (u(k)),
ReLU(W, (x)))
m
TEA
v2
- (A) x1) x;))
m
rEB
21
(Px(k))) x Xp (x] (x).w. (27,0)2222000
m77
rEAp
20
Pz(k)) x xp (R. (.)20) (x] (4)220)
rEB p=1
2n
H (A: +
H (k)) (Pz(k)))
p=1
This proves the first inequality. The second inequality can be shown with a similar argument.
In particular, if there is no sign flip of the weights, then H(k) the inequalities in Lemma] [are are equalities. Next, using Lemma T y u(k) using H up to error term.
(++) + ( = H(k) and
we can derive an expression for
Lemma 2. For any 0 7 1/(2Mmn) and any O, we have that
y u(k) (I 2m P)* t: (y u(0)) <(k),
(29)
where
I - -(()) | (I- P) (y - u(O))/p u
||E({)]|pp < 2n
t=0
(30)
2n
(M))P//+((((P)) utt)lp
Proof. For l 2 define r(k) by
r(k) y u(k) (1 - 27/ 1)P) (y uu( 1)).
(31)
Then, by Lemma 1 we have
[[r(k]]pp s 2n (| 1)Pl|p + |[ 1)Pllp) lly u(k 1)llp-
(32)
Note that eq. 31) is first-order non non-homogeneoos recurrence relation for y u(k), which has an analytic solution. Thus, we can expand y u(k) for & 2 1 as
y u(k) ((I - 2n 1)P) (I - H()P)) (y u(O))
k-1
(33)
rkk) Σ (1-2n H 1)P) (I 2r) r(t).
Moreover, we can write the product of the matrices as Su & Yang 2019
(I- 1n2nH((k 1)P) (I (-2))((0))))
-(1 - 2 + k-1
(34)
+2n
(I-2m
5

---

Published as a conference paper at ICLR 2023
Combining eq.
333
and eq.
34
obtain eq.
29
where
<(A: = 2n
2n
2n H
k-1
+r(k) Σ (11-2 ... (I- (1-2)
t=1
Finally, we note that
(Pt))(())P//
Amax (H(()P) Amax
H(1PL/2) p H())p//2
sup (ER"\(O)
|
H(ttPCilp -|H(())Pllp. Kclp
sup (ER"\(0)
sup
CERM\())
(35)
and that
H(tt) H(tt) El
H(t))Ellp [H(t)PE
[H()) [PEll2
H(t)
sup (ERMMO
sup EERM
|PEll2
EEll
(36)
We can then bound HH p using Mp defined in 8 and [H(())22 as
HH()))pp S Mp |H(())2 Mp S Mp
HH(I),, [H(()) S Man.
By requiring that 7) < <1)(2Mmn) we have Aminn (I 2n H ())P) > 0 for all f. Hence, I- PP)
positive definite (R", (., ))), and according to eq. (35p we have | - (t) = Amax
Pt) 1. The upper bound in eq. 30 follows from the triangle inequality and estimate
on Fa in eq. 32
The residual terms in Lemma can be made small by controlling MMtt) + [L(t) and [[(())) HII) Their upper bounds are given in Lemma First, we define
S,(1) = (1 m (w-(t)) x.20) + (0) 2.20) for some S S
Sr
to be the set of indices the weights that have changed the sign at least once by the kth iteration. Lemma 3. For all 2 0, we have
4M m²
max (|M(())) + [[(())l|p (H()) H(t)PP)p))
Σ (is((t)
1=1
Moreover, for any < < 1, with probability at least 6, we have
log (2g/))))
(H - -(O)) < 2M
Proof.
First, we have
[ = M [M()] s MΦ [MM())]
Mp
Σ
11 114. (1w.CO)T...0...00T....... (2,00
22,
m²
==1 p=1
rEA
Mfn m
Σ
(t) 2
m² 1=1

---

Published as a conference paper at ICLR 2023
The estimate for |[(t)P||p is exactly the same and obtained by replacing A with B. We also have
(IH - H())PPPP & Mb [(()) H() < MP H())) H(!))I
Mp
n
m
(0)
m
Mp n
MP m
(1S(()) + (,(1))
(2|s(0))+2113) +21,,(0)))
m
p=1
4Mpn n (S(())2
m
This proves the first inequality. Since (0) is the average of m iid random variables bounded in [0, 1]. by Hoeffding's inequality (Hoeffding 1963). for any / and any i, S have
212
f2
(m (2)(0) - HET 2 1) s 2exp
S 2exp
(37)
m
YTR
Set t vm ( With probability at least 1 -8/n2, have
Ho) H log (2n2/8)
log (2n/o)
22
(38)
m
8, we have Hence, by a union bound, we know that with probability at least
log(2n/6)
H H(O))l2 < H H(O))l, - 2
m
The last estimate follows from the definitions of Mp (see eq. (8 and eq. (36))
Now, state and prove our initial control of the decay of the residual.
Lemma 4. Let 0, > 0,0 < 8 < 1 and T > 0 be given. There exist constants Cm, C > such that if v S m)) and m satisfies
Mfn R222
(+ x² MBM 2
m 2 Cm
N51
) + +
and
m 2 C Man log(n/8)
25 (1 (1 x R2MB
+ +12
e²
then with probability at least 8, we have the following for all S k S T:
u(k) (I - 2 (y u(0)) + E(k),
||E(ki]lp p S.
(39)
Proof. Set 8' 5/3. For any and 1,.... m. since w, x; N0 x2), we have
2R
IP (0) x R) E [ [[)w. &1
By Hoeffding's inequality (Hoeffding 1963). for any t > 0 we have
2mR
2t (--
t2
P (1
+
<.
exp
S exp
1sisn. (40)
Vak
m
Thus, we set
vm loggo///// then we find that with probability at least
8/nn we have
2mR
R VTK
log (n/8')
1 (0).(0))T
<
+
m loggm1//5 < 2m
+
TTK
7

---

Published as a conference paper at ICLR 2023
By union bound, we have with probability at least - 8'
Σ
[| (0T&.1))
4m
R
log(n/o")
VTTK
By combining this with Lemma
3 we have that with probability at least 28',
4M
Σ
"
Σ (.
m
2
S
4.5p
R
log(n/00
(41)
m²
VTK
m
and
H - H(0)PPlpp S 2M log (og(2n/0))
(42)
Since the ith entry of (0) has mean O and variance n²? have [[( S x², where (u(0)); the ith entry of u()). Hence, we have IE probability least 1 - 8", we have
[I) p Mbnx?. By Markov's inequality, with
| (00))lpp - KM/////8'
ly u(0)lpp - lyllp KMP Vn/8'.
(43)
By a union bound, know that eqs. (1 to hold with probability of least theorem now follows using induction, where the base case when ls = 0 is obvious. Assume eq. (39) holds for .....,k k 1, where
35'. The
T. Then, we have
2n y u(t)lp S 2n 1=
Σ (1 (1- (1-20)) I u(O)llp + + S 15 by u(0))lp+2nIt (44)
t=
where the first inequality follows from the fact that P is positive semidefinite in (R", :)) with the maximum eigenvalue being 21z2o. and the second inequality follows by bounding the power series. By the definition of Ao, have
k-1
2n
HT) u())
2n
Σ (1 2-
Ily -())l s No lly u(0)
1=
(45)
By Lemma
and
we have
y - u(kk = -1- P) u()) + ((k)
with
|<<())] S A/ [[H(()) H HPPPPp ly - -u(0))p
4MPn mn
(46)
+ 2,
2/
(S((k) (A5 Ily u(0)lpp + n/Te),
where we used the fact that [t)(t) is a nondecreasing function of and the triangle inequality
[H H(t) Pllp < [[ 0) HPpp (I((()) H(O)) Here, we also combined
do (t) H ) ly ( with the last term on the right-hand side of eq. (30) and
applied Lemma 3 eq.
and eq. (45 obtain the last term the right-hand side of eq. (46). To
control SS [A:)]. we first bound the change of the weights. For any S S and S S m,
the change of weights in one iteration can be bounded by
au(() @0p(u) Ow,
Ww (t. 1) w w,(1112 =
ou
2
Ou(() Ow,
2n Mp Ily u(()lpp
"
|P(y (()))l22 < m
where the inequalities follow from eq. be bounded by
27 and eq.
28
Hence, the total change of the weights can
(t,(t) w, S npy
ly utt))lpp I Rrs
(47)
2'
8

---

Published as a conference paper at ICLR 2023
where Rr Mpv (Xp |yy u(0)llp + 2nTTe). Recall that S,(k) is the set of indices of weights that have gone through at least sign flip by iteration k. Thus, if E S, have (t)(t) (,)ll 2 (0) x; for some 0 - t s & as the sign flip leads to (w) (O))), & I
(0) x, (t) { This gives us
[Si(k) < {r E [m]] (0) X. < (w) (0)l22 for some 0 O2LSk) k]]
(48)
< { E [m] (0) x,| S RTH
where [m] = f1...... m). Hence, there exists constant C 0 such that
log log((n/8'))
[|<(k)]pp - 2M
by u(O)llp
m
Rr
log(n/8")
8.Mon
(A5 lly u(O)lpp p + nfTe)
V VTK
m
S 2Mpn V
log (6g()//))
1 x+Mpp Xo C
3n
m
A1
+ 8M
Mp
n
Ao C
3n 1 + *-MVy
+ 2n/l'e
log(3n/0)
TTn
2mm
8
Aa
3n [1+
Ao
1+ kDMpy 8
+ tnTe
A4
(49)
where the first inequality follows from eq. (41) eq. (46), and eq. (88) and the second inequality follows from eq. (43) and (47). Finally, eq. (39) follows from the way we define By taking Om large enough, we guarantee that 2M MMAAAAA < e/3. By taking C large enough, guarantee that 8M e/3. Hence, eq. 39 follows.
Lemma 4 gives us an estimate of the residual y u(k) in terms of the initial residual y u(0). However, in analyzing the frequency bias, we hope to express the residual terms of y only. This can be done by controlling the size of u(0). First, we note that the proof of eq. (43) does not rely
on the assumptions on m in Lemma Hence, holds for any n, m 2 1, > 0,0 < and positive definite matrix P. Now we are ready to prove our first main result Theorem
Proof of Theorem 7
By eq.
43 with probability at least 1 - 8/2, we have
H P
u(0) < [|((O)] xMPv2nn/6
(50)
By taking K S
we guarantee that
| (T- u(o))
u(0)) <//2.
By the way we pick xs and m, for some constant C" that only depends on d, we have
2 M2n C
8
Hence, by taking C2 in eq. 13 large enough, we guarantee that m satisfies the assumptions in Lemma 4 with T. and 5 to be c/2, T. and 8/2, respectively. Then, have eq. (39) is true with probability of at least 1 8/2, 2. for which [|e(k)]]p < e/2. The result follows from the triangle inequality and union bound.

---

Published as a conference paper at ICLR 2023
Notably, there are other initialization schemes that allow us to avoid using R. One of the examples is to initialize the weights at odd indices W2p+1 and 02p+1 randomly and set W2p+2 = Wap+1, dgp-2 a2r++1 1, assuming m is even (Su & Yang 2019). This initialization scheme guarantees that u()) = O and hence we do not need to introduce x to control the initialization size || [|p In addition, if we assume that each entry of w, is initialized from iid sub-Gaussian distribution with zero mean and whose support is the entire IR, then since H is still SPD (see the remark at the end of Appendix B and the Hoeffding's 's inequality holds, the proof does not break down and result similar to Theorem[[er can be shown.
Following the same steps of proof, we can study the case when the gradient descent steps are slightly perturbed. That is, Suppose we perturb the output of the NN by ōu, at the jth iteration. Then, we expect that the residual of the NN at the kth iteration is approximately
y ukk) ~ (I P)
2- ((I 21 + Sui) + 5uz) + ... duR
(I P)
Σ (I- H/ Cuj.
P is less than one, we can then control the errors in Since the maximum eigenvalue of I - H
this approximation using arguments similar previous lemmas.
In Theorem D we showed how the parameters of the NN should depend on the desired maximum error e, Sometimes, it is also very useful to understand the dependence of e on the parameters n, 12, m, etc. Therefore, we present the following result to show this dependency.
Theorem D. In eq. 5). suppose that Wi,..., wm are initialized iid from Gaussian random vari- ables with covariance matrix I,,,, bj.... bm are initialized to zero, and ai,..., ..m are initialized tid as +1 with probability 1/2 and -1 otherwise. Suppose the NN is trained with training data (xs, v:) for S S n, loss function up in eq. (6) for a symmetric positive definite matrix P, and the training procedure is the gradient descent update rule eq.
N₂ be the NN function after the kth iteration and u(k) = (7p with step size n $ 1/(2M3n). Let where No is the initial NN function. Let a probability of failure O < 5 < 1 be given. Then, there exists constant C > O that depends only on the dimension such that with probability 2 - 8, the following statement holds: for any 1, we define Ex by
||y u(t) - -II P)
CK = max
1SIs-11
then we have
||y u(k)- (1-))) 22 S 22Mmy
log(Gn/0) xo
3n 1 + xMMp
8
m
1
3n
log (3/33)/)
+ 8MMR
Mp
C
1 ++MMp
+ 27/hEs
+
(51)
v VTR
2m
m
3n
2n
1++MMp V
+ nkEE
<xMP V
i
8
Proof. The result follows immediately from eq.
(49) and eq. (50).
While this paper is primarily concerned with learning a continuous function using loss functions that are adapted from MSE, we briefly discuss the changes that are needed to study classifiers trained by cross-entropy. If the classification task has p classes, then our NN has p outputs, each of which is then passed through a softmax layer and represents an estimate the likelihood that the input belongs to the corresponding class. More information on the NN architecture and the cross-entropy loss function can be found in (Kurbiel 2021). Let N2 W) be the jth entry of the outputs of the NN and let uy W) softmax(N,, (x; W < j S p. Let (x( be the ground-truth of the jth entry of the outputs and let 2, (x; W) = 9 (x) - uy W) be the residual. Assume we use the gradient flow and have access to data the entire domain. Then, derive formula analogous
10

---

Published as a conference paper at ICLR 2023
eq. 2. for each fixed we have
dz,(x: W)
duy(x; W)
(x;(x; W) dNi(x; W)
dl
dl
dN,
dl
(x W) (x; W) dW
du,(x; W) ONi(x; W)
(aL(W)
Σ
dN:;
oW
dt
dN
OW
OW
du, (x; W) (x; W)
(N; W)
du(x))
(x);
dN;
OW
34-1
OW
where L is the cross-entropy loss function computed as integral over gd-1 and in the last step we used the fact that (d/dN, (((')) W) = uy (x'; W) ge (x') = 22 (x'; W) Kurbiel 2021 Hence, eq. (2) now becomes
dz (x; W)
duy(x; w)
P
ON: OW
(x; W),
ON:
OW (x'; w) zn (x': W)du(x)
dl
dN:
34-1
=K, (x.::W)
where we also know that (d/dN;)u, = =)= (1 -, W)). Again, we define H.S as the discretization of Ki in expectation over random initialization of W. Note that H coincides with H that we used extensively in this paper. However, the entries of H might differ with H in signs. This potentially causes difficulties in analyzing the spectrum of H Now, by the formula above, we expect that the residual can approximately be written as
(k(k + 1) 2 (N:) = [x)(x) u + 1)] (x) u,
(k) ((-()))) .. 1 (x= -u, u,(k)) Σ H Pz. (K))
(52)
where "o' is the Hadamard product, u (,) [xy(x1: W(k)), ,, (>,x W(k)) and (k) (x1 W(K),, ... 22 (x,x W [Kk))] Suppose we define the vectorized residual and define the up x np block matrix J(k) by (kk) (
[zT.... .,,1 [z,,..,,,,,
diag (A)) a ([I ([=()=)).".. 1(--)) uy (A))) for i, H for i 0, ...... 1. Then, eq. 52
O,.... P 1. Let H be the np np
block matrix such that H ((++)))((+-)))xx(+))))))))))((
can be written compactly as
z(k - 1) z(k) - (Ip P)z(())
(53)
where '8' is the Kronecker product. Frequency bias can be analyzed by studying the dynamics of 2kk) based on eq. (53). However, the fact that depends on k is expected to add complication to the analysis.
D THE THEORY OF FREQUENCY BIAS WITH AN L -BASED LOSS FUNCTION
In this section, we prove the results stated in Section where we are concerned with the frequency bias behavior of NN training when using the squared L norm as the loss function. We theoretically show the frequency bias phenomena in this setting, up to a quadrature error.
D.1 A CONSEQUENCE OF THEOREM
Given bandlimited function Sd-1 + R with bandlimit L, we can uniquely decompose into spherical harmonic expansion as g(x) Σt. (x),, where (x(x) E Hg. Here, Hg is the space of the restriction of (real) homogeneous harmonic polynomials of degree É on gd-1 That is,
N(d.8)
gx(x)= Σ
Yemp
ge.p ff ((x))t,p(x)ds
11

---

Published as a conference paper at ICLR 2023
where (d, E) is given in section 2 and Yt.p are the spherical harmonic function of degree é and order p. As a consequence of Theorem we can consider the NN training error with the squared -a-b loss function.
Proof Theorem By Theorem 1 for every l -,....: 7, can write
[lu(k) - -ylle =
yloo + Ea(k),
lea(k)] s |e(k))le Se.
(54)
To estimate the first term, we first note that the matrix I - Hn De is positive semidefinite in (R2", (1)) and || - ByHHaDDll I 1 2nAo (see Theorem have
Since g(x) Di 26 (x),
(I 2r De) E 2n De)''
8=0
P=0
where y (e(x))....,99(66 R". By the Funk-Hecke formula and the quadrature rule, have
Dey") - Σ ckK (x,,
(xp, ())e + e pege(xp) epee 88-1
where o is quadrature error (see eq. (6)). Therefore, in vectorized form, we have H Dey Hey + of or, equivalently, (I 2n De)y² (1 2njee y 2n where ex (e (1, e
.T. By applying I 2n/H R0 De to y for l times. find that
k-1
(I- 2n Do) = 2n y 21
2nue)' (I 2 -
t=
The second term, ey, can be easily bounded from above to obtain
1
|| - 2n /|e Σ (1 2mpr)*
|
t=
The inequality above shows that 21~ 20 D.) Day ef is close to (1 2njue) y We define
L D.)
Σ 2mue)* yr(
E2 =
F=
to be the quantity in the statement of Theorem 2 which measures the accuracy of approximating the eigenvalues and eigenvectors of HD using the eigenvalues and eigenfunctions the continuous kernel K Hence, have
L (1 2 of
H
teg.
(55)
Using the triangle inequality, we have
|22|
Σ lflll
1
c
(
L
VAu
max
μi
14
IsiSe
E=
12

---

Published as a conference paper at ICLR 2023
Recall that Ei=1 Ad, the surface area of gd-1, Next, can write
Σ (1 ( yd
= Σ (1 - 2mme) x²)
De
Σ (1-20 (1-2m ) y²) P=
(1 11 (1 11-2 yd Day
(Jee 95 (y(())e(E)dd +
1n1 ) (1 (1-2n
ビ=
L L
Σ 8=
(1-2 2mpp) 2* 11 +
Σ
(1 (1-221) 211 (1- 21 eiee (56)
1= 20
where we used the fact that Jj and ge are orthogonal in (2( for j l. Combining eq. 55 and eq. (56). we can write
[[ (I- Dylll
(1 - 2212)) 28 |1 + E1kk) + 82.
(57)
where
L L
1 (A:)
-
Σ
(1 2n,,) (1 (1-1111110) 11-22pp)** cj,
1=0
The result follows from eq.
54 and eq. (57p
Similarly, suppose
Theorem I
we can write down Theorem 2 in form such that ea(k)
depends on the parameters of the NN.
Theorem 2 Under the same setup and assumptions of Theorem I let P D. and Mp /marr
g Sd R is bandlimited function with bandlimit L and
1 2npe > for all < l $ L
(see eq. 12 ), then with probability 2 1 we have
ly u(k)lle
(1 2npe))
2k Igel 2 t +22
0 0skST,
(58)
where [ea(k)] is bounded by eq. 51 and E1 (k) and e2 satisfy
VAa
[k)] <
(1 ) (1 (1-2n1u))* ej.
Je2
S
max 1sisn
led
8=0
t=
We remark that the left-hand side of eq. (17 can be rewritten as
ly-u(k)]le =
Σ ca(u - 2x(k))² = Σ - -Nxxx,
[lg - 11 Fiellg Nxx)),
where Ng is the neural network at the kth iteration. Hence, eq. can also be written
llg -Ng-NNll Nall
2mpee
22 lgell +
(59)
(gg - -N, Moreover, assumed g is bandlimited, and as we see in Proposition 2 the spherical harmonic coefficients of A& decay fast the frequency & - This shows that the size of [A)) can also be controlled by %ne in eq. (18). Therefore, we derived a frequency bias statement of the generalization error with respect to the uniform distribution on gd-1
where 61, are in Theorem 2 and [k)] <
13

---

Published as a conference paper at ICLR 2023
D.2 FREQUENCY BIAS UP AN APPROXIMATION ERROR
Theorem shows that we theoretically have frequency bias up to the level of quadrature errors é (k) and 62- If the quadrature errors are large, then we may not observe frequency bias in practice. Here, we show that the quadrature errors can be made arbitrarily small by taking enough samples in the training data. Recall that our quadrature rule satisfies eq. (88
Next, we pass the quadrature error to the approximation error, which may not necessarily be tight. However, this allows us to use the existing theory of spherical harmonies approximation to show the decay of quadrature errors.
Lemma 5. Let f gd-1 R be a function and dist( IT:)
min II h1 We have heng
1 M())EE Σ (xii)) S 2n, |/ 2A [T))
(60)
for any integer& l f20 O.
Proof. Let h4 arg min |lf b By the triangle inequality, we have
hET
18s- f(E)dE Σ cf((x)
n f f(E)dE - 1S-m he(E)dE + +115a he(E)dE Σ Eaheexii) + (he(x)) f(xx))
ga-1
<Agdist(f
I1/)= Th l1belle + Addist(f. S 27m ll + 3A,
where we used the fact that e > 0 for ,,...,7 n and the fact that |ielll S 2|1
Next, we focus on controlling the minimum approximation error dist(f, II:)) on the right-hand side of eq. (60). To do so, prove the following lemma.
Lemma 6. Let (E) = K ())(()) and (in(E) = (E) Then, for a constant C > that only depends d, we have
dist(fij. 11/) < 5 + |ا
isisn,o L,
dist(g;p: I1:) < _ +
11g
- 11 0 0
L.
for all l 1.
Proof. For 1 < < b < d where a, b N, and / E T), let Qa,t, denote the action on $d-1 of rotation by the angle in the (Ia, rbb planee. For an integer a 1, we define the operator on functions on gd-1 by
A = (1 T(Qu,.)))
where TxQ)f(x)= = S(Q If ((S-1)), then we define for t > 0 that
walfit)
max sup A A. Igached 18|st
By DDi & Xu 2013, Thm. 4.4.2), we have
dist(f, I ci (f:et)))
1 121,021.
where e > is some constant that only depends on a. Then it is sufficient to bound w., (Jigi& 8-1) and (gipi 1 to finish the proof.
First, we aim bound the term dist(fe; (1d) where fiy(E) K k (E), We fix < i n, 1 5 < b < d where a, b E N, and choose 0 such that 18] e-1 We have
Lessllll = -1( (2.(Q
1.00
14

---

Published as a conference paper at ICLR 2023
We then define
o =- (x 2 - (x;,
=- = --(00,,)) -g)(E))
We then have
- 1,00 = =1|K< (g))())))))) (K (1
(1 (g) (g)( p0 + || (x, E)) (E)
(61)
We control the terms separately. First, to control the second term, we write
(x, (4)l22> S ||| (xi, +> (5) S (رو,
(62)
based on the definition of K in eq. For some constant (2 > 0 that depends only on d, we have
S c2 j 119
(6g;(E)) 1= = 0,,0 , S ozt (Da
(63)
where Do. 0g Izdd and the two inequalities follow from (Dai & Xu 2013 Lem. 4.2.2
(iii) and (Dai & Xu 2013 Lem. 4.2.4), respectively. Next, we control the first term of eq. (6T by writing
(E)
(g)(1) S (6)7(())l (1,(0 = [))K)()))lz= 2
(64)
We fix & and define g' = Qu,b,e5. It follows that
8K; (E) k0 (x E') K (x,, E)
= 4T [(x] g' + 1) arccosi x E1) - (x] E + ( E))]
4 [x' - <) (TT - arccos(x; E)) - (x] 5' + 1) (arccos -)x arccoss {
Next, by the triangle inequality for angles, we have
|arccos(x; E) arccos(> < S | S E-1
Since arccos is monotone and ((d/ dt) ar)cos(t)l > 1 for all t, by the fundamental theorem of calculus, must have
x - x S [arccos(x] { arccos(x? [x') < e
As result, we have
+ 2 c-1 4T
|8K S 4x
[e x + 26 26-
(65)
By eq.
64 and eq.
655
we find that
T T+2 6-1
||KK (E) 8g, (E))
|| 1
(66)
4T
Putting eqs. 61 to 63 and (66) together, obtain
π +
A -- (o(()) fer (Q..b. I
+ [2)
e-1 ||gs |
4x
Since a, b, and 0 chosen arbitrarily, this bound also holds for wi (feji 1-1).
Second, aim to bound the term dist(gpp: I1)) where g)p(E) gj (E)g, As before, fix the b < d and 0 such that [0] < E-1 Similarly, define
indices a, b E N where
رgح ($) g3 (Q.b. ),((), (gp(E) gp (QTT) (E)
By eq.
63 we have
(E)) 9,9, 9,9, (2
(E),()) (g)(E) + 5g, (E)) + 5g
1,00
|lōg, (E) (gp ( (E))(E)ogp (E)
(67)
< <²² + و 1, |ل
Since b, and 0 are arbitrary numbers, this bound also holds for wi (gipi 1-1).
15

---

Published as a conference paper at ICLR 2023
Using these lemmas, can prove that Theorem asymptotically controls the quadrature errors.
Proof of Theorem
First, we control (k) as
L
(ei(k)]
" (1 (1)p))))* eip S 122n11))*
1= p=0
f=0
7
e |> + 2Addist(gip= IT/)
==
p=0
Σ
2mm I1l 1ppll + 2A.C + 1ااوا 11spl1..)
E
j= p=0
where the third and the forth inequalities follow from Lemma and Lemma respectively. The final upper bound for [k)) holds since oo Ep + p) = O(L"). Next, there exists C2 such that we can control 82 by writing
VAa
L VAd (2 Smm.el99jl12 119 + -2A +1 119011
|22
max Siin
Σ
Hi
1=0
j=0
S C2
Σ
(
L2 +Lme)) Lime) max I
where the second and the third inequalities follow from Lemma and Lemma respectively. The proof is complete.
O
Proof of Corvllary 7 By Theorem suffices to show that maxosjsr 119; 1m S C Clgllia for some constant C > that does not depend on g. Since Hid 1 Hj in I for * j. we have 119,1l12 & lR for S j < The claim follows from the fact that I|-ll and I1 are equivalent in 117.
E THE THEORY OF FREQUENCY BIAS WITH A H8-BASED LOSS FUNCTION
This section presents detailed proofs for Proposition and Theorem in Section which concerns the frequency bias behavior of NN training using the H loss function.
E. A 2-LAYER RELU NEURAL NETWORK IN H H FOR 3/2
We prove that 2-layer ReLU NN map is contained in H=dd- for any < 3/2 (see Proposi- tion
Proof of Proposition
Since N can be written
m
N(x)
Σ a, ReL xw,
Rd, b E RR. Since ReLU((x) aReI.U(x) for any >> 0, we can assume that |w|| = 1. Moreover, since the Sobolev spaces are rotationally invariant, we can assume that w (1, 0, O) Then, f can be written as
suffices prove that f(x) = ReLU(w T x+b) Hd for all w E Rd
f(x) ReI.U(r + b).
b < -1 or then f(x) is constant, and thus f E (S for all R. We assume
<<<b< Then, we have
[I]
Φ b
f(x)
0,
z S b.
16

---

Published as a conference paper at ICLR 2023
We define the function
(x(f)x)== = [Ts(x) f(x)]
dt,
125+1
where
I.f(x) = =f ffrr F(E)dE,
C(x,t)= 15 su-1 arrcoo(E x) S 5t.
(o
Here, fC(K.A) S(E)dE = 10(xx1)1 Scrxe [(E)d is the averaged integral, where |C(x, () is the Lebesgue measure of C(x, 1). Then, by (Barceló et al. 2020 Thm. 1.1), we have f E H 1 if and only if S& (S) is integrable. We now show that ( () is integrable on both Ei {x S 21 > bb} and Eg = fx gd-1 2 < b} if < 3/2.
First, we define the function
h(x) - x + b.
Then, H))))-1). If we can show that
/-- I f)(x) (h (xx))
S,(h f)))
dt
{20+1
integrable on E,, then we have
/ E,
E, 10
[xs(x) - f(x)
Sa([(x)ddx
dldx
120+1
In((x) - Mxx)2 + [I, ()xx) - (0--000- (x)]
2 2
didx (68)
(20+1
= 2 E1
(,(h)(x)xx +2 S,(h - ()x) <0.
E1
Assume F,, and let be the minimum angular distance between and any point in the set
S (E E Sd-1 S E = -b). i.e., P minges arccos x). Then, for 0 < t S p. we clearly have
[1 (x) 0 = (h- ()). Assume p < f m. We divide C(x, t) into two parts C and Co
up to Lebesgue null set, where C. = C(x, t) n E.. Then, h - f = 0 on Cj. Next, by 201
we know that the measure of C22 satisfies
1C2l - θ (1(² C((x, ()I
8 0²
12 2 1 -
( B
2 p²
2 1)
ttpt
12
where / the regularized incomplete beta function and the incomplete beta function. Here and throughout the proof, the constants in the big-O notations independent of p but possibly depend on and d, which are fixed in the proof. Moreover, we have the formula
2
0² d 1 12
[tt
/2)//////2 F
d d+2 1
B
2'2
d/2
2' 2
where F is the hypergeometric function that converges to 1 as 1 + p² sect. 8.17, sect. 15.2). Hence, we have
Olver et al. 2010
C2
(U-
p)d/2
= +
1 1->0 pt.
(69)
C((x
fd/2
Now, by the way we defined h f. there exist constants R1, R₂ > 0 such that Ih (1) s Rt p).
C2
t 1-p)
hh (l)) > Rt p).
gE c C2
min arccos 0) 2 AES
2
For two functions (t) and B(t), we say at)) e(((t) as + p² if there exist positive constants Ct, Cr and radius > 0 such that C, a(t) < (() for all tt-pt <.
17

---

Published as a conference paper at ICLR 2023
This gives us
((ttp))(e+)))
(h (n- =0
1d12
1 l
(70)
1d/2
Now, we have
10 1/¹ (-2--11(h--1((x
("
-" 1-20-1 (foreen
(n (h- (EEddo))
de
(((lt-ppaa+200 2) -0
= 0 1-200-1-1(
0(p2-20 2 +
To integrate S, - over E,, we first change the coordinates and integrate over Sd-2 by fixing p. The resulting integral is still in @(p from the fact that function in (pp + 1) is integrable near = 0 if and only if < 3/2. This proves (. - f) is integrable Eς if and only if < 3/2. Note that if S, on E1. then (f) is neither integrable. This proves the proposition when 2 3/2.
1). We then integrate over p and the result follows
[) is not integrable
To see S,(f) is integrable over Eg when
3/2, we note that f can be rewritten as f h where f(x) ReI.U(-11 b) and h(x) = -1 - b. By the same argument, we have that Sz(f) (f h) is integrable on Ez, which completes the proof.
E.2 FREQUENCY BIAS WITH A SQUARED SOBOLEV NORM AS THE LOSS FUNCTION
In this section, we prove Theorem 4 on Sobolev training. Recall that we compute the !/-bbased loss based on eq. (20).
Proof of Theorem Fix some 0 < é < T.. We can write
Erss N(d.)
N(d.f)
Lre N(d.j)
HOP
H wya
Σ
H H wis
H H w
(71)
where (1 + 2)2s and we used the fact that
Jp .(( Su (E)(()))(E)dE + es
ge.p + cii Cipp'
i = if otherwise.
Next, we have
H ajm);
{ fga-1
(V,, + el (1yYii((x + Cig.p
where the last equality follows from the Funk-Hecke formula. Hence, the first term in eq. can be written
(d.E)
N(d.))
N(d.e)
Σ H wrarp
Σ
(uyYe + deeeee = HyWey (x,) (x:)+ + Σ
p=1
Moreover, the second term in eq.
7I
can be written as
Emx N(d.f)
Lus N(d.j)
Σ
Σ H
Σ
Σ
weels (M5)) + choz))
1=0 p=1
Therefore, we have
HOP of u + w/ef
(72)
where
N(d,8)
N(d.j)
(Ef);
Σ
W/
eijoo (ugY),((Xs) + el
(73)
we
18

---

Published as a conference paper at ICLR 2023
Applying eq. (22 recursively, have
L A-1
(I Po)
(1 2nweas) ) yf-2212 -2 0
Σ (1 2mwwwe) (I 21-2n .) jk k- Wie
0
Now, since HoP, P. is self-adjoint and positive definite in (R", (s )p, ). by the way we pick y, we guarantee that I - Pr is positive definite in (RR", (t, (p, and hence
|| - Ps S 112100
This gives us |eIlp,, s Et Me 1 | and the result follows from Theorem
While Theorem captures the frequency bias in squared Hº loss training up quadrature errors, analyzing the quadrature errors can be task-specific. Therefore, studying the quadrature rules could be direction of future research.
Suppose we use Theorem [ in the proof, we can write down Theorem in a form such that 62 62)) depends the parameters of the NN.
Theorem 4 Suppose g E I1 and 4 is the loss function in eq. 20
where Ps is positive definite
and C max Under the assumptions of Theorem [ if 2n
1)20 0 ffr all S S L,
then with probability 2 1- - 5 over the random initialization, we have
y-u(k)
Σ 111-2mue(111 + t)20)* o + +11 8=0
0 OSKST,
(74)
where [[2((k]|p,, is bounded by eq. E satisfies
51 with Mp Mr,, and yd (e. (xx))) and
L
fecr
(1+j) (ddjj)
|eilpp, S En
(
Σ el (ps
+c(sp)
(1+
t=0
jm0
pml
Moreover, we note that the remark after the proof of Theorem applies here as well. In particular, using the relation that
yy
u(k)le
Vllg NNl12 Pc((o-Na)3)
we can rewrite eq.
21 into
l1g Nellz
Σ (1 2m + 1)20)* ye
t + =z(k)) Ek)))
(75)
6=0
where lEil <
|| (k))
< ||2(k)]le are in Theorem By eq. (7). we can directly relate E
and (Es(
V VeElg- - N..
+ e)2m) yd to
V Et (1 (1- 2 (1 + 2)2+)²2 26 ll up to some quadrature errors. Therefore, the generalization eтror with respect to the uniform distribution can be written as
llg - -- Σ (1-2 (1-2nu +1 l1gell + ENTK + Equad
where ENIK an error that can be made arbitrarily small by taking λ small enough and large enough and Eqund involves only quadrature errors and can be made arbitrarily small if we make the quadrature rule accurate enough.
F EXPERIMENTAL DETAILS
We now present the details of the three experiments in Section
19

---

Published as a conference paper at ICLR 2023
F.1 LEARNING TRIGONOMETRES POLYNOMIALS ON THE UNIT CIRCLE
In section6..1 we train a NN with data derived from sampling trigonometric polynomial at nonuni- form points the unit circle. The n 1140 nonuniform data points (x.) for this test are generated
by taking the union of three sets of equally spaced points, as shown in Figure [I The data set {(cos(0.), sin(O.))} contains 100 equally spaced nodes sampled from 0 E (0, 2 superimposed
with 40 equally spaced nodes sampled from 0 E [0, 0.3T] and 1000 equally spaced nodes sampled left). We construct the quadrature weights ej by minimizing Σ5=1 S. under the constraints that the e,'s 's are positive and the quadrature rule is exact 11 i.e.,
from E [1.4T, 1.8T] (see Figure [
(f) = 0 for all f E ug.. Note that due to the linearity of the quadrature rule, it suffices to check
finite set of linear constraints
=
0 S 1 p (2)
This computation method is proposed in (Mhaskar et al., 2000). Here, 55 is selected to an integer close to the maximum degree l such that there exists positive quadrature rule exact IIş. In the upper-bounds of the quadrature errors in Theorem 3 there exist terms
I,3
T.2
E + I. Tm,e,
{ + I=/n,e
(76)
where L is a constant bandlimit of the target function. By requiring the quadrature rule to be exact on ILE we guarantee that 6, O. Hence. by requiring to to be large,
heuristically make Tn.e smaller for a moderate This allows us to show that the upper-bounds in eq. (76) are small by balancing the term that involves t-1, which vanishes as l + oo, and the term that involves To.6. which increases as & + oo. This justifies why compute the quadrature rule by requiring it to be exact on spherical harmonies of degree as large as possible.
The experiment consists of two parts. First, compare the effects of training with the loss function T based on eq. (1) against the squared I.2 loss function T in eq. (3). where
Ad
Φ W)
[(xx) - (x:))
((W)
cs (W(x)) - g(x:)
2n 1=1
2
We define the target function to be
9
g(x) = 5 Σ sin(
x x= x(0) = (cos 0, sin 0) ES²,
where =(0)= = (((())). We set up two 2-layer ReLU-activated NNs with 5 x 10 hidden neurons in each layer and train them using the same training data and gradient descent procedure, except with different loss functions & and $. Figure 5 we showed the evolution of the NNs trained using & and 6, respectively. While the NN trained with & approximates the function very well in the region where the training data are dense (i.e., where 0 E [1.4x, 1.8T] RJ [4.40, 5.65)), the NN trained with h provides better overall approximation the entire domain and demonstrates frequency bias much more clearly.
To evaluate the frequency loss, collect 100 uniform samples from N(x) and g(x) and compute the Fourier coefficients (E) and g() such that functions
30
30
-(x)=1(00) NO
Σ N
g(x) = -(0) & Σ 20)
where [[) ((x())). The frequency loss (N( g()) estimates how g(x) is approximated by ((() at the frequency E when training with the different loss functions (see Figure || middle). In addition, we also train the NN to learn each individual frequency with the training data coming from ge = (80 and count the number of iterations it takes to obtain & (W) < 1.0 x 10 (see Figure right).
The second part of the experiment focuses on NN training with a discretized squared Sobolev norm as the loss function. More precisely, we fix some E R and consider the Sobolev loss func- tion eq. (20). For S1, we have N E) 2 if & > 0. We take Yx,(x)) sin((0)/ /2xx and (x)( cos(e0)) /2n where the /2m factor is a normalization factor.
20

---

Published as a conference paper at ICLR 2023
Iteration 1000
Iteration = 5000
Iteration 9000
value
value
value
domain
domain
domain
Figure 5: The target function (black, dotted), the NN trained with & (blue, solid), and the NN trained
with & (red, solid). The purple bars the horizontal axes show the positions of the training data.
loss
loss
loss
200
B00
100
300
100 400 300
epochs
epochs
epochs
Figure 6: Frequency loss for f = 3 (blue), / - 5 (red), and f = 9 (yellow) based on the squared H 1. The error bars are generated using the results obtained by executions with thirty different random seeds. In the left figure, the result of one of the thirty executions is omitted because the NN is trapped by a local minimizer that is not a global one, making the NN not converge to the target function.
norm as loss function. Left: 8 1; Middle: O; Right:
We 6mux 30 eq. (20 and learn g with different values ranging from to For each s, we compute the frequency loss (V(()= [(8) after different numbers epochs. As increases, the frequency loss for higher frequencies decays faster (see Figure 6). In particular,
in Figure 2 the "rainbow" plot, that when s = -1, the lower-frequee frequency losses are much smaller than the higher ones after 5000 iterations, while when the higher frequencies are learned faster than the lower ones.
F.2 LEARNING SPHERICAL HARMONICS ON THE UNIT SPHERF.
In 6.2 we train NN with data derived from sampling a function defined on S2 nonuniform points. The training data is a maximum determinant set of 2500 points that comes from the so-called "spherepts" dataset (Wright & Michaels, 2015). In this experiment, the target function
g(x) = (x),
where Y2.0 is the normalized zonal spherical harmonic function of degree 26, Therefore, the spher-
ical harmonic coefficients of y defined in eq. (4) satisfy Gr.p 1 if p 0 and e 2, 4, 30. and Ge.p otherwise. We then train an NN with the squared H norm as the loss function (see eq. 20
for 1, 2.5. By Theorem 4 need fmxx 2 L 30. We set Emax 40 in eq. (20) assum-
ing that the bandwidth L is not known a priori. We observe frequency bias in this experiment by considering [N ge,pl after each epoch for i = 4, 10, 20. We confirm that low frequencies of are captured earlier in training than high frequencies when s -1 and
(see Figure 3 left
and middle), and that this frequency bias phenomena can be counterbalanced by taking s 2.5 (see Figure right).
F.3 TEST ON AUTOENCODER
Autoencoders can be used as generative model to randomly generate new data that is similar to the training data. In this experiment, we use Sobolev-basee norms to improve NN training for producing new images of digits that match the MNIST dataset. In our final experiment, same autoencoder architecture as in (Chollet 2016), except we train the autoencoder with a different loss function (see section 6.3)
the
21

---

Published as a conference paper at ICLR 2023
Here, for training images {x,), standard loss function can be
1 S (W)) = ク/ (x)(N(()))
1 2n
Σ dxst((V(x,).a))
where j is the distribution of the training images and dist(N(x,,) x,) is a distance between the output of the NN given by (xx and the image x. We select the distance metric to measure the difference between (xx) and x as
1 S (W)
2n Σ ( xi112.
(77)
where || denotes the matrix Frohenius norm. The distance metric in eq. 77 can be viewed as a discretization of the continuous L norm. That is, one imagines generating a continuous function :: [0, 112 + [0, oo) that interpolates an image as well as a function that interpolates the NN, then
|| [W(z))) v2) x 92)) dy = [[V(()) - x112a.
[Ix(()) - x11
pixel
where Mpixel is the total number of pixels of the image In this continuous viewpoint, the /1" norm is given by (assuming that the continuous interpolating functions x and (xx) are constructed with periodic boundary conditions)
[[W(x) - x1121- -f
(1 (1+ (1+IPPYWWWCE - -(E)) |s. o (Vx - 12: (78)
where Fr, Fr are the left and right 2D-DFT matrices, respectively, (S.) = (1+ 12 + + 2 and oo is the Hadamard product. Hence, if we define vec(A) to be the vector obtained by reshaping matrix A using the column-major order, then we have
||S (Fr (N(x) - x) F.) I = (ddia(vec(S.)) @ Fi)veo(N((x) - x)112
where @ the Kronecker product of two matrices. Setting J. = diag(vec(S.)) @ Ff), the loss function in our NN training can be written as
1
JJ, vec (N(x,) x;) 1 (1
D, (W)
(79)
2n
where I is the n-by-n identity matrix and u, y are the vectors of length n x N Npixel given by (vec(N(xx))) ..... vec(N((x,)) ) and y (vec(x1)" ..... vec(x,) TT Hence, the discrete NTK matrix is given by n H @ J J.). where the (i, sub-block is H =
(vxe)))) @voo(Vix, :W)) for j ,,,,.,,77 71 Here, (Drec(Nix:::) (v :W1) is inter- JW
OW
OW
UW ( (x))))
preted as the -ypixe-b---Niice matrix whose (d', th entry is ( (ixvec
&W
SW
This means that the frequency bias behavior during NN training is directly affected by the choice of
s. Alternatively, one can consider this problem more abstractly from an operator learning perspec-
tive, which is presented in appendix[G] We remark that while eq. (79) is a mathematically equivalent expression for the loss function that allows us to easily express the NTK, in practice, we implement the loss function based on eq. (78) using a 2D FFT protocol.
We use the same autoencoder architecture as in (Chollet 2016). except with the loss function 1,, 1. We train the autoencoder using mini-batch gradient descent with
in eq. (79) for batch size equal to 256. We first pollute the training images with low-frequency noise and train the NN. hoping that the trained NN will act filter for the noise. We see that training the NN with eq. (79) for = 1 gives us the best results due to the high- figh-frequency bias induced by choice of the loss function. Although HT is low-frequency bias, the high-frequency bias of J J. domi- nates for sufficiently large s. In that case, the low-frequency noise barely changes the training in the earlier epochs as the low-frequency components of the residual correspond to small eigenvalues of H (I & J J.). Similar results are discussed in (Engquist et al. 2020) and (Zhu et al. 2021 in the inverse problem and image processing contexts, respectively.
The opposite phenomenon occurs when we add high-frequency noise (see Figure bottom row). Since 0 by itself makes the NN training procedure bias towards www-frequencies, the output for
does already filter fighffreueency noise. Since J. for s < 0 further biases towards low- frequencies, one can obtain better high-frequency filters. We observe that the best denoising results for the autoencoder come from selecting -1 (see Figure bottom row).
22

---

Published as a conference paper at ICLR 2023
G NTK AND FREQUENCY BIAS IN OPERATOR LEARNING
We saw how using the -a-based losses can help us tune frequency bias in training the autoencoder (see section 6.3). In fact, in training the autoencoder, are learning the identity operator the space of images. In this section, we briefly mention the NTK associated with operator learning and its consequences. Let be linear operator LL Let D (f1,..., [N) be a finite subset of L L and XI....,X, XXM be distinct "samplers" in g gd-1 Since L is linear, without loss of generality, we assume [|(f((x)).... Ji(xM)) "122 = for = 1,...,A .N. Given a function f. we use f(x to denote the vector (f(x)),.... .... f(xM))) We consider fully-connected two-layer ReLU NN, = (W1,...,,N5 ). that takes M inputs and produces M outputs. The goal of training is to learn the linear operator L D. That is, want (f (xx)) = (x,)(x)). In other words, given the samples f (x) of a function f. we want the NN to output the values of Cf at X1, ................................ XM, i.e., (x)) As before, we let P be an M x M symmetric positive definite matrix that measures the distance between two I,2 functions given their samples at X1, XM- That is,
D(((x), g(x)) = (J(() g()) T P(S(x) - g(x)).
We then consider loss function of the operator NN given by
N
4 (W)
Σ N
D((CF(()), N(A)).
(80)
where N(A)) = NAI (fi) in which NG((f) denotes the jth output of the NN when we input f.. That is, NV.(.)) (x)(())))) Let w be the ith weight in the jth neuron of the first hidden layer, 1 S S M and 1 S S m. where m the number of hidden neurons. Let by be the bias term of the jth neuron in the hidden layer. Let Wi. be the ith weight in the jth neuron of the output layer, so S i S m and S S M. assume the same initialization scheme. That is, w are initialized from iid Gaussian and by are initialized to 0, and they are updated during training, whereas w are initialized from iid Rademacher random variables and are not updated during training. In the derivation of the NTK below, we let W to be the vector of all trainable
weights and biases, (1) and b,. enumerated in an (arbitrary) fixed order. This allows us write W (wi...., wx) T, where K m(M + 1).
We assume that the gradient flow algorithm is used to train the NN, i.e., the vector of labels by
aW
8W We define
de
y; = (,,( L
== INI
Similarly, define the vector of the NN outputs by
u; (W) (Ni .M. W)) Our goal is to understand _ (y - u) and write it in terms of y u. To this end, we first consider
[u] TT
d(y; - u, (W))
(W) du, (W) dW (w) O
(81)
dt Denote by Wk the kth entry of W, where 1 S k s K. Then, by the chain rule, the kth entry of (o(W) can be written as aw
dt
dW dt dW OW
O (D(W) @D(W)
N
(((CF)(()) (z)f
dW
Own
N
Own
aD ((C (xx, (x)+)(x))
aN W)
N
aN();; W)
Owo
Lfv(x)) - -N((Ft)
aNax(Se) Dor
P
Cfr(XM) - (Fr)
23

---

Published as a conference paper at ICLR 2023
Hence, we have
aN
Cfv(x)) -M((f)
N
8wg
8hr
a
W
1
P
(82)
ow
N
P=1
(N
aNvrlfue Dank
(Jv(XM) - (Fr)
Chek
Now, combining eq.
81
with eq.
822
have
(Ni)
(N)
du, W
Own
Owk
dt
(h
Jan
dwx
aNuilaa
(xx( -N((F))
N
Oue
Cher
P
:
8N OarK
(CF((MM) -
dwx
which gives us
J J1
J
dly (ly-u(W))
du W)
1
:
(IN @ Py u).
(83)
dl
dl
N
J J JNJN
The derivation so far does not not rely on the architecture of the NN. fact, holds for the loss function & defined in eq. (80) with any abstract function M(f;; W). Now, exploit the NN architecture to study J. Jp. Consider the (j.j") f'.jt)) th entry of JJ Jg. We have
(J, Jo)6) 1
(2) (2) f((x) fx( + ku 2
(f((x) w/ +6 (x) (() (0 200" (84)
2
M is the collection of weights on the kth hidden neuron. Now, note that Wk. W.y = 1 i = j and is Rademacher random variable when j + j'. Hence, by the way
where w [wi.k-- (2) (2)
we initialize - we have
[J(()) fx()) + 1)(r (fcc)
I
(85)
4m
where the convergence is entry-wise. Now, suppose define the N x N matrix H as
H fv(())T((x)) 1)( (f) fx(x)))
(86)
4x
That is, we define H as in the function learning case, except that the inputs are (f((x)) instead
of {x,)² p By eq. (85) have
J J
M-
0 & IM,
(87)
J
JN
where the convergence is entrywise. Hence, we discretize the gradient flow algorithm and apply gradient descent with step size 77, then by eq. 83 and eq.
88 we expect that
N
Y: - (k) ~ (y: - u - 1))
H.
00 Ply. - ug 1)),
(88)
N
24

---

Published as a conference paper at ICLR 2023
otherwise written compactly,
(I &P))"
((k) = [IN (Ho
(89)
N
the variance in the initialization is small enough.
Given this characterization of the residual equation 89 we can see how the usage of the Sobolev loss plays role in tuning frequency bias. Suppose we decompose the residual vector into
M(d.E)
Yi - uk) = Σ
E,ps
t=
where Ytp- = (Vem(x))..... (xM)) is the evaluation of the spherical harmonic on Sd-1 Then, 7/2 measures the amount of frequency loss associated with the p)th frequency in learning the function fi. Let (k) = (K))........ (k)) The size of (k) measures the amount of overall frequency-E components (in the pth direction) in the residuals after the kth iteration. Assume wy is an eigenvalue of associated with the eigenspace that is approximately spanned by
N(d.)) Note that this is the case when P = P. is associated with the squared- loss on (Ye,p) (pmll (
gd-1 Then, by eq. 188) have
[N - 1 ) & N yrv.
(1))
(90)
where gfP = -( ,.....''' ,NND) is defined by the decomposition
(dd.))
Y t.p
Equation (90) demonstrates that we relatively large for bigger (e.g., when we use the squared- H loss with large s > 0), then expect that (k))(() decays much faster for high frequencies than the low ones, and vice versa. This connects frequency bias in operator learning to the spectral properties of P.. We studied and justified the phenomena in the autoencoder experiment in Sec. 6.3.
H COMPUTATION OF QUADRATURE WEIGHTS
In practice the training dataset usually does not come with a carefully designed quadrature rule. Hence, inevitably need compute set of quadrature weights before training the NN, In this section, we briefly discuss methods for computing positive quadrature weights.
Given set of points { on gd-1 we wish to construct quadrature rule so that
1=))== = Da (x((x)) Re
[___5xx f(x)dx
for sufficiently smooth f. where > O are positive quadrature weights. One approach that could give us a very accurate quadrature rule is guarantee that
(n(f) = f f(x)xx,
fe fellf.
(91)
32-1
where dim < The one-dimensional case of such quadrature rules was studied in (Austin
Trefethen 2017 Yu & Townsend 2022) and the general higher-dimensional case was analyzed
2000 Dai & Xu 2013). Given any dataset {x, } and & so that dim(115) < n. one cannot guarantee the existence of a positive quadrature rule satisfying eq. (91) (Mhaskar et al,
in (Mhaskar et al.
2000
Dai & Xu 2013),
when the distribution of {x,) is very regular (Yu & Townsend On the other hand, by choosing l to be small, we can eventually find an for which eq. (91)
2022
holds.
When such positive quadrature rule exists, Mhaskar et al. (2000) proposed to solve the
25

---

Published as a conference paper at ICLR 2023
following feasible constrained quadratic program
min
s.t. G 0 L1 sisn, n f gu-1 (x)xx
c (x)ss(x))) Σ
VA vosjstlSPS N(d,))
While eq. (9T) gives us a guarantee on the accuracy of the quadrature rule (provided is not too small), it is not always practical to compute the quadrature weights in this way. Indeed, if d is large, then we need a tremendous amount of points to guarantee that dim(II)) S even for small l. Also, if we have too many data points, then the quadratic program can get infeasible to solve. Hence, we need some other methods for computing quadrature weights that, albeit less accurate, can be applied more cheaply to general datasets. One of the many possible approaches is to do kernel density estimation (Rosenblatt) 1956 Parzen 1962). To do so, we fix a positive kernel K((x, y) = X[(accos(xx T y)) defined on $" x S A common choice of K. can be the Gaussian density function standard deviation centered at O. For each > O, we then define a function ps. on gd-1 by
Σ K arccos(x x;) i=1
Ph (x)
The bandwidth is hyperparameter, and with an appropriate h, the function ps is an (unnormal- ized) estimate of the density function of the distribution of nodes. Hence, by setting
Ph (x:)
G
Ad
(92)
2j=1 Ph. (xx)
we obtain positive quadrature rule that approximates the integral of smooth functions on Sd-1
26


Reviews:
[{"review_id": "tcTRd1buS5", "reviewer": "Reviewer_JXdi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 paper proposes to use quadratures to approximate the $L_2$ error of NTK training. By doing so, the spectral analysis of NTK training can be extended to non-uniform data. Further, this paper proposes to use a Sobolev norm to modify the loss function so that the convergence under the modified loss function will exhibit different spectral behavior. By doing so the authors were able to tune the spectral bias of NN training.", "summary_of_the_review": "Given the current state of this paper, I recommend weak reject due to the lack of support on the quadrature weights assumption, Eqn (17).", "strength_and_weaknesses": "Strength:\n1. The introduction of the Sobolev-norm loss function is new and interesting. It can explicitly guide NTK training to favor higher frequencies or lower frequencies.\n\nWeakness:\n1. The idea of using quadrature to approximate the loss function seems not well supported. My main concern is that it seems not easy to find good quadrature when given only the training data, namely, identifying proper $c_i$. Theorem 2 bounds the loss by the quadrature approximation error, and Theorem 3 assumes there is a quadrature weight $c_i$ ready to use. None of these indicate that $c_i$ can be determined properly. This heavily decreases the significance of this work.", "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": "npdwGOpjYv-", "reviewer": "Reviewer_g5Zh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 paper deal with training a NN with the nonuniform data distribution under the NTK regime. This paper assumes a data-dependent quadrature rule to build bound for non-uniform data. ", "summary_of_the_review": "The paper is super interesting, but the results are hard to interpret. Although I have criticized this paper a lot int he weakness part, I still think  the quadrature rule  idea here is super interesting and is worth accepting. ", "strength_and_weaknesses": "Strength:\nThe link between the data-dependent quadrature rule and non-uniform data is super interesting. I also believe this is the right way to conduct the research.\n\nWeakness:\n\nHowever, the paper presents a pretty hard-to-read bond, and I can't understand how different components of the assumptions are involved in the final results. I suggest the authors use a simple model to illustrate how different factors contribute to the bounds. The starting point I suggest is [1-5], which considers kernel gradient descent under Sobolev/L2 losses.\n\nAt the same time, in the abstract and main context, the author claims\n> Small generalization errors of over-parameterized neural networks (NNs) can be partially explained by the frequency biasing phenomenon\nHowever, as I understand, this paper deals with optimization but not the generalization error. I think the author can follow that variance analysis in [1-5] to see how this relates to the generalization properties. I think it would be interesting to see whether the error introduced by the quadrature rule will ruin the generalization error. (Or this can be revealed by the theorem in this version's paper)\n\nMy third concern is about the algorithm, the algorithm is not a gradient descent to original loss but needs to know the P. For a random dataset sampled from an unknown distribution, Is there any way to estimate the P?\n\nAt the same time,  I would like to ask is $H^\\infty P$ diagonalizable? To me this formulation is strange for the matrix here should be the gram matrix, which is symmetry. I guess the matrix should be $\\nabla f^\\top P \\nabla f$.\n\n[1] Pillaud-Vivien L, Rudi A, Bach F. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. Advances in Neural Information Processing Systems, 2018, 31.\n\n[2] Lin J, Rosasco L. Optimal rates for multi-pass stochastic gradient methods[J]. The Journal of Machine Learning Research, 2017, 18(1): 3375-3421.\n\n[3] Nitanda A, Suzuki T. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime[J]. arXiv preprint arXiv:2006.12297, 2020.\n\n[4] Mücke N, Reiss E. Stochastic gradient descent in Hilbert scales: smoothness, preconditioning and earlier stopping. arXiv preprint arXiv:2006.10840, 2020.\n\n[5] Lu Y, Blanchet J, Ying L. Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent. arXiv preprint arXiv:2205.07331, 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "HEatF_szKN", "reviewer": "Reviewer_XAwZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Motivated by quadrature rules, this paper studies the convergence of shallow ReLU networks trained on a quadratic loss defined by a symmetric positive definite matrix $P$.  They study the convergence rate along different components of the matrix determined by the NTK and the matrix $P$ for general target functions.  When $P$ is diagonal and the target is bandlimited, the convergence can be understood in terms of the eigenvalues of the NTK integral operator and the spherical harmonic components of the target.  They also demonstrate that by using a Sobolev-based loss function, one can modulate or even reverse the spectral bias by punishing low/high frequencies at different rates.", "summary_of_the_review": "**Summary**\n\nThis work illustrates how one can modulate the bias arising from the NTK by optimizing a quadratic loss determined by an appropriately chosen matrix $P$.  Furthermore they introduce Sobolev-style loss functions to enhance or reverse the low frequency bias of feedforward networks.  I believe these are contributions that the ICLR community will be interested in, and thus I recommend to accept this paper.\n\n**Comments and Questions for the authors**\n\nNote on page 2 that equation (2) is only true when one is performing gradient descent on the population loss and not the empirical loss.  It is worth emphasizing this to the reader as one in practice only has access to the empirical loss.\n\nOn page 2 you state “Under the assumptions that the weights do not change much during training, one can consider the NTK in the mean-field regime given the underlying time-independent distribution of $W$, i.e., $K_\\infty(x, x') = \\mathbb{E}_W[K(x, x' ;W)]$ (Du et al., 2018).” \n I think it is more appropriate to call this regime the NTK regime and not the mean-field regime.  The parameterization and dynamics in the NTK setting are distinct from the mean field setting [2].\n\nOn page 4 you state “As a consequence of Proposition 1, the matrix $H^\\infty P$ has positive eigenvalues, which we denote by $\\lambda_{n - 1} \\geq \\cdots \\geq \\lambda_0 > 0$”.  This is true but it is not obvious that $H^\\infty P$ is diagonalizable.  Worth referencing your discussion in page 1 in the Appendix here.\n\nThe formatting of Theorem 1 seems off.  Can you put the theorem statement in a theorem environment which should put the statement in italics.  Or alternatively, could you introduce a different formatting to make the statement stick out from the surrounding text.\n\nOn page 5 you state “Therefore, our rate of convergence does not vanish as\nthe number of training data points $n \\rightarrow \\infty$, provided that $M_{\\textbf{P}} = \\mathcal{O}(n^{−1/2})$\n. This is the case when $P = n^{-1}I$ which corresponds to eq. (1).  So, we overcome the vanishing convergence rate issue that appears in previous analyses of frequency biasing (Arora et al., 2019; Basri et al., 2019). As $\\eta$ decreases, the gradient descent algorithm gets closer to the gradient flow algorithm (Du et al., 2018), which allows us to more accurately quantify the frequency biasing (see section 4).”  This is not a fair comparison because Arora et al. [3]  and Basri et al. [4] work with the unnormalized squared error ($P = I$ without $1/n$ normalization) versus the choice $P = n^{-1} I$ corresponds to the mean squared error.  If you set $P = I$ you still have the same issue with vanishing convergence and learning rates as you send $n \\rightarrow \\infty$.\n\nOn page 6 you state “Under the reasonable assumption that our quadrature rule satisfies eq. (17), we can bound the quadrature errors appearing in Theorem 2.”  Is there any way to verify this assumption, at least in reasonable settings?\n\nOn page 6 in Theorem 3, may be worth stating that $\\ell$ in the theorem comes from equation (17)\n\nOn page 8 you state that you “compute the quadrature weights $(c_i)_{i=1}^n$ for the loss function $\\tilde{\\Phi}$ in eq. (3).” Perhaps mention how you compute the quadrature weights.\n\nOn page 9 in the last paragraph you state “Here, we present the results of the autoencoder for image denoising using the MNIST dataset LeCun et al. (2010)”, however the figure is earlier on the page.  Also there is no conclusion section and the article ends abruptly.  This issue should be fixed before the final version.\n\nOn page 1 in the Appendix you state “Since $H^\\infty$ are symmetric positive definite matrices (see Proposition 1), $H^\\infty P$ has positive real eigenvalues.”  I think you meant to say “Since $H^\\infty$, $P$ are symmetric positive definite matrices”\n\nReferences:\n\n[1] Ge Yang, Anurag Ajay, and Pulkit Agrawal. Overcoming the spectral bias of neural value approximation. In International Conference on Learning Representations, 2022. URL https:\n//openreview.net/forum?id=vIC-xLFuM6.\n\n[2] Mei et al. “A mean field view of the landscape of two-layer neural\nnetworks”. In: Proceedings of the National Academy of Sciences (2018).\n\n[3] S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Inter. Conf. Mach. Learn., pp. 322–332. PMLR, 2019.\n\n[4] R. Basri, D. Jacobs, Y. Kasten, and S. Kritchman. The convergence rate of neural networks for learned functions of different frequencies. Adv. Neur. Info. Proc. Syst., 32, 2019.\n", "strength_and_weaknesses": "**Strengths:**\n\nThe paper is well written and offers a new addition to the spectral bias literature by studying general quadratic losses.  By choosing $P$ appropriately one can compensate for bias's of the NTK.  Furthermore the Sobolev-based loss functions allow one to modify or reverse the spectral bias which can be useful when the low-frequency bias is a difficulty such as in value function approximation [1].\n\n**Weaknesses**\n\nThis work shares the weaknesses of other works in this area, such as being limited to the NTK regime, fixing the outer layer weights, specific initialization, limited to shallow feedforward networks, etc.  However since this weakness is present in other works and the community has not figured out yet how to fully overcome these limitations it is reasonable that this work also operates in this regime.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "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": {}}, {"review_id": "95mByJQddhK", "reviewer": "Reviewer_F3bk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Summary:\n\nThe paper considers the case of non-uniform data in a sphere, and gives a way to demonstrate the frequency bias of neural net learning in the NTK regime. \n", "summary_of_the_review": "The paper tackles a novel problem whose significance seems questionable. The technical tools developed seem somewhat useful nevertheless. ", "strength_and_weaknesses": "Strengths:\n\nThe paper is well-written and the key ideas in the Theorems are reasonably easy to understand.\n\nWeaknesses:\n\n1. The main issue I have with the paper is the objective of training. The paper assumes one has access to training data from a non-uniform distribution, but the final goal is to minimize error according to the uniform distribution (or L2 loss). This looks like a domain adaptation setting. If this is indeed the goal of the paper this should be made clear. Even if this is so, it seems like a very restricted setting of domain adaptation.\n\n2. For example, in Figure 1, what is the loss (and the final/intermediate trained model output) for training with $\\Phi$ and $\\tilde\\Phi$? Looking at how all the three dashed curves are below the solid curves seems to indicate that the model trained with $\\tilde \\Phi$ is strictly better than the model trained with $\\Phi$ at all points, but that seems at odds with the intuition that the model trained with $\\Phi$ would be better in the region of the circle with more data points than average.\n\n\n3. The Sobolev norm frequency biasing doesn't seem to do any meaningful tradeoffs (in Figure 2). i.e. choosing a larger value of s does seem to make the loss on low-frequency components significantly worse, but the loss on high-frequency doesn't seem to reduce nearly as much.  Is the main claim that choosing negative s and emphasising low-frequency components in the optimisation better than not emphasising any particular component by choosing s=0? If so, couldn't this same effect be achieved by NTK from a different initialisation with smaller variance?\n\n4. Similar comments on Figure 3. Choosing s=-1 makes the red and yellow curve higher than s=0, without meaningfully lowering the blue curve. \n\n5. MNIST experiment: There seems to be some confusion between high-frequency label noise components on the dataset and high-frequency noise components on a single image. The low-frequency bias on NTK says nothing about high or low frequency noise on a single image. \n\n\n======================\n\nAfter discussion phase. Having made the domain adaptation setting made clear solves several of the issues I had with the paper. I am raising my score to a marginal accept.\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster