arXiv cs.AI· Ryan Singh, Miguel De Llanza, Christopher L. Buckley·· 14 小时前AI 评分31
学习轨迹中的表示复杂度：以宽度换精度与时间
Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time
AI 导读
研究用 Kolmogorov n-width 量化有效表示复杂度，提出 oracle 学习模型，证明发现目标所需的初始有效宽度可远超学会后表示该目标所需的宽度。对 D 维 k-sparse parity，已知目标存在 O(k) 宽度表示，而通用下界已给出表示与发现之间的多项式分离；在忽略符号的测量分辨率下，临界尺度为 Õ_k(D^{k-1}τ²)。实验支持预测的维度依赖关系。
正文 · 原文
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{\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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.39027 [cs.LG] |
| (or arXiv:2610.39027v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.39027 arXiv-issued DOI via DataCite |
Submission history
From: Ryan Singh [view email]
[v1]
Wed, 28 Oct 2026 23:01:16 UTC (422 KB)
来源：arXiv cs.AI · arxiv.org