Title: OPTIMAL MARGIN DISTRIBUTION NETWORK

Abstract: Recent research about margin theory has proved that maximizing the minimum margin like support vector machines does not necessarily lead to better performance, and instead, it is crucial to optimize the margin distribution. In the meantime, margin theory has been used to explain the empirical success of deep network in recent studies. In this paper, we present ODN (the Optimal margin Distribution Network), a network which embeds a loss function in regard to the optimal margin distribution. We give a theoretical analysis for our method using the PAC-Bayesian framework, which confirms the significance of the margin distribution for classification within the framework of deep networks. In addition, empirical results show that the ODN model always outperforms the baseline cross-entropy loss model consistently across different regularization situations. And our ODN model also outperforms the cross-entropy loss (Xent), hinge loss and soft hinge loss model in generalization task through limited training data.

1. INTRODUCTION:

In the history of machine learning research, the large margin principle has played an important role in theoretical analysis of generalization ability, meanwhile, it also achieves remarkable practical results for classification (Cortes & Vapnik, 1995) and regression problems (Drucker et al., 1997) . More than that, this powerful principle has been used to explain the empirical success of deep neural network. Bartlett et al. (2017) and Neyshabur et al. (2018) present a margin-based multi-class generalization bound for neural networks that scales with their margin-normalized spectral complexity using two different proving tools. Moreover, Arora et al. (2018) proposes a stronger generalization bounds for deep networks via a compression approach, which are orders of magnitude better in practice.

As for margin theory, Schapire et al. (1997) first introduces it to explain the phenomenon that Ad-aBoost seems resistant to overfitting problem. Two years later, Breiman (1999) indicates that the minimum margin is important to achieve a good performance. However, Reyzin & Schapire (2006) conjectures that the margin distribution, rather than the minimum margin, plays a key role in being empirically resistant to overfitting problem; this has been finally proved by Gao & Zhou (2013) . In order to restrict the complexity of hypothesis space suitably, a possible way is to design a classifier to obtain optimal margin distribution. Gao & Zhou (2013) proves that, to attain the optimal margin distribution, it is crucial to consider not only the margin mean but also the margin variance. Inspired by this idea, Zhang & Zhou (2016) proposes the optimal margin distribution machine (ODM) for binary classification, which optimizes the margin distribution through the first-and second-order statistics, i.e., maximizing the margin mean and minimizing the margin variance simultaneously. To expand this method to the multi-class classification problem, Zhang & Zhou (2017) presents a multi-class version of ODM.

Based on these recent works, we consider the expansion of the optimal margin distribution principle on deep neural networks. In this paper, we propose an optimal margin distribution loss for convolution neural networks, which is not only maximizing the margin mean but also minimizing the margin variance as ODM does. Moreover, we use the PAC-Bayesian framework to derive a novel generalization bound based on margin distribution. Comparing to the spectrally-normalized margin bounds of Bartlett et al. (2017) and Neyshabur et al. (2018) , our generalization bound shows that we can restrict the capacity of the model by setting an appropriate ratio between the first-order statistic and the second-order statistic rather than trying to control the whole product of the spectral norms of each layer. And we empirically evaluate our loss function on deep network across different datasets and model structures. Specifically, we consider the performance of these models in generalization task through limited training data.

Recently, many researchers try to explain the experimental success of deep neural network. One of the research direction is to explain why the deep learning does not have serious overfitting problem.

Although several common techniques, such as dropout (Srivastava et al., 2014) , batch normalization (Ioffe & Szegedy, 2015) , and weight decay (Krogh & Hertz, 1992) , do improve the generalization performance of the over-parameterized deep models, these techniques do not have a solid theoretical foundation to explain the corresponding effects. As for our optimal margin distribution loss, it has a generalization bound to prove that we can restrict the complexity of hypothesis space reasonably through searching appropriate statistics dependent on data distribution. In experimental section, we compare our optimal margin distribution loss with the baseline cross-entropy loss under different regularization methods.

2. OPTIMAL MARGIN DISTRIBUTION LOSS:

Consider the classification problem with input domain X = {x| x ∈ R n } and output domain Y = {1, . . . , k}, we denote a labeled sample as z ∈ (X , Y). Suppose we use a network generating a prediction score for the input vector x ∈ X to class i, through a function f i : X → R, for i = 1, . . . , k. The predicted label is chosen by the class with maximal score, i.e. h(x) = arg max i f i (x).

Define the decision boundary of each class pair {i, j} as:

D i,j := {x|f i (x) = f j (x)}

Constructed on this definition, the margin distance of a sample point x to the decision boundary D i,j is defined by the smallest translation of the sample point to establish the equation as:

|γ(x, i, j)| = min δ δ δ δ δ δ 2 s.t. f i (x + δ δ δ) = f j (x + δ δ δ).

