summaries: 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.

summaries: 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.

summaries: 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.

summaries: 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.

abstractText: 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.

authors:
D.H. Wolpert
W.G. Macready

title: No free lunch theorems for optimization

venue: IEEE Transactions on Evolutionary Computation,

authors:
Peter L. Bartlett
Shahar Mendelson

title: Rademacher and gaussian complexities: Risk bounds and structural results

venue: J. Mach. Learn. Res.,

authors:
Anselm Blumer
A. Ehrenfeucht
David Haussler
Manfred K. Warmuth

title: Learnability and the vapnik-chervonenkis dimension

venue: J. ACM,

authors:
Peter L. Bartlett
Olivier Bousquet
Shahar Mendelson

title: Localized rademacher complexities

venue: Computational Learning Theory,

authors:
Guillermo Valle-Perez
Chico Q. Camargo
Ard A. Louis

title: Deep learning generalizes because the parameter-function map is biased towards simple functions

venue: In International Conference on Learning Representations,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning (still) requires rethinking generalization

venue: Communications of the ACM,

authors:
Yiding Jiang
Behnam Neyshabur
Hossein Mobahi
Dilip Krishnan
Samy Bengio

title: Fantastic generalization measures and where to find them

venue: In 8th International Conference on Learning Representations,

authors:
Gintare Karolina Dziugaite
Alexandre Drouin
Brady Neal
Nitarshan Rajkumar
Ethan Caballero
Linbo Wang
Ioannis Mitliagkas
Daniel M. Roy

title: In search of robust measures of generalization

venue: NeurIPS,

title: Discovering neural nets with low kolmogorov complexity and high generalization capability

venue: Neural Networks,

title: On tables of random numbers

venue: Theoretical Computer Science,

title: A formal theory of inductive inference

venue: i. Information and Control,

authors:
A. Lempel
J. Ziv

title: On the complexity of finite sequences

venue: IEEE Transactions on Information Theory,

authors:
Kamaludin Dingle
Chico Q. Camargo
Ard A. Louis

title: Input–output maps are strongly biased towards simple outputs

venue: Nature Communications,

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the Knowledge in a Neural Network

authors:
Li Yuan
Francis EH Tay
Guilin Li
Tao Wang
Jiashi Feng

title: Revisiting knowledge distillation via label smoothing regularization

venue: In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Yann LeCun
Corinna Cortes

title: MNIST handwritten digit database

venue: http://yann.lecun. com/exdb/mnist/,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Yisen Wang
Xingjun Ma
Zaiyi Chen
Yuan Luo
Jinfeng Yi
James Bailey

title: Symmetric cross entropy for robust learning with noisy labels

venue: In IEEE International Conference on Computer Vision,

authors:
Giorgio Patrini
Alessandro Rozza
Aditya Krishna Menon
Richard Nock
Lizhen Qu

title: Making deep neural networks robust to label noise: A loss correction approach

venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Eran Malach
Shai Shalev-Shwartz

title: Decoupling "when to update" from "how to update

venue: Advances in Neural Information Processing Systems,

authors:
Lu Jiang
Zhengyuan Zhou
Thomas Leung
Li-Jia Li
Li Fei-Fei

title: Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels

authors:
Bo Han
Quanming Yao
Xingrui Yu
Gang Niu
Miao Xu
Weihua Hu
Ivor Tsang
Masashi Sugiyama

title: Co-teaching: Robust training of deep neural networks with extremely noisy labels

venue: In NeurIPS,

authors:
Daniel Hsu
Ziwei Ji
Matus Telgarsky
Lan Wang

title: Generalization bounds via distillation

authors:
Samira Abnar
Mostafa Dehghani
Willem Zuidema

title: Transferring inductive biases through knowledge distillation, 2020

heading: 1 Introduction and Motivation

text:
On the surface, the problem of learning to generalize well over unseen data seems an impossible task. Classification is inherently a problem in function estimation, and the finite information that the training data samples impart seems hardly enough to be able to 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 (NeurIPS 2021).
structuredness in the ground truth, learning is not guaranteed, as was observed in the no free lunch theorem [1]. As shown in 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 classification problem, the other important parameter that decides the ability of a classifier to generalize, is 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, 3, 4] of the classifier’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, 8], 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-the-art 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 in 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 a 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 an example of the Occam’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 a 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 a deep neural network. The function that results from this weight configuration is essentially the constant function f(X) = 0. This observation points to the fact that even within a function space of a deep CNN, not all functions are equally complex, as some of them can still be approximated by shallower networks.
To that end, a 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 [10], where metrics from algorithmic complexity were developed to bias the learning process towards simpler functions. In this regard, measures of descriptional complexity [5] 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 [11] or Solomonoff Probability [12] 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 [10]. 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.
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.

