Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Note: this is a light review

The paper makes the hypothesis that the complexity of the function learned by DNNs depends on the convergence rate of its parameters (with special focus on the bias of the 1st layer) and other factors (variance of the bias, and distance from initialization).


main_review: Clarity: The paper is not clearly written. For instance, the meaning of the term "steadily" is not clear in the abstract (it is defined formally later in the paper). The statements of theoretical results are not explained in text to provide an intuitive understanding.

Major problems:

Some of the claims made by the authors are not concrete (but are rather casual). For instance, the first line of introduction says "Though neural networks (NNs) trained on relatively small datasets can generalize well, often significant trial and error is needed to select an architecture that does not overfit.". This statement has 2 problems:

1. typically using a ResNet architecture works out-of-the-box for image datasets and yields SOTA performance on classification tasks.
2. the claim that a proper selection of architecture can result in a model avoiding overfitting all together in practice is simply not true.

There is a mismatch between the claims made in the abstract/introduction section and the experimental results. The claims are mainly talking about the connection between behavior of the training process and the complexity of the DNN function learned (line 21). This suggests that the authors are considering the case where given a fixed dataset, if we change optimization hyper-parameters (or other factors), it will result in a change in the behavior of the training process which should be indicative of the complexity of the learned DNN function. However, the experiments use datasets with different levels of corruption or target functions with varying complexity (as measured by their frequency components). These experiments do not shed light on whether the behavior of training process can be indicative of the learned hypothesis (because to study that, one would have to fix the target function). Another problem is that these experimental findings are not novel. It has been shown in [1] that the complexity of the target function impacts the speed of convergence of DNN training. The additional plot provided by authors involving the converge rate of the bias of the first layer of the DNN is not surprising because of this simple reasoning: if the training/test loss has not converged, the parameters of the DNN must not have converged also.

Further, I find the choice of making the bias of the 1st hidden layer of a DNN the main object of analysis (viz complexity of the learned function) debatable. Any useful information/structure about the data is captured by the DNN weights, not biases. Biases merely act as threshold values (when using ReLU activations).

[1] Arpit, D., Jastrzębski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., ... & Lacoste-Julien, S. (2017, July). A closer look at memorization in deep networks. In International Conference on Machine Learning (pp. 233-242). PMLR.
limitations_and_societal_impact: please see the main review
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates how certain properties of the training trajectory such as its length relate to the complexity of functions learned by ReLU networks. Complexity is quantified by way of the network's distribution of the Lipschitz constants on the linear regions of its input space. The key finding is that networks that fit the training data with a smaller average Lipschitz constant exhibit a shorter trajectory and their parameters vary less near training convergence. For training with dropout, the authors also give a data-dependent generalization bound that features a polylogarithmic dependence on the number of parameters under certain assumptions.

main_review: I found the paper reasonably well-written and the results presented coherently. The techniques used in the paper in relation to bounding the Lipschitz constant by exploiting certain properties of ReLU networks appear novel.

The authors quantify neural network complexity by way of the Lipschitz continuity of the learned function on the linear regions of the input space. For ReLU networks, locally the Lipschitz constant is given by the norm of the gradient at any point within that region. The authors build on the observation that if the learned function has a large Lipschitz constant near an input datum, then SGD updates the bias of the first layer more quickly. Thus, for linear regions close to the training data, one can infer the average Lipschitz constant of the learned function by observing how fast the bias is updated. The authors show that the length of the optimization trajectory (with high probability over the SGD sampling) grows linearly with the average Lipschitz constant of the network. 

Simple experiments studying the training behavior on two tasks, namely, fitting sinusoids of increasing frequency and classifying CIFAR-10 images with increasing label corruption lend support to the theory: given two networks that fit the training data equally well, the one implementing a higher complexity function exhibits a longer trajectory with the weights having bigger variance near training convergence. The authors also show how the analysis can be extended to regions of the input space that are outside the training data. 


The proof for the upper bound in Theorem 1 assumes that the smallest singular value $\sigma_n(W_1^{(t)})$ is positive. This condition is missing in the statement of Theorem 1.

Minor:

l.123 (Sentence): that yield same activation pattern --> that yield the same activation pattern

