Hyperparameter Tuning is All You Need for LISTA
Year: 2021

Abstract:
Learned Iterative Shrinkage-Thresholding Algorithm (LISTA) introduces the concept of unrolling an iterative algorithm and training it like a neural network. It has had great success on sparse recovery. In this paper, we show that adding momentum to intermediate variables in the LISTA network achieves a better convergence rate and, in particular, the network with instance-optimal parameters is superlinearly convergent. Moreover, our new theoretical results lead to a practical approach of automatically and adaptively calculating the parameters of a LISTA network layer based on its previous layers. Perhaps most surprisingly, such an adaptive-parameter procedure reduces the training of LISTA to tuning only three hyperparameters from data: a new record set in the context of the recent advances on trimming down LISTA complexity. We call this new ultra-light weight network HyperLISTA. Compared to state-of-the-art LISTA models, HyperLISTA achieves almost the same performance on seen data distributions and performs better when tested on unseen distributions (specifically, those with different sparsity levels and nonzero magnitudes). Code is available: https://github.com/VITA-Group/HyperLISTA.

heading: 1 Introduction
text: In this paper, we study the sparse linear inverse problem, where we strive to recover an unknown sparse vector x∗ ∈ Rn from its noisy linear measurement b generated from
b = Ax∗ + ε, (1)
where b ∈ Rm is the measurement that we observe, A ∈ Rm×n is the dictionary, x∗ ∈ Rn is the unknown ground truth that we aim to recover, and ε ∈ Rm is additive Gaussian white noise. For simplicity, each column of A, is normalized to have unit `2 norm. Typically, we have much fewer rows than columns in the dictionary A, i.e., m n. Therefore, Equation (1) is an under-determined system. The sparse inverse problem, also known as sparse coding, plays essential roles in a wide range of applications including feature selection, signal reconstruction and pattern recognition.
Sparse linear inverse problems are well studied in the literature of optimization. For example, it can be formulated into LASSO [29] and solved by many optimization algorithms [9, 3]. These solutions explicitly consider and incorporate the sparsity prior and usually exploit iterative routines. Deep-learning-based approaches are proposed for empirically solving inverse problems recently [25], which produce black-box models that are trained with data in an end-to-end way, while somehow ignoring the sparsity prior. Comparing the two streams, the former type, i.e., the classic optimization methods, takes hundreds to thousands of iterations to generate accurate solutions, while black-box deep learning models, if properly trained, can achieve similar accuracy in tens of layers. However, classic methods come with data-agnostic convergence (rate) guarantees under suitable conditions,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
∗The first two authors made equal contributions.
whereas deep learning methods only empirically work for instances similar to the training data, lacking theoretical guarantees and interpretability. More discussions are found in [6].
Unrolling is an uprising approach that bridges the two streams [22, 21]. By converting each iteration of a classic iterative algorithm into one layer of a neural network, one can unroll and truncate a classic optimization method into a feed-forward neural network, with a finite number of layers. Relevant parameters (e.g., the dictionary, step sizes and thresholds) in the original algorithm are transformed into learnable weights, that are trained on data. [15] pioneered the unrolling scheme for solving sparse coding and achieved great empirical success. By unrolling the Iterative Shrinkage-Thresholding Algorithm (ISTA), the authors empirically demonstrated up to two magnitudes of acceleration of the learned ISTA (LISTA) compared to the original ISTA. The similar unrolling idea was later extended to numerous optimization problems and algorithms [28, 30, 26, 13, 36, 2, 16, 8, 5].

heading: 1.1 Related Works
text: The balance between empirical performance and interpretability of unrolling motivates a line of theoretical efforts to explain their acceleration success. [23] attempted to understand LISTA by re-factorizing the Gram matrix of the dictionary A in (1) and proved that such re-parameterization converges sublinearly and empirically showed that it achieved similar acceleration gain to LISTA. [33] investigated unrolling iterative hard thresholding (IHT) and proved the existence of a matrix transformation that can improve the restricted isometry property constant of the original dictionary. Although it is difficult to search for the optimal transformation using classic optimization techniques, the authors of [33] argued that the data-driven training process is able to learn that transformation from data, and hence achieving the acceleration effect in practice.
The work [7] extended the weight coupling necessary condition in [33] to LISTA. The authors for the first time proved the existence of a learnable parameter set that guarantees linear convergence of LISTA. Later in [18], they further showed that the weight matrix in [7] can be analytically derived from the dictionary A and free from learning, reducing the learnable parameter set to only tens of scalars (layer-wise step sizes and thresholds). The resulting algorithm, called Analytic LISTA (ALISTA), sets one milestone in simplifying LISTA. [31] extends ALISTA by introducing gain and overshoot gating mechanisms and integrate them into unrolling. [37] proposed error-based thresholding (EBT), which leverages a function of the layer-wise reconstruction error to suggest an appropriate threshold value for each observation on each layer. Another interesting work [4] uses a black-box LSTM model that takes the historical residual and update quantity as input and generates layerwise step sizes and thresholds in ALISTA. Their proposed model, called Neurally Augmented ALISTA (NA-ALISTA), performed well in large-scale problems.

heading: 1.2 Our Contributions
text: Our research question is along the line of [18, 37, 4]: can we improve the LISTA parameterization, by further disentangling the learnable parameters from the observable terms (e.g., reconstruction errors, intermediate outputs)? Our aim is to create more light-weight, albeit more robust LISTA models with “baked in" adaptivity to testing samples from unseen distributions. The goal should be achieved without sacrificing our previously attained benefits: empirical performance, and convergence (rate) guarantees – if not improving them further.
We present an affirmative answer to the above question by learning instance-optimal parameters with a new ALISTA parameterization. First, we prove that by augmenting ALISTA with momentum, the new unrolled network can achieve a better convergence rate over ALISTA. Second, we find that once the above LISTA network is further enabled with instance-optimal parameters, then a superlinear convergence can be attained. Lastly, we show that those instance-optimal parameters of each layer can be generated in closed forms, consequently reducing ALISTA to only learning three instanceand layer-invariant hyperparameters.
Our new ultra-light weight network is termed as HyperLISTA. Compared to ALISTA, the new parameterization of HyperLISTA facilitates new backpropagation-free “training" options (e.g., bayesian optimization), and can unroll to more iterations in testing than training thanks to its layer-wise decomposed form. When comparing to state-of-the-art LISTA variants in experiments, HyperLISTA achieves the same strong performance on seen data distributions, and performs better when tested on unseen distributions (e.g., with different sparsity levels and nonzero magnitudes). In the supple-
mentary materials, we also show that the superlinear convergence can be observed in HyperLISTA experiments, when our automatic parameter tuning is performed per instance.

heading: 2 Assumptions and Preliminaries
text: Mathematical Notations: We represent a matrix as a capital bold letter W , diag(W ) means the diagonal elements of matrix W and the pseudoinverse of a matrix is denoted by W+. A vector is represented as a lowercase bold letter x and its entries are represented as lowercase regular letters with lower indices x = [x1, x2, · · · , x3]T . Upper indices represent iterations or layers. Moreover, 0,1 represent a vector with all zeros or all ones, respectively. “supp(x)" denotes the support, the indices of all nonzeros in vector x.
ISTA Algorithm: With an `1 penalty term, the minimizer of LASSO, argminx 12‖Ax−b‖ 2 2+λ‖x‖1, provides an estimate of the solution of the sparse recovery problem (1). A popular algorithm to solve LASSO is Iterative Shrinkage-Thresholding Algorithm (ISTA):
x(k+1) = ηλ/L ( x(k) + 1
L AT (b−Ax(k))
) , k = 0, 1, 2, . . .
where ηλ/L is the element-wise soft-thresholding function ηθ(x) = sign(x) max(0, |x| − θ) with θ = λ/L and L is usually taken as the largest eigenvalue of ATA.
LISTA Model: The original LISTA work [15] parameterizes ISTA as x(k+1) = ηθ(k) ( W (k) 1 x (k) + W (k) 2 b ) , k = 0, 1, 2, . . . (2)
where Θ = {W (k)1 ,W (k) 2 , θ (k)} are learnable parameters to train from data. In the training process, iterations formulated in (2) are unrolled and truncated to K steps and the parameters are trained by minimizing the following loss function defined over the distribution of training samples Dtr:
minimize Θ
E(x∗,b)∼Dtr ∥∥∥x(K)(Θ, b,x(0))− x∗∥∥∥2
2 . (3)
Here x(K)(Θ, b,x(0)), the output of the LISTA model, is a function with input Θ, b and x(0). In practice, we usually set x(0) = 0. We will use x(K) to refer to x(K)(Θ, b,x(0)) for brevity in the remainder of this paper. x∗ denotes the underlying ground truth defined in (1). Although it cannot be accessed in iterative algorithm (2), it can be used as the label in supervised training (3).
ALISTA Model: ALISTA [18] advances LISTA with a lighter and more interpretable parameterization, where the learnable parameters are Θ = {γ(k), θ(k)} and the iterations are formulated as
x(k+1) = ηp (k)
θ(k)
( x(k) + γ(k)W T (b−Ax(k)) ) , (4)
where W is calculated by solving the following optimization problem:
W ∈ argmin W∈Rm×n
∥∥W TA∥∥2 F , s.t. diag(W TA) = 1. (5)
The thresholding operator is improved with support selection. At layer k, a certain percentage of entries with largest magnitudes are trusted as “true support” and will not be passed through thresholding. Specifically, the i-th element of ηp (k)
θ(k) (v) is defined as
(ηp (k)
θ(k) (v))i =  vi : vi > θ (k), i ∈ Sp(k)(v), vi − θ(k) : vi > θ(k), i /∈ Sp (k) (v), 0 : −θ(k) ≤ vi ≤ θ(k) vi + θ (k) : vi < −θ(k), i /∈ Sp (k) (v),
vi : vi < −θ(k), i ∈ Sp (k) (v),
(6)
where Sp (k) (v) includes the elements with the largest p(k) magnitudes in vector v ∈ Rn:
Sp (k) (v) = { i1, i2, · · · , ip(k) ∣∣∣|vi1 | ≥ |vi2 | ≥ · · · |vip(k) | · · · ≥ |vin |}. (7)
With p(k) = 0, the operator reduces to the soft-thresholding and, with p(k) = n, the operator reduces to the hard-thresholding. Thus, operator ηp (k)
θ(k) (v) is actually a balance between soft- and
hard-thresholding. When k is small, p(k) is usually chosen as a small fraction of n and the operator tends to not trust the signal, and vice versa. In ALISTA, p(k) is proportional to the index k, capped by a maximal value, i.e., p(k) = min(p · k, pmax), where p and pmax are two hyperparameters that will be tuned manually. Later in this work, we will consider p(k) as a parameter that could be adaptively calculated by the information from previous iterations (layers).
More Notations and Assumptions: Throughout this paper, we refer to “parameters” as the learnable weights in the models, such as the thresholds θ(k) and the step sizes γ(k) that are defined in the ALISTA model, which are usually trained by back-propagation. In contrast, we refer “hyperparameters” as those constants that are often ad-hoc pre-defined to calculate parameters. For example, θ(k) = c1‖A+(Ax(k) − b)‖1, where θ(k) is a parameter and c1 is a hyperparameter. Assumption 1 (Basic assumptions). The signal x∗ and noise ε are sampled from the following set:
X (B,B, s, σ) , { (x∗, ε) ∣∣∣‖ε‖1 ≤ σ, ‖x∗‖0 ≤ s, 0 < B ≤ |x∗i | ≤ B, ∀i ∈ supp(x∗)}. (8)

