Fast-rate PAC-Bayes generalization bounds via shifted rademacher processes
Research output: Contribution to journal › Conference article › Research › peer-review
The developments of Rademacher complexity and PAC-Bayesian theory have been largely independent. One exception is the PAC-Bayes theorem of Kakade, Sridharan, and Tewari [21], which is established via Rademacher complexity theory by viewing Gibbs classifiers as linear operators. The goal of this paper is to extend this bridge between Rademacher complexity and state-of-the-art PAC-Bayesian theory. We first demonstrate that one can match the fast rate of Catoni's PAC-Bayes bounds [8] using shifted Rademacher processes [27, 43, 44]. We then derive a new fast-rate PAC-Bayes bound in terms of the “flatness” of the empirical risk surface on which the posterior concentrates. Our analysis establishes a new framework for deriving fast-rate PAC-Bayes bounds and yields new insights on PAC-Bayesian theory.
Original language | English |
---|---|
Journal | Advances in Neural Information Processing Systems |
Volume | 32 |
ISSN | 1049-5258 |
Publication status | Published - 2019 |
Externally published | Yes |
Event | 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 - Vancouver, Canada Duration: 8 Dec 2019 → 14 Dec 2019 |
Conference
Conference | 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 |
---|---|
Country | Canada |
City | Vancouver |
Period | 08/12/2019 → 14/12/2019 |
Sponsor | Citadel, Doc.AI, et al., Lambda, Lyft, Microsoft Research |
Bibliographical note
Funding Information:
We would like to also thank Peter Bartlett, Gintare Karolina Dziugaite, Roger Grosse, Yasaman Mahdaviyeh, Zacharie Naulet, and Sasha Rakhlin for helpful discussions. In particular, the authors would like to thank Sasha Rakhlin for introducing us to the work of Kakade, Sridharan, and Tewari [21]. The work benefitted also from constructive feedback from anonymous referees. JY was supported by an Alexander Graham Bell Canada Graduate Scholarship (NSERC CGS D), Ontario Graduate Scholarship (OGS), and Queen Elizabeth II Graduate Scholarship in Science and Technology (QEII-GSST). SS was supported by a Borealis AI Global Fellowship Award, Connaught New Researcher Award, and Connaught Fellowship. DMR was supported by an NSERC Discovery Grant and Ontario Early Researcher Award.
Publisher Copyright:
© 2019 Neural information processing systems foundation. All rights reserved.
ID: 361431893