Learning Provably Improves the Convergence of Gradient Descent

Thanks for your questions and suggestions.

1. (L1) Presentation of Section 3.1

   1. (L1.1) Explanation for "stringent conditions" and "necessary conditions"

      A: As in lines 171-181, page5, the stringent conditions of LISTA-CPSS are some necessary conditions for learnable parameters and variables to ensure convergence, which are our evaluation targets that are detailed in lines 171-181. The results are in Figure 3(a).

      The necessary conditions (line 161) of Math-L2O do not prove sufficient conditions to guarantee that the proposed models can converge. It only assumes it converges, which is a necessary condition, to derive a reasonable architecture of neural network models.

   2. (L1.2) Empirical results of Math-L2O

      A: The evaluation results of Math-L2O are in Figure 3(b).

      Due to the page limit, we put it along with the results of the LISTA-CPSS. The result shows the poor training convergence of Math-L2O in large steps $T$.

2. (L2) Presentation of Section 3.2

   1. (L2.1) $X_T^0$ in both size of inequality.

      A: This is a typo. And there are two typos in inequalities (9) and (10). The right-hand side (RHS) of inequality (9) in line 197 should be $\frac{\beta}{T}\Vert X_0^0-X^*\Vert_2^2$, since the evaluating step is the subscript $_T$. The LHS represents the objective after $T$ steps. The RHS represents the objective of initial $X_0^0$.

      And the complete inequality should be $F(X_T^0) \leq \frac{\beta}{T}\Vert X_0^0-X^*\Vert_2^2$, which illustrates a convergence rate within $T$ steps of Gradient Descent algorithm.

      Moreover, the inequality (10) in line 200 should be $F(X_T^k) \leq r_k \frac{\beta}{T}\Vert X_0^k-X^*\Vert_2^2$. This is due to $X_0$ being a given initial point, which is not violated by training iteration $k$. In this inequality, the superscript is $^k$, which means that this is not related to training iteration. The subscripts in the left-hand-side (LHS) are $_T$ and in the RHS are $_0$, which formulates the convergence rate of L2O model within $T$ steps.

   2. (L2.2) Sub-linear convergence rate of $\mathcal{O}(1/T^2)$

      A: This is a typo. The right version should be $O(1 / T)$, which is the convergence rate of vanilla gradient descent. We will fix it in final version. However, this is minor compared to our main contribution.

Thanks for your questions and suggestions.

Weaknesses:

1. Weakness 1: Presentation

   1. (W1) Presentation of convergence improvement

      1. (W1.1) Relationship between Eq. (8) and Eq. (9).

         A: There are two typos in inequalities (9) and (10). The right-hand side (RHS) of inequality (9) in line 197 should be $\frac{\beta}{T}\Vert X_0^0-X^*\Vert_2^2$, since the evaluating step is the subscript $_T$. The LHS represents the objective after $T$ steps. The RHS represents the objective of initial $X_0^0$.

         And the complete inequality should be $F\left(X_T^0\right) \leq \frac{\beta}{T}\Vert X_0^0-X^*\Vert _2^2$, which illustrates a convergence rate within $T$ steps of Gradient Descent (GD) algorithm.

         Moreover, the inequality (10) in line 200 should be $F\left(X_T^k\right) \leq r_k \frac{\beta}{T}\Vert X_0^k-X^*\Vert _2^2$. This is due to $X_0$ is a given initial point, which is not violated by training iteration $k$. In this inequality, the superscript is $^k$, which means that this is not related to training iterations. The subscripts in the left-hand-side (LHS) are $_T$ and in the RHS is $_0$. which formulate the convergence rate of L2O model within $T$ steps.

      2. (W1.2) Alignment between L2O algorithm's initial state and GD.

         A: Yes.

         Our proposed deterministic initialization method achieves the satisfaction of this condition by setting the last layer of neural network (NN) model to be all ones and eliminating bias term. This will give all zero output before activation layer. By a $2\times$ sigmoid activation function. The final output is all one. We manually produce a $1/\beta$ to achieve an identical step size with GD. These are detailed in Section 5.1.

   2. (W2) Sub-linear convergence rate of $O\left(1 / T^2\right)$

      A: This is a typo. The correct version is $O\left(1 / T\right)$. We will fix it in the final version.

   3. (W3) Connection between Section 3 and Section 4

      A: In Section 3, we use denotation $r_k$ as a general symbol to illustrate our main framework. In the first paragraph (lines 211-216) of Section 4, we use text descriptions to explain the relationship. In our Theorem 4.3 it is exactly $\left(1-4 \eta \frac{\beta_0^2}{\beta^2} \delta_4 \alpha_0^2\right)^k$. We will add this explanation of the correlation between $r_k$ and our demonstrated convergence rate in Theorem 4.3 in the final version.

   4. (W4) Precise definitions and assumptions for lemmas and theorems

      A: Thanks for your suggestion. As in Equation 11, to simplify the formulations in lemmas and theorems, we define several quantities. Each quantity represents an inner formulation in the demonstration of lemmas and theorems. The detailed step-by-step demonstrations are in the Appendix. In response 2 to Reviewer ooXd, we give an explanation and analysis of the magnitude for all quantities. We will add them to the paper in the final version.

