This paper presents a margin-based multiclass generalization bound for neural networks which scales with their margin-normalized spectral complexity: their Lipschitz constant, meaning the product of the spectral norms of the weight matrices, times a certain correction factor. This bound is empirically investigated for a standard AlexNet network on the mnist and cifar10 datasets, with both original and random labels, where it tightly correlates with the observed excess risks. Neural networks owe their astonishing success not only to their ability to fit any data set: they also generalize well, meaning they provide a close fit on unseen data. A classical statistical adage is that models capable of fitting too much will generalize poorly; what's going on here? Let's navigate the many possible explanations provided by statistical theory. A first observation is that any analysis based solely on the number of possible labellings on a finite training set -as is the case with VC dimension -is doomed: if the function class can fit all possible labels (as is the case with neural networks in standard configurations (Zhang et al., 2017)), then this analysis can not distinguish it from the collection of all possible functions! (Krizhevsky et al., 2012) trained on cifar10, both with original and with random labels. Triangle-marked curves track excess risk across training epochs (on a log scale), with an 'x' marking the earliest epoch with zero training error. Circle-marked curves track Lipschitz constants, normalized so that the two curves for random labels meet. The Lipschitz constants tightly correlate with excess risk, and moreover normalizing them by margins (resulting in the square-marked curve) neutralizes growth across epochs. Next let's consider scale-sensitive measures of complexity, such as Rademacher complexity and metric entropy, which work directly with real-valued function classes, and moreover are sensitive to their magnitudes. Figure 1 plots the excess risk (the test error minus the training error) across training epochs against one candidate scale-sensitive complexity measure, the Lipschitz constant of the network (the product of the spectral norms of their weight matrices), and demonstrates that they are tightly correlated (which is not the case for, say, the l 2 norm of the weights). The data considered in Figure 1 is the standard cifar10 dataset, both with original and with random labels, which has been used as a sanity check when analyzing neural network generalization (Zhang et al., 2017). There is still an issue with basing a complexity measure purely on the Lipschitz constant (although it has already been successfully employed to regularize neural networks (Cisse et al., 2017) ): as depicted in Figure 1 , the measure grows over time, despite the excess risk plateauing. Fortunately, there is a standard resolution to this issue: investigating the margins (a precise measure of confidence) of the outputs of the network. This tool has been used to study the behavior of 2-layer networks, boosting methods, SVMs, and many others (Bartlett, 1996; Schapire et al., 1997; Boucheron et al., 2005) ; in boosting, for instance, there is a similar growth in complexity over time (each training iteration adds a weak learner), whereas margin bounds correctly stay flat or even decrease. This behavior is recovered here: as depicted in Figure 1 , even though standard networks exhibit growing Lipschitz constants, normalizing these Lipschitz constants by the margin instead gives a decaying curve. This work investigates a complexity measure for neural networks which is based on the Lipschitz constant, but normalized by the margin of the predictor. The two central contributions are as follows. • Theorem 1.1 below will give the rigorous statement of the generalization bound which is the basis of this work. In contrast to prior work, this bound: (a) scales with the Lipschitz constant (product of spectral norms of weight matrices) divided by the margin; (b) has no dependence on combinatorial parameters (e.g., number of layers or nodes) outside of log factors; (c) is multiclass (with no explicit dependence on the number of classes); (d) measures complexity against a reference network (e.g., for the ResNet (He et al., 2016), the reference network has identity mappings at each layer). The bound is stated below, with a general form and analysis summary appearing in Section 3, the full details relegated to the appendix. • An empirical investigation, in Section 2, of neural network generalization on the standard datasets cifar10, cifar100, and mnist using the preceding bound. Rather than using the bound to provide a single number, it can be used to form a margin distribution as in Figure 2 . These margin distributions will illuminate the following intuitive observations: (a) cifar10 is harder than mnist; (b) random labels make cifar10 and mnist much more difficult; (c) the margin distributions (and bounds) converge during training, even though the weight matrices continue to grow; (d) l 2 regularization ("weight decay") does not significantly impact margins or generalization. A more detailed description of the margin distributions is as follows. Suppose a neural network computes a function f : where k is the number of classes; the most natural way to convert this to a classifier is to select the output coordinate with the largest magnitude, meaning x → arg max j f (x) j . The margin, then, is to measure the gap between the output for the correct label and other labels, meaning Unfortunately, margins alone do not seem to say much; see for instance Figure 2a , where the collections of all margins for all data points -the unnormalized margin distribution -are similar for cifar10 with and without random labels. What is missing is an appropriate normalization, as in Figure 2b . This normalization is provided by Theorem 1.1, which can now be explained in detail. To state the bound, a little bit of notation is necessary. The networks will use L fixed nonlinearities (σ 1 , . . . , σ L ), where σ i is ρ i -Lipschitz (e.g., as with coordinate-wise ReLU, and max-pooling, as discussed in Appendix A.1); occasionally, it will also hold that let F A denote the function computed by the corresponding network: Whenever data (x 1 , . . . , x n ) are given, collect them as rows of a matrix X ∈ R n×d . Occasionally, notation will be overloaded to discuss F A (X T ), a matrix whose i th column is F A (x i ). The l 2 norm · 2 is always computed entry-wise; thus, for a matrix, it corresponds to the Frobenius norm. Next, define a collection of reference matrices (M 1 , . . . , M L ) with each dimension at most W ; for instance, to obtain a good bound for ResNet (He et al., 2016) , it is sensible to set M i := I, the identity map, and the bound below will worsen as the network moves farther from the identity map; for AlexNet (Krizhevsky et al., 2012), the simple choice M i = 0 suffices. Finally, letting · σ and · 1 respectively denote spectral norm and the unrolled l 1 vector norm, the spectral complexity R F A = R A of a network F A with weights A is (1.1) The following theorem provides a generalization bound for neural networks whose nonlinearities are fixed but whose weight matrices A have bounded spectral complexity R A . Theorem 1.1. Let nonlinearities (σ 1 , . . . , σ L ) and reference matrices (M 1 , . . . , M L ) be given as above (i.e., σ i is ρ i -Lipschitz and σ i (0) = 0). Then with probability at least 1 − δ over an iid draw of n examples ((x i , y i )) n i=1 , every margin γ > 0 and network where 2 . The full proof (based on metric entropy) is relegated to the appendix, but a sketch is provided in Section 3, along with a more general form (not limited to spectral norms), along with a (non-matching!) lower bound. Section 3 also gives a discussion of related work, but briefly it's essential to note that margin and Lipschitz-sensitive bounds have a long history in the neural networks literature (Bartlett, 1996; Anthony and Bartlett, 1999; Neyshabur et al., 2015); the distinction here is the sensitivity to specifically the spectral norm, as well as no explicit appearance of combinatorial quantities such as numbers of parameters or layers (outside of log terms, and indices to summations and products). Figure 3a , but identical in the other subplots; the cifar10 (blue) and random cifar10 (green) distributions are the same each time. This section will now use the core generalization bound, stated in Theorem 1.1, to empirically study generalization behavior of neural networks via margin distributions. Before proceeding with the plots, it's a good time to give a more refined description of the margin distribution, one that is suitable for comparisons across datasets. Given n data points ((x i , y i )) n i=1 as rows of matrix X ∈ R n×d and predictor F A : R d → R k with spectral complexity R A (cf. eq. (1.1)), the (normalized) margin distribution is the univariate empirical distribution of the data points each transformed into a single scalar according to where spectral complexity R A is from eq. (1.1). The normalization is thus derived from the bound in Theorem 1.1, but ignoring log terms. Taken this way, the two margin distributions for two datasets can be interpreted as follows. Considering any fixed point on the horizontal axis, if the cumulative distribution of one density is lower than the other, then it corresponds to a lower right hand side in Theorem 1.1. For no reason other than visual interpretability, the plots here will instead depict a density estimate of the margin distribution. The vertical and horizontal axes are rescaled in different plots, but the random and true cifar10 margin distributions are always the same. A little more detail about the experimental setup is as follows. All experiments were implemented in Keras (Chollet et al., 2015) . In order to minimize conflating effects of optimization and regularization, the optimization method was vanilla sgd with step size 0.01, and all regularization (weight decay, batch normalization, etc.) were disabled. "cifar" in general refers to cifar10, however cifar100 will also be 4 10 epochs 20 epochs 40 epochs 80 epochs 160 epochs Comparing datasets. A first comparison is of cifar10 and the standard mnist digit data. mnist is considered "easy", by which it is typically meant that any of a variety of methods can achieve roughly 1% test error. The "easiness" is corroborated by Figure 3a , where the margin distribution for mnist places all its mass far to the right of the mass for cifar10. Interestingly, randomizing the labels of mnist, as in Figure 3b , results in a margin distribution to the left of not only cifar10, but also slightly to the left of (but close to) cifar10 with randomized labels. Next, Figure 3c compares cifar10 and cifar100, where cifar100 uses the same input images as cifar10; indeed, cifar10 is obtained from cifar100 by collapsing the original 100 categories into 10 groups. Interestingly, cifar100, from the perspective of margin bounds, is just as difficult as cifar10 with random labels. This is consistent with the large test observed error on cifar100 (which has not been "optimized" in any way via regularization). Lastly, Figure 3d replaces the cifar10 input images with random images sampled from Gaussians matching the first-and second-order image statistics (see (Zhang et al., 2017) for similar experiments). Convergence of margins. As was pointed out in Section 1, the weights of the neural networks do not seem to converge in the usual sense during training (the norms grow continually). However, as depicted in Figure 4a , the sequence of (normalized!) margin distributions is itself converging. Regularization. As remarked in (Zhang et al., 2017), regularization only seems to bring minor benefits to test error (though adequate to be employed in all cutting edge results). This observation is certainly consistent with the margin distributions in Figure 4b , which do not improve (e.g., by shifting to the right) in any visible way under regularization. An open question, discussed further in Section 4, is to design regularization that improves margins. This section will sketch the proof of Theorem 1.1, state a few generalizations, give a lower bound, and discuss related work.  ; note that R γ and R γ respectively upper bound the probability and fraction of error on the source distribution and training set. Lastly, given a set of real-valued functions H, define the Rademacher complexity as R(H |S ) := E sup h∈H n i=1 i h(x i , y i ) where the expectation is over the Rademacher random variables With this notation in place, the basic bound is as follows. Lemma 3.1. Given functions F with F f : R d → R k and any γ > 0, define Then, with probability at least 1 − δ over a sample S of size n, every f ∈ F satisfies This bound is a direct consequence of standard tools in Rademacher complexity. In order to instantiate this bound, covering numbers will be used to directly upper bound the Rademacher complexity term R((F γ ) |S ). Interestingly, the choice of directly working in terms of covering numbers seems essential to providing a bound with no explicit dependence on k; by contrast, prior work primarily (solely?) handles multiclass via a Rademacher complexity analysis on each coordinate of a k-tuple of functions, and pays a factor √ k (Zhang, 2004). This subsection proves Theorem 1.1 via Lemma 3.1 by controlling the Rademacher complexity R((F γ ) |S ) for networks with bounded spectral complexity via covering numbers. This first step is to prove a more general covering number bound (in terms of general operator norms) which will eventually be specialized with l 2 data norms and spectral operator norms to prove Theorem 1.1. A tantalizing direction for future work is to specialize the general bound in other ways, namely ones that are better adapted to the geometry of neural networks as encountered in practice. The structure of the networks is the same as before; namely, given matrices with the convention F ∅ (Z) = Z. • The input Z ∈ V 1 is associated with some norm |Z| 1 ≤ B. The subscript merely indicates an index, and does not refer to any l 1 norm. The vector space V 1 , and moreover the eventual collection of vector spaces (V 1 , . . . , V L ), have no fixed meaning and are simply abstract vector spaces. However, when using these tools to prove Theorem 1.1, V 1 = R d×n and Z ∈ V 1 is formed by collecting the n data points into its columns; that is, Z = X . • The linear operators A i : V i → W i+1 are associated with some operator norm |A i | i→i+1 ≤ c i : where once again |||·||| i+1 is an abstract norm introduced purely to lend this proof more flexibility. As stated before, these linear operators A = (A 1 , . . . , A L ) vary across functions F A . When used to prove Theorem 1.1, Z is a matrix (the forward image of data matrix X across layers), and these norms are all matrix norms. • The ρ i -Lipschitz mappings σ i : W i+1 → V i+1 have ρ i measured with respect to norms | · | i+1 and |||·||| i+1 : for any z, z ∈ W i+1 , These Lipschitz mappings are considered fixed within F A . Note again that these operations, when applied to prove Theorem 1.1, operate on matrices which represent the forward images of all data points together. Lipschitz properties of the standard coordinate-wise ReLU and max-pooling operators can be found in Appendix A.1. Lastly, just before giving the bound, the notation for (proper) covering numbers is as follows. The notation N (U, , · ) means the least cardinality of any subset V ⊆ U which covers U at scale with norm · , meaning sup A∈U min B∈V
Another thread of work REF Neyshabur et al., 2017b,a) tries to develop novel complexity measures that are able to characterize the generalization performance in practice.
Spectrally-normalized margin bounds for neural networks
ArXiv
ArXiv
Computer Science Mathematics