In order to approximate the margin distance in the nonlinear situation, Elsayed et al. ( 2018) has offered a linearizing definition:

| γ(x, i, j)| = |f i (x) -f j (x)| ∇ x f i (x) -∇ x f j (x) 2 .

Naturally, this pairwise margin distance leads us to the following definition of the margin for a labeled sample z = (x, y):

γ h (x, y) = f y (x) -max i =y f i (x) ∇ x f y (x) -∇ x max i =y f i (x) 2 .

Therefore, the defined classifier h misclassifies (x, y) if and only if the margin is negative. Given a hypothesis space H S of functions mapping X to Y, which can be learned by the fixed deep neural network through the training set S, our purpose is to find a way to learn a decision function h ∈ H S such that the generalization error

R(h) = E (x,y)∼(X ,Y) [1 h(x) =y ] is small.

In this work, we introduce a type of margin loss, and connect it to deep neural networks. The origin loss function has been specially adapted for the difference between deep learning models and linear models by us as following definition:

EQUATION

where r is the margin mean, θ is the margin variance and µ is a parameter to trade off two different kinds of deviation (keeping the balance on both sides of the margin mean). In the Appendix A, we explain the reason why we use these three hyper-parameters to construct such a optimal margin distribution loss function.

Fig. 1 shows, equation 1 will produce a linear loss decreasing progressively when the margins of sample points satisfy γ h ≤ r -θ and a square loss increasing progressively when the margins satisfy γ h ≥ r + θ. Therefore, our margin loss function will enforce the tie which has zero loss to contain the sample points as many as possible. So the parameters of the classifier will be determined not only by the samples that are close to the decision boundary but also by the samples that are away from the decision boundary. In other words, our loss function is aimed at finding a decision boundary which is determined by the whole sample margin distribution, instead of the minority samples that have minimum margins. To verify superiority of the optimal margin distribution network, our paper verifies it both theoretically and empirically.

3. ANALYSIS:

To present a new margin bound for our optimal margin distribution loss, some notations are needed. Consider that the convolution neural networks can be regarded as a special structure of the fully connected neural networks, we simplify the definition of the deep networks. Let f w (x) : X → R k be the function learned by a L-layer feed-forward network for the classification task with parameters w = (W 1 , . . . , W L ), thus f w (x) = W L φ(W L-1 φ(. . . φ(W 1 x))), here φ is the ReLU activation function. Let f i w denote the output of layer i before activation and ρ be an upper bound on the number of output units in each layer. Recursively, we can redefine the deep network:

f 1 w (x) = W 1 x and f i w (x) = W i φ(f i-1 w (x)). Let • F ,

• 1 and • 2 denote the Frobenius norm, the element-wise 1 norm and the spectral norm respectively. In order to facilitate the theoretical derivation of our formula, we simplify the definition of the loss function:

L r,θ (f w ) = Pr (x,y)∼(X ,Y) f w,y (x) -max i =y f w,i (x) ∇ x f w,y (x) -∇ x max i =y f w,i (x) ≤ r -θ + Pr (x,y)∼(X ,Y) f w,y (x) -max j =y f w,j (x) ∇ x f w,y (x) -∇ x max j =y f w,j (x) ≥ r + θ .

Specially, define the L 0 as r = θ and θ → ∞, actually equal to the 0-1 loss. And let L r,θ (f w ) be the empirical estimate of the optimal margin distribution loss. So we will denote the expected risk and the empirical risk as L 0 (f w ) and L 0 (f w ), which are bounded between 0 and 1.

In the PAC-Bayesian framework, one expresses the prior knowledge by defining a prior distribution over the hypothesis class. Following the Bayesian reasoning approach, the output of the learning algorithm is not necessarily a single hypothesis. Instead, the learning process defines a posterior probability over H, which we denote by Q. In the context of a supervised learning problem, where H contains functions from X to Y, one can think of Q as defining a randomized prediction rule. We consider the distribution Q which is learned from the training data of form f w+u , where u is a random variable whose distribution may also depend on the training data. Let P be a prior distribution over H that is independent of the training data, the PAC-Bayesian theorem states that with possibility at least 1 -δ over the choice of an i.i.d. training set S = {z 1 , ..., z m } sampled according to (X , Y), for all distributions Q over H (even such that depend on S), we have (McAllester, 2003) :

E u [L 0 (f w+u )] ≤ E u [ L 0 (f w+u )] + D KL (w + u P ) + ln m δ 2(m -1) . (2)

Note that the left side of the inequality is based on f w+u . To derive an expected risk bound L 0 (f w ) for a single predictor f w , we have to relate this PAC-Bayesian bound to the expected perturbed loss just like Neyshabur et al. ( 2018) derive the Lemma 1 in their paper. Based on the inequality 2, we introduce a perturbed restriction which is related to the margin distribution (the margin mean r and margin variance θ): Lemma 1. Let f w (x) : X → R k be any predictor with parameters w, and P be any distribution on the parameters that is independent of the training data. Then, for any r > θ > 0, δ > 0, with probability at least 1 -δ over the training set of size m, for any w, and any random perturbation u

