It is well known that eigenfunctions of a kernel play a crucial role in kernel regression. Through several examples, we demonstrate that even with the same set of eigenfunctions, the order of these functions significantly impacts regression outcomes. Simplifying the model by diagonalizing the kernel, we introduce an over-parameterized gradient descent in the realm of sequence model to capture the effects of various orders of a fixed set of eigen-functions. This method is designed to explore the impact of varying eigenfunction orders. Our theoretical results show that the over-parameterization gradient flow can adapt to the underlying structure of the signal and significantly outperform the vanilla gradient flow method. Moreover, we also demonstrate that deeper over-parameterization can further enhance the generalization capability of the model. These results not only provide a new perspective on the benefits of over-parameterization and but also offer insights into the adaptivity and generalization potential of neural networks beyond the kernel regime.
Paper
Similar papers
Peer review
Summary
This paper investigates the influence of over-parameterization on the adaptivity and generalization of sequence models. The work highlights the significance of eigenfunctions in kernel regression and introduces an over-parameterized gradient descent method to analyze the effects of varying eigenfunction orders. Theoretical results demonstrate that over-parameterized models can adapt to the underlying signal structure and outperform traditional methods. The research shows that deeper over-parameterization further enhances model generalization. This approach provides insights into improving the flexibility and performance of neural networks, especially in practical scenarios where network architecture and initialization conditions dynamically evolve.
Strengths
The paper presents a novel approach by leveraging over-parameterization in sequence models to enhance adaptivity and generalization. This originality is evident in its creative combination of kernel regression techniques and over-parameterized gradient descent methods, which have not been explored together in this context before. Its significance lies transforming the understanding of neural network adaptivity beyond the traditional NTK framework, providing a robust theoretical foundation for improving model performance in practical scenarios where network architecture and initialization are dynamic.
Weaknesses
One significant weakness of the paper is the limited experimental validation. While the theoretical results are compelling, the empirical evidence provided is not sufficient to fully support the claims made about the superiority of the over-parameterized models in practical scenarios. The paper would benefit from a more extensive set of experiments across various datasets and model architectures to demonstrate the robustness and generalizability of the proposed methods. Additionally, there is a need for more practical examples that illustrate how the approach can be applied in real-world settings, especially given the dynamic nature of network architecture and initialization conditions mentioned. Including these aspects would enhance the paper's contributions and practical relevance.
Questions
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? 2. The theoretical results are promising, but the empirical validation is limited. Have you considered testing the proposed over-parameterized gradient descent method on a wider range of datasets and model architectures? How does the method perform in different domains, such as natural language processing or computer vision, compared to traditional methods and other over-parameterization techniques?
Rating
5
Confidence
2
Soundness
3
Presentation
2
Contribution
3
Limitations
None
Summary
The authors analyze the generalization error for kernel regression sequence models in the overparameterized regime. They rigorously show that due the overparameterization, the learned parameters are better adapted to the underlying structure. They also provide some numerical experiments corroborating their findings (in the appendix).
Strengths
- Clear motivation and presentation - Rigorous analysis that could be useful for further research
Weaknesses
The main concern here, is that the setting is too constrained, in that the kernel map is assumed to be fixed.
Questions
- The NTK is mentioned multiple times in the introduction, could you elaborate a bit more on the connection of your work to NTK? - How would you go about approximating the (infinite sequence ) $\lambda_i$ in practice? How does this affect performance and guarantees?
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
2
Limitations
Limitations have been addressed.
I thank the authors for answering my questions. I keep my score.
Summary
This paper proposed an overparameterized gradient descent method. Its benefits on generalization has been verified both theoretically and empirically.
Strengths
1.The paper is well-written with a clear structure. Motivations are well-explained on why the authors study the problem, and the illustrative examples are helpful in understanding the motivations. 2.Theoretical results are solid and well-organized. The authors made the theoretical settings clear: definitions are well-explained and assumptions are clear. Proofs of the theory are sound as far as I read into. 3.Experiments are provided in Appendix, which can verify the theoretical conclusions.
Weaknesses
1.The insightful explanations for why the proposed method can improve generalization are lacked. 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.
Questions
See weakness.
Rating
7
Confidence
3
Soundness
3
Presentation
3
Contribution
4
Limitations
No negative social impact.
Summary
This paper investigates how over-parameterization can enhance generalization and adaptivity within the non-parametric regression framework. Drawing on insights from kernel regression and over-parameterization theory, the authors focus on the sequence model, which can approximate a wide range of non-parametric models, including kernel regression. The authors highlight three key findings through mathematically stylized examples. First, they identify limitations of traditional kernel regression, including neural tangent kernel (NTK) theory, by demonstrating that the alignment (ordering) of eigenvalues can significantly impact generalization properties, even when eigenfunctions are correctly specified (Section 2). Second, by analyzing the gradient flow for a two-layer Hadamard neural network corresponding to the sequence model, they claim that this method can dynamically adjust eigenvalues to adapt to the underlying structure of the signal, achieving nearly the oracle rate with suitable regularization (Section 3.1). Finally, they show that adding depth can mitigate the impact of eigenvalue initialization, thereby improving generalization capability (Section 3.2).
Strengths
This work offers a clear and effective account of the limitations of the traditional kernel regression framework (including NTK theory) and the advantages of over-parameterized gradient descent. The simple yet concrete examples effectively support the authors' claims, and the accompanying intuitions are sensible and easy to understand. Additionally, the two main theorems (Theorem 3.1 and Theorem 3.2) are presented concisely and effectively, and the discussion in Section 3.3 is particularly helpful for interpreting the results.
Weaknesses
While this work makes significant theoretical contributions and provides a fresh perspective on the benefits of over-parameterization, there are areas where it could be improved: **1. Narrow/Restrictive Settings:** The sequence model and the parameterization in Eq. (8) and Eq. (14), viz., the Hadamard neural network, might be too simplistic. I am curious if the insights in this paper can be extended to more realistic parameterizations, such as fully connected networks. **2. Dynamically Evolving Kernels:** This paper addresses issues with misaligned eigenvalues and the benefits of over-parameterized gradient flow to mitigate them. However, during training, the kernel itself (and thus its eigenfunctions) may evolve, as empirically evidenced by [Seleznova and Kutyniok 2022] and [Wenger et al., 2023]. While the authors mention in Section 4 that this is left for future work, it would be helpful to understand if the eigenvalue alignment discussed in this paper can shed light on over-parameterization in practical settings beyond the stylized examples provided.
Questions
1. The meaning of the sentence in lines 172-175 is unclear. Could the authors elaborate on this? Additionally, it would be helpful if the sequence model were described earlier to enhance its comprehension. Perhaps the authors could include a background section or rearrange the description of the sequence model in lines 183-186 to be presented upfront, with appropriate references. 2. Regarding the adaptive choice of the stopping time discussed in lines 279-288, I can roughly follow the authors' point. However, it appears that there is an unspecified constant, which is not known a priori, needed to choose the stopping time $t \asymp \epsilon^{\frac{2D+2}{D+2}}$, making it not practically feasible either. Thus, I am wondering if the advantage is more aligned with universality, rather than practicality. Could the authors clarify this? 3. Including the numerical experiments from Appendix A into the main text would be beneficial, if possible. Additionally, could the authors design a simple experiment to support the practical relevance of eigenvalue misalignment and the discussions in this paper? For instance, would it be possible to demonstrate that it is common in real-world datasets that kernels are well-identified but eigenvalues are easily misaligned? Typos/minor suggestions: - Line 89: add transpose to $X$ - LIne 149: defines -> defined - Line 205: Inspired -> Inspired by - Line 235: shows the generalization error -> presents an upper bound for the generalization error - Line 260: have -> present?
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
This is primarily a theoretical work, and the authors discussed the potential limitations of the work and potential future research directions.
Remaining response for Question 3
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.
Response to the Authors' Rebuttal
I thank the authors for addressing my questions and concerns. Since most of my inquiries were for clarification, I trust that the authors will incorporate the additional explanations and reorganization into their revision. However, I was unable to locate the real-world dataset experiments mentioned in response to my Question 3; if the experiments have already been conducted, could the authors attach them to the global rebuttal? It would be also beneficial to include these (along with the authors' response to my Q3) in the revision. Overall, I believe this work makes a solid theoretical contribution, though I suggest some revisions to further improve clarity regarding the scope of contributions and limitations, as well as their relation to existing work (e.g., following the authors' discussion with Reviewer EWHq and Reviewer kYgJ) and future directions. Specifically, I recommend the following among others, some of which the authors have already committed to: (i) Properly introduce the sequence model, including a concise yet self-contained exposition of the Le Cam equivalence, potentially in the Appendix if necessary. (ii) Further clarify the dynamic adaptivity of the kernel. While I agree with the authors that a dynamic update of eigenvalues can lead to adaptive kernel choices, even with a fixed eigenbasis, this offers limited adaptivity compared to a more general adaptive kernel/feature model, as the authors also noted. It would be helpful if the authors could elaborate on the extent to which the current approach is effective and whether they believe an extension to a more general kernel model is needed. With that understanding, I am inclined to raise my rating to a 6.
Experiment details
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.
Summary
Authors consider the problem of fitting data with given a kernel but with a different estimator than kernel regression, which is based on an overparameterized version of the gradient flow for the squared loss. This estimator is inspired by the behavior of first-order algorithms in the area of deep learning theory under overparameterized models. The interesting regime in their theoretical result is when the order of the coefficients of the target function (that we hope to learn) in the eigenbasis of the kernel does not match the decay in the eigenvalues of the kernel itself; in this regime, while the conventional kernel regression estimator is suboptimal and can have undesirable dimension dependencies, they show that their estimator achieves a better rate, and intuitively is able to exploit the low dimensionality and adapt the eigenvalues of the kernel to the coefficients of the target function, a task which kernel regression with a fixed kernel is unable to do. Their analysis starts with using the Le cam theorem on the equivalence of kernel fitting and sequence models, then instead of running the gradient flow for the L2 loss of the sequence model only on the functions coefficients, they also train on some hyperparameters for the sequence model that resemble the kernel eigenvalues.
Strengths
The theoretical result is interesting and connects to areas, first one in statistics about JS estimators and benefits of alternative estimators than fitting the data in the l-2 sense (which is equivalent to kernel regression in our context), and the deep learning theory literature where researchers are trying to figure our the benefits of training neural nets over fitting a fixed kernel, and what the role of overparameterization is in this regard. Even though the algorithm is gradient flow and not computable in this paper, in a way it illustrate the benefit of training a simple overparameterized model and how it can is picking a kernel adaptively which works better than kernel regression with a fixed kernel. There are similar results in deep learning theory literature such as these: [1] “Optimization and Adaptive generalization of Three layer Neural Networks” [2] “What happens when SGD Reaches Zero Loss? – A Mathematical Framework” [3] “Label noise (stochastic) gradient descent implicitly solves Lasso for quadratic parameterization”
Weaknesses
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 the them.In particular, running gradient-based methods on overparameterized nets, such as the quadratic parameterization is known to recover the underlying sparse solutions [3], also [2] section 6.2. In particular, I am curious if your result can imply or be phrased as a sparse recovery type argument for high high dimensional regression (i.e. similar rate to lasso)? And can you quantitatively compare your end results/rates with these papers, independent of the differences between algorithms/initialization? The work of [Zhao et al., 2022] that you have already cited also seems to have such sparse recovery results for high dimensional regression for gradient descent run on overparameterized model. Please also clarify the difference between your setup/rates with them quantitatively. Minor comments This work [1] also shows that training overparameterized three-layer neural nets with a specific architecture leads to the algorithm adaptively picking the kernel (instead of NTK where the kernel is fixed), which seems similar in flavor to your result, so it is good mention/compare.
Questions
- 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?
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
The literature review/comparison with current result still needs work, upon addressing this I am happy to increase my score.
Dear Reviewers
We would like to thank the reviewers for their comments. We’ve taken the time to carefully go through each review. If anything is still unclear, please just let us know and we’ll get back to you quickly. Thanks again for your support!
Start discussions with authors, please
Dear Reviewers, Thank you for your valuable contributions to the review process. As we enter the discussion phase (August 7-13), I kindly request your active participation in addressing the authors' rebuttals and engaging in constructive dialogue. Please: - Carefully read the authors' global rebuttal and individual responses to each review. - Respond to specific questions or points raised by the authors, especially those requiring further clarification from you. - Engage in open discussions about the paper's strengths, weaknesses, and potential improvements. - Be prompt in your responses to facilitate a meaningful exchange within the given timeframe. - Maintain objectivity and professionalism in all communications. If you have any concerns or need guidance during this process, please don't hesitate to reach out to me. Your continued engagement is crucial for ensuring a fair and thorough evaluation process. Thank you for your dedication to maintaining the high standards of NeurIPS. Best regards, Area Chair
Re:
I thank the authors for responding to my comments. I'd like to increase my score based on the authors' response.
Response
Thank you for your response. regarding your claims in the new response that previous work in NN theory only show structural result about convergence of gradient based methods and does not consider generalization, that is not true I think, e.g. reference [1] that I sent above also consider the generalization capability of the final NN weights (which achieves similar rates to what you get in classical sparse recovery). So I think I don't understand that part of your claim. Regarding your comparison with Zhao et al., 2022, you mentioned they consider the l-2 case without weights so it cannot be used for the infinite weighted case, do you mean there is a fundamental barrier in generalizing their approach to cover the weighted infinite case, or is it that they just did not investigate this case in that paper?
Thank you for your insightful comments. **Regarding the first point**, we apologize for any miscommunication. Our intention was to emphasize that while most research on over-parameterized models focuses on structural results, there has been less exploration into the generalization benefits of over-parameterization. We appreciate your reference to [1], which is indeed a significant work on the generalization capabilities of over-parameterized neural networks that we had missed. Our work shares some conceptual similarities with [1], particularly in viewing over-parameterization through an adaptive kernel perspective. However, there are still differences in our approach: while [1] explores an adaptive kernel space in the form of $G\odot K^\infty$ around the NTK space, our study examines an eigenvalue-parameterized kernel space with a fixed eigen-basis. We believe that the diversity of approaches, including those in [1], will contribute to a deeper understanding of the generalization properties in over-parameterized models. We will ensure to include [1] in our revised introduction and add a detailed comparison within the paper. **Regarding the second point**, there is indeed a fundamental difference between their approach and our approach in the weighted infinite case. Specifically: 1. We have to track the differently weighted initialization across components; 2. We provide new insights on the benefits of over-parameterization by learning the eigenvalues, see Proposition 3.4; 3. We extend our study to deeper layers, demonstrating additional benefits, whereas Zhao et al., 2022 is limited to the two-layer setting. We appreciate your thorough review and the opportunity to improve our work.
Decision
Accept (poster)