On the Dynamics of Delayed Generalization in Linear Models

Abstract

Delayed generalization, where training accuracy becomes nearly perfect substantially before test accuracy, has often been studied in the context of the depth and compositional structure of deep networks. In this paper, we ask whether delayed generalization can occur in simpler settings. We show that it can arise in a linear model trained with gradient descent and an exponential-tail loss on linearly separable data. We characterize the finite-time hyperplane dynamics into three phases: a population phase, a support vector dominated unlearning phase and a generalization phase. The convergence of the residual beyond the maximum-margin direction is sufficient for the unlearning phase to begin. In the support vector dominated phase, we characterize the hyperplane dynamics. The time scale in these dynamics causes delayed generalization. We validate our theory through controlled experiments varying population and support-vector distributions, and further verify the predicted bias behavior in a deep model with a single output neuron on MNIST. Our results provide a unified characterization of the asymptotic and finite-time dynamics underlying delayed generalization in linear models.