heading: 2 Contributions

text:
This paper makes the following contributions.
1. First, we undertake a brief theoretical analysis for exploring the relevance of descriptional complexity 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 toKG(f). 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 network-to-network (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, we see 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 as training progresses. However, this trend completely reverses when the training data labels are noise corrupted and N2N regularization is able to stem the undesirable increase of KG during training.

heading: 3 Kolmogorov Growth: Relevance to Generalization

text:
Assume that our training data consists of m d-dimensional i.i.d samples and their labels S = [(z1, y1), (z2, y2), .., (zm, ym)] drawn from some distribution Pm.
We propose two growth measures for a single function f , namely Kolmogorov Growth KGm(f) and empirical Kolmogorov Growth K̂GS(f). Note that, when appropriate, we may drop the subscript m and refer to KGm(f) as KG(f). These measures are primarily motivated from the well-known growth function in statistics. The growth function Πm(F) is defined as
Πm(F) = max z∈Rd |{(f(z1), f(z2), ..., f(zm)) : f ∈ F}| (1)
Note that the growth function is defined for a space of functions and captures the maximum number of label assignments a function space F can generate on any m points in Rd. To define Kolmogorov Growth measures for a single function f , we first need to generate a function space from f , based on a description Df of f . This is done via noting all the parameters involved in the description Df (other than the co-ordinates in Rd), and then assigning all possible values to those parameters to generate a space of functions F(Df ) from the description Df . Next, we note that for a function f , we consider multiple descriptions (D1f , D 2 f , D 3 f , ...), all of which faithfully generate the output of f over all points in Rd, with the additional constraint that each F(Dif ) 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:
KGm(f) = min i
log Πm ( F(Dif ) ) m . (2)
Note that KGm(f) requires the knowledge of distribution Pm of the training samples. For an instance of the datapoints in S, we define the empirical Kolmogorov Growth via the empirical growth function Π̂S(F), which only computes the number of label assignments a function space can generate over the given m training data samples in S. Thus, Π̂S(F) = |{(f(z1), f(z2), ..., f(zm)) : f ∈ F}|. This leads to the following definition of the empirical Kolmogorov Growth of a function f :
K̂GS(f) = min i
log Π̂S ( F(Dif ) ) m . (3)
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 , Kolmogorov 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 us to directly comment on the error bounds for the function f (see Section 3.1). We believe that a possible direction of future work would be to do a 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.e., f outputs random labels at every point X ∈ Rd), one expects KG(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).

heading: 3.1 Bounding Generalization Error using Kolmogorov Growth

text:
Here we present error bounds that depend on KG(f), 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 êrrS(f), and the overall generalization error with respect to the distribution P , denoted by errP (f). We define them as follows:
êrrS(f) = m∑ i=1 (1− f(zi)yi) 2m
(4)
errP (f) = E z,y∼P
[ (1− f(z)y)
2
] . (5)
These definitions hold for any function f . Note that the error functions depend both on the function f and the distribution P .
With this, we have the following results. The proofs of all results are provided in the supplementary material.
Theorem 1 For 0 < δ < 1, with probability p ≥ 1− δ over the draw of S, we have
errP (f) ≤êrrS(f) + √ 2KGm(f) +
√ log (1/δ)
2m . (6)
The following corollary of the above theorem gives bounds that depend on empirical Kolmogorov growth K̂GS(f).
Corollary 1.1 For 0 < δ < 1, with probability p ≥ 1− δ over the draw of S, we have errP (f) ≤êrrS(f) + √ 2K̂GS(f) + 4 √ 2 log (4/δ)
m . (7)
Remark: Theorem 1 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 approximate the empirical Kolmorogov growth K̂GS(f).

heading: 4 Teacher-Student Approximation Bounds for Kolmogorov Growth