s.t. Pr u max x∈X |f w+u (x) -f w (x)| ∞ < r-θ 4

≥ 1 2 , we have:

L 0 (f w ) ≤ L r,θ (f w ) + D KL (w + u P ) + ln 3m δ m -1 .

The margin variance information does not change the conclusion of the perturbed restriction, the proof of this lemma is similar to Lemma 1 in Neyshabur et al. (2018) .

In order to bound the change caused by perturbation, we have to bring in three definitions that are used to formalize error-resilience in Arora et al. (2018) as follows: Definition 1. (Layer Cushion). The layer cushion of layer i is defined to be largest number µ i such that for any x ∈ S:

µ i W i F φ(f i-1 w (x)) 2 ≤ f i w (x) 2 .

Intuitively, cushion considers how much smaller the output

W i φ(f i-1 w (x)) is compared to the upper bound W i 2 φf i-1 w (x) 2 .

However, for nonlinear operators the definition of error resilience is less clean. Let's denote M i,j : R h i → R h j the operator corresponding to the portion of the deep network from layer i to layer j, and by J i,j its Jacobian. If infinitesimal noise is injected before level i then M i,j passes it like J i,j , a linear operator. When the noise is small but not infinitesimal then one hopes that we can still capture the local linear approximation of the nonlinear operator M by define Interlayer Cushion: Definition 2. (Interlayer Cushion). For any two layers i < j, we define the interlayer cushion µ i,j , as the largest number such that for any x ∈ S:

µ i,j J i,j f i w (x) F φ(f i-1 w (x)) 2 ≤ f j w (x) 2

. Furthermore, for any layer i we define the minimal interlayer cushion as

µ i→ = min i≤j≤L µ i,j = min{ 1 √ ρ , min i≤j≤L µ i,j }.

The next condition qualifies a common appearance: if the input to the activations is well-distributed and the activations do not correlate with the magnitude of the input, then one would expect that on average, the effect of applying activations at any layer is to decrease the norm of the pre-activation vector by at most some small constant factor. Definition 3. (Activation Contraction). The activation contraction c is defined as the smallest number such that for any layer i and any x ∈ X :

φ(f i w (x)) 2 ≥ f i w (x) 2 c

To guarantee that the perturbation of the random variable u will not cause a large change on the output with high possibility, we need a perturbation bound to relate the change of output to the structure of the network and the prior distribution P over H. Fortunately, Neyshabur et al. ( 2018) proved a restriction on the change of the output by norms of the parameter weights. In the following lemma, we preset our hyper-parameters r and θ, s.t. the parameter weights w ∈ H satisfying f w (x) 2 ≤ r + θ, when fixing W L 2 = 1. Thus, we can bound this change in terms of the spectral norm of the layer and the presetting hyper-parameters: Lemma 2. For any L > 0, let f w : X → R k be a L-layer network. Then for any w ∈ H satisfying f w (x) 2 ≤ r + θ, and x ∈ X , and any perturbation u

= vec({U i } L i=1 ) s.t. U i 2 ≤ 1 L W i 2

, the change of the output of the network can be bounded as follows:

|f w+u (x) -f w (x)| 2 ≤ O c(r + θ) L i=1 U i 2 W i 2 µ i µ i→ .

The proof of this lemma is given in Appendix B. Eventually, we utilize all above bounding lemmas and the error-resilience definitions to derive the following new margin based generalization bound for our Optimal margin Distribution Network. Theorem 1. (Generalization Bound). For any L, ρ > 0, let f w : X → R k be a L-layer feed-forward network with ReLU activations. Then, for any δ > 0, r > θ > 0, with probability ≥ 1 -δ over a training set of size m, for any w, we have:

L 0 (f w ) ≤ L r,θ (f w ) + O    c 2 L 2 ρ ln(Lρ)(r + θ) 2 L i=1 Wi 2 F Wi 2 2 µiµi→ + ln Lm δ m(r -θ) 2    .

The proof of this theorem is given in Appendix B.

Remark. Comparing with the spectral complexity in Bartlett et al. (2017) :

EQUATION

which is dominated by the product of spectral norms across all, our margin bound is relevant to r, θ dependent on the margin distribution and µ i and µ i→ dependent on the network structure.

The product value in equation 3 is extremely large and is hard to control it, but the parameter in our generalization bound is easy to restrict. Explicitly, the factor consisted of hyper-parameters

r+θ r-θ 2 = 1+ θ r 1-θ r 2 = 2 1-θ r -1

