A Design Space Study for LISTA and Beyond
Authors: Tianjian Meng
Xiaohan Chen
Yifan Jiang
Zhangyang Wang
Venue: ICLR 2021 Poster (2021)

Abstract: In recent years, great success has been witnessed in building problem-specific deep networks from unrolling iterative algorithms, for solving inverse problems and beyond. Unrolling is believed to incorporate the model-based prior with the learning capacity of deep learning. This paper revisits \textit{the role of unrolling as a design approach for deep networks}: to what extent its resulting special architecture is superior, and can we find better? Using LISTA for sparse recovery as a representative example, we conduct the first thorough \textit{design space study} for the unrolled models.  Among all possible variations, we focus on extensively varying the connectivity patterns and neuron types, leading to a gigantic design space arising from LISTA. To efficiently explore this space and identify top performers, we leverage the emerging tool of neural architecture search (NAS). We carefully examine the searched top architectures in a number of settings, and are able to discover networks that consistently better than LISTA. We further present more visualization and analysis to ``open the black box", and find that the searched top architectures demonstrate highly consistent and potentially transferable patterns. We hope our study to spark more reflections and explorations on how to better mingle model-based optimization prior and data-driven learning.

Published as a conference paper at ICLR 2021
A DESIGN SPACE STUDY FOR LISTA AND BEYOND
Tianjian Meng'; Xiaohan Chen² Yifan Jiang", Zhangyang Wang²
"Google Research "The University of Texas at Austin
aineriannian@googee.. (xiachan chen, yifanjiang97, atlaswang) Butesas
ABSTRACT
In recent years, great success has been witnessed in building problem-specific deep networks from unrolling iterative algorithms, for solving inverse problems and beyond. Unrolling is believed to incorporate the model-based prior with the learning capacity of deep learning. This paper revisits the role of unrolling as a design approach for deep networks: to what extent its resulting special architec- ture is superior, and can we find better? Using LISTA for sparse recovery as a representative example, we conduct the first thorough design space study for the unrolled models. Among all possible variations, we focus on extensively vary- ing the connectivity patterns and neuron types, leading to gigantic design space arising from LISTA. To efficiently explore this space and identify top performers, we leverage the emerging tool of neural architecture search (NAS). We carefully examine the searched top architectures in a number of settings, and are able to dis- networks that consistently better than LISTA. We further present more visualization and analysis to "open the black box", and find that the searched top architectures demonstrate highly consistent and potentially transferable patterns. We hope our study to spark more reflections and explorations on how to better mingle model- optimization prior and data-driven learning.
INTRODUCTION
The signal processing and optimization realm has an everlasting research enthusiasm on addressing ill-conditioned inverse problems, that are often regularized by handcrafted model-based priors, such as sparse coding, low-rank matrix fitting and conditional random fields. Since closed-form solutions are typically unavailable for those model-based optimizations, many analytical iterative solvers arise to popularity. More recently, deep learning based approaches provide interesting alternative to inverse problems. A learning-basee based inverse problem solver attempts to approximate the inverse mapping directly by optimizing network parameters, by fitting "black box" regression from observed measurements to underlying signals, using synthetic or real-world sample pairs.
Being model-based and model-free respectively, the analytical iterative solvers and the learning- based regression make two extremes across the spectrum inverse problem solutions. A promising direction arising in-between them is called algorithm unrolling (Monga et al. 2019). Starting from an analytical iterative solver designed for model-based optimization, its unrolled network architec- ture can be generated by cascading the iteration steps for a finite number of times, or equivalently, by running the iterative algorithm with carly stopping. The original algorithm parameters will also turn into network parameters. Those parameters are then trained from end to end using standard deep network training, rather than being derived analytically or selected from cross-validee poossvalidation.
Unrolling was first proposed to yield faster trainable regressors for approximating iterative sparse solvers (Gregor & LeCun 2010), when one needs to solve sparse inverse problems on similar data re- peatedly. Later on, the unrolled architectures were believed to incorporate model-based priors while enjoying the learning capacity of deep networks empowered by training data, and therefore became rising direction in designing principled and thysics-informe ularity of unrolling lies in their demonstrated effectiveness in developing compact, data-efficient, in- terpretable and high-pertte perffrrrrreeece architectures, when the underlying optimization model assumed available. Such approaches have witnessed prevailing success in applications such as compressive
deep architectures. The growing pop-
"The authors Tianjian Meng and Xiaohan Chen contribute equally to the work.

---

Published as a conference paper at ICLR 2021
sensing Zhang & Ghanem 2018), computational imaging (Mardani al. 2018). wireless commu-
nication (Cowen et al. [2019] Balatsoukas- Strooumiin--ttiinngggge & Studer 2019), computer vision (Zheng et al.
2013
Peng et 2018), 8), and other algorithms such as ADMM (Xie et al. 2019).
The empirical success of unrolling has sparkled many curiosities towards its deeper understanding,
A series of efforts (Moreau & Bruna 2017 Giryes al. 2018 Chen al.; 2018 Liu et al., 2019
Ablin et a 2019] l'akabe & Wadayamal (020) explored the theoretical underpinning of unrolling as
a specially adapted iterative optimizer to minimizing the specific objective function, and proved the
favorable convergence rates achieved over classical iterative solver, when the unrolled architectures are trained to (over)fit particular data. Orthogonally, this paper reflects on unrolling as a design approach for deep networks. The core question we ask is:
For solving model-based inverse problems, whut is the role of unrolling in designing deep architectures? What can we learn fearnfrom unrolling, and how to go beyond?
1.1 RELATED WORKS: PRACTICES AND THEORIES OF UNROLLING
Gregor& & LeCun 2010) pioneered to develop a learning- based model for solving spare coding, by unrolling the iterative shrinkage thresholding algorithm (ISTA) algorithm (Blumensath & Davies 2008 as a recurrent neural network (RNN). The unrolled network, called Learned ISTA (LISTA), treated the ISTA algorithm parameters as learnable and varied by iteration. These were then fine- tuned to obtain optimal performance on the data for a small number of iterations. Numerous works (Sprechmann al. 2015 Wang et al. 62 Zhang & Ghanem] 2018 Zhou et al. 20188) followed this idea to unroll various iterative algorithms for sparse, low-rank, or other regularized models.
As the most classical unrolling example, a line of recent efforts have been made towards theoreti- cally understanding LISTA. Moreau & Bruna((2017) re- factorizedd the Gram matrix of the dictionary, and thus re- c--paramtterzzed LISTA show its acceleration gain, but still sublinearly. Giryes et al. (2018) interpreted LISTA as a projected gradient descent descent (PGD) where the projection step was inaccurate. Chen et al. (2018) and et al. (2019) for the first time introduced necessary condi- tions for LISTA to converge linearly, and show the faster asymptotic rate can be achieved with only minimal learnable parameters (e.g., iteration-wise thresholds and step sizes). Ablin et al. (2019) further proved that learning only step sizes improves the LISTA convergence rate by leveraging the sparsity of the iterate. Besides, several other works examined the theoretical properties of unrolling other iterative algorithms, such as iterative hard thresholding (Xin et al. 2016), approximated mes- sage passing (Borgerding & Schniter, 2016)), and linearized ADMM (Xie et al. [2019). Besides, the
safeguarding mechanism was also introduced for guiding learned updates to ensure convergence,
even when the test problem shifts from the training distribution (Heaton et al. 2020).
On a separate note, many empirical works (Wang al. 201 bj Gong al. 2020) advocated that the unrolled architecture, when used as a building block for an end-to-end deep model, implicitly enforces some structural prior towards the model training (resulting from the original optimization objective) (Dittmer et al. 2019). That could be viewed as a special example of "architecture as prior" (Ulynnvv al.) 2018). A recent survey (Monga et al. 2019) presents comprehensive discussion. Specifically, the authors suggested that since iterative algorithms are grounded on domain-specific formulations, they embed reasonably accurate characterization of the target function. The unrolled networks, by expanding the Iearnable capacity of iterative algorithms, become "tunable" to approx- imate the target function more accurately. Meanwhile compared to generic networks, they span a relatively small subset in the function space and therefore can be trained more data-efficiently.
1.2 MOTIVATIONS AND CONTRIBUTIONS
This paper aims quantitatively assess "how good the unrolled architectures actually are", using LISTA for sparse recovery as a representative example. We present the first design space ablation study on LISTA: starting from the original unrolled architecture, we extensively vary the connec- tivity patterns and neuron types. We seek and assess good architectures in number of challenging settings, and hope to expose successful design patterns from those top performers.
As we enable layer-wise different skip connections and neuron types, the LISTA-oriented design space is dauntingly large (see Sections 2.1 and 2.2 for explanations). As its manual exploration is infeasible, we introduce the tool of neural architecture search (NAS) into the unrolling field. NAS
We define design space as family of models derived from the same of architecture varying rules.
2

