# A Strongly Quasiconvex PAC-Bayesian Bound

arXiv: https://arxiv.org/abs/1608.05610 · HTML: https://mlsanity.com/paper/1608.05610/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2016.

## Built on by (most cited first, 30 of 54)

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Bayesian Model Selection, the Marginal Likelihood, and Generalization](https://mlsanity.com/paper/2202.11678/) (2022)
- [Enhancing Adversarial Training with Second-Order Statistics of Weights](https://mlsanity.com/paper/2203.06020/) (2022)
- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [Sparse is Enough in Fine-tuning Pre-trained Large Language Models](https://mlsanity.com/paper/2312.11875/) (2023)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)
- [Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory](https://mlsanity.com/paper/2310.04935/) (2023)
- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)
- [Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote](https://mlsanity.com/paper/2106.13624/) (2021)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior](https://mlsanity.com/paper/2102.03748/) (2021)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [Wide stochastic networks: Gaussian limit and PAC-Bayesian training](https://mlsanity.com/paper/2106.09798/) (2021)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [FedHB: Hierarchical Bayesian Federated Learning](https://mlsanity.com/paper/2305.04979/) (2023)
- [Conditionally Gaussian PAC-Bayes](https://mlsanity.com/paper/2110.11886/) (2021)
- [On Margins and Generalisation for Voting Classifiers](https://mlsanity.com/paper/2206.04607/) (2022)
- [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022)
- [Weight Expansion: A New Perspective on Dropout and Generalization](https://mlsanity.com/paper/2201.09209/) (2022)
- [Improving Generalization of Complex Models under Unbounded Loss Using PAC-Bayes Bounds](https://mlsanity.com/paper/2305.19243/) (2023)
- [Task-Driven Detection of Distribution Shifts with Statistical Guarantees for Robot Learning](https://mlsanity.com/paper/2106.13703/) (2021)
- [PAC-Bayesian Learning of Optimization Algorithms](https://mlsanity.com/paper/2210.11113/) (2022)
- [Recursive PAC-Bayes: A Frequentist Approach to Sequential Prior Updates with No Information Loss](https://mlsanity.com/paper/2405.14681/) (2024)

## Abstract (arXiv)

We propose a new PAC-Bayesian bound and a way of constructing a hypothesis space, so that the bound is convex in the posterior distribution and also convex in a trade-off parameter between empirical performance of the posterior distribution and its complexity. The complexity is measured by the Kullback-Leibler divergence to a prior. We derive an alternating procedure for minimizing the bound. We show that the bound can be rewritten as a one-dimensional function of the trade-off parameter and provide sufficient conditions under which the function has a single global minimum. When the conditions are satisfied the alternating minimization is guaranteed to converge to the global minimum of the bound. We provide experimental results demonstrating that rigorous minimization of the bound is competitive with cross-validation in tuning the trade-off between complexity and empirical performance. In all our experiments the trade-off turned to be quasiconvex even when the sufficient conditions were violated.