Improving Adaptivity via Over-Parameterization in Sequence Models

Thank you for your efforts in reviewing our paper and your comments. We appreciate that you recognize that "the theoretical results are compelling". We would like to address your concerns in the following:

One significant weakness of the paper is the limited experimental validation.

2.The theoretical results are promising, but the empirical validation is limited.

We appreciate the reviewer’s concern about the experimental validation.

First, we would like to point out that while our experiments are mostly done on the sequence model, similar results hold for the kernel model under the non-parametric regression setting. We have performed additional experiments and we will include them in the new revision of the paper.

More importantly, the goal of our paper is to capture the dynamic nature of neural networks under the kernel framework and investigate the impact of the dynamic evolution of the kernel on the generalization performance. The reason why we consider a simplified model is that (1) directly analyzing a deep neural network is technically significantly challenging; (2) the simplified model enables us to gain a clear understanding of the dynamic evolution of the kernel and its impact on generalization. Moreover, the experiments included in our paper, particularly those in Appendix A, align well with our theoretical results. Therefore, our simplified model allows us to gain insights and provides a solid theoretical foundation for understanding more complicated over-parameterized models.

From a higher perspective, our main insight is that over-parameterized models combined with gradient-based training methods lead to a dynamically adaptive kernel that can adapt to the structure of the truth signal, which we would like to refer to as the "adaptive kernel" perspective. This perspective would be a valuable stepping stone for understanding the generalization properties of more complex neural networks. Under the guidance of this perspective, we will be able to consider more complicated over-parameterization and more realistic models like fully connected deep neural networks.

Therefore, while our current model may not directly apply to real-world datasets in natural language processing or computer vision, we think that our insights gained in this simplified setting will guide further research that explores the practical implications of our findings in these and other areas. We believe that starting from this point, we will be able to consider more realistic settings and understand more complex models in the near future.

We hope this clarification addresses your concern and highlights the intended scope of our work.

1.Can you provide more detailed theoretical justification or insights into why deeper layers contribute to better performance? Specifically, how does the introduction of additional layers influence the adaptation of eigenvalues, and are there any diminishing returns or optimal depth considerations that should be taken into account?

Thank you for the insightful question. To summarize, the additional trainable parameters introduced by deeper layers reduce the impact of misaligned initialization on the eigenvalues and enable the model to adapt more effectively to the structure of the true signal, thereby improving generalization performance.

To provide a more detailed theoretical justification, let’s revisit the parameterization of our model: $\theta_j = a_j b_j^D \beta_j$ for $j \geq 1$, where the initialization is given by $a_j(0) = \lambda_j^{1/2}$, $b_j(0) = b_0$, and $\beta_j(0) = 0$. In this framework, the term $a_j b_j^D$ is responsible for learning the eigenvalues, while $\beta_j$ captures the signal. Then, Proposition 3.4 provides key insights:

1. For signal components (large $\theta_j^\star$): $a_j b_j^D$ increases to approximate $|{\theta_j^* }|^{\frac{D+1}{D+2}}$ multiplied by a constant factor. This indicates that the eigenvalues become better aligned with the true signal as $D$ increases, since $\frac{D+1}{D+2}$ is an increasing function of $D$.

2. For noise components: If $\lambda_j \leq \epsilon^{2/(D+2)}$, $a_j b_j^D$ does not exceed its initial value by more than a constant factor, thereby controlling the generalization error contributed by noise. A larger $D$ allows this condition to be met for more components, thus enhancing the model's generalization performance.

While deeper layers facilitate more effective adaptation to the true signal, there are considerations regarding diminishing returns and optimal depth:

1. Training Time and Computational Cost: As shown in Corollary 3.3, the required training time $t \asymp \epsilon^{-\frac{2D+2}{D+2}}$ increases with $D$, as does the computational cost due to the added layers. This may not be desirable in practical applications where computational efficiency is a concern.