2. Weakness 2: Novelty of NTK

   A: Thanks for your suggestion. We are the first to utilize the new NTK framework in [2] to demonstrate an explicit convergence of RNN-like models.

   In this work, we apply the NTK framework proposed in [2] to demonstrate the convergence rate of L2O. Our main contribution is to originally prove that training of L2O can yield a convergence-improved algorithm (L2O itself). However, the utilization of the NTK is not identical to that in [2]. The L2O framework (named as unrolling) recurrently uses one NN model to generate the step size of GD, which is demonstrated to be a more complicated case of convergence demonstration with NTK in the following citation. Also, we do not mainly claim the originality of utilizing the NTK framework in [2] for RNN-like models. However, to our knowledge, we are the first to achieve that.

   [1] Allen-Zhu et al . On the convergence rate of training recurrent neural networks. NeurIPS 2019.

   [2] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. ICML, 2021.

Questions:

1. (Q1) Improvement of L2O over GD

   1. (Q1.1) Lower and upper bounds.

      A: Lower bound is 0. Upper bound is 1.

      From Theorem 4.3 and the above explanations. The improvement is determined by $r_k$, i.e., $r_k := \left(1-4 \eta \frac{\beta_0^2}{\beta^2} \delta_4 \alpha_0^2\right)^k$, which is a term less than one since $\delta_4=\sigma\left(\delta_3 \Theta_L\right)\left(1-\sigma\left(\delta_3 \Theta_L\right)\right) >0$ and $\alpha_0:=\sigma_{\min }(G_{L-1, T}^0) > 0$ ($G_{L-1, T}^0$ is a thin matrix). Trivially,$r_k$'s upper bound is one. From Equation (10), this implies that L2O is at least as fast as GD. However, we think that the investigation of the upper and lower bounds of the improvement is necessary to conduct new research work. Thanks for this question, which provides us with a new interesting question.

   2. (Q1.2) Essential of improvement.

      A: Yes.

      As in Section 3, improvement of training is orthogonal to backbone algorithm steps. Intuitively, it can be somehow illustrated as finding a shortcut from offline training. After that, we will benefit in faster online inference.

   3. (Q1.3) Generalization

      A: Empirically, the inference performance in Figure 8 shows that it generalizes well.

      The theoretical generalization analysis of solving optimization problems with L2O on test instances is a non-trivial research topic as well. This work does not include this part. Some existing works focus on this area. We list some citations in the following.

      [1] Sucker, Michael, and Peter Ochs. A Generalization Result for Convergence in Learning-to-Optimize. ICML 2025.

      [2] Qingyu Song et al. Towards Robust Learning to Optimize with Theoretical Guarantees. CVPR 2024.

2. (Q2) Neural network width requirements

   1. (Q2.1) NN width requirement

      A: Yes. Scale 3 in Table 1, page 40, is an under-parameterized case.

      $O(d)$ represents an under-parameterized case, where the layer of NN is not wide. We do have some under-parameterized experiments in Appendix. For example, in Table 1 Appendix C.1 page 40, the Scale 3 is the case where the width of NN layer is only 20, which is extremely smaller than input dimension $10\times512$. The results (orange line) in Figure 7 show that the model still converges. For this, we would like to note that the proved bounds and conditions for training convergence are an upper bound. The tightness of the bound derived from NTK is a non-trivial research topic. In the future, we aim to improve the bound proposed in this paper.

   2. (Q2.2) Performance comparison of scales in Table 1

      A: They are not on the same scale.

      The first two models with different scales are designed to solve problems that are not comparable. The third model, although targeting the optimization problem with the same dimension, has a different number of training samples, i.e., N. It is designed to align with the training configurations of the baseline model, LISTA-CPSS. Moreover, due to the GPU memory limitation, we set a thin NN, whose convergence is not guaranteed by our proposed theorem. This experimental result is used to further demonstrate our proposed framework in Section 3. Thus, we would like to note that the three scales are not comparable.

