Cryptographic Hardness of Score Estimation
Authors: Min Jae Song
Venue: NeurIPS 2024 poster (2024)
Keywords: diffusion models
score-based generative models
score estimation
statistical-to-computational gap
computational hardness
learning with errors (LWE)
Primary area: learning_theory
TL;DR: We show that L2-accurate score estimation, in the absence of strong assumptions on the data distribution, is cryptographically hard.

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

Cryptographic Hardness of Score Estimation
Min Jae Song
Paul G. Allen School of Computer Science and Engineering
University of Washington
mjsong32@cs. wewpnng2@ees.wwwinggtoo.. edu
Abstract
We show that a.c-acuuaaee score estimation, in the absence of strong assumptions on the data distribution, 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 unknown data distribution reduces to LL-accurate score estimation. Our hard-to- estimate distributions are the "Gaussian pancakes" distributions, originally due to Diakonikolas al. (FOCS 2017). which have been shown be computationally indistinguishable from the standard Gaussian under widely believed hardness assumptions from lattice-based cryptography (Bruna et al.. STOC 2021; Gupte al., FOCS 2022).
1 Introduction
Diffusion models [70, 72, 42, 73] have firmly established themselves as a powerful approach to generative modeling, serving as the foundation for leading image generation models such as DALL-E 2 [62]. Imagen [66], and Stable Diffusion [65]. A diffusion model consists of a pair of forward and reverse processes. In the forward process, noise drawn from standard distribution, such as the standard Gaussian, is sequentially applied to data samples, leading its distribution to a pure noise distribution in the limit. The reverse process, as the name suggests, reverses the noising process and takes the pure noise distribution "backward in time" to the original data distribution, thereby allowing us generate new samples from the data distribution. A key element in implementing the reverse process is the score function of the data distribution, which is the gradient of its log density. Since the data distribution is typically unknown, the score function must learned from samples [44, 78, 72].
Recent advances in the theory of diffusion models have revealed that the task of sampling, in fact, reduces
estimation under minimal assumptions on the data distribution [9, 23, 53, 61, 22, 17, 51, 6]. In particular, Chen et al. [17] have shown that T.a...--cca a.c-urceeeee score estimates along the forward process sufficient for efficient sampling. Thus, assuming access estimation, one can efficiently sample from essentially any data distribution. However, this leaves open the question of whether score estimation oracles themselves can be implemented efficiently, in terms of both required sample size and computation, for interesting classes of distributions.
oracle for I T.2-accurate score
We show that L aacccuree score estimation, in the absence of strong assumptions the data distribu- tion, is computationally hard, even when sample complexity is polynomial the relevant problem parameters. This establishes a statistical- cectifcalltt--onmee to-computational gap for -cccrraee score estimation, which refers to an intrinsic gap between what is statistically achievable and computationally feasi- ble. Our hard-to-este -o-ttmmttt distributions are the "Gaussian pancakes" distributions, which previous works [31, 13, 39] have shown are computationally indistinguishable from the standard Gaussian un- der plausible and widely believed hardness assumptions. In fact, "breaking" the hardness of Gaussian pancakes, by means of an efficient detection or estimation algorithm, has profound implications for lattice-based cryptography, which central the post-quantum cryptography standardization led by the National Institute of Standards and Technology (NIST) [58]. Building on the sampling-to-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

