# On the Fine-Grained Hardness of Inverting Generative Models

arXiv: https://arxiv.org/abs/2309.05795 · HTML: https://mlsanity.com/paper/2309.05795/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 46 references that are in the map.
- First posted on arXiv 11 Sep 2023.

## Builds on (most cited first, 30 of 31)

- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Deep Image Prior](https://mlsanity.com/paper/1711.10925/) (2017)
- [GAN Inversion: A Survey](https://mlsanity.com/paper/2101.05278/) (2021)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Invertible generative models for inverse problems: mitigating representation error and dataset bias](https://mlsanity.com/paper/1905.11672/) (2019)
- [One Network to Solve Them All --- Solving Linear Inverse Problems using Deep Projection Models](https://mlsanity.com/paper/1703.09912/) (2017)
- [Solving Linear Inverse Problems Using GAN Priors: An Algorithm with Provable Guarantees](https://mlsanity.com/paper/1802.08406/) (2018)
- [Deep Compressed Sensing](https://mlsanity.com/paper/1905.06723/) (2019)
- [Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk](https://mlsanity.com/paper/1705.07576/) (2017)
- [Inverting Deep Generative models, One layer at a time](https://mlsanity.com/paper/1906.07437/) (2019)
- [Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors](https://mlsanity.com/paper/1906.08763/) (2019)
- [Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models](https://mlsanity.com/paper/1908.10744/) (2019)
- [Learning to Invert: Signal Recovery via Deep Convolutional Networks](https://mlsanity.com/paper/1701.03891/) (2017)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2205.06249/) (2022)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [Fast and Provable ADMM for Learning with Generative Priors](https://mlsanity.com/paper/1907.03343/) (2019)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [A Provably Convergent Scheme for Compressive Sensing under Random Generative Priors](https://mlsanity.com/paper/1812.04176/) (2018)
- [Provable Compressed Sensing with Generative Priors via Langevin Dynamics](https://mlsanity.com/paper/2102.12643/) (2021)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails](https://mlsanity.com/paper/1404.1448/) (2014)
- [Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping](https://mlsanity.com/paper/1502.01063/) (2015)
- [If the Current Clique Algorithms are Optimal, so is Valiant's Parser](https://mlsanity.com/paper/1504.01431/) (2015)
- [Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry](https://mlsanity.com/paper/2110.10283/) (2021)
- [On the Quantitative Hardness of CVP](https://mlsanity.com/paper/1704.03928/) (2017)
- [Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)](https://mlsanity.com/paper/1911.02440/) (2019)

## Built on by (most cited first, 1 of 1)

- [Hidden in the Noise: Two-Stage Robust Watermarking for Images](https://mlsanity.com/paper/2412.04653/) (2024)

## Abstract (arXiv)

The objective of generative model inversion is to identify a size-n latent vector that produces a generative model output that closely matches a given target. This operation is a core computational primitive in numerous modern applications involving computer vision and NLP. However, the problem is known to be computationally challenging and NP-hard in the worst case. This paper aims to provide a fine-grained view of the landscape of computational hardness for this problem. We establish several new hardness lower bounds for both exact and approximate model inversion. In exact inversion, the goal is to determine whether a target is contained within the range of a given generative model. Under the strong exponential time hypothesis (SETH), we demonstrate that the computational complexity of exact inversion is lower bounded by Omega(2n) via a reduction from k-SAT; this is a strengthening of known results. For the more practically relevant problem of approximate inversion, the goal is to determine whether a point in the model range is close to a given target with respect to the ℓp-norm. When p is a positive odd integer, under SETH, we provide an Omega(2n) complexity lower bound via a reduction from the closest vectors problem (CVP). Finally, when p is even, under the exponential time hypothesis (ETH), we provide a lower bound of 2Omega (n) via a reduction from Half-Clique and Vertex-Cover.