2 is a monotonicity increasing function with regard to the ratio θ r ∈ [0, 1). Under the assumption of separability, we can come to the conclusion that maller θ and larger r make the complexity smaller. Searching a suitable value of r and θ for the specific data distribution will lead us to a better generalization performance.

4. EXPERIMENT:

In this section, we empirically evaluate the effectiveness of our optimal margin distribution loss on generalization tasks, comparing it with three other loss functions: cross-entropy loss (Xent), hinge loss, and soft hinge loss. We first compare them under limited training data situation, using only part of the MNIST dataset (LeCun et al., 1998) to train and evaluate the models deploying the four different losses, with the used data ratio ranging from 0.125% to 100%. Similar experiments are also performed on the legend CIFAR-10 dataset (Krizhevsky & Hinton, 2009) . Then we compare them under different regularization situations, investigating the combination of optimal margin distribution loss with dropout and batch normalization. Finally, we visualize and compare the features learned by the deep learning model with the four lose functions as well as the margin distribution from those models.

Here we introduce three commonly used loss functions in deep learning for comparison in the experimental section:

Cross-entropy Loss (Xent):

L Xent (f w ) = -ln exp(f w,y (x)) k i=1 exp(f w,i (x))

Hinge Loss:

γ h (x, y) = f w,y (x) -max i =y f w,i (x) ∇ x f w,y (x) -∇ x max i =y f w,i (x) 2 , L Hinge (f w ) = max [0, γ h (x, y) -γ 0 ] ,

where γ 0 is a hyper-parameter to control the minimum margin as support vector machine does.

Soft Hinge Loss:

L Sof tHinge (f w ) = - 1 k •   ln(1 + exp(-f w,y (x))) - i =y ln(1 + exp(-f w,i (x)))   ,

where k is the number of classes.

4.1. EXPERIMENTAL SETUP:

Regarding the deep models, we use the following combination of datasets and models: a simple deep convolutional network for MNIST, original Alexnet (Krizhevsky et al., 2012) for CIFAR-10.

In terms of the implementation of optimal margin distribution loss, as shown in Section 2, there is a gradient term in the loss itself, which can make the computation expensive. To reduce computational cost as Elsayed et al. ( 2018) do, in the backpropagation step we considered the gradient term ∇ x f y (x) -∇ x max i =y f i (x) 2 as a constant, so that we recomputed the value of ∇ x f y (x) -∇ x max i =y f i (x) 2 at every forward propagation step. Furthermore, since the denominator item could be too small, which would cause numerical problem, we added an with small value to the denominator so that clip the loss at some threshold.

For special hyperparameters, including the margin mean parameter and margin variance parameter for the ODN model, and margin parameter for hinge loss model, we performed hyperparameter searching. We held out 5000 samples of the training set as a validation set, and used the remaining samples to train models with different special hyperparameters values, on both the MNIST dataset and the CIFAR-10 dataset. As for the common hyperparameters, such as, learning rate and momentum, we set them as the default commonly used values in Pytorch for all the models. We chose batch stochastic gradient descent as the optimizer. Evaluated on the testing dataset, the baseline cross-entropy model achieves a test accuracy of 99.09%; the hinge loss model achieves 98.95% on MNIST dataset; the soft-hinge loss model achieves 99.14% and the ODN model achieves 99.16%. On the CIFAR-10 dataset, the baseline cross-entropy model trained on the remaining training samples achieves a test accuracy of 83.51%; the hinge loss model achieves 82.15%; the soft-hinge loss model achieves 81.96% and the ODN model achieves 84.61%.

4.2. LIMITED SMALL SAMPLE LEARNING:

It is well-known that deep learning method is very data-hungry, which means that if the training data size decreases, the model's performance can decrease significantly. In reality, this disadvantage of deep learning method can restrict its application seriously since sufficient amount of data is not always available. On the other hand, one of the desirable property of optimal margin distribution loss based models is that it can generalize well even when the training data is insufficient because the optimal margin distribution loss can restrict the complexity of the hypothesis space suitably. To evaluate the performance of optimal margin distribution loss based models under insufficient training data setting, we randomly chose some fraction of the training set, in particular, from 100% of the training samples to 0.125% on the MNIST dataset, and from 100% of the training samples to 0.5% on the CIFAR-10 dataset, and train the models accordingly.