Thank you for your detailed response.

Regarding the improvement of L2O over GD, I have some remaining concerns about the lower bound:

• If we consider the limit case where training iterations $k\to \infty$, theoretically, the trained NN-optimizer could reach the optimum in a 1 gradient step. This would imply that the NN predicts $g_W(x_0, \nabla F(x_0)) = \beta (X_0 - X^*) / \nabla F(x_0)$ according to Equation (3).
  • How does this mechanism generalize to arbitrary initial points $X_0$ and problem parameters $M$ (even when limited to the training dataset)?
  • Specifically, since $M$ does not appear to be explicitly treated as an input to the neural network, how does the network predict $M$-dependent optimal solutions in a single step?
  • Alternatively, is this simply a case of the network memorizing the entire training dataset and exhibiting overfitting, as suggested in your response to Reviewer ooXd?

Thanks for your questions and suggestions.

Weakness:

1. (W1) Intuitive of our proposed framework

   A: Yes. As demonstrated in our Section 3, the reader will find that the training iteration (denoted as $k$) is orthogonal to the convergence metric, i.e., step $T$, where the convergence of training performs an incremental convergence improvement on gradient descent (GD) by $r_k$. Our Theorem 4.3 (after a long journey) shows that we can achieve $r_k$ by proving a learning convergence from the NTK theory. Thus, it is natural to expect that we can utilize exhausted training to achieve extremely fast convergence and even reach the optimum by one step. This is known as the over-fitting problem in the machine learning community. Over-fitting will lead to poor robustness of inference. However, the generalization of solving optimization problems of L2O on test instances is a non-trivial research topic as well. This work does not include this part. Some existing works focus on this area. We list some citations as follows.

   [1] Sucker, Michael, and Peter Ochs. A Generalization Result for Convergence in Learning-to-Optimize. ICML 2025.

   [2] Qingyu Song et al. Towards Robust Learning to Optimize with Theoretical Guarantees. CVPR 2024.

   Moreover, the training complexity for different steps is different. Training a L2O with a small $T$ is more complex than training a L2O with a large $T$. From the convergence rate of L2O in Equation (10), a small $T$, for example, 1, leads to a smaller right-hand-side (RHS) than a large $T$, 10. This requires a smaller $r_k$ for $T=1$ case. As in the convergence rate term from Theorem 4.2, we set a proper learning rate to ensure a consistent convergence rate for both cases. We need more training iterations for $T=1$ case. Moreover, if we would like to utilize fewer training iterations, from the following interpretation for the learning rate settings, we need to set a larger learning rate. However, this will lead to the fluctuation around the optimum for stochastic optimizers, for example, SGD, which requires more complicated training techniques to stabilize training.