heading: In other words, x∗ is bounded and sparse. σ > 0 is the noise level.
text: Compared with the Assumption 2 in [7], the assumption of “|x∗i | ≥ B > 0” for non-zero elements in x∗ is slightly stronger. But we will justify (after Theorem 1) that uniformly under Assumption 1 in this paper, our method also achieves a better convergence rate than state-of-the-arts.

heading: 3 Methodologies and Theories
text: In this section, we extend the ALISTA (4) in three aspects. First, we introduce a better method to calculate matrix W in formula (5). Second, we augment the x-update formula (4) by adding a momentum term. Finally, we propose an adaptive approach to obtain the parameters p(k), θ(k), γ(k).

heading: 3.1 Preparation: Symmetric Jacobian of Gradients
text: Before improving the formula (5), we first briefly explain its main concepts and shortcomings. Mutual coherence is a key concept in compressive sensing[11, 10]. For matrix A, it is defined as maxi6=j |(ATA)i,j | where (ATA)i,i = 1 since each column of A is assumed with unit `2 norm. A matrix with low mutual coherence satisfies that ATA approximates the identity matrix, thus implying a recovery of high probability. In ALISTA [18], the authors extended this concept to a relaxed bound between matrix A and another matrix W : ‖W TA‖F (described in (5)). By minimizing this bound, they obtained a good matrix W that can be plugged into the LISTA framework.
One clear limitation of ALISTA is that, with W obtained by (5), the model is only able to converge to x∗ but not the LASSO minimizer [2]. Consequently, one has to train ALISTA with known x∗ in a supervised way (3). This is partially due to the fact that the update direction W T (Ax− b) in ALISTA is not aligned with the gradient of the `2 term in the LASSO objective: ∇x 12‖Ax− b‖ 2 2 = AT (Ax− b). This limitation motivates us to adopt a new symmetric Jacobian parameterization so that W TA is symmetric and the coherence between A and W is minimized.
Inspired by [1], we define W = (GTG)A (the matrix G ∈ Rm×m is named as the Gram matrix), and get the following problem instead of (5):
min G ‖ATGTGA− I‖2F , s.t. diag(ATGTGA) = 1. (9)
However, the constraint in the above problem (9) is hard to handle. Thus, we introduce an extra matrix D = GA ∈ Rm×n and use the following method instead to calculate dictionary:
min G,D ‖DTD − I‖2F +
1 α ‖D −GA‖2F , s.t. diag(DTD) = 1. (10)
With proper α > 0, the solution of (10) approximates (9) well. We use an adaptive rule to choose α and adopt a variant of the algorithm (described in details in the supplement) proposed in [19] to solve (10). Such formula leads to a symmetric matrix W TA = (GA)T (GA). With this symmetry, the vector W T (Ax − b) is actually the gradient of function 12‖G(Ax − b)‖ 2 2 with respect to x.
γ(k)W TA (k ≥ 1). The momentum creates extra skip connections at the bottom.
One may train model (4) using methods in [2] with the following loss function without knowing the ground truth: F (x) = 12‖G(Ax− b)‖ 2 2 + λ‖x‖1. On the other hand, it usually holds that
‖W TA− I‖F ≈ ‖(GA)T (GA)− I‖F , (11)
where W is calculated by (5) and G is calculated by (10). We validate (11) by numerical results in Section 4.1. Conclusion (11) demonstrates that the mutual coherence between A and (GTG)A is similar to that between A and W obtained by (5). Although we limit the matrix W TA to be symmetric, (10) hardly degrades any performance of the ALISTA framework compared to (5).

