Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.
But 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?

2. Typos. 
In line 317 "more are more adaptive". 

Plus, should the y-axis label "NMES" be "NMSE" in the figures?

3. 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.

4. Extends question 1, it is suggested to introduce the real-world applications of LISTA, and how will the proposed HyperLISTA help in those applications.
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.
It is not likely for the work to have any potential negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposed a modification to the ALISTA algorithm which offers a better convergence rate. 
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: 

- 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". 
- 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..?
- 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. 
- trains -> training in first line of the abstract
- typo l39 "for" x2
- since it is a key concept, you should explain what unrolling means in the context of LISTA in the introduction.
- 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"
- typo "the" x2 in l85
- 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?
- typo in conclusion "trained more efficiently and at the same time more are more adaptive"


I would recommend proof reading your submission carefully to correct grammar/typos before resubmitting. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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. 

The 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.

This 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.

The 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.  

Experiments 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.

Reading 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.

Overall I’m very positive about this work. The following suggestions are for the authors’ reference: 
-	The 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.
-	Consider 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.
-	[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.
-	[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).

limitations_and_societal_impact: Theoretical work. No concern here.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

**Originality**

The work is novel and cleverly combines aspects from different previous works, to find a more lightweight ALISTA algorithm.

**Quality**

L33: 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. 

L142: 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.

From 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.

L214: 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?

L179: What proofs the claim you already make in this line?

Why 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.

As 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).

**Clarity**

One 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? 

L19: “each column of A, is normalized” -->  normalized to sum to 1?
And can you indicate here why this does help in simplicity, because it comes a bit out of the blue here.

L43-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). 

In L57 and L69, the authors speak about dictionary D, but in equation 1 the dictionary was called A. 

L91: “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.”
This 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.  

L91-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.

*Section 2*

To 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.

L137: “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?

L140: 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?

*Section 3*

L146: 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.

*Section 3.1*

I have most problems understanding section 3.1. Here are some tips/questions that might improve its clarity:

L 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.

L 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).

L151: 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?

L161: 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?

L163: “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.”
--> Which conclusion do you refer to, mutual coherence of what are you referring to,  and which performance?

L164: 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?

*Section 3.2*

L167: “… 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.

L213: You write that you estimate ||x^k -x*||, but in eq. 17 this term is different: ||x^k(x*)-x*||. 


L238: “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’.

From 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?

A textual reference to figure 1 is missing, and a more informative stand-alone caption could be useful.

*Algorithmic description*

After 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.
Looking 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.

*Section 4*

Fig. 3: Introduce the meaning of the abbreviations in the legend in section 4.1.

Fig. 4: What is the difference in implementation between HyperLISTA-GS and HyperLISTA-Full, this is not clear from paragraph 4.2.
Why is comparison to NA-ALISTA only added in section 4.3, but not in 4.1 and 4.2?

 
**Significance**
Reducing the number of hyperparameters in existing algorithms is an interesting direction, and of use to the community.

**Minor points**

L39: double ‘for’ in the sentence.

L115: represent instead of represents

L121: You mention eta_theta while in the formula you use eta_lambda/L.

L 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.

L133: It looks like your forgot bold notation of the last v in this line.

L142: In this line your write B_ < x*_i, while in eq. 8 your use a smaller-equal sign for that inequality.

L153: The set of reals is here indicated with a different R than used in the preceding text.

L157: adopt --> adopt

L159: The gradient with respect to which variable?

L186: How should I interpret this notation: x^k(x*). Is it a dot product or a function operator maybe?

L229: The notation in the denominator of the second term seems faulty.

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_title: null

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)