Learning Provably Improves the Convergence of Gradient Descent Qingyu Song Xiamen University simmonssong96@gmail.com Wei Lin, Hong Xu The Chinese University of Hong Kong wlin23@cse.cuhk.edu.hk, hongxu@cuhk.edu.hk Abstract Learn to Optimize (L2O) trains deep neural network-based solvers for optimization, achieving success in accelerating convex problems and improving non-convex solutions. However, L2O lacks rigorous theoretical backing for its own training convergence, as existing analyses often use unrealistic assumptions—a gap this work highlights empirically. We bridge this gap by proving the training convergence of L2O models that learn Gradient Descent (GD) hyperparameters for quadratic programming, leveraging the Neural Tangent Kernel (NTK) theory. We propose a deterministic initialization strategy to support our theoretical results and promote stable training over extended optimization horizons by mitigating gradient explosion. Our L2O framework demonstrates over 50% better optimality than GD and superior robustness over state-of-the-art L2O methods on synthetic datasets. The code of our method can be found from https://github.com/NetX-lab/MathL2OProof-Official . 1 Introduction Learn to optimize (L2O) represents an increasingly influential paradigm for tackling optimization problems [ 6 ] . Numerous studies have demonstrated the efficacy of employing learning-based models to achieve superior performance across a spectrum of optimization tasks. These encompass convex problems, exemplified by LASSO [ 7 , 23 , 8 ] and logistic regression [ 22 , 34 ] , and non-convex scenarios such as MIMO sum-rate maximization [ 35 ] and network resource allocation [ 33 ] . Distinct from black-box approaches [ 36 , 41 , 5 ] , which directly derive solutions to optimization problems from a neural network (NN), the so-called “white-box” methodologies are garnering increased attention. This heightened interest stems from their inherent advantages, such as enhanced trustworthiness [ 14 ] and theoretical guarantees [ 34 ] . A key characteristic of these white-box strategies is the integration of mechanisms to ensure the “controllability” of the generated solutions. For instance, Lv et al. [25] employ a NN to predict the step size for the gradient descent (GD) algorithm, where the inherent structure of GD stabilizes the optimization trajectory. Similarly, Heaton et al. [14] integrate a conventional solver within an L2O framework to act as a safeguard, thereby preventing the learning-based model from producing solutions with extreme violations. This principle of guided or constrained learning has also been extended to the training phase of L2O models [ 39 ] . Further, “unrolling” has emerged as a prominent technique within L2O [ 6 ] , characterized by the strategic replacement of components of conventional optimization algorithms with neural network (NN) blocks [ 15 , 12 , 20 ] . For instance, Liu et al. [22] introduce Math-L2O that imposes architectural constraints on unrolled L2O models by deriving necessary conditions for their convergence. Their analysis revealed that for a L2O model to achieve optimality, its embedded NN must effectively perform a linear combination of input feature vectors, weighted by learnable parameter matrices. Empirical validation demonstrates that the proposed methods exhibit strong generalization capabilities when trained using a coordinate-wise input-to-output strategy. Subsequent research by Song et al. [34] further enhance this generalization performance by reducing the magnitude of input features. Despite these advancements, to the best of our knowledge, a formal demonstration of the convergence for unrolling-based L2O methods in solving general optimization problems remains elusive. While LISTA-CPSS [ 7 ] establishes convergence for the well-known LISTA framework [ 12 ] , its analysis is based on the assumption that neural network (NN) outputs are confined to a specific subspace, a condition that is often not met in practical implementations. Similarly, while Math-L2O [ 22 ] derives necessary conditions for convergence, the mechanisms by which the training process itself can guarantee such convergence are not elucidated. Subsequent analysis by Song et al. [34] investigates the inference-time convergence of Math-L2O. However, this work relies on a stringent training assumption, effectively constraining the L2O model to emulate the behavior of a conventional Gradient Descent (GD) algorithm. This apparent deficiency in comprehensively demonstrating L2O convergence stems from two fundamental, unresolved technical challenges. First, unrolling-based L2O models [ 12 , 23 , 8 ] represent a specialized class of NN architectures. Despite much progress in understanding the training convergence of general neural networks (NNs), notably through the Neural Tangent Kernel (NTK) theory since 2019 [ 2 , 11 , 3 , 29 , 30 , 24 ] , a formal proof of training convergence remains conspicuously absent. Such a proof is an essential precursor to establishing the convergence of the L2O model in its primary task of solving optimization problems. Second, the precise relationship between the training convergence achieved during the L2O model’s training phase (i.e., optimizing the NN parameters) and the convergence of the L2O model when applied to the target optimization problem (i.e., finding the optimal solution) is not well understood. For instance, Math-L2O [ 22 ] is designed to learn the step size for an underlying GD algorithm. While the problem-solving efficacy of Math-L2O is naturally evaluated based on the progression of GD iterations, its training convergence is measured in terms of training steps (e.g., epochs). These two notions of convergence: one on model parameter optimization and the other on problem-solving iterations, are largely decoupled and operate on fundamentally different scales. In this work, we present the first rigorous demonstration that an unrolling framework can achieve theoretical convergence in solving optimization problems. Our analysis focuses on the state-of-the-art (SOTA) Math-L2O framework, wherein a NN functions as a recurrent block, iteratively generating hyperparameters for an underlying optimization algorithm. The solution obtained at each iteration, which utilizes these generated hyperparameters, is then incorporated as an input feature for the subsequent iteration [ 22 ] . This inherent recurrence imparts RNN-like characteristics to Math-L2O, significantly complicating the analysis of its training convergence. Specifically, the recurrent structure causes the NN to manifest as a high-order polynomial function with respect to (w.r.t.) its input features [ 3 ] . This characteristic poses challenges for establishing tight analytical bounds, potentially leading to looser convergence rates compared to non-recurrent architectures, as highlighted in related NTK analyses for RNNs [ 3 ] . Moreover, the Math-L2O architecture introduces an additional layer of complexity: the emergence of high-order polynomial dependencies not only on the input features but also on the learnable parameters themselves. This distinct feature renders the convergence proof for Math-L2O arguably more intricate than those for conventional RNNs, where such parameter-dependent high-order terms are typically less pronounced. We address the pivotal connection between the NN’s training convergence and the ultimate problem-solving convergence of the L2O model. Within the Math-L2O framework, we establish this critical linkage by explicitly demonstrating an alignment between the convergence dynamics exhibited during the NN’s training phase and the convergence characteristics of its underlying backbone optimization algorithm. This alignment provides a novel theoretical bridge, ensuring that a successfully trained L2O model translates to effective convergence when applied to optimization tasks. Our contributions are summarized as follows: 1. We provide a formal proof that the Math-L2O training framework substantially enhances the convergence performance of its underlying backbone algorithms. This is achieved by rigorously establishing an explicit alignment between the convergence rates of the training process and the iterative steps of the backbone algorithm. 2. We establish the first linear convergence rate for Math-L2O training. Inspired by [ 30 ] , we employ a NN architecture with a single wide layer and utilize NTK to prove the boundedness of NN outputs, gradients, and the training loss function within the Math-L2O framework. 3. We introduce a novel deterministic parameter initialization scheme, coupled with a specific learning rate configuration strategy. This combined approach is proven to guarantee the training convergence of the Math-L2O model across all iterations. 4. We empirically validate our theoretical findings through comprehensive experiments. The results showcase significant performance advantages, including up to a 50% improvement in solution optimality over the standard GD algorithm post-training, and superior robustness compared to SOTA L2O models and the Adam optimizer [ 10 ] . Furthermore, ablation studies empirically confirm the practical efficacy and individual contributions of our proposed theorems. 2 Preliminary This section first defines the optimization problem objective and the L2O framework. The L2O training loss is then formulated based on these definitions. Then, the NN’s computational graph is employed to detail the forward pass and the derivation of parameter gradients. 2.1 Definitions Let d>b , suppose x\in\mathbb{R}^{d\times 1} , y\in\mathbb{R}^{b\times 1} , and \mathbf{M}\in\mathbb{R}^{b\times d} , we define the optimization objective as: \min_{x\in\mathbb{R}^{d}}f(x)=\tfrac{1}{2}\|\mathbf{M}x-y\|_{2}^{2}. (1) This objective function is commonly selected for convergence analysis [ 4 ] . The least-squares problem, a frequent subject in NN convergence studies [ 11 , 2 , 3 , 21 , 30 ] , is a specific instance of the minimization in Equation 1 where d=b and \mathbf{M}=\mathbf{I} . We assume f to be \beta -smooth, such that \|\mathbf{M}^{\top}\mathbf{M}\|_{2}\leq\beta , and \mathbf{M} to possess full row rank, with \lambda_{\min}(\mathbf{M}\mathbf{M}^{\top})=\beta_{0}>0 . This setting often favors numerical algorithms (e.g., GD) over analytical solutions due to computational complexity. GD’s \mathbf{O}(bd) complexity is typically lower than the \mathbf{O}(b^{3}) of analytical methods involving costly matrix inversions. The loss function is then defined as the sum of N objectives specified in Equation 1 : F(X)=\tfrac{1}{2}\|\mathbf{M}X-Y\|_{2}^{2}, (2) where F , \mathbf{M}\in\mathbb{R}^{Nb\times Nd} , X\in\mathbb{R}^{Nd\times 1} , and Y\in\mathbb{R}^{Nb\times 1} represent the concatenated objectives, parameters, variables, and labels, respectively, from N optimization problems (see Section A.1 for details). F is also \beta -smooth, given that \|\mathbf{M}^{T}\mathbf{M}\|_{2}\leq\max_{i=1,\dots,N}\{\|\mathbf{M}_{i}^{T}\mathbf{M}_{i}\|_{2}\}=\beta . Learn to Optimize (L2O). Given an initial point X_{0} , L2O takes X_{0} as the input and generates a solution, denoted as X_{t} , with a machine learning model. Typically, let g_{W} denote an L -layer NN with parameters W=\{W_{1},\dots,W_{L}\},W_{\ell}\in\mathbb{R}^{n_{\ell}\times n_{\ell-1}},n_{1},\dots,n_{L}\in\mathbb{R} . Math-L2O [ 22 ] takes an iterative workflow to generate solutions. For each step t\in[T] in solving the problem in Equation 1 , the NN model in Math-L2O is defined as g_{W}(X_{t-1},\nabla F(X_{t-1})) . The NN receives the current state variable X_{t-1} and its gradient \nabla F(X_{t-1}) as input. The update rule at step t , which employs the Hadamard product (denoted by \odot ), is formulated as: \displaystyle X_{t} \displaystyle=X_{t-1}-\tfrac{1}{\beta}P_{t}\odot\nabla F(X_{t-1}),P_{t}=g_{W}(X_{t-1},\nabla F(X_{t-1})). (3) P_{t} represents a vector whose entries are learned step sizes. The NN g_{W} takes structured layer-wise architecture. It employs a coordinate-wise architecture, processing each input dimension independently, recognized for its robustness in L2O applications [ 22 , 34 ] . Thus, output dimension of the NN is one, i.e., n_{L}=1 . Denote [L]:=\{1,\dots,L\} , for layer \ell\in[L] , we denote G_{\ell,t} as the (inner) output of layer \ell at step t . Utilizing ReLU ( \relu ) [ 1 ] and Sigmoid ( \sigma ) [ 27 ] activations, G_{\ell,t} is defined as: G_{\ell,t}=\begin{cases}[X_{t-1},\nabla F(X_{t-1})]^{\top}&\ell=0,\\ \relu(W_{\ell}G_{\ell-1,t})&\ell\in[L-1],\\ P_{t}=2\sigma(W_{L}G_{L-1,t})^{\top}&\ell=L.\end{cases} (4) The L2O training problem is defined by: F(W)=\tfrac{1}{2}\|\mathbf{M}X_{T}-Y\|_{2}^{2},X_{T}=L2O_{W}(X_{0},\nabla F(X_{0})). (5) 2.2 Layer-Wise Derivative of NN’s Parameters Let k denote a training iteration for loss Equation 5 minimization, which is distinct from an optimization step t for solving objective Equation 2 . The computational graph in Figure 1 illustrates the Math-L2O forward and backward operations, which parallel those of Recurrent Neural Networks (RNNs) [ 13 ] . Figure 1(a) details the NN block (see Equation 4 ). Figure 1(b) depicts the overall process: the block takes an input solution, performs T internal optimization steps to produce an updated solution (red dashed arrows), and each training iteration k triggers a full backward pass (blue bold lines). As per [ 22 ] , the gradient flow from the input features to the NN block is detached. (a) NN Block (b) Forward and Backward Processes Figure 1 : Computational Graph of Math-L2O The derivative of an objective F w.r.t. the parameters W_{\ell} of layer \ell is determined via the computational graph, paralleling Back-Propagation-Through-Time (BPTT) for RNNs [ 26 ] : \tfrac{\partial F}{\partial W_{\ell}}=\tfrac{\partial F(X_{T})}{\partial X_{T}}\Big({\sum}_{t=1}^{T}\big({\prod}_{j=T}^{t+1}\tfrac{\partial X_{j}}{\partial X_{j-1}}\big)\tfrac{\partial X_{t}}{\partial P_{t}}\tfrac{\partial P_{t}}{\partial W_{\ell}}\Big). (6) The summation aggregates gradients across T optimization steps. {\prod}_{j=T}^{t+1}(\partial X_{j}/\partial X_{j-1}) represents the chain rule application from the final output X_{T} to an intermediate state X_{t} . Moreover, we derive two key gradients, instrumental for establishing the theoretical results in the ensuing section. Following Definition 2.2 in [ 2 ] , the gradient of the ReLU is represented by a diagonal matrix \mathbf{D}_{\ell}^{t} , where its i -th diagonal element is [\mathbf{D}_{\ell}^{t}]_{i,i}\coloneqq\mathbf{1}_{(W_{\ell}G_{\ell-1,t})_{i}\geq 0} for i\in[n_{\ell}] . Let \Gamma_{t}\coloneqq\mathbf{M}^{\top}(\mathbf{M}{X_{t}}-Y) and \Xi_{\ell}\coloneqq(\mathbf{I}_{d}\otimes W_{L})({\prod}_{j=L-1}^{\ell+1}\mathbf{D}_{j,t}(\mathbf{I}_{d}\otimes W_{j}))\mathbf{I}_{n_{\ell}} . Defining \mathcal{D}(\cdot) as the operator that constructs a diagonal matrix from a vector, the gradients for an inner layer W_{\ell} ( \ell1 for all j\neq i . Following the experimental design in [ 22 ] , we quantify the violation percentage of the aforementioned conditions during inference. The results are presented in Figure 3 . We consider two settings: (i) shared parameters W across iterations ( Figure 3(a) ), and (ii) unique parameters W_{t} per step t ( Figure 3(b) ). Both scenarios reveal that the specified conditions are frequently violated post-training. For instance, in the shared W case ( Figure 3(a) ), while the conditions hold in later steps, substantial violations occur in early steps. The divergence contradicts the convergence rate analysis presented in [ 7 ] . (a) Shared W (b) Unique W_{t} per Step Figure 3 : Violation Ratio of LISTA-CPSS Conditions During Inference The preceding observations highlight that training is indispensable for L2O convergence analysis. Three fundamental questions arise in L2O: (i) What is the impact of training on convergence? (ii) How can training be incorporated into the convergence analysis framework? (iii) What mechanisms ensure a stable training process? We propose a concise approach to address these questions, establishing a direct alignment between the training’s convergence rate and an existing algorithm’s rate. 3.2 L2O Convergence Demonstration: Aligning L2O to An Algorithm First, we introduce a general convergence analysis framework. Let X^{*} be the optimal solution, r_{t} represents an iteration-dependent rate term, and C(X_{0}) be a constant that dependent on the initial point X_{0} (and X^{*} ), the convergence rate of an algorithm (either learned or classical) for minimizing an objective F(X) (e.g., the objective in Equation 1 or the loss in Equation 2 ) is often formulated as: F(X_{t})\leq r_{t}C(X_{0}) . For example, standard GD has a rate of F(X_{t})\leq\frac{\beta}{t}\|X_{0}-X^{*}\|_{2}^{2} [ 4 ] . The performance of L2O models, stabilized via training, is typically assessed after T iterations [ 22 , 34 ] . We formulate the L2O training convergence rate w.r.t. training iteration k as: F(X_{T}^{k})\leq r_{k}C(X_{T}^{0}),\quad\text{where }X_{T}^{0}=\text{L2O}_{W^{k}}(X_{0}^{0}), (9) with X_{T}^{0} being the initial solution from the L2O model and a constant mapping C . Based on the proof in [ 38 ] , non-learning GD algorithm’s convergence rate corresponding to the initial L2O state is: F(X_{T}^{0})\leq\tfrac{\beta}{T}\|X_{0}^{0}-X^{*}\|_{2}^{2}. (10) Given the independence of training iteration k and optimization step T , we align the LHS of Equation 9 with the RHS of Equation 10 by setting C(X_{T}^{0})=F(X_{T}^{0}) . Given initial point is constant that X_{T}^{0}=X_{T}^{k} , this yields the combined training convergence rate: F(X_{T}^{k})\leq r_{k}\tfrac{\beta}{T}\|X_{0}^{k}-X^{*}\|_{2}^{2}. (11) Here, the LHS represents the objective value after k training iterations, while the RHS is a constant term dependent on the initial point X_{0} . W.r.t. T , Equation 11 demonstrates a sub-linear convergence rate of at least \mathcal{O}(1/T) . The rate indicates that integrating L2O with an existing algorithm via training can enhance its convergence. Such integration is achieved by the Math-L2O framework [ 22 ] , which utilizes a NN to learn hyperparameters for non-learning algorithms (e.g., step size for GD, step size and momentum for Nesterov Accelerated Gradient [ 4 ] ). Further, we construct the Math-L2O training rate r_{k} (see Equation 9 ). Section 4 establishes its linear convergence. Subsequently, Section 5 proposes a deterministic initialization strategy to ensure the alignment ( C(X_{T}^{0})=F(X_{T}^{0}) ) and uphold the theoretical conditions for this linear rate. 4 Linear Convergence of L2O Training In this section, we establish the linear convergence rate for training a Math-L2O model employing an over-parameterized NN, w.r.t. the loss defined in Equation 2 . By training the NN ( Equation 4 ) using GD, we establish its linear convergence rate via NTK theory. Classical NTK theory [ 16 ] requires infinite NN width to maintain a non-singular kernel matrix, which facilitates a gradient lower bound akin to the Polyak-Lojasiewicz condition [ 32 , 30 ] . Applying the relaxation from [ 30 ] and the rigorous NN formalizations ( Section 2 ), we demonstrate that an NN width of \mathcal{O}(Nd) is sufficient. To derive the rate, we first introduce a lemma to bound Math-L2O’s gradients. We then prove that appropriate initialization leads to deterministic loss minimization in the initial training iteration. After that, we develop a strategy to maintain this property throughout training, thereby ensuring convergence. This approach culminates in a linear convergence rate for an \mathcal{O}(Nd) -width NN. The main results are summarized herein, with detailed proofs deferred to Section A.5 and Section A.6 . 4.1 Bound Outputs of Math-L2O We define \alpha_{0}\coloneqq\sigma_{\min}(G^{0}_{L-1,T}) and let C_{\ell}>0 for \ell\in[L] be any sequence of positive numbers. Moreover, for t,j\in[T] , we define the following quantities: \!\!\begin{aligned} &\bar{\lambda}_{\ell}=\|W_{\ell}^{0}\|_{2}+C_{\ell},\Theta_{L}=\textstyle\prod_{\ell=1}^{L}\bar{\lambda}_{\ell},\Phi_{j}=\|X_{0}\|_{2}+\frac{2j-1}{\beta}\|\mathbf{M}^{\top}Y\|_{2},\\ &\Lambda_{j}=(1+\beta)\|X_{0}\|_{2}^{2}+\tfrac{(4j-3)(1+\beta)+\beta}{\beta}\|X_{0}\|_{2}\|\mathbf{M}^{\top}Y\|_{2}+\tfrac{(2j-1)(\beta(2j-1)+(2j-2))}{\beta^{2}}\|\mathbf{M}^{\top}Y\|_{2}^{2},\\ &\begin{aligned} S_{\Lambda,T}&=\textstyle\sum_{t=1}^{T}\Lambda_{t},&\delta_{1}^{t}&=\textstyle\sum_{s=1}^{t}\left(\textstyle\prod_{j=s+1}^{t}(1+\tfrac{1+\beta}{2}\Theta_{L}\Phi_{j})\right)\Lambda_{s},\\ S_{\bar{\lambda},L}&=\textstyle\sum_{\ell=1}^{L}\bar{\lambda}_{\ell}^{-2},&\delta_{2}&=\textstyle\sum_{s=1}^{T-1}\left(\textstyle\prod_{j=s+1}^{T-1}(1+\tfrac{1+\beta}{2}\Theta_{L}\Phi_{j})\right)\Lambda_{s},\\ \zeta_{1}&=\sqrt{\beta}\|X_{0}\|_{2}+(2T+1)\|Y\|_{2},\quad&\delta_{3}&=(1+\beta)\|X_{0}\|_{2}+\big(2T-1+\tfrac{2T-2}{\beta}\big)\|\mathbf{M}^{\top}Y\|_{2},\\ \zeta_{2}&=\|X_{0}\|_{2}+\tfrac{2T-2}{\beta}\|\mathbf{M}^{\top}Y\|_{2},&\delta_{4}&=\sigma(\delta_{3}\Theta_{L})(1-\sigma(\delta_{3}\Theta_{L})),\\ \end{aligned}\end{aligned} (12) where X_{0} denotes the initial point, and \mathbf{M} (parameter matrix) and Y (labels) are input features from Equation 2 . The defined quantities are positive under the conditions j\geq 1 and \bar{\lambda}_{\ell}>0 . First, we derive a bound for the training gradients by considering them as perturbations from initialization. This bound relates the gradient magnitude to the objective function in Equation 2 , as detailed in the following lemma. Despite the derivative for inner layers ( Equation 7 ) containing an additional term compared to that of the last layer ( Equation 8 ), a uniform bound as stated applies. The proof is provided in Section A.5.4 . Lemma 4.1 . Assuming \max(\|W_{\ell}^{k+1}\|_{2},\|W_{\ell}^{k}\|_{2})\leq\bar{\lambda}_{\ell} for \ell\in[L] , for any training iteration k , the gradient of the \ell -th layer parameters W_{\ell}^{k} is bounded by: \big\|\frac{\partial F}{\partial W_{\ell}^{k}}\big\|_{2}\leq\frac{\sqrt{\beta}\Theta_{L}S_{\Lambda,T}}{2\bar{\lambda}_{\ell}}\|\mathbf{M}X_{T}^{k}-Y\|_{2}. Building upon Lemmas A.6 and 4.1 and auxiliary results (see Section A.5 ), we analyze the dynamics of the final solution X_{T} w.r.t. parameter updates during training. The subsequent lemma establishes a rigorous formulation for the fluctuation of X_{T} in response to changes in parameters between adjacent training iterations. This result demonstrates that Math-L2O, viewed as a function of its learnable parameters, exhibits semi-smoothness, aligning with findings for ReLU-Nets in [ 30 ] . The proof is provided in Section A.5.3 . The semi-smoothness of the Math-L2O NN is preserved despite its recurrent operations. The coefficient associated with \|W_{\ell}^{k+1}-W_{\ell}^{k}\|_{2} exhibits \mathcal{O}(e^{LT}) scaling, where e is an initialization parameter detailed in Section 5 . This represents a looser bound compared to that for ReLU-Nets [ 30 ] , which is a consequence of Math-L2O’s greater architectural complexity, specifically the T -fold execution of an L -layer NN block (see Equation 8 ). However, this scaling behavior is consistent with observations for other deep architectures [ 2 ] . Lemma 4.2 . For any training iteration k , assume there exist constants \bar{\lambda}_{\ell}\in\mathbb{R}^{+} for \ell\in[L] such that \max_{k^{\prime}\in\{k,k+1\}}\|W_{\ell}^{k^{\prime}}\|_{2}\leq\bar{\lambda}_{\ell} . Let X_{t}^{k+1} and X_{t}^{k} be outputs of the Math-L2O (defined in Equations 3 and 4 ) corresponding to parameters W^{k+1}=\{W_{\ell}^{k+1}\}_{\ell=1}^{L} and W^{k}=\{W_{\ell}^{k}\}_{\ell=1}^{L} , respectively. Then, Math-L2O exhibits the following semi-smoothness property: \|X_{t}^{k+1}-X_{t}^{k}\|_{2}\leq\tfrac{1}{2}{\sum}_{s=1}^{t-1}\big({\prod}_{j=s+1}^{t}(1+(1+\beta)/2\Theta_{L}\Phi_{j})\big)\Lambda_{s}\Theta_{L}\big({\sum}_{\ell=1}^{L}\bar{\lambda}_{\ell}^{-1}\|W_{\ell}^{k+1}-W_{\ell}^{k}\|_{2}\big). Lemma 4.2 demonstrates that Math-L2O solutions exhibit a bounded response to perturbations in its NN parameters. This finding, in conjunction with Lemma 4.1 , facilitates a more nuanced analysis of the loss dynamics. Further, judicious selection of learning rates enables control over the evolution of NN parameters. Such control is instrumental in bounding the constant quantities from these lemmas, thereby establishing the desired convergence rate presented in the subsequent theorem. 4.2 Linear Training Convergence Rate of Math-L2O Leveraging the bounds on Math-L2O’s output ( Lemma A.6 ) and its gradient ( Lemma 4.1 ), the following theorem establishes the linear convergence rate for training the Math-L2O model. The proof is provided in Section A.6 . Theorem 4.3 . Consider the NN defined in Equation 4 , using quantities from Equation 12 , suppose the following conditions hold at initialization: Let the learning rate \eta satisfy: Then, for weights W^{k}=\{W_{\ell}^{k}\}_{\ell=1}^{L} at training iteration k , the loss function F(W^{k}) converges linearly to a global minimum: F(W^{k})\leq\big(1-4\eta\tfrac{\beta_{0}^{2}}{\beta^{2}}\delta_{4}\alpha_{0}^{2}\big)^{k}F(W^{0}). Remark 1 . (1-4\eta\frac{\beta_{0}^{2}}{\beta^{2}}\delta_{4}\alpha_{0}^{2})^{k} is r_{k} in Equation 11 , which is a less than one term since \delta_{4}=\sigma(\delta_{3}\Theta_{L})(1-\sigma(\delta_{3}\Theta_{L}))>0 and \alpha_{0}:=\sigma_{\min}(G_{L-1,T}^{0})>0 ( G_{L-1,T}^{0} is a thin matrix), which ensure that the L2O converges at least as fast as GD. Equations 14a and 14b are based on the quantities defined in Equation 12 . Each quantity represents an inner formulation in the demonstration of lemmas and theorems. We use these quantities to simplify the formulations. The conditions specified in Equation 13 impose additional lower bounds on \alpha_{0} , the minimal singular value of the (L-1) -th layer’s inner output. The bounds stipulated in Equations 13c , 13d and 13b are influenced by both the network depth L and the number of gradient descent (GD) iterations T . In contrast, the constraint in Equation 13a primarily depends on T . An initialization strategy ensuring these conditions are met is proposed in Section 5 . We provide a detailed interpretation in Section A.2 . 4.3 Analysis of Learning Rate Magnitude The bounds in Equations 14a and 14b indicate that the learning rate \eta diminishes as L and T increase. We argue that this requirement for a small \eta is not a significant limitation; it is consistent with the NTK framework, which does not rely on large learning rates for convergence. To quantify this, we examine the scaling of \eta relative to T,L, and \bar{\lambda}_{\max} . Here, \bar{\lambda}_{\max}=\max\{\bar{\lambda}_{\ell}\},\ell\in[L] is the maximum constant upper bound on the singular values of the NN layers ( Equation 12 ). These bounds are parameters that can be directly influenced by the choice of initialization method. First, analyzing Equation 14a , we derive the scaling of \eta as \mathcal{O}(\frac{T\bar{\lambda}_{\max}^{LT}+T^{2}}{((T\bar{\lambda}_{\max}^{LT})+\bar{\lambda}_{\max}^{L}T^{3}L\bar{\lambda}_{\max}^{-2})T^{6}}) , where constant factors independent of T and L are omitted. This expression highlights that the magnitude of \eta is strongly dependent on the bound \bar{\lambda}_{\max} . This dependence implies that the learning rate can be prevented from becoming extremely small by using a proper initialization method (such as our proposed method in Section 5) to control \bar{\lambda}_{\max} . Moreover, Equation 14b shows that \eta ’s magnitude is highly correlated with the lower bound of \alpha_{0} (the penultimate layer’s singular value, per Section 4.1 ). Given the four distinct lower bounds for \alpha_{0} derived in Equation 13 , we now formulate the magnitude of \eta for each respective case. First, if Equation 13c holds, \eta=\mathcal{O}(\exp(2T\bar{\lambda}_{\max}^{L})T^{-2}) , which is a non-restrictive bound due to the exponential term. Second, if Equation 13d holds, \eta=\mathcal{O}((\bar{\lambda}_{\max}^{2L}T^{4}+\bar{\lambda}_{\max}^{2L}(T+T\bar{\lambda}_{\max}^{LT})L\bar{\lambda}_{\max}^{-2}T^{3})^{-1}) . This scales inversely with \bar{\lambda}_{\max} and exponentially with L and T . Third, if Equation 13b holds, \eta=\mathcal{O}(\bar{\lambda}_{\max}^{-L}T^{-3}) , which also scales inversely with \bar{\lambda}_{\max} and exponentially with L . Finally, if Equation 13a holds, \eta=\mathcal{O}(\exp(\frac{2}{3}T\bar{\lambda}_{\max}^{L})(\bar{\lambda}_{\max}^{2L}T^{2}L\bar{\lambda}_{\max}^{-2})^{-\frac{2}{3}}) , which, similar to the first case, is a non-restrictive bound due to the exponential term. The foregoing results indicate that a larger \bar{\lambda}_{\max} correlates with a smaller learning rate \eta . Nevertheless, this does not result in a degradation of convergence speed. This conclusion is supported by two observations: Theoretical Consistency : The requirement for a small \eta is permissible under NTK theory [ 16 ] . The NTK regime assumes infinitely wide networks, where convergence is achieved within a compact space around the initialization, thus obviating the need for large learning steps. Empirical Insensitivity : Our experimental results demonstrate that the convergence speed is robust to the learning rate. As depicted in Figure 4(a) , our method achieves similar convergence rates for \eta across a wide range (e.g., 10^{-3} to 10^{-7} ). Adopting a small learning rate is a pragmatic trade-off to avoid the requirement for an extremely wide NN. Existing analyses [ 3 , 30 ] that remove the infinite-width assumption often impose a polynomial width dependency (e.g., \mathcal{O}(N^{3}) ) on the sample size N . In our framework ( Section 2 ), the coordinate-wise L2O treats d -dimensional features as independent inputs, leading to an effective sample size of Nd . A polynomial dependency on Nd would be impractical. Therefore, we opt for the alternative constraint of a smaller learning rate, which permits a feasible network width. 5 Deterministic Initialization This section introduces an initialization strategy ensuring the alignment between Math-L2O and GD (see Section 3 ) while also satisfying the conditions presented in Section 4 . The proposed initialization strategy first establishes Math-L2O to operate as a standard GD algorithm, and then guarantees the uniform convergence of Math-L2O throughout subsequent training iterations. 5.1 Initialization for Alignment Following methodology in [ 30 ] , we let C_{\ell}=1 for \ell\in[L] . For parameter matrices initialization W (see Section 2 ), we randomly initialize parameter matrices of first L-1 layers, i.e, \{W_{1}^{0},\dots,W_{L-1}^{0}\} from a standard Gaussian distribution and set the last layer’s parameter matrix W_{L}^{0}=\mathbf{0} . Through the 2\sigma activation detailed in Equation 4 , it outputs a constant step size, i.e., P_{T}=\mathbf{I} . Consequently, the learning proceeds with a uniform step size of 1/\beta after initialization, emulating standard GD and its typical sub-linear convergence rate [ 38 ] . Moreover, this zero-initialization of W_{L}^{0} ensures that initial gradients for the inner layers are all zero (as shown in Equation 7 ), which serves to mitigate gradient explosion. The condition \alpha_{0}>0 (see Theorem 4.3 ) is fulfilled by randomly sampling the initial weight matrices \{W_{k}^{0}\}_{k=1}^{L-1} from a standard Gaussian distribution. This approach generally ensures full row rank for fat matrices (more columns than rows) [ 37 ] . Each matrix W_{k}^{0} then undergoes QR decomposition. Non-negativity is subsequently enforced upon the elements of the resulting upper triangular factor (e.g., via its element-wise absolute value, achieved in PyTorch using its sign function). 5.2 Enhancing Singular Values for Linear Convergence of Training Motivated by properties of minimal singular values in ReLU-Nets identified in [ 30 ] , we analyze the order-gap for \alpha_{0} between the left-hand side (LHS) and right-hand side (RHS) of the inequalities in Equation 13 . To satisfy these inequalities, we propose increasing \alpha_{0} . This is achieved by applying a constant expansion coefficient e\geq 1 to the initial NN parameters \{W_{1}^{0},\dots,W_{L-1}^{0}\} , transforming them to \{eW_{1}^{0},\dots,eW_{L-1}^{0}\} . This parameter expansion scales the minimal singular value \alpha_{0} to e^{L-1}\alpha_{0} , reflecting the cumulative impact across L-1 layers. However, other terms on the RHS of Equation 13 also depend on e . We then establish four lemmas to demonstrate that the conditions for linear convergence, as specified in Theorem 4.3 , are met for an appropriately chosen value of e . First, we set the initial point to the origin, X_{0}=\mathbf{0} , a choice commonly adopted in L2O literature [ 22 , 34 ] . Then, with C_{\ell}=1 for \ell\in[L] , we present four lemmas demonstrating that the conditions for linear convergence (see Theorem 4.3 ) are satisfied for an appropriately chosen constant e . The lemmas indicate that a larger e is required as the number of optimization steps ( T ) increases. Specifically, Lemma 5.2 establishes that e scales exponentially with T . Conversely, increasing the network depth ( L ) alleviates the need for a large e . The proofs are provided in Appendix B . Lemma 5.1 . Assuming X_{0}=\mathbf{0} , if e=\mathbf{\Omega}(T^{\frac{1}{L-1}}) , then the inequality Equation 13a holds. Lemma 5.2 . If e=\mathbf{\Omega}(T^{\frac{3T+6}{TL-T-4L+6}}) , then the inequality Equation 13b holds. Lemma 5.3 . Assuming X_{0}=\mathbf{0} , if e=\mathbf{\Omega}(T^{\frac{4}{L-1}}) , then the inequality Equation 13c holds. Lemma 5.4 . Assuming X_{0}=\mathbf{0} , if e=\mathbf{\Omega}(T^{\frac{5}{L-1}}L^{\frac{1}{L-1}}) , then the inequality Equation 13d holds. 6 Empirical Evaluation This section presents an empirical evaluation of the framework proposed in Section 3 and the theoretical results from Section 4 . Experiments are conducted using Python 3.9 and PyTorch 1.12.0 on an Ubuntu 20.04 system equipped with 128GB of RAM and two NVIDIA RTX 3090 GPUs. Data Generation. Due to GPU memory constraints, vectors X\in\mathbb{R}^{5120\times 1} and Y\in\mathbb{R}^{4000\times 1} for Equation 2 are generated by sampling from a standard Gaussian distribution. These represent ten problem instances with respective dimensional components of 512 (for X ) and 400 (for Y ). Following the coordinate-wise approach in [ 22 ] , we formed an input feature matrix of 5120\times 2 . This setup is equivalent to a training batch of 5120 two-feature samples. Math-L2O Model Architecture. The Math-L2O model is configured with T=100 optimization steps ( Equation 2 ). Its architecture comprises a L=3 -layer DNN, as formulated in Equation 4 . The first layer has an output dimension of 2 . To ensure over-parameterization, the (L-1) -th (i.e., second) layer’s output dimension is set to 512\times 10=5120 . The final layer produces a scalar output (dimension 1 ). Three specific model configurations are designed for ablation studies, foundational experiments, and robustness evaluations. These are detailed in Section C.1 . Training and Initialization Configurations. L2O models are trained using the Stochastic Gradient Descent (SGD) optimizer. For the L=3 -layer network configuration, parameters for the initial two layers ( l=1,2 ) are initialized according to the methodology presented in Section 5.1 , while parameters for the final layer ( l=3 ) are zero-initialized. 6.1 Training Performance We evaluated the mean training loss in Equation 2 across all samples. Figure 4(a) illustrates this loss at T=100 , benchmarked against the standard GD objective (black dashed line). The results demonstrate that Math-L2O consistently achieves fast training convergence, corroborating the theoretical linear convergence established in Theorem 4.3 . Further, we investigated the robustness of our proposed L2O method to variations in optimization steps and learning rates (LRs). Models corresponding to different step/LR configurations are trained for 400 epochs. Figure 4(b) presents the training objectives for these configurations, benchmarked against standard GD (black dashed line). In contrast to the instability observed for Math-L2O [ 22 ] and LISTA-CPSS [ 7 ] under certain settings ( Figure 2 ), the consistent convergence across all tested configurations in Figure 4(b) demonstrates the robustness of our proposed L2O approach. (a) Loss with Training Iteration (b) Loss with Optimization Step Figure 4 : Training Loss of Our L2O Moreover, we evaluate the inference performance of our framework against baseline methods. Experimental results (in Section C.4 ) demonstrate the framework’s robustness to hyperparameters. 6.2 Ablation Studies for Learning Rate \eta and Expansion Coefficient e We conduct ablation studies to assess the impact of the LR \eta , theoretically bounded in Equations 14a and 14b ( Theorem 4.3 ), and the initialization coefficient e , defined in Section 5 . The experimental configuration employs T=20 , input X\in\mathbb{R}^{32\times 32} , output Y\in\mathbb{R}^{32\times 20} , and a neural network width of 1024. Performance is measured by the relative improvement of the proposed L2O method over standard GD at iteration T=20 , calculated as \frac{\text{obj}_{\text{GD}}-\text{obj}_{\text{L2O}}}{\text{obj}_{\text{GD}}} . These studies further validate Corollary C.1 , which establishes an inverse relationship between the viable LR \eta and the coefficient e , implying that a larger e necessitates a smaller \eta to ensure convergence. With the initialization coefficient fixed at e=50 , we evaluate the impact of varying the LR \eta on the relative objective improvement. The results in Figure 5(a) demonstrate that while LRs such as 10^{-4} and smaller achieve convergence, \eta=10^{-3} leads to unstable behavior or divergence. This finding empirically supports the existence of an operational upper bound on the LR, consistent with the theoretical constraints outlined in Equations 14a and 14b . Moreover, reducing the LR below this stability threshold results in slower convergence rates. This observation aligns with the implication of Theorem 4.3 that, under the specified conditions, larger permissible LRs yield faster convergence. Fixing the LR at \eta=10^{-7} , we examine the influence of the initialization coefficient e on performance. The results, presented in Figure 5(b) , demonstrate that the relative objective improvement consistently increases with larger values of e . Additional results exploring different e and LR combinations are deferred to Appendix C owing to space constraints. These findings validate the proposed strategies for selecting the initialization coefficient and learning rate. (a) Ratio with Learning Rate \eta , e=50 (b) Ratio with Expansion Coefficient e , \eta=10^{-7} Figure 5 : Ablation Studies of Improve Ratio to Learning Rate and Expansion Coefficient 7 Conclusion This work analyzes a Learning-to-Optimize (L2O) framework that accelerates Gradient Descent (GD) through adaptive step-size learning. We theoretically prove that the L2O training enhances GD’s convergence rate by linking network training bounds to GD’s performance. Leveraging Neural Tangent Kernel (NTK) theory and the over-parameterization scheme via wide layers, we establish convergence guarantees for the complete L2O system. A principled initialization strategy is introduced to satisfy the theoretical requirements for these guarantees. Empirical results across various optimization problems validate our theory and demonstrate substantial practical efficacy. Appendix A Appendix A.1 Details for Definitions General L2O. Given X_{0} , we have the following L2O update with NN g to generate X_{T} : X_{t}=X_{t-1}+g(W_{1},W_{2},\dots,W_{L},X_{t-1},\nabla F(X_{t-1})),t\in[T]. (15) Concatenation of N Problems. For t\in[T] , we make the following denotations to represent the concatenation of N samples (each is a unique optimization problem): \displaystyle\mathbf{M} \displaystyle:=\begin{bmatrix}\mathbf{M}_{1}&&\\ &\dots&\\ &&\mathbf{M}_{N}\\ \end{bmatrix},X_{t}:=[x_{1,t}^{\top}|x_{2,t}^{\top}|\dots|x_{N,t}^{\top}]^{\top},Y:=[y_{1}^{\top}|y_{2}^{\top}|\dots|y_{N}^{\top}]^{\top}. X_{t} and Y are still column vectors since we take the coordinate-wise setting from [ 22 ] . A.2 Detailed Interpretation of Quantities in Theorem 4.3 We elaborate on the quantities introduced in Theorem 4.3 . Our notational convention is as follows: subscripts T and k identify constant terms that are dependent on the total steps T and the training iteration k . Conversely, indices j and t (appearing as superscripts or subscripts) are used to reference scalar-valued functions at a specific step t or index j . • \bar{\lambda}_{\ell} is a positive constant upper bound for each \ell -th layer in NN g_{W} (see Section 2 ), which is constructed in the proof of Theorem 4.3 . • \Theta_{L} is a positive constant w.r.t. \bar{\lambda}_{\ell} . • Denote \bar{\lambda}_{\min},\bar{\lambda}_{\max}:=\min\{\bar{\lambda}_{\ell}\},\max\{\bar{\lambda}_{\ell}\},\ell\in[L] , \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} is a scalar-valued function w.r.t. step j . The constant coefficients are given by initial point X_{0} , coefficient matrix \mathbf{M} , and coefficient vector Y from problem defined in Equation 2 . \beta is the smoothness extent of objective. We use two denotations, j and t , for step, which are used to formulate different computations in formulations. This formulation is derived by the upper bound relaxation of L_{2} -norm of gradient at X_{0} . \Phi_{j} is \mathcal{O}(j) and \Omega(j) . • \Lambda_{j} is a scalar-valued function w.r.t. step j , which is identical to those in \Phi_{j} . \Lambda_{j} is \mathcal{O}(j^{2}) and \Omega(j^{2}) . • S_{\Lambda,T} and S_{\bar{\lambda},L} are positive constants, which represents the summation of \Lambda of T steps and summation of \bar{\lambda} of L -th NN layers, respectively. • S_{\Lambda,T} is used in the demonstration for Lemma 4.1 (bound of gradient of NN training), line 625, page 22. The proof is achieved by upper bound relaxation of L_{2} -norm. S_{\bar{\lambda},L} is used in Theorem 4.3 and related auxiliary lemmas. 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}) . Denote \bar{\lambda}_{\min},\bar{\lambda}_{\max}=\min\{\bar{\lambda}_{\ell}\},\max\{\bar{\lambda}_{\ell}\},\ell\in[L] , 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} are two positive constants scale linearly w.r.t., X_{0} , \mathbf{M} , Y , T , and \beta . \zeta_{1} and \zeta_{2} are both \Omega(T) and \mathcal{O}(T) . • \zeta_{1} and \zeta_{2} : Two positive constants scale linearly w.r.t., X_{0} , \mathbf{M} , Y , T , and \beta . \zeta_{1} and \zeta_{2} are both \Omega(T) and \mathcal{O}(T) . • \delta_{1}^{t} : A scalar-valued function w.r.t. step t . The constant coefficients are \Theta_{L} , \Phi_{j} , and \Lambda_{s} , where s denotes an step. Denote \bar{\lambda}_{\min},\bar{\lambda}_{\max}=\min\{\bar{\lambda}_{\ell}\},\max\{\bar{\lambda}_{\ell}\},\ell\in[L] , \delta_{1}^{t} is \Omega(t\bar{\lambda}_{\min}^{Lt}) and \mathcal{O}(t\bar{\lambda}_{\max}^{Lt}) . • \delta_{2} : Positive constant scales with T . Denote \bar{\lambda}_{\min},\bar{\lambda}_{\max}=\min\{\bar{\lambda}_{\ell}\},\max\{\bar{\lambda}_{\ell}\},\ell\in[L] , \delta_{2} is \Omega(T\bar{\lambda}_{\min}^{LT}) and \mathcal{O}(T\bar{\lambda}_{\max}^{LT}) . Moreover, \delta_{2}^{-1} is \Omega(T\bar{\lambda}_{\max}^{-LT}) and \mathcal{O}(T\bar{\lambda}_{\min}^{-LT}) . • \delta_{3} : Positive constant scales linearly w.r.t., X_{0} , \mathbf{M} , Y , T , and \beta . \delta_{3} is both \Omega(T) and \mathcal{O}(T) . • \delta_{4} : Denote \bar{\lambda}_{\min},\bar{\lambda}_{\max}=\min\{\bar{\lambda}_{\ell}\},\max\{\bar{\lambda}_{\ell}\},\ell\in[L] , \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})) . A.3 Derivative of General L2O In this section, we derive a general framework for any L2O models by the chain rule, which gives us a complete workflow of each component in the derivatives within the chain. Then, we apply it to the Math-L2O framework [ 22 ] to get the formulation for the L2O model defined in Equation 4 . Due to the chain rule, we derive the following general formulation of the derivative in L2O model: \tfrac{\partial F(X_{T})}{\partial W_{\ell}}=\tfrac{\partial F(X_{T})}{\partial X_{T}}\left(\tfrac{\partial X_{T}}{\partial X_{T-1}}\tfrac{\partial X_{T-1}}{\partial W_{\ell}}+\tfrac{\partial X_{T}}{\partial G_{L,t}}\tfrac{\partial G_{L,t}}{\partial W_{\ell}}\right). We then calculate each term in the right-hand side (RHS) in the above formulation. First, we calculate \tfrac{\partial X_{T-1}}{\partial W_{\ell}} as: \tfrac{\partial X_{T-1}}{\partial W_{\ell}}=\tfrac{\partial X_{T-1}}{\partial X_{T-2}}\tfrac{\partial X_{T-2}}{\partial W_{\ell}}+\tfrac{\partial X_{T-1}}{\partial G_{L,T-1}}\tfrac{\partial G_{L,T-1}}{\partial W_{\ell}}. Thus, we can iteratively derive the gradient until X_{1} . After rearranging terms, we have the following complete formulation of \tfrac{\partial F}{\partial W_{\ell}} : \tfrac{\partial F(X_{T})}{\partial W_{\ell}}=\tfrac{\partial F(X_{T})}{\partial X_{T}}\big({\sum}_{t=1}^{T}({\prod}_{j=T}^{t+1}\tfrac{\partial X_{j}}{\partial X_{j-1}})\tfrac{\partial X_{t}}{\partial G_{L,t}}\tfrac{\partial G_{L,t}}{\partial W_{\ell}}\big). (16) We note that \tfrac{\partial X_{j}}{\partial X_{j-1}} relies on different implementations. For example, for general L2O model that the update in each step is directly the output of neural networks (NNs), we have \tfrac{\partial X_{j}}{\partial X_{j-1}}:=\mathbf{I}+\tfrac{\partial G_{L,j}}{\partial X_{j-1}} . Then, Equation 16 is derived by: \tfrac{\partial F}{\partial W_{\ell}}=\tfrac{\partial F(X_{T})}{\partial X_{T}}\Big({\sum}_{t=1}^{T}\big({\prod}_{j=T}^{t+1}(\mathbf{I}+\tfrac{\partial G_{L,j}}{\partial X_{j-1}})\big)\tfrac{\partial X_{T}}{\partial G_{L,t}}\tfrac{\partial G_{L,t}}{\partial W_{\ell}}\Big). (17) \tfrac{\partial G_{L,j}}{\partial X_{j-1}} depends on specific implementation of NNs. Liu et al. [22] simplify \tfrac{\partial G_{L,j}}{\partial X_{j-1}} by detaching input tensor from the back-propagation process, which truncate the branches in the chain from F(X_{T}) to W_{\ell} . The detaching operation yields simpler \tfrac{\partial X_{j}}{\partial X_{j-1}} . As will be introduced in the following sections, \tfrac{\partial X_{j}}{\partial X_{j-1}} depends only on NN’s output. Further, the definition of \tfrac{\partial X_{T}}{\partial G_{L,t}} is framework-dependent. In the general L2O model, \tfrac{\partial X_{T}}{\partial G_{L,t}}:=\mathbf{I} , whereas in Math-L2O [ 22 ] , it is defined based on the FISTA algorithm [ 4 ] . Subsequently, we perform a layer-by-layer computation for each derivative \tfrac{\partial G_{L,j}}{\partial X_{t-1}} and \tfrac{\partial G_{L,t}}{\partial W_{\ell}} . First, we derive \tfrac{\partial G_{L,t}}{\partial G_{L-1,t}} by: \tfrac{\partial G_{L,t}}{\partial G_{L-1,t}}=\begin{cases}{\nabla\relu(G_{L-1,t})}W_{\ell}&\ell\in[L-1],\\ {\nabla 2\sigma(G_{\ell,t})}W_{\ell}&\ell=L.\end{cases} For simplification, we use \nabla\relu and \nabla 2\sigma to represent derivatives \nabla\relu(G_{L-1,t}) and \nabla 2\sigma(G_{\ell,t}) , respectively, which are corresponding diagonal matrices of coordinate-wise activation function’s derivatives. Next, \tfrac{\partial G_{L,t}}{\partial X_{t-1}} is given by: \displaystyle\tfrac{\partial G_{L,j}}{\partial X_{T-1}}=({\prod}_{\ell=L}^{2}\tfrac{\partial G_{l,j}}{\partial G_{l,j-1}})\tfrac{\partial G_{1,j-1}}{\partial X_{T-1}}={\nabla 2\sigma}w_{L}({\prod}_{\ell=L-1}^{2}{\nabla\relu}W_{\ell})[\mathbf{I},\mathbf{H}^{\top}], (18) where \mathbf{H}:=\mathbf{M}^{\top}\mathbf{M} denotes the Hessian matrix of the loss function in Equation 2 . Second, \tfrac{\partial G_{L,t}}{\partial W_{\ell}} is given by: \displaystyle\tfrac{\partial G_{l,t}}{\partial W_{\ell}} \displaystyle=\big({\prod}_{j=L}^{\ell+1}\tfrac{\partial G_{j,t}}{\partial G_{j-1,t}}\big)\tfrac{\partial G_{l,t}}{\partial W_{\ell}} (19) \displaystyle=\begin{cases}{\nabla 2\sigma}w_{L}({\prod}_{j=L-1}^{\ell+1}{\nabla\relu}W_{j}){\nabla\relu}(\mathbf{I}_{n_{\ell}}\otimes{G_{\ell-1,t}}^{\top})&\ell\in[L-1],\\ {\nabla 2\sigma}(\mathbf{I}_{n_{\ell}}\otimes{G_{L-1,t}}^{\top})&\ell=L,\end{cases} where \mathbf{I}_{n_{\ell}}\in\mathbb{R}^{n_{\ell}\times n_{\ell}} , \otimes denotes Kronecker Product, and \mathbf{I}_{n_{\ell}}\otimes{G_{\ell-1,t}}^{\top}\in\mathbb{R}^{n_{\ell}\times n_{\ell}n_{\ell-1}} . Substituting Equation 18 and Equation 19 into Equation 17 yields following final derivative formulation of general L2O model: \displaystyle\tfrac{\partial F}{\partial W_{\ell}} (20) \displaystyle= \displaystyle\tfrac{\partial F(X_{T})}{\partial X_{T}}\Big({\sum}_{t=1}^{T}\big({\prod}_{j=T}^{t+1}(\mathbf{I}+\tfrac{\partial G_{L,j}}{\partial X_{j-1}})\big)\tfrac{\partial X_{T}}{\partial G_{L,t}}\tfrac{\partial G_{L,t}}{\partial W_{\ell}}\Big), \displaystyle= \displaystyle\begin{cases}\begin{aligned} \mathbf{K}_{n_{\ell},n_{\ell-1}}\bigg(&({X_{T}^{k}}^{\top}\mathbf{M}^{\top}-Y^{\top})\mathbf{M}\\ &\Big({\sum}_{t=1}^{T}\big(\mathbf{I}+{\nabla 2\sigma}w_{L}({\prod}_{\ell=L-1}^{2}{\nabla\relu}W_{\ell})[\mathbf{I},\mathbf{H}^{\top}]\big)^{T-t}\\ &\hskip 20.00003pt\nabla{2\sigma}w_{L}^{\top}\big({\prod}_{j=L-1}^{\ell+1}{\nabla\relu}W_{j}\big){\nabla\relu}(\mathbf{I}_{n_{\ell}}\otimes{G_{\ell-1,t}}^{\top})\Big)\bigg)^{\top}\end{aligned}&\ell\in[L-1],\\ \begin{aligned} \mathbf{K}_{n_{\ell},n_{\ell-1}}\Bigg(&({X_{T}^{k}}^{\top}\mathbf{M}^{\top}-Y^{\top})\mathbf{M}\\ &\Big({\sum}_{t=1}^{T}\big(\mathbf{I}+{\nabla 2\sigma}w_{L}({\prod}_{\ell=L-1}^{2}{\nabla\relu}W_{\ell})[\mathbf{I},\mathbf{H}^{\top}]\big)^{T-t}\\ &\quad{\nabla 2\sigma}(\mathbf{I}_{n_{\ell}}\otimes{G_{L-1,t}}^{\top})\Big)\Bigg)^{\top}\end{aligned}&l=L,\end{cases} where \mathbf{K}_{n_{\ell},n_{\ell-1}} denotes a commutation matrix, which is a n_{\ell}*n_{\ell-1}\times n_{\ell}*n_{\ell-1} permutation matrix that swaps rows and columns in the vectorization process. A.4 Derivative of Coordinate-Wise Math-L2O Based on the results in Section A.3 , in this section, we construct the gradient formulations for Math-L2O model. We present the results in Equation 7 and Equation 8 . As defined in Equations 3 and 4 , Math-L2O [ 22 ] learns to choose hyperparameters of existing non-learning algorithms [ 22 , 34 ] . Suppose P_{i}\in\mathbb{R}^{N*d},i\in[0,\dots,T] is the hyperparameter vector generated by NNs. Suppose X_{-1}:=X_{0} , based on Equation 3 , the solution update process from the initial step is defined by: \displaystyle X_{1} \displaystyle=X_{0}-\tfrac{1}{\beta}P_{1}\odot\nabla F(X_{0}), (21) \displaystyle X_{2} \displaystyle=X_{1}-\tfrac{1}{\beta}P_{2}\odot\nabla F(X_{1}), \displaystyle\dots, \displaystyle X_{T} \displaystyle=X_{T-1}-\tfrac{1}{\beta}P_{T}\odot\nabla F(X_{T-1}), We re-use the definition in Section 2 that defines \mathcal{D}(\cdot) as the operator that constructs a diagonal matrix from a vector, we calculate the following one-line and linear-like formulation of X_{T} with X_{0} : X_{T}={\prod}_{t=T}^{1}(\mathbf{I}-\tfrac{1}{\beta}\mathcal{D}(P_{t})\mathbf{M}^{\top}\mathbf{M})X_{0}+\tfrac{1}{\beta}{\sum}_{t=1}^{T}{\prod}_{s=T}^{t+1}(\mathbf{I}-\tfrac{1}{\beta}\mathcal{D}(P_{s})\mathbf{M}^{\top}\mathbf{M})\mathcal{D}(P_{t})\mathbf{M}^{\top}Y. (22) Given that P_{t} is generated by a non-linear neural network with X_{t-1} as input, the resulting system dynamics are inherently non-linear. Consequently, this system cannot be formulated as the aforementioned linear dynamic system. Moreover, we note that for non-smooth problems, the uncertain sub-gradient can be replaced by the gradient map to obtain analogous formulations [ 34 ] . Due to the above computational graph in Figure 1 , the gradient of X_{t} comes from X_{t-1} and P_{t} , which yields the following framework of each layer’s derivative ( Equation 6 ): \tfrac{\partial F}{\partial W_{\ell}}=\tfrac{\partial F(X_{T})}{\partial X_{T}}\Big({\sum}_{t=1}^{T}\big({\prod}_{j=T}^{t+1}\tfrac{\partial X_{j}}{\partial X_{j-1}}\big)\tfrac{\partial X_{t}}{\partial P_{t}}\tfrac{\partial P_{t}}{\partial W_{\ell}}\Big). (23) We obtain the above equation by counting the number of formulations from F to W_{\ell} . From the Figure 1 , we conclude that each timestamp t leads to the gradient of \tfrac{\partial X_{T}}{\partial X_{T-1}} . Thus, there are {\prod}_{j=T}^{t+1}\tfrac{\partial X_{j}}{\partial X_{j-1}} blocks of formulation in total. We start with deriving the formulation of gradient w.r.t. the GD algorithm, which yields the gradient of \tfrac{\partial X_{T}}{\partial P_{T}} . Due to the GD formulation in Equation 21 , we derive \tfrac{\partial X_{t}}{\partial X_{t-1}} as: \displaystyle\tfrac{\partial X_{t}}{\partial X_{t-1}}= \displaystyle\mathbf{I}_{d}-\tfrac{1}{\beta}\tfrac{\partial\Big(P_{t}\odot\nabla F(X_{t-1})\Big)}{\partial X_{t-1}} (24) \displaystyle= \displaystyle\mathbf{I}_{d}-\tfrac{1}{\beta}\tfrac{\partial P_{t}\odot\big(\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y)\big)}{\partial X_{t-1}}, \displaystyle= \displaystyle\mathbf{I}_{d}-\tfrac{1}{\beta}\mathcal{D}(P_{t})\mathbf{M}^{\top}\mathbf{M}-\tfrac{1}{\beta}\tfrac{\partial P_{t}\odot\big(\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y)\big)}{\partial P_{t}}\tfrac{\partial P_{t}}{\partial X_{t-1}}, \displaystyle= \displaystyle\mathbf{I}_{d}-\tfrac{1}{\beta}\mathcal{D}(P_{t})\mathbf{M}^{\top}\mathbf{M}-\tfrac{1}{\beta}\mathcal{D}\big(\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y)\big)\tfrac{\partial P_{t}}{\partial X_{t-1}}. Next, we calculate \tfrac{\partial P_{t}}{\partial X_{t-1}} . Similarly, we derive \tfrac{\partial{\operatorname{vec}}(G_{L,t})}{\partial W_{\ell}} and each \tfrac{\partial{\operatorname{vec}}(G_{L,j})}{\partial X_{j-1}} of Math-L2O layer-by-layer. \tfrac{\partial{\operatorname{vec}}(G_{L,t})}{\partial{\operatorname{vec}}(G_{L-1,t})} in Math-L2O is similar to Equation 19 . We calculate: \displaystyle\begin{cases}\tfrac{\partial P_{t}}{\partial W_{\ell}}=\begin{aligned} &\mathcal{D}\big(P_{t}\odot(1-P_{t}/2)\big)(\mathbf{I}_{d}\otimes W_{L}){\prod}_{j=L-1}^{\ell+1}\mathbf{D}_{j,t}\mathbf{I}_{d}\otimes W_{j}\mathbf{I}_{n_{\ell}}\otimes{G_{\ell-1,t}}^{\top}\end{aligned}&\ell\in[L-1],\\ \tfrac{\partial P_{t}}{\partial W_{L}}=\mathcal{D}\big(P_{t}\odot(1-P_{t}/2)\big){G_{L-1,t}}^{\top}&\ell=L.\end{cases} (25) Similarly, we calculate the following derivative of output of Math-L2O w.r.t. it input at step t : \displaystyle\tfrac{\partial P_{t}}{\partial X_{t-1}}=\mathcal{D}\big(P_{t}\odot(1-P_{t}/2)\big)W_{L}({\prod}_{\ell=L-1}^{2}\mathbf{D}_{\ell,t}W_{\ell})[\mathbf{I},\mathbf{H}^{\top}]^{\top}. (26) Substituting Equation 26 into Equation 24 yields \tfrac{\partial X_{t}}{\partial X_{t-1}} : \displaystyle\tfrac{\partial X_{t}}{\partial X_{t-1}}= \displaystyle\mathbf{I}_{d}-\tfrac{1}{\beta}\mathcal{D}(P_{t})\mathbf{M}^{\top}\mathbf{M} (27) \displaystyle-\tfrac{1}{\beta}\mathcal{D}\big(\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y)\big)\mathcal{D}\big(P_{t}\odot(1-P_{t}/2)\big)W_{L}({\prod}_{\ell=L-1}^{2}\mathbf{D}_{\ell,t}W_{\ell})[\mathbf{I},\mathbf{H}^{\top}]^{\top}. We note that in [ 22 ] , the gradient formulations are simplified in the implementation by detaching the input feature from the computational graph. Thus, we can eliminate the complicated last term in the above formulation, which leads to the following compact version: \tfrac{\partial X_{t}}{\partial X_{t-1}}=\mathbf{I}_{d}-\tfrac{1}{\beta}\mathcal{D}(P_{t})\mathbf{M}^{\top}\mathbf{M}. (28) In this paper, we take the gradient formulation in Equation 28 . Next, we calculate the \tfrac{\partial X_{t}}{\partial P_{t}} component in Equation 23 . We calculate the derivative of GD’s output w.r.t. its input hyperparameter P (generated by NNs) as: \displaystyle\tfrac{\partial X_{t}}{\partial P_{t}} \displaystyle=-\tfrac{1}{\beta}\mathcal{D}(\nabla F(X_{t-1}))=-\tfrac{1}{\beta}\mathcal{D}\big(\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y)\big), (29) where \nabla F(X_{t-1}):=\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y) is the first-order derivative of the objective in Equation 1 . Substituting Equation 25 , Equation 28 , and Equation 29 into Equation 23 yields the final derivative of all layers’ parameters. First, for \ell=L , since there is no cumulative gradients of later layers, Equation 8 is directly calculated by: \displaystyle\tfrac{\partial F}{\partial W_{L}}= \displaystyle-\tfrac{1}{\beta}{\sum}_{t=1}^{T}\big(\mathbf{M}^{\top}(\mathbf{M}{X_{T}}-Y)\big)^{\top}\big({\prod}_{j=T}^{t+1}\mathbf{I}-\tfrac{1}{\beta}\mathcal{D}(P_{j})\mathbf{M}^{\top}\mathbf{M}\big) \displaystyle\mathcal{D}\big((\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y))\big)\mathcal{D}\big(P_{t}\odot(1-P_{t}/2)\big){G_{L-1,t}}^{\top}. And its transpose is given by: \displaystyle{\tfrac{\partial F}{\partial W_{L}}}^{\top}= \displaystyle-\tfrac{1}{\beta}{\sum}_{t=1}^{T}G_{L-1,t}\mathcal{D}\big(P_{t}\odot(1-P_{t}/2)\big)\mathcal{D}\big((\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y))\big) (30) \displaystyle\big({\prod}_{j=t+1}^{T}\mathbf{I}-\tfrac{1}{\beta}\mathbf{M}^{\top}\mathbf{M}\mathcal{D}(P_{j})\big)\mathbf{M}^{\top}(\mathbf{M}{X_{T}}-Y). When \ell\in[L-1] , the derivative is calculated by: \displaystyle\tfrac{\partial F}{\partial W_{\ell}}= \displaystyle\tfrac{\partial F(X_{T})}{\partial X_{T}}\left({\sum}_{t=1}^{T}\left({\prod}_{j=T}^{t+1}\tfrac{\partial X_{j}}{\partial X_{j-1}}\right)\tfrac{\partial X_{t}}{\partial P_{t}}\tfrac{\partial P_{t}}{\partial W_{\ell}}\right), \displaystyle= \displaystyle-\tfrac{1}{\beta}{\sum}_{t=1}^{T}(\mathbf{M}^{\top}(\mathbf{M}{X_{T}}-Y))^{\top}\big({\prod}_{j=T}^{t+1}\mathbf{I}_{d}-\tfrac{1}{\beta}\mathbf{M}^{\top}\mathbf{M}\mathcal{D}(P_{j})\big) \displaystyle\mathcal{D}\big((\mathbf{M}^{\top}(\mathbf{M}X_{t-1}-Y))\big)\mathcal{D}\big(P_{t}\odot(1-P_{t}/2)\big) \displaystyle(\mathbf{I}_{d}\otimes W_{L}){\prod}_{j=L-1}^{\ell+1}\mathbf{D}_{j,t}\mathbf{I}_{d}\otimes W_{j}\mathbf{I}_{n_{\ell}}\otimes{G_{\ell-1,t}}^{\top}. Remark 2 . The only difference between Equation 8 and Equation 7 lies in the last term, where Equation 7 is more complicated due to the accumulated gradients from later layers. The above two formulations are used in the next section to derive the gradient bound for each layer. A.5 Tools In this section, prior to constructing the convergence bounds, we first derive several analytical tools. These tools are foundational for the convergence rate analysis and also establish key properties of the L2O models. We use superscript k to denote parameters and variables at training iteration k , and subscript t to denote the optimization step. A.5.1 NN’s Outputs are Bounded First, we demonstrate that the outputs and inner outputs of NN layers within the L2O model are bounded. Bound \big\|\mathbf{I}-\tfrac{1}{\beta}\mathcal{D}(P_{t}^{k})\mathbf{M}^{\top}\mathbf{M}\big\|_{2},\forall k,t . Lemma A.1 . Suppose \|\mathbf{M}^{\top}\mathbf{M}\|_{2}\leq\beta and 0