Single-Index Models are high-dimensional regression problems with planted
structure, whereby labels depend on an unknown one-dimensional projection of
the input via a generic, non-linear, and potentially non-deterministic
transformation. As such, they encompass a broad class of statistical inference
tasks, and provide a rich template to study statistical and computational
trade-offs in the high-dimensional regime.
While the information-theoretic sample complexity to recover the hidden
direction is linear in the dimension $d$, we show that computationally
efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree
Polynomial (LDP) framework, necessarily require $\Omega(d^{k^\star/2})$
samples, where $k^\star$ is a "generative" exponent associated with the model
that we explicitly characterize. Moreover, we show that this sample complexity
is also sufficient, by establishing matching upper bounds using a partial-trace
algorithm. Therefore, our results provide evidence of a sharp
computational-to-statistical gap (under both the SQ and LDP class) whenever
$k^\star>2$. To complete the study, we provide examples of smooth and Lipschitz
deterministic target functions with arbitrarily large generative exponents
$k^\star$.

单指标模型是高维回归问题，根据未知的一维投影通过非线性、潜在非确定性的变换，标签与输入相关，涵盖了广泛的统计推断任务，提供了在高维领域研究统计和计算权衡的丰富模版。我们证明了在统计查询（SQ）和低次多项式（LDP）框架内计算高效算法所需的样本复杂度最低为 Ω(d^k/2)，其中 k 是与模型关联的 “生成” 指数，我们明确定义了这个指数。此外，通过使用部分跟踪算法建立的匹配上界证明了这个样本复杂度也是充分的。因此，我们的结果表明，在 SQ 和 LDP 类中，只要 k>2，计算与统计之间存在明显的差距。为了完成这个研究，我们提供了具有任意大生成指数 k 的平滑和 Lipschitz 确定的目标函数的示例。