Cryptographic Hardness of Score Estimation
Authors: Min Jae Song
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that L2-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 L2-accurate score estimation. |
| Researcher Affiliation | Academia | Min Jae Song Paul G. Allen School of Computer Science and Engineering University of Washington mjsong32@cs.washington.edu |
| Pseudocode | No | The paper describes algorithmic steps, such as the DDPM update rule (Eq. 3), but does not present them in a structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the described methodology. |
| Open Datasets | No | This is a purely theoretical paper and does not use or analyze datasets for empirical evaluation. |
| Dataset Splits | No | This is a purely theoretical paper and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | This is a purely theoretical paper and does not describe any hardware used for running experiments. |
| Software Dependencies | No | This is a purely theoretical paper and does not specify any software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | This is a purely theoretical paper and does not include details about an experimental setup, such as hyperparameter values or training configurations. |