Cryptographic Hardness of Score Estimation
Min Jae Song
We show that $L^2$-accurate score estimation, in the absence of strong
assumptions on the data distribution, is computationally hard even when sample
complexity is polynomial in the relevant problem parameters. Our reduction
builds on the result of Chen et al. (ICLR 2023), who showed that the problem of
generating samples from an unknown data distribution reduces to $L^2$-accurate
score estimation. Our hard-to-estimate distributions are the "Gaussian
pancakes" distributions, originally due to Diakonikolas et al. (FOCS 2017),
which have been shown to be computationally indistinguishable from the standard
Gaussian under widely believed hardness assumptions from lattice-based
cryptography (Bruna et al., STOC 2021; Gupte et al., FOCS 2022).