Generalization of Gibbs and Langevin Monte Carlo Algorithms in the Interpolation Regime

This paper provides data-dependent bounds on the expected error of the Gibbs algorithm in the overparameterized interpolation regime, where low training errors are also obtained for impossible data, such as random labels in classification. The results show that generalization in the low-temperature regime is already signaled by small training errors in the noisier high-temperature regime. The bounds are stable under approximation with Langevin Monte Carlo algorithms. The analysis motivates the design of an algorithm to compute bounds, which on the MNIST, CIFAR-10 and SVHN datasets yield nontrivial, close predictions on the test error for true labeled data, while maintaining a correct upper bound on the test error for random labels.

Modern AI systems can sometimes fit their training examples perfectly, even when the answers are random. This makes it hard to tell, from training accuracy alone, whether a system has truly learned useful patterns or merely memorized noise. Our work studies this problem for a family of randomized learning methods that favor models with low training error, similar to how physical systems favor low-energy states. We show that the key signal is not only what happens at the noiseless version of training, when the model fits the data very well, but also what happens earlier in a noisier version of the learning process. When real labels are present, models already make fewer training mistakes in this noisier regime; when labels are random, they do not. Using this difference, we derive mathematical guarantees that estimate, from the training data alone, how well the learned model should perform on new, unseen examples. We also show that the guarantees remain meaningful when the idealized method is approximated by practical sampling algorithms. In experiments on standard image datasets, our approach gives close upper estimates of test error for correctly labeled data, while still correctly warning that random-label data will not generalize.