Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper suggests a learning-based algorithm for sparse recovery, where the goal is to recover a latent sparse parameter vector from observations (say, in the basic setting of sparse linear regression, the observations are noisy linear measurements). The algorithm is based on "unrolling" an existing non-learned iterative algorithm, which means fixing some number of iterations and learning some of the algorithm's internal parameters by optimization on an existing training dataset of related problems and their known solutions. The paper theoretically studies the capacity and generalization properties of the proposed algorithm, and presents some experimental results on synthetic data.
main_review: The paper is generally well-written. The idea of the algorithm, its precise details, and the assumptions and claims of the theoretical analysis are all presented clearly and in detail. The approach of the algorithm makes sense and seems potentially promising, and targets an important set of problems.

The weakest point of the paper is the experimental section. The experiments are restricted to synthetic data of a limited scale, and to perhaps the most basic sparse recovery setting (linear regression, while the introduction makes the point that the method is more broadly applicable). While I appreciate the theoretical analysis and its validation on synthetic data, the utility of learning-based algorithms hinges to a significant extent on whether they can be substantiated on real data, where the correspondence between the training and test data is not as structured and clear as in the synthetic case. At present, it is hard to say from the paper whether the proposed method is plausibly useful in practice.

There seem to be parts of related literature that are not mentioned. I am not sure if they are directly related, and perhaps the authors could comment on it in the response. These include some additional learning-based algorithms for latent parameter recovery (e.g., [a,b], though they move away from sparsity), and generalization bounds for learning-based algorithms [c,d].

[a] Bora, A., Jalal, A., Price, E. and Dimakis, A.G., Compressed sensing using generative models, ICML 2017
[b] Wu, S., Dimakis, A., Sanghavi, S., Yu, F., Holtmann-Rice, D., Storcheus, D., Rostamizadeh, A. and Kumar, S., Learning a compressed sensing measurement matrix via gradient unrolling, ICML 2019
[c] Gupta, R. and Roughgarden, T., A PAC approach to application-specific algorithm selection, SICOMP 2017
[d] Balcan, M.F., DeBlasio, D., Dick, T., Kingsford, C., Sandholm, T. and Vitercik, E., How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design, STOC 2021


Post-rebuttal update: The authors' response and revisions of the paper answered my main concerns, primarily the lack of empirical evaluation on real data, which they have now added. As a result, I have revised my numerical assessment of the empirical merit of the paper, and have upgraded my overall score. Pending some concerns raised by other reviews, which would be resolved in the internal discussion phase, from my point of view the paper can be accepted. 
summary_of_the_review: This is a well-written paper that presents a plausible approach to a meaningful problem, but falls short in empirical validation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a learning-based sparse regression or compressed sensing algorithm. The paper assumes that a supervised dataset of sparse recovery instances is available and uses the dataset to fine-tune the hyperparameters of a sparse recovery algorithm known as the path-following algorithm. The proposed algorithm has a recursive structure where at each recursion it needs to solve an instance of the path-following algorithm with different hyperparameters.
main_review: My first concern is that there is not enough interest or applications for learning-based compressed sensing. It is not a good assumption that there exists a supervised dataset of sparse recovery instances available for tuning the parameters of the proposed algorithm. The fact that all experiments in this paper are based on synthetic datasets and no real datasets are used in this paper confirms my concern. 

In terms of presentation, I think it would help if the authors discussed the path-following algorithm a bit since their result is based on this algorithm.

Moreover, the algorithm is recursive and each recursion of the algorithm involves running an instance of the path-following algorithm. So even after fully training the parameters, just evaluating the algorithm on an input instance is several times slower than the original path-following algorithm. The complexity is even much worse during the training phase because one needs to evaluate the whole algorithm multiple times and compute its derivatives with respect to the learnable parameters. The paper does not analyze the runtime complexity, unfortunately.

