Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper extends the previous theoretical studies around convergence of subgradient descent (Algorithm 1 from [20]) for ReLU generative priors to cases where the generative model is not necessarily expansive. The result relies on the weights being drawn from i.i.d. Gaussian matrices and assumes network widths and measurement numbers are proportional to input dimension (See Theorem 1.1, conditions 1 and 2). The results extend to other inverse problems like phase retrieval, denoising and spiked matrix recovery. 
Theorem 5.4 provides the result for random Gaussian matrices and weights, and Theorem 4.4 provides a more general result for any matrices satisfying RRIC and R2WC. Lemma 5.1 is well known in the literature. Lemma 5.2 and 5.3 are proven in the appendix and together with Theorem 4.4 imply Theorem 5.4.
The extensions to phase retrieval, denoising and spiked matrix recovery are given in the supplementary materials, although the proofs are not explicitly given. 

strengths_and_weaknesses: **Strength**

* The paper improves the analysis of [22] (also [21]) and gets much better dependence on the number of layers $d$ and removes the dependence of width of layer $i$ on the layer index $i$. 
* R2WDC is weaker that WDC condition, and nonetheless provides better results. 
* The proof builds on many previous works, for example [18], [20], [22], and, based on my rapid read, is sound and well presented.
* The contribution of the paper, namely relaxing the constraints on the network further and introducing R2WDC, is a good step forward in this analysis.

**Weakness**

* Some important limitations of the paper are not mentioned clearly by the authors, and some of the statements are not fully precise (see some comments below – for example, it seems to me that the sample complexity has drastic dependency on $d$; also on information theoretic optimality.).
* The authors do not extract relevant guidelines from their theory. Practical generative models are trained from data. The paper considers generative models with random Gaussian weight, which is fine to derive the theoretical analysis. Even if the results are not directly applicable to practical networks, it is important to extract theoretical insights from the developed theory (like the authors’ comment on denoising effect of Algorithm 1 and generative priors). This is missing from the paper. See also my comments on gradient descent issues for trained generative priors.
* Having numerical results, for instance similar to those in [20], can always help communicating the paper’s contribution better.
* The paper could have been organized better by removing some discussions to the supplementary materials and presenting first the core idea behind the proof (similar to [20]).

questions: 
* [21] seems to be the extended NeurIPS version of workshop paper [22]. It is probably better to use this version instead of [22]. 
* I suggestion expanding on the denoising effect of the algorithm 1 as mentioned in page 3, line 89. This is an interesting consequence. 
* A relevant question, from practical perspective, is to see if one can verify R2WDC for a pre-trained network (not a random one). It is known that verifying RIP property of a matrix is NP-hard. It would be interesting if the authors can comment on it. 
* Gradient descent-based methods used in context of trained generative priors suffer from lack of convergence and usually require occasional restarts. This is in contrast with the current claims of optimality in the paper. This merits some comments from the paper. Which assumption in the theoretical framework is likely to be violated for this to happen? Gaussian assumption is a good candidate, but it is just an instance of distributions satisfying R2WDC. Is it related to details of Algorithm 1, for instance the check $f(-x_t)<f(x_t)$? Some comments on this can be helpful for the paper.
* In page 2, the authors mention that the method of [20] is information theoretically optimal given $m=\tilde{\Omega}(k)$. As far as I can see [20] does not claim information theoretic optimality. Why is this the case? Is there any work providing lower bound on the sample complexity for random generative models (for example like Gelfand width analysis in compressed sensing)? A similar claim is made in the final part of the paper.  
* Please add a few sentences to the paper on how the subgradient can be computed in practice. Of course, for smooth generative models, this is not an issue, but for ReLU networks, the question is whether the gradient descent as implemented in backprop is a good proxy.
* I suggest rephrasing the mention of Rademacher’s theorem in line 149, page 4. The implication of Rademacher’s theorem, roughly, is that Clarke’s subdifferential is well behaved since the $\text{dom}(\nabla f)$ has full measure.  With current phrasing, this point is not clear.
* I suggest adding the intuition behind the matrix $Q_{r,s}$ to the main paper (for example by mentioning the connection with measuring angle distortion by $x\to W_{+,x}$).
* The $\epsilon$ in Theorem 4.4 is $O(1/d^{90})$. This term would dominate the rest of terms in the sample complexity condition (11) (see Assumption A.3). Basically, $m\geq \hat{C}_\epsilon$ implies at least $m\geq d^{90}$. This is a poor dependency on $d$, although it is present in the related works too. 
* In Remark 1 and 2, it is suggested that the factors $2^d$ can be removed with the entries of $W_i$ drawn from $\mathcal{N}(0,2/n_i)$. Would not this violate the requirements for R2WDC condition?
* Apart from $\hat{C}_\epsilon$, the condition A.3 of Assumptions A has implicit linear dependence on $d$. Consider a non-expansive network with $n_i=n$ for all $i$. Then the sample complexity lower bound includes $dm$. Similar arguments can be made of assumption B.2 and for $n_i$, namely $n_i\geq k.i \log (ne/k)$. The authors should comment on this.
* Typo: in two places in the paper, RRWDC is used instead of R2WDC. 

