  A leading hypothesis for the surprising generalization of neural networks is
that the dynamics of gradient descent bias the model towards simple solutions,
by searching through the solution space in an incremental order of complexity.
We formally define the notion of incremental learning dynamics and derive the
conditions on depth and initialization for which this phenomenon arises in deep
linear models. Our main theoretical contribution is a dynamical depth
separation result, proving that while shallow models can exhibit incremental
learning dynamics, they require the initialization to be exponentially small
for these dynamics to present themselves. However, once the model becomes
deeper, the dependence becomes polynomial and incremental learning can arise in
more natural settings. We complement our theoretical findings by experimenting
with deep matrix sensing, quadratic neural networks and with binary
classification using diagonal and convolutional linear networks, showing all of
these models exhibit incremental learning.
