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

PAC-Bayes-Chernoff bounds for unbounded losses

NeurIPS 2024 · Learning theory and algorithms › Kernels and regression theory · approach: PAC-Bayes bounds · 1 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.

Introduces an oracle PAC-Bayes bound for unbounded losses built on Cramér-Chernoff tail control of the Cramér transform, enabling exact optimization of the free parameter λ and model-dependent CGF bounds that yield posteriors beyond the Gibbs posterior.

Problem

PAC-Bayes generalization bounds for unbounded losses typically depend on a free parameter λ that must be tuned via union-bound grids, and bounded-CGF assumptions are uniform across models, discarding model-specific concentration information.

Approach

Averages the Cramér transform of the generalization gap over the posterior and controls its survival function uniformly over models, yielding an oracle bound whose λ is optimized exactly at a log(n) cost; the model-dependent CGF bound then gives posteriors that are not Gibbs.

Key results

• Main theorem gives PAC-Bayes bound with infimum over λ in [0,b) at a log(n) penalty, exact optimization without union bounds.
• Recovers Langford-Seeger-type bound for 0-1 loss (kl bound with (KL+log(n/δ))/(n-1)).
• Empirically, models with smaller log-loss variance, weight norm, or input-gradient norm have smaller estimated CGFs for InceptionV3 on CIFAR10.

Measured effects reported in the paper

Surprising findings

• The posterior minimizing the bound is not the standard Gibbs posterior; CGF-dependent terms shape the optimal posterior.

Limitations

• Assumes light-tailed (sub-exponential) losses for two-sided bounds; the bound only controls the right tail of the generalization gap.
• The log(n) penalty may be suboptimal in some cases.
• Log-Sobolev assumption (Assumption 2) is only empirically supported for InceptionV3, not verified for all models.

Experimental setup

Datasets: CIFAR10

Benchmarks: CIFAR10

Metrics: estimated CGF log-loss variance of log-loss expected input-gradient norm

Baselines: Langford-Seeger bound bounded CGF PAC-Bayes bound (union-bound over λ grid) sub-Gaussian PAC-Bayes bounds

Builds on: PAC-Bayes bounds (McAllester, Langford-Seeger) Donsker-Varadhan change of measure Cramér-Chernoff bound bounded CGF PAC-Bayes bounds

Closest papers by meaning

• Block-Sample MAC-Bayes Generalization Bounds (ICLR 2026 · similarity 0.90)
• PAC-Bayes under potentially heavy tails (NeurIPS 2019 · similarity 0.90)
• PAC-Bayes Learning Bounds for Sample-Dependent Priors (NeurIPS 2020 · similarity 0.89)
• PAC-Bayesian Theory Meets Bayesian Inference (NeurIPS 2016 · similarity 0.89)
• Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound (NeurIPS 2024 · similarity 0.87)
• A Unified Recipe for Deriving (Time-Uniform) PAC-Bayes Bounds (NeurIPS 2024 · similarity 0.86)