Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions
This addresses the computational efficiency challenge in training neural networks on high-dimensional data for researchers and practitioners, though it is incremental as it builds on existing multi-index models.
The paper tackles the problem of how neural networks learn low-dimensional structures from high-dimensional noisy data, showing that repeating data twice during SGD training allows learning of multi-index functions with at most O(d log d) steps, surpassing previous limitations like the Information and Leap exponents.
Neural networks can identify low-dimensional relevant structures within high-dimensional noisy data, yet our mathematical understanding of how they do so remains scarce. Here, we investigate the training dynamics of two-layer shallow neural networks trained with gradient-based algorithms, and discuss how they learn pertinent features in multi-index models, that is target functions with low-dimensional relevant directions. In the high-dimensional regime, where the input dimension $d$ diverges, we show that a simple modification of the idealized single-pass gradient descent training scenario, where data can now be repeated or iterated upon twice, drastically improves its computational efficiency. In particular, it surpasses the limitations previously believed to be dictated by the Information and Leap exponents associated with the target function to be learned. Our results highlight the ability of networks to learn relevant structures from data alone without any pre-processing. More precisely, we show that (almost) all directions are learned with at most $O(d \log d)$ steps. Among the exceptions is a set of hard functions that includes sparse parities. In the presence of coupling between directions, however, these can be learned sequentially through a hierarchical mechanism that generalizes the notion of staircase functions. Our results are proven by a rigorous study of the evolution of the relevant statistics for high-dimensional dynamics.