heading: 3.2 ALISTA with Momentum: Improved Linear Convergence Rate
text: As is well known in the optimization community, adding a momentum term can accelerate many iterative algorithms. Two classic momentum algorithms were respectively proposed by Polyak [27] and Nesterov [24]. Nesterov’s algorithm alternates between the gradient update and the extrapolation, while Polyak’s algorithm can be written as an iterative algorithm within the space of gradient updates by simply adding a momentum term. To avoid extra training overhead, we use Polyak’s heavy ball scheme and add a momentum term to the ALISTA formula for k ≥ 12 (illustrated in Figure 1):
x(k+1) = ηp (k)
θ(k)
( x(k) + γ(k)W T (b−Ax(k)) + β(k)(x(k) − x(k−1)) ) (12)
Note that there are other LISTA variants that incorporated additional momentum forms [23, 32], but they did not contribute to provably accelerated convergence rate. Defining constant µ as the mutual coherence of D, i.e., µ := maxi 6=j |(D:,i)TD:,j |, we have the following theorem, which demonstrates that, in the context of (A)LISTA, model (12) can provide a faster linear convergence rate, than that of ALISTA in the same settings.
Theorem 1 (Convergence of ALISTA-Momentum). Let x(0) = 0 and {x(k)}∞k=1 be generated by (12). If Assumption 1 holds and s < (1 + 1/µ)/2 and σ is small enough, then there exists a uniform sequence of parameter {θ(k), p(k), γ(k), β(k)}∞k=1 for all (x∗, ε) ∈ X (B,B, s, σ) such that
‖x(k) − x∗‖2 ≤ C0 k∏ t=0 c(t)+ 2sCW 1− 2µs+ µ σ, ∀k = 1, 2, · · · , (13)
where C0 > 0 is a constant depending on s,B, µ and CW = max1≤i,j≤n |Wi,j |. The convergence rate c(k) > 0 satisfies:
c(k) ≤ 2µs− µ < 1, ∀k (14)
c(k) ≤ 1− √
1− 2µs+ µ < 2µs− µ, ∀k ≥ log(B)− log(2C0) log(2µs− µ)
(15)
and the parameter sequence satisfies
θ(k) =µ sup (x∗,ε)∈X (B,B,s,σ)
{ ‖x(k) − x∗‖1+CWσ } , γ(k) = 1, ∀k
β(k) → ( 1− √ 1− 2µs+ µ )2 , p(k) → n, as k →∞
(16)
2As k = 0, we keep the ALISTA formula since x(−1) is not defined.
Despite remaining linearly convergent, our model has an initial rate of 2µs − µ that is no worse than the rates in state-of-the-arts [7, 18, 1] and an eventual rate 1 − √ 1− 2µs+ µ that is strictly better than the rate in [7] because 2µs − µ > 1 − √
1− 2µs+ µ as 2µs − µ < 1. For example, if 2µs − µ = 0.9, then our new rate is 1 − √ 1− 2µs+ µ ≈ 0.684. Moreover, the eventual error 2sCWσ/(1− 2µs+ µ) is no worse than that in [7]. Proof details can be found in the supplement.

