Cryptographic Hardness of Score Estimation

arXiv:2404.03272v1 Announce Type: new
Abstract: 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 …

abstract arxiv assumptions chen complexity cs.cc cs.cr cs.lg data distribution iclr math.st parameters polynomial sample samples show stat.ml stat.th type