Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper establishes state evolution analysis of multi-layer approximate message passing algorithms used to find an input vector from multi-layer noisy measurements (or finding the latent code of generative models) with random convolutional layers or random Gaussian layers.  The proof is based on writing random convolutional layers in terms of random Gaussian matrices using permutation matrices (Lemma 4.3). The proof points to a connection between convolutional matrices and spatially coupled matrices in coding theory. The results are numerically verified for linear and multi-layer cases. 

strengths_and_weaknesses: **Strengths**

* Applying state evolution analysis in deep learning context is very interesting direction, which is explored here. Similarly, spatially coupled matrices and related theoretical works are an important and rich area of coding theory, and the connection with coding theory opens up an interesting perspective. 
* The paper is in general well written and covers related works in a clear and adequate way.
* The proofs and derivations seem sound to me and tend to follow standard message passing derivations apart from Lemma 4.3. I have not checked the derivations line by line.

**Weaknesses**

* The problem considered in this paper and some of the assumptions are different from typical generative compressed sensing paper (putting aside the assumptions on randomness of parameters). Please see my comments below.
* The core issue, related to the comment above, is to mix the notion of measurements and the notion of prior. Generative priors are not measurements in context of generative CS. In the paper, the layers of the generative model are measurements with their measurement noise (channel noise $\zeta$ in Definition 3.3). See my comments below on the notion of channel noise.
* Practical models do not have random convolutions but trained ones. The implication of the current approach for the trained models is not clear and not discussed in the paper. 

Overall, the paper has a valuable contribution and present that contribution properly, however, the connection with generative compressed sensing in style of Bora et al is not properly established. A particular deviation from standard networks is the notion of channel noise. I think that the framework can still be relevant for generative priors by considering it as the problem of inverting a network or finding the latent code. This would require some changes in the paper and its exposition.

questions: * Regarding Definition 3.3, Generative priors do not have noise in them. Note that this is not a bias term, otherwise, the conditional distributions  like $P^{(l)}(h|z)$ are not needed. This can indicate that the paper is about multi-layer measurements and not generative priors. The authors should comment on what happens if the channel noise is assumed to be zero or non-random. If I am not mistaken, the analysis should remain valid (at least in $y=Ax$ case, where the Onsager correction disappears).  


* The problem description of the paper is bit confusing specially when the connection with generative prior is mentioned. Generative priors  are used to parametrize a signal $s$ using $s=G_\theta(x)$, and then solve an inverse problem $y=As$ using it, for example by gradient descent on $\Vert y-AG_\theta(x) \Vert_2^2$.

The authors. However, mention: “one seeks to recover a data signal $x_0$ given access to measurements $y_0 = G_\theta(x_0)$”. This seems to combine the generative prior and measurement model.  The measurements are typically of form $y=Ax$; one can try to incorporate it as the last layer of the generative model, which is implicitly done by the authors. See Page 1, and the choice $\phi(z)=z$ which means $y=Wh$. However, this is not typical generative compressed sensing setup.  As I reflected in my summary, the paper can be seen as finding the latent code of a generative model, which can be useful in context of generative compressed sensing. In any case, there is a subtle difference between these cases, and the authors can comment to clarify it. 

* As far as I can see Manoel et al. 2017 consider a general random matrix with i.i.d. entries and not only Gaussian (in contrast with the claim in page 2). However, the matrices are still unstructured. It is good if the authors replace the term “dense Gaussian” with a more general term, say unstructured random matrices.

* The last paragraph of “Related Work” section: the notion of stable training, mentioned in this paragraph, is a bit convoluted and ill defined. The stability issues of training GANs is very different from covariate shift related stability handled by batch norm. These are different notions of stability. Besides, I do not see the relevance of this discussion for the rest of the paper. 

* On flow based models, it is better to cite the original work of Rezende et al 2015 and Dinh et al. 2015 and then mention follow up works like GLOW, RealNVP.  

