A Fourier perspective on the learning dynamics of neural networks: from sample complexities to mechanistic insights

Neural networks trained with gradient-based methods exhibit a strong simplicity bias: they learn simpler statistical features of their data before moving to more complex features. Previous analyses of this phenomenon have largely focused on settings with (quasi-)isotropic inputs. In this work, we study the simplicity bias from a Fourier perspective, which allows us to include two key features of natural images in the analysis: approximate translation-invariance and power-law spectra. We first show experimentally that simple neural networks trained on image classification tasks first rely on amplitude information $-$ related to pair-wise correlations between pixels $-$ before exploiting phase information, which encodes edges and higher-order correlations. In view of this, we introduce a synthetic data model for translation-invariant inputs that allows precise control over amplitudes and phases while remaining tractable. We rigorously establish that for isotropic and high-dimensional inputs, classification based on phase information alone is a genuinely hard task: online stochastic gradient descent (SGD) cannot distinguish the structured inputs from noise within $n \ll N^3$ steps, but needs at least $n \gg N^3 \log^2{N}$ steps. In contrast, we show both experimentally and theoretically that power-law spectra can dramatically accelerate the speed of learning phase information, even if the spectra do not help with classification. Simulations with two-layer networks trained on textures and with deep convolutional networks on ImageNet and CIFAR100 confirm this non-trivial interaction between amplitudes and phases, providing mechanistic insights into how deep neural networks can learn natural image distributions efficiently.

How do neural networks learn to classify images? It is well known that neural networks are able to exploit complex patterns learnt directly from their training data, but the mechanism behind this procedure is not yet fully explained. In this paper, we investigate feature learning by modeling the input data in Fourier space, a particularly convenient framework for representing natural images. We ask: how hard is it to learn from Fourier amplitudes and from Fourier phases, respectively? More precisely: do the amplitudes have a role in accessing the information encoded in the phases? We answer this question in the affirmative, by demonstrating theoretically that power-law decaying amplitudes $-$ which are typical of natural images $-$ speed up learning phase information with stochastic gradient descent. Instead, we prove that, in absence of information carried by the amplitudes, learning from the phases requires a number of samples which is prohibitive for practical purposes in high dimensions. We corroborate our findings in experiments with real images. Our results improve our understanding of how data structures affect the way neural networks extract increasingly complex patterns from their data.