Hyperparameter Tuning is All You Need for LISTA
Authors: Xiaohan Chen
Jialin Liu
Zhangyang Wang
Wotao Yin
Venue: NeurIPS 2021 Poster (2021)
Keywords: LISTA
unrolling

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 (speciﬁcally, those with different sparsity levels and nonzero magnitudes). Code is available: https://github.com/VITA-Group/HyperLISTA.

Hyperparameter Tuning is All You Need for LISTA
Xiaohan Chen 1+
Jialin Liu
Zhangyang Wang'
Wotao Yin
University of Texas at Austin AAlibaba US, Damo Academy (xiachan. chen, atlaswang) Suteras. edu (jialin.ling wotao. wal.nnaaaaaaabiiinn..... com
Abstract
Learned Iterative Shrinkage-Thressolling Algorithm (LISTA) introduces the con- cept of unrolling an iterative algorithm and training it like a neural network. It has had great success on sparse recovery. this paper, we show that adding momentum to intermediate variables in the LISTA network achieves a better convergence rate and, particular, the network with instance-optimal parameters is superlinearly convergent. Moreover, our new theoretical results lead to practical approach of automatically and adaptively calculating the parameters of LISTA network layer based on its previous layers. Perhaps most surprisingly, such an adaptive adaptive-parammen parameter procedure reduces the training of LISTA to tuning only three hyperparameters from data: new record set in the context of the recent advances on trimming down LISTA complexity. We call this new ultra-light weight network HyperLJSTA. Com- pared to Mate-of-theearr LISTA models, HyperLISTA achieves almost the same performance on seen data distributions and performs better when tested on unscen distributions (specifically, those with different sparsity levels and nonzero magni- tudes). Code available: botps://github cww/ Group/HyperLISTA
Introduction
In this paper, study the sparse linear inverse problem, where strive recover an unknown sparse vector x' E R= from its noisy linear measurement b generated from
b = Axx +
where b E R" is the measurement that we observe, A E Rmxn is the dictionary, x E R the unknown ground truth that aim recover, and R is additive Gaussian white noise. For simplicity, each column of A, is normalized to have unit &2 norm. Typically, we have much fewer than columns in the dictionary A, i.e., m & Therefore, Equation (1) is under-determined system. The sparse inverse problem, also known as sparse coding, plays essential roles in wide range of applications including feature selection, signal reconstruction and pattern recognition.
Sparse linear inverse problems are well studied the literature of optimization. For example, be formulated into LASSO [29] and solved by many optimization algorithms p These solutions explicitly consider and incorporate the sparsity prior and usually exploit iterative routines. based based approaches
Deep-learning-
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 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 layers. However, classic methods come with data-agnostic convergence (rate) guarantees under suitable conditions,
35th Conference 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 [2 21 By converting each iteration of classic iterative algorithm into one layer of a neural network, one unroll and truncate classic optimization method into a feed-forward neural network, with 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. [5] pioneered the unrolling scheme for solving sparse coding and achieved great empirical success. By unrolling the Iterative Shrinkage-Threshodiing Thresholding Algorithm (ISTA), the authors empirically demonstrated up to two magnitudes of acceleration of the learned ISTA (LISTA) compared the original ISTA. The similar unrolling idea was later extended
to numerous optimization problems and algorithms [2 30 26
13
36
16 8 [].
1.1 Related Works
The balance between empirical performance and interpretability of unrolling motivates a line of theoretical efforts to explain their acceleration success. (33 attempted understand LISTA by re-factorizing the Gram matrix of the dictionary A in (T 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 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 77 extended the weight coupling necessary condition in 33 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.
1.2 Our Contributions
Our research question is along the line of 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 not improving them further.
We present an affirmative answer to the above question by learning Instance-optimal parameters with new ALISTA parameterization. First, 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 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 instance- and layer-invariant hyperparameters.
Our new ultra-light weight network is termed as HyperLISTA. Compared to ALISTA, the new param- eterization of HyperLISTA facilitates new backpropagation-fii "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 sate-of-thh-art LISTA variants in experiments, HSPA achieves the same strong performance on seen data distributions, and performs better when tested on unseen distributions (c.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.
Assumptions and Preliminaries
We represent a matrix as capital bold letter W, diag W) means the diagonal elements matrix W and the pseudoinverse of a matrix is denoted by W+, vector represented as lowercase bold letter and its entries are represented lowercase regular letters with lower indices a = 12 22. ... za] ]" Upper indices represent iterations or layers. Morcover, 0, represent vector with all zeros all ones, respectively. "supp(æ)) denotes the support, the indices of all nonzeros vector æ.
Mathematical Notations:
With an & penalty term, the minimizer of LASSO, argmin, Ax >/ provides an estimate the solution of the sparse recovery problem ( LASSO is Iterative Taankkagg-TTreeshdninggg Algorithm (ISTA):
ISTA Algorithm:
A popular algorithm to solve
x (k+1) TA/L (x)
+ 1 (z(b)x(())) k= 0,0,1,2,
where MAyL the element- wise coft-thresholdigg function 170 (a:) sign(x)) max(0, |æ| () with 0 X/L and is usually taken as the largest eigenvalue of A A.
LISTA Model: The original LISTA work
[5] parameterizes ISTA as
x (k+1) = ()ckk) W
(k) + 1) b).
0, 0,1,,,....
(2)
where θ = (
((0) are learnable parameters to train from data. In the training process, iterations formulated in unrolled and truncated K steps and the parameters trained by minimizing the following loss function defined over the distribution of training samples Drr:
minimize E(x Dir (( (G, (0()) x
Here x: (O, b, xx (0)),, the output of the LISTA model, is function with input O b and (0) In practice, we usually set (0) = O. We will use (KK) to refer to (O. b, ())) for brevity in the remainder this paper. x" denotes the underlying ground truth defined in ( Although cannot be
accessed in iterative algorithm (2), it can be used as the label in supervised training (
ALISTA Model: ALISTA [8] advances LISTA with lighter and more interpretable parameter-
ization, where the learnale parameters are θ (x) g(k) and the iterations formulated as
(k+1) ((*))
(A) W (b (x))
Tg(0))
x:
(4)
where W is calculated by solving the following optimization problem:
W E argmin
||WTA A
s.t. diag W A) =1
(5)
WeRmxn
The thresholding operator is improved with support selection. At layer k. certain percentage of entries with largest magnitudes are trusted as "true support" and will not be passed through
thresholding. Specifically, the i-th element m=(") (v) is defined as
14 > 006
i (D (V); i SD
(k)
> 0(k)
(w),
(1pte)) (w)); =
0
(1k) < < ((k)
(6)
Ui + ((h)
t. < g(b),
i S (v). e S (v),
2. < (b))
where (p(*) (v) includes the elements with the largest p magnitudes in vector v E R::
( (v) = { |1 i2 ... /pes |1ss1 2 |uta 2 ... 10 1....1u,cce) I... 2 |v
3

---

With p(A) = O, the operator reduces to the soft-thresholing and, with p(*) the operator reduces to the -orethhreshoding.. Thus, operator Toge (v) is actually a balance between soft- and hard-thresholding. When k is small, (()) is usually chosen as a small fraction of and the operator tends to not trust the signal, and vice versa. In ALISTA, p(*) is proportional to the index k, capped by a maximal value, i.e., p( = min(p k Pmax)) where p and Pmax are two hyperparameters that will be tuned manually. Later in this work, we will consider p(*) as parameter that could be adaptively calculated by the information from previous iterations (layers).
Throughout this paper, we refer to "parameters" as the learnable weights in the models, such as the thresholds ((k) and the step sizes 7(k) that are defined in the ALISTA model, which are usually trained by back-propagation. In contrast, we refer "hyperpa- rameters" as those constants that are often ad-hoc pre-defined to calculate parameters. For example, g(k) = c: (Ix)(((x(())))) (Ax(*) b)ll2. where ((a) is a parameter and 01 is a hyperparameter.
More Notations and Assumptions:
Assumption (Basic assumptions). The signal x² and noise are sampled from the following set:
X(B,B,,,o), A ((0 S a, ||0*| llo S s, 0 < B S 2 S B, Vi E supp(x")). (8)
In other words. x² is bounded and sparse. o > 0 the noise level.
Compared with the Assumption 2 in 77). the assumption of x; > B > 0" for non-zero elements in x' is slightly stronger. But we will justify (after Theorem this paper, our method also achieves better convergence rate than state-of-the-ards
I that uniformly under Assumption
[ in
3 Methodologies and Theories
In this section, we extend the ALISTA 4 in three aspects. First, we introduce better method to calculate matrix W in formula ( Second, we augment the x-update formula 4 by adding a momentum term. Finally, we propose an adaptive approach to obtain the parameters p(h), (000 ,
3.1 Preparation: Symmetric Jacobian of Gradients
Before improving the formula (5). we first briefly explain its main concepts and shortcomings. Mutual coherence is a key concept in compressive sensing IT] [O]. For matrix A, it is defined as since each column of A is assumed with unit & norm. A matrix with low mutual coherence satisfies that A " 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 Alr (described in ()) By minimizing this bound, they obtained a good matrix W that can be plugged into the LISTA framework.
maxişj (AATA) A),,5l where (ATA)), A).,
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 supervised way (3). This is partially due to the fact that the update direction W (Ax - b) in
ALISTA is not aligned with the gradient of the E2 term in the LASSO objective: V A bll2
Ar
AT ( (An b). This limitation motivates us to adopt a new symmetric Jacobian parameterization so that WTA A is symmetric and the coherence between A and W is minimized.
Inspired by MЛ. we define W (GTG) A (the matrix G m is named as the Gram matrix), and get the following problem instead of (5)
min G
A GA- I|E
s.t. diag(A GA G
(9)
However, the constraint in the above problem 9 is hard to handle. Thus, we introduce an extra matrix D = GA E Rmxx and use the following method instead to calculate dictionary:
min
D I G.D
D GA D
s.t. diag D D) 1.
(10)
With proper a >> O, the solution of (1O) approximates 9 well. We use an adaptive rule to choose and adopt variant of the algorithm (described in details in the supplement) proposed in [19 to solve (10). Such formula leads to a symmetric matrix WT A (GA) With this symmetry,
the vector W'Axx b) is actually the gradient of function G| b)ll with respect to

---

Layer
Layer
Layer
K
Pyia
gal
100
Figure 1: ALISTA with momentum formulated in 12) with (
(0) W A, (d)
(1+3(0)
(00 W A (k 2 1). The momentum creates extra skip connections the bottom.
using methods [2] with the following loss function without knowing the ground truth: F(x)) G( b)ll + x||1 On the other hand, it usually holds that
One may train model 4
W A || = (GA)"(GA) I|r.
(11)
where W calculated by 5 and is calculated by (T0). We validate
by numerical results in Section 4.1 Conclusion T1 demonstrates that the mutual coherence between A and (G" A
11
is similar to that between and W obtained by (5). Although we limit the matrix W to be
symmetric, 100 hardly degrades any performance of the ALISTA framework compared to
3.2 ALISTA with Momentum: Improved Linear Convergence Rate
As is well known 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 's algorithm can be written as iterative algorithm within the space of gradient updates by simply adding a momentum term. To avoid extra training overhead. we use Polyak's 's heavy ball scheme and add momentum term to the ALISTA formula for k > (illustrated in Figure I
(k+1) -igee (b) + ( (b (x) + (xx) x0(--1))
(12)
Note that there are other LISTA variants that incorporated additional momentum forms 23
32
they did not contribute to provably accelerated convergence rate. Defining constant lu as the mutual coherence of D, i... μ max4, I(D.,)" d. we have the following theorem, which demonstrates that, in the context of (A)LISTA, model (2) can provide a faster linear convergence
rate, than that of ALISTA in the same settings.
Theorem (Convergence
and (k) J be generated by (1).. If Assumption holds and < (1 + 1/p)/2 and a is small enough, then there exists uniform sequence of parameter {0tk), ,p(k), (1)),g()) j for all (x* E (B, B, such that
(ASSTA-Mmmentmm,, Let (0)
s)
2sCw
(x)(k) - x
Co II
(1)
J, Vk 1,2,
(13)
I- 2ps +
t=0
where Co > 0 a constant depending on s, B. and Cw maxigijsn s The convergence rate (k) satisfies:
(k)) < 2us- 1, Vk:
(14)
log( B) log(2Co)
(k) < v 2118 + p < 2js n4 Vk >
(15)
log 11)
and the parameter sequence satisfies
((k) =11 sup
(1a0( xx -x*ll++Cwo ((k) =1,
Vk
(20 ( 8,0))
(16)
g(k) + I 1 24s 11)
(A) + n.
as k + oc
2 As k O, we keep the ALISTA formula since x (-1) is not defined.
5

---

Despite remaining linearly convergent, our model has an initial rate of 2js that is no worse than the rates of-ee-of-the-arts [ [8] D and an eventual rate vI 2μs I that is strictly 1- 24s + f as 2us < 1. For example, better than the rate in 7 because 2js / v1 2|us + Rs 0.684. Moreover, the eventual error 2 μr 0.9, then our new rate is
2sCwa/ (1 2,s + μ1) is no worse than that in 7 Proof details can be found in the supplement.
3.3 Instance-Adaptive Parameters: From Linear to Superlinear Convergence
In ALISTA (18), the authors show that linear convergence is lower bound. This means that one cannot expect superlinear rate if a uniform set of optimal parameters are learned for dataset.
State-of-the-an theoretical results show that LISTA converges with linear rate 7 18
One promise to enhance the rate in Theorem | is to further introduce instance adaptivity. We establish
that, if {0(k), pp(), , j can be searched for an instance, such instance-optimal parameters lead to superlinear convergence.
Theorem 2. Let (0)) 0 and {a be generated by 12 If Assumption holds and 8 < (1 1/ 122 and a is small enough, then there exists a sequence of parameters {0(k) plk), (00), 3(k)) kk=1 for each instance (x*,E) E XBB, B, s, σ) so that we have:
2sCw
(k -10122 VsB II
d0 1
0, Ak 1,2,
(17)
2ps +
t=0
where Cw is defined in Theorem 1 and the convergence rate x! satisfies
g(k) + 0 as k + co. 00.
(18)
To achieve this super-linear convergence rate, parameters are chosen as follows:
g(k) = (1) (ul| x=111 + Cwo). Ak
(19)
and (K) follows 16 for all k. The other two parameters ((8 g(8) follow 16 at the initial stage (with small k) and they are instance-adaption as l large enough. Consequently. the model (12)
reduces the conjugate gradient (CG) iteration on the following linear system k large enough:
W (Asæs 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.
3.4 HyperLISTA: Reducing ALISTA to Tuning Three Hyperparameters
Adaptive Parameters Based on Theorem 2 we design the following instance-adaptive parameter formula as the recovery signal (k) is not accurate enough (equivalently, as k is small):
(k) 1,
(21)
σ(k) (1 || A+ -b)))
b)ll;
(22)
g(k) c2f (*)
(23)
||At b/1
(k) ca min
log
|A+(Ax((* b)]1 ).
(24)
where > 0, > 0, > 0 are parem--assmeters to tune.
The step size formula 21 stems from the conclusion [6) Theorem 2 suggests. The threshold
g(k) in (19 cannot be directly used due to its dependency the ground truth xt. In 22 we use ||A (Ax - b)ll to estimate (19) because
| + *Aa b)]l,
A A(x(1) -x") A A (1la x011) + (
Similar thresholding schemes studied in 37

---

Sorted |
(e(k)
Possible Area of [ (K)
Trust Region p!k)
Figure 2: Choice of support selection
The momentum rule (33 obtained via equation 16 The momentum factor ((() is asymptotically
equal to (1 - vT- 2ps pi)² which is a monotonic increasing function w.r.t. s, the number of nonzeros in the ground truth sparse vector x². Therefore, lo norm of x<() is natural choice to approximate g(k), considering that (*)) will gradually converge to x" and hence (|xx()) to |o=
The support selection rule (4 be explained as follows. First sort the magnitude of [a=]] in
Figure At the k-th layer, given e(R)
=0oloo each element in (k) can be bounded as xx) xx
p (k)
(A) |
S |
+ e(k)
Vi.
Such area is shown as the gray area in Figure 2 As we discussed in Section following definition (6), the support selection is scheme to select those elements that can be trusted true support. The "trust region" in [igurr@iilustratte such entries. Intuitively, the trust region should be larger as the error ((k) gets smaller. We propose to use the logarithmic function of the error to estimate ((k)
|1==|l<< ) = log |IA b)ll1 c(k)
||Abbll
c3 log
(25)
The hyperparameter c3 < 1 is to tune based the distribution of x". With upperbound
(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 which means that the operator p/th) is getting close to a hard-thresholding operator. The support selection scheme proposed in LISTA-CPSS 7 also follows such principle but requires more prior knowledge. Compared to that, formula 24 is much more automatic and self-adaptive.
the supplement.) As k oc, it holds that (*k) - 0 and (
Switching to Conjugate Gradients Theorem suggests that may call conjugate gradient (CG) to obtain faster convergence as the recovery signal (k) is accurate enough. In practice, choose to
switch to CG as k is large enough such that (*) 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 (k) since we
assume z (R) is accurate enough when we call CG. Finally, HyperLISTA is described Algorithm
3.5 Peperparameter-TTninee Options for HyperLISTA
HyperLISTA has reduced the complexity of the learnable parameters to nearly the extreme: only three. While backpropagation remains to be viable option solve them, it becomes an over-kill to solve just three variables by passing gradients through tens of neural network layers. Besides, the hyperparameter e3 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 HSPerL.STA has certain robustness to perturbing the found values of C1, <2. C3. which also encourages to go with less precise yet much cheaper search methods.

---

Algorithm 1: HyperLISTA with tuned c1, 02,
Input: Observation b, dictionary A, hyperparameters c c2 Cg-
Initialize: Let (x(0) O.
Calculate D and G with 10 set W= = (G"GG)
2 Calculate with = maxiij 1(D D)..l
for j = 0, 1,2,... until convergence do Conduct iteration (12) with parameters defined in 24
if (+)) is large enough then
break end end
Set = su)p(x:()), call the conjugate gradient algorithm to solve linear system (0 Output: 2, the result of the conjugate gradient.
In this work, we try replacing the backpropagation--assd training with the vanilla grid search for learning HyperLISTA. Besides the ultra-light parameterization, another enabling factor is the low evaluation cost on fitness hyperparameters: just running inference on one minibatch of training samples with them, and no gradient-based training needed. From another aspect, HyperLISTAA 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 wants to afford the cost of re- re-searching hyperparameters each dataset, whose cost is still much lower than training using back propagation.
Specifically, we we first use 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.
Numerical experiments
Experiment settings We use synthesized datasets of 51,200 samples for training, 2,048 validation and 2,048 testing. We follow previous works [8] to 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 have unit & column norms. The sparse vectors are sampled from N NN00, o²)- Bern(p), where N(u, o²) represents the normal distribution and Bern(p) the Bernoulli distribution with probability p to take value By default, we choose
and p 0.1, meaning that around 10% of the elements are non-zero whose magnitudes further follows standard Gaussian distribution. The additive noise: in I follows Gaussian distribution N(0, o²). The noise level is measured by sggnal-tonoisee ratio (SNR) in decibel unit. Note that we can change the values of ar, 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 [8 31), unless otherwise specified. Besides synthesized data, we also evaluate HyperLISTA on compressive sensing task using natural images. The results are presented Appendix B due to limited space.
Comparison Methods: In this section, we compare with the original LISTA [5] formulated in ALISTA formulated in (4) and its variant with momentum acceleration denoted as ALISTA-MA A suffix -Symm will be added if model adopts the symmetric parameterization introduced in Section 3.1 We use HyperL/STA(
to represent our proposed method which we optimize all three hyperparameters C1, 02, C3 in (22) (24) using grid search. In contrast, we can use back-
propagation to train e₁ and 02 and leave (()) manually selected as in ALISTA because the loss
function is not differentiable with respect to (*). The resulting model is denoted as HyperLISTA-BI
The
Other baselines include Ada-LISTA and NA-ALISTA (4.
4.1 Validation of symmetric matrix parameterization and Theorem
We first validate the efficacy of the symmetric matrix parameterization and Theorem 1, showing the acceleration brought by the momentum term. For this validation, compare four models: ALISTA,

---

0
NMSE (dB)
-20
NMSE (dB)
-40
ALISTA
ALISTA-MM-Symm
ALISTA-Symin
-00
HyperLISTA-BP
-60
ALISTA-MM
HyperUSSTA-GS
ALISTA-MM-Symm
80
HyperLUSTA-Full
10
15
5
10
15
Layer
Layer
Figure Effect of symmetric matrix parame- terization and momentum. Momentum provides acceleration for either parameterization.
Figure 4: Back-propagation and grid search based training, compared with HyperLISTA-Full with C1, C22 C3 searched.
-20
NMSE (dB)
NMSE (dB)
-40
ALISTA
ALISTA
-60
ALISTA-MM.Symm
-0
MMM
Ada LFISTA
Ada: LFISTA
MyperLISTA
-30
HyperLISTA
10
15
5
10
15
Layer
(a) Noiseless, No train/test mismatch.
(b) Sparsity ratio p changed to 0.155
ALISTA
ALISTA- MSTTAA-M--SSMI
-20
NMSE (dB)
NMSE (dB)
-10
NA-ALISTA
-40
HyporLiSTA
ALISTA
AL MYYTA-MA-Symm
-0
-60
NA-AUISTA
80
-30
10
Layer
Layer
(c) Variance a non-zero elements changed to 2.
(d) Noise level changed to SNR=30dB.
Figure 5: Adaptivity experiments. All models are trained in the noiseless case with p 0.1, 1.0, shown in subfigure (a). We directly apply the models trained in (a) to three different settings, which changes 0.15, and SNR of the noises to 30 respectively, shown in subfigures (b), (c), (d).
ALISTA-SYmm, ALISTA-MM and ALISTA-MM-Syme We train them the dataset and compare their performance measured by NMSE on the testing set. Here, the support selection ratios selected by following the recommendation in the official implementation of (18). Results are shown in Figure 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.
4.2 Validation of instance-optimal parameter selection and grid search
In this subsection, we show that the adaptive parameterization in Eqns 22 (24). i.e., HyperLISTA,
can perform well or even better than the uniform parameterization 12]. ). and we also show the efficacy of the grid search method. We optimize HyperLISTA--ull using grid search and train HyperLISTA-BP with backpropagation-be
method (SGD), respectively. For a fair comparison with HyperL.ISTT -SP we introduce variant of SirperLISTA--R in which we only grid-search ci
'Here ALISTA achieves worse NMSE than that in here instead of unlimited training set in [88
18 We attribute this to the finite-size training set that

---

NMSE (dB)
-50
ALiSTA-Extra NA-ALISTA
-100
HyperLiSTA
10
20 Layer
30
40
Figure 6: Direct unrolling to 40 layers (all models are trained with 16 layers).
We denote this variant as HyperL/S7AAGGs Figure show that grid search can find even better solutions than backpropagation and the uniform parameterization. When we further use grid search for searching Ci, C22 C3 simultancously (HyperLiSTA-Full), there is more performance boost.
and in (22 and 23 and use the same (*)) as manually selected in HyperL.ISTA
4.3
Comparison of adaptivity with previous work
We conduct experiments when there exists mismatch between the training and testing. We instantiate training/testing mismatch terms of different sparsity levels the sparse vectors x², different distributions of non-zero elements in x², and different additive noise levels. We compare HyperLISTA with ALISTA [8] and its variant ALISTA-MIS MMM--mmmM Ada-LFISTA M 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. 5ch. Note our computational overhead is also much lower than using LSTM.
Directly unrolling HyperLISTA to more layers Another hidden gem in HyperLISTA is that learns indeeeennn 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 any number of layers, it has worse performance and adaptivity compared to HyperLISTA, as we compare in Figure o
We also compare HyperLISTA with another baseline of 40-layer ALISTA (named which is directly extrapolated from a 16-layer ALISTA model by reusing the last layer parameters. We clearly observe that ALISTA cannot directly scale with more layers unrolled.
5 Conclusions and Discussions of Broad Impact
In this paper, we propose a ultra-light weight unrolling network, HyperLISTA, for solving sparse linear inverse problems. We first introduce new ALISTA parameterization and augment it with momentum, and then propose an adaptive parameterization which reduces the training of HyperL only tuning three instance- and layer-invariant hyperparameters. HyperL LSSer is theoretically proved and also empirically observed to have super-linear convergence rate as it uses instance-optimal parameters. Compared previous work, HyperLISTA achieves faster convergence on the seen distribution (i.c., the training data distribution) and shows better adaptivity on unseen distributions.
As limitation, we do not consider perturbations in dictionaries in this work yet. We also find that HyperLISTA, as a compact model similar to ALISTA [8]. may fail to perform well on signals with complicated structures such real images, where the underlying sparse linear model (I) 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.
10

---

References
[1] Aviad Aberdam, Alona Golts, and Michael Elad. Ada-lista: Learned solvers adaptive varying models. arXiv preprint arXiv:2001.0444 08446, 2020.
[2] Pierre Ablin, Thomas Moreau, Mathurin Massias, and Alexandre Gramfort. Learning step sizes for unfolded sparse coding. In Advances in Neural Information Processing Systems, pages 13100- 13100-131100 13110, 2019.
[3] Amir Beck and Mare Teboulle. A fast iterative shrinkagg-thrrshooldnn algorithm for lincar inverse problems. SIAM journal on imaging sciences, 2(1))183-202, 2009.
[4] Freya Behrens, Jonathan Sauder, and Peter Jung. Neurally augmented ALISTA. In International Conference Learning Representations, 2021.
HanQin Cai, Jialin Liu, and Wotao Yin. Learned robust pea: A scalable deep unfolding approach for high-dimensional outlier detection. arXiv preprint arXiv:2 arXiv:21 2021.
[6] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang. and Wotao Yin. Learning to optimize: A primer and benchmark. arXiv preprint arXiv:2 12828, 2021.
[7] Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of unfolded ISTA and its practical weights and thresholds. In Advances in Neural Information Processing Systems. pages 9079-9089, 2018
2018.
[8] Benjamin Cowen, Apoorva Nandini Saridena, and Anna Choromanska. Lsalsa: accelerated souree separation via learned sparse coding. Machine Learning, 108(8-9):1307 9):1307--3277 2019.
[9] Ingrid Daubechies. Michel Defrise, and Christine De Mol. An iterative thresholding algorithm linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 57(11):1413-1
2004.
[10] David L Donoho, Michael Elad, and Vladimir N Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions information theory, 52(1):6-18, 2005.
[11] David L Donoho, Xiaoming Huo, et al. Uncertainty principles and ideal atomic decomposition. IEEE transactions information theory, 47(7):2845-2862, 2001.
[12] Matthias Feurer and Frank Hutter. Hyperparameter optimization. In Automated Machine Learning, pages
3-33. Springer, Cham, 2019.
[13] Raja Giryes, Yonina Eldar, Alex M. Bronstein, Guillermo Sapiro. Tradeoffss between conver- gence speed and reconstruction accuracy in inverse problems. IEEE Trunsactions on Signal Processing. 66(7):1676-1690 Apr 2018.
[14] Gene H Golub and Charles F Van Loan. Matrix computations, volume 3. JHU press, 2013.
[15] Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th international conference international conference on machine learning, pages 399-406, 2010.
[16] Satoshi Hara, Weichih Chen, Takashi Washio, Tetsuichi Wazawa, and Takeharu Nagai. Spod-net: Fast recovery microscopic images using learned ista. In Asian Conference on Machine Learning, page 694-709, Oct 2019.
[17] Kuldeep Kulkarni, Suhas Lohit, Pavan Turaga, Ronan Kerviche, and Amit Ashok. Reconnet: Non-iterative reconstruction of images from compressivoly sensed mcasurements. In Proceedings the IEEE Conference Computer Vision and Puttern Recognition, pages 449-458, 2016.
[18] Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Alista: Analytic weights are as good as learned weights in lista. In International Conference on Learning Representations (ICLR), 2019.
[19] Canyi Lu, Huan Li, and Zhouchen Lin. Optimized projections for compressed sensing via direct mutual coherence minimization. Signal Prucessing, 151:45-55, 2018
[20] David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, volume 2, pages 416 423. IEEE, 2001.
11

---

[21] Tianjian Meng, Xiaohan Chen, Yifan Jiang, and Zhangyang Wang. A design space study for lista and beyond. In International Conference Learning Representations. 2021.
[22] Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing, arXiv preprint arXiv:1912.10557, 2019.
[23] Thomas Moreau and Joan Bruna. Understanding trainable sparse coding with matrix factorization. In International Conference on Learning Representations, 2017.
[24] Yurii E. Nesterov. A method for solving the convex programming problem with convergence rate (1/k" 2). In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[25] Gregory Ongie, Ajil Jalal, Christopher A Metzler, Richard G Baraniuk, Alexandros G Dimakis, and Rebecca Willett. Deep learning techniques for inverse problems in imaging. IEEE Journal on Selected Areas in Information Theory. 1(1):39 56, 2020.
[26] Dimitris Perdios, Adrien Besson, Philippe Rossinelli, and Jean-Philippe Thiran. Learning the weight matrix for sparsity averaging in compressive imaging. In 2017 IEEE International Conference on Image Processing (ICIP), pages 3056-3060. IEEE, 2017.
[27] Boris Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
[28] Pablo Sprechmann, Roce Litman, Tal Ben Yakar, Alexander M Bronstein, and Guillermo Sapiro. Supervised sparse analysis and synthesis operators. Advances in Neural Information Processing Systems, 26:908-916 -966, 2013.
[29] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methadological), 58( 1):267-288, 1996.
[30] Zhangyang Wang, Qing Ling, and Thomas Huang. Learning deep to encoders. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 30, 2016.
[31] Kailun Wu, Yiwen Guo, Ziang Li, and Changshui Zhang, Sparse coding with gated learned ista. In International Conference on Learning Representations, 2020.
[32] Jinxi Xiang, Yonggui Dong, and Yunjic Yang. Fista-net: network for inverse problems in imaging. IEEE Transuctions on Medicul Imaging, 1005):1329-111 1339, 2021.
Learning fast itcrative shrinkage thresholding
[33] Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal sparsity with deep networks? Advances in Neural Information Processing Systems, 29:4340-4348, 2016.
[34] Yangyang Xu and Wotao Yin. A fast patch-dictionary method for whole image recovery. Inverse Problems and Imaging, 10(2):663-583, 2016.
[35] Chengzhu Yang, Yuantao Gu, Badong Chen, Honghing Ma, and Hing Cheung So. Learning proximal operator methods for nonconvex sparse recovery with theoretical guarantce. IEFE Transactions on Signal Processing, (8:5244-5259, 2020.
[36] Joey Tianyi Zhou, Kai Di, Jiawei Du, Xi Peng, Hao Yang, Sinno Jialin Pan, Ivor W Tsang, Yong Liu, Zheng Qin, and Rick Siow Mong Goh. Sc2net: Sparse Istms for sparse coding. In AAAI, pages 4588-4595, 2018.
[37] Li Ziang, Wu Kailun, Yiwen Guo, and Changshui Zhang. Learned ista with error-based thresholding for adaptive sparse coding, 2021.
12


Reviews:
[{"review_id": "oXIomp2i11q", "reviewer": "Reviewer_WJ5N", "summary": "The paper is based on a branch of works named LISTA(Learned Iterative Shrinkage-Thresholding Algorithm), reducing hyperparameters to 3, while maintaining almost the same performance on seen data distributions. Theoritical explainations and experiments are also carried out.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. As is stated in line 9-10, the work of this paper trims down LISTA complexity to 3 hyperparameters. Considering the performance showed in figure 6 by experiments, the performance under certain circumstance is good, HyperLISTA outperforms NA-ALISTA. So the trimming-down can be a contribution.\nBut does the improvement come with drawbacks? This is not fully discussed in the paper. There is one major problem. Will the flexibility be influenced when reduce the number of hyperparameters to 3? If the flexibility will be influenced, what impact will it produce?\n\n2. Typos. \nIn line 317 \"more are more adaptive\". \n\nPlus, should the y-axis label \"NMES\" be \"NMSE\" in the figures?\n\n3. In line 258 \"We use synthesized datasets of 51,200 samples for training, 2,048 validation and 2,048 testing\". As the paper claims that the work improves and extends the branch of works LISTA as is stated in line 9-10. To show that the proposed HyperLISTA is as widely applicable as former algorithms, more experiments on real-world datasets are suggested.\n\n4. Extends question 1, it is suggested to introduce the real-world applications of LISTA, and how will the proposed HyperLISTA help in those applications.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not discussed limitations of their work. By reducing the hyperparameters to 3, there might be some drawbacks comparing to original LISTA works. It is recommended to discuss if there are any drawbacks\\limitations or not, and why.\nIt is not likely for the work to have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}, {"review_id": "JFW0qloPojZ", "reviewer": "Reviewer_NZWV", "summary": "This paper proposed a modification to the ALISTA algorithm which offers a better convergence rate. ", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is out of my field and I would struggle to make informed comments about its substance. However I can state with confidence that this paper does not meet NeurIPS standards when it comes to presentation, clarity, phrasing and lack of typos. This is a non-exhaustive list of some of what I mean: \n\n- You have an entire sentence duplicated (l43-44 vs l55-56). This confusion probably arose because the entire second half of your introduction should go into \"related work\". \n- In line 57 you refer to the dictionary as D but it is introduced as A in equation 1, are you speaking of the same thing..?\n- In the introduction you define \"model-free\" methods as \"Deep learning base black-box models\" which is confusing because that's not model-free by definition. \n- trains -> training in first line of the abstract\n- typo l39 \"for\" x2\n- since it is a key concept, you should explain what unrolling means in the context of LISTA in the introduction.\n- this sentence needs rephrasing: \"Although such transformation is difficult to optimize, the authors argued that the data63 driven training process practically learned that, and hence the acceleration effect\"\n- typo \"the\" x2 in l85\n- this sentence is confusing and needs rephrasing: \"Throughout this paper, we refer “parameters” as learnable weights, thresholds theta(k), step sizes gamma(k) that are directed defined in LISTA models\". What is \"directed defined\"? Is it another typo?\n- typo in conclusion \"trained more efficiently and at the same time more are more adaptive\"\n\n\nI would recommend proof reading your submission carefully to correct grammar/typos before resubmitting. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7YyeQf3lKoG", "reviewer": "Reviewer_vByu", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors reduce the unfolded neural network implementation of ALISTA such that their algorithm finally reduces to having only 3 hyperparameters, that can be found by e.g. a grid search. The experiments on synthetic data show promising results. The main improvement point is the clarity of the explanation of the method itself. \n\n**Originality**\n\nThe work is novel and cleverly combines aspects from different previous works, to find a more lightweight ALISTA algorithm.\n\n**Quality**\n\nL33: Reference [6] is not peer reviewed. More established (and peer-reviewed) papers are available that discuss the trade-off between model-based vs model-free methods. \n\nL142: Does the convergence proof also hold for bounded noise, as assumed in the proof of ref 7? Otherwise it is unfair to compare convergence rates. Also in your experiments you do add noise.\n\nFrom eq. 13 I understand that x^k+1 is updated more when the difference between x^k and x^k-1 is larger. I would expect opposite behavior, as you also suggest in l171: in low curvatures (so where the difference between  x^k and x^k-1 is small) you want a fast update.\n\nL214: Why is it a logical choice in your opinion to use the L0 norm of x^k as a proxy for weighing the momentum factor?\n\nL179: What proofs the claim you already make in this line?\n\nWhy did you choose 16 layers, since the errors clearly did not converge at 16, ALISTA-MM seems to become better than ALISTA-MM-Symm for more number of layers.\n\nAs you mentioned; you don’t need backpropagation anymore, but only have to find 3 hyperparameters. So why wouldn’t you do the grid search for these C1-C3 directly on new unseen (test data), rather than on training data? In that way you’d present you algorithm as just an iterative algorithm rather than an unfolded network, which includes a grid search on three settings (similar as many algorithms, e.g. ISTA, where you also need to find hyperparameters like thresholds and step sizes).\n\n**Clarity**\n\nOne of the mentioned contributions is to add momentum to improve the convergence rate (also mentioned in L94). Can you be more specific already in the abstract on what entity you apply momentum? \n\nL19: “each column of A, is normalized” -->  normalized to sum to 1?\nAnd can you indicate here why this does help in simplicity, because it comes a bit out of the blue here.\n\nL43-53: This paragraph partly contains information that is later again presented in the related work section. Also, lines 43 and 55 are exactly the same. The related work section seems a more detailed version of the mentioned paragraph, but written in a difference style (as if it was written by another author). \n\nIn L57 and L69, the authors speak about dictionary D, but in equation 1 the dictionary was called A. \n\nL91: “First, we start with a new symmetric parameterization for the weight matrix in ALISTA so that ALISTA also converges to LASSO function minimizers, that lays the foundation of momentum-based analysis.”\nThis sentence contains a lot of information that has not been presented before. The reader is not aware yet about the non-symmetric parameterization of the weight matrix in ALISTA, nor about any momentum-based analyses.  \n\nL91-98: In the abstract three main contributions are mentioned, while in lines 91-98 four contributions are mentioned. The first of these four however comes out of the blue.\n\n*Section 2*\n\nTo improve readability and structure of this section, it would be wise to add subsection headers named 'Setup and Notations', 'ISTA', 'LISTA', 'ALISTA', 'Assumption 1'. It is nice for completeness that your also provide the background on ISTA, but having it separated with subsections makes it easier for the reader when you want to search back the ALISTA notation later on during reading the paper.\n\nL137: “In ALISTA, p(k) is regarded as a hyperparameter to be manually tuned by cross validation or so.” --> Is it typically tuned separately per index k in ALISTA, so generating K hyperparameters, or is it typically set to the same value for all layers?\n\nL140: From eq. 8 I understand that the elements in x* are strictly larger than 0, since 0 < B_ < x*_i. But the definition of sparse elements is that they are exactly zero right?\n\n*Section 3*\n\nL146: Please add a short introduction about the section. Mention that you will extend the ALISTA framework (as provided in a separate subsection in related work, so that the reader can easily refer back to those formulas), and which aspects you will improve upon. Because now I suddenly jump into the title Symmetric Jacobian of Gradients which seems out of the blue, when coming from the related work section, and L148 only implicitly says that you will continue upon formula 5.\n\n*Section 3.1*\n\nI have most problems understanding section 3.1. Here are some tips/questions that might improve its clarity:\n\nL 148: It was not explained why good weights should have low coherence with matrix A, and why W^TA should be symmetric, which is in fact the key take away of this section.\n\nL 148: It is unclear to me how the two problems formulated in l148 (i.e. non-symmetry and no gradient of a (which?) function)  hamper convergence to F(x).\n\nL151: Here you mention that ALISTA can only be solved using the ground truth, while from equation 5 I understood something different. Why can’t you use eq. 5 directly, instead of resorting to the method by ref. 1 using gram matrices?\n\nL161: What do you mean by “it usually holds in practice”. This method using the Gram matrix is proposed by yourself, so which practice are you referring to? The current paper or earlier work?\n\nL163: “Such conclusion demonstrates that procedures (10) and (5) lead to similar mutual coherence and, consequently, one can also pursue x(k) -> x* with the new dictionary GA, with almost no performance loss.”\n--> Which conclusion do you refer to, mutual coherence of what are you referring to,  and which performance?\n\nL164: If indeed it doesn’t matter much whether we use the symmetric or non-symmetric dictionary, why would we then do all the effort at all to find this symmetric dictionary D?\n\n*Section 3.2*\n\nL167: “… the above new symmetric parameterization make us be able to unify the proof schemes in ALISTA and Polyak’s heavy ball momentum, which was not feasible previously.”  --> The Polyak’s heavy ball momentum was not introduced before, and the sentence seems grammatically incorrect as well.\n\nL213: You write that you estimate ||x^k -x*||, but in eq. 17 this term is different: ||x^k(x*)-x*||. \n\n\nL238: “In practice, we choose the switching condition as p(k) large enough.” --> I don’t understand what you mean by choosing p(k), as p(k) is adaptively computed, rather than chosen. So how can you guarantee that it is ‘large enough’.\n\nFrom section 3.5 I understand that HyperLISTA in the end is not trained with backpropagation, so why would you then still implement it as an unfolded neural network and not just as an iterative algorithm? Is it still accelerated as an unfolded NN compared to using it as an iterative algorithm maybe?\n\nA textual reference to figure 1 is missing, and a more informative stand-alone caption could be useful.\n\n*Algorithmic description*\n\nAfter having read the different formulas, it is a pleasure to see a summarizing algorithmic description. However, the description is not stand-alone (enough). A reader that does not want to be bothered with the proofs is not able to follow it like a recipe.\nLooking at the equations needed in the algorithm, it seems that next to **b**, also **A** must be given. Moreover, given **A**, the user should solve eq. 10 to find D, in order to be able to compute mu, as used in eq. 21 and eq. 23. This information is missing from the description.\n\n*Section 4*\n\nFig. 3: Introduce the meaning of the abbreviations in the legend in section 4.1.\n\nFig. 4: What is the difference in implementation between HyperLISTA-GS and HyperLISTA-Full, this is not clear from paragraph 4.2.\nWhy is comparison to NA-ALISTA only added in section 4.3, but not in 4.1 and 4.2?\n\n \n**Significance**\nReducing the number of hyperparameters in existing algorithms is an interesting direction, and of use to the community.\n\n**Minor points**\n\nL39: double ‘for’ in the sentence.\n\nL115: represent instead of represents\n\nL121: You mention eta_theta while in the formula you use eta_lambda/L.\n\nL 126: Please mention that x^* is the optimal solution (i.e. the ground truth). It’s now implicit from eq. 1, but I was initially confused, since x^* was used in eq.1, but not in eq.2, and again in eq. 3.\n\nL133: It looks like your forgot bold notation of the last v in this line.\n\nL142: In this line your write B_ < x*_i, while in eq. 8 your use a smaller-equal sign for that inequality.\n\nL153: The set of reals is here indicated with a different R than used in the preceding text.\n\nL157: adopt --> adopt\n\nL159: The gradient with respect to which variable?\n\nL186: How should I interpret this notation: x^k(x*). Is it a dot product or a function operator maybe?\n\nL229: The notation in the denominator of the second term seems faulty.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not address limitations of their work. A discussion on improvements points/future research could be added in section 5.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "4cjqCiIpzC3", "reviewer": "Reviewer_fXkT", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper adds a distinguished breakthrough to the LISTA literature, and I can see the work to become very influential in this booming community. \n\nThe theory part made substantial extensions from [14,5]. The seminal ALISTA [14] constructed the “optimal\" model weights for achieving lower-bound linear rate, but that construction was not practically achievable due to requiring ground-truth sparse codes. The recent LSTM-based approach in [5] was theoretically motivated by revisiting the recovery guarantees of ALISTA and may achieve tighter error bounds. All previous results sit with linear rates for ALISTA.\n\nThis paper for the first time demonstrates ALISTA achieves a better convergence rate, and in particular is superlinearly convergent, with instance-optimal parameters. Although [5] had similar observations, this paper shows such instance-optimal parameters can be constructed in a way to have ALISTA achieve superlinear convergence, which is a significant step forward. Besides, Section 3.2 was also the first to unify the proof schemes in ALISTA and the momentum acceleration (Polyak’s heavy ball), which was not feasible previously.\n\nThe new theoretical results of Theorems 1 and 2 lead to a practical approach of automatically and adaptively calculating the parameters in a layer-progressive way. By that, HyperLISTA has reduced the complexity of learnable parameters to nearly the extreme: only three hyperparameters. That enables more efficient solving via cheaper gradient-free methods in HPO. For example, the authors showed even a grid search can do well, unlike previous LSTM black boxes.  \n\nExperiments find this compact adaptive paramterization can be self-adaptive to different sparsity levels, non-zero element magnitudes, additive noise levels, and even unrolled layer numbers. Overall, HyperLISTA achieves faster convergence on the seen distribution (i.e., the training data distribution), and shows better adaptivity on unseen distributions, while being ultra-lightweight.\n\nReading this paper has also been a joy. The writing is very good and easy to follow. Section 3 is well organized into a thoughtful and logical progression.\n\nOverall I’m very positive about this work. The following suggestions are for the authors’ reference: \n-\tThe re-parameterization of W in Section 3.1 was inspired by a very relevant prior work [1]. However, the authors never compared with [1] in their experiments (only NA-LISTA was compared). This one should be either explained or added.\n-\tConsider reporting ALISTA and other baselines too, in Figure 6’s unrolling iteration plot. Naïve options to extrapolate may include copying and re-using last-iteration hyperparameters or using some ad-hoc decay schedule. I guess that won’t hurt your main conclusion, just suggested for completeness.\n-\t[Nitpick] All experiments are on synthetic data. Following the standard of most LISTA papers nowadays, the authors shall consider reporting on natural image experiments too.\n-\t[Nitpick] Figure 5 shows a few test-time adaptivity settings. More settings may be considered, such as changing the non-zero element distribution family (currently, still Gaussian but altering std), or dictionary mismatch (like in robust ALISTA).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Theoretical work. No concern here.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethic concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hourse"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work makes significant contributions to research into algorithm unrolling, by building upon the LISTA and ALISTA works. After providing a new ALISTA parameterization, and introducing a momentum term the authors both significantly reduce the complexity of tuning relative to prior work, and achieve significant performance gains. Most reviewer criticism centered on quality of writing, which was addressed in the rebuttal. Regarding the technical merit of the work, some reviewers offered extremely high praise arguing strongly for acceptance. 
Decision: Accept (Poster)