Generalization of Gibbs and Langevin Monte Carlo Algorithms in the Interpolation Regime
This work addresses generalization bounds for machine learning algorithms in the interpolation regime, offering insights for researchers in statistical learning, but it is incremental as it builds on existing Monte Carlo methods.
The paper tackles the generalization of Gibbs and Langevin Monte Carlo algorithms in the overparameterized interpolation regime, providing data-dependent bounds on test error that are stable under approximation and verified on MNIST and CIFAR-10 datasets.
The paper provides data-dependent bounds on the test 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 bounds are stable under approximation with Langevin Monte Carlo algorithms. Experiments on the MNIST and CIFAR-10 datasets verify that the bounds yield nontrivial predictions on true labeled data and correctly upper bound the test error for random labels. Our method indicates that generalization in the low-temperature, interpolation regime is already signaled by small training errors in the more classical high temperature regime.