* Note that Bora et al do not only consider convolutional models. They also use MLP variants of generative priors (VAEs).  
limitations: The main limitation of the paper is the way it connects with existing works on generative priors.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of estimating a signal vector from an observation obtained via a multilayer convolutional model. The weights defining the convolutional model are assumed to be random (and known). The main contributions are an AMP algorithm for signal estimation and a theorem proving that state evolution accurately predicts the performance of AMP on this model.  Numerical results, presented for synthetic settings, show good agreement of  empirical performance and state evolution predictions.
strengths_and_weaknesses: The technical contribution of extending the multilayer AMP and state evolution from iid Gaussian weight matrices to a specific class of random convolutional matrices is a nice one. The proof technique is clever: it uses permutatation matrices to shuffle the weight matrices so that the correlated entries are in separate blocks, and then invokes the graph-based AMP proposed to define a matrix-valued AMP for the permuted matrix.  The problem setting is a bit artificial since assumes that the weights are random (rather than learned from data), but in my opinion the novelty of the proof technique is a nice contribution. 

A weakness of the paper is the presentation. The paper is dense, some of which is due to the notation required to defined the convolutional matrices, but the notation is inconsitent and sometimes confusing. Key results and their implications should also be discussed in more depth to aid understanding. More details in the "Questions" section below. 


questions: -- It is mentioned in the abstract and the introduction that the state evolution equations for the MCC model are the same for as the iid Gaussian case, upto rescaling. I find this surprising based on an analogy with spatial coupling, where AMP with spatially coupled matrices has a different state evolution from the iid Gaussian case. The authors should discuss this point after Definition 4.1/Theorem 4.2, and if possible, give some high-intuition on why the two SEs are the same.

-- The blue shaded parts in Fig. 2 are confusing.  It's not clear why kP entries from the matrix on the left are connected to a single one on the right.

-- the notation is Definition 4.1 (State evolution) is inconsistent with the theorem below. One uses m and \hat{m}, while the other uses \kappa and \hat{\kappa}. Do these refer to the same quantities?

-- To have a state evolution result that can applied to compute asymptotic loss, like MSE, the test functions in Theorem 4.2 should also take as arguments h^l/x or z^l. Please also refer to the assumptions (on x and the noise) in Def. 3.3 in the theorem statement.

-- In the definition of the multilayer model (in the display above eq. 2), the same noise variable  \eta is used for each layer. If the \eta's in each layer are indepdendent, please make this clear.

-- The noise level \eta in the simulations is chosen to be 10^{-4}, extremely small. Is this required to get a good match between empirical results and SE at reasonable dimensions?

-- Below eq. (2), could you clarify whether h^L is taken to be x? 

Typos: 
l.33 : distributions --> distribution;   l.206: should be "iteration (4)" -- add parentheses around 4.
limitations: The random convolutional model is simplistic and omits many aspects of real convolutional networks, but the authors acknowledge this.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a theoretical study on the multi-layer approximate message passing (ML-AMP) algorithm with sensing matrices in some of the layers being multi-channel convolution, which extends previous results with regular 2D sensing matrices in all layers. The main result is the state evolution equations presented in Sec. 4, derived under asymptotic limits on the shape of convolution matrices. Experimental evidence shows that the theoretical results align well with the simulation results.
strengths_and_weaknesses: **Originality**

As the paper explains, there is existing work on the analysis of ML-AMP for regular (2D) sensing matrices. The novelty of this work lies in extending such analysis for the case where the sensing matrices are convolutional.

**Quality**

The paper seems to be providing a good quality theoretical result that aligns well with the simulation results, even though the analysis concerns an asymptotic case only.

**Clarity**

I find the paper to be very well written, with an informative introduction, sufficient background before presenting their main result and so on.
questions: The paper may benefit from a discussion on why their theoretical result is of practical interests.
limitations: This is discussed at the end of the paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The submitted paper addresses multi-layer aproximate message-passing (ML-AMP) for signal recovery under multi-layer generative neural network priors (1), in which the activation (or denoiser in compressed sensing) is separable and the sensing matrices are sampled from the multi-channel convolution ensemble in Definition 3.2. ML-AMP was originally proposed by Manoel et al. [2017] for dense sensing matrices with zero-mean i.i.d. (Gaussian) elements. The submitted paper generalizes the existing ML-AMP to the convolutional case in Definition 3.2. 

