Improving Generalization of Deep Neural Networks by Leveraging Margin Distribution
Shen-Huan Lyu Lu Wang Zhi-Hua Zhou




  

  

    Improving Generalization of Deep Neural Networks by Leveraging Margin Distribution
  

  

  


  

    [t]1.0
      

        Author:

        http://www.lamda.nju.edu.cn/lvsh/Shen-Huan Lyu,
        http://www.lamda.nju.edu.cn/wangl/Lu Wang, and
        http://www.lamda.nju.edu.cn/zhouzh/Zhi-Hua Zhou (Corresponding author)
      

    

    
    A pre-printed manuscript

    which is accepted by Neural Networks

    
    
    < g r a p h i c s >


    http://www.lamda.nju.edu.cn/CH.MainPage.ashxLAMDA Group

    Department of Computer Science and Technology

    National Key Laboratory for Novel Software Technology


    

    
    < g r a p h i c s >


    https://www.nju.edu.cn/Nanjing University

    Nanjing, China

    

    Citation: Shen-Huan Lyu, Lu Wang, and Zhi-Hua Zhou. Improving generalization of deep neural networks by leveraging margin distribution. Neural Networks, 2022. doi: https://doi.org/10.1016/j.neunet.2022.03.019.
    

  




empty
	
Rephasing efficiency of sequences of phased pulses in spin-echo and light-storage experiments
    Thomas Halfmann
    Received; accepted
=============================================================================================




Recent research has used margin theory to analyze the generalization performance for deep neural networks (DNNs). The existed results are almost based on the spectrally-normalized minimum margin. However, optimizing the minimum margin ignores a mass of information about the entire margin distribution, which is crucial to generalization performance. In this paper, we prove a generalization upper bound dominated by the statistics of the entire margin distribution. Compared with the minimum margin bounds, our bound highlights an important measure for controlling the complexity, which is the ratio of the margin standard deviation to the expected margin. We utilize a convex margin distribution loss function on the deep neural networks to validate our theoretical results by optimizing the margin ratio. Experiments and visualizations confirm the effectiveness of our approach and the correlation between generalization gap and margin ratio.





§ INTRODUCTION


Deep neural networks (DNNs) are making major advances in solving problems that have resisted the best attempts of the artificial intelligence community for many years <cit.>, especially in the field of computer vision <cit.>. Recently, many research try to explain the practical success of DNNs via generalization, which is the ability of a classifier to perform well on unseen samples. However, some new empirical evidence has started to question this explanation. Adversarial training samples can cause the model to misclassify seriously by slight feature perturbation <cit.>. On the other hand, <cit.> find that the deep neural networks have enough complexity to fit an arbitrarily corrupted data, and a small geometric transformation may cause networks deteriorating in performance <cit.>. This complex and fragile nature of DNNs leads to a key problem, how to use the data distribution and network parameters to estimate the generalization ability of DNNs. Although several regularization techniques, such as dropout <cit.>, batch normalization <cit.>, and weight decay <cit.>, do improve the generalization performance of the over-parameterized deep models, <cit.> show that these regularizers cannot solve this problem either.

Consequently, several recent works <cit.> have started to address this question, proving that we can control the capacity of DNNs via different upper bounds based on the minimum margin. However, the generalization bounds based on analyses of model complexity and noise stability only focus on the minimum margin, which is based on the closest distance of the training points to the decision boundary. This notion is brittle and sensitive to outliers due to a lack of the entire margin distribution information. 
<cit.> propose a measure by looking at the entire distribution of distances, and conduct empirical studies on how well it can predict the generalization gap. However, how the margin distribution information affects the generalization error of the model still needs more specific theoretical analysis, which will lead us to optimize the entire margin distribution appropriately.

The margin distribution has been shown to correspond to generalization properties in the literature on linear models and boosting algorithms, <cit.> first introduce it to explain the phenomenon that AdaBoost seems resistant to overfitting problem. 
Two years later, <cit.> indicates that the minimum margin is crucial for margin theory. <cit.> conjecture that the margin distribution, rather than the minimum margin, plays a key role. The debate has been finally solved by <cit.> who theoretically proved that the AdaBoost process attempts to maximize the margin mean and minimize margin variance simultaneously; highlighting for the first time that two factors rather than a single factor are crucial for margin theory. These two factors are the first and second-order statistics describing the margin distribution, while in most cases the higher-order one is less useful. Their result successfully explains why AdaBoost seems resistant to overfitting: even when the training error reaches zero, the margin mean can be increased and/or the margin variance can be decreased further, leading to the improvement of generalization performance; it also discloses that AdaBoost will finally overfit: when the margin mean cannot be increased and margin variance cannot be decreased further. The long march of the theoretical exploration of AdaBoost is summarized in <cit.>, and <cit.>’s result has been theoretically confirmed by <cit.>. Inspired by <cit.>’s finding, powerful learning machines can be built by maximizing the margin mean and minimizing margin variance simultaneously, rather than simply maximizing the minimum margin like in traditional large-margin machines.
<cit.> propose the optimal margin distribution machine (ODM) for binary classification. In <cit.>, ODM is extended to many forms.

