Network-to-Network Regularization: Enforcing Occam's Razor to Improve Generalization
Authors: Rohan Ghosh
Mehul Motani
Venue: NeurIPS 2021 Poster (2021)
Keywords: Generalization
Deep Learning
Complexity
Label Noise

Abstract: What makes a classifier have the ability to generalize? There have been a lot of important attempts to address this question, but a clear answer is still elusive. Proponents of complexity theory find that the complexity of the classifier's function space is key to deciding generalization, whereas other recent work reveals that classifiers which extract invariant feature representations are likely to generalize better. Recent theoretical and empirical studies, however, have shown that even within a classifier's function space, there can be significant differences in the ability to generalize. Specifically, empirical studies have shown that among functions which have a good training data fit, functions with lower Kolmogorov complexity (KC) are likely to generalize better, while the opposite is true for functions of higher KC. Motivated by these findings, we propose, in this work, a novel measure of complexity called Kolmogorov Growth (KG), which we use to derive new generalization error bounds that only depend on the final choice of the classification function. Guided by the bounds, we propose a novel way of regularizing neural networks by constraining the network trajectory to remain in the low KG zone during training. Minimizing KG while learning is akin to applying the Occam's razor to neural networks. The proposed approach, called network-to-network regularization, leads to clear improvements in the generalization ability of classifiers. We verify this for three popular image datasets (MNIST, CIFAR-10, CIFAR-100) across varying training data sizes. Empirical studies find that conventional training of neural networks, unlike network-to-network regularization, leads to networks of high KG and lower test accuracies. Furthermore, we present the benefits of N2N regularization in the scenario where the training data labels are noisy. Using N2N regularization, we achieve competitive performance on MNIST, CIFAR-10 and CIFAR-100 datasets with corrupted training labels, significantly improving network performance compared to standard cross-entropy baselines in most cases. These findings illustrate the many benefits obtained from imposing a function complexity prior like Kolmogorov Growth during the training process.  

Network-to-Network Regularization: Enforcing Occam's Razor to Improve Generalization
Rohan Ghosh and Mehul Motani
Department of Electrical and Computer Engineering
N.1 Institute for Health Institute of Data Science
National University of Singapore
rghosh920gmail.. com, motani Guu edu.sp
Abstract
What makes classifier have the ability to generalize? There have been lot of important attempts address this question, but clear answer still elusive. Proponents of complexity theory find that the complexity of the classifier's function space key deciding generalization, whereas other recent work reveals that classifiers which extract invariant feature representations are likely to generalize better. Recent theoretical and empirical studies, however, have shown that even within classifier's 's function space, there can be significant differences in the ability generalize. Specifically, empirical studies have shown that among functions which have good training data fit, functions with lower Kolmogorov complexity (KC) are likely to generalize better, while the opposite true for functions higher KC. Motivated by these findings, propose, in this work, a novel measure complexity called Kolmogorov Growth (KG), which we use to derive new gen- eralization error bounds that only depend the final choice of the classification function. Guided by the bounds, we propose a novel way of regularizing neural networks by constraining the network trajectory to remain in the low KG zone during training. Minimizing KG while learning is akin to applying the Occam's ss neural networks. The proposed approach, called network-to- to-tewookk regu- larization, leads to clear improvements in the generalization ability classifiers. We verify this for three popular image datasets (MNIST, CIFAR-10, CIFAR- 100) across varying training data sizes. Empirical studies find that conventional training of neural networks, unlike network-to-nettorkk regularization, leads networks of high KG and lower test accuracies. Furthermore, we present the benefits of N2N regularization in the scenario where the training data labels are noisy. Using N2N regularization, we achieve competitive performance on MNIST, CIFAR-10 and CIFAR- 100 datasets with corrupted training labels, significantly improving network performance compared to standard cross-entropy baselines in most cases. These findings illustrate the many benefits obtained from imposing a function complexity prior like Kolmogorov Growth during the training process.
Introduction and Motivation
On the surface, the problem of learning to generalize well over unseen data seems an impossible task. Classification inherently a problem in function estimation, and the finite information that the training data samples impart seems hardly enough to be able correctly guess the behaviour of the function over the unseen data samples outside the training set. However, assumption of a structured ground truth label function, which is the unknown function which generates the ground truth label for any datapoint, leads to more optimistic outlook on the problem. Without the assumption of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

structuredness in the ground truth, learning is not guaranteed, as was observed in the no free lunch theorem M. As shown that work, there is no universal learning algorithm which can generalize well for possible choices of ground truth label functions.
Since one does not have any control over the true nature of the ground truth function in any classifi- cation problem. the other important parameter that decides the ability of a classifier to generalize, the complexity of its function space itself. Over the past few decades, there have been multiple attempts at bounding the generalization error on the basis of various complexity measures 2 the classifier's 's function space F. The overall results of these theoretical developments indicate that generalization is primarily governed by metrics that are proportional to the size of F. Examples of complexity metrics in this regard include Rademacher complexity, VC-Dimension, and Local forms of Rademacher Complexity (for more tight bounds). However, as observed in [5] these metrics lead to relatively loose bounds on the generalization performance for deep neural networks. This is because deep neural networks have high complexity spaces with flexibility to learn any label assignment on any set of training datapoints. This was perhaps most clearly observed in [6], where even after random label assignments on the training data samples, the networks still were able to fit the training data labels with no errors. Thus, often other methods have been explored to establish the relationship between complexity measures and generalization performance 7 g
3 4 of
such as causal relations.
These studies lead to a natural question, which is, other than the metrics which relate to the size of the function space of a classifier, what other factors contribute towards its ability to generalize? State-of-ther of-tt---rrttttte deep neural networks, as observed above, will yield very high complexity spaces, which does not explain their remarkable ability to generalize well in complex high-dimensional supervised classification problems, such as vision. We note, that metrics such as Rademacher complexity or VC dimension, which relate to whole function spaces F (or subspaces within F which fit the training data well), essentially assign the same generalization gap to all functions within F (or the subspace within F). However, there has been longstanding understanding of the fact that usually among all functions which fit the training data well, simpler functions are expected to generalize better. This is example of the Occam's 's Razor principle, which states that among all hypotheses that explain a phenomenon, the simplest hypothesis is preferred [9] In the context of neural networks, even for very high complexity deep neural network function spaces, there will always be some weight configurations of deep neural network, which yield simpler functions. For example, all network weight configurations yielding input-output functions which can still be efficiently approximated by smaller, shallower networks, could be considered to be simpler. An extreme example of this would be where we assign all weight values to zero within deep neural network. The function that results from this weight configuration is essentially the constant function f f(X) O. This observation points to the fact that even within a function space of deep CNN, not all functions are equally complex, as some of them can still be approximated by shallower networks.
To that end, primary objective of this paper is to probe complexity measures which enable us to assign a level of complexity to individual functions within a function space. Subsequently, our objective would be to steer the learning process towards network configurations which yield less complex input-output functions. An important work which explored similar directions is 100, where metrics from algorithmic complexity were developed to bias the learning process towards simpler functions. In this regard, measures of descriptional complexity (3] of functions have been proposed over the years, which quantify the level of complexity of an individual function, based on its shortest description. Although fundamental measures of descriptional complexity such as Kolmogorov Complexity [I] or Solomonoff Probability 112 are uncomputable, computable approximations to them have been developed [13). In spite of this early work, there is a lack of concrete theoretical or empirical work to continue this line of investigation after [TO] Mainly, there is a lack of work that explores the relevance of such descriptional complexity measures to the generalizational ability of functions. That is. until recently, when interest in the descriptional complexity of a function was renewed as it was found that outputs of random maps tend to be biased towards simpler functions 14. This result indirectly hinted that for classification tasks, the ground truth labelling function has a simple description with high probability. This was further investigated in [5] in the context of deep neural networks, where it was found that the Lempel-Ziv (LZ) complexity (a form of descriptional complexity) of most neural networks with random choices of weights are low (shorter description), in accordance with the result in 14]. Empirically, it was found that network weight configurations which lead to functions of smaller Lempel-Ziv complexity show better generalization performance.
2

