Timezone: »

Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processes
Jun Yang · Shengyang Sun · Daniel Roy

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #227

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 (2008), 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 (Catoni, 2007) using shifted Rademacher processes (Wegkamp, 2003; Lecué and Mitchell, 2012; Zhivotovskiy and Hanneke, 2018). 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.

Author Information

Jun Yang (University of Toronto)
Shengyang Sun (University of Toronto)
Dan Roy (Univ of Toronto & Vector)

More from the Same Authors