In this paper, we study a d-layer feed-forward network with ReLU activation functions. Our theoretical result states that the statistics of margin distribution play an important role in the generalization estimation rather than the traditional minimum margin. This result is consistent with the previous results on boosting and linear algorithms <cit.>. It also inspires us to understand the similarities between deep learning and traditional machine learning from the perspective of margin distribution. Specially, we propose a new loss function to optimize the statistics-based measure in the theoretical results. A strong correlation between generalization and our measure is empirically shown by studying a wide range of network structures trained on the MNIST, CIFAR-10 and ImageNet datasets.
The detailed contributions of this paper are as follows:



  
PAC guarantee Our bound shows that we can restrict the capacity of deep nets by the ratio of second- to first-order statistic of margin distribution at the last layer. Compared with the existing results based on minimum margin <cit.>, our bound contains more information on the entire margin distribution to estimate the generalization error. Moreover, the empirical evaluation shows that optimizing the margin ratio can control the model capacity to alleviate the overfitting risk. 



  
Optimization Inspired by our theoretical result, we encourage DNNs to optimize the margin ratio for better generalization performance. Therefore, we propose a new approach called margin distribution Networks (mdNet), which utilizes a convex margin distribution loss function to optimize the first- and second-order statistics of margin. Moreover, we empirically evaluate our loss function on deep neural networks across different image datasets and model structures. Specifically, empirical results demonstrate the effectiveness of the proposed method in learning tasks with limited training data.


The rest of paper is organized as follows. The related work is introduced in Section <ref>. Some notations are introduced in Section <ref>. In
Section <ref>, we present a generalization bound leveraging margin distribution rather than minimum margin and demonstrate that the ratio of the margin standard deviation to the expected margin is the key to control the model capacity. Section <ref> list the detailed proofs for our theorems and lemmas. In Section <ref>, we formulate the convex loss function to optimize the margin ratio. Section <ref> reports our experimental studies and empirical observations.  Finally, Section <ref> concludes with future work.




§ RELATED WORK
 

Recently, margin-based deep learning algorithms have developed rapidly. <cit.> use the triplet loss to encourage a distance constraint similar to the contrastive loss. Similarly, <cit.> enhance the supervision of the learned filters by incorporating the information of class labels in the training data and learn the filters based on the idea of multi-class linear discriminant analysis (LDA) for classification task. <cit.> propose a generalized large-margin softmax loss which explicitly encourages intra-class compactness and inter-class separability in the learned representation space. It would be interesting to theoretically study feature space transformation which might be a key to understanding mysteries behind the successes of deep neural networks <cit.>.
Since <cit.> and <cit.> associate the generalization of deep neural networks with the minimum margin, a line of work establishes that first-order methods can automatically maximizing the minimum margin in the settings of logistic regression <cit.>, deep linear networks <cit.>, and symmetric matrix factorization <cit.>. However, <cit.> point that how to extend these results to non-linear neural networks remains unclear. Recently, <cit.> propose to understand the model dynamics from the perspective of control theory. Another line of algorithm-dependent analysis of generalization <cit.> uses stability of specific optimization algorithms that satisfy certain generic properties
like convexity, smoothness, etc. Specially, <cit.> make a connection between the sharpness of the solution obtained using the SGD algorithm and its ability to generalize well. The notion of sharpness corresponds to robustness to adversarial perturbations of parameters. Furthermore, <cit.> draw a connection to the PAC-Bayesian theory for sharpness. The margin distribution measure presented in this paper is closely related to sharpness <cit.>, because we use the statistics of the margin distribution to theoretically describe the value of the allowable perturbation. Compared with the sharpness measure which is difficult to optimize, the margin distribution measure proposed in this paper is easy to calculate, and can be directly optimized through the SGD algorithm by designing a convex loss function. Recently, <cit.> present abundant empirical evidence to validate that the generalization in deep learning can be estimated from the margin statistics. In addition, the relevant theories of domain adaptation <cit.> are also used to improve the generalization capability of deep learning <cit.>. Domain generalization cannot see existing training source domains during training. This makes domain generalization more challenging than domain adaptation but more realistic and favorable in practical applications <cit.>.



§ NOTATIONS
 

Consider the multi-class task with feature domain 𝒳 and label domain 𝒴. Let 𝒟 be an unknown (underlying) distribution over 𝒳×𝒴. A training set S={(_1,y_1),… ,(_m,y_m)} and a validation set S'={(_1,y_1),…,(_m',y_m')} are drawn identically and independently  according to 𝒟. We denote a labeled sample as (,y)∈𝒟. 

Let f_𝒳_B,n→𝒴' be the function represented by a d-layer feed-forward network with parameters 
    ={_1,_2,…,_d}
 and output domain 𝒴'=ℝ^k. The entire network can be formulated as 
    f_()=_dϕ(_d-1ϕ(…ϕ(_1))),
 where ϕ is the ReLU activation function and let ρ be an upper bound on the number of output units in each layer. 

We can define the fully connected networks (FNNs) recursively: 
    ^1=_1  and  ^i=_iϕ(^i-1),
 where ^i denotes the output of the i-th layer. 

The predicted label is denoted by 

    h()=_j f_,j()∈ℋ,

where h  𝒳→𝒴 is a map from the feature domain to the label domain and f_,j is the j-th element of the score vector. 

In the multi-class setting <cit.>, the label associated to point  is the one resulting in the largest score h()=max_if_,i(). This naturally leads to the following definition of the margin γ_h(,y) of the function h at a labeled example (,y): 

    γ_h(x, y)=f_,y(x)-max _j ≠ y f_,j(x).

Thus, h misclassifies (,y) iff γ_h(,y)<0.



§ MARGIN DISTRIBUTION RATHER THAN MINIMUM MARGIN
 

In Subsection <ref>, we list error-resilience assumptions that will be used. In Subsection <ref>, we introduce the existed results based on the minimum margin. In Subsection <ref>, we present our main results based on the entire margin distribution. 



 §.§ Error-resilience assumptions