heading: 3.3 Instance-Adaptive Parameters: From Linear to Superlinear Convergence
text: State-of-the-art theoretical results show that LISTA converges with a linear rate [7, 18, 1, 31, 35]. In ALISTA [18], the authors show that linear convergence is a lower bound. This means that one cannot expect a superlinear rate if a uniform set of optimal parameters are learned for a dataset.
One promise to enhance the rate in Theorem 1 is to further introduce instance adaptivity. We establish that, if {θ(k), p(k), γ(k), β(k)}∞k=1 can be searched for an instance, such instance-optimal parameters lead to superlinear convergence.
Theorem 2. Let x(0) = 0 and {x(k)}∞k=1 be generated by (12). If Assumption 1 holds and s < (1 + 1/µ)/2 and σ is small enough, then there exists a sequence of parameters {θ(k), p(k), γ(k), β(k)}∞k=1 for each instance (x∗, ε) ∈ X (B,B, s, σ) so that we have:
‖x(k) − x∗‖2 ≤ √ sB k∏ t=0 c̄(t)+ 2sCW 1− 2µs+ µ σ, ∀k = 1, 2, · · · , (17)
where CW is defined in Theorem 1 and the convergence rate c̄(k) satisfies
c̄(k) → 0 as k →∞. (18)
To achieve this super-linear convergence rate, parameters are chosen as follows: θ(k) = γ(k) ( µ‖x(k) − x∗‖1 + CWσ ) , ∀k (19)
and p(k) follows (16) for all k. The other two parameters γ(k), β(k) follow (16) at the initial stage (with small k) and they are instance-adaptive as k large enough. Consequently, the model (12) reduces to the conjugate gradient (CG) iteration on the following linear system as k large enough:
W TS ( ASxS − b ) = 0, (20)
where S denotes the support of x∗ and AS ,WS denotes, respectively, the sub-matrices of A,W with column mask S.

