Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Summary 

The paper proposes a new notion of complexity measure called geometric complexity (GC) . The paper discusses how GC relates to the familiar concepts in deep learning literature and made extensive links to existing regularizer methods. I enjoyed a lot reading this paper, and found it helpful to understand the connections among all the mentioned regularizers. 



strengths_and_weaknesses: Major strength 
1. The paper is well organized and well written. 
2. The authors made extensive analysis to link GC with typical deep learning architectures, demonstrating the connections between existing training regularizers and GC. These links explicitly demonstrate that GC , to some extent,  unify the regularizers in the sense that penalizing these regularizers would simultaneously penalize GC.
3. In comparison to other complexity measures, GC is more computationally tractable.   
The paper empirically evaluates the connection between the generalization property and GC: after the critical region, increasing model size would necessarily decrease GC, showing the usefulness of GC in estimating the generalization error, showing potential benefits of using GC to improve generalization.  

Questions. 
I am not expert on this complexity measurement topic, but I have some basic understanding of complexity measures. If you don’t mind me asking, what is the advantage of GC over Rademacher complexity? Is it because GC is more computationally convenient?  Is it possible to compare these two types of complexity in some sense empirically or theoretically? 

questions: Please see the above comments for questions. 
limitations: The author has addressed the limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Regularization is key when it comes to model selection; if we seek models that generalize well, choosing the less complex one tends to be a good heuristic in classical machine learning. In deep learning, however, it is not clear what is a good metric to measure the "complexity" of a given model, as the classic ones tend to be unreliable (e.g. parameter counting and the double-descent effect), and/or intractable (e.g. VC dimension). 

This work presents a new complexity metric, the Geometric Complexity (GC). Throughout the paper, the authors present their metric in simple scenarios (ReLU and linear networks), relate it with other metrics (Lipschitz smoothness and Dirichlet energy), and empirically demonstrate that many common regularization techniques in DL minimize the GC under the hood. Finally, the authors reproduce the original double descent experiments, and show that GC recovers the traditional U-shaped curve.
strengths_and_weaknesses: **Strengths (S)**
1. The main contribution of the paper can be fairly impactful. GC is computable, and it seems to be well correlated with the test error. More importantly, previous work does not need to be thrown away. The authors related GC with other metrics, and showed that effectiveness regularization techniques greatly affect the GC. I expect this work to be impactful.
2. The paper has a strong empirical flavour, which I find necessary for a paper on this topic. Moreover, the range of methods tested is broad and is well-structured in different sections (initialization, implicit regularization, and explicit regularization).
3. The theoretical results and claims look sound to me. Specially, the connection of GC with Dirichlet energy is really appealing. However, I have only fully read the main paper and the proofs until A3.
4. The paper is well written and easy to follow.

