The Spectral Bias of Polynomial Neural Networks
Authors: Moulik Choraria
Leello Tadesse Dadi
Grigorios Chrysos
Julien Mairal
Volkan Cevher
Venue: ICLR 2022 Poster (2022)
Keywords: Deep Neural Networks
Polynomials
Spectral Bias
Neural Tangent Kernel
Deep Image Prior
Infinite Width
Mercer Decomposition

Abstract: Polynomial neural networks (PNNs) have been recently shown to be particularly effective at image generation and face recognition, where high-frequency information is critical. Previous studies have revealed that neural networks demonstrate a $\text{\it{spectral bias}}$ towards low-frequency functions, which yields faster learning of low-frequency components during training. Inspired by such studies, we conduct a spectral analysis of the Neural Tangent Kernel (NTK) of PNNs. We find that the $\Pi$-Net family, i.e., a recently proposed parametrization of PNNs, speeds up the learning of the higher frequencies. 
We verify the theoretical bias through extensive experiments. We expect our analysis to provide novel insights into designing architectures and learning frameworks by incorporating multiplicative interactions via polynomials. 


Published as a conference paper at ICLR 2022
THE SPECTRAL BIAS OF POLYNOMIAL NEURAL NET- WORKS
Moulik Choraria
Leello Dadi
University of Illinois at Chhama-Champaign moulike2@1 illinois edd
EPFL., Switzerland
leel 1c. dadi @epf ch
Grigorios G Chrysos
Julien Mairal
EPFL, Switzerland grigorics,
Univ. Grenoble-Ale Alpes, Inria julien mai ral3 Pinria.
Volkan Cevher
EPFL, Switzerland
volkan. wewaannceeeeeeeeel.cccco
ABSTRACT
Polynomial neural networks (PNNs) have been recently shown to be particularly effective at image generation and face recognition, where high-frrquency informa- tion is critical. Previous studies have revealed that neural networks demonstrate spectral bias towards wwwfrequency functions, which yields faster learning of low-frequency components during training, Inspired by such studies, we conduct a spectral analysis the Neural Tangent Kernel (NTK) of PNNs. We find that the IT-Net family, i.e., a recently proposed parametrization of PNNs, speeds up the learning of the higher frequencies. We verify the theoretical bias through exten- sive experiments. We expect our analysis to provide novel insights into designing architectures and learning frameworks by incorporating multiplicative interactions via polynomials.
INTRODUCTION
Deep neural networks (DNNs) have demonstrated remarkable success in different domains [22, 11]. DNNs can approximate complex functions or even datasets with randomized labels arbitrarily well [50, 3], which makes their ability to avoid over-fitting real data surprising, since it seems to disagree with prior notions of model complexity. This has sparked the interest investigating the notion of "implicit bias" in neural network training, which makes them favor low complexity solutions [43, 21, 26].
The spectral analysis of deep networks offers one perspective this implicit bias. Deep neural networks demonstrate a learning bias towards low frequency functions i.e. functions that vary globally without local fluctuations are learned faster when training neural networks via gradient descent [37, 48]. The phenomenon, termed as the spectral bias of neural networks [37], has been explored from the perspective of the Neural Tangent Kernel (NTK) [24]. The eigenvalues of the obtained kernel influence important characteristics such as the approximation properties and rate of learning [10, 39, 36]. For standard two-layer ReLU networks within the NTK regime, the analysis supports the idea of spectral bias by showing faster emror convergence for information in lower frequencies [12].
Recently, another class of models, Polynomial Neural Networks (PNNs), that express high order polynomial expansions, have demonstrated state-of-the-art performance the challenging tasks of image generation [28] and face recognition [17]. Both tasks rely fine-grained details, which correspond to high- gigh-freuencc information. More generally, multiplicative interactions have demon- strated strong empirical performance image- based applications [44, 47, 4]. Jayakumar et al. [25] highlight how multiplicative interactions, which construct second degree polynomials, can enlarge the hypothesis space and lead faster leamning for certain classes of functions.

---

