Year: 2021

Abstract:
This paper discovers that the neural network with lower decision boundary (DB) variability has better generalizability. Two new notions, algorithm DB variability and ( , η)-data DB variability, are proposed to measure the decision boundary variability from the algorithm and data perspectives. Extensive experiments show significant negative correlations between the decision boundary variability and the generalizability. From the theoretical view, two lower bounds based on algorithm DB variability are proposed and do not explicity depend on the sample size. By Chebyshev’s inequality, we also prove two upper bounds of O (√ AV (fQ,D)/m(k − 1) ) and O ( 1 √ m + + η log 1 η ) based on algorithm and data DB variability, respectively. The algorithm DB variability upper bound is easier to calculate in practice, while the data DB variability upper bound relies on less assumptions. Moreover, the bounds do not explicitly depend on the network size, which is usually prohibitively large in deep learning.

text: This paper discovers that the neural network with lower decision boundary (DB) variability has better generalizability. Two new notions, algorithm DB variability and ( , η)-data DB variability, are proposed to measure the decision boundary variability from the algorithm and data perspectives. Extensive experiments show significant negative correlations between the decision boundary variability and the generalizability. From the theoretical view, two lower bounds based on algorithm DB variability are proposed and do not explicity depend on the sample size. By Chebyshev’s inequality, we also prove two upper bounds of O (√ AV (fQ,D)/m(k − 1) ) and O (
1√ m + + η log 1η
) based on algorithm
and data DB variability, respectively. The algorithm DB variability upper bound is easier to calculate in practice, while the data DB variability upper bound relies on less assumptions. Moreover, the bounds do not explicitly depend on the network size, which is usually prohibitively large in deep learning.

heading: 1 INTRODUCTION
text: Neural networks (NNs) have achieved significant success in vast applications (Krizhevsky et al., 2012; Vaswani et al., 2017). However, the advance of NNs is arduous to be characterized by canonical statistical hypothesis complexity, such as VC-dimension (Vapnik et al., 1994) or Rademacher complexity (Bartlett & Mendelson, 2002). Considering the intimate connection between low variance and significant performance in learning theory, we investigate decision boundaries (DBs) from the perspective of variability in this paper. For neural networks, the decision boundary variability is largely caused by (1) the randomness from the training algorithm, and (2) the training data. In this paper, they are measured by two new terms, algorithm DB variability and ( , η)-data DB variability, and networks with lower DB variability are proved to possess better generalization performance.
Algorithm DB variability measures the variability of DBs in different training repeats, and extensive experiments are conducted on CIFAR-10, and CIFAR-100 (Krizhevsky & Hinton, 2009) datasets to explore the factors influence algorithm DB variability. We visualize the trend of the algorithm DB variability with respect to (w.r.t.) different training strategies, training time, sample sizes, and label noise. The empirical results present the negative correlation between algorithm DB variability and the test accuracy in all scenarios, which suggests that the algorithm DB variability largely indicates the generalization of neural networks. From the theoretical view, two lower bounds and an upper bound of the generalization error are proved based on the algorithm DB variability. The upper bound has a rate of O (√ AV (fQ,D)/m(k − 1) ) , where AV (fQ,D) is the algorithm DB variability for
fQ on data generating distribution D, m is the sample size, and k is the number of classes. To present how the training data influences the decision boundary variability, the ( , η)-data DB variability is introduced by employing the η-subset to reconstruct decision boundaries with error (see Definition 5.1). If a decision boundary can be reconstructed by training on a smaller η-subset with a smaller reconstruction error , the decision boundary possesses smaller data DB variability. Moreover, an η- curve can be drawn by varying the value of η and numerically evaluating the label mismatch rate. The area under the η- curve could be a more elaborate indicator for the generalization of NNs because the curve contains richer information than the algorithm DB variability. An
O (
1√ m + + η log 1η
) generalization bound based on the ( , η)-data DB variability is established
theoretically to enhance the relationship between the generalization of NNs and DB variability.
Compared to the algorithm DB variability upper bound, the data DB variability bound does not depend on additional Assumption 2, while the algorithm DB variability is easier to calculate than data DB variability in practice. Moreover, in contrast to many existing generalization bounds based on hypothesis complexity (Bartlett et al., 2019; Golowich et al., 2018; Bartlett et al., 2017) that require access to the network weight, our generalization bounds based on DB variability only demand the network predictions and thus have advantages in empirically approximating the generalization bound in (1) black-model settings, where model parameters are unavailable; and (2) over-parameterized settings, where calculating the weight norm is of prohibitively high computing burden.

heading: 2 RELATED WORKS
text: Deep learning theory. Due to the bias-variance trade-off, model complexity faces a dilemma in conventional wisdom (Mohri et al., 2018). Recently, Zhang et al. (2021) reveal the surprising ability of neural networks in fitting noise, but the networks still have impressive generalization performance in practice. This gap between the well-known bias-variance trade-off and the universal approximation ability for NNs draws attention to numerous researchers (Belkin et al., 2019; Nakkiran et al., 2019). Many works attribute the success of NNs to the effectiveness of the stochastic gradient descent (SGD) algorithm (Bottou, 2010; Hardt et al., 2016; Jin et al., 2017). Some empirical studies also explain the decent performance of networks by uncovering their learning properties (Nakkiran et al., 2020; Jiang et al., 2021; He et al., 2021). For instance, neural networks tend to fit the low-frequency information first (Rahaman et al., 2019; Xu et al., 2019) and gradually learn a more complex function (Kalimeris et al., 2019) during the training procedure.
Decision boundaries and generalization. Recent studies attempt to understand neural networks from the aspect of decision boundaries (He et al., 2018; Karimi et al., 2019). Guan & Loew (2020) empirically show the negative correlation between the complexity of decision boundary and generalization performance. Mickisch et al. (2020) reveal the phenomenon that the distance from data to decision boundaries continuously decreases during the training procedure. More recently, researchers find that NNs only rely on the most discriminative or simplest features to construct the DBs (Ortiz-Jimenez et al., 2020; Shah et al., 2020). Instead, our approach is different from these former methods by considering decision boundary variability, which is empirically and theoretically shown to closely correlate with the generalization in neural networks.
Adversarial training and generalization. It has been shown that the adversarial examples, which are created by adding non-perceivable perturbation on the input data, can completely mislead the NNs (Szegedy et al., 2013; Goodfellow et al., 2014). To tackle this problem, adversarial training is proposed to improve the robustness of the NNs through continuous training on adversarial examples (Madry et al., 2017). Nevertheless, Su et al. (2018) and Zhang et al. (2019) show a trade-off between the robustness and the generalization performance of NNs.

