On the Disconnect Between Theory and Practice of Overparametrized Neural Networks

Thank you for your review and feedback! If we could answer your questions, we would appreciate if you'd consider updating your score. If anything remains unclear, please let us know.

Detailed Response

While each of the authors' claims is clear, the connections between them are somewhat disjointed. Specifically, it is challenging to perceive Section 3.1-3.2's issues as problems since, in reality, wide NNs experience less catastrophic forgetting, as suggested in Section 3.3. Therefore, combining Sections 3.1 and 3.2 into one section and separating Section 3.3 might help avoid this confusion.

Could you clarify what you mean by "[...] it is challenging to perceive Section 3.1-3.2's issues as problems since, in reality, wide NNs experience less catastrophic forgetting, as suggested in Section 3.3."? While the issues described in Sections 3.1 and 3.2 have the same underlying assumptions (that the networks behave according to the kernel regime), they all consider different domains (training, uncertainty quantification and continual learning). Only Section 3.3 concerns itself with catastrophic forgetting.

All three sections (training, uncertainty quantification, and continual learning) make assumptions based on the kernel regime. For provably faster optimization via natural gradient descent, we find that practical architectures are not wide enough to be close to the kernel regime and thus satisfy Jacobian stability. In the neural bandit setting, we find that sequential actions taken based on the uncertainty as given by the empirical NTK perform no better than random. In theory if the network was sufficiently close to the kernel regime, it should achieve near-optimal regret (Zhou et al., 2020). Finally, in the continual learning setting catastrophic forgetting can be predicted and mitigated if the network is near the kernel regime. In practice, at first glance wider networks seem to mitigate forgetting (as observed by Mirzadeh et al., 2022), but based on our experiments only if the networks are not trained to high accuracy, which is clearly desirable in practice. Therefore all of these sections show that drawing conclusions from the kernel regime about the behavior of neural networks used in practice can be problematic. This is the observed disconnect we describe.

Have you considered restructuring the sections to more coherently present the content, possibly merging Sections 3.1 and 3.2, and separating Section 3.3?

We believe all three sections 3.1-3.3 fit semantically under one heading, since they all assume the networks behave according to the kernel regime, while in practice with realistic widths they behave very differently. For the final version we will improve the introduction to Section 3 to make that very explicit. Would a different title for Section 3 rather than "Connecting Theory and Practice" help make it more clear what we are describing in Section 3?

The title of Section 3.1, "Training: Second-order Optimization", doesn't accurately convey the content discussed within. The empirical evidence in Section 3.1 (Figures 2-3) primarily supports the instability of the Jacobian in finite NNs. While this might be one of the reasons second-order optimization methods fail when applied to NNs, the paper doesn't seem to present direct experiments that validate this. Moreover, second-order optimization can fail for more than one reason: Slow convergence and Poor generalization. The authors do not specify which of these reasons is attributed to the unstable Jacobian. To avoid confusion, it's recommended that the title of Section 3.1 be revised.

Q: Second-order optimization can exhibit issues like slow convergence and poor generalization. Could you specify which of these issues the unstable Jacobian directly contributes to, based on your research?

You are completely correct that second-order methods may not only converge slowly, but also demonstrate poor generalization or other issues. We only consider the speed of convergence of the training loss in our work. As we describe on page 4 in the paragraph "Fast Convergence of NGD in the Kernel Regime", a network in the kernel regime, if trained with natural gradient descent (an approximate second-order method), provably exhibits fast convergence (Theorem 3, Zhang et al. 2019). The proof by Zhang et al. (2019) assumes conditions (7) and (8), whereby (8), the Jacobian stability, is the condition which is satisfied if the network is sufficiently close to the kernel regime. We experimentally demonstrate that this assumption is not satisfied for practical architectures (see Figure 2b). While second-order methods may perform well for deep learning, our findings show this cannot be explained via the kernel regime. To reflect better what we describe in Section 3.1, we changed the title to "Training: Conditions for Fast Convergence of Second-Order Optimization".

Thank you for your taking the time to review our paper. If we could answer your questions to your satisfaction, we would appreciate if you would consider updating your score.

Detailed Response

The experimental results of Section 3.1 seem to refute the theory of Zhang et al. (2019), rather than the NTK theory.

We do not refute the theory of Zhang et al. (2019). Their theory is correct, but the required width to reach the kernel regime, such that conditions (7) and (8) are satisfied are out of reach in practical architectures.

Logically, the NTK theory does not claim that (7) and (8) should be satisfied.

This is incorrect. In the limit of large-width, Jacobian stability (8) is satisfied. In fact, as Zhang et al. (2019) write below "Condition 2" in their paper, eqn (8) with small $C$ implies that the NN is close to a linearized NN at initialization. The NTK is simply the function-space view of this property. In fact, Lee et al. (2019) use Jacobian stability (formulated as a Lipschitz smoothness condition, see paragraph below Condition 2 in Zhang et al. (2019)) to prove the convergence of the empirical NTK to the empirical NTK at initialization at the rate we give in eqn (6) (c.f. eqn S50 and eqns S69-S72). Condition 1 (eqn 7) is simply a regularity condition, which is violated e.g. if there are duplicate datapoints in the dataset.