In Fig. 2 , we show the test accuracies of cross-entropy, hinge, soft hinge, and optimal margin distribution loss based models trained on different fractions of the MNIST and CIFAR-10 dataset. As shown in the figure, the test accuracies of all these four models increase as the fraction of training samples increases. Obviously, the ODN models proposed by our paper outperform all the other models constantly across different datasets and different fractions. Furthermore, the less training data there are, the larger performance gain the ODN model can have. On the MNIST dataset, the optimal margin distribution loss based model outperforms cross-entropy loss model by around 4.95%, hinge loss model by around 6.84% and soft-hinge loss model by around 3.03% on the smallest training set which contains only 0.125% of the whole training samples. Similarly, The ODN model outperforms cross-entropy loss model by around 9.9%, hinge loss model by around 10.1%, and soft hinge loss model by 13.4% on the smallest CIFAR-10 dataset which contains only 0.5% of the whole training samples. We also compared our optimal margin distribution loss with the baseline cross-entropy loss under different regularization methods and different amounts of training data, whose results are shown in Table 1 . As suggested by Table 1 , our loss can outperform the baseline loss consistently across different situations, no matter whether dropout, batch normalization or all the CIFAR-10 dataset are used or not. Specifically, when the size scale of training samples is small (5% fraction of the CIFAR-10 training set), the advantage of our optimal margin distribution loss is more significant. Moreover, our optimal margin distribution loss can cooperate with batch normalization and dropout, achieving the best performance in Table .1, which is shown in bold red text. Unlike dropout and batch normalization which are lack of solid theory ground, our optimal margin distribution loss has the margin bound , which guides us to find the suitable ratio θ r to restrict the capacity of models and alleviate the overfitting problem efficiently.

4.3. REGULARIZATION METHODS:



4.4. DATA VISUALIZATION:

Since the performance of the ODN models is excellent, we hope to see that the distributions of data in the learned feature space (the last hidden layer) are consistent with the generalization results. In this experiment, we use t-SNE method to visualize the data distribution on the last hidden layer for training samples and test samples. Fig. 3 and Fig. 4 plots the 2-dimension embedding image on limited MNIST and CIFAR-10 dataset, which is only 1% of the whole training samples. t-SNE (Maaten & Hinton, 2008 ) is a tool to visualize high-dimensional data. It converts similarities between data points to joint probabilities and tries to minimize the Kullback-Leibler divergence between the joint probabilities of the low-dimensional embedding and the high-dimensional data. Consistently, we can find that the result of our ODN model is better than all the others, the distribution of the samples which has the same label is more compact. To quantify the degree of compactness of the distribution, we perform a variance decomposition on the data in the embedding space. By comparing the ratio of the intra-class variance to the inter-class variance in Table 2 and Table 3 , we can know that our optimal margin distribution loss alway attain the most compact distribution in these four loss functions. Moreover, the visualization result is consistent with the margin distribution of these four models in Fig. 5 , which means getting an optimal margin distribution is helpful to deriving a good learned features space. And that representation features space can further alleviate the overfitting problem of deep learning. Hence, the optimal margin distribution loss function can significantly outperforms the other loss functions in generalization task through limited training data.

4.5. MARGIN DISTRIBUTIONS:

Fig. 5 plots the kernel density estimates of margin distribution producted by cross-entropy loss, hinge loss, soft hinge loss and ODN models on dataset MNIST. As can be seen, our ODN model derives a large margin mean with a smallest margin variance in all these four models. By calculating the value of ratio between the margin mean and the margin standard deviation, we know that the ratio in our ODN model is 3.20 which is significantly larger than 2.38 in the cross-entropy loss, 2.35 in the hinge loss and 2.63 in the soft hinge loss. The distribution of our model becomes more "sharper", which prevents the instance with small margin, so our method can still perform well as the training data is limited, which is also consistent with the result in Fig. 2 .

5. CONCLUSIONS:

Recent studies disclose that maximizing the minimum margin for decision boundary does not necessarily lead to better generalization performance, and instead, it is crucial to optimize the margin distribution. However, the influence of margin distribution for deep networks still remains undiscussed. We propose ODN model trying to design a loss function which aims to control the ratio between the margin mean and the margin variance. Moreover, we present a theoretical analysis for our method, which confirms the significance of margin distribution in generalization performance. As for experiments, the results validate the superiority of our method in limited data problem. And our optimal margin distribution loss function can cooperate with batch normalization and dropout, achieving a better generalization performance.

A EXPLAINATION FOR OPTIMAL MARGIN DISTRIBUTION LOSS:

Inspired by the optimal margin distribution principle, Zhang & Zhou (2017) propose the multi-class optimal margin distribution machine, which characterizes the margin distribution according to the first-and second-order statistics. Specially, let γ denote the margin mean, and the optimal margin distribution machine can be formulated as:

min w,γ,ξi, i Ω(w) -ηγ + λ m m i=1 (ξ 2 i + 2 i ) s.t. γ h (x i , y i ) ≥ γ -ξ i γ h (x i , y i ) ≤ γ + i , ∀i,

