Generalization of Hamiltonian algorithms

Many machine learning algorithms use stochastic methods, but understanding how well these algorithms generalize to unseen data remains a challenge. A key problem is bounding the generalization gap, or the difference between an algorithm’s performance on training data versus new data. This paper tackles this challenge by focusing on a class of stochastic algorithms that produce probability distributions according to a Hamiltonian function. Existing bounds often come with unnecessary limitations or include extra terms that are difficult to interpret.

This work introduces a novel, more efficient method for bounding the generalization gap of algorithms with Hamiltonian dynamics. The core idea involves bounding the log-moment generating function, which quantifies the algorithm’s output distribution’s concentration around its mean. The paper offers new theoretical guarantees for Gibbs sampling, randomized stable algorithms, and extends to sub-Gaussian hypotheses. These improved bounds are simpler and remove superfluous logarithmic factors and terms, significantly advancing the field.