mlsanityData to 7 Oct 2026

Cryptographic Hardness of Score Estimation

arXiv 2404.03272 ↗First posted 4 Apr 2024cs.LG cs.CC cs.CRcited by 3

Not on the map. Why?

Abstract (arXiv)

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. 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).

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 46 of its 87 references that are in the map. First posted on arXiv 4 Apr 2024.

Builds on

46 of 87 references.

References · 46

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  3. 2021High-Resolution Image Synthesis with Latent Diffusion Modelscited by 18,694
  4. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  5. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,539
  6. 2022Photorealistic Text-to-Image Diffusion Models with Deep Language Understandingcited by 6,322
  7. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  8. 2021Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modelingcited by 594
  9. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  10. 2021How to Train Your Energy-Based Modelscited by 271
  11. 2022Convergence of denoising diffusion models under the manifold hypothesiscited by 237
  12. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localizationcited by 230
34 more
  1. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptionscited by 215
  2. 2023Undetectable Watermarks for Language Modelscited by 208
  3. 2022Convergence of score-based generative modeling for general data distributionscited by 179
  4. 2022Convergence for score-based generative modeling with polynomial complexitycited by 176
  5. 2023Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Datacited by 171
  6. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  7. 2022Score-Based Generative Models Detect Manifoldscited by 121
  8. 2020Generative Modeling with Denoising Auto-Encoders and Langevin Samplingcited by 118
  9. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  10. 2022Let us Build Bridges: Understanding and Extending Diffusion Generative Modelscited by 102
  11. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  12. 2020Outcome Indistinguishabilitycited by 74
  13. 2014A statistical model for tensor PCAcited by 72
  14. 2024Optimal score estimation via empirical Bayes smoothingcited by 60
  15. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  16. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  17. 2023Learning Mixtures of Gaussians Using the DDPM Objectivecited by 56
  18. 2022Planting Undetectable Backdoors in Machine Learning Modelscited by 55
  19. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  20. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  21. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Modelscited by 39
  22. 2020Continuous LWEcited by 37
  23. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  24. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  25. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  26. 2018Notes on computational-to-statistical gaps: predictions using statistical physicscited by 22
  27. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  28. 2013From average case complexity to improper learning complexitycited by 16
  29. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  30. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  31. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  32. 2014Sum-of-squares proofs and the quest toward optimal algorithmscited by 12
  33. 2013Computational Lower Bounds for Sparse PCAcited by 11
  34. 2020Statistical Query Lower Bounds for Tensor PCAcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Data Generation without Function Estimationcited by 1
  2. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 1
  3. 2026Barron Optimal Transport I: Generative Modelingcited by 0