mlsanityData to 7 Oct 2026

On the Fine-Grained Hardness of Inverting Generative Models

arXiv 2309.05795 ↗First posted 11 Sep 2023stat.ML cs.CC cs.LGcited by 1

Not on the map. Why?

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.

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

Builds on

31 of 46 references.

References · 31

  1. 2021High-Resolution Image Synthesis with Latent Diffusion Modelscited by 18,694
  2. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,539
  3. 2016Density estimation using Real NVPcited by 2,029
  4. 2017Deep Image Priorcited by 1,097
  5. 2021GAN Inversion: A Surveycited by 366
  6. 2017Compressed Sensing using Generative Modelscited by 337
  7. 2022On The Computational Complexity of Self-Attentioncited by 137
  8. 2019Invertible generative models for inverse problems: mitigating representation error and dataset biascited by 93
  9. 2017One Network to Solve Them All --- Solving Linear Inverse Problems using Deep Projection Modelscited by 67
  10. 2018Solving Linear Inverse Problems Using GAN Priors: An Algorithm with Provable Guaranteescited by 58
  11. 2019Deep Compressed Sensingcited by 46
  12. 2017Global Guarantees for Enforcing Deep Generative Priors by Empirical Riskcited by 37
19 more
  1. 2019Inverting Deep Generative models, One layer at a timecited by 33
  2. 2019Algorithmic Guarantees for Inverse Imaging with Untrained Network Priorscited by 32
  3. 2019Information-Theoretic Lower Bounds for Compressive Sensing with Generative Modelscited by 25
  4. 2017Learning to Invert: Signal Recovery via Deep Convolutional Networkscited by 22
  5. 2018Hardness of Approximate Nearest Neighbor Searchcited by 19
  6. 2022Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimationcited by 19
  7. 2014Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)cited by 18
  8. 2019Fast and Provable ADMM for Learning with Generative Priorscited by 18
  9. 2017On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networkscited by 16
  10. 2018A Provably Convergent Scheme for Compressive Sensing under Random Generative Priorscited by 15
  11. 2021Provable Compressed Sensing with Generative Priors via Langevin Dynamicscited by 14
  12. 2021The Fine-Grained Hardness of Sparse Linear Regressioncited by 12
  13. 2014Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH failscited by 6
  14. 2015Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warpingcited by 6
  15. 2015If the Current Clique Algorithms are Optimal, so is Valiant's Parsercited by 4
  16. 2021Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometrycited by 3
  17. 2017On the Quantitative Hardness of CVPcited by 2
  18. 2019Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)cited by 2
  19. 2022Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!cited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Hidden in the Noise: Two-Stage Robust Watermarking for Imagescited by 18