heading: 3 PRELIMINARIES
text: We denote the training set by S = {(xi, yi), i = 1, . . . ,m}, where xi ∈ Rn, n is the dimension of input data, yi ∈ {1, . . . , k}, k is the number of classes, and m = |S| is the training sample size. We assume that (xi, yi) are independent and identically distributed (i.i.d.) random variables drawn from the data generating distribution D. Denote the classifier as fθ(x) : Rn → Rk, which is a neural network parameterized by θ. The output of fθ(x) is a k-dimensional vector and is assumed to be a discrete probability density function. Let f (i)θ (x) be the i-th component of fθ(x), hence∑k i=1 f (i) θ (x) = 1. We define T (fθ,x) = {i ∈ {1, · · · , k}|f (i) θ (x) = maxj f (j) θ (x)} to denote the set of predicted labels by fθ on x. Due to the randomness of the learning algorithm A, let Q(θ) = A(S) denote the posteriori distribution returned by the learning algorithm A leveraged on the training set S. Hence, we focus on the Gibbs classifier (a.k.a. random classifier) fQ = {fθ|θ ∼ Q}. 0− 1 loss is employed in this paper, and the expected risks in terms of θ and Q are defined as:
RD(θ) = E(x,y)∼D [I (y /∈ T (fθ,x))] (1)
and RD(Q) = E(x,y)∼DEθ∼Q [I (y /∈ T (fθ,x))] , (2) respectively. Here I(·) is the indicator function. Since the data generating distributionD is unknown, evaluating the expected risk RD is not practical. Therefore, it is a practical way to estimate the expected risk by the empirical riskRS , which is defined as:
RS(θ) = E(x,y)∼S [I (y /∈ T (fθ,x))] = 1
m m∑ i=1 I (yi /∈ T (fθ,xi)) (3)
RS(Q) = E(x,y)∼SEθ∼Q [I (y /∈ T (fθ,x))] = 1
m m∑ i=1 Eθ∼Q [I (yi /∈ T (fθ,xi))] , (4)
where (xi, yi) ∈ S and m = |S|.

heading: 3.1 DECISION BOUNDARY
text: If the output k-dimensional vector fθ(x) on the input example x has a tie, i.e., the maximum value of the vector is not unique, then x is considered to locate on the decision boundary of fθ. With this idea, the decision boundary can be formally defined as below: Definition 3.1 (decision boundary). Let fθ(x) : Rn → Rk be a classifier network parameterized by θ. Then the decision boundary of fθ is defined by
{x ∈ Rn|∃i, j ∈ {1, · · · , k}, i 6= j, f (i)θ (x) = f (j) θ (x) = maxq f (q) θ (x)} (5)
After defining the decision boundary, we have the following remark: Remark 1. (1) If an input example (x, y) is not located on the decision boundary of fθ, T (fθ,x) is a singleton, and we have
I (y /∈ T (fθ,x)) = I (y 6= T (fθ,x)) . (6) (2) If the input x is a boundary point, in practice, we randomly draw a label from the set T (fθ,x) as the prediction of fθ on x.