where Ω(w) is the regularization term to penalize the norm of the weights, η and λ are trading-off parameters, ξ i and are the deviation of the margin γ h (x i , y i ) to the margin mean. It is evident that m i=1 (ξ 2 i + 2 i )/m is exactly the margin mean. In the linear situation, scaling w does not affect the final classification results such as SVM, the margin mean can be normalized as 1, then the deviation of the margin of (x i , y i ) to the margin mean is |γ h (x i , y i ) -1|, and the formula can be reconstruct as:

min w,ξi, i Ω(w) + λ m m i=1 ξ 2 i + µ 2 i (1 -θ) 2 s.t. γ h (x i , y i ) ≥ 1 -θ -ξ i γ h (x i , y i ) ≤ 1 + θ + i , ∀i,

where µ ∈ (0, 1] is parameter to trade off two different kinds of deviation (keeping the balance on both sides of the margin mean). θ ∈ [0, 1) is a parameter of the zero loss band, which can control the number of support vectors. In other words, θ is a parameter to control the margin variance, while the data which is out of this zero loss band will be used to update the weights to minimize the loss.

For this reason, we simply regard it as the margin variance.

However, under the non-linear setting in our paper, we can not directly linearly normalize the margin mean to the value 1. So we assume that the normalized margin mean is r, then the optimization target can be reformulated as:

min w,ξi, i Ω(w) + λ m m i=1 ξ 2 i + µ 2 i (r -θ) 2 s.t. γ h (x i , y i ) ≥ r -θ -ξ i γ h (x i , y i ) ≤ r + θ + i , ∀i.

In our paper, we use the linear approximation (Elsayed et al., 2018) to normalize the magnitude of the norm of weights, so we can just transform this optimization target to a loss function as:

r,θ,µ (γ h ) =      (r-θ-γ h ) 2 (r-θ) 2 γ h ≤ r -θ 0 r -θ < γ h ≤ r + θ µ(γ h -r-θ) 2 (r+θ) 2 γ h > r + θ,

There is always some noise in the actual data, when deep network try to fit these data, the performance of model get worse with a larger margin variance. So we hope the larger side of the margin mean has a larger loss, which can effectively control the noise-fitting ability of models. That is why we adapt the smaller side of the margin mean to hinge form as:

r,θ,µ (γ h ) =      r-θ-γ h r-θ γ h ≤ r -θ 0 r -θ < γ h ≤ r + θ µ(γ h -r-θ) 2 (r+θ) 2 γ h > r + θ B PROOF OF LEMMA 2 AND THEOREM 1 Proof of Lemma 2. Let f L-i w (•) = W L φ(W L-1 φ . . . W i+1 φ(•)) and f i-1 w (•) = W i-1 φ(W i-2 φ(• • • W 1 (•)

)), we will write the network as

f w = f L-i w (W i φ(f i-1 w (x))

). If we just give i th layer parameter weights W i a perturbation U i , we can have following:

EQUATION

In the last Approximate equation in Equation 4, we assume that the perturbation U i is in the linear space span by W i , therefore, the part of φ(f i-1 w (x)) that is orthogonal to the space of W i will not affect the output of perturbation. In other word, we equal the projection on the linear space of W i + U i with the one on the linear space of W i , ie.

φf i-1 w (x) 2 = f i w (x) 2 Wi 2 . M i,i+1 (f i w (x) + ∆ i ) -J i,i+1 f i w (x) (f i w (x) + ∆ i ) 2 ≤ W i+1 2 ∆ i 2 ≤ ∆ i 2 W i+1 φf i w (x) 2 f i w (x) 2 • W i+1 2 f i w (x) 2 W i+1 φf i w (x) 2 ≤ ∆ i 2 W i+1 φf i w (x) 2 f i w (x) 2 • W i+1 2 f i w (x) 2 µ i+1 W i+1 F φf i w (x) 2 Layer Cushion ≤ ∆ i 2 W i+1 φf i w (x) 2 f i w (x) 2 • c W i+1 2 µ i+1 W i+1 F Activation Contraction = ∆ i 2 W i+1 φf i w (x) 2 f i w (x) 2 • c µ i+1 r i+1 ≤ U i 2 W i 2 f i+1 w (x) 2 • c µ i+1 r i

where r i+1 is the stable rank of layer i + 1, i.e. Wi+1 F Wi+1 2 . Therefore by induction method we have:

