A framework for overparameterized learning
An explanation for the success of deep neural networks is a central question
in theoretical machine learning. According to classical statistical learning,
the overparameterized nature of such models should imply a failure to
generalize. Many argue that good empirical performance is due to the implicit
regularization of first order optimization methods. In particular, the
Polyak-{\L}ojasiewicz condition leads to gradient descent finding a global
optimum that is close to initialization. In this work, we propose a framework
consisting of a prototype learning problem, which is general enough to cover
many popular problems and even the cases of infinitely wide neural networks and
infinite data. We then perform an analysis from the perspective of the
Polyak-{\L}ojasiewicz condition. We obtain theoretical results of independent
interest, concerning gradient descent on a composition $(f \circ F): G \to
\mathbb{R}$ of functions $F: G \to H$ and $f: H \to \mathbb{R}$ with $G, H$
being Hilbert spaces. Building on these results, we determine the properties
that have to be satisfied by the components of the prototype problem for
gradient descent to find a global optimum that is close to initialization. We
then demonstrate that supervised learning, variational autoencoders and
training with gradient penalty can be translated to the prototype problem.
Finally, we lay out a number of directions for future research.