heading: 3.2 ADVERSARIAL TRAINING
text: Adversarial training (AT) is a popular strategy to enhance the adversarial robustness of neural networks against adversarial examples, which is generated through projected gradient descent (PGD) (Madry et al., 2018) in our empirical studies. More specifically, adversarial training can be formulated as solving the minimax-loss problem as follows:
min θ
1
m m∑ i=1 max ‖x′i−xi‖≤γ ` (fθ (x ′ i) , yi) , (7)
where γ is the radius to limit the distance between adversarial examples and original examples. Adversarial training can be considered to enlarge the minimum distances from training examples to decision boundaries to at least γ.

heading: 4 ALGORITHM DECISION BOUNDARY VARIABILITY
text: Due to the randomness of learning algorithms, there is no doubt that the parameters have a substantial variation when the network is repeatedly trained. However, do the decision boundaries in these repeated-training networks have a large discrepancy? With this question, we define the algorithm decision boundary variability (AV) to measure the variability of DBs caused by the randomness of algorithms in different training repeats. Definition 4.1 (algorithm decision boundary variability). Let fθ(x) : Rn → Rk be a classifier network parameterized by θ and let Q(θ) be the distribution over θ. Then, the algorithm decision boundary variability for fQ on D is
AV (fQ,D) = E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) 6= T (fθ′ ,x))] , (8)
where T (fθ,x) = {i ∈ {1, · · · , k}|f (i)θ (x) = maxj f (j) θ (x)}.
In the light of Definition 4.1, smaller algorithm DB variability AV (fQ,D) means that the network produces more stable DBs or converges to more similar DBs during different training repeats. The algorithm DB variability is also a good notion for the “entropy” of decision boundaries because it measures the decision uncertainty over the whole data generating distribution; we provide a detailed discussion in Appendix B.1 due to space limitation.

heading: 4.1 ALGORITHM DB VARIABILITY AND GENERALIZATION
text: To explore the relationship between the algorithm DB variability and generalization in neural networks, we conduct experiments with different network architectures and training strategies on CIFAR-10 and CIFAR-100. In detail, VGG-16 (Simonyan & Zisserman, 2014), ResNet-18 (He et al., 2016), and WideResNet-28 (Zagoruyko & Komodakis, 2016b) are optimized by standard, non-data-augmentation and adversarial training, respectively, until the training procedure converges. We clarify that basic data augmentation (crop and flip) (Zagoruyko & Komodakis, 2016a) is adopted in both standard and adversarial training, and only the basic data augmentation is considered in our experiments and analysis. Each training setting (dataset, architecture, training strategy) is repeated for 10 trials with different random seeds to estimate the parameter distribution Q(θ). As for simulating the data generating distribution, we trained two conditional BigGAN (Zhao et al., 2020), an advanced generative network architecture, to produce 100, 000 fake images for CIFAR-10 and CIFAR-100, respectively. Examples of fake images have been shown in Figure 1(a) and 1(b).
Through these generative fake images, we can estimate the algorithm DB variability w.r.t. these well-trained models. For each training setting, we plot both the average test accuracy and algorithm DB variability; see Figure 1(c). From the plots, we have several observations: (1) adversarial training dramatically decreases the test accuracy and promotes the algorithm DB variability compared to standard training. (2) data augmentation decreases the algorithm decision boundary variability by comparing the standard training and non-data-augmentation training. The reason is that the augmented images by cropping or flipping are still located on the data generating distribution, so data augmentation is considered to expand the size of the training set. Hence, the expanded training set can characterize longer or larger decision boundaries on the data generating distribution; (3) WideResNet has better test accuracy and lower algorithm DB variability than ResNet and VGG; and (4) there is a negative correlation between the test accuracy and the algorithm DB variability. Therefore, based on these findings, we propose the following conjecture:
Hypothesis 1. Neural networks with smaller algorithm decision boundary variability on the data generating distributions possess better generalization performance.
We then conduct experiments on the algorithm DB variability w.r.t. training time, sample size, and label noise to concrete this hypothesis.

heading: 4.2 ALGORITHM DB VARIABILITY AND TRAINING TIME
text: To investigate the relationship between algorithm DB variability and training time, we train 40 ResNet-18 with different initial learning rates of 0.1 and 0.01 on CIFAR-10 and CIFAR-100. Then, the algorithm DB variability and test error are calculated at each epoch; see Figure 2(a). From the plots, we can observe that (1) algorithm DB variability and test error share a very similar curve w.r.t. the training time; and (2) algorithm DB variability decreases during the training process. The decline of algorithm DB variability shows that the interpolation on examples reduces the variability of decision boundaries on data generating distribution. As shown in Figure 2(b), we collect the points of (algorithm DB variability, test error) from different epochs, and the scatter plots present a significant positive correlation between test error and the algorithm DB variability, and thus supports Hypothesis 1.

heading: 4.3 ALGORITHM DB VARIABILITY AND SAMPLE SIZE
text: We next investigate how sample size impacts the algorithm DB variability. 100 ResNet-18 are trained on five training sample sets of different sizes randomly drawn from CIFAR-10 and CIFAR100, while all irrelevant variables are strictly controlled. Then, the algorithm DB variability and test error are calculated in all cases; see Figure 3(a). From the plots, we have the following observations: (1) test error and algorithm DB variability share a very similar curve w.r.t. the training sample size; (2) larger sample size, which intuitively helps obtain a more smooth estimation of the decision boundary, also contributes to smaller algorithm DB variability; and (3) there is a significant positive correlation between test error and algorithm DB variability, which fully supports Hypothesis 1.

heading: 4.4 ALGORITHM DB VARIABILITY AND LABEL NOISE
text: Belkin et al. (2019); Nakkiran et al. (2019) show the surprising epoch-wise double descent of test error, especially with the existence of label noise. In this section, we explore the trend of algorithm DB variability when the label noise exists. We train 20 ResNet-10 for 500 epoch with a constant learning rate of 0.0001 on CIFAR-10 and CIFAR-100 with 20% label noise. We clarify that the noise labels remain unchanged during different training repeats, which is necessary to estimate the algorithm DB variability. Then, the average test error and algorithm DB variability are calculated at each training epoch, as shown in Figure 3(b). From the plots, we observe that: (1) test error and
algorithm DB variability still share a very similar curve w.r.t. the training time with the existence of label noise; and (2) the algorithm DB variability also undergoes an epoch-wise double descent during the training process, especially in the left panel of Figure 3(b), which implies that factors influence the generalization of networks can also have an influence on the algorithm DB variability. Hence, algorithm DB variability is an excellent indicator for the generalization ability of networks.

heading: 4.5 THEORETICAL EVIDENCE
text: In this section, we explore and develop the theoretical foundations for the algorithm decision boundary variability on data generating distributions.
Assumption 1. The decision boundary of the classifier network fθ on data generation distribution D is a set with measure zero. Corollary 1. Let fθ(x) : Rn → Rk be a classifier network parameterized by θ. If Assumption 1 holds for all θ ∼ Q, then, for all i ∈ {1, · · · , k}, we have
E(x,y)∼D [I(i ∈ T (fθ,x))] = E(x,y)∼D [I(T (fθ,x) = i)] (9)
and E(x,y)∼D [I(i /∈ T (fθ,x))] = E(x,y)∼D [I(T (fθ,x) 6= i)] . (10)

heading: 4.5.1 ALGORITHM DB VARIABILITY-BASED LOWER BOUNDS
text: Theorem 1 (lower bound on expected risk). Let fθ(x) : Rn → Rk be a classifier network parameterized by θ and let Q(θ) be the distribution over θ. Then, if Assumption 1 holds for all θ ∼ Q, we have
RD(Q) ≥ AV (fQ,D)
2 , (11)
where AV (fQ,D) = E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) 6= T (fθ′ ,x))] is the algorithm DB variability for fQ on data generating distribution D.
The proof is given in Appendix C.1. Theorem 1 provides a lower bound on the expected riskRD(Q) based on the algorithm DB variabilityAV (fQ,D), and the lower bound presents that the Gibbs classifier fQ possesses a significant expected risk when its algorithm DB variability is large. Moreover, when we consider the binary classification, i.e., k = 2, there is a tighter lower bound:
Theorem 2 (lower bound for binary case). Let fθ(x) : Rn → R2 be a binary classifier network parameterized by θ and let Q(θ) be the distribution over θ. Suppose the expected riskRD(Q) ≤ 12 and Assumption 1 hold for all θ ∼ Q, then we have
RD(Q) ≥ 1−
√ 1− 2AV (fQ,D)
2 . (12)

heading: 4.5.2 AN ALGORITHM DB VARIABILITY-BASED UPPER BOUND
text: Before we present the upper bound based on the algorithm DB variability, let us introduce the assumption used in this section.
Assumption 2.
E(x,y)∼DE2θ∼Q [I (y /∈ T (fθ,x))] ≤ 2
k + 1 RD(Q), (13)
where i ∈ {1, 2, · · · , k} and k is the number of potential categories.
With Assumption 2, we can derive the upper bound on the variance of risk:
Lemma 1 (upper bound on risk variance). Let fθ(x) : Rn → Rk be a classifier network parameterized by θ and let Q(θ) be the distribution over θ. Suppose Assumption 1 and 2 hold, then we have
Var(x,y)∼D [Eθ∼Q [I (y /∈ T (fθ,x))]] ≤ AV (fQ,D) k − 1 , (14)
where AV (fQ,D) = E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) 6= T (fθ′ ,x))] is the algorithm DB variability of fQ on data generating distribution D.
The proof is given in Appendix C.3. Hence, the next theorem is a direct consequence of the onesided Chebyshev’s inequality: Pr [ E[Z1]− 1m ∑m i=1 Zi > a ] ≤ Var[Z1]2ma2 for any a > 0.
Theorem 3 (PAC upper bound on expected risk). Let fθ(x) : Rn → Rk be a classifier network parameterized by θ and let Q(θ) be the distribution over θ w.r.t. the training set S. Suppose Assumption 1 and 2 hold. Then, with the probability of at least 1 − δ over a sample of size m, we have
RD(Q) ≤ RS(Q) + √ AV (fQ,D) 2m(k − 1)δ . (15)
The above theorem presents that a smaller algorithm DB variability AV (fQ,D) contributes to a tighter upper bound on the true risk, which theoretically verifies Hypothesis 1 that neural networks with smaller algorithm decision boundary variability possess better generalization performance.

heading: 5 DATA DECISION BOUNDARY VARIABILITY
text: In the previous sections, we introduced the algorithm DB variability, which measures the decision boundary variability caused by the randomness of learning algorithms. However, the algorithm DB variability hardly shows the decision boundary variability caused by changes in training data. To remedy the problem and complete our theorem about decision boundary variability, we define the data DB variability as below:
Definition 5.1 (data decision boundary variability). Let fθ(x) : Rn → Rk be a classifier network parameterized by θ, where θ ∼ A(S) is returned by leveraging the stochastic learning algorithm A on the training set S, which is sampled from the data generating distribution D. We term Sη ⊂ S as a η-subset of S if |Sη||S| = η. Then, if we fixed η and
inf Sη⊂S E(x,y)∼DEθ∼A(S),θ′∼A(Sη) [I (T (fθ,x) 6= T (fθ′ ,x))] = , (16)
the decision boundary of fA(S) is said to possess a ( , η)-data decision boundary variability.
The data decision boundary variability contains two parameters of and η, respectively. That Gibbs classifier fA(S) has a ( , η)-data DB variability means that only the proportion of η of S, i.e., Sη , which can be considered as “support vector set”, is enough to reconstruct a similar decision boundary with the reconstruction error . The data DB variability can also be connected with the complexity of decision boundaries if we assume that simpler decision boundaries rely on fewer “support vectors”; we provide a detailed discussion in Appendix B.2 due to space limitation.
5.1 η- CURVES ABOUT DATA DB VARIABILITY
According to Definition 5.1, the data DB variability degrades to the algorithm DB variability AV (fQ,D) when Sη = S . In other words, the algorithm DB variability is a special case of the data DB variability with η = 1. Therefore, the data DB variability could present more detailed information on reflecting how the decision boundary variability depends on the training set, especially when we observe the variation of the reconstruction error w.r.t. different η.
To explore the relationship between the reconstruction error and the proportion of subset η, we train 1000 networks of ResNet-18 on CIFAR-10 and CIFAR-100 of different sample sizesm, respectively. Albeit finding the most suitable η-subset is intractable, we adopt a coreset selection approach named selection via proxy (Coleman et al., 2020), which can rank the importance of training examples, to estimate the η-subset for a given training set S and proportion η (full list of η involved in our experiments is presented in Appendix A.3.6). Then, through repeatedly training the network on Sη , we can estimate the reconstruction error . The η- curves of CIFAR-10 and CIFAR-100 are presented in Figure 4(a) and 4(b), respectively. From the plots, we have an observation that there is a more rapid decline in along with small η and also a smaller algorithm DB variability when the training sample size m is larger. Furthermore, we plot the schematic diagram of η- curves w.r.t. different sample size m, as shown in Figure 4(c). When η = 0, fA(Sn) cannot be better than random guess, and hence = k−1k , where k is the number of potential categories. We have noticed that has a sharper drop along with η when the sample size m is larger. Therefore, we rationally propose the following assumption, which is also shown by the right angle with m∞ in Figure 4(c).
Assumption 3. If m→∞, then we have → 0 when η → 0.
These plots indicate that the area under the η- curve could be a more meticulous predictor for the generalization ability of neural networks compared to the algorithm DB variability, which is only a point on the η- curve when η = 1. Hence, the area under the η- curve can also be considered as an extension of the algorithm DB variability: if the Gibbs classifier fA(S) possesses a smaller area under the η- curve, it produces more stable decision boundaries with varying training subsets. In the following section, we will theoretically establish the connection between the parameters of η and and the generalization ability of neural networks.

heading: 5.2 THEORETICAL EVIDENCE
text: In this section, we develop the theoretical foundations for the data decision boundary variability, and present that neural networks with better data DB variability possess better generalization.
Lemma 2. If the decision boundaries of fA(S) possess a ( , η)-data DB variability, then we have
|RD(A(S))−RD(A(Sη))| ≤ . (17)
Lemma 2 shows that the difference between the expected risk of A(S) and A(Sη) can be bounded by their difference in decision boundaries. Then, by applying the concentration inequality, we can
bound the difference between their empirical risk on the same training set S with the probability 1− δ: Lemma 3. If the decision boundaries of fA(S) possess a ( , η)-data DB variability, then, with probability of at least 1− δ over a sample of size m, we have
RS(A(Sη)) ≤ RS(A(S)) + √ 1
2m log
1 δ + , (18)
where m = |S| is the training sample size. If we further assume the training error RS(A(S)) = 0, then, with the probability of at least 1− δ over a sample of size m, we have
RS(A(Sη)) ≤ √ 1
2m log
1 δ + (19)
Theorem 4 (data DB variability-based upper bound on expected risk). If the decision boundaries of fA(S) possess a ( , η)-data DB variability on the data generating distributionD, and assume η ≤ 0.5 and the empirical risks RS(A(S)) = RSη (A(Sη)) = 0, then, with the probability of at least 1− δ over a sample of size m, we have
RD(A(S)) ≤ Ω + √ 4Ω∆ + 8∆ + , (20)
where
Ω = 1
1− η
(√ 1
2m log
2 δ +
) , (21)
∆ = η log e
η +
1 m log 2 δ . (22)
Moreover, for sufficient large m, we have
RD(A(S)) ≤ O( 1√ m + + η log 1 η ). (23)
The proof is omitted here and is given in Appendix C.7. According to Assumption 3, whenm→∞, then η → 0 and → 0, and according to Eq. 23, RD(A(S)) → 0. Therefore, the generalization bound is asymptotically converged. Theorem 4 presents that smaller data DB variability, i.e., smaller and η, contributes to a tighter upper bound on the expected risk, and also theoretically verifies the relationship between the data DB variability and the generalization ability of neural networks.

heading: 6 CONCLUSION AND DISCUSSION
text: In this paper, we empirically and theoretically explored the relationship between decision boundary variability and generalization in neural networks, through the algorithm DB variability and data DB variability, respectively. A significant negative correlation between the decision boundary variability and generalization performance is observed in our experiments. As for the theoretical results, two lower bounds and two upper bounds were proposed based on algorithm DB variability and data DB variability to enhance our findings. The algorithm DB variability upper bound is easier to calculate in practice, while the data DB variability upper bound relies on less assumptions. Moreover, in contrast to many existing generalization bounds based on hypothesis complexity that require access to the network weight, our generalization bounds based on decision boundary variability only demand access to the network predictions and thus have advantages in empirically approximating the generalization bound in (1) black-model settings, where model parameters are unavailable; and (2) over-parameterized settings, where calculating the weight norm is of prohibitively high computing burden. Furthermore, the analysis in Section 5.1 mentioned that the algorithm DB variability is a special case of the data DB variability. Therefore, unifying the theoretical works about algorithm DB variability and data DB variability will be a promising direction in future works.

heading: ACKNOWLEDGEMENT
text: The authors sincerely appreciate the anonymous reviewers for their valuable suggestions.

heading: A ADDITIONAL EXPERIMENTS DETAILS
text: This section provides all the additional details of our experiments.

heading: A.1 DATASETS
text: Our experiments are conducted on two public datasets (CIFAR-10 and CIFAR-100 (Krizhevsky & Hinton, 2009)) and two manufactured datasets (fake CIFAR-10, and fake CIFAR-100). The detail of these datasets are shown as follows.
• CIFAR-10 consists of 50, 000 training images and 10, 000 test images from 10 different classes, and CIFAR-100 consists of 50, 000 training images and 10, 000 test images from 100 different classes. One can download CIFAR-10 and CIFAR-100 from https:// www.cs.toronto.edu/˜kriz/cifar.html.
• Fake CIFAR-10 consists of 100, 000 test images from 10 different classes. The fake CIFAR-10 is generated by conditional BigGAN (Zhao et al., 2020). The pre-trained BigGAN is provided by Kang & Park (2020) and can be download from https://drive. google.com/drive/folders/1xVN7dQPWMLi8gDZEb5FThkjbFtIdzb6b.
• Fake CIFAR-100 consists of 100, 000 test images from 100 different classes. The generation of fake CIFAR-100 is similar to it of fake CIFAR-10, while the training set for the BigGAN is replaced from CIFAR-10 to CIFAR-100.

heading: A.2 MODEL ARCHITECTURES
text: We use different neural network architectures in our experiments, including VGG-16, ResNet-18, and WideResNet-28. The architectures are presented in Table 1.
A.3 IMPLEMENTATION DETAILS
This section provides all the additional implementation details for our experiments.

heading: A.3.1 MODEL TRAINING
text: We employ SGD to optimize all the models and the momentum factor is 0.9. The weight decay factor is set to 5e-4, and the learning rate is decayed by 0.2 every 50 epochs.

heading: A.3.2 ADDITIONAL DETAILS IN SECTION 4.1
text: We train VGG-16, ResNet-18, Wide-ResNet-28 on CIFAR-10 and CIFAR-100. In the training procedure, the model is trained for 200 epochs, in which the batch size is set to 128, and the learning rate is initialized as 0.1. There are three training strategies included in this experiment: standard training, non-data-augmentation training, and adversarial training. In the adversarial training, the radius of the adversarial perturbation is set as 10/255 and l∞ distance is selected. The basic data augmentation (cropping and flipping) in the standard training and adversarial training is achieved by the following Pytorch code:
1 transforms.RandomCrop(32, padding=4) 2 transforms.RandomHorizontalFlip()
The experiment is repeated for 10 trials for each (dataset, architecture, training strategy) setting.

heading: A.3.3 ADDITIONAL DETAILS IN SECTION 4.2
text: We repeatedly train 10 ResNet-18 on CIFAR-10 and CIFAR-100, respectively, with different random seeds. In the training procedure, the model is trained for 200 epochs, in which the batch size is set to 128, and the learning rate is initialized as 0.1 and 0.01, respectively. Basic data augmentation is included during the training process.

heading: A.3.4 ADDITIONAL DETAILS IN SECTION 4.3
text: We randomly sample examples from the training set of CIFAR-10 and CIFAR-100 to form five datasets with different sizes of [2000, 5000, 10000, 20000, 50000], respectively. 10 ResNet-18 are trained for each dataset. In the training procedure, the model is trained for 200 epochs, in which the batch size is set to 128, and the learning rate is initialized as 0.1. Basic data augmentation is included during the training process.

heading: A.3.5 ADDITIONAL DETAILS IN SECTION 4.4
text: We randomly change the labels of 20% examples in the training set of CIFAR-10 and CIFAR-100. Then, 10 ResNet-18 are optimize by SGD for 500 epochs on the noise CIFAR-10 and CIFAR-100, respectively. the momentum factor is 0.9, and the learning rate is 0.001 and does not decay during the training process.

heading: A.3.6 ADDITIONAL DETAILS IN SECTION 5.1
text: We randomly sample examples from the training set of CIFAR-10 and CIFAR-100 to form five datasets with different sizes of [2000, 5000, 10000, 20000, 50000], respectively. For each dataset, we obtain 10 η-subsets with different η of [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0] via a coreset selection approach named selection via proxy (Coleman et al., 2020). The related code can be downloaded from https://github.com/stanford-futuredata/ selection-via-proxy. The ResNet-18 is repeatedly trained for 10 trials to estimate the complexity of decision boundaries for each η-subset.

heading: B ADDITIONAL DISCUSSION ON DECISION BOUNDARY VARIABILITY

heading: B.1 ALGORITHM DB VARIABILITY AND THE ENTROPY OF DECISION BOUNDARIES
text: If Assumption 1 holds for all θ ∼ Q, 1−AV (fQ,D) can be rewritten as
E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) = T (fθ,x))] = E(x,y)∼D k∑ i=1 E2θ∼Q [I (T (fθ,x) = i)] . (24)
The term ∑k i=1 E2θ∼Q [I(T (fθ,x) = i)] can be considered to measure the degree of prediction uncertainty for the given voxel x in the input space Rn. If we leverage − log(·) on the term∑k i=1 E2θ∼Q [I(T (fθ,x) = i)], then − log ∑k i=1 E2θ∼Q [I(T (fθ,x) = i)] denotes the collision entropy of prediction made by the Gibbs classifier fQ on x. We can also replace the collision entropy with canonical Shannon entropy− ∑k i=1 Eθ∼Q [I(T (fθ,x) = i)] logEθ∼Q [I(T (fθ,x) = i)] in the future research. Hence, the algorithm DB variability is closely related to the “entropy of decision boundary”, and the uncanny generalization in neural networks might be further uncovered by investigating this low entropy of decision boundary.

heading: B.2 DATA DB VARIABILITY AND THE COMPLEXITY OF DBS
text: According to Guan & Loew (2020), a complex decision boundary is considered to own large curvatures and conjectured to indicate inferior generalization. Nevertheless, from the perspective of causality, we argue that the large curvature or non-linearity of DBs is the result other than the cause for the classification task, and the primary reason for shaping a complex DB during the training procedure should be the significant non-linearity of the training data. If only the geometric properties of decision boundaries are analysed without investigating the data, the results might be incomplete and even misleading. Another obstacle for describing the complexity of DBs via its geometric properties is the huge dimensional input space, which makes the geometric properties of DBs hard to quantify and estimate. Therefore, defining the complexity of DBs based on its curvature is not rational and impractical.
Here we consider the complexity of DBs from the perspective of the training set. During the training procedure, a small part of training examples, considered as “support vectors”, play a more critical role in supervising the formation of decision boundaries and compelling the DB to be gradually more complicated. If the construction of decision boundaries relies on fewer “support vectors”, the decision boundary should be simpler. In other words, if these “support vectors” are excluded from the training sample, the DB will be notably dissimilar when the network is retrained on the modified training set. Hence, the complexity of DBs can be also defined with the notion of the data DB variability: Definition B.1 (complexity of decision boundaries). Let fθ(x) : Rn → Rk be a classifier network parameterized by θ, where θ ∼ A(S) is returned by leveraging the stochastic learning algorithm A on the training set S, which is sampled from the data generating distribution D. We term Sη ⊂ S as a η-subset of S if |Sη||S| = η. Then, if we fixed η and
inf Sη⊂S E(x,y)∼DEθ∼A(S),θ′∼A(Sη) [I (T (fθ,x) 6= T (fθ′ ,x))] = , (25)
the decision boundary of fA(S) is said to possess a ( , η)-complexity.
Implications about the complexity of DB. With Definition B.1, we could more intuitively understand the relationship between the complexity of DBs and the generalization ability in deep learning: (1) difficult tasks generally have more complex decision boundaries, since their datum are more nonlinear and contain more “support vectors”; (2) in adversarial training, each data point is converted to a “data ball” with the radius of the adversarial perturbation and has more impact on forming the DBs. Hence, adversarial training contributes to a more complex decision boundary by enlarging the “support vector set”; (3) for data augmentation, generated images are also considered to obey the data generation distribution D. Hence, data augmentation decreases the complexity of decision boundaries by greatly expanding the training set S, while |Sη| has only a slight growth. Besides, according to our theoretical results in Section 5.2, it can be verified that neural networks with simpler decision boundaries possess better generalization performance.

heading: C PROOFS
text: To avoid technicalities, the measurability/integrability issues are ignored throughout this paper. Moreover, Fubini’s theorem is assumed to be applicable for any integration w.r.t. multiple variables. In other words, the order of integrations is exchangeable. We also use E2[·] to denote [E [·]]2 in our proof for simplicity.

heading: C.1 PROOF OF THEOREM 1
text: Proof. If Assumption 1 holds for all θ ∼ Q, we have
E(x,y)∼DEθ,θ′∼Q [I (y ∈ T (fθ,x)) I (y ∈ T (fθ′ ,x)) I (T (fθ,x) 6= T (fθ′ ,x))] = 0 (26)
Hence,
AV (fQ,D) =E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) 6= T (fθ′ ,x))] (27) =E(x,y)∼DEθ,θ′∼Q [I (y ∈ T (fθ,x)) I (y /∈ T (fθ′ ,x)) (28)
+ I (y /∈ T (fθ,x)) I (T (fθ,x) 6= T (fθ′ ,x))] (29) ≤2RD(Q) (30)
The proof is completed.

heading: C.2 PROOF OF THEOREM 2
text: Proof. When the classification is binary, i.e., k = 2, with Assumption 1, we have
E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) = T (fθ,x))] (31) =E(x,y)∼DE2θ∼Q [I (y ∈ T (fθ,x))] + E(x,y)∼DE2θ∼Q [I (y /∈ T (fθ,x))] (32)
=E(x,y)∼DE2θ∼Q [I (y ∈ T (fθ,x))] + E(x,y)∼D [1− Eθ∼Q [I (y ∈ T (fθ,x))]] 2 (33)
=2E(x,y)∼DE2θ∼Q [I (y ∈ T (fθ,x))] + 2RD(Q)− 1 (34)
Plugging in Var(x,y)∼D [Eθ∼Q [I (y ∈ T (fθ,x))]] = E(x,y)∼DE2θ∼Q [I (y ∈ T (fθ,x))] − (1 − RD(Q))2 yields
E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) = T (fθ,x))] (35) =2Var(x,y)∼D [Eθ∼Q [I (y ∈ T (fθ,x))]] +R2D(Q) + (1−RD(Q))2 (36) ≥R2D(Q) + (1−RD(Q))2 (37)
Plugging inAV (fQ,D) = 1−E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) = T (fθ′ ,x))] and solving the inequality yield the desired inequality and finishes the proof of Theorem 2.

heading: C.3 PROOF OF LEMMA 1
text: Proof. Without loss of generality, we assume that all examples are belong to the first class, i.e., y = 1. Hence, for 1−AV (fQ,D) = E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) = T (fθ′ ,x))], we have
E(x,y)∼DEθ,θ′∼Q [I (T (fθ,x) = T (fθ′ ,x))] (38)
=E(x,y)∼D k∑ i=1 E2θ∼Q [I (T (fθ,x) = i)] (39)
=E(x,y)∼D [ E2θ∼Q [I (T (fθ,x) = y)] + k∑ i=2 E2θ∼Q [I (T (fθ,x) = i)] ] (40)
=E(x,y)∼D (1− k∑ i=2 Eθ∼Q [I (T (fθ,x) = i)] )2 + k∑ i=2 E2θ∼Q [I (T (fθ,x) = i)]  (41) ≤1 + 2
k∑ i=2 E(x,y)∼DE2θ∼Q [I (T (fθ,x) = i)]− 2 k∑ i=2 E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)]
+ 2 ∑ i>j>1 ( E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)]E(x,y)∼DEθ∼Q [I (T (fθ,x) = j)] ) (42)
≤1 + 2 k∑ i=2 E(x,y)∼DE2θ∼Q [I (T (fθ,x) = i)]− 2 k∑ i=2 E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)]
+ (k − 2) k∑ i=2 ( E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)] )2 (43)
≤1 + 2 k∑ i=2 E(x,y)∼DE2θ∼Q [I (T (fθ,x) = i)]− 2 k∑ i=2 E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)]
+ (k − 1) k∑ i=2 ( E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)] )2 (44)
The penultimate inequality holds because 2pipj ≤ p2i + p2j . Moreover, the variance of Eθ∼Q [I (y /∈ T (fθ,x))] is
Var(x,y)∼D [Eθ∼Q [I (T (fθ,x) 6= y)]] (45) =E(x,y)∼DE2θ∼Q [I (T (fθ,x) 6= y)]− E2(x,y)∼DEθ∼Q [I (T (fθ,x) 6= y)] , (46)
plugging the equality into Eq. 44 yields
1−AV (fQ,D) ≤1− (k − 1)Var(x,y)∼D [Eθ∼Q [I (T (fθ,x) 6= y)]] + (k − 1)E(x,y)∼DE2θ∼Q [I (T (fθ,x) 6= y)]
− (k − 1)E2(x,y)∼DEθ∼Q [I (T (fθ,x) 6= y)] + (k − 1) k∑ i=2 E2(x,y)∼DEθ∼Q [I (T (fθ,x) = i)]
+ 2 k∑ i=2 E(x,y)∼DE2θ∼Q [I (T (fθ,x) = i)]− 2 k∑ i=2 E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)] (47)
Then, because Eθ∼Q [I (T (fθ,x) 6= y)] = ∑k i=2 Eθ∼Q [I (T (fθ,x) = i)], we have
k∑ i=2 E2(x,y)∼DEθ∼Q [I (T (fθ,x) = i)] ≤ E 2 (x,y)∼DEθ∼Q [I (T (fθ,x) 6= y)] (48)
and k∑ i=2 E(x,y)∼DE2θ∼Q [I (T (fθ,x) = i)] ≤ E(x,y)∼DE2θ∼Q [I (T (fθ,x) 6= y)] . (49)
Therefore, Eq. 47 can be scaled to (k − 1)Var(x,y)∼D [Eθ∼Q [I (T (fθ,x) 6= y)]]
≤AV (fQ,D) + (k + 1)E(x,y)∼DE2θ∼Q [I (T (fθ,x) 6= y)]− 2 k∑ i=2 E(x,y)∼DEθ∼Q [I (T (fθ,x) = i)]
(50)
Then, with Assumption 2 that E(x,y)∼DE2θ∼Q [I (y /∈ T (fθ,x))] ≤ 2k+1RD(Q), we get the following inequality w.r.t. the variance:
Var(x,y)∼D [Eθ∼Q [I (T (fθ,x) 6= y)]] ≤ AV (fQ,D) k − 1 . (51)
The proof is completed.

heading: C.4 PROOF OF THEOREM 3
text: Proof. For the random variable Zi, recall the one-sided Chebyshev’s inequality that
Pr [ E[Z1]− 1
m m∑ i=1 Zi > a
] ≤ Var[Z1]
2ma2 . (52)
Let Zi = Eθ∼Q [I (yi /∈ T (fθ,xi))], so we have
Pr [RD(Q)−RS(Q) > a] ≤ Var(x,y)∼D [Eθ∼Q [I (y /∈ T (fθ,x))]]
2ma2 . (53)
Plugging Lemma 1 into the above inequality yields
Pr [RD(Q)−RS(Q) > a] ≤ AV (fQ,D)
2m(k − 1)a2 . (54)
Plugging in δ = AV (fQ,D)2m(k−1)a2 yields the desired inequality and completes the proof.

heading: C.5 PROOF OF LEMMA 2
text: Proof. From the definition of the complexity of DB, there exists a η-subset Sη s.t. E(x,y)∼DEθ∼A(S),θ′∼A(Sη) [I (T (fθ,x) 6= T (fθ′ ,x))] = . (55)

heading: Recall the LHS = |RD(A(S))−RD(A(Sη))|, then
text: LHS = ∣∣E(x,y)∼DEθ∼A(S) [I (y /∈ T (fθ,x))]− E(x,y)∼DEθ∼A(Sη) [I (y /∈ T (fθ,x))]∣∣ (56) = ∣∣E(x,y)∼DEθ∼A(S),θ′∼A(Sη) [I (y /∈ T (fθ,x))− I (y /∈ T (fθ′ ,x))]∣∣ (57)
≤ E(x,y)∼DEθ∼A(S),θ′∼A(Sη) [|I (y /∈ T (fθ,x))− I (y /∈ T (fθ′ ,x))|] (58) ≤ E(x,y)∼DEθ∼A(S),θ′∼A(Sη) [I (T (fθ,x) 6= T (fθ′ ,x))] = (59)
The proof is completed.

heading: C.6 PROOF OF LEMMA 3
text: Proof. Let µ = E(x,y)∼DEθ∼A(S),θ′∼A(Sη) [I (T (fθ,x) 6= T (fθ′ ,x))] (60)
µ̂ = 1
m m∑ i=1 Eθ∼A(S),θ′∼A(Sη) [I (T (fθ,xi) 6= T (fθ′ ,xi))] , (61)
By applying Hoeffding’s Inequality, we have Pr [µ̂− µ ≥ t] ≤ exp(−2mt2). (62)
Plug in δ = exp(−2mt2) into Eq. 62, thus, with the probability of at least 1− δ, we have µ̂ ≤ √ 1
2m log
1 δ + µ ≤
√ 1
2m log
1 δ + . (63)
Following the proof of Lemma 2, we can derive the inequality of |RS(A(Sη))−RS(A(S))| ≤ µ̂. Plugging this into Eq. 63 yields the desired inequality and concludes the proof of Lemma 3.

heading: C.7 PROOF OF THEOREM 4
text: We first introduce Lemma 4 and Lemma 5 as below. Lemma 4 (Lemma 30.1 in (Shalev-Shwartz & Ben-David, 2014)). Assume T and V are two datasets independently sampled from the data generating distribution D, then, with the probability of at least 1− δ, we have
RD(A(T )) ≤ RV (A(T )) +
√ 2RV (A(T )) log(1/δ)
|V | +
4 log(1/δ)
|V | . (64)
Lemma 5 (Theorem 30.2 in (Shalev-Shwartz & Ben-David, 2014)). Let Sη be a η-subnet of the dataset S, which is sampled from the data generation distribution D and the sample size |S| = m. Let S\Sη = S − Sη and assume η ≤ 0.5. Then, with the probability of at least 1− δ over a sample of size m, we have
RD(A(Sη)) ≤ RS\Sη (A(Sη)) + √ 4RS\Sη (A(Sη))∆ + 8∆, (65)
where ∆ = η log e
η +
1 m log 1 δ′ . (66)

heading: Proof of Lemma 5.
text: Pr [ ∃Sη ⊆ S s.t. RD(A(Sη)) ≤ RS\Sη (A(Sη)) + √ 2RS\Sη (A(Sη)) log(1/δ)
|S\Sη| +
4 log(1/δ)
|S\Sη| ] (67)
≤ ∑ Sη⊆S Pr [ RD(A(Sη)) ≤ RS\Sη (A(Sη)) + √ 2RS\Sη (A(Sη)) log(1/δ) |S\Sη| + 4 log(1/δ) |S\Sη| ] (68)
=
( m
ηm
) δ ≤ ( e
η
)ηm δ (69)
Plug in δ′ = ( e η )ηm δ, and use the assumption η ≤ 12 , which implies |S\Sη| ≥ m 2 , then, with the probability of at least 1− δ′, we have that
RD(A(Sη)) ≤ RS\Sη (A(Sη))+ √ 4RS\Sη (A(Sη)) ( η log e
η +
1 m log 1 δ′
) +8 ( η log e
η +
1 m log 1 δ′
) ,
(70) which concludes the proof.
With the above lemmas, we can derive the generalization bound based on the complexity of decision boundary.
Proof of Theorem 4. With the assumption of zero-training error that RS(A(S)) = RSη (A(Sη)) = 0, we can derive the follow inequality:
RS\Sη (A(Sη)) = 1 1− η ( RS(A(Sη))−RSη (A(Sη)) ) = 1 1− η RS(A(Sη)) (71)
Then, by plugging the above equation into to Lemma 3, with the probability of at least 1 − δ, we have
RS\Sη (A(Sη)) ≤ 1
1− η
(√ 1
2m log
1 δ +
) (72)
Through combining this with Lemma 5, with the probability of at least 1− 2δ, we have
RD(A(Sη)) ≤ Ω + √ 4Ω∆ + 8∆, (73)
where
Ω = 1
1− η
(√ 1
2m log
1 δ +
) , (74)
∆ = η log e
η +
1 m log 1 δ . (75)
Plugging the equality of RD (A (S)) ≤ RD (A (Sη)) + in Lemma 2 into Eq. 73, with the probability of at least 1− 2δ, we have
RD(A(S)) ≤ Ω + √ 4Ω∆ + 8∆ + . (76)
Plugging in δ′ = 2δ yields the desired inequality of Eq. 20. When m is sufficient large, √ 4Ω∆ can be dropped due to √
4Ω∆ ≤ Ω + ∆. Considering η ≤ 0.5, Ω ≤ 2 (√ 1
2m log 1 δ +
) = O( 1√
m + ). The term 1m log 1 δ in ∆ can be dropped because it has a faster convergence speed compared to √
1 2m log 1 δ in Ω. Because log 1 δ is considered as a constant,
we have RD(A(S)) ≤ O(
1√ m + + η log 1 η ). (77)
The proof of Theorem 4 is finished.

heading: D ADDITIONAL EXPERIMENTAL RESULTS
text: This appendix collect experimental results omitted from the main text due to the space limitation.

heading: D.1 ADDITIONAL RESULTS FOR LEARNING RATE
text: Accroding to Li et al. (2019) that learning rate is a major factor of affecting generalization of networks, we investigate the relationship between algorithm DB variability and learning rate by training 20 ResNet-18 with different constant learning rates (no decay) of 0.001 and 0.0001 on CIFAR-10 until the training procedure converges. Then, the average test error and algorithm DB variability are calculated at each epoch, as shown in Figure 5. From the plots, we observe that: (1) the larger learning rate 0.001 contributes to better generalization performance; and (2) algorithm DB variability with the larger learning rate 0.001 is smaller during the training process, compared to the learning rate 0.0001. Therefore, there is still a negative correlation between algorithm DB variability and generalization by varying the learning rate, and thus Hypothesis 1 is well supported.

Review summaries:
The authors introduce the notion of decision boundary (DB) variability and develop generalization bounds in terms of this.  They consider two notions, that of 'algorithm DB variability' and 'epsilon-eta DB variability', the latter a generalization of the former.  They show upper and lower bounds for the risk of classifiers in terms of DB variability under a variety of assumptions, as well as experimentally verify some of their claims.  

This paper studies that the smaller variability of prediction can provide a better generalization in empirical and theoretical foundations. Considered examples and theories are solid, and the intensive studies reveal the relationship (correlation not causation) between the variability of prediction and generalization. The paper considers two types of variability with respect to algorithm and training data. In any case, lower variability ensures higher performance in generalization.    

Decision boundary variability is measured in two ways. One method depends on the algorithm, or the random seed and reflects how much the boundaries change wen retraining the same network on the same data. The other technique reflects the variability across different amounts of training data. Generalization bounds derived from these two quantities are presented.