Source-linked AI summary
The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
Ronen Basri, David Jacobs, Yoni Kasten, Shira Kritchman
TL;DR
The paper studies how function frequency relates to neural-network learning speed and addresses the role of omitted bias terms in linearized analyses. It derives frequency-dependent predictions and shows that these predictions, including slower learning of higher frequencies, match experiments on shallow and deep networks.
Problem
The paper examines why overparameterized networks can learn simple solutions and whether learning dynamics explain their preference for low-frequency functions.
Method
The authors analyze a linearized gradient-descent model on hyperspherical data, compute its frequency-specific eigenvalues, and modify it to include bias terms.
Results
Functions of frequency k are learned in time scaling as k^2, while bias-free two-layer networks cannot represent or learn odd-frequency functions; experiments support these predictions in shallow and deep networks.
Takeaways & Limitations
Gradient descent acts as frequency-based regularization: networks fit low frequencies first, favor smoother interpolants, and may reduce high-frequency noise through early stopping.
Takeaways & Limitations
The relevance of lazy-training results to large-scale real-world systems remains unresolved, although experiments fit the predictions in real but simple networks.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper analyzes why neural networks learn low-frequency components faster than high-frequency components and derives frequency-specific convergence predictions. It also shows that bias is necessary for shallow networks to represent and learn odd-frequency functions, while experiments support the predictions in shallow and deep networks.
- Motivation: Overparameterized networks can learn low-frequency components significantly faster than high-frequency components under uniform data distributions.The analysis uses a linearized training dynamics model and frequency analysis.
- Convergence predictions: The linear-system analysis computes eigenvalues that predict how quickly each target-function frequency is learned.For one-dimensional functions, the predicted learning time scales as k2.
- Bias terms: Without bias, shallow two-layer networks cannot represent or learn odd-frequency functions, including simple low-frequency cases.The paper therefore modifies the model to include bias.
- Bias terms: Adding bias preserves spherical-harmonic eigenvectors and allows odd frequencies to be learned at rates similar to even frequencies.This addresses the representational deficiency of the bias-free model.
- Empirical behavior: A network first fits low-frequency structure and gradually adds higher frequencies, producing low-frequency interpolation where data are missing.In the illustrated one-dimensional example, the learned function is almost purely low frequency.
- Implications: The frequency-based learning pattern helps explain why early stopping and gradient descent can favor smooth, generalizing solutions over complex high-frequency fits.The paper connects faster low-frequency learning with reduced overfitting when low-frequency fits are available.
2 Prior Work
Prior work connects neural-network training dynamics, architecture, frequency content, and generalization, but largely does not provide explicit convergence-speed predictions. Existing linearized analyses also commonly omit explicit bias terms, while the relevance of lazy-training theory to practical systems remains debated.
- Frequency analyses: Earlier analyses related network outputs or gradient-descent updates to Fourier frequency but generally did not explicitly predict convergence speed.Some approaches imposed strong assumptions, such as zero outputs outside a bounded domain.
- Frequency analyses: Other work studied shallow-network convergence, band-limited functions, and the ability of deeper networks to learn frequencies inaccessible to comparable shallow networks.These studies address convergence bounds, depth, or component frequency rather than the paper’s explicit speed predictions.
- Optimization and generalization: Research on gradient descent and generalization includes max-margin solutions, generalizable solutions, and weight-matrix alignment in linear or shallow networks.These results examine optimization dynamics and generalization across several settings.
- Linearized dynamics: Linearized analyses of heavily overparameterized networks show that weights change little during training and commonly omit explicit bias terms.Bias was often treated as unnecessary because a constant value could be appended to normalized training data.
- Open questions: The relevance of lazy-training results to large-scale practical systems remains an open question, although the paper’s experiments match its predictions in simple real networks.The limitation concerns extrapolation from the analyzed regime to large-scale systems.
3 Background
The paper reviews a linear-dynamics model for shallow, overparameterized ReLU networks trained by gradient descent. For uniformly distributed data on a hypersphere, the expected Gram matrix is a convolution operator whose eigenvectors are spherical harmonics.
- 3.1 A Linear Dynamics Model: Gradient descent evolves the network outputs through a dynamic matrix Z whose indicator entries depend on which ReLU units are active.Because activation indicators change between iterations, Z and the associated Gram matrix H are time-dependent.
- 3.1 A Linear Dynamics Model: The expected Gram matrix H∞ is defined by averaging H over random initializations and governs the linearized training dynamics.Its eigenvectors and eigenvalues determine convergence behavior in the reviewed model.
- 3.2 The Eigenvectors of H∞ for Uniform Data: For uniformly distributed training points on a hypersphere, H∞ forms a convolution matrix with a rotationally symmetric kernel.The hyperspherical convolution reduces to ordinary periodic convolution on S1 when the kernel depends on angular differences.
- 3.2 The Eigenvectors of H∞ for Uniform Data: Consequently, the eigenvectors of H∞ are Fourier series on S1 and spherical harmonics on higher-dimensional spheres.The proof interprets the matrix action as a discretization of convolution with the limiting kernel.
4 Harmonic Analysis of H∞
The harmonic analysis identifies spherical harmonics as the relevant eigenfunctions and shows that bias changes which frequencies a shallow network can represent and learn. Eigenvalues predict frequency-dependent convergence: roughly quadratic on S1 and roughly cubic on S2, consistent with experiments.
- Bias-free networks: Bias-free two-layer networks cannot represent odd frequencies k ≥3, which therefore lie in the kernel's null space and cannot be learned.Theorem 2 states that coefficients at odd frequencies k ≥3 are zero; the same null-space result extends to odd spherical harmonics in higher dimensions.
- Bias-free networks: A bias-free network can fit cos(3θ) training points using even frequencies, but its interpolation between points is poor.The network fits 51 sampled points perfectly while producing behavior off the training data that differs substantially from the target function.
- Convergence rates: Figure 6 measures convergence-time growth of O(k2.15), O(k1.93), O(k1.94), and O(k2.11) for bias-free shallow, biased shallow, deep, and deep residual networks on S1.Convergence is defined as reaching 5% fitting error; theoretical curves are rescaled to reflect gradient-step length.
- Convergence rates: Eigenvalues determine learning speed: for S1, even-frequency eigenvalues shrink as 1/k2, implying quadratically slower learning for high frequencies.The convergence-time derivation links iteration count to the inverse eigenvalue, yielding quadratic growth asymptotically for all frequencies once bias is included.
- Adding bias: With bias, the kernel passes all frequencies, odd frequencies leave the null space, and leading eigenvectors include both low even and odd frequencies.The biased eigenfunctions remain spherical harmonics under uniform hyperspherical data.
5 Discussion
The paper develops a quantitative account of frequency-dependent learning speed and finds that high-frequency functions are learned more slowly than low-frequency functions. It interprets gradient descent as frequency-based regularization, with experiments suggesting applicability beyond heavily overparameterized networks.
- 5 Discussion: High-frequency functions are learned much more slowly than low-frequency functions.The analysis provides a quantitative understanding of this frequency-dependent learning speed.
- 5 Discussion: Experiments suggest that the frequency-dependent learning behavior applies to real neural networks, although the analysis concerns heavily overparameterized networks.The empirical evidence extends beyond the exact theoretical setting without removing that scope distinction.
- 5 Discussion: Gradient descent first fits low-frequency components before fitting high-frequency components.This ordering is presented as frequency-based regularization.
- 5 Discussion: Early stopping may regularize by selecting smoother functions.The paper connects this smoothing to reduced high-frequency noise while preserving more of the signal.
A Cross entropy loss
The paper tests convergence under cross entropy using binary classification targets generated from thresholded cosine functions. A deep residual network exhibits a near-quadratic convergence rate as target frequency increases.
- A Cross entropy loss: Binary classification targets are constructed by thresholding cos(kθ) on the 1D circle for each integer k > 0.Points with |cos(kθ)| ≤ 2/3 are omitted; the remaining points receive classes 1 or -1 according to the threshold.
- A Cross entropy loss: The cross entropy experiment shows a near-quadratic convergence rate with target frequency.The leading exponent is estimated as O(K^2.34).
- A Cross entropy loss: A deep residual network with 10 hidden layers, bias, m = 256, η = 0.05, and n = 1001 is evaluated.The figure specifies uniform bias initialization and the weight initialization used in [13].
B Eigenvalues of H∞with d > 1
The paper computes higher-dimensional eigenvalues by applying the Funk-Hecke theorem to the convolution kernel and spherical harmonics.
- B Eigenvalues of H∞with d > 1: The Funk-Hecke theorem converts the relevant kernel–harmonic integrals into eigenvalue calculations.The derivation collects useful formulas, formulates the integrals, and computes the resulting expressions.
B.1 Useful integrals and equations
This section assembles integral identities and kernel decompositions needed to compute harmonic-transform coefficients for bias-free and biased networks on the hypersphere.
- B.1 Useful integrals and equations: The derivation uses integration by parts to evaluate cosine and sine integrals, with parity determining which terms vanish.Several displayed identities distinguish even and odd n.
- B.1 Useful integrals and equations: For uniformly sampled hyperspherical inputs, the kernel is expressed through the angle between input vectors and t = cos θ.Because θ ranges from 0 to π, the absolute value in the kernel expression can be removed.
- B.1 Useful integrals and equations: Adding bias changes the kernel by introducing a new bias component alongside the original kernel terms.The integrals are divided into four parts, with K_b = K_3 + K_4 and the complete kernel formed from all four terms.
- B.1 Useful integrals and equations: The notation a_k^d, b_k^d, and c_k^d records harmonic-transform coefficients for the original, bias, and complete kernels.These coefficients index frequency k and dimension d as used in the subsequent eigenvalue calculations.
B.3 Application of the Funk Hecke theorem
The section applies the Funk–Hecke theorem by projecting the kernel onto spherical harmonics, reducing the calculation to zonal harmonics and their transforms. It then introduces Gegenbauer polynomials and assumes even dimension to simplify subsequent coefficient calculations.
- The eigenvalues of H∞ are obtained by projecting the kernel onto spherical harmonics through a transform.Because the kernel contains only zonal-harmonic components, only zonal harmonics need to be considered.
- Only zonal harmonics are required because the kernel is written with components exclusively in the zonal harmonic.
- The k-th order harmonic transform is computed for inputs on the sphere S^d, where the input dimension is d + 1.
- The calculation uses the Gegenbauer polynomial Pk,d(t) and Euler’s gamma function in the transform expressions.
- For simplification, the subsequent coefficient calculations assume that d is even and treat cases with and without bias separately.The DC component is computed first, followed by coefficients for k > 0.
B.4 Calculating the coefficients: no bias
The no-bias coefficient calculation combines harmonic contributions from the kernel components K1, K2, K3, and K4. The resulting expression shows that, except for k = 1, coefficients for odd frequencies vanish.
- Kernel-component calculations: The no-bias analysis computes coefficients by separately expanding K1, K2, K3, and K4 before combining their contributions.The harmonic coefficients of Kb = K3 + K4 are also denoted separately during the calculation.
- Parity dependence: The component calculations use parity-dependent expressions for even and odd k.
- Odd-frequency result: Except for k = 1, the coefficients for odd frequencies in equation (58) vanish.This result is stated as proven in Theorem 3.
- Final expression: The final coefficients are obtained after substituting the value of k from equation (58) into the assembled expressions.