PLUGIn: A simple algorithm for inverting generative models with recovery guarantees

We consider the problem of recovering an unknown latent code vector under a known generative model. For a d-layer deep generative network G : R n0 ! R n d with ReLU activation functions, let the observation be G(x) + ✏ where ✏ is noise. We introduce a simple novel algorithm, Partially Linearized Update for Generative Inversion (PLUGIn), to estimate x (and thus G(x)). We prove that, when weights are Gaussian and layer widths n i & 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 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 G(x) are at most in the order of p 4 d n 0 /n d k✏k. 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.