M i,j (f i w (x) + ∆ i ) -J i,j f i w (x) (f i w (x) + ∆ i ) 2 ≤ U i 2 W i 2 f j w (x) 2 • j k=i c µ k+1 r k+1 = O( c j-i µ j-i ) Obviously, we can know that M i,j (f i w (x) + ∆ i ) -J i,j fw(x) (f i w (x) + ∆ i ) 2 ≤ O( c d µ d ), when d = j -i ≥ 2 f L-i w (f i w (x) + ∆ i ) -f L-i w (f i w (x)) = M i,L (f i w (x) + ∆ i ) -M i,L (f i w (x)) 2 = M i,L (f i w (x) + ∆ i ) -M i,L (f i w (x)) + J i,L f i w (x) (∆ i ) -J i,L f i w (x) (∆ i ) 2 ≤ J i,L f i w (x) (∆ i ) 2 + M i,L (f i w (x) + ∆ i ) -M i,L (f i w (x)) -J i,L f i w (x) (∆ i ) 2 ≤ J i,L f i w (x) (∆ i ) 2 + (M i,L -J i,L f i w (x) )(f i w (x) + ∆ i ) 2 + (M i,L -J i,L f i w (x) )(f i w (x)) 2 ≤ J i,L f i w (x) (∆ i ) 2 + O( c L-i µ L-i ) ≤ J i,L f i w (x) F W i F f i-1 w (x) 2 + O( c L-i µ L-i ) ≤ c J i,L f i w (x) F W i F φf i-1 w (x) 2 + O( c L-i µ L-i ) Activation Contraction ≤ c µ i J i,L f i w (x) F W i φf i-1 w (x) 2 + O( c L-i µ L-i ) Layer Cushion = c µ i J i,L f i w (x) F f i w (x) 2 + O( c L-i µ L-i ) ≤ c µ i µ i→ |f w (x)| 2 + O( c L-i µ L-i ) Interlayer Cushion ≤ O (r + θ) U i 2 W i 2 c µ i µ i→

Suppose that all the perturbations U i are independent from each other, so we can just add the influence linearly for union bound:

|f w+u (x) -f w (x)| 2 ≤ O c(r + θ) L i=1 U i 2 W i 2 µ i µ i→ .

Proof. of Theorem 1.

The proof involves chiefly two steps. In the first step we bound the maximum value of perturbation of parameters to satisfied the condition that the change of output restricted by hyper-parameter of margin r, using Lemma 2. In the second step we proof the final margin generalization bound through Lemma 1 with the value of KL term calculated based on the bound in the first step.

Let β = L i=1 W i 2 1 L

and consider a network structured by normalized weights W i = β Wi 2 W i . Due to the homogeneity of the ReLU, we have that for feedforward networks with ReLU activations f w = f w , so the empirical and expected loss is the same for w and w. Furthermore, we can also get that

L i=1 W i 2 = L i=1 W i 2 and Wi F Wi 2 = Wi F Wi 2

. Hence, we can just assume that the spectral norm is equal across the layers, i.e. for any layer i, W i 2 = β.

When we choose the distribution of the prior P to be N (0, σI), i.e. u ∼ N (0, σI), the problem is that we will set the parameter σ according to β, which can not depend on the learned predictor w or its norm. Neyshabur et al. (2018) proposed a method that can avoid this block: they set σ based on an approximation β on a pre-determined grid. By formalizing this method, we can establish the generalization bound for all w for which |c 0 β -β| ≤ 1 L β, while given a constant c, and ensuring that each relevant value of cβ is covered by some β on the grid, i.e. Since u ∼ N (0, σ 2 I), we get the following bound for the spectral norm of U i according to the matrix extension of Hoeffding's inequalities (Tropp, 2012; Mackey et al., 2014) :

Pr Ui∼N (0,σ 2 I) [ U i 2 ≥ t] ≤ 2ρe -t 2 2ρσ 2 .

(5)

Taking the union bound over layers, with probability ≥ 1 2 , the spectral norm of each layer perturbation U i is bounded by σ 2ρ ln(4Lρ). Plugging this into Lemma 2 we have that with probability ≥ from the above inequality. Naturally, we can calculate the KL-diversity in Lemma 1 with the chosen distributions for P ∼ N (0, σ 2 I).

D KL (w + u P ) ≤ |w| 2 2σ 2 ≤ O c 2 L 2 ρ ln(Lρ) (r + θ) 2 (r -θ) 2 β-2 L i=1 W i 2 F ≤ O c 2 L 2 ρ ln(Lρ) (r + θ) 2 (r -θ) 2 L i=1 W i 2 F β 2 µ i µ i→ ≤ O c 2 L 2 ρ ln(Lρ) (r + θ) 2 (r -θ) 2 L i=1 W i 2 F W i 2 2 µ i µ i→

Hence, for any β, with probability ≥ 1 -δ and for all w such that, | β -β| ≤ 1 L β, we have:

L 0 (f w ) ≤ L r,θ (f w ) + O    c 2 L 2 ρ ln(Lρ)(r + θ) 2 L i=1 Wi 2 F Wi 2 2 µiµi→ + ln Lm δ (r -θ) 2 m    .

This proof method based on PAC-Bayesian framework has been raised by Neyshabur et al. (2018) , we use this convenient tool for proofing generalization bound with our loss function which can obtain the optimal margin distribution.

:



Figures and Tables:

