Generalization Bounds with Arbitrary Complexity Measures

Paul Viallard, Rémi Emonet, Amaury Habrard, Emilie Morvant, Valentina ZantedeschiICLR 2023 · OpenReview

Abstract

In statistical learning theory, generalization bounds usually involve a complexity measure that is constrained by the considered theoretical framework. This limits the scope of such analysis, as in practical algorithms, other forms of regularization are used. Indeed, the empirical work of Jiang et al. (2019) shows that (I) common complexity measures (such as the VC-dimension) do not correlate with the generalization gap and that (ii) there exist arbitrary complexity measures that are better correlated with the generalization gap, but come without generalization guarantees. In this paper, we bridge the gap between this line of empirical works and generalization bounds of statistical learning theory. To do so, we leverage the framework of disintegrated PAC-Bayes bounds to derive a generalization bound that involves an arbitrary complexity measure. Our bound stands in probability jointly over the hypotheses and the learning sample, which allows us to improve the correlation between generalization gap and complexity, as the latter can be set to fit both the hypothesis class and the task.
BibTeX
@inproceedings{viallard2023generalization,
  author = {Paul Viallard and Rémi Emonet and Amaury Habrard and Emilie Morvant and Valentina Zantedeschi},
  title = {{Generalization Bounds with Arbitrary Complexity Measures}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=WhwtdGkbaDr},
}

Loading related content...

Figure