l.229 (Sentence) "Furthermore, denote by ... used in the last layer." -- add, respectively: Let $S_T$, $\varphi_T$, $\mu_T$ denote, respectively, ...





limitations_and_societal_impact: Addressed by the authors. I do not foresee any potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper attempts to understand the complexity of the function learned by a model from the training behavior of its weights. The authors consider neural networks with ReLU activation. The 3 main results are:

(a) The length and variance of the trajectory of the bias of the first layer can be bounded by a function of the Lipschitz constant close to training data.

(b) The Lipschitz constant (for steady learners) can also be given for regions not present in the training data, provided the activation pattern in the region is covered by the activation patterns of the training data.

(c) The authors give a data-dependent and training-dependent generalization bound for steady learners with Dropout. The proof involves bounding the global Lipschitz constant, which requires a simplified assumption that all the neurons have non-zero activity without Dropout in the training set.

The authors corroborate their findings with an experimental study.
main_review: The paper tries to understand the relationship between the SGD trajectory and the complexity of the learned function. The authors come up with a novel strategy to look at the trajectory of the bias of the first layer. The novelty of the technique comes from cleverly utilizing the fact that a ReLU network divides the input space into multiple linear regions and then connecting the bias to the Lipschitz constant of the linear classifier in each region. A couple of previous works try to connect the trajectory of weights of the model to the complexity of the function learned. However, most of the analyses were in the NTK or the mean-field regime. The strength of this work is that it assumes nothing on the initialization of the neural network. 

However, I have a couple of questions and few suggestions:

(1) In theorem 1, the assumption to keep the upper bound finite is $\sigma_n (W_1^{(t)}) > 0$. I think the authors should explicitly mention it in the theorem statement. What happens when the data comes from a low dimensional space $k < n$, and the input layer weights have to fit that subspace? Can the bounds then be changed to $\sigma_k(W_1^{(t)})$ in some trivial way? 

(2) What do the authors mean by the statement "a larger complexity NN will need to fit the training data more closely to achieve the same variance as that of a lower complexity NN" (line 189)? What parameters in Corollary 2 do I need to compare to get this statement (e.g. $\epsilon^{\mathrm{var}}_{ f^{(t)} }$, and the Lipschitz constant)?

 (3) I believe you need more conditions to claim Corollary 1. I think the result that you can claim from theorem 1 and definition 1 is that given a set of iteration indices $T \ge \tau$ for a $(\tau, \varphi)$-steady learner, with $|T|$ large enough, $\frac{1}{T} \sum_{t \in T} \lambda^{avg}_{f^{(t)}} (X) \le \beta \varphi$.  How is this related to the Lipschitz constant of every training data point after $t \ge \tau$, provided you don't assume how the Lipschitz constant changes for a steady learner? 

(4) Can the authors explain how Dropout helps in Theorem 3? I guess, Claim 1 in the appendix is the main underlying tool. However, the proof contains multiple notational issues (e.g. what is the meaning of $\sum_{i=1}^{k} s_{ t, l }(x)$?). But I can guess the strategy is that since Dropout drops neurons with a probability of $1/2$,  and the assumption that all the neurons have some activity in the training set, one can show that the activation patterns of the training set (along with Dropout masks) can form a basis of the activation pattern of the entire region with some non-zero probability. That will now help to get a bound on the global Lipschitz constant from Theorem 2. 

It will be great if the authors can mention 2-3 lines on how dropout helps in the main paper.

(5) In the experiments on regression of a sinusoidal function, the authors have set the first layer of the MLP to Identity. How do the experimental observations change if they don't fix it to Identity? 

(6) It will be interesting to see if the experimental observations stay the same for trajectories of biases of the other layers. 

**Notation issues

$\lambda_f^{\mathrm{steady}}$ has never been defined in the main paper.

I enjoyed reading the paper since it makes a novel attempt at understanding the connection between the trajectory of neural networks and the complexity of the function learned. The proofs are simple to understand (baring notational issues in the appendix), which is a strength of this paper. My scores are slightly lower since I need to make sure I understand the use of Dropout in theorem 3. I am happy to increase my score after discussing it with the authors and other reviewers.


