Research map / Learning theory and algorithms / Kernels and regression theory

A Unified Recipe for Deriving (Time-Uniform) PAC-Bayes Bounds

NeurIPS 2024 · Learning theory and algorithms › Kernels and regression theory · approach: PAC-Bayes bounds · 6 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a unified recipe (nonnegative supermartingales or reverse submartingales, method of mixtures, Donsker-Varadhan change of measure, Ville's inequality) for deriving time-uniform PAC-Bayes bounds that hold at all stopping times, recovering many classical bounds and deriving novel ones.

Problem

Classical PAC-Bayes bounds are fixed-time and become invalid when the sample size is chosen adaptively (stopping times), and there is no unified recipe for deriving PAC-Bayes bounds.

Approach

Combine supermartingale or reverse-submartingale constructions with mixtures over posteriors, the Donsker-Varadhan (convex duality) change of measure, and Ville's inequality to obtain a master theorem giving time-uniform PAC-Bayes bounds for any process upper bounded by such a martingale-type process, with no distributional assumptions for supermartingale cases.

Key results

• Recovers time-uniform versions of McAllester, Catoni, Seeger, and Maurer PAC-Bayes bounds; supermartingale-based time-uniform bounds lose no tightness versus fixed-time counterparts.
• Gaussian-mixture bound for subGaussian losses is tighter than McAllester's fixed-time bound by a factor of sqrt(2) when tuned to a fixed n.
• Reverse-submartingale bounds lose at most a log log t factor relative to fixed-time bounds for all t.

Surprising findings

• Supermartingale-based time-uniform PAC-Bayes bounds require no explicit distributional assumptions on the data.

Limitations

• Reverse-submartingale bounds are looser (log log t factor) and require stationary losses and exchangeable data.
• Time-uniformity gives little benefit when the empirical risk is only computable at a fixed time, as for some U-statistic bounds.
• Open problem on bounds under only a bounded p-th moment with 1<p<=2.

Experimental setup

Baselines: McAllester bound Catoni bound Seeger bound Maurer bound

Builds on: Ville's inequality Donsker-Varadhan formula sub-psi processes PAC-Bayes bounds of McAllester, Catoni, Seeger, Maurer

Closest papers by meaning

• Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms (NeurIPS 2023 · similarity 0.87)
• PAC-Bayes Learning Bounds for Sample-Dependent Priors (NeurIPS 2020 · similarity 0.87)
• PAC-Bayes-Chernoff bounds for unbounded losses (NeurIPS 2024 · similarity 0.86)
• Block-Sample MAC-Bayes Generalization Bounds (ICLR 2026 · similarity 0.86)
• Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound (NeurIPS 2024 · similarity 0.83)
• Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss (NeurIPS 2024 · similarity 0.83)