Signal Recovery with Non-Expansive Generative Network Priors
Authors: Jorio Cocola
Venue: NeurIPS 2022 Accept (2022)
Keywords: inverse problems
generative networks
signal recovery
compressed sensing

Abstract: We study compressive sensing with a deep generative network prior. Initial theoretical guarantees for efficient recovery from compressed linear measurements have been developed for signals in the range of a ReLU network with Gaussian weights and logarithmic expansivity: that is when each layer is larger than the previous one by a logarithmic factor. It was later shown that constant expansivity is sufficient for recovery. It has remained open whether the expansivity can be relaxed, allowing for networks with contractive layers (as often the case of real generators). In this work we answer this question, proving that a signal in the range of a Gaussian generative network can be recovered from few linear measurements provided that the width of the layers is proportional to the input layer size (up to log factors). This condition allows the generative network to have contractive layers. Our result is based on showing that Gaussian matrices satisfy a matrix concentration inequality which we term Range Restricted Weight Distribution Condition (R2WDC) and which weakens the Weight Distribution Condition (WDC) upon which previous theoretical guarantees were based. The WDC has also been used to analyze other signal recovery problems with generative network priors. By replacing the WDC with the R2WDC, we are able to extend previous results for signal recovery with expansive generative network priors to non-expansive ones. We discuss these extensions for phase retrieval, denoising, and spiked matrix recovery.