text:
The fundamental idea for approximating empirical Kolmogorov growth of a function f which belongs to the function space F is to use a student classifier with a function space F1small (with a much smaller parametric count and complexity) to approximate the given function f (the teacher). We apply this idea recursively. That is, if the function f1small ∈ Fsmall approximates f best, we recursively estimate the empirical Kolmogorov growth of f1small by approximating it via another classifier with a smaller function space F2small (thus, Πm(F 2 small) < Πm(F 1 small)), and so on. We use this recursive way to then obtain a final estimate for K̂GS(f). We conjecture that, like Kolmogorov complexity itself, the true K̂GS(f) is uncomputable, so the estimate that results from this recursive approximation process is essentially an upper bound to the true K̂GS(f). The following theorem establishes an upper bound to empirical KG approximation from a single smaller student classifier.
Theorem 2 Given the function f ∈ F : Rd −→ R2 which outputs class logits for binary classification. We construct a function space F1small such that Πm(F 1 small) < Πm(F) and ∀g ∈ F 1 small, there exists a description Dg such that Π̂S (F(Dg)) ≤ Π̂S(F1small). We approximate f via another function f1small ∈ F 1 small : Rd −→ R2 and let max be such that
2max/2 = max X∈Rd ‖f1small(X)− f(X)‖2. (8)
Denote the output probabilities generated from the corresponding logit outputs of f(X) using the softmax operator (temperature T = 1), as P0(f(X)) (label 1 output) and P1(f(X)) (label 2 output). Let 0 ≤ δ ≤ 1 be such that
Pr (∣∣∣∣log(P0(f(X))P1(f(X) )∣∣∣∣ ≤ max) ≤ δ, (9)
when X is drawn from S. Then we have,
K̂GS(f) ≤ δ log 2 + log Π̂S
( F1small ) m , (10)
where m is the number of samples in S.
Remark: Theorem 2 demonstrates a way to bound the true empirical Kolmogorov growth of the function f , using a single student classifier function f1small ∈ F 1 small. Note that unlike in Theorem 1, there are no direct constraints on the expressivity of F1small, but rather a joint constraint on F 1 small and δ combined. If F1small cannot fit all m points sampled from Pm, then the approximation error in δ will likely be higher, which will add to the estimate of K̂GS(f). The proof of Theorem 2 and its extension to the recursive approximation case are given in the supplementary material.

heading: 5 Network-to-Network (N2N) Regularization

text: We denote the base network to be trained as N base and the function modelled by the network weights wbase asN base(wbase, X), whereX ∈ Rd is the input. Here, N base(wbase, X) represents the output logits for the networkN base when presented with the inputX . Thus, we haveN base(wbase, X) ∈ Rc, where c is the number of classes. For what follows, let us denote the available training data and their labels by S = {Xi, yi}mi=1. The approach that follows is directly motivated from the result in Theorem 2. The main objective is to ensure that the KG of the network stays low during learning, using the teacher-student approximation error in Theorem 2. This is primarily achieved by ensuring that during training, the base network function N base(wbase, 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-network (N2N) regularization approach.

heading: 5.1 Multi-Level N2N: Details

text:
In multi-level N2N regularization, we have multiple smaller networks nsmall1 , n small 2 , ..., n small K of decreasing complexity such that Πm(F1small) > Πm(F 2 small) > · · · > Πm(F K small).
Algorithm 1 N2N Regularization (Multi-Level) Input: Training data {Xi, yi}mi=1, base network N base and its weights wbase, K networks nsmall1 , n small 2 , ..., n small K , with weights w1, w2, ..., wK (s.t. |nsmall1 | > |nsmall2 | > ..|nsmallK | in size), Number of epochs J , Hyperparameters λ0, λ1, λ2, ..., λK−1, α0, .., αK , ebase, esmall. 1: for j = 1, 2, . . . , J do 2: for iter = 1, 2, . . . , ebase do 3: L1 = ∑m i=1(LCE(N
base(Xi), yi) + λ0‖N base(Xi)− nsmall1 (Xi)‖2) 4: Weight update: wbase ←− wbase − α0m ∂L1 ∂wbase 5: for k = 1, 2, . . . ,K do 6: for iter = 1, 2, . . . , esmall do 7: if k = 1 then 8: Lk = ∑ i‖N base(Xi)− nsmall1 (Xi)‖2 + λ1‖nsmall2 (Xi)− nsmall1 (Xi)‖2
9: else if k = K then 10: Lk = ∑ i‖nsmallk (Xi)− nsmallk−1 (Xi)‖2 11: else 12: Lk = ∑ i‖nsmallk (Xi)− nsmallk−1 (Xi)‖2 + λk‖nsmallk (Xi)− nsmallk+1 (Xi)‖2 13: Weight update: wk ←− wk − αkm ∂Lk ∂w1
The corresponding functions resulting from the network weights w1, w2, .., wK are denoted as nsmall1 (w1, X), n small 2 (w2, X), ..., n small K (wK , X). Next, we outline the loss functions for all networks. For the larger to-be-trained base networkN base, the loss objective is to minimize cross-entropy loss on S while being close to nsmall1 (w1, X) for some choice of weights w1 (L1 in Algorithm 1). For the smaller network nsmall1 , the objective is two-fold: find the weight configuration w1 that approximates the larger network function N base, while also being close to nsmall2 (w2, X) for some choice of w2 (L2 in Algorithm 1). Thus, we force the smaller network nsmall1 to be close to the base network and an even lower-complexity network nsmall2 at the same time. Similarly we can define L3,L3, ..,LK−1, except for LK which applies to the smallest network nsmallK . The loss objective for nsmallK is to just keep n small K (wK , X) close to n small K−1 (wK−1, X). Finally, we optimize the loss functions in an alternating manner in the order of L1,L2, ..,LK . Details are given in Algorithm 1. The choice of mean-squared error based loss functions here directly follows from the result in Theorem 2. Note that Algorithm 1 updates with the entire batch of training data points at each iteration, and can be extended to the case of minibatch stochastic gradient descent (SGD).

heading: 5.2 Other Relevant Approaches in Literature

text: To the best of our knowledge, our proposed approach is 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 to 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 a more 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 a multi-level approach for a recursive way of regularizing multiple networks of different levels of complexity.

heading: 6 Experiments

text: We test N2N on three datasets: MNIST [17], CIFAR-10 [18] and CIFAR-100 [19]. We also demonstrate that N2N regularization improves performance in the presence of label noise. Lastly, we analyse Kolmogorov growth of networks during training. Experiments were either carried out on an RTX 2060 GPU or a Tesla V100 or A100 GPU. As mentioned in Algorithm 1, an epoch refers to a total of ebase 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://github.com/rghosh92/N2N.

heading: 6.1 Supervised Classification: MNIST, CIFAR-10, CIFAR-100

text:
K̂GS(f) of the trained networks.
The primary objective of the experiments presented here is 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 combine N2N with L2-norm regularization. All networks were trained for a total of 200 iterations,
and in each case results reported are averaged over five networks. For all experiments we set ebase = 3, esmall = 1 in Algorithm 1. The values of the regularization parameters (λ0, λ1) are 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.
Results are shown in Table 1, 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, we 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 1), outperforms single-level N2N (N2N-1, m = 1 in Algorithm 1), with the exception of CIFAR-10 with the full training dataset. For the CIFAR-10 and CIFAR-100 datasets, we used the benchmark ResNet architectures ResNet44 and ResNet-50 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 2 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, CIFAR-100). Furthermore, as Table 2 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 1, as high KG functions are expected to have a larger generalization gap.

heading: 6.2 Learning with Noisy Labels

text:
As our proposed regularization approach constrains the network function to be simpler by minimizing an approximation of Kolmogorov Growth, it naturally applies to the case of noisy training labels.
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, a fact that we 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 a certain extent. We test whether enforcing a simpler function (large λ0, ...λm) 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 p = 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 p = 0.5 and p = 0.2 on MNIST, CIFAR-10 and CIFAR-100 in Table 3. For F-correction [22], Decoupling [23], MentorNet [24] and 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 a 48k-2k training-validation 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 λ0 and λ1 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 λ0 in Figure 1. We find that for MNIST, large λ0 helps achieve significantly higher test accuracy, whereas for CIFAR-10 and CIFAR-100 accuracy peaks around λ0 = 0.6 and λ0 = 0.5 respectively. Note that accuracies may differ from Table 3 because of different training configurations used.

heading: 6.3 Comparing Kolmogorov Growth Trajectories during Training

text: 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 K̂G(f) of the function f 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 error term δ in Theorem 2, as F1small is fixed to a single-layer CNN (of a fixed configuration) for all results in Fig. 2. Π̂S ( F1small ) was estimated using a VC dimension based approximation shown in [7]. Results are shown in Figure 2. We find that in the case of no training label noise, the KG of networks typically have high initial values, steeply reducing within a 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 of no label noise. This can be partly explained by the fact that as training progresses, the network slowly adapts its decision boundary to fit the erroneous labelling, eventually resulting in a decision boundary of 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.

heading: 7 Discussion and Reflections

text:
This results in this paper further the recent work by [5], where it 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 f 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 [5] however, put a new perspective on the results in [6]: any random choice of network weights on smaller networks is likely to yield a 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 a 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 λ0 increases, more emphasis is put on lowering KG, which improves generalization and yields better test accuracy. However, this happens up to a threshold (see Figure 1) and test accuracy decreases as λ0 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 on minimizing KG.
Our theoretical results in Section 3.1 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 1 outlines an Occam’s razor like principle for generalization. Theorem 1 implies that for all functions which have zero training error, the function with the smallest KGm(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-level 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 a significant impact (Section 6.2). This also leads to a current limitation of our approach, which is that the hyperparameters (λ0, λ1, ..) 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 a 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 a 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/equivariance choices in the smaller networks on the generalization behaviour of the larger network, similar to the observations on distillation methods transferring inductive biases in [27].
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.

heading: 8 Acknowledgements

text: 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 I21001E0002). We would also like to acknowledge the helpful feedback provided by members of the Kent-Ridge AI research group at the National University of Singapore.

title: Network-to-Network Regularization: Enforcing Occam’s Razor to Improve Generalization