Here we formalize the error-resilience properties for deep neural networks. <cit.> show that if we inject a scaled Gaussian noise to the input of deep nets, as it propagates up, the noise has rapidly decreasing effect on higher layers. This fact implies compressibility of deep nets, i.e., low rank of parameters' matrix. The empirical version of noise-sensitivity parameters are first proposed by <cit.>. It inspires us to bound the perturbation caused by Gaussian noise with the validation-based version of noise-sensitivity parameters below. 


	(Layer Cushion). The layer cushion of layer i is defined to be largest number μ_i such that for any validation data ∈ S':
	
    μ_i_i_Fϕ(^i-1)_2 ≤^i_2.




	(Interlayer Cushion). For any two layers i<j, we define the interlayer cushion μ_i,j, as the largest number such that for any validation data ∈ S':
	
    μ_i,jJ_^i^i,j_Fϕ(^i-1)_2  ≤^j_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}. For any two layer i<j, denote by M^i,j the operator for composition of these layers and J_^i,j be the Jacobian matrix (the partial derivative) of this operator at input . Therefore, we have ^j=M^i,j(^i). Furthermore, since the activation functions are ReLU (hence piece-wise linear), we have M^i,j(^i)=J_^i^i,j^i.


	(Interlayer Smoothness). For any two layers i<j, we define the interlayer smoothness ρ_δ as the smallest number such that with probability 1-δ over noise η for any validation data ∈ S':
	
    M^i, j(^i+η)-J_^i^i, j(^i+η)≤η^j/ρ_δ^i


For a single layer, ρ_δ captures the ratio of input/weight alignment to noise/weight alignment. <cit.> show that the interlayer smoothness is indeed good: 1/ρ_δ is a small constant.

The next two conditions qualify a common appearance: if the input in the activation and margin calculations is well-distributed and the calculations do not correlate with the magnitude of the input, then one would expect that, the effect of applying activation at any layer and margin at last layer is to decrease the norm of the vector by at most some small constant factor, i.e., c and α.


	(Activation Contraction). The activation contraction c is defined as the smallest number such that for any layer i and any validation data ∈ S':
	
    cϕ(^i)_2 ≥^i_2.




	(Margin Contraction). The margin contraction α is defined as the smallest number such that for any validation data ∈ S':
	
    αγ_h(,y)_2 ≥^d_2.



In this paper, we only use the noise-sensitivity parameters in Assumptions <ref> - <ref> as descriptions of error-resilience properties, from which the margin distribution term of our bound is derived. Therefore, we just need estimate these parameters based on validation data to show the magnitude of our bound rather than optimizing these parameters in the training process like <cit.> did. 



 §.§ Existed results


In the deep learning theory community, great efforts have been made to explain why over-parameterized deep neural networks can success, which is contrary to the classical VC dimension analysis <cit.>. <cit.> and <cit.> made an important stride by showing minimum margin based bounds for multi-layer neural networks. These bounds do not depend directly on the number of parameters of the network but depends on the normalized minimum margin. Theorem <ref> provides a unified description of these bound. The only difference between them lies in the value of constants and the type of norms.

<cit.>
	For any d,ρ>0 and _2≤ B, let f_:𝒳→ℝ^k be a d-layer feed-forward network with ReLU activation. Then, for any δ > 0, with probability ≥ 1-δ over a training set of size m, for any ={_1,_2,…,_d}, we have:
	
    L_0(f_) ≤L_γ(f_)+𝒪(√(B^2 d^2ρln (d h) Π_i=1^d_i_2^2∑_i=1^d_i_F^2/_i_2^2+lnd m/δ/γ^2 m)),

	where L_0(·) is the 0-1 loss, L_γ(·)=_S[γ_h(,y) ≤γ] is the empirical estimation of γ-margin loss and 𝒪(·) describes the limiting behavior of a function.


Based on this margin theory view, <cit.> provide an improved bound by considering the compressibility of deep nets as follows:

<cit.>
	For any d>0, let f_:𝒳→ℝ^k be a d-layer feed-forward network with ReLU activation. Then, for any δ > 0, with probability ≥ 1-δ over a training set of size m, for any ={_1,_2,…,_d}, we have:
	
    L_0(f_) ≤L_γ(f_)+𝒪(√(c^2 d^2max _∈ Sf_()_2^2∑_i=1^d1/μ_i^2μ_i→^2/γ^2 m))

	where μ_i,μ_i →,c,α are layer cushion, interlayer cushion, activation contraction and interlayer smoothness defined in Assumptions <ref>, <ref>, <ref> and <ref> respectively


These existed results follow the traditional margin theory, so they only focus on the minimum margin γ. Because they lack the description of the entire margin distribution, they can only take the minimum margin γ as the optimization target to improve the generalization performance. These methods ignore the information of the entire margin distribution. In the next subsection, we expect to prove a bound related to the entire margin distribution, so as to inspire us to directly optimize margin distribution for improving the generalization performance for DNNs.




 §.§ Main results



We begin with an intuitive comparison of the minimum margin based classifier and the margin distribution based classifier. Figure <ref> shows that maximizing the minimum margin will make the classifier easy to be misled by a small number of samples, thus ignoring the distribution information of samples, while the margin distribution based classifier considers the mean and variance of samples and generalizes better. 



In order to utilize the mean and variance information into the theoretical analysis, we design a new margin loss, which uses r to adjust the mean of margin and θ to adjust the variance of margin. For any parameter r>θ>0, we can define a (r,θ)-margin distribution loss function (see Figure <ref>), which penalizes h with a cost of 1 when it predicts  with a margin smaller than r-θ, but also penalizes h when it predicts  with a margin larger than r+θ. The margin distribution bound is presented in terms of this loss function, which is formally defined as follows.
(Expected margin distribution loss function). 
	 For any r>θ>0, the (r,θ)-margin loss is the function L_r,θ(·) defined for all h∈ℋ as:
	
    L_r,θ(h) = _𝒟[γ_h(,y) ≤ r - θ] + _𝒟[ γ_h(,y)   > r + θ] .


