TY - GEN

T1 - Fast-rate PAC-Bayes generalization bounds via shifted rademacher processes

AU - Yang, Jun

AU - Sun, Shengyang

AU - Roy, Daniel M.

N1 - 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.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85089185756&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85089185756

VL - 32

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

SN - 1049-5258

T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019

Y2 - 8 December 2019 through 14 December 2019

ER -