---

Published as a conference paper at ICLR 2021
explore gigantic design space much more efficiently, and quickly identify the subset of top-peri cop-perfomning candidates for which we can focus our analysis on. Our intention is not to innovate on NAS, but instead, to answer novel question in LISTA using NAS experiment tool.
From our experiments, befitting quote may be: for designing neural networks to solve model- based inverse problems, unrolling is good answer, but usually not the best. Indeed, we are able to discover consistently better networks in all explored settings. From top candidates models, we observe highly consistent and potentially transferable patterns. We conclude this paper with more discussions on how to better leverage and further advance the unrolling field.
2
TECHNICAL APPROACH
Assume sparse vector x" [2
MM I E R.M, observe its noisy linear measurements:
b Σ M
d dma
+ Dx +,,
m=1
where b E RN, D D dv] E RRNMM is the dictionary, and E R is additive Gaussian white noise. For simplicity, each column of is normalized, that is, ||dmmll |DD.m 1, m
1,2, ........ M. Typically, we have N < M. A popular approach for solving the inverse problem: > x. is solve the LASSO below (A is scalar):
1 minx 2
l Dxll2 A||x||a
(2)
using iterative algorithms such as the iterative shrinkage thresholding algorithm (ISTA):
(b+1) 71yL 1 x + D -D"(b-Dx()))
Dx
k = 0, 1,2.....
where Th is the soft-hhresooldin function and L is a smoothness constant that decides the step size. Inspired by ISTA, (Gregor & LeCun 2010) proposed to learn the weight matrices in ISTA rather than fixing them. LISTA unrolls ISTA iterations as a recurrent neural network (RNN): truncated to K iterations, LISTA becomes K K-layer ferw-forward neural network with side connections:
x (k-1) = (70ck) W + (k) W (k) (*)),, = =, K 1.
x =I D' (*) = ((*) = X/L, then LISTA recovers ISTA If we set WT DT ( (R) In practice, we start with (0) set to zero. As suggested by the seminal work (Liu et al. 2019) sharing W, and Wx across layers does no hurt to the performance while reducing the parameter complexity. We follow their weight-rying scheme in the paper, while learning layer-wise (*) and g(k), (k) is separated from Wx preserve flexibility.
We note one slight difference between our formulation (4), and the parameterization scheme sug- gested by Theorem of (Chen et al. 2018). The latter also restricted {Wb. Wx) to be coupled layerwise, and showed it yielded the same representation capability as the orginal LISTA in Gregor & LeCun (010)). We instead have {W. W I as two independent learnable weight matrices. The main reason we did not follow (Chen et al., 2018) is that WD-V W, coupling was directly derived for unrolling ISTA, which is no longer applicable nor intuitive for other non-LISTA architecture variants. Our empirical results also back that our parameterization in { is easier to train for varied architectures from search, and performs the same well when adopted training the original LISTA.
Now, given pairs of sparse vector and its noisy measurement (x", b), our goal is to learn the param- K-1 such that (K) is close to x" for all sparse x* following some eters θ = (Wb, Wx. (k), ((k) ===0 distribution P. Therefore, all parameters in & are subject to end-to-end learning:
min Ex b-r (K) (K)(), b. (0)) x"
This problem is approximately solved over a training dataset { (x}, by) b sampled from P.
"Soft-thresholding function is defined in component-wise way: 77 (x) = sign(x) max |x] 0)
'Those be parameter initialization in LISTA, which we follow (Chen al. 2018) use by default.
3

---

Published as a conference paper at ICLR 2021
Ckuc
(8)
W
41
W
x x
9k-1k
x00
W1
x()
CLt
W
Ri
(a) Original LISTA
(b) Injection w/ Learnable Weighted Average
Figure
illustration of (a) classic LISTA; (b) connection injection with learnable weighted
average. We only plot one layer for illustration.
2.1 VARYING THE CONNECTIVITY IN LISTA
-oriented architectures based on extensively varying the connectivity patterns, starting from the original unrolled LISTA. The way add connections to the original unrolled model is called Learnable Weighted Average (LWA). Specifically, before the output of the k-th layer (x()) is fed into the next layer, we allow the outputs previous layers to possibly (not necessarily) connected to (k) The input to the next layer is calculated with learnalle average of all the connections. Formally,
We first present how we construct new
96.k (Ci.k x))).
(6)
where G are (unbounded) model parameters that will be trained with data, and 9i,k are gates whose values are chosen to decide specific connectivity. Note that LWA introduces a few extra parameters (coefficients c, than LISTA, but those constitute only a very minor portion w.r.t. the size of O
We completely recognize that there are other possibilities vary connections, and did our due dili- gence to make the informed choice of LWA. First, we only focus on adding connections, motivated from both the deep learning and the empirical unrolling fields. On one hand, prevailing success in deep learning (He et al. 2016 Huang et al. 2017) endorse that more densely connected networks are more likely to yield better performance. Prior unrolling works (Wang al. 2016a) also empirically found that removing connections from an unrolled architectures would deteriorate its effectiveness. We also provide additional experiments in the Appendix [A.4 to demonstrate that pruning existing connections in LISTA will be consistently harmful. Second, besides injecting new connections by LWA, we have also experimented with several other options, including a naive averaging way (sim- ply averaging the outputs of all chosen layers), and momentum-ing inspiired averaging way (which is inspired by placing a momentum term into the unrolled algorithm). Through various experiments, we have confirmed that both options are almost consistently inferior to LWA, and therefore focus on IWA in the main paper. The details of the two other options, as well as the experimental compar- isons, can be founded in the Appendix A.3 too.
We by default keep all existing connections in LISTA itself, i.e. the gate function Jg.6 that controls the connection from the immediate preceding layer is always 1. In this case, for K K-layer network,
the total number of possible architectures 22+2+--++KK
When K 16 as commonly set in previous unrolling works (Chen et al. 2018 Borgerding & Schniter 2016). only varying the connnecitivy will lead to a total over 2 100
(X-1)
10st different architectures.
2.2 VARYING THE NEURON TYPE IN LISTA
Besides connection patterns, another important factor that might affect the model performance is the choice of the neuron (non-linear activation function) type. The default neuron in LISTA is the soft-thresolding operator with learnable thresholds (bias term), naturally from unrolling ISTA.
To study whether they might be potential better neuron options combinations, augment the search space to allow each layer to select its neuron from three types: (oss:ssfff sooftttreesolling. ReLU, LeakyRel.U(o 0.1)). That increases the total architecture numbers further by 316 times, resulting in the final gigantic space of 1.75 x 3039 candidate architectures deriving from a 16-layer LISTA.
2.3 HOW TO EFFICIENTLY FIND AND ANALYZE GOOD ARCHITECTURES
The daunting size our LISTA search space begs the question: how to effeetively find the best small subset of architectures, that can observe and reliably summarize patterns from? A manual
4

---

Published as a conference paper at ICLR 2021
exploration is infeasible, and hence we refer to the tool of neural architecture search (NAS) (Zoph & Le 2016) to fulfill our goal. Here NAS is leveraged as an aff-the-shelf tool to explore the search space efficiently and to quickly focus on the most promising subset of top candidates.
Are NAS results stable and trustworthy? Since our main goal is to analyze the found top- performer models and to identify design patterns, the effectiveness and stability of NAS are crucial to the trustworthiness of our conclusions. We take several actions to address this potential concern.
First, avoid the instability arising in training and evaluating the sampled candidate models, adopt no parameter sharing (Pham et al. 2018 Liu et al. 2018). Parameter sharing is currently a popular scheme in NAS to save search time, but can introduce search bias (Chu et al. 20T9). Despite the accompanied tremendous computation costs, we train each individual model from scratch to fully converge. to ensure the most stable, thorough and fully reproducible search results as possible.
Second, to avoid the possible artifact of any single NAS algorithm, we repeat our experiments using three different state-of-the th-tth--rtt non-weight-sharing NAS algorithms,, including reinforcement learn- ing (RL) based method (Zoph & Le (2166), regularized evolution based method (Real et al. 2019) and random sampling based method (Li & Talwalkar] 2019). Those algorithms usually yield di-
verse search behaviors, and in general there is no clear winner among the three (Li & Talwalkar 2019). We use the negative validation NMSE as the optimization reward for them all. Somehow surprisingly, we find: (1) the best candidate architectures (c.g., top-50 in terms of NMSE) found by the three methods reach almost the same good NMSE values; and (2) those best subsets are highly overlapped (nearly identical) in the specific models found, and show quite consistent architecture patterns. Hence due to the space limit, we focus on reporting all results and findings from RL-based NAS, as the other two produce almost the same. We hypothesize that our gigantic LISTA search space might have a smoother and more friendly landscape compared to typical NAS benchmarks, that facilitates oftt--of-the-arr NAS algorithms to explore. We leave that for future work verify.
Third, the top-1 architecture found by NAS will inevitably be subject to sampling randomness and other search algorithm fluctuations (e.g.. hyperparamettess. Therefore, instead of overly focusing on analyzing the top-1 or few architectures, we take one additional step to create an "average ar- chitecutre" from the top-50 architectures, to further eliminate random factors that might affect our results' credibility. Specifically, for every possible connection between layers, we compute the per- centage (between O and 1) of models from the top-50 set that have this connection. We then use a threshold of 0.5 to decide whether the average architecture will have this connection (if the per- centage 2 0.5) or not (if < 0.5). As we will visualize in Section 4 the top-50 architectures usually have a high agreement level on connections, making most percentages naturally close to either 0 or 1. The average architecture helps more clearly perceive the "good patterns" shared by top models.
3 EXPERIMENTS AND ANALYSIS
3.1 EXPERIMENT SETTING AND IMPLEMENTATION DETAILS
Searching. As discussed in Section 2.3 we focus on the RL.-based NAS ZZop & Le| 2016) without weight sharing, i.c., train sampled models from scratch to full convergence. Our experiments are performed on 400 Cloud TPUs, with more than 25,000 architectures sampled during each searct
After the search is complete, we focus on the "average architecture" from the top-50 sampled set, as defined in Section 2.3 Typical NAS works that often find the few best models to have notable performance gaps between each other; different from them, our top-50 searched models have only minor NMSE deviations, in addition their consistent architecture patterns. That endorses the stability of our search, and potentially reaffirms our smoothness assumption of LISTA search space.
To emphasize, we have only performed NAS in the problem setting of Section 3.2 (synthetic, noise- less). For all remaining experiments, we directly re-train and evaluate the same average architecture, on corresponding training and testing sets. The main motivation the ledious model search for every new problem. Instead, we wish to show that by searching only once in problem setting, the searched architecture not only performs best in the same setting, but also can be directly applied (with re- re-training) to other related settings with superior performance. Such transferrability study has also been a popular subject in NAS literature (Zoph et al. 2018). where one searches on one dataset and re- re-trains the searched model on another similar dataset.
avoid the hassle of re-doing
*Our codes, and searched & trained models are published on GitHub
5

---

Published as a conference paper at ICLR 2021
Table 1: Summary of all synthetic experiment results: Comparing our searched architecture (from
Section 3.2) with three baselines. All performance numbers are in decibel (the lower the better).
Model
LISTA
LFISTA
Dense-LISTA
Searched
[a] Number of extra connections (w..t. LISTA)
14
105
42
[6]
SNR oc (the idcal setting where NAŠ is performed)
-43.3
-47.3
-48.3
-54.2
c Gaussian Noise: SNR=40
-34.3
-35.3
-37.3
-38.2
d
Gaussian Noisc: SNR=20
-16.5
-16.9
-17.8
-18.7
c
Non-exactly sparse x"
-22.4
-26.3
-26.9
-29.1
f Transfer-Non Noise (Gaussian): SNR=00 + SNR=40
-32.4
-33.1
-33.7
-34.3
Transfer- Noise (Gaussian): SNR=00 + SNR=20
-7.6
-13.0
-13.3
-13.3
h
Transfer-Noise (Gaussian - S&P): density 1%
-6.0
-9.2
-11.3
-11.7
i
Perturbed dictionary
-28.9
-29.8
-30.4
-30.4
Limited Data (Training size 10,240) Limited Data (Training size 5,120)
-32,4
.42.6
-38,4
.49.6
k
-26.0
-35.3
-26.9
-35,4
Training and evaluating sampled models. adopt the same stage-wise training strategy from (Chen al. 2018 Liu et al. 2019) and use the same default K =16 layers. Every model is trained with batch size 128 and learning rate 0.0005 on Cloud TPUs. In most experiments, the training, validation and testing sets are sampled i..dd without overlap, except the training/testing mismatch experiments where we purposely have training and testing sets sampled from different distributions. Also by default, sample 102,400 samples for training. and 10,240 for validation and testing each, constituting data abundant settings. A data limited setting will be discussed later. For all synthetic data experiments, the model performance evaluated with normalized MSE (NMSE) in decibel Chen et al. 2018 averaged over the testing set: the lower the better.
Baselines. We compare with three strong hand-crafted baselines: the original unrolling LISTA model; the densely connected variant of LISTA (every layer connected to all its preceding lay- ers), denoted as Dense-LISTA; and another improved unrolled sparse recovery model from FISTA (Moreau & Bruna 2017) called LFISTA, which could also perceived as model-based injection of more connections into LISTA. For the fair comparison with LFISTA, we adopt the same parameter- ization to 4 and (6) to model its Nesterov acceleration term. We find that to consistently improve the training stability and final performance LFISTA too. More details are in the Appendix A.
3.2 SEARCH AND EVALUATION IN THE NOISELESS SETTING
We perform our search on the simplest synthetic setting with no additive noise, i.e. 0 in We generate all our data, with a random sampled dictionary D E mm with m 250, n 500, following (Chen et al. 2018 Borgerding & Schniter, 2016). In Appendix A.2 we also investigate the effect of problem size by varying m and n, as well as the effect an ill-conditioned dictionary (instead of Gaussian). We sample the entries of D i.i.d. from the Gaussian distribution Dij N(0, 1/ /m) and normalize its columns to unit & norm. To sample the sparse vectors æ, we decide each of its entry to be non-zero following the Bernoulli distribution with p 0.1, and then generate its non-zero entries from the N(0, 1). We tried to adjust the dictionary formulation, sparsity level or nonzero magnitude distributions in some experiments, and observe the conclusions to be highly consistent. We therefore only report in this setting due to the space limit.
The results are reported and in the row [6] in Table where we compared our searched top-50 average architecture with three baselines. Our main observations are:
The searched average model (significantly) outperforms hand-crafted ones. That proves our concept: much stronger models could be found by NAS in the LISTA-oricnted design space. Particularly, it surpasses the vanilla LISTA by a large gap of 10.9 dB.
The choices of neuron types are "embarrassingly uniform". Even we allow each of the 16 layers independently select neurons, none shows favor ReLU or leaky ReLU, All our top-50 architectures unanimously adopt toft-thresholding as the only neuron type for all their layers. It somehow surprise, and hints the important role of model-basee prior in unrolled networks.
both im- prove over LISTA, search result indicates that "the denser the better" is not the true claim here (Table row [a)). ) That differs from the general mind in computer vision models (Huang
Non-trivial connectivity patterns are discovered, While LFISTA and
et al. 2017 More discussions the searched connectivity in Section

---

Published as a conference paper at ICLR 2021
3.3 TRASNFERABILITY STUDY FOR THE SEARCHED MODEL
We now present the transferablity study, to re-train and evaluate the above-searched average archi- tecture in more challenging settings. The baselines are also re-trained and compared fair settings.
#1 Noisy measurement [c, d] We first add non-zero Gaussian noise E (i.idd across training and testing) to synthetic data. We use two noise levels, corresponding to SNR = 40 dB and 20 dB, respectively. Results in rows [c), [d] of Table show similar trends as [a], though with small gaps.
#2. Non-exactly sparse vector [e] We next challenge LISTA to recover the non-exactly sparse x" in (I. We generate x" from the Gamma distribution r(a, 3) with a = 1.0 and [ = 0.1.. In this way, x has a handful of coordinates with large magnitudes, while the remaining coordinates have small yet nonzero values, making it approximately sparse or not exactly so. In order to disentangle different factors' influences, no additive noise placed in this case (SNR = oo). From row [e] of Table D the same trend is observed, so is the superiority of the searched model.
#3. Training-testing mismatch [fs g. h, i] We proceed to checking more challenging and prac- tical scenarios of model robustness where the training and testing distribution may mismatch. We consider three cases in Table []] (1) Transfer-Noise (Gaussian): we train models on the noiseless training set (S))= and directly apply to the two noisy testing sets, i.e., SNR = 40 dB as in row [s] and 20 dB in [g]. (2) Transfer-Noise (Gaussian + salt & pepper): the models trained with SNR = 00 are encountered with an unseen noise type in testing: salt & pepper noise with 1% den- sity; (3) Perturbed dictionary" we keep our soaniing/valiaationnn sets generated by the same dictionary D (SNR= oo), while re- re-generating a testing set by the following way: we sample a small AD from Laplacian distribution L(, 10 perturb D D + AD create unseen basis, normalize D to unit column and then use it to generate new testing samples (no additive noise).
degraded performance under those challenging settings, but our searched architecture sticks as the best (or tie) among all. LFISTA and Dense-LiSTA are also able to outperform LISTA. Besides, the gaps between Dense-LISTA and ours are generally reduced in all those mismatch cases, implying that denser connections might benefit model robustness here.
Not surprisingly, all models
#4. Limited training data [j. k] We lastly verify a hypothesis raised in (Monga et al. 2019), that unrolling provides model-based prior and helps train more generalizable networks in the data-limited training regime. To prove this concept, we reduce the training set to 10,240 and 5,120 samples, i.e., 10% and 5% of the default training size, respectively The validation set also reduced to 1,024 samples (10% default size), but the testing set size remains unchanged.
We observe two specifically interesting phenomenons: for the first time in our experiments, LFISTA outperforms Dense-LISTA notably, and the margin seems to enlarge as the training size decreases; (2) the searched architecture largely outperforms the other three when the training size is 10,240; yet it becomes comparable to LFISTA at the smaller 5,120 training size, albeit still clearly surpassing LISTA and Dense-LISTA. The lessons we learned seem to convey compound informa- tion: (i) LFISTA's robust performance suggests that model-based unrolling indeed provides strong inductive prior, that is advantageous under data-limited training: (ii) compared to [6 - i] where Dense-LISTA has consistently strong performance, adding overly dense connections seems not to be favored in data-limited regimes; (3) our searched architecture appears to be the right blend of model-based prior and data-driven capacity, that also possesses robustness to lata-limited training.
4 OPEN THE BOx: WHAT GOOD DESIGN PATTERNS ARE INSIDE?
closer look at the averaged connectivity. Experiments in Section 3 indicate that significantly im- proved architectures can be spotted by NAS, whose strong performance generalizes in many unseen settings. We now dive into analyzing our searched average architecture. Figure the top-50 architectures before threshold, i.e., each value indicate the "percentage" of top-50 models having that connection (1 denotes all and 0 none). The following patterns are observed:
the average of
The consensus connectivity is overall high. There are nearly 50% connections that over 90% of the top-50 models agree not to use. It seems the sparse recovery task obeys certain model-based prior and does not favor overly densely connections, as seen in Dense-LISTA.
Many applications (such as video-based) can be formulated as sparse coding models whose dictionaries are subject to small dynamic perturbations (c.g, slowly varied over time) (Liu et al., 2019 ZZao et al. 2011). We did go smaller since all performance would catastrophically drop when training size below 5%.
7

---

Published as a conference paper at ICLR 2021
Layerlli
Layeriti
Layer!ti
Layeriti
Layer!ii
Layerti
0.52
Layerhi
0.22
0.52
0.28
Layer!ti
0:86
Layar!
0.28
0:88
0.12
Layarthn
0.62
0.24
0.02
Layer!iil
0.94
0.08
0.98
0.6
Layertiz)
0.08
0.08
0.04
0.02
Layor!!
0.1
0:42
0.18
Layer!!4)
0.02
0.1
0.04
Layer!i3)
[ayerti4)
x/0
X y0:
yit XP
y0N
Figure 2: Visualization of our scarched "averaged architecture". The vertical and horizontal axes denote the "destination" " and "origin" layer indices for a skip connection. Note that every layer is always taken as input for its immediate preceding layer, therefore the diagonal line is all one.
Besides the default connection (diagonal line), every layer uses at least one extra skip connection. If counting threshoding (0.5), all layers except layers 12. 14. 15 "activate" no less than 1/3 possible input skips, and more than half layers "activate" no less than 1/2. Those extra connections might represent be interpreted as acceleration terms, potentially more sophisticated than studied in (Moreau & Bruna 2017): we leave for future research.
Early and late layers have better consensus on connections, while middle layers (9-11) display some diversity of choice. The last layer (16) looks particularly special: it has connections from most preceding layers with high agreements. Our further experiments find that those connections to the last layer contribute a notable part to our searched performance: we only pick those extra connections to layer-16 16 from our average architecture, and add them to LISTA/LFISTA, then can immediately boost LISTA from -43.3 dB to 48.2 dB, and LFISTA from -47.3 dB to -48.4 dB (noiseless setting). Understanding the role of "densely connected last layer" unrolling seems to be an interesting open question.
Transferring found pattern to other unrolling. We briefly explore whether the LISTA-found design patterns can generalize to other unrolling. We choose differentiable linearized ADMM (D- LADMM) (Xie et al. 2019), another competitive unrolling model for sparse recovery, as the test bed. We directly transplant the connectivity in Figure 2 by adding those extra (non-diagonal) connec- tions to augment D-LADMM, with no other change. We compare (a) the original D-LADMM; (b) random architectures with 42 extra connections sampled i.i.d. (the same total number as the trans- ferred pattern); (c) D-LADMM with dense connections added only to the latter half layers (77 extra connections in total); (d) densely-
D-LADMM constructed similar to Dense-LISTA with 105 extra connections; (e) our transferred one with 42 extra searched connections. For the random connected models, we sample patterns and report the average NMSEs.
The three models are trained and evaluated in three representative settings: (1) noiseless: the three models' NMSEs are -54.2 / -55.0 / -55.3 / -55,4 / -55.6dB, respectively; (2) noisy (SNR 20): NMSEs - 18.2 18, - 18.9 / -19.0/ dB; (3)
(training size 10,240): NMSEs -24.8
/-25.6/ / 29.8 -2..6 -33.5 dB. Several observations and conclusions can be drawn:
The transferred connectivity pattern immediately boosts D-LADMM in all three settings;
The more dense variants perform comparably with our augmented one when training data is sufficient, but degrades even behind the original in the data-limited regime;
The Prnss-in-LLater-HEE does not outperform the transferred pattern, and especially de- grades the performance when the training data becomes limited. It seems some earlier-layer extra connectivity might help the trainability of the early layer those cases. That indicates that our learned connectivity pattern is more subtle than naively "denser for latter";
The randomly connected models with the same amount of extra connections as the trans- ferred one are in general on par with the data. Those show that although appropriate connection percentage is a useful factor, it does not constitute the major value our searched specific connectivity.
Hall. but even worse on limited
8

---

Published as a conference paper at ICLR 2021
5 DISCUSSIONS AND FUTURE WORK
While unrolling often yields reasonably good architectures, we seem to discover consistently better networks in this study. But are we denying the advances and promise of the unrolling field? Abso- lutely Not. As veterans studying unrolling, we hope this work to provide a reference and spark more reflections, on when unrolling is useful, how to improve it more, and (broadly) how to mingle model- based optimization and data-driven learning better. good perspective was taken in (Monga al.] 2019), suggesting that with the original model-based optimization (Dittmer al. 2019) induced as a prior, the unrolled architectures behave as "an intermediate state between generic networks and it- erative algorithms", possessing relatively low bias and variance simultaneously. Unrolled networks might be more data-efficient to learn (supposed by our while if training data is sufficient, if linear sparse model is not the accurate prior, then unrolling does not have to be superior. We then recommend data-driven model search or selection, perhaps leveraging the unrolled model as a robust starting point the design space.
training experiments). Mean-
We shall further comment that this study is in completely different track from theoretically under- standing LISTA
learned optimization algorithm (Moreau & Bruna 2017 Giryes et al. 2018
Chen et al. 2018 Liu et al. 2019; Aberdam et al., 2020). Those works' interests are mainly on in- terpreting the unrolled architecture as an early- early-truncated iterative optimizer (with adaptive weights): unrolling plays the central role in bridging this optimization -iise interpretability. Unrolling can also connect to more desired stability or robustness results from the optimization field (Aberdam et al.) 2020 Heaton et al. 2020), which makes great research questions yet is beyond this paper's s scope.
REFERENCES
Aviad Aberdam, Alona Golts, and Michael Elad. Ada-lista: Learned solvers adaptive to varying models. arXiv preprint arXiv:2001.08450 2020.
Pierre Ablin, Thomas Moreau, Mathurin Massias, and Alexandre Gramfort. Learning step sizes for unfolded sparse coding. In Advances in Neural Information Processing Systems, 2019.
Alexios Balatsoukas- Salatsoukka-SSimmingg and Christoph Studer. Deep unfolding for communications systems: A survey and some new directions. arXiv preprini urXiv:/906.05774 2019.
Amir Beck and Mare Teboulle. A fast iterative shrinkagg-thhresholdnng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1): 2009.
José M Bioucas-Dias and Mário AT Figueiredo. age/thresholding algorithms for image restoration. IEEE Transactions on Image processing, 16 (12):2992-3004, 2007.
new twist: Two-step iterative shrink-
Thomas Blumensath and Mike E Davies. Iterative thresholding for sparse approximations. Journal of Fourier analysis and Applications, 14(5-6):629-66) 2008.
Mark Borgerding and Philip Schniter. Onsager-corrected deep learning for sparse linear inverse problems. In Signal and Information Processing (GlobalSIP), 2016 IEEE Global Conference on, pp. 227-231. IEEE, 2016
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of un- folded ista and its practical weights and thresholds. Advances in Neural Information Processing Systems, pp. 9061-9071, 2018.
Xiangxiang Chu, Bo Zhang, Ruijun Xu, and Jixiang Li. Fairnas: Rethinking evaluation faimess of weight sharing neural architecture search. arXiv preprint arXiv:1907.01845. 2019.
Benjamin Cowen, Apoorva Nandini Saridena, and Anna Choromanska. Lsalsa: accelerated source separation via learned sparse coding. Machine Learning, 10378-7) 2019.
Sören Dittmer, Tobias Kluth, Peter Maass, and Daniel Otero Baguer. Regularization by architecture: A deep prior approach for inverse problems. Journal of Mathematical Imaging and Vision, pp- 1-15, 2019.

