Despite existing work on ensuring generalization of neural networks in terms of scale sensitive complexity measures, such as norms, margin and sharpness, these complexity measures do not offer an explanation of why neural networks generalize better with over-parametrization. In this work we suggest a novel complexity measure based on unit-wise capacities resulting in a tighter generalization bound for two layer ReLU networks. Our capacity bound correlates with the behavior of test error with increasing network sizes (within the range reported in the experiments), and could partly explain the improvement in generalization with over-parametrization. We further present a matching lower bound for the Rademacher complexity that improves over previous capacity lower bounds for neural networks. Deep neural networks have enjoyed great success in learning across a wide variety of tasks. They played a crucial role in the seminal work of Krizhevsky et al. (2012) , starting an arms race of training larger networks with more hidden units, in pursuit of better test performance (He et al., 2016) . In fact the networks used in practice are over-parametrized to the extent that they can easily fit random labels to the data (Zhang et al., 2017) . Even though they have such a high capacity, when trained with real labels they achieve smaller generalization error.Traditional wisdom in learning suggests that using models with increasing capacity will result in overfitting to the training data. Hence capacity of the models is generally controlled either by limiting the size of the model (number of parameters) or by adding an explicit regularization, to prevent from overfitting to the training data. Surprisingly, in the case of neural networks we notice that increasing the model size only helps in improving the generalization error, even when the networks are trained without any explicit regularization -weight decay or early stopping (Lawrence et al., 1998; Srivastava et al., 2014; Neyshabur et al., 2015c) . In particular, Neyshabur et al. (2015c) observed that training on models with increasing number of hidden units lead to decrease in the test error for image classification on MNIST and CIFAR-10. Similar empirical observations have been made over a wide range of architectural and hyper-parameter choices (Liang et al., 2017; Novak et al., 2018; Lee et al., 2018) . What explains this improvement in generalization with over-parametrization? What is the right measure of complexity of neural networks that captures this generalization phenomenon?Complexity measures that depend on the total number of parameters of the network, such as VC bounds, do not capture this behavior as they increase with the size of the network. Existing works suggested different norm, margin and sharpness based measures, to measure the capacity of neural networks, in an attempt to explain the generalization behavior observed in practice (Neyshabur et al., 2015b; Keskar et al., 2017; Dziugaite & Roy, 2017; Neyshabur et al., 2017; Bartlett et al., 2017; We observe that even when after network is large enough to completely fit the training data(reference line), the test error continues to decrease for larger networks. Middle panel: Training fully connected feedforward network with single hidden layer on CIFAR-10. We observe the same phenomena as the one observed in ResNet18 architecture. Right panel: Unit capacity captures the complexity of a hidden unit and unit impact captures the impact of a hidden unit on the output of the network, and are important factors in our capacity bound (Theorem 1). We observe empirically that both average unit capacity and average unit impact shrink with a rate faster than 1/ √ h where h is the number of hidden units. Please see Supplementary Section A for experiments settings. BID0 Golowich et al., 2018 ; BID0 . In particular, Bartlett et al. (2017) showed a margin based generalization bound that depends on the spectral norm and 1,2 norm of the layers of a network. However, as shown in Neyshabur et al. (2017) and in FIG6 , these complexity measures fail to explain why over-parametrization helps, and in fact increase with the size of the network. Dziugaite & Roy (2017) numerically evaluated a generalization bound based on PAC-Bayes. Their reported numerical generalization bounds also increase with the increasing network size. These existing complexity measures increase with the size of the network, even for two layer networks, as they depend on the number of hidden units either explicitly, or the norms in their measures implicitly depend on the number of hidden units for the networks used in practice (Neyshabur et al., 2017) In this paper we present a new capacity bound for neural networks that empirically decreases with the increasing number of hidden units, and could potentially explain the better generalization performance of larger networks. In particular, we focused on understanding the role of width in the generalization behavior of two layer networks. More generally, understanding the role of depth and the interplay between depth and width in controlling capacity of networks, remain interesting directions for future study. We also provided a matching lower bound for the capacity improving on the current lower bounds for neural networks. While these bounds are useful for relative comparison between networks of different size, their absolute values still remain larger than the number of training samples, and it is of interest to get bounds with numerically smaller values.In this paper we do not address the question of whether optimization algorithms converge to low complexity networks in the function class considered in this paper, or in general how does different hyper parameter choices affect the complexity of the recovered solutions. It is interesting to understand the implicit regularization effects of the optimization algorithms (Neyshabur et al., 2015a; Gunasekar et al., 2017; Soudry et al., 2018) for neural networks, which we leave for future work.
We suggest a generalization bound that could partly explain the improvement in generalization with over-parametrization.
{"src": "scitldr-AIC_train", "paper_id": "BygfghAcYX"}