PLUGIn: A simple algorithm for inverting generative models with recovery guarantees
Authors: Babhru Joshi
Xiaowei Li
Yaniv Plan
Ozgur Yilmaz
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: generative neural network
inverse problem
denoise
gradient type method
non-convex optimization

Abstract: We consider the problem of recovering an unknown latent code vector under a known generative model. For a $d$-layer deep generative network $\mathcal{G}:\mathbb{R}^{n_0}\rightarrow \mathbb{R}^{n_d}$ with ReLU activation functions, let the observation be $\mathcal{G}(x)+\epsilon$ where $\epsilon$ is noise. We introduce a simple novel algorithm, Partially Linearized Update for Generative Inversion (PLUGIn), to estimate $x$ (and thus $\mathcal{G}(x)$). We prove that, when weights are Gaussian and layer widths $n_i \gtrsim 5^i n_0$ (up to log factors), the algorithm converges geometrically to a neighbourhood of $x$ with high probability. Note the inequality on layer widths allows $n_i>n_{i+1}$ when $i\geq 1$. To our knowledge, this is the first such result for networks with some contractive layers. After a sufficient number of iterations, the estimation errors for both $x$ and $\mathcal{G}(x)$ are at most in the order of $\sqrt{4^dn_0/n_d} \|\epsilon\|$. Thus, the algorithm can denoise when the expansion ratio $n_d/n_0$ is large. Numerical experiments on synthetic data and real data are provided to validate our theoretical results and to illustrate that the algorithm can effectively remove artifacts in an image.

