arXiv preprint ·
Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
What Can Firms Do in the Face of Model Distillation?
When the Same Prompt Gives Different Answers (and the Same Answer Isn't Always Right): A Taxonomy of Failure Mechanisms, Testing, and Mitigation Strategies for LLM-Assisted Evidence Synthesis Read-and-Evaluate Tasks
Predicting What Answer Engines Cite: Open Decision Models, Rerankers and a Distilled 4B Student on Ten Engines under Controlled Retrieval
Certified Access: Test-Time Compute on Conservative Physics-Structured AI Memory
Jailbreak Connectivity: Towards Diverse, Transferable, and Universal Multimodal Large Language Model Jailbreak
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.