2. Limited Benefit: The primary benefit of deeper layers is to mitigate the impact of misaligned initialization on the eigenvalues. However, once $D$ is sufficiently large and this impact is no longer dominant, further increasing $D$ may not yield significant improvements.

Therefore, the optimal depth is problem-dependent, with $D$ being large enough to minimize the influence of misaligned initialization while balancing computational considerations.

We appreciate your positive feedback and valuable comments. We will address your concerns in the following:

The main concern here, is that the setting is too constrained, in that the kernel map is assumed to be fixed.

In fact, the goal of our paper is to investigate the impact of the dynamic evolution of the kernel on the generalization performance, so we are indeed considering a dynamic kernel/feature map. We have tried to consider a family of feature maps $\Phi_θ(\cdot)$ parameterized by $θ$ and the model

It is clear that it includes the neural networks as a sub-models and could (partially) capture the dynamic of feature learning characteristic in neural networks. It is clearly a hard task to investigate the most general adaptive kernel/feature models, however, some insight may be obtained from some simple families of feature maps.

For the kernel regression, the feature map is fixed, namely, $\Phi_θ(x)= (\sqrt{λ_1}e_1(x) ,\sqrt{λ_2}e_2(x),...)$, where $(e_j)_{j\geq 1}$ are orthonormal functions, and the kernel is $K(x,y)=\Phi(x)^{T}\Phi( y)$.

As the first attempt to understand the benefit of dynamic feature maps, we study the slightly complicated family $\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$, where the parameters $θ$ are learned during the training process. However, there are some technical challenges to theoretically analyze the differential equation associated to the family $\Phi_θ(x)$. Thus, we simplify the analysis by transitioning to the sequence model, which is justified by the celebrated Le Cam equivalence.

Here, we point out that while the eigenfunctions are fixed, the feature map can change by learning the eigenvalues, and, as shown in the main results, this dynamic evolution of the eigenvalues can greatly improve the generalization. Therefore, while simplified, our model still capture the dynamic nature of kernels/feature maps and provides insights and a solid theoretical foundation understanding more complicated over-parameterized models.

From a higher perspective, our main insight is that over-parameterized models combined with gradient-based training methods lead to a dynamically adaptive kernel that can adapt to the structure of the truth signal, which we would like to refer to as the "adaptive kernel" perspective. Starting from this point, we believe we will be able to explore more realistic settings and more complex models in the near future.

Moreover, as an extension of this work, with extra technicalities, we are now able to analyze directly the parameterization $\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$ in the Reproducing Kernel Hilbert Spaces (RKHS) (see the Future Work section). Due to the paragraph limit, we plan to explore it further in an extended journal version of this work.

Questions

1. The NTK is mentioned multiple times in the introduction, could you elaborate a bit more on the connection of your work to NTK?

   The motivation of this work is to go beyond the fixed kernel in the NTK theory and explore how the dynamic evolution of the kernel improves the generalization performance. The NTK theory shows that the training dynamics of deep neural networks can be approximated by certain kernel regression with a fixed tangent kernel if the network width tends to infinity. However, when the width is finite, the corresponding tangent kernel can be dynamically evolving during training, which is shown empirically in recent works. Therefore, in our work, we go beyond the NTK theory and explore the dynamic evolution of the kernel, particularly its impact on the generalization performance. Since the analysis directly over fully-connected networks is extremely challenging, we simplify the setting by considering parameterizing the kernel only by its eigenvalues and focusing on these eigenvalues. Our results show that such dynamic evolution of the kernel can greatly improve the generalization performance compared to the fixed kernel.

2. How would you go about approximating the (infinite sequence $\lambda_i$) in practice? How does this affect performance and guarantees?

   In our setting where we parameterize the kernel by the eigenvalues, we actually choose an infinite sequence $\lambda_i$ first as the eigenvalues and then get the corresponding kernel, so the approximation of the eigenvalues is not needed. The usage of "eigenvalues" is just to be consistent with the fixed kernel framework (see the connection to NTK), and these "eigenvalues" are just the initialization of the (dynamic) kernel in our setting. Following our main result (Theorem 3.1 and Theorem 3.2), it suffices to choose eigenvalues with a fast decay such as $\lambda_i = i^{-4}$ so that the extra error caused by the misalignment of the initial eigenvalues and the truth signal is small.

