Generalization of the Gibbs algorithm with high probability at low temperatures
This work addresses the theoretical understanding of generalization in machine learning, particularly for stochastic algorithms at low temperatures, but it is incremental as it builds on existing Gibbs algorithm analysis.
The paper provides a theoretical bound on the generalization error of the Gibbs algorithm, extending known results to low temperatures where error depends on the data-dependent loss landscape, and shows that generalization improves with the prior volume of hypotheses having similar or smaller empirical error, supporting the benefit of flat minima.
The paper gives a bound on the generalization error of the Gibbs algorithm, which recovers known data-independent bounds for the high temperature range and extends to the low-temperature range, where generalization depends critically on the data-dependent loss-landscape. It is shown, that with high probability the generalization error of a single hypothesis drawn from the Gibbs posterior decreases with the total prior volume of all hypotheses with similar or smaller empirical error. This gives theoretical support to the belief in the benefit of flat minima. The zero temperature limit is discussed and the bound is extended to a class of similar stochastic algorithms.