score estimation reduction by Chen et al. [17], we show that computationally efficient L accurate score estimation for Gaussian pancakes implies an efficient algorithm for distinguishing Gaussian pancakes from the standard Gaussian. Thus, while sampling may ultimately reduce to I,2 a.caucte score estimation under minimal assumptions on the data distribution, score estimation itself requires stronger assumptions on the data distribution for computational feasibility. It is worth noting that the presence of statistical-to toniiiccllt--ommptttttonnnd gaps in L'-accurate score estimation was anticipated by Chen et al. [17, Section I.1], who mentioned it without formal statement or proof.
1.1 Main contributions
Our main result is a simple reduction from the Gaussian pancakes problem (i.c., the problem of distin- guishing Gaussian pancakes from the standard Gaussian) to I'²-accraaee score estimation. We show that given oracle access to acccuuaee score estimates along the forward process (Assumption A3), one can compute a test statistic that distinguishes, with non-trivial success probability, whether the given score estimates belong to a Gaussian pancakes distribution or the standard Gaussian.
A Gaussian pancakes distribution P., with secret direction E gd-1 can be viewed as a "backdoored" Gaussian, It is distributed as a (noisy) discrete Gaussian along the direction u and as a standard Gaussian in the remaining d 1 directions (see Figure 1). A class of Gaussian pancakes (Pu) ME8--1 is parameterized by two parameters, y and Ør, which govern the spacing and thickness of pancakes, respectively. For instance, Gaussian pancakes distribution P.. with spacing Y and thickness a R is essentially supported on the one-dimensional lattice 1Z/ along the secret direction u. The Gaussian pancakes problem, then, is sequence of hypothesis testing problems indexed by the data dimension d E N in which the goal is to distinguish between samples from a Gaussian pancakes distribution (with unknown u) and the standard Gaussian distribution (N Ia) with success probability slightly better than random guessing (see Section 2.3 for formal definitions). Thus, our result can be summarized informally as follows.
Theorem 3.1). Let ((d) (.0(d) O be sequences such that 2 1 1/poly(() (d) and the corresponding (7,0) -aaussinnn pancakes distributions (Pu)ugga-1 all satisfy (V,,,,NN Ia)) 1/2. Then, there exists a polynomial-imme randomized algorithm with access to a score estimation oracle of T?2-rroo O(1/ //og that solves the Gaussian pancakes problem.
Theorem 1.1 (Informal,
We emphasize that the hardness of estimating score functions of Gaussian pancakes distributions arises solely from hardness of learning. The score function of Pu is efficiently approximable by function classes commonly used in practice for generative modeling, such as residual networks [40]. In addition, under the scaling oy = O1), which includes the cryptographically hard regime, the secret parameter u can be estimated upto ~ 17 via brute-force search over g with poly(d, 7, 1/n) samples (Theorem 4.2). The estimated parameter á in turn enables -acuurrte score estimation (see Section 4). Our estimator, based on projection pursuit [35, 43], may be of independent interest.
We also analyze properties of Gaussian pancakes using Banaszezyk's theorems the Gaussian mass of lattices [3, 74]. This serves two purposes. Firstly, it allows us to verify that Gaussian pancakes distributions readily satisfy the assumptions for the sampling-to-scon
estimation reduction of Chen et al. [17], namely Lipschitzness of the score functions along the forward process (Assumption Al). This is necessary as the proof of our main theorem crucially relies on the reduction. Secondly, Banaszezyk's 's theorems provide simple means of analyzing properties of Gaussian pancakes, which interesting mathematical objects in their own right. While these theorems are standard tools in lattice-based cryptography (see e.g., [74, IJ), they are likely less known outside the community.
1.2 Related work
Theory of diffusion models. Recent advances in the theoretical study of diffusion models have focused on convergence rates of discretized reverse processes [9, 23, 53, 61, 22, 17, 51, 6]. Of particular relevance to our work is the result of Chen et al. [17] who showed that a,aaccurate score estimates are sufficient to guarantee convergence rates that are polynomial in all the relevant problem parameters under minimal assumptions on the data distribution, namely Lipschitz scores throughout the forward process and finite second moment. Prior studies fell short by requiring strong structural assumptions on the data distribution, such as a log- Sobolee inequality [50, 82], assuming
An animated visualization of Gaussian pancakes be found in [12].

---

Ponyy Waaar aidie
1.0
-00
0.0
0.5
1.0
1100
-05
0.0
-1.0
-05
0.0
0.5
1.0
1.5
1.0
0.5
0.0
0.5
1.0
1.5
1.
1.0
0.5
0.0
0.5
1.0
1.5
1.5
1.0
0.5
0.0
0.5
1.0
1.5
0.01
0.05
0.25
Figure 1: Top: Scatter plot of 2D Gaussian pancakes Pu with secret direction u = (-1//2, 1/v2), f0.01, 0.05, 0.25). Bottom: Re-scaled probability densities of Gaussian pancakes (blue) for each {0.01, 0.05, 0.25] and the standard Gaussian (black) along u. For fixed 7, the pancakes "blur into each other" increases.
spacing y 6, and thickness
L accurate score estimates [23], or providing convergence rates that are exponential in the problem parameters [9, 23, 22]. We note that recent works have made the "minimal" assumptions of Chen et al. [17] even more minimal by considering early stopped reverse processes and dropping the Lipschitz score assumption [15, 6]. We refer to the book draft Chewi [19] for more background.
Gaussian pancakes. The Gaussian pancakes problem stands out among problems exhibiting statistical-to-con torssticclto-oommpuaattonallllll gaps due to its versatility and strong hardness guarantees. Initially intro- duced hard-to-learn Gaussian mixtures in the work of Diakonikolas al. [31], which established their SQ hardness, Gaussian pancakes have been extensively utilized in establishing SQ lower bounds for various statistical inference problems such robust Gaussian mean estimation [31] and agnos- tically learning halfspaces and ReLUs over Gaussian inputs [28]. For further details, we refer to the textbook by Diakonikolas and Kane [29, Chapter 8). Gaussian pancakes distributions them- selves serve as instances of fundamental high-dimensional inference problems such as non-Gaussian component analysis [8] and Wasserstein distance estimation in the spiked transport model [57].
Bruna et al. [13] initiated the exploration of the cryptographic hardness Gaussian pancakes. They showed that assuming hardness of worst-case lattice problems, fundamental to lattice-based cryptography [56, 60], both the Gaussian pancakes and the closely related continuous learning with errors (CLWE) problems hard. Follow-up work by Gupte al. [39] showed that the learning with errors (LWE) problem [63], a versatile problem which lies at the heart of numerous lattice- based cryptographic constructions, reduces to the Gaussian pancakes well. These cryptographic hardness results have sparked a wave of recent works showcasing various applications of this newly discovered property of Gaussian pancakes. Notable examples include planting undetectable backdoors in machine learning models [38], novel public-key encryption schemes based on Gaussian pancakes [10], and cryptographic hardness of agnostically learning halfspaces 75).
For additional related work on score estimation and statistical-to-compuaaiec gaps, see Section A.
1.3 Future directions
Our work brings together the latest advances from the theory of diffusion models and computational complexity of statistical inference. This intersection provides fertile ground for future research, some avenues of which outline below.

---

Stronger data assumptions for efficient score estimation. Our result shows that for any class of distributions that encompasses hard Gaussian pancakes, computationally efficient L'-acccrate score estimation is impossible. This implies that stronger assumptions on the data, which exclude Gaussian pancakes, are necessary for efficient score estimation, Finding assumptions that exclude hard instances while being able to capture realistic models of data is an interesting open problem.
Weaker criteria for evaluating sample quality. In the context of learning Gaussian pancakes, if the goal of the sampling algorithm were to merely fool computationally bounded testers that lack knowledge of the secret u E gd-1, then it could simply generate standard Gaussian samples and fool any polynomial-time test. Thus, sampling is strictly easier than a.C-accu score estimation the criteria for evaluating sample quality is less stringent. This suggests exploring sampling under different evaluation criteria, such as "discriminators" with bounded compute or memory. For example, Christ et al. [20] have used weaker notions of sample quality in the context of watermarking large language models (LLMs). More precisely, they used the notion of computational indistinguishability to guarantee quality of the watermarked model relative to the original model. Exploring potential connections to the literature on leakage simulation [45, 18, 76] and outcome indistinguishabiiit [41, 32, 33] is also an interesting future direction, these areas have addressed related questions for distributions on finite sets.
Extracting "knowledge" from sampling algorithms. A key difficulty in directly reducing the Gaussian pancakes problem to sampling is that the Gaussian pancakes problem is hard for polynomial- time distinguishers, even with access to exact sampling oracles (see Section 2.3 for more details)." Thus, any procedure utilizing the learned sampler in black box manner cannot solve the Gaussian pancakes problem. This is puzzling since for the algorithm to have "Icarned" to generate samples from the given distribution, it ought to possess some non-trivial information about it (e.g., leak information about the secret parameter u.)
This raises the question: How much "knowledge" can we extract with white box access to the sampling algorithm? Under reasonable structural assumptions on the sampling algorithm, can we extract privileged information about the data distribution it simulates, beyond what is obtainable solely via sample access? Our work provides one such example. White box access to a diffusion model gives access to its score estimates. These score estimates, which enable efficient solutions to the Gaussian pancakes problem, constitute privileged knowledge that cannot be learned efficiently even with unlimited access to bona fide samples.
Preliminaries
Notation. We denote by (at) the sequence a1, 02 a3. indexed by E N. When there is no natural ordering on the index set (e.g., (au)uege-1), we interpret it as set. We write a S b or (()) to mean that a S Cb for some universal constant C > O. The notation a 2 b and are defined analogously. We write x b or a (b)) to mean that S b and 2 both hold. We write A, V to mean logical AND and OR, respectively. We also write a A b and a V to mean min b) and max(a, b). respectively. We denote by Qa the "standard" Gaussian (0, (a (see Remark 2.3). We omit the subscript d when it is clear from context.
((bb)
2.1 Background on denoising diffusion probabilistic modeling (DDPM)
We give a brief exposition on denoising diffusion probabilistic models (DDPM) [42], a specific type of diffusion model, since the main reduction of Chen et al. [17] pertains to DDPMs. This section closely follows [17, Section 2.1] and [80, Section 3]
Let D be the target distribution defined on Rdd In DDPMs, we begin with the forward process, an Ornstein-Uhlenber
(OU) process that converges towards Q = -O(0, (1/27) which is described by the following stochastic differential equation (SDE). Note that the constant 1/vT / in front of dW, in (1) non-standard.' 3 See Remark 2.3 for an explanation of our unconventional choice of
Note, however, that algorithms that run in time T can query the sampling oracle most T times, so the running time imposes a limit on the number of samples the algorithm can see. Thee usual choice is 22, for which the stationary distribution is ( Ia).

---

variance for the resulting stationary distribution Q.
dX, -x,tt (1/VT)dW;
Xo Do D
(I)
where W is the standard Brownian motion in IR..
Let D, be the distribution of X, along the OU process. It is well-known that for any distribution D, Dj + Q exponentially fast in various divergences and metrics such as the KL divergence [2]. this work, we only consider Gaussian pancakes (Pu) and the standard Gaussian Q. If D Pa and > O, then the distribution D; is simply another Gaussian pancakes distribution with a larger thickness parameter (see Definition 2.5). Meanwhile, if D Q, then D, Q for any 2 O. We run the OU process until time T' > 0, and then simulate the reverse process, described by the following SDE.
dy, = (Y, + (1/T)V/u log Dr DT-:(Y))dd + (1/VT)dW,,
Yo ~ Fo Dr
(2)
Here, V log Dj is called the score function of D,. Since the target is not known, order to implement the reverse process the score function must be estimated from data samples. Assuming for the moment that we have exact scores (V log Dr)te (n,7]. if we start the reverse process from Fo Dr, have Y, F2 Dr for any 0 S l S T, and ultimately Yr Fr D. Thus, starting from (approximately) pure noise Dy s Q, the reverse process generates fresh samples from the target distribution D. We need to make several approximations algorithmically implement this reverse process, In particular, we need to approximate Dr by Q, discretize the continuous-ting SDE, and approximate scores along the (discretized) forward process. Let h be the step size for the SDE discretization and denote N := T/h. Given score estimates performs the following update (see e.g., [67, Chapter 4.3
the DDPM algorithm
y ex ys (1/T)(e* 1)s(N (B)NN)))((R))) + c 12g
where 2* ~ Q is an independent Gaussian vector. Note that the only dependence of the reverse process the target distribution D arises through the score estimates (SKA)
The result of Chen et al. [17] demonstrates polynomial convergence rates of this process the target distribution D. assuming access to L accurate score estimates (SH4)RE[N) and minimal conditions on the target D. We refer to Section 3.1 for formal statement of their assumptions and theorem.
2.2 Lattices and discrete Gaussians
Lattices. A latfice & C Rd is discrete additive subgroup of RRd. In this work, we assume all lattices are full rank, i.e., their linear span is Rd For a d-dimensional lattice L, a set of linearly independent vectors {b), .... bJ} is called a basis of L if C is generated by the set, i.c., L Bzd where B = [b..... ba....,,,], ba]. The determinant of a lattice C with basis B is defined as det(C) = det(B))
The dual lattice of lattice L. denoted by L* is defined
L = { E T
(I, y) E Z for all x E C)
If B is basis of C then (BT)-1 is basis of L*; in particular, det(C*) det(C)-1
Fourier analysis.
We define the Fourier transform of function f _2 by
B(w) - [(x) exp(eexppieepee -201-(2 yar
The Poisson summation formula offers a valuable tool for analyzing functions defined on lattices. Lemma 2.1 (Poisson summation formula). For any lattice L C R2d and any fanction f Rdd C,
f(c) = del(C") "(()),
where we denote f(S) - f(x) for any set S.
"To be precise, f must satisfy niceness conditions; this will always hold in applications.
5

---

Discrete Gaussians. A discrete Gaussian is discrete distribution whose probability mass function given by the Gaussian function. These distributions are closely related to Gaussian pancakes distributions and their properties will be crucial for our analysis.
Definition 2.2 (Gaussian function). We define the Gaussian function Ps I R of width & by
Pa(x) == exp [<<]|=||<>]1//""
When s 1, we omit the subseript and simply write p. In addition, for any lattice L IR4,, we denote by (C) = Emec (z) the corresponding Gaussian mass of L.
Remark 2.3 -oon-standard choice of "standard" variance). We refer to Qa NoO,, 1/( as the "standard" Gaussian. This indeed the standard choice in lattice-basse cryptography because simplifies normalization factors that arise from laking Fourier transforms. For instance, it allows us to simply write Ps 8 P1/s and P pffor
To translate these results for the "usual" standard Gaussian, we can simply replace with s/ /2xx for each occurrence.
Definition 2.4 (Discrete Gaussian). For any lattice L C IRd, parameter > O, and shift E IR4, the discrete Gaussian D D-tt,s a distribution supported on the coset C t with probability mass
Pa -t)
Dr De-e,x(x))
Ps PL -t
We denote by A, the discrete Gaussian of width 1 supported on the one one-dimensional lattice (1/7)Z, The distribution of a Gaussian pancakes distribution Pu along the hidden direction is smoothed discrete Gaussian, which we formalize in the following.
Definition 2.5 (Smoothed discrete Gaussian). For any Y > 0, let A, be the discrete Gaussian of width 1 the lattice (1/7)).. We define the o-smoothed discrete Gaussian AG, the distribution of the random variable y induced by the following process.
V (a 02),
where x ~ Ay and 2 ~ Q
Furthermore, the density of A? is given by
VI+
pplk/t)Powiiad 1ockk/7VV 1ocokk////+0/ A²((2) Op((1/7)Z)
Σ KEE
(4)
Likelihood ratio of smoothed discrete Gaussians. Let A be the a-smoothed discrete Gaussian on (1/y)Z. likelihood ratio T with respect to the standard Gaussian is given by
VI+
(2) (p((L/7)z)
- V1to-11+o2k//
(5)
KEZ
When y and a are clear from context, we omit them and simply denote the likelihood ratio by T.
2.3 Gaussian pancakes
We define Gaussian pancakes distributions using the likelihood ratio T = A Q. It is important note that our parametrization differs from the one used in previous works [13, 39]. We believe our parametrization more convenient as it elucidates a natural partial ordering on the space of parameters (y, o... addition, there an explicit mapping between the different parametrizations, so computationally hard parameter regimes identified by previous works [13, 39] can readily be translated into setting. See Remark 2.7 for more details.
Definition 2.6 (Gaussian pancakes). For any d E N, spacing and thickness parameters 7, 0, we define the (7, .r) -Gaussian pancakes distribution P with secret direction Sd-1 by
(T) == Q(x) T, ((xr, u))
where Q NoO, (1/2x)Ta) and T is the likelihood ratio of AG, with respect to Q. When parameters Y, a are clear from context, we omil them in the notation and simply denote the distribution by Pa, to avoid clutter.

---

Remark 2.7 (Partial ordering on Gaussian pancakes), The smoothed discrete Gaussian A?, arises
in the OU process for the discrete Gaussian Ay at time log [vI++*) Consequently, for any fixed Y > 0, there exists natural partial ordering on the family of Gaussian pancakes parametrized by (). given by (7, 1) S 02) whenever σ S 02. This ordering arises from the fact that Aq reduces to A whenever di S 02 via the OU process starting at t = log [v1+0] and run until 12 = log [ +2))-
Definition 2.8 (Advantage). Let A: X - 10, 1 be any decision rule (i.e., distinguisher). For any pair of distributions (P, 2) on X, we define the advantage of A by
a(A) = PIA(()) = 11 -
11|
For a sequence of decision rules (As)den and distribution pairs (Pa. Qa)dEN, we say (Ad) has non-negligible advantage with respect to (Pa. Qa) if its advantage sequence ad = a(Aa) is non-negligible function d, i.e., a function in ((dd"))oorr some constant >
Definition 2.9 (Computational indistinguishabilit).. A sequence of distribution pairs (Pa, Qa) is computationally indistinguishable if no poly -timee computable decision rule achieves non- negligible advantage.
Definition 2.10 (Gaussian pancakes problem). For any sequences (d) 0 and n(d) e N, the (7), o, n) Gaussian pancakes problem is to distinguish (Pa. 2a) with non-negligible advantage, where Pa is the sample distribution induced by the following two-stage process: 1) draw uniformly from 8d-1, 2) draw n. i.i.d. Gaussian pancakes samples I T1,..., In pmn and Qu = Q2 iee. the distribution of n i...d. standard Gaussian vectors.
As will be explained next, the exact number of samples n is irrelevant for most applications due to the cryptographic hardness of the Gaussian pancakes problem. For certain parameter regimes of (7, the problem maintains its computational intractability regardless of the sample size n.
Hardness of Gaussian pancakes. There is abundance of evidence demonstrating the hardness of the Gaussian pancakes problem. This makes it compelling to directly assume that Gaussian pancakes and the standard Gaussian are computationally indistinguishable (see Definition 2.9) for certain parameter regimes of (7, o). Initial results by Bruna et al. [13, Corallary 4.2] showed that the Gaussian pancakes problem as hard as worst-case lattice problems for any parameter sequence (7, or) satisfying y 2 2vd and 2 1/poly(d), SQ hardness the problem has been demonstrated as well [31, 13, 27]. Perhaps surprisingly, the reduction of Bruna et al. shows that even with unlimited access to an exact sampling oracle, no polynomial time algorithm
can achieve non-negligible advantage on the (7.a) (7.0)- >Gaassin pancakes problem. This stems from the fact that the running time of A naturally restricts the number of samples can "see", resolving the apparent mystery.
An important follow-up work by Gupte et al. [39] reduced the well-known LWE problem to the Gaussian pancakes problem. Assuming sub-exponential hardness of LWE [52), standard assumption underlying post-quantum cryptosystems expected to be standardized by NIST, the Gaussian pancakes problem hard for any Y 2 (log d) Ic,, where > is any constant, and o 2 1/poly (d) [39, Section 1.2]. Taken together, these findings strongly support the hardness of Gaussian pancakes for the specified regimes of (7, Note, however, that the condition a 2 1/poly(d (d) is necessary for hardness as there exist polynomial-ting algorithms, based on lattice basis reduction, for exponentially small a [83,25] 25].
3 Hardness of Score Estimation
Our main result is Theorem 3.1, which presents a reduction from the Gaussian pancakes problem to L acccuuuaee score estimation. Since the Gaussian pancakes problem exhibits both cryptographic and SQ hardness in the parameter regime 7 2 2/d and a 2 1/poly(d) [13, 39], these notions of hardness extend to the task of estimating scores of Gaussian pancakes. Further details the hardness of the Gaussian pancakes problem can be found in Section 2.3.
Theorem 3.1 (Main result). Let (dd) > 1, (d) > 0 be any pair of sequences such that a Z 1/ l/poly(d) (d) and the corresponding (sequence of) (7, a) Gaussian pancakes distributions (Pu)uess
7

---

satisfies Pu., Qa) > for any d E N. Then, any d E (0.1), there exists (oggllloo//// time algorithm with access score estimation oracle of L2-error OLL/Vlog d) that solves the (7,0)) -ra-ssasn pancakes problem with probability al least 1 - 6.
The requirement TV(P.. Qu) > 1/2 is mild and entirely captures interesting parameter regimes of (y,o) for which cryptographic and SQ hardness of Gaussian pancakes are known. We provide sufficient condition in Lemma B.9, which shows that ya < C' for some constant C' >> 0 ensures separation in TV distance.
Theorem 3.1 implies that even a score estimation oracle running in time poly(d, 21/²". where > 0 is the L estimation error bound, implies poly(d) time algorithm for the Gaussian pancakes problem. This means that estimating the score functions Gaussian pancakes to L Lacauurayyy & even in (oly 22/²²) time is impossible under standard cryptographic assumptions.
3.1 Proof outline of Theorem 3.1
Here, we sketch the proof of Theorem 3.1 and defer full details to Section B.1. We first recall the sampling-to-scont estimation reduction of Chen et al. [17] and its required assumptions to illustrate the main idea behind our reduction. The precise formulation of our idea is given in Lemma 3.3.
Assumptions on data distribution. The reduction of Chen al. [17] requires the following assumptions on the data distribution D over R.
A1 (Lipschitz score). For all 2 0, the score Vlog Dj is I-Lipschitz.
A2 (Finite second moment). D has finite second moment, i.e., m3 == Em [||2||]]] < oo.
A3 (Score estimation error). For step size := T/N and all I,....N,
ED Skh V log Duall S E
Theorem 3.2 ([17, Theorem 2)). Suppose assumptions A1-A3 hold. Let Qa be the standard Gaussian on Te and let FT be the output of the DDPM algorithm (Section 2.1) 1) at time T with step size h = T/N such that h S I/L, where L 2 1. Then, it holds that
[V DJ S VKL(D || Qa) exp(-T)) (Lvdh + Lmgh) Lmghh) VT
Escore VT
(6)
convergence of forward process
discretization evror
score error
In particular, im E d, then T x max((og(
(a)))) and h xx/((T21))) gives
TV(Fr, D) S + Escore max( (oax((/lo((KL(())) Qa)/e). for N = ( L2d
Theorem 3.2 shows that if the unknown data distribution D has Lipschitz scores and satisfies ma S d. then its s-accurate score estimates along the discretized forward process (SK))aE(N) can be used to compute a certificate of Gaussianity defined as follows.
max EQ, [sn + | KE[N]
(7)
Using A test statistic, we decide D >> 0 and D = Qa otherwise. This test statistic is motivated by the observation that the discretized reverse process depends on the data distribution D solely through its score estimates (see (3). For any sequence of score estimates ($t)cE(o.T) the reverse process outputs Fy that is TV-close to D provided its L error along the forward process (D:)ue(o,z] is small.
if A for some carefully chosen threshold
We claim that if A < 17² and the score estimates (SKA) are e-accurate for (Dx)), then the output of the reverse process Fy. roughly (s + 1/)-cl TV distance to the standard Gaussian. This is because the standard Gaussian is invariant throughout the OU process, so A is, in fact, the L score estimation error bound for the case where the data distribution is equal to Qa. In other words, A < 17² means that for all k E [N], the score estimates (SKA) are r-close to 2 which is the score function of Qa. Thus, A is small only if D is close TV distance to Qd, which shows that distinguishes between D= Qa and D E (Pu)ues--I provided TV Qa) > 1/2. The following lemma formalizes this idea. Theorem 3.1 follows from Lemma 3.3 and Lipschitzness of the score functions (Lemma B.5).
8

---

Lemma 3.3 (Gaussianity testing with scores), For any E (0,1) and K 2 2, let D be any dis- tribution on Rd such that m2 S d and KT(D] || Qa) I K with I.ssiisccitz score V Vlog De for any t 2 O, and let Ě x e// ////))((//E) be the L score estimation error bound with discretization parameters T x log(K/E),, x =² and N := := Tíh so that (FT II D) S & (via The- orem 3.2). If (SK])KE[N] are E-accurate score estimates for the forward process (Dun)ke(N] and maX] Equllskh (x) + 2Txl? then
TV Qa) Set V log(K/E).
In particular, TV, Qd) > 1/2 then there exist constants C1, C2 > O such that for any score estimates (skA JEIN of the forward process satisfying maxKE[N] EDA,. [(sA(()) V log (x)(2))l 5 C1/ / log K. it holds
A M C2/ log K.
Proof. By Theorem 3.2 and our choice of 1,2 score estimation error bound é, we have TV D) S In addition, the score estimates (st) also satisfy v -errro bound with respect to the forward
process of Qa. which is invariant with respect to time t. Thus, Theorem 3.2 applied with 1 = Qa as the data distribution, discretization parameters T, h, and score estimates (skh) gives (V Qa) x
V Volog(K//) (/e). By the triangle inequality, we have
TV(D,Q) < TV(Fr, D) + TV(FF, S Volog(K/e).
The second part of the theorem follows from using the assumptions TV(D,Q) > 1/2, K 2 2, and fixing 0 to a sufficiently small constant, which gives
1 1 / log K
4 Sample Complexity of Gaussian Pancakes
To establish that there is indeed a gap between statistical and computational feasibility, we demonstrate a polynomial upper bound on the sample complexity of L'-accurate score estimation for Gaussian pancakes. In particular, we show that sufficiently good estimate á of the hidden direction u is enough (Lemma 4.1). The polynomial sample complexity of score estimation then follows from Theorem 4.2, which shows that if (dd) and (d) satisfy na = O(1), then (ú, u)² < 1/² is statistically achievable with poly(d, 7, 1/n) samples, albeit through brute-force search over gd-1
Our estimator à is based on projection pursuit [35, 43]. We design a functional E : gd + IR of the form F(v)= == Ee 9 (ar, v))) with g R -> TR. carefully chosen to ensure that E(()) 2 F((22) and only if (v1, u)| 2 (V2, 4. Given such a "monotonic" functional (its empirical counterpart E, to be precise), our estimator for the secret direction is essentially
û arg max E(v).
vEgd-1
We remark that parameter regime ya 0(1) Theorem 4.2 encompasses the cryptographically hard regime of Gaussian pancakes. It is also worth noting that if min(y, yo) = w w(Vlog d), then Gaussian pancakes are statistically indistinguishable from Qa by Lemma B.
We defer the full proofs of Lemma 4.1 and Theorem 4.2 to Section C. Lemma 4.1
estimation reduction). For any > 1, > 0, let Pa be the (7, o-) Gaussian pancakes distribution with secret direction Sd-1 Given any E (0. 1) and â E Sd-1
such that (Ū, u)² S n7², the score estimate s(x) 2 + V log Tę ((z, ú)) satisfies
Re Pa [|x(()) - s(x=))² S max(1,1/o*) ./d where s(x) = x + V log TV ((x, u)) is the true score function of Pu-
Theorem 4.2 (Sample complexity of parameter estimation). For any constant C >>> 0, given ((d >
1, (d) > 0 such that "a < C, estimation error parameter 1] > 0, and 8 E (0, 1), there exists a brute- force search estimator û Bd - Sd-1 that uses n = poly(d, d. 7, 1 1/m, 1/8) samples and achieves |ā( fu(xx....,,8 In) ull2 < .?2 with probability at least 5 over i.i.d. samples Zi...., ~ Pa. where Pa is the (7, σ)) Gaussian pancakes distribution with secret direction u E Sd-1

---

References
[1] D. Aggarwal and Stephens-Davidowitz, An improved constant in banaszczyk's transference theorem. arXiv preprint arXiv:1907.09020, 2019.
[2] D. Bakry, I. Gentil, M. Ledoux, et al. Analysis and geometry of Markov diffusion operators. volume 103. Springer, 2014.
[3] W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296:625-635, 1993.
[4] A. Bandeira, A. Perry, and A. Wein. Notes on computational-tossaiiiiiaal gaps: predictions using statistical physics. Portugaliae Mathematica, 75(2):159-186, 2018.
[5] B. Barak and D. Steurer. Sum-of-squares proof' and the quest toward optimal algorithms. arXiv preprint arXiv: 1404.1444552 5236, 2014.
[6] Benton, V. De Bortoli, A. Doucet, and G. Deligiannidis. Nearly d-linear convergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations, 2024.
[7] Q. Berthet and P. Rigollet. Computational lower bounds for sparse pea. arXiv preprint arXiv:1304.088 2013.
[8] G. Blanchard, M. Kawanabe, M. Sugiyama, V. Spokoiny, K.-R. Müller, and S. Roweis. In search of non-gaussian components of high-dimensional distribution. Journal of Machine Learning Research, 7(2), 2006.
[9] A. Block, Y. Mroueh, and A. Rakhlin. Generative modeling with denoising auto-encoders and langevin sampling. arXiv preprint arXiv:2002.00107, 2020.
[10] A. Bogdanov, M. C. Noval, C. Hoffmann, and A. Rosen. Public-key encryption from continuous Iwe. Cryptology ePrint Archive, 2022.
[11] M. Brennan and G. Bresler. Reducibility and statistiaalcoomputttioaall gaps from secret leakage.
In Conference on Learning Theory, pages 648-847 PMLR, 2020.
[12] B. Brubaker. doors. Quanta magazine, 2023. https: /tops://www... www.:uguaaataaaiinnea... org/ pyyptograpeer--hhoe sww-sshhooow---o hide- [Accessed: 2024-03-12).
In neural networks, unbreakable locks can hide invisible
in-iiin-------iii-ii- a-- 21-20230302/
[13] Bruna, O. Regev, M. J. Song, and Y. Tang. Continuous Iwe. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, 2021.
[14] C. L. Canonne. A short note arXiv:2202.07198, 2022.
inequality between kl and tv. arXiv preprint
[15] H. Chen, H. Lee, and J. Lu. Improved analysis score-based generative modeling: User- friendly bounds under minimal smoothness assumptions. In International Conference Machine Learning, pages 4735-4763. PMLR, 2023.
[16] M. Chen, K. Huang, T. Zhao, and M. Wang. Score approximation, estimation and distribution recovery diffusion models on low-dimensional data. In International Conference on Machine Learning, pages 4672-4712. PMLR, 2023.
[17] S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. R. Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations (ICLR), 2023.
[18] Y.-H. Chen, K.-M. Chung, and J.-J. Liao. On the complexity of simulating auxiliary input. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 371 1790. Springer, 2018
[19] S. Chewi.
Log-concave sampling, 2024.
10

---

[20] M. Christ, S. Gunn, and O. Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306.09194 194, 2023.
[21] A. Daniely, N. Linial, and S. Shalev-Shwartz. From average case complexity to improper learning complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 441-448, 2014.
[22] V. De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. arXiv preprint WxXi:2208.003//4 2022.
[23] V. De Bortoli, J. Thornton, J. Heng, and A. Doucet. Diffusion schrödinger bridge with applica- tions to score-based generative modeling. Advances in Neural Information Processing Systems, 34:17695-17709, 2021.
[24] S. Decatur, O. Goldreich, and D. Ron. Computational sample complexity. In Proceedings of the tenth anmual conference on Computational learning theory, pages 130-142, 1997.
[25] I. Diakonikolas and D. Kane. Non-gaun non-gaussian component analysis via lattice basis reduction. In Conference on Learning Theory, pages 4535-454) PMLR, 2022.
[26] I. Diakonikolas, D. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. In International Conference on Machine Learning, pages 7922-7938. PMLR, 2023.
[27] I. Diakonikolas, D. Kane, L. Ren, and Y. Sun. Sq lower bounds for non non-gaussian component analysis with weaker assumptions. Advances in Neural Information Processing Systems, 36, 2024.
[28] I. Diakonikolas, D. Kane, and N. Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems, 33:13586-13598 2020.
[29] I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge university press Cambridge, 2023.
[30] I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. Conference on Learning Theory, pages 1514-1539. PMLR, 2020.
[31] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73 73-84. IEEE, 2017.
[32] C. Dwork, M. P. Kim, O. Reingold, G. N. Rothblum, and G. Yona. Outcome indistinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1095-1108, 2021.
[33] Dwork, M. P. Kim, O. Reingold, G. Rothblum, and G. Yona. Beyond bernoulli: Generating random outcomes that cannot be distinguished from nature. In International Conference on Algorithmic Learning Theory, pages 342-380. PMLR, 2022.
[34] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2), 2017.
[35] H. Friedman and J. W. Tukey. projection pursuit algorithm for exploratory data analysis. IEEE Transactions on computers, 100(9):881-89) 1974.
[36] D. Gamarnik. The overlap gap property: A topological barrier to optimizing random structures. Proceedings of the National Academy of Sciences, 118(41) 118(41)=21188492118 2021.
[37] S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. Klivans. Superpolynonial lower bounds for learning lne-layer neural networks using gradient descent. In International Conference on Machine Learning, pages 3587-3596. PMLR, 2020.

---

[38] S. Goldwasser, M. P. Kim, V. Vaikuntanathan, and O. Zamir. Planting undetectable backdoors machine learning models. arXiv preprint SxXi:2204.06977, 2022.
[39] A. Gupte, N. Vafa, and V. Vaikuntanathan. Continuous lwe as hard as Iwe applications to learning gaussian mixtures. arXiv preprini arXiv:2204.0233 2022.
[40] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[41] U. the (computationally-ddni) iddeiifiiii)))i masses. In International Conference on Machine Learning, pages 1939.1948. PMLR, 2018.
M. Kim, O. Reingold, and G. Rothblum. Multicalibration: Calibration for
[42] J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-666 68510 2020.
[43] J. Huber. Projection pursuit. The annals of Statistics, pages 435-475, 1985.
[44] A. Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4). 2005.
[45] D. Jetchev and K. Pietrzak. How fake auxiliary input. In Theory of Cryptography Conference, pages 566-590. Springer, 2014.
[46] M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6))983-1006, 1998.
[47] D. Kunisky. Spectral Barriers in Certification Problems. PhD thesis, New York University, 2022.
[48] D. Kunisky, A. S. Wein, and A. S. Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In Mathematical Analysis, its Applications and Computation: ISAAC 2019, Aveiro, Portugal, July 29-August 2, pages 1-50. Springer, 2022.
[49] B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal optimization, 11(3):79--87,,
2001. 2001.
[50] H. Lee, J. Lu, and Y. Tan. Convergence for score-based generative modeling with polynomial complexity. Advances in Neural Information Processing Systems, 15:22870-228822 2022.
[51] H. Lee, J. Lu, and Y. Tan. Convergence of score-basee generative modeling for general data distributions. In International Conference Algorithmic Learning Theory, pages 946-985. PMLR, 2023.
[52] R. Lindner and C. Peikert. Better key sizes (and attacks) for lwe-based encryption. In Topics in Cryptology- CCT-RSA 20/1: The Cryptographers' Track at the RSA Conference 201 I, San Francisco, CA, USA, February 14-18, 2011. Proceedings, pages 319-339. Springer, 2011.
[53] X. Liu, I.. Wu, M. Ye, and Q. Liu. Let us build bridges: Understanding and extending diffusion generative models. arXiv preprint arXiv:2208.1 14699, 2022.
[54] Z. Ma and Y. Wu. Computational barriers in minimax submatrix detection. The Annals of Statistics, 43(3), 2015.
[55] S. Mei and Y. Wu. Deep networks as denoising algorithms: Sample-efficient learning of diffusion models in high-dimensional graphical models. arXiv preprint arXiv:2309.11420 2023.
[56] D. Micciancio and O. Regev. Lattice-based cryptography. In Post-quantum cryptography, pages 147-191. Springer, 2009.
[57] Niles-Weed and P. Rigollet. Estimation of Wasserstein distances the Spiked Transport Model. Bernoulli, 28(4):2663 2688, 2022.
12

