Comparative Generalization Bounds for Deep Neural Networks
Authors: Tomer Galanti
Liane Galanti
Ido Ben-Shaul
Venue: Accepted by TMLR ()

Abstract: In this work, we investigate the generalization capabilities of deep neural networks. We introduce a novel measure of the effective depth of neural networks, defined as the first layer at which sample embeddings are separable using the nearest-class center classifier. Our empirical results demonstrate that, in standard classification settings, neural networks trained using Stochastic Gradient Descent (SGD) tend to have small effective depths. We also explore the relationship between effective depth, the complexity of the training dataset, and generalization. For instance, we find that the effective depth of a trained neural network increases as the proportion of random labels in the data rises. Finally, we derive a generalization bound by comparing the effective depth of a network with the minimal depth required to fit the same dataset with partially corrupted labels. This bound provides non-vacuous predictions of test performance and is found to be empirically independent of the actual depth of the network.

Published in Transactions on Machine Learning Research (05/2023)
Comparative Generalization Bounds for Deep Neural Net- works
Tomer Galanti
galanti@mitt.c edu
Deportment of Brain and Cognitive Sciences Massachusetls Institute of Technology
Lianc Galanti
limegalaanti @mail. tau..c.il
School Computer Science
Tel Aviu University
Ido Ben-Shaul
ido www.bbennsuuu@@@@@aac.cc com
Department of Applied Mathematics
Tei-Aviu University
eBay Research
Reviewed on OpenReview: https: // openreview. net/ forum? id= k62T
Abstract
In this work, investigate the generalization capabilities of deep neural networks. We introduce novel measure of the elfective depth of neural networks, defined as the first layer at which sample embeddings are separable using the nearest-class center classifier. Our empirical results demonstrate that, in standard classification settings, neural networks trained using Stochastic Gradient Descent (SGD) tend to have small effective depths. We also explore the relationship between effective depth, the complexity of the training dataset, and generalization. For instance, find that the effective depth of trained neural net- work increases the proportion of random labels in the data rises. Finally, we derive generalization bound by comparing the ellective depth of net work with the minimal depth required to fit the same dataset with partially corrupted labels. This bound provides non- vacuous predictions of test performance and is found to be empirically independent of the actual depth the network.
1
Introduction
Deep learning systems have steadily advanced the state of the art in wide range of benchmarks, demon- strating impressive performance in tasks ranging from image classification (Taigman et al. 2014 Zhai et al.
2022
language processing (Devlin et al. 2019 Brown et al. 2020), open-ended environments Silver et al.
2016
Arulkumaran et al. 2019). to coding (Chen et al. 2021
Recent rescarch suggests that deep neural networks are able generalize well new data bocause they have large number of parameters relative to the number of training samples (Belkin al.] 2018 Belkin Advani et al. 2020; Belkin et al.) 2019). However, it has been shown that in these cases deep learning models can also precisely interpolate arbitrary training labels (Zhang et al. (017), phenomenon known as the "interpolation regime." " Understanding how deep learning models learn through interpolation is an important step towards a more comprehensive theoretical understanding of their successes.
2021
Traditional gencralization bounds (Vapnik 1998 Shaley-Shwartz Ben-David, 2014 Mohri et al. 2018
Bartlett & Mendelson 2003) are based on uniform convergence and are used control the worst-case gener- alization gap (the difference between train and test errors) over set of predictors that includes the outputs

---

Published in Transactions on Machine Learning Research (05/2023)
Duisent
MNNIST CONV-FL50
Fasiso MINIST
CIFARLIO
CIEARIO
Archrtectone
00NV-I-100
CONV-I-100
CONVRES-L-00
Degth (G)
To
12
15
10
12
15
16
18
20
16
TM
15
Test
0.0075
0.0004
0.0074
0.0236
0,0066
0
0,3920
0.2638
0.2448
0.2001
0.2504
The ecvor old.
0.0006
0,0000
10000
0.0844
000677
0,0099
01066
0,004
0.1
0.1
01
6.R
0.2
B4
0/4
0.8
0.1
bound
0.1
0.1
0.1
0.2
0.2
0.00
0.00
0.53
0.4
1m.m
Bartvet Mencvison
1:7fe117
2.750+335
Navslalez st
1.64406
7.925+407
8 6.90
4.636-406
2:233+4000
6061e400
Prolesttx
Neydaaorr
8856-408
8. 1010--005
2.316+077
2 2.800+00
2:330++00
1.776400
1.012++10
300866111
Spae 4,
Bustart
2801-405
6.412x-006
9.5004405
4.8064406
5.516-4066
9:1760406
1.1e+407
1.500+008
1.22a4-10
Sprc Vrob
Seydhisur 4t ml 170
3 39956-43
111100+00
1. 1.386+04
4.0095--01
2.8014001
2.53ee011
9 9.15306-D4
1.013e405
1 1003e400
Table 1: Comparing our bound with baseline bounds in the literature for networks of varying depths. Our error bound is reported in the fourth row, and the baseline bounds are reported in the bottom rectangle. While the test error is universally bounded by 1, the baseline bounds are much larger than 1, and therefore, are meaningless. In contrast, our bound achieves relatively tight estimations of the test error and unlike the baseline bounds, our bound is fairly unaffected by the network's depth.
of a learning algorithm. However, the applicability of these bounds to certain interpolation learning regimes has been called into question by Nagarajan & Kolter
(2019), who described theoretical scenarios where an interpolation learning algorithm generalizes well but uniform convergence bound cannot detect this. Sub-
sequent rescarch by Bartlett & Long (001)); Zhou et al. 2020); Negrea et al. (2020); Yang et al. (2021) has
also dernonstrated the limitations of uniform convergence in various interpolation learning siluutions.
Several recent papers have obtained non-vacuous bounds in various learning settings. For instance, Dziugaite & Roy (2017); Zhou ct al. (2019) adopted a PAC-Bayesian sctting where the network incorporates random weights, while Hellström & Durisi 2022) considers random compressed versions of the neural network. While these advancements have significantly contributed to the knowledge of generalization in deep learning theory, they are far from contemporary practice, which generally focuses on deterministic networks obtained directly through stochastic gradient descent (SGD). In a different paper (Biggs & Guedj] 2022). the authors derived deterministic generalization bounds for neural networks based on PAC-Bayes and stability. However, this analysis is limited to 2-layer fully-connected networks.
Contributions. In this paper, we present novel approach for measuring generalization in deep learning that does not rely on uniform convergence bounds. Instead, our bound suggests that model will perform well at test time if its complexity is small compared to the complexity of a network required to fit the same dataset with partially random labels. In other words, even if a trained nel has complexity greater than the number of training samples, it may still be less complex than a model that fits partially random labels. As a result, in such cases, our bound may provide a non-trivial estimato of the test crror. In contrast to previous non-vacuous bounds the literature, our bound applies to a wide range of neural networks, including convolutional layers, batch normalization layers, and residual connections.
To formally describe our notion of complexity, we use the concept of nearest class-center (NCC) scparability. This property states that the feature embeddings associated with training samples belonging to the same class can be separated using the nearest class-center decision rule. While earlier research (Papyan et al. 2020) found that NCC separability occurs at the penultimate layer of trained networks, more recent research (Ben- Shaul & Dekel 2022) has discovered NCC separability in intermediate layers as well. In this work, we introduce the concept of "effective depth" " in neural networks, which refers to the lowest layer at which the features are NCC scparable (soc Soc. 3.2
We have made several key observations about effective depths. First, we have found that the effective depth of trained networks increases as the amount of random labels in the data increases. Second, when training deep networks, we have observed that they tend to converge to an effective depth Lo. regardless of their actual depth L. This means that the feature embeddings of layers above Lo lend to be NCC separable. In addition, we have shown in Tab. [ that our bound on generalization is empirical, non-vacuous, and independent of depth, unlike traditional bounds. In Section 3.3 we further discuss the limitations of modern norm-basod generalization bounds (e.g.. Neyshabur et al. (2015): Bartlett al. (2017);; Golowich et al. (2020); Neyshabur et al. (2018)), along with the key distinctions wetween these bounds and the proposed bound.
2

---

Published in Transactions on Machine Learning Research (05/2023)
1.1 Additional Related Work
Emergent properties. There has been signilicant research on the geometrical properties of intermediate
layers in deep neural networks, such as clustering and separability (Papyan 2020
Tirer & Bruna, 2022:
Galanti et al.] 2022
Ben-Shaul & Dekel 2022 Cohen et al.) 2018 Alain & Bengio 2017 Montavon et al.
2011 Papyan et al.
2017 Ben-Shaul & Dekel 2021 Shwartz- Ziv & Tishby, 2017).
While previous studies
have analyzed these properties theoretically (Zhu et al. 2021 Xu et al. 2023; Lu & Steinerberger 2020;
Fang et al.) 2021 Ergen & Pilanci 202I), their specific role deep learning and potential relationship with generalization are not yet fully understood. We foeus on the question of whether these properlies are good indicator of generalization. In contrast, previous research (Zhu et al. 2021 has shown that such properties may occur even when training a network with random labels, suggesting that they may not directly indicate generalization. In this paper, we argue that effective depth can be used to measure the complexity of fitting a dataset, and show how this idea can help us predict test performance.
2 Problem Setup
In this section, we explain the learning setting used in our theory and experiments. We focus on the task of training model for standard multi-class classification. Specifically, we consider a distribution P over samples (z. y) where x belongs to the instance space N, and y belongs to the label space Ve with a cardinality of C. To simplify, we use one-hot encoding for the label space, where labels are represented by unit vectors in RCC and Ve {ec c II...,C} C} and eg is the cth standard unit vector in gC, We also use the notation y instead of y ec. The class conditional distribution of given y = c is denoted as Pa(-) = P(z E y = c].
A classifier hw : X2 + RC assigns soft label to an input point E XX and its performance on the distribution P is measured by the expected risk
Lp(hw) = ((l.
where e: RC Vcc [0, 00) is non-negative loss function (e-g., L2 or cross-entropy losses).
We typically do not have direct access to the full population distribution P. Therefore, generally aim to learn a classifier, h, using some balanced training data S == 3)) = S = - Ves (m( of m = C. ma samples consisting ma independent and identically distributed (i.i.d.) samples drawn from Pa for each c E [C]. Specifically, we intend to find W that minimizes the regularized empirical risk
m (bwh)) = m Σ (2.). + AI|W
(1)
where the regularization controls the complexity of the function hw and typically helps reducing over- fitting. Finally, the performance of the trained model is evaluated using the train and test error rales; ( : Em I[arg max, (w;)) # yl and errp(hww == B(zy)> [[aarg max, hw (x)e # vll. where I: (True, False] + (0, 1} the indicator function.
Neural networks. In this work, the classifier hw is a neural network composed of a set of parametric layers. is written as hw := ew, o fii, == ew, o gtv,, o...o ghy, where giv are parametric functions that map from 24 to R411, and ew, is a linear function that maps from Rd to RC. These layers can be standard linear convolutional layers (with ReLU activations) or residual block. To simplify, we denote fi : g" ..... g¹ and h == hw. The specific architectures we used in the experiments are described in Appendix A.1
Optimization. We optimize our models by minimizing the regularized empirical risk (h) using Stochas- tic Gradient Descent (SGD) for a certain number of iterations T with a regularization cocfficient À > 0. To do this, we initialize the weights Wo of h with a standard initialization distribution Q of our choice (e.g., a standard normal distribution the Kaiming He initialization (He et al. 2015)) and at each iteration, update W + W.- pa V Lg(h), where Me > 0 is the learning rate at the t-th iteration, and Š C S is subset of size B selected uniformly at random. Throughout the paper, we denote by W. the output of the learning
3

---

Published in Transactions on Machine Learning Research (05/2023)
algorithm starting from Wo- When Wo is not relevant or is obvious from the context, will simply write Wo h2 fs.
3 Neural Collapse and Generalization
In this section, we examine the theoretical connection between neural collapse and generalization. We begin by defining neural collapse, NCC separability, and effective depth neural networks. We then explore how these concepts relate the test-time performance of neural networks.
3.1 Nearest Class- Center Separability
Neural collapse (Papyan et al. 2020 identifies training dynamics of deep networks for standard classification tasks, in which the features of the penultimate layer associated with training samples belonging to the same class tend to concentrate around their class-means. This includes (NC1) class-features variability collapse, (NC2) the class means of the embeddings collapse to the vertices of a simplex equiangular tight frame, (NC3) the last-layer classifiers collapse to the class means up to scaling and (NC4) the classifier's decision collapses to simply choosing whichever class has the closest train class mean, while maintaining a zero classification error.
In this paper we focus weak form of NC4 we call "nearest class-center separability" (NCC separability). Formally, suppose we have dataset S = - of samples and a mapping f Rd - R2, the features of f are NCC separable (w.r.t. 5) if for all i [mi, we have h (xx4 Vss where
hy(+) arg min [1/(x) - (((x))"{(S))11 cE[C]
(2)
To measure the degree of NCC separability of a feature map f, use the train and test classification error rales of the NCC classifier top of the given layer, errs(hg) and errp(hy).
Essentially, NC4 asserts that during training, the feature embeddings in the penultimate layer become separable and the classifier h itself converges to the 'nearest class-center classifier' hy.
3.2 Effective Depths and Generalization
In this section, we study the effective depths of neural networks and their connection with generalization. To formally define this notion, we focus on neural networks whose L top-most layers are of the same size. We observe that neural networks trained for standard classification exhibit an implicit bias toward depth minimization.
Observation (Minimal depth hypothesis). Suppose we have a dataset There erists an integer Lg 2 1, such that, if we properly frain neural network of any depth L > Lo for cross-entropy ménémization on S using SGD with weight decay, the learned features f become (approzimately) NCC separable for all & e L).
We note that if the Lo'th layer of ft exhibits NCC separability, we could correctly classify the samples already in the Lo 'th layer of St. using linear classifier (i.e., the nearest class-center classifier). Therefore, intuitively its depth is effectively upper bounded by Lo. The notion of effective depth of a neural network is formally defined as follows.
Definition 1 (e-effective depth). Suppose we have dalasel S and neural network h eog ogg with g. RRd Rdd:, g²: IR.. - BR and linear classifier Rede+1 - RCC Let ha(x)) == arg min flf((z) Fr (S.)ll. The e-effective depth (1) of the network h is the minimal value i E [T.], such that, errs(he) (and (h)(h) = if such i E [L] is non-existent).
To avoid confusion, we note that the e-effective depth is a property of neural network and not of the function it implements. That is, function can be implemented by two different networks of different effective dept.s.
4

---

Published in Transactions on Machine Learning Research (05/2023)
Informally, our observation (Obs. 1 suggests that when two sufficiently deep neural networks are properly trained (i.e., when the optimizer effectively minimizes the loss function), they will collapse to identical effective depths. However, achieving this result requires proper tuning of the hyperparameters to ensure that the neural network can be trained to minimize the loss function effectively.
While our empirical observations in Sec. suggest that the optimizer learns neural networks of low depths, it is not necessarily the lowest depth that allows NCC separability. As next step, we define the e-minimal NCC depth. Intuitively, the NCC depth of a given architecture is the minimal value L N, for which there exists neural network of depth L whose features are NCC separable. As we will show, the relationship between the c-effective depth of a neural network and the c-minimal NCC depth is connected with generalization.
Definition 2 (c-Minimal NCC depth). Suppose we have dataset 5 = -U_ and neural network archilecture 14 = =gh gh .....g' g² with g² IRd, - IRdo and gf E C (g' g': R - Rdo for all i= 2..... L. The c-minimal NCC depth g G is the månimal depth I, for which there exist porameters W = (Wi] such that, f= fly- =gW, denole the e-minimal NCC depth by d (uin(9
Iw, o...o 9w, satisfies errs(hy) S e, where hy(x) == arg mic) [lf(z) pS((S)))l We
To study the performance of a given model, we consider the following setup. Let S (( ) and be two balanced datasets. We consider them two splits of the training dataset S, with
S2 - ( ) the classifier Wh representing the model selected by the learning algorithm using S,, and S₂ being used to assess its performance. It is worth mentioning that although the model may differ slightly between training and testing, we regard hs, as the function used during testing. For example, when the model incorporates Batch Normalization layers, we use mini-batch statistics during training. However, when evaluating the output model Wa on new data, we switch to using population statistics. We denote by X, = {-]) ym and the instances and labels in Sj.
1m
Y5 {w:) )m
To formally state our bound, we make two technical assumptions. The first is that the misclassified labels that ng. produces over the samples X₂ = u (=2 Tm are distributed uniformly.
Definition 3 (6m-uniform mistakes). We say that the mistakes of a learning algorithm A (S),W)) + hsg are un-ufoor,,, if with probability 2 - 5m over the selection of S1 ~ PB (m), the values and indices of We the mistaken labels of hs, over X2 are uniformly distributed (os a function of Wo ~ =Q).
The above definition provides two conditions regarding the learning algorithm. It assumes that with a high probability (over the selection of S1, S2), hg, makes the same number of mistakes on S2 across all initializations Wo- In addition, it assumes that the mistakes are distributed uniformly across the samples in S2 and their (incorrect) values are also distributed uniformly. While these assumptions may be violated in practice, the train error typically has small variance and the mistakes are almost distributed uniformly when the classes are non- -in-hierarllical (e.g., CIFAR10, MNIST).
For the second assumption, we consider the following term. Let p E (0,1/2), a E (0, 1), we denote
pappa = PP S. 3 2 (1+a) p: & Lin
(9. S1 U2) > Ry, ( (1, U U.S.]]]
(3)
Here, Y2 and y/ denote sets of random labels. These labels are generated by first taking the set Y2, then randomly selecting [pm] (Igm]) labels from this set. Each of the selected labels is then replaced with a random selection from the set [k]. Let 5₂ and Sg are datasets obtained by replacing the labels of Sg with yg and Y2 (resp.). We assume that 62 &m.pa is small. Mcaning, with a high probability, the minimal depth to fit [(2 p)m] correct labels and [pm]] random labels is upper bounded by the expected minimal depth to fit [(2 4)ml correct labels and [gm] random labels for any q 2 (1+ + a)p.
While explicitly characterizing the values of 82 p.p. can be challenging, it is reasonable to assume that 82 pm is small since it is necessary to increase the model's capacily when fitting larger amounts of random labels (refer to Figs. 3). In order words, in both cases, the model has to simultaneously fit a significant amount of correct labels and at the same time [pm] (or [gm]) random labels. Assuming that the target function y is realizable by a sufficiently deep network, as m increases, we can expect that the "majority" of the complexity required to fit. the data would be devoted to fitting the random labels. This is because fitting these labels
5

---

Published in Transactions on Machine Learning Research (05/2023)
typically demands increase in network complexity while the target function requires finite number of layers to implement. Therefore, grows large, we anticipate that the inequality follows primarily from the need for deeper networks to fit more noisy labels.
Although proving this assumption in its entirety is difficult, the following proposition provides some intuition by demonstrating that the expected minimal depth required to fit a given dataset with random labels tends to infinity when increasing the number of training samples.
Proposition 1. Let do, m. L 2 3 and let X {ai]= C Rdo be a set of m unlabeled samples. Let G {o(W> x + b) | W E Rdoxdo, b Rdd), where a is the ReLU element-wise activalion function. Lel Y (91 ........ Fm) be set of uniformly distributed labels in {+1} and S = {(z,, W.) Then,
Cym (1- 2E)
Ey ( (G] 2
(4)
do log(m)) Vlog do) log(em)
for some universal constant. C> 0.
In the above proposition, we consider binary classification problem (with labels {+1}) and lower bound the expected number of fully-connected layers necessary to fit arbitrary training samples with random labels. The proposition shows that the expected value of the minimal depth, (G, S), necessary to fit a dataset with random labels increases as the number of training samples grows. Specifically, when fixing the width du and threshold 6, the right-hand side of the equation grows in proportion to ym, implying that Ey [di (G, , S)] must also grow accordingly.
Based on the previous proposition, we can further establish that the O-minimal NCC depth required fit set of samples following the form described in equation 3 is expected to increase with the proportion p of noisy labels in the data.
Proposition 2. Let do, m, 3, and let S1, S2 C Rd x {=1} be two sets of labeled somples. Let Y2 be labels that are generated by first taking the set Y2 (the labels of S2), then randornl selecting [pm] labels from this set. Each of the selected labels is then replaced with a random selection from the set ==]] Let S2 be the same set as S2 with the labels Y2 replaced with Yz. Then,
pm
Ey, Ey,Idh S (9,S 2
(5)
do log( [pm]) / log(do) log(e [pm]]
for some universal constant C' 0.
Our generalization bound. Following the above, are ready to formulate our generalization bound. Proposition 3. Let m E P (0, E (0 and E (0. 1). Assune that the error of the learning algorithm is 5t, uninorrr Assume that S1. ~ Pn(m). Let Wo be the output of the learning algorithm given access to dataset S and initialization Wo. Then,
Es, (e S P [wo-o (d', [hW 2 iin (9,
(6)
+ (1+aap 8 + 82 8m.p.a
where Y/2 = (i denotes a set of random labels that are generated by first taking the set Y2, then randomly selecting [pm] labels from this set, each of the selected labels is re-selected randomly from the set [k]].
The above proposition provides an upper bound on the expected test error of the classifier h which is the term that we would like bound. The proposition assumes that the mistakes l generates on X₂ are distributed uniformly (with probability 2 1 11 6,,). To account the likelihood that this assumption fails, our bound includes the term 8h., which assumed to be small.
Informally, the bound suggests the following idea evaluate the performance of h Wo We start with an Wo initial guess Pm E (0, of the test error of lts. Using this guess, we compare its e-effective depth with the minimal depth dinm (9, S1 U (22) required to NCC separate the samples in S U 52, where $2 is the

---

Published in Transactions on Machine Learning Research (05/2023)
result of randomly relabeling Pm of Sy's labels. Intuitively, if the mistakes of We hs; are uniformly distributed and its c-effective depth is smaller than mii (9, S1 U $2), then, we expect hgg to make at most Pm mistakes on S2. In a sense, the choice of pm serves as a 'guess" whether the effective depth of a model trained with S1 is likely to be smaller than the minimal depth required to NCC separate the samples in S U2.
Next, we interpret each term separately. The term Ewo-old', ( depends on the complexity of the classification problem and the implicit bias of SGD to favor networks of small e-ellective depths. In the worst case, if SGD does not minimize the e-effective depth or the labels in S₁ are random (and m is sufficiently large), we expect Ewo~old3, ( = L. On the other hand, Lmin (9, Si U 52) measures the complexity of a task that involves fitting a dataset of size 2m samples, where (2 - Pm )m 2 m of the labels are correct and Pm are random labels. By decreasing Pm; we expect diin (9, S1 U S2) to decrease, making the first term in the bound larger. In addition, if h = eo ft is a neural network of a fixed width, it is impossible to fit an increasing amount of random labels without increasing the depth. Therefore, when Pm - 00, the dataset S U S2 becomes increasingly harder to fit, and we expect d (G, S1 U S2) to
tend to infinity. If Ewo-old's (. (hg) is bounded as a function of L and m and if pm
- 00, we obtain m--00
that PlEWo~q(d's (b! 2 dimin (1,51 10
0, we have Es, (errp(hs,)) + 0 and together with pm m0000
6/ + 82 8m + (1).
As side note, computing the expectation over St, S2 in the bound is impossible, due to the limited access of the training data. However, instead, we empirically estimate this term using set of k pairs (S1, of m samples, yielding an additional term that scales as O(1/Vk) to the bound (see Prop. 4 in the appendix).
Lastly, we would like to mention that the analysis presented above assumes a fixed width dg for each layer to simplify the analysis. However, it is straightforward to extend this analysis to cases where the width varies between layers in the trained network. The effective depth (Def. [ of the trained model would still be measured as the first layer for which NCC separability occurs. The minimal complexity (Def. 2 would be the minimum number of layers with width dg required to achieve NCC scparability up to an crror of c, where do represents the maximun width of layer in the trained network.
3.3 Comparing Prop. 3 with Standard Generalization Bounds
Classic bounds (e.g.; (Vapnik 1998)) are based on bounding the test error with the sum between the train error together with term O( P(VC(H)/m)) where C(H) measures the complexity (e.g., VC dimension) of the class H (e.g., neural networks) and m is the number of training samples. However, as discussed in Sec. [ these bounds are vacuous in overparameterized learning regimes (e.g., training ResNet-50 on CIFARIO classificationn. For instance, for VC-dimension based bounds (Vapnik 1998). C(H) cquals the VC-dimension of the class H. which scales with the number of trainable parameters for ReLU networks (Bartlett et al. 2019). For example, even though the ResNet-50 architecture generalizes well when trained on CIFARTO, it has over 23 million parameters compared to the m 50000 training samples in the dataset.
More recently, Neyshabur et al. (2015 Bartlett et al. 2017]; Golowich et al 2020 Neyshabur et al.
2018
suggested generalization bounds for neural networks that weakly depend on uniform convergence. In these
bounds, the class-complexity C(H) is replaced with the individual complexity C(hw) of the function we learn. For example, Golowich et al. (2020) proposed bounds that scale with C(hw) = p² L,, where L is the depth of hw and p measures the product of the norms of its weight matrices. However, Nagarajan & Kolter (2019) showed that in certain cases unregularized least squares can generalize well even when its norm P scales as @(ym) and the bound becomes (1). Furthermore, these bounds tend to be very large in practice (see Tab. 8 in (Neyshabur et al.) 2019) and Tab. [ and are negatively correlated with the test performance (Jiang ct al. 2020). In addition, if the network's 's weight matrices' norms are larger than 1, quantities like p grow exponentially when L is varied. As shown in Tab. D this is empirically the case.
Our Prop. g offers a different way to measure generalization. Since this bound is not based on uniform convergence, it does not require that the network's complexity would be small in comparison to m; rather, the bound guarantees generalization if the network's effective size is smaller than that of a network that fits partially random labels. For instance, when the optimizer has a strong bias towards minimizing the effective
7

---

Published in Transactions on Machine Learning Research (05/2023)
1.0
1.0
1.0
NCC train acc
0.8
0.8
0.8
Accurac)
0.6-
Accuracy
0.6-
0.6
0.4
0.
1.00
1.00
1,34-
0.2
0.2
6.2
lene
0.0
0.0
0.0
200
500
100
200
300
500
100
Epach
Epoch
Epoch
layers
layers
8 layers
1.0
1.0
1.0
NCC train ace
0.8
Accuracy
0.8
0.6
0.6
0.4
04-
0.4
2.00
1.00
Tye
3.30
Syer
0.40
10
0.48
Mear
0.98
Syerce
0.0
200
300
400
500
9.0
200
300
500
0.0
100
300
500
Epoch
12 layers
16 layers
20 layers
Figure 1: Intermediate NCC separability of CONV-L-400 trained on CIFAR10. We plot the NCC train accuracy rates of neural networks with varying numbers of layers. Each curve stands for a different layer within the network.
depth, Ewo-old's (d's (15, [o] x (9, which is by definition upper bounded by (9 U 52). We note that d'min (G, S1 U U2) grows to infinity as m + (since the network needs to memorize m - random labels). On the other hand, ( S1) is bounded by the depth of a network that approximates the target function y up to an approximation error e (which typically exists due to universal approximation arguments). Therefore, for sufficiently large m, we expect to have Lini (G, S1 U U2) > Lim S1)... As we empirically see in Sec. 4 the effective depths of SGD-traiindd networks are usually small.
Unlike previous bounds, bound has the advantage of being fairly independent of L. Namely, when the minimal depth hypothesis (Obs.) 1 holds, we expect Swg-old3, (hW)) to be unaffected by the depth L. of hi (as long as Lo)- Since i (9, Si US2) is by definition independent of L, we expect P[Ew-~Qle (4', (h 2 de (G (9,S, U U2)] to be independent of L (when L 2 Lo). In Tab. 1 we empirically validate that our bound does not grow when increasing L.
We
4 Experiments
In this section, we experimentally analyze the emergence of neural collapse in the intermediate layers of neural networks. First, we validate the "Minimal Depth Hypothesis" (Obs. D] Following that, we look at how corrupted labels affect the extent intermediate layer NCC separability and the e-effective depth. We show that as the number of corrupted labels in the data increases, so does the e-effective depth. Finally, using the bound in Prop. 3 provide non-trivial estimates of the test error. In Tab. [] empirically compare our bound with relevant baselines and show that, unlike other bounds, it achieves non-vacuous estimations of the test error. Throughout the experiments, we used Tesla-k80 GPUs for several hundred runs. Each run took between 5-20 hours. For additional experiments, see Appendix A For clarity, in various plots we added a small rectangle located at the bottom each plot to provide a magnified view of the lines between epochs 200 500, specifically within the y-axis range of 0.97 to 1.1. vertical line connocts the small rectangle with the zoomed-in area, while a horizontal line indicates the minimum value of y, which is set y=0.97. The plots high-definition pictures and are best viewed when zoomed in.
8

---

Published in Transactions on Machine Learning Research (05/2023)
Capt
Effective Depan
Effedive Depth
Effeetive Depth
Coate 10
000
0U04
0.33
8.04
642
C.04
CIFARIO, & =1 CONV-L-400
Fashion MNIST, ==
Fashion MNIST, A
MLP-L-100
CONV-L-
Sodt Cesth
Effective Desth
Effective Desth
Effect Depth
Cost
Cupth
090
0014
3.00
0.00
62
0.00
6.6
Cds
642
CD
ods
CIFARIO. &s 20 CONV-L-400
Fashion MNIST, k 20 MLP-L-100
Fashion MNIST, k 20 CONV-L-100
Figure 2: Averaged e-effective depths over the last few epochs. We plot the e-effective depth (y-axis) as function of (x-axis). Each line specifies the e-effective depth of a neural network of certain depth We show the averaged eeeffettive depth over the last k 1,20 epochs across 5 initializations. The network's architecture, datasct and & are specified below each plot.
1.0
irain nOC
0.5
0.8
0.6
Accuracy
9.6
Accuracy
0.6
0.6
0.4
1.00
1.00
0.2
0.2
6.2
0.0
0.0
200
500
100
200
300
500
100
Epach
Epoch
Epoch
1.0
1.0
1.0
boat sxr
Accuracy
0.6
0.6
0.6
0.4
0.4
0.0
9.0
0.0
200
300
400
500
200
300
500
100
200
300
400
500
Epach
0% noise
25% noise
75%
noise
Figure 3: Intermediate NCC separability of CONV-10-400 trained on CIFAR10 with partially corrupted labels. We plot the NCC train/test accuracy rates of the varions layers of network trained with a certain amount of corrupted labels (see titles).
4.1 Setup
Training process. We consider k-class classification problems (e.g., CIFAR10) and train multilayered neural networks h = ea ft = oo..'... R. + FC on the corresponding training dataset S. The models are trained with SGD for cross-entropy loss minimization between its logits and the one-hot encodings of the
9

---

Published in Transactions on Machine Learning Research (05/2023)
Datases
MNIST
Fushion NIST
CIFARIO
CIFARTO
Architecture
CONV-10-50
CONV-10-100
CONV-IG- 100
CONVRES 10-50
Bs, [e
0.0075
0.0996
0.2676
0.29
0.05
0.075
0.1
0.05
0.15
0.2
0.4
0.45
0.5
0.1
0.4
0.5
Bound
1.05
0.173
0.1
1.05
0.75
0.2
0.66
0.72
0.7
0.4
0.4
0.5
Table 2: Estimating the bound in Prop.
We used 6 0.005 to measure the effective depths.
Dataset
MNIST
Fashion MNIST
CIFARI0
Arch
Test
Bound
Arch
Test
Bound
Arch
Test
Bound
Dziugaite & Roy 2017
MLP-2-300
0.015
0.17
Biggs & Gued 2022
MLP-2-H
0.043
0.693
MLP-2-H
0.153
0.976
Zhou 2019
LeNet-5
0.46
Ours
CONV-15-50
0.0074
0.1
CONV-15-100
0.0996
0.2
CONVRES- 15-30
0.2804
0.4
Table 3: Comparing our bound with baseline non-vacuous bounds in the literature. Our error bound is reported in the fourth row, and the baseline bounds are reported in the bottom rectangle. We report the best bound achieved in each paper for each dataset. 'The experiments were conducted on binarized version of MNIST. Thhe specific width is not specified. Thee test performance is not reported.
labels. We consistently use batch size 128, learning rate schedule with an initial learning rate 0.1, decayed three times by a factor of 0.1 at epochs 60, 120, and 160, momentum 0.9 and weight decay 5e-4. Each model trained for 500 epochs.
Architectures. We focused on three types of architectures: (a) MLP-L-H with L fully- colneced layers of width H, (b) CONV-L-II with L 3 x 3 convolutional layers with padding 1, stride 1 and И output channels and (c) residual convolutional network CONVRES-L-H with L residual blocks with two 3 x33 3 convolutional layers. In each network the layers are interlaced with batch normalization layers and ReL.U activations. For more details see Appendix A..1
Datasets. We consider various datasets: MNIST, Fashion MNIST, and CIFAR1O. For CIFAR10 we used random eropping, random horizontal flips, and random rotations (by 15k degrees for k uniformly sampled from [24)). All datasets were standardized.
4.2 Results
Intermediate neural collapse. To investigate the bias towards depth mininization, we trained several CONV-L-400 networks with varying depths on CIFAR10. Each plot in Fig. [ illustrates the train NCC classification accuracy rates for every intermodiate layer of a network of a specific depth. We made several interesting observations: (i) Networks with eight or more hidden layers display NCC train accuracy rates of about 100% the eighth and higher layers, indicating that they are effectively of depth 7. (ii) The top layer embeddings become NCC separable at approximately the same epoch. (iii) The degree of NCC separability of intermediate layer i converges a function of L. In other words, the degree of NCC separability for each layer is more or less the same across all neural networks with depth of at least 8, regardless of whether the layer is at the beginning or the end of the network.
For additional experiments and repeat results with varions architectures and datasets, refer to Figs. 5 14 in Appendix A In these experiments, we also report NCC train and test accuracy rates, along with additional mcasures of neural collapse when varying the depth. For instance, Figs. and G we present the outcomes with CONVRES-L-500.
The effect of the depth on the e-effective depth. As next step would like to verify Obs. [ For this purpose, we would like to show that the e-offective depth remains largely consistent when two sulficiently deep neural networks are trained successfully. To validate this hypothesis we conducted the following experiments. We trained models on MNIST, Fashion MNIST and CIFAR10 with varying depth L. In Fig. | we plotted the averaged c-offective depths of each network's last k = 1, 20 epochs as a function of c. We also average the results across 5 different weight initializations and plot them along with error bar standard deviations. As can be seen, the e-effective depth is almost. unaffected by the choice of L for
10

---

Published in Transactions on Machine Learning Research (05/2023)
given Remarkably, for each e, the averaged effective depth varies very little across the various networks. Differently said, the eeeffective depths of two trained deep networks of different depths are more or less the same, validating our Minimal Depth Hypothesis.
NCC separability with partially corrupted labels. Simply put, Prop. 3 compares the depths required to fit, correct labels and partially corrupt labels. To better understand the effect of corrupted labels on the complexity of the task, we compare the e-effective depths of models trained with varying amounts of corrupted labels. Namely, study the degree of NCC separability in the intermediate layers of neural networks that are trained with varying amounts of corrupted labels.
For this experiment, we trained instances of CONV-10-400 for CIFARIO classification with 0%, 10% and 75% corrupted labels (e.g. uniformly distributed random labels). We plot the degrees of NCC separation on the train and test sets, 1 - (h.) and 1 - cfrp(h:), across the intermediate layers of the neural networks during the optimization procedure.
As can be seen in Fig. g when increasing the number of random labels, the degree of NCC separability across the intermediate layers tends to decrease. For example, when training with 2 25% corrupted labels, the sixth layer's NCC accuracy rate drops lower than 98%, in comparison with training without corrupted
labels that gives us > 98% accuracy. In particular, the e-effective depth of the former network is 6 while the latter's is 5 when 0.02 (see Def. D For additional experiments of this kind, see Figs. 15 19
Estimating the bound in equation 6 We estimate the bound in equation 6 for multiple archilectures and datasets. In each case, we used 6 <= 0.005 by default and employed different 'guesses' p (see Tab. 2 depending on the complexity of the learning task. We report an estimation of the expected test error of the models, Es,,wo ww.eerp(hh )h )] and an estimation of the bound for cach selection of p. For concrete tochnical details, see Appendix A
As can be seen, for appropriate choices of p, we obtained non-trivial estimates of the test performance of the models, which is uncommon for standard bounds for deep neural networks. As expected, if the value of p is too optimistic (e.g,, close to s,, (errp(h (h)))) ))), then, the first term in the bound tends to be large compared to ".s.wweerrphhh ). As predicted, when p is increased, the first term in the bound decreases.
Comparing our bound with standard generalization bounds. We expect the bound in equation G to be insensitive to depth because the e-effective depth of deep neural networks is insensitive to depth, shown in Fig. 2 We estimated the bound for various models and datasets, including CONV-L-50 trained on MNIST and CONV-L-100 trained on Fashion MNIST and CIFAR10, and CONVRES-L-50 trained on CIFAR1O with different values of L. The results, shown in Tab. [ indicate that our bound gives similar values for each value of L. We also compared our bound to several norm-based generalization bounds for deep networks that can be found in (Bartlett & Mendelson 2003 Neyshabur et al. 2015 Bartlett et al., 2017 Neyshabur et al. 2019) (we used the implementation of Neyshabur et al. (2019) to compute them). We found that our bound perforossss traditional bounds, as it is empirically non-vacuous and fairly independent of depth, while traditional bounds are extremely vacuous and rapidly increase with depth. These results support our prediction of the superiority of our bound over traditional bo
As mentioned in Section recent papers (Biggs & Guedj 2022: Dziugaite Roy 2017 Hellström & Durisi 2022 Zhou et al., 2019) have obtained non-vacuous bounds in various learning settings. However, comparing our results with those of previous studies is challenging due to significant differences in theoretical and experimental setups.
On the theoretical side, Dziugaite & Roy (017]; Zhou et al. (2019) Hellström & Durisi (0022 used a PAC-Bayesian framework that incorporates random classifiers, while our paper focuses on standard training of deterministic neural networks using SGD, In (Biggs & Guedj] 2022), they derived generalization bounds for 2-layer networks, whereas our paper only considers deep networks. On the empirical side, the results of Dziugaate & Roy] (017)) are based on a binary version of MNIST, where digits 0-4 are classified as O, and digits 5-9 are classified as 1. Similarly, Hellström & Durisi (2022) experimented with MNIST, but only on a
The norm-based generalization bounds could not be calculated for the CONVRES-I-50 architecture, these bounds are not applicable for neural networks incorporating residual connections.
11

---

Published in Transactions on Machine Learning Research (05/2023)
0.8-
0.8
Probability of Error
Probabiltt Error
0.6
0.4
0.4-
0.2
20
40
20
40
60
80
Test Sample
Test Sample
MNIST
Pashtto MNIST
Figure 4: The plot displays the probability of error across 100 random test samples, as we train 5000 networks with different. initialization seeds, on 5000 randomly selected training samples for MNIST and Fashion MNIST datasets respectively.
binary version of MNIST that includes digits 4 and 9. In a different experiment, they evaluated their bound on a model trained on CIFAR10, but only after it was pre-trained on ImageNet, which could have influenced the test performance and the bound, particularly as CIFARIO a subset of ImageNet.
Given these variations, we compare some of the bounds by their best-performing setup reported in each paper in Tab. For clarity, we provide disclaimers about the relaxations that each one makes. As shown in the table, our bound generally provides tighter bounds for neural networks.
Validating mistakes uniformity. To simplify the analysis in Section we assumed that the mistakes made by the trained network on the test set are uniformly distributed across samples when the initialization is randomized. This assumption has two aspects: (1) the number of mistakes made by the network remains fixed across initializations, and (2) the probability of the network misclassilying given test sample is unchanged across samples.
To validate this assumption empirically, standard deviations of the test errors of the models presented in Tab. [ Since the standard deviations were found to be very low, it verifies that the number of mistakes on the test is more or less constant.
conducted multiple experiments. Firstly, we computed the
Additionally, we performed an experiment to validate uniformity. We trained 5000 CONV-10-50 networks on 5000 randomly selected samples from both the MNIST and Fashion MNIST datasets for 20 epochs each. For each test sample (z,, 9;), we measured the probability p; that it was misclassified by the model across the 5000 brained models. Then, we calculated the Coefficient of Variation f) = a/p of pt across all samples, where p and represent the expectation and variance of p: across all samples, respectively. Essentially, n measures the extent to which the error probability p; varies across samples when normalized against its mean. Our results showed that the Coefficient of Variation for this test was 0.5204 and 0.42 for MNIST and Fashion MNIST, respectively. We present the probability of error for 100 randomly selected test samples across the different networks in Fig. | Based on these experiments, it can be observed that the error probabilities are generally uniform, with only a minority of outlier samples that are difficult to classify accurately.
Estimating 52 p... We conducted an experiment. where took 10 pairs of splits Si and St each with a size of m 25000, and generated multiple corrupted labelings yiP for S with corruption rates p E Q = {q1 = 0.01, 92 = 0.05, 9s = 0.1, 94 = 0.15, qs = 0.203. We needed to compute the minimal complexity required to fit a given dataset S.S" = Si U S but doing so required significant computational power (as discussed in Appondix A). Instead, we estimated 82 8mp by replacing & with de K and using
trained CONV-10-50 models on S.....
For each qy we trained a CONV-10-50 model hig on S where $/ is St with its labels replaced by the sampled corrupted labels, with qj fraction being random. To estimate 52 a on for each qj Q, we computed
12

---

Published in Transactions on Machine Learning Research (05/2023)
the probability across that dsyy (hi,))) is larger than dsy, (hig) for q 9y, where 9 Q. We used aj g -1 for each qj since (1 ataay 9j+1- The following are the resulting estimates: 82 m,0.01,4 0, 8 0,0.05.1 1/10, 6 m.0.1.0.5 4/10, 6² m,0.15.1/3 = 1.
5 Conclusions
Understanding the ability of SGD generalize well when training overparameterized neural networks is attributed one of the major open problems in deep learning theory (Zhang et al., 2017). In this paper, offer new angle to study the role of depth in deep learning and the connection between neural collapse and generalization.
Our approach involves introducing the concept of effective depth, which identifies the lowest layer that exhibits NCC separability. We propose a novel generalization bound that estimates the likelihood that the effective depth of a trained neural network is strictly smaller than the minimal depth required to achieve NCC separabilityy with partially corrupted labels. As demonstrated empirically, this criterion useful predictor of generalization. Furthermore, networks are trained, they converge to the same effective depth, implying that our bound is fairly constant when the depth is varied.
characterize and empirically demonstrate that when sufficiently deep
13

---

Published in Transactions on Machine Learning Research (05/2023)
References
Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional dynamies of generaliza-
tion error in neural networks. Neural Networks, 132:428 446, 2020. ISSN 0893-6080. doi: https://
doi.org/
CRL http:s//www...aaaaaaaacccc.oooor
50893608020308117
Guillaume Alain and Yoshua Bengio. Understanding intermediate layers using linear classifier probes. In International Conference Learning Representations Workshop, 2017. URL https://openeeview.eee
forum?1d=ryF7rTqqll
Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '19, pp. 314 315, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367486. doi: 10.1145/33196119.3222
URL https::/doi.org:: 11t1///391144/339111199 3321894
Peter L. Bartlett and Philip M. Long. Failures of model-dependent generalization bounds for least-norm in- terpolation. Journal of Machine Learning Research, 22(204):1 15, 2021. URL http:://jmll weaellr.rrg/ggggee prrgpppere// v 11600.1116..10 html
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463 482, 2003. ISSN 1532-4435.
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Opectrally-normalliee margin bounds for neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6241-6250. Curran Associates Inc., 2017. ISBN 9781510860964.
Peler L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20 (63):1-17, 2019. URL http::////aaa.ooopaapaaaaa//////
Mikhail Belkin, Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203 248, 2021.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand
kernel learning. In Proceedings of the 35th International Conference on Machine Learning, volume Proceedings of Machine Learning Research, pp. 541-549. PMLR, 10-15 Jul 2018. URL https:/7 proceedings... mlr. prees//v00/belkin1B..tt
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning prac- tice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, 116: 15849 15854, 2019. doi: 10.1073 ptt.//a....0000111.. URL hntpp://www http//wwpp.......m.p//po pnas. pnas. 1903077116
1073/
Ido Ben-Shaul and Shai Dekel. Sparsity-probe: abs/2105.06849, 2021.
Analysis tool for deep learning models. ArXiu,
Ido Ben-Shaul and Shai Dekel. Nearest class-center simplification through intermediate layers. In Proceedings of Topological, Algebruic, and Geometric Learning Workshops 2022, volume 196 of Proceedings of Machine Learning Research, pp. 37-47. PMLR, Feb-22 Jul 2022. URL httpss:/prroceedings.t wtw.ptt.nnnmmmr.see.s..eeeeeeeee press/
#196/ben--han 22a.html
Felix Biggs and Benjamin Guedj. Non-vacuous generalisation bounds for shallow neural networks. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 1963-1981, PMLR, 2022. URL [tRl/ttss//ppoccciigg..u press/v162/ v
bi biggs22a. hhmll
14

---

Published in Transactions on Machine Learning Research (05/2023)
Tom Brown, Benjamin Mann, Nick Ryder, Mclanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Nee- lakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christo- pher Berner, Sam McCandlishh, Alec Radford, Πya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Cur- ran Associates, Inc., 2020. URL https://proceeddii nwwris...upppp... meerips.cc/paper wwwes/ filles/paper/2220/i11a 1B5700666b1444495418118888888883
pdf
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretehen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Fe- lipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantamu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katic Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish; Ilya Sulskever, and Wojciech ZZarebba. Evaluating large language models trained on code, 2021.
Gilad Cohen, Guillermo Sapiro, and Raja Giryes. Dun or k-nn: That is the generalize vs. memorize question, 2018. URL
wwwpexxii.oooraaaoeeoo a80eaa/s...aaeea/////e/e/eeee 06822
Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirec- tional transformers for language understanding, In Proceedings of the 2019 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4171-4186, Minncapolis, Minnesota, 2019. Association for Computational Linguistics. doi: 10.18653/v11N1/ 1423. URL httpps//acllantoooog..orr// org/N19-1423
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more paramcters than training data. In Proceedings of the Thärty- Third Conference on Uncerlainly in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017. AUAI Press, 2017. URL http:://aaat ptgg://a222///pppoooed//////pp/p
pdf
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3004-3014. PMIR, 18 24 Jul 2021. URL. htttps:/prroceedingg mlr.
press/v139/ergen211 html
Cong Fang. Hangfeng He, Qi Long, and Weijie J. Su. Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. Proceedings of the National Academy of Sciences, 118 (403::2100 2021. pnas. 2aN.2911001111
doi: 10.1073/pnas 2at.0910000911111 URL htLLhhtps::///e //ww: www..pnas.oo org/ hts//////aaa////////
Tomer Galanti, András György, and Marcus Hutter. On the role of neural collapse in transfer learning. In International Conference on Learning Representationss 2022. URL ctttp:://openrevieev.nee////
SwIp410B6aQ
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Information and Inference: A Journal of the IMA, 9:473-504 2020. ISSN 2049-8772. doi: (0.1093/imaial/iwx0007 URL //dois///oi..ooo 1ttp:///...9///mmaaaaii.. 00090//mmm/m/ia000001110
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In 2015 IEEE International Conference on Computer Vision (ICCV), pp. 1026-1034, 2015. doi: 10. 10.1109/ICCV 123..
15

---

Published in Transactions on Machine Learning Research (05/2023)
Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using samplewise evalu- ated cmi. In Advances in Neural Information Processing Systems, volume 35, pp. 10108-1012)) Cur- ran Associates, Inc., 2022. URL https://proceed 101674422000e332232322333-32---0 Paper-Cooeeeeence pdf
peeurips.c//paeee htwprr/ps.ccppppe....l/////pp//p Filess/paper/202//11el
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic general- ization measures and where to find them. In International Conference on Learning Representations, 2020. URL http:s/sppppareviissseeerfororoa
JBFvH
Jianfeng Lu and Stefan Steinerberger. Neural collapse with cross-entropy loss. CoRR, abs/2012.084655, 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT
Press, 2nd edition, 2018. ISBN 0262039400.
Grégoire Montavon, Mikio L. Braun, and Klaus-Rober Müller, Kernel analysis of deep networks, Journal of Machine Learning Research, 2(78))2663-2553 2011. URL http://jmlr http:://ha....rr///p/p////////// http://wwww....pp//////////aaaaa
html
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain gen- eralization in deep learning. In Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL https::/prooeednns..eee http:eeeddddnnn................. peeurips.cc/ppppr/20000000 .ddf.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: General- ization via derandomization with application to interpolating predictors. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, mlr
pp. 7263 7272. PMLR, 13-18 Jul 2020. URL 9 pptess//119/eegre////e
html
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of The 28th Conference Learning Theory, volume 40 of Proceedlings of Machine Learning Research, pp. 1876-1400 Paris, France, 03 06 Jul 2015. PMLR. URL http::tt///rroooeiings mlr mwt.pggssmm...s.ss//m//m v40/Neyshabur15 html
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Representations, net/forumiiddSkz,
2018. URL htttps://operreww//e
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of pwr.perrantiizttionn in generalization of neural networks. In International Conference on Learning Rep- resentations, 2019. URL htttps:/ wtt.://w....ttooommo/dd/dyygggg
Vardan Papyan. Traces of class/cross-clan structure pervade deep learning spectra. Journal of Machine Learning Research, 21(252):1-64 2020. URL http::///aaa.oor//pps///////0//0 html
Vardan Papyan, Yaniv Romano, and Michael Elad. Convolutional neural neural networks analyzed via convolutional
sparse coding, Journal of Machine Learning Research, 18(83)11-52, 2017. URL http::ttjjl.oorrgg// www.lororrpppppppppee
v18/16-505. htmm
Vardan Papyan, X. Y. Han, and David L. Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40):2465-22466) 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-705513-5.
Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. ArXiv, abs/1703.00810, 2017.
16

---

Published in Transactions on Machine Learning Research (05/2023)
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Toannis Antonoglon, Veda Panneershelvam, Mare Lanciot, Sander Dieleman, Do- minik Grewe, John Nham, Nal Kalchbrenner, llya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Gracpel, and Demis Hassabis. Mastering the game Go with deep neural networks and tree search. Nature, 529:484 489, 2016. ISSN 0028-0836. doi: 10.1033/nabure1666
Yaniv Taigman, Ming Yang, Marc' Aurelio Ranzato, and Lior Wolf. Deepface: Closing the gap to human-level performance in face verification. In 2014 JEEE Conference on Computer Vision and Pattern Recognition, pp. 1701-1708, 2014. doi: 10.1109/CVPP CVPR.2014.220.
Tom Tirer and Joan Bruna. Extended unconstrained features model for exploring deep neural collapse. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.); Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 11478-215001 PMLR, 2022. URL. httts::/ mlr. press/
v162/tirer22..htm html
Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Intersciene 1998.
Mengjia Xu, Akshay Rangamani, Qianli Liao, Tomer Galanti, and Tomaso Poggio. Dynamics in deep clas- sifiers trained with the square loss: Normalization, low rank, neural collapse, and generalization bounds. Research, 6:0024, 2023. doi: (0.34133/research..0 34133/research.002 0024
URL https://spj..cieett wwwpiceerrr////i//aeeee org/doi/bbs/10.
Zitong Yang, Yu Bai, and Song Mei. Exact gap wetween generalization error and uniform convergence in random feature models. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11704-11715. PMLR, 18-24 Jul 2021. URL https://proceeedings mlr, atress/vi39/yang2la.o
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 12104-12113, June 2022.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. URL htttps://peerroeee mot//formmm7dd5yydddxxxx
Lijia Zhou, Danica J. Sutherland, and Nati Srebro. On uniform convergence and low-norm inter- polation learning. In Advances in Neural Information Processing Systems, volume 33, pp. 6867- 6877. Curran Associates, Inc., 2020. URL
5cc50066004444400097777666--- .pd.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous generaliza- tion bounds at the imagenet scale: a PAC-bayesian compression approach. In International Conference on Learning Representations, 2019. URL
Zhihui Zhu, Tianyu DING, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu. A geometric analysis of neural collapse with unconstrained features. In Advances in Newral Information Processing Systems, volume 34, 2021. URL
17

---

Published in Transactions on Machine Learning Research (05/2023)
A Additional Experiments and Details
A.1 Architectures
In this section, we describe the architectures used in our experiments.
The first architecture is a convolutional network, denoted CONV-L-H, which consists of a stack of two convolutional layers with stride 2, batch normalization, and ReLU activation. This is followed by L stacks of blocks g²(x=) = o (B)((()))) where C. is 3 x 3 convolutional layer with H channels, stride 1, and padding 1, Bi is batch normalization layer, and is the ReLU activation. The final layer is linear. The ith intermediate layer refers to the output of the ith block of g'.
The second architecture is an MLP, denoted MLP-I-H, which consists of L hidden layers, where each layer g'(x) = a (B, (x))) contains a linear layer T, with output width H, followed by a batch normalization layer B, and ReLU activation function a. The final layer is linear.
The third architecture is a convolutional residual network, denoted CONVRES-L-H. It consists of stack of two xx2 2 convolutional layers with stride 2, batch normalization, and ReLU activation, followed by L residual blocks. Each block computes ga(x) o(x B3 (C2 (B) (x)))))) where C/ is a 3 x 3 convolutional layer with H channels, stride 1, and padding B is a batch normalization layer, and o is the ReLU activation. The final layer is linear.
A.2 Estimating the Generalization Bound
In this section we describe how empirically estimate the bound in Prop. 3
Estimating the bound. We would like to estimate the first term in the bound,
P S. RWooo 145, () 2 Lin (9,5) u
According to Prop. in order to estimate this term we need to generate i.i.d. triplets SJ, Y?). Since we have limited access to training data, we use variation of cross-validation and generate k = 5 i.i.d. disjoint splits (S), St) of the training data S. For each one of these pairs, we generate k2 = corrupted labeling Y We denote by Sy the set obtained by replacing the labels of S) with yo and 5 = St U.
As first step, we would like to estimate Ewo-o |0 (1
Wo for each E [ki]. For this purpose, we randomly )
W Q and for each one, we train the model wi using the training protocol described in Sec. 4.1. Once trained, we compute &ss, (h for each t E [Ti] (sce Def. 1) and approximate Ewo~old;; ( using d, = J, En dz W.).
select Ti- 5 different initializations
As a next step, we would like to evaluate I[[d; 2 dimin (9, 55') }. We notice that d, 2 di (G, U 5:) if and only if there is d,-layered neural network f g .... g for which errgy (ft) I c, where hy(x)) = arg mij (1xx)) - (S.)). In general, computing this Boolean value is computationally hard. Therefore, to estimate this Boolean value, we simply train a (d, + 1a-laye network h eo f and check whether its penultimate layer is e-NCC separable, i.e., err errgy (fy) S e, where (x) = arg min (l[(x) - (S.) If SGD implicitly optimizes neural networks to maximize NCC separability as observed in (Papyan et al. 2020 (and also in this paper), should expect to obtain e-NCC separability in the penultinate layer if that is possible with a dy-layered network. Since training might be non-optimal, to obtain robust estimation, we train T2- = 5 models h4 = e, o ft of depth d, + and pick the one with the best NCC separability in its penultimate layer. Namely, we replace dimin (9, 5 with mingerss &' (he) and estimate I[d 2 dimm (9, 55
using lid, 2 minserrs) Egy(0) (lt))
18

---

Published in Transactions on Machine Learning Research (05/2023)
Our final estimation is the following
d:
min E TTa)
Sy (hn) se ss. Ewo- [000 2 iin (I
(8)
In order to estimate the bound we assume that 6m and 6 m. are negligible constants and that a 1. The estimation of the bound is given by the sum of the left-hand side in equation g and
Estimating the mean test error. To estimate the mean test error, Es,, (h W,)) as typically done in machine learning, we replace the population distribution with the test set Stest and we replace the expec- tation over S₁ and Wo with averages across the kj random selections of { 14, and Ti random se- Wi lections of (Wo) Namely, we compute the following N, Σ + E eIt (hs))
Es, wo (errp(h))) (
A.3 Neural Collapse
To obtain comprehensive analysis of collapse across layers, also estimate the degree of NC1.
To evaluate NC1, we follow the process suggested by Galanti et al. 2022 which is simplified version of the original approach of Papyan et al. (2020). For a feature map
R and two (class-conditiona) distribution Q1, Q2 over X' c IR, we define their dissadds normalized variance (CDNV) to be
v2(1), = Var, (Q2) 21 (Q2)
where := [u]]((((( and by Var.(Q) := Ellelllu(z) pr, (Q)1 the mean and variance of u(z) for ~ Q. Essentially, this quantity measures to what extent the feature vectors of samples from Qi and Q2 are separated and clustered in space.
To demonstrate the gradual evolution of collapse across the layers, for each sub-architecture f = g'o...oog (z' we consider the train and test class features variations Avgezt (S., Ser]] and Avgege [V Pe)] The population distribution of each class, Pe. is replaced with the test samples of that class.
As shown by Galanti al. (2022), this definition essentially the same as that of Papyan et al. (2020) Furthermore, they showed that the NCC classification error rate can be upper bounded in terms of the CDNV. However, the NCC error can be zero in cases where the CDNV is larger than zero. For example, if the two classes are uniformly distributed over the 1-radius circles around the points (-1,0) and (1, 0) in R2. then they are perfectly NCC separable while the CDNV between the two distributions is 0.25.
we plot the NCC and the CDNV rates of neural networks with varying numbers of layers evaluated on the train and test data. Each curve stands for different layer within the network. As can be seen, in all cases, for networks deeper than a threshold we obtain (near-perfect) NCC separability in all of the top layers. Furthermore, the degree of class-features variability collapse increases with the network's depth depicted by decreasing CDNVs.
Auxiliary experiments on the effective depth. In Figs.
we repeat the experiment in Fig. 3 and plot the results of the same experiment, with different networks and datasets (see captions). As can be seen, the effective NCC depth of a neural network tends to increase as we train with increasing amounts of corrupted labels.
Auxiliary experiments with noisy labels. In Figs. 15 19
2The definition be extended finite S1,82 C by defining V2) Vy(U(S)).U(s))..
19

---

Published in Transactions on Machine Learning Research (05/2023)
16-
1.0
1.0
NCC train noc
Accuracy
Accuracy
0.6
0.4
0.4-
0.4
kmc
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
0.8
0.8
0.5
NCC train
Accuracy
1o
10
1.00
1.00
0.2
0.2
0.2
100
200
200
Epech
Epoch
Epoch
12 luycro
16 layera
20 Jayero
NCC seat sce
Acouracy
Accuracy
0.6
0.6
0.6
0.0
0.0
100
300
400
160
200
600
100
200
460
500
Epoch
Epach
Epoch
layene
laywer
1.0
1.0
0.8
0.8
Accuracy
Acruracy
NCC Lest
0.4
0.4
10am
Spar
1ap
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layera
20 loyers
Figure 5: Intermediate NCC separability of CONVRES-I-500 trained on CIFARIO. We plot the NCC train and test accuracy rates of neural networks with varying numbers layers. Each curve stands for different layer within the network.
20

---

Published in Transactions on Machine Learning Research (05/2023)
CDNY truin
CONV
21
21
274
2-
2n
2-3
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
layers
21
21
21
CDNY triis
CONV
2-2
2.a
2.4
2:4
100
200
200 Epoch
Epech
Epoch
12 luycro
16 layera
20 Jayers
CDNY teat CDNV
CDNV
244
2%
2-
2-a
2-4
2-
100
300
400
160
200
600
100
200
460
500
Epoch
Epach
Epoch
layere
laywer
CDNV 100
23
22
CONV
14
2.4
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layera
20 leyers
Intermediate class-features variability collapsc scparability of CONVRES-I-500 trained on CIFAR10. We plot the CDNV on the training and test data of neural networks with varying numbers of layers. Each curve stands for different layer within the network.
Figure 6:
21

---

Published in Transactions on Machine Learning Research (05/2023)
14-
1.0
1.0
NCC train nOc
Accuracy
Accuracy
0.6
0.4
0.4-
0.4
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
0.8
0.8
0.5
NCC train
AEcurcyy
Accuracy
13
15
10
1.00
1.00
0.2
0.2
0.2
06.0
Tam
100
200
Epoch
Epoch
Epoch
12 luycrs
16 layora
20 Jayero
NCC seat sce
0.6
Accuracy
0.6
Accuracy
0.6
0.0
0.0
100
300
400
160
200
600
100
200
460
500
Epoch
Epach
Epoch
layere
laywer
1.0
1.0
0.8
Accuracy
Acruracy
NCC Lest
0.4
0.4
10ar
Spar
100
200
300
<00
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layera
20 loyers
Figure 7: Intermediate NCC scparability of CONV-L-400 trained on CIFARIO. We plot the NCC
train and test accuracy rates of neural networks with varying numbers of layers. Each curve stands for a different layer within the network.
22

---

Published in Transactions on Machine Learning Research (05/2023)
CDNY truin
CONV
21
21
274
2-
2n
2-3
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
layers
21
21
2
CDNY triis
CONV
Myy
1aye:
Apy
2-2
2.a
2.4
2:4
100
200
200
Epech
Epoch
Epoch
12 luycro
16 layera
20 Jayers
CDNY teat CDNV
CDNV
244
24
2.4
2-a
2-
2-
100
400
160
200
600
100
200
460
500
Epoch
Epach
Epoch
layere
laywes
Mym
CDNV 100t
22
22
CONV
bee7
14
Npm
2-4
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layera
20 leyers
Figure Intermediate class-fcatures variability collapse scparability of CONV-I-400 trained on CIFAR10. We plot the CDNV on the training and test data of neural networks with varying numbers of layers. Fach curve stands for different layer within the network.
23

---

Published in Transactions on Machine Learning Research (05/2023)
16-
1.0
1.
NCC train noc
Accuracy
Accuracy
0.6
0.4
0.4-
0.4
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
0.8
0.8
0.5
NCC train
Accuracy
lapr 13
10ar
11ae 10
1.00
1.40
Maa
1.00
0.2
0.2
0.2
lear
Tam
100
200
Epech
Epoch
Epoch
12 luycro
layera
20 Jayero
NCC seat sce
0.6
Accuracy
0.6
Accuracy
0.6
0.0
0.0
100
300
400
160
200
6.0
100
200
460
500
Epoch
Epach
Epoch
layere
Iayyers
1.0
1.0
0.
NCC Lest uce
0.4
0.4
Spar
1ape11
100
200
300
<00
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layora
20 loyers
Figure 9: Intermediate neural collapse of MLP-L-300 trained on CIFARIO. We plot the NCC train and accuracy rates of neural networks with varying numbers of layers. Each curve stands for different layer within the network.
24

---

Published in Transactions on Machine Learning Research (05/2023)
24
CDNY train.
CONV
2.a
24
24
24
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
Layerr
21
21
CDXY truin
CONV
kpy:
2-2
2.4
2.a
100
200
Epech
Epoch
Epoch
12 luycrs
16 layera
20 Jayers
214
22
240
Heer
CDNY teat
2
21
2'
CDNV
CDNV
2.7
2-
2-
2-
2-
100
300
400
160
200
600
100
200
460
500
Epoch
Epach
Epoch
layere
laywer
21
27
21
1y51
27.
CDNV L00
Kam
CONV
24
21
Sper
Nox
Sear
2.9
2.
2
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layers
LG layora
20 loyers
Figure 10: Intermediate class-fcatures variability collapse scparability of MLP-I-300 trained on CIFAR10. We plot the CDNV on the training and test data of neural networks with varying numbers of layers. Fach curve stands for different layer within the network.
25

---

Published in Transactions on Machine Learning Research (05/2023)
1.-
1.0
1.0
NCD train nOc
Accuracy
Accuracy
0.6
04-
0.4-
0.4
Wer
kmc
1pm
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
0.8
0.8
0.5
NCC train
Accuracy
10mm
Tape 13
10ar
-81
1aae 10
60
1.00
1.00
0.2
0.2
0.2
13
lear
Tam
100
200
200
Epech
Epoch
Epoch
12 luycrs
16 layera
20 Jayers
NCC seat sce
0.6
Acouracy
0.6
Accuracy
0.6
60
6.48
3.90
0.0
0.0
100
300
400
1.0
200
300
6.00
100
200
460
500
Epoch
Epach
Epoch
Iayere
Iayyers
2.0
1.0
0.
NC Lest uce
Accuracy
0.4
0.4
1.00
1.00
1.00
10am
1pee
10
Spar
100
200
300
4.00
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layora
20 loyers
Figure 11: Intermediate ncural collapse of CONV-L-50 trained on MNIST. We plot the NCC train and accuracy rates of neural networks with varying numbers of layers. Each curve stands for different layer within the network.
26

---

Published in Transactions on Machine Learning Research (05/2023)
21
21
21
CDNY train
24
21
21
CONV
214
2.4
214
2-
2-
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
layers
CDNV truin
2-4
2-
CONV
2.9
2
2-
Rpy:
2.9
2
2-
2-7
2-
2-1
2.7
2.
2.9
100
200
Epech
Epoch
Epoch
12 luycrs
16 layera
20 Jayers
CDNY beat
2-4
CDNV
2-
100
300
400
160
200
600
100
200
460
500
Epoch
Epach
Epoch
layere
laywes
21-
CDNV L00
CONV
2-1
2-1
10012
2-1
2-
2
2-
Spa:
2.54
12
2-7
2-
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layera
20 leyers
Figure 12: Intermediate class-fcatures variability collapsc scparability CONV-L-50 trained on MNIST, We plot the CDNV on the training and test data of neural networks with varying numbers of layers. Fach curve stands for different layer within the network.
27

---

Published in Transactions on Machine Learning Research (05/2023)
14-
1.0
1.0
NCC train nOC
Accuracy
Accuracy
0.6
04-
0.4-
0.4
Wer
kmc
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
0.8
0.8
0.5
NCC train
Accuracy
10ar
-51
12
00
1.40
1.00
0.2
0.2
0.2
lear
1am
100
200
200
Epoch
Epoch
Epoch
12 luycrs
16 layera
18 Jayero
NCC seat sce
0.6
Acouracy
0.6
Accuracy
0.6
0.0
0.0
100
300
400
160
200
600
100
200
460
500
Epoch
Epach
Epoch
layene
laywers
2.0
1.0
0.8
0.8
Acruracy
Accuracy
NCC Lest
0.4
0.4
10mm
10am
Spar
1apm
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layera
18 loyers
Figure 13: Intormediate neural collapsc of MLP-I-100 trained on Fashion MNIST. We plot the NCC train and test accuracy rates of neural networks with varying numbers of layers. Each curve stands for different layer within the network.
28

---

Published in Transactions on Machine Learning Research (05/2023)
24
CDNY train.
CONV
CONV
21
2.7
244
24
24
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
Epoch
Layere
1yer1
21
21
CDNY truin
CONV
kapr 72
2-2
2
2.4
21
100
200
Epech
Epoch
Epoch
12 luycrs
16 layera
18 Joyers
214
22
240
Heer
CDNY teat
2
21
21
CDNV
CDNV
2.7
2-
2"
2-
2-
100
300
400
160
200
600
200
460
500
Epoch
Epach
Epoch
layere
laywen
21
27
1y51
27
1007
CDNV L00
1gm
CONV
10977
1990
24
21
Sear
2.9
2
2
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
12 layera
1G layora
18 loyers
Figure Intermediate class-fcatures variability collapse scparability of MLP-I-100 trained on Fashion MNIST. We plot the CDNV on the training and test data of neural networks with varying numbers of layers. Each curve stands for different layer within the network.
29

---

Published in Transactions on Machine Learning Research (05/2023)
CAN
CDNV
layer
layor
layer
Iayer
Jayer 10
NCC
300
Epech
0% bolae
10% noise
26% moise
50% noise
76% noise
CDNY. Test
CWN
CAN
Jayer
layor
layar
Iayer
Jagner 10
NCO
180
10
15
35c
Epech
49
300
0%. Rolse
10% noise
25% molee
50% nolae
75% modee
Figure 15: Intermediate neural collapse of CONV-10-400 trained on CIFAR10 with partially corrupted labels. In the first (third) row, plot the CDNV the train (test) data for intermediate layers of networks trained with varying amounts of corrupted labels (see legend). In the second (fourth) row, we plot the NCC accuracy rates of the various layers of network trained with certain amount of corrupted labels (see titles).
30

---

Published in Transactions on Machine Learning Research (05/2023)
CDNV
310
layer
layer
layer 6
layer
layer 10
NCC. tealn
Kacch
Sauc
Lacd
0%
10%
25%
50% noise
75% noise
CDNY
layer
layer
layer 6
layer 8
layer 10
INCO test
180
0% noise
10% noise
25% noise
50%
noise
75% noise
Figure 16: Intermediate neural collapse of CONVRES-10-500 trained on CIFAR10 with noisy
labels. See Fig 3 in the main text for details.
31

---

Published in Transactions on Machine Learning Research (05/2023)
CDN
ka0 layer
801 layer 10
layer
layer
layer 6
NCC tealn
Kacch
Lacd
0%
10%
25%
50% noise
75% noise
CDNY OW
layer
layer
layer 6
layer
layer 10
DCC test
140
0%
noise
10% noise
25% noise
50%
noise
75% noise
Figure 17: Intermediate neural collapse of MLP-10-500 trained on CIFAR10 with noisy labels.
See Fig 3 in the main text for details.
32

---

Published in Transactions on Machine Learning Research (05/2023)
CDNV
Bai layer 10
layer
layer 6
layer 8
layer
NCC tealn
Kacch
Lacd
0%
5%
10%
20% noise
30% noise
CDNY
layer
layer
layer 8
layer
layer 10
INCO test
140
0% noise
5% noise
10% noise
20% noise
30% noise
Figure 18: Intermediate neural collapse of CONV-10-100 trained Fashion MNIST with noisy labels. See Fig. 3 in the main text for details.
33

---

Published in Transactions on Machine Learning Research (05/2023)
CDNV
CIMY
Jayer
Jayer
Jayez
layer
Lagres 10
NOC traio
0%S Bo200
195 wo2e
2% uodse
0%8 uoise
10% polse
CDNN M0M
Jayer
Jayer
Jayer
Jayer
Lagrer 10
IVOI tent
$3007
XX
200
22
0%
nasee
nalee
5%
10% nalse
Figure 19: Intermediate neural collapse of CONV-10-50 trained MNIST with partially rupted labels. See Fig. 15 for details.
34

---

Published in Transactions on Machine Learning Research (05/2023)
B Proofs
Proposition 3. Let N, D (0,1/2), E (0,1) and e E (0. 1). Assume that the error of the learning algorithm is 8tn unifform. Assume that S1, S2 ~ Pø(m). Let Wo given access to a dalaset Si and initialization Wo. Then,
ss be the output of the learning algorithm
Es,
S Ps @ (!$1 2 oi (9, US))
(6)
+ +1++a)p- - 6n, + +o m..p.a
where Y2 = 1i denotes a set of random labels that are generated by first taking the set Y2, then randomly selecting [pm] labels from this set, each of the selected labels re-selected randomly from the set [k]].
(.) v/) and S2 = ((3, D/ be two balanced datasets. Let c > 0, > and == (1+ a) p. Let Y2 and Y2 be a uniformly selected set of labels that disagree with Y2 on [pm] and [qm] randomly selected labels ). We denote by S2 and $2 the relabeling of S2 with the labels in Y2 and in 8/2 (resp.). We define four different events,
Proof. Let S = [(r],
A S2, Y2) = (1+a) 8 S1 Ey, Si U
A2 = ((S), | the mistakes of iss, are not uniform over 52)
A3 (2,,, Y2) (S,, Y2) Ai U.U.D A2 and Ew ( [ < y (G, (
(9)
A4 = (2, 12) (Si, S2, V2) & A₁ A2 and Ew (d's, (h 2 min (9, U 82))
B1 S2, Y2)
Ewo-old3, ( [h 2 d Emiu (G, U $2)
By the law of total expectation
Es, p
( (h = ss, Swo |e (h
Σ P[A:] Ss.. [Bo (1 A:]
(10)
S P[A|] + P[A2] + Sy, EWar (errs, (h As] F[B.),
where the last inequality follows from errs, (1 Wo) < F[Aa] < and A4 C Bi.
We would like to upper bound each one of the above terms. First, notice that since the mistakes of the network are -uniform, P[A₂] < 5%,-- In addition, by definition P[A1] s 82 m.pp.a
As next step, we upper bound Es,,s,, (Ewo-olerrs, ) As). Assume that (S, Y2) E A3. Hence, S2, F2) A₁ U A2. Then, the mistakes of h Wo over S2 uniformly distributed (with respect to the
selection of Wo). Assume by contradiction that erts, Wo) (h > (1 aa) with non-zero probability over the selection of Wo- Then, since the mistakes of i. over Sa uniformly distributed, errs, for all values of Wo. Therefore, we have
Wo
(h (h))) > (1 a p
( SG (.S(US))) < Ewo-olds, WW)] < d (9 US2),
where the first incquality follows from the definition of drmin S, and the second one by the assumption that (S1, S2, Y2) Ag. However, this inequality contradicts the fact that (2, Y2) & A1. Therefore, (h Wo we conclude that in this case, Ewo-qferrs, (h1,0) < (1+a) and Es,.a. (Ewonqlors ferrs, (h Wo Asl < a1) p.
Proposition Let m E N, (0,1/2), a a 10 and c E (0, Assume that the error of the learning
algorithm is 6)2 uniform. Let Sr. Sz, Si PB(m) (for i E [(e]). Let Y {ūr m be a set of labels that disagrees with Y uniformly selected [pm] labels and S is relabeling of S2 with the labels in Y Let
35

---

Published in Transactions on Machine Learning Research (05/2023)
We be the output of the learning algorithm given access to dataset S1 and initialization Wo- Then, with Ss
probability at least over the selection of {(S}, Sh, Yz) we have
Es, @ eerpp p (1
I E Ewon (1 2
mian (9, Si
U Si)
==1
log(2/6)
+ (1 + a) p 6m + 82 pm + V
2k
Proof. By Prop.
3
we have
Es, Ewo Fll.-wpp (1 & S, Eworold's (h5))) Wo
2 S
+ (1 + a Pm + 6m + 8 8mp.
We define i.d. random variables
V = I [Eoo (1 2 Liin (9 5
(11)
Therefore, we can rewrite,
P S 8s Swonolds, (15 (1 2
d (1
[[[]
(12)
By Hoeffding's inequality,
k V/
k
E[V]
2
c
S 2 2exp(-222
(13)
By choosing /1og(1/26)/2K, obtain that with probability at least 6, we have
1 k k
BM
S =v++ V /log(1/26)/2k.
(14)
When combined with Prop. 3. we obtain the desired bound.
Proposition 5. Let do. m, I. 2 3 and let X {- C Rdd be a set of m unlabeled samples. Lel FL be the class of ReLU neural networks f 1Rdo + ido of depth L and width do, i.e., f(x) a(b + Wy.0(br-11 + Wr.-i...o((,, + Wix))), where W; E Rdoxdo and b; E Rddo for all i E [L]. Let hy(x) = - (z) (S- l1(()) (S()i)) be the NCC classifier associated with f given S, where Se the subset of 5 of samples labeled c. Let Y (fi.... Um) be set of m uniformly distributed labels in {+1} and S = =1(0, 0.)1 Then,
C" Cmvm
(1 (1-2RR 2E
[ min errg(is)) reF.
L
(15)
do log(m) /lgg (do) log(em)
for some universal constant C²>0. 0.
Proof. We define a set of classifiers H' = [1((x) sign(])((x) -ill 11f(x)) w2ll) 12)l) I E Ft, MI, E Rdo..
By definition, the Rademacher complexity of Ht' can be written as follows (sce (Mohri et al. 2018)):
Radx(H()
By sup Σ (xh(zz)
(16)
m NEW
= ãr and (,;(2;) = - otherwisc. Therefore and we can represent )),((;;) using the classification error, (x,) = 21(h(xz)) = Ø11 - = 2 - [[h(r,) +
We notice that = 1f =
= = 0.1
ū:))= - 1. In particular, m Σm j.h((x:) = 2(1 - (h))
Hence,
Radx Radx(Hl)) = (1 11-By Eg
inf err err pm))(()) ) NEH''
inf erra(hy)) [EFL
2 1 2T
(17)
36

---

Published in Transactions on Machine Learning Research (05/2023)
where the last inequality follows from the fact that hy E Ht for any f E FL.
We notice that any h E H.' can be represented as follows:
h(x) =
mIll - [x u2ll)
sign(1]f(z) - -1ll2 [1f(z) - -Mal1 12l13)
sign((f(x), 2(12 -11)) + |||1111--11 ||
Therefore, H' C. H. = (h(x) = sign (z)), w) + b) | f E F E Ro, b RJ. In particular, Rads -
Rads(H), By (cf. Mohri et al. (2018):
, Corollary 3.19),
(H) log(em)
2 Radx(H)) 2 1 221 inf eng(hr)) rEFe
(18)
m
Furthermore, by (Bartlett et al., 2019). dim O(ULLog(U)), where U the total number of trainable
parameters in h H. By counting the number of parameters, we obtain that U 1 Ldo OLL))). Therefore, there exists some constant 1, such that dim(H) aLL2dh log(L)² log(do)). Hence, we obtain that
C'vm
(1-28,, 1-2 inf
[EA, errs(h)))
Log(LL) 2
(19)
dov/og((do (o) log(em)
for some universal constant C' E (0.1).
As next step, we would like to prove that I, a/ log(m), where denotes the right-hand side of equation 19 We consider two cases; S and
(where is Euler's number).
If a S e, since L 2 3 and m 2 3, we immediately obtain that L 2 2 a/ e/logmm).
On the other hand, 2 e, we can use the following inequality. Suppose L, a are two real numbers, such that, L log(L) 2 a 2 e, then we have L 2 exp(W(a)) (a)) 2 exp(log(a) - log log(a)) 2 a/ log(a), where W is Lambert's function. Since a 2 e and a S m (since do 2 3, m 2 3 and C", (1 2F lerr g (hr))) S 1), we have, log(a) & log(m) and L 2 a/ log(m) as desired.
Proposition 1. Let do. m, I. 2 3 and let X x= { C Rda be a set of m unlabeled samples. Let G (a(Wx æ + b) | W E Rdoxdo, E Rdd}, where a is the ReLU element-wise activation function. Let Y (V1.... ........ Fm) be of uniformly distributed labels in {+1} and $ ((I,, 0.)0m Then,
Cym (1 26)²
()] 2
(4)
do log(m) log do) log(em)
for some universal conslant C' >>0 0.
Proof. Let 8 E (0,1) and let L = El
Since (9, is non-negative, we can apply Markov's
inequality,
P [ (G,
<
Elg (G,5)
P ( (9, El (G.51)
> 2- 5,
(20)
where the probability is taken with respect to the selection of Y. The first equation follows from the fact that de din (S) is integer.
By Prop.
5
[ min S),
C' C'mm
(1-28, 2Eg
inf orgg(hi) feFL
L >
(21)
8
do log(m) Vlog(dg do) log(em)
As a next step, we would like to bound Ey (inf feF, err (h,)]. We note that any L-layer ReLU fully-connected network can be implemented using an (L layer ReLU fully-connected network (simply by taking the last layer to be fully-connected layer with zero bias and identity weight matrix). Therefore, Fr, C Fi, for all
37

---

Published in Transactions on Machine Learning Research (05/2023)
L S Lg. In particular, if L' (9, S) - L, then inf JeF, errs(hy) I yer,- crrs(hy) I c. We note that It & I. occurs with probability at least 1 by equation 20 In case this event does not happen, we may just use the fact that je ( - L. Therefore, by the law of total expectation:
Ey inf err errg s s -)- FEFL
(22)
Therefore, for any 8 E (0, 1), we have
C'vm
Eldmin [),
(1 2(e + 8))6.
(23)
do log(m) Vlo do log em)
By picking 8 = -1-22e/44 2,)/4, get (1 (1=2(e+ 8))6 (1 - 4e + 462)/8 (1- 22)2222)//88 and we finally obtain that
Cvm (1 (1-26 22)²
Elde min (9, 2
(24)
do log(mm) /log(d)) log(em)
for C' C8/
Proposition 2. Let do, m, L. 2 3, and let S1, S2 C TR x {+1} be two sets of m labeled samples. Let Yz be labels that are generated by first taking the set Y2 (the labels S2), then randomly selecting [pm] labels from this set. Each of the selected labels is then replaced with a random selection from the set {=1}. Let S2 be the same set as S2 with the labels Y2 replaced with Yz. Then,
CV pm
Ey, S (G,SUUS 2
(5)
do log [pm)) 1) log (do) log(e [pm])
for some universal constant C 0.
Proof. Let S2 be two sets of m labeled samples. Let X2 be the set of unlabeled version of S2. We note that Y2 is generated by first sclecting subset Xg of [pm] unlabeled samples and relabeling them with random labels Y3 from {=1}. This gives new set S3 of [pm] randomly labeled samples.
Let f be neural network of depth (9 U $2) such that the NCC classifier h, (given S1 U $2) has NCC train error Since hy correctly classifies all of the samples S S1 U, we notice that h, correctly classifies the subsct S3 of the pmm randomly labeled samples in S2. Hence,
Ey, ( (9.S, S2)1 2 Ex,Ey, Id (a))
(25)
By Lem. 1 for any set X3 of unlabeled samples, we have
pmm
Ey, Jd Ss) 2
(26)
do log [pm]) log(do) log(e pmn]
Hence,
CV [pm
Eyg (innnn (9, U U2)] 2 Exg L (o (9, St)] 2
(27)
dg log( [pm
log (g) /log
log(e [pm]])
as desired.
38


Reviews:
[{"review_id": "1io7uavqea", "reviewer": "Reviewer_Qs9F", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n+ This paper provides a novel view (as to me) to investigate the generalization of deep neural networks. The definition of  ϵ-effective depth and ϵ-Minimal NCC depth are elegant. More important, the generalization bound derived in this paper is non-vacuous, and this is supported by the experiments. \n+ This paper provides several interesting observations empirically. E.g., it empirically demonstrates that when sufficiently deep networks are trained, they converge to the same effective depth.\n+ This paper is well written. It provides clear notation for clarification, and I am glad to read it. \n\n**Weaknesses:**\n\n1.I wonder whether the experimental results still hold if the batch normalization (BN) layers are removed in the networks.? Indeed, the analyses in this paper will not hold if there is BN in the network, because the function of BN is different during training (using the mini-batch statistics) and test (using population statistics). Based on my understanding, the analyses shown in this paper should ensure the functions during training (for empirical errors) and test (for generalization errors) should be the same. \n\n2.Some claims should be more rigorous. E.g., “we claimed that the ϵ-effective depth is insensitive to the actual depth of the network (once it exceeds a certain threshold).”. To support this sentence, I think this paper should consider the optimization problem that whether the deeper model can be well optimized. E.g., If this paper considering training a more complex  dataset, e.g, ImageNet, it might be another story (is it still insensitive to the actual depth of the network?); or train the 56-layer/110-layer conv network (with and without residual connection), whether the results still hold?\n\n3.It is nice to see the proposed bound seems to be non-vacuous. However, I indeed have concerns on the effectiveness of the two assumptions. This paper should provide more discussion for the assumptions, e.g., is there any theoretically base, or can the assumption can be well investigated by experiments? It is more interesting for me, if this paper can provide experiments on synthetic datasets that can well be used to characterize the assumptions, and the results.  \n\n4.I have some concerns on the setup of initialization. It is not a common setup in practice that initializing weight $W_0=\\gamma$ (a fixed number) as described in page 3 that “we initialize the weights $W_0=\\gamma$ of h with a standard initialization procedure and at each iteration”. Does this paper means that $gamma$ is the variance/stdev? \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a new view to investigate the generalization capabilities of deep neural networks. It defines the effective depth and ϵ-minimal nearest-class center (NCC) depth of neural networks, and show the relationship between these two quantities is connected with generalization. In particular, it derives a generalization bound by comparing the effective depth of a network with the minimal depth required to fit the same dataset with partially corrupted labels, under two assumptions that are well formulated. This bound provides non-vacuous predictions of test performance based on the experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Address the weakness 1, 2 and 3. ", "broader_impact_concerns": "No impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BdEqFSVv5j", "reviewer": "Reviewer_rPZ8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n-----------\n\n- Empirical validation of the observation that DNNs tend to converge to an effective depth $L_0$ regardless of their actual depth $L$\n- Ability to provide non-vacuous generaliation bounds \n\nWeaknesses:\n-----------\n\n- Missing discussion and comparison with other non-vacuous bounds using PAC-Bayes or Conditional Mutual Information (see Missing Related works)\n\n- Since the proposed generalization bound requires splitting the training data into two sets and training multiple networks on this split. It would also be meaningful to include the average of the cross-validation error across these runs as a baseline for the estimated generalization error. \n\n- Estimating the generalization bound would require many computationally expensive runs (which might beg the question, why not just train the network for long enough and estimate the cross-validation error?)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nThis work investigates DNN generalization by introducing a new measure of the effective depth. It is defined as the first layer at which the sample embeddings are separable using a nearest-class classifier.\n\nAs per their bound, a network will generalize if its complexity is small compared to the complexity of a network required to fit the dataset with partially random labels.\n\nThis work provides the following key observations and validates these through empirical evaluations on multi-class classification datasets and various architectures. \n- Effective depth of the trained networks increase as the amount of random labels in the data increases \n- DNNs tend to converge to an effective depth $L_0$ regardless of their actual depth $L$ ( any feature layer above depth $L_0$ is nearest-class  )\n- Their proposed generalization bound is empirical, non-vacuous, and independent of the network depth.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions for Authors:\n------------\n\n- Table 1 does not include non-vacuous bounds provided by recent works (see missing Related works)\n\n- In Figure 1, what are the vertical and horizontal lines at the Epoch=200 mark?\n\n- Since you already split the data into sets S1 and S2, and train multiple networks. Could you report the performance of the cross-validation term as a baseline on the generalization error (simply the average of the error on the set S2 achieved by various networks when trained on set S1)?\n\n- Does your bound suggest anything w.r.t. improvements on the DNN architectures (since their effective depth is more often than not much smaller than their actual depth)?\n\n- How does your bound adapt to the setup where the later layers do not have the same width (as is prevalent in many popular architectures)?\n\n- How do you scale the proposed generalization measure to larger datasets (I would expect training multiple hypothesis on a large scale would be computationally expensive)?\n\nMissing Related Works: \n---------\n\n- Non-Vacuous Generalisation Bounds for Shallow Neural Networks (https://arxiv.org/pdf/2202.01627.pdf)\n- Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data (https://arxiv.org/pdf/1703.11008.pdf)\n- NON-VACUOUS GENERALIZATION BOUNDS AT THE IMAGENET SCALE: A PAC-BAYESIAN COMPRESSION APPROACH (https://openreview.net/pdf?id=BJgqqsAct7)\n- A New Family of Generalization Bounds Using Samplewise Evaluated CMI (https://openreview.net/pdf?id=GRd5UCkkXcV)\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5Ery0NJHvA", "reviewer": "Reviewer_Pgfg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Apart from the contributions discussed in the previous section, the paper is generally well prepared and easy to follow. Many experimental details are discussed both in the paper and appendix. These results either support the theory or better demonstrate key concepts, e.g., effective depth, in the paper.\n\nWhile the study is interesting and the theoretical results are correct, this reviewer has a mixed evaluation towards the empirical and theoretical results. Specifically, the generalization theory in proposition 1 seems like a proof-of-concept, in that the four terms in the right-hand side of Equation (4) are all elusive. It is rather difficult to assess the magnitude of these terms theoretically and rigorously; moreover, some quantities are assumed to be small without verification, e.g., $\\delta_{m, p, \\alpha}$ and $\\delta_m^1$.\n\nOn the other hand, experimental results are much comprehensive compared to theoretical results. The test of effective depth makes sense, and the predicted generalization bounds indeed tightens all existing ones significantly. This reviewer appreciates that details of how to estimate the first probability term in the generalization bound are provided in appendix. However, it misses any test of the $\\delta_m$-uniform mistakes assumption in experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper theoretically and empirically studies generalization bounds of deep neural networks (including convolutional, residual convolutional and feedforward architectures) in classification problems. The most outstanding contribution is the obtained generalization bound is much tighter than existing norm-based or uniform concentration-based generalization bounds (as demonstrated in Table 1). A closer examination of the generalization error in Equation (4) reveals several intriguing characteristics of the bound: 1) the bound depends on the learning algorithm and initialization; 2) the bound also depends on the data distribution; 3) the bound is intrinsic to the network architecture (e.g., effective depth), even though the network itself is overparameterized. All these observations are important factors to unveil the generalization properties of large neural networks. This reviewer believe the topics and findings in the paper will be of interest to the community.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Neural collapse and effective depth are well motivated and recognized. However, conditions like $\\delta$-uniform mistakes are far less explained. It gives the feeling that authors need these conditions because they know how to do the proof under these conditions. At least, some empirical demonstration should be provided to validate all the terms in the generalization bound, instead of just assuming they are dominated by the probability term.\n\n2. NCC separability can be closely related to margin conditions in classification problems. When the noisy label becomes dominant, classification margin fades and makes separability difficult. Is it possible to prove a rigorous bound for some simplified classification problems, if general setting is elusive. A candidate can be linear separable data with a small fraction of label contamination.\n\n3. (optional) Will the width of the network play a role in generalization? For example, is it possible that narrower networks often need large effective depth, yet wider networks do not (or there is a threshold on the width of the network).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new measure to investigate the generalization ability of neural networks. It provides a new perspective to understand the generalization by introducing effective depths and nearest-class center (NCC) depth.  

In the review phase, this manuscript receives two positive and negative comments.  All the reviewers consider the proposed method novel and the experimental results comprehensive. Compared with the existing methods, this paper gives a different view and makes a contribution to the community. However, the theoretical results still have some blemishes as pointed out by reviewers (e.g., Quite a few quantities are assumed to be small but not proved to be or tested in experiments). The authors are encouraged to further improve the theoretical results in the final version.

Overall, I recommend accepting this paper with minor revision. 
Decision: Accept (poster)