Generalization in Deep Learning: Two Theoretical View Points

Deep learning has transformed computer vision, natural language processing, and speech recognition. However, two critical questions remain obscure: (1) why do deep neural networks generalize better than shallow networks; and (2) does it always hold that a deeper network leads to better performance? In this thesis, we derive an upper bound on the expected generalization error for neural networks based on information theory. This upper bound shows that as the number of layers increases in the network, the expected generalization error will decrease exponentially to zero. Layers with strict information loss, such as the convolutional or pooling layers, reduce the generalization error for the whole network; this answers the first question. However, algorithms with zero expected generalization error does not imply a small test error. This is because the expected training error is large when the information for fitting the data is lost as the number of layers increases. This suggests that the claim ``the deeper the better'' is conditioned on a small training error. We also show that deep learning satisfies a weak notion of stability and the sample complexity of deep neural networks will decrease as the number of layers increases. The information-theoretic view on the generalization of learning algorithms requires the sub-gaussian assumption on the loss function, which does not hold when the loss function is unbounded and/or the distributions of the instance and hypothesis are heavy-tailed. To overcome this issue, we further derive upper bounds on the generalization error of learning algorithms based on their algorithmic transport cost: the expected Wasserstein distance between the output hypothesis and the output hypothesis conditioned on an input example. The bounds provide a novel approach to study the generalization of learning algorithms from an optimal transport view and impose less constraints on the loss function, such as sub-gaussian or bounded. We further provide several upper bounds on the algorithmic transport cost in terms of total variation distance, relative entropy (or KL-divergence), and VC dimension, thus further bridging optimal transport theory and information theory with statistical learning theory. Moreover, we also study different conditions for loss functions under which the generalization error of a learning algorithm can be upper bounded by different probability metrics between distributions relating to the output hypothesis and/or the input data. Under our established framework, we also analyze the generalization error in deep learning. Our two analyses of generalization error in deep learning mainly exploit the hierarchical structure in DNNs and the contraction property of f-divergence and mutual information, which may be of independent interest in analyzing other learning models with hierarchical structure