The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies

By Ronen Basri, David W. Jacobs, Yoni Kasten, Shira Kritchman. 2019

267 citations recorded by the source corpus.

We study the relationship between the frequency of a function and the speed at which a neural network learns it. We build on recent results that show that the dynamics of overparameterized neural networks trained with gradient descent can be well approximated by a linear system. When normalized training data is uniformly distributed on a hypersphere, the eigenfunctions of this linear system are spherical harmonic functions. We derive the corresponding eigenvalues for each frequency after introducing a bias term in the model. This bias term had been omitted from the linear network model without significantly affecting previous theoretical results. However, we show theoretically and experimentally that a shallow neural network without bias cannot represent or learn simple, low frequency functions with odd frequencies. Our results lead to specific predictions of the time it will take a network to learn functions of varying frequency. These predictions match the empirical behavior of both shallow and deep networks.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Scaling & Learning Theory, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Scaling & Learning Theory

In Statistical Learning Theory

Citations in the corpus

Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains (2020, background): “Analysis of the NTK’s eigendecomposition shows that its eigenvalue spectrum decays rapidly as a function of frequency, which explains the widely-observed “spectral bias” of deep networks towards learning low-frequency functions [3, 4, 33].”
When and why PINNs fail to train: A neural tangent kernel perspective (2020, background): “For fully-connected networks, the eigenvectors corresponding to higher eigenvalues of the NTK matrix generally exhibit lower frequencies [29, 42, 32].”
On the Similarity between the Laplace and Neural Tangent Kernels (2020, methodology): “With no bias, however, two-layer networks are nonuniversal, and in particular λk = 0 for odd k ≥ 3 [7].”
Implicit Regularization via Neural Feature Alignment (2020, background): “Several recent works (Bietti & Mairal, 2019; Basri et al., 2019; Yang & Salman, 2019) investigated such bias for neural networks, in linearized regimes where the tangent kernel remains constant during training (Jacot et al.”
Frequency Bias in Neural Networks for Input of Non-Uniform Density (2020, methodology): “Additional work (Bach, 2017; Basri et al., 2019; Bietti & Mairal, 2019; Cao et al., 2019) proved the existence of frequency bias in NTK models of two-layer networks and derived convergence rates of training as a function of target frequency.”
On the eigenvector bias of Fourier feature networks: From regression to solving multi-scale PDEs with physics-informed neural networks (2020, background): “For conventional fully-connected neural networks, the eigenvalues of the NTK shrink monotonically as the frequency of the corresponding eigenfunctions increases, yielding a significantly lower convergence rate for high frequency components of the target function [30, 32].”
Knowledge Distillation in Wide Neural Networks: Risk Bound, Data Efficiency and Imperfect Teacher (2020, background): “ined by online-SGD and get a similar bound of Oe[L q > z 1 n z=n]. A slower increasing q > z 1 n means a faster decreasing generalization error, which also means the task is more data efﬁcient. [19] supports our idea from the perspective of optimization. They calculate ( x;x)’s eigensystem in ”
Multiview Neural Surface Reconstruction by Disentangling Geometry and Appearance (2020, methodology): “ayers of width 512. We use the non-linear maps of [38] to improve the learning of high-frequencies, which are otherwise difﬁcult to train for due to the inherent low frequency bias of neural networks [45]. Speciﬁcally, for a scalar y2R we denote by k(y) 2R2kthe vector of real and imaginary parts of”
On the Inductive Bias of Neural Tangent Kernels (2019, background): “The zero eigenvalues prevent certain functions from belonging to the RKHS, namely those with non-zero Fourier coefficients on the corresponding basis elements (note that adding a bias may prevent such zero eigenvalues [9]).”
COIN: COmpression with Implicit Neural representations (2021, background): “While overﬁtting such MLPs, referred to as implicit neural representations, is difﬁcult due to the high frequency information contained in natural images [3, 34], recent research has shown that this can be mitigated by using sinusoidal encodings and activations [23, 34, 30].”
Towards Understanding the Spectral Bias of Deep Learning (2019, result): “[Basri et al., 2019] established similar results as [Bietti and Mairal, 2019], but considered the case of training the first layer parameters of a two-layer networks with bias terms.”
A Fine-Grained Spectral Perspective on Neural Networks (2019, background): “Finally, we note that several recent [64] or concurrent [9, 8] works studied one-hidden layer ReLU neural networks over the sphere, building on Smola et al.”
Tensor Programs II: Neural Tangent Kernel for Any Architecture (2020, background): “The spectrum of NTK has been analyzed to provide finer-grained answers to these problems [10, 24, 65].”
Finite basis physics-informed neural networks (FBPINNs): a scalable domain decomposition approach for solving differential equations (2021, background): “This is the well-studied observation that neural networks tend to learn higher frequencies much more slowly than lower frequencies [Xu et al., 2019, Rahaman et al., 2019, Basri et al., 2019, Cao et al., 2019], with various convergence rates being proved.”
Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks (2021, methodology): “5 γ ≤ 1 , ResNTK of inﬁnite depth converges to FC-NTK with L = 1 hidden layer, i.e., NTK for a bias-free two-layer MLP, for which it was shown in (Basri et al., 2019) that the eigenvalues for odd frequencies with k ≥ 3 are zero.”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, methodology): “Different decompositions of the learning process for neural networks have been used: [83, 104, 87, 105] study the learning in the Fourier domain and show that low-frequency functions are learned earlier than high-frequency ones.”