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 th…