heading: 3.4 HyperLISTA: Reducing ALISTA to Tuning Three Hyperparameters
text: Adaptive Parameters Based on Theorem 2, we design the following instance-adaptive parameter formula as the recovery signal x(k) is not accurate enough (equivalently, as k is small):
γ(k) = 1, (21) θ(k) = c1µγ (k) ∥∥A+(Ax(k) − b)∥∥
1 , (22)
β(k) = c2µ ‖x(k)‖0, (23)
p(k) = c3 min ( log ( ‖A+b‖1
‖A+(Ax(k) − b)‖1
) , n ) , (24)
where c1 > 0, c2 > 0, c3 > 0 are hyper-parameters to tune.
The step size formula (21) stems from the conclusion (16) as Theorem 2 suggests. The threshold θ(k) in (19) cannot be directly used due to its dependency on the ground truth x∗. In (22), we use ‖A+(Ax(k) − b)‖1 to estimate (19) because∥∥A+(Ax(k) − b)∥∥ 1 = ∥∥A+A(x(k) − x∗)−A+ε∥∥ 1 ≈ O ( ‖x(k) − x∗‖1 ) +O ( σ ) .
Similar thresholding schemes are studied in [37].
The momentum rule (23) is obtained via equation (16). The momentum factor β(k) is asymptotically equal to ( 1 − √ 1− 2µs+ µ )2
, which is a monotonic increasing function w.r.t. s, the number of nonzeros in the ground truth sparse vector x∗. Therefore, `0 norm of x(k) is a natural choice to approximate β(k), considering that x(k) will gradually converge to x∗ and hence ‖x(k)‖0 to ‖x∗‖0. The support selection rule (24) can be explained as follows. First we sort the magnitude of |x∗i | as in Figure 2. At the k-th layer, given e(k) = ‖x(k) − x∗‖∞, each element in x(k) can be bounded as
|x∗i | − e(k) ≤ |x (k) i | ≤ |x ∗ i |+ e(k), ∀i.
Such area is shown as the gray area in Figure 2. As we discussed in Section 2 following definition (6), the support selection is a scheme to select those elements that can be trusted as true support. The “trust region" in Figure 2 illustrates such entries. Intuitively, the trust region should be larger as the error e(k) gets smaller. We propose to use the logarithmic function of the error to estimate p(k).
p(k) ≈ c3 log ( ‖x∗‖∞ e(k) ) ≈ c3 log ( ‖A+b‖1 ‖A+(Ax(k) − b)‖1 ) (25)
The hyperparameter 0 < c3 < 1 is to tune based on the distribution of x∗. With an upperbound n (the size of the vector x∗), we obtain (24). Actually (25) can be mathematically derived by assuming the magnitude of the nonzero entries of x∗ are normally distributed. (The derivation can be found in the supplement.) As k → ∞, it holds that e(k) → 0 and p(k) → n, which means that the operator ηp (k)
θ(k) is getting close to a hard-thresholding operator. The support selection scheme proposed in LISTA-CPSS [7] also follows such principle but it requires more prior knowledge. Compared to that, formula (24) is much more automatic and self-adaptive.
Switching to Conjugate Gradients Theorem 2 suggests that one may call conjugate gradient (CG) to obtain faster convergence as the recovery signal x(k) is accurate enough. In practice, we choose to switch to CG as k is large enough such that p(k) is large enough. The linear system (20) to be solved by CG depends on the support of x∗ and we estimate the support by the support of x(k) since we assume x(k) is accurate enough when we call CG. Finally, HyperLISTA is described in Algorithm 1.

heading: 3.5 Hyperparameter-Tuning Options for HyperLISTA
text: HyperLISTA has reduced the complexity of the learnable parameters to nearly the extreme: only three. While backpropagation remains to be a viable option to solve them, it becomes an over-kill to solve just three variables by passing gradients through tens of neural network layers. Besides, the hyperparameter c3 in (23) decides the ratio of elements that will be selected into the support and hence passes the thresholding function; that makes c3 non-differentiable in the computation graph.
Instead, we are allowed to seek simpler, even gradient-free methods to search for the parameters. We also empirically find HyperLISTA has certain robustness to perturbing the found values of c1, c2, c3, which also encourages us to go with less precise yet much cheaper search methods.
Algorithm 1: HyperLISTA with tuned c1, c2, c3 Input: Observation b, dictionary A, hyperparameters c1, c2, c3. Initialize :Let x(0) = 0.
1 Calculate D and G with (10), set W = (GTG)A. 2 Calculate µ with µ = maxi6=j |(DTD)i,j |. 3 for j = 0, 1, 2, . . . until convergence do 4 Conduct iteration (12) with parameters defined in (22 - 24). 5 if p(k) is large enough then 6 break 7 end 8 end 9 Set S = supp(x(k)), call the conjugate gradient algorithm to solve linear system (20).
Output: x̂, the result of the conjugate gradient.
In this work, we try replacing the backpropagation-based training with the vanilla grid search for learning HyperLISTA. Besides the ultra-light parameterization, another enabling factor is the low evaluation cost on fitness of hyperparameters: just running inference on one minibatch of training samples with them, and no gradient-based training needed. From another aspect, HyperLISTA can be viewed as an iterative algorithm instead of an unfolded neural network. It can be optimized directly on the unseen test data, as long as one wants to afford the cost of re-searching hyperparameters on each dataset, whose cost is still much lower than training using back-propagation.
Specifically, we we first use a coarse grid to find an “interested region” of hyperparameters, and then zoom-in with a fine-grained grid. Details are to be found in Section 4.2, and we plan to try other options such as bayesian optimization [12] in future work.

heading: 4 Numerical experiments
text: Experiment settings We use synthesized datasets of 51,200 samples for training, 2,048 validation and 2,048 testing. We follow previous works [7, 18] to use a problem size of (m,n) = (250, 500). The elements in the dictionary A are sampled from i.i.d. standard Gaussian distribution and we then normalize A to have unit `2 column norms. The sparse vectors x∗ are sampled from N(0, σ2) · Bern(p), where N(µ, σ2) represents the normal distribution and Bern(p) the Bernoulli distribution with probability p to take value 1. By default, we choose σ = 1 and p = 0.1, meaning that around 10% of the elements are non-zero whose magnitudes further follows a standard Gaussian distribution. The additive noise ε in (1) follows Gaussian distribution N(0, σ2ε). The noise level is measured by signal-to-noise ratio (SNR) in decibel unit. Note that we can change the values of σ, p and σε during testing to evaluate the adaptivity of models. In all experiments, the model performance is measured by normalized mean squared error (NMSE, same as defined in [7, 18]) in decibel unit. All models are unrolled and truncated to 16 layers for training and testing following the typical setting in [7, 18, 31], unless otherwise specified. Besides synthesized data, we also evaluate HyperLISTA on a compressive sensing task using natural images. The results are presented in Appendix B due to limited space.
Comparison Methods: In this section, we compare with the original LISTA [15] formulated in (2), ALISTA formulated in (4) and its variant with momentum acceleration denoted as ALISTA-MM (12). A suffix -Symm will be added if a model adopts the symmetric parameterization introduced in Section 3.1. We use HyperLISTA(-Full) to represent our proposed method in which we optimize all three hyperparameters c1, c2, c3 in (22) - (24) using grid search. In contrast, we can use backpropagation to train c1 and c2 and leave p(k) manually selected as in ALISTA because the loss function is not differentiable with respect to p(k). The resulting model is denoted as HyperLISTA-BP. Other baselines include Ada-LISTA [1] and NA-ALISTA [4].

