Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes

Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss

NeurIPS 2024 · Probabilistic and scientific modeling › Uncertainty and Gaussian processes · approach: Nonparametric and PAC-Bayes Bayesian learning · 0 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.

Proposes Recursive PAC-Bayes, a loss decomposition enabling sequential prior updates in PAC-Bayes without losing confidence information, plus a discrete split-kl inequality, and shows tighter bounds on MNIST and Fashion MNIST.

Problem

Data-informed PAC-Bayes priors waste the data used to build the prior and discard the prior's confidence information, so sequential prior updates give no benefit to the final bound.

Approach

Decompose the posterior loss as an excess loss relative to a downscaled prior loss plus the downscaled prior loss, and bound the prior loss recursively, so every chunk of data is used both to build the next prior and to evaluate bounds; also generalizes split-kl to discrete random variables via superposition of Bernoulli variables.

Key results

• On MNIST, RPB with T=8 reaches a bound of .158 and test 0-1 error of .097, versus .408 bound and .371 test error for data-informed priors.
• On Fashion MNIST, RPB with T=8 reaches a bound of .242 and test error .192, versus .440 bound and .413 test error for data-informed priors.
• Bounds tighten monotonically as recursion depth T grows from 2 to 8 on both datasets.

Measured effects reported in the paper

Surprising findings

• With T=2, RPB has a looser bound than Informed + Excess Loss on MNIST (.321 vs .192) even though its test error is lower.

Limitations

• Only zero-one loss and two small image datasets evaluated
• Optimization uses relaxed PAC-Bayes-classic bound and cross-entropy surrogates, and the gamma_t is fixed at 1/2 in experiments
• Bounds depend on a geometric data split chosen by hand

Experimental setup

Datasets: MNIST Fashion MNIST

Benchmarks: MNIST Fashion MNIST

Metrics: 0-1 test error PAC-Bayes bound train 0-1 loss

Baselines: Uninformed PAC-Bayes Data-informed priors Data-informed priors + excess loss

Builds on: PAC-Bayes-kl inequality PAC-Bayes-split-kl inequality data-dependent priors PAC-Bayes excess loss bounds

Closest papers by meaning

• PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees (ICML 2021 · similarity 0.89)
• More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithms (ICML 2024 · similarity 0.89)
• Bridging the Gap Between Practice and PAC-Bayes Theory in Few-Shot Meta-Learning (NeurIPS 2021 · similarity 0.89)
• PAC-Bayesian Theory Meets Bayesian Inference (NeurIPS 2016 · similarity 0.88)
• Learning via Surrogate PAC-Bayes (NeurIPS 2024 · similarity 0.88)
• Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound (NeurIPS 2024 · similarity 0.87)