Intuitively, our (r,θ)-margin distribution loss function looks for a classifier h which forces as many data points as possible into the zero-loss band (r-θ≤γ_h(,y)< r+θ). Therefore, we let r≃𝔼_𝒟 [γ_h(,y)], θ^2≃_𝒟[γ_h(,y)], which implies that the expected margin is larger than the standard deviation. Actually, θ just need to be a second-order statistic, so we can re-scale θ^2=a·_𝒟[γ_h(,y)] to satisfy r>θ. In this way, the (r,θ)-margin distribution loss is a surrogate loss function.
In particular, for r = θ and θ→∞, the zero-loss band is the positive area (γ_h(,y)>0) and L_r,θ corresponds to the 0-1 loss L_0. Let L_r,θ(f_) be the empirical estimate of the expected margin distribution loss. So we also denote the expected risk and the empirical risk as L_0(f_) and L_0(f_), which are bounded between 0 and 1. 

We begin with bounding the change of output caused by the noise on the classifier  with the noise-sensitivity parameters and the statistics of margin distribution:


	Let f_𝒳→ℝ^k be a d-layer network. For any d > 0,
	and vec({_i}_i=1^d)=(_1,_2,…,_d) is a vector of perturbation parameters with _i=β_i_i_F, and β=vec({β_i}_i=1^d)=(β_1,β_2,…,β_d) is a vector of random vectors with 𝔼[ββ^⊤]=σ^2, the change of the output of the network can be bounded with a fixed probability (δ=1/2):
	
    max_∈𝒳|f_+()-f_()|_2^2 ≤𝒪(
    		∑_i=1^ddα^2c^2σ^2(r+θ)^2/μ_i^2μ_i →^2).



The result shows that the perturbation caused by  increases with the variance σ^2 is related to the outermost edge of margin distribution r+θ, that is, the right green dotted line in Figure <ref>. The next Lemma shows that we can bound the generalization gap through a Kullback-Leibler divergence term, if we can guarantee that the perturbation caused by  is smaller than r-θ/8 with a constant probability. Therefore, the allowable value of σ^2 under the (r,θ)-margin distribution assumption is consistent with the intuitive understanding (see Figure <ref>), i.e., σ^2∝r-θ/r+θ=1-λ/1+λ, where λ=θ/r∈(0,1). When the margin distribution is more compact (smaller λ), the larger noise σ^2 can be allowed, that is, it is not easy to cause misclassification. When the margin distribution is more loose (larger λ), even a small noise have misclassification risk.


	Let f_:𝒳→ℝ^k be any predictor with parameters , 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 , and any random perturbation   _[ max_∈𝒳| f_+() - f_() |_2 < r-θ/8] ≥1/2, we have:
	
    L_0(f_) ≤L_r,θ(f_) +  4√((+‖ P) + ln6m/δ/m-1).



The detailed proof is presented in Section <ref>. This Lemma improves the result of <cit.>, especially using two parameters θ, r to describe the entire margin distribution instead of using one parameter γ to describe the minimum margin. Based on this result, we can derive the following generalization bound, with proof deferred to Section <ref> showing that the Kullback-Leibler divergence term is inversely proportional to σ^2.


	For any d,ρ>0, let f_:𝒳→ℝ^k be a d-layer feed-forward network with ReLU activation. Then, for any δ > 0, with probability ≥ 1-δ over a training set of size m, for any , we have:
	
    L_0(f_) ≤L_r,θ(f_) +
    		𝒪( √((1+λ/1-λ)^2(∑_i=1^ddα^2c^2/μ_i^2μ_i →^2)+ln6m/δ/m)).

	where the margin ratio is defined by λ=θ/r.


We prove an upper bound on generalization gap related to the margin ratio term, where λ is a parameter denoting the ratio of the margin standard deviation θ to the expected margin r over the underlying distribution, and the error-resilience term relies on the noise sensitivity <cit.> quantified by μ_i,μ_i →,c,α (See Assumptions <ref>, <ref>, <ref> and <ref>). 
Theorem <ref> states that the entire margin distribution has much leverage in generalization performance rather than the minimum margin.
Specifically, restricting a smaller λ (larger r and smaller θ) can effectively control the capacity of models, so as to reduce the risk of overfitting. 
It inspires us that optimizing margin distribution can get better generalization performance than the traditional minimum margin maximization algorithm.















  
Discussion. The main difference between <cit.> and our paper: <cit.> proved that the generalization performance of deep neural network is related to the sparsity of its parameters, focusing on how to compress the parameters of the trained model. Our paper studies the relationship between DNN generalization performance and margin distribution under the condition that DNN parameters is sparsity, focusing on optimizing margin distribution during training. Figure <ref> shows that the improvement of our bound relative to <cit.> (the shaded part in the figure) is because the margin ratio will gradually decrease during the training process. The main difference between <cit.> and our paper: <cit.> conjectured that the generalization performance of DNN may be related to the interval distribution. The correlation between generalization and R^2 <cit.> is calculated experimentally, and no theoretical proof is given. Our paper proves theoretically that the generalization performance of DNNs can be bound by the margin ratio and gives the improved algorithm.






§ PROOFS
 

In this section, we provide the detailed proofs for the main theorem and lemmas. First, we present a useful lemma as follows:


	
	Let 𝒬 be a probability distribution over the reals. For any random variable v,v_1,v_2,…,v_m'∼𝒬 identically and independently (i.i.d.), we have
	
    _v∼𝒬[v≥max_v_1,…,v_m'∼𝒬{v_1,v_2,…,v_m'}]= 1/m'+1.



