PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
| Autor: | Grünwald, P.D., Steinke, T., Zakynthinou, L., Belkin, M., Kpotufe, S. |
|---|---|
| Přispěvatelé: | Belkin, M., Kpotufe, S. |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Computer Science - Information Theory Information Theory (cs.IT) Generalization TheoryofComputation_GENERAL Machine Learning (stat.ML) condition Machine Learning (cs.LG) ComputingMethodologies_PATTERNRECOGNITION Statistics - Machine Learning Bernstein Compression scheme Conditional Mutual information PAC-Bayes Fast rates |
| Zdroj: | STARTPAGE=2217;ENDPAGE=2247;TITLE=None |
| Popis: | We give a novel, unified derivation of conditional PAC-Bayesian and mutual information (MI) generalization bounds. We derive conditional MI bounds as an instance, with special choice of prior, of conditional MAC-Bayesian (Mean Approximately Correct) bounds, itself derived from conditional PAC-Bayesian bounds, where `conditional' means that one can use priors conditioned on a joint training and ghost sample. This allows us to get nontrivial PAC-Bayes and MI-style bounds for general VC classes, something recently shown to be impossible with standard PAC-Bayesian/MI bounds. Second, it allows us to get faster rates of order $O \left(({\text{KL}}/n)^{\gamma}\right)$ for $\gamma > 1/2$ if a Bernstein condition holds and for exp-concave losses (with $\gamma=1$), which is impossible with both standard PAC-Bayes generalization and MI bounds. Our work extends the recent work by Steinke and Zakynthinou [2020] who handle MI with VC but neither PAC-Bayes nor fast rates, the recent work of Hellstr\"om and Durisi [2020] who extend the latter to the PAC-Bayes setting via a unifying exponential inequality, and Mhammedi et al. [2019] who initiated fast rate PAC-Bayes generalization error bounds but handle neither MI nor general VC classes. Comment: 24 pages, accepted for publication at COLT 2021 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|