To summarize, Jacobian stability is simply a "weight-space view" condition for when a NN is in the kernel regime. In Figures 2 and 3 we show that both for wide toy architectures and for WideResNets with widths as used in practice, Jacobian stability is not satisfied. Therefore, conclusions drawn from the kernel regime do not apply, in particular, NGD does not necessarily converge faster than gradient descent.

The general question is: how the irrelevance of the NTK theory follows from the fact that certain assumptions of a theory developed in a previous paper (e.g. Stable Jacobian conditions (7) and (8)) are not satisfied in current experiments.

Our claim is not that NTK theory is irrelevant, rather that its assumptions are not satisfied in practice. Therefore making assumptions based on the kernel regime can be misleading and to suboptimal algorithms. We demonstrate this across three different domains, pointing out a disconnect between theory and practice. Specifically for Section 3.1: If practical architectures were well-described by NTK theory, Jacobian stability (8) would be satisfied, which is not what we see in our experiments.

The same holds for the Neural Contextual Bandits experiments. It seems that Section 3.2 shows that the formula for the exploration parameter from Zhou et al. is not very good in a practical setting [...]. But this does not mean that "the practical relevance of the infinite-width limit" is in question.

As you correctly point out, we observe experimentally that the exploration parameter choice of Zhou et al. (2020) does not lead to competitive results. However, they prove that under the assumption of sufficiently large width (s.t. the NN is in the kernel regime), their choice of $\gamma_t$ leads to near-optimal regret $\tilde{O}(\sqrt{T})$ with high prob. (see Thm 4.5, Zhou et al. 2020). Now, to explain our experimental results, either their theorem is incorrect, which we do not claim, or the NN does not in fact behave as if in the kernel regime, which is our contention. Therefore the infinite-width limit is not informative for this case.

In the sequential decision making setting, where UQ is crucial, making assumptions derived from the kernel regime can be counterproductive. Instead, we propose to leverage UQ tools that are designed for finite-width neural NNs as deployed in practice, such as the Laplace approximation. We emphasize that this does not mean that the NTK theory is not important for understanding NNs. We only claim that it is more effective to use finite-width approximations/theories for finite-width problems.

Concerning catastrophic forgetting, there is no discussion of why the previous research (e.g. Mirzadeh et al. (2022)) somehow contradicts the experimental results of the paper.

As we write in Section 3.3 (paragraph "Experiment Results" and caption of Figure 7) the results for the shallow MLP seem to confirm that catastrophic forgetting decreases with width as Mirzadeh et al. (2022) suggest. However, they also found the same to hold for WideResNet on SplitCifar100. A finding which based on our experimental results was due to early stopping, not the lazy regime. Therefore, if practical architectures are trained to high accuracy, large width does not mitigate forgetting (see Figure 7). Therefore, as we write in the caption of Figure 7: "[...] architectures in practice are not actually wide enough to reduce forgetting via the kernel regime." Could you clarify in what way you believe the differences in experimental results from Mirzadeh et al. (2022) and our paper were not discussed?

Thank you for your positive feedback! We will make it more explicit in the final version of the paper that we consider the lazy training regime. We hope we could answer any questions you raised below. If anything should remain unclear, we would be glad to address it.

Detailed Response

My primary critique is the lack of distinction made between width and feature learning strength. [...] I do not expect the authors to redo experiments in this alternative parameterization (though that would certainly be an interesting follow up). It would be very good, however, to distinguish between overparameterized theory not being representative of realistic finite-width networks (which I think is an incorrect claim) vs lazy training at large widths being non-representative of realistic finite-width networks (which is the claim that the paper very nicely supports). A few sentences in the introduction making this explicit would be very welcome.

We will make this distinction more clear both in the introduction and by adding a paragraph to the supplementary (due to space constraints) that explicitly mentions and cites different parametrizations that have been proposed based on the references you provide.

For optimization, besides stability conditions, were there other signs like faster convergence that second-order methods may work better? Or was SGD consistently better?

To the best of our knowledge there's no empirical comparison of first and second-order methods on large-scale benchmark datasets that shows a clear performance difference. Here, we consider theoretical conditions under which second-order methods (specifically NGD) converge provably faster than first-order methods (Zhang et al. 2019; Thm. 1 and paragraph below). These conditions are satisfied in the kernel regime and we test them empirically for architectures used in practice with realistic widths. To test these conditiones it is not necessary to train the network, but only to evaluate the difference in Jacobians at initialization and the Jacobians at parameters in a ball around the initial parameters. This is what we test and show in Figure 2 and 3.