---

These results and observations show that descriptional complexity measures may help to understand empirically the generalization behaviour of deep neural networks. In this paper. we advance this line of investigation by proposing a new theoretical framework for relating descriptional complexity measures to generalization performance. Subsequently, we also provide a computable method which improves generalization performance of neural networks by lowering their descriptional complexity.
2
Contributions
This paper makes the following contributions,
1. First, we undertake a brief theoretical analysis for exploring the relevance of descriptional com- plexity measures of functions to their expected generalization error. We propose a novel measure of complexity called Kolmogorov Growth (KG). Error bounds are estimated which portray the dependence of generalization error of a single function f to K KG))). The bounds depict that functions of higher KG (f) will likely lead to a higher generalization gap. This result formalizes the Occam's razor principle for classifiers, and also concurs with the empirical findings in [5), where functions of higher LZ-Complexity showed worse generalization performance.
2. Like Kolmogorov Complexity, KG is also uncomputable. Therefore, we propose computable approximations of KG for neural networks, based on the concept of teacher-student approximation (similar to knowledge distillation (15)). Specifically, we show that neural network functions f which can be approximated well by smaller networks will have smaller empirical KG with high probability.
3. Next, using this idea, we then develop a novel method for regularizing neural networks, called sewoork-to-netorte (N2N) regularization. N2N regularization forces trained network configurations to be of low KG. We find that doing so not only improves the generalization performance across a range of training data sizes, but also helps in the case of label noise. For instance in MNIST, test error decrease by 94%, reaching results competitive with benchmark methods.
4. Finally, we study the evolution of empirical KG as networks are trained and observe that, in the standard classification scenario, networks show a sharp decrease in their KG training progresses. However, this trend completely reverses when the training data labels are noise corrupted and N2N regularization is able stem the undesirable increase of KG during training.
3 Kolmogorov Growth: Relevance to Generalization
Assume that training data consists of m d-dimensional i.i.d samples and their labels S [[21, (22, 32),.., ... (Zm: Vnm) drawn from some distribution pm.
We propose two growth measures for single function f, namely Kolmogorov Growth K KG (f) and empirical Kolmogorov Growth KGs(J). Note that, when appropriate, we may drop the subscript vn and refer to K &. (f) as KG()). These measures are primarily motivated from the well-known growth function in statistics. The growth function (J) is defined as
Imm (F)
max ZER-
f(z)), (zm)) : e FH
Note that the growth function is defined for space of functions and captures the maximum number of label assignments a function space F can generate on any m points in Rdd
To define Kolmogorov Growth measures for single function f. we first need to generate a function space from f, based on a description D, of f. This is done via noting all the parameters involved in the description Dy (other than the co-ordinates in RR)), and then assigning all possible values to those parameters to generate space of functions F(D,) from the description Dy. Next, we note that for function f. we consider multiple descriptions (D), D3, DJ,... all of which faithfully generate the output of f over all points in Rd, with the additional constraint that each F(D)) should fit any m datapoints sampled from pm.
Given these observations and denominations, we then can define the Kolmogorov Growth of a function f as follows:
log IIm (F(D))
KG, (f) min
m
3

---

Note that (f) requires the knowledge of distribution pm of the training samples. For an instance of the datapoints S, we define the empirical Kolmogorov Growth via the empirical growth function IIs (F). which only computes the number label assignments a function space can generate over the given m training data samples in S. Thus, [F) = ((f()1), fz22). f(2m)) E FH This leads the following definition of the empirical Kolmogorov Growth of function f:
log Hss (F(D))
KGs(J) = min
m
Remark: Kolmorogov growth is indirectly motivated from Kolmogorov complexity itself. However, unlike Kolmogorov complexity, which is the length of the shortest program that generates f. Kol- mogorov Growth is concerned with the smallest function space that f can belong to, that can still fit the data well. Functions which have shorter descriptions usually require a smaller number of variables and are expected to have lower Kolmogorov Growth. Moreover, it turns out that Kolmogorov Growth allows directly comment on the error bounds for the function f (see Section [.1]. We believe that a possible direction of future work would be to do deeper study of the relationship between Kolmogorov Growth and Kolmogorov Complexity itself.
Remark:
Note that, in the binary classification scenario, for a completely unstructured function f (i.c., f outputs random labels at every point X IR,), one expects (f) to be near its maximum value (i.e.. log 2). A structured f would generate shorter descriptions with fewer parameters and therefore lead to smaller KG(f).
3.1 Bounding Generalization Error using Kolmogorov Growth
Here we present error bounds that depend on (Gf)), where f is the classification function, given the m training data samples and their labels in S. As before, the data samples and labels in S are drawn from some underlying distribution pm
We now define a set of error functions for computing training loss (0-1 loss) on S, denoted as eris sf)). and the overall generalization error with respect the distribution P, denoted by erry(f). We define them as follows:
f(z))))
errs(s)
(4)
2m
(1 f())v)
errp(S)
E 2.groP
(5)
2
These definitions hold for any function f. Note that the error functions depend both on the function and the distribution P.
With this, we have the following results. The proofs of all results are provided in the supplementary material.
Theorem For 0 < 8 < 1, with probability 2 1 - 8 over the draw of S, we have
errr(f) seirs()) (f) log (1/8)
(6)
2m
The following corollary of the above theorem gives bounds that depend empirical Kolmogorov growth (f.
Corollary 1.1 For 0 < 8 < 1, with probability - å over the draw of S, we have
errp(f) serrs()) + 22 22K 4. 2 (4/8)
Theorem and its corollary essentially state that for functions f of lower Kolmogorov growth, we should expect a smaller generalization gap. In what follows, we outline ways to approxi- mate the empirical Kolmorogov growth (f).
Remark:

