2020

Frequency Bias in Neural Networks for Input of Non-Uniform Density

Basri, Ronen, Galun, Meirav, Geifman, Amnon et al.

Understand

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 $\kappa$, convergence at a point $\x \in \Sphere^{d-1}$ occurs in time $O(\kappa^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.

Built on

Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks
Original
Arora, S., Du, S. S., Hu, W., Li, Z., and Wang, R · 1901
Earlier work this paper cites.
Regularization , kernels and sigmoid netst
Canu, M. F. and Elisseef, A · 1999
Earlier work this paper cites.
The effect of the input density distribution on kernel-based classifiers
Williams, C. and Seeger, M · 2000
Earlier work this paper cites.
On the eigenspectrum of the gram matrix and the generalization error of kernel-pca
Shawe-Taylor, J., Williams, C. K., Cristianini, N., and Kandola, J · 2005
Earlier work this paper cites.
Eigen-analysis of nonlinear pca with polynomial kernels
Liang, Z. and Lee, Y · 2013
Earlier work this paper cites.
Breaking the curse of dimensionality with convex neural networks
Bach, F · 2017
Earlier work this paper cites.
Eigenvalue decay implies polynomial-time learnability for neural networks
Goel, S. and Klivans, A. R · 2017
Earlier work this paper cites.
Diverse neural network learns true target functions
Xie, B., Liang, Y., and Song, L · 2017
Earlier work this paper cites.

Similar

On the convergence rate of training recurrent neural networks
Allen-Zhu, Z., Li, Y., and Song, Z · 2018
Cited alongside, same era.
A spectral approach to generalization and optimization in neural networks
Farnia, F., Zhang, J., and Tse, D · 2018
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Jacot, A., Gabriel, F., and Hongler, C · 2018
Cited alongside, same era.
Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds
Vempala, S. S. and Wilmes, J · 2018
Cited alongside, same era.
A convergence theory for deep learning via over-parameterization
Allen-Zhu, Z., Li, Y., and Song, Z · 2019
Cited alongside, same era.
The convergence rate of neural networks for learned functions of different frequencies
Basri, R., Jacobs, D., Kasten, Y., and Kritchman, S · 2019
Cited alongside, same era.
On the inductive bias of neural tangent kernels
Bietti, A. and Mairal, J · 2019
Cited alongside, same era.
Towards understanding the spectral bias of deep learning, 2019
Cao, Y., Fang, Z., Wu, Y., Zhou, D.-X., and Gu, Q · 2019
Cited alongside, same era.
On exact computation with an infinitely wide neural net
Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R., and Wang, R
Cited in the paper.

Then

On lazy training in differentiable programming
Chizat, L., Oyallon, E., and Bach, F · 2019
Later among the works it cites.
Gradient descent provably optimizes over-parameterized neural networks
Du, S. S., Zhai, X., Poczos, B., and Singh, A · 2019
Later among the works it cites.
Dynamics of deep neural networks and neural tangent hierarchy
Original
Huang, J. and Yau, H.-T · 2019
Later among the works it cites.
Wide neural networks of any depth evolve as linear models under gradient descent
Lee, J., Xiao, L., Schoenholz, S., Bahri, Y., Novak, R., Sohl-Dickstein, J., and Pennington, J · 2019
Later among the works it cites.
Bayesian deep convolutional networks with many channels are gaussian processes
Novak, R., Xiao, L., Bahri, Y., Lee, J., Yang, G., Hron, J., Abolafia, D. A., Pennington, J., and Sohl-Dickstein, J · 2019
Later among the works it cites.
On the spectral bias of neural networks
Rahaman, N., Baratin, A., Arpit, D., Draxler, F., Lin, M., Hamprecht, F., Bengio, Y., and Courville, A · 2019
Later among the works it cites.
Kernel and deep regimes in overparametrized models
Original
Woodworth, B. E., Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N · 2019
Later among the works it cites.
Frequency principle: Fourier analysis sheds light on deep neural networks
Original
Xu, Z. J., Zhang, Y., Luo, T., Xiao, Y., and Ma, Z · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…