2. (W2) Step size in Equations (13a) and (13b)

   A: Equations (13a) and (13b) are based on the quantities defined in Equation (11). Each quantity represents an inner formulation in the demonstration of lemmas and theorems.

   Due to the page limit, we put the main results on the main pages. We use these quantities to simplify the formulations. The detailed step-by-step demonstrations are in Appendix. First, we would like to introduce their magnitudes as follows. We will add this interpretation to the main page in the improved version, where we will have one bounce page. In the denotations, we use subscripts like $T$ and $L$ to emphasize that the defined constant terms are related to step $T$ and training iteration $k$, and use superscripts or subscripts like $j$ and $t$ to emphasize that the defined scalar value functions are related to step $t$ and $j$. We denote $\bar{\lambda}\_{\min}, \bar{\lambda}\_{\max} = \min\{\bar{\lambda}\_\ell \}, \max\{\bar{\lambda}\_\ell \},\ell \in [L]$, which are some constant upper bounds of the singular value of the NN layers (defined in Equation (11)).

   • $\bar{\lambda}_{\ell}$: A positive constant upper bound for each NN layer $\ell$. Demonstrated in the proof of Theorem 4.3.
   • $\Theta\_{L}$: A positive constant w.r.t. $\bar{\lambda}\_{\ell}$. $\Theta\_{L}$ is lower and upper bounded by $\Omega(\bar{\lambda}\_{\min}^L)$ and $\mathcal{O}(\bar{\lambda}\_{\max}^L)$, respectively. Moreover, $\Theta\_{L}^{-1}$ is $\Omega(\bar{\lambda}\_{\max}^{-L})$ and $\mathcal{O}(\bar{\lambda}\_{\min}^{-L})$.
   • $\Phi_j$: A scalar-valued function w.r.t. step $j$. $\Phi_j$ is $\mathcal{O}(j)$ and $\Omega(j)$.
   • $\Lambda_{j}$: $\mathcal{O}(j^2)$ and $\Omega(j^2)$.
   • $S\_{\Lambda,T}$ and $S\_{\bar{\lambda},L}$: $S\_{\Lambda,T}$ is $\mathcal{O}(T^3)$ and $\Omega(T^3)$. $S\_{\Lambda,T}^{-1}$ is $\mathcal{O}(T^{-3})$ and $\Omega(T^{-3})$. $S\_{\bar{\lambda},L}$ is $\Omega(L\bar{\lambda}\_{\max}^{-2})$ and $\mathcal{O}(L\bar{\lambda}\_{\min}^{-2})$. Moreover, $S\_{\bar{\lambda},L}^{-1}$ is $\Omega(L^{-1}\bar{\lambda}\_{\max}^{2})$ and $\mathcal{O}(L^{-1}\bar{\lambda}\_{\min}^{2})$.
   • $\zeta_1$ and $\zeta_2$: $\zeta_1$ and $\zeta_2$ are both $\Omega(T)$ and $\mathcal{O}(T)$.
   • $\delta\_1^t$: $\Omega(t\bar{\lambda}\_{min}^{Lt})$ and $\mathcal{O}(t\bar{\lambda}\_{max}^{Lt})$.
   • $\delta\_2$: $\delta\_2$ is $\Omega(T\bar{\lambda}\_{min}^{LT})$ and $\mathcal{O}(T\bar{\lambda}\_{max}^{LT})$. $\delta\_2^{-1}$ is $\Omega(T\bar{\lambda}\_{max}^{-LT})$ and $\mathcal{O}(T\bar{\lambda}\_{min}^{-LT})$.
   • $\delta_3$: Both $\Omega(T)$ and $\mathcal{O}(T)$.
   • $\delta\_4$: $\delta\_4$ is $\Omega(\exp(-T\bar{\lambda}\_{max}^L))$ and $\mathcal{O}(\exp(-T\bar{\lambda}\_{min}^L))$. Moreover, $\delta\_4^{-1}$ is $\mathcal{O}(\exp(T\bar{\lambda}\_{max}^L))$ and $\Omega(\exp(T\bar{\lambda}\_{min}^L))$.

   Next, we analyze the magnitude of learning rate $\eta$, where we would like to highlight that it is acceptable by the NTK framework since training does not need large learning rates in NTK theory. Our learning rate settings are designed to be close to these results. The results also empirically demonstrate that convergence from NTK theory does not need a large learning rate.

   1. Typo in Equation (13a): There are some typos in the subscricpts, the revised version is ...$\big( \delta_2 + \Theta_L S_{\Lambda,T} S_{\bar{\lambda},L} \big)^{-1} S_{\Lambda,T}^{-2}$.

   2. We calculate the scales of learning rate $\eta$ w.r.t., $\bar{\lambda}_{\max},T,L$, which are likely to scale with L2O configurations. $T$ is the GD steps and $L$ is NN layers. We can control these values by some specific initialization methods.

   Equation (13a): We calculate the scale of $\eta$ by $\mathcal{O}(\frac{T\bar{\lambda}\_{max}^{LT} + T^2}{((T\bar{\lambda}\_{max}^{LT})+\bar{\lambda}\_{max}^{L}T^3L\bar{\lambda}\_{max}^{-2})T^6})$. The value is reaching one with the increase of $\bar{\lambda}\_{max}$. Learning rate will not be extremely small with some proper initialization method, such as our proposed method in Section 5.

   Equation (13b): $\eta$ is correlated with lower bound of $\alpha_0$, which is the singular value of the layer before last layer (line 223, section 4.1). Moreover, in Eq. 12-(abcd), we demonstrate four lower bounds of $\alpha_0$. We then analyze the magnitude of $\eta$ in each case. We aim to formulate the upper bound of learning rate $\eta$.

   • Inequality (12a) holds: $\eta$ is $\mathcal{O}(\exp(2T\bar{\lambda}\_{\max}^L)T^{-2})$.

   • Inequality (12b) holds: $\mathcal{O}(\bar{\lambda}\_{\max}^{2-LT-2L}T^{-4}L^{-1})$.

   • Inequality (12c) holds: $\mathcal{O}(\bar{\lambda}_{\max}^{-L}T^{-3})$.

   • Inequality (12d) holds: $\mathcal{O}(\exp(T\bar{\lambda}\_{\max}^L)(\bar{\lambda}\_{\max}^{2L}T^2L)^{-\frac{2}{3}})$.

   One will see that the increase of $\bar{\lambda}_{\max}$ leads to smaller learning rates. However, this will not lead to slow convergence. First, theoretically, a small learning rate does not contradict the NTK theory. The vanilla NTK theory [1] establishes a methodology that uses an infinitely wide NN with enormous neurons. Then, linear convergence can be obtained by finding an optimal solution within a small closed space around initialization [1]. Thus, a large learning rate is not necessary in NTK theory. Second, our empirical results show that the convergence performance of training is not sensitive to learning rates.** For example, in Figure (4a), learning rates from $10^{-3}$ to $10^{-7}$ have similar convergence speeds.

   Moreover, the small learning rate setting is a compromise to avoid further increasing the width of NN. In some works [2] [3], although the infinite width requirement is eliminated, the polynomial width is still required, such as $N^3$ in [2] and [3], where $N$ is the number of samples. In this work, the number of samples is proportional to the dimensionality of the optimization problem in the coordinate-wise L2O (treat each dimension independently, defined in lines 118-122), where d dimensions feature are reshaped into the sample dimension, the input of NN is $Nd$ rows, defined in line 115. Hence, we take a different compromise by setting a smaller learning rate to avoid an extremely wide NN.

   [1] Arthur J. et al. Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS, 2018.

   [2] Allen Z. et al. On the convergence rate of training recurrent neural networks. NeurIPS 2019

   [3] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. ICML, 2021

