Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper derives asymptotic scaling laws that characterize the rate of decay of the loss for neural networks trained by gradient descent in the NTK regime. Interestingly, the exponent of the power law describing this decay depends only on a few natural parameters (properties of the target function, dimensional of the data, smoothness of the nonlinearity).
main_review: Many of the current guarantees for training are difficult to operationalize because they are weak upper bounds on the evolution of the loss. The authors here take a distinct approach that focuses instead on networks in the NTK regime which are formally infinite width. In essence, the approach can be outlined as follows: initially one assumes that the parameters are close to optimal (always the case in the infinite width limit) and linearize the dynamics. If the data density is smooth and compactly supported then the spectrum of the integral operator $\tilde{\mathcal{A}}$ that acts on the residual will have a well-behaved spectrum. In some cases, the spectrum of this operator has a power law form, leading to an evolution equation for the loss that decays like $t^{-\xi}$.

I found the exposition throughout, especially in Sec. 3, to be quite clear and precise. Appendix D gives a very complete accounting of the different function classes considered throughout. 

The numerical results seem consistent with but not conclusive for the picture the authors advocate. 

Sec. 6.3 did not provide enough context to argue for the power law.
limitations_and_societal_impact: The most obvious limitation in this work is the NTK assumption. The authors are well aware of this fact and have some suggestive results in the mean-field regime near the end of the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper identifies a polynomial decay rate in the loss function during gradient descent under the condition that both the eigenvalues of the semigroup operator, and the coefficients in the eigenfunction expansion of an initial loss (g), exhibit power law decay. These assumptions are verified for the semigroup operator in the infinitely wide (NTK) regime, a mean field regime, and also, interestingly, under a homogeneity assumption in the transition kernel. Two scenarios for g are also considered. Throughout, the authors have taken care to be precise with coefficients and compute quantities exactly. 
main_review: I'm fond of what this paper manages to achieve. There is a great attention to detail from a mathematical point of view. The exposition is clear, assumptions well-specified, and a number of scenarios are covered. The recent push to consider spectral distributions in theoretical machine learning is an exciting one, and I think this paper is a prime example of what can be accomplished. An enjoyable read for sure. 

However, much of the presentation seems too matter of fact for this venue, with little discussion surrounding consequences and interpretations. A concluding paragraph to interpret the findings more generally would be ideal. I recognize that this is hampered by space constraints. To cut down on space, there are a number of paragraphs that should probably belong in supplementary material instead. For this particular venue, lines 123-127 and 176-187 (for example) bog down the exposition. Otherwise, making more equations inline and cutting down on some unnecessary paragraph breaks could help with this.

As a side comment, there is a particular line of research establishing an empirical connection between tail exponents in power laws and generalization performance [1-3]. There has been a subsequent push to explain these connections theoretically. I believe the presented work could be an excellent contribution to this literature in the following sense: the belief to date is that decreasing the exponent nu in (6) should improve performance. This coincides well with the conclusion in (9). Furthermore, the relationship between nu, xi, alpha, and d, all seem to coincide well with empirical results. I recognize that the eigenspectrum of the operator A is not quite the same as the heavy-tailed distributions considered in the present literature, but I would expect there to be a relationship, due to the presence of the Jacobian in the NTK (2) and therefore in (3). Besides, much of the "heavy-tailed" literature is ad hoc about where the tail exponent comes from, since it is believed that many of the power laws encountered are related. As far as rate of convergence results are concerned, I also recall a similar strategy of using spectral distributions in [4] --- not sure if this is also worth mentioning. 

With some of these changes, I believe this could be an outstanding paper --- at least a 7 or 8. 

[1] Mahoney, M., & Martin, C. (2019). Traditional and heavy tailed self regularization in neural network models. In International Conference on Machine Learning (pp. 4284-4293). PMLR.

[2] Simsekli, U., Sagun, L., & Gurbuzbalaban, M. (2019). A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning (pp. 5827-5837). PMLR.