PLUGIn: A simple algorithm for inverting generative models with recovery guarantees
Babhru Joshi
Yaniv Plan Department of Mathematics The University of British Columbia
Xiaowei Li
Özgür Yılmaz
{b. jb.jo xli, yaniv, oyilmaz)@math.. wal.maaa/mattuuu...... ubc.uuc.... ca
Abstract
We consider the problem of recovering unknown latent code vector under a known generative model. For a d-layer deep generative network R - IRdd with ReLU activation functions, let the observation be G(x) + c where c is noise. We introduce a simple novel algorithm, Partially Linearized Update for Generative Inversion (PLUGIn), to estimate (and thus (ar)). We prove that, when weights are Gaussian and layer widths nı Z 5'mo (up to log factors), the algorithm converges geometrically to neighbourhood of x with high probability. Note the incquality on layer widths allows n, > n,+1 when 2 1. To our knowledge, this is the first such result for networks with some contractive layers. After sufficient number of iterations, the estimation errors for both æ and ((x) are at most in the order of / (4/no/nallee Thus, the algorithm can denoise when the expansion ratio na/ ng is large. Numerical experiments on synthetic data and real data are provided to validate our theoretical results and to illustrate that the algorithm can effectively remove artifacts in an image.
Introduction
We consider the inverse problem of recovering an unknown vector x² E 1n0 from a noisy observation y E nh of the form
(1) where 6 Th is noise and G Ro -> Th is known d-layer feed-forward neural network with ReLU activation functions (in fact, it is straightforward to generalize to positively homogeneous activation functions, which we will elaborate later). Precisely, G has the form
y 9(x" +
... (A (xx) a (Aaa(Aa- 1ak-1...o(A12.. (A1z)....))
where (.)) max(- 0) is the ReLU activation function and A₁ E m is the weight matrix in the i-th layer.
The inverse problem I has applications in, for example, signal denoising and signal compression 2 B. In the case of denoising the typical goal to recover a clean signal y² from its noisy observation y" + and, in the case of compression, the goal is to find an efficient low dimensional representation of y Traditional approaches for these problems often use priors on signals, for example, sparsity prior with respect to fixed basis or dictionary 4 5. 6 An emerging viewpoint to use generative prior that assumes the unknown signal y" is the range of deep generative model G, i.e., yf = G(x"). and develop algorithms that can estimate the latent code vector x: from y* + c, thus recovering y²
Recent advancements in training deep neural networks have shown that priors in the form of gen- erative models can effectively map low dimensional vectors the space of natural image classes
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

3
9
Learned generative models can then be used as priors to solve various inverse problems
including denoising I compressive sensing [T 12 13
15 IG phase retrieval [17], blind deconvolution [8 19 low-rank matrix recovery 20 and have been shown to perform on par or
outperform classical sparsity based approaches for these inverse problems. For example, in [ the authors empirically showed that an end-to-end approach for denoising using neural network that maps noisy patches in an image to noise-free ones achieves state-of-the-art performance and is on par with BM3D, Similarly, in || the authors empirically showed that for compressive sensing using generative prior, optimization of the empirical risk objective over the latent code space (of the generative prior) can recover vector that effectively estimates the uncompressed signal with 5-10 times less measurements compared to Lasso in some cases.
Given that equals ((x"). ). with possibly some additive noise, standard way to estimate x², .i.., to invert ((x*), ), would to look for a minimizer of the program
min RER"
ly (x))
Unfortunately, this program is non-convex and to knowledge there is no known efficient method that can achieve its global minimum in general. On the other hand, for generative networks with random (Gaussian) weight matrices, line of papers showed that gradient-based algorithms can provably avoid local minima with high probability Lo [4, 17 20) In partieular, [TO] considers a
random Gaussian noise model, and random Gaussian weight matrices A, which are highly expansive at cach layer. Under these conditions, the authors show that the latent code vector x' can be accurately estimated using a gradient-based method that uses the Subbejgradient updates given by
(4) where x² is the k-th estimate, 77 E R is step size, and Dj is diagonal matrix with entries that either zero one. Each D, zeros out the inactive rows of A, with respect to the estimate xf and so it is function of x² (and A, for p < j). Thus, at each iteration all D, need to be updated.
x²+1= I² T7 () (D2A2)T (DaAs) (g(x*) -((=)))).. v).
In this paper, we show that we can drop the D3 and still recover an accurate estimate of x²" We propose the following iterative algorithm, Partially Linearized Update for Generative Inversion (PLUGIn), to estimate r=:
PLUGIn:
2kt - ======-nAAA .. ..AJ (9(x*) y)
(5)
This algorithm inspired by previous work showing that latent vectors for non-linear single-index function can be approximately estimated by treating the function as linear [2 22]. Similar to
19 233, for theoretical analysis, we assume the weight matrices are Gaussian. To show that the algorithm works more broadly, we conduct real data simulations. Applying the
[T
[ 12
14
ideas in 21 2 one can show that for any fixed z²., the first iteration of (5) provides an unbiased estimate of x: with 1) = 2d, which is generally not the case for the gradient descent estimates given by see Section for further details. Additionally, each iteration of PLUGIn maps the difference (z y to the low dimensional latent code space using a static matrix AT AT, which can be pre-multiplied and reused subsequent iterations.
In addition to the randomness assumption on the weight matrices, when the width of the each layer satisfies n; 2 5'mo (up to log factors), noise is independent of weight matrices, and the step size 7 is fixed, we show that the estimates provided by PLUGIn converge to neighbourhood of x² geometrically with high probability. This result allows n4. Ri41 for > and thus can provide theoretical guarantees for estimating x from ① even when & has some contractive layers. To our knowledge, this is the first such result. Additionally, we show that the k-th recovery and reconstruction errors satisfy
n
4
100 - 11''
||l|| nd
and (G(=*))9(('))
|ell
with high probability when & is large. Thus, PLUGIn can effectively denoise noisy observations satisfying O provided that the expansion ratio na/na no is large. These contributions are highlighted below:
1. We introduce a simple novel algorithm ( called Partially Linearized Update for Generative Inversion (PLUGIn), for inverting a generative model. Note that each update of PLUGIn
2

---

can be implemented with two blackboxes. The first blackbox provides the g(x*) for each iterate and the second blackbox provides the product of the weight matrices A[A] A.. Thus, given these two blackboxes the individual matrices are not needed.
2. Under relatively mild conditions, we show that for generative priors with possibly contractive layers, PLUGIn effectively estimate the unknown latent code x² and the unknown signal ((x") from observation satisfying | of step sizes.
The convergence is geometric and holds for a range
3. In the presence of arbitrary noise we show that the recovery and reconstruction error corresponding to the estimate z², for sufficiently large k. is approximately / /4 e|]- In contrast typical random noise assumptions, of the weight matrices. This allows stochastic noise (independent of weight matrices) as special case if one can bound the norm of the stochastic noise with high probability.
only require the noise be independent
we introduce notations used through the paper. In state the main results. In Section 3 provide outline of the proof. In Section we provide numerics on synthetic and real data. Section activation functions, well limitations in our results.
Organization of the paper: In Section Section 2
we briefly discuss a generalization of S
1.1 Notations
For positive integer n. let [n] = (1, .n..
For a vector æ, let ||=||| be its Euclidean norm; for ||
matrix A, let A|] be its operator norm; for a matrix A and a set T, let ||A|T :- suP=ET\(0) ][]] Let (000 f2) be the normal distribution with mean zero and standard deviation t. Let ((x, r) be the Euclidean ball of radius centered at x and let (") be the Euclidean ball in IR with radius centered origin. We use C and denote absolute constants (often for small ones and for large ones) which may vary from line to line. We also use Co, C1, etc., to denote particular absolute constants, which do not change throughout the paper.
2
Main Results
Let the generative model G R + Ind be defined as in Equation problem:
We consider the inverse
Let: x² R0"0 Rd y= G(x") +c,
Given: generative model and observation y, latent code vector x" and G(x").
Estimate:
We assume:
A1. All activation functions are ReLU.
A2. Each A, E R has i.i.d. N (0, 1/n;) entries and {A; (ete are independent.
A3. Layer widths (number of nodes each layer) satisfy
Th; 2 Co5'no no log
enj II
E [d]
no
for some (sufficiently large) absolute constant Co-
A4. The noise does not depend on { {Aihetj (The noise may be deterministic or random.)
Let x E "o and let x be the result of applying & iterations of PLUGIn 5). Under assumptions A1-A4, x geometrically converges to neighbourhood of x (and also ((z*) neighbourhood of
((x*)) for range of step sizes near 2d. Precisely, we have the following theorem.
Theorem 1. Let 0 E (0, & and ler a
0 + 10 E (0, 1). Let R be a positive number such that || 2-1 < R. Under assumptions AI-A4, the k-th estimate a² given by PLUGIn algorithm with constant step size y) = 62d satisfies
150
|| - x²
a R R+
2d no/ no//alle||, and
3

---

450
||0(x")- - -g(x")| S 30 R++
1- 2d
/nn na |e]l
with probability at least 1 - 2(k + 3)
When 0 1, Theorem D reduuee the following corollary.
Corollary 1. Let R be positive number such that || - x=1l S R. Under assumptions A1-A4, the k-th estimate æt given by PLUGIn algorithum ① with constant step size 22t satisfies
R - 30 2 /nn//allllll and 110t x111 S 2
[[((x*)) ((x 2 $2 + 90 2d / no/ mall
with probability at least 1 - 2(k + 3)- 100o.
Remark 1 (Allowed number of iterations and comparison of error bound summands). The probability in Theorem (and also Corollary D decreases the number of iterations increases. However, this is generally not a problem because we can take up to exponentially many iterations before this probability becomes trivial. In fact, if we require probability of at least 99% on the error bounds, then we can take any k S k- (no) == 200 10no - 3. Note that h* grows exponentially in no and it is
already large when no is relatively smal
The noise term in the error bounds (proportional to ||el)) will dominate the other term (long) before k- many iterations are reached, unless the noise is virtually zero. Indeed, in Corollary 1 if 2-2- R 2 v /4 ||, then the noise must satisfy
||]|| < R
T"n (2)
(4)²²==
= =R
(op((10o)/200)
Note that (1) (2)xx(100n)/2000 is a double exponential and extremely small so we will consider the k"
noise being virtually zero in this case. On the other hand, 2- R < v m then after at most kt iterations, with probability at least 99%, the estimation errors for x¹ and ((x") will be at most C' /4 maal/// The same argument can be made for Theorem when a is close to 1 (i.e., O is close to 1) so that a decays fast and 1 is not close to being singular. I-a Remark (Contractive layers). In A3, (6 states lower bound on n, with respect to the latent code dimension no (up to log factors). While this bound strictly increases with layer depth i, it not necessary for n, to always increase with (except in the first layer). For example, consider n, 5C,5 nod((d
i) where / is any fixed number such that 3Cg E N and / 2 4 + log Co. It is easy to see n1 > n2 > ... > n.d, and we can also verify (see Appendix DD) that such n, satisfy (6). In this case, the network is contractive in each layer after the first, and Theorem still applies.
Remark 3 (Initialization may depend on random weight matrices). The results the theorem can still hold when x is chosen randomly, dependent on the weight matrices A,. In this case, suppose that ||z - x² < R with probability at least 1 - 8. Then, the error bounds hold with probability at least 1 2(k 3) -10mg 8. This does not follow directly from the theorem as stated (which fixes x², then takes random weight matrices), but follows from the proof.
Remark 4 (Comparison to guarantees for gradient- gradient-based method), Here we compare our results to the ones in 100 which uses 4 for iterations and considers random noise model.
When the noise (O, na n I, the error bounds on the k-th PLUGIn iterate Corollary with high probability, reduces to
max x" ""11- 11())) S (2 2d /o/nn//a)))
Thus, we get geometric convergence with a rate of 1/2 and after sufficiently many iterations, the errors are at most C2d /no/nay-
similar result was shown in 10,, which studies a gradient-based method for solving the inverse problem I They show that when the weight matrices are random Gaussian and sufficiently
For example, (5) 2.59 " and (10) z 1.34 x 10
For example, 2 exp(10)/200 x 7 x 10

---

expansive at each layer, the iterates of the gradient based method converge to a neighborhood of the target signal x*. The result holds for fixed step size, dependent on d. After sufficiently many iterations, the iterates converge geometrically to neighborhood of x² of radius at most the order of / nay, up to log factors. This rate of convergence takes the form (1 C/d²), thus giving slower convergence for deeper nets. On the other hand, we note that dependence on is relatively minor concern. Generative models usually have small depth in practice, our MNIST experiments (below) work well with depth and typical applications use depth less than 8.
Proof Outline
Here give sketch for the proof of Theorem I For simplicity, will only focus analyzing one iteration of PLUGIn with step size 7) = 2 The complete proof can be found in appendices.
The Special Case
Let us first look at the special case where d = and 0. The analysis here highlights some of the key ideas in our proofs, while its result Lemma ! serves as building block for proof in the general case. In this special case, PLUGIn with 17 = 2d reduces to
x k+1 x² - 2AT [a(A**) (AAx)]
where ReLU and A E RRx is random with i.i.d. A (0, : entries.
In fact, the first iterate provides an unbiased estimate of x² when x. does not depend A. Indeed,
the rotation invariance property of Gaussian distribution may leveraged to show 21 22], for
any fixed x,
EATo(Ar)) jz..
(7)
For completeness, we also include proof for in Appendix iteration gives
Lemma
Applying
7 to the first
Ex. x² - AEAT (Ax*) + 2EA 2E (Ax")
- + x
Thus, even the first iterate can be shown be good estimate by showing that æ concentrates around its mean. Further iterates are generally no longer unbiased estimators because they pick up complex dependence on the random matrix A. We overcome this by developing series of uniform deviation inequalities, as below.
Let us suppose have shown that, with high probability, ||* x=1 S for some (small) constant > 0. Then we wish to show that ||, -x"l S r/2 with high probability, Notice that
-x*++1 x²) = 2AT [o<(A*) - a(Ax)) - (x* x²) |10 x=11= sup (Au, (A**) (Ax')) (u, x²)
vERa-1
= 2 sup 7(u ;²²²")
uE8n-1
where
((u, u; = (Au) o oAAx')) (u, x²).
We wish to bound the supremum of random process Z(u, x²; over u E Sa-1 However, this process is challenging to analyze since I² depends on A when & > 1. To alleviate this dependency, we bound by the supremum of Z(u, v; x²) over (u, v) E T == (0 1) x B(x", instead. It is worth noting that Z(u, u; x)) is centred, namely (u o; xfx*) = 0 for any fixed v., We now arrive at the estimate
||a - x S1 2 2 sup vu,) I|a Sr.
(M.
The following Lemma I provides bound supyo u("). In fact, it is slightly more general because we replaced 7 with Ti x Tz (this replacement helpful when studying the general case d > 1). The proof of this lemma can be found in Appendix B The proof idea is to first establish
5

---

that (u, 2") has mixed Ssub-Gausiia and sub- cub-exponential) tail increments through Bernstein' s inequality, and then apply the result from [24], which provides general bound for the supremum of random processes with mixed tail increments.
Lemma 1. Lei a - ReLU. Fix w E IR" and A E B.uxa have i.i.d. N (0, + entries. Define ((u, u; w) (A (Au)) o (Aw)) - 1/2 (u, v ww.
Suppose Tı, T2 are sets (not depending on A) such that
Ti = S (0, and
To = S₂ n (ww,r))
for some q-dimensional (affine) subspaces S1, C IR and real numbers a, > O. Then for any t 1,
(1
(u, u; w) S Cia²r
q 1
sup wE T
TE72
with probability at least e- Here C1 0 is an absolute constant.
We can apply Lemma D to estimate
(with S S2 = (R") and get, for example,
|x 201 S 2Cir (V + + V
2
with probability at least e provided that m 2 (16C) n
The General Case
Let illustrate the proof idea with d 2 (the extension to d > 2 is straightforward) Denote
of = =A(1a") and w = xAArz)) By adding and subtracting 24 (of - xς) we can write 5 with
1 = 2d as
xx = x² - -2' - -((=)))))(()))) x 1+1
(x - ---==x---- 22A (o(A1z²) -o(a=))))
2AA [xx] - 2AA (o(Azat) -(A24)))
+ 2 Al AJe.
Similar to the special case above, we can get
| x²11 sup mc8mo-1
201 (u, x+)++
sup 2 2' 2
(9)
wE8
where (denote z/ = x²)
7,(u, v) == - (u, xzー1)> j ;= 1.2.
r. it remains bound each term on the right hand side of ( The first term can be bounded directly through Lemma (with t = 10mg). The last term is also easy to bound by the randomness of A, (see Appendix C Lemma G). which case we have ATell S 15-/no/nallll with high probability.
Also assume that 1 1
Denote Gi (z) = (AAr)) for E "0" For the second term, first notice that range(Ai) is a no- dimensional subspace in RR, Using the ideas from I| 25 we can also show that range(G)
is contained in a union of N many rag-dimensional (affine) subspaces, where N < (eni/no) /no) 1o
Furthermore, let be the event such that mappings A1, G1, G have Lipschitz constants being at most 3, then we can show (Appendix C Lemma g that P(E) 2 1 - 3e 10mo, Also on event & (note that || || < 3 and || - x1 < 3r), we have
A C range(A)) B" (0,3) S SB (0,3) =
a E range B(r 3r) C USEINI (Si, n B(x;, 3r)) =: USENN
where S and S2,j are nn-dimensional (affine) subspaces. Applying Lemma on each Ti x T2.j followed by union bound over j [N], we get (denote To UJE[N T2,5)
sup Zz(u, v) (g(r)) (V T
+
n2
n2
122

---

441
401
361
321
281
layer widths with
241
201
161
121
41
7
11
15 17
code dimension,
Figure 1: The empirical recovery probability from synthetic data in the noiseless with code dimension level no as a function of widths of the subsequent layers ni = n2 ng. Each block correspond the average from 20 independent trials. White blocks correspond to successful recovery and black blocks correspond to unsuccessful recovery. The area to the left of the line satisfies na > 20n
with probability (over Ag and conditioning on A1) least Ne By choosing & 2mo (og(en1/oo) we obtain a high probability bound for suPne8 Z2(A, u. xT).
Finally, if Co is sufficiently large, thus show from 9 that, with high probability,
1 r +-+00 2 /o//nallll)
| - x²1l
4 Numerical Experiments
In this section, we provide numerical experiments synthetic random data and MNIST images where the oberservations follow the model {T). The first experiment illustrates a phase portrait that verifies Theorem in the noiseless case. The second experiment illustrates that the PLUGIn algorithm 5 stable to small dense noise and compares its performance to gradient descent. The third experiment illustrates decay rate of recovery error and reconstruction error of PLUGIn in the presence of noise and compares its performance to gradient descent. Lastly, the final experiments illustrates that PLUGIn effectively remove dense unstructured random noise introduced to MNIST images. All experiments were conducted using Google Colaboratory.
In the synthetic experiments, we let the generative prior be 3-layer neural network G R + R of the form ((=) a (A) sampled from (0, 1 1/nz). We sample the target latent code x uniformly from S% set the noise level as a E IR, and set the noise to be av where v is sampled uniformly from gms-1, Then we set y G(x*) + av. We run PLUGIn and gradient descent each for 10,000 iterations, difference in norm between consecutive iterates is less than 10 11 times the norm of the current iterate, whichever comes first, and set å to be the output. We use fixed step size of n 3 for PLUGIn; for gradient descent, we use a parameter of 1000 to move along the gradient descent direction computed using PyTorch 26).
where the entries of weight matrix A, E R xn.- are
until the
For the first experiment, we ni E (1,2,... 19), mi E (1, 21, 41, 441). ng = 1/2 = n1 and = O. We randomly initialize PLUGIn, setting - to have independent standard normal entries. Note that the norm of o concentrates around /no, and thus generally far from the norm of the target latent vector. For each trial, say PLUGIn successfully recovers the target latent code if

---

Becumemutioo ann
Rocoery CTo
2.5
2.0
1.5
1.0
0.5
0.0
0.0
0.0
0.2
0.4
0.6
0.6
0.0
622
0.6
08
1.0
Noise signal rablo
Ncike to signal
(a) Recovery and noise level
(b) Reconstruction and noise level
10
10mk-
Reconay
10-1-
Reconste
10
x 10
6 10?
10
3
4 10"
6 10'
10'
(c) Recovery error and expansion ratio
(d) Reconstruction error expansion ratio
Figure 2: Comparison of PLUGIn (solid line) with gradient descent (dashed line). Panel (a) shows dependence relative recovery error with noise level-to-signal level from 20 independent trials. Panel (b) shows the dependence of relative reconstruction error and noise level-to-signall level. Panel (c) and (d) shows the dependence of relative recovery error and reconstruction error, respectively, with respect to the expansion ratio ng/no.
|| --'- 10-5, Figure shows the fraction of successful recoveries from 20 independent trials using the from observation as described above. Black squares corresponds to no successful recovery and white squares correspond to 100% successful recovery.
For the second experiment, we fix no 20, ni 600, ni 500, ng 500, sample noise level uniformly in the interval [0, 1]. In figures 2a and 2b the solid line corresponds to performance PLUGIn and the dotted line represents the performance of gradient descent.
Figure 2a shows the empirical dependence of the the relative recovery eπror || - x/'l|// on the noise-to-signal ratio given, given by a, from 20 independent trials. Similarly, figure 2b shows the empirical dependence of the the relative reconstruction error [|((2) G(>*) /l/ ( from 20
independent trials. The figures show that PLUGIn can be used to stably denoise signals using a generative prior with contractive layers.
For the third synthetic experiment, we fix fg = 20, noise level a 0.1 and sample nı n2 = ng in the interval [200, 5000]. Figures 2 and 2d show the empirical dependence of relative recovery error | x ||/||=* and relative reconstruction error [|]($) ((x*)] (xx*)] ]], respectively, on
the expansion ratio na/nng from 20 independent trials. In figures 2c and 2d the solid line corresponds
to PLUGIn and the dotted line corresponds to gradient descent. The figures confirm the lincar dependence in the recovery and reconstruction emrors of PLUGIn, in log scale, with respect pa/no.
provided n,, for all Z are sufficiently large compared to ngg.
We now empirically show that PLUGIn can effectively remove noise synthetically introduced to MNIST images and compare its performance to gradient descent. We trained a VAE (27] using Adam optimizer [28] with learning rate of 0.001 and mani-batch size 100 on the MNIST dataset consisting 60,000 number 28 28 images handwritten digits 29]. The latent code dimension of the trained network G is 20 and the decoder network in the VAE is fully connected network with parameters 20- 500 500 784. Finally, noisy image y generated via pixelwise addition an
image from the MNIST database and noise vector [8781 i.c. y² + u. In all MNIST

---

3
0 1 2 3 4 5 6 7 9
0 0 2 3 4 5
6
8 9
7
Figure 3: The figure shows the result denosing an image using PLUGIn and gradient descent. The top row corresponds noisy image. The second and third row corresponds to images recovered using PLUGIn and gradient descent, respectively.
experiments,
fixed step size of 1/7 for PLUGIn, where 7 is the product of the operator norms of the weight matrices; for gradient descent, we use parameter 1000 to move along the gradient descent direction computed using PyTorch. Similar to the synthetic experiment. we run PLUGIn and gradient descent each for 10,000 iterations, or until the difference norm between consecutive iterations is less than 10-18 times the norm of the current iterate, whichever comes first.
In figure 3 the images in the top row are the observations, the images in the second row and third row are the recovered images corresponding to PLUGIn and gradient descent, respectively. Figure shows the result using PLUGIn and gradient descent to remove noise sampled uniformly over the sphere 778 from observation y. The noise level was adjusted so that the signal-to-noise ratio is in the interval [50, 200]. with 50 corresponding to the leftmost column and 200 corresponding to the rightmost one.
5 Final Remarks
Extension to positively homogeneous activation functions
Our proofs and results can be extended to generative model & with positively homogeneous activation functions (such as Leaky ReLU). To see this, we modify the definition for [(u, o; w) in Lemma to
Z(u, w) = (Au, (Av)) o(Aw) - X Xu, ww.
where À = Eg- (g) with g ~ (O, 1), and change the step size from = 2d to A-d The random process 7(n. U; w) remains centred (Appendix A Lemma 2) and one prove similar version of Lemma Moreover, in the multi-layer case, the range at each layer is still contained in a union of dimdinnnsi (affine) subspaces in Ih (Appendix C Lemma 7 prove a version of Theorem in this case.
similarly
Limitations
In Theorem assumed that weight matrices independent and Gaussian. Although this is a commonly used assumption in literature (e.g. [TC [1 12] analysis, practitioners may wonder whether theory based upon this assumption instructive towards predicting convergence when the algorithm is applied to generative models with learned weights. Our experiments with MNIST give some evidence that the algorithm does indeed generalize. Without the Gaussian assumption, one needs a heuristic for choosing the step size. We find that the inverse of the product of the norm of the weight matrices works well. Secondly, in numerical experiments, comparison between PLUGIn and gradient descent over synthetic data seems to suggest that PLUGIn has error with similar dependence on parameters to gradient descent, but with larger constant.
14
17
19 23 for theoretical
Activation functions satisties (at) (t for all 2 and E R.

---

Acknowledgments and Disclosure of Funding
Y. Plan is partially supported by an NSERC Discovery Grant (GR009284), an NSERC Discovery Ac- celerator Supplement (GR007657), and Tier II Canada Research Chair in Data Science (GR009243). O. Yılmaz partially supported by an NSERC Discovery Grant (22R82411) and Pacific Institute for the Mathematical Sciences (PIMS) CRG 33: High-Dimensional Data Analysis. B. Joshi is partially supported by the Pacific Institute for the Mathematical Sciences (PIMS). (The research and findings may not reflect those of the Institute.)
References
[1] Harold C. Burger, Christian J. Schuler, and Stefan Harmeling. Image denoising: Can plain neural networks compete with hm3d? 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 239222399,, 2012.
[2] Karol Gregor, Frederic Besse. Danilo Jimenez Rezende, Ivo Danihelka, and Daan Wierstra. Towards conceptual compression. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, aditors,Avvancee in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[3] Shibani Santurkar, David Budden, and Nir Shavit. Generative compression. In 2018 Picture Coding Symposium (PCS), pages 258-262, 2018.
[4] D.L.. Donoho. De-noising by soft-thresholding, IEEE Transactions Information Theory, 41(3):613-627, 1995.
[5] M. Aharon, M. Flad, and A. Bruckstein. K-svd:
An algorithm for designing overcomplete dictionaries for sparse representation. IEFE Transactions on Signal Processing, 54(11):431 1):4311 -4322, 2006.
[6] Michael Elad and Michal Aharon, Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing,
2006.
[7] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of GANs for improved quality, stability, and variation. In International Conference on Learning Representations, 2018.
[8] Hoo-Chang Shin, Neil A. Tenenholtz, Jameson K. Rogers, Christopher G. Schwarz, Matthew L. Senjem, Jeffrey L. Gunter, Katherine P. Andriole, and Mark Michalski. Medical image synthesis for data aug- mentation and anonymization using generative adversarial networks. In Ali Gooya, Orcun Goksel, Ipek Oguz, and Ninon Burgos, editors, Simulation and Synthesis in Medical Imaging, pages 1-11, Cham, 2018. Springer International Publishing.
[9] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In 2019 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 4336-44000 2019.
[10] Reinhard Heckel, Wen Huang, Paul Hand, and Vladislav Voroninski. Rate-optimal denoising with deep neural networks. Information and Inference: A Journal of the IMA, 06 2020. iaaa0l
[11] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In International Conference on Machine Learning, pages 537-546, PMLR, 2017.
[12] Paul Hand and Vladislav Voroninski. Global guarantees for enforcing deep generative priors by empirical risk. CORR, abs/1 0as///005.07776 2017.
[13] Viraj Shah Chinmay Hegde. Solving linear inverse problems using gan priors: An algorithm with provable guarantees. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4609 4613, 2018
[14] Wen Huang, Paul Hand, Reinhard Heckel, and V. Voroninski. A provably convergent scheme for com- pressive sensing under random generative priors. Journal of Fourier Analysis and Applications, 27:1-34, 2018.
[15] Ganlin Song, Zhou Fan, and John Lafferty. Surfing: Iterative optimization over incrementally trained deep networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Bol Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8 14, 2019, Vancouver, BC, Canada, pages 15008- 15017, 2019.
10

---

[16] Fabian Latorre, Armin eftekhari, and Volkan Cevher. Fast and provable admm for learning with generative priors. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advancey Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[17] Paul Hand, Oscar Leong, and Vladislav Voroninski. Phase retrieval under generative prior. CoRR. abs/1807,04e 04261, 2018
[18] Muhammad Asim, Fahad Shamshad, and Ali Ahmed. Solving bilinear inverse problems using deep generative priors. CoRR, abs/1882.04073, 2018.
[19] Paul Hand and Babhru Joshi. Global guarantees for blind demodulation with generative priors. In H. Wallach, Larochelle, A. Beygelzimer, d'Alché-Bue, Fox, R. Garnett, editors, Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[20] Jorio Cocola, Paul Hand, and Vladislav Voroninski. statistical computiialllommutaationnaall gap spiked matrix models with generative network priors. Entropy, 23(1), 2021.
[21] David R. Brillinger. Generalized Linear Model With "Gaussian" Regrexsor Variables, pages 589-606. Springer New York, New York, NY, 2012.
[22] Yaniv Plan and Roman Vershynin. The generalized lasso with non-linear observations. IEEE Transactions on Information Theory, 62(3):1528-11) 1537, 2016.
[23] Constantinos Daskalakis, Dhruv Rohatgi, and Manolis Zampetakis. Constant-expansion suffices for compressed sensing with generative priors. CoRR, abs/2006.04237, 2020.
[24] Sjoerd Dirksen. Tail bounds via generic chaining. Electron. Probab., 20(53):1-29. 2015.
[25] Jiri Matousek. Lectures discrete geometry, volume 212. Springer Science & Business Media, 2013.
[26] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vetooo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. NIPS-W. W, 2017.
[27] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[28] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[29] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applicd to document recognition. P Proceedings of the IEEE, 86(1)) (6(11)2278-2324, 1998.
[30] Simon Foucart and Holger Rauhut. Mathematical Introduction to Compressive Sensing. Birkhäuser, New York, NY, 2013.
[31] Roman Vershynin. -igee-iinnsoonal Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[32] Michel Talagrand. The generic chaining: upper and lower bounds of stochastic processes. Springer Science & Business Media, 2006.


Reviews:
[{"review_id": "ovlxSVfYVem", "reviewer": "Reviewer_eL82", "summary": "This paper introduces an algorithm for recovering an unknown latent code vector under a specific generative model: a deep generative network with ReLU activation functions. Innovation of paper compared with [10] is to show that one drops the $D_j$ and still recover an accurate estimate of $x^*$. Theoretical results on geometrical convergence to a neighborhood of $x^{*}$ are confirmed by experiments on synthetic random data and MNIST images.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Unfortunately, I don't familiar quite well with generalized Dudley’s integral theory, so the questions are about numerical experiments:\n`1. Did you try to check your method for other image datasets (for example CIFAR10)?\n2. Figures 2c and 2d show that gradient descent numerically faster converges compared with PLUGIn. Does your method work much faster than SGD? Evaluations on time comparison for image/synthetic datasets and additional comments on the performance of PLUGIn compared with SGD are recommended.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "fGxy_QYH9X", "reviewer": "Reviewer_67vh", "summary": "This paper studies the question of inverting a generative model; formally, given relu network G and a noisy observation y = G(x^*) + eps, approximately recover x. Similar to existing works in this literature, they assume the weight matrices in G are all Gaussian, suitably scaled. But whereas previous works needed to assume expansivity, namely that at each layer the ratio between output and input dimensions is at least some universal constant (or more), this paper only requires that the ratio between the output dimension of any layer L and the input dimension of *the network itself* scales at least exponentially in L. In particular, they can handle networks where some of the intermediate layers are contractive, as long as the network is expansive \"on average\" across layers.\n\nIn this setting, they analyze the update rule x' <- x - eta M^T(G(x) - y), where M is the product of the weight matrices, and show that it converges exponentially quickly to a neighborhood of x^*. Their assumption on eps is very mild: it just needs to be independent of the randomness of the weight matrices.\n\nThe motivation for this update rule is that when eps = 0, after a single step from an arbitrary initialization, the next iterate is equal to x^* in expectation with respect to the randomness of the weight matrices. This is not true for subsequent iterates as they depend on this randomness, but one can nevertheless look at the norm of the distance between any iterate and x^*. To break the dependence, the author(s) upper bound this by the sum of suprema of certain random processes corresponding to the different layers of the network. They give a high probability bound for these suprema via a chaining argument. The key fact that lets them avoid the need for expansivity is that these processes are over points that lie in a union of subspaces whose dimension is given by the *input dimension of the network*.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Inverting generative models is a very clean and well-motivated algorithmic challenge, and this paper contributes many interesting new ideas for this problem. From the point of view of the algorithm, existing approaches for this problem rely on showing that that the landscape for the square loss L(x) = ||G(x) - y||^2 is benign with high probability for expansive networks, so that gradient descent with respect to L converges to an approximate inverse for y. In this context, it is quite innovative to study the alternative update rule in this paper, and the fact that it works just as well for this problem and can even handle non-expansive networks is very interesting. \n\nFrom the point of view of the analysis, existing works are based on verifying that a tall and skinny Gaussian weight matrix whp satisfies a certain \"weight distribution condition\" which one could also interpret as a bound on the supremum of some random process, this is by definition a condition that must hold *layer-by-layer* for the Hand-Voroninski-style analysis to apply. In contrast, the random processes that this paper considers are defined in terms of *sub-networks* of G rather than individual layers, which is why one can hope to get away with \"expansivity on average\" rather than strict expansivity.\n\nAdditionally, the technical details are well-written, and the example calculations in the first nine pages give the reader a good sense for how their proof works at a high level. I would enthusiastically recommend acceptance.\n\nMinor comments:\n- What are the obstacles for handling the setting where one only has compressive measurements of y?\n- Caption for Figure 2 should be self-contained, i.e. should write that solid line is PLUGin and dotted line is gradient descent.\n- In the display below line 462 of supplement, fix formatting for absolute values in |\\sum^m_{i=1} X_i|\n- Line 517 of supplement: capitalize \"proof\"\n- Line 559 of supplement: \"result\" -> \"results\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There does not appear to be potential negative societal impact. Additionally, the authors clearly acknowledge the primary limitation of the result is the Gaussianity assumption, which is standard in this literature.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dAVT24gvKRy", "reviewer": "Reviewer_yoTL", "summary": "This paper proposes an algorithm to solve the problem of inverting random generative models from noisy measurements where the weights of the model are drawn from $\\mathcal{N}(0, 1/n)$ where n is the width of the corresponding layer, and the activation function is a ReLU unit. \n\nTheir proposed algorithm \"Partially Linearized Update for Generative Inversion\" (PLUGIn) is a simple iterative algorithm where each iterate is given by $x^{k+1} = x^k - \\eta A_1^T \\dots A_d^T (\\mathcal{G}(x^k) - y)$. The authors demonstrate that \n\n1. PLUGIn requires 2 blackboxes, (1) $\\mathcal{G}(x^k)$ for every $x^k$ and (2) $ A_1^T \\dots A_d^T $. \n2. They show that for generative priors with possibly contractive layers, PLUGIn can effectively estimate the unknown signal from noisy observations, at a geometric rate. \n3. In the presence of noise independent of the weight vector, the reconstruction error corresponding to $x^k$ for large enough $k$ goes as $\\sqrt{4^d n_0/n_d}\\| \\epsilon \\|$. \n\nThe proof of the result relies on simple properties of Gaussian matrices. In the case of the first layer it is enough to see that $E[A^T \\sigma(Ax)] = 1/2 x$ and so with $\\eta = 2$ we are done, for subsequent layers one needs to account for bias that creeps in and increase $\\eta$ layer-wise. The authors overcome this by developing a series of uniform deviation inequalities, and bounding the resulting error. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I think this is a good paper and makes progress in understanding when and how generative models are invertible. Prior work had intermediate layers with diagonal matrices, and could not tolerate noise that was only independent of the weight matrices. \n\nI have read the author response. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper and of limited societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of inverting a generative model. More precisely, we are given a ReLU network $G$ and we observe $y = G(x^*) + \epsilon$ and the goal is to recovery $x^*$. The paper gives strong provable guarantees under much milder assumptions than in earlier work. Earlier work of Hand and Voroninski gives recovery guarantees when the weights matrices in the network are Gaussian and each layer is expansive. This paper is able to weaken the former condition to an expansion on average. In particular some layers can be contractive, as long as the ratio of their output to the size of the input to the network is large. Further they give a simple iterative algorithm. The intuition behind it is clear, however the technical analysis is complicated by the fact that the iterates depend on the randomness. All the reviewers agreed that this paper takes a definitive step forward on an important class of problems. 
Decision: Accept (Spotlight)