Modern machine learning relies on vastly overparameterized models trained on high-dimensional data, where generalization and training dynamics display sharp transitions and strong inductive biases. This thesis develops tractable frameworks, analyzed with tools from statistical physics, to characterize when feature learning emerges, how it depends on data structure and architecture, and how it enables generalization from finite samples.
A first set of results focuses on multi-index target functions, a canonical model of feature learning where labels depend nonlinearly on a low-dimensional subspace of the input. We derive sharp sample-complexity conditions for weak recovery by first-order methods and identify computational transitions. Interactions between directions lead to a hierarchical ``grand staircase'' phenomenon, in which features can be learned sequentially when coupled to easier ones. We then analyze multi-pass gradient descent, showing that batch reuse can overcome single-pass limitations and enable efficient finite-time learning for broad classes of target functions.
A second theme connects feature learning and scaling laws in overparameterized two-layer models to matrix compressed sensing. We derive sharp asymptotics for optimal polynomial-time algorithms and show that regularized empirical risk minimization in quadratic two-layer networks maps to nuclear-norm-penalized matrix sensing. This correspondence predicts training and test errors, identifies interpolation and recovery thresholds, and yields a phase diagram of scaling regimes mirroring empirical neural scaling phenomena. It also highlights rank-constrained structure, induced by regularization, as a key mechanism shaping generalization.
We finally extend this framework to sequential data and attention mechanisms. Finite-rank multi-layer attention networks map to multi-index models on sequences, yielding asymptotically exact generalization formulas, sharp sample-complexity thresholds, AMP predictions, and sequential learning across layers. To move beyond finite-rank attention while preserving solvability, we generalize the matrix-sensing perspective to a full-width tied attention layer, characterizing its learning curves, thresholds, learned spectra, and regularization-induced inductive biases.
Overall, the thesis provides solvable benchmarks and sharp theoretical predictions linking optimization, architecture, and generalization in modern high-dimensional learning.
