On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregation
This provides theoretical tools for validating Gibbs algorithms, which is important for researchers in statistical learning theory, though it appears to be an incremental theoretical contribution.
The paper analytically characterizes how Gibbs algorithms depend on training data, deriving closed-form sensitivity expressions for performance differences with alternative algorithms. It develops explicit relationships between training and test errors for different datasets, introduces new generalization metrics, and establishes connections between Jeffrey's divergence and error measures for specific dataset sizes and algorithm parameters.
The dependence on training data of the Gibbs algorithm (GA) is analytically characterized. By adopting the expected empirical risk as the performance metric, the sensitivity of the GA is obtained in closed form. In this case, sensitivity is the performance difference with respect to an arbitrary alternative algorithm. This description enables the development of explicit expressions involving the training errors and test errors of GAs trained with different datasets. Using these tools, dataset aggregation is studied and different figures of merit to evaluate the generalization capabilities of GAs are introduced. For particular sizes of such datasets and parameters of the GAs, a connection between Jeffrey's divergence, training and test errors is established.