Proof of Lemma <ref>: Let the Cumulative Distribution Function (CDF) and Probability Density Function (PDF) of random variable v be F(x) and f(x), and we denote the maximum of a set of m' random variables by v^(m')=max_v_1,…,v_m'∼𝒬{v_1,v_2,…,v_m'}. Then


    _v_1,…,v_m'∼𝒬[v^(m')≤ x]
    
    	=   _v_1,…,v_m'∼𝒬[(v_1≤ x)∧…∧ (v_m'≤ x )]
    
    	=   _𝒬[v_1≤ x]×…×_𝒬[v_m'≤ x]
    	=F^m'(x).


In other word, the CDF and PDF of the minimum v^(m') are F^m'(x) and m'F^m'-1(x)f(x). Then we can use the minimum value of the sample's set to bound the random variable v with a probability m'/m'+1, which converges to 1 with a rate 𝒪(1/m'):


    _v,v_1,…,v_m'∼𝒬[v≤ v^(m')]
    
    	=   _v,v_1,…,v_m'∼𝒬[v- v^(m')≤ 0]
    
    	=   ∬_x≤ yf(x)F^m'-1(y)f(y)  x  y
    
    	=   ∫_-∞^+∞m'F^m'-1(y)f(y)  y ∫_-∞^y f(x)  x
    
    	=   ∫_-∞^+∞m'F^m'(y)f(y)  y
    
    	=   m'F^m'+1(y).|_-∞^+∞-∫_-∞^+∞m'^2F^m'(y)f(y)  y .


According to Eq. (<ref>) and Eq. (<ref>), we have


    _v,v_1,…,v_m'∼𝒬[v≤ v^(m')]=m'/m'+1.






 §.§ Proof of Lemma <ref>


We begin with a lemma as follows:


	For any layer i, the point-wise compressibility of the layer-wise parameters can holds with a probability 1-1/m'+1 over ∈𝒟 as follows:
	
    μ_i_i_Fϕ(^i-1)_2    ≤^i_2,
    μ_i,jJ_^i^i,j_Fϕ(^i-1)_2     ≤^j_2,
    M^i, j(^i+η)-J_^i^i, j(^i+η)   ≤η^j/ρ_δ^i
    
    		cϕ(^i)_2    ≥^i_2,
    αγ_h(,y)_2    ≥^d_2,

	where m' is the size of the validation set.


Proof of Lemma <ref>: According the independence between S and S', we can regard the noise-sensitivity parameters 1/μ_i,1/μ_i,j, c and α as random variables over reals relying on the randomness of variable ∈ S'. Then, the cushion parameters defined in Assumptions <ref>, <ref>, <ref>, <ref> and <ref> can be interpreted as choosing the maximum of multiple independent samples. We first prove Lemma <ref> on the tail of a random variable v∼𝒬 by choosing the maximum of multiple independent samples of the random variable. Specifically, using the following simple lemma based on the distribution of the maximum, we can guarantee the point-wise compressibility of the learned parameters over the underlying data distribution 𝒟 with a high probability by calculating the maximum of the empirical dataset, i.e., 1/μ_i, 1/μ_i,j, c and α. 




Proof of Lemma <ref>: First, we need to bound the perturbation of linear operator caused by injecting a scaled Gaussian noise =β_F, 𝔼[ββ^⊤]=σ. For any fixed vectors ,, we have

    𝔼_β^⊤ (+)  - ^⊤_2= 𝔼_β_2^⊤^⊤_2
       = 𝔼_β_F_2^⊤ββ^⊤_2 
       = σ_F_2_2.

According the Markov inequality, we have

    _β[ ^⊤ (+)  - ^⊤_2 ≥σ√(d)/√(δ)_F_2_2]
       ≤σ^2_F^2 ^2_2^2_2/(dσ^2/δ)_F^2^2_2^2_2 =δ/d.


Now, we will bound the perturbation of the d-layer deep nets by induction. For any layer i≥0, let x^j be the output at layer j with original net and _i^j be the output at layer j if the weights _1,…,_i in the first layers are replaced with _1+_1,…,_i+_i. The induction hypothesis is then following:

Consider any 0<ϵ≤1, the following is true with probability 1-iδ/d over _1+_1,…,_i+_i for any j≥ i:

    _i^j-^j_2^2 ≤∑_l=1^ic^2 d σ^2/δμ_l^2μ_l →^2^j_2^2.


For the base case i = 0, since we are not perturbing the input, the inequality is trivial. Now assuming that the induction hypothesis is true for i-1, we consider what happens at layer i.

    _i^j-^j_2^2   =(_i^j-_i-1^j)+(_i-1^j-^j)_2^2
       ≤2(_i^j-_i-1^j)_2^2+2_i-1^j-^j_2^2


The second term in Eq. (<ref>) can be bounded by ∑_l=1^i-1c^2  σ^2/μ_l^2μ_l →^2^j_2^2 by induction hypothesis. Therefore, it is enough to show that the first term in Eq. (<ref>) is bounded by c^2  σ^2/μ_i^2μ_i →^2^j_2^2. We decompose the error into two error terms one of which corresponds to the error propagation through the network if activation were fixed and the other one is the error caused by change in the activations:

    (_i^j-_i-1^j ) 
       = M^i, j ((_i+_i) ϕ (^i-1 ) )-M^i, j (_i ϕ (^i-1 ) ) 
       = M^i, j ((_i+_i) ϕ (^i-1 ) )-M^i, j (_i ϕ (^i-1 ) )
         +J_^i^i, j (^iϕ (^i-1 ) )-J_^i^i, j (^iϕ (^i-1 ) ) 
       ≤J_^i^i, j (^iϕ (^i-1 ) ) + M^i, j ((_i+_i) ϕ (^i-1 ) )
       -M^i, j (_i ϕ (^i-1 ) )-J_^i^i, j (^iϕ (^i-1 ) ) .