---

[58] NIST.
cryptography. Post- Quantum Crr.ruugrrrytt..pppp.....
Post-quantum
https://csrc https::/ccrr..iit..000 got.st.go//rooects/
[59] P. A. Parrilo. Structured semidefimite programs and semialgebraic geometry methods in robust- ness and optimization. California Institute of Technology, 2000.
[60] C. Peikert. A decade of lattice cryptography. Foundations and trends@ in theoretical computer science, 10(4):283-424, 2016.
[61] J. Pidstrigach. Score-based generative models detect manifolds. Advances in Neural Information Processing Systems, 35:35852-35533 2022.
[62] A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXivv2204.06125, 2022.
[63] O. Regev, On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1-40, 2009,
[64] Roman. The umbral calculus. Pure and Applied Mathematics, 1984.
[65] R. Rombach, A. Blattmann, D. Lorenz. P. Esser, and B. Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10684-10695, 2022.
[66] C. Saharia, W. Chan, S. Saxena, L. Li, Whang, E. L. Denton, K. Ghasemipour, Gon- tijo Lopes, B. Karagol Ayan, T. Salimans, et al. Photorealistic text-to-image diffusion mod- els with deep language understanding. Advances in neural information processing systems, 35:36479-36494 2022.
[67] S. Särkkä and A. Solin. Applied stochastic differential equations, volume 10. Cambridge University Press, 2019.
[68] K. Shah, S. Chen, and A. Klivans. Learning mixtures of gaussians using the ddpm objective. Advances in Neural Information Processing Systems, 36, 2024.
[69] S. Shalev-Shwartz, O. Shamir, and E. Tromer. Using more data to speed-up training time. In Artificial Intelligence and Statistics, pages 1019-1027. PMLR, 2012.
[70] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. International conference on machine learning, pages 2256-2263 PMLR, 2015.
[71] M. J. Song, I. Zadik, and Bruna. On the cryptographic hardness of learning single periodic neurons. Advances in Neural Processing Systems (NeurIPS), 2021.
[72] Y. Song and S. Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[73] Y. Song and D. P. Kingma. How train your energy-based models. arXiv preprint arXiv:2101.03288, 2021.
[74] N. Stephens-Daviddwiiz On the Gaussian Measure Over Lattices. PhD thesis, New York University, USA, 2017.
[75] S. Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems. In The Thirty Sixth Annual Conference on Learning Theory, pages 3029-3064. PMLR, 2023.
[76] L. Trevisan, M. Tulsiani, and S. Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 126-136. IEEE, 2009.
[77] R. Vershynin. Hime-dimes probability: An introduction with applications data science, volume 47. Cambridge university press, 2018
13