I thank the authors for answering my questions. I keep my score.

Thank you for your positive feedback and recognizing the contribution of our work. We will address your concerns in the following:

1. The insightful explanations for why the proposed method can improve generalization are lacked.

   We are sorry for not presenting it clearer. Generally speaking, the proposed over-parameterized gradient descent can improve generalization by adjusting the " eigenvalues" to fit the structure of the truth signal, so that it can outperform the standard gradient descent. In Section 3.3 paragraph "Learning the eigenvalues", we have further investigated why the over-parameterized gradient descent can improve generalization. Proposition 3.4 in this paragraph shows that for the signal components, the eigenvalues are learned to be at least a constant times a certain power of the truth signal magnitude; while for noise components, the eigenvalues do not exceed the initial values by some constant factor. Therefore, the over-parameterized gradient descent effectively adapts eigenvalues to the truth signal while mitigating overfitting to noise, which leads to better generalization.

2. While the experiments in appendix have verified the effectiveness of overparameterized gradient descent, it is recommended to compare the performance of this new method with other algorithms, such as SGD or SAM.

   Thank you for pointing out this. We have conduct more experiments to compare the performance of the proposed over-parameterized gradient descent with other algorithms, such as SGD or SAM. The results show that without the over-parameterization, neither SGD nor SAM can achieve the optimal generalization rate as the over-parameterized gradient descent does.

   Theoretically, as far as we know, the SGD algorithm in kernel regression achieves the same generalization rate as the standard gradient descent ([Lin and Volkan, 2020]), so that it also suffers from misalignment of the eigenvalues in our setting and be inferior to the over-parameterized gradient descent.

References

[Lin and Volkan, 2020] Lin, Junhong, and Volkan Cevher. “Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms.” Journal of Machine Learning Research 21 (2020): 147–1.

Thank you for your efforts in reviewing our paper and recognizing the contribution of our work. We appreciate your constructive feedback and will address your concerns in the following:

Narrow/Restrictive Settings

Dynamically Evolving Kernels

We fully agree with you that the dynamic evolving kernel/feature would explain the superiority of the neural network and this is our start point of this manuscript. We have tried to consider a family of feature maps $\Phi_θ(\cdot)$ parameterized by $θ$ and the model

It is clear that it includes the neural networks as a sub-models and could (partially) capture the dynamic of feature learning characteristic in neural networks. It is clearly a hard task to investigate the most general adaptive kernel/feature models, however, some insight may be obtained from some simple families of feature maps.

For the kernel regression, the feature map is fixed, namely, $\Phi_θ(x)= (\sqrt{λ_1}e_1(x) ,\sqrt{λ_2}e_2(x),...)$, where $(e_j)_{j\geq 1}$ are orthonormal functions, and the kernel is $K(x,y)=\Phi(x)^{T}\Phi( y)$.

As the first attempt to understand the benefit of dynamic feature maps, we study the slightly complicated family $\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$, where the parameters $θ$ are learned during the training process.

However, there are some technical challenges to theoretically analyze the differential equation associated to the family $\Phi_θ(x)$. Thus, we looked for some alternative approaches. Fortunately, the celebrated Le Cam equivalence could allow us to simplify the setting to a sequence model. (Please see the answer of Question 1 for details)

Here, we point out that while the eigenfunctions are fixed, the feature map can change by learning the eigenvalues, and, as shown in the main results, this dynamic evolution of the eigenvalues can greatly improve the generalization. Therefore, while simplified, our model still holds a connection to the dynamic evolving kernel/feature models and provides insights and a solid theoretical foundation understanding more complicated over-parameterized models.

