Research map / Learning theory and algorithms / Sample complexity
Cryptographic Hardness of Score Estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that L2-accurate score estimation for diffusion models is computationally hard by reducing the cryptographically hard Gaussian pancakes distinguishing problem to score estimation, with the reduction building on Chen et al. (2023).
Problem
Whether L2-accurate score estimation of unknown data distributions can be done efficiently in computation and sample size, given that sampling reduces to score estimation under minimal assumptions.
Approach
A reduction from the Gaussian pancakes distinguishing problem (cryptographically hard under LWE/lattice assumptions) to L2 score estimation: a test statistic built from score estimates along the OU forward process certifies Gaussianity, so an efficient score estimator would break the hardness. Also gives a brute-force polynomial-sample score estimator via projection pursuit for parameter estimatio
Key results
- Reduction shows a polynomial-time distinguisher for Gaussian pancakes given L2 score estimates with error O(1/sqrt(log d)), so efficient score estimation would contradict cryptographic hardness.
- Under gamma*sigma = O(1), secret direction can be estimated to L2 error eta with poly(d, gamma, 1/eta) samples via brute-force projection pursuit, giving polynomial sample complexity for score estimation.
- Score functions of Gaussian pancakes are O(1/s^4)-Lipschitz and the second moment is at most d/(2pi), satisfying the Chen et al. assumptions.
Surprising findings
- Gaussian pancakes are hard to distinguish even with exact sampling oracles, so black-box use of a learned sampler cannot solve the problem, while white-box score access can.
Limitations
- Result is conditional on widely believed cryptographic (LWE-based) hardness assumptions
- Hardness only for distributions in the Gaussian pancakes family; does not rule out efficient score estimation for restricted natural distribution classes
Experimental setup
Metrics: total variation distance L2 score estimation error advantage
Builds on: Chen et al. 2023 sampling-to-score reduction Bruna et al. 2021 Gaussian pancakes hardness Gupte et al. 2022 LWE reduction to Gaussian pancakes DDPM
Closest papers by meaning
- Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals (ICML 2023 · similarity 0.86)
- Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmetic (ICML 2025 · similarity 0.82)
- How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions (ICLR 2025 · similarity 0.80)
- Dissecting Sample Hardness: A Fine-Grained Analysis of Hardness Characterization Methods for Data-Centric AI (ICLR 2024 · similarity 0.80)
- A Reliable Cryptographic Framework for Empirical Machine Unlearning Evaluation (NeurIPS 2025 · similarity 0.79)
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination (NeurIPS 2025 · similarity 0.79)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.