The main contribution is rigorous state evolution of ML-AMP for the multi-channel convolution ensemble, i.e. Theorem 4.2. The proof is fully based on graph-based AMP and its rigorous state evolution by Gerbelot and Berthier [2021]. The main technical contribution is Lemma 4.3, allowing us to transform any multi-channel convolution matrix into block-convolutional matrix with dense, zero-mean, and i.i.d. Gaussian blocks via permutation. When separable activations, i.i.d. signals, and i.i.d. channel noise in (2) are assumed, all  permutation matrices are absorbed into messages in graph-based AMP via the change of variables. Since graph-based AMP is general enough to model ML-AMP, ML-AMP for the multi-channel convolution ensemble reduces to a special case of graph-based AMP. 

The state evolution result is also justified via numerical simulations for artificial data. No numerical simulations are presented to show the advantage of the multi-channel convolution ensemble against conventional dense Gaussian ensemble or practical usefulness of ML-AMP for real data.
strengths_and_weaknesses: Strength
The strength is the proof of Theorem 4.2. From a technical point of view, the main part of the contributions to prove the theorem might be in Gerbelot and Berthier [2021]. Nonetheless, it should be significant contributions to understand graph-based AMP and apply its framework to signal recovery under multi-layer generative neural network priors. If the framework were old results, such as Bayati and Montanari [2011] or Rangan et al. [2019], I would not have positive impression since they are (well) known in the NeurIPS community. However, graph-based AMP is state-of-the-art message-passing and therefore not fully understood in the community.  

Weakness 
As pointed out in Summary, the weakness of the submitted paper presents no numerical simulations to show the advantage of the multi-channel convolution ensemble against conventional dense Gaussian ensemble or practical usefulness of ML-AMP for real data. The paper only presents numerical simulations for artificial data with the so-called Bernoulli-Gaussian prior. At least the authors could add numerical comparisons between the multi-channel convolution ensemble and conventional dense Gaussian ensemble for artificial data. 
questions: --(A1) assumes pseudo-Lipschitz activations of any finite order while conventional state evolution by Bayati and Montanari [2011] postulated the Lipschitz-continuity. When pseudo-Lopschitz activations are used, in my understanding, the boundedness of higher-order signal moments is required as the iteration t increases. Eventually, we need to assume the boundedness of all signal moments. Do not the authors need to assume any regularity conditions on the signal prior, such as sub-Gaussian? 

--The terminology "line" is a bit unclear. Clarify whether it means column or row. 

--\tilde{W} in Lemma 4.3 is not displayed appropriately. It should be presented like (57) in Appendix A. 
limitations: The submitted paper is theoretical and therefore has no negative social impacts.
review_title: null

Meta-review: metareview: This paper considers finding an input vector from multi-layer noisy measurements. This can alternatively be thought of as finding the latent code of generative models. The authors analyze the state evolution of a multi-layer multi-layer approximate message passing algorithm. The main technical idea is relating random convolutional layers to Gaussian ones using permutation matrices and then utilizing a connection with spatially coupled matrices in coding. The authors also provide numerical evidence. Overall all the reviewers were positive but did raise some concerns about the model bing not realistic since the convolutional layers are not trained. I agree with the assessment of the reviewers. I think the paper is interesting and the connections and theoretical results are nice. Therefore I recommend acceptance. However, I do have some concerns about the model studied. I also have some concerns about the theoretical analysis as it is sometimes difficult to differentiate what is fully rigorous and what is based on statistical physics conjectures. In your final manuscript please clarify which parts are fully rigorous (perhaps all) and which parts rely on conjectures that have not been fully proved.

confidence: Certain
Decision: Accept