**Weaknesses (W)**
1. While I agree with the authors on removing extra sources of noise for the main experiments (e.g. not using momentum or lr schedulers), there should a section/experiment where all the DL machinery is put together, and compare the GC of those new models with the ones already on the paper. Otherwise, the performance gap is too big compared to other works. For example, test accuracy on CIFAR10 is around 75% in the paper (Figure 4), while using the same model **other works achieve an accuracy of 95.55%** (according to [papers with code](https://paperswithcode.com/sota/image-classification-on-cifar-10?tag_filter=3)).
2. I feel the paper glosses over connections with the proposed metric. For example, line 186 says that Jacobian regularization basically _minimizes the proposed metric (GC) explicitly_ on the loss, but the topic is covered with 4 lines. This is _really_ important, Jacobian regularization is not just another regularization method to mention. Similarly, section 7 says that GC is similar to Kolmogorov complexity and MDL, but these similarities are not explained anywhere.
3. I miss some motivation and intuition for the proposed metric, Def. 2.1 feels arbitrary until you read the end of section 2. I think introducing the metric as a modification of Dirichlet energy minimization would feel more natural.

_Note:_ While I can understand and follow all the paper, I am not that well-versed in the topic, and therefore I cannot fully assess the novelty of the proposed metric as I could miss well-known literature. To me, the metric seems novel for this purpose, but strong connections were vaguely mentioned, which I find concerning.
questions: **Questions (Q)**
1. What is the training error in section 6? I assume that it is zero, but otherwise I think it is important to show the training error as well. Given that the U-shaped curve explains overfitting, I don't find useful to recover the curve with GC if that does not explain overfitting as in traditional ML. 

**Nitpicks (N)**
1. The quantity $h/B$ in line 246 has been studied before, maybe you want to add a few lines commenting on it. See, e.g., [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://arxiv.org/pdf/1706.02677.pdf), [Don't Decay the Learning Rate, Increase the Batch Size](https://arxiv.org/pdf/1711.00489.pdf), or [An Empirical Model of Large-Batch Training](https://arxiv.org/pdf/1812.06162.pdf).
2. The font of the figures should be increased.
3. You should point to specific parts of the SM in the main text, not just the SM in general.

limitations: I think the authors correctly addressed the limitations of the method.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors introduce the Geometric Complexity (GC), a novel measure/predictor of neural network performance, based on the evaluation of a discrete Dirichlet energy on the logits in the output of the network. Given that the Dirichlet energy is a measure of how variable a function is, the Geometric Complexity is closely linked to many more common ML notions e.g. regularization and smoothness.
The authors argue that keeping a low GC, while training the NN model, allows a test performance improvement. This conclusion is drawn from the observation that a variety of well-known Deep Learning heuristics, including initialization, regularization and fine-tuning of the parameters of the learning algorithm seem to produce models with low GC that generalize well.
Finally, the authors show that GC can be used to trace the double-descent behavior, in the transition to the over-parametrized regime. 

AFTER REBUTTAL
The authors have addressed most of the concerns raised in the review process and clarified and expanded upon their work. 
strengths_and_weaknesses: Computability is an essential property for any performance metric that is proposed to predict NN performance. The authors argue that the Dirichlet energy, while being conceptually close to other smoothness assessment metrics, is much simpler to estimate, as it is simply defined as an expectation over the training set. Moreover, the theoretical connection with harmonic theory allows for a very simple intuition of the concept of smooth interpolators and might be useful for designing better (more explicit) training algorithms.
What seems to be the main weakness of this work is that the assumption of the authors, of the fundamental importance of GC minimization in training DNNs, is only supported through a limited set of positive observations. The authors go through a range of well-known and functioning deep learning heuristics and show the relationship/correlation with a GC decrease. However, it remains unclear whether this decrease is a sufficient/necessary condition for achieving better performance. What would complete this study is a set of experiments where the GC is explicitly controlled and competitive performance is reached, either with an exact GC minimization (probably too computationally expensive), or with some novel regularization technique that aims at GC minimization.
Another weak point of this work is in the presented experiments, involving relatively small models and semi-obsolete datasets (MNIST, CIFAR).    
questions: - Figure 3: The curve related to L2 norm does not seem to show the expected behavior, can the authors comment on it, or provide a plot where more values are shown in the range of regularization intensity where the GC drops?
- The accuracies shown in figure 4 seem to be way below the reference performance of a Resnet 18 on CIFAR10. The effect shown in the plot seems very clean, with lower GC and better generalization, but does this apply also close to state-of-the-art performance?
- Since GC can be explicitly evaluated and the authors argue that many heuristics implicitly minimize it, I think the authors should try a set of experiments where this minimization is done explicitly (even though the required computations may be very expensive). Otherwise, the correlation vs causation question remains open. Is there a reason why such a test was not performed, at least in a small network setting?
- Is there any other way of using the Dirichlet energy and harmonic theory to guide the learning process?
- Since the GC is data-dependent, how can it be used in the context of transfer learning and in OOD generalization settings? Could it still provide some useful insight, and would the smoothness vs generalization relationship still hold, even though the network was not trained on that data?
- Given two different DNN architectures, can their GC still be informative on which will perform best? Can GC be used for model selection? 
limitations: I think that the main unaddressed limitation of this work is that the authors do not spend enough time trying to disprove their claim. This could only be achieved by explicitly controlling the GC and finding out whether its minimization is a sufficient drive for effective training.
review_title: null

Meta-review: metareview: All reviewers and the AC find this paper makes valuable contributions to the deep learning theory community. Thus, the AC recommends acceptance.
confidence: Certain
Decision: Accept