3. (W2) Unclear notations

   A: Thank you for figuring out the typos. We will fix them in the final version.

   $W_{[L]}$: We use it to represent the learnable parameters of a L2O model, where we eliminate all bias terms in every layer. The $X_T$ is generated by $W_{[L]}$ and a given $X_0$.

   Parentheses: Due to character limit, we will fix it in the improved version.

   Lemma 4.2: Fixed: ...$\Lambda\_{s} \Theta\_L\big(\sum\_{\ell=1}^{L} \bar{\lambda}\_{\ell}^{-1} \Vert W\_{\ell}^{k+1} - W\_{\ell}^{k} \Vert\_{2}\big).$ Proof is in line 613, Appendix.

   $F(W^k)$: Sorry for the misleading. $W$ here is $W_{[L]}$ in Equation (2). $F(W^k)$ represents $F(X_T^k; W^k)$. Here, as in Equation (2), we use $;$ to represent that $X_T^k$ is generated by $W^k$ with given $X_0$ (aks, $X_0^k$ since it is not related to $k$). To make it clearer, we will define the objective in Equation (2) as $F(X)=\tfrac{1}{2}\Vert \mathbf{M} X-Y\Vert _2^2$, which only illustrates the target optimization problem and is not related to underlying methods.

   For $W_{[L]}$, it is only used in problem definition in Equation (2), illustration of L2O's behavior in Equation (7). In other equations, $W$ is used. We will revise $W_{[L]}$ to be $W$.

Thanks for your question. Sorry for the misleading description in line 123.

$P_t$ is a vector. As defined in Equation (4), $P_t$ is the output of the NN by $2 \times$ sigmoid activation function. We will fix the typo by replacing "diagonal matrix" with "vector" in the related description in line 123.

Throughout the duration of this study, the definition of $P_t$ was revised from the "diagonal matrix" to the vector form in Equation (4). Because we find that if we define $P_t$ to be a diagonal matrix, due to the chain rule, calculating the gradient of $P_t$ will yield matrix-by-matrix and vector-by-matrix derivatives. To simplify the formulation, we define $P_t$ as a vector. For example, in Equation (24) in line 521, page 15, Appendix, we need to calculate the derivative of NN's output ($P_t$) with respect to NN's parameters. In Equation (28) in line 529, page 15, Appendix, we need to calculate the derivative of L2O's output ($X_t$) to NN's output ($P_t$).

