Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors investigate the asymptotic behavior of unrolling applied to dictionary learning. The applicability of unrolling to dictionary learning results from the circumstance that dictionary learning can be reformulated in terms of bilevel optimization, where the lower-level (or inner) problem is a sparse coding problem (in the LASSO case considered here). Unrolling means to replace the argmin in the lower-level problem with the $N$-th iterate of a suitable optimization algorithm. Gradients of the upper-level loss can then be computed by means of backpropagation through algorithmic iterates. The authors study the behavior of resulting gradients depending on $N$ and draw a comparison with alternating minimization. They find that unrolling constitutes a scalable alternative to alternating minimization, where unrolling a relatively small number of iterations or using truncated backpropagation is favorable to ensure stable approximate gradients.
main_review: From my point of view, this paper is well-written and the presented analysis is interesting in the context of a recently growing body of work on unrolling. It provides a rigorous theoretical investigation and justification of practically observable phenomena.

I only have one minor point which can hopefully be clarified. Maybe the authors can comment on the role of $L$ in Proposition 2.2. Is it correct that $L$ is at the same time the row dimension of $D$ and a constant to estimate convergence speed?
summary_of_the_review: I think that this paper should be accepted. As far as I can see, the presented results are relevant and correct. However, I did not check the proofs in the last detail.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors theoretically study the performance of dictionary learning using "unrolling" based methods. As opposed to alternating minimization (AM) which switches back and forth between dictionary estimation and sparse recovery, the paper writes down the target dictionary as the solution to a bi-level optimization, where the "inner" optimization is approximated by unrolling with N steps. The main contribution is an approach (along with careful analysis) of computing the subgradient for the outer optimization, and experiments to show that this method works on synthetic and real datasets.
main_review: Pros:
- The topic is important and timely.
- Unrolling optimization algorithms and coupling them via backpropagation is a natural direction being pursued in several application domains. It is nice to see some careful analysis for this specific context (dictionary learning).
- The paper is nicely and clearly written.
- The experiments are thorough and well conducted.

Cons:
- The significance of the proposed method (and analysis), and overall relative contributions to the state of the art, is somewhat unclear.
- Theoretical analysis of dictionary learning is a well-studied problem (with all kinds of running time and sample complexity guarantees).
It will be helpful to precisely position the quantitative guarantees (Theorem 2.4, Prop 2.6) in the literature whether there is any particular benefit or drawback of computing the (outer) sub-gradient over, say, AM or other techniques.
- Backpropagation through the solution of sparse recovery has been already done before (by Bertrand et al, ICML 2020), so a clear comparison with this previous approach (and discussions of pros vs cons of backpropagation through unrolling) will be beneficial.
- The experimental results in Figs 3/4 don't really show significant improvement over AM. It may be helpful to illustrate what lessons can be learned here. 
- Since the MEG application addresses convolutional DL, it may be helpful to address whether variations of the analysis approach is applicable to the convolutional case.

---

Thanks for your response and for clarifying my questions regarding novelty. Bumping my score up to 6.
summary_of_the_review: This nicely written paper theoretically studies the dynamics of dictionary learning via unrolling + backpropagation style training. However, the authors could consider contrasting the results with the existing literature and clearly articulating how/where unrolling-style training is better or worse than the current of the art.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies dictionary learning where assumes that data can be represented as a linear combination of a few atoms of a matrix called dictionary. Traditionally, one way to approach the problem is to set up a min-min (bi-convex) optimization problem known as lasso or basis pursuit and solve it through alternating minimization (alternate between a sparse coding step and a dictionary update). The paper compares gradient based alternating minimization which uses an analytic gradient (given the code estimate, compute the gradient) to unrolled-based dictionary learning which uses backpropagation (automatic differentiation) through an iterative algorithm estimating the code (inner problem) to compute the gradient for update of the dictionary. This paper borrows results from (Ablin et al., 2020) that had studied min-min optimization problems when the objective functions are smooth, differentiable, and strongly convex. Specifically, solving lasso iteratively through ISTA or FISTA, after support selection, with some assumption on the dictionary, the problem of this paper is reduced to the strongly convex case of (Ablin et al., 2020). Hence, the results follow. Their contribution that makes their paper different from (Ablin et al., 2020) is the study of the Jacobian and instability of the convergence prior to support selection. This very same model (dictionary learning through unrolled algorithms) have been already studied theoretically by [1] (which is missing in the citations) and empirically in the context of convolutional dictionary learning by this paper (Tolooshams et al., 2020) that they cite.
main_review: Pros: The paper is written clearly. They study an interesting problem. Given the summary above, the stability analysis of the Jacobian and insights of limited-depth backpropagation to improve stability is new and of interest (proposition 2.5). The authors have provided comprehensive numerical results along with real applications to support their theories and claims. The visualization of loss landscape is interesting and has not previously explored for dictionary learning.

