Source-linked AI summary
Frequency Bias in Neural Networks for Input of Non-Uniform Density
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, Shira Kritchman
TL;DR
The paper investigates whether frequency bias persists for realistic, non-uniform training densities rather than only uniform data. Using shallow and deep ReLU NTK models, it combines analytic derivations with empirical evidence and finds density-dependent learning rates, with higher-frequency components learned faster in denser regions. These results extend frequency-bias analysis beyond uniform data while leaving higher-dimensional analytic derivations as a conjectural boundary.
Problem
Prior frequency-bias analyses largely assumed uniformly distributed training data, leaving its behavior under realistic non-uniform densities unclear.
Method
The paper analyzes ReLU NTK models for two-layer and deep fully connected networks using spectral decompositions, closed-form shallow-network results, and experiments.
Results
Learning speed depends on frequency and density: shallow models require O(κ^2/p*) iterations in one dimension, while deep-network evidence supports O(κ^d/p*) for frequency-κ harmonics.
Takeaways & Limitations
NTK frequency bias occurs under both uniform and non-uniform data, supporting its possible role in how over-parameterized networks avoid overfitting.
Takeaways & Limitations
Analytic higher-dimensional results are left for future work, with current claims there based on simulation experiments and conjecture.
Abstract
from arXiv · showhide
Recent works have partly attributed the generalization ability of over-parameterized neural networks to frequency bias -- networks trained with gradient descent on data drawn from a uniform distribution find a low frequency fit before high frequency ones. As realistic training sets are not drawn from a uniform distribution, we here use the Neural Tangent Kernel (NTK) model to explore the effect of variable density on training dynamics. Our results, which combine analytic and empirical observations, show that when learning a pure harmonic function of frequency $κ$, convergence at a point $\x \in \Sphere^{d-1}$ occurs in time $O(κ^d/p(\x))$ where $p(\x)$ denotes the local density at $\x$. Specifically, for data in $\Sphere^1$ we analytically derive the eigenfunctions of the kernel associated with the NTK for two-layer networks. We further prove convergence results for deep, fully connected networks with respect to the spectral decomposition of the NTK. Our empirical study highlights similarities and differences between deep and shallow networks in this model.
1. Introduction
The paper asks whether frequency bias persists when training data have non-uniform density, using NTK theory and experiments to study how density changes learning dynamics. It finds that low frequencies remain easier to learn, but learning speed also depends on local density and network depth.
- Gradient descent typically learns low-frequency components before high-frequency components, a behavior proposed to help explain generalization in over-parameterized networks.
- In locally constant-density regions, low frequencies are learned faster than high frequencies, while learning rates also increase linearly with density.
- For two-layer ReLU NTK models, eigenfunctions have higher local frequencies where training-data density is higher.
- O(κ^2/p*) iterations are required to learn a one-dimensional sine of frequency κ, while experiments suggest O(κ^d/p*) for spherical harmonics on S^(d−1).
- For deep fully connected networks, eigenvalue decay suggests frequency bias, pure frequency-κ harmonics take O(κ^d) iterations under uniform data, and non-uniform data suggests O(κ^d/p*) iterations.
- Low-frequency signals can be learned slowly in sparse regions, allowing high-frequency noise components in dense regions to be learned before early stopping.
2. Prior work
Prior work connected neural-network generalization and frequency bias to kernel dynamics, especially NTK analyses under uniform data. However, NTK models face criticisms about unrealistic width and whether their linear dynamics fully explain neural-network performance.
- NTK theory models infinitely wide neural networks and has been extended across two-layer, fully connected, residual, and convolutional architectures.
- NTK models have been criticized for requiring unrealistically wide networks, and their linear lazy-training dynamics may underperform common nonlinear networks.
- Earlier frequency-bias studies found that gradient descent fits low frequencies first and higher frequencies later, with NTK work deriving convergence rates for two-layer networks.
- Classical non-uniform kernel research mainly bounded differences between empirical and theoretical kernel matrices, while some work derived analytic eigenfunctions for polynomial kernels.
3. Preliminaries
The paper formulates ReLU NTK models for shallow and deep fully connected networks, specifies their parameterization and training setup, and relates learning dynamics to kernel eigensystems. Uniform-data kernels have spherical-harmonic eigenfunctions with frequency-dependent eigenvalues.
- The paper studies NTK models for fully connected neural networks with ReLU activations.
- The NTK is defined through expectations over random network initializations, with f(x,w) denoting network output and x_i, x_j denoting training points.
- The two-layer model includes first-layer weights and biases, with ReLU activation σ(x)=max(x,0); bias enables representation of odd-frequency harmonics beyond frequency 1.
- Deep fully connected networks use L+1>2 layers and omit bias because experiments indicate universality without it.
- Training samples are drawn independently from a distribution p(x) on the hypersphere, with theoretical derivations assuming piecewise-constant density and optimization by gradient descent.
- For two-layer analysis, only first-layer weights and biases are trained, while deep-network analysis trains all weights.
- Under uniform data, the NTK is a convolution on the hypersphere, its eigenfunctions are spherical harmonics, and eigenvalues decay as O(1/κ^d), yielding O(κ^d) iterations for pure harmonics.
- For deep networks, the NTK is expressed through a recursion involving covariance matrices and derivatives of the ReLU activation.
4. The eigenfunctions of NTK for two-layer networks for non-uniform distributions
For non-uniform data on the circle, the NTK eigenfunctions adapt their local frequencies to density, and the smallest density controls convergence for harmonic targets. The analysis derives these eigenfunctions for piecewise-constant densities and supports the predicted density-dependent rates empirically, with higher-dimensional results remaining conjectural.
- NTK eigen-system: The eigen-system of the finite kernel matrix approaches that of the density-weighted kernel operator as the number of training points grows.The operator has a non-symmetric polar kernel, which is symmetrized to establish real eigenvalues.
- Explicit expressions for the eigenfunctions: Eigenfunctions on each constant-density region are cosine functions whose frequencies are proportional to √p_j.Thus, local frequency increases with the density of the corresponding region.
- Explicit expressions for the eigenfunctions: Across decreasing eigenvalues, eigenfunction frequencies increase in every region while preserving ratios equal to ratios between corresponding density square roots.The same qualitative behavior appears for a continuous density in the empirical eigenvectors of H_p.
- Time to convergence: O(κ^2/p*) iterations suffice to learn a frequency-κ target on S1, up to logarithmic terms, where p* is the minimal density.The convergence bound accounts for possible correlations with eigenfunctions having smaller eigenvalues.
- Empirical validation: Experiments on S1 show runtime increasing in proportion to κ^2 and convergence occurring faster in denser regions in proportion to p(x).The experiment uses a two-layer network trained on sine targets under three constant-density regions.
- Higher dimension: For higher-dimensional spheres, simulations suggest convergence time scales as O(k^d/p*) and that eigenfunctions resemble density-modulated patches of spherical harmonics.Analytic expressions for non-uniform distributions in dimensions d > 2 are left for future work.
5. Deep networks
For deep fully connected networks, NTK eigenvectors govern gradient-descent convergence, while eigenvalues preserve frequency-dependent learning behavior across depths and data densities.
- Deep-network convergence: NTK eigenvectors characterize gradient-descent convergence for overparameterized fully connected networks of finite width.The result extends earlier convergence analysis from two-layer networks to deep networks.
- Spectral structure: For uniform data, the NTK decomposes over spherical harmonics, or Fourier series on S1, because its kernel depends on input inner products.The corresponding kernel matrix forms a convolution under the uniform distribution.
- Uniform-density rates: O(κ^2) in S1 and O(κ^3) in S2 are the asymptotic learning-time rates for frequency κ, regardless of network depth.The NTK eigenvalues decrease monotonically with frequency, indicating faster learning of lower frequencies.
- Non-uniform density: For non-uniform data, deep-network NTK eigenfunctions appear indistinguishable from those of two-layer networks, with eigenvalues differing from the uniform case by density-dependent scaling.The reported comparison concerns a depth-10 network and piecewise density settings.
6. Conclusion
The paper extends NTK frequency-bias results from uniform to non-uniform data and combines theoretical analysis with empirical comparisons across network depths. It finds density-dependent learning rates, persistent frequency bias, and distinct treatment of middle frequencies by deep and shallow networks.
- Conclusion: The paper’s main contribution is extending frequency-bias insights from uniformly distributed training data to more realistic non-uniform data.The analysis also extends results from shallow to deep fully connected networks.
- Conclusion: Training times for uniform data are compared with times predicted by the eigenvalues of the corresponding NTK model.The comparison covers target-frequency experiments in S1 and S2.
- Implications: NTK frequency bias may help explain why real neural networks avoid overfitting, including when training data have non-uniform density.The paper presents this as support for the possible importance of frequency bias in real networks.
- Quantified density effects: For piecewise constant data distributions, NTK eigenfunctions are piecewise harmonic, with local frequency increasing linearly with the square root of local data density.For 1D inputs, the resulting learning speed increases quadratically with frequency and decreases linearly with local density.
A. Eigenfunctions of NTK for a two layer-network for data drawn from a piecewise constant distribution
For piecewise-constant data density on S1, the two-layer NTK eigenfunctions are derived through differential equations and continuity constraints, with amplitudes varying across regions. Under structured density patterns, each frequency can yield paired eigenfunctions.
- Differential characterization: The NTK eigenfunctions satisfy an ordinary differential equation obtained by combining the kernel equations.The derivation differentiates the governing relation repeatedly and simplifies it under piecewise-constant density assumptions.
- Differential characterization: Assuming locally constant density, the eigenfunction equation simplifies because derivatives of p(x) vanish.This produces a lower-order relation involving f and its derivatives at x and x + π.
- Differential characterization: With π-periodic density and antisymmetry f(x + π) = −f(x), the equation reduces to a homogeneous differential equation solved by the proposed eigenfunctions.The paper later removes the periodicity assumption through preprocessing that preserves the function being learned.
- Amplitude structure: Eigenfunctions are continuous and differentiable across region boundaries, while their amplitudes are characterized through neighboring-region ratios.The analysis first bounds adjacent amplitude ratios and then extends those bounds across all regions.
- Amplitude structure: When density is piecewise constant, higher-density regions produce constrained amplitude transitions, yielding bounds on all eigenfunction amplitudes.The bounds are tight for equally sized regions containing integer numbers of cycles.
- Amplitude structure: For the Figure 13 distribution, frequencies satisfying mod(q, 3) = 0 produce two eigenfunctions of each frequency through integer-cycle and phase constructions.The two eigenfunctions form pairs sharing the same eigenvalue.
C. Local convergence rate as a function of frequency
The convergence analysis bounds learning a harmonic target by decomposing it over NTK eigenfunctions and controlling the number and size of relevant spectral components. For a piecewise-constant density, the iteration complexity scales quadratically with target frequency and inversely with minimum density, up to logarithmic factors.
- Setup and spectral truncation: The proof assumes a piecewise-constant distribution with a fixed number of equal-sized regions and minimum density p∗ > 0.Only a number of eigenfunctions linear in frequency and inversely linear in √p∗ need be considered for convergence.
- Setup and spectral truncation: The convergence proof controls the target’s projection onto eigenfunctions and truncates the spectral expansion after sufficiently many terms.The truncation is selected so the remaining tail contributes at most the prescribed error.
- Setup and spectral truncation: For a target g(x) = cos(kx), the basis functions have local frequency qij = qi√pj/Z in region Rj.The local frequency therefore varies with the density of the region.
- Convergence rate: ˜O(k^2/p∗) iterations suffice to achieve ∥g(x) − u(t)(x)∥ < δ, with logarithmic factors hidden.The result is stated for any δ > 0 under the piecewise-constant density model.
- Convergence rate: The proof derives the rate by combining bounds on the relevant eigenvalue, spectral tail, and gradient-descent contraction.The asymptotic argument focuses on sufficiently large k and uses the corresponding eigenvalue order.
D. Spectral convergence analysis for deep networks - proof of Theorem 2
For deep fully connected networks, the paper specifies the network and NTK objects used for spectral convergence analysis. The theorem framework relates training dynamics to the eigenvalues and eigenvectors of the limiting NTK under normalized-data assumptions.
- Network and training setup: The deep network uses trainable weight matrices W1, …, WL together with fixed input and output matrices A and B.The hidden layers use element-wise ReLU activation.
- Network and training setup: The model is trained by minimizing the ℓ2 loss over the network outputs.Diagonal activation-pattern matrices are associated with each input and layer.
- Spectral analysis: The analysis constructs finite-sample and limiting kernel matrices H and H∞ and studies their spectral decompositions.The eigenvectors and eigenvalues of H∞ determine the relevant spectral coordinates, with λ0 denoting its minimum eigenvalue.
- Spectral analysis: The deep-network convergence theorem is stated under parameter, accuracy, and probability conditions for the random initialization and gradient-descent procedure.The theorem is supported by bounds on the kernel dynamics around the limiting NTK.
D.2. Proof strategy
The proof strategy controls the deviation between finite-width training dynamics and limiting NTK dynamics, then applies spectral contraction and initialization bounds. Probability guarantees follow from concentration over the random initialization.
- Proof ingredients: The proof relies on an earlier theorem for deep networks together with an auxiliary lemma derived from its proof.These ingredients provide the finite-width control needed for the main convergence theorem.
- Assumptions: The theorem assumes normalized inputs separated by at least δ and bounded targets.These conditions are inherited from the cited deep-network result.
- Dynamic decomposition: The training-error recursion separates limiting-kernel contraction from a perturbation term involving H(t) − H∞ and an error sequence.The perturbation is bounded using operator norms and the current prediction error.
- Finite-width control: A separate lemma bounds ∥H(t) − H∞∥2, supplying the finite-width stability estimate used in the recursion.The proof also invokes a loss bound to control the remaining terms.
- Dynamic decomposition: The contraction factor is controlled by the minimum eigenvalue λ0, while initialization loss and kernel deviation receive separate bounds.These estimates are combined recursively to complete the convergence argument.
D.4. Supporting Lemmas
The supporting lemmas establish high-probability bounds controlling parameter movement, derivatives, activations, initialization, and NTK stability under the theorem’s assumptions. These bounds are combined to derive the convergence guarantee in Theorem 5.
- Proof strategy: The proof decomposes coefficient and error terms, applies triangle inequalities and earlier lemmas, and then sums the resulting bounds across layers and data points.The derivation repeatedly separates terms, bounds them individually, and combines them before substituting the selected learning rate and perturbation scale.
- Auxiliary bounds: Additional lemmas control gradient norms, network outputs, initialization magnitudes, kernel approximations, and perturbations of the kernel matrix.These results support the final stability and convergence bounds used in the theorem proof.
- Kernel stability: The derivation concludes by combining two bounds and obtaining a bound on kernel variation of the form ∥H(t) − H(0)∥ ≤ O(n^3 log^5/6 m).The kernel-stability estimate follows from bounds on individual kernel entries and auxiliary lemmas.
- Theorem 5: Theorem 5 states a high-probability gradient-descent guarantee under Gaussian initialization and a specified learning rate.The theorem is presented for ϵ ∈ (0, 1] and δ in the stated range, with assumptions on initialization and parameters.
- Weight and activation control: The supporting lemmas bound changes in weights and establish conditions under which diagonal activation-related matrices remain controlled.Lemma 4 bounds weight movement, while Lemmas 5–8 provide perturbation, diagonal-matrix, and initialization-dependent controls.
- Relation to prior results: The appendix notes that the theorem generalizes an earlier result from τ = 1 to τ ∈ (0, 1] by modifying m and η by a factor of 1/τ^2.A related cited result is also extended to the setting where the first and last layers are held fixed.
E. Experiment setup
The paper provides an experimental setup for all figures, without further setup details in the supplied passage.
- Experimental setup: The experimental setup is stated to apply to all figures in the paper.