From a higher perspective, our main insight is that over-parameterized models combined with gradient-based training methods lead to a dynamically adaptive kernel that can adapt to the structure of the truth signal, which we would like to refer to as the "adaptive kernel" perspective. Starting from this point, we believe we will be able to explore more realistic settings and more complex models in the near future.

Moreover, as an extension of this work, with extra technicalities, we are now able to analyze directly the parameterization $\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$ in the Reproducing Kernel Hilbert Spaces (RKHS) (see the Future Work section). Due to the paragraph limit, we plan to explore it further in an extended journal version of this work.

Questions

1. The meaning of the sentence in lines 172-175 is unclear. Additionally, it would be helpful if the sequence model were described earlier to enhance its comprehension.

   We apologize for the confusion. In these lines, we are illustrating that kernel regression can be simplified to a sequence model using the so-called Le Cam equivalence. In detail, the Le Cam equivalence states that the minimax risk of estimating a function in a reproducing kernel Hilbert space (RKHS) is equivalent to the minimax risk of estimating a sequence of coefficients in a sequence model. Informally, if we multiply $\Phi(x_i)$ on both sides of the equation $y_i=\Phi(x_i)^{T}β+ε_i$ and take the mean over $i=1,...,n$, we get $\frac{1}{n}\sum_i \Phi(x_i)y_i = \frac{1}{n}\sum_i \Phi(x_i)\Phi(x_i)^T β + \frac{1}{n}\sum_i \Phi(x_i)ε_i$. Using the orthogonality of $e_j$'s in $\Phi(x)^{T}=(\sqrt{λ_1}e_1(x) ,\sqrt{λ_2}e_2(x),...)$ and approximating the empirical mean with the integration, we derive $\frac{1}{n}\sum_i \Phi(x_i)y_i \approx \Lambda β+\xi$, where $\xi$ is a vector of Gaussian noise and $\Lambda$ is a diagonal matrix with entries $\lambda_j$, so we reach at the Gaussian sequence model. This equivalence allows us to focus on a more tractable model while retaining the essential characteristics needed for our theoretical analysis. We hope this would clarify the point.

   In the new revision, we will reorganize the content and make sure the model is properly introduced.

2. Regarding the adaptive choice of the stopping time discussed in lines 279-288, I can roughly follow the authors' point.

   We apologize for the confusion. Our point is to show the over-parameterized gradient descent method has also the advantage of adaptivity over the vanilla gradient descent method. For the vanilla gradient descent, the optimal stopping time $t \asymp ε^{-(2q\gamma)/(p+q)}$ is dependent on the unknown parameters $p$ and $q$ of the signal; in contrast, for the over-parameterized gradient descent, the choice $t \asymp ε^{-\frac{2D+2}{D+2}}$ does not require prior knowledge of the signal's structure. Moreover, the hidden constant in this stopping time expression only need to be large enough with only a dependency on Assumption 1, a weak assumption on the span of the signal (but not its specific structure). So, the stopping time is adaptive in the sense that it does not require prior knowledge of the signal's specific structure.

3. Including the numerical experiments from Appendix A into the main text would be beneficial, if possible. ...

   Thank you for your advice. With the additional content page if our paper is accepted, we will be able to include the numerical experiments from Appendix A into the main text to enhance the readability of the paper.

   For real-world datasets, we believe that the eigenvalue misalignment is a common phenomenon in practice.

   Due to the character limit, the details are given in a new comment block.

3. Including the numerical experiments from Appendix A into the main text would be beneficial, if possible. ...

   Thank you for your advice. With the additional content page if our paper is accepted, we will be able to include the numerical experiments from Appendix A into the main text to enhance the readability of the paper.

   For real-world datasets, we believe that the eigenvalue misalignment is a common phenomenon in practice.

   • From the theory side, as discussed in Example 2.2 (Low-dimensional example), if the regression function of the data exhibits an unknown low dimensional structure on the covariates, then using a fixed kernel that takes all covariates into account would lead to misalignment of the eigenvalues. Since the low-dimensional structure is very common in real-world datasets, the eigenvalues would be misaligned in practice.

   • To conduct experiment on real-world datasets, we can estimate the regression function's coefficients over the eigen-basis of the kernel and check whether they exhibit a sparse structure. We have conducted new experiments on datasets like "California Housing" and "Concrete Compressive Strength", where we choose the eigen-basis to be the multi-dimensional Fourier basis. The results show that the coefficients over the eigen-basis concentrate over a few components, indicating the sparse structure of the regression function, so misalignment of the eigenvalues would occur. Therefore, the eigenvalue misalignment might be very common in real-world datasets.