On page 5, after assumption 3.1, it is stated that condition b is weaker than RIP. It seems to me that when the loss function is least squares, then condition b is exactly the RIP.

Theorem 3.1 is somehow telling that the optimal parameters give a small error but it does not tell you how easy it is to find the optimal parameters. In particular, the parameters need to be found by solving some optimization problem but it is not even clear if this optimization problem is convex or not. If the problem is non-convex, you would only be able to find a local minimum and Theorem 3.1 would become useless. 
Furthermore, \kappa_n in Theorem 3.1 is defined ambiguously. It needs to be defined more specifically.


-------------------------------- Score after revision -----------------------

The revised version looks better now and seems to address my concerns. Therefore, I raise my score to 6.


summary_of_the_review: I think there is not enough interest or applications for learning-based compressed sensing. The fact that all experiments in this paper are based on synthetic datasets and no real datasets are used in this paper confirms my concern. 


Moreover, the algorithm is recursive and each recursion of the algorithm involves running an instance of the path-following algorithm. So even after fully training the parameters, just evaluating the algorithm on an input instance is several times slower than the original path-following algorithm. The complexity is even much worse during the training phase because one needs to evaluate the whole algorithm multiple times and compute its derivatives with respect to the learnable parameters. The paper does not analyze the runtime complexity, unfortunately.


Theorem 3.1 is somehow telling that the optimal parameters give a small error but it does not tell you how easy it is to find the optimal parameters. In particular, the parameters need to be found by solving some optimization problem but it is not even clear if this optimization problem is convex or not. If the problem is non-convex, you would only be able to find a local minimum and Theorem 3.1 would become useless.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a learning-to-learn algorithm for the classic problem of compressed sensing. The algorithm is based on a deep unrolling of a non-convex optimization procedure from a prior work (Wang et al, 2014) in the literature. The paper contains some theory (for capacity and generalization) and experiments, establishing the efficacy of the algorithm. 
main_review: update
-----
I maintain my rating after reading the author(s)' response.

The approach from this paper is promising and mostly novel. The paper is generally well written. Overall I recommend accept. I have a few concerns regarding the theoretical claim and experiment.

Strong points 
-----
1. The paper tackles a classic and important problem (i.e., compressed sensing), and the learning-to-learn approach should be a good step in this direction.
2. The framework from the paper appears flexible enough to handle other sparse estimation problems. So the work may lead to future impact. 
3. The author(s) gives some theoretical justification of their procedures. 

Concerns
-----
1. In abstract and later in the intro, the author(s) claims that "our analysis makes novel connections between the generalization ability and algorithmic properties such as stability and convergence". The author(s) should be careful about the scope of this claim. The connection between algorithmic stability and generalization is textbook classic. The paper applies this framework to the specific setting of learning-based sparse recovery. 

2. Theorem 3.1 appears somewhat weak. The claim is that "there exists a set of parameters θ .... such that the estimation error is small". However, these parameters are also learned. Is there any (theoretical) justification why the algorithm would find such good parameters θ?

3. In Section 4 on generalization, the author(s) should clarify the distributional assumptions here. Are we assuming random iid design? Is $\beta^*$ also distributional? (Note that Assumption 3.1 is a set of deterministic conditions.)

4. The paper does not compare PLISA with other classic algorithms in the sparse recovery literature, for example, convex relaxation or linear sketching methods. It would to nice if the experiments are more comprehensive. 

Other minor issues
-----
1. There has been a few works on unrolling or differentiable learning of classic algorithms. For example, https://arxiv.org/abs/1910.13984 and https://arxiv.org/abs/1903.08850. This is very closely related to the nature of this work. The authors should make a reference.
2. I am not familiar Wang, et al (2014). It would be helpful if the author(s) could give a quick rundown of the algorithm therein, perhaps in the appendix. What are the main features of Wang, et al (2014) that PLISA borrows?  
summary_of_the_review: The paper aims at an important problem and provides a novel solution. The theory and experiment are generally solid. I believe the work could have future impact.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents a deep unrolling method that unrolls the path-following algorithm of Wang et al. (2014) for learning to regularized sparsity estimation. Theoretical guarantees on sparsity recovery and generalization performances are provided. A simulation study is carried out to verify the theory and effectiveness of the proposed algorithm. 
main_review: 1. Strengths:

