Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time

Ryan Singh; Miguel De Llanza; Christopher L. Buckley

cs.LGOct 28, 2026

Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time

Authors: Ryan Singh, Miguel De Llanza, Christopher L. Buckley

Organizations: Department of Engineering and Informatics, University of Sussex

Abstract

What computational role does overparameterisation play during learning? Information-plane analyses suggest that neural networks can traverse representations substantially more complex than those required by their final predictors. We explore when this transient complexity serves a computational purpose by comparing the representation complexity needed for prediction with that needed to make an unknown target statistically visible through gradient feedback. We introduce an oracle model of neural network learning and use Kolmogorov $n$ -widths to quantify effective representation complexity. Our main technical result transfers complexity bounds from the forward representation to the corresponding gradient-query features. Combined with statistical-query lower bounds, this gives a task-agnostic lower bound on the initial effective width required for target-dependent gradient information to become detectable. For $k$ -sparse parity in $D$ dimensions, a known target admits an $O(k)$ -width representation, while the general bound already implies a polynomial separation between representation and discovery. We then exploit parity's invariance under coordinatewise sign reflections to identify a sharper unsigned effective width, which removes sign distinctions invisible to the parity information channel. At a transfer-compatible measurement resolution, its critical scale is $\widetildeΘ_k\left( D^{k-1}τ^2 \right)$ , up to logarithmic factors. Thus, the representation resources required to discover a predictor can substantially exceed those required to represent it once learned. Interpreting precision through accumulation over fresh samples yields a corresponding width-time frontier. Experiments support the predicted dimension dependence and examine how optimisation and generalisation depart from this idealised frontier.

Figures & tables

Panel of Figure 1 — Figure 1: Effective-width–sample phase diagram for $k$ -sparse parity. The blue curve is the task-visibility frontier $NR_{\mathrm{task}}(N)=\widetilde{\Theta}_{k}(D^{k-1})$ . Above the frontier the target is detectable. The dashed red line $R=N$ marks the crossover in fixed-feature behaviour. When $R<N$ , exact interpolation requires a large readout norm; effective-width control consequently obstructs premature fitting. When $R>N$ additional readout regularisation or implicit norm control may be required.

Panel of Figure 2 — Figure 2: Representation complexity during learning and its scaling with problem dimension. Results are shown for $k=3$ sparse parity across ambient dimensions $D\in\{5,7,9,11\}$ , with colours denoting different initialisation scales. (a) Instantaneous width $\widehat{R}_{t}$ can vary substantially across successful trajectories, with small initialisations exhibiting little to no transient increase. (b) The distribution of $\widehat{\mathcal{C}}_{\varepsilon}$ across hyperparameter settings as a function of $D$ , against the predicted $D^{2}$ scaling. (c) Normalising $\widehat{\mathcal{C}}_{\varepsilon}/D^{2}$ produces an approximate collapse across the tested dimensions.

Panel of Figure 3 — Figure 3: Width–time frontiers for $k=3$ , $D=10$ parity across initialisation scales (colour) and weight-decay values (marker). (a) Accuracy plotted against cumulative effective-width expenditure. (b) The training-time frontier remains close to the predicted inverse lower envelope and is comparatively insensitive to weight decay. (c) The test-time frontier departs upward beyond a characteristic effective width, resulting in a U-shaped lower envelope. Runs with stronger weight decay remain closest to the frontier, while the growing gap $T_{0.1}^{\mathrm{test}}-T_{0.1}^{\mathrm{train}}$ indicates delayed generalisation.

Overparameterized Neural Network

See all 16 papers

Oct 18, 2026

A Distribution-Free Separation Between Learned and Fixed Features

The success of neural networks is largely attributed to their ability to learn useful representations from training data. However, known results that prove a computational advantage of learned features over fixed ones are restricted to specific input distributions. We settle the COLT open question of Feldman, Kamath, and Srebro (2026) by showing that this advantage can persist in the distribution-free setting. We construct a family of hypothesis classes that can be efficiently learned by a natural gradient-based algorithm on a two-layer ReLU network, but cannot be represented by linear predictors over any fixed feature map with polynomial dimension (and runtime). Specifically, for any sufficiently small error and any sufficiently large runtime budget R (depending on the error), there exists a hypothesis class that the neural network learns under any input distribution to the desired expected classification error in time at most R, while the dimension complexity (governing the dimension needed by linear predictors) is superpolynomial in R.

Daniel Barzilai

Weizmann Institute of Science

Two-Layer Neural Networks Statistical Learning Theory Representation Learning

Ask PDF

Oct 16, 2026

Mesoscopic learning dynamics of extensive-width neural networks

Understanding how stochastic gradient descent learns internal representations in wide neural networks trained on rich target functions is a central problem in machine learning. We study this question in two-layer neural networks learning target functions represented by networks of the same architecture, with arbitrary nonlinearity, and with network width and input dimension growing proportionally. In this regime, standard approaches for describing the learning dynamics require tracking a diverging number of overlaps, which measure correlations between learned and target features, leaving no obvious description in terms of a few order parameters. Here, we develop a mesoscopic description of learning by characterizing the distribution of overlaps. In the early stages of learning, we find that a Gaussian description of overlap statistics reduces the learning dynamics to a few collective variables that track learning of the target function's linear and quadratic components. We then estimate the timescale of specialization, when Gaussian closure breaks down and individual learned features begin to strongly correlate with specific target features. We find that specialization in extensive-rank networks is accelerated via a quadratic shielding mechanism, whereby learning the linear and quadratic components of the target function filters gradient fluctuations. We finally describe how the activation function determines the pattern of specialization and characterize the subsequent refinement of learned features. Together, these results show how collective learning gives way to individual feature discovery and clarify when learning in large neural networks admits a simple statistical description.

Shu Zhou, Jean Barbier, Sebastian Goldt

International School for Advanced Studies (SISSA) Via Bonomea 265, 34136 Trieste, Italy · The Abdus Salam International Centre for Theoretical Physics (ICTP) Strada Costiera 11, 34151 Trieste, Italy

Neural Network Training Dynamics Representation Learning Statistical Physics of Learning

Ask PDF

Mar 1, 2026

Scaling of learning time for high dimensional inputs

Representation learning from complex data typically involves models with a large number of parameters, which in turn require large amounts of data samples. In neural network models, model complexity grows with the number of inputs to each neuron, with a trade-off between model expressivity and learning time. A precise characterization of this trade-off would help explain the connectivity and learning times observed in artificial and biological networks. We present a theoretical analysis of how learning time depends on input dimensionality for a Hebbian learning model performing independent component analysis. Based on the geometry of high-dimensional spaces, we show that the learning dynamics reduce to a unidimensional problem, with learning times dependent only on initial conditions. For higher input dimensions, initial parameters have smaller learning gradients and larger learning times. We find that learning times have supralinear scaling, becoming quickly prohibitive for high input dimensions. These results reveal a fundamental limitation for learning in high dimensions and help elucidate how the optimal design of neural networks depends on data complexity. Our approach outlines a new framework for analyzing learning dynamics and model complexity in neural network models.

Carlos Stein Brito

NightCity Labs, Lisbon, Portugal

Neural Network Training Dynamics Scaling Laws Hebbian Learning Independent Component Analysis

Ask PDF

Abstract

Overparameterized Neural Network

Explore similar work

A Distribution-Free Separation Between Learned and Fixed Features

Mesoscopic learning dynamics of extensive-width neural networks

Scaling of learning time for high dimensional inputs