We forgot to change the description in line 123.

Thanks for raising this question for us. We will modify the description accordingly.

Thanks for your questions and suggestions.

Weakness (W) and Questions (Q):

1. Typos:

   1. (W1) $\mathbf{M}_1$

      A: Defined in line 467, page 13.

   2. (W1) $W_{[L]}$

      A: As in part 3 of the response to Reviewer ooXd, $W_{[L]}$ is only used in problem definition in Equation (2), illustration of L2O's behavior in Equation (7). In other equations, $W$ is used.

   3. (Q3) $O(1 / T^2)$

      A: Typo. Should be $O(1 / T)$.

2. (Q7) Lemma A.2 Proof and (Q8) $0 < P_t^{k} < 2$

(Q7) A: $0 < P_t^{k} < 2$ is the configuration of activation by $2*sigmoid$.

(Q8) A: $\mathcal{D}$ is diagonalization operation on vector $P_t^{k}$, whose maximal eigenvalue is trivially bounded by $2$. We will add this to the appendix.

3. (Q4) Quantities in Line 223

   A: They are symbols to simplify the formulations in lemmas and theorems.

   First, the first two lines are formulations with pre-defined parameters. For example, $X_0$ is defined in Equation (3) and M and Y are defined in Equation 2. (A clearer definition is provided in part 3 of the response to Reviewer ooXd). Further, the remaining four lines include a composite formulation of first three lines and the parameters. Detailed analysis of these quantities is provided in part 2 of the response to Reviewer ooXd. They are used in formulations in Theorem 4.3 and step-by-step demonstrations in Appendix.

4. (Q4) Existence of $a_0, \bar{\lambda}\_\ell, C\_\ell$

   A: They can be deterministically defined by our initialization methods and can be probably confined to a closed set by stochastic initialization methods.

   Since $\bar{\lambda}\_{\ell} = \Vert W\_{\ell}^0\Vert_2 + C\_\ell$ and $C\_\ell$ is a constant sequence (Section 4.1), if $\Vert W\_{\ell}^0\Vert\_2$ is known, $C\_\ell$ can be trivially constructed. Since $\alpha\_0 \coloneqq \sigma\_{min}(G^0\_{L-1,T})$, where $G^0\_{L-1,T}$ is generated by $W\_{\ell}^0$ and given input feature. It is bounded if $\Vert W\_{\ell}^0\Vert\_2$ is bounded as well. For a deterministic initialization, for example, our proposed method in Section 5, $W\_{\ell}^0$ is trivially deterministic. For a random initialization, for example, LeCun's initialization method introduced in Nguyen ICML 2021 [1], $W\_{\ell}^0$ is sampled from standard Gaussian distribution. It has a high probability of being bounded within the sphere around origin.

5. (Q4, Q9) Weyl's inequality and related bound proof

   A: In lines 643-650, Appendix, we proved that $\Vert W_{\ell}^{k+1} - W_{\ell}^{0}\Vert_2 \leq C_\ell$. The Weyl's Inequality for singular values is $|\sigma_k(A)-\sigma_k(B)| \leq \sigma_1(A-B)$, where $\sigma_k$ represents $k$-th largest singular value. In our paper, we take $\sigma_k$, which is spectral norm in our formulation. Thus, we have $\Vert W_{\ell}^{k+1} \Vert_2 - \Vert W_{\ell}^{0}\Vert_2 \leq C_\ell \Vert W_{\ell}^{k+1} - W_{\ell}^{0}\Vert_2 \leq C_\ell$.

6. (W1, Q10) Illustration of NTK

   A: Yes, NTK is implied by the non-singular. The kernel matrix is for the gradient of loss to learnable parameters. The main technique of NTK theory is the establishment of non-singularity of the kernel matrix by a wide-NN layer. This invokes the Polyak-Lojasiewicz condition (a more relaxed condition than strongly convex) for linear convergence. Due to the page limit, we eliminate the explicit formulation of kernel matrix. Based on Nguyen ICML 2021 [1], the non-singularity of kernel matrix is established by $\sigma_{\min}(G^0_{L-1,T}) > 0$. It is guaranteed by the condition in Theorem 4.3 and implemented by our initialization strategy in Section 5.

