The Computational Complexity of Learning Gaussian Single-Index Models

单指数模型是具有植入结构的高维回归问题，标签依赖于通过通用、非线性和潜在非确定性变换的未知一维投影的输入。因此，它们包括广泛的统计推断任务，并提供了一个丰富的模板来研究高维情况下的统计和计算折衷。虽然恢复隐藏方向的信息论样本复杂度在维数d中是线性的，但我们表明，在统计查询（SQ）和低次多项式（LDP）框架内，计算有效的算法必须需要Ω（d ^ k * / 2）个样本，其中k *是我们明确表征的与模型相关的“生成”指数。此外，我们通过使用部分跟踪算法建立匹配的上界，表明这个样本复杂度也是充分的。因此，我们的结果提供了证据，表明在SQ和LDP类下，只要k * > 2，就存在明显的计算-统计差距。为了完成研究，我们提供了具有任意大的生成指数k * 的光滑和Lipschitz确定目标函数的示例。

论文旨在解决单指数模型在高维回归问题中的计算复杂度和统计复杂度之间的差距问题。该问题是否是一个新问题？

论文提出了使用统计查询和低次多项式算法来解决单指数模型的计算复杂度问题，并明确了与该模型相关的生成指数。同时，论文证明了在该模型中，计算复杂度与统计复杂度之间存在一个锐利的差距。

论文的亮点在于提出了一种新的解决高维回归问题计算复杂度和统计复杂度之间差距的方法，并提供了相应的理论证明。论文还提供了平滑和Lipschitz确定性目标函数的例子，并证明了与该模型相关的生成指数可以任意大。实验使用了部分跟踪算法，并提供了相应的开源代码。

在相关研究方面，最近的研究集中在高维回归问题的计算复杂度和统计复杂度之间的差距。相关论文包括“Computational Lower Bounds for Fourier PCA and Sketching”和“Statistical-Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures”。