Figure 1: The optimal margin distribution loss function (a) and the structure of fully connected network with optimal margin distribution loss (b).

Figure 2: Performance of selected MNIST (a) and CIFAR10 (b) models on generalization tasks.

Figure 3: Learned features visualization of selected MNIST models on training set (a); Learned features visualization of selected CIFAR-10 models on training set (b).

Figure 4: Learned features visualization of selected MNIST models on testing set (a); Learned features visualization of selected CIFAR-10 models on testing set (b).

Figure 5: Margin distribution of selected MNIST models.

µ i µ i→ can be considered as a constant.

w+u (x) -f w (x)| 2 ≤ c(r + θ) L i=1 U i 2 βµ i µ i→ ≤ eL(r + θ) β-1 σ 2ρ ln(4Lρ) ≤ r -θ4We can derive σ = r-θ cL(r+θ) β-1 √ ρ ln(4ρL)

Test accuracy of Alexnet on CIFAR-10 with different regularization methods and different fraction of training set.

Table content: <table><tr><td>Accuracy (%)</td><td colspan="2">Batch Normalization</td><td colspan="2">Non Batch Normalization</td></tr><tr><td/><td>Xent</td><td>ODN</td><td>Xent</td><td>ODN</td></tr><tr><td>ALL DROPOUT</td><td colspan="4">85.782 ± 0.198 87.644 ± 0.151 83.517 ± 0.322 84.643 ± 0.255</td></tr><tr><td colspan="5">ALL NON DROPOUT 81.491 ± 0.143 86.233 ± 0.244 72.223 ± 1.284 76.793 ± 1.279</td></tr><tr><td>5% DROPOUT</td><td colspan="4">61.955 ± 1.945 67.636 ± 1.633 50.747 ± 3.735 58.739 ± 1.348</td></tr><tr><td>5% NON DROPOUT</td><td colspan="4">57.753 ± 2.228 64.173 ± 1.982 36.293 ± 4.872 47.056 ± 3.927</td></tr><tr><td>Hyper-param (r / θ / µ)</td><td>-</td><td>30/0.7/0.1</td><td>-</td><td>1.2/0.7/0.1</td></tr></table>

Variance decomposition of selected MNIST models on embedding space.

Table content: <table><tr><td>Models</td><td/><td colspan="2">Training data</td><td/><td/><td colspan="2">Test data</td><td/></tr><tr><td/><td colspan="4">Xent Hinge Soft Hinge ODN</td><td colspan="4">Xent Hinge Soft Hinge ODN</td></tr><tr><td>Inter Class V ar</td><td>522</td><td>529</td><td>466</td><td>190</td><td>831</td><td>811</td><td>854</td><td>649</td></tr><tr><td colspan="3">Intra Class V ar 11200 11092</td><td>14128</td><td colspan="3">16469 13007 12986</td><td>11362</td><td>13955</td></tr><tr><td>ratio</td><td colspan="2">21.45 20.96</td><td>30.32</td><td colspan="3">86.68 15.65 16.01</td><td>13.3</td><td>21.5</td></tr></table>

Variance decomposition of selected CIFAR-10 models on embedding space.

Table content: <table><tr><td>Models</td><td/><td colspan="2">Training data</td><td/><td/><td/><td>Test data</td><td/></tr><tr><td/><td colspan="8">Xent Hinge Soft Hinge ODN Xent Hinge Soft Hinge ODN</td></tr><tr><td>Inter Class V ar</td><td>804</td><td>713</td><td>637</td><td>193</td><td>1993</td><td>1429</td><td>1917</td><td>1279</td></tr><tr><td colspan="3">Intra Class V ar 15692 9466</td><td>17546</td><td colspan="2">13273 7260</td><td>4780</td><td>5810</td><td>5645</td></tr><tr><td>ratio</td><td colspan="2">19.52 13.28</td><td>27.55</td><td>68.77</td><td>3.64</td><td>3.34</td><td>3.03</td><td>4.41</td></tr></table>

Peer review (iclr2019):
 This paper presents a PAC-Bayesian bound for a margin loss. Theorem 1 seems specific to ReLU activations. I wonder whether this theorem holds for other activations since most deep neural networks can use different activations at different layers instead of only the ReLU activation for all the layers. In Section 3, only Definition 3 is related to the activation. Can an activation satisfying Definition 3 have a similar bound to Theorem 1? Moreover, since the convolutional layer is a simplified case of the fully connected layer discussed in Section 3, does the convolutional layer simplify the bound in Theorem 1? There are some typos in this paper. “To derive a expected risk bound”: a -> an “used to formalize error-resilience in Arora et al. (2018) as following:”: following: -> follows. “the deep network from layer i to layer j”, “injected before level i”: i,j should be in the math mode. “dependent on the network structure .” there is an additional blank space after ‘structure’.