Inverting Deep Generative models, One layer at a time

By Qi Lei, Ajil Jalal, Inderjit S. Dhillon, A. Dimakis. 2019

58 citations recorded by the source corpus.

We study the problem of inverting a deep generative model with ReLU activations. Inversion corresponds to finding a latent code vector that explains observed measurements as much as possible. In most prior works this is performed by attempting to solve a non-convex optimization problem involving the generator. In this paper we obtain several novel theoretical results for the inversion problem. We show that for the realizable case, single layer inversion can be performed exactly in polynomial time, by solving a linear program. Further, we show that for multiple layers, inversion is NP-hard and the pre-image set can be non-convex. For generative models of arbitrary depth, we show that exact recovery is possible in polynomial time with high probability, if the layers are expanding and the weights are randomly selected. Very recent work analyzed the same problem for gradient descent inversion. Their analysis requires significantly higher expansion (logarithmic in the latent dimension) while our proposed algorithm can provably reconstruct even with constant factor expansion. We also provide provable error bounds for different norms for reconstructing noisy observations. Our empirical validation demonstrates that we obtain better reconstructions when the latent dimension is large.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Generative Models, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Generative Models

In Safety, Robustness & Interpretability

Citations in the corpus

Unsupervised 3D Shape Completion through GAN Inversion (2021, background): “Typically, the latent vector can be optimized based on gradient descent [22, 20], or projected by an extra encoder from the image space [39, 17].”
Robust Compressed Sensing MRI with Deep Generative Priors (2021, background): “[54] Qi Lei, Ajil Jalal, Inderjit S Dhillon, and Alexandros G Dimakis.”
Deep Neural Networks are Surprisingly Reversible: A Baseline for Zero-Shot Inversion (2021, background): “Besides discriminative models, [21, 53] investigate the theoretical invertibility of the deep generative model.”
Deep Learning Techniques for Inverse Problems in Imaging (2020, background): “optimization problem (4) is non-convex and actually NPhard [120].”
When and How Can Deep Generative Models be Inverted? (2020, methodology): “Interestingly, we note that the conclusions in [14, 17], suggesting that large latent spaces cause gradient descent to fail, are imprecise and valid only for ﬁxed hidden layer size.”