---

Published as a conference paper at ICLR 2021
Raja Giryes, Yonina C Eldar, Alex Bronstein, and Guillermo Sapiro. Tradeoff's between convergence speed and reconstruction accuracy in inverse problems. IEEE Transactions on Signal Processing, 2018.
Dong Gong, Zhen Zhang, Qinfeng Shi, Anton den Hengel, Chunhua Shen, and Yanning Zhang- Learning deep gradient descent optimization for image deconvolution. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference on Machine Learning, pp. 399-406 406. Omnipress, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Howard Heaton, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Safeguarded learned convex optimization. arXiv preprini arXiv:2003.01880 2020.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Kuldeep Kulkarni, Suhas Lohit, Pavan Turaga, Ronan Kerviche, and Amit Ashok. ReconNet: Non- iterative reconstruction of images from compressively sensed measurements. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 449-458. 2016.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search.
arXiv preprint arXiv: 1902200600.. 2019.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv
preprint arXiv: 1e0..0905..0.0 2018.
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Alista: Analytic weights good as learned weights lista. In ICLR, 2019.
Morteza Mardani, Qingyun Sun, David Donoho, Vardan Papyan, Hatef Monajemi, Shreyas
Vasanawala, and John Pauly. Neural proximal gradient descent for compressive imaging. In Advances in Neural Information Processing Systems, pp. 9573 9773-9583,.22 2018.
Vishal Monga, Yuelong Li, and Yonina Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. arXiv preprint 19Xiv: 2019.
Thomas Moreau and Joan Bruna. Understanding trainable sparse coding with matrix factorization. In ICLR, 2017.
Xi Peng, Ivor W Tsang, Jocy Tianyi Zhou, and Hongyuan Zhu. k-meansnet: When k-means meets differentiable programming. arXiv preprint arXiv: 1808. 07292, 2018.
Hieu Pham, Melody Y Guan, Barret Zoph, Quoc V Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint arXiv:1802.03266 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference artificial intelligence, volume 33, pp. 4789-4789, 2019.
Pablo Sprechmann, Alexander Bronstein, and Guillermo Sapiro. Learning efficient sparse and low rank models. IEEE transactions on pattern analysis and machine intelligence, 37(9):1821- 1833, 2015.
2015.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance initial- ization and momentum in deep learning. In International conference on machine learming, pp- 1139-1147, 2013.
Satoshi Takabe and Tadashi Wadayama. Theoretical interpretation of learned step size in deep- unfolded gradient descent. arXiv preprint arXiv:2001.05 2020.
10