What happens if you make the tasks more similar in the continual learning setting? Does the NTK theory begin to hold?

For toy architectures with very large widths the predictions from NTK theory hold. The parameters change only very little from initialization (and therefore also the learned representation) and catastrophic forgetting is reduced (see Figure 7, left column). Now as you rightly point out, following this reasoning suggests that if tasks are more similar, then catastrophic forgetting should also be reduced, possibly also at much smaller widths. One can see this in Figure 9, for the toy architecture on rotated MNIST (where tasks differ by a rotation of 22.5 degrees). Forgetting is reduced on tasks that are within a few 22.5 degree rotations of each other. It is still larger for smaller widths, but not nearly as large for more similar tasks than for very different tasks (c.f. Task 0: Tasks Learned = (0,1) vs Tasks Learned = (0, 4)).

I thank the authors for their response and continue to support acceptance.

Thank you for your review and detailed feedback! We included your suggestions in the revised version. We hope we could answer the questions you raised in your review below, if not we are happy to clarify further.

Detailed Response

It was hard for me to understand how novel the submitted paper is. I would appreciate a comparison to "Empirical Limitations of the NTK for Understanding Scaling Laws in Deep Learning".

While Vyas et al. (2023) briefly discuss generalization as a function of width, they primarily study the NTK in the context of scaling laws, i.e. how quickly generalization error decreases with more training data. In contrast, our paper primarily studies predicted phenomena from the kernel regime as a function of width. Our work focuses on domains where the kernel regime promises to inform better algorithms in practice. More concretely, how to train them efficiently, how to obtain reliable and cheap uncertainty quantification and how to deploy them in a continual learning setting. In that sense our paper complements the findings by Vyas et al. (2023). Not only is the NTK limit not predictive of finite-width NN generalization, but predictions from the kernel regime should also not be used without scrutiny as the basis for better algorithms (training, uncertainty quantification) or guiding principles in practice (continual learning). We've added a citation to Vyas et al. (2023) to the revised version of the paper.

In Section 3.1, can the authors explain in what sense does NGD have "favorable convergence over GD" in theory? Does the paper refer to an appropriate source for this statement? Is this ``strict'' in some way? (otherwise it's unclear why testing only NGD is sufficient to draw conclusions on GD).

We apologize for not clearly citing this statement, which is detailed in [1] (paragraph below Equation (11), $n$ is the number of data points and $\lambda_0$ is defined in footnote 6 of our paper):

Compared to analogous bounds for gradient descent [Du et al., 2018a, Oymak and Soltanolkotabi, 2019, Wu et al., 2019], we improve the maximum allowable learning rate from $\mathcal{O}(1/n)$ to $\mathcal{O}(1)$ and also get rid of the dependency on $\lambda_0$. Overall, NGD (Theorem 3) gives an $\mathcal{O}(\lambda_0 / n)$ improvement over gradient descent.

We will make this more clear in the final version of the paper.

In Section 3.1 (Page 6), why do the authors use only a subset of the data for the CNN regression experiment? (this should be explained in the paper as well).

We use only a subset of the data for the regression experiment in Section 3.1. due to computational constraints at large widths. For example, for the WRN computing one data point for large widths and $N=2000$ requires roughly 3 GPU days.

More specifically, the JVPs and VJPs required to multiply with the NTK matrix require looping over the data in batches, performing forward and backward passes. For NNs with very large widths those operations quickly become expensive (note that for fully-connected NNs the number of parameters scale as $O(P)=O(m^L)$ with width, and JVP and VJP costs scale with number of parameters). Since we want to explore large widths, our only choice to reduce cost is to use less data. To make sure that this does not corrupt our experiments, we compared the conditions for two different sub-set sizes in Fig. 3 which confirms that using more data leads to weaker linearity (as predicted by the theory too).

Still in Section 3.1, does it make sense to somehow plot in Figure 2 (e.g., with a horizontal line) the $\lambda_{\text{min}}$ and $C'$ in the limit where the width $\to \infty$ (i.e., in the NTK regime)? Is there perhaps a way to compute that theoretically rather than numerically? I believe it may complete the picture for this experiment.

We can compute $\lambda_{\text{min}}$ theoretically for the toy architectures, since the limiting kernel is known. The Gram matrix converges to $\mathbf{G}^\infty_{ij} = \mathbf{x}_i^T \mathbf{x}_j\frac{\pi - \arccos(\mathbf{x}_i^T \mathbf{x}_j)}{2\pi}$ (see Zhang et al. (2019), Definition 1). We've computed the minimum eigenvalue of this matrix and added it as a dashed horizontal line to the plot (see Figure 2a in the revised paper). For Figure 2b, we can draw $C'$ in the limit of infinite width, since as we write in the paper below eqn. 8, $C \to 0$. We've drawn $C'=0.5$ as a black dashed line in Figure 2 to indicate the threshold for which the Jacobian is sufficiently stable for rapid convergence of NGD.