The first term in Eq. (<ref>) is bounded by:














    J_^i^i, j^iϕ (^i-1 ) _2
       ≤ (√(d)σ/√(6δ)) J_^i^i, j_2 _i _Fϕ (^i-1 ) _2 
       ≤ (√(d)σ/√(6δ)) J_^i^i, j_2 _i _F^i-1_2
       ≤ (√(d)σ/√(3δ)) J_^i^i, j_2 _i _F^i-1_2
       ≤ (c√(d)σ/√(3δ)) J_^i^i, j_2 _i _Fϕ (^i-1 ) _2
       ≤ (c√(d)σ/√(3δ)μ_i) J_^i^i, j_2 _i ϕ (^i-1 ) _2
       ≤ (c√(d)σ/√(3δ)μ_iμ_i →) ^j_2.


where Equation (<ref>) is bounded by Eq. (<ref>), Equation (<ref>) is bounded by Lipschitzness of the activation function, Equation (<ref>) is bounded by inductive hypothesis, Equation (<ref>) is bounded by activation contraction, Equation (<ref>) is bounded by layer cushion, and Equation (<ref>) is bounded by interlayer cushion.

The second term in Eq. (<ref>) can be bounded as:

    M^i, j ((_i+_i) ϕ (^i-1 ) )-M^i, j (_i ϕ (^i-1 ) )
         -J_^i^i, j (^iϕ (^i-1 ) ) _2
       =  (M^i, j-J_^i^i, j ) ((_i+_i) ϕ (^i-1 ) )
         - (M^i, j-J_^i^i, j ) (_i ϕ (^i-1 ) ) _2
       =  (M^i, j-J_^i^i, j ) ((_i+_i) ϕ (^i-1 ) ) _2
         +  (M^i, j-J_^i^i, j )(_i ϕ(^i-1)) _2.


