Chapter 1: Introduction

A great resource for introducing the field of Probably Approximately Correct (PAC) learning theory is given in (Alquier, 2023). It details the progression of results in the field and motivates the various research avenues. PAC learning theory is a general framework for studying learning algorithms, and my aim here is to illustrate how this theory is being contextualized within machine learning, with a specific focus on neural networks. With this report, I want to introduce the theory and detail some applications, as well as provide some recent extensions. The main product of PAC learning theory is bounds on the performance of the output of learning algorithms, termed PAC bounds. This report will not provide an exhaustive list of the various PAC bounds being applied to neural networks. I will instead provide some well-known results in the literature and how some of them manifest in applications. For a comprehensive introduction to the field of PAC, the reader is recommended to refer to (Alquier, 2023). Nevertheless, this report will be mostly self-contained, with proofs for the major results and elaboration on the implementations of PAC theory.

Contents

• Chapter 2 - PAC Bounds
• Introducing PAC Bounds
• Notation
• PAC Bounds
• Occam Bounds
• Expected Risk Minimization
• Compression
• Establishing the Notion of Compression
• Compression of a Linear Classifier
• Compression of a Fully Connected Network
• Chapter 3 - Empirical PAC-Bayes Bounds
• Introduction to PAC-Bayes Theory
• Bayesian Machine Learning
• Notations and Definitions
• PAC-Bayes Bounds
• Optimizing PAC-Bayes Bounds via SGD
• Chapter 4 - Oracle PAC-Bayes Bounds
• Theory of Oracle PAC-Bayes Bounds
• Oracle PAC-Bayes Bounds in Expectation
• Oracle PAC-Bayes Bounds in Probability
• Bernstein's Assumption
• Data Driven PAC-Bayes Bounds
• Implementing Data-Dependent Priors
• Chapter 5 - Extensions of PAC-Bayes Bounds
• Disintegrated PAC-Bayes Bounds
• Application to Neural Network Classifiers
• PAC-Bayes Compression Bounds
• Chapter 6 - Appendix
• Extensions to Convolutional Neural Networks
• Current State of the Art PAC-Bayes Bounds
• The PAC-Bayes Foundations
• Finding Random Subspaces
• Quantization and Training
• Optimization
• Rademacher Complexity
• References

Downloads

• Simple version where proofs are omitted.
• Detailed version where proofs are included.
• A digression into PAC bounds for Reinforcement Learning (RL).
• A digression into PAC bounds for Graph Neural Networks (GNNs).