We would like to thank you for raising the score and providing further valuable comments on our paper. In the new revision, we will follow your advice to improve the clarity.

For the experiments on the real-world dataset, it seems that we missed the opportunity to post a global rebuttal where we can show figures and tables. We apologize for this. We will include the results in the new revision of the paper. Nevertheless, we would like to describe in detail the experiments and results here.

First, as discussed in Example 2.2 (Low-dimensional example) or Example 2.3, the misalignment happens when the order of the eigenvalues of the kernel mismatches the order of coefficients of the truth function. For the experiment setup, we consider the multidimensional Fourier basis (the trigonometric functions) as the eigen-basis of the kernel, which can be given by $e_{\mathbf{m}}(x) = \exp(2\pi i \langle{\mathbf{m},x}\rangle)$, where $\mathbf{m} \in \mathbb{Z}^d$. For the commonly considered kernel that correspond to Sobolev space (see also Example 2.2), the kernel and also its eigenvalues are isotropic in the sense that $\lambda_{\mathbf{m}} \asymp (1+||{\mathbf{m}}||_2^2)^{-r}$ for some $r > 0$. Therefore, it gives an order of the eigen-basis.

For the real-world dataset, we compute the coefficients of the regression function over the eigen-basis of the kernel by the empirical inner product. For "California Housing" and "Concrete Compressive Strength", the dimension of $x$ is 8, so we choose $\mathbf{m}$ up to $|m_i| \leq 2$, resuling in $5^8 = 390625$ coefficients. Then, we plot the magnitudes of the coefficients in the order given by the kernel. If the kernel is well aligned with the truth function, the coefficients should exhibit a smooth decay in this order. However, the resulting plot show multiple significant spikes. Also, among the coefficients, only very few components have large magnitudes, indicating the sparse structure of the regression function. Together, these results suggest that the eigenvalues of the kernel are misaligned with the truth function in these datasets.

Please feel free to ask if you have any further questions or need more details on the experiments. Thank you.

Thank you for your positive feedback and valuable comments. Following your advice, we will add the related papers that you mentioned.

My major concern is that similar results to this one already exist in the literature and the authors have not compared their results to them and how they differ from them. I am curious if your result can imply or be phrased as a sparse recovery type argument for high dimensional regression.

Thank you for pointing out the related works and the connection between our result and sparse recovery. Indeed, it is known that the over-parameterized nets with gradient-based methods tend to recover the sparse solutions, as shown in the related works you mentioned and also [Hoff 2017], [Vaškevicius et al., 2019], etc., cited in our paper. However, there are major differences on the settings and the results between our work and the related works, which we will clarify in the following:

• Analysis of Generalization Error: The papers [2,3] and also previous works like [Hoff 2017], [Gunasekar et al. 2017] are focused only on the optimization process using gradient-based methods, showing sparsity properties of the final solution, but they do not consider generalization error bounds. In comparison, our work (and also related works [Vaškevicius et al., 2019], [Zhao et al., 2022]) focuses further on the generalization error of the over-parameterization methods, which turns out to be a harder problem. More specifically, the works on the optimization process often assume the absence of noise in the data and consider the final interpolator as $t \to \infty$. However, such an interpolator may not generalize well under the presence of noise. In fact, as shown in our work and also [Vaškevicius et al., 2019, Zhao et al., 2022], proper early stopping is also crucial for generalization. Therefore, we have to analyze the full training process rather than the final convergence point to understand the generalization error, which is a more challenging problem.