***After Rebuttal***
I have increased my score to 7. I would request the authors to make changes to the paper to address the different clarity issues mentioned by the reviewers.
limitations_and_societal_impact: The authors mention the limitations and the future directions of their work. Since the paper discusses a theoretical connection between trajectory and the Lipschitz constant of the neural network, I don't foresee a potential negative impact (to the best of my knowledge).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents an analysis of learning dynamics of neural network that relate the trajectory of changes in the first layer bias of neural network to bounds on Lipschitz constant, and thus the complexity of the model.   In other words, the authors establish that behaviour of first layer’s bias during training is a good predictor of the trained model’s complexity. 
main_review: Though the main logic of the argument is somewhat straight forward – Lipschitz constant of a network is linked to complexity, gradient of the entire network is linked to Lipchitz constant, therefore the trajectory of first layer bias, which depends on that gradient, is linked to complexity of the entire model – I think a rigorous mathematical treatment and the results presented are worth of notice.  The paper is written well and the ideas are presented clearly. 

I think the results in Ch 4 for complexity around the training points are interesting, though it is clear that from practical point of view, trajectory of bias alone is not sufficient to gauge complexity, as one also has to take into account singular values of W_1, which would change during training.

I do have a bit of an issue when it comes to complexity analysis when “far from training data”.  Specifically, if my understanding of Assumption 1 in Ch 5 is correct,  it allows changes of parameters in the model as long as long as the activation patterns (which ReLU neurons switch on and which one stay off)  stay the same.  Doesn’t that make the neural network essentially a linear model?  While this makes the analysis possible, it throws away the thing that makes neural networks useful…and I suspect, the Assumption is not likely to hold in practice 

limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors measure the complexity of the learned function of NN by the distribution of an approximation of its Lipschitz constants. They analytically show that the average of the Lipschitz constants at the beginning of the learning process can predict various aspects of the entire learning process, which could possibly allow picking the right architecture in a faster way.
main_review: The paper tackles an interesting topic, from a theoretical approach. As far as I can tell, this approach is new and can shed light on several aspects of NN training dynamics, which could be beneficial to the community.

However, this paper also has many faults:
The paper is very hard to read and even harder to understand. It is composed of many equations, with a stunning amount of notations and abbreviations. The paper introduces a large number of bounds, and the distinctions between them could be better explained. The paper lacks some high-level overview, which can better explain the motivation and usage of each bound.

The empirical part of the work feels premature. The authors merely explain the settings of each experiment, without clear motivation or analysis, which again makes it very hard to follow. The experiments are done mostly in toy settings, and it is unclear if they could be extended to real problems, raising concerns about the validity of the motivation.


Since this work is not directly in my field of studies, some of my concerns may be due to my unfamiliarity. Therefore, I tend to accept this paper, but as I can not give it a higher score than "marginally accept" with its current issues.


----------------------------------------------------------

Post rebuttal:
After reading the authors' response and the other reviews, I'm more confident than my original review that this is indeed a good paper, which should be accepted. As other reviewers also mentioned the readability issues, which in my opinion, are a significant problem with this version, I'll keep my score as "6: Marginally above the acceptance threshold", and raise my confidence score to 3.
limitations_and_societal_impact: not relevant
review_title: null

Meta-review: Five knowledgeable reviewers recommend this paper for acceptance. Most concerns from the reviewers were addressed during the discussion and some reviewers increased their score after the discussion. One reviewer comments that this submission presents very concrete strong theoretical contributions, with a simple empirical study supporting them. I agree with the reviewers. Hence I recommend this paper for acceptance. For the preparation of the final manuscript, I encourage the authors to take the reviewers comments carefully into consideration. In particular: One reviewer is still concerned about the clarity of the paper. One reviewer mentions s/he doesn’t think the lack of experiments in the large scale setting is a primary weakness of this paper, but that having them would be great. Another reviewer still thinks that the quality of the paper could be greatly improved if it included some experiments (even if toy) to confirm the theoretical findings more directly and provided concrete suggestions. Another reviewer found that his/her questions were well addressed, but s/he still has some reservations about Assumption 1 and is not sure there is any chance it would hold in practice (although s/he does not see this as a major problem for the purposes of the theoretical analysis). 
Decision: Accept (Poster)