Decision boundary variability and generalization in neural networks
Authors: Shiye Lei
Fengxiang He
Yancheng Yuan
Dacheng Tao
Venue: ICLR 2022 Submitted (2022)
Keywords: explainability of deep learning

Abstract: Existing works suggest that the generalizability is guaranteed when the margin between data and decision boundaries is sufficiently large. However, the existence of adversarial examples in neural networks shows that excellent generalization and small margin can exist simultaneously, which casts shadows to the current understanding. This paper discovers that the neural network with lower decision boundary (DB) variability has better generalizability. Two new notions, algorithm DB variability and $(\epsilon, \eta)$-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, we prove two lower bounds and two upper bounds of the generalization error based on the decision boundary variability, which is consistent with our empirical results. Moreover, the bounds do not explicitly depend on the network size, which is usually prohibitively large in deep learning.

Under review as a conference paper at ICLR 2022
DECISION BOUNDARY VARIABILITY AND GENERALIZATION IN NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper discovers that the neural network with lower decision boundary (DB) variability has better generalizability. Two new notions, algorithm DB variabil- ity and (e, data DB variability, are proposed to measure the decision bound- ary variability from the algorithm and data perspectives. Extensive experiments show significant negative correlations between the decision boundary variabil- ity 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
log 2t based on algorithm o ( (Je D)/m(k))])]] 1)) and O + (
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.
INTRODUCTION
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 canon- ical statistical hypothesis complexity, such as VC-dimension (Vapnik et al., 1994) or Rademacher complexity (Bartlett & Mendelson 2002p. Considering the intimate connection between low vari- ance 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 (e, n)- 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, 10, and CIFAR-100 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.(.) 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 rate of O (VVV D)/m(k 1aak--1jj 1)). where AV (fQ. D) is the algorithm DB variability for fo on data generating distribution D, m is the sample size, and is the number of classes.
To present how the training data influences the decision boundary variability, the (c, n)-dtaa DB variability introduced by employing the subset to reconstruct decision boundaries with error e (see Definition 5.1). If decision boundary can be reconstructed by training on smaller subset with a smaller reconstruction error e, the decision boundary possesses smaller data DB variability. Moreover, an 17-c curve can be drawn by varying the value of 1 and numerically evaluating the label mismatch rate. The area under the ne curve could be a more elaborate indicator for the general- ization of NNs because the curve contains richer information than the algorithm DB variability. An

---

Under review as a conference paper at ICLR 2022
vm 0 (+m ( + generalization bound based on the (e, -)-dttaa 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 de- pend on additional Assumption 2 while the algorithm DB variability is easier 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. (017)) 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 (I) black- model settings, where model parameters are unavailable; and (2) over-par weer-paameterized
settings, where calculating the weight norm of prohibitively high computing burden.
2 RELATED WORKS
Deep learning theory. Due to the bias-variance trade-off, model complexity faces a dilemma in conventional wisdom (Mohri et al. 2018). Recently, Zhhng et al. (202T) 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 approxima- tion 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 de- scent (SGD) algorithm (Bottou 2010: Hardt et al.) [016 Jin et al.) (017)). Some empirical studies also explain the decent performance of networks by uncovering their learning properties (Nakki-) ran et al. 2020 Jiang 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 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 al. 2019). Guan & Loew (2020) empirically show the negative correlation between the complexity of decision boundary and gener- alization performance. [Mckiicch et al.) (2020) reveal the phenomenon that the distance from data to decision boundaries continuously decreases during the training procedure. More recently, re- searchers find that NNs only rely on the most discríminative or simplest features to construct the DBs (Ortiz-Jimenez et al., 22200 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 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 (Marry et al. (207)). Nevertheless, Su et al. (2018) and and/Zangg et al. (2019) show a trade-off between the robustness and the generalization performance of NNs.
3 PRELIMINARIES
We denote the training set by S (xx,, 1,.., m). where x; E IR",, n is the dimension of input data, y/ (1,..., k.. l is the number of classes, and m = |S] is the training sample size. We assume that (x, v.) are independent and identically distributed (i.idd) random variables drawn from the data generating distribution D. Denote the classifier as fo(x) RR" + RR which is a neural network parameterized by 0. The output of (x) is a k-dimensional vector and is assumed to be a discrete probability density function. Let f( (x) be the i-th component of fx)... hence
(x) = 1. We define x(Jo,x) = (i E (1,.... 1)116 (x) max, s!a) (x)) to denote the set of predicted labels by fe on x. Due to the randomness of the learning algorithm A, let ((0)= A(S) denote the posteriori distribution returned by the learning algorithm AA leveraged on the training set S. Hence, we focus on the Gibbs classifier (a.k.a. random classifier) fo = {fol e ~
Σ (()) (x)
@) 0 1 loss is employed in this paper, and the expected risks in terms of 0 and Q are defined as:
RD (0) Ex [T (y E T (Jo: x))]
2

---

Under review as a conference paper at ICLR 2022
and
(x(Q) = B(x.))<Eooaq [T $ T (fe. x))],
(2)
respectively. Here I(-) is the indicator function. Since the data generating distribution D is unknown, evaluating the expected risk Rd not practical. Therefore, expected risk by the empirical risk Rss which defined
practical way to estimate the
Rs( = (x) 1I (v & T (fo, (fo,x))]
Σ 1 (yr $ T (fe.
(3)
R.s (2) = E(x,y)~s Bawa (v & T (So, x)]] Σ Ea-e [1| (yi & T (Jo,)
(4)
where (x,; Ui) S and |S).
3.1 DECISION BOUNDARY
the output k-dimensional vector [x( on the input example x has a tie, i.e,, the maximum value of the vector not unique, then x is considered to locate on the decision boundary of fe. With this idea, the decision boundary can be formally defined as below:
Definition 3.1 (decision boundary). Let fx(x) "R R$ be classifier network parameterized by 0. Then the decision boundary of So defined by
{x E 12 E
j E (1.-... k). j. f. (x) max fo (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 fe. T T(fe, x)
a singleton, and we have
(y & T (fe. x)) (y + T (fo,x))
(6)
(2) If the input is boundary point, in practice, randomly draw label from the set T T(fe. x)
as the prediction of fe on x.
3.2 ADVERSARIAL TRAINING
Adversarial training (AT) is popular strategy to enhance the adversarial robustness of neural net- works 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 formu- lated as solving the minimax-loss problem as follows:
min
max
(fo (x+) v1))
where is the radius 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 least
4 ALGORITHM DECISION BOUNDARY VARIABILITY
Due to the randomness of learning algorithms, there is no doubt that the parameters have a substan- tial variation when the network repeatedly trained. However, do the decision boundaries in these repeated-training networks have 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 fx( R." + R be a classifier
network parameterized by 9 and let Q(0) be the distribution over 0. Then, the algorithm decision boundary variability for fe on is
AV D) E(x,))DEo,or [I (T x) x))o
(8)
where T(Jo, x) (i (1, ",)))
[k)]s((((x) (x) max, [1)
3

---

Under review as a conference paper at ICLR 2022
CIFAR-10
CIFAR-100
Algorttmm varfability
Algorithm variablity
A
VGG WRN
VSG WRN
k20
Test acc
acc
(a) CIFAR-10
(b) Fake CIFAR-100
(c) Algorithm DB variability vs. test accuracy
Figure 1: Algorithm decision boundary variability on CIFAR-10 and CIFAR- 100. (a) Examples of fake CIFAR- 10 images generated by conditional BigGAN. (b) Examples of fake CIFAR-100 images generated by conditional BigGAN. (c) Scatter plots of algorithm DB variability to accuracy on test set with different architectures and training strategies CIFAR-IO and CIFAR-100. The colors of blue, red, and yellow points denote the architectures of VGG-16 (VGG), ResNet-18 (ResN), and WideResNet-25 28 (WRN), respectively. The shapes of A, and designate the training strategies of standard training (S), non-dattaaaugmentttio training (N), and adversarial training (A), respectively. Each point is calculated and then averaged 10 trials.
smaller algorithm DB variability AV 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 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.I due space limitation.
In the light of Definition 4.1
4.1 ALGORITHM DB VARIABILITY AND GENERALIZATION
To explore the relationship between the algorithm DB variability and generalization in neural net- works, 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 al. 2016), and WideResNet-28 (Zagonykko & Komodakis] (016b) are optimized by standard, non non-data-auge augmentation and ad adversarial training, respectively, until the training procedure converges. We clarify that basic data augmentation (crop and flip) (Zagoruyko ko Komodakis (016a) 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 (0).. As for sim- ulating 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 [(a] and [(b)
Through these generative fake images, well-trained models. For each training setting, we plot both the average test accuracy and algorithm DB variability; see Figure Fic) From the plots, have several observations: (1) adversarial train- ing 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 aon-data--ugmentatii mented 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) NedeResNet 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 these findings, we propose the following conjecture:
estimate the algorithm DB variability w.zt. these
training. The reason is that the aug-
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.t. training time, sample size, and label noise concrete this hypothesis.
4

---

Under review as a conference paper at ICLR 2022
CIFAR-10 (LR=0.1)
CIFAR-10 (LR-0.01)
CIFAR-100 (LR-0.1)
CIFAR-100 (LR-0.01)
Testener Varaabiity
D8 sonaiii
Agpe 06 noriiii
Varib
Veduslliy
2
1:2
Epoch
Spach
Epoch
Epochh
(a) Algorithm DB variability and test error vs. training time
CIFAR-10 (LR=0.1)
CIFAR-10 (LR=0.01)
CIFAR-109 (LR=0.1)
CIFAR-100 (LR=0.01)
8
Test emor
Test
Test
Algorithi DB variability
Algorithm DB variailitty
Algorithm DB variability
Algonithm DB variability
(b) Test error vs. algorithm DB variability
Figure 2: (a) Plots of algorithm DB variability and test error as functions of training time (LR is learning rate). (b) Scatter plots of test error to algorithm DB variability (LR is learning rate). The points are collected from different epochs. Each curve and point is calculated and then averaged on 10 trials.
4.2 ALGORITHM DB VARIABILITY AND TRAINING TIME
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 very similar curve w.E.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 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]
4.3 ALGORITHM DB VARIABILITY AND SAMPLE SIZE
We next investigate how sample size impacts the algorithm DB variability. 100 ResNet-18 18 are trained on five training sample sets of different sizes randomly drawn from CIFAR-10 and CIFAR- 100, 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.E. the training sample size; (2) larger sample size, which intuitively helps obtain more smooth estimation of the decision boundary, also contributes to smaller algorithm DB variability; and (3) there is significant positive correlation between test error and algorithm DB variability, which fully supports Hypothesis) [
4.4 ALGORITHM DB VARIABILITY AND LABEL NOISE
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
5

---

Under review as a conference paper at ICLR 2022
CIFAR-10
CIFAR-100
CIFAR-10
CIFAR-100
Aggrrthmm DB carabiity
Tecterrr 413 Varibbliyy
Test enror
Mariabilly
Test emrr
Alp 7hm 96 vatueblliyy
Var ability
Va Ra
Tost oner
oe
1
Op
Eroer
012
610
03
2010
Sample
Epoch
Epoch
(a) Algorithm DB variability sample size
(b) Algorithm DB variability vs. time (label noise)
Figure 3: (a) Plots of algorithm DB variability and test error as functions of training sample size on CIFAR- 10 and CIFAR-100. (b) Plots of algorithm DB variability and test error as functions of training time with the existence of 20% label noise on CIFAR-10 and CIFAR-100. Each curve is calculated and then averaged on 10 trials.
algorithm DB variability still share a very similar curve w.z. the training time with the existence of label noise; and (2) the algorithm DB variability also undergoes epoch-wise double descent during the training process, especially in the left panel of Figure [3b]] 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.
4.5 THEORETICAL EVIDENCE
In this section, we explore and develop the theoretical foundations for the algorithm decision bound- ary variability on data generating distributions.
Assumption 1. The decision boundary of the classifier network fe on data generation distribution D is set with measure zero.
Corollary 1. Let fx(x) R²" + R be a classifier network parameterized by 0. If Assumption holds for all 0 ~ Q, then, for all E {1,-.. ,k), we have
E(XNND [[(i E T(Ja, x)) = Exx,) [[(([o, x) = =()]
(9)
and
Exxy)~D [l(i & T(fo, = ExxY\D [[ x) # f)].
(10)
4.5.1
ALGORITHM DB VARIABILITY SAABLII LOWER BOUNDS
Theorem (lower bound on expected risk). Let fo(x): R + R be a classifier network parame- terized by 0 and let Q(0) be the distribution over 0. Then, Assumption holds for all Q. we have
AV
RD( 2
(11)
2
where AV (ff. = Exx 0 II (T(fo, + T(for x))] is the algorithm DB variability for fo on data generating distribution D.
The iroof is given in Appendix C.I Theorem provides lower bound on the expected risk RD (Q) based on the algorithm DB variability AV AV D), and the lower bound presents that the Gibbs clas- sifirr fo 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 tighter lower bound:
Theorem 2 (lower bound for binary case). Let fo(x) : R² RR2 be binary classifier network parameterized by and let (()) be the distribution over O. Suppose the expected risk Rx(Q) S and Assumption Toold for all 0 Q. then we have
/ 2AV (fa,
( 2
(12)
2

---

Under review as a conference paper at ICLR 2022
4.5.2 AN ALGORITHM DB VARIABILITY-BASEH UPPER BOUND
Before we present the upper bound based on the algorithm DB variability, let us introduce the assumption used in this section.
Assumption 2.
2 E E(x.)) E [T T k k+1 Ro(Q),
(13)
where E (1, , and is the number of potential categories.
With Assumption 2 we can derive the upper bound on the variance of risk:
Lemma (upper bound on risk variance). Let fa(x) IR" + R be classifier network parameter- ized by f and let Q(0) be the distribution over O. Suppose Assumption and hold, then have
(fo. k-1
(x.()))) Ea~ (1 $ T ( x))Il S
(14)
where AV DD
D) = ((x,))) -pe I1 (T (fe, x) + T [))]] is the algorithm DB variability
of fo on data generating distribution D.
The proof given in Appendix
C.3
Hence, the next theorem is direct consequence of the one-
sided Chebyshev's 's inequality: Pr
E 21
- Zi > a] S
Var[2,] for any 0.
2maa
Theorem (PAC upper bound on expected risk). Let fo(x)
: R + R be classifier network parameterized by 0 and let (Q)) be the distribution over 0 w.r.t. the training set S. Suppose As-
sumption T and hold. Then, with the probability of at least 1 8 over sample of size m, we have
AV D)
RD(Q) (2(
(15)
2m 1)8"
The above theorem presents that smaller algorithm DB variability AV D) contributes to a tighter upper bound the true risk, which theoretically verifies Hypothesis I that neural networks with smaller algorithm decision boundary variability possess better generalization performance.
DATA DECISION BOUNDARY VARIABILITY
In the previous sections, we introduced the algorithm DB variability, which measures the decision boundary variability caused by the randomness 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 fo(x) R + R be classifier network parameterized by 0, 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 r--ubset of S if [Spl [
Then, if we fixed and
inf
Bo-.))) (T # T(Jo. =
(16)
the decision boundary of fA(S) said to possess a (c, d)aa decision boundary variability.
The data decision boundary variability contains two parameters of and n, respectively. That Gibbs classifier fA(S) has (e, -daat DB variability means that only the proportion of n 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"; provide detailed discussion in Appendix B.2 due to space limitation.

---

Under review as a conference paper at ICLR 2022
Maseso Masose
Mi m00000
203000
Missodo
3030000
26
04
22 0.1 0.8
10
02
9.4 0.8
1.5
(a) 17-6 curves CIFAR-10
(b) 5/-6 curves on CIFAR-100
(c) Schematic diagram
Figure 4: (a) The THE curves on CIFAR-10 with different training sample sizes 2000 (m22000), 2000 (m2000), 10000 (M10000). 20000 (M20000), and 50000 (mo5000u), respectively. (b) The 17-c curves on CIFAR-100 with different training sample sizes. (c) The schematic diagram of the 17-c curves w.r.f. small (m²), medium (17m), large (ra1), and infinite (m)) sample sizes, respectively.
5.1 77-6 CURVES ABOUT DATA DB VARIABILITY
According to Definition 5.1 the data DB variability degrades to the algorithm DB variability (V D) when S, = S. In other words, the algorithm DB variability is special case of the data DB variability with = 1. Therefore, the data DB variability could present more detailed in- formation on reflecting how the decision boundary variability depends on the training set, especially when we observe the variation of the reconstruction error w.r.f. different 1).
To explore the relationship between the reconstruction error and the proportion of subset r,, we train 1000 networks of ResNet-1e 18 on CIFAR- 10 and CIFAR- 100 of different sample sizes m, respectively. Albeit finding the most suitable susuueet 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 s--uubset for given training set S and proportion 1) (full list of 7j involved our experiments is presented in Appendix (A.36)). Then, through repeatedly training the network on S,, we can estimate the reconstruction error e. The 17-6 curves of CIFAR-I0 and CIFAR- 100 are presented in Figure 4(a) and 4(b) respectively. From the plots, we have observation that there is a more rapid decline in e 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 1p-c curves w.r.t. different sample size m, as shown in Figure [[c]] When = 0, f'A(S.)) cannot be better than random K. where & is the number of potential categories. We have noticed that
guess, and hence has a sharper drop along with 7) 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 - oc, then we have + 0 when - 0.
These plots indicate that the area under the 17-6 curve could be a more meticulous predictor for the generalization ability of neural networks compared the algorithm DB variability, which only point on the 77-6 curve when = 1. Hence, the area under the 1/-6 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 17-r curve, it produces more stable decision boundaries with varying training subsets. In the following section, we will theoretically establish the connection between the parameters and and the generalization ability of neural networks.
5.2 THEORETICAL EVIDENCE
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 f(As)) possess a (E, daaa DB variability, then we have
(R((A()) - RD(A(S,)) 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
8

---

Under review as a conference paper at ICLR 2022
bound the difference between their empirical risk on the same training set S with the probability 1-6: 6:
Lemma 3. If the decision boundaries of f(A()) possess (e, n) data DB variability, then, with prob- ability of at least 1 - 8 over a sample of size m, we have
Rs(A(),))) S Rs(A(S)) + 2m
log +
(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 least 1 over sample of size m, have
Rs((()))) &
log +
(19)
2m
Theorem (data DB variability-based upper bound on expected risk). If the decision boundaries of [A(S) possess (e, data DB variability on the data generating distribution D, and assume 1/ S 0.5
and the empirical risks Rs((A(8) Rss, (A(S,)) 0, then, with the probability of least 1 5
over a sample of size m, we have
Ro(A(S)) S Q 44A 8A+C,
(20)
where
Ω 1 - V
log
+
(21)
2m
1
A n log
log
(22)
m
Moreover, for sufficient large m, we have
1 17
RD (A())) s 00
+ n log
(23)
mm
The proof is omitted here and is given in Appendix C.7 According to Assumption when m + 00, then v 0 and 0. and according Eq. 23 RD(A(S)) - 0. Therefore, the generalization bound is asymptotically converged. Theorem presents preeeemppreeents that smaller data DB variability, iee, smaller and 7/. contributes to 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.
6 CONCLUSION AND DISCUSSION
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 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 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 de- mand 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 werr-paammeterized 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 special case of the data DB variability. Therefore, unifying the theoretical works about algorithm DB variability and data DB variability will be promising direction in future works.
ACKNOWLEDGEMENT
The authors sincerely appreciate the anonymous reviewers for their valuable suggestions.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalizze margin bounds for neural networks. arXiv preprint arXiv: 08498, 2017.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20( 20(1)22255-301,, 2019.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15841111544-4-444..-- 2019.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT pp. 177-186. Springer, 2010.
Cody Coleman, Christopher Ych, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In International Conference on Learning Representations, 2020. URL https: oopenreview http://weeeettooommiodoooooooooo
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Conference On Learning Theory, pp. 297-299. PMLR, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Shuyue Guan and Murray Loew. Analysis of generalizability of deep neural networks based on the complexity of decision boundary. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 101-106. IEFE, 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-12221 1234. PMLR, 2016.
Fengxiang He, Shiye Lei, Jianmin Ji, and Dacheng Tao. Neural networks behave as hash encoders: An empirical study, arXiv preprint arXiv:2101.05490 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Warren He, Bo Li, and Dawn Song. Decision boundary analysis of adversarial examples. In Inter- national Conference on Learning Representations, 2018.
Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, and J Zico Kolter. Assessing generalization of sgd via disagreement. arXiv preprint UrXiv:2106.13760 2021.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference Machine Learning, pp. 1724-1732. PMLR, 2017.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in Neural Information Processing Systems, 32:3496-355 -506, 2019.
Minguk Kang and Jaesik Park. Contragan: Contrastive learning for conditional image gen- eration. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 21357-21369. Curran As- sociates, Inc., 2020. URL http:: httpp:::/poocoednggg www.ediiiinnnnnnnnnneeeee htppsccc/ll httppps..ceppppr//2///1111. F490c742cd833 8b8ee 1a
pd
10

---

Under review as a conference paper at ICLR 2022
Hamid Karimi, Tyler Denr, and Jiliang Tang. Characterizing the decision boundary of deep neural networks, arXiv preprint arXiv:1912.11460 2019.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gameet (eds.), Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019. URL /
p ngs nwurips.pp....
Pwper. pdf
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks, arXiv preprint wrXiv:170.06688) 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
David Mickisch, Felix Assion, Florens Greßner, Wiebke Günther, and Mariele Motta. Under- standing the decision boundary of deep neural networks: An empirical study. arXiv preprint arXiv:2002.018/00 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.02299 2019.
Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners good offline generalizers. arXiv preprint arXiv:2010.08127, 2020.
Guillermo Ortiz-Jimenez, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Hold me tight! influence of discriminative features deep network boundaries. arXiv preprint arXiv:2002.0634 2020.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. the spectral bias of neural networks. In International Confer- on Machine Learning, pp. 5301-5310. PMLR, 2019.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. arXiv preprint arXin:2006.07710, 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 2014.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin- Yu Chen, and Yupeng Gao. robustness the cost of accuracy?-a comprehensive study the robustness of 18 deep image classification models. Proceedings of the European Conference on Computer Vision (ECCV), pp. 631-648, 2018.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312,6 /2929999999... 2013.

---

Under review as a conference paper at ICLR 2022
Vladimir Vapnik, Esther Levin, and Yann Le Cun. Measuring the ve-dimension of learning ma- chine. Neural computation, 6(5):851-876, 1994.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv preprint arXiv: .05223,662.... 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016a.
Sergey Zagoruyko and Nikos Komodakis. 1705.07660, 2016b.
Wide
residual networks.
arXiv preprint
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pp. 7472-7482. PMLR, 2019.
Shengyu Zhao, Zhijian Liu, Ji Lin, Jun-Yan Zhu, and Song Han. Differentiable augmentation for data-efficient gan training, arXiv preprint arXiv:2006. 10738, 2020.
12

---

Under review as a conference paper at ICLR 2022
A
ADDITIONAL EXPERIMENTS DETAILS
This section provides all the additional details of our experiments.
A.1 DATASETS
Our experiments are conducted on two public datasets (CIFAR-I0 and CIFAR-I00 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 50, 000 training images and 000 test images from 100 different classes. One can download CIFAR-10 10 and CIFAR-100 from https:// www. cs soronto..ed..
far .tmll
Fake CIFAR-10 consists of 100, 000 test images from 10 different classes. The fake CIFAR-I0 generated by conditional BigGAN (Zhao et al. 2020). The pre-trained Big- GAN is provided by Kang & Park (2020) and can be download from https:://rive
google com drive folders /wwp//xv////// WWPPPPPPPWMMM.. 8pp 2Eb5F Thk
Fake CIFAR-100 consists of 100, 000 test images from 100 different classes. The gener- ation of fake 110 is similar to it of fake CIFAR-10, while the training set for the BigGAN replaced from CIFAR-10 to CIFAR-100.
A.2 MODEL ARCHITECTURES
We use different neural network architectures in our experiments, including Y6G-16, ResNet-18, and WideResNet-28. The architectures are presented in Table
Table I: Detailed model architectures for CIFAR-10/100
VGG-16
ResNet-18 WideResNNet22-100
(3 3, 32) x
3 3, 64
3, 16
maxpool, 2 x
(3 x 3, 128) x 2
3 x 3, 64
3 x 3, 160
x 2
4
maxpool, 2
3,64,4
x 3, 160
(3 x 3, 256) x 3
3 3,3,122
3 x 320
maxpool, 2 2
3x 128
X
3 x 3,
x 3, 512)
3 256
3 x 3, 640
x
4
maxpool, 2 x 2 (3 3, 512) 3 maxpool, 2 x
3 x 3, 256
3 x 3, 640
3 3, 512
x 2
X 3, 512
fc-4096
avgpool
avgpool
fc-4096
fc-10/100
fc-10/100
10-10/100
A.3 IMPLEMENTATION DETAILS
This section provides all the additional implementation details for our experiments.
A.3.1 MODEL TRAINING
We employ SGD to optimize all the models and the momentum factor is 0.9. The weight decay factor is 5e-4, and the learning rate is decayed by 0.2 every 50 epochs.
13

---

Under review as a conference paper at ICLR 2022
A.3.2 ADDITIONAL DETAILS IN SECTION 4.1
We train VGG-16, ResNet-18, Wide-ResNet-288 on CIFAR-IO and CIFAR-I00. In the training pro- cedure, the model is trained for 200 epochs, in which the batch size is set to 128, and the learning rate initialized as 0.1. There are three training strategies included in this experiment: standard training. non-data-augna augmentation training, and adversarial training. In the adversarial training, the radius of the adversarial perturbation is set as 10/255 and (o distance selected. The basic data augmentation (cropping and flipping) in the standard training and adversarial training is achieved by the following Pytorch code:
trans transforms forms. RandomCrop (32, padding-4) transforms Randenoorizoon www.srriiioottaaiplloo
The experiment repeated for 10 trials for each (dataset, architecture, training strategy) setting.
A.3.3 ADDITIONAL. DETAILS IN SECTION 4.2
We repeatedly train 10 ResNet- 18 on CIFAR-10 1- and CIFAR- 100A, respectively, with different random seeds. In the training procedure, the model is trained for 200 epochs, in which the batch size is set 128, and the learning rate is initialized as 0.1 and 0.01, respectively. Basic data augmentation is included during the training process.
A.3.4 ADDITIONAL DETAILS IN SECTION
We randomly sample examples from the training set of CIFAR-I0 and CIFAR-I00 to form five datasets with different sizes of [2000, 5000, 10000, 20000, 50000]. respectively. 10 ResNet-18 trained for each dataset. In the training procedure, the model is trained for 200 epochs, in which the batch size included during the training process.
128, and the learning rate is initialized as 0.1. Basic data augmentation is
A.3.5 ADDITIONAL DETAILS IN SECTION
We randomly change the labels of 20% examples the training set of CIFAR-10 and CIFAR- 100. Then, 10 ResNet-18 18 optimize by SGD for 500 epochs the noise CIFAR-10 and CIFAR-100. respectively. the momentum factor 0.9, and the learning rate is 0.001 and does not decay during the training process.
A.3.6 ADDITIONAL DETAILS IN SECTION 5.1
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 cach dataset, obtain 10 77-ubsees with different 17 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 re- com/ stanford futuredata/
lated code be downloaded from /ttps::/giitht se selection via via-proxy The ResNet-18 18 is repeatedly trained for 10 trials to estimate the com- plexity of decision boundaries for each susbett..
14

---

Under review as a conference paper at ICLR 2022
B ADDITIONAL DISCUSSION ON DECISION BOUNDARY VARIABILITY
B.I ALGORITHM DB VARIABILITY AND THE ENTROPY OF DECISION BOUNDARIES
If Assumption holds for all f Q AV D) be rewritten as
(akxy~-EBo,rre (To. x) = T (Jo, x))] = E (x,)~ Σ 2 (T x) = =]]] (24)
The term Ei 0 [I(T (So, x) = i)] can be considered to measure the degree of prediction uncertainty for the given voxel x in the input space R=. If we leverage - -og(()) on the term Ei 12 [I[ (fe, x) i)], then - log Ei_, 12 [[[ (So, x) - i)] denotes the collision en- tropy of prediction made by the Gibbs classifier fa on x. We can also replace the collision entropy with canonical Shannon entropy Σx Ee- [I( (fo. x) = 2)] log Eo- [T(T (fo,
x) +)] 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 inves- tigating this low entropy of decision boundary.
B.2 DATA DB VARIABILITY AND THE COMPLEXITY OF DBS
complex decision boundary is considered to own large cur- vatures 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 pro- cedure should be the significant non- linearity of the training data. If only the geometrie 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 curvature is not rational and impractical.
According to Guan & Loew 2020
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 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 fe()) RR" - RR be a classifier network parameterized by O, where 0~ 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, C S as
a ny-subset of S if [S.] [S]
n7. Then, if we fixed 1 and
inf E ((x.))/DE of [T((J,, + T(Jor x))l =,,
(25)
S,Cs
the decision boundary of fA(S) said to possess a (e, compllexxy
Implications about the complexity of DB. With Definition B.I we could more intuitively under- stand 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 non- linear and contain more "support vectors": (2) in adversarial training. each data point is converted to "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 DD Hence, data augmentation decreases the complexity of decision boundaries by greatly expanding the training set S, while [S,] has only slight growth. Besides, ac- cording to our theoretical results in Section it can be verified that neural networks with simpler decision boundaries possess better generalization performance.
15

---

Under review as a conference paper at ICLR 2022
C
PROOFS
To avoid technicalities, the measurabiityyintegrallly issues ignored throughout this paper.
Moreover, Fubini's theorem assumed to be applicable for any integration w.E.. multiple vari- ables. In other words, the order of integrations is exchangeable. We also use [ our proof for simplicity.
to denote [E]-]]
C.1 PROOF OF THEOREM 1
Proof. If Assumption holds for all 0 Q we have
(T # (for x))] =0
(26)
Hence,
AV D) -Bxx,) ~ ((o
(27)
T(fo,
(28)
+ T
xi)]
(29)
<2Rx(Q)
(30)
The proof is completed.
C.2
PROOF OF THEOREM 2
Proof. When the classification is binary, i.e., k = 2, with Assumption ! we have
(31)
BB
BonG 0 [1 7 x)]] - E(x,y)~DE [I $ T (So, x))]
(32)
=BixUIN 2 E (Te, x)) - E(x,)DD 1- Ean [Ty E (Jo,
(33)
-2E B2_ [T E (Je. x)) (R -1
(34)
Plugging in Var(x))> Eoo (T T (fo,x))) Exx,) (
(1
( yields
Bxx
(35)
(B (1 E (f) (3(() + Ro(2))²
(36)
+ (1-
(37)
Plugging in AV (fe. D) = 1- Ex. 02 (T T(for
for x))] and solving the inequal- ity yield the desired inequality and finishes the proof of Thhorem
16

---

Under review as a conference paper at ICLR 2022
C.3 PROOF OF LEMMA 1
Proof.
Without loss of generality, we assume that all examples are belong to the first class, i.e.
y 1. Hence, for 1 AV D) Eo [I (T (So, x) (Sor, x)]], we have
DD 3 (fo. x) = =T (for,)) x))]
(38)
= (x
R @ (T (Jo, x) = =i]
(39)
Bang (Jo. x) -y)l + d
-Bix,yi~D
Σ g [ (Jo, =
(40)
(1=
-Bix.yinD
Σ
B [T (T (T(),, (Jo,x)=1]] =
E ang (T = =ii]
(41)
1=2
i=2
k
k
51 + 2
Σ
E (x)D) E2 0 [T (T x) = =1)] -2 -
R (I)) [T (so, x) = i)
i=2
+2 Σ
(Box))- (T
(T (fo. x) =i]] ((x [1 (T (So, x) = -])))
(42)
<>j>1
k
<1 + 22)
E E(xx))> BangDDBBnnh (Jo, =i]] Σ
E (xxx) (I (fo, x) = i)]
1=2
+ (k: 2)
- (T' (T' x) = i)))
(43)
k
k
<1 + >
E Exx,)) 1 xf) = i)] -2 -1]--2 -
E(x.j)-DEo (I (fo.x) x) = i)]
i=2
i=2
+ (k: 1)
(E (Bx.N)-DRo-e1101
(T (Jo, x) = i)))
(44)
The penultimate inequality holds because 2p:P, S pē + pz. Moreover, the variance of Eawa [T (y & T (fo,x)) is
Var [Boo (T x) v]]l
(45)
=I LD [I (T (fo. x) + y)] - B -
# v)l.
(46)
plugging the equality into Eq. 44 yields
1 1-AV 1-AV(fe, D)
<1 - (k - 1) Var Ea-e (I (fo. x) + r)]l + (k- - 1)E Bong [T (Jo, x) + v)l
4:
(k: 1) Eo x) + أ)لl + (k- - 1)
(x.)) Eo (I (fo. x) = i)]
E
k E (x.w)) Eg_q (T = 1)] -2 Σ
k
Σ + 2
E BIx (T x)= =
(47)
Then, because Eg (T (Jo, x) # U) = Σhz Ea- (T (Jo, x) = 1)], we have
E EX II (T (fo. x) i) S E2 Band [I (T (fe. x) # v)
(48)
and
Σ
Exx.)DDB E2 (T x) = +)) s Exx,nj EE (fo. x) + +y)l.
(49)
17