heading: 4.1 Validation of symmetric matrix parameterization and Theorem 1
text: We first validate the efficacy of the symmetric matrix parameterization and Theorem 1, showing the acceleration brought by the momentum term. For this validation, we compare four models: ALISTA,
ALISTA-Symm, ALISTA-MM and ALISTA-MM-Symm. We train them on the same dataset and compare their performance measured by NMSE on the testing set. Here, the support selection ratios are selected by following the recommendation in the official implementation of [18]. Results are shown in Figure 33. As we can see from Figure 3, the symmetric matrix parameterization results in almost no performance drop, corroborating the validity of the new parameterization. On the other hand, introducing momentum to both parameterization brings significant improvement in NMSE.

heading: 4.2 Validation of instance-optimal parameter selection and grid search
text: In this subsection, we show that the adaptive parameterization in Eqns (22) - (24), i.e., HyperLISTA, can perform as well as or even better than the uniform parameterization in (12), and we also show the efficacy of the grid search method. We optimize HyperLISTA-Full using grid search and train HyperLISTA-BP with backpropagation-based method (SGD), respectively. For a fair comparison with HyperLISTA-BP, we introduce a variant of HyperLISTA-Full in which we only grid-search c1
3Here ALISTA achieves a worse NMSE than that in [18]. We attribute this to the finite-size training set that we use here instead of unlimited training set in [18].
and c2 in (22) and (23) and use the same p(k) as manually selected in HyperLISTA-BP. We denote this variant as HyperLISTA-GS. Figure 4 show that grid search can find even better solutions than backpropagation and the uniform parameterization. When we further use grid search for searching c1, c2, c3 simultaneously (HyperLISTA-Full), there is more performance boost.

