From Generalisation Error to Transportation-cost Inequalities and Back
This work provides a theoretical framework for generalization error bounds in machine learning, offering incremental advances by extending existing results to more general divergence measures.
The paper connects bounding expected generalization error with transportation-cost inequalities, generalizing beyond Kullback-Leibler divergences and sub-Gaussian measures to show equivalence between functional and measure inequalities, recovering standard bounds and introducing new ones involving arbitrary divergences.
In this work, we connect the problem of bounding the expected generalisation error with transportation-cost inequalities. Exposing the underlying pattern behind both approaches we are able to generalise them and go beyond Kullback-Leibler Divergences/Mutual Information and sub-Gaussian measures. In particular, we are able to provide a result showing the equivalence between two families of inequalities: one involving functionals and one involving measures. This result generalises the one proposed by Bobkov and Götze that connects transportation-cost inequalities with concentration of measure. Moreover, it allows us to recover all standard generalisation error bounds involving mutual information and to introduce new, more general bounds, that involve arbitrary divergence measures.