---

Published as a conference paper at ICLR 2021
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9446-9454, 2018.
Zhangyang Wang, Qing Ling, and Thomas Huang. Learning deep 10 encoders. In AAAI Conference on Artificial Intelligence, pp. 2194-2200, 2016a.
Zhangyang Wang, Ding Liu, Shiyu Chang, Qing Ling, Yingzhen Yang, and Thomas S Huang. D3: Deep dual-domain based fast restoration of jpeg-compressed images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2764-2772, 2016b.
Xingyu Xie, Jianlong Wu, Guangcan Liu, Zhisheng Zhong, and Zhouchen Lin. Differentiable lin- earized admm. In International Conference on Machine Learning, pp. 6902-6911, 2019.
Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal sparsity with deep networks? Advances in Neural Information Processing Systems, pp. 4340-4348, 2016.
Yangyang Xu and Wotao Yin. A block coordinate descent method for regularized multiconvex optimization with applications nonnegative tensor factorization and completion. SIAM Journal on imaging sciences, 6(3): 2013.
Jian Zhang and Bernard Ghanem. Ista-net: Interpretable optimization-inspieee deep network for image compressive sensing, In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1828-12 1837, 2018.
Bin Zhao, Li Fei-Fei, and Eric Xing. Online detection of unusual events in videos via dynamic sparse coding. In Computer Vision and Pattern Recognition (CVPR), pp. 3313-3320 IEEE, 201 1.
Shuai Zheng, Sadeep Jayasumana, Bernardino Romera- Cennera-Prredes,, Vibhav Vineet, Zhizhong Su, Da- long Du, Chang Huang, and Philip HS Torr. Conditional random fields recurrent neural net- works. In Proceedings of the IEEE international conference on computer vision, 2015.
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 LSTMs for sparse coding. In AAAI Conference Artificial Intelligence, 2018.
Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning, arXiv preprint arXiv:1611.0157,, 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018.
A APPENDIX
A.1 HAND-CRAFTED CONNECTIVITY BASELINES
Other than the original unrolled LISTA, we also compare our searched connectivity pattern with two hand-crafted connectivity baselines LFISTA and Dense-LISTA. Figure 3 shows straightforward visualization for these two hard-crafted connectivity patterns.
A.1.1 LFISTA
The formulation of FISTA Beck & Teboulle 2009 is
((++)) 1 v1 + 41)++
((k)
(++1) = (1))= + +(++1) (x (k) - x (01-)))
(7)
(1+1) 7aa1 (y +D + 1x
11

---

Published as a conference paper at ICLR 2021
Loyok
Lonnk
lapve
Lowik
Leprie
Loporit
(a) LFISTA connectivity
(b) Dense-LISTA connectivity
Figure 3: Connectivity visualization for LFISTA and Dense-LISTA. The vertical and horizontal ax- esdenote the "destination" and "origin" layer indices for skip connection. 1 means the connection activated.
It is natural to parameterize the second step
(k+))) (k) (8)
(k) (k (k-1)
+ C2
(8)
which will reduce FISTA to LWA that introduced in the main text. Of course we can plug (k++1) into the third equation in (7) re-arrange and combine terms and parameterize the iteration
(k+1) T
( (w(k))) (k) + W (1- + Wbb)
However, this will introduce more parameters than LWA. As we mainly consider LWA in the main text, we use the parameterization in (8) in this paper for fair comparison. Introducing FISTA to our design space would add 14 extra skip connections.
A.1.2 DENSE-LISTA
Inspired by successful application of dense connections in deep learning (Huang al.) (017). manually enable all possible skip connections in our connectivity design space. For this densely- connected LISTA instantiation, each layer will take the outputs of all its previous layers input, leading to 105 extra skip connections comparing to the original LISTA.
A.2 COMPLEMENTARY EXPERIMENTS
A.2.1 DIFFERENT PROBLEM DIMENSIONALITIES
We are also curious whether our finding is also applicable to sparse coding problems with different dimensionalities. Here we follow the same noiseless setting Section3.2 in the main text, but enlarge the dictionary to 512x 1024, i.c. m 512, n = 1024, and regenerate the training, valiation and test data with the new dictionary. As shown in the first row of Table 2 our results with new dimensionality setting are highly consistent to the noiseless measurement setting, indicating our searched pattern does not overfit a specific problem size.
A.2.2 ILL-CONDITIONED DICTIONARIES
Most dictionaries used in the experiments well-conditioned Gaussian random matrices that enjoy ideal properties such as natural incoherence. However, in real-world applications, this is too ideal be true. Here we manually create ill-conditioned matrices and use them as the dictionaries. We sample two Gaussian matrices U E 250 and V E 202005500 Then we use D = UVV as the dic- tionary, which is inherently low-rank. With an ill-conditioned dictionary, our searched architecture still outperforms other counterparts as demonstrated in the second row of Table 2
A.2.3 REAL-WORLLD COMPRESSIVE SENSING
Beyond synthesis experiments with generated signals with ideal sparsity, we further re-used the architecture searched on the synthetic data, and train/test this architecture Natural Im-
12

---

Published as a conference paper at ICLR 2021
Table 2: Complementary experiment results for different dictionaries.
Dictionary
LISTA
LFISTA
Dense-LISTA
Searched
D E R512x1024
-4.11
-47.0 -33.4
-47.9 -42.4
-52.4
D = U E IR 250x200
V E
IR 200x 500
-27.1
-42.8
age Compressive Sensing, following the setting in Section 4.2 of (Chen et al.) 2018). We ex- tract 16x16 patches from the natural images in BSD500 dataset and downsample the patches to 128-dimension mcasurements using 128 x256 Gaussian sensing matrix (c.g.. compressive learned using a dictionary learning algo-
sensing ratio = 50%). The dictionary (256x512)) rithm (Xu & Yin 2013). We train LISTA, LFISTA, Dense-LISTÄ and the searched architec- ture on 400 training images on BSD500 and test the trained model on 11 standard testing im- ages (Kulkarni et al. 2016). The results are shown in Table where the average PSNR in decibel on the testing images are reported. We run three repetitions of training for all archi- tectures and report the average PSNR over the three runs. We observe that although the chitecture is searched on synthetic data/task and then directly reused for training on dif- ferent new task robustly, outperforming LISTA by 0.11
data (natural image patches), the searched architecture still performs dB, and slightly surpassed L.FITA and Dense-LISTA.
Note that the synthetic data and natu- ral images have significant gaps. Al- though the transferred architecture is not dedicatedly searched for the compres- sive sensing problem, it still performs very robustly; re-searched architecture on natural images would naturally only expect better performance.
Table 3:
Real-world compressive sensing experiment re- sults in PSNR (dB) on our searched average architecture (from Section 3.2 and three baselines.
Model
LISTA
LFISTA
Dense-LISTA
Searched
PSRN (dB)
34.67
34.73
34.69
34.78
A.3 CONNECTION INJECTION OPTIONS
Other than the Learnable Weighted Average (LWA) we use by default in the main text, we also consider two other options inject connections.
A.3.1 NAIVE AVERAGE (NA)
The most naive approach fuse extra connectivity into the unrolled LISTA 4 to simply take the average of the outputs of all chosen layers, before we apply the linear transform (kk), Formally, replace xk) in with
(b))
Σ 9s.k x(1)
(NA)
Σi=1 Gi.k
where Ji,k E {0.1} is gate that controls whether the i-th iterate is chosen as the input to the k-th layer (same hereinafter). Denote the gates that connect the k-th layer, e.g. all gates (NA) as vector
gi = (gI.k..... xT, and then concatenate into long ordered vector g = [g. [gT.....g., gg_ - All possible combination of the gate values of the gates form the search space H. {g).
T
A.3.2 MOMENTUM (MM)
We also consider more complicated way to manipulate extra skip connections, inspired by momen- tum approaches Sutskever al.) (2013) optimization. Several acceleration approaches for ISTA leverage momentum terms, such the renowned Fast ISTA (FISTA) Beck & Teboulle (000);; Bioucas-Diaz & Figueiredo (2007). To allow for flexibly learnable momentum, we illustrate our idea with simple example, where only last two iterates are considered in the momentum. In this way, the ISTA iteration (3) is extended as:
(k+1) Mour (x)(k) + g(())(()))
(9)
13

---

Published as a conference paper at ICLR 2021
b
W
(k)
x
W1
gk.k
(k)
a2
((h-1)
W2
1.1
x(1)
W
81,k
Figure 4: An illustration connection injection with Momentum.
where ((0) is hyperparameter that controls the strength of momentum. Note that 9 reduces
ISTA (3) if we set g(k) = L/L, o0k) = A/L and ((k) Vxf(x(() D (x(1) (k) is the
update direction that already takes momentum into consideration involving the last two iterations:
((k) = - + (
(10)
1* (8)) (1- (1- D(b (x
(11)
- Dx - - 1D" (x(
(12)
Substituting 12) in 9 gives
D'x x (1+1)) = (7 (B(4) D' (I 3(6) (M +
-1-(0)) -1-001 D' D)x (13)
Denote ((()) DT. w(()) =I- - (k D and W(! = (1 D' and then
we get the untied version (do not share wh(hh) w(lk) ((( within layers) of (8):
(k+1)) Moc
(1) b W(th (k) x
(14)
As suggested by the seminal work (Liu al. 2019), sharing the above weight matrices (correspond- ing to using layer-invariant 33 and 7) across layers does no hurt to the performance while reducing
the parameter complexity. However, introduce two scaling parameters a (N) and a2 (will be
(k)
trained using data) to loosen the constraint, yielding a simpler form of (14:
x (++1) Ticck (W,b a (x) + a (k)
(2)(.-))).
(15)
Extending 15) to the general case where all previous iterates could be chosen by a gate to get involved momentum term ((k, we get
x (k+11)= = 7 Wob
Ex 9641- (a. (.x(
(MM)
where the subscript W, means its input to come from the i-th last iterate and og (k) is the step size parameter associated with W; in the k-th layer. Step sizes a; (k) are initialized with 1.
A.3.3 EMPIRICAL RESULTS
Before launching our large-scale search experiment, we first compare three of our connection injec- tion methods (LWA, NA and MM) by randomly sampling about 500 architectures from our design space, and train each of them individually following our single model training protocol in Section Since we are focusing on evaluating injection methods, we use soft- sottttreesholding as our neuron type by default.
14

---

Published as a conference paper at ICLR 2021
MM L9A
MM
-22.
UMA USTA
KA USTA
KA
LISTA
120
NADE (18)
-213
WHBE 0181
-000
-46
Numberof of cornections
Numberon stip conecct (b) SNR 40dB
Number of contections
(a) Noiseless (SNR=x)
(c) SNR 20dB
Figure 5: The NMSE distribution of sampled architectures, using NA, LWA and MM to inject extra skip connections, synthetic experiments under different SNRs. The red star marks the original LISTA. x-axis from left to right denotes the number of added extra connections from low to high. y-axis denotes the models' obtained NMSEs (the lower the better). Best zoom in and view in color
-2
MM
-33
-30
LISTA
NMSE (dB)
NMSE (dB)
-25
LWA
LISTA
-40
-26
-50
20
40
100
20
60
80
100
Number of skip connections
Number of skip connections
(a) Non-exactly sparse case.
(b) Data limited (10240) case.
Figure 6: Distribution of sampled architectures in non-exactly sparse vector case and limited training data case.
Noiseless measurement and Gaussian noise. We first conduct experiments under three most common settings (noiseless measurement, noisy measurement with 40dB and 20dB additive Gaus- sian noise). As shown in Figure 5) NA always hurts the performance in all three settings. While MM could perform slightly better than LWA in noiseless setting, LWA clearly beats MM in noisy setting for both SNR=40dB and SNR=20dB. Based on our observation that NA constantly yields worse performance, we conduct the rest comparative experiments using only LWA and MM.
More complicated settings. Other than additive Gaussian noise cases, we also evaluate and com- pare LWA and MM on the two more challenging and realistic settings: non-exactly sparse vector and limited training data. We follow the same setting as described in Section 3.3 We use 10240 as training data size limited training data setting. From NMSE distributions in both Figure and noisy setting in Figure 5 can clearly tell that LWA has better robustness when the same connectivity pattern is applicd. At the same time, probably due to the larger number of parameters introduced, MM suffers more from limited training data.
Since MM only wins in the easiest noiseless case with sufficient training data, we can safely tell that LWA has more practical values noise the data and where the data is limited. Since we are not in an ideal world, we choose to conduct all main experiments using LWA to fuse injected connections.
is consistently the winner of settings where have different
15

---

Published as a conference paper at ICLR 2021
A.4 SIDE CONNECTION PRUNING
Despite of our focus on adding skip connections in this paper, we also empirically evaluate what will happen we also allow for pruning connections. As shown in Figure [[a] we insert gate func- tions to side connections to decide whether they will be removed from the original unrolled LISTA. Specifically, we allow all the side connections except the first one to have the probability being re- moved from the architecture. As use K 16 LISTA layers search space is consisted of 2 potential candidates for original unrolled LISTA architecture. For our joint injection and pruning setting, the search space is enlarged to 2 x 2 2 Note also utilize the tool of random sampling here as in Section A.3.3 and choose to use soft-thresholding for all layers.
default setting, pruning
NMSE (dB)
-20
b
W
fb.k
Pruned USTA
-40
LISTA
(k)
W
Number of side connections
#1
(a) Connection Pruming
(b) NMSE Distribution LISTA Pruning
Figure Pruning from original unrolled LISTA.
A.4.1 PRUNING FROM ORIGINAL LISTA
We first apply the side connection pruning search space to the original LISTA. shown in the Figure 7(b) removing side connections will always do harm to the unrolled LISTA model, which echos finding observed by (Wang et 2016a).
LWA
-37.5
NMSE (dB)
-20
NMSE (dB)
-45.0
30
-50
LISTA
-52.5
16
70
100
110
120
Number side connections
Number of connections
(a) Side Connection Pruning from LWA
(b) Arrow pointed from pruned to connected
Figure 8: Pruning from LWA architectures.
A.4.2 JOINT INJECTION AND PRUNING
Next we apply both connection injection and side connection removal at the same time. Our results in Figure 8(a) illustrate that although connection injection greatly reduce the influence of side
16

---

Published as a conference paper at ICLR 2021
Layer!l
Layerit!
Layer!!
Layeriti
0
Layer!!i
Layarti
-3.13
Layer!i
0.003
0.02
0013
Layer!ti
<0.057
-0.0087
B013
40.0087
0.55
Layartmn
0.04
-0019
Layertiii
00.089
0.057
Layertizi
0.13
0.008
0.000/
0.52
Layor!!i
Layer!!4)
Layer!i3)
(ayertii)
x=1
yith
x
gitar
yit
ytM
Figure 9: The connection difference between the default top-50 average and top-30 average.
connection pruning, most architectures from this design space suffer from the removal of side con- nections. We also randomly select some models this setting, keep their injected skip connections and reconnect all their side connections. Figure 8(b) shows how NMSEs change for LWA models. The arrows point from the "pruned side connections" case to "full side connections" case and the axis means the total number of skip connections and side connections. As we see, we can almost always gain performance by reconnecting all side connections, which is aligned with our observa- tions in A.4.1 Our observation here indicates that should always keep all side connections.
A.5 STABILITY AVERAGED ARCHITECTURE
To further demonstrate the stability of our averaged architecture, we recalculate an averaged archi- tecture from top-30 models, and compute its connection differences with the default top-50 average one. The difference map is visualized in the Figure Clearly, they are highly aligned and echo our observations that those top architectures already have high agreement on connections be activated.
17


Reviews:
[{"review_id": "woYZQkDY2lV", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of contributions: \n\nIn this paper, authors performed a neural architecture search to improve LISTA algorithm for solving the lasso on synthetic data. The main motivation of this paper is to investigate the effectiveness of unrolling in comparaison with a more \"black box\" architectures. The \"averaged\" top architectures found by the study give better performance than LISTA when the  two models are trained on the same dataset.\n\nStrengths: \n\n-The idea of using NAS to study unrolled models seems to be novel to the best of my knowledge. \n\n-This idea is interesting. I definitely agree that the relevance of unrolled architectures should be questioned. \n\n-The authors did a good job to describe clearly their idea and the experiments they conducted (at the exception of the last paragraph \"transferring found patterns to other unrolling\" which lacks clarity in my opinion).\n\nWeaknesses: \n\n-I think that the overall conclusions of the paper are not very significant. The authors only focus on a very simple problem : the lasso on synthetic data (with known dictionaries). In such a simple setting I do not see why one would consider using this trainable model rather than more standard algorithms for solving the lasso (which are significantly faster than ISTA and have convergence guarantees and/or duality gap).\n\n-I am not convinced by the results regarding transferability. Even if the searched model outperforms the other methods in the simplest setting, the searched model seems to be very sensitive to perturbations. Looking at line (i) of table 1 with perturbed dictionary, the gap between searched model and LFISTA is small and the searched model performs as good as Dense Lista. More generally, the searched model seems to perform as good as Dense LISTA in most of the perturbed settings. Again this question the utility of this model. \n\n-The authors only consider the problem where the underlying optimization problem is known. I think it would be much more interesting to study the case when this underlying optimization problem is not known and has to be learnt (that aspect is briefly discussed at the end of the related work section). For example what if the dictionary is not known ? Lista offers the possibility to learn the dictionaries with end-to-end training. What would be the results of the NAS in the setting with unknown dictionary, how would unrolled models perform in that setting ?\n\nSuggestions to authors: \n\n-It would be interesting to consider the case where the underlying optimization problem is not known a priori. In that situation I think that unrolled models make more sense  (unrolled weighted-l1sparse coding for a simple task such as denoising, experiments with learned dictionaries ...). In that setting I would be more curious regarding the results of the NAS study.\n\n-I think it would be relevant to compare the unrolled models to other algorithms for solving the lasso (lars...). In my opinion, it would clarify the conclusion of the paper. (A comparison in term of inference speed, accuracy, computational cost would be interesting).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "oZILNiRwWcc", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper conducts an empirical study on unrolling architecture design, by applying NAS to search the connectivity pattern based on LISTA, and compares the searched model to the original LISTA.\n\nPros:\n+ The paper is clearly written and not hard to follow\n+ Experiments show that the searched architecture performs better than LISTA\n+ The experiments are comprehensive, including various experimental settings that can compare the unrolled architectures from different aspects\n\nCons:\n- Technically, it is a direct application of NAS to LISTA, so the methodological contribution is not very strong\n\nThrough extensive experiments, this paper shows the effectiveness of NAS for searching for a better architecture based on unrolled algorithms, via a case study on LISTA. It tells that unrolling may not be the best choice and better architecture can be found by NAS. However, the technical contribution and novelty of the approaches are not strong enough. I personally think this is a broader line paper and my score is actually between weak acceptance and weak rejection.\n\ngrammar:\n- In the abstract, '.... and are able to discover networks that consistently better....' ->  '.... and are able to discover networks that ARE consistently better....'\n\n====after author response===\nI would like to thank the authors for the detailed response which resolves some of my concerns about the novelty of this paper. I agree that this is the first work (as far as I know) that brings NAS to unrolled algorithms. Unlike what I initially commented, 'my score is actually between weak acceptance and weak rejection', now I am happy to rate this paper as a weak acceptance.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Xu7UakCtKjJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied the structure designing problem for a class of neural networks, i.e., the unrolling networks, or more specifically the LISTA model. Specifically, the authors varied the connectivity patterns and neuron types to define a rich searching space for the network design, and then applied the neural architecture search techniques to fined the best networks. \n\nThe studied problem is interesting and important, and the conducted experiments reveals some insights of unrolling based deep networks, which provides some useful guidelines for further research in this direction. The paper is also well written and easy to follow. Overall, I think this is a good submission.\n\nA drawback, concerning about the experiments, of the manuscript is that it lacks applications. Therefore, a suggestion is to apply the learned network structures to more practical problems, such as image denoising and compressive sensing, or something else, to see whether they are effective in practice.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q1jN7QfKPO", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a very interesting new problem of assessing unrolled models in a broader context using NAS methods. LISTA-style unrolling has been popular for deep learning-based inverse problems. But it is quantitatively unclear how good the unrolled models are, among all possible model variations. To fill in this gap, the authors first define a proper search space based on the varying connections and neurons from the unrolled LISTA backbone architecture. NAS is then exploited as the tool to find the best subsect of architecture from the large space. \n\nThis method is very intuitive yet solidly done. Since NAS itself is not always stable, the authors present a number of efforts and discussions to support the reliability and reproducibility of their observations. Sec 2.3 shows their diligence in trying out multiple NAS algorithms; avoiding using weight sharing; and “averaging” the top architectures to smooth out random fluctuations. I appreciate those valuable careful efforts. \n\nThe experimental study in Section 3 is very comprehensive and clearly laid out. Table 1 gives a great gist of their main findings. The authors compare with two natural baselines, LFISTA and Dense-LISTA. They prove NAS can indeed find superior architectures than those hand-crafted in all the different settings. The overall take-home point seems like no big surprise at first glance: unrolling provides a reasonably good architecture; yet if there are abundant training data, more complicated architectures can be discovered by varying connections (varying neurons seems not helpful). \n\nBut, a closer look at those experiments reveals many new finer-grained observations that really intrigue me. For example, it is interesting to see “the denser the better” is not the simple right claim in unrolling; and especially unrolling-based models are advantageous under data-limited training. Another good surprise is to see that all top architectures unanimously adopt soft thresholding as the only neuron type for all layers. The most interesting part of this paper is the \"open the box\" section 4 where the authors discuss the common characteristics of top architectures. Figure 2 is a highly interesting visualization and shows the top-50 architectures are indeed consistent on most connections.  It is very promising if we can understand further (1) why “the later the denser” - could that imply/be interpreted as switching to another higher-order algorithm in later iterations? and (2) why the last layer is particularly all-connected?\n\nI think bringing NAS to learning based algorithm design is a very novel and interesting direction. This paper can potentially turn into a seminal work here to inspire followers. The paper is also well written, and the logic is very clear to follow. Section 5 concludes with a thoughtful discussion on what this work may connect and point to for the entire unrolling field. \n\nI have a few suggestions and critiques for the authors to address:\n\n-\tCan we have a “weighted” version of Figure 2, say the higher-ranked architectures from the top-50 will get more weights when summed up; and in this way would we be able to observe more consensus of what relatively better models (if weighed more) tend to prefer?\n\n-\tLFISTA is a principled way to add more connections to LISTA using momentum. In this paper, the authors claimed their LWA to be better than momentum-based averaging in NAS. I wonder what will happen if replacing the momentum connection in LFISTA with the LWA way: will LFISTA performance improve or degrade?\n\n-\tI remain to be skeptical about the last LADMM example. It is rather unclear to me WHY the learned connectivity patterns from LISTA should transfer to LADMM? Perhaps, that implies some general idea of how dense connectivity could be properly injected in a sparse regression task. I would request to see comparison results from (1) adding dense connections only in the latter half layers; and (2) adding random connections, but with the same total connected percentage as the LISTA pattern. If either 1 or 2 can perform on par or better than the transferred LISTA pattern, the authors should consider tuning their claims to be more specific about what really matters here, than just saying vaguely about “transfer”. \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper initially received mixed ratings, with one reviewer strongly supporting the paper given that the idea of combining unrolled algorithms and NAS is new and interesting, and one reviewer not convinced by the significance of the results. His/her main concern was the use of synthetic data only, which is not realistic. This was a legitimate concern as the performance of sparse estimation algorithms can change drastically when there is correlation in the design matrix. See for instance, the benchmarks in 
F. Bach, R. Jenatton, J. Mairal and G. Obozinski. Optimization with Sparsity-Inducing Penalties. 

The rebuttal addresses this concern in a satisfactory manner and the area chair is happy to recommend an accept.
Decision: Accept (Poster)