heading: 4.3 Comparison of adaptivity with previous work
text: We conduct experiments when there exists mismatch between the training and testing. We instantiate training/testing mismatch in terms of different sparsity levels in the sparse vectors x∗, different distributions of non-zero elements in x∗, and different additive noise levels. We compare HyperLISTA with ALISTA [18] and its variant ALISTA-MM-Symm, Ada-LFISTA [1] and NA-ALISTA [4] which also dynamically generates parameters per input using an external LSTM. Figure 5 show that in the original and all three mismatched cases, HyperLISTA achieves the best performance, especially showing excellent robustness to the non-zero magnitude distribution change (Fig. 5c). Note our computational overhead is also much lower than using LSTM.
Directly unrolling HyperLISTA to more layers Another hidden gem in HyperLISTA is that it learns iteration-independent hyperparameters, which, once searched and trained (on some fixed layer number), can be naturally extended to an arbitrary number of layers. Although NA-ALISTA [4] can also be applied to any number of layers, it has worse performance and adaptivity compared to HyperLISTA, as we compare in Figure 6.
We also compare HyperLISTA with another baseline of 40-layer ALISTA (named as ALISTA-Extra), which is directly extrapolated from a 16-layer ALISTA model by reusing the last layer parameters. We can clearly observe that ALISTA cannot directly scale with more layers unrolled.

