# A spectral-based analysis of the separation between two-layer neural networks and linear methods

arXiv: https://arxiv.org/abs/2108.04964 · HTML: https://mlsanity.com/paper/2108.04964/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 10 Aug 2021.

## Builds on (most cited first, 25 of 25)

- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/1702.03118/) (2017)
- [The Deep Ritz method: A deep learning-based numerical algorithm for solving variational problems](https://mlsanity.com/paper/1710.00211/) (2017)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [A Priori Estimates of the Population Risk for Two-layer Neural Networks](https://mlsanity.com/paper/1810.06397/) (2018)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [On the Computational Efficiency of Training Neural Networks](https://mlsanity.com/paper/1410.1141/) (2014)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Approximation spaces of deep neural networks](https://mlsanity.com/paper/1905.01208/) (2019)
- [Diverse Neural Network Learns True Target Functions](https://mlsanity.com/paper/1611.03131/) (2016)
- [Learning with SGD and Random Features](https://mlsanity.com/paper/1807.06343/) (2018)
- [Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks](https://mlsanity.com/paper/1607.01434/) (2016)
- [A Dynamical Central Limit Theorem for Shallow Neural Networks](https://mlsanity.com/paper/2008.09623/) (2020)
- [ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time](https://mlsanity.com/paper/1510.03528/) (2015)
- [When Hardness of Approximation Meets Hardness of Learning](https://mlsanity.com/paper/2008.08059/) (2020)
- [Sharp Lower Bounds on the Approximation Rate of Shallow Neural Networks](https://mlsanity.com/paper/2106.14997/) (2021)

## Built on by (most cited first, 7 of 7)

- [The alignment property of SGD noise and how it helps select flat minima: A stability analysis](https://mlsanity.com/paper/2207.02628/) (2022)
- [Sampling weights of deep neural networks](https://mlsanity.com/paper/2306.16830/) (2023)
- [Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks](https://mlsanity.com/paper/2404.18769/) (2024)
- [Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networks](https://mlsanity.com/paper/2212.13848/) (2022)
- [Analyzing the Role of Permutation Invariance in Linear Mode Connectivity](https://mlsanity.com/paper/2503.06001/) (2025)
- [The L^∞ Learnability of Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2306.02833/) (2023)
- [On the Intrinsic Dimensions of Data in Kernel Learning](https://mlsanity.com/paper/2601.16139/) (2026)

## Abstract (arXiv)

We propose a spectral-based approach to analyze how two-layer neural networks separate from linear methods in terms of approximating high-dimensional functions. We show that quantifying this separation can be reduced to estimating the Kolmogorov width of two-layer neural networks, and the latter can be further characterized by using the spectrum of an associated kernel. Different from previous work, our approach allows obtaining upper bounds, lower bounds, and identifying explicit hard functions in a united manner. We provide a systematic study of how the choice of activation functions affects the separation, in particular the dependence on the input dimension. Specifically, for nonsmooth activation functions, we extend known results to more activation functions with sharper bounds. As concrete examples, we prove that any single neuron can instantiate the separation between neural networks and random feature models. For smooth activation functions, one surprising finding is that the separation is negligible unless the norms of inner-layer weights are polynomially large with respect to the input dimension. By contrast, the separation for nonsmooth activation functions is independent of the norms of inner-layer weights.