Abstract
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.
Introduction
Deep generative models, such as Generative Adversarial Networks (GANs) and Variational Autoencoders (VAEs), have revolutionized our ability to represent high-dimensional data distributions. These models typically map a low-dimensional latent vector $z \in \mathbb{R}^k$ to a high-dimensional signal $x \in \mathbb{R}^n$ through a series of non-linear transformations. The "inversion problem"—finding the latent code $z$ that corresponds to a given observation $x$—is a fundamental prerequisite for downstream tasks like image denoising, inpainting, and compressed sensing.
Traditionally, inversion is treated as a non-convex optimization problem, typically solved using gradient descent to minimize the reconstruction error $\|G(z) - x\|_2^2$. However, due to the non-linearity of neural networks, gradient descent is prone to getting trapped in local minima. This paper proposes a novel approach: inverting the generator one layer at a time using linear programming (LP), providing the first polynomial-time guarantees for exact recovery under constant expansion.
Methodology: Layer-wise Inversion
The core innovation of this work is the decomposition of the global inversion problem into a sequence of local, layer-wise problems. Instead of optimizing over the entire network, the algorithm works backward from the output layer to the input.
Linear Programming for ReLUs
For a single layer with ReLU activations, the inversion problem can be framed as a set of linear constraints. If the activation pattern (which neurons are "on" or "off") is known, the problem is strictly linear. To handle noise and unknown activation patterns, the authors introduce two primary LP formulations:
- $\ell_\infty$ LP: Optimized for observations with uniformly bounded noise.
- $\ell_1$ LP: Designed for robustness against more varied noise distributions.
By relaxing the requirement to explicitly know the ReLU signs, the authors formulate a convex optimization problem that can be solved efficiently using standard LP solvers.
Theoretical Analysis
The paper provides a rigorous theoretical foundation for the layer-wise approach:
- Complexity: The authors prove that while inverting a single layer is a convex problem, inverting two or more layers is NP-hard in the general case. This justifies the layer-by-layer strategy.
- Expansion Requirements: A critical finding is that exact recovery is possible if the network is "expansive." Specifically, if each layer expands the dimension by a constant factor (approximately $\ge 2.1$) and the weights are random, the LP approach succeeds with high probability. This is a significant improvement over gradient descent, which theoretically requires logarithmic expansion ($n = \Omega(k \log k)$).
Experimental Results
The proposed method was evaluated on both synthetic data and the MNIST dataset.
Synthetic Benchmarks
In noiseless settings, the LP method achieved a 100% recovery rate for significantly larger latent dimensions than gradient descent. For instance, in a specific architecture, LP maintained perfect recovery up to $k=109$, while gradient descent failed once $k$ exceeded 60.
Robustness to Noise
Quantitative analysis shows that the LP methods ($\ell_1$ and $\ell_\infty$) provide stable recovery even as noise levels increase, whereas gradient descent often fails to converge to the global minimum, resulting in a high error floor.
MNIST Performance
On real-world data, the LP approach demonstrated a massive computational advantage. Inverting a trained MNIST generator took approximately 0.5 seconds using LP, compared to 72 seconds for gradient descent. Furthermore, the LP method avoided the "hallucinations" common in gradient descent, where the optimizer produces a valid-looking but incorrect digit.
Conclusion
This work shifts the paradigm of generative model inversion from non-convex global optimization to efficient, layer-wise linear programming. By proving that constant expansion is sufficient for recovery, the authors bridge the gap between theoretical requirements and practical neural network architectures. Future work remains to extend these guarantees to non-expansive layers (bottlenecks) and more diverse activation functions.
Summary updated