# On Margins and Derandomisation in PAC-Bayes

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 78 references that are in the map.
- First posted on arXiv 8 Jul 2021.

## Builds on (most cited first, 30 of 31)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Being Bayesian, Even Just a Bit, Fixes Overconfidence in ReLU Networks](https://mlsanity.com/paper/2002.10118/) (2020)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Bayesian Deep Learning via Subnetwork Inference](https://mlsanity.com/paper/2010.14689/) (2020)
- [Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors](https://mlsanity.com/paper/1712.09376/) (2017)
- [In Search of Robust Measures of Generalization](https://mlsanity.com/paper/2010.11924/) (2020)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience](https://mlsanity.com/paper/1905.13344/) (2019)
- [NeurIPS 2020 Competition: Predicting Generalization in Deep Learning](https://mlsanity.com/paper/2012.07976/) (2020)
- [Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks](https://mlsanity.com/paper/1905.10259/) (2019)
- [Generalization bounds for deep learning](https://mlsanity.com/paper/2012.04115/) (2020)
- [Second Order PAC-Bayesian Bounds for the Weighted Majority Vote](https://mlsanity.com/paper/2007.13532/) (2020)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020)
- [PAC-Bayes bounds for stable algorithms with instance-dependent priors](https://mlsanity.com/paper/1806.06827/) (2018)
- [Near-Tight Margin-Based Generalization Bounds for Support Vector Machines](https://mlsanity.com/paper/2006.02175/) (2020)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)

## Built on by (most cited first, 19 of 19)

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [PAC-Bayesian Generalization Bounds for Adversarial Generative Models](https://mlsanity.com/paper/2302.08942/) (2023)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Generalisation under gradient descent via deterministic PAC-Bayes](https://mlsanity.com/paper/2209.02525/) (2022)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [On Margins and Generalisation for Voting Classifiers](https://mlsanity.com/paper/2206.04607/) (2022)
- [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023)
- [Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound](https://mlsanity.com/paper/2202.05560/) (2022)
- [A PAC-Bayesian approach to generalization for quantum models](https://mlsanity.com/paper/2603.22964/) (2026)
- [Kernel Interpolation as a Bayes Point Machine](https://mlsanity.com/paper/2110.04274/) (2021)
- [PACMAN: PAC-style bounds accounting for the Mismatch between Accuracy and Negative log-loss](https://mlsanity.com/paper/2112.05547/) (2021)
- [Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?](https://mlsanity.com/paper/2509.26149/) (2025)
- [PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoders](https://mlsanity.com/paper/2609.05212/) (2026)
- [Streaming PAC-Bayes Gaussian process regression with a performance guarantee for online decision making](https://mlsanity.com/paper/2210.08486/) (2022)
- [Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancing](https://mlsanity.com/paper/2609.32271/) (2026)

## Abstract (arXiv)

We give a general recipe for derandomising PAC-Bayesian bounds using margins, with the critical ingredient being that our randomised predictions concentrate around some value. The tools we develop straightforwardly lead to margin bounds for various classifiers, including linear prediction -- a class that includes boosting and the support vector machine -- single-hidden-layer neural networks with an unusual (erf) activation function, and deep ReLU networks. Further, we extend to partially-derandomised predictors where only some of the randomness is removed, letting us extend bounds to cases where the concentration properties of our predictors are otherwise poor.