Benefits of Additive Noise in Composing Classes of Functions with Applications to Neural Networks

Abstract

Let F and H be two (compatible) classes of functions. We observe that even when both F and H have small capacities as measured by their uniform covering numbers, the capacity of the composition class H o F={h o f| f in F, h in H} can become prohibitively large or even unbounded. To this end, in this thesis we provide a framework for controlling the capacity of composition and extend our results to bound the capacity of neural networks. Composition of Random Classes: We show that adding a small amount of Gaussian noise to the output of cF before composing it with H can effectively control the capacity of H o F, offering a general recipe for modular design. To prove our results, we define new notions of uniform covering number of random functions with respect to the total variation and Wasserstein distances. The bounds for composition then come naturally through the use of data processing inequality. Capacity of Neural Networks: We instantiate our results for the case of sigmoid neural networks. We start by finding a bound for the single-layer noisy neural network by estimating input distributions with mixtures of Gaussians and covering them. Next, we use our composition theorems to propose a novel bound for the covering number of a multi-layer network. This bound does not require Lipschitz assumption and works for networks with potentially large weights. Empirical Investigation of Generalization Bounds: We include preliminary empirical results on MNIST dataset to compare several covering number bounds based on their suggested generalization bounds. To compare these bounds, we propose a new metric (NVAC) that measures the minimum number of samples required to make the bound non-vacuous. The empirical results indicate that the amount of noise required to improve over existing uniform bounds can be numerically negligible. The source codes are available at https://github.com/fathollahpour/composition_noise