---

[78] P. Vincent. A connection between score matching and denoising autoencoders, Neural compu- tation, 2377):661--167, 2011.
[79] M. Wainwright. Constrained forms of statistical minimax: Computation, communication and privacy. In Proceedings of the International Congress of Mathematicians, pages 13-21, 2014.
[80] A. Wibisono, Y. Wu, and K. Y. Yang. Optimal score estimation via empirical bayes smoothing. Xrviv preprint arXiv:2402.07744 2024.
[81] Y. Wu and Xu. Statistical problems with planted structures: Information theoretical and
computational limits. Informaation-Theoreiii Methods Data Science, 383:13, 2021.
[82] K. Y. Yang and Wibisono. Convergence of the inexact langevin algorithm and score-based generative models in kl divergence. arXiv preprint arXiv:221 2022.
[83] I. Zadik, M. J. Song, A. S. Wein, and J. Bruna. Lattice-based methods surpass sum-of-squares clustering. In Conference on Learning Theory, pages 1247-1248. PMLR, 2022.
[84] L. Zdeborová and F. Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5):453 00004455-55,,2222 2016.
[85] Y. Zhang, M. Wainwright, and M. I. Jordan. Lower bounds the performance of polynomial- time algorithms for sparse linear regression. In Conference on Learning Theory, pages 921-948. PMLR, 2014.
14

---

Appendices
Additional Related Work
16
B Proofs for Section 3
16
B.1 Proof of Theorem 3.1
16
B.2 Score functions of Gaussian pancakes
19
B.3 Distance from the standard Gaussian
21
Proofs for Section
24
C.I Sample complexity of score estimation
24
C.2 Sample complexity of parameter estimation
25
15

---

A Additional Related Work
Score estimation. Several works have addressed the statistical question of sample complexity for various data distributions and function classes used to estimate the score [16, 55, 80]. Wibisono et al. [80] study score estimation for the class of subgaussian distributions with Lipschitz scores. By establishing a minimax lower bound exhibiting a curse of dimensionality. they show that the exponen- tial dependence on dimension is fundamental to this nonparametric distribution class, underscoring the need for stronger assumptions the data distribution for polynomial sample complexity. Chen et al. [16] study neural network-based score estimation and derive finite-sample bounds for data distributions that lic on dow-dimensional linear subspace, which circumvents the curse of dimension- ality. Mei and Wu [55] study neural network-band whaskk-bseddd--e score estimation for graphical models which are intrinsically high dimensional. Assuming the efficiency of variational inference approximation to the data-generating graphical model, they show that the score function can be efficiently approximated by residual networks [40] and learned with polynomially many samples. Efficient score estimation both in sample and computational complexity has been achieved by Shah et al. [68] for mixtures of two spherical Gaussians using shallow neural network architecture that matches the (losed-form expression of the score function.
Maaissical-oo-computaaiiooo gaps. cnnisticallt-ccomuuattaiiio gaps have rich history in statis- tics, machine learning, and computer science [7, 85, 54, 69, 24]. Indeed, many high-dimensional inference problems exhibit gaps between what is achievable statistically (with infinite computational resources) and what is achievable under limited computation. Notable examples include sparse PCA [7], sparse linear regression [85, 79], and learning one-hidden-layer neural networks over Gaussian inputs [37, 30].
Since there are known reductions from NP-hard problems, the gold standard for computational hardness, to any average-case problem arising in statistical inference, alternative techniques have been developed provide rigorous evidence of hardness. These include proving lower bounds for restricted classes of algorithms like sum of squares (SoS) [49, 59, 5] and statistical query (SQ) algorithms [46, 34], which capture spectral, moment, and tensor methods, and reducing from "canonical" problems believed to be hard on average, such as the planted clique [11] or random k-SAT [21] problem. We refer the reader surveys and monographs [84, 4, 81, 36, 48, 47, 29] for thorough overview of recent literature and diverse perspectives ranging from computer science and information theory to statistical physics.
B Proofs for Section 3
B.1 Proof of Theorem 3.1
Theorem B.1 (Theorem 3.1 restated). Let 7(d) > 1, > be any pair of sequences such that 2 1/poly (d) and the corresponding (sequence of) (Gaussinnnn pancakes distributions (Pu)uega- satisfies TV(Pu, Qa) > 1/2 for any d E N. Then, for any E (0, 1), there exists poly(d)- . -log(1/ (0((/8)) -8)mmmee algorithm with access to score estimation oracle of 122-rror O(1/VTop d) that solves the σ))
( Gaaussian pancakes problem with probability at least 8.
Proof. Let D E (Pu) U Q be the given data distribution. We first verify that assumptions A1-A3
hold, allowing us to apply the score- score-based Gaussianity test from Lemma 3.3. For any ((d),<(() > 0 such that o 2 1/poly(d), (d), the (y, -Gaussian pancakes satisfy the Lipschitz score condition L < poly(d) (Assumption A1) by Lemma B.5 and the second moment bound m2 < d (Assumption A2) by Lemma B.2. In addition, (T.(Pu Q) < poly(d) (Lemma B. 1), Lemma 3.3 applies to
D with K = (oly(d). Moreover, since TV Q) > 1/2, Lemma 3.3 implies that D E (Pu)uess 1, there exist universal constants C1,Cr satisfy EDA. [z)) v log (z) < C1/ d, then A 2 C2/ logd.
such that if the score estimates (SAA (SN))e[[M]
Let T = C2/ log d and n² = min (amnTT/4, loggd Then, we have that with r7accurate score estimates (S we have A < 172 < if Q and A > otherwise. Note that 17 x 1/ //oog d and N = 7/h = dod K < (d)y Our proposed distinguisher A uses a finite-sample estimate of A as a test statistic (7). using acccrrate score estimates (SK)) and Nē i.i.d. standard
Gaussian samples (z ([.,))[N])( as follows. Later, it will be shown that setting the batch size E
16

---

to = poly(d) is sufficient for our distinguisher A.
Á (k)
where Å (b)
Σ [|s
(10) 2TT2
1012
NEIN]
The distinguisher A decides D = Q if Å S 1/2 and D E (Puluesu 1 otherwise. This procedure runs in time ( and makes N poly(d) queries to the score estimation oracle of L -accurryy O(1/Vlog d).
One issue in estimating A is that the score estimates (skA. only satisfy the mean guarantee with respect the forward process (Dea): ). i.e. E San (a) log (ra(2)) S 17². These guarantees
do not necessarily provide control over the concentration of random variables [[) + 2 = induced
by ~ Qa- Moreover, if = Pu, then st (z) may behave erratically for ~ Qu. taking on large norms in low density areas between the pancakes, which may deter the estimation of A. We handle this by truncating the score estimates.
Let M > 0 be some large number to be determined later. Define the truncated score 8 by
(x)
if [xx) < M otherwise
3,
0
We claim that using the truncated score estimates (5x) in place of (s:) introduces negligible (in data dimension d) additional I score estimation error with respect to the forward process (Dr) compared to the original score estimates (st). Hence, Lemma 3.3 applies with the uniformly bounded vector fields (Ska)ke') as the -L-accurate score estimates for (DRA)kE(N)- For any (discretized) time 0 l < T and distribution D, from the forward process,
ED, (z)
V log Dj (a=)l = E.D, [())c(a)) Vlog (x) [[])](=)]] s M]
+ ED, [I] log (=) [x)]l M]]
The second term on the RHS can be upper bounded by
ED, [I[ log (x))) (=))| > M]]
Ep. ||| log (x))) [[ [[)]] M) A (I) (x)=) > M/2]]
+ ED, V log [(( > M) A (I) log Dx(x)) |I s M/2]]
Ep, [|| log (=)) Vo (x(x) > M/2]
ED, (x)) v log (=) 1[]ls( M]
(8)
where in (8) used the fact that if [I,(
M and || D,(x)] < M/2, then
||V log (x)) || < M/2 < (x) v log (x))l
Putting things together, we have (2)r) - log D2(x))11 S (D,lIs((ar) - V log (2) D,
+ En. | log (z)=) 1|l log (= > M/2]]
It remains to bound E||| log (x) 1 (=(=)) > M/2] which depends only on the distribution D,. We choose M x (Vd + 1/0²). If Qs. then D. Qa for any t > 0, and by Cauchy-Schware and norm concentration (see e.g. [77, Theorem 3.1.1J), there exists a constant
C > 0 such that
Eq, [| 1 ||||=|| > M/2[] s EQ,
Pr[]|=|| > M/2] < exp(-CM²)
Qa
On the other hand, if D Pu, then by Lemma B.4, (13) and the triangle inequality
x + (TT) u))
V log Pu(x)]
< | 8T(1 + 1/0²).
Ty (zx, u))
17

