mlsanityData to 14 Oct 2026

On Margins and Derandomisation in PAC-Bayes

arXiv 2107.03955 ↗First posted 8 Jul 2021cs.LG math.ST stat.THcited by 19

Not on the map. Why?

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.

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

31 of 78 references.

References · 31

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  3. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,417
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  5. 2017Exploring Generalization in Deep Learningcited by 600
  6. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  7. 2019Fantastic Generalization Measures and Where to Find Themcited by 513
  8. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  9. 2018Stronger generalization bounds for deep nets via a compression approachcited by 307
  10. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  11. 2020Being Bayesian, Even Just a Bit, Fixes Overconfidence in ReLU Networkscited by 231
  12. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 224
19 more
  1. 2017Generalization in Deep Learningcited by 146
  2. 2019A Primer on PAC-Bayesian Learningcited by 132
  3. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 126
  4. 2020Tighter risk certificates for neural networkscited by 112
  5. 2020Bayesian Deep Learning via Subnetwork Inferencecited by 87
  6. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  7. 2020In Search of Robust Measures of Generalizationcited by 79
  8. 2020On the role of data in PAC-Bayes boundscited by 64
  9. 2019Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resiliencecited by 51
  10. 2020NeurIPS 2020 Competition: Predicting Generalization in Deep Learningcited by 41
  11. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  12. 2020Generalization bounds for deep learningcited by 38
  13. 2020Second Order PAC-Bayesian Bounds for the Weighted Majority Votecited by 34
  14. 2020Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Boundcited by 32
  15. 2020Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networkscited by 29
  16. 2018PAC-Bayes bounds for stable algorithms with instance-dependent priorscited by 21
  17. 2020Near-Tight Margin-Based Generalization Bounds for Support Vector Machinescited by 19
  18. 2021Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Boundcited by 16
  19. 2020De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictorscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 7; 2023: 5; 2024: 0; 2025: 1; 2026: 3.

19 papers.

Sort:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  2. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  3. 2022PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingalescited by 24
  4. 2022Non-Vacuous Generalisation Bounds for Shallow Neural Networkscited by 22
  5. 2022On PAC-Bayesian reconstruction guarantees for VAEscited by 20
  6. 2023PAC-Bayesian Generalization Bounds for Adversarial Generative Modelscited by 13
  7. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 12
  8. 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
  9. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  10. 2022On Margins and Generalisation for Voting Classifierscited by 7
  11. 2023Comparing Comparators in Generalization Boundscited by 5
  12. 2022Controlling Multiple Errors Simultaneously with a PAC-Bayes Boundcited by 3
7 more
  1. 2026A PAC-Bayesian approach to generalization for quantum modelscited by 2
  2. 2021Kernel Interpolation as a Bayes Point Machinecited by 1
  3. 2021PACMAN: PAC-style bounds accounting for the Mismatch between Accuracy and Negative log-losscited by 1
  4. 2025Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?cited by 1
  5. 2026PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoderscited by 1
  6. 2022Streaming PAC-Bayes Gaussian process regression with a performance guarantee for online decision makingcited by 0
  7. 2026Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancingcited by 0