7. (Q5) Initialization strategy in Section 5

   A: As in line 279, we only set learnable matrix of last layer to be all zeros. The former layers are randomly sampled. The reviewer may be confused by $\{W_1^0, \dots, W_{L-1}^0, W_L^0 = \mathbf{0}\}$, where $W_1^0, \dots, W_{L-1}^0$ represents no definition. We will make it clearer in the final version.

8. (Q1) & (Q2): Generalization problem: non-ReLU (Q1) and LSTM (Q2)

   (Q1) A: As in line 572, we use 1-Lipchitz property of ReLU in the proof. Any activations with constant-Lipchitz can be applied.

   (Q2) A: LSTM avoids gradient exploding or vanishing by a gate. However, the theoretical demonstration for LSTM is complex. To our knowledge, there is no LSTM convergence proof with NTK.

9. (W2) NN model on MNIST

   A: We design an additional experiment to show the faster convergence of our proposed L2O than GD on a small CNN network for MNIST dataset in training (our paper mainly focuses on training). The constructions of experiment is as follows. The faster training convergence demonstrates the effectiveness of our proposed initialization and learning rate setting method.

   • L2O: As in the paper, 3 layers, the width of wide layer: 20 (similar to Scale 3 in Table 1, page 40)
   • CNN: 1537 learnable parameters
     • 1st layer: Conv2d(in_channels=1,out_channels=2,kernel_size=3,stride=1,padding=1,dilation=1). Other:Default
     • 2nd layer: Conv2d(in_channels=1,out_channels=2,kernel_size=3,stride=1,padding=1,dilation=1). Other:Default
     • 3rd layer: Linear(in_features=3*7*7,out_features=10). Other:Default. 10 is for 10 classes of digitals in MNIST.
   • Configuration of GD
   • Step size: 0.01
   • Steps $T$: 10000
   • Configuration of L2O
   • Step size: 0.01
   • Steps $T$: 100 (Note: Our results show that 100 step is enough.)
   • Number of samples: 200 from MNIST
   • Loss: Cross-entropy of all samples
   • Training Epochs: 200
   • Optimizer: SGD
   • Learning rate and initialization: Learning rate is $10^{-6}$. $e=100$. (Configurations in our paper)

   We list the loss with step sizes. For GD, we list its loss every 1000 steps. For L2O, we select the first 10 steps. The results show that L2O converges in one step. However, GD with a 0.01 step size does not converge with 10000 steps. The result demonstrates a great convergence outperformance of L2O over GD on non-convex cases.

10. (Q6): Typo.

Limitations:

1. Generalization

   A: We primarily aim to demonstrate that learning can enhance the convergence of existing algorithms, which can be generalized to any unrolling L2O framework.

   We need to establish NN training convergence. From our investigation, we find that NN training convergence demonstration is a really complex and non-trivial problem. We take the NTK theory to achieve that, which is proposed to demonstrate the convergence proof for typical supervised learning or inverse problems, where $L_2$-norm is typically used as objective. For the generalization of NTK theory for other optimization objectives, the existing works have generalized it to more objectives [1-3], for example, cross-entropy. However, we choose $L_2$-norm in this work since it is straightforward to derive an explicit convergence rate (most existing works do not prove convergence rate w.r.t the objective but a surrogate one [3]), which helps us to design a deterministic initialization strategy. This is more applicable to model and training settings.

   [1] Arthur J. et al. Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS, 2018.

   [2] Chizat, L., & Bach, F. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. COLT, 2020.

   [3] Yu, Z., & Li, Y. Divergence of Empirical Neural Tangent Kernel in Classification Problems. ICLR, 2025.

   [4] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. ICML, 2021.

2. NAG

   A: NAG is achievable by dynamic system formulation.

   We chose the GD as the backbone algorithm to make it easier to follow. As discussed in Section 3, we are the first to demonstrate a sufficient condition for L2O's training convergence without any assumption on the sequences generated by L2O. From our knowledge, our result is the first general sufficient condition for training convergence. As our first work in the L2O convergence demonstration, we chose the GD as the backend algorithm to complete the training convergence demonstration. From our knowledge, there is no theoretical convergence demonstration for L2O with GD, either.

   We think the convergence proof of NAG is still achievable. Our basic idea is that convergence can be established by properly setting a bound output of L2O to align the convergence of backbone algorithm. For example, in Equation (3), we use the \beta-smooth property to conduct step size. This methodology can be applied to any algorithm with a convergence guarantee. We aim to bound $X_T$ with $X_0$. First, we can formulate the NAG as a linear dynamic system from $X_0$. For some $t$, $X_{t+1}$ is transferred from $X_t$ by the left production of some transferring matrix. Then, we set a proper output of NN to generate momentum terms and step sizes to avoid the transfer matrix from exploding within T steps. Then, the bound of $X_T$ can be derived based on Cauchy-Schwarz and Triangle inequalities.