limitations: Although the paper is theoretically interesting and a step forward, I feel that the authors can do a better job in communicating the idea, extracting useful guidelines and presenting the limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper relaxes an assumption in previous theoretical work on signal recovery with generative networks. Namely, previous work required that the generative network have constant-width layers (and before that, logarithmically expanding layers). This work shows that the generative model may preserve the signal recovery guarantees, while having layers of contracting width.
strengths_and_weaknesses: Strengths:
- Solid theoretical result on a relaxed assumption for generative model-based signal recovery.

Weaknesses:
- Motivation is lacking. The paper asserts that relaxing the assumption in question is important, as contractive layers are "often the case in real generators". However, this is stated without citation, and I am not sure it is true. Most GANs and VAEs involve constant or growing width of layers in the generative network. The only provided support for relaxing this assumption is a citation of [1]. However, I could not find this statement anywhere in the cited work. The authors did state that relaxing the logarithmically expansive width assumption was important, but that has apparently already been shown by [2, 3].

Overall, it is unclear to me how important the theoretical improvement is, as this is not my main area of expertise, and the paper does not properly motivate the contribution. However, I believe that this work provides a straightforward contribution to theory in this field.

[1] Hand, P., & Voroninski, V. (2018, July). Global guarantees for enforcing deep generative priors by empirical risk. In Conference On Learning Theory (pp. 970-978). PMLR.
[2] Daskalakis, C., Rohatgi, D., & Zampetakis, E. (2020). Constant-expansion suffices for compressed sensing with generative priors. Advances in Neural Information Processing Systems, 33, 13917-13926.
[3] Joshi, B., Li, X., Plan, Y., & Yilmaz, O. (2021, October). PLUGIn-CS: A simple algorithm for compressive sensing with generative prior. In NeurIPS 2021 Workshop on Deep Learning and Inverse Problems.
questions: Please answer the motivation question above.
limitations: No.
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 presents a theoretical analysis for signal recovery with non-expansive generative networks. The main results suggest that given a random Gaussian generator, any signal in its range can be reconstructed from Gaussian measurements as long as the number of measurements and the width of all layers are proportional to the size of input layer. This result improves upon the earlier analyses that require width of layers to expand. 
strengths_and_weaknesses: Strengths. 
- The paper presents a new analysis for the general signal recovery using generative priors. 
- The main contribution is in relaxing the conditions on the width of the network layers. 

Weaknesses. 
- This analysis makes a strong assumption that the network has Gaussian weights. This is quite far from real settings where the network is learned from some data. Authors acknowledge that as a limitation. It will be good for the community to start analyzing this real problem. 



questions: I did not check the derivations for accuracy, so I do not have any specific question at this point. 
limitations: n/a
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 considers the problem of inverse problems with generative priors. Prior work has shown that gradient descent recovers the ground truth in poly-time under the assumption of generative models with random weights and sufficient expansion. As real world networks do not satisfy the expansivity assumption, recent work has tried to relax the assumptions. The most relevant prior work [22] allows for contractive layers (i.e., the size of layer $i$ can be smaller than layer $i-1$), but requires the size of layer $i$ to grow exponentially with $i$. This further implies that the number of measurements required for compressed sensing / phase recovery grows exponentially with the depth of the generative model, while traditional results only required linear / quadratic dependence on depth.

