In the last few years, deep learning has been tremendously successful in many applications. However, our theoretical understanding of deep learning, and thus the ability of providing principled improvements, seems to lag behind. A theoretical puzzle concerns the ability of deep networks to predict well despite their intriguing apparent lack of generalization: their classification accuracy on the training set is not a proxy for their performance on a test set. How is it possible that training performance is independent of testing performance? Do indeed deep networks require a drastically new theory of generalization? Or are there measurements based on the training data that are predictive of the network performance on future data? Here we show that when performance is measured appropriately, the training performance is in fact predictive of expected performance, consistently with classical machine learning theory. Is it possible to decide the prediction performance of a deep network from its performance in training -as it is typically the case for shallower classifiers such as kernel machines and linear classifiers? Is there any relationship at all between training and test performances? Figure 1a shows that when the network has more parameters than the size of the training set -which is the standard regime for deep nets -the training classification error can be zero and is very different from the testing error. This intriguing lack of generalization was recently highlighted by the surprising and influential observation (Zhang et al. (2016) ) that the same network that predicts well on normally labeled data (CIFAR10), can fit randomly labeled images with zero classification error in training while its test classification error is of course at chance level, see Figure 1b . The riddle of large capacity and good predictive performance led to many papers, with a variety of claims ranging from "This situation poses a conceptual challenge to statistical learning theory as traditional measures of model complexity struggle to explain the generalization ability of large artificial neural networks... " Zhang et al. (2016) , to various hypotheses about the role of flat minima Keskar et al. (2016) ; Dinh et al. (2017) ; Chaudhari et al. (2016) , about SGD Chaudhari & Soatto (2017) ; Zhang et al. (2017) and to a number of other explanations (e.g. Belkin et al. (2018) ; Martin & Mahoney (2019) ) for such unusual properties of deep networks. We start by defining some key concepts. We call "loss" the measure of performance of the network f on a training set S = x 1 , y 1 , · · · , x N , y N . The most common loss optimized during training for binary classification is the logistic loss L(f ) = 1 N N n=1 ln(1 + e −ynf (xn) ). We call classification "error" 1 N N n=1 H(−y n f (x n )), where y is binary and H is the Heaviside function with H(−yf (x)) = 1 if −yf > 0 which correspond to wrong classification. There is a close relation between the logistic loss and the classification error: the logistic loss is an upper bound for the classification error. Thus minimizing the logistic loss implies minimizing the classification error. The criticism in papers such as Zhang et al. (2016) refers to the classification error. However, training minimizes the logistic loss. As a first step it seems therefore natural to look at whether logistic loss in training can be used as a proxy for the logistic loss at testing. The second step follows from the following observation. The logistic loss can always be made arbitrarily small for separable data (when f (x n )y n > 0, ∀n) by scaling up the value of f and in fact it can be shown that the norm of the weights of f grows monotonically with time The linear relationship we found means that the generalization error of Equation 3 is small once the complexity of the space of deep networks is "dialed-down" by normalization. It also means that, as expected from the theory of uniform convergence, the generalization gap decreases to zero for increasing size of the training set (see Figure 1 ). Thus there is indeed asymptotic generalization -defined as training loss converging to test loss when the number of training examples grows to infinity -in deep neural networks, when appropriately measured. The title in Zhang et al. (2016) "Understanding deep learning requires rethinking generalization" seems to suggest that deep networks are so "magical" to be beyond the reach of existing machine learning theory. This paper shows that this is not the case. On the other hand, the generalization gap for the classification error and for the unnormalized cross-entropy is expected to be small only for much larger N (N must be significantly larger than the number of parameters). However, consistently with classical learning theory, the cross-entropy loss at training predicts well the cross-entropy loss at test when the complexity of the function space is reduced by appropriate normalization. For the normalized case with R = 1 this happens in our data sets for a relatively "small" number N of training examples as shown by the linear relationship of Figure 2 . The classical analysis of ERM algorithms studies their asymptotic behavior for the number of data N going to infinity. In this limiting regime, N > W where W is the fixed number of weights; consistency (informally the expected error of the empirical minimizer converges to the best in the class) and generalization (the empirical error of the minimizer converges to the expected error of the minimizer) are equivalent. This note implies that there is indeed asymptotic generalization and consistency in deep networks. However, it has been shown that in the case of linear regression, for instance with kernels, there are situations -depending on the kernel and the data -in which there is simultaneously interpolation of the training data and good expected error. This is typically when W > N and corresponds to the limit for λ = 0 of regularization, that is the pseudoinverse. It is likely that deep nets may have a similar regime, in which case the implicit regularization described here, with its asymptotic generalization effect, is just an important prerequisite for a full explanation for W > N -as it is the case for kernel machines under the square loss. The results of this paper strongly suggested that the complexity of the normalized network is controlled by the optimization process. In fact a satisfactory theory of the precise underlying implicit regularization mechanism has now been proposed Soudry et al. (2017) As expected, the linear relationship we found holds in a robust way for networks with different architectures, different data sets and different initializations. Our observations, which are mostly relevant for theory, yield a recommendation for practitioners: it is better to monitor during training the empirical "normalized" cross-entropy loss instead of the unnormalized cross-entropy loss actually minimized. The former matters in terms of stopping time and predicts test performance in terms of cross-entropy and ranking of classification error. More significantly for the theory of Deep Learning, this paper confirms that classical machine learning theory can describe how training performance is a proxy for testing performance of deep networks.
Contrary to previous beliefs, the training performance of deep networks, when measured appropriately, is predictive of test performance, consistent with classical machine learning theory.
{"src": "scitldr-AIC_train", "paper_id": "BkelnhNFwB"}