Cons: Given (Ablin et al., 2020, Tolooshams et al., 2020, and [1]), the novelty of the paper is incremental. Specifically, proposition 2.2 is known results from Ablin et al., 2020. Given the support and uniqueness assumption of the code, the reconstruction loss is strongly convex, and the optimization is reduced to the case in Ablin et al., 2020. Hence, proposition 2.3 follows. Stochastic CDL using unrolled networks has been previously explored in (Tolooshams et al., 2020) in the context of spike sorting and image denoising. Theoretical analysis and comparison of g1 and g2 for dictionary learning is known from [1].

The authors must clearly indicate their contributions and how their work differs from (Ablin et al., 2020, Tolooshams et al., 2020, and [1]). An additional analysis to make this work different from prior works can be providing dictionary recovery type of results similar to [2]. Overall, a better organization of the paper is recommended. See my detailed comments below. 

- There are some statements that are not fully supported and are not completely accurate.
	- For example, In "Gradient estimation in dictionary learning" paragraph, the authors mention that " ... complete theoretical analysis of these problems are arduous". It is not clear what that means. Indeed, [2] is missing where it studies gradient-based alternating minimization for dictionary learning and provides convergence guarantees.
	- The statement on "... computing optimal sparse codes at each gradient step is unnecessary to recover the dictionary" is not precise. Indeed,  one factor that is crucial is sparsity of the code.
	- The statement before Section 3 is not generally true. For example, the instability issue does not exist for the case of strongly convex function or a another loss function.
	- The statement "we notice that there is no gain in the usage of DDL for the minimization of F_N without learning the steps sizes" seems to be contradicting the whole idea of "a better gradient estimation with DDL compared to AM". Elaborations needed.
	- The statement "... taking sub-windows of the full signal and performing SGD ..." is not precise. It depends whether you define a global loss function over the whole image or local for each patch.
	- The authors refer to the dictionary learning problem as non-convex. However, a more accurate statement is "bi-convex".

- How can you guarantee that invertibility of D^TD on the support stays along the whole iterations of alternating minimization?

- In dictionary learning, you usually learn the dictionary for a finite set of examples. However, (1) does not reflect this and aims to learn D for only one example y.

- The proof of proposition 2.2, the authors should clearly cite and highlight that Proposition 2.2 is a result from Ablin et al., 2020.

- How is lambda chosen to guarantee dictionary recovery in the numerical examples given the data generation of y = Dx? Given the overcomplete dictionary, very low lambda may result in false positive in support recovery which will affect the dictionary recovery result. The value of lambda is indeed crucial at the presence of noise to avoid noise overfitting.

- Experiments: 
	- The paper has skipped a lot of experimental details in the main text and included only in the supp. Here are some that is recommended to be included in the main. How many iterations is "full"? At what iteration of the dictionary learning, Figure 1, 2, 3, 4 are based on (i.e., at dictionary initialization, after convergence, etc.)? Please elaborate what DL-Oracle is? How do you compute the optimal loss?
	- Why the dictionary error in Figure 4 (right) does not go to zero, and if their theory and analysis can explain that.
	- How to you define D of interest used in S(C)?
	- In Figure 5, do the authors train with various N values or train with the max N and look into the denoising performance given the code estimate at iteration n (i.e., Dx_n)?
	- What is the PSNR of the noisy image?
	- Intuitively, you may expect to find a trend in performance as you move from 100 batch size (which is not very low) to full batch. However, Figure 5 does not show such trend. Is there any insight for this?


- Other comments:
	- In the introduction, it is missed to mentioned that n  >> m.
	- "we propose to study the correlation between the gradients ...". It is not clear how we can show dictionary recovery given such comparison.
	- In (6), does y entails the entire data? Is there a notion of # of examples?
	- The change of y-axis from Figure 4 to 5 is confusing. Recommend to use the same x-axis on Figure 5 (left) as in Figure 4.
	- What is the SNR for when the noise variance is 0.1?
	- What are the properties of the dictionary and code, in addition to lambda, that can make support selection faster?
	- Recommend to differentiate between L in proposition 2.2 and 2.3 which are different.

