  Understanding the fundamental principles behind the massive success of neural
networks is one of the most important open questions in deep learning. However,
due to the highly complex nature of the problem, progress has been relatively
slow. In this note, through the lens of infinite-width networks, a.k.a. neural
kernels, we present one such principle resulting from hierarchical localities.
It is well-known that the eigenstructure of infinite-width multilayer
perceptrons (MLPs) depends solely on the concept frequency, which measures the
order of interactions. We show that the topologies from deep convolutional
networks (CNNs) restructure the associated eigenspaces into finer subspaces. In
addition to frequency, the new structure also depends on the concept space,
which measures the spatial distance among nonlinear interaction terms. The
resulting fine-grained eigenstructure dramatically improves the network's
learnability, empowering them to simultaneously model a much richer class of
interactions, including Long-Range-Low-Frequency interactions,
Short-Range-High-Frequency interactions, and various interpolations and
extrapolations in-between. Additionally, model scaling can improve the
resolutions of interpolations and extrapolations and, therefore, the network's
learnability. Finally, we prove a sharp characterization of the generalization
error for infinite-width CNNs of any depth in the high-dimensional setting. Two
corollaries follow: (1) infinite-width deep CNNs can break the curse of
dimensionality without losing their expressivity, and (2) scaling improves
performance in both the finite and infinite data regimes.