Both terms in Eq. (<ref>) can be bounded using Assumption <ref>. By notations we find ^iϕ(^i-1)=x̂_i-1^i. By induction hypothesis, we have that ^iϕ(^i-1)-^i_2^2 ≤∑_l=1^i-1c^2 d σ^2/δμ_l^2μ_l →^2^i_2^2. Now by interlayer smoothness property, (M^i, j-J_^i^i, j)(^iϕ(^i-1)_2^2 ≤∑_l=1^i-1c^2 d σ^2/δμ_l^2μ_l →^2^j/ρ_δ≤(∑_l=1^i-1c^2d σ^2/δμ_l^2μ_l →^2 )^j_2^2/(3d)≃i-1/3dc^2 d σ^2/δμ_i^2μ_i →^2^j_2^2. Similar to this term, (M^i, j-J_^i^i, j)((^i+_i) ϕ(^i-1))≤(∑_l=1^ic^2 dσ^2/δμ_l^2μ_l →^2 )^j/(3d)≃i/3dc^2 d σ^2/δμ_i^2μ_i →^2^j_2^2. Putting everything together completes the induction with probability at least 1-δ (if i=d).

Instead of assuming that the input domain 𝒳 is bounded by a constant B, we assume that the input boundary is relative to the expected value which implies the data-distribution information: max_^d_2 ≤𝒪(𝔼_𝒟^d_2). According to the margin contraction property, we can use the first- and second-statistics of the margin in the last layer 𝔼_𝒟 [γ_h(,y)]=r, _𝒟[γ_h(,y)]=θ^2 to bound the perturbation instead of the worst situation:

    max_^d_2^2    ≤𝒪(𝔼_𝒟^d_2^2) ≤𝒪(α^2 𝔼_𝒟γ_h(,y)_2^2) 
       ≤𝒪(α^2(r^2+θ^2)) ≤𝒪(α^2(r + θ) ^2)


Connecting these two inequalities we prove that the equality holds with a probability at least 1/2:

    |f_+()-f_()|_2^2 ≤𝒪(
    	∑_i=1^ddα^2 c^2(r+θ)^2σ^2/μ_i^2μ_i →^2).







 §.§ Proof of Lemma <ref>


Proof of Lemma <ref>:
Let '=+, Let 𝒮_ be the set of perturbations with the following property:

    𝒮_⊆{^'|max _∈𝒳| f_^'()-f_()|_2<r-θ/8√(ρ)},

then we will have max _∈𝒳| f_^'()-f_()|_∞<√(ρ)max _∈𝒳| f_^'()-f_()|_2<r-θ/8.

Let q be the probability density function over the parameters '. We construct a new distribution Q̃ over predictors f_ where  is restricted to 𝒮_ with the probability density function:

    q̃()=1/Z
    		q()    ∈𝒮_
     0     otherwise

According to the lemma assumption, we have Z=ℙ[^'∈𝒮_] ≥1/2. Therefore, we can bound the change of the margins for any instance:

    max _i, j ∈[k], ∈𝒳|(|f_()[i]-f_()[j]|)-(|f_()[i]-f_()[j]|)|<r-θ/2

Here we define a perturbed loss function as:

    L'_r,θ(h) = _𝒟[γ_h(,y) ≤r - θ/2] + _𝒟[ γ_h(,y)   > r + θ + r - θ/2] .

We can get the following:

    L_0(f_) ≤ L'_r,θ(f_) 
       L'_r,θ(f_) ≤L_r,θ(f_)

Finally, using the proof of <cit.>, with probability 1-δ over the training set we have:

    L_0(f_)    ≤𝔼_[L'_r,θ(f_)] 
       ≤𝔼_[L'_r,θ(f_)]+2 √(2(( P)+ln2 m/δ)/m-1)
       ≤L_r,θ(f_)+2 √(2(( P)+ln2 m/δ)/m-1)
       ≤L_r,θ(f_)+4 √((^' P)+ln6 m/δ/m-1)








 §.§ Proof of Theorem <ref>

Proof of Theorem <ref>:
Since Lemma <ref> proves that the perturbation caused by random vector  is bounded by a term relative to the variance σ, we can preset the value of σ to make the random perturbation satisfy the condition for Lemma <ref>. Bounding the Kullback-Leibler divergence term by _2^2/_2^2 in PAC-Bayesian theorem, we can attain the generalization bound based on a specific margin distribution.

The proof involves chiefly two steps. In the first step we bound the maximum value of perturbation of parameters to satisfy the condition that the change of output restricted by hyper-parameters of margin r and θ, using Lemma <ref>. In the second step we prove the final margin generalization bound through Lemma <ref> with the value of Kullback-Leibler divergence term calculated based on the bound in the first step.

    |f_+()-f_()|_2^2    ≤𝒪(
    	∑_i=1^ddα^2c^2(r+θ)^2σ^2/μ_i^2μ_i →^2)
       = (r-θ/8√(ρ))^2

We can derive σ=r-θ/8α cd√(ρ)(r+θ)√(∑_i=1^d1/μ_i^2μ_i →^2) from the above inequality. Naturally, we can calculate the Kullback-Leibler divergence in Lemma <ref> with the chosen distributions for P∼𝒩(0,σ^2𝐈).

    (+P)   ≤||^2/2||^2|ηη^⊤|^2=1/2σ^2
       ≤𝒪( (r+θ)^2/(r-θ)^2∑_i=1^ddρα^2c^2/μ_i^2μ_i →^2)
	
Put it in Lemma <ref> and let λ=θ/r, with probability at least 1-δ and for all  such that, we have:

    L_0(h) ≤L_r,θ(h) + 𝒪( √((1+λ)^2/(1-λ)^2∑_i=1^ddρα^2c^2/μ_i^2μ_i →^2+lndm/δ/m)).





§ OPTIMIZING MARGIN DISTRIBUTION MEASURE


The generalization theory shows the importance of optimizing the margin distribution ratio λ. The result inspires us to find a margin distribution band (r-θ≤γ_h(,y)<r+θ) containing as many training samples as possible to minimize the empirical estimate loss L_r,θ, but also a ratio λ=θ/r as small as possible to minimize the generalization gap L_0(h)-L_r,θ(h). This type of loss function was first proposed by <cit.> to optimize the first- and second-order statistics of margin distribution. We formulate a convex margin distribution loss function for DNNs:

(Convex margin distribution loss function).
	For a labeled sample (,y)∈𝒟, we denote its margin by γ_h which is defined as Eq. (<ref>). We define the margin distribution loss for networks (mdNet loss) as: 
	
    ℓ_r,θ,η(h(),y) =
    		(r-θ-γ_h)^2/(r-θ)^2   γ_h ≤ r - θ
    
    			0     r - θ < γ_h ≤ r + θ
    η (r + θ - γ_h)^2/(r + θ)^2   γ_h > r + θ,

	where r is the margin mean parameter, θ is the margin variance parameter and η is a parameter to trade off two different kinds of deviation (keeping the balance on both sides of the margin mean). Figure <ref> shows the shape of this convex loss function.


Equation (<ref>) will produce a square loss when the margin satisfies γ_h ≤ r-θ or γ_h ≥ r + θ. Therefore, our margin loss function will force the zero-loss band to contain as many sample points as possible. The ratio of hyper-parameters λ=θ/r can control the capacity measure, which implies our measure is dependent to our specific learning algorithm (loss function with specific hyper-parameters). Since our loss function aims at finding a decision boundary which is determined by the entire margin distribution, instead of the minority samples that have minimum margins, we name our method as margin distribution Networks (mdNet).




§ EXPERIMENTS
 

In Subsection <ref>, we introduce the configuration of datasets and models. In Subsection <ref>, We design an ablation experiment to verify the superiority of our method. In Subsection <ref>, we show the correlation between separability of representations and margin ratio via visualization. In Subsection <ref>, we design experiments to confirm that our method can control the capacity of deep nets. In Subsection <ref>, we discuss the influence of the different hyper-parameters on the test accuracy. 



 §.§ Configuration


Since our method only works on the loss function part of deep models and does not change the architecture of deep neural networks, we can verify the effectiveness of mdNet on the classic CNNs (convolutional neural networks) and image classification benchmark datasets. We consider the following architectures and datasets: a LeNet architecture for MNIST dataset <cit.>, an AlexNet architecture <cit.> for CIFAR-10 dataset <cit.> and a ResNet-18 architecture <cit.> for ImageNet dataset <cit.>. From the literature, these datasets come pre-divided into training and testing sets, therefore in our experiments, we use them in their original format. The loss functions used for comparison in the experiments are as follows: cross-entropy loss (abbr., xent), hinge loss and soft hinge loss. Hinge loss <cit.> and soft hinge loss <cit.> are loss functions specially proposed to optimize the minimum margin, both of them are inspired the traditional margin theory.

As for details about the architecture, we remove the weight decay <cit.>, dropout <cit.> and batch normalization (BN) <cit.> from all the models, because the batch normalization operation and weight decay will shift the data distribution. The notable dropout technique, in which some neurons are dropped from the DNNs in each iteration, can also be viewed as an ensemble method composed of different neural networks, with different dropped neurons <cit.>. It is hard to analyze the influence of the ensemble structure on the margin distribution, so we remove this technique in these architectures in the experiments except to understand the contribution of the components to the whole models in the ablation study.

For special hyper-parameters, including the expected margin parameter and margin variance parameter for mdNet loss model, and margin parameter for hinge loss model, we perform hyper-parameter search. We hold out 5000 samples of the training set as a validation set, and use the remaining samples to train models with different special hyper-parameters values on all datasets. As for the common hyper-parameters, such as learning rate and momentum, we set them as the default commonly used values in PyTorch <cit.> for all the models. We chose batch stochastic gradient descent as the optimizer. We run all the experiments on four K80 GPU machines. As for the influence of the different hyper-parameters on the test accuracy, we discuss it empirically in Subsection <ref>.

























 §.§ Ablation study
 

Since the optimization algorithm proposed in this paper only focuses on the improvement of loss function, we design an ablation experiment to study the performance of our proposed mdnet method and the traditional benchmark loss functions under different regularizations in Table <ref>. The mdNet loss outperforms the others consistently across different situations, no matter whether dropout, batch normalization or the entire dataset are used or not. The experiments are evaluated on three MNIST (LeNet), CIFAR-10 (AlexNet) and ImageNet (ResNet-18) datasets. Specifically, when the amount of training samples is small, the advantage of mdNet loss is significant. Moreover, the mdNet loss function can cooperate with both batch normalization and dropout, achieving the best performance in Table <ref>, which is highlighted in bold red text. Unlike dropout and batch normalization which lack solid theoretical grounds, the mdNet loss function is inspired by the margin distribution bound in Theorem <ref>, which guides us to find a suitable margin ratio to restrict the model capacity and alleviate the overfitting problem efficiently.




 §.§ Feature visualization
 

In this experiment, we use t-SNE method to visualize the learned representations on the last hidden layer. Figure <ref>, <ref> and <ref> plot the 2D t-SNE <cit.> embedding image on limited datasets, including MNIST (LeNet), CIFAR-10 (AlexNet) and 10-class ImageNet (ResNet-18). Consistently, we can find that the result of mdNet loss model is better than all the others, the distribution of samples which have the same label are more compact. To quantify the degree of separability of data distribution, we perform a variance decomposition on the data in the embedding space. By comparing the ratio of inter-class variance S_E to intra-class variance S_A in Figure <ref>, <ref> and <ref>, we see that the mdNet loss always attain the most separable distribution among these four loss functions. Moreover, the visualization result is consistent with the margin distribution ratio 1/λ of these four models, which means that optimizing the margin distribution (searching an appropriate margin ratio λ) is helpful to attain a good learned representation space. This representation features space can further alleviate the overfitting problem of deep learning, we verify empirically that a network trained with mdNet loss shows stronger clustering. Specially, Figure <ref>, <ref> and <ref> show the relationship between the margin ratio and test error. Moreover, Figure <ref> plots the test error of mdNet and the margin ratio across the different epochs. We can see that more compact margin distribution gets better prediction performance across different models and epochs. This exhibits that optimizing margin distribution can indeed improve the learning ability of deep nets.




 §.§ Controlling capacity
 

The first two experiments have demonstrated that our mdNet can outperform other classical loss functions and our method can learn a more separable feature representation, as the corresponding margin ratio is also smaller. However, it leads to the last question:

 Can smaller margin ratio reduce the capacity of models and accelerate the convergence of generalization gap?


Let's go back to the theoretical result obtained by Theorem <ref>. The generalization gap of the model is bounded by Λ_λ,/√(m), where the margin distribution measure Λ_λ,∝1+λ/1-λ determines the worse case of generalization gap when the number of samples are equal:

    Generalization Gap≤𝒪(Λ_λ,/√(m)).



Therefore, we design experiments to compare the empirical value of generalization gap with the increase of training samples under different loss functions. In Figure <ref>, it shows that the red dotted line representing the convergence curve of our method always convergences faster than the other lines under different datasets and models. It also demonstrates that our method can effectively control the capacity of the model by optimizing the margin distribution ratio, so that the trained model has better generalization performance.

Given a fixed number of samples m, we find that the worst case of generalization gap is proportional to the model capacity. When m is large enough, the scale factor 1/√(m) will be close to 0, and the difference of sample complexity is not significant. The advantage of optimizing margin distribution is relatively significant when √(m) is relatively small. Therefore, in the right of Figure <ref> (the ImageNet experiment), we specially truncate the most significant result of convergence rate (form 0.1‰ to 5‰ of training set), which shows that optimizing margin distribution can control the capacity of the model even on such a complex dataset.




 §.§ Influence of the hyper-parameters


Figure <ref> plots the 3D surface figure for the test accuracy on the MNIST, CIFAR-10 and ImageNet datasets varying with two hyper-parameter r and θ. It shows that the ratio 1/λ=r/θ (the lower surface with rainbow colors) increases with r increasing and θ decreasing. As for the test accuracy (the upper surface with warm-cool colors), we find that its trend is consistent with the ratio 1/λ. Therefore, the influence of the hyper-parameters demonstrates that our theoretical result. Within a certain range, getting a smaller ratio λ through specific optimization (the margin distribution loss function) will effectively reduce the size of the hypothesis set for deep nets (returned by the specific algorithm), so as to improve the generalization ability of the learned model. In other words, the test accuracy changes consistently with the ratio of hyper-parameters (an estimation of the ratio of margin distribution). The parameter η to trade off two different kinds of deviation (keep the balance on both sides of the margin mean) is always fixed to 0.1 in practice.




§ CONCLUSION
 

This paper proves generalization bound for deep neural networks by considering the margin distribution at the last layer instead of the minimum margin. The theoretical result inspires us to utilize a margin distribution loss function to improve the generalization performance of neural networks. Experimental results show that our method can effectively control the model capacity by optimizing the margin distribution measure, so that the trained model learns more separable representations and has better generalization performance. In future work, we will explore the effectiveness of regularization methods from a margin theory perspective.



§ ACKNOWLEDGEMENT

This research was supported by the National Science Foundation of China (61921006) and the Collaborative Innovation Center of Novel Software Technology and Industrialization. The authors would like to thank the anonymous reviewers for constructive suggestions, as well as Yi-Xiao He and Yi-He Chen for helpful discussions.












*