---

Under review as a conference paper at ICLR 2022
Therefore, Eq. 47 can be scaled to
(k: - (x))))) [Ba- [] (T' (fo, x) + :)]l
<AV +)+ (K: + 11)++11))))000)0)) (x)))) [1 (T (fe. x) + v) - Σ
(I (fe. x)
i)]
1=
(50)
Then, with Assumption 2 that ing incquality w.r.f. the variance:
(1v $ T (fe. x))] S
2 RD()),
we get the follow-
K+I
AV D)
(x))x Eo ( (fo + b)ll
(51)
k-
The proof is completed.
L
C.4 PROOF OF THEOREM 3
Proof. For the random variable Zi, recall the one-sided Chebyshev's inequality that
1 Σ Z
Var(Z1]
Pr E[Zi]
(52)
2ma²
t=1
Let Z; = Ea-q [T(y (yt & T (Jo, x:))], so we have
(x Eang [1 $ T (fo, x))l
Pr (Q) - Rs (Q) a] S
(53)
2ma
Plugging Lemma 1 into the above inequality yields
AV D)
Pr (Q) Rs( > a)
(54)
2m 1)a²
Plugging in 8 = 2m 1)a yields the desired inequality and completes the proof.
(o.
C.5 PROOF OF LEMMA 2
Proof. From the definition of the complexity of DB, there exists a 7y-subset Sn s.t. (T x) * x =c cc
Exx.))-DEo
(55)
Recall the LHS (D(A(S) (D(As))))) then
LHS
((x [1 (y & T T(je, x))]
(1 $ T(fo,)))]
(56)
Bis.ppicpDEo--sss,.......11 [I (y $ T(fo, x)) - 1 $ T(for x))] []] $ T(Jo, x)) 11 $ T(for x))l
(57)
< Bix.))-DEo0A11)00-444
(58)
S Bxxc))-PEo-Ass)00--.55 (T x) + T(for, x))] =E
(59)
The proof is completed.
C.6
PROOF OF LEMMA
3
Proof. Let
J B.x.))=D (
[T x) # (((oo,))))
(60)
E o. (TT(ff + Tf x:))]
(61)
By applying Hoeffding's Inequality, we have
Pr [a 2 t] < exp(-2mt²).
(62)
Plug in 5 exp(-2mml into Eq. 62 thus, with the probability of at least - 6, we have
p s
log
5
log +
(63)
2m
2m
Following the proof of Lemma
2 we can derive the inequality of (s((A(s))) - Rs(
A.
Plugging this into Eq. 63 yields the desired inequality and concludes the proof of Lemma 3
n
18

---

Under review as a conference paper at ICLR 2022
C.7 PROOF OF THEOREM 4
We first introduce Lemma 4 and Lemma 5 as below.
Lemma 4 (Lemma 30.1 in (Shalev-Shwarte
Ben-David 2014)). Assume T and are two datasets independently sampled from the data generating distribution D, then, with the probabil- ity of at least we have
Rx(A(T)) S RV(A(T)) 2Rv (A(T)) log(1/0)
llg(1/8)
(64)
[V]
[V]
Lemma 5 (Theorem 30.2 in Staaev-Shwarrs Ben-David 2014).. Let S, be a 77-sunnet of the dataset S, which is sampled from the data generation distribution D and the sample size |S]
Let S S = S - S, and assume v) S 0.5. Then, with the probability of at least á over a sample of size m, we have
RD(A(S,)) S Rsys, (A(S,)) + / (ARS,,,(A1S,))) 84,
(65)
where
A = nlog e + log
1
(66)
11
8'
Proof of Lemma
2Rs log(1/))))((())) |S,,S,1
4 1og(110))
ss, S.st.. RD(A(S,)) S Rs(s,(A(S,)). +
S
(67)
2Rsys, (A(S,)) log(1/0) log,,)
4log(1/0)
Σ
Pr Ro(A(S,)) Rsys. (A(S,)) +
S
S
(68)
m
mm c
8
(69)
1jm
Plug 8' nmm
5, and use the assumption 1) S 1 which implies |S),8,1 2 2 then, with the
probability of at least 8', have that
RD(A(S,)) (A(S,) &Rs,s, (A(S,)) (nlo n m
1 log
1 8
+8 17 17 e
1
log 8
n m
(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 With the assumption of zero-training error that Rs(A(S)) = we can derive the follow inequality:
1
R.y.s, (A(S,)) = 1 (Rs(A(S,)) - Rs,, (A(S,))) = 1- Rs(A(S,))
(71)
Then, by plugging the above equation into to Lemma 3 with the probability of at least 1 5, we have
1
(V
1
Rsy,, (A(S,)) <
2m log +e g
(72)
1-
Through combining this with Lemma with the probability of at least 1 - 28, have
Ro(A(S,)) < Ω V40A +A,
(73)
19

---

Under review as a conference paper at ICLR 2022
where
Ω
log
+
(74)
1 1
2m
= 1 log
log
(75)
8
Plugging the equality of RD (A (8)) RD (A (S,)) in Lemma bility of at least 1 - 26, we have
2 into Eq.
73
with the proba-
Ro(A(S) - Ω + 4NA + +
(76)
Plugging in 8' = 20 yields the desired inequality of Eq. 20
When is sufficient large, V4ΩA can be dropped due to V V4DA S St + A. Considering 17 S 0.5, Ω S 2
log 1 +E) O mm + E). The term log &/ in A can be dropped because it has
2m
faster convergence speed compared we have
V 2m log 3 in S2. Because log 3 is considered as constant,
RD(A(S)) s 00 Tm + + 1lo - 17 The proof of Theorem is finished.
D ADDITIONAL EXPERIMENTAL RESULTS
This appendix collect experimental results omitted from the main text due to the space limitation.
D.1 ADDITIONAL RESULTS FOR LEARNING RATE
Accroding to Li et al. 2019) that learning rate is a major factor of affecting generalization of net- works, investigate the relationship between algorithm DB variability and learning rate by training 20 ResNet-18 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
calculated at each epoch, as shown in Figure From the plots, we observe that: (1) the larger learn- ing rate 0.001 contributes 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
better generalization performance; and (2) algorithm DB variability
is well supported.
CIFAR- 10
CIFAR-11 10
0.7
LR=0.001
Algorithm DB variability
0.40
LR=0.001
0.5
LR=0.0001
0.35
LR=0.0001
Test error
0.55
0.3
0.20
0.2
0.1
0.10
50
150
200
150
Epoch
Epoch
(a) Test error vs. training time
(b) Algorithm DB variability vs. training time
Figure 5: (a) Plots of test error as function of training time (LR learning rate). (b) Plots of algorithm DB variability as function of training time (LR is learning rate). Each curve is calculated and then averaged on 10 trials.
20


Reviews:
[{"review_id": "m2zByd4ErNa", "reviewer": "Reviewer_3dWe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proof and empirical results are sufficient to show the claim. All claims are clarified and clear to understand, the organization of the paper looks good. \n\n(1) I have some issues concerning the theoretical aspects.\n \n1. Assumptions 2--3 can be sound. These conditions are essential for the proof. When these conditions break down, what will we observe? In the binary classification, assumption 3 means the correct classification on average for any $(x, {\\bf y}) \\sim \\mathcal{D}.$  \n2. Can you clarify the situation when the assumptions 2--3 are weakened? \n\n(2) In addition, simulations studies to validate the claims are limited since we cannot know the causality between prediction variability and generalization due to various confounding effects. If you consider the causal graph to address this issue, the claim can be strong. In this case, I can only know the correlation, not causation.  \n\n    \n    ", "summary_of_the_paper": "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.\nThe paper considers two types of variability with respect to algorithm and training data. In any case, lower variability ensures higher performance in generalization.    ", "summary_of_the_review": "There is a valuable empirical analysis for the prediction variability. However, the more realistic cases should be considered.\nAdditionally, to validate the claim of the proposed, assumptions 2--3 should be checked in experiments.     \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "g9ZrKgi9tn", "reviewer": "Reviewer_kiZ8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main concern about this paper is how well the findings hold in a more realistic setting, given the strong assumptions made in the limited experiments and several confusions in the theoretical part. \n\n1. Although the authors see a certain level of negative correlation between the decision boundary (DB) variability and generalization, the variability may not be a reliable characterization of generalization unless the following confounding factors are well addressed:\n\n   * Training steps: models trained with different numbers of steps may have different variabilities but the same generalizability. for example, the claim that algorithm DB variability is zero on the linearly separable data is not true unless SGD takes infinite steps and other assumptions hold [1]. So training with different numbers of training steps, the variability would change. While after a certain amount of steps, which is often observed empirically, the generalization gap stops changing. In this case, the variability does not well reflect the generalization - more experiments are needed to understand this.\n\n    * Label noise: continue with the training steps, if there exists some level of label noises and consequently epoch-wise double descent [2], the connection between training steps and generalization is even more complicated. Does the DB variability still characterize the generalizability?\n\n    * Factors that may increase the DB variability while improving the generalization: there are cases where instabilities of the training process leading to better generalization, for example, dropout and large learning rate [3]. Do such instabilities also lead to larger DB variability? If so, why is better generalization achieved? \n\n    * The current observations on the negative correlation between DB variability and generalizability can probably be both explained by over-parameterization. And in the other cases like those listed above, it is unclear whether the correlation still holds.\n\n2. The quantification of the DB variability depends on the data generating distribution, which is however vaguely defined in the paper. For the two-moon dataset, the data generating distribution seems to be the $\\mathcal{R}^2$, and the authors empirically selected the rectangular grid in their experiments. But on the Cifar-10 dataset, the author picked the images generated by BigGAN as the data generating distribution, where the decision boundaries off the data manifold are excluded. \n\n3. The authors propose two factors, simplicity effect, and constraint effect, to account for the algorithm DB variability without rigorous definitions which have led to confusion. For example, when discussing the adversarial training under section 4.1, the paper says \"which (adversarial training) substantially decreases the inter-class distances and makes the training set more complex\", the authors seem to confuse the two factors into the same phenomenon. It is not convincing to me that significant the difference between these two factors is.\n\n4.  The motivation of the data DB variability is not clear to me. The authors motivate the data DB variability as \"the algorithm DB\nvariability hardly shows the decision boundary variability caused by changes in training data\". Why is that important in characterizing the generalizability? And the paper lacks the comparison between the bounds built upon the two variability metrics. It is not clear to me when one is more useful / tighter than the other and should be used.\n\nMinor:\n\n1. \"Remark 1. (1) If a input...\" -> \"Remark 1. (1) If an input...\"\n\n[1] Soudry, Daniel, et al. \"The implicit bias of gradient descent on separable data.\" The Journal of Machine Learning Research 19.1 (2018): 2822-2878.\n\n[2] Nakkiran, Preetum, et al. \"Deep Double Descent: Where Bigger Models and More Data Hurt.\" International Conference on Learning Representations. 2019.\n\n[3] Li, Yuanzhi, Colin Wei, and Tengyu Ma. \"Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks.\" Advances in Neural Information Processing Systems 32 (2019).", "summary_of_the_paper": "This paper proposes to characterize the generalizability with the variability of decision boundary instead of the margin. They show empirically that generalizability is negatively correlated with the variability and theoretically bounded by it. ", "summary_of_the_review": "For the reasons listed above, I think substantial experiments are required to better understand the phenomenon and confirm the empirical findings, rigorous definitions and clarifications are needed in the theoretical sections, and thereby my current rating.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PMwj7HG0DNk", "reviewer": "Reviewer_fXBi", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The notions introduced are rigorous and prove useful. The theoretical claims are supported by some empirical work as well. The bounds do not depend on network size and apparently reflect the behavior of practical and popular networks.\n\nSeveral bounds are presented, and while it is stated that they do not depend on model size -- implying other existing bounds do -- there is no comparison presented. When would these bound be more useful than existing ones? When are other be more appropriate (or tighter)? If these questions seem misguided, perhaps a short discussion of why the bounds derived do not need to be compared to existing ones would be helpful.\n\nI admit I am not so familiar with this domain and may have overlooked something.", "summary_of_the_paper": "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.", "summary_of_the_review": "The derivations of new bounds that utilize the proposed decision boundary variability measures are strong. The claims are supported by experimental results where appropriate. This paper would be even stronger with more detail/discussion about existing work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "3vLgmUObBB9", "reviewer": "Reviewer_pU8o", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverall, I think the paper introduces a number of interesting potential ideas for explaining generalization in neural networks.  But my initial read leads me to a number of questions and concerns before I can more confidently back this paper for acceptance; I've listed a number of them below.\n\n\n(1) For the central 'algorithm DB variability' claims, the primary experimental validation relies upon the three algorithmic variations of \"standard training w/ data augmentation\", \"adversarial training\", and \"standard training without data augmentation\".  My understanding is the primary purpose of these set-ups is to produce a plot like in Figure 2(c), comparing generalization of fixed models but changing algorithmic procedures, so as to discern a relationship between generalization and DB variability.  I feel the strength of this message would be improved if a small number of additional experiments further tested this hypothesis.  Some possible ideas: using different early-stopping schedules, or using progressively larger data subsets (e.g. using 10,000, 20,000, 30,000 training samples).  This would allow for a fixed model but a change in other parameters that can affect test accuracy.\n\n(2) The usage of BigGAN images to estimate variability seems tolerable but it would be best if there were some additional confirmation that the obvious alternative -- data subsetting, say keeping 5,000 random samples from the training set as a new test set and not using these in the training process -- would result in similar trends.\n\n\n(3) What is the intuition for why Assumption 3 is needed?  Can the authors give a verbal description of how this places a role in the proof in the main section?\n\n\nSome minor points/typos etc.:\n\np.1 and a few places: the notion of \"margin\" seems a bit muddled throughout.  The margin of a classifier f(x) is the largest distance gamma s.t. y * f(x) >= gamma.  The authors seem to be referring to the margin at a point x in terms of the largest rho s.t. y * f(x') has the same sign as y * f(x) for all ||x-x'|| <= rho; these are closely related only if f has a small Lipschitz constant as a function of x.  It is definitely the case that large margins in the former sense have good generalization performance (vs. authors' suggestion in p.1); this is shown in standard statistical learning theory.  But adversarial robustness  (the latter sense of margin) does not imply good generalization. \n\n\np.4, Sec. 4.1: Soudry et al. (2018) isn't really about neural networks; better references would be Lyu & Li (2020) and Ji & Telgarsky (2020) not 2018a (\"directional convergence and alignment\").\n\np.4: in Fig. 1, the authors say (c) plots DB variability as a function of sample complexity, but x axis is nonlinearity level?\n\np.7: Assumption 2 is missing an \"=j\" inside the second expectation\n\nAppendix A.1: what adversarial training method is used?\n\nAppendix B.2: how does Def B.1 differ from eta, epsilon DB variability?\n\nAppendix C: the E^2() notation is weird; does this mean [E()]^2 or E[()^2]?\nHow does one go from (50)-(51)?   Not clear on first read.\n", "summary_of_the_paper": "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.  ", "summary_of_the_review": "Overall, I think the paper introduces a number of interesting potential ideas for explaining generalization in neural networks.  But my initial read leads me to a number of questions and concerns before I can more confidently back this paper for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes the notation of DB variability, which is essentially prediction variance. It is also closely related to algorithmic stability which is a theoretically more sound notation to derive generalization bounds. The paper is a mixed bag of empirical observations and "theory". However, looking at the "theoretical results" in the paper, it is clear that the authors lack adequate theoretical background. 

I'd be more positive if the paper has been focused more on the former, and could be judged by the empirical part only. While the reviews were positive, I looked at them and realized that similar to the authors, the reviewers also lack theoretical backgrounds. 

First, the fact large variance implies a generalization lower bound is trivial, to the degree it is not worth stating as a "result". Second small variance implies a generalization upper bound isn't true. One can have a predictor that perfectly overfits the training data and predicts class 0 everywhere else. This has small prediction variance but poor generalization. In this context, the upper bound analysis of the paper is clearly misleading. Usually one compares training error to generalization error, where the estimator depends on the training set. In such case, one cannot use the simple argument of the convergence of the empirical mean of sum of independent random variables to the mean due to the dependency of estimator on the training set, e.g. in Thm 3. One needs to use uniform convergence and exponential probability (instead of Chebyshev) inequality to obtain such results. The right hand side of Thm 3 (the theorem itself is also very poorly stated. and shouldn't be allowed to be published) could not be interpreted as training error as should usually be the case for such bounds, but only as validation error. Such a result (comparing validation and test error when distribution isn't changed) has no value. 

I would not elaborate on other similar issues.  My recommendation is to focus on the empirical study if the authors are not familiar with theoretical analysis.
Decision: Reject