• Linear regression vs. non-parametric regression The most related works are [Vaškevicius et al., 2019], [Zhao et al., 2022] that considered generalization performance of over-parameterized models with gradient training under the setting of high dimensional linear regression. In comparison, our work considers the non-parametric regression setting under reproducing kernel Hilbert spaces ( RKHS). There are several main differences between our result and their results:

  • Problem settings: They consider the high-dimensional linear regression where the input dimension (while growing) is finite, but we consider the non-parametric regression where the input dimension is directly infinite. Also, they focus on the setting with the separation of signal components and noise components, while we consider the more general setting of signal in the sequence model, allowing the magnitudes of the signal across components to vary continuously.

  • Over-parameterization setup: [Zhao et al., 2022] considers the over-parameterization setup that $\theta = a \odot b$ where the initialization is $a(0) = \alpha \mathbf{1}$ and $b(0) = \mathbf{0}$; [Vaškevicius et al., 2019] considers $\theta = u^{\odot D} - v^{\odot D}$ with $u(0) = v(0) = \alpha \mathbf{1}$. However, their parameterization can not apply to the infinite dimensional case since the components are treated equally and the $\ell^2$ norm of the estimator would be infinite after any step of training. In comparison, our work considers parameterization $\theta_j = a_j b^D_j \beta_j$ with $a_j(0) = \lambda_j^{1/2}$, $b_j(0) = b_0$ and $\beta_j(0)=0$, so the components are treated differently. Therefore, we have to tackle both the infinite dimensionality and also the interplay of different initialization, which is more complicated.

  • Interpretation of the over-parameterization: The previous works view the over-parameterization mainly as a mechanism for implicit regularization, while our work provides a novel perspective that over-parameterization adapts to the structure of the truth signal by learning the eigenvalues. Our perspective could provide more insights on the benefits of over-parameterization.

In the new revision, we will add a detailed comparison and discussion with the related works in the paper. We hope this will clarify the novelty and contribution of our work.

Can you compare your rate with the results in sparse recovery, if you use lasso instead of your estimator? specifically do you think the low dimensional example that you mention can be observed as some kind of sparsity that can be exploited by lasso?

Our results can be phrased for the setting of high dimensional regression with sparsity. Taking a sparse signal $(\theta_j^*)_{j \geq 1}$ in our paper, e.g., $\theta_j^* = 1$ for $j \in S$, $|S| = s$ and $\theta_j^* = 0$ for $j \notin S$, we have $\Phi(\epsilon) = s$ and $\Psi(\epsilon) = 0$, so we can find that the resulting rate is $O(s/n)$, which is the same as the rate of the lasso estimator.

For the low dimensional example in the sequence model, a JS estimator or thresholding estimator can indeed recover the sparse signal and achieve the optimal generalization rate, as shown in Chapter 6 and 8 in [Johnstone 2017]. We believe that a lasso-type estimator can also recover the sparse signal in this case. We think that a deeper connection between over-parameterization and these estimators can be explored in future work.

References

Due to character limit, please see the next comment block for references.

[Hoff 2017] Peter D. Hoff. Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization. Computational Statistics & Data Analysis, 115:186–198, November 2017. ISSN 0167-9473. doi: 10.1016/j.csda.2017.06.007

[Gunasekar et al. 2017] S. Gunasekar, B. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, volume 2017-December, pages 6152–6160, 2017.

[Vaškevicius et al., 2019] Tomas Vaškeviˇcius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery, September 2019. URL http://arxiv.org/abs/1909.05122.

[Zhao et al., 2022] Peng Zhao, Yun Yang, and Qiao-Chu He. High-dimensional linear regression via implicit regularization. Biometrika, 109(4):1033–1046, November 2022. ISSN 0006-3444, 1464-3510. doi: 10.1093/biomet/asac010.

[Johnstone 2017] Iain M. Johnstone. Gaussian estimation: Sequence and wavelet models. 2017.