We show that $L^2$-accurate score estimation, in the absence of strong
assumptions on the data distribution, is computationally hard even when sample
complexity is polynomial in the relevant problem parameters. Our reduction
builds on the result of Chen et al. (ICLR 2023), who showed that the problem of
generating samples from an unknown data distribution reduces to $L^2$-accurate
score estimation. Our hard-to-estimate distributions are the "Gaussian
pancakes" distributions, originally due to Diakonikolas et al. (FOCS 2017),
which have been shown to be computationally indistinguishable from the standard
Gaussian under widely believed hardness assumptions from lattice-based
cryptography (Bruna et al., STOC 2021; Gupte et al., FOCS 2022).

在样本复杂度与相关问题参数的多项式条件下，我们证明了在没有对数据分布进行强假设的情况下，$L^2$- 准确的评分估计在计算上是困难的。我们的研究基于 Chen 等人（ICLR 2023）的结果，他们证明了从未知数据分布生成样本的问题可以归约为 $L^2$- 准确的评分估计。我们难以估计的分布是最初由 Diakonikolas 等人（FOCS 2017）提出的 “高斯煎饼” 分布，根据在格基密码学领域的广泛公认的困难性假设，这些分布与标准高斯分布在计算上是不可区分的（Bruna 等人，STOC 2021；Gupte 等人，FOCS 2022）。

评分估计的密码学难度

Cryptographic Hardness of Score Estimation

We show a simple reduction which demonstrates the cryptographic hardness of
learning a single periodic neuron over isotropic Gaussian distributions in the
presence of noise. More precisely, our reduction shows that any polynomial-time
algorithm (not necessarily gradient-based) for learning such functions under
small noise implies a polynomial-time quantum algorithm for solving worst-case
lattice problems, whose hardness form the foundation of lattice-based
cryptography. Our core hard family of functions, which are well-approximated by
one-layer neural networks, take the general form of a univariate periodic
function applied to an affine projection of the data. These functions have
appeared in previous seminal works which demonstrate their hardness against
gradient-based (Shamir'18), and Statistical Query (SQ) algorithms (Song et
al.'17). We show that if (polynomially) small noise is added to the labels, the
intractability of learning these functions applies to all polynomial-time
algorithms, beyond gradient-based and SQ algorithms, under the aforementioned
cryptographic assumptions. Moreover, we demonstrate the necessity of noise in
the hardness result by designing a polynomial-time algorithm for learning
certain families of such functions under exponentially small adversarial noise.
Our proposed algorithm is not a gradient-based or an SQ algorithm, but is
rather based on the celebrated Lenstra-Lenstra-Lov\'asz (LLL) lattice basis
reduction algorithm. Furthermore, in the absence of noise, this algorithm can
be directly applied to solve CLWE detection (Bruna et al.'21) and phase
retrieval with an optimal sample complexity of $d+1$ samples. In the former
case, this improves upon the quadratic-in-$d$ sample complexity required in
(Bruna et al.'21).

研究展示了学习单个周期神经元在等向高斯分布中存在噪声时的加密难度，提出了正确性证明，同时证明具有显著普适性，可应用于各种多项式时间算法，并且噪声对这种难度结果的必要性得到了证明。