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

Ryan Singh, Miguel De Llanza, Christopher L. BuckleyarXiv 2026 · arXiv

TL;DR

This paper argues that overparameterization in neural networks isn't just about having enough "room" to fit a final solution, but about providing the functional diversity needed to discover that solution in the first place. By introducing a measure called "effective width," the authors prove that the resources required to find a hidden pattern (like sparse parity) can be polynomially larger than the resources needed to represent it once learned.

What Problem Does This Paper Address?

We know that modern neural networks are "overparameterized"—they have far more parameters than data points. While this helps them generalize, it raises a fundamental question: Why do we need so much complexity for relatively simple tasks?

Previous "information-plane" studies noticed that networks often become very complex during the middle of training before simplifying toward the end. This paper tackles the "why" behind this transient complexity. Specifically, it explores the gap between representation (can the network express the target function?) and discovery (can the gradient descent algorithm actually "see" the target to start learning it?). The authors focus on "hard" problems like sparse parity, where the target is simple to describe but notoriously difficult for standard optimizers to find.

Methods

The authors move away from counting raw neurons and instead define Effective Width ($R$). This is a functional measure based on Kolmogorov $n$-widths, which quantifies the number of linear "degrees of freedom" or distinct functional directions a representation provides.

Key components of their approach include:

  • An Oracle Model: They analyze a two-layer network where the optimizer receives noisy gradient information through a "statistical query" oracle.
  • Forward-Backward Transfer: A core technical contribution is a proof showing that the geometric complexity of a network's forward activities (used for prediction) directly constrains the complexity of its gradient queries (used for learning).
  • Variation Spaces: They use Barron-type variation norms to measure complexity, which allows them to relate the "diversity" of neurons to the precision of the gradient signal.
  • Phase Diagram Analysis: They map out a "frontier" relating effective width, sample size (precision), and optimization time.

Datasets

As a theoretical work, the paper primarily uses synthetic benchmarks designed to test the limits of feature learning:

  • $k$-sparse Parity: The task is to identify which $k$ bits out of $D$ total input bits determine the output (a classic "needle in a haystack" problem for gradients).
  • Rademacher Inputs: Inputs are vectors of $\pm 1$, which is standard for analyzing parity problems.

Key Insights and Ideas

  • Discovery is Harder than Inference: A $k$-sparse parity can be represented by just $O(k)$ neurons once you know which bits matter. However, to find those bits using noisy gradients, you might need an effective width that scales polynomially with the total dimension $D$ (specifically $D^{k-1}$).
  • The Width-Precision-Time Trade-off: There is a fundamental frontier. You can find a target with a "narrow" representation if you have extremely high precision (many samples/long time), or you can find it faster/with less precision if you have a "wide," diverse representation.
  • Effective Width as a Resource: Overparameterization creates "distinct functional directions." If your network is too narrow, different potential targets look identical to the optimizer (they all produce a zero gradient), leaving the learner "blind."
  • The $R \approx N$ Crossover: The authors identify a phase transition where the effective width $R$ meets the number of samples $N$. Below this point, the network must "struggle" to interpolate, often requiring very large weights (norm inflation). Above it, the representation is rich enough to fit the data easily.
The effective-width–sample phase diagram for k-sparse parity. The blue curve represents the "task-visibility frontier"—below this, the target is invisible to the optimizer. The red dashed line marks the crossover where the network becomes wide enough to interpolate the data without forcing large readout norms.

Key Results

  • Theoretical Bound: For $k$-sparse parity, the critical initial effective width required for discovery is $\widetilde{\Theta}_k(D^{k-1}\tau^2)$, where $\tau$ is the noise level.
  • Empirical Validation: Experiments with $k=3$ parity across various dimensions ($D=5$ to $11$) showed that the "cumulative effective width" needed to reach a target accuracy collapsed onto a single curve when normalized by $D^2$, exactly as their theory predicted.
  • U-Shaped Test Frontier: They found that while increasing width always speeds up training (fitting the data), it only helps testing (generalization) up to a certain point. Beyond the $R \approx N$ crossover, more width accelerates fitting but doesn't necessarily improve the discovery of the true underlying feature.

Limitations and Future Work

  • Shallow Networks: The current analysis is limited to two-layer (shallow) networks. Extending this to deep networks would require tracking how information is transformed across multiple layers.
  • Task Specificity: While the "Width-Transfer" framework is general, the tightest bounds rely on the specific symmetries of parity problems. Future work could explore other "hard" features like Gaussian single-index models.
  • Adversarial vs. Stochastic Gradients: The model uses a coordinate-wise adversarial oracle. Real-world SGD might behave differently, potentially exploiting "lucky" samples in ways this worst-case analysis doesn't capture.
  • Estimation: Calculating Kolmogorov $n$-widths for arbitrary data distributions remains a difficult computational challenge.

Summary updated

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.
BibTeX
@misc{singh2026representation,
  author = {Ryan Singh and Miguel De Llanza and Christopher L. Buckley},
  title = {{Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time}},
  year = {2026},
  eprint = {2610.39027},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39027},
}
Figure