On the Fine-Grained Hardness of Inverting Generative Models
This work addresses the fundamental computational challenges in generative model inversion, which is crucial for applications in computer vision and NLP, but it is incremental as it strengthens known hardness results with fine-grained analysis.
The paper tackles the computational hardness of inverting generative models, establishing new lower bounds for both exact and approximate inversion problems, with results including Ω(2^n) complexity under SETH for exact and odd p-norm approximate cases, and 2^{Ω(n)} under ETH for even p-norm approximate cases.
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 $Ω(2^n)$ 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 $\ell_p$-norm. When $p$ is a positive odd integer, under SETH, we provide an $Ω(2^n)$ 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 $2^{Ω(n)}$ via a reduction from Half-Clique and Vertex-Cover.