Learning Provably Improves the Convergence of Gradient Descent
Authors: Qingyu Song
Wei Lin
Hong Xu
Venue: NeurIPS 2025 poster ()
Keywords: Learn to Optimize
Gradient Descent
Neural Tangent Kernel
Primary area: optimization
TL;DR: This paper proves the convergence of learn to optimize.

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.

Learning Provably Improves the Convergence of Gradient Descent
Wei Lin, Hong Xu The Chinese University of Hong Kong simmonssoug90@gaii com wlin230cse cuhk. cuhk.edu.Jii edu.hk, hongxu@cuhk. edu. hk
Qingyu Song"
Xiamen University
Abstract
Learn to Optimize (L20) trains deep neural network-baset solvers for optimiza- tion, achieving success in accelerating convex problems and improving non-convex solutions. However, L20 lacks rigorous theoretical backing for its own train- ing convergence, as existing analyses often use unrealistic assumptions- gap this work highlights empirically. We bridge this gap by proving the training convergence of L20 models that learn Gradient Descent (GD) hyperparame- ters for quadratic programming, leveraging the Neural Tangent Kernel (NTK) theory. We propose a deterministic initialization strategy to support our theo- retical results and promote stable training over extended optimization horizons by mitigating gradient explosion. Our L20 framework demonstrates over 50% better optimality than GD and superior robustness over state-of-the-art L20 methods on synthetic datasets. The code of our method can be found from https: //gptt///ithub... com NetX- haap/Machl22Proof-OFFF
Introduction
Learn to optimize (I.2O) represents an increasingly influential paradigm for tackling optimization problems (6) Numerous studies have demonstrated the efficacy of employing dearning-based models
to achieve superior performance across a spectrum of optimization tasks. These encompass convex &
problems, exemplified by LASSO 7
[2 and logistic regression 23 34] and non-convex scenarios
such as MIMO sum-rate maximization
35 and network resource allocation
[3
Distinct from black-box approaches problems from a neural network (NN), the so-called "white-box, 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, L.v 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 the training phase of L2O models [39].
5
36 41). which directly derive solutions to optimization
Further, "unrolling" has emerged as prominent technique within L20 (6] characterized by the strategic replacement components conventional optimization algorithms with neural network (NN) blocks [12 15 20 For instance, Liu et al. [23] introduce Math-1-20 that imposes architectural constraints on unrolled I.20 models by deriving necessary conditions for their convergence. Their analysis revealed that for L20 model to achieve optimality, its embedded NN must effectively perform linear combination of input feature vectors, weighted by learnable parameter matrices.
"Thi work was done at The Chinese University of Hong Kong (CUHK) when Qingyu was PhD candidate.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Empirical validation demonstrates that the proposed methods exhibit strong generalization capabilities when trained using a coordinate-wiss wise snput-to-ouppu strategy. Subsequent research by Song et al. further enhance this generalization performance by reducing the magnitude of input features.
34
Despite these advancements, the best of our knowledge, formal demonstration of the convergence for unrolling-baal based L20 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 specific subspace, a condition that often not met in practical implementations. Similarly, while Math-L220 [2]] 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-L20. However, this work relies on a stringent training assumption, effectively constraining the I.20 model to emulate the behavior of a conventional Gradient Descent (GD) algorithm.
This apparent deficiency in comprchensively demonstrating L20 convergence stems from two fundamental, unresolved technical challenges. First, unrolling-based L20 models 12 [2] represent specialized class of NN architectures. Despite much progress in understanding the training convergence of general neural networks (NNs), notably through the Neural Tangent Kemel (NTK) theory since 2019 absent. Such a proof is an essential precursor to establishing the convergence of the L20 model in its primary task of solving optimization problems. Second, the precise relationship between the training convergence achieved during the 1.20 model's training phase (i.e., optimizing the NN parameters) and the convergence of the 1,20 model when applied to the target optimization problem (i.e., finding the optimal solution) is not well understood. For instance, Math-1120 2 is designed to learn the step size for an underlying GD algorithm. While the problem-solving efficacy of Math-L20 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.
29 30
formal proof of training convergence remains conspicuously
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-L20 framework, wherein 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 (23]. 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....)) 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 B. Moreover, the Math-L20 architecture introduces an additional layer of complexity: the emergence of high-order polynomial dependencies not only on the input features but also the learnable parameters themselves. This distinct feature renders the convergence proof for Math-L.20 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 L.20 model. Within the Math-L20 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 characteristies of its underlying backbone optimization algorithm. This alignment provides a novel thcoretical bridge, ensuring that a successfully trained I.20 model translates to effective convergence when applied to optimization tasks. Our contributions are summarized as follows:
1. We provide formal proof that the Math-L20 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-L20 training. Inspired by (29] 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-I.20 framework.
3. We introduce novel deterministic parameter initialization scheme, coupled with a specific learning rate configuration strategy. This combined approach is proven guarantee the training convergence of the Math-1.20 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 L20 models and the Adam optimizer [IO]. 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 L20 framework. The L20 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 parameter gradients.
2.1 Definitions
Let d > b, suppose E Rdx1, y E 1 and M E RRodd we define the optimization objective as: min f(x) Mr vl zERd
(I)
This objective function is commonly selected for convergence analysis 4
The least-squares
problem, frequent subject in NN convergence studies 3 29 is specific instance of the
minimization in Equation (I) where = b and M I.
We assume f to be 8-smooth, such that ||M M ||MM||| < 8, and M to possess full row rank, with Amiin (MM 3o > 0. This setting often favors numerical algorithms (e.g.. GD) over analytical solutions due to computational complexity. GD's O(bd) complexity is typically lower than the O(b*) of analytical methods involving costly matrix inversions. The loss function is then defined as the sum of N objectives specified in Equation I
F(X) = 1 | -
where F, M E Nox.d X E Ndx1, and Y E R.Nbx1 represent the concatenated objectives, parameters, variables, and labels, respectively, from N optimization problems (see Appendix A. for details). F is also 3-smooth, given that M/2 S max; {IM M,lla] = B.
Learn to Optimize (I.20). Given initial point Xo, I.20 takes Xo as the input and generates solution, denoted as X,, with machine learning model. Typically, let gw denote an L-layer NN with parameters W = (W1,. ... W.). We E 1 Xme-1, 1eee,,,,......... ..A..... n. R. Math-L20 (23 takes an iterative workflow to generate solutions. For each step t E [T] in solving the problem in Equation [[] the NN model in Math-L2O is defined as gw (X,-1, VF(X,-1)). The NN receives the current state variable X1-1 and its gradient V ( as input. The update rule at step t, which employs the Hadamard product (denoted by @), formulated as:
} Pe c VF((x-1), P (X,11, VF(X,,)))
Pt represents a vector whose entries are learned step sizes. The NN gw takes structured layer- wise architecture. It employs coordinate-wist architecture, processing each input dimension independently, recognized for its robustness in 1.20 applications 23 34 Thus, output dimension
of the NN is one, i.c., ny = 1. Denote [L] := (1...., L). for layer & L]. we denote Ge as the
(inner) output of layer l at step Utilizing ReLU (ReLU) (1] and Sigmoid (a) [27] activations, Ge defined as:
{= 0,
Ge
ReLU(W.GG-L.) 20(WW
LE [L 1). {= L.
(4)
3

---

The L20 training problem is defined by:
F(W)= IMX YI Xx 1.20w VF(()))-
2.2 Layer-Wise Derivative of NN's Parameters
Let k denote a training iteration for loss Equation 5 minimization, which distinct from an optimization step for solving objective Equation 2 The computational graph in iillustrates the Math-L220 forward and backward operations, which parallel those of Recurrent Neural Networks (RNNs) 13 Figure Ta details the NN block (see Equation (4). Figure [Tjuricc 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 & triggers full backward pass (blue bold lines). As per [23], the gradient flow from the input features to the NN block is detached.
XT
Loss
GM
Gradiont Tamm: Forward:
>
Backward:
Detach
(a) NN Block
(b) Forward and Backward Processes
Figure Computational Graph of Math-1.20
The derivative of objective F' w.r.t. the parameters Wy of layer is determined via the computational Tarruugh-Time Time (BPTT) for RNNs [26]:
graph, paralleling Back-
af BW,
(F(XT) ΣT
1-1 (I1
ax
Dx, 8P. UP, aW:
(6)
The summation aggregates gradients across optimization steps. n (aX, represents the chain rule application from the final output XT to an intermediate state X,.
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 ReL.U is represented by a diagonal matrix D where its i-th diagonal element is [Dik, = Le)) for i E [me]. Let Dj,
I, = M (MX, Y) and E, == (La & - @ operator that constructs a diagonal matrix from a vector, the gradients for an inner layer W. (L < L) and the final layer Wi, are given by:
I,) Defining D(-) as the
AF - BW.
La 1MM MDD( - 0 G (7) aF = - ET (II (La DD(P)MM M)) (1-
(8)
aw,
where & denotes the Kronecker product. Equation (8) (for WL) differs from Equation 7 (for We) in its final terms: GT-1,= replaces E, @ G. This simplification arises as W, is the terminal layer, and Gz- is its direct input from layer L - 1. Thus, its gradient calculation does not involve subsequent layer propagation factor analogous E
3 L20 Convergence Demonstration Framework
This section rigorously substantiates the convergence of the L20 framework, Math-L2O. We first expose theoretical and numerical instabilities prevalent in current SOTA L20 methods. Then, demonstrate Math-L20's accelerated training convergence compared to GD and then present formal methodology establish its convergence.
3.1 Limitations Analysis of Existing SOTA L20 Frameworks
We analyze limitations the convergence guarantees two SOTA L20 frameworks: LISTA- CPSS 7 and Math-L2O 233. LISTA-CPSS [7] constructively proves that its predecessor, LISTA 12]. can attain a linear convergence rate. However, this theoretical guarantee is contin- gent upon several stringent conditions. Math-L20 23 proposes an L20 framework derived from the GD algorithm, incorporating necessary conditions for convergence. Both frameworks employ sequential solution updates and utilize BPTT for parameter optimization.
Initially, we assess training loss across varying optimization steps. This pertinent due the well- documented issue of gradient explosion of BPTT arising from long-term gradient accumulation [19

---

Both models are trained on 10 randomly sampled optimization problems for 400 epochs. Figure 2 depicts training losses (y-axis) against optimization steps (x-axis) for several learning rates (distin- guished by line color). Data points exhibiting numerical overflow (indicative of gradient explosion at the first training iteration) are excluded, resulting in plot lines terminating before 100 steps for affected configurations. The results demonstrate that both frameworks suffer from poor convergence at low learning rates (LRs) and training instability at high LRs.
Uh 02
F(X400)
Ln:s
100
Lize 03
Ln:si 03
10a
0n00000
Un:t -25
10
11300 05
Ln9--25 -23
10a
10
Sap.pspp G S 66 200
Optimization Step T (a) LISTA-CPSS 7 Figure 2: Training Loss of SOTA L20 Frameworks
Optimization Step T
(b) Math-120 23
Further, examine the convergence conditions outlined for LISTA-CPSS 77.. illustrating their propensity for violation during typical training procedures. The first condition mandates asymptotic sign consistency between iterates X₁ and the solution X requiring sign(X,) = bign(X*) for all t. The second condition imposes constraints on the columns of the learned parameter matrix W relative to the columns of the objective coefficient matrix M. Specifically, denoting column indices by and j. it necessitates that W. M, = and W M2 > for all j # i.
Following the experimental design in 23 we quantify the violation percentage of the aforementioned conditions during inference. The results are presented Figure We consider two settings: (i) shared parameters W across iterations (Figure 3a). and (ii) unique parameters W, per step (Figure Bb).
Both scenarios reveal that the specified conditions are frequently violated post-training. For instance, in the shared W case (Figure(a) while the conditions hold in later steps, substantial violations occur in early steps. The divergence contradicts the convergence rate analysis presented in 77.
Violation Ratio %
Violation Ratio %
100-
100
siSTA signix':
LISAA signix
USSTA CPSS signtr)) - sllpnor"
USSA signtr') - StOREx
CPSS
USTA
20
5
6
10
11 12 T
14
2
3 4 5 6
10 11 12 13 14 15
Optimization Step
Optimization Step T
(a) Shared W
(b) Unique We 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 L20: (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 concise approach to address these questions, establishing direct alignment between the training's convergence rate and an existing algorithm's 's rate.
3.2 L20 Convergence Demonstration: Aligning L20 to An Algorithm
First, we introduce a general convergence analysis framework. Let X* be the optimal solution, r represents an iteration-dependee depeeddenteetteeeeeeeee rate term, and C(X,) be constant that dependent the initial point Xo (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) the loss in Equation 2 is often formulated
as: F(X,) < rXx). For example, standard GD has rate of F(X.) < P fll X 4.
The performance of L20 models, stabilized via training, is typically assessed after T iterations 23 We formulate the L20 training convergence rate w.r.t. training iteration & as:
34
F(X+) S TxC())), where X L20 (X)),
with X7 being the initial solution from the L20 model and constant mapping C. Based on the proof in (38, non-learning GD algorithm's 's convergence rate corresponding to the initial 1.20 state is:
F(X+)= < f x
(10)
5

---

Given the independence of training iteration i and optimization step T. we align the LHS of Equation (9) with the RHS of Equation (10) by setting C(X²) F(X)). Given imitial point is constant that X x this yields the combined training convergence rate:
F(X)) f 1
(11)
Here, the LHS represents the objective value after training iterations, while the RHS a constant term dependent on the initial point Xo. W.t.. T, Equation (11) demonstrates sub-linear convergence
rate of at least (1/TT). The rate indicates that integrating L20 with an existing algorithm via training
can enhance its convergence. Such integration is achieved by the Math--220 framework [23] 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 44)
Further, we construct the Math-L20 training rate Ti (see Equation ( Section I establishes its linear convergence. Subsequently, Section 5 proposes deterministic initialization strategy to ensure
the alignment (C(X)) = ((X))) and uphold the theoretical conditions for this linear rate.
Linear Convergence of L20 Training
In this section, we establish the linear convergence rate for training Math-L20 model employing an over-parameterized NN, w.r.t. the loss defined in Equation (2). By training the NN (Equation (
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 rigorous NN formalizations (Section
Lojasiewizz condition [29] 32). Applying the relaxation from [29] and the
we demonstrate that an NN width of ((Nd) is sufficient.
To derive the rate, we first introduce lemma to bound Math-L20'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 O(Nd)-witth NN. The main results are summarized herein, with detailed proofs deferred to Appendix A.5 A.5land and Appendix A.6
4.1 Bound Outputs of Math-L20
We define ag mmin (G -Irr) and let Ct > for [L] be any sequence of positive numbers. Moreover, for f,j E [T]. we define the following quantities:
X = || + Ce θ2 -I Xe, $ = X + 21 M
A, = (1 + |) Xo 113
(4j (1 +
X M T Y| + (2)- 12 1)
M YI
3
SA. ΣT= Av:
6f = E:=1
[I
[TT)=++1(1 (1 1t8 ( As;
(12)
ST, Ele X=3
82 Σt (1/--1
2 9,) Ass
C = V /311 + (2T + 1)
6- = (1 - B)1 + (2T - 1 2T Y(l2,
6 ||ool2 2T M M Yll2.
6 = の (6
where X, denotes the initial point, and M (parameter matrix) and Y (labels) are input features from Equation (2) The defined quantities are positive under the conditions j 2 1 and d > 0.
First, derive bound for the training gradients by considering them as perturbations from initialization. This bound relates the gradient magnitude to the objective function in Equation ( 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 Appendix (A.5.4
Lemma 4.1. Assuming max( |l,,
[W/lla) for & [L]. for any training iteration k, the OF
gradient of the E-th layer parameters W is bounded by:
1l <
yBe,
2ht |MX Y|12-
aw?
Building upon Lemmas 4.1 and A.6 and auxiliary results (see Appendix A.5). we analyze the dynamics of the final solution XT w.r.t. parameter updates during training. The subsequent lemma

---

establishes rigorous formulation for the fluctuation of XT 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 ReI.U-Nets in [29] The proof is provided in Appendix A.5.3
The semi-smoothness of the Math-L20 NN is preserved despite its recurrent operations. The
coefficient associated with | W W la exhibits O(et"") scaling, where e is an initialization parameter detailed in Section 5 This represents looser bound compared that for ReLU-Nets (29), which is consequence of Math-L.20's greater architectural complexity, specifically the T-fold
execution of an L-layer NN block (see Equation (8)). However, this scaling behavior consistent with observations for other deep architectures [2).
Lemma 4.2. For any training iteration k. assume there exist constants de E RR for E E [L] such that max E 1+ W lla & Xx- Let x and X be outpus of the Math-L20 (defined in Equations 33 and (4)) corresponding to parameters W [W li=1 and W (WW)) JE=1
respectively. Then, Math-1.20 exhibits the following semi-smoothnes property:
| k+1 - x2 S
(1+ (1 (141000000((1//2222))4400000111
'II - -2ll2).
Lemma 4.2 demonstrates that Math-L20 solutions exhibit a bounded response to perturbations in its NN parameters. This finding, in conjunction with Lemma 4. facilitates 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 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-L20
Leveraging the bounds on Math-L20's output (Lemma A.6) and its gradient (Lemma 4.1 the following theorem establishes the linear convergence rate for training the Math-L20 model. The proof is provided in Appendix A.6
Theorem 4.3.
Consider the NN defined in Equation 12 suppose the following conditions hold
using quantities
from Equation
at initialization:
0g 8(1 + B) (13a) og
g² 4 0 (-110- A (A) 82)5x, (1+3)02 vB 0,00000-166
(13b)
a 2 max O, 8'v8
2
EE[L] C.s. 83, 04 SISATT
(13c) ag
(13d)
20
Let the learning rate satisfy:
1) << g02 + AT) (62 + 1 Sx.7 (14a)
"
2
(14b)
P6
Then, for weights W ( training iteration k. the loss function F(Wk) converges linearly to a global minimum:
F(W*) S (1 4n 4n ) F(W").
Remark 1. (1 3 g) is Tы in Equation 11 which is less than one term since 84 (1- ()) > and ag := min ( 0 (G) is a thin matrix), which ensure that the L20 converges at least fast as GD.
Each quantity represents an inner formulation the demonstration of lemmas and theorems. We use these quantities to simplify the formulations. The conditions specified in Equation (3) impose additional lower 1) bounds on Cgj, the minimal singular value of the (L- layer's 's inner output. The bounds stipulated
Equations 14a) and [4b) are based the quantities defined in Equation
in Equations [lbb to (3d) 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 met is proposed in Section We provide detailed interpretation in Appendix A.2
4.3 Analysis of Learning Rate Magnitude
The bounds in Equations 14ab and (1b)) indicate that the learning rate diminishes as L and T increase. We argue that this requirement for a small ry is not significant limitation; consistent with the NTK framework, which does not rely on large learning rates for convergence. To quantify
7

---

this, we examine the scaling of relative to T, L, and Amax. Here, Amax max A E [Z] is the maximum constant upper bound on the singular values of the NN layers (Equation bounds are parameters that can be directly influenced by the choice of initialization method.
These
TX +2
First, analyzing Equation (14)), we derive the scaling of v) as O ((T 1+ Amma T where constant factors independent of T and L are omitted. This expression highlights that the magnitude of 1j is strongly dependent on the bound Amax- This dependence implies that the learning rate can be prevented from becoming extremely small by using proper initialization method (such as our proposed method in Section 5) to control Amax-
Moreover, Equation (14b) shows that rj's magnitude is highly correlated with the lower bound of oo (the penultimate layer's s singular value, per Section (41). Given the four distinct lower bounds for ao derived in Equation 13 we now formulate the magnitude of 7) for each respective case. First, if Equation 13c holds, 7) = (mxxp(2T>
which a non-restrictive bound due to the expo- nential term. Second, if Equation (13d) holds, 7) = (( T* + Amax (T' + +T TX - 7))- This scales inversely with Amax and exponentially with L and T. Third, if Equation (13b) holds, O which also scales inversely with Amax and exponentially with L. Finally, if ) )
7
Equation 13a holds, 1] = ((epp( ( maxx) (X
which, similar the first case, is
a non-restrictive bound due to the exponential term.
The foregoing results indicate that larger Amax correlates with a smaller learning rate n). Nevertheless, this does not result in a degradation of convergence speed. This conclusion is supported by two observations: Theoretical Consistency: The requirement for small r is permissible under NTK theory [6]. The NTK regime assumes infinitely wide networks, where convergence is achieved within 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 the learning rate. As depicted in Figure 4aj our method achieves similar convergence rates for n across a wide range (e.g., 10-3 to 10 10-?).
Adopting a small learning rate is a pragmatic trade-off to avoid the requirement for extremely wide NN. Existing analyses [3 [29] that remove the width assumption often impose a polynomial width dependency (e.g.. O(N)) the sample size N. In our framework (Section 2), the coordinate- wise 1,20 treats d-dimensional features as independent inputs, leading to an effective sample size of Nd. A polynomial dependency Nd would be impractical. Therefore, we opt for the alternative constraint of a smaller learning rate, which permits a feasible network width.
Deterministic Initialization
This section introduces initialization strategy ensuring the aligmment between Math-L20 and GD (see Section 3) while also satisfying the conditions presented in Section 4 The proposed initialization strategy first establishes Math-L.20 to operate as standard GD algorithm, and then guarantees the uniform convergence of Math-L20 throughout subsequent training iterations.
5.1 Initialization for Alignment
Following methodology in (29]. we let C2 = for E [L]. For parameter matrices initialization W (see Section 2). we randomly initialize parameter matrices of first L - layers, i.c. {WP ......., W 2-113
from standard Gaussian distribution and set the last layer's parameter matrix W = 0. Through the 2a activation detailed in Equation (4). it outputs a constant step size, i.e., Pr I. Consequently, the learning proceeds with a uniform step size of 1/33 after initialization, emulating standard GD and its typical sub-linear convergence rate 38) Moreover, this zero-initialization of WT ensures that initial gradients for the inner layers are all zero (as shown in Equation ), which serves to mitigate gradient explosion.
The condition ap 0 (sce Theorem 4.3 is fulfilled by randomly sampling the initial weight matrices [WP) from standard Gaussian distribution. This approach generally ensures full row rank for fat matrices (more columns than rows) (37]. Each matrix W:O then undergoes QR decomposition. Non-negativity is subsequently enforced upon the elements of the resulting upper triangular factor P PyTorch using its sign function).
(c.g., via its clement-wiss absolute value, achieved in
8

---

5.2 Enhancing Singular Values for Linear Convergence of Training
Motivated by properties of minimal singular values in ReLU-Nets identified in 29 we analyze the gap for dg between the left-hand side (LHS) and right-hand side (RHS) of the inequalities in Equation T3]. To satisfy these inequalities, we propose increasing ag. This is achieved by applying constant expansion coefficient 2 to the initial NN parameters (WT,- ..... W transforming eW This parameter expansion scales the minimal singular value oo to cL- reflecting the cumulative impact across I -- layers. However, other terms the RHS of Equation (13) also depend on e. We then establish four lemmas to demonstrate that the conditions for linear convergence, specified in Theorem 4.3 are met for an appropriately chosen value of e.
them to [eWT , .....
First, we set the initial point to the origin, Xg = 0, a choice commonly adopted in L20 literature 123 34I. Then, with C₁- 1 for E [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 larger is required as the number of optimization steps (T) increases. Specifically,
Lemma (52 establishes that e scales exponentially with T. Conversely, increasing the network depth
(L) alleviates the need for large e. The proof' are provided in Appendix B
Lemma 5.1. Assuming Xo = 0, ife = ('(T'>>), then the inequality Equation
13ap holds.
Lemma 5.2. If (T 7 L2 then the inequality Equation 13b) holds.
Lemma 5.3. Assuming Xg 0, if e S(TT=')), ), then the inequality Equation (3c) holds.
Lemma 5.4. Assuming Xg = 0, if = - LT-)), then the inequality Equation 13d) holds.
Empirical Evaluation
This section presents an empirical evaluation of the framework proposed in Section and the theoretical results from Section 4 Experiments are conducted using Python 3.9 and Py PyTorch 1.00.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 E RS120X1 and Y E 1,40001 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-ve wise approach in (23), we formed an input feature matrix of 5120 This setup is equivalent to a training batch of 5120 two-feature samples.
Math-I.20 Model Architecture. The Math-L.20 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 2. To ensure over-parameterization the (L - 1) (i.e.,
second) layer's output dimension is set to 512 x 10 51 5120. The final layer produces scalar output (dimension 1). Three specific model configurations are designed for ablation studies, foundational experiments, and robustness evaluations. These are detailed in Appendix C.I
Training and Initialization Configurations. L20 models are trained using the Stochastic Gradient Descent (SGD) optimizer. For the L 3-layer network configuration parameters for the initial two layers (1 1,2) are initialized according to the methodology presented in Section 5.1 while parameters for the final layer 3) are eero-initialized.
6.1 Training Performance
We evaluated the mean training loss in Equation 2 across all samples. Figure 4a illustrates this loss T 100, benchmarked against the standard GD objective (black dashed line). The results demon- strate that Math-L22 consistently achieves fast training convergence, corroborating the theoretical linear convergence established in Theorem 4.3
Further, we investigated the robustness of our proposed L20 method to variations optimization steps and learning rates (LRs). Models corresponding to different step/L.R configurations are trained for 400 epochs. Figure 4b presents the training objectives for these configurations, benchmarked against standard GD (black dashed line). In contrast to the instability observed for Math-L20 (3)

---

and LISTA-CPSS 77 under certain settings (Figure 2) the consistent convergence across all tested configurations in Figure demonstrates the robustness our proposed L20 approach.
F(X
x 10-1
10"
Math-L20
Gradient Descent
F(X 4003
10
Grazient Descerr
LR. 0003
LR 001
LR:1e LR:le-08 06 LR:3e-
x 10
10a
5.00
1000
1500
2000
2500
3000
3500
4000
4500
6 100
Training Iteration k
Optimization Step T
(a) Loss with Training lteration Figure 4: Training Loss of Our L20
(h) Loss with Optimization Step
Moreover, evaluate the inference performance of framework against baseline methods. Experimental results (in Appendix C.4) demonstrate the framework's ' robustness to hyperparameters.
6.2 Ablation Studies for Learning Rate 7) and Expansion Coefficient e
We conduct ablation studies to assess the impact of the LR 7, theoretically bounded in Equations (4a) and (14b) (Theorem 4.3). and the initialization coefficient defined in Section The experimental configuration employs T 20, input X 323223, output Y E R23220 and neural network width of 1024. Performance is measured by the relative improvement of the proposed L2O method standard GD iteration T 20, calculated objnnobij.. These studies further validate objen Corollary C.I which establishes an inverse relationship between the viable LR vy and the coefficient implying that larger necessitates a smaller r to ensure convergence.
With the initialization coefficient fixed relative objective improvement. The results in Figure Sa demonstratee that while LRs such as 10 and smaller achieve convergence, 17 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.
50, we evaluate the impact of varying the LR r) on the
Fixing the LR v 10-7 we examine the influence of the initialization coefficient e on performance. The results, presented in Figure 5b. 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(Coowe [[owngg to space constraints. These findings validate the proposed strategies for selecting the initialization coefficient and learning rate.
Ratio (x100%)
0.5
Ratio (x100%)
0.5
0.3
LR: 9051
0.3
LR B0200
0.1
LR:: ooc001
LR:: aocacol
0.1
Un: 80000001
-0.1
500
1500
2000
2500
1000
3500
4000
4500
500
1000
1500
3500
4000
4300
Training lteration k
Training lteration k
(a) Ratio with Learning Rate 7/.
(b) Ratio with Expansion Coefficient e, 1
10
Figure 5: Ablation Studies of Improve Ratio Learning Rate and Expansion Coefficient
7 Conclusion
This work analyzes a Baaming-to-Optimiii (L20) framework that accelerates Gradient Descent (GD) through adaptive step-size learning. We theoretically prove that the L20 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 wide layers, we establish convergence guarantees for the complete 1.20 system. A principled initialization strategy introduced to satisfy the theoretical requirements for these guarantees. Empirical results across various optimization problems validate theory and demonstrate substantial practical efficacy.
10

---

Acknowledgements
This work is supported in part by funding from CUHK (4937007, 4937008, 5501329, 5501517).
References
[1] AF Agarap. Deep Learning Using Rectified arXiv: 1833:0:803.08375 2018.
Linear Units (ReLU).
arXiv preprint
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A Convergence Theory for Deep Learning via Over-Parameterizatin In Proc. ICML, 2019.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the Convergence Rate of Training Recurrent Neural Networks. In Proc. NeurIPS, 2019.
[4] Amir Beck and Mare Teboulle. A Fast Iterative Thrnksao--TTreshlldnng Algorithm for Linear Inverse Problems. SIAM Journal on Imaging Sciences, (()::183-202 2009.
[5] Yanmei Cao, Guomei Zhang, Guobing Li, and Jia Zhang. A Deep Q-Network Allocation Scheme for Massive MIMO-NOMA. IEEE Commun. Lett., 25(5):1544-1544 2021.
[6] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Zhangyang Wang, Howard Heaton, Jialin Liu, and Wotao Yin. Learning to Optimize: A Primer and a Benchmark. Journal of Machine Learning Research, 23(1):8562-8620, 2022.
[7] Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical Linear Convergence of Unfolded ISTA and Its Practical Weights and Thresholds. In Proc. NeurIPS, 2018.
[8] Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Hyperparameter Tuning is All You Need for LISTA. In Proc. NeurIPS, 2021.
[9] Chizat, Lenaic and Bach, Francis. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Proc. COLT, 2020.
[10] Kingma Diederik. Adam: A Method for Stochastic Optimization. arXiv preprint
arXiv:1412.6988 2014.
[11] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient Descent Provably Optimizes Over-Parameterizne Neural Networks. arXiv preprint arXiv:1810.02054, 2018.
[12] Karol Gregor and Yann LeCun. Learning Fast Approximations of Sparse Coding. In Proc. ICML, 2010.
[13] Stephen Grossberg. Recurrent neural networks. Scholarpedia, 8(2):1888, 2013.
[14] Howard Heaton, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Safeguarded Learned Convex Optimization. In Proc. AAAI, 2023.
[15] Qiyu Hu, Yunlong Cai, Qingjiang Shi, Kaidi Xu, Guanding Yu, and Zhi Ding. Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems. IEEE Trans. Wireless Commun., 20(2):1394-1410 2020.
[16] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernl:: Convergence and generalization neural networks. In Proc. NeurIPS, 2018.
[17] Sungyoon Kim and Mert Pilanci. Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time. arXiy preprint 2rXiv:2402.03625 2024.
[18] Sungyoon Kim, Aaron Mishkin, and Mert Pilanci. Exploring the Loss Landscape of Regularized Neural Networks via Convex Duality. arXiv preprint 2rXiv:2411.07777 2024.
[19] Timothy P Lillicrap and Adam Santoro. Backpropagation Through Time and the Brain. Current Opinion in Neurobiology, 55,82-89, 2019.

---

[20] Wei Lin, Qingyu Song, and Hong Xu. Adaptive Coordinate- -Wise Step Sizes for Quasi-Newton Methods: A Learning-to Learning-to-Optinnge to-Optimize Approach. arXiv preprint arXiv:2412.00059, 2024.
[21] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss Landscapes and Optimization in Over- Parameterized Non-Linear Systems and Neural Networks. Applied and Computational Har- monic Analysis, 59:85-116, 2022.
[22] Jialin Liu and Xiaohan Chen. ALISTA: Analytic Weights Are As Good As Learned Weights in LISTA. In Proc. ICLR, 2019.
[23] Jialin Liu, Xiaohan Chen, Zhangyang Wang, Wotao Yin, and HanQin Cai. Towards Constituting Mathematical Structures for Learning to Optimize. In Proc. ICML, 2023.
[24] Xin Liu, Zhisong Pan, and Wei Tao. Provable Convergence of Nesterov's s Accelerated Gradient Method for Over-Parameterized Neural Networks. Knowledge-Bard Basedd Systems, 251:109277, 2022.
[25] Kaifeng Lv. Shunhua Jiang, and Jian Li. Learning Gradient Descent: Better Generalization and Longer Horizons. In Proc. ICML, 2017.
[26] Michael C Mozer. A Focused Backpropagation Algorithm for Temporal Pattern Recognition. In Backpropagation, pages 137-169. Psychology Press, 2013.
[27] Sridhar Narayan. The Generalized Sigmoid Activation Function: Competitive Supervised Learning. Information Sciences, 99(1-2):69-88 82, 1997.
[28] Nathanson, Melvyn B. Weyl's inequality, pages 97-119. Springer New York, New York, NY, doi:
1996. ISBN 978-1-4757-3845-2.
[29] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. In Proc. ICML, 2021.
[30] Quynh N Nguyen and Marco Mondelli. Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology. In Proc. NeurIPS, 2020.
[31] Mert Pilanci. From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford Algebra and Convexity. Transactions on Machine Learning Research, 2024.
[32] Boris Teodorovich Polyak. Minimization of Unsmooth Functionals. USSR Computational Mathematics and Mathematical Physics, 93)::4-29, 1969.
[33] Yifei Shen, Yuanming Shi, Jun Zhang, and Khaled B. Letaief. Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis. IEEE JSAC, 39(1):001-115,, 2021.
[34] Qingyu Song. Wei Lin, Juncheng Wang, and Hong Xu. Towards Robust Learning Optimize with Theoretical Guarantees. In Proc. IEEF/CVF CVPR, 2024.
[35] Qingyu Song, Juncheng Wang, Jingzong Li, Guochen Liu, and Hong Xu. A Learning-only Method for Multi-Cell Multi-User MIMO Sum Rate Maximization. In Proc. ICCC, 2024.
[36] Haoran Sun, Xiangyi Chen, Qingjiang Shi, Mingyi Hong, Xiao Fu, and Nicholas D Sidiropoulos. Learning to Optimize: Training Deep Neural Networks for Interference Management. IEEE Trans. Signal Process., 66(20):5438-544 5453,, 2018.
[37] Terence Tao. Topics in Random Matrix Theory, volume 132. American Mathematical Soc., 2012.
[38] Ryan Tibshirani. 10-725: Convex Optimization lecture 6: Gradient descent, convergence analysis, and subgradients. Course lecture notes, Carnegie Mellon University. September 2013. URL hhttts:///eee stat. cmw.cmm.eeeeeeee. edue wttp.//mmttraaaataab///////////a wwwraaaiibbs/coeeoooptttt https//oteexxootoeeeeeeeoe F13/ /ccr searibbee/ecc
pdf Scribed by Micol Marchetti-Booiee Lecture date: 12 Sep 2013. Accessed 11 May 2025.
12

---

[39] Junjie Yang, Tianlong Chen, Mingkang Zhu, Fengxiang He, Dacheng Tao, Yingbin Liang, and Zhangyang Wang. Learning to Generalize Provably in Learning to Optimize. In Proc. AISTATS, 2023.
[40] Yu, Zixiong and Tian, Songtao and Chen, Guhan. Divergence of empirical neural tangent kernel in classification problems. Proc. ICLR, 2025.
[41] Yu Zhao, Ignas G. Niemegeers, and Sonia M. M.Hemstrr De Groot. Dynamic Power Allocation for Cell-Free Massive MIMO: Deep Reinforcement Learning Methods. IEEE Access, 9:102953- 102965, 2021.
13

---

A Appendix
A.1 Details for Definitions
General 1,20. Given Xo. we have the following 1.20 update with NN g to generate Xy:
= - 9(W,, W WL,X VF(X e [2].
(15)
Concatenation of N Problems. For & [T], we make the following denotations represent the concatenation of N samples (each is a unique optimization problem):
M
M
X, = -x
N Y = [v] 122
[N]
MN
X₁ and Y are still column vectors since we take the coordinate-wise setting from 23
A.2 Detailed Interpretation Quantities in Theorem
We elaborate on the quantities introduced in Theorem 4.3 Our notational convention is as follows: subscripts and & identify constant terms that dependent on the total steps T and the training iteration k. Conversely, indices and & (appearing as superscripts or subscripts) are used to reference scalar- functions at a specific step or index j.
d is positive constant upper bound for each 2-th layer in NN gw (see Section 2). which is constructed in the proof of Theorem
O is a positive constant w.r.t. de.
Denote Amin Amax == minf max [L]. OL is lower and upper bounded by ((Niin)) and ((X respectively. Moreover, 0 is 2(Amls)) and O()
1 is a scalar-valued function w.r.t. step j. The constant coefficients are given by initial point No. coefficient matrix M, and coefficient vector Y from problem defined in Equation 2 is the smoothness extent of objective. We use two denotations, j and for step, which are used to formulate different computations in formulations. This formulation is derived by the upper bound relaxation of L2-norm of gradient at Xo- Ø is O(j) and P(i).
Aj is a scller-valued function w.r.t. step j. which is identical to those in D A, is O(i²) and 2()²).
SA. and Sx,r. r. are positive constants, which represents the summation of A of steps and summation of L-th NN layers, respectively.
SA. 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 L2-norm. Sx, is used in Theorem 4.3 and related auxiliary lemmas. Sx, is O(T9) and 2(T*). ST is O(T-)) and () Denote Xunis Amax = min(Ae]. max ( l E [L] Sx is Q(L and (TTĀ_ Moreover, S7.1 is Q( ) and ( X2
Çi and (2 are two positive constants scale linearly w.r.t,, Xo. M, Y. T, and B. Çi and (a are both S2(T") and OI').
<ı and (z: Two positive constants scale linearly w.r.t,, Xo. M, Y, T, and B. Çi and Co are both 52()") and (I').
of: A scalar-valued function w.r.t. step t. The constant coefficients are θr, by. and Ag, where denotes step. Denote Amins Amax = min(2e)) max(me), E [L], 8f is 2 min) and O(
dy: Positive constant scales with T. Denote Amins Amax = min min()e), max ( (eet E [L] 82 is Q(TXLT and (TXLT Moreover, 8, is 12(TAX-LT) -LT) and OTT I.T
63: Positive constant scales linearly w.r.t., Xo. M. Y. T, and 3. 83 is both ((T) and O(T).
δz: Denote Amian Amax me), (e)x E [Z]. 82 is D(exp(-TXe 2 and O(exp(-TXL Moreover, ,, is ( and (xx)
14

---

A.3 Derivative of General L20
In this section, we derive general framework for any L20 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-L20 framework [23] to get the formulation for the L20 model defined in Equation (4)
Due to the chain rule, we derive the following general formulation of the derivative 1.20 model:
@F(X))
aF(XT) 0XT
8XT-1 0XT aGL. axx-1 aw,
0XT
aw;
UG aw,
We then calculate each term the right-hand side (RHS) in the above formulation. First, we calculate 8XT
as: OW,
8XT 1
8XT 2 OW.
8XT
LGLT aW.
SW.
8XT-2
8GL
Thus, can iteratively derive the gradient until X₁. After rearranging terms, have the following complete formulation of Of ow.
OF (xx) OF(XF) j DGL. OW:
(E
ax, ax. 8G
(16)
8W.
8XT
We note that ax, 7X,-1 relies on different implementations. For example, for general L20 model that the update in each step is directly the output of neural networks (NNs), we have ax, Then, Equation (16) is derived by:
8x,-1 I aG1,1
ax,-1
(F(XT) DW.
Σ (1,
0G 0Xr aG Dx,-1 UGL, OW,
(17)
OXT
8G by detaching input 8G... depends on specific implementation of NNs. Liu et al. (23 simplify āX,-1
0x,-1
tensor from the back pack-propagation process, which truncate the branches in the chain from F F(XT) to
ax,_ We. The detaching operation yields simpler ãX,-1" As will be introduced in the following sections,
2x, depends only on NN's output.
8X,-1
I, whereas in Math-L20 [23], it is defined based on the FISTA algorithm 4 Subsequently, perform layer-by-layer computation for each derivative aG2.i TX.-1 DW.
Further, the definition of 8Xr is framework-dependdnt. In the general L20 model, 8Xr
JGZ,
DGL.:
and DGL.
First, derive aG
by:
8G
8GL,
V RReLU(GL-LdWa (2o(Gr.))
LE [L- 1]. L.
8G1
For simplification, we use ReLU and V2a to represent derivatives VReLU(GL-1.) and (2o(GG,)), respectively, which are corresponding diagonal matrices of coordinate- wise activation function's derivatives. Next, aG., is given by:
Dx,-1
8GL.i aXT-1
(T2
8GL1 8G 80 8XT-1
V2ow ReLUW))
(18)
where M MM denotes the Hessian matrix of the loss function Equation
2
Second,
3G1, is given by: OW;
aG.. aw,
a0,.c 0GL = (II j=L LG 3G,-1,1 aW,
(2ow (T Re V & G.-I. Le ( L-
(19)
20 (Ine 2 GI.-I. T
f t=L,
where Inf E x & denotes Kronecker Product, and L, & GE-11 T xnnexmee-1
15

---

Substituting Equation 18) and Equation
19
into Equation
yields following final derivative
formulation of general 20 model:
af BWe
(F(
Li== (I] +
ax aG
8XT -XT
ax,-1
JG aW,
K Kni
(x² M M -Y
EEEr(1 (I+ V2ou V T-t
E [T. 1},
V20w 6+1 (
Ge-1,
Knome-
(x) M -Y
(I (I+ V
1 1= L,
Vnne GL-11"))
(20) where K ne- denotes commutation matrix, which is ne # ng fg-11 permutation matrix that swaps rows and columns in the vectorization process.
A.4 Derivative of Coordinate- Wise Math-L20
Based on the results in Appendix A.3 in this section, construct the gradient formulations for Math-L20 model. We present the results in Equation ( and Equation (8).
As defined in Equations and Math-L20 (23 learns to choose hyperparameters of existing
non-learning algorithms 23 Suppose P. E R Nod (0...., T) is the hyperparameter vector
generated by NNs. Suppose X 1 Xo. based Equation the solution update process from the
initial step is defined by:
X1 = X₂ 1 O VF(X)).
X₂ X1 P2 VF(X)),
(21)
Xy = X - Pr O VF(XT-1).
We re-use the definition in Section 2 that defines D(-) as the operator that constructs diagonal matrix from a vector, we calculate the fol following one-line and linear-like formulation of XT with Xo:
Xy [I 1DPP)MM M)X. + IE II |
MyD(P.M Y. (22)
Given that Pt is generated by a non-linear neural network with X,-1 as input, the resulting system dynamics are inherently non-linear. Consequently, this system cannot be formulated as the afore- mentioned linear dynamic system. Moreover, we note that for non non-smooth problems, the uncertain sub-gradient can be replaced by the gradient map to obtain analogous formulations
Due to the above computational graph in Figure [] the gradient of X, comes from X,-1 and P., which yields the following framework of each layer's derivative (Equation (6):
af OW;
(F(XT)
1-1 8x 8X, 8P (1,
(23)
OW.
We obtain the above equation by counting the number of formulations from F to W.. From the 2Xr. we conclude that each timestamp t leads to the gradient of aXT-1' Thus, there are
Figure
1+1
- 0x blocks of formulation in total.
16

---

We start with deriving the formulation of gradient w.r.t the GD algorithm, which yields the gradient of 8Xr Due to the GD formulation in Equation (1 we derive 0x,
3Pr
ax,-1
as:
ROVF(XX 1)
8X
0X1-1
=I,- 3P. (M (MX,-I-Y)
0X
(24)
-1- DD(P)MM M O..O M (MXX- 0p;
JKe-1*
Ia- (D(P)M M D (MX,-1 - Y))
OPP.
8x.-1*
Next, we calculate TX--1' Similarly, we derive @vec(GL...) and each @vec(GZ.s) of Math-L20 layer- dW.
ap.
ax;-1
by-layer. avec[G1.-1.)
(vec(G2.1) in Math-L20 is similar to Equation
19). We calculate:
f+1 BP D(P o 11- Pt/2)) (L. @ D OW, ap: D(P, (1)2)(():)))
D & @ GL-LI"
E [L -1],
i = L.
OW.
(25)
Similarly, we calculate the following derivative of output of Math-L20 w.r.t it input at step t:
OP. 8X
D( DE,
(26)
Substituting Equation (66) into Equation (4) yields oX--1"
8x. 8x.
8X. 0x, 1
-I, -.P)) M
(27)
DM (
We note that in 23 the gradient formulations are simplified in the implementation by detaching the input feature from the computational graph. Thus, eliminate the complicated last term in the above formulation, which leads to the following compact version:
8x. xX,
Ia (DPP) M.
(28)
In this paper, we take the gradient formulation in Equation 28
aX, Next, we calculate the JP. component in Equation 23 We calculate the derivative GD's output
w.r.t. its input hyperparameter P (generated by NNs) as:
ax. JP.
()))((X))) L-I-D-DTTTT..... (MX;-I-Yi).
(29)
where VF(X,-1) T (MX,- - YY is the first-order derivative of the objective in Equation I
Substituting Equation 25 Equation (28). and Equation 29) into Equation 23 yields the final
derivative of all layers' parameters.
First, for l L, since there is no cumulative gradients of later layers, Equation is directly calculated by:
ar BWL
(M (MTX, - 1P(P))MMMM
((MM(MXX.11 -Y) (1
And its transpose is given by:
aF = -
dWL
(30)
(IT
AM MD(P))) (MX7
17

---

When E [L - 1), the derivative is calculated by:
OF OW,
@F(XT)
Et (II Ox
8X, 0P:
EXT
[ JP aw;
= - EΣ (M (MXT -X) (I] M MD(P)))
(MM) (1- P./2)) (La 60 W
WyIne @ G T
Remark The only difference between Equation (8) and Equation 7 lies the last term, where Equation is more complicated due to the accumulated gradients from later layers.
The above two formulations used in the next section derive the gradient bound for each layer.
A.5
Tools
In this section, prior constructing the convergence bounds, first derive several analytical tools. These tools are foundational for the convergence rate analysis and also establish key properties the L20 models. We superscript k denote parameters and variables at training iteration kt and subscript 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 L20 model are bounded.
Bound
|| 3 D(P() M V.
Lemma A.1. Suppose [M M| and 0 < Pt < 2, have the following bound:
I # D(P M M <1
(31)
Proof. Suppose eigenvalues and eigenvectors of M M are or and ug i [l,..., N respectively, we calculate:
D(PP)) Mu, D(P)))
Due to 0 < Pt. < 2, we have following spectral norm definition:
x T
D(P M M),
I DD(PP) MI/,
8
ØER4
Then, by taking U. calculate:
! vT - DDPt)) M);; =1 fut D(P M = D(P SusS 1,
where 1 is due to 0 Pl < 2.
Remark 3. In our design, we ensure < pk < < by an activation function 2a at the output layer.
Bound |DD(P)) 12, Vk, t. Similar to the bound of | MM Vk, t, due to the Sigmoid function, we directly have:
Lemma A.2. Suppose 0 < ph < 2, we have the following bound:
|PD(P)) <
(32)
Proof. Since is the diagonalization operation and < Ph 2, we directly have ||D(P)))l
<
2.
18

---

Besides, we can derive another bound from the Lipschitz property for the Sigmoid activation function:
|D(P))]22 -| (MX;- r) )... ... "WEE )1
18 -11l[ MM -| +1,
(33)
(8 11111/ | (MX; - 1.
① from equation (17), Lemma 4.2 of (30 2 from triangle inequality.
Remark 4. In contrast to the Lipschitz continuous property ReLU, the aforementioned bound associated with the Sigmoid function prevents the derivation of meaningful numerical results. To analyze the convergence rate of Gradient Descent (GD), a tighter bound on the neural network's output is required. One potential alternative is the convex cone defined by W for the last hidden layer. However, such a cone spans an unbounded space for the set of learnable parameters.
Bound Semi-Smoothness of NN's Output, i.e., 1/D((P+)() - (P/))))22, Ak, Vk,t. Since I.20
model is coordinate-wise model 23 suppose P: (1--a))) (.aa, ap [0, 1]. based
on Mean Value Theorem, we have (D(P,+t) - (f(((tt)) - Thus, we bound
| D(PP) by the following lemma:
Lemma A.3. Denote j [L]. for some Ny R, we assume || S Ny. Using quantities from Equation 12 we have:
|D(P D(P ||2
s (1 + +)1x - -
(34)
+ x || (MX 1 -Whll.
Remark The above lemma shows the output of NN is "mixed" Lipschitz continuous on input feature and learnable parameters. The first term illustrates the Lipschitz property on input feature. The second term can be regarded as Lipschitz property on learnable parameters with a stable input feature.
19

---

Proof. Due to Mean Value Theorem, we have:
|D((P - ll
[Re.(o(RRe.UU(.... ReLUU(X M (M - W )
- -RCLU RELU M (MX;-, -M)X
x))WT") .... T )W?))ll.
W
(1 (Po()))))-(PP))))m))))))) max
|| |RLUU Ret..-RRLLUU M.....M M - x)] ... - T >
- -ReLU(... (el.U( (Mx;- - Y) ) W W
= BeLUU(RelUUXX M (MX - -Y]jW W T >wh++
W) W T W
ReLU(-. ReLL M (MX r) ....wh==+")
-ReLU ReLU M (MX;- FO .....--i | 1/2
+ 11 ReLU(.--ReLL((AA ReLU(XX M (MX;- M)D Wal W
IMg 1/11 | M (MX++ r)]WW+ wh "w
(RELU(.--ReLUU/ M (MX Y)J Wi-2 ! T 1oodr.
1 ||[X" M (MX Y| 1 -Wil2.
1
1/ ReLUU-- ... ReLU M (MX - x)) wh:
- -ReLU( ReL M - )... Wh-z 11lood
+ } [|[XX_ M (MX;- Y) I 1 [/ W/ll2,
+ [1 M [MX Y) " -W
@ ReLUU. ReLU . -M -
- -ReLU(.-- REUU--- M (MX - -Y)W Wh_ do
+ I1[ M (MX; 1 11 - W + + Wh-1lls),
- k MJ (MX Y)] - , M M 1)]1202
-
+ + M. (MX;1 r)1l(20 \E - -
2) -
+ 1 1 |M
(Et ''' -
I is due to triangle and Cauchy Schwarz inequalities, where we make a upper bound relaxation from oo-norm to 2-norm. 2 is due to I-Lipschitz property of ReLU and max([ W 1|2, [| < Å in the definition. It note-worthy that any activations with constant-Lipchizz properties can be applied. 3 is due to triangle and Cauchy Schwarz inequalities as well. We make a arrangement in 4 and eliminate inductions in 2-norm. c is due to triangle inequality, the definition of Frobenius norm, and | M S L of objective's 's L-soooth property.
5 we make another upper bound relaxation from co-norm to
Semi-Smmothness of Inner Output of NN, i.e., Bound |[G - Gh Ghlll,, E [T. 1), b,
20

---

Lemma A.A. Denote E L 11. for some de E R, we assume max [ |22, 12) S X Using
quantities from Equation
we have:
G - G2lel2 S(1
- xp-ilall
+
(1) [|
||
(MX; -I
- W
Proof.
Since the bounding target in Lemma A.4 is degenerated version of that in Lemma A.3 Similar to the proof of Lemma A.3 we calculate:
G - G2,ll2
M
M - Y)]WT .... W
)... )....?? lll <|[XX-1,, M M - Y)] - (X (M
+ +[[[X_,,, M - N E A, = W2'l2,
S(1+ - -x--lallii
+ (1Ix2- ||M (MX/ 1) No EE 11W W
Bound NN's Inner Output G / 1L 1], Vk, t.
Lemma A.5. Denote E IL for some de RR assume [W S de. Using quantities from
Equation 12 we have:
||G x)1xxo1 + (2t 1 2 M IIl
Proof.
|G = ReLeLLLLLLLLU M TMXX - Y) ).. W/> 1l2
$ <|[[X M (MX VIII
811 + |IM (MXX - -M -1))) ||
((1 +1111Xoo12 + (1+,8)2(1-1) + M | Y
<(1 + X)llX + (21 1+ 1= 2 ||
! is from equation (17), Lemma 4.2 30 2 is from triangle inequality, 3 is due to definition of 8-smoothness of objective and upper bound of [|eel in Lemma A.6
A.5.2 Outputs of L20 are Bounded
Next, we establish bounds for the Math-L2O's outputs. Leveraging the momentum-free setting, we formulate the dynamics from Xo to X, as a semi-linear system, where parameters are non- linearly generated by the NN block (see Figure Lap. Application of the Cauchy-Schward and triangle inequalities to this system yields the following explicit bound.
Lemma A.6 (Bound Math-L2O Output). For any training iteration k. the t-th output X of M20 (as per Equation 3 is bounded by: || ll2 I ||Xoll2 + 2 ||M Y 1|2-
21

---

Proof. We calculate the upper bound based on the one-line formulation from Xo in Equation (22).
| ll2
[I- A- D(PP M)X + -E -1- D0
I
1/ D(P:) M M + Ei MDD(P))))DD
@
D M 1Xoll2
++1 I D(P))) M
Y
3
X + E | Y|12
|
3 M Yl12,
where ① is from the triangle inequality, 2 is due Cauchy Schwarz inequalities, and 3 is due to Lemma A. and Lemma A.2
This lemma demonstrates that Math-L20 outputs remain bounded independently of the training iteration l and the specific learnable parameters.
A.5.3 1,20 is Semi-Smooth to Its Parameters
In this section, we treat the 1.20 model defined Equation (2T) and corresponding neural network as functions of their learnable parameters. We then prove that these functions are semi-smooth with respect to these parameters. This property is foundational for establishing the convergence of the gradient descent algorithm, its analysis inherently involves the relationship between parameters at adjacent iterations.
First, we give the following explicit formulation of P:
p = - (MX - - = R M (MXX - ... ...T.. T WW)
Moreover, present ReLU activation function with signal matrices defined in Section 2 We denote as the entry-wise product to the matrices, which is also equivalent to reshape a matrix to a vector then product diagonal signal matrix and reshape back afterward.
pe 20(WW 'K Wh-z(-.. D1 * (WIIXE, M - -.. -0. (o(((......(((t.. ([X/,,, M (MX+_, Y)JWT) K D DI....) WWE K D
Proof for Lemma 4.2
We demonstrate the moni-smoothness Math-L-20's output, i.e., bound
||x++1
X/112 112, Vk,t
Proof. Diverging from the approach 300, X and X are outputs non-linear neural network corresponding to different inputs. A direct subtraction between these terms, as would be feasible in linear-like system, is therefore intractable. Consequently, we must construct an upper bound for this difference. By applying norm norm-based relaxation and utilizing the quantities defined in
22

---

Equation 12 we proceed with the following calculation:
|x X2ll2
= =|| - -D(et ( (M
- -1) - - -
II 1D((Ptt) M M M X - I- (I- 3D(PP)MMMMMM
+ +1(D(Pttt)
D(P.)))MTY -DPP))TT)-DPP))NNT
ING
(1- (D(Ptt)) -1- ( M) |
1- (D(P:)) | x M Y|IaID((P - -D(P)))l
(((P)))) ((P:)
| x YlglDiP -
<|D(P/tH) -(
2 + -
+ + -D(p:))
=11xo112 3 M
-D(())) + 12
2(1Xolla + - | |M 222
(3 [[++3)]I*** 12111
+ 4111x~11l12 1| + |IM (I E/ -W/lla
|| - x ||
(1 + (1lxoll2 + 2 |M 112) (12)) - x -
x11Xoll2 2 | T Y l12)
(1 1122 + ||M - Y) - 1| -
3 35 [IT, [1]==++(( (1 (oll2 - M 22) (()))
(|ooll2 2--1 Φ
|M T 21l 3) (2x 1 2 || Yll2)
W
where ( is from triangle inequality. ② from Lemma A.6
3 due inductive summation to
t = 1. ④ is due to the semi-smoothness of NN's output in Lemma A.3
5 is from induction.
Remark 6. We note that the above upper bound relaxation is non-loose. Current existing approaches derive semi-smoothness in terms of NN functions, where parameters matrices are linearly applied
and activation functions Lipschitz continuous. However, in our setting under [23] the sigmoid
activation is not Lipschitz continuous. Moreover, the input that is utilized to generate X is from x x-11 which is not identical the X for generating X (-11
A.5.4 Gradients are Bounded
In this section, we derive bound for the gradient of each layer's parameter the given iteration k.
Proof for Lemma 4.1 We demonstrate that the gradients of Math-L20's each layer are bounded.
23

---

Proof. For l = L, we calculate the gradient on W (Equation (
BF BWT,
lla
E (M' (MX$-1))
71.
①
M (MX) Y) II PDPP Mi
(MX (1) 12
2
|MX E (MM
$ 2/3
/3
2 M - M (1 (2t 1 1 2
(11oll22 + 1 (1MM)))))) (2),,
2 MX - -11all1 X
(1 + B)1 Xol12 + ((41 3)(1 + +))
Yll2 (27 11-1)32222--0
|M Y
1
SA. |MX 2112, 2
where ① is from triangle and Cauchy- Schwarz inequalities. is from the bound of "p" in is from the bound of L20 model's output in Lemma A.6 and inner outputs in
Lemma A.
Lemma
For E [L
1]. we calculate gradient on W (Fquation 7 at iteration 1: by:
aF Ow?
2
(M (MX+ - Y)) (I 3 MD(P)))
D(M (MX - D)) o (1- (1-P//2)) (Ia W/) Wt)
D Ih Gi-L, 2
11= M (MX) - Y)
M (TMPPP))))PPPM (MX - Y)
[D(P 3 (1 P. /2)
- D I 8 G/ T 11:
2 2
10 | - YIITT
( M 1l2 + | Y |
40
MX Y|lal| E
2
+ () Xoll2 + ((41 - 31 + +) + 1) Yll2+ (2T (322 (27 2)) M Y12
V SA.T |MX 21 2x,
! is from triangle and Cauchy-Schwarc inequalities. Inequality 2 is from bounds of "p" in Lemma and we make rearrangement in it. In inequality 2 use norm's triangle inequality of dot product and Kronecker product, bounds of NN's inner output in Lemma and we calculate - [[W] l| || ||/ We reuse the result in the proof for the last layer's gradient upper bound for l L in equality ④ get the final result.
11 W 2
A.6 Bound Linear Convergence Rate
Now we are able to substitute the above formulation into three bounding targets Equation 44 and bound them one-by-one by the NTK theorem. We summarize the main idea of NTK theory before
24

---

the proof. The main technique of NTK theory is the establishment of non-singularity of the kernel matrix by wide-NN layer, where kemnel matrix is for the gradient of loss to learnable parameters. This invokes the Polyak-LLojasiewizz condition (a more relaxed condition than strongly convex) for linear convergence. Due to the page limit, we eliminate the explicit formulation of kernel matrix in main page. Following the methodology in [29], the non-singularity of kernel matrix is established by min (Gr) > 0. is guaranteed by the conditions in Theorem 4.3 and implemented by the initialization strategy in Section 5
Proof. We start prove the Theorem 4.3 by proving the following lemma.
Lemma A.7.
{ [| S Xo, mmin (G 1,7 2 2 on.
E [E rE [0, k],
re [0, Rl. F([WT) & (1 ,Ann %
(35)
#2 5a)" F((W1), r rE [].
Remark 7. The first inequality means that there exists a scalar de that bounds each layer's learnable parameter. The second inequality means that the last inner output is lower bounded. The last inequality is the linear rate of training.
A.6.1 Induction Part 1: NN's Parameter and the Last Inner Output are Bounded
For k = O, Equation (35) degenerates and holds trivially, Assume Equation (35 holds up to iteration k, we aim to prove it still holds for iteration First, we calculate the following term:
[ 1
k ==
[Wett +++++111
Willa
OF W?
==0
1
<
Y112-
2A:
21
130 2hx 2he
SA. A.T E (1 1/4m f |MX. Y112,
where ① is due to triangle inequality. 2 is due to the definition of gradient descent. 3 is due the gradient is being apper-bounded Lemma 4.1 and our assumption that || S de, e [L], Vr E [0, k). ④ is due to the linear rate in our induction assumption.
V1 1741 8 Ss, calculate the summation of geometric sequence by:
Define
1/8L SA. Σx=o u MXX Ylle =1 n 2hx
V8OL 2X,
k-1 SA.T
|MX] Y Yll2.
1-a
/30 SA,T(1
u²) 1- | Y112.
2x,
SA.T || - Yl12,
2
4nj 32
84
v SA.T ( (V3l (2T + 11)))
2h
4n g2
Ct.
where ① is due to 1 11-1-
54 ② is due to 0 < u 1. O is due to NN's output's bound ④ is due to the lower bound on the singular value of last inner output layer in
1 30
in Lemma A.6
Equation 13cb.
Thus, we have:
|
w S Cc.
(36)
25

---

(38) Denote 01(+) as calculating the smallest singular value of any matrices, due to Weyl's inequality (28. we have:
|| |W - o (W ++1 - -W?)
S [| W2ll2.
S Ce..
where the first inequality is from Weyl's inequality and the last inequality is due to Equation (3).
Then, we directly have [|W ||2 ||W S C₁ and || 1|2 s ||W?ll2 + C2 λe.
Next, we bound G 1,, by calculating:
|- G2 -1rrl1
211 (1+ 31+ - X2 x2-1ll211-=1,
+ + + |M (MX+- 1I "I Woll2.
② 21 (12(1) Xolla _T II
+ 112 M (MX
Y) 1 \/ - W2ll2
As Σt A5 11 Willal15 S(1 + B1+ or Σ [1 (1 ف , ,r
+ +1IAf-ill2 + |M (MXP-1 EI | W2ll2,
(37)
where ! is due the semi-smoothness of NN's inner output in Lemma A.4 2 is due to the triangle inequality. 3 is due to semi-smoothness of L20 in Lemma 4.2
Further, based on the inner results in the former demonstration for | [ W 2. we have:
Σ Et - Will2 S
VBe SA MXX 2he
Y|12-
An
ga
Substituting above result back into Equation
37 yields:
- -
G2r1
+(1+ ()2 | Y
+ +[| + |M -
V30, 2h:
SA.T MXX] - Y112.
Any 32 64
(1 ()2 X + (2T (11-=1111112)5A11111111
2h
41 1
2(1 (oo12 - M 1112)
(1+ 3) (v)) + (2T - 1)11111)) I1 Ete
5-
5-1 /30,
Et=1
2xr
82
+ F
where L is due to NN's output's bound in Lemma A.6 and ② and 33) are due to the other lower bound for minimal singular value of NN's inner output in Equation (1a and Equation [ld The inequality in Equation (38 implies amin (einnG*) (G 2 a00 since a (G) ag.
Based on the above two inequalities, we prove the linear rate in Theorem step-by-step in the following sub-section.
26

---

A.6.2 Induction Part 2: Linear Convergence
In this section, we aim to prove that F([]]+1)) S 11 5, )++1 F(())).
Step 1: Split Perfect Square
By leveraging term MX we can split the perfect square in objective
F([]]+t)) as:
F([W]**1) = [(W11)+++++ | 1 + (MX)+1 Mx T (MX) - Y). (39)
Based on [29]. we aim to demonstrate that F F(WW]*+1) can be upper-bounded by F(W]))) where
Ck < is a coefficient related training iteration k:
Step 2: Bound Term-by-Term We aim to upperly bound all terms in Equation 339 by F([]1).
Bound the first term 1 || calculate
MX 12. First, based on the 8-smoothness of objective F, we
|| Mx = -
x M M(X x*),
- - x MM]2,
The above inequality shows that need bound the distance between outputs of two iterations. Moreover, since our target is to construct linear convergence rate, we need to find the upper bound of above inequality w.r.t. the objective F[W]*), i... 1 +| 112. We apply Lemma 4.2 derive the following lemma.
Lemma A.8. Denote & E [T.], for some X E R. we assume max l|2, 11 < de, Vk. Using quantities from Equation 11). we further define the following quantities with j E (T]:
A (1 + 3) x)
((4i - -3)(1 + })) + Xolaaa Yll2
(2 118(122 ()+(21-222 2 Y
8
4 | la + 25-1
M 1l12.
81" T ET (II) (1+ + - (Ej (E)=)
We have the following upperly bounding property:
g² 16 (ō, y2 ( 2
|IM - -
|MX - 8112- (40)
Proof. We calculate:
| T MX#1 S - -
Σ. =
[= (1+ + ))
wxlla)
ow? 1.)²
2 2
[I (1 ) ) |1
Σ
T [1] (1+ )) 11.002 15 2hc
vTel (SA.)) |MX Y112
2
x2
1+8 (Σm (11 (1+
2 0, (SA.T 0 ) X- | - Y112
32
6,
L (6, ( (8.)))
8 16
|
2112,
(41)
I from semi-smoothness of 1.20's output in Lemma 4.2 Appendix A.5.3 descent with learning rate 7). ② is from gradient bounds in Lemma
② is due to gradient
D
27

---

Bound the second term (MX²*1 -MX)) (MX; Y). We calculate:
(MX+*1 MXX) (MX; Y)
=(x - xx)) MTMMMMMM (MX). Y),
(42)
=(X²+1 - xx) M (MX; - Y).
Following the methodology in 29 we hold all other learnable parameters fixed and focus the analysis on the gradient with respect to the last layer, Wz. This approach facilitates the construction of non-singular NTK, which turn establishes the PL condition, thereby guaranteeing linear convergence rate.
Given last NN layer's learnable parameter Wh+1 at iteration k + 1, due to the GD formulation in define the following quantity:
Equation 21
Z Z= x - (2(
- ) (MX+-1 Y),
(43)
where G -,T represents inner output of layer L 1 at training iteration k.
With Z, we reformulate Equation
42 as:
(x - x+) MM (MX) - Y),
=(x+ - + Z XX) M (MX - YY),
(44)
=(X++1 - M (MX²- Y) (Z x M (MX} VY,
where x at training iteration l + with wh++ and solution X at training iteration & with W defined as:
X ket - - D( (attl//eelttttlt JIM JM (MX Y).
- JM (
Then, we have the following lemmas to bound the two terms, respectively:
Lemma A.9. Denote & for
for some Xe, E IR with j E [T], we assume max (I 11,, (W2112) s Xe. Define the following quantities with [T]:
A =(1 + 3) 122 + ((4t 31 + })) 1)
(2T- (2T-1)(((2 11(8(1)))1)1))11))) 11+
| Y
8 ||| Xolla + 21-1 MT
1 =0,
82 = -T- [I - (1 + 1+9 02
We have the following upperly bounding property:
(x - -)) TM MMMM - Y) < (A, + 5,)0
| Y12
Proof. We straightforwarddy apply upper bound relaxation in this part, where we reuse the results of the first term 1 ||MX*+1 -
x 's's upper bound in Lemma A.8
To reuse the results, we would like to construct the X X4_ term. We substitute Equation (46) into above equation and use the Cauchy-Schwer inequality for vectors to split our bounding targets
28

---

into two parts and relax the L2 -orm of vector summations into each element by triangle inequalities:
(X - (M Y)
G = =(x - - " ( (MX+-1- (MXX+111 -X) (MMX (1(a 1 G-I,T) M) X
- -xx (D(2 G GI-IT) )M (MXx-1-111) M (MX+-V)
- -II - D G G--IT) T JM JMMMM))MX M
+ + (1 Gtt,, - D G(-11) - M l1))
Cz+1
AMMMM - -)lla,
(I(4s (D(2 JM (X -
- x
(45)
+ -1(II- (.
Gh+1 ( JM M)
MM)
- -IT-- - GT JIM M) x 111
+ M IM (MX
-Y)
(1[(a= (D( G - JM M) M||l |x -
- x112 11/2
+ +11 M X || | ||C (ill)))))))))())) |M (MX² - -
(1x x
X || C++1ll2 + | JIM (MX+ 1)ll2:
w (1x#*] - 1 + (|1xoll2 2 + للالج M
lll) (MM -MXX--YIl
where I is due to triangle and Gauchy-Schwarr inequalities. ② is due to triangle inequality. 4 is due to Cauchy-Schware inequality. ④ is due to 3-smooth definition that M M < and
[ (22 + G + T JM M|]2 1 in Lemma A.I ④ is due the upper bound of
1,7)
XT-1 Lemma A.6
(wh++ G (W2 T. We apply the Mean Value Theorem and assume a point of. For of ' each entry (uf),, for some af, E [0, we calculate (uf) ) as:
Further, we bound Ck+1
(1f), = (
Gh+1 ) (1.00,,(WW"" ((W Gh-1r)
Then, represent quantity ||Ck+alle by:
[DD(2 ( () - D(20 D G
(W
gk+1 1-1.7 W oL--TT)
Dup
IAQ
(
ck+1 G - wh wh+ aht
lel Gt S &ellGh -Ciiirll
where ! is from the Mean Value Theorem. ② from the gradient upper bound of Sigmoid function. is from triangle inequality and definition of learnable parameter WI.
29

---

We further substitute the upper bound of || G GL--1 lla in Lemma A.4 and calculate:
< (1 + -|
- -
+ +[| 122 + |M (MX > -W,'12)
S (1+ |002 1|02 - x 122
1/2 (1 + Xoll 2 + (2T -1+ 2T
3 |||
| 1|
W/'l2.
where ① is due to upper bound of XT-1 in Lemma A.6 Substituting the above inequality back into Equation 45
yields:
(X/+1 - Z) " (MX+ - Y)
|| x Xololll2 3 |M [M)+11)[C II (MX;- -V)l2,
|| - 2
+ (llool12 +
(1(1+ 3)0 - x 112
+ *1((11 + x)olX + (2T 1+ 3
IM | - w)llla)
||M (MX; -))
-(11 1+8
1/2 , Xull2 + 2T 1M Xx
3
+ (b((1 + +3)| + (2T 1 3
(11oll12 + M > - w2)l2)
||M (MX - 1)
-(11+ 1+0 ,, (1.xol12 + 27-1 M T Y Y112)) | x
45
3 (1++))1x001 + ((4T 3)(1 + 1 Ylla
(2T 1968 12+ 2))
M Y1
Ar
0 I (MX+-
=(1++ 110 X + w2ll2)
1 - -))l2
30

---

Further, we apply semi-smoothness of L20 model in Lemma 4.2 and upper bound of gradient in Lemma to derive the upper bound. We calculate:
(x M (MXX Y)
(1+ 2 0. ||-
X 2 | -Will)
|M (MX² y)
(1 7 ,r 0T) 2 10 - [1
(1 (1 0 A. A.EE-I -1 W
+
|M (MX; - Y)
16 Σ
(1+ 2 1 Ao '
+ +
W//12 |M (MX+- -Y]l2,
= = (027 122,9 W k+1 - W + (Ar + ' w1lle) IIMM (MXF - r)
- 0) (AT 52)
5t) 1==
|W W (MX# V)ll2
where 1 is due to Lemma 4.2
2 is due to Ar 2 O.
Further, based on the gradient descent, i.e., W W Nawy we substitute the bound of gradient in Lemma 4.1 and calculate:
OF
(x - M (MX+ - Y) 5Ar + 52) -i=1 X7 | WillaalM (MX;- -1Il,
<70, + 82) E/ N5'
||M SMMTMMX - 1)1l2,
200 + 8,) E X-1
A-
v=1
| - DIXIM -
2d
2A + 0, I -112
where ! is due Lemma 4.1 and ② is due to MMIl S vB.
Lemma A.10. Define the following quantities with t [T]:
A =11 + B) + ((4t - 3)(1 + }) + (
+ (2T -13-11(((2--))
M Y
82
1 = Xolll + 2j-1 M Y 12
0 =0
83 = -(11 x) (2T - 1+ 2T-2) | || Ylll).
We have the following upperly bounding property:
z - x+) M (MX+ -Y)
< <( - BO (8,0)) (() ag + T0
MX - -1
Proof. In our above demonstrations, we have constructed a non-negative coefficient of the upper bound w.r.t the objective | |||MX* Y| To achieve the requirement of the lincar convergence
31

---

rate, we would like negative one from our remaining bounding target. We calculate:
(Z x+) T (MX) M -Y
- -xx " (M
- (X+- - (M
MM - Y), (46)
3 (M (M V)) D Gf -2(WW;G"-1..)
(M (M
Similarly, due to Mean Value Theorem, suppose v2, - G (1
2 E [0, 1). based on Mean Value Theorem, we calculate:
2 GZ -o = a(20(v),)) 0(12,))
(WL+ G - (W -
0(20(12,1)) 0(12,
Denote u
we calculate:
D(2 -V
D ([
[
(20()
- )
Oug,
-
- - wh. )
0 - [20 -
OF G aw?
where v5, (W, GL-11 ---
is an interior point between the corre-
sponding entries of W G - and W I is from gradient descent formulation of W in Equation (8]
Substituting above into Equation yields:
(Z (+) M (MX² - YY
= (MX+_ - Y)) (120 - (1 or aw G T (M (MX+ Y)),
G
aF G = awF. 1, D( (v²,.) -(()) (MM)))/MMM/_XX)-- (M (MT(M -Y))
Further, substitute the gradient formulation in Equation g and calculate:
(2- x M (MX+ -Y)
=- 3 D' (MT (MMTMMX - Y)) T
( - TG
(47)
(12, - (MN -MX)
MM Y) MBBMT (MX+-1 -Y,
where B
defined by:
B
MOD - @ (1- -P/122)
I-
G D (1 d(st,)))))PMM (MX+-I-
We discuss the definite property of B byseeb
32

---

Case l:
n - ( MMMMMMMMM M degenerates to be 1. The Equation 47
becomes:
1(Z xt) M M (MX² Pa
-- (MXX - -
D(M (MX
D(P 3 @ (1-1f/2))
(48)
G.,-1TT G².-1,T
D(220 (12,)(1 o ((
D(M (MX YJ) (MX; YY,
We first present the following corollary to show that there exists negative upper bound of [(Z
x "MT (MX² - P
Corollary A.11. RHS Equation (48) 0 Amin A
G GT.,I,T) O.
Proof. Due definition of eigenvalue and Cauchy-Sehwarz inequality, we calculate:
(MX² - -YTM
D(M (MX
D(P) o P1122) (221))(200)))0
D(M ( - -Y,,
(P+ o (1 P (120 (20 (1 -((2.)))) min
Amin(GE-1s G CL-IT))min (MMT)/M (MX+ -Y)12;
1 50,
where ! is due to Sigmoid function is non-negative, Ban 1,7 1,7 " G/.,1,T) > 0, and Amin (MMT) 0 by definition. Thus, (Z ) TM the minimal value among all entries.
MMTTTMMAA (MX Y) < 0 by nature. (mmi means
To get an upper bound, we expect G L-T f--1. to be positive definition, in which we require n Z N. Thus, we can easily get the upper from its minimal eigenvalue.
Based on Corollary A.11
we calculate the negative lower bound of Equation (48 by:
z
x M (MX+ Y)
S - 2 P 3 (1
22)))) min (220 (1oo))) ((st)))) min
(49)
Amia Amin
T G -I,,,,D)mmin MM (MX+ Y)
The remaining task is to calculate (P# @ (1 2)) min and ((2o (1 (((t,))) achieve that by calculating the values on the boundary of closed sets.
min' We
First, denote o = W 1,7", we represent Pb @ (1 - 22 by:
o1 = 20 (0 T T
Since the Sigmoid function is coordinate- wise non-decreasing function, can straightforwardly find (12o(155,) ovb5)))) min and (ug) o (1 o Jmin
Juin by on the closed sets of u and vς. respectively, which is achieved by the following lemma.
33

---

Lemma A.12. For some b, B E R VvR b s vh S B, we calculate (20(1*) @ @ (1-o111p (1-o((²))) (T) mmi by:
min - (20(B)(1-o(3)
b + B. - B.
(2o(U*) @ (1--o(1")) min
Proof. Since (x) E (0, 1).. ((2o(x) の (1 (x))) is quadratic function w.r.t æ. Since (x)) (0, 1), ((2a(a) 3 (1- (x)))
Since the coefficient before the x² term is negative, its lower bound is either the value on the boundary or O.
Since (b), σ B) E (0, 1). if -b * B, the lower bound is the smaller one, i.e., min @ (1 (b)), 20 () @ (1 - of (B))) Otherwise, since both (xx) and ((2 (2) @ (1 (a:))) are symmetric around have (B( o (1 (B)) 2 (b)
ob)).
Further, we calculate the bounds of u and ug and invoke Lemma A.12 to get (220 (1 ()) min and (20(1)) @ (1 a ) min-
present the following two lemmas to show the closed sets that of and vg belong to.
Lemma A.13. Denote E [L] for some À E R. assume || S λp. We define the following quantity:
63 = ((1 + [ool (2T - + 2T 3 M YYl))
,, = I1 de.
For u == =0, G 1.) + (1 0z) (V E [0, 1]. of belongs to the following
closed set:
Proof. We calculate wf's upper bound by:
|/ loc =Ila @ - --
G
= max k
kk max
L
(50)
max max <n 1f
=max(max - ||
S <max [ r G*
where ! is due to triangle inequality and @ is due to a, E [0, 1] and upper bound of NN's inner output Lemma A.5
We calculate the bound of w Gh-1,rll by:
|
G Gf.-1
[ k++ ||2||
_ + B) Xoll2 (2T 1 + 2T T
((1 + Xoll + (2T 11 22' 2) ||M M Yll2)
where ① is due to Cauchy-Schwarr inequality and 2 is due to definition and upper bound of NN's inner output in Lemma A.5 Similarly, we can get || w Gt 1 & og0,.
L
g means the space training iteration k.
34

---

Substituting back to Equation 50 yields:
1 1lo S L
Thus, we have the following bound for vector vy by nature:
- v u I 630L.
It is worth noting that the above lower bound is non-trivial since cannot have vy 2 0, which can be easily violated by little perturbation from gradient descent.
Lemma A.14. Denote E [L] for some de E R, we assume quantity:
[ S de- We define the following
83 ((1 x)ll (2T 1+ 27 M (l2))
O. -
For up = -WiGh-im Vki v belongs to the following closed set:
of E (10
Proof.
We prove the lemma by a similar method. We calculate the bound of [W by:
|| =IWW
2x,((1 + 3)l + (2T -1 1 27-2 | %e.
Xol + +2T
(2T - 2T IIM Ylk)
where ① is due to Mauchy-Schwary inequality and ② is due to definition and upper bound of NN's
inner output in Lemma A.5
We have the following bound for v by nature:
-5 S 50011.
We calculate (220(2))) -a (v min by substituting Lemma A.13 into Lemma A.12
(200 a (v),))) min -00 -(bh)))))
Similarly, we get (P+ @ (1 -P//2)) by substituting Lemma A.14 into Lemma A.12
(P+ O (1 - P2(2) = (0 - ((50))))
Substituting the above results into Equation (49 and Equation 48 yields:
[ - xx) M (MX+ - ))
- 3z @ (1 2+) min (22 (1 - ((1) min
T G 1, 1,7 Amnin (MM M/MM (MX# Y)
Amin
( (G 1,T
< 2 (0 - (8 Amin (G G (MM) M M (MX - Y)IL.
- ---8 - 11 MX Y
(51)
where 1 is from definition.
35

---

Case 2: t < T. We derive the upper bound of above term by inequality:
[[ - xx) MMM (MX+- Yeat
=- -M - Y) M Σ -
D(M (MX - - C 12)) G/...IT
((120(112,) (1 (( MM (MX) -Y,,
① S
Σ [I (
MMM Y)) (L- PL-P/ T Gh--1
12 (1 - ((4,) (MXX)
(MX -Y) |IM M - 112.
> MD(
IID(P: (1 11 -
|D(M ( -M MM |2/ -122
T-1 E 1=1 D(P @ @( - (
(1 l1
[D(M 1 - X)) (MX 1) - Y12
111 1.. // (MX* 1) (MX Y))
13
|MX - 212.
13 x0l1 + / M y (l2) + |
1 X 112 " |M + || YII)))I - Y112.
1/ (3(1) 2T M T Y11 (1 + Xoll + (2T - 1 2T | | Y112)
T B) Xul12 + (2t- 1+ 2 | Y
(3 - M Yl12) ( + ||M 1l -1112
where ! is due to Cauchy-Schwarz inequality. It is worth noting that ! is non-trivial since B non-necessarily to be positive definite. 2 is due to upper bound of NN's output in Lemma A. based on the Sigmoid function is bounded.
is
is
Further, due to the definition of the quantities, we calculate:
[(Z x)) 'M (MX²
P
<
n6 4
[1+33]|XXo113 + (44'-3)(11 Xo 111
(2T-1) (27 -2T-2))
M Y (I))
3a
AT
ET-
(1x + ((4t - 3)(1 + ()) 1x N M T (2T (2T-1) 1)+ (2T-
|M |M
82
@ Y
nd A
Ar A
T-1 2 MX - Y
2
(52)
Combining the two parts in Equation 51 and Equation 52 yields:
(7 ( "M (MX+ Y)
0 T-11 1= A, - 1188 (10)0))((1000000))3333
08 Ar
a 1/2 |M -112
2
36

---

Using quantities from Equation
12
substituting the upper bounds in Lemma A.8 Lemma
A.9
and
Lemma A.10 into Equation
39 we calculate:
F([W]++))
=F([W]*) + M MX (MX -MX)++) (IX))TMXX Y):
) (SA.)
(0) ) -
+ 62 M - -
(
82 00 + q3 0 - A7 ET= ) - -112
66
+ (0 x2²)
2
F((W1))
(A ((W]()
(800))))) -100000))) 2 -60
20 )() F([W)))
(6 7) SA.T) ) 0012 br
1 + 16 (6)
(2) 7
n6 OT T-1 A. 1880 (1)0)) ( { F((W]*),
11+ + +2) +
1780 -156 0B)
F([W]*).
-(1 (11=(((1899))(1-06683)))} B(AT + 8,) - 1
AT Et An)
F((1)*)
(1 (000
2 F([W]*), 0
Anj 7
where ( is due to the definition of objective.
2 is due to upper bound of learning rate in Equa- 3 is due to the lower bound of the least eigenvalue
tion (4a) and 8," 82 + > Aj in definition.
0g in Equation 13b).
d8 < 1, which yields Due to learning rate's upper bound in Equation (14b), know 0 3 the following linear rate by nature:
F((W7) ( (1-14n5566) ((
B Details for Initialization
B.1 Preliminary
To begin with, we define the following quantities:
5, o ( (2T - 1+ 2T | ||M 011201) (1- -2 YI))
6g min | (I -
87 min
(ET-1 -I- M
37

---

Analysis for the numerical stability of d5. 55 is a function with A,, which is also enlarged w.r.t. e". In general, it is possible to push a - o ((T
1+ 11 -- | ())) to zero and let RHS of above inequality to be co when e + oo. As presented in the lemma, we claim that the required
not necessarily to be oo. Thus, oū can be regarded as a O(e--1) < oo constant. In the following proofs, we demonstrate that it holds since is finite.
We calculate the following exact formulations of the quantities defined in Theorem 4.3
AT = + x)1l + ((47 (1 + }) + 1) | lll2
+ (2T -10000(0))-)10222-2)) M T 1
1(8+1) M Y 12 (1++3) X /0/2/11 M Yl
-3-0 | T Y (1b) T
4846
(53)
+ (1+ + B) X 1 - (2+ }) | ||2 M T Y1l2 + 8+2 |M Y Y12.
① 14 M Y 112 - M Y [T + + | Y
where ① is due to Xo = 0 and
- (1+
+ ((4) 3) + () + 1) Yll2
(2i 1)(1(2) 1)+ 2)
M Y
Ba
11-+11
|M Y 1 + (2-)))) Xolla 122 # || |M Y 1123)r T2
3
(54)
(11 + 3)1l X |||l Y
8+1 3/32
||M T Y y13)
((9+11 3
| Y YIST - + Y 15T²
S | Y 1/T
where I is due to X₂ = O.
Then, we analyze the expansion of o min (G (L1TT) ) w.r.t [W eWWl.. Due to the one line form
equation of 1.20 model in Equation 22 we have mmin (G) is calculated by:
miin (Gh-1.T) = Omin Rel.U(ReLLU T (MX T-1 - v)J -..- 1),
where due to Equation 22
x T- is given by:
x- T-1 - 3 M MIX, MT
18 E
T (1 - (I
I 1/2 M M) T Xo + 8 EE M TMT
# 1= [I 1 (MMM)TT'''
T-
(55)
where ① is due to P. (0) I since Wr 0. The result shows that Xi_ is unrelated to [W]r. with W, = 0. ② is due to Xo = O.
Further, for E [T]. denote the angle between x and M (MX2) Y) as 0,-1, we have sin(0,-1) E (0, 1). setting [W] e[W],, we calculate amin (GT) by:
Tmin (G (G9..1.T) =0 minn [RLLU M M Y)low? ........_...... T)), 2 min (1XP-1) M (MX IIIII 1-1 Omin (eW?))
1x9- || (MLX- -Y )ll (in
Ih 1-1
m (eW?),
|x4_ 1|2 IM (MX)_, V)[la
(56)
sin 1)
/=1 Jmin (eW?).
|| +1 M -
sin(Or-1) mmin (W²)), 1l2.
38

---

Based on the definition of T-1 in Equation 55 we calculate following bound:
Omin (G) (-1,)
(in(Or-1)
T
M
M) T -M Y mmin (eW?),
3
3
sin
min Di=1 M
M) T ") |M Yllge" I min (W
(57)
where - is constant related to problem definition.
Substituting Equation (55)
we calculate a tighter lower bound of | by:
|X 212
(D(P)) M)D(P?)M Y
IV
| Y 0
ΣT
D(P M)D(P!)).
(58)
Iv
| Iv
T-1 Y 12
Umin
[1=-T-10 (I - D(P M M) min (D(P.))
E T-1
( - (I- D M M) min (D( ((P.)).
where ① is due to all matrices in the summation positive semi-definite by definition.
We calculate lower bound for Juin (I D(P2)) M) by:
Mmin (I D MM M) 21 3 m (D(2(eWW2(211.) M)
21 2 -1 (6g(t)) max (eW
(59)
64
is easy verify that the above equation equal when too and it decreases with e. Also,
large ensures the RHS of above inequality to be positive.
Similarly, calculate lower bound for miin (P.)) by:
0 min (D(P.) ! min (20
min
82g Bmm
(eW2
2 min (eW2
(60)
_ 20 W m0n G0 (G)_
220, 6,
20 (1x2_ |M (MX+ - Y)I),
2 220, |
where I means we apply the expansion here. ② is due to Mean Value Theorem and 144 denotes
inner point between 0 and eW-G 3 is due to Lemma A.12 and Lemma A.14 4 is due to
W2 is vector in definition. 5 is similar the workflow in Equation 56
Substituting Equation (59) and Equation (60) back into Equation 588 yields:
X 2 M 21
WT I1 (
(IX
M (MX-1-Y)
23 M 1I1.0.E.. sim
Similarly, we can get the following lower bound of |XP_1122
|XL1|22
|| (in,,)))) x)]
Based on the above results, calculate the Ω of PXP-alla in terms of I and θ as:
39

---

|XP 50,,,
Ej=1) -2(0)/-))
T-2 terms
Substituting back into Equation 56) yields:
mmin miin (LL-1,)))))))
-((((T-1(L-)))
(61)
B.2 Proof of Lemma 5.1
Proof. Making up the lower bounding relationship with Equation (57) and Equation 62
yields:
e X 26 m mmin (W?) 28(1 + ()) + 27-2 M Y 2
B
8(1+9) (TT - 2) | 1122. B
which yields:
8(1+3) 8 07 miin (W2)-1 - 2).
e 62
B.3 Proof of Lemma 5.4
We apply similar workflow prove Lemma 5.4
Proof. With Xo = 0, we find the upper bound of the RHS of Equation [3d by substituting the quantity ds:
(1+-))8² /B 28g
8 X|olo + (27 + +/ 02 X
(1+-8)88 VB 255
6s ( |1olo + (27 + 1)
1(3+1)
M
Y 11 के M Y 1:TT22 3
| |M
11 0
(Et= 2x4
3,32
@ (1+-))8/
85
Y
M
Y 22 (2 1)
(62)
296
4(8+1)
M
Y1 म M 21
3+1
M M y12TT
0r.1 (E/ 214 )
337
33
(1+9)/3
65
Y || M Y 1
635
1663 + 1)7 (8.3 20)7 6(23 + 1)T +(3 4)7 + + 1)T) LO L-1
where ! is due to Equation (5 and definition of quantity 87-1 in Theorem 4.3 3 is due to λ = 1 and À 1, E [1.
2 is due to Xo 0.
Making up the lower bounding relationship with Equation 577 and Equation 62
yields:
J | Y
|22 L-1 min (W?)
2L-
(1+0))8 8 || M Y 1 (IIW 2l2 + 1)²
(63)
63/9
16633 1)75 (83 + 20) 6 1)7 + 2 + 4)7 + 2(3 + 177).
which yields:
e e a V22 (16(3 + 1)T5 (83 20)7 6(2,3 + 1)T3 + 2(3 4)T2 + 2(B + 1)T)
where C2,5, denotes the
(1+817 R6
6 Y |24 /- (1 + 1)>31 0 term
Similarly, the finite RHS of above inequality ensures 65 oc.
40

---

B.4
Proof of Lemma 5.2
Proof. Using quantities from Equation 12
with Xo 0. we find the upper bound of the RHS of
Equation
13b) by substituting the quantity ds:
g 65
10% ( - A.) 07.5 S (AT 52)SSA.)
496
g 66
- -
4(8+1) 2
M Y 1112722 48+6
T
Y
11
3+2
M T Y
4/6
(((+1))
| Y 11 - 1)²² 전े
1)
|
Y ( - 1))
383
38
+ +075
[18+11
Y 112
48
12
8+2
M x13
32
32
+
[I] [=:==+]] (1
1- (2) - MI1 Y1l2))
28
418+1) 32
M Y 1135²
48+6
M
13 + I Y13
8
1(3+1) 3,2
M MI
M
8+1
50(62L-27S 225-175 + 62L 626-47666
(64)
where ① is due to Equation (54 and definition of quantity 67 -1 in Theorem 4.3 2 is due to Xo 0. 3 due to d = 1 and d 1, E [L- - 1].
Making up the lower bounding relationship with Equation (11 and Equation 62 yields:
(D(((T-1)(-1))) 2 O( TL-T+2L----1 10eTb-T42L-yp37-- 3T66)
which yields:
37+66 e = T
B.5 Proof of Lemma 5.3
Proof. Using quantities from Equation 12
with Xo = 0, we find the upper bound of the RHS of
Equation (3ch by substituting the quantity d5:
max 9,_ 82V3 L)
CeAe 806
(2T 1+ 2T M
1 2(1 (1-o((21) - 1+ 2T | T
SA. (2T + 1)),
8² /3 SA, A (2T 1)
[/2 22 + +1),
(65)
80
@ 8" v
85
1(3+1)
M Y 2
3
M
Y yIgTT2
1+1
| Y
(1)TT)
8
33
3
(2T + 1)
1);
V/ 65 16 M 11
(1(+1) 383
4(3+1)
3)
2
+
2
3+1 353
1
2+1
T
8/5
332
33
3
(1W2l + 1),
where ① is due X > 1, l [L [L-1] 1] and b 1. 2 is due Equation 554
We analyze the two sides of the above inequality when [W], = e W],, z. to demonstrate sufficient lower bound of to ensure Equation (65 holds.
41

---

If W e[W],, since 2 1. Equation 65
is upper- bounded by:
/² As | 112
8(8+1) 33
T
1(3+1)
Bz )
[3x
2
8+1 33
T
3t1T)
8+1 33
896
33"
( (e)
+)
1-1
VB
| |121M|1
85
(66)
8
8(8+1)
332
TM
1(0+1) 33
32
7
19
+
2
28+1
332
T
B+1 3
I (1W2ll2 1).
If RHS (lower bound) of Equation (57) greater than the RHS (upper bound) of above result, lower bound condition for minimal singular value Equation (65) sufficiently holds, which yields:
|M 21 min (W?)
BB ds 1|2 | 80
M13+117" 332
[[(8+1)
3
#2
2
B2
+
2211
3,32
T
3,82
- (1 1),
which yields:
e 2 6-1 C1.85
8(8+1)T4 + ( - -(1-2 -
211T)
where C1,5s denotes the "constant" w.r.t. dg-
vB 8366684
85|lY | (1 + 1)m omin min (W?)-² term, which
In the end, it trivial to evaluate that the RHS of above óG finite with such e.
C Additional Experimental Results
In this section, we present detailed experimental settings and corresponding results. We define problems at three distinct scales, as described in Appendix C.I The smaller scale is utilized for ablation studies (Section 6.2). whereas the larger scales are adopted for training experiments (Section 6. and Appendix C.2 and inference experiments (Appendix C.4
C.1 Configurations for Different Experiments
Details of the three experimental configurations are presented in Table [ Scale involves a DNN trained with input X E 32 and output Y E 32 featuring an (Z 1)-th layer dimension of 1024. Scale 2 utilizes input X E IR 10x5112 and output Y E TR 1000xx000 with the (L 1)-th layer dimension established 5120. Scale 3 employs input X E R2018x512 and output Y 20118 100 This configuration designed as an under-parameterized system, with an (T. 1)-th layer dimension of 5120, specifically to evaluate the robustness of our proposed L20 framework. The third model, although targeting the optimization problem with the same dimension, has a different number of training samples N. We design the scale align with the training configurations of the baseline model LISTA-CPSS [7]. Moreover, due to the GPU memory limitation, we set a thin NN, whose convergence guaranteed by our proposed theorem. The related experimental result is used to further demonstrate our proposed framework in Section
Table Configurations with Different Scales Dimension of L Layer's Output
Index
d
b
Training Samples
1
32
25
1024
32
2
512
400
5120
10
3
512
400
20
2048
42

---

C.2 Additional Training Performance Comparisons verses L20 Baselines
For these experiments, the Scale 3 configuration is utilized. Both baseline state-of-the-ar art (SOTA) methods and our proposed L20 framework are trained for 2000 epochs using a learning rate of 0.001. However, the inherent model construction and training scheme of prominent SOTA method, LISTA-CPSS 77. diverges considerably from the requirements of our problem. Direct application of its original settings to our scenario results in over-fitting and poor training convergence, indicating lack of robustness for this specific application. The following discussion elaborates on these incompatibilities and the modifications undertaken.
The original LISTA-CPSS framework possesses two key characteristics pertinent to this discussion. First, regarding its model construction, LISTA-CPSS addresses inverse problems by formulating learnable Least Absolute Shrinkage and Selection Operator (LASSO) problem, wherein it learns scalar coefficient for the L1 regularization term However, our objective in Equation (I) is quadratic. Second, its training protocol is supervised, utilizing an L2 loss against pre-generated optimal solutions, and employs a layer-wise training scheme. In this scheme, one layer is progressively added to the set of trainable parameters per training iteration, and these parameters are updated using four back- proppaaattntiinn (BP) steps 77. To adapt LISTA- CCTSSSSSS for our purposes, we modify both its model architecture and original training scheme to enable unsupervised optimization of our loss function (defined in Equation and to better align with our established training configuration.
First, to demonstrate the challenges of applying LISTA-CPSS's original training paradigm to un- supervised quadratic objectives, we evaluate minimally adapted version. This version trained unsupervisedly by defining the loss as the objective function value from the final optimization step. Given our quadratic loss in Equation (2), any model components in LISTA-CPSS specifically de- signed for non-quadratic terms are not directly applicable. Moreover, a critical aspect of the publicly available LISTA-CPSS implementation its initialization of the neural network (NN) with fixed matrix M. This initialization inherently restricts the trained model's 's utility to problems featuring this identical, predetermined M.
We train this minimally adapted LISTA-CPSS variant for 50 epochs (corresponding to 20000 BPs due to its layer-wise updates) using the Adam optimizer on dataset of 2048 randomly generated samples. The loss function defined in Equation 2 is evaluated at an optimization step of T = 100. The experimental results, depicted in Figure 6 reveal that this configuration leads to severe over- fitting on the training samples. Specifically, Figure 66 illluusstttess the convergence of the objective function (at T 100) as function of the training iteration k. Concurrently. Figure [bb] displays the mean objective value across 100 optimization steps during inference. These results indicate that while AISTACCSSS achieves rapid convergence on the training data (which used a fixed M), its performance degrades catastrophically (i.e., fails to generalize) when evaluated with different matrix, M', during inference.
10
10a
10a
16a5
(00)
10a
Gradient Descent
10
LISTA-CPSS
10
LIST USSAACCSS
10
10
1041
10-10
10
10a
2000
4000
6000
8000
10000
12000
14080
16000
18000
10a
100
Training Iteration &
Optimization Step
(a) Loss with Training Iteration k
(b) Objective Trajectory Inference
Figure 6: Training Loss and Inference Trajectory of LISTA-CPSS 7
with Fixed M
Informed by the above observation, a more robust approach is achieved through the random initial- ization of LISTA-CPSS. Specifically, weights are sampled from standard Gaussian distribution and subsequently scaled by a factor of a-b to mitigate potential numerical overflow in cumulative products. The LISTA-CPSE CPSS model is then trained using this initialization strategy.
For our proposed L20 framework, the expansion coefficient is set to 100. As detailed in Scale 3 in Table we implement inder-parameterizze system wherein the dimension of the (L - 1)-th layer
*Our preliminary experiments indicates that SGD fails to converge with SSSA--SSS's original layer-wise training scheme.
43

---

is configured to 20. This implementation intentionally deviates from the theoretical requirements stipulated by our proposed theorems, which necessitate that the dimension of the (L 1)-th layer must be larger than the input dimension. This particular experiment is conducted to demonstrate the robustness the proposed 1.20 framework, especially under such conditions that depart from our established theoretical framework.
The training losses of LISTA-CPSS and our proposed L20 framework are depicted in Figure 7 with the performance of non-learnable gradient descent (indicated by a horizontal line in the figure) serving as baseline. Under scenarios with varied M configurations, LISTA- T-TCSSSSS exhibits markedly slower convergence compared to both our proposed L20 framework and the gradient descent baseline. Moreover, the fast convergence observed for our L20 framework underscores the robustness and efficacy of its proposed initialization strategy, particularly when applied to under-pant peterr--rrmmteizeed models.
109
10a
F(x Fo0
Gradient Desceni
104
LISTA-CPSS
10a
Our L20
10a
10a
400
800
1200
1600
2000
2400
2800
3200
3600
4000
4400
4800
Training Iteration K
Figure 7: Training Losses with Varied M
C.3 Real- World Training Performance Comparisons
To empirically validate our proposed theorem, we perform additional experiment comparing the training convergence of our L20 construction against standard Gradient Descent (GD). Utilizing compact Convolutional Neural Network (CNN) on the MNIST dataset, our method achieved significantly faster convergence, thereby corroborating our theoretical findings.
We employ the Scale 3 configuration (an under- parameterized setting from Table T The CNN architecture (Table comprises two convolutional layers, two max- maxxpooling layers, ReLU activation functions, and a final linear layer. The optimization objective is the total cross-entropy loss over 200 randomly selected MNIST samples. The learning rates for training our L.20 model and the CNN set to 10-6 and 10-2, respectively.
Table 2: Architecture of a Small CNN Model with MNIST Dataset
Input
Output Channel
Kernel Size
Input Size
Output
Layer Convolution
Channel
Size
2
28 x 28
28
x
28
Max Pooling
2
28 28
14
14
ReLU
2
N/A
14 x 14
14
X
14
Convolution
3
x
14
14
Max Pooling
3
2
14 x 14
7 7
ReLU
3
N/A
7
7
Linear
147
10
N/A
1
To validate our framework, we conducted a comparative analysis of the CNN training loss the MNIST dataset, contrasting our proposed L20 method with Gradient Descent (GD). The results are depicted in Figure Sal which plots the training loss over 100 iterations. We evaluate two versions of our L20 optimizer, pre-trained for 100 and 200 epochs, respectively. In both scenarios, our L20 framework yields substantially lower loss than the GD baseline, which corroborates the effectiveness of our approach for training DNN models.
Additionally, Figure 8b provides quantitative comparison of the iteration cost for both methods. The proposed 1.20 framework converges to a more optimal (lower) loss value than GD in substantially fewer iterations, confirming its superior efficiency in training the CNN model.
44

---

10
Gradiont Descont
10
Our L20, Epochs: 100
Method
Loss Value with Iterations
10-3
GD
10,000 Iterations: 2.92c-04
10-3
Our L20, Epoch: 100
100 Iterations: 2.91e-04
10
20
50
50
50
50
90
Our L20, Epoch: 200
100 Iterations: 1.22e-04
Optimization Step
Training Losses
Final Loss Values of CNN MNIST Dataset
Figure 8: Performance of Training CNN on MNIST Dataset
C.4 Inference Experiment
Beyond analyzing training outcomes, extend our evaluation to the robustness of the proposed L20 framework by assessing its performance in inference-stage optimization. This involves comparing the convergence characteristics of L.20 against the Adam optimizer [10) and standard gradient descent (GD). It should be noted that while our theorems provide convergence guarantees for the training phase, such guarantees do not explicitly extend this inference optimization context. For this empirical investigation, both our L20 framework and the Adam optimizer are executed across range of hyperparameter settings for 3000 iterations (longer than 100 iterations in training), and their respective objective function trajectories are plotted as a function of the iteration count.
Adam utilizes momentum accelerate gradient descent. In addition to the learning rate 7, Adam employs two crucial hyperparameters, 31 and B2, which control the exponential moving averages of past gradients and their squared magnitudes, respectively. For the Adam optimizer in experiments, we set the learning rate y 3 (3-smoothness of objective) and explored apper-parameters 31 E ...., 0.9) and B2 E (0.95, 0.955..... 1.0).
1
Regarding our proposed 1.20 framework and consistent with the initialization strategy detailed in Section 5 we selected a large expansion coefficient L20 model is then trained with learning rates 1) chosen from the set {10-3 1 ,.... 10-7).
100 to enhance training stability, The
As illustrated in Figure we present the objective trajectory over 3000 optimization steps, where each point is mean value of 30 randomly generated problems' objectives. While the objective function initially exhibits rapid decay, the Adam optimizer fails to maintain this convergence, ultimately settling at sub-optimal values and not converging average. In contrast, proposed framework demonstrates superior performance compared to the Gradient Descent (GD) algorithm and exhibits robustness across various learning rates.
GD
F(x
Our L2O
10-3
Adam
10-3
10-7
10-9
10-11
600
1200
1800
2400
3000
Optimization Step t
Figure 9: Inference Trajectory of Our Proposed L.0
C.5 Corollary in Ablation Studies
Corollary C.1 (LR's upper bound w.r.t. e).
-TT-L4-4 17 ot ((
37
45

---

Proof. From Equation
14a we calculate:
9
3 (62 + Ar)
82 + +SATT)
O
E
j=s=11 (1 +
1+8
(2j - 2) |M Ylla))
2
100+1) 32
|
Y 1
48+6 32
M T 11 + 3 |M |MMY1
(18+11
M
11
Y
18+6
M T 11 + 3 M MM v13)
3
Σ Σ
([]j=st1( (1
2/ (2j 1)02
| x111)
4(8+1)
| 11133²
18+6 3
M T
1135
IM T 1113
(1(++1)
Y
M
لفو - |M |
3/2
B2
4(8+1)
|
Y
M
Y
11
3
IM
55.1
333
-0 10
From Equation 14b due to the four lower bounds in Equation upper bounds:
13
we calculate following four
1
8
26
64
00
2
66
8G
L 8/1
85
||l2 |
| ||
8(8+1) TM
(18+1)
2
T
+
2
8+1 3,8
l12 +1)
3,82
3,3
= -6
<
36
8
04
0
Equation 63
182
05
2 2L-2(118))
85 YY | Y
4 180
6.68
[16(3 + 1)75
(88 + 20)7 6(23 1)7 2( + 4)7 + +((++ 111+)
(1 +12 1)2
=0 2 - 3
17
182 18
8m
2
a
2
Equation 66
82 B3
O(e -1-22++---- -6)
<
1
4 3.83
5444
00
Equation
13a
4 4.3
32
85
8(1 +
2T |M 2 = O
46

---

C.6 Additional Ablation Studies for Learning Rates
We present two additional ablation studies with of 25 and 100. Both use the configuration in Table [
The results are in Figure [O] which shows deterministic relationship between LR
and expansion coefficient. For ε 25 Figure [0a] the 10 LR is too small and leads worse optimality, The large LRs, i.e., 10-3, 10-2, cause unstable convergence. Similarly, for e = 100 in Figure
10b
a proper LR 10-4
Ratio (x100%)
Ratio (x100%)
0.5
0.5
0.3
col
0.3
0.c01
0.0001
0.001
0.1
Lift 00001
Lift 000001
0.1
Lift 0.00001
LRt 00000001
00000001
(R nccooco
0.1
500
1060
1500
2500
3000
350d
4000
4500
0.1
500
1060
3000
3500
4000
4500
Training tteraiio k
Training lteration
(a)
25
(b) 6 100
Figure 10: Additional Ablation Studies Learning Rate with Different 6.
C.7 Additional Ablation Studies for Expansion Coefficient in Initialization
present two additional ablation studies for e with learning rates of 0.001 0.00001. Both use the configuration in Table I The results in Figure II For large LR, large may cause poor convergence due to Theorem 4.3 From Figure Ila e 25 is proper setting for best convergence with 17 0.001. Similarly, for r 0.00001, 5 enough.
Ratio (x100%)
Ratio (x100%)
0.1
2:108
-0.1
500
1000
1500
2000
3500
40n0
4500
-0.1
500
1000
1500
2000
2500
3000
3500
4000
4500
Training lteration
Training Ileration
(a) 1l = 0.001
(b) rj = 0.00001
Figure 11: Additional Ablation Studies of with Different Learning Rates.
D Discussion
Scope of Theoretical Guarantees. Our theoretical analysis establishes convergence guarantees and demonstrates superior convergence rates specifically for over-parameterized Math-L.20 systems compared to baseline optimization algorithms. While we acknowledge the empirical effectiveness of certain mnder-parameterizee Math-L20 systems 23 34], providing theoretical convergence proofs for them remains challenging due to the inherent non non-conyyxity the underlying neural network training. Alternttive theoretical approaches, such as convex dualization [7 explored. However, these methods typically necessitate the inclusion regularization terms within the loss function, which may deviate from the original optimization objective we aim to solve.
I8 31, have been
Generalization Other Objective Functions. The central thesis of Section 3 is that learning can enhance algorithmic convergence. To substantiate this claim, we first require convergence guarantee for the neural network training process a well-known complex problem. We leverage Neural Tangent Kernel (NTK) theory, which typically analyzes convergence under an Ln-norm objective [66.. Despite generalizations NTK to other loss functions 40), we retain the L2-norm for two reasons: (1) it permits the derivation of an explicit convergence rate, rather than surrogate one [40], and (2) it aids in demonstrating a deterministic initialization strategy, which has practical implications for model and training design.
47

---

Choice of Base Algorithm. Our framework utilizes Gradient Descent (GD) as the core algorithm primarily because admits a direct amalytical formulation relating the initial point Xo the iterate Xr. This tractability is crucial for our analysis. In contrast, accelerated variants like Nesterov Accelerated Gradient Descent (NAG) 4 generally lack such closed-form expressions for Xr- This absence significantly complicates the derivation of the output bounds required to analyze the L20 system's dynamics and to prove convergence guarantees. Consequently, rigorously extending our current theoretical framework to momentum-based methods, despite attempts using inductive approaches, remains an open challenge.
We contend that convergence proof for NAG can be constructed. Our central strategy involves bounding the L20 model's output satisfy the convergence conditions the backbone algorithm. This is analogous to our use of the 3-smoothness property to derive the step size in Equation (3) and a methodology applicable to any provably convergent algorithm. To this end, we aim to bound Xr relative to Xo. The proof proceeds as follows: First, NAG is formulated as a linear dynamical system where transition matrix maps X₃ to X Second, we constrain the neural network outputs (i.e., momentum terms and step sizes) to ensure the transition matrix remains bounded over I steps. Finally, by applying the Cauchy-Schwan and Triangle inequalities to this stable system, a formal bound on X7 is derived.
E Impact Statement
This paper presents work whose goal is to advance the field of Learning Theory and its combination with optimization. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
48

---

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

---

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

---

Answer: [No]
Justification: accepted, we will open source the codes.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
cessionnooccyyl for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli//uuuia wwwtc//gguie///eeeeceoocc CoodeSubeiiieeeec ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Section 6 and Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Section and Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
51

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /tttus:://eurips... http://ourrrps.ccpuubbbbee http:/p...........ttttcccccieeea
Answer:
[Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
52

---

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

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
54

---

Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy htteas////eerrpppoccc///f/rreerp for what should or should not be described.
55


Reviews:
[{"review_id": "wgLznavewA", "reviewer": "Reviewer_yQfy", "summary": "This paper provides a theoretical study of Learn to Optimize (L20) framework, where the optimization of the main model is performed using an additional model that generates per-coordinate stepsizes. This work provides convergence guarantees for such an optimization problem when the original problem that we want to solve using the main model is quadratic. The authors provide a linear convergence rate for the Math-L2O framework. The theoretical claims are supported by empirical ablations.", "questions": "- Can we use LSTM-type networks that suffer less from vanishing/exploding gradient problems instead of RNN-type updates?\n\n- Can the theory be generalized to non-ReLU types of activations?\n\n- Can the authors clarify why we obtain $O(1/T^2)$ rate (line 203)?\n\n- Line 223 is confusing. Are $\\alpha_0$, $\\overline{\\lambda}\\_{\\ell}$, $C\\_{\\ell}$ fixed? Can we always find such constants that (11) is verified? The next concern in this line is the assumption $\\\\{\\\\|W\\_{\\ell}^{k+1}\\\\|_2,\\\\|W\\_{\\ell}^{k}\\\\|_2\\\\}\\le\\overline{\\lambda\\_{\\ell}}$. The proof of it is also unclear. Can the authors show how Weyl's inequality is used?\n\n- The initialization (section 5) is unclear. The authors first set weight matrices to be zero, but then sample from a Gaussian distribution. Which one is used in the end?\n\n- Typo: line 546, \"eigenvalues\" are missing\n\n- The proof of Lemma A.2 is not full. How to obtain the final bound (31)?\n\n- Where is the assumption $0 < P^k_t < 2$ verified which is used in some lemmas (e.g., Lemma A.1)?\n\n- Can the authors provide more details on why the bound $\\\\|W\\_j^{k+1}\\\\|\\le\\overline{\\lambda}_j$ holds?\n\n- Where do the authors use the NTK regime? Can the authors clarify this point, please? Is it used when assuming that $\\sigma\\_{\\min}(G\\_{L-1,T}^0) > 0$?", "limitations": "- It seems that the proof techniques are extremely hard to generalize beyond the quadratic case.\n- The authors discuss the limitations in Section D, mentioning that the explicit form for $X_T$ related to $X_0$ is crucial in the derivations. This is more complicated for other algorithms, e.g., Nesterov Accelerated Gradient. \n- I believe it is hard to extend this approach to neural networks of real size since the input of the second NN is $[X_t,\\nabla F(X_t)]$, which is a very high-dimensional nowadays.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "***Strengths:***\n\n- Convergence guarantees for a quadratic objective in NTK regime (which is somehow needed to ensure that PL condition holds and consequently leads to linear convergence).\n- Experimental results demonstrate that Math-L2O framework might outperform classic algorithms like GD and Adam.\n- The authors demonstrate that previous assumptions used in previous approaches, like LISTA-CPSS, are not verified during training (Figure 3)\n\n***Weaknesses:***\n- The paper is poorly written, and the technical details are hard to parse. Due to typos and/or inaccuracies in writing, overloaded notation it is hard to evaluate the theoretical results (e.g. $M_i, W_{[L]}$ are never defined in the main part; line 224 involves so many new definitions without any intuition why they are even needed for a presentation, how they are used, and so on). I also didn't find a specific place where some properties are explicitly used (the definition of NTK is also absent). Therefore, in my view, evaluation of the theoretical results requires a significant improvement in the presentation.\n\n- Algorithms like Adam and SGD shine when training real networks of enormous sizes. Testing the performance of the proposed scheme against those algorithms on a toy quadratic problem is not a convincing result that can be used to claim \"up to a 50% improvement\". I acknowledge that deriving theoretical guarantees for Math-L2O seems to be a challenging task, but the evaluation has to be on at least MLP model on MNIST, which is a standard benchmark in DL (although small).", "was_revised": true, "final_justification": "The authors addressed my main concerns during the rebuttals. I encourage them to incorporate their clarifications and modifications to the raised questions into the revised manuscript, such as:\n\n- limited size of tested models and scalability of the approach;\n\n- inaccuracies and typos in the claims and proofs;\n\n- necessary NTK regime in the theoretical analysis and possible ways to avoid it.", "rebuttal": "Thanks for your questions and suggestions.\n\nWeakness (W) and Questions (Q):\n\n1. Typos:\n\n   1. (W1) $\\mathbf{M}_1$\n\n      A: Defined in line 467, page 13.\n\n   2. (W1) $W_{[L]}$\n\n      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.\n\n   3. (Q3) $O(1 / T^2)$\n\n      A: Typo. Should be $O(1 / T)$.\n\n2.  (Q7) Lemma A.2 Proof and (Q8) $0 < P_t^{k} < 2$ \n\n   (Q7) A: $0 < P_t^{k} < 2$ is the configuration of activation by $2*sigmoid$. \n\n   (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.\n\n3. (Q4) Quantities in Line 223\n\n   A: They are symbols to simplify the formulations in lemmas and theorems. \n\n   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.\n\n4. (Q4) Existence of $a_0, \\bar{\\lambda}\\_\\ell, C\\_\\ell$\n\n   A: They can be deterministically defined by our initialization methods and can be probably confined to a closed set by stochastic initialization methods. \n\n   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.\n\n5. (Q4, Q9) Weyl's inequality and related bound proof\n\n   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$.\n\n6. (W1, Q10) Illustration of NTK\n\n   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.\n\n7. (Q5) Initialization strategy in Section 5\n\n   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.\n\n8. (Q1) & (Q2): Generalization problem: non-ReLU (Q1) and LSTM (Q2)\n\n   (Q1) A: As in line 572, we use 1-Lipchitz property of ReLU in the proof. Any activations with constant-Lipchitz can be applied.\n\n   (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.\n\n\n9. (W2) NN model on MNIST\n\n   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.\n   * L2O: As in the paper, 3 layers, the width of wide layer: 20 (similar to Scale 3 in Table 1, page 40)\n   * CNN: 1537 learnable parameters\n      * 1st layer: Conv2d(in_channels=1,out_channels=2,kernel_size=3,stride=1,padding=1,dilation=1). Other:Default\n      * 2nd layer: Conv2d(in_channels=1,out_channels=2,kernel_size=3,stride=1,padding=1,dilation=1). Other:Default\n      * 3rd layer: Linear(in_features=3\\*7\\*7,out_features=10). Other:Default. 10 is for 10 classes of digitals in MNIST.\n   * Configuration of GD\n   * Step size: 0.01\n   * Steps $T$: 10000\n   * Configuration of L2O\n   * Step size: 0.01\n   * Steps $T$: 100 (Note: Our results show that 100 step is enough.)\n   * Number of samples: 200 from MNIST\n   * Loss: Cross-entropy of all samples\n   * Training Epochs: 200\n   * Optimizer: SGD\n   * Learning rate and initialization: Learning rate is $10^{-6}$. $e=100$. (Configurations in our paper)\n\n   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.\n\n|  | 1 | 2  | 3 | 4| 5 | 6  | 7  | 8   | 9 | 10|\n| --- | ---| --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| GD | 9.0698e-03 | 2.7549e-03 | 1.4932e-03 | 9.9039e-04 | 7.2780e-04 | 5.6902e-04 | 4.6368e-04 | 3.8922e-04 | 3.3406e-04 | 2.9170e-04 |\n| L2O 100 Epoch | 2.9170e-04 | 2.9166e-04 | 2.9163e-04 | 2.9159e-04 | 2.9155e-04 | 2.9151e-04 | 2.9148e-04 | 2.9144e-04 | 2.9140e-04 | 2.9136e-04 |\n| L2O 200 Epoch | 1.2220e-04 | 1.2220e-04 | 1.2219e-04 | 1.2218e-04 | 1.2217e-04 | 1.2216e-04 | 1.2215e-04 | 1.2215e-04 | 1.2214e-04 | 1.2213e-04 |\n\n10. (Q6): Typo.\n\nLimitations:\n\n1. Generalization\n\n   A: We primarily aim to demonstrate that learning can enhance the convergence of existing algorithms, which can be generalized to any unrolling L2O framework. \n\n   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.\n\n   [1] Arthur J. et al. Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS, 2018.\n\n   [2] Chizat, L., & Bach, F. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. COLT, 2020.\n\n   [3] Yu, Z., & Li, Y. Divergence of Empirical Neural Tangent Kernel in Classification Problems. ICLR, 2025.\n\n   [4] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. ICML, 2021.\n\n2. NAG\n\n   A: NAG is achievable by dynamic system formulation.\n\n   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.\n\n   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.\n\n3. Input dimension\n\n   A: Our L2O model is coordinate wise, only 2 input features.\n\n   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}$."}, {"review_id": "PKbzBPOOFa", "reviewer": "Reviewer_ooXd", "summary": "This paper studies the convergence of learning an NN-based optimizer that is used to solve the quadratic optimization problem. In particular, the paper focus on Math-L2O, whose learned optimizer outputs a step size which is applied in the gradient descent step of the base optimization problem. By leveraging the NTK-based analysis, the paper derives a linear convergence rate of the optimizer training. The paper also provided experiments to validate the theoretical results.", "questions": "None.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n1. The problem tackled by this paper is both significant and difficult. To further support the contribution of the paper, experimental results showing that the assumptions made in previous works are unrealistic are also included.\n\n2. The paper deals with a complicated deep MLP optimizer in the Math-L2O setting. This is both technically difficult and general in terms of the result.\n\n3. The convergence result proved by the paper is a clean linear convergence with no extra error terms.\n\n**Weaknesses**\n\n1. The main concern I have about the paper is that Theorem 4.3 shows that applying the output step size to the GD optimization problem with a fixed number of steps $T$, the final loss converges to zero as the training steps $k$ goes to infinity. This is particularly confusing as it seems that there is no requirement on $T$. In particular, this means that, as long as we do sufficient training to the optimizer model, its output step size can result in a convergence of the base optimization problem even with one step of gradient descent, which seems super intuitive. I suggest the author to provide a reasonable explanation of this surprising result.\n\n2. The choice of the step size in (13a) and (13b) seems complicated. Yet, the paper does not provide a good interpretation of what these expressions means and how the step size scales intuitively. Without such interpretation, it is possible that the step size are super small and lead to very slow convergence.\n\n3. Some of the notations are unclear. For instance,  $W\\_{[L]}$ never appears on the right-hand side of Eq.(2), where the dependency should be through $X\\_T$. In Eq.(6) and Eq.(7) I believe that parentheses are missing in the product terms, and similarly for the equation in Lemma 4.2, where the last parenthesis should include $||W\\_{\\ell}^{k+1} - W\\_{\\ell}^k||_2$. Moreover, It is a bit unclear what $F(W^k)$ really denotes, although it could be inferred from the text that it is $F(X\\_T, W\\_{[L]})$.", "was_revised": true, "final_justification": "It is seems that my previous major concern is due to the typo in the paper, which the author has promised to fix in the camera ready version.", "rebuttal": "Thanks for your questions and suggestions.\n\nWeakness:\n\n1. (W1) Intuitive of our proposed framework\n\n   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.\n\n   [1] Sucker, Michael, and Peter Ochs. A Generalization Result for Convergence in Learning-to-Optimize. ICML 2025.\n\n   [2] Qingyu Song et al. Towards Robust Learning to Optimize with Theoretical Guarantees. CVPR 2024.\n\n   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.\n\n   \n2. (W2) Step size in Equations (13a) and (13b) \n\n   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. \n\n   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)).\n\n   * $\\bar{\\lambda}_{\\ell}$:  A positive constant upper bound for each NN layer $\\ell$. Demonstrated in the proof of Theorem 4.3.\n   * $\\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})$.\n   * $\\Phi_j$: A scalar-valued function w.r.t. step $j$. $\\Phi_j$ is $\\mathcal{O}(j)$ and $\\Omega(j)$.\n   * $\\Lambda_{j}$: $\\mathcal{O}(j^2)$ and $\\Omega(j^2)$.\n   * $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})$.\n   * $\\zeta_1$ and $\\zeta_2$: $\\zeta_1$ and $\\zeta_2$ are both $\\Omega(T)$ and $\\mathcal{O}(T)$.\n   * $\\delta\\_1^t$: $\\Omega(t\\bar{\\lambda}\\_{min}^{Lt})$ and $\\mathcal{O}(t\\bar{\\lambda}\\_{max}^{Lt})$.\n   * $\\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})$.\n   * $\\delta_3$: Both $\\Omega(T)$ and $\\mathcal{O}(T)$.\n   * $\\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))$.\n\n   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.\n\n   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}$.\n\n   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.\n\n   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.\n\n   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$.\n\n   * Inequality (12a) holds: $\\eta$ is $\\mathcal{O}(\\exp(2T\\bar{\\lambda}\\_{\\max}^L)T^{-2})$.\n\n   * Inequality (12b) holds: $\\mathcal{O}(\\bar{\\lambda}\\_{\\max}^{2-LT-2L}T^{-4}L^{-1})$.\n\n   * Inequality (12c) holds: $\\mathcal{O}(\\bar{\\lambda}_{\\max}^{-L}T^{-3})$.\n\n   * Inequality (12d) holds: $\\mathcal{O}(\\exp(T\\bar{\\lambda}\\_{\\max}^L)(\\bar{\\lambda}\\_{\\max}^{2L}T^2L)^{-\\frac{2}{3}})$. \n\n   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.\n\n   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.\n\n   [1] Arthur J. et al. Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS, 2018.\n\n   [2] Allen Z. et al. On the convergence rate of training recurrent neural networks. NeurIPS 2019\n\n   [3] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. ICML, 2021\n\n3. (W2) Unclear notations\n\n   A: Thank you for figuring out the typos. We will fix them in the final version.\n\n   $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$.\n\n   Parentheses: Due to character limit, we will fix it in the improved version.\n\n   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. \n\n   $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.\n\n   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$."}, {"review_id": "a9uKCc3OHz", "reviewer": "Reviewer_u4ci", "summary": "This work proves that the L2O methods probably improve the convergence of gradient descent.\nThe authors establish that L2O can improve GD convergence rates by a factor of $r_k$ and prove training convergence of the L2O network using NTK theory in the over-parameterized regime. To bridge theory and practice, they propose an initialization strategy that satisfies the theoretical assumptions. Experimental results demonstrate improved convergence stability of the trained optimizer and validate the effectiveness of the proposed initialization scheme.", "questions": "1. Regarding the improvement of L2O over GD:\n   - What are the upper and lower bounds of this improvement?\n   - Does this improvement stem primarily from learning optimal hyperparameters (as mentioned in line 205), or is there another explanation?\n   - What is the worst-case/generalization performance of the trained L2O optimizer? Is it consistently superior to GD across all test instances with varying problem parameters?\n2. Regarding neural network width requirements:\n   - Section 4 requires NN width to be O(Nd), which is reflected in experiments (e.g., width 5120 in line 320). Do smaller widths (e.g., O(d) as suggested by universal approximation theory) perform adequately in practice?\n   - Is there a direct performance comparison among the three neural network architectures in Table 1?", "limitations": "See the weakness.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n- It provides solid theoretical analysis for L2O training convergence using NTK theory in the over-parameterized setting.\n\nWeakness\n\n- Convergence improvement claims require clarification (Section 3.2):\n     - The relationship between the LHS of Eq. (8) and the RHS of Eq. (9) in line 198 is unclear. Does this indicate that an L2O algorithm's initial state matches non-learning GD algorithms? If so, does the Deterministic Initialization in Sec. 5 satisfy this requirement?\n     - The author claims \"Eq. (10) demonstrates a sub-linear convergence rate of at least $O(1/T^2)$\", which is unclear since Eq. (10) shows a convergence rate of $O(r_k \\beta / T)$ and $r_k$ is independent of $T$.\n     - $r_k$ in Eq. 10 seems not to appear in Sec. 5 or Sec. 6.\n     - A formal theorem with precise definitions and assumptions is needed to substantiate these claims.\n- Novelty clarification needed: \n    - The technical contribution when applying NTK theory to prove linear convergence of L2O training in Sec. 4, compared to the cited work (Nguyen 2021), should be stated more explicitly.\n\nI will reconsider my evaluation if these concerns are addressed.", "was_revised": true, "final_justification": "Initially, I scored 3, given the unclear improvement of L2O methods compared with gradient descent.\nAfter the clarification by the authors, I raised my score to 4, but not higher due to:\n- The convergence analysis for overparameterized L2O seems less critical than its generalization property.", "rebuttal": "Thanks for your questions and suggestions.\n\nWeaknesses:\n\n1. Weakness 1: Presentation\n\n   1. (W1) Presentation of convergence improvement\n\n      1. (W1.1) Relationship between Eq. (8) and Eq. (9).\n\n         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$.\n\n         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. \n\n         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.\n\n\n        2. (W1.2) Alignment between L2O algorithm's initial state and GD.\n\n            A: Yes.\n\n            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.\n\n   2. (W2) Sub-linear convergence rate of $O\\left(1 / T^2\\right)$\n\n      A: This is a typo. The correct version is $O\\left(1 / T\\right)$. We will fix it in the final version.\n\n\n   3. (W3) Connection between Section 3 and Section 4\n \n      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.\n\n   4. (W4) Precise definitions and assumptions for lemmas and theorems\n\n      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.\n\n2. Weakness 2: Novelty of NTK\n\n   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.\n\n   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.\n\n   [1] Allen-Zhu et al . On the convergence rate of training recurrent neural networks. NeurIPS 2019.\n\n   [2] Quynh Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. ICML, 2021.\n\n\nQuestions:\n\n1. (Q1) Improvement of L2O over GD\n\n   1. (Q1.1) Lower and upper bounds.\n\n      A: Lower bound is 0. Upper bound is 1.\n\n       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.\n\n   2. (Q1.2) Essential of improvement.\n\n       A: Yes. \n\n       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.\n\n   3. (Q1.3) Generalization \n\n      A: Empirically, the inference performance in Figure 8 shows that it generalizes well.\n\n      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.\n\n      [1] Sucker, Michael, and Peter Ochs. A Generalization Result for Convergence in Learning-to-Optimize. ICML 2025.\n\n      [2] Qingyu Song et al. Towards Robust Learning to Optimize with Theoretical Guarantees. CVPR 2024.\n\n2. (Q2) Neural network width requirements\n\n   1. (Q2.1) NN width requirement\n\n      A: Yes. Scale 3 in Table 1, page 40, is an under-parameterized case.\n\n      $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.\n\n   2. (Q2.2) Performance comparison of scales in Table 1\n\n      A: They are not on the same scale.\n\n      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."}, {"review_id": "5i49xF8qvf", "reviewer": "Reviewer_VMJi", "summary": "This paper addresses a significant and often overlooked issue in the Learning to Optimize (L2O) field: the formal proof of convergence for the training process of L2O models. The authors focus on the Math-L2O framework and leverage Neural Tangent Kernel (NTK) theory to prove that learning hyperparameters for Gradient Descent (GD) can provably enhance its convergence rate. A novel initialization strategy is also introduced to support the theoretical claims and ensure training stability.", "questions": "While the contributions are significant, the paper's clarity could be improved in several key sections. The following points should be addressed to strengthen the manuscript.", "limitations": "In section 3.1: the goal of this section is to analyze the limitations of existing frameworks, but the presentation could be more specific and balanced.\n\n- In Lines 157-162, the descriptions of prior work use general terms like \"stringent conditions\" and \"necessary conditions\" without immediately specifying what those conditions are. It would be more impactful to state the specific limitations upfront before the empirical analysis.\n- The section provides a detailed empirical analysis of the limitations of LISTA-CPSS (e.g., training instability and violation of sign consistency conditions). However, a similar analysis for the Math-L2O framework, which is also introduced as a target of analysis in this section, appears to be missing. The text should clarify the specific limitations of the original Math-L2O framework that this work aims to overcome.\n\nIn section 3.2: This section introduces the core conceptual framework of the paper, but its presentation is difficult to follow.\n- Can you explain that why $X_{T}^0$ occurs two sides of equation (9)?\n- In Line 202, the paper asserts that Equation (10) demonstrates a sub-linear convergence rate of at least $O(1/T^2)$. Can you illustrate it more details?", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The primary strength of this work lies in its novelty and significance. Many L2O frameworks implicitly assume that the underlying neural network models are trainable and will converge during training.", "was_revised": true, "final_justification": "I am not very familiar with this field. If my understanding is correct, this work would be highly significant. However, the current writing requires more careful revision. Overall, the manuscript remains somewhat unrefined and requires further careful revision.", "rebuttal": "Thanks for your questions and suggestions.\n\n1. (L1) Presentation of Section 3.1\n\n   1. (L1.1) Explanation for \"stringent conditions\" and \"necessary conditions\"\n\n      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). \n\n      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.\n\n   2. (L1.2) Empirical results of Math-L2O\n\n      A: The evaluation results of Math-L2O are in Figure 3(b). \n\n      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$.\n\n2. (L2)  Presentation of Section 3.2\n\n   1. (L2.1) $X_T^0$ in both size of inequality.\n\n      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$.\n\n      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. \n\n      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$. \n      This is due to $X_0$ being a given initial point, which is not violated by training iteration $k$. \n      In this inequality, the superscript is $^k$, which means that this is not related to training iteration. \n      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.\n\n   2. (L2.2) Sub-linear convergence rate of $\\mathcal{O}(1/T^2)$\n\n      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."}]

Author rebuttal:

Meta-review: **Summary.** This work presents a rigorous convergence analysis for the Learning to Optimize (L2O) framework. Specifically, the authors study the learning of coordinate-wise step sizes for Gradient Descent (GD) applied to the least-squares problem and demonstrate theoretical improvements over standard GD. The paper establishes a linear convergence rate for the Math-L2O framework, and the theoretical claims are well supported by accompanying numerical experiments.

**Strengths and weaknesses.** All reviewers recognize the non-triviality of the considered problem and acknowledge that the paper makes a meaningful contribution toward bridging the gap in the theoretical understanding of L2O methods. On the other hand, reviewers highlighted several weaknesses, including the limited scale of tested models, questions about scalability, and some inaccuracies and typographical errors in the claims and proofs. The authors acknowledged these issues and committed to addressing them in the final version.

**Final recommendation.** Given the importance of the problem, the novelty of the results, and the positive assessments from the reviewers, I recommend acceptance. In my view, the strengths of the paper outweigh its weaknesses. However, it is crucial that the authors carefully implement all the promised corrections and improvements in the camera-ready version.
Decision: Accept (poster)