Metraipolis › archive › dc_b20da3aa4344
Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time — arXiv:2610.39027
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.39027
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T06:13:02.948Z
- SHA-256 of the archived text
32bbf092640e0459379e5e5e335799ca9e5990080e6c2d535a2f8f104d9a08b2- Stable URL of this page
https://metraipolis.com/documento/dc_b20da3aa4344
How to cite
Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time — arXiv:2610.39027 — arXiv (en), https://arxiv.org/abs/2610.39027 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b20da3aa4344 (Metraipolis archive dc_b20da3aa4344, sha256 32bbf092640e0459379e5e5e335799ca9e5990080e6c2d535a2f8f104d9a08b2)
BibTeX
@misc{dcb20da3aa4344,
title = {Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time — arXiv:2610.39027},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.39027},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b20da3aa4344; sha256 32bbf092640e0459379e5e5e335799ca9e5990080e6c2d535a2f8f104d9a08b2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39027. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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{\Theta}_k\left( D^{k-1}\tau^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.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2610.39027 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T06:07:08.691Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).