Generalization in Learning: Eyring Formula and Predator-prey Model
Authors: S. V. Kozyrev, I. A. Lopatin, Alexander Pechen
Organizations: Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia · Ivannikov Institute for System Programming of the Russian Academy of Sciences, Moscow, Russia
In this work, generalization in machine learning is investigated using a predator-prey model. We overview biological and chemical interpretation of the stochastic gradient Langevin dynamics and generative adversarial network. For a particular example of recovering an unknown function by a polynomial of fixed degree from a set of noisy data, the predator-prey model provides better approximation compared to the gradient descent method. Further, thermodynamical arguments, in particular Eyring formula, are used to explain grokking (delayed generalization) phenomenon in machine learning.
Figures & tables
Figure 1: Sampling examples of training and test datasets for the function f(x)=sin(πx) .
Degree d
1
3
5
7
Loss on train
0.171
0.072
0.027
0.026
Loss on test
0.400
0.033
0.161
0.159
Deviation from f
0.227
0.007
0.059
0.080
Table 1: Learning results for different degrees of polynomials. The last line of the table shows the MSE of the model predictions for the hidden function on a uniform grid on [−1,1] with 1000 points.
Figure 2: Solid lines show approximations to the function f (dashed lines) found by gradient descent after 106 iterations for d=1,3,5,7 in ( 9 ). The train points are marked by ’x’.
Figure 3: Simulation results for: (a) loss on train; (b) loss on test; (c) distance between the predator and the prey; (d) distance between the current state uk and the averaged state uk for the prey.
Figure 4: Deviation of the model from the hidden function vs number of iterations.
A machine learning method is proposed using two agents (representing two coupled replicas of the model parameters) that simulate the biological behavior of a predator and a prey. In this method, the two agents interact with each other via a pair of potentials that simulate the dynamics when the predator chases the prey while the prey runs away from the predator - to perform an optimization on the landscape. This method allows, for optimization landscapes with narrow ravines with gentle slope or even flat bottoms, to avoid optimization getting stuck in a ravine. For some examples of grokking (i.e., delayed generalization) problems we show that this method allows for achieving up to a hundred times faster learning in gradient evaluations and up to 60 times in the wall-clock time compared to the standard learning procedure.
I. A. Lopatin, S. V. Kozyrev, A. N. Pechen
Steklov Mathematical Institute of Russian Academy of Sciences, Gubkina str. 8, 119991 Moscow, Russia · Ivannikov Institute for System Programming of the Russian Academy of Sciences, Moscow, 109004 Russia
Understanding generalization remains a central challenge in machine learning because it requires jointly considering data, architecture, and training dynamics. In this paper, we develop a theoretical framework that characterizes how these factors jointly shape generalization performance throughout training. More precisely, we study a broad class of neural networks trained under the ℓ2 loss by gradient descent (GD) with weight decay, and prove the convergence of GD to a neighbourhood of the global minimizers of the empirical loss. By partitioning the space based on the input data, we then decompose the population error into data error, optimization error, and prediction variation error, and bound them separately. In particular, for the prediction variation error, which measures the oscillations of the learned function, we propose (local) approximate homogeneity and derive explicit cellwise and layerwise bounds for its evolution along the training trajectory. These bounds yield two important implications: a necessary condition of improved generalization explains differences in layerwise generalization behavior; a sufficient condition describes delayed generalization and provides a theoretical characterization of grokking.
Yuqing Wang, Ioannis G. Kevrekidis, Mikhail Belkin
Johns Hopkins University · University of California San Diego
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.