Published as a conference paper at ICLR 2022
To understand this success of PNNs, conduct spectral analysis, inspired by the analysis of DNNs. We focus on one instance of polynomial networks called II-Nets [16], where the output is piece-wise polynomial function of the imput obtained via multiplicative layers. The parameters of a TT-Net can be represented as high-order tensors, while polynomial expansions can offer increased representation power [17]. Our main contributions be summarized as follows:
We analyze two-layer polynomial networks in the NTK regime. By studying the spectral proper- ties of the corresponding kernel, we prove a theoretical speed-up in learning higher frequencies over standard neural networks and validate the hypothesis the approximate NTK regime, on the task of learning spherical harmonics.
2. Beyond the NTK regime, we demonstrate this enhanced bias of II-Nets towards higher frequen- cies in several experimental settings, beginning from synthetic learning tasks and then proceeding to state-of-art networks and inverse problems with 2D images.
Aside from improving the understanding of polynomials in neural networks, our proposed analysis also sheds new light on the effect of multiplicative interactions in neural networks, prevalent in certain domains of machine learning including vision and natural language processing [29, 7].
RELATED WORK
Motivated by the empirical observations in [3, 37, 48, 46] that deep networks first learn "simple patterns", several papers [49, 12, 8, 2] have conducted theoretical analyses to explain this bias towards lower frequencies. The work of [2], aiming to understand why random labels take longer to learn than natural labels, showed that alignment of the labels with the eigenvectors of the NTK Gram matrix determines the learning speed. Extending this result, Cao al. [12] provide an explanation for the spectral bias by analyzing the decay rate of eigenvalues of the NTK when the input data is uniformly distributed on the sphere. Under the same assumption, Basri al. [8] study training dynamics in the NTK setting for 2-layer ReLU networks with a fixed outer layer and an explicitely included linear bias term in the ReLU. [9] further extends this work account for non-uniform data distributions. All these findings show that DNNs learn lower frequency functions faster which prompted Tancik et al. [45] to propose methods to mitigate this bias. Our paper aims to establish similar results for PNNs, to explain their good performance at learning higher frequencies.
Spectral Bias:
Polynomial neural networks (PNNs): The early papers that explore polynomials the context of neural networks are mainly divided into two categories: 1) self-organizing networks with hard coded features [23]. 2) Pi-Sigma networks [41, 34]. In both cases, the constructions did not scale well to higher dimensional inputs, and were not used for high-dimensional signals, such as images. More recent papers have used the Hadamard product to capture correlations between different branches of an architecture [4, 44, 47, 17]. Our goal is to analyze the properties of these polynomial neural networks that have shown sucess in practice.
Polynomial activation functions (PAFs): is important to note the distinction between PNNs and Polynomial activation functions. PAFs expand (element-wise) each feature to an nTh degree, i.e., they assume (deep) neural network where the element-wise activation functions are Th degree polynomials. This is substantially different from capturing higher-order correlations across input (or feature) elements like PNNs especially in the presence of non-linear activations. Theoretical work on over-parametrizzatoo [18], expressive power [30] and generalization of shallow nets [35] have emerged for PAFs. The aforementioned papers, however, do not conduct a spectral analysis and do not exhibit the benefits of PNNs for learning high-frequency information.
ANALYSIS OF POLYNOMIAL NEURAL NETWORKS IN THE NTK REGIME
In this section, we conduct careful analysis of the kernel approximation of polynomial neural networks (PNNs) to gain insight on the effect of the multiplicative interactions. PNNs include mul- tiplicative interactions and express high-degree polynomial expansions. The recent parametrization of the II-Net family [16], which we summarize below, is used as a representative PNN. We re- view the tangent kernel approximation of neural networks and then we derive the tangent kernel of two-layer TI-Nets to study the spectral bias of II-Nets.
Notation: We denote by (:, the standard inner-product Rd. For two vectors x, y Rdd, x yy denotes the element- wise or Hadamard product. We use x to denote the mode-m vector product!.
Thee reader may refer to the appendix for more details on the mode-m product.
2

---

Published as a conference paper at ICLR 2022
We define the asymptotic notations 12(-) and (2(-) as follows: Let an and bn be two sequences. We write 0n (2(b,)) if lim inf [an/bul > O. We use S((.) hide the logarithmic factors in I(()).
3.1 II-NET FORMULATION
polynomial expansion of the input vector E I2$ can be used to express the output æ E R² as an N degree polynomial expansion as follows:
n+1
x
Σ
Win
II
xz B,
where B E IR' and (Wylm) Rox X d1 N
n-1 are the learnable parameters, and Xm is the mode- m vector product. Since the number of tensor parameters w/ grow exponentially with the degree of the polynomial, coupled tensor decomposition with factor sharing can be used. The idea in TT-Nets is to propose such decompositions that can capture higher order correlations, and can be implemented in standard deep learning frameworks. One such decomposition uses the recursive [T]))) (5% (S + B( b(n) for = 1,.... N and expresses the out- put x as a = CaN + B. The term in the rightmost parenthesis is exactly the recursive form of standard neural network (without activations). Therefore, IT-Nets augment standard neural net- work with multiplicative interactions via the Hadamard product. While TT-Nets can approximate the target function without activations, they achieve state-of-art performance with activation functions, wherein the output is a piece-wise polynomial. We include more details in the Appendix.
formulation
3.2 THE NEURAL TANGENT KERNEL
Consider the following two-layer ReLU neural network (without bias parameters) with width m that assumes the following form (defined as [10]): fw(()) = V W20 (W where W1 Rmx(d+1), W2 E IR1m and we assume inputs {=> follow some distribution on the unit sphere sd E Rd+ a-)) denotes the element- wise ReLU operator. As the width of the network m goes to infinity, if the weights at initialization (0) are independent and each follow the standard normal distribution, the inner product of the network gradient at initialization gives rise to limiting kernel, namely the Neural Tangent Kernel (NTK) [24] τ defined as
R6 k(xx = lim SW (x), (w T--
(2)
This kernel has been used to characterize the behavior of sufficiently wide networks fw during training. For instance, the network is trained to minimize the & loss, then its training dynamics closely track those of kernel regression under k. This holds in a particular training regime, referred to as "lazy training" [14], where the parameters hardly vary after initialization and the network can be approximated by its first-order Taylor expansion at initialization as:
(w(x) R Swros (æ) + (Ww/wiorar W W())
In practice however, the conditions of lazy training are often violated (notably, the requirement that the weights do not move) within the first few steps of gradient descent. Nevertheless, the NTK remains a useful theoretical tool for analyzing the neural network behavior as some of its predictions have been shown to hold in practice [12, 32].
The NTK for the two-layer ReLU network fw (x)) takes the following form [10, 14, 19]
<(x,, x') = 2xx, x') "e'xei(e x') + 2x²(
(3)
where the kernels K₂ and K2 are defined as follows:
Ki (x, x') Ew- (oo x) x)) (kw, x²>]],
(4)
R2 (2(2, x') Ew--Noo,) (Kw, )))a((( (auu,x")))) x²))],
where o-)) denotes the ReLU operator and o'(-) denotes the indicator function 1[: > OJ. The kernels Ki, K2 have been explicitly computed for the ReLU actívation in [38, 15, 10] where they were shown to be positive semi-definite dot-pruduct kernels. The function value depends only on the value of the dot-product of the arguments or more formally, Ky (z, x') = g1 (xx, x and <2 x') = g2 (2( æ²)) for some functions 91. : R + R. These kernels will serve as building blocks for the tangent kernel of the TT-Net architecture studied in the next section.
3

---

Published as a conference paper at ICLR 2022
3.3 II-KERNEL
Following [8, 10, 12] that consider shallow two-layer ReLU networks, we derive the tangent kernel for two-layer IT-Net by supplementing the standard network with multiplicative interaction layer:
(w)x) Ws Wala((Wzz) o o(W1))]
where W1, W2 E Ix W3 E RIxm, * denotes the Hadamard product and we again assume inputs { that follow some distribution T on the unit sphere $ c gd-1
Remark Note that formulation yields piece-wise quadratie polynomial and that it is important to consider ReLU activations (or other non-line non-linearities) since otherwise, the network yields quadratic polynomial of the input and is no longer a universal approximator, even with infinite width.
Theorem Let K1, R2 as defined in Eq. (4). The limiting kernel for the two-layer II-Net, called TI-kernel and denoted by Kiz (x, x.), takes the following form:
Ker (x, x') 2(2(xx, x x'x'x''''aaaaa (x x') (2 (222(
(6)
The proof follows the standard NTK calculations and is presented in the Appendix. Importantly, the addition of a single multiplicative interaction induces product of kernels form.
Remark 2 The required width that ensures that the two-layer II-Net stays close to initialization (the corresponding NTK is close to the limiting Kx) is slightly higher than standard networks, by a ((ylog m) factor. We provide rough sketch of the proof in the Appendix (end of C).
Remark 3 The advantage of using the 2-layer IT-Net formulation is that it allows us to directly contrast against prior results on standard 2-layer feed-forward network, by gauging the effect of the extra multiplicative layer. However, unlike feed-forward networks, the theory does not easily extend to polynomials of higher degree or depth, since even with a fixed degree and depth, the NTK varies with the placement of the multiplicative connections. In this work, we choose to focus primarily on the effect of the multiplicative layer and leave the extension to general polynomials for future work.
Since the IT-kernel Kx can be expressed as sum of products of continuous positive definite dot- product kernels K1 and K2, inherits their regularity properties and is itself Mercer kernel, as a consequence of the Schur Product theorem.
3.4 SPECTRAL ANALYSIS
To properly characterize the approximation properties and the behavior during training of this newly derived kernel, we study its Mercer decomposition. Indeed, this approach was used in [10] show that the 2-layer NTK (Eq. (3)) has better approximation properties than a fixed first layer network, and in [ [12] to study the spectral bias of feed forward ReLU networks.
The Mercer decomposition of a kernel k is derived from the eigenvalues and eigenfunction of the integral operator associated to the kernel (see [40] Theorem 2.10 and references therein). Taking X to be some compact set in Idd, recall that for any continuous kernel function X' x X - R and Borel measure 7 on X, we can define an integral operator L, that "convolves" any square integrable function f (XY) with K:
(x) = [{ n( (
For Mercer kernel, this linear operator admits countable, real, non-negative eigenvalues {Mi J., } and the associated eigenfunctions form an orthonormal basis of (Z)). If the data uniform on the sphere Sd. and a dot-product kernel, then these eigenfunctions of L, are the spherical harmonics ([42), Lemma 4). Consequently, by applying Mercer's 's Theorem, we can obtain the following decomposition:
N(d.k)
((x x0)
Σ 1 Σ
(x)()))
(8)
where Yk. for j = 1,2. 1,2...N k) represent the spherical harmonics of degree k in d + 1 variables (whose explicit formula is given in Appendix D.I in [5]). and N(d, k) 28 1+ (k+d-2)
4

---

Published as a conference paper at ICLR 2022
From this, can characterize the RKHS H associated to as follows:
M(dk) Ye. subject to llfll
N(d.) KKj
H
00
Pk
k
The benefit of determining the decay rate of the eigenvalues {ui, P2..... can be easily deduced from the previous set as the eigenvalues determine the size of H. Indeed, the slower the decay of
(/11:/2,... J. the more sequences (an.)).. will verify Σx 10 2زー1 "i oi < cc. The results of [12] rely on this decay rate to show that gradient descent on wide networks picks up low-frequency information first (Theorem 4.2, [12]). This decay rate is therefore of central importance. Next, briefly refer to the prior results on characterizing this decay rate for the kernel obtained for the two- layer feed forward ReLU network (Eq. (3)) and we derive the equivalent results for the II-kemell.
Proposition 1 (Theorem 4.3 in Cao et al. [12], Proposition 5 in Bietti & Mairal [10]) For the tangent kernel corresponding to foed ReLU network, the eigenvalues (px)) satisfy the following:
Po: Mn 12(1):
pi 0, when k is odd,
M. 1(k--d11 when > d.
The decay is exponentially fast in the input dimension d. For the II-kernel, we show the following improvement.
Theorem Let (,,,1,..,,,.... denote the eigenvalues of the linear operator Lx,, associated to the kernel Km For k >> d (k + 2 mod 4), it holds that F = -2(k -((k--(222)
The proof of the theorem is provided in the Appendix. The main idea is to plug in the Mercer decom- position of each kernel, leading to a product of polynomials form. The expansion of this product then allows for isolating the dominant terms contributing to the eigenvalues for each frequency. The key take-away is the much slower rate of decay the 1tth cigenvalue (an order almost ((1((422) when compared to the standard two-layer NTK. An immediate consequence is a "larger" RKHS, which lends the IT-kernel superior approximation properties in the higher frequencies. Further, when combined with the findings of [12], it yields a speed-up in learning higher frequency harmonics.
Remark 4 On the point of "larger" RKHS, note the two perspectives at play. First is the idea that a slower decay implies more functions contained in the RKHS, leading to better approximation properties. However, from the classical statistical learning point of view, while larger RKHS makes the optimization problem easier, it may lead to sub-optimal prediction performance [6]. eventually relating to the traditional trade-off in machine learning. We note through our experiments that is the perspective relating to better approximation and optimization for the II-kernel that dominates.
Remark The k >> d setting may not reflect the case for image-based applications. For instance, generation tasks wherein the output is an image of resolution d x d, the higher frequencies of interest roughly correspond to the order of (dd). Consequently, the exponential improvement in the decay rate for the k: > d setting, and by extension in the approximation properties of the RKHS as well as the speed of learning higher frequency information, may not be as dramatic elsewhere. Nevertheless, our analysis provides sufficient intuition to expect some degree of improvement in realistic settings.
NUMERICAL EVIDENCE
The analysis in Section 3 reveals that polynomial networks in the NTK regime learn higher fre- quency information faster. In practice however, neural networks deviate from the near-initialization NTK conditions within just few iterations of gradient descent. Therefore, to verify the analysis on the spectral bias of II-Nets, we conduct a series of experiments that increasingly deviate from the NTK regime, including image-based based datasets to further verify our theoretical analysis. We initially consider synthetic data (Section 4.1), then move onto realistic settings. For all experiments, we use II-Nets based on the product of polynomials formulation (Appendix), in the same vein as [16].
We offer brief characterization of the result in the Appendix.
5

---

Published as a conference paper at ICLR 2022
4.1 EXPERIMENTS ON SYNTHETIC DATA
Our first experiment relates to learning spherical harmonics in the approximately infinite width NTK regime [12]. More precisely, the task comprises of learning linear combinations of spherical harmon- ies with data uniformly distributed on the unit sphere. We consider large-width two-layer networks simulate the infinite-width settings and we compare the performance of 11-Nets against standard neural networks. The optimization method is full batch vanilla gradient descent, to avoid stochastic effects. The observations align with our theoretical findings, we defer the results to Appendix due to space constraints. Next, we assess whether the spectral bias manifests beyond the NTK regime. We consider the task of learning sinusoidal signals with smaller width networks and larger learning rates, so as to expressly violate the NTK assumptions.
Comparison on Learning Sinusoids
1.0
0.8
0.8
Iterations
Iterations
0.6
10000 20000 30000
25
Frequency [Hz]
Frequency [H2]
Figure 1: Comparison of learning speeds across different frequencies. The target signal. i.e., sinu-
soids, is transformed in the Fourier domain and the learned components are compared to the true amplitudes. On the colormap scale, denotes the perfect approximation. We observe that the IT-Net (right) learns higher frequencies faster, i.e., lower in the axis, than the standard network (left).
Learning Sinusoids The goal is to learn sinusoidal signals [37]. Given frequencies e K., with amplitudes A; E a and phases é; E ④, the target map f [0, 1] - IR is defined as f*(() = A, sin(2xk; d.). We approximate this map with two methods: i) fully connected neural network and ii) a II-Net. In the first setting, we compare a 256-unit wide, six-layer deep neural network against a 256-unit wide, six-layer deep II-Net (which has five multiplicative layers). In each case, the network So (parametrized by 0) regresses over f (K = (5. 10, .... 45, 50), di (O, 2x) and A; AA i), using N = 200 evenly spaced input samples over [o, 1] and with a fixed learning rate (same for both networks); the spectrum of the network (k) monitored during training by tracking the magnitude of learned components for each frequency, averaged over 5 runs (Fig. 1).
Remark The experimental setup for training the networks replicates the setup of Rahaman et al. [37], without any special initialization hyper-parameter tuning for either network and the TT-Net is implemented exactly as the product of polynomials formulation specified in the Appendix.
We observe that 1I-Nets do speed up training of higher frequencies. To better substantiate our claim, we consider two additional variants, the results of which are included in the Appendix. In the first, compare deeper nine-layer feedforward network with six-layer II-Net with only three multi- plicative layers, such that the feedforward network includes more parameters (Fig. 10). Since skip connections (additive) are known to speed-up training, we next compare the II-Net with feedfor- ward network of same depth, but with additive skip connections instead of multiplicative (Fig. 11). In both cases, we verify that the speed-up learning higher frequencies due to multiplicative layers much more significant.
the task of learning sinusoids, multiplicative interactions can speed up the learning of higher frequencies and are more effective at doing so than simply increasing the depth. In the Appendix, we conduct an experiment to evaluate the robustness the networks in retaining high frequency information (Fig. 12) and frequencies. Remarkably, the II-Net with more interactions is noticeably more robust than the lower degree polynomial network (Fig. 13 in the appendix). We hypothesize that IT-Nets enhance the
Discussion:
that II-Nets more robust to perturbations in the higher

---

Published as a conference paper at ICLR 2022
representational space for higher frequencies, relating our observations the RKHS in the NTK regime, which makes them less susceptible than standard neural networks. This could also explain why more multiplicative interactions lead to more robustness.
4.2 LEARNING IMAGES
To further validate our claim in natural images, we adopt the convolutional layers often used in deep convolutional neural networks (DCNNs) [31]. DCNNS are ubiquitous in vision, partly due to the DCNN structure imposing a suitable prior for tasks with natural images, termed as the Deep Image Prior (DIP) [33]. We precisely assess how this prior changes with multiplicative interactions in TI-Nets in denoising setup adapted from the DIP framework.
We consider an image x e R33H*W and obtain its noisy version To + 6, perturbed with Gaussian noise. For the input, we sample a random tensor e R RNxxxx = in our setup). We consider a neural network So (making the parametrization by 0 explicit), and optimize the reconstruction loss, ming [[]( zoll². with respect to the noisy image. We can expect the DCNN structure to first learn the ("natural") features corresponding to the true image x and pick up the noise only in the latter stages, which can then be avoided using carly-stopping [33].
Experiment Denoising:
Remark Our goal is not to quantify the denoising performance but rather, to validate the experi- mental observation sinusoids and assess whether I1-Nets can speed up learning of high frequen- cies in real-world applications. If the speed up is confirmed, II-Nets can be early-stopped, i.e., require less iterations for achieving the target result.
Denolsing
PSAft with Moiy Image lol
PSRN wkh True Image Ex)
22.5
20.0
17.9
PSNRR
13.5
10.0
Standerdd
standard network Tineework
Rinehwork
2C00
2500
Rorations
Eorations
Figure 2: The plots track the progress of the denoising task in the DIP setup via measuring the PSNR w.r.t. the noisy image (left) and the true image (right). We ideally want to stop the optimization process when the PSNR w.r.t the true image is maximum. We observe that for II-Nets, the maximum PSNR point occurs much earlier, beyond which the PSNR w.r.t the true image starts decrease as the network begins to learn the noise. This indicates that the IT-Net shows a reduced impedance towards high frequency information, compared to standard networks.
As in [37], we experiment with the U-net architecture, adapting it suitably for II-Nets with image of resolution 480 x 600. The implementation details are included in the Appendix. We train both networks for 2500 iterations, with the same learning rate and identical input tensor z. We monitor the Peak Signal-to-Noise Ratio (PSNR) curves while training, in Fig. 2. The peak-PSNR with the true image for both standard and I1-Nets are roughly the same, indicating similar denoising performance. However, II-net achieves this peak PSNR in approximately half the number of iterations. Beyond this point, the II-net PSNR with the true image decreases as starts to pick up the high figu-frry noise. We confirm this in the visual snapshot of the output of the two networks (Fig. 16 in the appendix). We conclude that TT-Nets do indeed speed up learning in images, by showing a reduced impedance towards high-frequee frequencyycc information. Next, we check how this bias affects learning high frequency information pertaining to natural images in the absence of noise.
We consider the identical setup as the denoising experi- ment but without the noise perturbation, setting O. Therefore, the task for the network fo learn 8* such that fox (z) = x.. We allow 600 iterations of gradient descent and we monitor the radial power spectral density (p.s.d.) of the network output image against the ground truth p.s.d. It allows us explicitly track the learning progress for each the frequency magnitude.
Experiment- Power Spectrum Analysis:
7

---

Published as a conference paper at ICLR 2022
Iteration
Iteration
Iteration 150
image
10
n-nettscalo-22
10
108
P(]
std netiscale-3)
104
true image
10
true image
10
(--ret(saal==2)
(i-et(scale=22)
std. netiscale=3)
std. net(scale=3)
10
10
10a
10
10
10a
10
10f
10?
||M||
|||||
||w]||
Iteration 225
Iteration
Iteration
10a
10a
10
P(]
P(]
10c
true image
10
true image
10
true image
(--et(scale=22)
(--et(scale=2)
n-net(scale=2)
std. netiscale=3)
std. netiscale=3)
std. netiscale=3)
10
10
10?
10
101
10a
10
101
10a
||w||
|||||
||]||
Iteration: 450
Iteration 525
Iteration 600
10
10a
208
10c
ninettscale-2) std netiscale-3)
image
10
n-nettscale-2] std netiscale-3)
image
10
n-netiscale=2) std netiscale-3)
image
10
10a
102
10a
10a
10a
10
10a
10a
|||||
|||||
||]||
Figure 3: We compare the power spectral density curves at different checkpoints during 600 itera- tions of optimization, for standard (scale 3) vs networks (scale = 2). The goal for each network is to match the power spectral density of the target image. We observe that the 11-Net picks up hige-freyuency information in the image faster.
We use the same U-net structure and suitably modify it for IT-Nets as before. Since the multiplicative interactions introduce more parameters, we reduce the depth/scale (by scale, we mean number of down/up-sampling operations in the U-net) of II-Net to ensure roughly the same parameters (~ 1.3 million). The learning speeds in different fiequeencies can be observed in Fig. 3. In the Appendix, we repeat the same experiment for equal depth networks.
Discussion:
From the preceding two experiments, we establish how II-Nets pick up high frequency information faster than (larger) DCNNs. In the Appendix, we note the effect of multiplicative inter- actions on the deep image prior of the network. We also verify that this altered spectral bias remains relevant for standard learning tasks with natural images. Consequently, for tasks where capturing the finer details of the image is important (such the denoising instance above). this potentially leads to a reduced number of iterations for 11-Nets as compared to standard networks. We expect the insights from our work to be useful for guiding network design with multiplicative interactions in scale experiments.
4.3 EFFECT OF LABEL NOISE IN CLASSIFICATION
Finally, we conduct an experiment in a classification setting, wherein the goal is to quantify the effect of this spectral bias in presence of label noise. The setup is adapted from Rahaman et al. [37], a fully connected 6-layer deep 256-unit wide network trained on binary classification on MNIST images (by only considering classes "3" and "8"). The labels are perturbed by label noise of different frequencies and the network is trained on the noisy labels with mean squared loss. Rahaman et al. [37] noted for feedforward networks that for fixed amplitude, low frequency label noise degrades generalization performance (difference between training and validation losses) to a larger extent than high frequency noise. While the low frequency noise is learned instantly, the high-frequency noise is only fit later in the training. As a result, the network learns only true labels at first, and this corresponds "dip" in the true validation loss in the early stages. This "dip" becomes larger
8

---

Published as a conference paper at ICLR 2022
with increasing frequency of noise, indicating network impedance towards higher frequencies in the early iterations. Thus, is only during the latter stages that the true validation loss degrades.
We repeat the experiment with II-Nets, by supplementing the feedforward network with exactly one multiplicative layer, and contrast the two networks. Since 1I-Nets pick up high frequency variations faster, consequently expect smaller "dip". We train for 5000 iterations with identical learning rates and observe the validation loss curves for different label noise frequencies. Fig. 4, we zoom in the first 1000 iterations for better visualization (complete curves included in the Appendix).
Discussion: While the performance for the two networks is identical in absence of label noise (freq=0), the validation "dip" in TT-Net for higher frequencies (0.3, 0.5, 1) is visibly smaller and is negligible for lower frequencies (0.1, 0.2), indicating that II-Nets pick the high frequency label noise the decision boundaries much faster. Additionally, we verify that increasing the number of multiplicative layers reduces the "dip" even further. The plots are deferred to the Appendix.
pi-net (1 multiplicative layer)
standard-net
10a
MSE Validaation Loss
freq 0.0
freq = 0.0
10-1
0.05
0.65
freq 0.1
fraq 0.1
froq
freq 0.3
freq 0.3
froq
freq 1
freq =
200
400
600
800
1000
200
400
600
800
1000
Training Iteration
Training Iteration
Figure 4: We compare the validation loss curves for the first 1000 iterations on the binary classifica- tion task, for II-Net (left) and standard network (right). For the same frequency, the validation dips for Ie-Net are much smaller, indicating a higher tendency to pick up high high-frequency label noise.
5 DISCUSSION
In this work, we focus on the spectral of polynomial neural networks. Our theoretical results in the NTK regime utilize two-layer polynomial network and demonstrate a speed-up in the learning of higher frequencies over standard neural networks. We experimentally verify these properties, even outside of the NTK training regime. Additionally, the results offer intuition behind the success of networks that use multiplicative interactions, such as StyleGAN [28], whose connections to polyno- mials have been noted previously [17].
As a future direction, we aim to design controlled settings to study how polynomial and multi- plicative interactions affect performance in state-of-the-art conditional generative models for image generation or deblurring, where high-frequency information critical for photo-realistic outcomes. should be noted that the spectral bias of standard neural networks towards low frequency (com- plexity) functions is believed to help in generalization. Therefore, another important direction is to explore whether this enhanced spectral bias of polynomials towards higher complexity functions translates to differences in their generalization properties. Finally, our results in the classification task yield further research direction towards analyzing the smoothness of decision boundaries of TI-Nets with multiplicative interactions, especially focusing on areas wherein this effect becomes relevant such as adversarial susceptibility or knowledge distillation.
ACKNOWLEDGMENTS
We are thankful to the anonymous reviewers for their constructive feedback. Research spon- sored by the Army Research Office and was accomplished under Grant Number W91 1NF-19-11 0404. This project has received funding from the European Research Council (ERC) under the

---

Published as a conference paper at ICLR 2022
European Union's Horizon 2020 research and innovation programme (grant agreement n 725594 time-data). JM was supported by the ERC grant number 714381 (SOLARIS project) and by ANR 3IA MIAI @
MIAI@Grenoble Grenoble Alpes, (ANR19-P3IA-0003)
REFERENCES
[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization.. CoRR, abs/181 2018. URL http://arxiv.orr org/ abs/
1811.03966
[2] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Interna- tional Conference on Machine Learning, pp. 322-332. PMLR, 2019.
[3] Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Si- mon Lacoste-Julics Julien. A closer look at memorization in deep networks. arXiv:1706.055: [cs, stat], July 2017. URL http: /arxivv//aivvvv//aa org/ abs/ 1706. 053 94. arXiv: 1706.05394.
[4] Francesca Babiloni, loannis Marras, Filippos Kokkinos, Jiankang Deng, Grigorios Chrysos, and Stefanos Zafeiriou. Poly-nl: Linear complexity non-local layers with polynomials. In International Conference on Computer Vision (ICCV), 2021.
[5] Francis Bach. Breaking the Curse of Dimensionality with Convex Neural Networks. httpaaaxivvv....... ort.abs/112/2.
arXiv:1412.860 26990 [cs, math, stat), October 2016. URL 8690. arXiv: 1412.8690.
[6] Francis R. Bach. Sharp analysis of low-rank kernll matrix approximations. abs/1208.2015. 2012. URL TRL:ttp://a/ http:://aaxivve http://twwww..gg../...//// abs///////// abs/1208.... 2015.
CoRR,
[7] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural Machine Translation by Jointly Learning Align and Translate. 1409: 0473 [cs, stat), May 2016. URL http:
// //arxiv. org/ abs 102//1400 1409. 0473. arXiv: 1409.0473.
[8] Ronen Basri, David W. Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. CoRR, URL http::tp::///aa
2019.
org/ atbs/1966. 00425.
[9] Ronen Basri, Meirav Galun, Amnon Geifman, David W. Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. CoRR, (as/2003.0456.) 2020. URL httpp:://aaxiv..ott/ http:iii...raaa////////aa
04560.
[10] Alberto Bietti and Julien Mairal. On the Inductive Bias of Neural Tangent Kernels. arXiv:1905.12 12173 fes, stat], October 2019. URL http://arxiv org/ abs/1905 12173. arXiv: 12173.
[11] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language Models are Few-Shot Learn- arXiv:2005.1 200.20005.1415 [cs], July 2020. URL http: // arxiv org/ abs /205 14165. arXiv: 2005.14165.
[12] Yuan Cao, Zhiying Fang, Yue Wu, Ding- Xuan Zhou, and Quanquan Gu. Towards Understand- ing the Spectral Bias of Deep Learning. arXiv:1912.011 [cs, stat], October 2020. URL http:// ///rxxaivvv////////////// viv. org/ abs 1912. 011 98. arXiv: 1912.01198.
[13] L. Carlitz.
The product of two ultraspherical polynomials. gow Mathematical Journal, 7(2):76-79 July 1961.
Glas-
ISSN 2051-2104, URL https: www..
2040-6185. doi: 00.1017/5004011850004444
10

---

Published as a conference paper at ICLR 2022
htt.a//aaaaa..oooo///////a/aaaaa ott.pppspppacccc.....o.oaaaaaaaa BF 28730019220884444111100222222222 Pubiihie Cambridge University Press.
Publisher:
[14] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Pro- gramming. 10x.::8112077956 (cs, mathJ, January 2020. URL http: httppp///axxi.oog//bbbb...t org/abs/ 1812.07955 arXiv: 1812.07956.
[15] Youngmin Cho and Lawrence Saul. Kernel Methods for Deep Learning. In Advances in Neural Information Processing Systems, volume 22. Curran Asso- ciates, Inc., 2009. URL https://paper:: wttp:/iwp.ss..pp......eepppp
html.
[16] Grigorios G. Chrysos, Stylianos Moschoglou, Giorgos Bouritsas, Yannis Panagakis, Jiankang Deng, and Stefanos Zafeiriou. P-nets: Deep Polynomial Neural Networks. pp. 7325- 7335, 2020. URL http:::///ppaacceeeeee thecth.eeeeccc com/ Searttent__v_____ee html Bonn//Crryos_Paae Pereossssssessseeeeeeeee SerettsDDee__eeeeee ortpa//eess.ooppeppoooooooaaaaaa paper. html.
[17] Grigorios G. Chrysos, Stylianos Moschoglou, Giorgos Bouritsas, Jiankang Deng, Yannis Pana- gakis, and Stefanos P Zafeiriou. Deep Polynomial Neural Networks. pp. 1-1, 2021. ISSN 1939-3539. doi: 10. 10.1109/PAMM.202 3305889.. Conference Name: IEEE Transactions Pattern Analysis and Machine Intelligence.
[18] Simon Du and Jason Lee. On the power of over-parametrizzaion in neural networks with quadratic activation. In International Conference Machine Learning (ICML), pp. 1329- 1338, 2018.
[19] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient Descent Provably Op- timizes Over-parameterizer Neural Networks. arXiv:1810.022 [cs, math, stat], February 2019. URL http:///// pestt://aree /ttp/a/axvvv//.///////ee///aaav/ www.aaiwwwww....aaaoaaaaaaaaaa/e
02054. 4. arXiv: 1810.02054.
[20] Christopher Frye and Costas J Efthimiou. Spherical harmonics in dimensions. arXiv preprini arXiv:1205.3548, 2012.
[21] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit Bias of Gradient Descent Linear Convolutional Networks. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., wttpeuurp...pppppp///eeeee (ppppr//01//hassitt URL https://proceedee Ab-ttbttactttt... html. Oe De98aeeb54acc 2eeeeeeeeee2226282
2018.
neuri ca
[22] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Mia Xu Chen, Dehao Chen, Hy- oukJoong Lee, Jiquan Ngiam, Quoc V. Le, Yonghui Wu, and Zhifeng Chen. GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism.
1811106969 [cs], July arXiv: 1811.06965.
2019. URL http: / /ttp/vaaiivvv/vv///////e..//a.ia org/ abs/
06965.
[23] A. G. Ivakhnenko. Polynomial Theory of Complex Systems. IEEE Transactions on Sys- tems, Man, and Cyhernetics, SMC-I(4):364-377 October 1971. ISSN 2168-2909. doi: 2.1109/TMMC.1991 1931..338320. Conference Name: IEEE Transactions on Systems, Man, and Cybernetics.
[24] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks, arXiv:1806.077 07572 [cs, math, stat], February 2020, URL http:/ /ttp:///axivvv org/ abs NDN///8066 07572. arXiv: 1806.07572.
[25] Siddhant M. Jayakumar, Wojeiech M. Czamecki, Jacob Menick, Jonathan Schwarz, Jack Rae, Simon Osindero, Yee Whye Teh, Tim Harley, and Razvan Pascanu. Multiplicative interactions and where find them. In International Conference on Learning Representations (ICLR), 2020.
[26] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Proceedings of the Second Conference on Learning Theory, pp. 1772-1798. PMLR, June 2019. URL https: : http/////o//////e//////e/////e/e mlr, ppwsssvv9/ssne html. ISSN: 2640-3498.

---

Published as a conference paper at ICLR 2022
[27] Ziwei Ji, Justin D. Li, and Matus Telgarsky. Early-stopped neural networks consistent. 2021. arxiv: 05932 [cs.LG].
[28] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Conference Computer Vision and Pattern Recognition (CVPR), 2019.
[29] Tero Karras, Samuli Laine, and Timo Aila. A Style-Based Generator Architecture for Gen- erative Adversarial Networks. arXiv: /8/2. 812.04948 [cs, stat), March 2019. URL http: wwwpii.orggab//eoo
04948. arXiv: 1812.04948.
[30] Joe Kileel, Matthew Trager. and Joan Bruna. On the expressive power of deep polynomial neural networks. Advances in neural information processing systems (NeurIPS), 32: 10310- 10319, 2019.
[31] Yann LeCun and Yoshua Bengio. Convolutional networks for images, speech, and time series. In The handbook of bruin theory and neural networks, pp. 255-258. MIT Press, Cambridge, MA, USA, October 1998. ISBN 978-0-262-51102.5.
[32] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32:8572-8583, 2019.
[33] Victor Lempitsky, Andrea Vedaldi, and Dmitry Ulyanov. Deep Image Prior. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9446-9454, June 2018. doi: 10.1109/CVPR.201 20..04444 .0984.
ISSN: 2575-7075
[34] Chien-Kuo Li. A Sigma-Pi-Sigma Neural Network (SPSNN). Neural Processing Letters, 17 (1):1-19, February 2003. ISSN 1573-773X. doi: 10.1023/410022965553888 URL https: //doi.
1023 : 1al.267522222888
[35] Stefano Sarao Mannelli, Eric Vanden-Eijnden, and Lenka Zdeborová. Optimization and gen- eralization of shallow neural networks with quadratic activation functions. arXiv preprint arXiv:2006.15499 15459, 2020.
[36] Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent un- der neural tangent kernel regime. In International Conference on Learning Representations (ICLR), 2021.
[37] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A. Ham- precht, Yoshua Bengio, and Aaron Courville. On the Spectral Bias of Neural Networks. arXiv: 1801188066844 [es, stat), May 2019. URL http: //axxiv////vvvv orgg /ab////// 2oos/1000 188880600 08734.
[38] Nicolas Le Roux and Yoshua Bengio. Continuous neural networks. In Marina Meila and Xi- aotong Shen (eds.), Proceedings of the Eleventh International Conference Artificial Intel- ligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pp. 404-411, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR. URL hwttpss:/proceeeeeeeee html.
mlr.
[39] Meyer Scetbon and Zaid Harchaoui. spectral analysis of dot-product kernels, 2021.
[40] Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[41] Y. Shin and J. Ghosh. The pi-sigma network: an efficient higher-order neural network for pattern classification and function approximation. In IJCNN-91 JCCN-91-Seattle International Joint Conference Neural Networks, volume i, pp. 13-18 1. July 1991. doi: 10.1109/1ICNN. 1991.155142.
[42] Alex Smola, Zoltán Óvári, and Robert C Williamson. Regularization with dot dot-product kernels. In T. Leen, T. Dietterich, and V. Tresp (eds.), Advances in Neural Information Processing Systems, volume 13. MIT Press, 2001. URL https: http:////cccceceeppeeeee meurips.co. .dff.
12

---

Published as a conference paper at ICLR 2022
[43] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The Implicit Bias Gradient Descent on Separable Data. arX1:: [cs, stat], December 2018. URL http:///aaa......oaaa//a//////
arXiv: 1710.10345.
[44] Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. Highway Networks. 55555,0087711 [cs]. November 2015. URL arXiv: 1505.00387.
00387.
[45] Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Fridovich-Keil, Nithin Ragha- van, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng. Fourier fea- tures let networks learn high frequency functions in low dimensional domains. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7537-7547. Curran Asso- ciates, Inc., 2020. URL htR.htts::/// /ttp::/es////c/eeeeeeeeeo ngs neuri pdf.
[46] Guillermo Valle-Perez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes be- cause the varameter-functinn map is biased towards simple functions. International Con- ference on Learning Representations, 2019. URL https: openrevieeeeeeeeeeeeeeeeeee net. forum? id=rye4g3AqFm.
[47] Yan Wang, Lingxi Xie, Chenxi Liu, Siyuan Qiao, Ya Zhang, Wenjun Zhang, Qi Tian, and Alan Yuille. Sort: Second-order response transform for visual recognition. In International Conference on Computer Vision (ICCV), pp. 1359-1368, 2017.
[48] Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. CoRR, abs/1901.06523, 2019. URL http: arxiv.ai........ org/ abs 1901..1.1... 06523.
[49] Greg Yang and Hadi Salman. A fine-grained spectral perspective neural networks. arXiv preprint vrXivvI907. 10599, 2019.
[50] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. 1. 1.03530 [cs], February 2017. URL http::/t//// arxiv. org/ abs/1611. 03530.
arXiv: 161 1.03530.
13

---

Published as a conference paper at ICLR 2022
APPENDIX
A
A PRIMER ON POLYNOMIAL NEURAL NETWORKS (II-NETS)
Polynomial neural networks (II-Nets) [16] were recently introduced with the output being a high degree polynomial expansion of the input. The parameters of II-Nets can be represented as higher order tensors. These networks are able serve as function approximators even without the use of non-linear activations. When used in conjunction with activations, the models demonstrate better expressivity and achieve state-of-art results on a variety of learning tasks. We next describe the construction of II-Nets.
A.1 METHOD
Mode-m vector product: Consider an M order tensor X, with each of its element addressed by M indices, i.e., (X)ss. Fin..a....dar An 2h real-valued tensor X is defined over the tensor space [R 12 x x IM where Lm 2 for m 1,2, ...... The mode-m unfolding of a tensor X' E R41x12x..xXX maps X' to a matrix ((m) E Im with 1m = I 7t- such that the tensor element X i2........ is mapped to the matrix element Xim5 where j = + E - (is 1)JK, where Js I 1nmm In. The mode-m vector product of X' with vector R'm, denoted by X m a 11xxxx.......................... In 1m-1x1e 1 xlmm1--... results in a tensor of order M 1:
Im
(X x u) 1mm
Σ
Fig.2a Us
Furthermore, we denote X x X2 Ug.... XM UM X II x mmm
11-Net learns function G nd - Ro, such that each element of the output Ij can be expressed as a polynomial of all the input elements 2₁, with [1, d] follows:
Tj G(z), = 33 + !0!"" + =- _T
(10)
5 X
3 x3 y
[N]
xn
n-1
xmdi { カ-1 are parameters for approximating the output Ty. The correlations (of the input elements 2,) up to 7h order emerge in Eq. (10). More compactly:
where Bj E R and (W] E R
= G(z)
=
mln
I
X5
+ 3,
(11)
the learnable parameters. This form allows us to approximate any smooth function as per an extension of the Weierstrass Theorem. To prevent an exponential number of parameters, the authors propose using coupled tensor decompositions.
where 8 Ho and (wix) E _o Xmd
in=1
A.2 TENSOR DECOMPOSITION FOR SINGLE POLYNOMIAL
An appropriate tensor decomposition on the parameters in Eq. (11) allows for implementation with a neural network. Here, we briefly describe one such decomposition:
Next, we consider joint hierarchical decomposition on the polynomial parameters. Nested coupled CP decomposition (NCP) results in the following recursive relationship for Nth order approximation:
Model: NCP:
(A[m)z) * (S% + Bi b(1)
(12)
14

---

Published as a conference paper at ICLR 2022
for n 2, 2.....N with œ1
[m] *
B iml b[mll and a CÆN + B. The parameters C
Roxk [m] E Raxk [(]] E RRxx [(n E Ruxk [xx]
R for n. 1, 1,..., N, are learnable.
N [b(n] E RR n- act as scaling factor for each parameter tensor, whose role illustrated in case of the third order approximation in Eq. (13):
A
A []]
A
Bnj
*
S/g
*
Sto
*
C'
((z)
B
bt3
Figure 5: Schematic illustration of the NCP [16].
G(z) = 3 wlll x2 llg x m1l1 x2 6[2] x W x2 6[3] x3 (13)
Further, the joint factorization of the parameter tensors (in matrix form) for the third order NCP polynomial may be summarized as follows:
First order parameters w/Hl| C(A(3) C BBy)
Second order parametes: w [2]
C
A o
(A C B S }
(1)
(A (4m 2 Buj sTa) S/3 }
Third order parameters: w [3] = C
A 0
A.3 PRODUCT OF POLYNOMIALS
The second scheme of implementation approximates the target function using a product of poly- nomials form, wherein the output of first polynomial is fed to the next and The concept is visually depicted in 6; for instance, each polynomial degree two, then stacking such polyno- mials results in overall order of N
Remark: practice, each matrix operation in the recursive formulation II-Nets represents an affine transform on vector. Therefore, the implementation in standard libraries may be simple as using a convolutional or fully-connected layer. The other difference arises due to the multiplicative layers, which may be seen as special 'skip' connections which are combined with the network output via the dlement-wise vector product (Hadamard product), as opposed to addition. Therefore, it is easy to see why these networks scale as well as standard deep networks.
15

---

Published as a conference paper at ICLR 2022
Order 2
Order 2
Order 2
%
G(*)
Figure 6: Schematic illustration of the product of polynomials model [16].
B EIGENVALUES DETERMINE THE SPEED OF LEARNING
As noted previously, the integral operator with respect to kernel function is defined as follows:
(z) = J( <( ())(d)))()))
(14)
The key idea in [12] is to establish guarantees on the speed of convergence of gradient descent along different directions of L,., as defined by its eigenfunctions. Consider {Aa with \ >> X > be the strictly positive eigenvalues of L, with { the respective eigenfunctions and define n (<'(x))))))))) ((x²) (( ()))). Since the eigenvalues may not be distinct, define rx the sum of multiplicities the first distinct eigenvalues of T, Define Vr, (v1..., Ur.). By definition, Warr,, are rescaled restrictions of orthonormal functions on the training examples. Therefore, they form a set almost orthonormal bases in the vector space IR"
Finally, denote y = (y1, un) and g) (fwre (x1). .............. fwo. (In))² as the ground truth and predictions at time t, respectively, where fwie: denotes the 2-layer ReLU network. Then the following result holds:
Theorem 4.2 [12]: Suppose [6,(x)] & M for j E [rx] and æ e gd+1, For any e, > and integer if n > 12(= max (Ara - Ar++1) (++))) m > Mppoly(T; a then with probability at least gradient descent with step size = O(m-)) satisfies:
n 1/2 VV (0) < 2 Ara) 1/2 || yl12 +
(15)
which is to say that the convergence rate of VIV g(0) or alternatively the projection of the residual eиror on the space spanned by the first Fą eigenvalues is controlled by the r eigenvalue Aru- With some additional work, this result can be extended the 2-layer II-Netby accounting for the extra width factor of (0VVoo /log m). noted previously.
The key takeaway in that with wide enough network and large enough sample size, gradient descent first learns the target function along the cigen-directions with larger cigenvalues. Since the decay of cigenvalues slower for the 2-layer 1I-Net, it leads to a speed-up in learning higher frequencies.
C PROOF OF THEOREM 1: DERIVING THE II-KERNEL
this section, we prove our first main result for the II-kenel corresponding to theorem two-layer II-Net fw parametrized follows:
Consider
V Ws(o(Wzz) a (Wiæ))]
fw(x)
(16)
where the weights W, xx W2 E mxd cally distributed ( coordinates.
W, E R xm are initialized with independent identi-
16

---

Published as a conference paper at ICLR 2022
Recall that the neural tangent kernel Kr corresponds to the limit of the following inner product
Kr xr, x²) lim W Vw (w/wo(())))>
(17)
m0-00
We can compute the inner-product Eq. (17) by computing the derivatives with respect to W1, W2, W3 of fw separately and sum up the inner products to obtain Ka. since the gradient can be split into three blocks.
denote by ā == Wi and by 3 = W2x the pre-activation vectors; and by a, 3 the post- activation vectors where the element-wise activation is applied to ā and B respectively.
First consider the derivative w.r. W1 denoted ow,
2
ow.fw fw)
W
a(()).
(18)
m
Since a; e. W (W1.ex²") where e, E Rm is the i-th canonical basis vector of R", have that
Ōw, (w) e.a""
(w(x),, (x), ēw, (w')) Note that since The contribution to the NTK (Eq. (17)) corresponds to (ōw, Jw the network is symmetric in (W1, W2), we need only look at W, obtain the contribution for W2 as well. We find that
(ww
Σ www.oddaaocccceeleeedd/dddodddde ,ea"!
m f.j-1 wwW.ccckcboobcchhllecccccceedddd 8, m W-=1
2 m
2 m wwW.doddcoooodcceeed////aadaaaad
(19)
As lim m co, the above quantity converges to its expectation by the law of large numbers because the terms are independent and identically distributed with finite expectation. Consequently,
lim (ōw, fw(x), (w, [w(w')) 22xx, x' xxx1 (xc x' )022
(20)
m-
since
Ew, ((( Ki (x, x²) Ew, [a (o((((())
K2, x²)
Lw. [
= 1.
By symmetry, we obtain with a similar term for Wa and their total contribution to Eq. (17) adds up to twice the term obtained for W₁. Characterizing the kernel w.r. W3 is more straightforward:
(w.fw(x) =V - (((()))) (
2 m
(21)
Therefore, its contribution the NTK is
(ew.fw(l)),...wl(e 2 (((
(22)
Applying the law of large numbers again, as lim oc, this quantity tends
17

---

Published as a conference paper at ICLR 2022
Ww..w.wor(((((.:))))))) ) 2) W x3}}}}
-Ew,lo( W1, Ew, [o (2 x))) ) (w2) )]
(23)
( x' )K x').
The theorem follows by summing up 2x Eq. (20) and Eq. (23).
Width Requirements
As noted previously, two-layer IT-Netneeds an the extra factor S2 log m) in terms of width, to stay close to initialization The proof is largely derived from Lemma A.6 [27], based on ideas first noted in [1] and therefore, we just provide rough sketch here. For simplicity, consider the set of weights (W2, Wa) fixed at initialization, i.e. W W and note the first-order Taylor expansion for the I[-Net w.r.t W1 as follows:
fw(x) fw(x)= fw) + (V w: fwoo (z), W1 w
Here fw denotes the first order Taylor expansion of f at Wo. We can then expand the RHS as:
2 Σ w (0) T w m 3.
(a
Wo) w()) ( + oa w 2o' w W
(W15 - w())
Consequently, we can bound the approximation error as:
2 Σ
(ww & m
w (()))))) ( + ta (w"w ( w()))
2.
Notice that aside from the (o W 2.) the enror term is exactly the same as that for a standard network. Also note that P( W2, > T) P(a(x"
T) < - for t > 0 by the the union
sub-gaussian tail bound. To ensure (s T W (0) & j with probability 6, bound to obtain the condition on m.e - < 8. Consequently, we have that [ (lvlog m), which essentially becomes an additional constant factor in the error term, over the usual error terms from the standard feed-forward network.
18

---

Published as a conference paper at ICLR 2022
D PROOF OF THEOREM 2: CHARACTERIZING THE II-KERNEL EIGENDECAY
Here, we prove the IT-kerne eigenvalue decay rate stated theorem 2. We first recall some connec- tions between spherical harmonics and Gegenbauer polynomials.
Definition For given I. Gegenbauer for ultraspherical) potynomials denoted C% [-1,1] - R are a family of orthogonal polynomials with respect to the weight function æ - (1 12)0-.. ie,
[ -
for k th f.
Remark: Gegenbauer polynomials are generalization of Legendre polynomials which can be re- covered by taking a 1
The following addition formula expresses Gegenbauer polynomials in terms of spherical harmonics.
Lemma (Theorem 4.11 in [20]) (Addition formula) Let (Yk.)) of degree k in d + variables. It holds that, for any x, x' E S".
N(d.)) denote spherical harmonics
N(d.)
(()
By making use of this Lemma, we can rewrite the Mercer decomposition of any admissible dot product kernel K when the data is uniform the unit sphere. Indeed, by simplifying the Mercer's decomposition terms of spherical harmonics we have
N(d.k)
K(x, [(xxx))= =
M
Σ (x)
R=
(24)
((,((k)) (<x,
where (px) are its corresponding cigenvalues, and the second equality follows from Lemma
Now, since K1 and K2 dot-product Mercer kernels, akin to Eq, (24), obtain their respec- tive decompositions in terms of Gegenbauer polynomials. There exist (H1,)) and (#2,)) both sequences of eigenvalues, such that
MI, (
(x, x Ke (x, x')
(25)
R2 62 x²)
(d
The decay rate of the eigenvalues ((i,)) and (12,)) is known [5, 10, 12] and is stated in the following Lemma.
Lemma (Appendix D.2 of Lemma 17 [10]) For d, even, we have that Pi,k d-1 --d) and P2.6 B(d)k-d-2-1) d-2-1/2 where A(d) and B(d) are constants only depending on the dimension d.
Our goal is to establish the decay rate of the eigenvalues (p (Mm,,) of the kernel
Ky (z. x') = xx, x e0)xo ( (x, x') + K2(2,, x') K2( x²). By plugging in the representations in Eq. (25) into the TT-kemel expression (Eq. (26)), find that
(26)
19

---

Published as a conference paper at ICLR 2022
S (d, (a, x'); u2 k) (<x, ((xxx")))
Kir (2, x²) = 2(
Σ 0=-
(2
x')))
(27)
Moreover, since we can also write
8 Σ Mn. ((d
+ (Kx, 2')),
Rig (z. x
((x),
1=0
an appropriate factorisation of the product Eq. (27) will allow us to deduce the order of Mr,k by equating the coefficients appearing front of the Gegenbauer polynomials.
Developing the product in Eq. (27) leads to the appearance of products of Gegenbauer polynomials. The product of two Gegenbauer polynomials turns out to linear combination of other Gegen- bauer polynomials.
Lemma (Equation [13]) Let a IR for any m, n there exists positive coefficients (A (m) min(m.n) such that s-0
min(m.n)
C (z)
Σ
Xmm Chot
(28)
By using this expansion, coefficients for each Gegenbauer polynomial may be identified.
Take k E N to be an even number. We know from plugging Lemma 3 into Eq. (27) that the coefficient
(d=1)
Mm.2k (d, 2k) in front of the polynomial
can be lower bounded as follows.
2k
Ha 2x, 2k) > (d, () + 22,4) (k.b)
(29)
We obtain this lower bound by considering the contribution of single term in Eq. (28) where m = n and s = to the coefficient in front of chf ( This contribution a lower bound because all coefficients involved in the product non-negative.
Consequently, order to establish a decay rate for (HT,,) suffices to study the decay rate of (k.kk)
This rate is given by the following Lemma.
Lemma Let d-1 be an integer, the coefficient No (k.k) defined in Lemma 3 admits the following expression (k.kk) ((o+--1))2 (24)) (a []]])] (a+2k-1) m.. Moreover, for k d, it holds that
A (k. k(d/2).
See Appendix D.1 for proof.
We now dispose of all the necessary results to prove Theorem 2. Starting from Eq. (29), we find that for l >> d, we have that
((d,k)² (2 + 12,4) (R.A) (k..)
Ms N(d, (k)
kd
(2k)d (2)11, + 12. kd
(k.k) (k.k)
(by Stirling)
(30)
2d ( 22 -(((2)) 4/2 4/2-2).
(by Lemma 2 and Lemma 4)
This concludes the proof that, for divisible by 4, we have Mr, 9(k 0(k--/222) For k mod 4, conduct the same reasoning taking the coefficient x 1,2+1.22)) For l 3 mod 4. the coefficient to consider is X (2k+1, 1,22+), The equivalence derivation Lemma 4 proceeds in exactly the same manner for these coefficients.
20

---

Published as a conference paper at ICLR 2022
D.1 PROOF OF LEMMA 4
Let us denote (a)s == a(a + (a + 2)....(ax+ k 1) and (a)o == 1.
From Equation 8 in [13], we have that
2k + a (a)o(a))(o)) (20)2x (2k)
10 (k.b)
2k + O!(K)!(A)) (a1)2 (2cx2s
(a)x(a) (2k)!
(k)!(k) (a)2x
(31)
((a k- 1)!)² (2k)!(a - 1)!
((a--)((k)!)² (a 2k 1)!
((a + --1 (2h)
(a - ())(()))) (a 2k 1)!"
We apply Stirling's approximation stating that n! /2nn( ) to find that:
(R.A) k -
(2k(2))
(32)
Va- k()-)) Va + 2h- 1(a + 2k - 1)0+2k-1
Considering the case when & >> a or equivalently, >> since a = (d- - 1)/2, we obtain the following simplification:
1(20422-11
(2k) 22-))
10
(k,k)
1
(2k) 2k-00
(33)
y0 1d/22)
h
21

---

Published as a conference paper at ICLR 2022
E LEARNING SPHERICAL HARMONICS WITH II-KERNE
Following the setup in [12], we perform a similar experiment on learning combinations of spherical harmonics in the NTK regime. We define and initialize the 1I-Net exactly as specified, with width of 32768 neurons and using vanilla gradient descent, to approximate the kernel learning in the infinite width limit. We take 1000 samples, {a:}__ from the uniform distribution on the unit sphere goo,
We define our target function with integral & E K. as follows:
(x))= N(C)
Σ A,Pa((a, KEK
(34)
where the (t(t) is the Gegenbauer polynomial with degree k. C2 are fixed vectors that are indepen- dently generated from uniform distribution on unit sphere in IR and N(K) a suitable normalizing constant to keep the order of magnitude of the target function approximately the same for different choices of K. As noted previously, f may be seen as a linear combination of spherical harmonics and we compare the error residuals during the learning process in standard vs I1-Nets in the NTK regime, for varying K. We use a moving average of range 20 on these curves to smoothen out the heavy oscillations in the latter stages.
FIRI= I Pulk A. R= (0
restuul projection kength 1log Sc4M))
Mandardd-een cermel Diceme!
propectton beoggh Beg wodde)
standard-aama
resional projcctoon tengin 100g scotto
dandand cerme
OHiee nel
Dicerne!
500D 10000 32003 20000 25000
30000
5000 10000 15000 20003 75020 2000
5300 10000 15003 20000 25200 30000
Bwcations
beneltons
Figure 7
The plots represent comparison of log-scale convergence curve of error projection lengths for standard vs Il-kernel for different order harmonics with K = {1,2, 43. indicating a clear improvement in the rate of convergence of error for higher harmonies
Figure 8:
For the first setting, we look K. 21,2,44 4), with corresponding weight ratio as A A2 A 1:1: 1. For each frequency, we look at the rate of convergence for the two kernels. We observe (Fig. 8) that the rate of error convergence for the TI-kernel is much faster than the standard two-layer NTK and especially for higher harmonics (clearest increase for the highest k = 4), which exactly what expected from theoretical results.
Next, we consider K = {1, 3, 4,5,8 8, 12} i.e. we consider higher frequency harmonics and also introduce odd harmonics, with the respective Aş assigned the equal weights relative to each other. Recall that the eigenvalues corresponding to odd harmonics vanish for the standard kernel, meaning that we expect a much slower convergence rate for them. As before, we look at the rate of conver- gence for individual harmonies for the two kernels. The convergence curves are presented in Fig. 9. We verify the speed-up in higher frequencies, and an especially notable gap for odd harmonics other than & = 1.
The empirical results strongly support our hypothesis that the II-kernel can speed up learning higher harmonics faster than the standard two-layer kernel, even for settings outside of >>> d.
Discussion:
22

---

Published as a conference paper at ICLR 2022
Coo Σ. D.D.P.DK.GII 8.
1-1
8-5
2-44
PesSUU projection kenott U00 (CAMe)
#andart-komel tikerne!
PeSStUM project lenggh: Hog scaMe)
restoual project lennit: 100 accile)
standard- seme mikenll
5000 13008
25000 50000
5000 15000
30000
20002 25002 50000 borotions
TeNEO project on tenoth too scales
Fee Ch project on tenggh tho SCAle)
doul project on tooggh (1og sc280)
15500
15030 Berstorr
19000
Perstions
terations
Figure 9: The plots represent comparison of log-scale convergence curve of error projection lengths for standard vs II-kernel for different order harmonics with AC = {1, 3, 4, 5, 8, 12). We again a clear improvement in the rate of convergence of error for higher harmonics, and especially so for odd harmonics greater than 1.
23

---

Published as a conference paper at ICLR 2022
F SYNTHETIC EXPERIMENTS WITH SINUSOIDS
F.1 LEARNING SINUSOIDS
standard-net (depth Depth Polynomial: Learning
Ti-net (depth injections)
Iterations
0.4
0.4
002
0.2
10000
0.0
0.0
10
25
30
40
45
50
15 20
30
35
40
Frequency [Hz)]
Frequency [H22]
Figure 10: The heat map denotes comparison on the effectiveness of increasing depth introduc- ing multiplicative interactions via II-Nets for learning high-frre freh-frreuency information. The empirical evidence shows that multiplicative layers are more effective for learning higher frequencies faster.
Additive Multiplicative Skip Connections: Learning Sinusoids
standard-nen net (depth 6, additive skip connections)
Tiinet (depth 6, injectioon)
40000 50000
0.8
0.8
Iter peraaiinss
0.6
terations
0.6
10009 20000 30000
0.2
0.2
0.0
0.0
5
10
15
20
25
30
35
40
45
50
5
10
15
20
25
30
35
40
45
50
Frequency [Hz]
Frequency [Hz]
Figure 11: The heat map denotes a comparison on the effectiveness of multiplicative layers via Nets only using additive skip connections. The additive skip connections do not to affect the spectral bias over standard neural networks in terms of improving speed of learning for high frequencies.
F.2 ROBUSTNESS
Robustness to Perturbations: Motivated by the observations of Rahaman et al. [37], we evaluate the susceptibility of higher frequencies to random perturbations for standard networks and II-Nets. The setup relies the learning task in the previous experiment. More precisely, following conver- gence of the network to low-error approximation of target f* (denoted by fee), random isotropic
perturbations are introduced to the network parameters: 0 = 8* + 80. We monitor the effect of increasing the perturbation magnitude 8 on the frequencies of interest. In the first setting (Fig. 12), the six-layer standard network the six-layer I[-Net
compare the effects of perturbations (with five multiplicative layers). the second setting (Fig. 13), we directly compare the two vari- ants of 6-layer deep II-Nets i.e. one with five layers and the other with three layers. We observe that that II-Nets are more robust to perturbations, especially in terms of retaining high frequency information, compared standard feedforward networks. We also note that the presence of more multiplicative interactions makes the network more robust.
24

---

Published as a conference paper at ICLR 2022
Comparison Robustness
standard
ninet (depth injections)
1.0
100
0.8
0.8
Perturbation Norm
teeration
0.6
2.0
0.4
0.4
1.0
0.2
-02
Frequency [H2]
Frequency [H2]
The heap maps present comparison the robustness random parameter perturba- tions for six- six-layer standard vs six-layer IetN The y-axis denotes the norm of the random pertur- bation. For standard networks, the high-frequency information is lost quickly the perturbation norm increases, while IT-Nets are much more effective at retaining higher frequency information, under large perturbations.
Figure 12:
Effect Robustness
(depth injections)
Thnet (depth injections)
-1.0
-10
0.8
0.8
Perturbation Norm
99
lterations
0.6
2.0
0.4
1.0
0.2
002
0.0
Frequency [H2]
Frequency [H2]
Figure 13: The heap maps present comparison the robustness random parameter perturbations for two variants of II-Nets, one with three multiplicative injection layers and the other, a higher degree polynomial with five multiplicative layers. We observe higher degree polynomial leads to higher robustness, which is consistent with our intuition that multiplicative layers expand the solution space for learning high-frequency information.
25

---

Published as a conference paper at ICLR 2022
G EXPERIMENTS WITH IMAGES
G.1 IMPLEMENTATION DETAILS
U-net type hourglass architectures provide the ideal inductive bias for a host of image restoration tasks in the DIP framework and for our experiments, we use the same architectural design as [33] for the standard networks. Since we require the output and imput to have the same spatial dimensions, the number of downsampling blocks is equal to the upsampling blocks. We refer to this number as the 'scale" of the U-net. We provide a schematic illustration Fig. 14.
Skap
Down Sampling
UpSampling
G(x)
Down Sompling
UpSampling
Figure 14: Illustration for the U-net with scale = 2, i.e the standard network with two upsam- pling/downsampling operations.
Note that the each down/upsampling block within itself contains convolutions, normalization and pooling but we abstract those details from the schematic for clarity. For the Il-network architecture, we consider product of two polynomials model which modifies the standard network by introduc- ing multiplicative connections. An illustrative schematic is presented in Fig. 15.
Doee: Samping
Up Samplig
Sumplin
Up Suaplinx
Figure 15: Adapting the 2-scale U-net for the product of two polynomials II-network, the vertical dotted line highlights the separation between the polynomials.
Remark: In addition to the architecture, it is important to note another important detail about using II-Nets. In practice, we recommend the use of two separate learning rates while training II-Nets, wherein the learning rate for multiplicative connection parameters specifically is lower than the learning rate corresponding the parameters the berw-fo part of the network. leads to more stability while training.
26

---

Published as a conference paper at ICLR 2022
G.2
ADDITIONAL EXPERIMENTS
100
$ 1
?
&E
200
KO
Ko
300
400
500
200
400
600
800
0
100
3
&
200
Ko
Ko
300
Earea
400
500
0
200
400
600
800
(b)
Figure 16: Visual comparison of the denoised image pertaining to the denoising experiment in 4.2. We compare a snapshot (right) of the respective network outputs after 2500 iterations against the true image (left) for (a) standard network (b) II-Net. We visually confirm that I--nework has already begun to fit the high- figh-frequency noise faster and to a larger extent.
27

---

Published as a conference paper at ICLR 2022
10
multiplicative layers
multiplicative layers
multiplicative layers
P[[
106
100
10
102
||l
Figure 17:
We visualize the deep image prior of different II-Nets initialization with random weights for the same input, by looking at the power spectral density of the output. With a fixed U-net architecture, introducing trum towards higher frequencies, which offers intuition towards understanding why multiplicative interactions speed up learning in high-frequency information.
multiplicative interactions in network shifts the network spec-
Iteration :
Iteration 75
Iteration : 150
10
true image
100
n-network
10a
10a
standard network
PQ][[[])
107
105
image n-network
105
true
n-network
standard network
standard network
100
10a
10a
10
10a
10a
10
10a
10a
||a||
||w||
||a||
Iteration
Iteration
Iteration
10a
10a
P[[[]]]
105
true image
[1-neworr
108
true image
n-network
105
true image
fl-nework
standard network
standard network
standard network
10
10a
10a
10
10a
10
10a
10a
|||||
||M||
||M||
Iteration: 450
Iteration 525
Iteration : 600
10a
10a
20a
P(][W]]
true image
true image
true
105
T-network
105
n-network
10a
n-network
standard network
standard network
standard network
100
10a
102
109
101
10a
100
10a
10a
|||||
||]||
||]]|
Figure 18: Comparison of the power spectral density curves over 600 iterations for standard II networks (same scale) against the ground truth. We observe that the II-Net pick up higher frequen- cies faster.
28

---

Published as a conference paper at ICLR 2022
H
ADDITIONAL EXPERIMENTS IN CLASSIFICATION
pi-net (1 multiplicative layer)
standard-net
10"
MSE Validation Loss
freq 0.0
freq 0.0
freq 0.05
freq 0.05
freq
freq
freq
freq
freq 0.3
freq 0.3
freq
freq
freq
freq
200
400
600
800
1000
0
200
400
600
800
1000
Training Iteration
Training iteration
(a) Validation loss curve zoomed in for first 1000 iterations.
pi-net (1 multiplicative layer)
standard net
100
MSE Validation Loss
freq 0.0
freq 0.0
freq
freq
10-1
freq 0.1
freq 0.1
freq 0.2
freq 0.2
freq 0.3
freq 0.3
freq 0.5
freq 0.5
freq
freq
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
Training Iteration
Training Iteration
(b) Validation loss curve for 5000 itcrations.
Figure 19: Validation loss curves corresponding the classification experiment, presenting com- parison between II-Net with one multiplicative layer and standard feedforward network. The smaller dip for I[-Net implies a tendency to pick up high frequency label noise faster.
Our results allow us to make further overarching conclusion that II-Nets, in addition to picking up higher frequencies w.r.t inputs faster (as demonstrated in the DIP settings), in classification settings can also pick up high frequency variations in the decision boundaries faster, thus making our general claims about the spectral bias II-Nets and multiplicative interactions stronger.
29

---

Published as a conference paper at ICLR 2022
pi-net (1 multiplicative layer)
pi-net (2 multiplicative layers)
10a
MSE Validation Loss
freq = 0.05
freq = 0.05
freq
freq 0.2
freq 0.2
freq 0.3
freq 0.3
freq
10-1
freq
freq
200
400
600
800
1000
0
200
400
600
800
1000
Training Iteration
Training iteration
(a) Validation loss curve zoomed in for first 1000 iterations.
pi-net multiplicative layer)
pi-net (2 multiplicative layer)
freq 0.05
freq 0.05
freq 0.1
freq 0.1
freq 0.2
freq = 0.2
MSE Validation Loss
freq 0.3
freq 0.3
freq 0.5
freq 0.5
freq
freq
10-1
2000
3000
4000
1000
2000
3000
4000
5000
Training Iteration
Training Iteration
(b) Validation loss curve for 5000 itcrations.
Figure 20: Validation loss curves corresponding the classification experiment to observe the effect of increasing multiplicative injections. We compare the IT-Net with one multiplicative layer to TI- Net with two multiplicative layers. The validation dip reduces even further for the TT-Net with more multiplicative layers (i.e., a higher degree polynomial) indicating that more multiplicative interactions improve the network's ability learn more complex decision boundaries (introduced by the high frequency noise).
30


Reviews:
[{"review_id": "YM2-3LFs4LY", "reviewer": "Reviewer_FuRi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: This paper provides an interesting viewpoint to explain why polynomial neural network performs better than feedforward neural networks in some vision tasks. The story is that PNN learns high-frequency components faster, and high-frequency components matter in these specific tasks.\n\nWeakness:\n1. Oversimplification: the model this paper analyzes can hardly be seen as a 'polynomial network'. It has two layers, which at best can express a quadratic function. For a two-layer structure, I see no necessity in forcing the $\\Pi$-Net formulation. Additionally, the original PNN has no non-linear activations, while the simplified two-layer model has ReLU activations.  While I understand that the spectral analysis in previous works is performed on two-layer nets, the authors should at least explain in the paper why not analyze the full-rank polynomial network and why the ReLU activations. Currently, I feel the theoretical results for the two-layer model cannot really be applied to the PNN in practice. \n2. Technical Novelty: I feel the technical novelty is lacking. The only novel contribution of this paper is to show the decay rate is slower. And to calculate the order of the eigenvalues, most efforts have been done in previous papers, except the arguments from equation (28) to equation (32). The eigenvalues of $\\kappa_1$ and $\\kappa_2$ are calculated in [7]; and 'larger eigenvalues imply faster learning' is proved in [9].\n\n3. Mathematical Rigor & Presentation: it would be better to reformulate the arguments from (28) to (32), by building up inequalities between the eigenvalue and terms that are calculated. Currently, the proof looks very sloppy. When setting up the mathematical notations, it is better to keep the paper self-contained. For example, the mode-$m$ product is not introduced here. Another drawback is that the main body does not introduce why larger eigenvalues imply faster learning. This may cause a less informed audience at loss.\n\n", "summary_of_the_paper": "This paper considers a simplified model of the polynomial neural network, and shows that the eigenvalues of the induced tangent kernel have a slower decay rate, compared with the classical two-layer network. This also means the polynomial neural networks can learn the high-frequency components faster. The empirical evidence supports this tendency.", "summary_of_the_review": "While the topic and story of this paper are interesting, it has several drawbacks that need to be addressed. The setting is very restricted, and the theoretical results lack novelty.\n\n\n\n========Post-rebuttal updates===========\n\nI raise the score from 3 to 5, given that the presentation of the updated version is more rigorous and clear.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SEdQnb_2Vod", "reviewer": "Reviewer_nFMY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Note that the network (7) for which NTK kernel was calculated and spectral analysis is made, is not a Π-Net (because it includes ReLU as sigma). So, why can we apply the spectral analysis to Π-Net architecture?\n\nExperiments seem to support the main claim, though fig 5 shows that the difference from standard network is not so sharp. Eventually, it seems that the standard network is also able to learn the high frequency. Also, experimental setups are taken from well-known papers. \n\n", "summary_of_the_paper": "The paper is dedicated to the study of spectral bias in polynomial neural networks. For feed-forward neural networks with ReLU activation function it is well-known that learning high-frequency terms is made slower (Rahaman et al.). \n\nAuthors claim that polynomial networks are able to learn both low frequency and high-frequency terms almost equally fast. Theory, based on spectral analysis of an integral operator associated with the NTK kernel, is provided.  Theoretical approach was taken from arXiv: 1905.12173, but for NTK kernel of the network with an additional multiplicative interaction layer. \nThen, experiments that support claims are provided. \nIt is claimed that multiplicative interactions in the architecture of a NN may be the reason for an ability to learn high frequencies. \n", "summary_of_the_review": "The narrative is well structured and easy to read. The main claim is partially supported. Weak aspects of Π-nets are not discussed. I would assess that it is a borderline paper.", "strength_and_weaknesses": "", "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": {}}, {"review_id": "CRyKjYOBYqV", "reviewer": "Reviewer_cEcf", "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": "Overall I think this paper is well organized and well written. The proof of this paper seems solid. The main theoretical contributions of this paper are Theorem 1 and 2. Theorem 1 gives the kernel limit of two-layer $\\Pi$-net. And Theorem 2 computes the eigenvalues of the linear operator. Given the techniques used in reference [9], the proof of Theorem 1 and 2 are quite strict forward.  The empirical results are quite clear and well supports the main theorem. It's is quite interesting that $\\mu_{k} = \\Omega(k^{-d/2 -2 })$ rather than $\\mu_{k} = \\Omega(k^{-d - 1})$.  What will happen if we increase the number of layers or the degree?", "summary_of_the_paper": "The paper gives an analysis of polynomial networks in the NTK regime. They show a theoretical speed-up in learning higher frequencies when using polynomial networks. They also have some experiments that verify these properties. ", "summary_of_the_review": "This paper is well organized and well written.  The proof is solid, and the empirical results support its claim. However, given the previous paper the, proof techniques are not novel. Therefore, I would only suggest a weak acceptance.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6JMnLOhMK5r", "reviewer": "Reviewer_KnZp", "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": "Main strengths of the paper\n1. Ability to control the spectral bias of neural networks is an important and mostly open question, at least for networks that operate on high-dimensional inputs. This paper offers a valuable step in this direction by showing that multiplicative connections reduce the low-frequency bias of neural networks.\n2. The paper is clearly written.\n\nMain limitations of the paper\n1. The theoretical contribution is limited to a very restrictive model: 2 layers, no nonlinear activation function, no bias term, and many more data points than parameters. Further, the analysis is in the NTK regime, which assumes that width tends towards infinity and learning rate tends towards zero.\n2. Although the experiments do test violating the 2-layer assumption and the NTK regime assumptions, they remain restricted to very low dimensional problems (1D synthetic functions and 2D images) where, to the best of my knowledge, a neural network would not be the go-to method in real applications.\n3. The related work section is very sparse. This should include prior work on spectral bias of ReLU networks (some of which is included in the introduction, but not all--for example, https://arxiv.org/abs/1906.00425 and https://arxiv.org/abs/2003.04560). It should also include other methods that affect spectral bias, for example https://arxiv.org/abs/2006.10739. \n\nLow-level suggestions\n1. Claim 2 could be more specific. Upon a first reading of “standard inverse problems in imaging” I expected some 3D imaging or CT or MRI experiments, but this is actually referring to 2D image denoising.\n2. Equation (1) uses the “mode-m vector product”. A quick search showed me the definition of this operation, but it would be easier for the reader if this were defined in the paper (perhaps with examples in the case of vectors and matrices).\n3. Equation (2) could be visualized with a simple diagram of the 2-layer pi-net you analyze.\n4. It would be helpful for the last sentence of section 3.3 to mention the Schur product theorem as justification.\n5. It would be helpful to more clearly delineate the difference between the first and second experiments in section 4.1. As far as I can tell the difference is that the first uses large width and low learning rate and the second uses a smaller width and larger learning rate (to violate NTK assumptions), but these should be stated explicitly.\n6. Figure 2 is not very convincing--actually I find Figure 11 in the appendix to be a more compelling comparison, both visually and in terms of the relevance of the comparison.\n", "summary_of_the_paper": "The paper presents a theoretical analysis of the RKHS of the NTK of two-layer polynomial neural networks without bias terms or nonlinear activations. The primary difference between these networks and standard ReLU networks is the presence of (elementwise) multiplicative skip connections, which the authors show (both in the NTK analysis and experiments) improves the convergence rate for higher frequency target functions. ", "summary_of_the_review": "The paper offers an interesting approach to reduce the spectral bias of neural networks by introducing multiplicative connections, and supports this claim with NTK analysis of shallow networks and experimental evidence on low-dimensional synthetic and real data. Although both the theoretical and experimental contributions are rather restricted, I hope they will serve as useful building blocks for subsequent research on more realistic models and data.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "216ssAT7FRC", "reviewer": "Reviewer_TQnp", "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": "The paper is well written and explains the problem as well as the approach clearly. I appreciate the authors for spending their time polishing the writing, providing clean theorems, and reviewing the literature.\n\nI also think that the problem presented here is meaningful and worth further studying. The fact that PNNs well learn high-frequency signals while general NNs don't indicate that some unique attributes of PNNs enable the model to retain a certain level of signal-to-noise ratio. The existing and current mathematical analyses on this open problem have shone a light on practical applications. Personally \n\nOne of the main concerns is that the paper studies only two-layer PNNs, which is restrictive. The authors stated in the abstract that \"we expect our analysis to provide novel insights into designing architectures and learning frameworks...\" But it seems to me that two-layer NNs may demonstrate significant behavior compared to DNNs. For example, I am not sure if the fairness of two-layer NNs extends to deeper models. Also, the analysis leverages an infinite-width assumption, far from being practical. \n\nAnother concern is regarding the experiments. The experiments considered the performance of NNs with more than two layers. Though the previous theoretical analysis does not apply to this setting, more layers make the scenarios more practical. But given the scale of the experiments, I think it might be reasonable to consider other supervised learning methods here. Alternatively, as the setting already violates the two-layer assumption, maybe it is appropriate to consider practical applications with high-dimensional and large datasets. \n\nFinally, I suggest the authors provide a better discussion in the related work section. Currently, it contains only two paragraphs, not delivering sufficient insights. In particular, it would be good to add comparisons (theories & techniques & proofs) between the essential references and the submission, i.e., what makes the paper special?\n", "summary_of_the_paper": "The paper studies ReLU-activated two-layer neural networks. The main contribution is that unlike traditional deep neural networks (DNNs), this type of polynomial neural network (PNN) also learns high-frequency information quickly. This claim partially verifies why PNNs are suitable for tasks like face recognition, where high-frequency components are crucial for performance. ", "summary_of_the_review": "I like the writing quality and the problem. While it is common to start with simplified models for theoretical analysis, I expect a more profound theorem addressing broader PNN families given the existing work. I appreciate the authors for discussing the prior work and performing experimental comparisons. But I think both aspects are subject to further improvements, i.e., the experiments should emphasize practicality, and the literature review could help differentiate the paper's contributions. ", "strength_and_weaknesses": "", "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:

Meta-review: *Summary:* Investigate the NTK of PNNs and enhanced bias towards higher frequencies. 

*Strengths:* 
- Spectral bias is a contemporary topic. 
- Some reviewers found the paper well written.

*Weaknesses:* 
- Restricted setting (two-layers / no bias / infinite width), particularly in view of the objective to provide architecture design guidance. Restricted experiments (Introduction indicates learning spherical harmonics). 
- Sparse discussion of related works, particularly on spectral bias. 

*Discussion:* 

During the discussion period authors made efforts to address some of the concerns of the reviewers. A late new experiment prompted KnZp to raise score. TQnp found the paper good but also expected a more profound theorem addressing broader PNN families given the existing work. They found that experiments and discussion of prior work could be improved. The authors added discussion of prior works and provided an explanation for their choices, but left extensions and further analysis for future work. nFMY expressed concerns about applicability of the analysis and evidence in experiments. Author responses addresses this in part. cEcf points out that the main theoretical contributions have straight forward proofs based on previous works and asks about extensions. Authors agree that the paper does not introduce novel techniques and that extending the analysis is an important direction, but leave this for future work. FuRi finds the paper provides an interesting viewpoint and raised score from 3 to 5 following the discussion (improving presentation, rigor, clarity), but considers that the paper has several drawbacks (oversimplification, lack of technical novelty) that need to be addressed. 

*Conclusion:* 

One reviewer found this work marginally below the acceptance threshold, three marginally above, and one good. I find that the paper considers an interesting problem and makes some interesting observations and some valuable advances. I appreciate the authors’ efforts during the reviewing period. Hence I am recommending accept. At the same time, I find that, clarity, technical and experimental contributions still can be improved and encourage the authors to carefully consider the reviewers comments when preparing the final version of the paper.
Decision: Accept (Poster)