Signal Recovery with Non-Expansive Generative Network Priors
Jorio Cocola Harvard University
j jcocola@seas harvard. edu
Abstract
We study compressive sensing with deep generative network prior. Initial theoret- ical guarantees for efficient recovery from compressed linear measurements have been developed for signals in the range of ReLU network with Gaussian weights and logarithmic expansivity: that is when each layer is larger than the previous one logarithmic factor. It later shown that constant expansivity is sufficient for recovery. It has remained open whether the expansivity can be relaxed, allowing for networks with contractive layers (as often the case of real generators). In this work we answer this question, proving that a signal in the range of a Gaussian generative network can be recovered from few linear measurements provided that the width of the layers is proportional to the input layer size (up to log factors). This condition allows the generative network have contractive layers. Our result is based on showing that Gaussian matrices satisfy matrix concentration inequality which we term Range Restricted Weight Distribution Condition (R2WDC) and which weakens the Weight Distribution Condition (WDC) upon which previous theoretical guarantees were based. The WDC has also been used to analyze other signal recovery problems with generative network priors. By replacing the WDC with the R2WDC, we are able to extend previous results for signal recovery with expansive generative network priors to non-expansive ones. We discuss these extensions for phase retrieval, denoising, and spiked matrix recovery.
Introduction
The compressed sensing problem consists in estimating a signal y, E IR" from (possibly) noisy linear measurements
Ay. +
where A R is the measurements matrix, and R" is the noise.
To overcome the ill-posedness of the problem, structural priors on the unknown signal y, need to be enforced. One now classical approach assumes that the target signal is sparse with respect to given basis. In the last 20 years, efficient reconstruction algorithms have been developed that provably estimate s-sparse signals in RR" from O(s log n) random measurements 5 [2]
Another approach recently put forward, leverages trained generative networks. These networks are trained, in an unsupervised manner, to generate samples from a target distribution of signals. Assuming y, belongs to the same distribution used train a generative network G R R" with k < an estimate of y. can be found by searching the input & ("latent code") of G that minimizes
Work done while at Northeastern University
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the reconstruction error
- 2116 AG
I arg min fea(x) = ZER
y+ = G(
As empirically demonstrated in B.. the minimization problem can be solved efficiently by gradient descent methods. Moreover, solving 1 can effectively regularize the solution of the compressed sensing problem, significantly outperforming sparsity-based algorithms in the low measurements regime M. Generative network based inversion algorithms have been subsequently developed for variety of signal recovery problems, demonstrating their potential to outperform inversion algorithms 28 For a recent overview see [32]
based on non-lcarned (hand-crafted) priors [G 6
The optimization problem ! is in general non-convex and gradient-based methods could get stuck in local minima. To better understand the empirical success of (I. in [X] the authors established theoretical guarantees for the noiseless compressed sensing problem (17 0) where G. R + R" is
d-layer ReLU network of the form:
G(+) = ReLU(Wa .. ReLU((WaReLU(Wi:))
(2)
with W; E R 740 k, nlg n, and ReLU(z) max(z, 0) is applied entrywise. The authors of [88] used a probabilistic model for the generative network G and measurement matrix A. They assumed that each layer W, has independent Gaussian entries and is strictly expansive. Specifically holds that
n; 2 n log -ogy-d--oly(dd poly(d) for all i 1....... d.
Moreover, they considered to be a Gaussian matrix and m 2 k log poly(d). Under this proba- bilistic model it was shown in [18] that, despite its non-convexity, fes has favorable optimization geometry and no spurious critical points exist apart from x, and a negative multiple of it -Pa where Pa is function of the depth d of the network.
The landscape analysis was later extended to recovery guarantees using a gradient based method in 211. under the same probabilistic assumptions of [18]. In particular, [21] has shown that there is an efficient gradient descent method (see Algorithm in Section 3 that given as input A, G and outputs latent vector è such that [/y. G(ø)lle (11ll2). This result demonstrated that efficient recovery is possible with a number of measurements which is information-theoret optimal up to log- log-factors n and polynomials in d (m = ((k)).
Generative networks used in practice though, have often contractive layers. For example, the output of the layers near the end of the StyleGAN generators have larger dimension than the generated images 25 24 Thus, one major drawback of the theory developed in [88] is constituted by the
expansivity condition on the weight matrices ( Relaxing the condition 3 and accommodating for
generative networks with contractive layers was formulated as an open problem in the survey paper B
B2].
An initial positive result on this problem came from 10 of Lipschitz functions, the authors proved that the results of [8 21 hold true also for weight matrices satisfying n; 2 n4-1 poly(d). While not allowing for contractive layers, this condition removed the logarithmic expansivity requirement of
Using a refined analysis of the concentration
have studied the denoising and compressive sensing problem with random generative network prior in [T8 21 20), and have shown that the expansivity condition can indeed be relaxed. In 23 they have provided an efficient iterative method that given as input A, b and G, assuming that up log-factors each layer width satisfies
More recently. 222 p3
T4 2 5'k,
(4)
and the number of measurement satisfies
2 2dh
(5)
outputs latent vector à such that for y. G(x.) it holds that 11.. G 0(24
|mll))
with high probability. Notice that the condition while requiring the width to grow with the depth, can allow for contractive layers n, < 7i-1-
Thii open problem also proposed in the recent talk |1]

---

1.1 Our contributions
is natural to wonder whether the price to pay to remove the expansivity assumption is indeed the exponential factors in the depth d of the network and the use of less-standard non-gradient based iterative methods, as happens [22 23). In this paper, we answer these questions. Our main result is summarized below and provides guarantees for solving compressed sensing with random generative network priors via gradient descent method (Algorithm inn Section
Theorem 1.1 (Informal version of Theorem 5.4 Assume that A has i..d NO,, 1/m) entries and each We has i..dd (O, 1/n;) entries. Suppose that y. G(x.). Furthermore assume that, up to loy-factors,
1. 2 k. poly(d);
2. 2 k. poly(d).
Suppose that the noise error and the step size are small enough. Then with high probability, Algorithm 7
with imput loss function fes. step size a and number of iterations T =poly(dd) outputs an
estimate G(rr) satisfying [[G(xr) 122 Olv k [1lll)).
Compared to 21 and 10 our result do not require strictly expanding generative networks and allows for contractive layers. Furthermore, we show that the same algorithm proposed in (2]] has
m (1lll)) rather denoising effect, leading to a reconstruction of the target signal y. of the order O(v & than only (1 We show that this holds true even in case of deterministic noise, while [19] discuss only the case of Gaussian noise. Furthermore, the decrease in the reconstruction error with the number of measurements has also been observed for trained generative networks (see for example Bl), and here we give a partial theoretical explanation for this phenomenon.
Compared to the results of 2
we show that it is sufficient for the width of the layers well as the number of measurements to grow polynomially with the depth rather than exponentially. Similarly, compared to [33 we remove the exponential factor in the depth from the reconstruction error.
The analysis of 18 was based on a deterministic condition on the weight matrices termed Weight Distribution Condition (WDC). This condition, together with deterministic condition A (see Sec 4 for details), was shown to be sufficient for the absence of spurious local minima in ① and to be satisfied by expansive Gaussian random generative networks @ The WDC was also used in the subsequent [1 to prove convergence of Algorithm I Our main technical contribution is to show that the WDC can be replaced by weaker form of deterministic condition, termed Range Restricted Weight Distribution Condition (R2WDC), and still, obtain the absence of spurious local minima and recovery guarantees via Algorithm T We will then show that random Gaussian networks satisfying the Assumption 1. of Theorem satisfy the R2WDC.
The framework introduced in 1 was used in a number of recent works analyze other signal recovery problems with generative network priors, from one-bit recovery to blind demodulation These works considered expansive generative network priors, using the WDC and the results of 18 in their analysis. Replacing the WDC with our R2WDC we can extend the previous results in the literature to more realistic mon-expansive) generative networks. This paper details these extensions for three representative signal recovery problems.
34
27
16
15
35|
Theorem 1.2. Suppose G is random generative network as in Q satisfying Assumption 1. of Theorem L. Then Algorithm with appropriate loss functions, step sizes, and number of steps, succeed with high probability for Phase Retrieval, Denoising, and Spiked Malrix Recovery.
Our result on the denoising problem, implies similar result on the inversion of generative network. The problem of inverting a generative neural network has important applications Il 33 and has been recently analyzed theoretically [26 network can be efficiently inverted by gradient descent, even when containing contractive layers. This motivates the empirical use of gradient- based methods for inverting generative networks.
22 2
Our result shows that a random generative

---

1.2 Organization of the paper
This paper is organized as follows. In Section we introduce some notation used in the rest of the paper. In Section we formalize the compressed sensing problem with generative network prior and describe an algorithm for the recovery. Section i we describe our novel deterministic condition on the weights of the network (R2WDC) and provide theoretical guarantees for solving compressed sensing with a generative network prior satisfying this condition via the algorithm described in Section 3] Then in Section 5 we demonstrate that random non-expansive generative networks satisfy the R2WDC with high probability. The appendix contains the full proof of the results described the main text. Appendix contains the extension of the theoretical guarantees for compressed sensing [
with generative network prior to other signal recovery problems.
2 Preliminaries
We use In to denote the n x identity matrix. For j 2 O, we define the j-th sub-network Gj R - ReLU(W,ReLU(Wiz))) CeLLUWy--ReUUWWeeLU((CCC
with the convention that Go(z) 4 For matrix W R let diag(Wx: > 0) be the diagonal matrix with i-th diagonal element equal to if (Wz), > 0 and 0 otherwise, and W+, = diag(Wz > 0)W. We then define W1,+,z (Wi) + diag(W1æ > 0) and
Iy (z) = ReLU(W,
W,+ = diag ( W,W, ,-1+,22= ... . W
Finally, we let Λo,z = 1 and for j 2 A = IT'= We+t with A = Ad,x = II We, Notice in particular that Gf(x) a 2 and G(xz) AgT.
For nonzero vectors in R,, we define the matrix
0r,
sin Or, Me
Qr
l
(6)
2T
2T
where 0r., = <(r,,), F r/11r122. = s/|s>| Le is the x l identity matrix and Mresa is the matrix that sends f + 8, $ + f. and with kernel fr))( If or s are zero, then we let Qr.s 0. The operator Qr. is used to define the WDC in the next sections, and allows to control how random ReLU layer distorts its inputs. Specifically, for very r, E R we have [ReLU(Wr)" RWW)(Wss) = Qr.e3 when W E paax has iidd 1/n..
Problem statement and recovery algorithm
Consider a generative network G R Ra as in
Q The compressive sensing problem with
generative network prior can be formulated as follows.
COMPRESSED SENSING WITH A DEEP GENERATIVE PRIOR
Let:
G: R + R. generative network, A E gmxx measurement matrix.
Let:
y. G(I.) for some unknown x, E R$
Given: G and A. Measurements Ay, + +1 R with m < n and E R noise.
Given:
Estimate:
y/
To solve the compressed sensing problem with deep generative prior G, in [1]], the authors propose the gradient descent method described in Algorithm with objective function f = fca. This algorithm attempts to minimize the objective function fes in I. Because of the ReLU activation function, the loss function fcs is nonsmooth. Algorithm [ therefore resorts to the notion of Clarke subdifferen- tial. Indeed, being continuous and piecewise smooth, fee is differentiable almost everywhere (by Rademacher's 's theorem) and admits Clarke subdifferential given by
(f)()) conv lim V.a(())))) Fp + I, Tp dom {cs)] p-000
For details for example

---

where with conv(-) we denote the convex hull and with (V the subset of E where f is differentiable. The vectors U, E (z) are called the subgradients of fes æ, and a point where les is differentiable it holds that (z) = (V))
Algorithm 1: SUBGRADIENT DESCENT 21
Input: Objective function f. initial point xo R \ {0} and step size a Output: An estimate of the target signal y/+ = G(x.) and latent vector s.
for 1. 1...
if f(-x+) < (x4) then 3g 3t
else ūt 4 It
Compute U2, E 0f()) F++1 + 2 ouR.
end
return 22,, G(Ia)
Notice that, as described in line 5, Algorithm Cerrnittmmmmrrraiiii corresponds to subgradient descent method with constant step size Before taking step in the direction of the subgradient though, the algorithm checks whether the objective function at the current state 2t has a larger value than the value at its negative -2 and if so updates the current state with its negative (line 3-4). This negation step allows the algorithm to escape the spurious critical point in a neighborhood of -pa where Pa E (0, 1), and it is motivated by the landscape analysis of fes under the deterministic and probabilistic assumptions that we describe the coming sections.
Recovery guarantees under deterministic conditions
The strategy taken in 1 and 21 to analyze the landscape of the minimization problem | and the convergence of Algorithm consists in identifying measurements matrix A and the generative network G, that ensure that the objective function ses is well behaved and Algorithm converges efficiently an estimate of r, and y.. These conditions are then shown to hold with high probability under probabilistic models for A and G. This is akin to the results on compressed sensing with sparsity where, for example, recovery guarantees were developed under the Restricted Isometry Property 4
of deterministic conditions the
The first condition, introduced in [18] is the measurement matrix A and ensures that AAT A behaves like an isometry over differences of points in the range of a generative network G.
Definition 4.1 (RRIC [8)). A matrix A E Rmx" satisfies the Restricted Isometry Condition with respect to G with constant for all 3 22, T3, 44 E R holds that
A -()((())))(())))...C)))))))))))) G(ra) G(x+)) <l|G(z)) - G(z))]l](((a) -G()))
The second deterministic condition introduced in 18 is on the weight matrices of G, ensures that they are approximately distributed like Gaussian, and allows the control of how the layers of the network distort angles.
We say that a generative network G as in 22. satisfies the Weight Distribution Condition (WDC) with constant e if for all é == 1,...,dd d, for all r, 8 E R=
Definition 4.2 (WDC [8].
(WW:).,,(W>+++... (W.)+.+ Qralla S,
Strictly speaking, in [88 the authors define the WDC as a property of single weight matrix W, and then assume that the WDC is satisfied each layer W; of G. This is equivalent the definition above and simplifies the introduction of a novel, weaker, condition on the weight matrices, the R2WDC below.
Definition 4.3 (R2WDC). We say that a generative network G as in 2 satisfies the Range Restricted
Weight Distribution Condition (R2WDC) with constant 0 if for all 1,..., d, and for all
5

---

I, 2,,,,,,,33 23, E R it holds that
(I 2r,a) u, v) S <||u||
where Gi-1(z))
s Gi-1(1),
G G)-1(
and V = G5-)( (
equivalent for i 1, but for S requires .W (Was to be close to the matrix Qr,s for any vector r, 8 E R to be close the matrix Only for vectors r, s on the range of G and when acting on vectors u, u E R given by the difference of points on the range of G Notice that contrary to (8) defining the R2WDC for layer requires considering the input/ouput pairs of the layers up to
Notice that the R2WDC is weaker than the WDC. Indeed. 8 and
i 2 2 equation
and when acting on any vector u, E I8 while equation 2
requires (Wi)
Our first technical result provides theoretical guarantees for efficiently estimating a target signal y, on the range of generative network from few linear measurements under the RRIC and the R2WDC. Theorem 4.4. Suppose d 2 2, and A and G satisfy the RRIC and the R2WDC with constant < Ki/do. Assume that || S Kallæ. Let { be the iterates generated by Algorithm wwth d4224/2
loss function Sea. initial point To E TR& (0) and step size a = Kz Then there exists a number of Kaf(we)2" such that
steps T' satisfying T S d'e 1
|xT - x=1l2 S K3d (xelllee 24d
In addition, for all 2 T, we have
|| - x, x.112 S Cttl C*t1--1127 100---IITXX/11 x.112 + 2/24/2 |7l1.
1.2
[[( V-ll2 2d/2
ch+1-T | x.112 1.2K7 |n|1.
where C' =
o nd
E (0, 1). Here, Ki,..., K7 are universal positive constants.
The exponential factors 2d appearing in the conditions and theses of the theorem are artifacts of the scaling of the weights of the generative network. For example, the output G(x)) of the network scales like ||x||///d// and the loss function (x) as ||x /2 (see for example Proposition C.I. Hence, for new constants K2, K4, the bounds for 1) and could be equivalently written as 1 I K22 K2llu=lla/d" and T S Kaf(zo)/ (do)/ cll= 112). Choosing the weights of the network to be {v2 W. )EE( would remove the 2 factors in the above theorem (and scale the definition of R2WDC).
Remark 1.
This theorem shows that, despite the nonconvexity of the minimization problem 11 if the RRIC and the R2WDC hold with constant e, after T = O(c=1) number of iterations the iterates of the subgradient descent method described in Algorithm enter in region of local convergence around &.. Moreover, after a large enough number of steps, G(zx.) gives an estimate of the target signal y/ up the noise level ((Ivl))
Theorem 3.1 in shows that Theorem 4.4 holds assuming that the RRIC and the WDC hold. Our first technical contribution is to show that the WDC in Theorem 3.1 of [21], can be relaxed into the R2WDC. Relaxing the WDC into the R2WDC, will enable the relaxing of the expansivity assumption needed to show that the WDC holds for Gaussian generative networks as we demonstrate in Section
We next describe the role of these deterministic conditions in the analysis of the problem Ib. The full proof of Theorem 4.4 is given in Appendix C
4.1 Global landscape analysis via the R2WDC
The analysis of [ and 21 follows the approach recent line of works that analyze the global landscape geometry of non-convex optimization problems arising in statistical and signal recovery problems (see for example 3d
37
K and for an overview). The analysis roughly consists of
two steps:

---

1) Showing that fa=(2) = fz(z) and (f)((a) = h2 uniformly over æ.
ii) Analyzing the global properties (z) and hgg and transfer them to fcx(2) and h using the first step.
Here (z) and h are continuous functions of z, corresponding to the expected value of fa=(z) and (x) under Gaussian weights and measurement matrix A (see next section for details) and zero noise. The RRIC and the WDC are used in (88] and [21] to obtain the uniform concentration in the first step, well directly proving convexity- properties of fes (2) in the vicinity of x..
To illustrate how the WDC and the R2WDC come into play, consider for simplicity the noiseless case 7 0. Then at point E _ where G' is differentiable, the gradient of fos is given by
fcs(() -
AAd.z.I.).
(Ad A.)
where Ad,z and Ad.a. ar defined in Section 2 and the approximation uses the fact that A satisfies the RRIC with respect G. Then if G satisfies the WDC have that
V Ves(x) A 3.)
(Wa) G (Wo) G.Ga- A6 17- (Wa Ga- Ad-1,,
-1- [Q (c) + ((e) Ad-1. 12 [Qa. (0) + O(1) Ad-1,2,
(W +.G2-1(()) where the last line used the WDC to control the concentration (W (Wa) and (Wa) Ga-1(())) (Wa) GG- The resulting terms are then controlled again applying the WDC to the the other d - weights of G, so that proceeding by induction over one obtains
(fs(())
h2
2d 22
(10)
2d
where i is a deterministic vector field defined in Appendix
C
In Appendix D we show that the R2WDC can be used to control directly the concentration of the terms
(W.) (c) (Ga (dd
and
- (x) (tr (Wa) + G.Ga- (.
around their expectation (with respect to Wa) obtaining in this way
foa(1) Ne (Ad Ad.a,
A4-1,IQQ, 100),0a ((m) Aa
1- 16)).s Aam + O(c|AA 1ll Ixll)
+
Then again applying the R2WDC the other layers G, we can show that 10 still holds. We can
then borrow the analysis of h2 from 21 and obtain the same convergence guarantees.
The advantage of using the R2WDC over the original WDC, that it is satisfied by random generative networks with contractive layers as we demonstrate in the next section.
Recovery guarantees under probabilistic assumptions
In this section we give probabilistic models for the measurement matrix A. generative network G, and noise vector y that will ensure that the RRIC and the R2WDC are satisfied with high probability and Algorithm ! Jefficienlly estimate the target signal up to an error of the order Ö k// ||]l))
We make the following assumption on the sensing matrix gmxxn Assumptions A.
A.I A is independent from {Wi)

---

A.2 A has i.i.d. (00, 1/m) entries.
A.3 There are sufficient number of linear measurements:
m C2 k. log
en k
(11)
where C. depends polynomially on e_
Under Assumptions A the measurement matrix satisfies the RRIC with respect to G with high probability.
Lemma 5.1 (Consequence of Proposition 6 in T Let Assumptions A be satisfied. Then A satisfies
the RRIC with constat c > 0 with respect to G. with probability at least
9e
where y and è are positive universal constants.
Proof. This result is proved in Proposition 6 in [8 for number of measurements satisfying
m 2 C² k - log - n. where C² depends polynomially on e. To imporove the lower bound on (11) is enough to follow the proof of Proposition 6 in [8] and use the sharper upper bound the number of affine subspaces in the range of a gnerative network given in Lemma D.I
We then provide a probabilistic model for generative network G R Assumptions B.
R as in
B.1 Each weight matrix W; E R have i.i.d. NO, 1/ms) entries.
B.2 The first layer satisfies n, C. h and for any i ..... d:
n: 2 Č k log
e n2
(12)
k
where C. depends polynomially on c!
B.3 The [W are independent.
Under Assumptions B the generative network G satisfies the R2WDC.
Lemma 5.2. Fix < c 1. Consider a d-layer ReLU network G with weight matrices (W;). (Ws) Assume that the (W.) d satisfy Assumptions Then G satisfies the R2WDC with constant with probability at least
(
[en]
e CaTt
Σ
(x=1)
eng
k
1=2
where c. depends polynomially on -1 and is a positive absolute constant.
We finally conclude with some assumptions the noise vector R Assumption C. The noise vector v is independent from A and the weights (W;)d
The next lemma is used bound the perturbation of the objective function fos and its gradient due to the presence of the noise term т/- These bounds are then used to show that Algorithm leads to reconstruction of y+ of the order ((/ll//llll)).
Lemma 5.3. Suppose G R& + IR" satisfies the R2WDC with < 1/(16T and d > 2. Let TR mx be matrix with i..dd entries NO, 1/m) and r) E IRm satisfies Assumption Let
13
k
log
5 II j=1
en,
(13)
24/2
12
m
k

---

Then with probability at least for every IR&h we have that if in addition G is differentiable at we also have that
log IT 2
(a, (T,ATATT) S w [|l|||
(14)
| A" nl S w||n||
(15)
Given the previous assumptions, we are now ready to state the main result of this section. Theorem 5.4. Suppose 2 K1 K1/d00 and w n|ll
Kalla, where w is defined in d222473
Assume that A, G and satisfy Assumptions and C
Then with probability at least
- ( (xx) C CCR1
(cm)
2h
en:
4/c
e cema/2
Ge -ce
(og(511. *
xx)
(16)
k+1
where 9 and è are positive universal constants, the following holds. Let {rz} be the iterates generated by Algorithm 1 with loss function Ses, initial point 3o E TR& {0} and step size K3 2d There exists a number of steps T satisfying T I d'claalla
Kaf(mo)2" such that
|xT - x.1l2 S K3d 1xalleee K6d22//2/l1lls
In addition, for all 2 T. we have
| - x+112 S Ct+1-T - 2.112 2| + w/
1.2
[[G(0+1) 1/-112 2d/2
C C |
x.112 1.2K ||nl2
where C' -
7 2a E (0, 1). Here, KI...., K7 are universal positive constants.
Proof. Combining Lemma Lemma 5.2 and Theorem 4.4 we obtain Theorem 5.4 with w and probability at least
m 7 k
Eng
c.m Efe tem
++1
Inspecting the proof of Theorem 3.1 in 21 it is easy that if Lemma 5.3
holds, then the
conclusions of Theorem 5.4 hold with w given by (13 and probability at least 16
As for Theorem 4.4 the exponential factors 2d are artifacts of the scaling of the weights of the network. Had the entries of We been drawn from (0, 2/T4) the 2d factors would not be present.
Remark 2.
Remark 3. Notice that 4k log(en/(Cr / + 1)) < 4kllggn)) (loogg)))/oo()) for every n 2 Thus for every
i= 1, ... d, it holds that
16 k c-c
(17)
log(n.)
log(2)
the conclusions of the theorem hold with nontrivial probubility bounds. In Appendix G we provide an example of a generative network G with contractive layers satisfying both 122 and
Theorem 5.4
provides guarantees for the efficient recovery of a signal in the range of generative network from few noisy linear measurements, using a nonconvex (sub)gradient descent method. Notice that the intrinsic dimension of the signal y, is l (the dimension of the latent space) and the number of measurements required m proportional to log factors in the widths of the network and polynomials in the depth. Notice moreover, that up to these factors, the width n, of each layer of the network is also required be linear in k. This necessary to ensure that each subnetwork G; * + g is invertible, and it is weaker than
and informationttheoretiallll optimal up

---

the assumptions in the previous works that required n; to be linear in n:-1 in order to ensure the invertibility of every single layer.
In Appendix H we empirically verify the predictions of Theorem 5.4 demonstrating how (a practical variant of) @gorrthmm[rrcovee signals y/+ in the range of non-expansive generative networks from undersampled noisy measurements. We show that the recovery is linear in k/m and that in practice the dependence on the depth d of the networks is milder than that predicted by our theory. We leave for future works the establishing of sharper bounds in the depth d.
Limitations of the current and previous works on theoretical guarantees for signal recovery with generative networks are the Gaussian assumption on the weights and the absence of biases. Important directions of future research are the inclusion of biases in the generative network and the departure from the Gaussian weights assumptions for more realistic probabilistic models.
Acknowledgments and Disclosure of Funding
I would like to thank Paul Hand for comments on an earlier version of this manuscript and Babhru Joshi for helpful discussions. This research was partially supported by the NSF award 1M4-1188087.
References
[1] Rameen Abdal, Yipeng Qin, and Peter Wonka. Image2stylegan: How to embed images into the stylegan latent space? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4432 4441, 2019.
[2] Aviad Aberdam, Dror Simon, and Michael Elad. When and how can deep generative models be inverted? arXiv preprint arXiv:2006. 100006..5555 15555, 2020.
[3] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 537-546. JMLR. org, 2017.
[4] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489-509, 2006.
[5] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incom- plete and inaccurate measurements. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences, 59(8): 1207-1133, 2006.
[6] Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions Signal Processing, 67(20):5239-5269 2019.
[7] Christian Clason. Nonsmooth Analysis and Optimization. arXiv preprint 1708. 2017.
[8] Jorio Cocola, Paul Hand, and Vlad Voroninski. Nonasymptotic guarantees for spiked matrix recovery with generative priors. Advances in Neural Information Processing Systems, 33:15185- 15197, 2020.
[9] Jorio Cocola, Paul Hand, and Vladislav Voroninski. No statisticalcoomputationall gap in spiked matrix models with generative network priors. Entropy, 23(1):115, 2021.
[10] Constantinos Daskalakis, Dhruv Rohatgi, and Emmanouil Zampetakis. Constant-expansion suffices for compressed sensing with generative priors. H. Larochelle, M. Ranzato, R. Had- sell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 13917-13926. Curran Associates, Inc., 2020.
[11] Alex Dimakis. Deep generative models and unsupervised methods for inverse problems, https: //youtu be/0er39Ar111/22-22088 October 2021. Algorithmic Advances for Statistical Inference with Combinatorial Structure.
10

---

[12] David L Donoho. For most large underdetermined systems of linear equations the minimal é1- norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(6):797-829, 2006.
[13] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
[14] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in neural information processing systems, 29, 2016.
[15] Paul Hand and Babhru Joshi. Global guarantees for blind demodulation with generative priors.
In Advances in Neural Information Processing Systems, pages 11531-11541, 2019.
[16] Paul Hand, Oscar Leong, and Vlad Voroninski. Phase retrieval under a generative prior. In Advances in Neural Information Processing Systems, pages 9136-9146, 2018.
[17] Paul Hand, Oscar Leong, and Vladislav Voroninski. Compressive phase retrieval: Optimal sample complexity with deep generative priors. arXiv preprint arXiv:2008. 2020.
[18] Paul Hand and Vladislav Voroninski. Global guarantees for enforcing deep generative priors by empirical risk. IEEE Transactions on Information Theory, 66(1):401-44) 4418. 2019.
[19] Reinhard Heckel and Paul Hand. Deep Decoder: Concise image representations from untrained non-convolutional networks. In International Conference on Learning Representations, 2019.
[20] Reinhard Heckel, Wen Huang, Paul Hand, and Vladislav Voroninski. Rate-optimal denoising denoissin with deep neural networks. Information and Inference: A Journal of the IMA, 1051:1225 2021.
[21] Wen Huang, Paul Hand, Reinhard Heckel, and Vladislav Voroninski. A provably convergent scheme for compressive sensing under random generative priors. Journal of Fourier Analysis and Applications, 27(2): 2021.
[22] Babhru Joshi, Xiaowei Li, Yaniv Plan, and Ozgur Yilmaz. Plugin: simple algorithm for invert- ing generative models with recovery guarantees. Advances in Neural Information Processing Systems, 34, 2021.
[23] Babhru Joshi, Xiaowei Li, Yaniv Plan, and Ozgur Yilmaz. PLUGIn-CS: A simple algorithm for compressive sensing with generative prior. In NeurlPS 2021 Workshop on Deep Learning and Inverse Problems, 2021.
[24] Tero Karras, Miika Aittlla, Samuli Laine, Erik Härkönen, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Alias-free generative adversarial networks. Advances in Neural Information Processing Systems, 14:852-8633 2021.
[25] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Analyzing and improving the image quality of stylegan. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8110-8119, 2020.
[26] Qi Lei, Ajil Jalal, Inderjit S Dhillon, and Alexandros G Dimakis. Inverting deep generative models, one layer at a time. Advances neural information processing systems, 32, 2019.
[27] Fangchang Ma, Ulas Ayaz, and Sertac Karaman. Invertibility of convolutional generative networks from partial measurements. Advances Neural Information Processing Systems, 31, 2018.
[28] Morteza Mardani, Enhao Gong. Joseph Y Cheng, Shreyas S Vasanawala, Greg Zaharchuk. Lei Xing, and John M Pauly. Deep generative adversarial neural networks for compressive sensing mri. IEEE transactions on medical imaging, 38(1):167-179, 2018
[29] Jiri Matousek, Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013.
11

---

[30] Sachit Menon, Alexandru Damian, Shijia Hu, Nikhil Ravi, and Cynthia Rudin. Pulse: Self- supervised photo upsampling via latent space exploration of generative models. Proceedings of the ieee/cvf conference on computer vision and pattern recognition, pages 2437-2445, 2020.
[31] Lukas Mosser, Olivier Dubrule, and Martin Blunt. Stochastic seismic waveform inversion using generative adversarial networks as a geological prior. Mathematiccal Geosciences, 52(1):53-79, 2020.
[32] Gregory Ongie, Ajil Jalal, Christopher A Metzler, Richard G Baraniuk, Alexandros G Dimakis, and Rebecca Willett. Deep learning techniques for inverse problems in imaging. IEEE Journal on Selected Areas Information Theory, 1(1):39-56, 2020.
[33] Xingang Pan, Bo Dai, Ziwei Liu, Chen Change Loy, and Ping Luo. Do 2d {gan]s know 3d shape? unsupervised 3d shape reconstruction from 2d image {gan)s. In International Conference on Learning Representations, 2021.
[34] Shuang Qiu, Xiaohan Wei, and Zhuoran Yang. Robust one-bit recovery via relu generative net- works: Near-optimal statistical rate and global landscape analysis. In International Conference on Machine Learning, pages 7857-7866. PMLR, 2020.
[35] Ganlin Song, Zhou Fan, and John Lafferty. Surfing: Iterative optimization over incrementally trained deep networks. Advances in Neural Information Processing Systems, 32, 2019.
[36] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery the sphere i: Overview and the geometric picture. IEEE Transactions on Information Theory, 63(2):853-884, 2016.
[37] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5): 131-1191, 2018.
[38] Roman Vershynin. High-diiennsioal probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
[39] Jun-Yan Zhu, Philipp Krähenbühl, Eli Shechtman, and Alexei A Efros. Generative visual manipulation on the natural image manifold. In European conference on computer vision, pages 597-613. Springer, 2016.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section S
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A] All the experiments were run locally
Apple M1 CPU
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vrkbdJl9W1M", "reviewer": "Reviewer_s2nj", "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.\n\nThis 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.", "questions": "I have no major questions or concerns-- I am listing my minor concerns as clarifications.\n\n- 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$? \nIs there something special about the analysis in this paper that allows for the $\\sqrt{k/m}$ term which does not appear in [20]? \n\n- 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$. \n\n- 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.\n\n", "limitations": "The limitations are sufficiently stated.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ 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.\n\n\n+ 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.\n\n+ The results are clearly stated and compared to existing results.\n\nWeaknesses:\n- 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$. \n\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$.\n\n- 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.\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i_kGqb0ES5U", "reviewer": "Reviewer_NCFH", "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. ", "questions": "I did not check the derivations for accuracy, so I do not have any specific question at this point. ", "limitations": "n/a", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths. \n- The paper presents a new analysis for the general signal recovery using generative priors. \n- The main contribution is in relaxing the conditions on the width of the network layers. \n\nWeaknesses. \n- 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. \n\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IDS8RczrKjO", "reviewer": "Reviewer_xC1X", "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.", "questions": "Please answer the motivation question above.", "limitations": "No.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Solid theoretical result on a relaxed assumption for generative model-based signal recovery.\n\nWeaknesses:\n- 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].\n\nOverall, 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.\n\n[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.\n[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.\n[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.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3lE50hOp7FU", "reviewer": "Reviewer_V26y", "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. \nTheorem 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.\nThe extensions to phase retrieval, denoising and spiked matrix recovery are given in the supplementary materials, although the proofs are not explicitly given. \n", "questions": "\n* [21] seems to be the extended NeurIPS version of workshop paper [22]. It is probably better to use this version instead of [22]. \n* I suggestion expanding on the denoising effect of the algorithm 1 as mentioned in page 3, line 89. This is an interesting consequence. \n* 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. \n* 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.\n* 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.  \n* 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.\n* 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.\n* 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}$).\n* 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. \n* 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?\n* 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.\n* Typo: in two places in the paper, RRWDC is used instead of R2WDC. \n", "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n* 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$. \n* R2WDC is weaker that WDC condition, and nonetheless provides better results. \n* The proof builds on many previous works, for example [18], [20], [22], and, based on my rapid read, is sound and well presented.\n* The contribution of the paper, namely relaxing the constraints on the network further and introducing R2WDC, is a good step forward in this analysis.\n\n**Weakness**\n\n* 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.).\n* 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.\n* Having numerical results, for instance similar to those in [20], can always help communicating the paper’s contribution better.\n* 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]).\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept