Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Merits:
1. 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.
2. 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.
3. 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.

However, I do have  the following questions and comments.

Questions/ Comments:
1. 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?
2. 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.
3. 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?
4. 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?
5. 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?
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.

There is no discussion in the paper on the potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

The 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.

Network-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.

N2N 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.

Experiments 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.

There 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.

[1] Understanding deep learning requires rethinking generalization, Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals

limitations_and_societal_impact: Please refer to the main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Questions:

Are 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.

Do the same trends in Table 2 hold up when the label noise is not symmetric?

Areas for improvement:

It 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.

The 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.

The 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).

These evaluations could cause me to raise my score.

Minor comments:

The 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.)

The tables can be tough to read. Increasing the line spacing slightly would be good.

There are multiple grammar errors (such as extraneous commas); I recommend that the authors carefully copyedit before the final version.
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.

As 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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Regarding 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.

Now I will discuss the concerns I have regarding the algorithm and experimental results:

- 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.
-nEmpirically, how does the method compare to reverse distillation?
- 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.
- 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.
- 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?
- The method has some hyperparameters. Could you discuss strategies for choosing the hyperparameters?

**Questions about proof**:

I 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.

I will use $g$ to denote $f_{small}^1$.

First 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$$

The 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?


**Other comments**:

- Equation 9 missing hat?
- 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.

Overall, 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.

**Reference**

[1] Uniform convergence may be unable to explain generalization in deep learning. Nagarajan et al.

[2] Towards Learning Convolutions from Scratch. Neyshabur et al.

[3] Fantastic Generalization Measures and Where to Find Them. Jiang et al.

[4] In Search of Robust Measures of Generalization. Dziguite et al.

[5] Transferring Inductive Biases through Knowledge Distillation. Abnar et al.

I am not entirely up-to-date with literature on distillation so I could have missed some there.

limitations_and_societal_impact: None
review_title: null

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)