[3] Martin, C. H., Peng, T. S., & Mahoney, M. W. (2021). Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data. Nature Communications, 12(1), 1-13.

[4] Paquette, C., Lee, K., Pedregosa, F., & Paquette, E. (2021). SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality. arXiv preprint arXiv:2102.04396.
limitations_and_societal_impact: The work presented is highly theoretical in nature. The limitations are predominantly to do with its assumptions, which are all clearly stated. Nevertheless, a concluding paragraph describing potential future improvements would be good to see.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the scaling law relation between $t$ (time) and the population loss in the NTK regime. The authors show that the scaling law is determined by two indices, (1) the index of the power law decay of the spectrum of the NTK (2) the index of the power decay of the residual of the loss on the eigenfunctions of the NTK.  The main technical contribution is the computation of the two indices. 


main_review: Scaling law behaviors of neural networks have attracted a lot of recent attention recently. The goal of this paper is study the scaling law under the NTK regime where the where the distribution of the learning task is given, in another words, the distribution of the input and the target are given and scaling law is mainly about the dependence of the population loss on time $t$. In this setting, population loss could be decompose into independent eigen-mode in the sense the loss is 
$$
loss(t) = \sum_{n} e^{-2 \lambda_n t} g_n^2
$$ where $\lambda_n$ are the eigenvalues of the NTK and $g_n$ are the projections of the residual.  As such, the scaling law is determined by the index ($\nu$ in the paper) of the power law decay (assumed in the paper) of $\{\lambda_n\}$ and the index ($\beta$ in the paper) of the power law decay of the residual $\sum_{n\geq m} \|g_m|^2$. The paper then proceeds to compute these two indices under various of settings, which are the most technical part of the paper and which are also a very classical topic in mathematical analysis. 

Overall, I think this is an interesting paper that draws a connection between scaling laws of neural network and oscillatory integrals although the analysis is limited to the NTK regime with popular loss. 
 
limitations_and_societal_impact: The work focuses on the NTK regime where the kernel is fixed, in which there is a nice and simple eigen-decomposition of the residual and does not cover the more realistic setting (mean field) where the kernel and the eigenvalues/eigenvectors are all evolving. Clearly, scaling law behavior under the latter setting is a very challenging open question in the field.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the scaling law in the training time of neural networks in the NTK regime.
main_review: The problem is novel and the scaling relations are very important both theoretically and practically. While the results in this work are interesting, I feel that the work could have spent some paragraphs discussing the practical uses of knowing the scaling law in training time.

Also, I am not too sure if the title is appropriate. The title reads: "Universal scaling laws in the gradient descent training of neural networks." However, the paper only studies the special form of scaling of the training loss with respect to the training time, but not all possible scaling laws. Therefore, I feel that the title needs to be changed to be more specific and avoid overclaiming. 

I will consider raising the score if the authors discuss the practical side of the work in the rebuttal and propose a more appropriate title (or convince me why the present title is indeed precise and accurate). 

Some other problems:
1. Figure 2 lacks axes labels.
2. line 158 "asisciate"



limitations_and_societal_impact: Sufficiently addressed.
review_title: null

Meta-review: Four reviewers recommend this paper for acceptance. One reviewer indicated that s/he is not as concerned with the NTK assumption and that this work could initiate some interesting follow-up studies on the benefit of certain power law scalings, and raised her/his initial score. Another reviewer raised her/his score as the authors sufficiently addressed his/her questions and proposed convincing improvements. Another reviewer concludes that the primary limitation of this work is the NTK assumption, but that the that the clarity of the submission is high compared with other submissions, and that the reviewers agree that the results are sufficiently interesting and could initiate a number of different inquiries both theoretical and numerical. In summary, the general consensus is for acceptance. I agree with this view and hence I am recommending this submission for acceptance. The reviewers made several suggestions and several improvements were proposed in the authors’ responses. I request the authors take these carefully into consideration when preparing the final manuscript. 
Decision: Accept (Poster)