This work shows that gradient descent converges in poly time, and only requires the size of each layer and number of measurements to grow polynomially in $d$. The results are novel and significant, and is in my opinion a valuable contribution to the field.
strengths_and_weaknesses: Strengths:
+ This paper considers an open problem in the field of solving inverse problems with generative priors. In my opinion it is sufficiently important and significant.


+ The analysis proposes a new condition, called the Range Restricted Weight Distribution Condition (R2WDC). This condition is seemingly the key to prove that contractive generative models can also be used. To the best of my understanding, the traditional WDC condition required an isometry between each successive layer _for all_ vectors in $\mathbb{R}^{n_i}$, which led to the requirement that $ n_{i+1} \geq c_i n_i \log n_i$. Under the new R2WDC condition, this isometry needs to only hold for vectors in $\mathbb{R}^{n_i}$ that can be generated by the neural network, which allows for the possible contraction between the layers. The idea is intuitive, and I think the paper provides a good explanation for its success.

+ The results are clearly stated and compared to existing results.

Weaknesses:
- In theorem 4.4, the number of steps $T$ is bounded by $2^d$, which is not truly polynomial in the generator parameters. However, this can be forgiven as $d$ is typically on the order of $\log n$. 

- This is similar to the above complaint -- theorem 4.4 bounds the norm of the noise as $ || \eta || \leq \frac{||x||}{poly (d) 2^{d/2}}$. This is not a very big problem, but perhaps the claims for the denoising effect of gradient descent (for e.g., in lines 87 - 90) can be toned down considering how the noise norm must be much smaller than the norm of $x$.

- I'm not sure I agree with Remark 1 . How would the R2WDC condition be satisfied if you scaled the weight matrices? As a simpler counter example, if $W \in R^{m \times n}$ is such that $W_{ij} \sim N(0,1/m)$, then $||Wx|| \approx ||x||$. Now, if $W_{ij} \sim N(0,2/m)$, then you get $||Wx|| \approx 2||x||$, and it seems like the requirements in R2WDC would not be satisfied.


questions: I have no major questions or concerns-- I am listing my minor concerns as clarifications.

- Line 87 - 90: Can the authors comment on whether the $O(|| \eta ||_2)$ error in [20] appears due to the assumption that $m \approx k \log n$? 
Is there something special about the analysis in this paper that allows for the $\sqrt{k/m}$ term which does not appear in [20]? 

- It is generally assumed that phase retrieval is a more difficult problem than compressed sensing, for e.g., random generative priors require $kd \log n$ measurements for compressed sensing, but the best known results for phase retrieval require $k d^2 \log n$. I would appreciate a short paragraph on whether a similar phenomenon appears in this paper, as I think it would be an interesting open problem to find the optimal poly dependence on $d$. 

- Perhaps for ease of understanding, it is worth clarifying that the benefit of R2WDC is that it takes into account the whole generative model from layer 1 to $i$, as opposed to WDC, which only considers the input / output pair of layer $i$ without considering the previous layers.


limitations: The limitations are sufficiently stated.
review_title: null

Meta-review: metareview: This paper focuses on theoretically studying signal reconstruction with non-expansive generative networks. In short the authors show that with a random Gaussian generator, any signal in its range can be reconstructed from Gaussian measurements. This holds as long as the number of measurements and the width of all layers are proportional to the size of input layer. Compared to prior work this paper removes the requirement of expansion of the layers. Most reviewers thought the paper was interesting and thought the improved theoretical analysis was nice. The reviewers also raised a variety of technical concerns most of which was addressed during the rebuttal. I concur with the reviewers and think is a nice contribution despite some flaws and am recommending acceptance. I urge the authors to follow the details comments of the reviewers to improve their manuscript for the camera ready version of the paper.
confidence: Certain
Decision: Accept