  Generalization analyses of deep learning typically assume that the training
converges to a fixed point. But, recent results indicate that in practice, the
weights of deep neural networks optimized with stochastic gradient descent
often oscillate indefinitely. To reduce this discrepancy between theory and
practice, this paper focuses on the generalization of neural networks whose
training dynamics do not necessarily converge to fixed points. Our main
contribution is to propose a notion of statistical algorithmic stability (SAS)
that extends classical algorithmic stability to non-convergent algorithms and
to study its connection to generalization. This ergodic-theoretic approach
leads to new insights when compared to the traditional optimization and
learning theory perspectives. We prove that the stability of the
time-asymptotic behavior of a learning algorithm relates to its generalization
and empirically demonstrate how loss dynamics can provide clues to
generalization performance. Our findings provide evidence that networks that
"train stably generalize better" even when the training continues indefinitely
and the weights do not converge.
