Cryptographic Hardness of Score Estimation
This establishes a fundamental computational barrier for score estimation in machine learning, which is incremental but crucial for understanding limitations in generative modeling.
The paper tackles the problem of $L^2$-accurate score estimation for data distributions without strong assumptions, showing it is computationally hard even with polynomial sample complexity, based on reductions to Gaussian pancakes distributions and lattice-based cryptography.
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).