heading: 5 Conclusions and Discussions of Broad Impact
text: In this paper, we propose a ultra-light weight unrolling network, HyperLISTA, for solving sparse linear inverse problems. We first introduce a new ALISTA parameterization and augment it with momentum, and then propose an adaptive parameterization which reduces the training of HyperLISTA to only tuning three instance- and layer-invariant hyperparameters. HyperLISTA is theoretically proved and also empirically observed to have super-linear convergence rate as it uses instance-optimal parameters. Compared to previous work, HyperLISTA achieves faster convergence on the seen distribution (i.e., the training data distribution) and shows better adaptivity on unseen distributions.
As a limitation, we do not consider perturbations in dictionaries in this work yet. We also find that HyperLISTA, as a compact model similar to ALISTA [18], may fail to perform well on signals with complicated structures such as real images, where the underlying sparse linear model (1) becomes oversimplified and no longer holds well. We will investigate these further in the future.
We do not see that this work will impose any social risks to the society. Besides the intellectual merits, the largest potential societal impact of this work is that unrolling models can be trained more efficiently and meanwhile more adaptive, increasing the reusability.

Review summaries:
The authors propose an extension to the ALISTA algorithm. Momentum is added to the update rule to speed up convergence, and parameters are adaptively determined per layer, rather than learned over a training distribution. Such adaptivity was recently proposed in the NA-ALISTA algorithm as well, but this solution is more light-weight. HyperLISTA was shown to converge faster and to lower optimum than ALISTA (and variants thereof) in a synthetic data setup. 

This paper proposes an ultra-light variant of LISTA, called HyperLISTA, for solving sparse linear inverse problems. The authors’ adaptive parameterization reduces the training of HyperLISTA to only tuning three instance- and layer-invariant hyperparameters. HyperLISTA is theoretically proved and empirically observed to have super-linear convergence rates: the first time ever so in LISTA literature. It also leads to superior test-time adaptivity.