Learnability of high-dimensional targets by two-parameter models and gradient flow
This addresses a fundamental theoretical problem in machine learning about the limits of model capacity and learnability, with implications for understanding overparameterization and optimization in neural networks.
The paper investigates whether models with fewer parameters than the target dimension can learn high-dimensional targets via gradient flow, proving that two-parameter models can achieve arbitrarily high success probability for specific distributions, but also that many targets remain non-learnable when parameters are insufficient.
We explore the theoretical possibility of learning $d$-dimensional targets with $W$-parameter models by gradient flow (GF) when $W<d$. Our main result shows that if the targets are described by a particular $d$-dimensional probability distribution, then there exist models with as few as two parameters that can learn the targets with arbitrarily high success probability. On the other hand, we show that for $W<d$ there is necessarily a large subset of GF-non-learnable targets. In particular, the set of learnable targets is not dense in $\mathbb R^d$, and any subset of $\mathbb R^d$ homeomorphic to the $W$-dimensional sphere contains non-learnable targets. Finally, we observe that the model in our main theorem on almost guaranteed two-parameter learning is constructed using a hierarchical procedure and as a result is not expressible by a single elementary function. We show that this limitation is essential in the sense that most models written in terms of elementary functions cannot achieve the learnability demonstrated in this theorem.