+ The idea of unrolling path-following algorithms for learning to optimize hyper-parameters (such as learning rate, regularization modulus and mixture weights of regularization components) is somewhat novel as far as I can see.

+ The analysis is theoretically sound and the writing style is clear and clean. 

2. Weaknesses

- My main concern is about the relevance and strength of theory. There are two types of guarantees established in this work on parameter estimation error and generalization gap bounds respectively. As shown in Theorem 3.1, the sparsity recovery analysis basically reveals that there exists a set of hyper-parameters under which the proposed PLISA algorithm is able to efficiently and accurately recover the underlying true model. This result seems not surprising at all as PLISA by definition naturally mimics an existing iterative sparse recovery method with similar guarantees. More importantly, IMO the current convergence/estimation analysis has little to with the optimization of hyper-parameters $\theta$ which is of central interest of deep unrolling but unfortunately totally ignored in the present study. In Theorem 3.1, the existence of the desired set of parameters is lack of transparency in the sense that it relies on another set of conditions as defined in Definition C.1 which are fairly stringent especially the condition (iii).  

- Continuing the above comment, the generalization analysis is also of limited interest and novelty. First of all, since the generalization is about the hyper-parameters involved in meta-optimization, most existing uniform convergence analysis techniques in classic learning theory are expected to work for bounding the generalization gap. Is there any particular reason to adopt the framework of Bartlett and Mendelson (2002) for generalization analysis? The technical part is relatively straightforward; it is not clear what’s new in this section of analysis, if any.

- It is unclear how to optimize the meta-parameters contained in Algorithms 1, probably via backpropagation? More implementation detail about meta-parameter update are desirable in addition to the iterative proximal gradient steps for cell objectives.

- Last but not least, I am seriously doubting the practical usage of the proposed approach to real-data sparse learning problems because it is only designed for well-defined sparsity models. An immediate challenge here is that the ground-truth sparsity models are required to supervise the meta-learning, which however are typically unavailable over the training optimization tasks! 

3. Minor comments:

- Equation (6): the general case of varying $n_i$ seems not investigated throughout. 

- The reason of introducing $\varepsilon>0$ in Theorem 3.1 is not clear. 

- Typos: P3, beside Algorithm 1: minimize  minimizes; and others. 


summary_of_the_review: The algorithm is somewhat interesting but the theory is of limited relevance and novelty. The implementation details and practical usage of algorithm are largely unclear in the current stage. 

=== Post discussion update ===

After reading other reviews and the author response, I would upgrade my rating to 5: marginally below the acceptance threshold.
review_title: null

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period.
There is consensus among the reviewers that the paper should be accepted:

-  This paper does contribute solidly to a timely topic of theoretical understanding of sparisty recovery with deep unroling. 
-  The original version had very limited experiments and only synthetic ones, which raised concerns about whether the setting is motivated and whether the algorithm works on actual real data. The revision fixed that to an extent with some experiments on real data.

Yet, there are still some concerns that we suggest to be tackled for the final version:
- The capacity analysis is carried out inside a strongly convex regime while the algorithm is advocated for nonconvex sparsity recovery (see, e.g., the Discussion at the end of Section 2.1 );
- The analysis is relatively loosely connected to the adopted fist-order optimization procedure;
- While the depth of network plays a role in the upper bound of Equation (15), its real impact on generalization gap looks quite limited.

The above are just suggestions to be looked more carefully, but there are not necessary. 

The current consensus is that the paper deserves publication.

Best
AC
Decision: Accept (Poster)