Learning high-dimensional targets by two-parameter models and gradient
  flow
Dmitry Yarotsky
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 such learnability can be ruled out for a large class of
elementary functions.