On the Fine-Grained Hardness of Inverting Generative Models
Feyza Duman Keles Chinmay Hegde
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(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 $\Omega(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^{\Omega (n)}$ via a
reduction from Half-Clique and Vertex-Cover.