---

Using similar concentration argument, we have
Ep. Vog Pu (x)]1²
v log Pu(x))) > M/2]]
x Ep. [[|2=]] + 1//0 + +) 1[[[]| M/2 ST 1
exp( cxp(-0(((2))
(9)
The OU process applied to Pu only increases the parameter, so the upper bound in Eq. holds uniformly over the forward process (DR)) if D = Pu. Thus, choosing M x (vd + 1/02) poly(d) as the truncation threshold suffices to ensure that for all discretized time steps = k/, the 1,2 score estimation error with respect the forward process (D₂) introduced by truncating the score estimate to 3, is negligible in d. Therefore, we apply Lemma 3.3 with (ER])RE[N] as the score estimates for the forward process (Dkh)ke(N)-
Since []5c(z) + 2T= 112, where z ~ Qa. is random variable with subexponential norm ((M)), we can apply Bernstein's inequality [77, Corollary 2.8.3] to the i.i.d. sum ( Thus, for any E [N], Gaussian samples suffice to guarantee accurate estimation of the population mean (k) with additive error less than e with probability with probability at least 1 - 5, this holds for all & E [N]. Setting e //8 = (1/ log d) and recalling that N = poly(dd))) we have distinguisher A for the Gaussian pancakes problem that makes N poly(d) (d) queries to the score estimation oracle, runs in time N = poly(d) 1og(1/8), and is correct with probability at least 1- 6.
(x -
least 5/N. By union bound,
Lemma B.2 (Second moment of Gaussian pancakes). For any 7: a > 0, and u E 8d-1, the (% ( Gaussian pancakes Pu satisfies
d
E E Pe |||=||]] S
2T
Proof. Without loss of generality, assume Ej. Then,
d-1
Ba-P, ||01 = EE-Ag [x0] + (d- - Q) = -Benagll" 1= +
2T
In addition,
E ExwAg [x Bx-A, (tw. o2
o² 1
1+ EeNA,
+ 1 02
2m
Thus, suffices to establish an upper bound on EzNA, x², i.e., the second moment of the discrete Gaussian on (1/>)Z. Using the Poisson summation formula (Lemma 2. and the fact that the Fourier transform of x² p(x) is (1/(2 - p(y))
E Ex A, [x²]] = p((1/7)Z)
Σ 2E(1/7)2
x p²)((x)
7
822 ply)
p((1/n)Z)
2T
(((2))
7
Σ DEクΣ
(10)
2T
p((L/7)Z)
p((1/T)Z)
2m
where in (10), we used the fact that pl72) (((1/))2)/ and that the second term is positive.
Since Ex=az [x= convex combination of Eg [x-²] and 1/(27), the conclusion follows.
18

---

B.2 Score functions of Gaussian pancakes
In this section, we show that score functions of Gaussian pancakes distributions are Lipschitz with respect to a E RR. The score function of Pu. the (7, σr) ( -aaussian pancakes distribution with secret direction us E gd-1, admits the following analytical expression.
v log Pu(a:) - 2xr + V log (((a, u)) = -2m + (T u))
(11)
(g u))
We use Banaszczyk's 's theorems on the Gaussian mass of lattices [3] to upper bound the Lipschitz constant of (IT) /Tę terms of a.
Theorem B.3 (174, Corollary 1.3.5)). For any lattice L C R., parameter 0, shift E IR, and radius > (2
Pol(C - rBB) <
where x r//- / (2x) and By denotes the Euclidean ball TRd..
Lemma B.4 ([74, Lemma 1.3.10]). For any lattice C c. RR parameter s >> O, and shift t E R4,
exp(-5 (p π
dist(t, ////5)/ Pa(C) S P. - 5
Lemma B.5 (Lipschitzness of V log Pu). For any n' >,,1, the score function of the (7, o) -Gaussian pancakes distribution Pu satisfies the Lipschitz condition:
o/vo+ and Sd-1,
V log Pa Pu V log Pu(a:)l - (1/s*)ly æll for any x, y R
(12)
and the likelihood ratio Tę of the a-smoothed discrete Gaussian AG relative to N(00 1/(2x)) satisfies the uniform bound:
(z)) (2)
8T 82
S
for any E IR..
(13)
Proof. It suffices to analyze the Lipschitz constant of the univariate function (TTY/TT IR. R
which we denote by / = (TTY since for any æ + y E Rd,
I log (y V log (=())) - 2n
x=| +
[[f((y. u)) f((2,, 22)
[f( u)) - f(12,, ui)l
s 2t yy
xz||
Ky u))
(3. u) {ax, uil
f(b) f(a) b
<
2T + sup
|1y 2011
a.DER
We bound the Lipschitz constant of the function f(2) by demonstrating a uniform upper bound on the absolute value of its derivative f2( = fz) For notational convenience, we omit the parameters 7, when denoting the likelihood ratio T. The derivative f' is given by
(T")T (T')
T"
T
2
f
(14)
T
T2
T
T
Hence, ((* + |T (x)) for any & E R. We prove uniform upper bounds on the RHS terms, starting with IT' /T/ Using the definition of the likelihood ratio T (F)).(5), have
(=)
2T
ΣLEZ -2 (1--//////////------>>>- -V+oo
7(2)
2T
B
[x],
(15)
19

---

where = s
02, C = = (1/7)Z, and DC-2,e is the discrete Gaussian distribution of width on the lattice coset -
s=
We upper bound [|[=]] via a tail bound on D Let r > 0 be any number and denote t =
r/s V1((2T). By Theorem B.3 and Lemma B.4,
Pol(C - rB2)) < exp(-x(() (C))
< exp( exp(1 dist( () 1/s 8) =cxp(-m((11) vI 1/(22>) )) 2)
where used the fact that dist(2, () 1/ for any 2 E IR in the last line.
Thus, for for r/(ss) 2 v1/(2x) (2
||>| 2] Pa((C - 2) 1 rB2))
Pr
I <exp(-xr"/22))
(16)
n- a~De 2,
PelC -
Denote ro = 8//2/7 1/7. Note that < 12/T 1/7 since E [0, 1). Then,
Ex-De-s..
/Pr[la| r|dr ro
Pr|[æ| 2 rldr
exp(-Tr" (25)))>>(2s)²)) )dr
ro
<o + 28
(2 22/T)) 1/7
(17)
Therefore by (15( and (17), for any
(2)
2T
((2 + 22/T) + 1/7).
(18)
T(z)
os
E13( in the statement of Lemma B.5 follows immediately from the fact that s < min(1, and 1. Next, we demonstrate uniform upper bound on T" /T. The analytical expression of /T given by
T T(=)
2T 7²
2
(Ekeel [Kezla- (14o0W/No0(=-v11t0020
o²
2x
2TT
2
22
I²
as
2T
where 3 2/v1+ 0², a.vaall/aaa 0², and (1/7)Z.
To uniformly bound [T /T) we upper bound the second moment of DC-2,a- Again, let ro =
sv 2/TT 1/7. Using the tail bound from Eq.(16) and the fact that (a + b)2 < 2a² + 26 for any
a, b E R
r rPr[aa| rldr S r//2+
rPr[22] 2 rldr
B> Dr-
0
r220
$ ///22+
rexp( rexp(-ar² ((x(=>²2((2))) )
r20
< </0/2+
2 +/72.
(19)
20

---

Applying (1)) and (19 to the expression for f = T /T (Eq.(14)) and using the fact that
>>> and 8 = a/v /vivv + t min(1, ( o), we have
IT |T| 00 || 11)
2T
((1 1/2m)s
((2 (2 1/7))²)
100m²
84
Therefore, V log (u( is ((1/s)) since 2 + || & 1/844
B.3 Distance from the standard Gaussian
We now prove lower (Lemma B.9) and upper (Lemmaa B.10) bounds the TV distance between Gaussian pancakes distributions (Pu) and the standard Gaussian Q. We also show that the KL divergence is upper bounded by poly(d) for Gaussian pancakes with 2 1/poly (d) (Lemma B.11).
The following fact reduces the d-dimensional problem of bounding TV(Pu Qu) to a one-dimensional problem of bounding TA4, Q), where AG is the o-sothhh discrete Gaussian (1/y) and
Q Q2. Without loss of generality, assume u e1. Then, by the L i'-characterizzation of the TV distance, we have
TV(P.. Qa) - 1 [Pu(x) - Qo(x))ldx - 1 / Qa(x))17 dæ
1
1
2 (19(x1) - Q(x
=V,449.Q) Q)
Hence, suffices demonstrate bounds TV(AS, Q). The same applies the KL divergence since KT((P, Qa) (LAAA, Q)- We first demonstrate lower bound the total variation distance. To this end, we introduce the periodic Gaussian distribution and its useful properties. The key lemma Lemma B.9.
Definition B.6 (Periodic Gaussian distribution). For any one -ie-dimensiona lattice C C R, we define the periodic Gaussian distribution L c, R - R2o as follows.
V (2) Ep(e 2) -)){_
ZEC
We can regard the function V/ c. distribution for the following reason: Let A1 denote the spacing L. Then, Ve restricted to [0, (C)) is probability density since
(1( (z)d =
(1(E)
A1(C)
1 rcc Po(x 2)
(=(2)dz
3
ZEC
REC
Lemma B.7 (Mill's inequality [77, Proposition 2.1.2]). Let 2 ~ N(0, 1). Thenfoor all >> 0, we have
P[I| 2 t) = V L 2d
2
1 [
2
V
Lemma B.8 (Periodic Gaussian density bound [71, Claim 1.6]). For any > and any z E (0,1) 1)
the periodic Gaussian density U [0, 1) + Rz0 satisfies
W (2) - < 2(1 11/(s))e
21

---

Proof. By the Poisson summation formula (Lemmaa 2.1).
(2)
Σ Ps (x
2)
8
Σ
2wrzy
P1/s(3)
yea
+1+
-mizz
P1/a(1)
yE2
Since |eta| s for any a R. we have
1/
Σ
ve-2rizy
p1;s(1) 5
Σ Pi/a(u)
y (2
yE21(U)
2 e Tx?
+ { E
E di
$ 2(1 + 1/ 1/(TT))
Lemma B.9 (TV lower bound). There exists constant C such that for any Y > 1 and o ya < C, then (AG, 1/(2>))) > 1/2. where A?, is the o-smoothed discrete Gaussian on (1/r)Z
Proof. For ease of notation, denote (0(01/((2T by Q. Since TV Q) sup (A9(S)- Q(S),. where F is the Borel o-algebra on R, it suffices to find measurable set $ C R such that
(S) Q(S)= 1/2.
the constant in the statement of Lemma B.9. Let ö E (0, 1/4) be the smallest number satisfying the condition no S 6/(3/log(1 (og((15)) Such 5 > always exists under the
Let C 1/(12/2
given assumptions since 8/ /lo(())) is increasing in 5 and 8 1/4 satisfies the condition (thanks to our choice of C). We claim that the set S defined below witnesses the TV lower bound.
{ E R dist(z, () S VI+ v /og((1/))
where L = (1/1v1+02)2.
We show a lower bound for (S) and an upper bound for Q(S). Using the mixture form of the density of A (4). and Mill's tail bounds for the univariate Gaussian (Lemma B.7), we have that for each Gaussian component in the mixture Aç, at least 1 - ô fraction of its probability mass is contained in S. This is because the component means precisely form the one-dimensional lattice and S contains all significant neighborhoods of L. Thus, AC(S) 2 5.
Now we show an upper bound for Q(S). Recall from Definition B.6 the density of the periodic Gaussian distribution Z2 Since S is periodic set, its mass Q(S) is equal to (Z n Z), where = o² and
$ == f Z dist(z, Z) s yo Log(log(1///
Since = > 1, by Lemma B.8 for any 2 E [0,1)
V (z) 1 < 4e ns² < 1/2.
Since ya 55//3//log(L//) it follows that Q(S) (5. [0, 11) + 4e . 27ov/log(11/) < 3 /1og111 < 5.
Therefore,
TV(A2, Q) 2 AQ(S) Q(S) > 1 1/2.
22

---

We now establish upper bounds on TFu. Qa) via upper bounds on TV Q). Lemma B.10 provides tighter upper bound when min(y, ya) w(vlog d). In this regime, the sequence (TV Qa))dEN is negligible in d. It is worth noting that Lemma B.10 is not tight since TV - O Ds + co, whereas the upper bound only converges to e x-x"".
On the other hand, Lemma B.11 provides an upper bound on (I ll Qa) which is useful when large. Note that the KL divergence upper bounds the TV distance through Pinsker's or the Bretagnolle-Huber inequality (see e.g., [14]).
Lemma B.10 (TV upper bound). For any " > and a > such that a 2 2/7, the following holds for the o-smoothed discrete Gaussian AG, and = (0(011/(21)
TA Q) S Se=
where 8 = 20/v
Proof. By the L' ccaaractterizttion of the TV distance,
TV Q) = [4g(x) - Q(+))d== = ; Q())(T((0) 1|dr,
where the likelihood ratio T is given by (see E5)
02
(x) (p((1/7)z)
Σ Pola 11 022k//1)
/To (1
Pra/
(p((1/7)Z)
kEz
The likelihood ratio is also re-scaled version of the periodic Gaussian density since
(t) Pa f)
Pa(k
(20)
KEZ
Plugging in s = h/o/////////// 0² (1/(1/02) + 1 to (20), we have
(x) p((1/7)Z) Uz (yx/ (T
The assumption 2 2/7 implies that 2 Thus, by Lemma B.8
7
(77 (x)) 1
Vz, (T, 02)
p((1/T)2)
((((/>)2)
< 7
2(1 + +1/(Ts)) T022
?
p((1/7)Z) -1
p((1/7)Z)
7
3e = m
(21)
p((1/>)2)
p((1/T)Z)
Since p((1/))))= = Pz(Z) = V 2,7 (0) and 7 > 1. by Lemma B.8 applied to 12
p((1/7)Z)
< 2(1 + 1/(77)) mr? < 3e -0 < <1/4.
7
We may thus write p((1/))Z)/ / = 1 + E for some c E IR such that |e| S 3e xx²²
< 1/4. Then,
7 1 1
8
(4/3)e.
p((1/))Z)
1
23

---

Applying the above inequalities to (q.(, we have that for any E R.
(T) 1
3r =T==
p((1/7)Z)
(1(1/7)2)
< (1 + 3e -==)) -3e =ss
+ =0?
s 4(E xx²
+ -=))))
Since 0 < < 7. follows that
TV(A Q) 4 +e - 8e-
Lemma B.11 (KI. upper bound). For any 7 > 0 and a > O, the following holds for the o-smoothed
discrete Gaussian AC, and Q = -O (2T).
(L(AZ)1Q) = log( V1+ 03/00 v
20²
Expressed in terms of the time with respect to the OU process e
for any 1 1>> 0
e 2-21 21
(L 11 S 2(1 21)
Proof. By Jensen's inequality and the fact that for any x E R, T: (x) < (T))))
(L(A71Q) Ez [log T (x)] S log E Eg T (x)
I log T (0)
v1 1 log (2) (Z)
where 70/ ////v112 02 <7
IFO S 81 S 82, then Pst (Z) S Pez (2). Hence, (2(2)/p (Z) S 1. Using the fact that (1) s
for any > 11 we have
KL Q) < log( /1 - (1/2) log(1 + 1/0 51/(20
The second part of the lemma follows straightforwarddy from the relation 0/ 9/v1 02 v1 - 2-21 Using the fact that log(1 a) 2 aa(11 a) for any a 1, for any > 0 have
2
KL(A, Q) & log(1/ /I - 22)) = ((122) log(1 - e e-21) v 2(1 212
C Proofs for Section
C.1 Sample complexity of score estimation
We show that score estimation reduces to parameter estimation for Gaussian pancakes. Given that the sample complexity of parameter estimation for Gaussian pancakes is polynomial in the relevant problem parameters (Theorem 4.2), our reduction implies that the sample complexity of score estimation is polynomial well.
Lemma C.1 (Lemma 4.1 restated). For any 7 > 1, > O, ler Pa be the (7, g) -G--usssiann pancakes distribution with secret direction u E gd-1 Given any n E (0,1) and Sd-1 such that 1 (ú, u) < 1/ the score estimate 8(x)) = - + V log T (ax, ú)) satisfies
By-P
P. [((())))) s(x)) & max 1 1/00) 1 d,
where s(x) -2Tx + V log T: ((x, u))) is the score function of P..
24

---

Proof. For simplicity, we omit super and subscripts of the likelihood ratio Tç and simply denote it by T. Let á be an estimate satisfying 1 (ú, u)² < n2 and denote á (û, u.u + w. Note that w E Rd is orthogonal to u and ||20|2 = (ū, u) S sn" Then, we have
((x, u))
T( ú])
s(x) 8(x))
(1 ui)
T( ú))
T' (1x,, u!)
((x ū1) (u, i1)
((e ū)) T( úi)
(ax, u))
(( ú])
By the triangle incquality and the fact that (a + 6)2 S 2a²
+ 2b2 for any a, b E R, we have
2
T (1r u))
T(( úi)
((a ūi)
[|s(x) - 8(x)]1 2 2
(2i i
+ 2
T((x, ui) s7²
T((x, u)
T(xx, ú))
2
2
T((x, u))
T( ú}))
T(x ú}}
T( ui) T((2r, úi)
+
(1- ((,,ū))² +
17²
T( u)
T( ū))
T(( ii)
T T' u))
(( (.)
T (ar, ú)) T((x, u))
17²
(22)
T( u))
T((æ, ū))
By Lemma B.5 and the fact that (1 + o²//0² < 2 m (1, 1/o²). we know that the Lipschitz constant L of T /T satisfies L S max(1, 1/0²). Furthermore, by Eq. (13) in Lemma B.5, we have |TT S max(1, 1/00). Applying these upper bounds to (22),
2
2
T' u))
(((x,ú))
T(x ú)) T((x, úi) n?²
[|(()) s(x)11²> 5
T((,, u))
T(ex ii)
1//o) u ú) + n7²)
$ 1(01)) - -il? + 122)
$ max(1111o")) .7 (|==|| +1
Since Em-p, ||:0|/2 < d by Lemma B.2, it follows that Ee Pa [1x {(x)]12 S max rfd.
C.2 Sample complexity of parameter estimation
For parameter estimation, we design a contrast function IR -+ R such that the (population)
functionals G and E, defined below, are monotonic. For any 7 > 0, gd-1, and (7, Gaasssaia pancakes Pu, we define
G(o) :- Ex Az [9(1) E(v) Ex Pe g (Ix w))]
(23)
(24)
Note that E(v) = G(o). where o² = =1 (u, creasing in a and E(e) is increasing (u, 0)2. We use g T for some appropriately chosen B > 0. The monotonicity property of 7 is shown in Lemma C.3. Thus, given two candidate directions U2 if E(v1) 2 E(v2), then (u, v2)² 2 (u, 2. This suggests the projection pursuit- based estimator á arg max É(v). where C is an 77-net of the parameter space gdf and ((v) = E
We choose so that G(a) is de-
u)) is the empirical version of E. The main theorem of this section (Theorem 4.2) shows that n = poly(d, 7, 1/n) samples is sufficient for achieving L 1) using the estimator ú. We start with useful fact about mmoothedd likelihood ratios 17.
Claim C.2. For any B > 0, a 2 O, and x E IR,
Enn T
VI+ x v ) - (x), -T,(0)))))))))))))))))))))>)))
1
25

---

where s == - (1 - and T denotes the likelihood ratio of the a-smoothed discrete Gaussian Ar on (1/r)ž with respect to Q = (2Tm) (see Eq. (5)).
Proof. Let = - and ck (7) = x / 32k/7. Then,
22 T +
3p((1/7)z) / p(z) E
VI+ $2
PB i a - 18kk )dz
KEZ
VI+ 82
E/
PBI 181/8 cx (z))) (ortza(ca())
Bp((1/7)Z) KEZ
VI+ + B2
E REZ
VB2 + 0² p((L/n)Z)
Plugging in E 02 and Ō 0/ VI+ gives us
VI+ VI+ 1 + Vi+ sp((1/7)Z) kEz
Eq
T
Ea(o- (1+t-/1++3k//) = Tx(())
where s = (1+ (++
Lemma C.3 (Monotonicity). Given any y > and 3 > O, define G(a) = EznAg (x:)), where T. denotes the likelihood ratio of the a-smoothed discrete Gaussian A?, on (1/7) with respect to (0 1/mm)) Then, for any a > O, we have G' (a) < O.
Proof. Let (z) Ek=o h2x (x) be the (formal) Hermite expansion of TT)x,, where (he)keN
form an orthonormal sequence with respect (. By Claim C.2, for any
(x) = 02
hzz (x))
(25)
1 0²
Using the orthonormality of (hx), for any > 0
G(o)) Ex ( (T 12
Σ
2
1
aizk
(1+ 32)
k=U
2ko
G'(a) 02kk
(1+02)tt)) 0.
(1 32)
Lemma C.4 (Non-trivial Hermite coefficient). Let (hx) be the normalized Hermite polynomials with respect to ). For any y > such that n and & N, holds that
E A, (x)) >
V
where Ay is the discrete Gaussian on (1/7)Z.
Proof. Let (Hx) be the unnormalized Hermite polynomials defined by Hz(x)p(x)) = (-1)* d dx p(x)
Using the relation between the Fourier transform and differentiation, we have
F(H)(z))(z))= = (-) d²
(-
dzk dot) } (-2rri)) p(y)
26

---

Let h4g = Hy be the normalized Hermite polynomials, where cæ (20)) (see e.g., [64,
Chapter 4.2.1D. By the Poisson summation formula (Lemma 2.1), we have
B B
Σ
cLll(())0z))
(((1/))Z)
xE(1/T)2
Σ
(- 2wiy) p(y)
(((1)))Z)
yÊ
We now analyze the maximum among the terms inside the sum. Let f(v) = p(y). Note that (2m)* exp(- + l klogg)
=
= ply) p(y)
The exponent in the above expression is maximized (y)) k. This maximum is indeed achieved in the sum since we can choose y" Ly, which is permissible given the assumption x7² N. Hence, the maximum value of f(y)
f(y") exp(-k/p2 + (k/2) log = ( (k/2eT)K/22
Plugging in the value Cj. (2 and using the Stirling lower bound k! /2rk(k//e)) for all k E N.
27
F R hx((r)) 2 p((1/T)Z)
Ct (2T)
(k=/2em))*
27
C4 (2Tk///)) k/2
(((1/))Z)
27
(k/e))
p((1/1)Z)
Vk!
27
p((1/7)Z)
(2mk)
In addition, we have that
((1)))2)=pplle = S <p(()= s 2y.
Plugging in k: = 22, we therefore have
1
E E hx(2) 2
22xl7
Corollary C.5 (Non-trivial Hermite coefficient, rounded degree). Let (h₂) ) be the normalized Hermite
polynomials with respect (,, ). For any 7 > 1, E N. and k = 2 mT? J, it holds that
Ea-A, ha l1x(2))
eV2
where Ay, is the discrete Gaussian on (1/7)Z.
= a. Then, a E [0, 1) and = (2 - 2a. Similar to the proof of Lemma C.4, we apply the Poisson summation formula (Lemma 2.1) as follows.
Proof. Let lon2 [[
Ex hx(x)= = p((1/7)Z)
Σ hx(x)
zE(1/T)²
Σ c-(-2ri))* p(y)
p((1/7)Z)
DEN8
27

---

As previously shown in Lemma C.4, the function fly) = y p(y) achieves its maximum at (v²)² k/2T e² a//T. The issue now is that y is not necessarily contained in yZ. However, we show that "rounding up" y" to syy is sufficient to establish a non-trivial lower bound. Taking the ratio of f(y") and f(87).
$ 3/
log ((8)) le log
Hence. f(87) > //e Combining this observation and the proof of Lemma C.4 leads to the conclusion.
Theorem C.6 (Theorem 4.2 restated). For any constant C > O, given 7 > 1, > 0 such that yo C, estimation error parameter 1) > 0, and ó E (0, 1), there exists brute-force search estimator ú Rdxx + sd-1 that uses n poly n, 1/1, 1/8) samples and achieves [/ Dnn) over i...d. samples Z1...., En Pu. where Pu is the (7, a) Gaussian pancakes distribution with secrel direction S
ul S n² with probability at least
Proof. Without loss of generality, we assume 1) S 1//y. If the given error parameter 7j is larger than 1/7, we set rj = 1/7. Let C be any ne-net of gd-1, Our brute-force search estimator is
1 n2
û arg max F(v)) DEC
where B(v)
Ty ((x,, v))
We choose 3 1/V/TT vy as the contrast function parameter for reasons explained later. The population
limit of E is E (Eq.(24), (24)), and the monotonicity of E with respect to (u, w)² (Lemma C.3) implies that = arg maxga-1 E(v) in the infinite-sample limit. For ~ Pu, the distribution of (a. v) is A6,. where _² = (1 +1+0 o2)/(u, w)² - 1. Let U1, U2 E gd-1 be such that (u, v1)2 - (u, v2) = E².
Let E (1 / (u, 01)² and E = (1 + /²)/ 02)² 1. Notice that
1
1
1+ 1+ 2 1+
For f-far pairs V1, such that & is sufficiently small, we establish a lower bound on F(w1) F(v2) in terms of e. This implies that if E(w,) and E(ws)) are close, then (u, ,2 and (u, v2)² are also close.
By Claim C.2, for any v E Sd-1, we have
E(v) (T 19)0 =
82)
k=0
Since all the terms in the series are non non-negative and monotonically decreasing in &, for any l e N and U1 U22 E gd-1 such that & ε2. we have
a²
((++3)
E(v1) - E(v2) 2
(1 32)
1
1 1 3
a²
1 + E
((++
k-1
1+ 2 k-2 i+ E
+...+11
(1 + (2)4(1 + Ei
1 3
+
(1+
2
(1 + (1) + 7
1
22
62
2 (1 Be) k
1 02
We choose == | 82 = 1/k. E < C²/k k for some constant C² > 0 (this will be justified
later), then by Corollary C.5, we have that az 2 1/(2Te?2)) Thus, using the fact that 1 + S et for any E RR,
2k
>
2 2k
2
E²
(1+32) (2) k-
1 02
c'11
1 1+02
2'
(1+02
28

---

Since o² c/2/// < C², it follows that
e² ?
B(v1) B((2)) 2T C2)e
(26)
Taking the contrapositive. if v1, 02 gd-1 are such that { E2, E S /²/k and E(v1) E(v2) - e² 22((2((1+ + C2)e +))), then (u, v1)² (u, U2)² s
Equipped with this result, we revisit our 77-net C of g Let v* arg ma E(v) be the population maximizer of E within C. By the monotonicity of E(v) with respect to (u. v)² we have that 1 (u, 2² S n/2 Moreover, since by assumption o² < C² /n2 and n/ 1/72 S 1, the
corresponding noise level (5*)² == (1 +++0 +/)///(u, w²)²
satisfies
(50) v 1 0²
12/2 - 1 0² 12
S 20 + s (2C² +1)/7² 1 1/2
(27)
Now consider à arg max F(()), the maximizer of the empirical objective. By the triangle inequality,
E(v") E(t) (E(v") B(o"))+ -(())+++ E(ū)) - [E( + [ - E(ū)].
(28)
We show that both terms in (28) concentrate. Recall that É(v) =(vn)(11n) Ei= ((v, ax)) and that the function Til satisfies (see proof of Lemma B.11)
B2 B2 (=) TT BP((1/72Z)
(((V++3//1 S V1+
2n Since 5² = 1 we have (x) S 2VT for any 2 E R. Thus. for any fixed E Sd E(v) of i.i.d. bounded random variables T By Hoeffding's inequality, n S (72//1²) log([Cl/6) samples are sufficient to guarantee that for all v E C. |E(v) - B(v) < 7/ with probability least 1 From standard covering number bounds (c.g.. [77. Corollary 4.2.13]). we have |C| < (3/n)". Hence, n S (dy (log(((n) + log(1/8)) samples are sufficient for the desired level of concentration.
follows that E(v*) - E(u)= S 1//// with probability 1 1 over the randomness of û. Since o* satisfies (E*)² < 1/72 (see Eq.(27) and e" < E, where we denote g² (11 (²) û)² the closeness of E(v") and E(ū) implies (u, 001² (u, u)² < v² due to Eq. Hence,
u à = 2(1 (u, 2) - 2n²² 2(1 v) s 3n/
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See our main result presented in Section 3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 1.3, we mention that our hardness result can be circumvented if we aim for learning not in statistical distance, but against bounded discriminators.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification:
Full theorem statements and proofs are provided in Sections B and C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This is purely theoretical paper with experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer:
[NA]
Justification:
This is purely theoretical paper with no experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ Saapii//guddes//oeeeee
wwwiiissssoolloiooiooo iiycc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //iips.cooo wttpccccpppccceeeeccecceccccccct httpa///ggiieee/eeeeuuubiiiiiiia /Codeeeooiissseeeeee wwtpaubmmsssoonni ssisnnol onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is purely theoretical paper with no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is purely theoretical paper with no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
32

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is purely theoretical paper with no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:://neuuuueeeeeeeee httprrpp.....pp..ttt/tieeeeeiiie
Answer: [Yes]
Justification: We present purely theoretical results. No human subjects or data were involved in this work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: We present purely theoretical results fundamental limitations of machine learning, so we do not see any potential for having societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not involve any release of data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use any assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
34

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "JCjuRdGUuA", "reviewer": "Reviewer_27f3", "summary": "Without knowing data distribution, it is computationally hard to estimate score function from data samples, such as the reverse step of diffusion models. One previous work shows that L^2-accurate score estimation along the forward process can help efficiently sampling from arbitrary data distribution. However, this works shows L^2-accurate score estimation is still computationally hard even with polynomial sample complexity. Finding a gap between statistical perspective and computational perspective leads to a set of hard distributions, which are “Gaussian pancakes” distributions. This works conclude computationally efficient  L^2-accurate score estimation should rely on stronger assumptions.", "questions": "Can you remove one “between” in Line 32?", "limitations": "None limitation has been detected.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work brings a set of solid future directions on the grounds of diffusion and computational complexity theory. It can guide fruitfully interesting research topics.\n2. This work also bridges the score estimation with cryptography on computationally  indistinguishability, which is a important property in the cryptography. Also, this work interprets the hardness from lattice-based cryptographic perspective.", "weaknesses": "This work is lack of empirical evidences, especially those related to diffusion models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and rating. We are grateful for the reviewer’s appreciation of the significance of our main result as a bridge between score estimation and the cryptographic notion of computational indistinguishability, as well as the future research directions we have proposed in light of our findings. We also appreciate the reviewer pointing out the typo in our submission; it will be corrected in the revised version. \n\nWe respectfully disagree with the view that lack of empirical evidence constitutes a weakness in our paper. While empirical evidence is indeed valuable in many areas of research, no amount of empirical evidence can establish computational hardness. Even if a large class of algorithms fails to solve a given problem, there is no guarantee that a different algorithm will not succeed. Instead, computer scientists and cryptographers begin with a few core hardness assumptions and rely on mathematical proofs to provide guarantees about computational hardness.\n\nGiven this context, our work demonstrates such fundamental limits through theoretical analysis. Specifically, our paper provides mathematical proofs that establish the hardness of L2-accurate score estimation under standard cryptographic assumptions.\n\nPlease let us know if there are any additional comments or questions. Thank you again for your time and consideration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jn1rqjaneF", "reviewer": "Reviewer_q3zX", "summary": "This paper shows that $L^2$-accurate score estimation, a crucial primitive in the theory of diffusion models and sampling, is computationally hard in the worst-case. The main theorem is a negative result that provides a statistical-computational gap: if computationally efficient $L^2$-accurate score estimation is possible, then one has a computationally efficient algorithm for solving the *Gaussian pancakes problem*, a hard instance under widely believed hardness assumptions from lattice-based cryptography. This negative result is particularly important in relation to Chen et al. (2023), as they showed that access to an $L^2$-accurate score estimation oracle (with some mild additional assumptions) admits an algorithm for sampling from any arbitrary distribution. The computational hardness of such an oracle suggests future directions for research in making stronger assumptions so such an oracle *is* possible (omitting the worst-case instance of Gaussian pancakes) or weaker criteria for understanding when a sample generated from the DDPM process is \"good enough.\"\n\nThe main result, Theorem 3.1, is proven mainly by way of using Theorem 2 of Chen et al. (2023), which states that, for any distribution, the output of the DDPM algorithm provides a certificate for Gaussianity. Importantly, this DDPM algorithm assumes access to an $L^2$-accurate score estimation oracle, so by using this certificate of Gaussianity on the particular choice of the Gaussian pancake distribution, we can distinguish just by using the certificate of Gaussianity as a test statistic. Theorem 4.2 also gives the sample complexity of estimating the Gaussian pancake distribution through a brute force search over the possible hidden directions.", "questions": "I have a couple of main questions, but they may stem from my ignorance of the literature:\n\n1. Because the Gaussian pancakes class is hard, I assume that there have been positive results in the light of this computationally hard instance in other problems that exclude this class. What are examples of such distribution-specific guarantees?\n2. How does the \"weaker criteria for evaluating sample quality\" in Section 1.3 relate to the Theorem 4.2? Is there still a statistical-computational gap if we allowed \"distinguish\" to be a looser requirement?", "limitations": "The authors have addressed the limitations of the work in the NeurIPS paper checklist. Because this is mainly a theory paper, I do not see it as having other ethical conflicts.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is very well-written and clear, and its main result, Theorem 3.1, is an interesting addition to the literature on both score estimation in diffusion model theory and the literature on statistical-computational gaps. I am not not an expert in either of these fields, particularly not in diffusion model theory, but I was able to mostly follow along with the proof and main statements in the work. However, because of my lack of previous exposure, I would take my words with a grain of salt.\n\n**Originality:** As far as I know, this work is the only one to evaluate the statistical-computational gap of the $L^2$-accurate score estimation oracle in DDPM. The proof's use of Gaussian pancakes as the hard distribution is certainly original and interesting, and I believe that the result itself is an original contribution to both the literature on diffusion models and the learning theory literature on proving computational hardness results for statistical problems.\n\n**Quality:** The work proves a theorem, Theorem 3.1, that is well-motivated and has ample analysis and interpretation to supplement the main claim. As far as my understanding goes, the proofs seem to be correct, though I may have not understood some details in the introduction of the stochastic differential equation defining the diffusion model process.\n\n**Clarity:** The paper is very well-written and clear. Although I am an outsider to the diffusion model theory literature, I was able to roughly follow along with the arguments and the main theorem seemed very well-motivated after Sections 1 and 2. In particular, the authors do a very good job in sketching the implications of their main result in Section 1.3, and I appreciated the clarity of that section for bringing to light the significance of the result.\n\n**Significance:** I am an outsider to the field of diffusion models, so I cannot confidently speak to the significance, but the result does seem very well-motivated and important, as, to my understanding, the score estimation oracle is central to the diffusion model process. Outside of the diffusion model literature, I believe that the general technique of using the Gaussian panacakes distribution as a hard instance for a statistical-computational gap is worth highlighting as an important technique. For this alone, I believe this paper presents a valuable contribution.", "weaknesses": "The paper was well-written and I could not find any typographical or clarity issues. To the best of my checking, the theorem seemed correct, and its proof outline provided insight into the argument. I am an outsider to the literature, so I would not be confident in critiquing the paper in terms of weaknesses. As far as I can see, it the paper is clear, the theorem is well-motivated, and the argument is correct.\n\nIf anything, one might critique that perhaps the work would be more complete with a positive result towards a distribution-specific narrowing of DDPM that avoids the Gaussian pancakes distributions. However, I have no gauge on how hard/standard this might be in the literature, and it seems that $L^2$-accurate score estimation is central enough a primitive in DDPM that this negative result is important in its own right.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and the detailed review of our paper. The reviewer's summary effectively and accurately captures the essence of our results. We address elements of the review below, which highlight the strengths of our paper and pose insightful questions that deserve further investigation.\n\n> *The paper is very well-written and clear … the main theorem seemed very well-motivated after Sections 1 and 2. In particular, the authors do a very good job in sketching the implications of their main result in Section 1.3, and I appreciated the clarity of that section for bringing to light the significance of the result.*\n\nWe are grateful for the reviewer’s appreciation of the motivation behind our work and the clarity of our exposition.\n\n> *… the work would be more complete with a positive result towards a distribution-specific narrowing of DDPM that avoids the Gaussian pancakes distributions. However, I have no gauge on how hard/standard this might be in the literature, and it seems that L2-accurate score estimation is central enough a primitive in DDPM that this negative result is important in its own right.*\n\nWe agree that pairing negative results with positive results might provide a more complete understanding of the computational landscape of L2-accurate score estimation. However, as the reviewer noted, we believe that our negative result is significant in its own right. Moreover, we think that positive results warrant separate and careful treatment.\n\nThere are various ways of excluding Gaussian pancakes, each leading to an intriguing class of distributions with its own set of technical challenges. Specific examples will be provided when addressing the reviewer’s **Question 1**. However, it’s important to note that each of these distribution classes has been explored in separate papers, each involving non-trivial analyses. Thus, from the perspective of topic homogeneity, it is not clear which classes should be analyzed within this paper and which might be better suited for separate investigation.\n\n> *1. Because the Gaussian pancakes class is hard, I assume that there have been positive results in the light of this computationally hard instance in other problems that exclude this class. What are examples of such distribution-specific guarantees?*\n\nThis is a great question. In the context of computationally efficient score estimation, recent works have analyzed mixtures of Gaussians with either a fixed number of components or \"well-conditioned\" components. In particular, Shah et al. [SCK23] demonstrated a score estimator for mixtures of spherical Gaussians with well-separated means, while Chen et al. [CKS24] provided a score estimator for $k$-mixtures of arbitrary Gaussians, with a running time that depends *exponentially* on $k$ and a certain \"condition number\" $\\tau$ of the mixture components. Note that the running time of Chen et al.’s score estimator is polynomial in the data dimension $d$ if $k$ and $\\tau$ are constants with respect to $d$. These distribution classes exclude Gaussian pancakes since the pancakes have degenerate covariances and the number of components $k$ grows with $d$ via the parameter $\\gamma$.\n\nAnother class of interesting distributions is motivated by non-Gaussian component analysis (NGCA). A prototypical distribution arising in NGCA consists of a low-dimensional non-Gaussian \"signal\" embedded in high-dimensional Gaussian noise. More precisely, there exists a hidden $k$-dimensional subspace $V$ such that the projection of the distribution onto $V$ is non-Gaussian, while the projection onto its orthogonal complement $V^\\perp$ is Gaussian. In standard NGCA settings where both $k$ and the non-Gaussian signal distribution are kept fixed with respect to the dimension $d$, polynomial time estimators for the hidden subspace $V$ are known [TV18, GS19]. \n\nAgain, Gaussian pancakes distributions are excluded from this class since their non-Gaussian \"signal\" distribution depends on $d$ via the parameters $\\gamma$ and $\\sigma$. In standard NGCA the difficulty stems solely from the signal being embedded in higher dimensions. In Gaussian pancakes, the difficulty is twofold: not only is the signal embedded in higher dimensions, but the 1D discrete Gaussian with spacing $1/\\gamma$ also becomes increasingly difficult to distinguish from the 1D standard Gaussian as $\\gamma$ grows with $d$.\n\n> *2. How does the \"weaker criteria for evaluating sample quality\" in Section 1.3 relate to the Theorem 4.2? Is there still a statistical-computational gap if we allowed \"distinguish\" to be a looser requirement?*\n\nAnother great question. We do not have clear answers, but it would depend on the specific weaker criterion used. For example, if the weaker criterion were \"match the first two moments\", then we do not anticipate any statistical-computational gap. An algorithm that simply outputs $\\mathcal{N}(\\hat{\\mu}, \\hat{\\Sigma})$, where $\\hat{\\mu}, \\hat{\\Sigma}$ are the empirical mean and covariance, would suffice. Thus, for this nearly trivial criterion, we can bypass L2-accurate score estimation entirely and directly satisfy the weak criterion.\n\nWe believe that understanding the computational complexity of learning a generative model that is \"indistinguishable\" from the data distribution with respect to interesting metrics, such as integral probability metrics induced by various function classes, is an exciting future direction.\n\n**References**\n\n- [CKS24] Sitan Chen, Vasilis Kontonis, Kulin Shah. Learning general Gaussian mixtures with efficient score matching. arXiv preprint. 2024\n- [SCK23] Kulin Shah, Sitan Chen, Adam Klivans. Learning Mixtures of Gaussians Using the DDPM Objective. *NeurIPS* 2023.\n- [TV18] Yan Shuo Tan, Roman Vershynin. Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods. *COLT* 2018.\n- [GS19] Navin Goyal, Abhishek Shetty. Non-Gaussian Component Analysis using Entropy Methods. *STOC* 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pVFg9olkZc", "reviewer": "Reviewer_CMgH", "summary": "This paper investigates the difficulty of distinguishing a Gaussian pancake distribution from a Gaussian distribution from the perspective of score estimation. The authors show that, by assuming the $L^2$-error of the score estimation is of the order $\\log(d)$, there is a polynomial-time algorithm that solves the Gaussian pancake problem. Moreover, they show that for the cryptographically hard regime, there is a polynomial sample complexity $O(d)$ that ensures a small score estimation error for Gaussian pancake problems.", "questions": "please solve my concern in the weaknesses part", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors introduce a new perspective on the Gaussian pancake problem by presenting the score estimation problem from diffusion models. Specifically, their Theorem 3.1 demonstrates that if the score is estimated accurately, then the Gaussian pancake problem can be solved in polynomial time. This perspective is novel for the Gaussian pancake problem.", "weaknesses": "One main selling point, which has been emphasized repeatedly in the paper and is also the title of this paper, is that the score estimation is cryptographically hard. This is confusing to me. In fact, as I understand it, the main theorem states that the Gaussian pancake problem can be solved under certain assumptions, while the hardness seems to state that the score estimation is hard.\n\nIf I understand correctly, the hardness arises from the assumption that $\\gamma\\sigma = O(1)$ in Theorem 4.2, which is known to be hard in existing literature, while the score estimation has a polynomial upper bound. However, I cannot see the hardness from Theorem 4.2. Even though the Gaussian pancake problem is hard, the score estimation is accurate. If we further combine Theorem 4.2 with Theorem 3.1, I guess the authors want to argue that if the score estimation is easy, then the Gaussian pancake problem can be solved. However, as it is already known that the Gaussian pancake problem is hard, the score estimation cannot be easy. But the score estimation error assumption in Theorem 3.1 does not match Theorem 4.2's conclusion. In fact, the $O(\\log d)$ assumptions of Theorem 3.1 on the estimation error are smaller than the polynomial $O(d)$ upper bound in Theorem 4.2, which may make the story incomplete.\n\nPlease correct me if my understanding is incorrect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for clearly communicating points of confusion and giving us the opportunity to clarify our results. Before providing any clarifications, we would like to mention that the reviewer’s summary below accurately and succinctly captures the main contribution of our paper.\n\n> *I guess the authors want to argue that if the score estimation is easy, then the Gaussian pancake problem can be solved. However, as it is already known that the Gaussian pancake problem is hard, the score estimation cannot be easy.*\n\nWe now address specific questions raised by the reviewer.\n\n> *… as I understand it, the main theorem states that the Gaussian pancake problem can be solved under certain assumptions, while the hardness seems to state that the score estimation is hard.*\n\nWe show that the Gaussian pancakes problem can be solved *if* we can solve L2-accurate score estimation for Gaussian pancakes distributions. More precisely, if an **efficient** algorithm existed for estimating the scores of Gaussian pancakes, it would imply the existence of an **efficient** algorithm for solving the Gaussian pancakes problem. This, as the reviewer correctly observed, is a contradiction since the Gaussian pancakes problem is known to be computationally hard.\n\nThe qualifier “efficient” is crucial here. Our score estimation algorithm for Gaussian pancakes (presented in Section 4) is **not** efficient; it involves a brute-force search over the d-dimensional unit sphere which requires exponential-in-d time. The polynomial quantity in Theorem 4.2 refers to the **number of samples**, not the **running time** of the estimator.\n\nThe main purpose of our inefficient estimator in Section 4 is to highlight a *gap* between what’s statistically possible, with no limits on computation, and what’s computationally feasible in poly(d) time (hence the name, statistical-to-computational *gap*). If a statistical problem is impossible even with infinite computation, then any claim of its computational hardness is vacuous. Section 4 demonstrates that our computational hardness result from Section 3 is not vacuous, as L2-accurate score estimation for Gaussian pancakes can be achieved with exp(d) computation time (and poly(d) samples).\n\n> *But the score estimation error assumption in Theorem 3.1 does not match Theorem 4.2's conclusion. In fact, the $O(\\log d)$ assumptions of Theorem 3.1 on the estimation error are smaller than the polynomial $O(d)$ upper bound in Theorem 4.2, which may make the story incomplete.*\n\nTo provide context, the $\\epsilon = O(1/\\sqrt{\\log d})$ assumption in Theorem 3.1 refers to an upper bound on the **L2 score estimation error** $\\epsilon$. Meanwhile, the $n = \\mathrm{poly}(d, \\gamma, 1/\\eta)$ in Theorem 4.2 refers to the **number of samples** sufficient for estimating the Gaussian pancakes secret direction up to L2-error $\\eta$. The magnitudes of these two quantities ($\\epsilon$ and $n$) are not meant to be directly compared.\n\nInstead, the two quantities are related as follows. For any score estimation algorithm (whether efficient or not) to satisfy the L2 score estimation error assumption $\\epsilon = O(1/\\sqrt{\\log d})$ in Theorem 3.1, it is *statistically sufficient* to choose $n$ to be some large **polynomial in $d$**. In other words, there exists a score estimation algorithm that achieves the L2-error bound $\\epsilon = O(1/\\sqrt{\\log d})$  using a polynomial number of samples. Our Theorem 4.2 provides a **computationally inefficient** score estimator with such guarantees.\n\nWe hope this explanation resolves any confusion and respectfully ask if the reviewer would be willing to reconsider our rating in light of this clarification. Thank you again for your time and consideration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper shows a statistical to computational gap for L2 score estimation under standard cryptographic assumptions. Reviewers agree this is an interesting and valuable contribution to understanding the computational complexity of problems related to diffusion models
Decision: Accept (poster)