3. Input dimension

   A: Our L2O model is coordinate wise, only 2 input features.

   We follow the methodology of Math-L2O (citation 22) to define a L2O model. As in line 115, section 3.1, we set the L2O model to be coordinate-wise, achieved by reshaping the $N$ samples with $d$-size vectors of $X$ and $\nabla F(x)$ into the dimension of samples. Thus, the input features are $\in \mathbb{R}^{Nd\times 2}$.

I thank the authors for detailed replies. Most of my concerns were addressed, and I have only minor ones:

• Can the authors discuss the scalability of L2O approach, i.e., what are the advantages and disadvantages of the approach with the size of the network.

• Can the authors discuss the possible convergence in the finite-width regime? Is it necessary in practice to achieve a good performance of L2O framework?

• Did the authors try to test L2O framework beyond simple models and datasets. This is especially important since training MLP on MNIST does not require lr adjustments during the training, and fixed stepsize works pretty well. How generalizable are those results to larger settings?

Thanks for your comment and questions.

1. Q1 and Q2: Size of NN in L2O and finite-width regime.

   1. Q1: Size of NN in L2O

      L2O still requires learning. From the perspective of generalization, according to the VC dimension theory [1], we expect minimizing the number of learnable parameters to enhance its robustness in solving unseen optimization problems. However, it still requires enough learnable parameters to maintain its capability to learn.

      From the perspective of theoretical training convergence, a wide NN is required to ensure the convergence. To our knowledge, there is no convergence guarantee of a thin NN with fewer learnable parameters. We provide a simple, more in-depth analysis as follows.

      Wide-NN requirement. The non-convexity is the nature of machine learning. For example, a simple MLP with ReLU as an inner activation function is non-convex. The optimization of NN is typically achieved by utilizing a simple first-order method to solve a non-convex problem. The convergence proof of such a process is extremely non-trivial since we can hardly make any reformulations of the variables (parameters of NN). Due to this difficulty, we cannot utilize many existing mathematical techniques, such as relaxation or primal-dual. However, the NTK theorem raises based on the Polyak-Łojasiewicz (PL) inequality, which derives a linear convergence rate from L-smoothness and $\frac{1}{2}\Vert \nabla f(x) \Vert^2 \geq \mu(f(x)-f^*)$ (PL inequality) [2]. The second term, PL inequality, requires that the gradient can be lower bounded by the objective and optimal value, which is a non-negative term. In the scenarios of NTK, the $\Vert \nabla f(x) \Vert^2$ (named NTKernal matrix) is calculated by \lambda_\min (\nabla f(x) \nabla f(x)^T) (and further decoupled to layer-wise derivative [3]), where $\nabla f(x)$ is $N$-by-$w$ matrix, $w$ is the denotation for a layer's width, N is number of samples. The PL-inequality defines the NTK matrix to be non-singular, which requires at least one layer to be wide, such that there exists some $w \geq N$.

   2. Relaxation? (Q2: finite-width regime)

      Since the convergence rate from NTK theory is linear but requires a strict condition of a wide NN, we can trivially expect some space for relaxation (a thin NN) and a corresponding slower convergence rate, for example, sub-linear. Empirically, it does since most applications of NN are not wide. Our result in Figure 8 is an example. However, to our knowledge, there are no existing theoretical works to achieve that.

2. Q3: Larger experiments

   For larger settings, we think it is not within the scope of this work. We would like to try to learn to optimize larger NNs in the future. However, it has gained a lot of attention and has several successful deployments in real-world scenarios. The related research topic is Meta-Learning. Nowadays, the most popular research direction of Meta-Learning is utilizing reinforcement learning to fine-tune LLMs.

Citation:

[1] Kearns, Michael J., and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.

[2] Karimi, Hamed, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition. Joint European conference on machine learning and knowledge discovery in databases. Cham: Springer International Publishing, 2016.

[3] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. ICML, 2021