Improving Adaptivity via Over-Parameterization in Sequence Models
Authors: Yicheng Li
Qian Lin
Venue: NeurIPS 2024 poster (2024)
Keywords: Over-parameterization
gradient descent
Gaussian sequence model
kernel regression
Primary area: learning_theory
TL;DR: We demonstrate that over-parameterized gradient descent in sequence models adapts to signal structures and significantly outperforms the vanilla gradient flow method induced by a fixed kernel.

Abstract: 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.

Improving Adaptivity via Over-Parameterization in Sequence Models
Yicheng Li
Qian Lin
Department of Statistics and Data Science Tsinghua University, Beijing, China liyc22@mai 1s. http:/mmaaisttttnuuaaaaa. edu.. cn
Department of Statistics and Data Science Tsinghua University, Beijing, China iianlin@tsingguu.. edu.
Abstract
It is well known that eigenfunctions of a kernel play a crucial role in kernel regression. Through several examples, demonstrate that even with the same set of cigenfunctions, the order of these functions significantly impacts regression outcomes. Simplifying the model by diagonalizing the kernel, introduce an over-parameterized gradient descent in the realm of sequence model to capture the effects of various orders of fixed set of sigen-functions This method designed to explore the impact of varying eigenfunction orders. Our theoretical results show that the over- seee-paratttrizationn gradient flow can adapt 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 new perspective on the benefits of over- aree-arramttrizzaionn and but also offer insights into the adaptivity and generalization potential of neural networks beyond the kernel regime.
Introduction
In recent years, the remarkable success neural networks in wide array of machine learning applications has spurred search for theoretical frameworks capable of explaining their efficacy and efficiency. One such framework is the Neural Tangent Kernel (NTK) theory (see, e-g., Dacot al. [2018), Allen-Zhu et al. (2019]), which has emerged pivotal tool for understanding the dynamics neural network training in the wnfinite-width limit. The NTK theory posits that the training dynamics of wide neural networks can be closely approximated by kernel gradient descent method with the corresponding NTK, elucidating their convergence behaviors during gradient descent and shedding light their generalization capabilities. Parallel to this, extensive literature kernel regression (see, c.g., Bauer et al. [2007]. Yao et al.] [2007] has studied its generalization properties, showing its minimax optimality under certain conditions and providing insights into the bias-variance trade-off. Thus, one can almost fully understand the generalization properties of neural networks in the NTK regime by analyzing the kernel regression method.
However, the application NTK theory to analyze neural networks, while invaluable, essentially frames the problem within traditional statistical method by fixed kemel. The NTK analysis, by its reliance on the fixed kernel approximation, can not entirely account for the adaptability and flexibility exhibited by neural networks, particularly those of finite width that deviate from the theoretical flinite-widthe limit (Woodworth et al. 22200. Morcover, empirical evidence (Wenger et al. 2003 Scleznova and Kutyniok 2022) also suggests that the assumption of constant kernel during training, a cornerstone NTK analysis, may not hold in practical scenarios where the network architecture or
"Corresponding author Qian Lin also affiliates with Beijing Academy of Artificial Intelligence, Beijing,
China
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

initialization conditions foster a dynamic evolution of the kemel. Also, Gatmiry et al. [202T] showed the benefits brought by the adaptivity of the kernel on a three-layer neural network. These results underscore the need for more nuanced understanding of neural network training dynamics, one that considers the intricate interplay between network architecture, initialization, and the optimization process beyond the simplifications of NTK theory.
Recently, another branch of research has focused on the verr-araameterization nature of neural networks beyond the NTK regime, exploring how parmmttrrettiiiioonnnn can lead to implicit regu- larization and even improve the generalization. In terms of training dynamics, studies (Hofi) (2077). Gunasekar et al. [2017]. Arora et al. [019a]], Kolb et al. [2023], etc.) in this domain have revealed that over- over-parameeeeee parameterieee models, particularly those trained with gradient descent and its variants, exhibit biases towards simpler, more generalizable functions, even in the absence of explicit reg- ularization terms. Moreover, terms of generalization, recent works [Vaškevičius et al.) 2019) Zhao et al., 2022 Li et al., [221a]] have shown that in the setting of high dimensional linear regres- sion, over- preepparamtterized models with proper initialization and early stopping can achieve minimax optimal recovery under certain conditions. These results underscore the potential and benefits of over-parameterized models that go beyond the traditional statistical paradigms.
In this work, we will incorporate the insights from the kernel regression and the over- over- vvee-parameterization theory investigate how over parameterization can improve generalization and also adaptivity under the non- non-poranaee parametric regression framework. As a first step towards this direction, we will focus on the sequence model, which is an approximation of wide spectrum of non con-aaraerrri models including kernel regression. We will show that, by dynamically adapting to the underlying structure of the signal during the training process, over over-paramen pree-paramttrrzatiion method with gradient descent can significantly improve the generalization properties compared with the fixed-eigenvalues method. We believe that our results provide a new perspective on the benefits of over-parameterizzaionn and offer insights into the adaptivity and generalization properties of neural networks beyond the NTK regime.
1.1 Our contributions
Limitations of the (fixed) kernel regression. In this work, we first investigate the limitations of the (fixed) kernel regression method by specific examples, illustrating that the traditional kernel regression method suffers from the misalignment between the kernel and the truth function. We show that even when the eigen-bast of the kernel is fixed, the associated eigenvalues, particularly their alignment with the truth function's coefficients in the basis, can significantly affect the generalization properties of the method.
Advantages of parameterateeed gradient descent. Focusing on the alignment between the kernel's 's cigenvalues and the truth signal (the truth function's coefficients), we consider the sequence model and introduce during the learning process. We show that with proper carly-stopping, the wwer-parameterization method can achieve nearly the oracle convergence rate regardless of the underlying structure of the signal, significantly outperforming the vanilla Exed-eigenvalues method when the misalignment is severe. In addition, the over over-vvraaae parameterization method is also adaptive by its universal choice of the stopping time, which is independent of the signal's 's structure.
perepaaattttiiitiionnn method (8) that dynamically adjust the eigenvalues
Benefits of deeper parameterization. Moreover, we also consider deeper weer-paaamcterization (14) and explore how depth affects the generalization properties the preetaaramttiiinioonnn method. Our results show that adding depth further the impact of the initial choice of the eigenvalues, thus improving the generalization capability of the model. We also provide numerical experiments to validate theoretical results in Section
1.2 Notations
We denote by @ { E5²1 az < 60) the space of square summable sequences. We write a S. if there exists a constant C' such that a S Cb and x if a S b and b S a, where the dependence of the constant C' on other parameters is determined by the context.

---

2 Limitations of Fixed Kernel Regression
Let us consider the non-paramenn con-aarmetrric regression problem given by y (x) + e, where is the noise with mean zero and variance o², x: E A and X' is the input space with μ being probability measure supported on X. The function fx) represents the unknown regression function we aim to learn. Suppose are given samples (:) drawn i..d. from the model. We denote X = (Zi..... _n,] and Y = (y1...., Bnn)
Let X X' IR be continuous positive definite kernel and Ha be its associated reproducing kernel Hilbert space (RKHS). The well-known Mercer's decomposition [Steinwart and Scovel 2012 of the kernel function k gives
kx,, v) = Σ )ye)(z)e,(V),
j=1
where (0z)521 is an orthonormal basis of (2 dp). and (25)521 are the eigenvalues of I: in descending order. Moreover, we can introduce the feature map ((x) = (A (A : X - (as a column vector) such that k(x, x') ) = (f(x), ((x')). With the feature map, a function f E Hz can be represented as f(z)= = (Ø x). 3) for some 3 E E2.
Defining the empirical loss L 2 Ei f(x:))² can consider an estimator ft (9(x), governed by the following gradient flow on the feature space
2 x= V
w (0)a))
where 80 3==0 0.
n
This kernel gradient descent (flow) estimator corresponds to neural networks at infinite width limit by the celebrated neural tangent kernel (NTK) theory [Jacot et al. 2018 Allen-Zhu et al., 2019].
2024a has studied the generalization performance of such kernel gradient descent estimator. From the Mercer's decomposition, we can further introduce interpolation spaces for as
An extensive literature Yao et al. 2007 Lin 2018 Li al.
[H&] = Σ Bj (35)221 e
which equipped with the norm |If [p.)) = 11 for f = Σド= B,13 eg. Particularly, the interpolation space [Ha]] corresponds to the RKHS H. itself. Then, assuming the eigenvalue decay rate X, x x the standard results (see, e.g., Yao et al. [2007], Li et al. (024aa)
) in kernel regression
state that the optimal rate of convergence under the source condition f [H4]* with || [[ I 1
is n 11-1, However, since the interpolation space [74,]* is defined via the degopdeccomooiition of the kernel, the generalization performance kernel regression methods ultimately related to the sigen-decomposition of the kernel and the decomposition of the target function under the basis, the performance is intrinsically limited by the relation between the target function and the kernel itself. In other words, the choice of the kernel could affect the performance of the method. To demonstrate this quantitatively, let us consider the following examples.
Example 2.1 (Eigenfunctions in common order).
well known that kernels possessing certain symmetries, such dot- kernels on the sphere translation canssaatonnnvvaiiant periodic kernels on the torus, share the same set of eigenfunctions (such as the spherical harmonics or the Fourier basis). If consider fixed set of eigenfunctions {e, 1521 and a given truth function f* for two kernels k and hi with eigenvalue decay rates Aj.1 = jー> and λj.2 = j-? respectively, it follows that:
f E [H,, st - 1 f E [H,,]] for 7181 = 72
Given that the convergence rate dependent solely on the product sy, the convergence rates relative to the two kernels will be identical.
seems to show that when the eigenfunctions are fixed, kernel regression methods yield Example 2.1
similar performance across different kernels. However, it's important to note that this similarity is due
3

---

to both kernels having the same eigenvalue decay order, which aligns with the predetermined order of the basis. In fact, if the eigenvalue decay order of a kernel deviates from that of the true function, even if the eigenfunction basis remain the same, it can lead to significantly different convergence rates. Let us consider the following example to illustrate this point.
Example 2.2 -iw-dinnniiooal structure). Consider translation canssatton-invariant periodic kernels on the torus T 1-1, with the uniform distribution. Then, their eigenfunctions are given by the Fourier basis 6m (x: exp(ir (m, m Zd. Within this basis, target function f*((x) can be represented as:
f Σ fm)m(x).
mEZ
Assuming f exhibits a low-dimensional structure, specifically f (x) g(z....., Id,) for some do < d, and considering g belongs to the Sobolev space H (T of order i, the coefficients f' can be shown simplify to:
Jmss m m (m1, 0), m. E
fm
0,
otherwise.
Let us now consider two translation-invaiiant periodic kernels kn and k2 given in terms of their cigenvalues: k1 is given by Am,1 = (1 | for some > d/2, whose RKHS is the full-
dimensional Sobolev space H" (TT*; k2 is given by Am,? (1+ ||] 1
(m,, 0) and Am.2 otherwise. Then, the function / belongs to both [Hx, J and [Ha,]* for 8 = l/r. After
for
reordering the eigenvalues in descending order, the decay rates for the two kernels are identified
as 71 = 2r/d and ?/2 = 2r/do- Thus, the convergence rates with respect to the two kernels are respectively:
2 21
2t
and
+ d
21 + do
Therefore, we see that when d is significantly larger than do, the convergence rate for the second kernel notably surpasses that of the first.
This example illustrates that the eigenvalues can significantly impact the learning rate, even when the eigenfunctions are the same. In the scenario presented, the second kernel benefits from the low-dimensional structure of the target function by focusing only the relevant dimensions, whereas the first one suffers from the curse of dimensionality since it considers all dimensions. The key point to take away from this example is the alignment between the kernel and the target function. To generalize this example, we can consider the following example where the order the eigenvalues does not align with the order of the target function's coefficients.
Example 2.3 (Misalignmennt). Let us fix set of the eigenfunctions (ez) and expand the truth function as f" E5²1 0jez. Note that by giving (ez),2ı we already defined an order of the basis in j. but coefficients 87 of the truth function are not necessarily ordered by j. Suppose that an index sequence {(j) gives the descending order of (3)) Then the difference between {(j) and j. Specifically, we assume that
characterize the misalignment by
0iss . j-+++++)/ and {()) ="" for 0, 2 1,
(p+1)/2
(4)
where larger indicates a more severe misalignment. In terms of eigenvalues, let us consider Ag.1 . which is in the order j. while A6g).2 x -, which is in the order of E(j). Then, the convergence rates with the two sequences of coefficients are respectively
P
P 1+1
and
p+q
Therefore, the convergence rates can differ greatly if the misalignment is significant, namely when g large.
From Example 2.2 and Example 2.3 we find that it is beneficial that the eigenvalues of the kernel align with the structure of the target function. However, one can hardly choose the proper kernel a priori, especially when the structure of the target function is unknown, the fixed kernel regression can be limited by the kernel itself and unsatisfactory. Motivated by these examples, we would like to explore the idea of an "adaptive kernel approach," where the kernel can be learned from the data.

---

3 Adapting the Eigenvalues by Over-parameterizatio in the Sequence Model
Motivated by the examples in the last section, as a first step toward the adaptive kernel approach, we consider adapting the eigenvalues of the kernel with eigenfunctions fixed. To simplify the analysis, we would like to the following sequence model, which captures the essences of many statistical models Brrwnn al. 2002 Johnstone 2017].
The sequence model
Let us consider the sequence model [Johnstone] 2017
2j = 03 + Ezr
j j21
(5)
where (2z1521 is the observation, 0" = =0j) E l² is sequence of unknown truth parameters and Eg, j 2 are (not necessarily independent) e² -usu-Gaausiian random variables with mean zero and variance at most e². For any estimator 0 (0,)ر21, the generalization error is measured by R*):0") = ンソ= (0, - 03)2. Under the asymptotic framework, we are often interested in the behavior of the generalization eтror as c - 0. Here, we note that the connection between non-parametric regression and the sequence model yields e ===
To the connection between the sequence model and the non-parametric regression model, we first write the gradient flow (2) in the RKHS in the matrix form as
1 (X))(X)) B. + (XX) n
B, - =
Now, since the where the feature matrix x(X) = (0(x)) ( (xnn))oxx and y (yl.....
eigenfunctions (ey)521 are fixed, intuitively, the gradient flow can be diagonalized in the eigen-basis since n (xx( ( ~ A diag(A1, A and the noise components are approximately normal with variance o² /m by the central limit theorem. Thus, we reach the sequence model. We refer to Subsection B.] for more detailed explanation of the connection between the sequence model and the kernel regression model.
Regarding the power series expansion in RKHS, for a sequence (Az))21 of descending positive numbers (e.g., ' ) we can consider similarly the parameterization 0j- = >3 3j. i 2 1 in e. Since (A,)521 corresponds to the cigenvalues of the kernel in the kernel regression, here we also refer (Az)521 as the "eigenvalues" with little abuse of terminology.
With the component-wiss loss function (0,) = (0, 2,)², we can apply a gradient descent (gradient flow) with early stopping to derive a component-wise estimator 0,. we directly param- eterize 03 = A 3, with only By trainable, we obtain the vanilla gradient descent method, which is just the diagonalized version of the kernel gradient descent. The estimator is simply given by 0g (1 e >>))))); where & is the stopping time, and its generalization error is easily computed as
20
BR 0²)) = (l,((;0)) + Var(() = Σ (e~)))))) Σ (1-E- j=1
(6)
j=1
We note here that these quantities also correspond generalization error in the (fixed) kernel
regression setting [Li et al. 2024a]. In particular, under the setting of (4) and >ラ x j=ン by choosing
2gx
2v.
t x p+7, we obtain the convergence rate e e which is far from optimal if q is large.
3.1 ever-parameteriace gradient descent
By the discussion in the previous section, we find it essential to adjust the eigenvalues beyond the fixed ones (Az)521- Inspired by the over-parameterization nature of neural networks, we can also consider over-paramettrrizaion with gradient descent in our sequence model to train the eigenvalues: Replacing //22 with trainable parameter aj. let parameterize
0g a
5

---

where aj aims to learn the eigenvalues and 83 aims to learn the signal. We consider the following gradient flow (simultanouusly for each component j):
à = --= T,j- BJ V3 991 T.j,
(8)
() =
Here, (A9)521 serves the initial eigenvalues, while the trainable parameters (az)z21 updated to adjust the eigenvalues during the training process.
To state our results with the most generality, let us introduce the following quantities on the target parameter sequence 0":
J == [::00:1 2622 5), (()) = Jaig (5)), (6))
Σ
(07)
(9)
(5
The quantity (6)) measures the number of significant components in the target parameter sequence 0, while (6) measures the contribution the insignificant components, which are commonly considered in the literature on the sequence model [Johnstone 2017). For the concrete setting of it is easy to show that
(6) x 8Í vr(6) x 8-it.
(10)
Moreover, we make the following assumption on the span of the significant components. Assumption 1. There exists constants 2 0 and Csig such that
max Jaig S Caig
Vo > 0.
(11)
Assumption 1 says that the span of the significant components, namely those with |0] 2 5, grows at most polynomially in 1/8. This assumption is mild and holds for many practical settings, such as cases considered in Example 2.3 (x p+1
2q for the first kernel). In other perspective, it imposes
mild condition on the misalignment between the ordering of the truth signal and the ordering of the eigenvalues, where k. measures the misalignment between the ordering of f and the ordering of itself. Then, the following theorem characterizes the generalization error of the resulting estimator.
Theorem 3.1. Consider the sequence model (5) under Assumption I Fix >3 j for some 7 > and let 00p be the estimator given by the gradient flow 8 stopped at time t. Then, there exists some we have
constants B1, B2 >> such that when Bye" St S B2e
ER(0OP,0") 2 [o(e)+ 1/7 (eln(1/e) as e -
(12)
3.2 Towards deeper over-parameteriiztion
Let us further introduce deeper over-parameeterizatio by adding extra D-layers:
0z = ,,bb 83
(13)
and consider the gradient flow
à = - Vaj Ljj
b, = Vo, B3 = - L,j- a,(0) - 1/ (0) by > 0, 8, = O,
(14)
where by is the common initialization of all by. We remark here if one considers the over- parameterization 8, a.b,,....... ...11..bbpp ,3, with the same initialization by. by. k 1,..., D, then by, remain to be the same by symmetry, so this is equivalent to our parameterization 0, = a, 3,. The following theorem presents an upper bound for the generalization error by this deeper over- parameterized gradient flow.
Theorem 3.2. Consider the sequence model (5) under Assumption I Fix A3 x for some y > 1 and let Op..D be the estimator given by the grudient flow 14 stopped time L. Then, by choosing
by = cD'z, there exists some constants B1, B2 > such that when B < bp < Bye we have
ER(OOn.D. ,0)) S 2 [[((e) + stZ + V (eln(1/e) as c 0.
(15)

---

3.3 Discussion of the results
Benefits of pavemtarratttiioatoonn Theorem 3.1 and Theorem 3.2 demonstrate the advantage of ave-parraeterizttionn in the sequence model. Compared with the vanilla fixe-eigenvaaues gradient gradient descent method can significantly improve the
descent method, the over over-parameterizer generalization performance by adapting the eigenvalues to the truth signal. For a more concrete example, if we consider the setting of Q plugging (TO) yields the following corollary.
Corollary 3.3. Consider the over-paramelerized gradient descent in @8 (setting D = or 14 g+1
Suppose holds and ) x "= for > 1 and y 2
Then, by choosing bo x 2iI (if #0)
D42'
2D 2
and t = we have
ER(OOD.D 0") 2 CF (1n(1/c) as
0.
(16)
2p
In comparison, the vanilla gradient flow method yields the rale
Ignoring the logarithmic factor, Corollary 3.3 shows that the over peeepparamttriieed gradient descent method can achieve a nearly optimal rate eaf1, while the vanilla gradient descent method only achieves the rate e E The improvement is significant when is large, which corresponds to the case that the misalignment between the ordering of the truth signal and the ordering of the eigenvalues is severe. Moreover, if we return to the low-dimensional regression function in Example 2.2 with the isotropic kernel ki, we can see that while the vanilla gradient descent method suffers from the curse of dimensionality with the rate 2t 21+dd the over-paramen prammeterreeiiioonnn leads to the dimension- free rate Therefore, the peer-arramttrizatioon significantly improves the generalization performance. 21-4-6
2p
Learning the eigenvalues To further investigate how the eigenvalues are adapted by over- parameterized gradient descent, we present the following proposition.
Proposition 3.4. Given the same conditions as in Theorem 3.2 or Theorem 3.1 (with D = 0 and b/ = 1 for Theorem 3.1). the term learning the eigenvalues ay (t)6,(( (t) is nen-decregiing in t for each j. Moreover, letting d E (0, 1), when is small enough, the following holds at time t chosen as in Theorem 3.1 or Theorem 3.2
Signal component: There exist constants C, > 0 such that for any component satisfying 8 2 CeIn(1/c), it holds with probability at least 1 5 that
a (t)bb(()) 2 c00
(17)
Noise component: There exist constants e, C, > such that, for any component where 031 S and Aj S ce ntzz it holds with probability at least 1 - that
(,(t)bf())) S CXtedia (0)6()))
(18)
From this proposition, we can see that for the signal components, the eigenvalues are learned to be least constant times a certain power of the truth signal magnitude. Thus, wee-parameterized gradient descent adjusts the eigenvalues to match the truth signal as expected. In the case of noise components, although the eigenvalues are still increasing due to the training process, the eigenvalues do not exceed the initial values by some constant factor, provided that X; is relatively small. This finding suggests that werrpaaaaeterizze gradient descent effectively adapts eigenvalues the truth signal while mitigating overfitting to noise. We remark that when X is relatively large, the method
still tends to overfit the noise components, contributing an extra e -4= 1 term in the generalization error, but this term becomes negligible for large y Moreover, also remark that there is In 1 1/e) gap between the signal and noise components. This is because the signal and the noise can not be distinguished for the components in the middle.
A notable advantage of the over-parameterized gradient descent method is its adaptivity. Consider the scenario described by ( vanilla gradient descent requires the selection of stopping time x (2x9))((p+)) to achieve the optimal convergence
Adaptive choice of the stopping time
7

---

rate. However, this choice of stopping time critically depends on the unknown parameters p and q of the truth parameter, posing significant challenge practical applications. In contrast, the premmerrameterized gradient descent only need to choose the stopping time as = BTž which does not rely on the unknown truth parameters, while still achieving the nearly optimal convergence rate. This independence from the truth parameters allows the over-parameterization approach to adaptively accommodate any truth parameter structure by employing a fixed stopping time, without the need for prior knowledge about the truth function's 's properties.
Effect of the depth The results in Theorem 3.2 also show that deeper weer-parametrrization can further improve the generalization performance. In the two-layer peee-parameteiizaionn, the extra term e- 1/2 in Theorem 3.1 emerges due to the limitation of the adapting large eigenvalues. With the introduction of depth, namely adding extra D layers to the model with proper initialization, this term
can be improved to piz } in Theorem 3.2 This improvement suggests that the depth can refine the model's s sensitivity to eigenvalue adaptation, enabling a more nuanced adjustment to the underlying signal structure. This finding underscores the importance of model depth in enhancing the learning process, providing also theoretical evidence for the empirical success of deep learning models.
Comparison with previous works We will compare our results with the existing literature (hao et al. 2022 Li et al. 202 Vaškevičius et al. [2099] on the generalization performance of over- parameterized gradient descent the following aspects:
Problem settings: While the existing literature (Zhao et al. 2022 Li et al.
202 aa
Vaške
vičius et al. 2019] investigate the realms of high-dimenstonal linear regression, focus- ing on implicit regularization and sparsity, the present study dives into kernel regression and its approximation by Gaussian sequence models, emphasizing the adaptivity of over- parameterization to the underlying signal's structure, a leap towards understanding model complexity beyond mere regularization. Moreover, while the literature primarily focuses on the setting of strong signal, weak signal and noise separation, we consider the more general setting of the sequence model with arbitrary signal and noise components.
aver-parametteizationn setup: The existing work Zhao al. [0022] considers the over- parameterization setup by the two-layer Hadamard product = a where the initialization is the same for each component that a()) = al and b(0) 0. In comparison, our work considers initializing the eigenvalues (0) = x differently for each component. Moreover, we extend the over-pare parameterization to deeper models by adding extra D layers. Although Vaškevičius Vathough/Wskkkvvvdusss... et al. [2019] and the subsequent work|Li et al. [2021a] also consider the deeper over-parrmetterzzatonn, their over-parameterization
= H p@D with u(0) v(0) al. Unfortunately, though being easy to analysis because of the homogeneous initialization, this setup could not bring insights into the learning of the eigenvalues, which is the key to our results. Furthermore, the analysis for Theorem 332 involves the interplay between the differently initialized aj and bj. so our analysis is more involved than the existing works. We also remark that although we only consider the gradient flow in the analysis, the results can be extended to the gradient descent with proper learning rates.
in the form
Interpretation of the ver-paraaeeterizatio:: The previous works view the over- parameterization mainly as mechanism for implicit regularization, while our work provides a novel perspective that over-paramtterizzaionn adapts to the structure of the truth signal by learning the eigenvalues. Our theory also aligns with the neural network literature (Yang and Hu 2022 Ba et al. 2022]. where over- wee--aarmeterizationn with gradient descent is known to be beneficial in learning the structure of the target function.
Connection to sparse recovery: Our results can be phrased for the setting of high dimen- sional regression with sparsity. Taking sparse signal (07))21, e.g., 07 1 for j S. |S| = 8 and 0; = 0 for j & S, we find that (<c) = s and Vc() 0. Consequently, ignoring the extra error term, the resulting rate obtained by Theorem 3.1 or Theorem 3.2 is ((s/n) (ignoring the logarithmic factor). This rate coincides with the minimax rate for sparse recovery in high-dimensional regression.
8

---

3.4 Proof outline
In this subsection, we will provide an outline of the proof of Theorem 3.1 and Theorem 3.2 For the detailed proof, we refer to Section for the analysis of the gradient flow equation and Section for the generalization error.
Equation analysis
The proof of Theorem 3.1 and Theorem 3.2 relies on the analysis of the gradient
flow (8) and (14) for each component j. For notation simplicity, will suppress the index in the following discussion. Firstly, the symmetry of the equation allows us to consider only the case > 0.
Then, one can find that
d a² dt D dt
d
8=
d b² 20(= - 0).
dt dt
so we get the conservation quantities (t) (t) + À and (² (t) bj. Consequently, for the case 0, we can obtain the explicit gradient flow of #:
= V at + 40 0), 0(0) = O.
Since v /aj + 402 can be bounded by multiple of az 20, can consider the other equation i (a 20) (2- 0), which admits a closed-form solution.
For the case D 2 1, the equation is more complicated. We will apply a multiple stage analysis concerning both the effect of a()) and b(L).
The generalization error In terms of the generalization error, we first separate the noise case when 151l 2 |0 and the signal case when Kε, < [0///2. /2. For the noise case, apply the analysis of the equation to show that 8 (t) is bounded roughly by >; for our choice of t. Moreover, the fact that Xy is summable ensures that error of these noise components does not sum up to infinity. On the other hand, for the signal case, if |03] 2 e eIn(1/e), we can show that our choice of t allows (t) to exceed 2/ 2/2 and converge to 2 close enough, so the error in these components is only caused by the random noise and sum up (c). In addition, the remaining signal components contribute to the error term (e (n(/e)) Summing up these two terms, we can obtain the desired generalization error bound.
4 Numerical Experiments
In this section, we provide some numerical experiments to validate the theoretical results. For more detailed numerical experiments, please refer to Section C
We approximate the gradient flow equation (22) and 330 by discrete-time gradient descent and truncate the sequence model to the first N terms for some very large N. We consider the settings as in Corollary 3.3 that 0* is given by (4) for some p >> and q 2 We e2 n where can be regarded as the sample size, and consider the asymptotic generalization error rates as grows.
We first compare the generalization parameterized gradient descent (OpGD) in Figure [ on page [0] The results show that the over- parameterized gradient descent can achieve the optimal generalization eπror rate, while the vanilla gradient descent suffers from the misalignment caused by > and thus has slower convergence rate. Moreover, with a logarithmic least-squares fitting, we find that the resulting generalization error rates also match the theoretical results in Corollary 3.3 (0.5 for OpGD and 0.33 for vanilla GD).
rates between vanilla gradient descent and over-
(3)(())) (t) over time as discussed in Proposition 3.4 The results are shown in Figure on page 10 We find that the eigenvalue terms can indeed adapt to the underlying structure of the signal: for large signals, the eigenvalue terms approach the signals as the training progresses, while for small signals, the eigenvalue terms do not increase significantly. Moreover, find that deeper over-paranen parameterization reduces the fluctuations of the eigenvalue terms for the noise components, and thus improves the generalization performance of the model.
Additionally, investigate the evolution of the eigenvalue terms a, (t)6,
In summary, the numerical experiments validate our theoretical results and provide insights into the adaptivity and generalization properties of the over-parameterized gradient descent method.

---

Generalization Errors; optimal rate=0.500
Generalization Errors: optimal rate=0.550
-0.9
Verlla 6D
-2.
Varilla
0.374kgm01025
0.3341bgh+
-1.0
0p5D
0p50
logerr - 0.52kkgo.
-100
logErr
0.449logm 0.55
logi genseatzatie entr
-1.1
111
-1.2
-12-
-1.3
-13
14.
-1.
-15
2000
10000
2000
10000
(bgarthhmie)
(bgarthmmi)
Figure 1: Comparison of the generalization error rates between vanilla gradient descent and over- parameterized gradient descent (OpGD). We set = 1 and q = 2 for the truth parameter 0", and y 1.5 for the left column and for the right column. For each n, we repeat 64 times and plot the mean and the standard deviation.
Model 8- ab& (D
t=0
t-150
t=300
X
K
-10
log15 mogritude
-15
2.0
-25
1
1.00
120
1400
160
1.0
200
100
120
140
160
150
200
100
120
1.50
160
180
200
Indle
index
Indect
Figure 2: The evolution of the trainable eigenvalues (t)6, (t) over the time across components j 100 to 200 for D The blue line shows the eigenvalues and the black marks show the non-zero signals scaled according to Proposition 3.4 For the settings, we set 1, 2 and 2.
5 Conclusion and Future Work
In this work, we studied the generalization properties of weer-parameterized gradient descent in the context of sequence models. We showed that the over-parameteriizaion method can adapt to the underlying structure of the signal and significantly outperform the vanilla fixed-eigenvalues method. These results provide a new perspective on the benefits of over peee-aaramttrizztiion and offer insights into the adaptivity and generalization properties of neural networks beyond the kernel regime.
However, there are also limitations of this work and many interesting directions for future research. For example, one can directly consider the pverpaaraetteiizaaion in the kernel regression by replacing the feature map & (x) (2)/2e, (x());z1 with the learnable one Φ(x; a) (1,e,(:));21 where
aj's 's are learnable parameters initialized by (0) x//²2 However, the analysis would be more challenging since now the components are mutually coupled in the gradient flow dynamics.
Perhaps one of the most interesting directions is to study how the wwe-parramttriization method can also learn the eigenfunctions the kernel during the training process, which leads the truly "adaptive kernel method"" We believe that future studies on this topic will provide deeper theoretical understanding of the success of neural networks in practice.
10

---

Acknowledgments and Disclosure of Funding
Qian Lin's research was supported in part by the National Natural Science Foundation of China (Grant 92370122, Grant 11971257),
We thank the anonymous reviewers and area chairs for their valuable comments and suggestions. Their feedback helped us improve the quality of the paper.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization, June 2019. Uttpttpp:/aarxi http://rxii..oggabbb//aaaaa
03962
Ingo Steinwart (auth.) Andreas Christmann. Support Vector Machines. Information Science and Statistics. Springer- Verlag New York, New York, NY, 1 edition, 2008 ISBN 0-387-77242-1 0-387-77241-3 978-0-387--7241-77 978-0-387-77242-4. doi: 10. 10110079988-00887-7722444
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization Advances in Neural Information Processing Sys-
in deep matrix factorization.
tems, 32, 2019a. URL. https://proceedings www.gg..n.urr.... pc/pppae c0c783b5f codf 450
html
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grainee analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pages
PMLR, 2019b.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019c. URLhttts:://rrooeeiiii
Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation, May 2022.
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms learning theory. Journal of complexity, 23(1):52-72, 2007.
2007. doi: 10.
0000
Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. arXiv preprint arXiv:2009. 14397, 2020.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pchlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In Proceedings of the 37th International Conference on Machine Learning, pages 1024-1034. PMLR, November 2020. URL WtRLitttss///prceeeeei
mlr. mlr. wwwpprsssvu119/bbodelllooot html
Lawrence D. Brown, T. Tony Cai, Mark G. Low, and Cun-Hui Zhang. Asymptotic equivalence theory for nonparametric regression with random design. The Annals of Statisties, 30(3):688-707) 2002. ISSN 0090-5364. doi: 10. /t/////00002227883388
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares al- gorithm. Foundations of Computational Mathematics, 7(3):311-66,, 2007. doi: 10. 10.1007/ $10208-006-0196-8.
Yunlu Chen, Yang Li, Keli Liu, and Feng Ruan. Kernel learning in ridge regression "automatically" yields exact low rank solution, October 2023.
Hung-Hsu Chou, Carsten Gicshoff, Johannes Maly, and Holger Rauhut. Gradient descent for deep matrix factorization: Dynamics and implicit bias towards low rank, August 2023, URL
13772
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131-10143, 2021.

---

Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterrieed neural networks. arXiv preprint arXiv:1810.02054, 2018.
Jianqing Fan, Zhuoran Yang. and Mengxin Yu. Understanding implicit regularization over-
parameterized single index model, November 2021. URL http:://axxiv.rr/abbaa org.ab////////
08322
Simon-Raphace Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least- squares algorithms. Journal of Machine Learning Research, 21:205:1 2020. URL https;
www www.seemanticschol.aa. org.
Khashayar Gatmiry, Stefanie Jegelka, and Jonathan Kelner. Optimization and Adaptive Generalization of Three layer Neural Networks. In International Conference on Learning Representations, October 2021. htttt:ttpp//peeeeee http://ppeeerreeeeeettffrrrrrraa wtt.:///eoooootrriaaaaaaaAAAa
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the Laplace and neural tangent kernels. In Advances in Neural Information Processing Systems, volume 33, pages 1451-1461, 2020.
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.
Peter D. Hoff. Lasso, fractional norm and structured sparse estimation using Hadamard product parametrization. Computational Statistics & Data Analysis, 115:186-198, November 2017. ISSN 0167-9473. doi: 10.1016/j.csda.200 wtt.:/csaaa.a...... 07.11.70.7...
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL http://poeceeeeeee ings. wwwiiinnnnnnnuripe cw/ppppee/01///////ee// 5a4be If 4004444466600000666666604442022 5a Paper .pff
lain M. Johnstone. Gaussian estimation: Sequence and wavelet models. 2017.
Chris Kolb, Christian L. Müller, Bernd Bischl, and David Rügamer. Smoothing the edges: A general framework for smooth optimization in sparse regularization using hadamard overparamettrization. arXiv preprint arXiv:2307.03571, 2023.
Masayoshi Kubo, Ryotaro Banno, Hidetaka Manabe, and Masataka Minoji. Implicit Regularization in aver-parameterized Neural Networks, March 2019. URL http:://axixy .owy.orrggg org/ ab9/
01997
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL ht p/poceeedds/soooeeeng http://prooeddnnneeee.e........e
Abstratt.ttttttttttt
Daniel LeJeune and Sina Alemohammad. An adaptive tangent feature perspective of neural networks, August 2023. URt.http://arzii..rrrg www.o//g/r...o..oooooo// 15478.
Jiangyuan Li, Thanh V. Nguyen, Chinmay Hegde, and Raymond W. Wong. Implicit sparse regularization: The impact of depth and early stopping, October 2021a. http:/// org/abs//108..5574
Yicheng Li, Haobo Zhang, and Qian Lin. On the asymptotic learning curves of kernel ridge regression under power-law decay. In Shirty-Sevntth Conference on Neural Information Processing Systems, 2023a. URR. net. /tt
Yicheng Li, Haobo Zhang, and Qian Lin. On the saturation effect of kernel ridge regression. In International Conference on Learning Representations, February 2023b. URL ht/ openreview net ptst//fommmiddtt/ tF kYWs_Y
12

---

Yicheng Li, Weiye Gan, Zuoqiang Shi, and Qian Lin. Generalization error curves for analytic spectral algorithms under power-law decay, January 2024a.
Yicheng Li, Zixiong Yu, Guhan Chen, and Qian Lin. On the eigenvalue decay rates of a class of neural-network related kemnel functions defined on general domains. Journal of Machine Learning Research, 25(8)): 2024b. ISSN 1533-7928. URL URLhttt::/ httthtt/mmmmll //jmrr pwwpg//ap//////aee 125/23-055 html
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning, April 2021b. URL /RRp:ttt///a /bs/ 2012. 09839
Zhiyuan Li, Tianhao Wang. and Sanjeev Arora. What Happens after SGD Reaches Zero Loss? Mathematical Framework, July 2022. URL.ppp://arrivv.orr//b////
06914
Junhong Lin, Alessandro Rudi, L. Rosasco, and V. Cevher. Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Applied and Computational Harmonic Analysis, 48: 868-890, 2018 doi: 10. (ot.f..cca..218.09.....
Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: A taxonomy of overfitting, July 2022.
Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, and Daniel Soudry. Implicit bias of the step size in linear diagonal neural networks. In International Conference on Machine Learning. pages 16270-16295. PMLR, 2022.
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit Regularization in Tensor Factorization, June 2021. URL htttt:////x/:iiti httpt:::/aaxxi.or//bbbbaaa ortpa///1//aaa/222222 altp//2./22..... 2192009977
Mariaa Seleznova and Gitta Kutyniok. Analyzing finite neural networks: Can we trust neural tangent kernel theory? In Mathematical and Scientific Machine Learning, pages 668-895. PMLR, 2022.
URL BRRLhttpp://proceeediii
mlr, press hetps//ll///s/// (eee1///eeeeeoovaa222 html
Ingo Steinwart and C. Scovel. Mercer's Theorem on General Domains: On the Interaction between Measures, Kernels, and RKHSs. 2012. doi: 10. 00010077500066--22-1555333
Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal Rates for Regularized Least Squares Re- gression. In COLT, pages 79-93, 2009. papers/038.pdl
httt:p:/www..eree http:://www.errrinhhhhorrr.o.og
Tomas Vaškevičius, Varun Kanade, and Patrick Rebeschini, Implicit regularization for optimal sparse recovery, September 2019. URL http: wrw. abs/ 1909.05122
Loucas Pillaud Vivien, Julien Reygner, and Nicolas Flammarion. Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation. In Proceedings of Thirty Fifth Conference Learning Theory, pages 2127-2159. PMLR, June 2022. _ httpa://
proceedings.co mlr..mmmr... wttpeeiiinn.mmr...pe/ss////eee www....eee//.////iiviii./ ppress/v17//viviee222.. htt.r///vvviee2aa.... html
Jonathan Wenger, Felix Dangel, and Agustinus Kristiadi. On the disconnect between theory and practice of overparametrized neural networks, September 2023. URL URL http:://rxiv.. wrg./bs......... abs/
2310.00137
Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Proceedings of Thirty Third Conference Learning Theory, pages 3673. PMLR, July 2020. URL
mlr press litess//125//oocoo wt1/5///wooooorhhhaa...... html
Greg Yang and Edward J. Hu. Feature learning in infinite-width neural networks, July 2022.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26:289-318 -35,, August 2007. doi: 10.1007//00065-0066 2-666663---000
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. unifying view on implicit bias in training
linear neural networks, September 2021. URL http: http:://arre //tpx//aavvv///////a//eee/aaae org/ abs hts///bs//00000/ 2010. 02501
13

---

Haobo Zhang, Yicheng Li, and Qian Lin. On the optimality of misspecified spectral algorithms, March 2023.
Peng Zhao, Yun Yang, and Qiao-Chu He. High-dimensional linear regression via implicit regu- larization. Biometrika, 109(4):0033-1046, November 2022. ISSN 0006-3444, 1464-3510, doi: 10. 10099//boom///aaa100.......
14

---

Contents
Introduction
1.1
Our contributions
Notations
2
Limitations of Fixed Kernel Regression
3
Adapting the Eigenvalues by Over-parametteiration in the Sequence Model
3.1
Over-parameterized gradient descent
3.2
Towards deeper over-parameterizzaion
3.3
Discussion of the results
3.4
Proof outhine
4
Numerical Experiments
Conclusion and Future Work
10
References
11
Additional related works
17
Supplementary Technical Details
18
B.1
The connection between RKHS and the sequence model
18
B.2
The examples Section
19
B.2.1
Example 2.1
19
B.2.2
Example 2.2
19
B.2.3
Example 2.3
20
Detailed Numerical Experiments
21
Experiments beyond the sequence model
22
Testing cigenvalue misalignment on real-world data
22
Analysis of the gradient flow
26
D.I The two-layer parameterization
26
D.2 Deeper parameterization
27
E
Main proofs
31
Proof of Theorem 3.
31
Proof of Theorem
33
3
The absolute error term
35
Proof of Proposition] 3.4
35
Auxiliary results
37
15

---

NeurlPS Paper Checklist
38
16

---

A Additional related works
In this section, we will provide additional related works and further discussions.
Regression with fixed kernel The regression problem with fixed kernel has been well studied in the literature. It has been shown that with proper regularization, kernel methods can achieve the
minimax optimal rates under various conditions [Caponnetto and De Vito 2007 [Seeiwwart et al.
2009
Lin al. 2018 Fischer and Steinwart 2020, Zhang et al. [023] Recently, a sequence of
works provided more refined results on the generalization error of kernel methods [Li et al. 2023b
Bordelon et al. 2020 Cui et al. 2021 Mallinar al. 2022 Li et al. 2023a 2024a
The NTK regime of neural networks Over-parameterized neural networks are connected to kernel methods through the neural tangent kernel (NTK) theory proposed by [Jacot et al. (2018], which shows that the dynamics of the neural network at infinite width limited can be approximated by kernel method with respect to the corresponding NTK. The theory was further developed by many
follow-up works [Arora et al. 2019c]b] b. Du ct al. 2018 Lee et al. [019 Allen Zhu et al. 2019]. Also.
the properties on the corresponding NTK have also been studied [Geifman et al. 2020 Bietti and
Bach 2020 Li et al. 2024b].
over-parameterization as Implicit Regularization There has been a surge of interest under- standing the role of over- parameterization in deep learning. One perspective is that over- over-vveveaeee parameterized models trained by gradient- based methods can expose certain implicit bias towards simple solutions,
which include linear models [Hoff, 2017 Vaskevičius et al., 2019 Zhao et al. 2022 Li et al.
202 la matrix factorization [Gunasekar et al. [201 Arora et al. 2019a Li et al. 2021b Razin et al. 2021
Chou et al. 2023), linear networks Yun al. 2021 Nacson et al. 2022 and neural networks Kubo et al. 2019 Woodworth et al., 2020J. Moreover, variants of gradient descent such as stochastic
gradient descent are also shown to have implicit regularization effects (Li et al. 2022 Vivien et al..
2022]. However, most of these works focus only on the optimization process and the final solution,
but the generalization performance is not well understood.
Generalization Guarantees for Over wver-parameterized Models Being the most related to our work, a few works provided generalization guarantees for over-parameterizee models, which only include linear models [Zhao et al. 2022. Li et al. 2021a Vaškevičius et al. 2019] and single index model Fan
al., 202T]. In detail, the two parallel works Zhao et al.] [002 Vaskevicius al. 2019) studied
the high-dimensional linear regression problem under sparse settings and showed that a two-layer diagonal over- pee--parmeterized model with proper initialization and early stopping can achieve minimax optimal recovery under certain conditions. The subsequent work [Li et al. 2021a obtained similar
results for multi-layer diagonal vee-parraeetrizee models.
The adaptive kernel perspective The idea of an adaptive kemel has appeared in a few recent works in various forms [Cen et al. 2023 Gatmiry et al. 2021 Leleune and Alemohammad 2023
Yang and Hu 2022 Ba et al. 2022). which is also known as "feature learning". Notably. Gatmiry al.] [202]] showed the benefits brought by the adaptivity of the kernel on a three-layer neural network, which is similar to our work in the adaptive kernel perspective. However, our work and theirs consider different aspects of the adaptive kernel: while they considered an adaptive kernel space in the form of G K around the NTK space, we consider an eigenvalue-parann parameterized kernel space with fixed cigen-basis. We believe that these various results, including ours, will contribute to a better understanding of the generalization properties of over- wver-parameterized models well as neural networks.
17

---

B Supplementary Technical Details
B.1 The connection between RKHS and the sequence model
Diagonalized kernel gradient flow as sequence model Moreover, this connection can also be seen directly from the following. The Mercer's decomposition of the RKHS H. associated with the kernel k also provides series representation of the RKHS:
agrfer (az))21 E (a>2eee)
H =
(19)
where we denote by 6 = (a)))21 E== ag < =0). Therefore, by introducing the feature mapping & : X' - l2 defined by
(z) = (A (z)))2
(20)
we establish a one-to-one correspondence between a function f E H. in the RKHS and a vector 3 E e in feature space via fxx) = (.) 3) for E H and B E l Moreover, it is convenient to consider ((x) as column vectors and also define the feature matrix (x)) = (x1)....., p(xn)) for
X ( Fn). Then, the gradient flow 2 in the feature space 1 writes
1 B(t) - VcC - (X))((X B(I) + y.
(21)
Intuitively, since the j. 1-th entry
A Σ
( n
(x(x))(x)T)
((()))((())))
51
the law of large numbers implies that +. (x) (X) converges the diagonal operator A diag(A1, .2,...): moreover, since j-th entry
n
( (x(()))
Σ (ax)e, + n Σ (x,))
T2
the central limit theorem suggest that it can be approximated by A32y, where 2j = 0, + and E is normal random variable with mean zero and variance o² 2//n. Therefore, with these approximations, the equation can be diagonalized as
(t) = ~3 + 23 -t) - -, 2g).
Moreover, we can rewrite the representation
f(x) (1(x), 8) into
f Σ
AsB j=1
Σ
Oyej, 0, X3 3,.
/=1
Then, in terms of f, we have
=
This is exactly the vanilla gradient flow in the sequence model in Section 3 Furthermore, we can consider the parameterized feature map
2x (a)e,(#)),22
where a = (az)z2) We can consider similar gradient flow the feature space with both /3 and a trainable. Then, with similar diagonalizing argument, we can show that the corresponding gradient flow in the sequence model is just the over-parameterized gradient flow in (7). Similar correspondence can be established for the multi-layer models L
18