- There are various typos and change of notation:
	- What is matrix A? there are numerous places that we see AD.
	- D has size of m x n but also n x L.
	- S is used once for the support and another time as a matric for dictionary error.
	- In the proof of Proposition 2.1, argmin must be over D \in C not D in general. In addition, z must have dimension m not L.

[1] B. Tolooshams and D. Ba, "PUDLE: implicit acceleration of dictionary learning by backpropagations", 2021.

[2] N. Chatterji and P. Bartlett, "Alternating minimization for dictionary learning: Local convergence guarantees", 2017.


------------
after discussion

See discussion on "Revision of the paper" comment initiated by the author's for my updated review. I hope the authors find my overall comments and the discussion useful in improving their manuscript. My main concern had been in relation to prior work and its novelty. The authors have addressed this with proper citation and additional explanation in the intro. I have updated my rating accordingly, increased the technical novelty to 3 (given the focus of the paper on the regime before support identification), however still kept the empirical novelty to 2.
summary_of_the_review: The paper contains some new results compared to prior works (stability analysis of the Jacobian and limited-depth backprop). However, the papers lacks novelty given the works from Ablin et al., 2020, Tolooshams et al., 2020, and [1] (see above for details). Given the current formulation, results, and version of the paper, the paper's contributions do not distinguish itself from prior works. Hence, I do not recommend an acceptance of this paper. I hope that authors find my comments helpful and can address my concerns detailed in the review.

------------
after discussion

The authors explained how their work with focus on instability of the Jacobian and analysis prior to support identification distinguishes itself from prior studies. Given this and the additional citations, I have increased my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper present an efficient unrolling scheme for finding an approximate solution to the optimization problem arising from sparsity-based dictionary learning. Some asymptotically analysis on its gradient is presented and the method is also tested on analyzing MEG signal.
main_review: *Strong points*

1. The technical writing of the paper is fairly well. The derivation can be followed without too much effort.

2. The paper presented an quite detailed discussion on unrolling scheme related to deep dictionary learning (DDL) which can be interested to the people working on DDL.

*Weak points*

1.  The applicability of the presented unrolling scheme is rather limited. It is only applicable to the problem motivated from a convex formulation of sparse coding, while a majority of the dictionary learning is using non-convex sparsity-regularization term such as -norm.

2. Its advantage over existing optimization methods e.g. K-SVD, proximal alternating method, and proximal alternating linearized method (PALM) for dictionary learning, is neither justified in theoretical analysis nor in experimental evaluation.

3. Experimental evaluation is limited with important missing information.

*Comments and Questions*


1. The hard part in dictionary learning is about the efficient treatment of non-convex constraints such as orthogonality or normalization. Are these treated using Lagrangian multiplier? if one want to call the proposed scheme for optimization model of dictionary learning

2. In Proposition 2.2 and 2.3. The results says there exist  such that the conclusion holds true. It seems that  is the cardinality of dictionary. Is this a typo, or they are the same.

3. While the proposed scheme is applicable to a specific learning scheme for MEG signal, it is not convincing enough to claim it is computationally efficient. The scale of such a problem is well handled by the traditional methods such as K-SVD, PAML.

4. In general, dictionary learning is not well-defined without additional constraints on the dictionary atoms, there is no mention of such constraints in the experiments.



summary_of_the_review: Numerical scheme for solving the non-convex problem related to dictionary learning has been extensively studied. For example, proximal alternating method and proximal alternating linearized method. The hard part indeed lies in efficient and effective estimation of dictionary with non-convex constraints. The proposed unrolling scheme does not address the true bottleneck of the problem. The asymptotic analysis presented indeed are rather the application of existing available techniques. Numerical experiments on MEG signals are also too limited to show its practical advantage
review_title: null

Meta-review: The paper proposes an unrolled algorithm to solve the l1-norm formulated dictionary learning problem, and focuses on the number of unrolling steps. It shows that it is better to limit the number of unrolling steps, and this leads to favorable performance over the alternating minimization baseline. The method can also be adapted to scale to very large datasets.

Most reviewers were positive or became positive after the rebuttals.  Reviewer njnY was still concerned about some issues, such as constraints and the choice of the l1 model over the l0 model; there also may have been confusion about unit sphere vs unit ball constraints.  However, given the recommendations of the other reviewers and my own opinion, I think the paper is a worthy contribution, and the point about not unrolling too deeply is an important one that is worth highlighting.
Decision: Accept (Poster)