Fast-Rate Loss Bounds via Conditional Information Measures with Applications to Neural Networks

We present a framework to derive bounds on the test loss of randomized\nlearning algorithms for the case of bounded loss functions. Drawing from\nSteinke & Zakynthinou (2020), this framework leads to bounds that depend on the\nconditional information density between the the output hypothesis and the\nchoice of the training set, given a larger set of data samples from which the\ntraining set is formed. Furthermore, the bounds pertain to the average test\nloss as well as to its tail probability, both for the PAC-Bayesian and the\nsingle-draw settings. If the conditional information density is bounded\nuniformly in the size $n$ of the training set, our bounds decay as $1/n$. This\nis in contrast with the tail bounds involving conditional information measures\navailable in the literature, which have a less benign $1/\\sqrt{n}$ dependence.\nWe demonstrate the usefulness of our tail bounds by showing that they lead to\nnonvacuous estimates of the test loss achievable with some neural network\narchitectures trained on MNIST and Fashion-MNIST.\n