---

Teacher-Student Approximation Bounds for Kolmogorov Growth
The fundamental idea for approximating empirical Kolmogorov growth of function which belongs to the function space F is to use student classifier with function space F (with much smaller parametric count and complexity) to approximate the given function f (the teacher). We apply this idea recursively. That is, if the function Jsmay E F smaal approximates f best, recursively estimate the empirical Kolmogorov growth of f Immatt by approximating it via another classifier with smaller function space F (thus, 1mm (F ( (F < 11m (F) smalt)), and so on. We use this
recursive way to then obtain a final estimate for (f) We conjecture that, like Kolmogorov complexity itself, the true (J) is uncomputable, so the estimate that results from this recursive approximation process is essentially upper bound to the true (Gs(f). The following theorem establishes an upper bound to empirical KG approximation from a single smaller student classifier.
Theorem Given the function f F 12 - IR² which outputs class logits for binary classification. We construct a function space F small such that 11m (F smalt) < [m and Vig Fsmally there exists description Dg such that IIs (F((g)) I [I smsai) We approximate f via another function femall E F IRd + RR2 and let Cmaz be such that
eaaz/2 2 maxl]sfemal - f()]
(8)
X X
Denote the output probabilities generated from the corresponding logit outputs of f(X) using the softmax operator (lemperature T = 1), as (X)) (label oulput) and Pi Pi(J(X)) (label output). Let 0 < 8 < 1 be such that
Pr (IoN
PO(I(XO)) (((((X))
3 Emaa 56
(9)
when X is drawn from S. Then we have,
log lIs (F F.mai))
KGs(1) s ō dlog 2
(10)
where m. is the number of samples in S.
Remark:
Theorem demonstrates way bound the true empirical Kolmogorov growth of the function f. using single student classifier function famall E F small- Note that unlike in Theorem there direct constraints on the expressivity of F1 Fsmaltt but rather a joint constraint on F small and 5 combined. If F1 small cannot fit all points sampled from pm, then the approximation error in 5 will likely be higher, which will add to the estimate of KGs(J) (J)) The proof of Theorem 2 and its extension to the recursive approximation case are given in the supplementary material.
5 Networr-to-Network (N2N) Regularization
We denote the base network be trained as Nasse and the function modelled by the network weights wasse as Arbase (wrese,_ .X), where X E I& is the input. Here, (hass((w "agaas,,'r XX) represents the output logits for the network Nbase when presented with the input X. Thus, we have Nouse (wh X) E RRo where is the number of classes. For what follows, let us denote the available training data and their labels by S = {X,, y: J
The approach that follows is directly motivated from the result in Theorem The main objective to ensure that the KG of the network stays low during learning, using the teacher-student approx- imation error in Theorem
2 This is primarily achieved by ensuring that during training, the base network function /hose (w case ;X) is always near to some function within the smaller network's function space. Next, we outline the details of the proposed multi-level network-to-networrk (N2N) regularization approach.
5.1 Multi-Level N2N: Details
In multi-level N2N regularization, we have multiple smaller networks nymail .nz .ngmall ..... small of decreasing complexity such that 11m (Flmll) > 11 ( 2 > 11m (F k
5

---

Algorithm N2N Regularization (Multi-Level)
Input: Training data {X, Yi 1m base network Nhose and its weights wdase, networks nimail mamaall 3..., "KK nemall with weights W1, W2, WK (s.t. Infmall > |ng > ... m megalli in
size), Number of epochs J, Hyperparameters λo >1, A AK-1 C0,, .. aK, Ebases Esmall-
1: for j = 1,, .,.;: do for iler = 1,2,... Chose do
2:
3:
Li -> (N (Xi), Mi) + Ap A (X;) (x:mal(X:)]1
4:
Weight update: whsse t w bose an OC;
m Swaase
5:
for k = .., do for iter = 112.... Csmall do
6:
7:
if 1: = then
8:
Ls = Σ | (X;) - ni mamall (X:))1 + [llngmmll (X,) nimaal (X;)]²
9:
else if k = K then
10:
L1 >x Eillggmal (Xi) n (X;)
11:
else
12:
Ls = E, Emllngmali (X;) - n (X,) + A [l (X,) - - -n271 (X2)
13:
Weight update: Wi f Wk m She
as 0C2
The corresponding functions resulting from the network weights wi, W2, WK are denoted as nf amail (w1, X), n (1gmal(ws) ..., n nimaal (Wx. X). Next, we outline the loss functions for all net- works. For the larger to-be- be-trained base network Nhose, the loss objective is to minimize cross-entropy loss on S while being close to nimmall (w1, X) for some choice of weights w1 (C1 in Algorithm I For the smaller network nimmal, the objective is two-fold: find the weight configuration wi that approximates the larger network function base while also being close to nz (w2, X) for some choice of W2 (L2 in Algorithm D.. Thus, we force the smaller network n rofmall to be close to the base network and an even lower-complest comel-complexity network n² nmmall at the same time. Similarly we can define La, L3, L except for LK which applies the smallest network nggaall The loss objective for nimmal is to just keep n gmaall X) close nk-1 ,, X). Finally, optimize the loss functions in an alternating manner in the order of L1, L2, .., LK. Details are given in Algorithm [ The choice of mean- mean-squared error based loss functions here directly follows from the result in Theorem 2 Note that Algorithm | updates with the entire batch of training data points at each iteration, and can be extended to the of minibatch stochastic gradient descent (SGD).
5.2 Other Relevant Approaches in Literature
To the best of our knowledge, our proposed approach novel, and we did not find much relevant work. Conceptually, we found the reverse knowledge distillation method [16] to be the most relevant to our proposed approach, which regularizes large teacher networks using smaller, trained versions of student networks of less depth. The outputs logits of the trained student networks are then essentially re-used for smoothing the outputs of the larger neural network. Here, we do not directly use trained student networks supervise the teacher, but instead simply ensure that during training, the teacher network is within reach of some student network (which may change throughout the training process), which is
relaxed constraint. Also, the mean-squared error based approximation error between the student and teacher networks is motivated from Theorem 2 and differs from KL-divergence based measures used in knowledge distillation. Another point of difference is that N2N uses multi-level approach for recursive way of regularizing multiple networks of different levels of complexity.
6 Experiments
We test N2N on three datasets: MNIST 17], CIFAR-10 18] and CIFAR- [1)].
We also demon- strate that N2N regularization improves performance in the presence of label noise. Lastly, we analyse Kolmogorov growth networks during training. Experiments were either carried out on an RTX 2060 GPU or a Tesla V100 or A 1100 GPU. As mentioned in Algorithm [ an epoch refers to a total of Cbose iterations of training the base network and esmall iterations of training the smaller networks on the whole dataset. Code will be made available at https//giilbb.oo///hhhh////

---

MNIST
CIFAR-10
100
Dara Size (Triningg)
nog
drope12
dropil2
+N2N-1
drop 12
+N2N.2
rgg
12-nerm
-N2N-1
12 N2N-2
reg
12/morm
12 +NIN-1
12 N2N-2
1000
96.74..m o.
97.22.mu
2012
97.82
45.35 125
48.99 uam
50.58 1006
$1.99114
6.
1.97
8.961e3:
9.45 mz
2000
97.71 1000
98
13.06.00
98.16..u
98.27..00 .000
51.88 m047
15.42
S6.21
57.23
9.75
13.01 Ln2
13:75
10000
98.92
99.07.0x
99.13
72.13 -22
72.55 -a
33.51 72.89.13
35.0 35.03
45.57
Complete
99.38
99.59
99.70 200
92.53
93.26.10
mm
Table 1: Test Accuracy on MNIST, CIFAR-10, and CIFAR-I00 for different training data sizes and different regularization choices (dropout, L2-norm, single-level N2N, multi-level N2N and their combinations). We note that N2N combined with dropout and L.2nnorm or only L2-norm leads to improvements in test accuracy for all cases. This shows that N2N regularization complements other regularization approaches well, improving generalization performance of trained networks further.
6.1 Supervised Classification: MNIST, CIFAR-10, CIFAR-100
The primary objective of the experiments pre- sented here to see whether N2N regularization can drive the training process towards network configurations that generalize better. For each dataset, results are reported for various choices of training data size. Furthermore, to show that our regularization approach complements other commonly used regularization approaches, we show results when our approach is combined with Dropout and L2-norm regularization. For the ResNet networks (CIFAR-10/100), we com- bine N2N with 1.2-norm regularization. All net- works were trained for total of 200 iterations, and in each case results reported are averaged over five networks. For all experiments we set Cbase 3. Esmall 1 in Algorithm [ provided in the supplementary material. Note that due to the additional iterations for training the smaller networks, the worst case training time for the N2N approach is 1.5 times longer than standard training. Across all three datasets, we generally find that for larger training data sizes, smaller regularization parameters yield best performance, reinforcing the fact that N2N is indeed a form of regularization. This is primarily because for large training data, the distribution is dense enough for the network to learn, and thus less emphasis can be given to the N2N regularization term.
log Ne (Tima))) m
KGs(J)
m=E00000.000)
log
drop+12+
reg
drop + 12
N2N-2
MNIST
0.0046
0.0032
0.0015
CIFAR-10 CIFAR-100
0,4721
0.4545
0.4427
0.725
0.6901
0.6324
Table 2: Averaged approximation error term (6 in Theorem 2 for the networks trained MNIST,
CIFAR- 10 and CIFAR-100 datasets for m = 1000, 2000. Smaller values of 5 imply lower (Gs(f) of the trained networks.
The values of the regularization parameters (Λo, A1) are
Results are shown in Table [ and the average approximation error for the trained networks is shown in Table 2 We note that the use of N2N regularization improves test accuracy. Mainly, see that N2N regularization complements common regularization approaches such as dropout and L2-norm well. In all cases we find that combining these well-known regularization approaches with the proposed approach yields the best results. Furthermore, we also see that the improvement in performance persists when the training data size is increased. Lastly, in most cases, we see that 2-level N2N regularization (N2N-2, m = 2 in Algorithm I.. outperforms single-level N2N (N2N-1, m in Algorithm []. with the exception of CIFAR-10 10 with the full training dataset. For the CIFAR-IO and CIFAR-T00 datasets, we used the benchmark ResNet architectures ResNet- 44 and Re respectively. Our results with L2-norm regularization for the ResNet-44 and ResNet-50 architectures are slightly better than the results originally reported in 20) For the MNIST dataset, we used a 5-layer CNN with 3 conv layers and fc layers. Network architecture details are provided in the supplementary material. Note that although better results can be found in literature, our objective was to demonstrate that using N2N regularization in conjunction with common regularization approaches can benefit both shallow CNN architectures (MNIST) and ResNets (CIFAR-10 10, CIFAR-100) 100). Furthermore, as Table shows, we find that N2N reduces the empirical KG of trained networks, and datasets on which test accuracies are lower yield higher KG of trained networks. This supports the implications of Theorem I as high KG functions are expected to have a larger generalization gap.
6.2 Learning with Noisy Labels
As our proposed regularization approach constrains the network function to simpler by minimizing an approximation of Kolmogorov Growth, it naturally applies to the case of noisy training labels.
7

---

MNIST (Symmetric Label Noise p 0.5)
CIFAR-10 (Symmetric Label naise p = 0.2)
Test Accuratcy
14
Test Accuracy
R8
70
Regularization Parameter (Ag)
Regularization Parameter (Ac)
(b)
Figure 1: The effect of the hyperparameter Ap of our proposed N2N regularization approach on
test accuracy on the MNIST (symmetric noise = 0.5) and CIFAR- 10 (symmetric noise p = 0.2)
datasets. The networks were regularized using 2- N2N, with fixed λ 0.1. In both datasets, we see significant performance improvements in response to regularization.
Noise level
F-Corretion
22
Decoupling 23
MettorNet 24
Co-Teaching 25
SCE 21
N2N (2-Levels)
MNIST
p=
12 (94.05)
a0 (94.05)
26.70 (94.05)
97. eazs (94.05)
99.30
(93,57)
99.09... (93.57)
p= 0.5
29 (66.05)
81 1S (66.05)
90.08 (66.05)
32 (66.05)
97.87 (65.63)
98.32 (65.63)
CIFAR-10
p= 0.2
84.55 (76.25)
80 nos (76.25)
80,76 (76.25)
82. 12 (76.25)
88.91 cas (86.42)
88.06 oo. (86.42
p= 0.5
39.83=4 (48.87)
a1ss (48.87)
71. 10 (48.87)
74.02 (48.87)
83,91 = 77.15)
80.95 (77.13)
CIFAAR-1OU
p= 0.2
61.7=aa (47.55)
44 42.3 (47.35)
52.13 (47.55)
54, 24a23 (47.55)
65 36 (64.4)
66.33 (64.4)
p= 0.5
41.04 ason (25.21)
25.80 sow (25.21)
39.00 (25.21)
41.37ears (25.21)
49.27 (48.74)
54.79 (48.74)
Table 3: Test performance on MNIST, CIFAR-10 and CIFAR-100 when symmetric label noise of probabilities p = 0.5 and p = 0.2 was applied on the training data labels. Average accuracies are reported for various state-of-the-art and benchmark approaches that have been recently proposed in literature, including benchmark approaches such as symmetric cross entropy (SCE (21)). The numbers within the brackets represent the test accuracy of the corresponding network architecture when trained with standard cross-entropy loss, and thus the relative reduction in error can be construed measure of effectiveness of each approach. We note that N2N regularization helps improve the cross-entropy baseline in all cases, significant improving in some of them.
Without regularization, label noise in the training data usually forces a network to emulate a more complex function, as it potentially makes the decision boundary more complex, fact that also empirically observe in section 6.3] We stipulate that N2N regularization should help the network in achieving simpler functions to approximate the training data labels, favoring simpler decision boundaries over complex ones, and thus potentially shielding against the corrupted labels to certain extent. We test whether enforcing a simpler function (large λg, ...Am) at the cost of compromising training loss can help improve test accuracy, when the training data is corrupted by label noise. We tested the cases where symmetric and asymmetric label noise of some probability p was applied (same as in 21]), and show our results for symmetric noise with p = 0.5 and 0.2. Results with asymmetric pair-flip noise of probability p- = 0.45 are shown in the Supplementary Material.
First, we show the results for symmetric label noise of probability CIFAR-10 and CIFAR-100 in Table For F-correction 22) Decoupling 23] MentorNet 24 and
0.5 and p 0.2 on MNIST,
Co-Teaching 25 methods, we report the accuracy over the last ten iterations of training as observed in (25). along with their standard cross-entropy results with corresponding network architectures for reference. We do the same for our implemented SCE and N2N methods on MNIST and CIFAR- 10, but for CIFAR- 100, we report the accuracies using 48k-2k rrainin-validdttin split of the data for both, as we find it to yield best performance (due to hard convergence). Note that we use the same network configurations for SCE. The values of A and X are provided in the supplementary material. We find that N2N regularization yields competitive performance in most cases. We also plot the test accuracy as a function of the regularization parameter Ao in Figure We find that for MNIST, large An helps achieve significantly higher test accuracy, whereas for 10 and CIFAR-100 accuracy peaks around Ao = 0.6 and A 0.5 respectively. Note that accuracies may differ from Table because of different training configurations used.
8

---

MNIST (No Label Noise)
MNIST (Symmetric Label Noise p = 0.5)
Kolnogorov Growet (Bound)
Without NEN
Kolnezorov Growth (Round)
0.215
With NIN Rug (/0 0.25)
Witherr N2N Reg
0.30
Rog
0.200
Wasa NIN Rug (0 - 2.0
With 3.0)
0.08
0.150
With NIN Rog (o 4.0)
0.115
9.100
8.855
20
80
Training Epoch
Training Epoch
(a)
(b)
Figure 2: We show the trend of the KG of networks (approximated using Theorem 2 during the training process MNIST-1k (with and without label noise). In (a), we plot how the KG of networks changes during training on MNIST (no label noise). There, we compare the trend for three different cases: N2N regularization, N2N regularization with Åy 0.25, and N2N regularization with Ao = 0.50. As λ increases, we see that the KG of the trained networks show a clear decrease, with the trajectories deviating after few epochs of training. In (b), we show KG of networks during training on the MNIST dataset corrupted with symmetric label noise of probability we find that the networks trained without any N2N regularization have significantly higher K than the networks trained with N2N regularization. Particularly, we find that as Åg increases. KG reduces, while also improving test performance (see Fig. [].. All values of KG estimated here are 10-fold averages over multiple training sessions with randomly initialized networks.
0.5. There,
6.3 Comparing Kolmogorov Growth Trajectories during Training
The improvements observed via the use of N2N regularization lead to the question of how the network trajectories differ when N2N regularization is used, as compared to when it is not applied. We use the result in Theorem 2 to compute the bounded approximation to empirical Kolmogorov growth of the network function. We thus plot the approximation of KG()) of the function represented by the neural network during the training process. Note that the variation of KG in all plots is only owing to the changes in the approximation eтror term in Theorem 2 as F small is fixed to a single-layer CNN (of fixed configuration) for all results in Fig. 2 iTg (Fl (Femalt) was estimated using VC dimension based approximation shown (7]. Results are shown in Figure We find that in the case of no training label noise, the KG of networks typically have high initial values, steeply reducing within few epochs of training, after which it stabilizes. Expectedly, when trained with N2N regularization, we find that the final KG of networks are lower, compared to KG of networks trained without N2N. In the case of label noise, we report some interesting observations. First, we see that, differently from before, the KG values rather increase with training and stabilize eventually at higher values. This is almost an opposite trend to the case no label noise. This can be partly explained by the fact that as training progresses, the network slowly adapts its decision boundary fit the erroneous labelling, eventually resulting in a decision boundary high complexity. For the label noise case, we find that N2N regularization significantly reduces the increase of KG during the training process. Furthermore, larger values of the À parameter leads to networks which exhibit smaller KG values. This also helps explain the significant gains in test accuracy observed for MNIST earlier in Table 3 when using N2N regularization.
7 Discussion and Reflections
This results in this paper further the recent work by (5), where was shown that neural networks are inherently biased towards simpler functions of lower Kolmogorov complexity. In particular, we provide an actionable method for incorporating a function complexity prior while learning, using a novel measure called Kolmogorov Growth. Unlike Kolmogorov complexity, which is the description of the shortest program that generates some function f. Kolmogorov Growth is concerned with the smallest function space that ʃ can belong to, that can still fit the data well. Functions with shorter descriptions will typically need fewer variables and thus may have lower Kolmogorov Growth. Although smaller function spaces have less expressive power, as recent work in [6] shows, even

---

shallower neural nets can fit random labels on the training data points. The observations in [ however, put a new perspective on the results in [6] any random choice of network weights on smaller networks is likely to yield low complexity function. Thus, even shallower networks can potentially exhibit a wide range of complexities. Among them, the higher Kolmogorov complexity functions are likely required for network to fit random labels (similar to observations in (5). In the case of label noise, N2N considers this fact by avoiding directly training the shallower networks to fit the noisy labels, which helps reduce their descriptional complexity, which then helps in regularizing the larger base network. As such, when using a pre-trained shallower network to regularize the base network (reverse KD), we found that performance can significantly suffer in the case of label noise.
Via N2N regularization we see that enforcing low KG for large networks can improve their ability to generalize. The proposed approach greatly helps in the scenario where the training data has noisy labels, attaining competitive performance on the three tested datasets when the training labels are corrupted with symmetric label noise. In the case of label noise, we see that networks trained without N2N regularization have larger Kolmogorov Growth (see Figure 2). which reduces immediately following the application of N2N regularization. Furthermore, it is clear that by varying the emphasis on minimizing the regularization term via tuning the À parameters, the KG of subsequently trained networks can effectively be controlled. As Å increases, more emphasis is put lowering KG, which improves generalization and yields better test accuracy. However, this happens up to a threshold (see Figure[I and test accuracy decreases A increases beyond the threshold. In the case of training data with noisy labels, we find that the threshold is larger because we can put less emphasis on fitting the noisy training labels and more emphasis minimizing KG.
Our theoretical results in Section 3.T show that network configurations that can be approximated well by smaller networks of lower complexity will have low Kolmogorov growth, and subsequently, lower generalization error. These results concur with the very recent theoretical findings in [26], which finds analogous results for the Rademacher complexity based generalization error framework, in the context of knowledge distillation. Our main result in Theorem outlines an Occam's razor like principle for generalization. Theorem fimplies that for all functions which have zero training error, the function with the smallest (f,(f) will be the most likely to show the least generalization error.
Our empirical findings consistently show that driving the networks towards simpler functions of lower Kolmogorov Growth leads to networks that generalize better. We find multi-level N2N follows from a theoretical result shown in the Supplementary material, where we bound the empirical KG of the base network function based on the set of recursive mean-squared error estimates. However, KG bounds resulting from recursive estimation are provably less tight than single-estimation KG bounds of the form in Theorem 2 We believe that more bounded loss terms could be one of the reasons behind 2-vel N2N yielding better performance on average, as compared to single-level N2N.
In the case of label noise, we see that enforcing low KGm (f) on the classification function f. by increasing the regularization parameter values, can have sigmificant impact (Section 6.2). This also leads to a current limitation of our approach. which that the hyperparameters (Ao, A1. have to be manually tuned. Automatic estimation of their optimal values is an avenue for future research. Another limitation of our work is that the growth function term in the empirical approximation of KG (Theorem 2) potentially can render the bounds quite loose. Thus, achieving tighter bounds with KG-based metrics is also a possible extension of this work.
In N2N regularization, we observe that the properties of the smaller networks can dictate the learning of the base network. If we choose smaller networks which are highly rotation invariant in their structure (for e.g.. by using rotation-invariant CNN), we should expect the base network to adopt some of the rotation invariance properties as well. We thus conducted an additional experiment on a custom MNIST [17] dataset, which contains images of digits translated randomly within the image. We added symmetric noise on the labels (p 0.5), and tested our proposed N2N regularization approach with student network which is highly translation invariant (large max-pooling windows). We found that N2N shows larger improvements, reducing test error by 27% compared to other baselines. This demonstrates the possibility of extending this work by analyzing the effect of invariance/equivariane choices in the smaller networks on the generalization behaviour of the larger network, similar to the observations on distillation methods transferring inductive biases in 22
Finally, since our work provides a certain level of robustness against label noise, it supports activities such as crowdsourcing data labelling, which potentially contains significant label noise.
10

---

8 Acknowledgements
This research was supported by the National University of Singapore and by A*STAR, CISCO Systems (USA) Pte. Ltd and National University of Singapore under its Cisco-NUS Accelerated Digital Economy Corporate Laboratory (Award 121001E0002), We would also like to acknowledge the helpful feedback provided by members of the Kent-Ridge Al research group at the National University of Singapore.
References
[1] D.H. Wolpert and W.G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82 -2, 1997.
[2] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, March 2003.
[3] Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the chervnncherv dimension. J. ACM, 36(4):929 965,,965,66 October 1989.
[4] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Localized rademacher complexities. In Jyrki Kivinen and Robert H. Sloan, editors, Computational Learning Theory, pages 44-58. Springer, 2002.
[5] Guillermo Valle-Perez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes because the parameter-function map biased towards simple functions. In International Conference on Learning Representations, 2019.
[6] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107 115, 2021.
[7] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[8] Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Ca- ballero, Linbo Wang, loannis Mitliagkas, and Daniel M. Roy. In search of robust measures of generalization. In NeurlPS, 2020.
[9] Occam's razor. httips://en.iiiiipeiiiaaa
[10] Jürgen Schmidhuber. Discovering neural nets with low kolmogorov complexity and high generalization capability. Neural Networks, 10(5):857-873. 1997.
[11] A.N. Kolmogorov. On tables of random numbers. Theoretical Computer Science, 207(2):387~ 395, 1998.
[12] R.J. Solomonoff. A formal theory of inductive inference, part Information and Control, 7(1):1-22, 1964.
[13] A. Lempel and J. Ziv. On the complexity of finite sequences. IEEE Transactions on Information Theory, 22(1):75-81, 1976.
[14] Kamaludin Dingle, Chico Q. Camargo, and Ard A. Louis. outut- maps strongly biased towards simple outputs. Nature Communications, 9(1):661, Feb 2018.
[15] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge in Neural Network. arXiv e-prints, March 2015.
[16] Li Yuan, Francis EH Tay, Guilin Li, Tao Wang, and Jiashi Feng. Revisiting knowledge distillation via label smoothing regularization. In IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.

---

[17] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. http://yann... lecun com/exdie com/exdb/mnan Boddb/mnis// 2010.
[18] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- (canadian institute for advanced research).
[19] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cif (canadian institute for advanced research).
[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770-778, IEEE Computer Society, 2016.
[21] Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In IEEE International Conference on Computer Vision, 2019.
[22] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 2233-2241, 2017.
[23] Eran Malach and Shai Shalev-Shwartz. Decoupling "when to update" from "how to update". In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[24] Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In ICML, 2018.
[25] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurlPS, pages 8535-8545, 2018
[26] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. In International Conference Learning Representations, 2021.
[27] Samira Abnar, Mostafa Dehghani, and Willem Zuidema. Transferring inductive biases through knowledge distillation, 2020.
12


Reviews:
[{"review_id": "zSvfxEYuSjm", "reviewer": "Reviewer_NwZ7", "summary": "This paper proposes a measure of function complexity that is based on a function itself rather than the function class it belongs to. It uses this complexity measure to establish generalization upper bounds for classifiers. In addition, an empirical method for approximating this measure, and optimizing it, is proposed and evaluated on three small benchmark datasets, exhibiting slightly improved test accuracy over existing baselines. The method is also shown to improve resilience to label noise.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem addressed is significant, as indeed most function class-based generalization bounds are not particularly useful for deep networks. The work seems to be original, and is fairly clear. The theoretical analysis seems reasonable, and the experiments show slight improvements over baselines; however, the amount of improvement is not substantial.\n\nQuestions:\n\nAre the KG-based generalization bounds (empirically approximated using the provided method) actually useful? It would be good to compute the right hand side of Corollary 1.1 (with KG_S replaced by the bound in (9)) on the datasets and compare this to the test error.\n\nDo the same trends in Table 2 hold up when the label noise is not symmetric?\n\nAreas for improvement:\n\nIt would be interesting to compare the empirical KG of different model architectures. For example, do modern CV architectures (e.g., ResNets, DenseNets) have a lower empirical KG than older-style architectures (from simple fully-connected networks to VGG)? In my view, this would substantially strengthen the paper as an additional way to support the usefulness of the metric.\n\nThe authors should discuss and cite \"Fantastic Generalization Measures and Where to Find Them\" (Jiang et al., 2019), which has a more exhaustive list of previously proposed complexity measures. In addition, this paper has strong empirical evaluations of these measures; adding in some of these evaluations as appropriate (and showing that empirical KG outperforms other existing complexity measures on these metrics) would also strengthen the paper.\n\nThe authors should include training time results (e.g., wall-clock time). The proposed N2N method is more expensive than standard training as it involves training multiple networks. In terms of total parameter count, I am not sure whether the N2N approach yields better accuracy than a slightly larger network with total number of parameters approximately equal to the sum of the number of parameters in the base and smaller networks in N2N (especially given the relatively small size of the improvements).\n\nThese evaluations could cause me to raise my score.\n\nMinor comments:\n\nThe related work section 5.2 is somewhat lacking. Although the discussion of reverse knowledge distillation is good, more related work can be discussed. (However, a fair amount of related work is discussed in the introduction.)\n\nThe tables can be tough to read. Increasing the line spacing slightly would be good.\n\nThere are multiple grammar errors (such as extraneous commas); I recommend that the authors carefully copyedit before the final version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors don't seem to have provided a section on negative societal impacts. In the checklist they actually only mention a possible positive societal impact. On the other hand, I fail to see any potential significant negative societal impacts specific to this work. Therefore, I would not consider this to be a mark against the paper.\n\nAs for limitations, the only thing that was mentioned was the fact that the hyperparameters must be manually tuned. The limitations could certainly be expanded upon.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "xYUxjpfA59a", "reviewer": "Reviewer_muBt", "summary": "The paper proposes a novel and theoretically inspired regularization techniques for training deep neural networks. The technique involves regulating the network by regressing the output of the model to a simpler model but the simpler model also regresses towards the output of the base model. The experimental results show that the proposed techniques are effective at reducing the generalization gap and improving performance in presence of label noise.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper first defines Kolmogorov Growth (KG) which is a variation of growth function that in addition considers the description length of the model that can still fit the data. Since KG is a growth function, the generalization gap can easily be bounded via Massart's finite lemma (Thm 1). The paper then proceeds to show that if a smaller model can fit the predictions of the base model, then KG of the larger model can be bounded by the growth function of the smaller model (Thm 2). The proof of theorem 1 is relatively straightforward but I have some questions regarding theorem 2 which I will elaborate below.\n\nRegarding the proposed method, the method seems fairly novel and is well motivated by the proposed theorem. The results show that it offers small improvement on standard classification benchmark and significant improvement in the presence of label noise which is pretty cool.\n\nNow I will discuss the concerns I have regarding the algorithm and experimental results:\n\n- The paper does not describe the motivation behind using multiple levels of distillation of increasingly small capacities. While the theorem shows that you can bound the KG by chaining inequality, it does not explain why this is necessary. Empirically it seems there are some benefits but it is unclear why we need multiple levels. Afterall, bounding with one level (the smallest) will yield tighter bounds. While this might be hard to rigorously justify, I want to see more discussion about intuition and if possible theoretical results.\n-nEmpirically, how does the method compare to reverse distillation?\n- Have you verified the conditions of theorem 2? To me it seems this condition is impossible to verify thus you don’t really know whether you are bounding the KG. In other words, did you compute $\\delta$ in addition to the growth function? For example, I can pick a really small network so the $\\delta$ is large -- Now the KG is dominated by $\\delta$ instead of the growth function.\n- Following the previous point, does the smallest student model fit the label perfectly? In my experience, models with 11k/16k parameters can have a hard time fitting cifar10 / cifar100 perfectly. If they don’t then the theory of KG breaks down.\n- How did you compute the growth function for neural networks for the RHS of eq 9, thm 2? Even small networks should have very high growth functions. As far as I can tell it’s also intractable to compute the exact growth function of an arbitrary neural network. If you relied on approximation then what method did you use?\n- The method has some hyperparameters. Could you discuss strategies for choosing the hyperparameters?\n\n**Questions about proof**:\n\nI have some questions about the details of thm 2’s proof. It is not immediately obvious to me that the conditions described by the first two sentences of the proof are true. Could you add more details to that part of the proof seeing that it is possibly the most important theoretical result of the paper.\n\nI will use $g$ to denote $f_{small}^1$.\n\nFirst we can rewrite $$\\log\\left( \\frac{P_0(f(X)}{P_1(f(X))} \\right) = f_0(X) - f_1(X)$$ and $$ \\epsilon_{max} = \\max_{X \\in \\mathbb{R}^d} || g(X) - f(X) ||^2 = \\max_{X \\in \\mathbb{R}^d} (g_0(X) - f_0(X))^2 + (g_1(X) - f_1(X))^2$$\n\nThe two sentences are essentially saying that $$|f_0(X) - f_1(X)| \\leq \\epsilon_{max} \\Longrightarrow argmax_{k} f_k(X) \\ne  argmax_{k}  g_k(X)$$. Could you elaborate why this is true?\n\n\n**Other comments**:\n\n- Equation 9 missing hat?\n- The related work section of the work seems kind of sparse as generalization for deep learning has attracted a lot of attention recently. I listed a few works at the end of this review that I think you can consider to discuss.\n\nOverall, I think this is a good paper with a nice empirical method motivated by principled theory. If the authors can address my concerns, I would be happy to raise my score to 7.\n\n**Reference**\n\n[1] Uniform convergence may be unable to explain generalization in deep learning. Nagarajan et al.\n\n[2] Towards Learning Convolutions from Scratch. Neyshabur et al.\n\n[3] Fantastic Generalization Measures and Where to Find Them. Jiang et al.\n\n[4] In Search of Robust Measures of Generalization. Dziguite et al.\n\n[5] Transferring Inductive Biases through Knowledge Distillation. Abnar et al.\n\nI am not entirely up-to-date with literature on distillation so I could have missed some there.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "SWngY3YR1Oa", "reviewer": "Reviewer_LCjW", "summary": "This paper addresses the fundamental problem of the generalization ability of deep neural networks and aims to shed light on the theoretical aspects of their generalization ability by introducing a approach based on a new complexity measure called \"Kolmogorov Growth\" (KG). A practical neural network training approach called Network-to-Network (N2N) Regularization is also introduced with the aim of enforcing the low KG condition so that the generalization gap is reduced. Theoretical results are accompanied by relevant experimental evaluations, including a noisy-label case investigation, which helps in validating the proposed KG-based N2N training of neural networks. Overall, the material introduced is seemingly novel, and although tries to address a well-established problem, the results presented are good guidance for research extensions in this direction.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Merits:\n1. Overall, the paper is well-written and theoretically sound. The idea of extending the concept of Growth Function to measure the descriptional complexity of a function space and connecting it with the well-known Rademacher complexity-based Generalization gap theorem from Learning Theory is new, and of interest to the research community.\n2. Although the theoretical results presented themselves are not entirely original and largely inspired from existing gen. gap results, coming up with the KG measure and developing a measurable approximation based on the recursive student classifier approach is still novel.\n3. The experimental evaluation is quite thorough, and attempts to validate most aspects of the theoretical results. The impact of the properties of the smaller networks (e.g. rotational invariance for CNNs) on the larger network is also briefly analyzed, which would be interesting for further research in this direction.\n\nHowever, I do have  the following questions and comments.\n\nQuestions/ Comments:\n1. In Algorithm 1 table, the first line reads ``Training data $\\{X_i, y_i \\}_{i=1}^k$''. What is $k$ here? Do you mean $m$ instead of $k$, where $m$ is the number of training samples?\n2. In Algo 1 table, what is $e_{base}$ and $e_{small}$? How is $e_{base}$ different from $J$? Later in Sec 6.1, it is mentioned that $e_{base}=3$ and $e_{small}=1$, but in Algo 1, $X_i$ and $y_i$ is used throughout, which does not make sense. The overall notation and usage in Algorithm 1 needs much more clarification.\n3. In Sec 6.1, it is said that \"larger training data sizes need smaller regularization parameters\". Could the authors provide any more insight into this observation, especially in the light of the introduced KG?\n4. In Sec 6.1, you say \"2-level N2N regularization\" and then mention $m=2$, but this makes no sense. Do you mean $K=2$, i.e., 2 smaller networks trained. Similarly with single-level N2N?\n5. In Sec 6.2, the observation that a larger $\\lambda_0$ gives a higher test accuracy. Could the authors provide any intuitive explanation for this trend, as to why KG decreases with higher $\\lambda_0$? In Fig. 2, what is $K$, i.e., how many student networks are used to learn the original teacher network?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of this work are briefly discussed in the Conclusion section (Sec. 7). However, a more complete discussion on the limitations and how to overcome them in future research is warranted.\n\nThere is no discussion in the paper on the potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no immediate ethical concerns or issues with this paper. ", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3ZDY52z65za", "reviewer": "Reviewer_aPxa", "summary": "This paper proposes a Kolmogorov Growth (KG), a novel measure of the complexity of a neural network. They derive new generalization bounds using KG and take inspiration from this bound to propose a new way of regularizing neural networks (network-to-network regularization, N2N). Finally, the paper verifies their regularization scheme on three standard image benchmarks.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As reflected in its name, Kolmogorov Growth takes inspiration from Kolmogorov complexity and the growth function. Conceptually, KG measures the size of the simplest class of functions that a given function f belongs to. The main innovation seems to be the min_i operator, which restricts our attention to the simplest function class. KG by itself is obviously not computable, but the paper proposes an interesting way to approximate it.\n\nThe generalization bound in section 3.1 is not particularly surprising. In a sense, the proof for this bound is embedded in the definition of KG itself. Still, I think this is an interesting approach to bounding the generalization error.\n\nNetwork-to-network regularization is motivated by the results in section 3.1, which show that functions that can be approximated well by small networks will have low KG. N2N trains a small student network and a large teacher network to output similar predictions to each other. This makes the student learn from the teacher, while the teacher is regularized by the simpler function of the student. The paper also considers a multi-level version where a sequence of progressively smaller networks are trained with the same loss.\n\nN2N hinges on the implicit assumption that smaller networks have smaller hypothesis spaces and thus learn simpler functions. While this is likely true in a strict sense, many results with neural networks show that small networks have surprisingly strong expressive power. For example, works on knowledge distillation show that minimal networks can achieve accuracy close to that of a large teacher, and [1] shows that a rather small network can fit random labels. I think this implicit assumption and its limitations should be discussed a bit more in the paper.\n\nExperiments show that N2N acts as an effective regularizer and that N2N regularization indeed reduces the KG bound. It would have been interesting to additionally include the generalization gap in Figure 2 so that the KG bound can be compared with it.\n\nThere may be a more direct correspondence between Kolmogorov complexity and KG. In KG’s definition (section 3), you essentially construct a short two-part program for describing the function f where you first describe the function class F and then specify f within F. I wouldn’t be surprised if the two concepts can be shown to have a stronger relation than KC simply acting as “indirect motivation” for KG (line 140). I think this is an exciting direction for future work.\n\n[1] Understanding deep learning requires rethinking generalization, Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduced a novel measure of the complexity of a class of functions. Reviewers agreed that the proposal was novel, and theoretically sound. Reviewers also felt that experiments exploring regularizing using (a proxy for) Kolmogorov Growth were convincing. One reviewer increased their score, and another increased their confidence in their (accept) score during discussion, both of which I take as very positive signs.

Reviewers had specific actionable feedback in their reviews, which the authors should incorporate into their manuscript before the camera ready.
Decision: Accept (Poster)