REVIEW 5 cited by
Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
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.
Forward citations
Cited by 5 Pith papers
-
Approximate Message Passing with Random Initialization for Phase Retrieval
Randomly initialized Bayes-optimal AMP provably achieves the weak-recovery threshold δ=1/2 and arbitrarily accurate recovery for δ>1.13 in proportional-regime noiseless phase retrieval.
-
Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions
A random shift of Gaussian inputs forces the first Hermite coefficient of any non-linear target to be large, yielding near-linear sample complexity independent of the target's information exponent, and a similar resul...
-
On The Concurrence of Layer-wise Preconditioning Methods and Provable Feature Learning
For two feature-learning models with anisotropic inputs, KFAC-style layer-wise preconditioning provably recovers features better than SGD and matches ridge regression in the single-index case.
-
On the Mechanisms of Weak-to-Strong Generalization: A Theoretical Perspective
In high-dimensional linear and one-step feature-learning models, a regularized student can outperform its teacher by fixing under-regularization, using better regularization structure, or retaining pretrained hard features.
-
Optimal Spectral Transitions in High-Dimensional Multi-Index Models
Two linearized message-passing spectral estimators achieve the optimal weak-recovery threshold in Gaussian multi-index models, with a sharp BBP-like spectral phase transition at the critical sample complexity.
Discussion (0). Continue with ORCID to comment.