The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms

In this paper, the method of gaps, a technique for deriving closed-form expressions in terms of information measures for the generalization error of supervised learning algorithms, is introduced.

This method relies on the notion of gaps, which characterize the variation of the expected empirical risk (when either the model or dataset is kept fixed) with respect to changes in the probability measure on the varying parameter.

This distinction results in two classes of gaps: algorithm-driven gaps (fixed dataset) and data-driven gaps (fixed model).

The method relies on two central observations: (i) the generalization error is the expectation of an algorithm-driven gap or a data-driven gap.

In the first case, the expectation is with respect to a measure on the datasets; in the second case, it is with respect to a measure on the models.

(ii) Both algorithm-driven gaps and data-driven gaps exhibit closed-form expressions in terms of relative entropies.

In particular, algorithm-driven gaps involve a Gibbs probability measure on the set of models, which represents a supervised Gibbs algorithm.

Alternatively, data-driven gaps involve a worst-case data-generating (WCDG) probability measure on the set of data points, which is also a Gibbs probability measure.

Interestingly, such Gibbs measures, which are exogenous to the analysis of generalization, place the supervised Gibbs algorithm and the WCDG probability measure as natural references for the analysis of supervised learning algorithms.

New exact expressions and all existing exact expressions for the generalization error of supervised learning algorithms can be obtained with the proposed method.

Such new expressions are intended as structural and conceptual characterizations, not computational shortcuts.

Finally, these expressions unveil strong connections among generalization, hypothesis testing, information measures, and Pythagorean identities.