---

B.2
The examples in Section
2
B.2.1 Example
The deduction in Example 2.1 is straightforward. The series expansion (3) can be written as
{
= fze
Ej < <00 <00)
|7/l**
321
521
We recall that A1,1 jj j- and λ3.2 x x0 72, Let f Ej²1 fzey. Then, for 1,
f E [HRe] + Σ
( <00 =
Σ (1g) < 0
921
521
Consequently,
f E [H 1 + f E [H, for 8181 = 7282.
B.2.2 Example 2.2
We justify the claims in Example 2.2 Let us consider the torus T = 1-,, and the uniform
measure on T (namely μ(TT) 1). Let us recall that the multidimensional Fourier basis is given by 6m (z) = exp(in (m,z) for m zd.
The Sobolev space (TT) is defined via the Fourier coefficients
HT(TT) { IEL (
1f (1 + [|m]]]] < c0).
mEZd
which is equipped with the inner product (as thus the induced norm)
(.9) = Σ fmim(1 + ||m]]] 2)
mEZd
Now, we briefly show that H (Td) is an RKHS when s > d/2. suffices to show that f + f f(x) is bounded for each E Td [Andreas Christmann
2008]. Using the boundedness Φm. we have
Σ 1mmmml S meZd
Σ 1fml <
Σ
1 + [|m]]/"
Σ (1+ [|] mezd
mezd
mEZA
Now,
/ ZERR
(1 ( S / 00
a1+1m
(1+12)-8pp) dr.
mEZ4
Since the last integral is finite when s > d/2, we find that there is a constant C such that
Σ
15mmml S CIISlI
mc24
Therefore, the series expansion f(x) = Emeza (m)m(() converges absolutely and uniformly, and thus [f(x) & Emeze (m S CI showing that f <> f(x) bounded for each Td.
Moreover, it is easy to see from the Mercer's decomposition T and the power series expansion
3 that the kernel of H (TT) is given by k(æ, x') = Emezo (1 [|m]|]]]=a - (z)@m (x"), so its
cigenvalues are 2m (1 + |m -
19

---

To determine the eigenvalue decay rate of Am = (1 (1+ + |m|| )- after reordering them in decreas- ing order, suffices determine the count # (m Am 5): the eigenvalue decay rate is
# {m Am > 8} 8-1/3, see, e.g., Proposition A.1 in Li al. 2024a We have
# (m: Am > 5) # m (1+ || ) > o}
Voll x E R² (1 (x(²)= > 83)
Voll E RR |x| - }} = 8 20.
We consider a function (x) g(z1, Ido) with low-dimensional structure. Let denote by dd = (Z1...., Táo) and x>do = (I (1..-1....,,3 Ia) for simplicity. Then, the Fourier coefficients of f are given by
Jm = (s", 4m) (.(TT,)))
=2 J I g(.1.-.................. Fdo exp(in # exp(in (m>doo=<dd (ddo doyyo
2 2- Jro g( gx....... Ido) explin (mgdas add 5d
2 (2((-do) do) / Ts-do
exp(in (m>do; x> x>d dZ
9m.gi
1 {m= -0}-
show that
Imgga (0
m = (m 0). msdo E Zdo otherwise.
fm
We recall that g (I so
2 (1 + |l 11 < oc.
Σ
Imgid
ma E
To determine the smoothness of f on [Hen,] and (Hey]* following
we compute
Σ mml [1 + m [3]l
Σ
Imggo [[11+ + || [13)]]
mE2
(m msdo E210
Σ
Jomscal (1 || 13)r3
mcda EZ3
so f belongs to [H,,) and [Ha,,] 1 for = t/r
B.2.3 Example 2.3
We recall that
(i x (1+13/2 and { x for p> 020,
where (()) gives the descending order of (0 To compute the relative smoothness of f w.r.t.
dj.1 x x5 compute
Σ 121
Σ
Ois)
Σ (EG)))
E- 121
so we have 8 < p/(7) (but arbitrarily close) and the corresponding generalization error rate It P_ The generalization error rate w.r.t. AUy x xーー can be computed similarly.
20

---

C Detailed Numerical Experiments
In this section, we provide numerical experiments validate the theoretical results. The codes are provided in the supplementary material. We approximate the gradient flow equation (22 and (30 by discrete-time gradient descent with sufficiently small step size. Moreover, we truncate the sequence model to the first N terms for some very large N. We consider the settings as in Corollary 3.3 that et is given by (4) for some > 0 and q 2 1. We set e² = n where n can be regarded as the sample size, and consider the asymptotic performance of the generalization error as n grows. For the stopping time, we choose the oracle one that minimizes the generalization error for each method. We first compare the generalization error rates between vanilla gradient descent and over- wver-parameterizedd gradient descent (OpGD) in Figure 3 on page 21 The results show that the over pararettaaeeeeed gradient descent achieve the optimal generalization error rate, while the vanilla gradient descent suffers from the misalignment caused by > 1 and thus has a slower convergence rate. Moreover, with a logarithmic least-squares fitting, find that the resulting generalization error rates are consistent with the theoretical results in Corollary 3.3 (0.5 for OpGD and 0.33 for vanilla GD); the oracle stopping times for the over- peeemaarametee gradient descent also match the theoretical value (0.5).
Generalization Errors; optimal rate-D.500
Oracle stopping
-0.9
Varilla GD
logerr 0.374kkgm 0.29
-1.0
lagErr 0.533kgm400.65
1m gen the
Verilla GD
log[=10030go 0.53
Opti
2.5
0050-8 -0.1
(lganthheic)
(ogarthmmcc)
Generalization Errors; optimal 0.50=
stopping
Vanill GD
log 0.341kgn 0.21
6-
IngErr 0.609kgn++0.55
log min gae step
gencrataaiion
Vanilla SD
0,17og + 2.02
logr 0.51lggn
-1.5
2000
10000
2000
20000
(sgartheic)
Osgarthhmici
Figure 3: Comparison of the generalization enror rates between vanilla gradient descent and over- parameterized gradient descent (OpGD). We set p and q for the truth parameter 0" The left and right columns show respectively the generalization error and the orcale stopping time with respect n. For the upper row, we the eigenvalue decay rate 1.5; for the lower row, set 3. For each n, we repeat 64 times and plot the mean and the standard deviation.
Furthermore, we investigate the generalization performance of over-parameterizee gradient descent (also with deeper parameterization) for different settings of the truth parameter 0", the eigenvalue decay rate 7 and the depth D. The results are reported in Table C page 22 We find that the generalization error rates are in general consistent with the theoretical results in Corollary 3.3 while
21

---

p
0.6 (r" 0.37)
p
(r"
0.5)
p
(r" 0.75)
1.5
Q=2
9=1
1.5
9=2
2
0= 1.5
2
1.1
0.38
0,40
0.50
0.50
0.45
0.48
0.78
0.69
0.67
2
0.36
0,41
0.52
0.49
0.46
0,50
0.80
0.73
0.72
0.36
0.41
0.52
0.48
0.46
0.50
0.76
0.73
0.74
Table Convergence rates of the over-parameterized gradient descent (8) under different settings of the truth parameter p, and the eigenvalue decay rate 7, where r" is the Ideal convergence rate. The convergence rate is estimated by the logarithmic least-squares fitting of the generalization error with ranging from 2000, 2200, 4000, where the generalization error is the mean of 256 repetitions.
p=
0.6 = 0.37)
p
==
1r = 0.5)
p=3 = 0.75)
7
=
g = 1.5
q= 2
q=1 1
g = 1.5
9 9=2
q q=1
q q= 1.5
q=
1.1
0.36
0.40
0.52
0.49
0.46
0.49
0.79
0.73
0.72
D = 1
2
0.36
0.40
0.52
0.48
0.46
0.50
0.76
0.73
0.73
3
0.30
0.32
0.38
0.45
0.41
0.44
0.75
0.73
0.74
1.1
0.34
0.39
0.49
0.46
0,44
0.48
0.76
0.74
0.75
D
2
0.35
0.40
0.51
0.47
0.45
0.49
0.74
0.73
0.73
3 0.36
0.40
0.51
0.48
0.46
0.50
0.74
0.73
0.73
Table Convergence rates the over-parameterized gradient descent The settings are the same as in Table C on page
14
with D and
D =
there are some fluctuations due the finite sample size. Comparing the results for y 1.1 across depth D = 0. D = 1 and D = 2, we see that the method with D = 0 has the slowest convergence rate, while the method with D 2 has the fastest convergence rate, justifying that deeper parameterization can improve the generalization performance. In summary, the numerical experiments validate our theoretical results.
Additionally, we investigate the evolution of the eigenvalue terms a, (t)) over time as discussed in Proposition 3.4 The results shown Figure on page 23 We find that the eigenvalue terms can indeed adapt to the underlying structure of the signal: for large signals, the eigenvalue terms approach the signals as the training progresses, while for small signals, the eigenvalue terms do not increase significantly. Moreover, we find that deeper over- parameterization reduces the fluctuations of the eigenvalue terms for the noise components, and thus improves the generalization performance of the model.
C.1 Experiments beyond the sequence model
We also explore the adaptivity of the over-parameterized gradient descent beyond the sequence model. Let us consider the diagonal adaptive kernel method by parameterizing the feature map with ( a) = (aye,(2) ( introduced in Section 5
We use the setting in Example 2.2 where the eigenfunctions are the trigonometric functions. In particular, we consider the truth function (z) sin(7.3 sin(7.5rrz with (I1, x2) E R22 We present the generalization еттоr curve of single trial and also the generalization error rates with respect the sample size n in Figure [ on page 24 The result also shows the benefit of over-parameterization in adapting to the underlying structure of
the signal.
C.2 Testing eigenvalue misalignment real-world data
In this section. we provide additional experiments to test the eigenvalue misalignment phenomenon on real-world data. Recalling Example 2.2)aam and Example 2.3] we know that the misalignment happens when the order of the eigenvalues of the kernel mismatches the order of coefficients of the truth function. Therefore, to test the misalignment, we compute the coefficients of the regression function over the eigen-basis of the kernel and examine whether the coefficients decay in the order given by the kernel. For the eigen-basis, we use the multidimensional Fourier basis (the trigonometric functions) considered in Example 2.2 where the order is given by the descending order of Xm (1+ (1+||m||3) ))
22

---

Generalization eiror
D-0
D-1
D
1010
10
Model & aB
t=0
t-
t=100
X
X
-1.25
1550
1010
1.75
Mu Up
100
120
140
160
180
200
100
120
140
160
200
100
120
140
150
180
200
indio
indux
index
Model abp (D 1)
t-0
t- 150
t-300
X
-10
log15 maghitude
-2.
-25
Ned 1 1
100
120
140
360
180
200
300
120
140
360
150
200
100
120
140
160
180
200
Indles
indse
Index
Model ab") (D-
t-0
t-350
t-700
-1.0
1.5
kg10
Mi
1
-30
100
120
140
160
180
200
100
120
140
160
180
200
100
120
140
160
180
200
Indix/
Indox
Indox
Figure 4: The generalization error as well as the evolution of the eigenvalue terms a, (t))
over the time The first row shows the generalization error of three parameterizations D D= 0, 1.3 with respect to the training time t. The rest of the rows show the evolution of the eigenvalue terms a,(t) (t(t)b(() (t) over the time f. For presentation, we select the index j 100 to 200. The blue line shows the eigenvalue terms and the black marks show the non-zero signals scaled according to Proposition 3.4 For the settings, we set p = q = 2 and 7 =
23

---

training time
Generalization vs.
-0.4-
peresiieettnn
+
Rood carsel
Emer
-0.8-
log fir -.31logn--.4
adept
13-4
1.9
-3.33lop--
Facd kome
-1.2
Dieg sdept
Dieg adapt DD-11
-144-
Ding adopt DD
160 140
220
250
280
310
310
370
400
Taining (lgg)
D. Doog nolgg--thmii #thmiil
Figure 5: Comparison of the generalization error between the fixed kernel gradient method and the diagonal adaptive kernel method. The left figure shows the generalization error curve of single trial. The right figure shows the generalization error rates with respect to the sample size n.
We consider the two real-world datasets: "California Housing" and "Concrete Compressive Strength". compute the empirical inner product of the regression function with the Fourier basis functions up to certain order. Then, we plot the coefficients in the order given by the kernel. The results are shown in Figure on page 25 The figures show that the empirical coefficients exhibit 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.
24

---

Fourier Coefficients in the Kernel's Order
2.0
1.5
1.0
0.5
0.0
Fourier Coefficients in the Descending Order
2.0
1.5
1.0
0.5
0.0
20000
40000
60000 80000 100000120000140000
Fourier Coefficients in the Kernel's Order
30
10
0
Fourier Coefficients in the Descending Order
20
2000
4000
6000
8000
10000
12000 14000
Figure 6: The empirical coefficients of the regression function over the Fourier basis for the "California Housing" dataset (upper) and "Concrete Compressive Strength" dataset (lower). Note that we take different numbers of Fourier basis functions for the two datasets for better visualization.
25

---

D Analysis of the gradient flow
D.1 The two-layer parameterization
Let us consider the gradient flow considered in 8 where we remove the subseript j for notational
simplicity. Let T. 20 z)² and f a,3. We interested in the gradient flow:
á = V L = 3(z -0),
8 V p L a(= -)).
(22)
(0)) = x > 0, B(0) = 0.
Symmetry of the solution We can find that the solution of the equation for 2 < 0 can be obtained by simply a(t), -Bt)) for the positive signal case of -2 > O. Therefore, only need to consider the case of 2 > 0. In this case, it is obvious that at)) ((t) and @(t) are all non-negative and increasing.
Gradient flow of 9 Now notice that
1 d
1
a 82 = =aβ(=- 106--)
2 di 2dl.
(t) (t) -2 =
(23)
Using this conservation quantity, we can prove the following estimations:
a 8
(24)
0 0 03 = = -
Moreover, the derivative of 0 writes
a 0 (a² + 3² - 0). 4
Using a² + - for 8:
v22 402, we conclude the follow explicit equation
=
402 0)- X2 /
(25)
Then, have the following approximation of the solution.
Lemma D.I. Let us consider the gradient flow (25 and
i = (A 210) 0). 0(0) = 0.
(26)
dt
Then we have
0 x 0(t/V2) < 0(1 < 50 == if 2
(27)
0 0(t/ 2 0(t) 2 01) if 2 5
Moreover, 26 is solved by
A(E - 1) 0(1)
E = exp((2)=) A)().
(28)
2| + XP
Proof. It suffices to consider the case = 2 a(t), 3(t) are non-negative. Then, using the elementary inequality
easy to see from the gradient flow (2) that both
2 (A+ + 2x) S v 4x2 < X + 2x,
have
1 (A+ 2x) =)
x) )) (2)22) x).
-
Then, the comparison principal ordinary differential equation yields is straightforward.
The verification of 28
26

---

D.2 Deeper parameterization
Now let us consider the deeper parameterization of the form
0 ab 3,
(29)
where a, b, 3 are all trainable parameters, and the gradient flow
à L.L B(= 0),
VoL = D-b -3(((= - 0),
(30)
8 V&L - ab (z - 0).
(()) x > 0, ((0) bo > 0, ((0) =
Main idea We provide the main idea of analyzing the gradient flow (30) here. Using the conser- vation quantities, we can first focus on the equation B. For the initial stage when is relatively small, (() only grows linearly in L. Next, when (()) exceeds a certain threshold depending on the initialization (and also the interplay between X, and bo), ((1) grows exponentially in 4, provided that ((t) S z/2. Thus, consider directly the equation of and show that O(t) converges to 2 exponentially fast.
upper bound the hitting time of 0(t) to z/2. Finally, when 0(t) 2 z/2,
Symmetry of the solution Similar to the two-layer case, we can find that the solution of the equation for = < 0 can be obtained by negating the sign of (()) for the positive signal case. Therefore, will focus on the case of 0 where a(t), b(t), B(t) and thus 0(t) are all non-negative and non-decreasing.
Conservation quantities
Similarly, we have
d 8² 32 = 0(2 - 0).
d²
(31)
2 dt
2D dt
2
SO
a = +A+ 32)
(b D33)
(32)
Using these conservation quantities, we can prove the following estimations in terms of 3:
min(X ,) S a v ma 8), min(bo. vD3) < b S v2 max(bo. vD3).
(33)
The evolution It is direct compute that
θ àbD 3 + aDbD-163 + ab
[(b 3)2 + (Dab 3)² + (ab D)] (z 0)
(34)
@2 2 B 8-2) 0).
Auxiliary notations Let us introduce
(1 inf { 2 0: B(t) 2 x+
( inf { 0: B(t)(t)= 2 bo/ .b/VDD.
(35)
Tesc = min((()) (?(),
T = inf (1 2 0: 0(1) 2 z/2]-
Lemma D.2 (Noise case). For the gradient flow 30 we have the initial estimation
[8()) < 2 الو X+ |z|t,
for is (),,((())rr())
(36)
[0(t)] < D+1 \b211
where
7())
(2 Dيو 1/ [|])]
TT2) = (2 D+1 VDA -1
(37)
27

---

Moreover, if X I bo/ DD then
[8(t) s A exp 22
2 up =1((t 7(1))))
for 1 i T
(38)
- [0(1) 2 2bl expl (2 2.3 68 101==(1-7710 -
where
bo VDA
T In
T
(39)
Proof. It suffices to consider the case > 0. Recalling 30
and 0 2 0, we have
< ab" P 2.
Using the upper bound in 33 when t S T namely when B(t) S X and vDB(t) S bu. we have
s (V22)) P= 2 2b
implying that
B(t) $ 141 1b zt, for S T
Therefore, we get the lower bound
T min(T T(
where (1) and (2) are defined by 37 in the lemma. Combining this again with the upper bound 2+3
that 0 - ab B < 2 ugby B when / < Tesc, we prove 33
For the second part, we consider the case Xá I bo/v/D In this case, we have T()) < ( and thus (1) > (1) from the above argument. Now, when E (T(), T(2)), turn the following equation:
B (V23)(V226)) = 2 23,
for tE
which yields
B(s B(5+7()) S ((T(1)) exp 2 D+1 up z
x exp
uy 28).
D
for 8 SE E (0, TT(2).
Comparing 3(s + T()) with bo/ /DD gives
1-2) - (1)) 2 2 D+1
In
bp
T
In
bp
VDA
VDA=
So
2 > (1) + +r In
bo
> 21)
(I+
bo
-1222)
VD
VDA
Therefore, the comparison principal yields
B(t) S X exp 2 D+1
to ( T(()))+) for t t T(122)
where we notice that the bound also holds for - (()) < T(1) since at that time 3(t) S A1, Finally, 38 obtained by using ab 3 < 2 P+1 for T(1),
bp 62 when E [rr(1, 2 while the bound also holds
Lemma D.3 (Signal case). For the gradient flow 30 we have;
X x bo/ VD, then
(D- D--D122/2) Diz
T < 2(bpl21)-
+
In
(40)
A
28

---

If 2 bo/v bo/VD, then
T $ 18 -111=) (1 + Rt),
(41)
where
(D)=1/2) D42
D 1,
R
b0
>>1 1.
D-1
Moreover, we have
1a 12-0 $ 2 2| exp ( (- D
(t - - for 2 T
D+3
(42)
Proof. It suffices to consider the case 2 > To provide an upper bound of the signal time T we observe that the lower bound in (33) implies a sufficient condition for 2/2 that
3 D 222
0 2 2
(43)
We first consider case that A < bo/vbDD Let us define T = 2(b8 2)- and suppose that T 2 2))"²) otherwise the statement (40) already holds. Then, we first have
B ab 2
Atbb for 1 s
(44)
This implies that
B(t) 2 1 1 st, for T 2
and thus
TW) $ T111 s T
Now, for / E we use the alternative bound a 2 3 to obtain
3bpp. 2, for te (7(1,777 T B 2 2
giving that
1 1110 28
8(s + T(1) 2 2 exp
for s s 10, -T(1)).
Comparing it with 43 we obtain
(D (D-D/2z/2)) D4z
(D-D/2//2) o
T - (1) < 200
(1)) In
A
A
which, together with the upper bound of (!)) proves
40).
The case that X 2 b /D is very similar. We define (2)
and suppose that
gis > ( Using the estimation (44) again, we get
( < (2) TTi
Now, when E (2), T we use > VD3 to obtain
B > 2
for te
[ reie].
This implies that for < 7 sig - T(2)
by
1
B(s+T(22) 2
exp
D=1,
VD
29

---

D-1
+(++ 2 (D-1/22b)-(0 -DD-1)
\= 28
if D>1.
2
Consequently, comparing it with 43) gives
(Dz/2) Diz
= =7 In (Dz/2) D+2
T - = 2 In
if D = 1,
bo
bo
T T(2) - D (V
1 T if D>L.
D
Finally, let us consider the convergence stage when 2 T Since it is always true that 0 < using the lower bounds (32). have
2 = = ab
B 2 8 B = D
implying that B < D 200+2) D+z t 7 we derive
Now, plugging this into (34) and noticing that 0 2 z/2 when
0a 2 Db- 3 )) 0) 2 (2-
1 2 D D=
D=7 (= 0)
4
D DDi2
0 2D13
(z 0).
4
Therefore, we have
2 - 2-0(s + Tols) S (2 ((Tdls)) exp ( D) 1o
2042
1
20+2
exp
17 1o
8
2
30

---

E
Main proofs
Notations
For notation simplicity, we will use C, denote generic positive constants that may change from line to line.
E.1 Proof of Theorem 3.1
We recall that
ER(0:0") = E >
(6, - 6
==1
Let us define the signal event
Sj = wi |6y1 < < 10011 sft = {w |ر,1 2 2 001
1
(45)
Then, on S3 we have 1091 S 12 S 2 0 while on 59 we have |zy| - 3|5ر1- Then, we decompose
(6, --- (0, - -,)) + (0, - -8
Moreover, when the signal is significant, use
(0, 03 2(0, 2 2(z 0 = =2(0, -2,) + =2531s,
On the other hand, when the noise is dominating, we apply
00; 1 S 20 2(0))
Summing over j and taking the expectation, we have
R(O0p, 0*) = E
03)- =
0 - 0,
+ E Σ
(0, - 03 sg
j=1
j=1
j=1
21E
00 1,,, + 2F
1 5g
+ 2
/ 1
5c + 21F
(0))²
sg
j=1
5=1
1=1
5=1
2E
() 1s, 107)
(46)
j=1
2E
03 %
(47)
j=1
80
2E
(03 23 1
(48)
j=1
Now, the first term (46), representing the absolute error, is controlled by Proposition E. that
1s, + (0))² [0 = 4 + [(C)
Therefore, we focus on the remaining two terms and obtain the estimations (49 and 5 in the following.
The noise term dominates. Applying Lemma D.I
The term (47 represents the extra error caused by the estimator when the noise obtain
0 = (0)( < [o(e)
2|2y| + 12,1 S
(y - 1)
1 22,,
exp exp (6615) + 22) on Sf.
31

---

Let us choose J = min (j :::1::14 X, 5 1//// Then, since t S BBe we have (15)1 + Az)t -
B2 B2s,///e++ + 1) and thus
E
Σ 03 s S C J2J
Σ
X +0) S C 3 33 S sce-111 -XSCC--r))CC>
J23
JzJ
where we notice that (xxp(C((())/))+++++ + C) is uniformly bounded by some constant for all j since each / is --sub-Gaussian. On the other hand, using the obvious bound obtain
| S l/&ا on sf. we
Σ jCJ
1g S C Σ BB S CeJJCe2
JEJ
Combining two terms, we conclude that
E
0
sg S C2-1/7
(49)
The signal term
The term 447) represents the approximation error when the signal is significant. D.I again derive
We apply Lemma
2 2|zz| + Aj
0,
23 S ((t/V2)- 2j = 2|2Ø| + X, exp (2|2,) 22)t/v2)
lzyl.
Using the fact that
\ 1
s |2 s 0107| on Sj. we derive that
(00) + 2,) (0, - -0 2 S eexp((22) (22 + 22)
(50)
Let us define eIn(1/e) 2 c. Recalling 9 and using Assumption I we have
S max (c) S Cc for j E Jaig S Jaig(() (c).
Now, if we take t t Bie-1 for some constant B1, since 10:| 2 for j E (v), we also have
1
10
V22 tc lnl/e 2 cB, In(1/c).
V2
and thus when j E (v).
In [ exp (1831\/22) 21 + 1/2 10 cB1 ln(c/)) C'nj 2 In
Consequently, as long as B₁ is large enough, we have
Xa exp (0/)1//2) 2 when E Jsig(v).
Therefore, plugging this into 50 we get
(
0 22)2,)2s S C 23 (2 + 2y)t/V2)
S &Cepp( (expp-((0)) + ())t(((2) (103) + 2,) (103)
and hence
Σ B(O, - 2,) < Σ
exp exp (-(00(10) + +2))4((22) (100) + +2,)
(V)
jE (u)))
00
< c Σ
[1107] + >1)1(] -2 *(001+ +2,2203
1=1
Ct- Σ
83 s C2.
1=1
32

---

On the other hand, with the trivial bound 02 33-2g 2g S 1zgl.
the remaining terms are bounded by
Σ
E(8, 22) 2s)
(07)² (2()..
((Jag(
(8-Jei(())
Therefore, we conclude that
00 - -2) S SCe + (eln(1/))).
(51)
1=1
E.2 Proof of Theorem 3.2
Following the same argument as the proof in the previous section, we introduce the events Sy and s
in (45) and decompose the error as in (46). (47) and (8)). Then, we will focus on the last two terms and derive the estimations (53) and (54) in the following. We recall that by x DTz and we choose such that Bie < bg < B2e 11 for some constants B1, B2 >> O that will be determined later.
Here, also note that the in correspondence to the component-wiss gradient flow considered in Subsection D.2, the initializations are given by Xj and bo.j = by in (30). Now, since λ X jj the index
J min {i {521: s bo.
D
bo
2/7
(52)
The noise term
To apply the bounds Lemma D.2
let us denote event
211 60 1t < In 13:3.2
bo
A2
2 VD
Then, since 12,l S 3|5 on sg. we have t S ST on Aj. where T .2) is defined via 39h. Then, for j > J, applying (38 yields
03 1 SgnA, S 22 exp 2 22 bg | 1 19G
s 22 exp (2 _ B2 2 / Asgna
S Cb. exxp(CI2s//e)1sgna sfnn,
where we use bpt < Bze in the last inequality. Consequently,
EE
03 1 SA s C63D
Σ ExEex((C1))1)) s CLD Σ X3
i>J
52d
< J < Cbuy (121D42-1/7)
where in the second inequality notice that E exxp(C11,l/e is uniformly bounded since each l/
On the other hand, noticing bpt < Byc-1 again, we have
bn
jE 49
Ch
2 In
A VD
bo
15yl/c 2 cB²11 In
cB In (b
DDVD
Hence, using Lemma F.I with the sub-Gaussian property of &, and noticing that 1/1,7/D= j > J, we obtain
/D 2 1 when
E
>50 03 sgnag SC
>
[
E
(1s, lee 2 cU''
(D))
j2l
33

---

< CE²
exp
-c[cBB
1>.
S SC2 Σ
-c [In (1n((1)77)3))
exp
5>J
S Ce2 1,-
-c -e(in(bfz>) [1] 13) dr
exp
C2b 2/7 { exp( exp(-e[In (e(-e(In(v>)) day, y y= 6
< 0 2/7 S -
|0, S 3يوا again, the remaining terms are bounded by
Finally, using the bound
031 sg Se JJ s Cebb 2/7 S Cefe Dia..
In summary, we conclude that
E M 0g S Cè 7
(53)
The signal term
We will apply the bound in Lemma D.3 Let us denote
Jree {j:t2 27 n Jssg(e).
Then, when j E Jree and Sj holds, (22) and the fact 2 1007 S |2y1 S 08] imply
10, - -1 S 2 |رح |15]|oxp exp
D D 243 (1 - Trinn) S c903 exp |c|00] D-
Consequently,
224
2042 E Σ (0,- - 2,, CC| Σ (0))² exp -c|07]
S Σ (07) (10710007)
20
カース
JEEJcc
jEJo
JEJ000
=C Σ
D42 tt D+1
<
Ct
D12 1+1
[sig(t)] S CE2
jEJmo
where we use exp(-cr) < Cx
in the second inequality.
Let define cln(1/c) 2 We claim that JC S [ Sy long as b8t 2 Bic-1 for
some large constant B,. Then, using the obvious bound 06 2g s lzyl s 100 Sy. we have
E Σ - 21) S $EJo_
Σ (07)² -v()). 1EJoic
(54)
To prove the claim, we show that Join (v) C Jree on Sj as long as B₁ is large enough. Recalling and using Assumption I for E Joig (v) C (c), we have
j S max Jsig (e) S CK
Now, we show that 2 27 for j E (u) on Sj for different cases in Lemma D.3
. 2//2 S bb/ D. we have 40) and thus
(D-
D/22 D
t > 21
11 In
1/2
34

---

1 1 10 ((m(()]17))) +
B1
2
Bieln(L/eec Cy
Bi Cx +C.
If 1 2 bo/ VDD 41 gives
t 2 2T
VDA 1/2 D 1+ Rt.
=
where
D= 1, D> 1.
R2
ba
D-1
So for both D = 1 and D > 1, we have similarly
t 2 27
VDA 1/2 8 10 C'I((b")) +C
= 10110 2 C11(116)+
= B₁ ln (/66))20)) Clm(1)))+
Therefore, for both cases, have 1 > 27, long as B₁ is large enough. This finishes the proof of the claim.
E.3
The absolute error term
The following proposition connect the absolute error term with the ideal risk in Johnstone [017]]
Proposition E.1. For the sequence model ( recalling the signal events 445 and the quantities have
E 1s, + 1
S 4
min(2,03)
(
(55)
J=1
Proof. is straightforward to see that
5}1s, + +311s (214111 + +0 121121211 S min min(4e}. 03),
so
E 131s, +0]1sg]
< EEmin(45,.0 < 4E min(()) < 4 minn 2,0))
Summing over yields the inequality. The last equality follows from the definition of 4 and (c).
E.4 Proof of Proposition 3.4
The fact that 0, (L)b((1) is non-decreasing follows from the analysis of the gradient flow in Subsection D.1 and Subsection D.2 For E (0, 1), let us choose C large enough such that P (IE,) < Cej Z 1 for any fixed J.
The case D 0 For the signal component where |071 > 2C's In(//e,, we have 1zy| 2 |0 with
high probability. Then, we follow the analysis of the signal term in Subsection E. and obtain that
(t) 23 C(03)2
1 (07)
provided that e small enough. This implies that
(t) > 1 189
35

---

Now, the second inequality in (24 implies that [0,(t)] I (t). Consequently, we conclude that (t(t) 10:112
For the noise component where since >j = " we have min [j 2 1: 2 S { x x 1/x, Following the similar analysis of the noise term in Subsection E. when j 2 C for some C > O. we have
[07] S e, we have bz S (C + 1)e with high probability. Moreover,
(,) S A exp((((2z)) + 2,) - > exp(Cet) S CX2,
Then, the first inequality in (24 gives [0,(t) 2 ()()), so we have [3,(t) & Cx2 Finally,
0g (t) / =](t) - C _2
The case 2 For the signal component where |87 2 lI1c), we still have we have |æy| 2 1 [ with high probability. Now, from the analysis of the signal term in Subsection E.2
we have 27, Moreover, investigating the proof of Lemma D.3
we see that the analysis in
Subsection E.2 actually shows that
[8,(t) 2 clzy|
clzy| pig 2 c07 m+
Consequently, 32 implies that
a (1)00((1) 13,(1) D+1 2 c00 87
For the noise component where 00] S 6, we also have |2 (C + 1)e with high probability, Now, we have
b 10 S (C+ 1)eb < Co.
for some constant Co. Following the similar analysis the noise term Subsection E.2 we can choose j 2 Cc t such that
bu
2 Co.
Now, this condition guarantees that S (1,2) defined in Lemma D.2 so Lemma D.2 gives
|8())) < A exp Cbb 1 (I s x cxp(Cbp lyylt) s CxA.
Combining it with the upper bound in 32 and noticing S (12) yield
a, (1)0(((0) < P+1 18,(0)10g s अ A
36

---

Auxiliary results
Lemma F.1. Suppose is --s--u--Gasssse namely, IP [|x] 2 2t eexp( 1) for
0. Then
for M 2 O, we have the tail bound
Ex {|X] 2 MM S 40 exp
402 402
(56)
Proof. Using integration by parts, we have
EX 2 M rP
r 2 max(M, M, r)) dr
1 max(M1 r²) dr
rexp
20
M
(M² + 2022)
exp
20²
1 M²
< 40 exp
40
Lemma F22 Suppose that (0z)521 satisfies (01)) x j- j-(p+ 1)/2 for some > 0 and |0yl otherwise, where ((j) is a sequence of indices. Defining (() and (6) as in we have
(6) x pfi,
V ( 8Pt1
Proof. First, from the definition of (6) and (6), that they do not depend ordering of the indices and zero values of fz. Therefore, we can assume that ((j) = j. Then, assuming that erj (2+1)/2 & 10,1 < Cij (p+ 1j/2, we have
(66) |0 10,1 2 831 < (i:CCi-(eta/ae 2 of s (8/C))== sोr
Moreover,
(((6) Σ
0, P1 (10,11 <8>
Σ 10,1 < C Σ j j-(0t1
(3)
{20(6)
< Cf < C' 2M
for some constant C' > 0. The lower bound of them can be obtained similarly.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims are supported by our main theorems as well as the numerical experiments.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations in the last section. The assumptions are also explained and justified.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
38

---

Answer:
[Yes]
Justification:
The proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The related codes are provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
39

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The related codes are provided in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpps:/nips.co
Sublic//giides/odeeuuue asseesouuoisiioooooo ssionoolccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / http:/puubiccc/uude.....e guidee//dee/ee/ Codeeubmiiiiac ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The related codes are provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are reported in Figure 3 on page 21
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
40

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments can be done by 64 CPU core laptop with 32 GB memory in one day.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps://neurips.cc// cetieeeeeeccceeiiiieeeeacaieece caciideeenne
Answer:
[Yes]
Justification:
We follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: is mainly theory paper, so there is no societal impact of the work
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
41

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: is mainly theory paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
42

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "4yJxBCc2eO", "reviewer": "Reviewer_QDTR", "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.", "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?", "limitations": "The literature review/comparison with current result still needs work, upon addressing this I am happy to increase my score.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nEven 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: \n\n[1] “Optimization and Adaptive generalization of Three layer Neural Networks”\n[2] “What happens when SGD Reaches Zero Loss? – A Mathematical Framework”\n[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.\n\nMinor comments\nThis 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and valuable comments.\nFollowing your advice, we will add the related papers that you mentioned.\n\n> My major concern is that similar results to this one already exist in the literature and the authors have not compared\n> their results to them and how they differ from them. I am curious if your result can imply or be phrased as a sparse\n> recovery type argument for high dimensional regression.\n\nThank you for pointing out the related works and the connection between our result and sparse recovery.\nIndeed, it is known that the over-parameterized nets with gradient-based methods tend to recover the sparse solutions,\nas shown in the related works you mentioned and also [Hoff 2017], [Vaškevicius et al., 2019], etc., cited in our paper.\nHowever, there are major differences on the settings and the results between our work and the related works,\nwhich we will clarify in the following:\n\n* **Analysis of Generalization Error**:\n  The papers [2,3] and also previous works like [Hoff 2017], [Gunasekar et al. 2017] are focused only on the\n  optimization process using gradient-based methods, showing sparsity properties of the final solution,\n  but **they do not consider generalization error bounds**.\n  In comparison, our work (and also related works [Vaškevicius et al., 2019], [Zhao et al., 2022]) focuses further on\n  the generalization error of the over-parameterization methods, which turns out to be a harder problem.\n  More specifically, the works on the optimization process often assume the absence of noise in the data and consider\n  the final interpolator as $t \\to \\infty$.\n  However, such an interpolator may not generalize well under the presence of noise.\n  In fact, as shown in our work and also [Vaškevicius et al., 2019, Zhao et al., 2022], proper early stopping is also\n  crucial for generalization.\n  Therefore, we have to analyze the full training process rather than the final convergence point to understand the\n  generalization error, which is a more challenging problem.\n\n* **Linear regression vs. non-parametric regression** The most related works\n  are [Vaškevicius et al., 2019], [Zhao et al., 2022] that considered generalization performance of over-parameterized\n  models with gradient training under the setting of high dimensional linear regression.\n  In comparison, our work considers the non-parametric regression setting under reproducing kernel Hilbert spaces (\n  RKHS).\n  There are several main differences between our result and their results:\n    * *Problem settings*: They consider the high-dimensional linear regression where the input dimension (while growing)\n      is finite,\n      but we consider the non-parametric regression where the input dimension is directly infinite.\n      Also, they focus on the setting with the separation of signal components and noise components, while we consider\n      the more general setting of signal in the sequence model, allowing the magnitudes of the signal across components\n      to vary continuously.\n    * *Over-parameterization setup*:\n      [Zhao et al., 2022] considers the over-parameterization setup that $\\theta = a \\odot b$\n      where the initialization is $a(0) = \\alpha \\mathbf{1}$ and $b(0) = \\mathbf{0}$;\n      [Vaškevicius et al., 2019] considers $\\theta = u^{\\odot D} - v^{\\odot D}$ with $u(0) = v(0) = \\alpha \\mathbf{1}$.\n      However, their parameterization can not apply to the infinite dimensional case since the components are treated\n      equally and the $\\ell^2$ norm of the estimator would be infinite after any step of training.\n      In comparison, our work considers parameterization $\\theta_j = a_j b^D_j \\beta_j$ with $a_j(0) = \\lambda_j^{1/2}$,\n      $b_j(0) = b_0$ and $\\beta_j(0)=0$,\n      so the components are treated differently.\n      Therefore, we have to tackle both the infinite dimensionality and also the interplay of different initialization,\n      which is more complicated.\n\n    * *Interpretation of the over-parameterization*: The previous works view the over-parameterization mainly as a\n      mechanism for implicit regularization,\n      while our work provides a novel perspective that over-parameterization adapts to the structure of the truth signal\n      by learning the eigenvalues.\n      Our perspective could provide more insights on the benefits of over-parameterization.\n\nIn the new revision, we will add a detailed comparison and discussion with the related works in the paper.\nWe hope this will clarify the novelty and contribution of our work.\n\n\n> Can you compare your rate with the results in sparse recovery, if you use lasso instead of your estimator?\n> specifically do you think the low dimensional example that you mention can be observed as some kind of sparsity that\n> can\n> be exploited by lasso?\n\nOur results can be phrased for the setting of high dimensional regression with sparsity.\nTaking a sparse signal $(\\theta_j^*)_{j \\geq 1}$ in our paper, e.g., $\\theta_j^* = 1$ for $j \\in S$, $|S| = s$ and\n$\\theta_j^* = 0$ for $j \\notin S$,\nwe have $\\Phi(\\epsilon) = s$ and $\\Psi(\\epsilon) = 0$,\nso we can find that the resulting rate is $O(s/n)$, which is the same as the rate of the lasso estimator.\n\nFor the low dimensional example in the sequence model, a JS estimator or thresholding estimator can indeed recover the\nsparse signal and achieve the optimal generalization rate, as shown in Chapter 6 and 8 in [Johnstone 2017]. We believe\nthat a lasso-type estimator can also recover the sparse signal in this case. We think that a deeper connection between\nover-parameterization and these estimators can be explored in future work.\n\n### References\n*Due to character limit, please see the next comment block for references.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "59h7Do3BnH", "reviewer": "Reviewer_EWHq", "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.\n\nThe 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).", "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.\n\n2. 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?\n\n3. 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?\n\nTypos/minor suggestions:\n- Line 89: add transpose to $X$\n- LIne 149: defines -> defined\n- Line 205: Inspired -> Inspired by\n- Line 235: shows the generalization error -> presents an upper bound for the generalization error\n- Line 260: have -> present?", "limitations": "This is primarily a theoretical work, and the authors discussed the potential limitations of the work and potential future research directions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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:\n\n**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.\n\n**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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts in reviewing our paper and recognizing the contribution of our work.\nWe appreciate your constructive feedback and will address your concerns in the following:\n\n> Narrow/Restrictive Settings\n>\n> Dynamically Evolving Kernels\n\nWe fully agree with you that the dynamic evolving kernel/feature would explain the superiority of the neural network and\nthis is our start point of this manuscript. We have tried to consider a family of feature maps $\\Phi_θ(\\cdot)$\nparameterized by $θ$ and the model\n$$\ny=\\Phi_θ(x)^{T}β+ε\n$$\nIt is clear that it includes the neural networks as a sub-models and could (partially) capture the dynamic of feature\nlearning characteristic in neural networks. It is clearly a hard task to investigate the most general adaptive\nkernel/feature models, however, some insight may be obtained from some simple families of feature maps.\n\nFor the kernel regression, the feature map is fixed, namely, $\\Phi_θ(x)= (\\sqrt{λ_1}e_1(x)\n,\\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(\ny)$.\n\nAs the first attempt to understand the benefit of dynamic feature maps,\nwe study the slightly complicated family $\\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$,\nwhere the parameters $θ$ are learned during the training process.\n\nHowever, there are some technical challenges to theoretically analyze the differential equation associated to the family\n$\\Phi_θ(x)$. Thus, we looked for some alternative approaches.\nFortunately, the celebrated Le Cam equivalence could allow us to simplify the setting to a sequence model.\n(Please see the answer of Question 1 for details)\n\nHere, we point out that while the eigenfunctions are fixed, **the feature map can change by learning the eigenvalues**,\nand, as shown in the main results, **this dynamic evolution of the eigenvalues can greatly improve the generalization**.\nTherefore, while simplified, our model still holds a connection to the dynamic evolving kernel/feature models and\nprovides\ninsights and a solid theoretical foundation understanding more complicated over-parameterized models.\n\nFrom a higher perspective, our main insight is that **over-parameterized models combined with gradient-based training\nmethods lead to a dynamically adaptive kernel that can adapt to the structure of the truth signal**,\nwhich we would like to refer to as the *\"adaptive kernel\" perspective*.\nStarting from this point,\nwe believe we will be able to explore more realistic settings and more complex models in the near future.\n\nMoreover, as an extension of this work, with extra technicalities, we are now able to analyze directly the\nparameterization\n$\\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$ in the Reproducing Kernel Hilbert Spaces (RKHS) (see the Future Work\nsection).\nDue to the paragraph limit, we plan to explore it further in an extended journal version of this work.\n\n### Questions\n\n1. > The meaning of the sentence in lines 172-175 is unclear. Additionally, it would be helpful if the sequence model\n   > were described earlier to enhance its comprehension.\n\n   We apologize for the confusion. In these lines, we are illustrating that **kernel regression can be simplified to a\n   sequence model using the so-called Le Cam equivalence**.\n   In detail, the Le Cam equivalence states that the minimax risk of estimating a function in a reproducing kernel\n   Hilbert space (RKHS) is equivalent to the minimax risk of estimating a sequence of coefficients in a sequence model.\n   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\n   $i=1,...,n$, we get\n   $\\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$.\n   Using the orthogonality of $e_j$'s in $\\Phi(x)^{T}=(\\sqrt{λ_1}e_1(x)   ,\\sqrt{λ_2}e_2(x),...)$ and approximating the\n   empirical mean with the integration, we derive $\\frac{1}{n}\\sum_i \\Phi(x_i)y_i \\approx \\Lambda β+\\xi$, where $\\xi$ is\n   a vector of Gaussian noise and $\\Lambda$ is a diagonal matrix with entries $\\lambda_j$, so we reach at the Gaussian\n   sequence model.\n   This equivalence allows us to focus on a more tractable model while retaining the essential characteristics needed\n   for our theoretical analysis. We hope this would clarify the point.\n\n   In the new revision, we will reorganize the content and make sure the model is properly introduced.\n\n2. > Regarding the adaptive choice of the stopping time discussed in lines 279-288, I can roughly follow the authors'\n   > point.\n\n   We apologize for the confusion. Our point is to show the over-parameterized gradient descent method has also the\n   advantage of adaptivity over the vanilla gradient descent method.\n   For the vanilla gradient descent, the optimal stopping time $t \\asymp ε^{-(2q\\gamma)/(p+q)}$ is dependent on\n   the unknown parameters $p$ and $q$ of the signal; in contrast, for the over-parameterized gradient descent, the\n   choice $t \\asymp ε^{-\\frac{2D+2}{D+2}}$ does not require prior knowledge of the signal's structure. Moreover,\n   the hidden constant in this stopping time expression only need to be large enough with only a dependency on\n   Assumption 1, a weak assumption on the span of the signal (but not its specific structure).\n   So, **the stopping time is adaptive in the sense that it does not require prior knowledge of the signal's specific\n   structure**.\n\n3. > Including the numerical experiments from Appendix A into the main text would be beneficial, if possible. ...\n    \n    Thank you for your advice. With the additional content page if our paper is accepted, we will be able to include the\n   numerical experiments from Appendix A into the main text to enhance the readability of the paper.\n\n   For real-world datasets, we believe that the eigenvalue misalignment is a common phenomenon in practice.\n\n   *Due to the character limit, the details are given in a new comment block.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fRavPuFQ5A", "reviewer": "Reviewer_kYgJ", "summary": "This paper proposed an overparameterized gradient descent method. Its benefits on generalization has been verified both theoretically and empirically.", "questions": "See weakness.", "limitations": "No negative social impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "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. \n\n2.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.\n\n3.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.\n\n2.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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and recognizing the contribution of our work.\nWe will address your concerns in the following:\n\n1. > The insightful explanations for why the proposed method can improve generalization are lacked.\n\n   We are sorry for not presenting it clearer.\n   Generally speaking, the proposed over-parameterized gradient descent can improve generalization by adjusting the \"\n   eigenvalues\" to fit the structure of the truth signal, so that it can outperform the standard gradient descent.\n   In Section 3.3 paragraph \"Learning the eigenvalues\", we have further investigated why the over-parameterized gradient\n   descent can improve generalization. Proposition 3.4 in this paragraph shows that for the signal components, the\n   eigenvalues are learned to be at least a constant times a certain power of the truth signal magnitude;\n   while for noise components, the eigenvalues do not exceed the initial values by some constant factor. Therefore, the\n   over-parameterized gradient descent effectively adapts eigenvalues to the truth signal while mitigating overfitting\n   to noise, which leads to better generalization.\n\n\n2. > While the experiments in appendix have verified the effectiveness of overparameterized gradient descent, it is\n   recommended to compare the performance of this new method with other algorithms, such as SGD or SAM.\n\n   Thank you for pointing out this.\n   We have conduct more experiments to compare the performance of the proposed over-parameterized gradient descent with\n   other algorithms, such as SGD or SAM.\n   The results show that without the over-parameterization, neither SGD nor SAM can achieve the optimal generalization\n   rate as the over-parameterized gradient descent does.\n\n   Theoretically, as far as we know, the SGD algorithm in kernel regression achieves the same generalization rate as the\n   standard gradient descent ([Lin and Volkan, 2020]), so that it also suffers from misalignment of the eigenvalues in\n   our setting and be inferior to the over-parameterized gradient descent.\n\n#### References\n\n[Lin and Volkan, 2020] Lin, Junhong, and Volkan Cevher. “Optimal Convergence for Distributed Learning with Stochastic\nGradient Methods and Spectral Algorithms.” Journal of Machine Learning Research 21 (2020): 147–1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mD5BhNLNz2", "reviewer": "Reviewer_GugS", "summary": "The authors analyze the generalization error for kernel regression sequence models in the overparameterized regime.\nThey rigorously show that due the overparameterization, the learned parameters are better adapted to the underlying structure.\nThey also provide some numerical experiments corroborating their findings (in the appendix).", "questions": "- The NTK is mentioned multiple times in the introduction, could you elaborate a bit more on the connection of your work to NTK?\n- How would you go about approximating the (infinite sequence ) $\\lambda_i$ in practice? How does this affect performance and guarantees?", "limitations": "Limitations have been addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Clear motivation and presentation\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive feedback and valuable comments.\nWe will address your concerns in the following:\n\n> The main concern here, is that the setting is too constrained, in that the kernel map is assumed to be fixed.\n\nIn fact, the goal of our paper is to investigate the **impact of the dynamic evolution of the kernel on the\ngeneralization performance**, so we are indeed considering a dynamic kernel/feature map.\nWe have tried to consider a family of feature maps $\\Phi_θ(\\cdot)$\nparameterized by $θ$ and the model\n\n$$\ny=\\Phi_θ(x)^{T}β+ε\n$$\n\nIt is clear that it includes the neural networks as a sub-models and could (partially) capture the dynamic of feature\nlearning characteristic in neural networks. It is clearly a hard task to investigate the most general adaptive\nkernel/feature models, however, some insight may be obtained from some simple families of feature maps.\n\nFor the kernel regression, the feature map is fixed, namely, $\\Phi_θ(x)= (\\sqrt{λ_1}e_1(x)\n,\\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(\ny)$.\n\nAs the first attempt to understand the benefit of dynamic feature maps,\nwe study the slightly complicated family $\\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$,\nwhere the parameters $θ$ are learned during the training process.\nHowever, there are some technical challenges to theoretically analyze the differential equation associated to the family\n$\\Phi_θ(x)$. Thus, we simplify the analysis by transitioning to the sequence model, which is justified by the celebrated Le Cam equivalence.\n\nHere, we point out that while the eigenfunctions are fixed, **the feature map can change by learning the eigenvalues**,\nand, as shown in the main results, **this dynamic evolution of the eigenvalues can greatly improve the generalization**.\nTherefore, while simplified, our model still **capture the dynamic nature of kernels/feature maps** and\nprovides insights and a solid theoretical foundation understanding more complicated over-parameterized models.\n\nFrom a higher perspective, our main insight is that *over-parameterized models combined with gradient-based training\nmethods lead to a dynamically adaptive kernel that can adapt to the structure of the truth signal*,\nwhich we would like to refer to as the *\"adaptive kernel\" perspective*.\nStarting from this point,\nwe believe we will be able to explore more realistic settings and more complex models in the near future.\n\nMoreover, as an extension of this work, with extra technicalities, we are now able to analyze directly the\nparameterization\n$\\Phi_θ(x)^{T}=(θ_1 e_{1}(x),θ_2e_{2}(x),....)$ in the Reproducing Kernel Hilbert Spaces (RKHS) (see the Future Work\nsection).\nDue to the paragraph limit, we plan to explore it further in an extended journal version of this work.\n\n\n#### Questions\n\n1. > The NTK is mentioned multiple times in the introduction, could you elaborate a bit more on the connection of your\n   > work to NTK?\n\n   The motivation of this work is to go beyond the fixed kernel in the NTK theory and explore how the dynamic evolution\n   of the kernel improves the generalization performance.\n   The NTK theory shows that the training dynamics of deep neural networks can be approximated by certain kernel\n   regression with a fixed tangent kernel if the network width tends to infinity.\n   However, when the width is finite, the corresponding tangent kernel can be dynamically evolving during training,\n   which is shown empirically in recent works.\n   Therefore, in our work, we go beyond the NTK theory and explore the dynamic evolution of the kernel, particularly its\n   impact on the\n   generalization performance.\n   Since the analysis directly over fully-connected networks is extremely challenging, we simplify the setting by\n   considering parameterizing the kernel only by its eigenvalues and focusing on these eigenvalues.\n   Our results show that such dynamic evolution of the kernel can greatly improve the generalization performance\n   compared to the fixed kernel.\n\n2. > How would you go about approximating the (infinite sequence $\\lambda_i$) in practice? How does this affect\n   > performance and guarantees?\n\n   In our setting where we parameterize the kernel by the eigenvalues, we actually choose an infinite sequence\n   $\\lambda_i$ first as the eigenvalues and then get the corresponding kernel, so the approximation of the eigenvalues\n   is not needed.\n   The usage of \"eigenvalues\" is just to be consistent with the fixed kernel framework (see the connection to NTK), and\n   these \"eigenvalues\" are just the initialization of the (dynamic) kernel in our setting.\n   Following our main result (Theorem 3.1 and Theorem 3.2), it suffices to choose eigenvalues with a fast decay such as\n   $\\lambda_i = i^{-4}$ so that the extra error caused by the misalignment of the initial eigenvalues and the truth\n   signal is small.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ryOEenaLqn", "reviewer": "Reviewer_cuCj", "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.", "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?\n\n2. 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?", "limitations": "None", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts in reviewing our paper and your comments.\nWe appreciate that you recognize that \"the theoretical results are compelling\".\nWe would like to address your concerns in the following:\n\n> One significant weakness of the paper is the limited experimental validation.\n>\n> 2.The theoretical results are promising, but the empirical validation is limited.\n\n\nWe appreciate the reviewer’s concern about the experimental validation.\n\nFirst, we would like to point out that while our experiments are mostly done on the sequence model,\n**similar results hold for the kernel model under the non-parametric regression setting.**\nWe have performed additional experiments and we will include them in the new revision of the paper.\n\nMore importantly, the goal of our paper is to capture the dynamic nature of neural networks under the kernel framework\nand investigate the **impact of the dynamic evolution of the kernel on the generalization performance**.\nThe reason why we consider a simplified model is that (1) directly analyzing a deep neural network is technically\nsignificantly challenging;\n(2) the simplified model enables us to gain a clear understanding of the dynamic evolution of the kernel and its impact\non generalization.\nMoreover, the experiments included in our paper, particularly those in Appendix A, align well with our theoretical\nresults.\nTherefore, our simplified model allows us to **gain insights and provides a solid theoretical foundation for\nunderstanding more complicated over-parameterized models**.\n\nFrom a higher perspective, our main insight is that over-parameterized models combined with gradient-based training\nmethods lead to a dynamically adaptive kernel that can adapt to the structure of the truth signal,\nwhich we would like to refer to as the *\"adaptive kernel\" perspective*.\nThis perspective would be **a valuable stepping stone for understanding the generalization properties of more\ncomplex neural networks**.\nUnder the guidance of this perspective, we will be able to consider more complicated over-parameterization and more\nrealistic models like fully connected deep neural networks.\n\nTherefore, while our current model may not directly apply to real-world datasets in natural language processing or\ncomputer vision, we think that our insights gained in this simplified setting will guide further research that explores\nthe practical implications of our findings in these and other areas.\nWe believe that starting from this point, we will be able to consider more realistic settings and understand more\ncomplex models in the near future.\n\nWe hope this clarification addresses your concern and highlights the intended scope of our work.\n\n\n\n\n\n> 1.Can you provide more detailed theoretical justification or insights into why deeper layers contribute to better\n> performance? Specifically, how does the introduction of additional layers influence the adaptation of eigenvalues, and\n> are there any diminishing returns or optimal depth considerations that should be taken into account?\n\nThank you for the insightful question. To summarize, the additional trainable parameters introduced by deeper layers\nreduce the impact of misaligned initialization on the eigenvalues and enable the model to adapt more effectively to the\nstructure of the true signal, thereby improving generalization performance.\n\nTo provide a more detailed theoretical justification, let’s revisit the parameterization of our model: $\\theta_j = a_j\nb_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$,\nand $\\beta_j(0) = 0$. In this framework, the term $a_j b_j^D$ is responsible for learning the eigenvalues, while\n$\\beta_j$ captures the signal. Then, Proposition 3.4 provides key insights:\n\n1. **For signal components (large $\\theta_j^\\star$)**: $a_j b_j^D$ increases to approximate $|{\\theta_j^*\n   }|^{\\frac{D+1}{D+2}}$ multiplied by a constant factor. This indicates that the eigenvalues become better aligned\n   with the true signal as $D$ increases, since $\\frac{D+1}{D+2}$ is an increasing function of $D$.\n\n2. **For noise components**: If $\\lambda_j \\leq \\epsilon^{2/(D+2)}$, $a_j b_j^D$ does not exceed its initial value\n   by more than a constant factor, thereby controlling the generalization error contributed by noise. A larger $D$\n   allows this condition to be met for more components, thus enhancing the model's generalization performance.\n\nWhile deeper layers facilitate more effective adaptation to the true signal, there are considerations regarding\ndiminishing returns and optimal depth:\n\n1. **Training Time and Computational Cost**: As shown in Corollary 3.3, the required training time $t \\asymp\n   \\epsilon^{-\\frac{2D+2}{D+2}}$ increases with $D$, as does the computational cost due to the added layers. This may\n   not be desirable in practical applications where computational efficiency is a concern.\n\n2. **Limited Benefit**: The primary benefit of deeper layers is to mitigate the impact of misaligned initialization on\n   the eigenvalues. However, once $D$ is sufficiently large and this impact is no longer dominant, further increasing\n   $D$ may not yield significant improvements.\n\nTherefore, the optimal depth is problem-dependent, with $D$ being large enough to minimize the influence of misaligned\ninitialization while balancing computational considerations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary:**

This paper investigates how over-parameterization can enhance generalization and adaptivity in non-parametric regression models, particularly focusing on sequence models that approximate kernel regression. The authors introduce an over-parameterized gradient descent method to analyze how varying eigenfunction orders affects performance. Key findings include:

- Limitations of traditional kernel regression methods when eigenvalue alignment is suboptimal
- Over-parameterized gradient flow can adapt to the underlying signal structure and outperform standard methods
- Adding depth to the model further improves generalization by mitigating initialization effects

**Strengths:**

- Novel theoretical analysis providing insights into benefits of over-parameterization
- Clear motivation and presentation of ideas
- Rigorous mathematical framework that could be useful for further research
- Shows limitations of fixed kernel approaches like NTK and provides path forward
- Demonstrates how over-parameterization can lead to adaptive kernel learning

**Weaknesses:**

- Model setting is somewhat simplified/constrained compared to practical neural networks
- Limited experimental validation on real-world datasets and tasks
- Not fully clear how insights translate to more complex architectures used in practice
- Some reviewers felt theoretical claims about optimality of linear decay schedule needed stronger support

**After rebuttal:**

Overall, reviewers found the theoretical contributions and insights valuable, but had some concerns about how directly applicable the results are to practical deep learning. The authors provided reasonable responses explaining the scope of the work as a theoretical foundation to build upon. Most reviewers were satisfied with the responses and some increased their scores, indicating the paper makes a solid contribution to understanding over-parameterization, even if further work is needed to fully bridge to applied settings.
Decision: Accept (poster)