神经网络能否实现最优计算-统计权衡？对单指数模型的分析

# 神经网络能否实现最优的计算-统计权衡？——单指标模型分析
来源：https://arxiv.org/abs/2606.15219  
查看PDF (https://arxiv.org/pdf/2606.15219)

> **摘要：** 本文探讨以下问题：基于梯度方法的神经网络能否在学习高斯单指标模型时实现最优的计算-统计权衡？此前研究表明，统计查询（SQ）框架下的任何多项式时间算法都需要 $\Omega(d^{s^\star/2}\lor d)$ 个样本，其中 $s^\star$ 是反映学习底层模型固有难度的生成指数。然而，神经网络能否达到这一样本复杂度尚不清楚。受标签变换和景观平滑等学习单指标模型的先前技术启发，我们提出了一种在多时间多项式时间内训练两层神经网络的统一梯度算法。该方法适用于多种损失函数和激活函数，覆盖了现有的一大类方法。我们证明，该算法学习到的特征表示与未知信号 $\theta^\star$ 高度对齐，其样本复杂度为 $\widetilde{O}(d^{s^\star/2} \lor d)$，对于所有生成指数 $s^\star \geq 1$，在至多一个多对数因子的范围内匹配 SQ 下界。此外，我们将方法扩展到 $\theta^\star$ 为 $k$ 稀疏（$k = o(\sqrt{d})$）的情形，引入了一种利用稀疏结构的新型权重扰动技术。我们推导出对应的 SQ 下界为 $\widetilde{\Omega}(k^{s^\star})$ 量级，我们的方法在至多一个多对数因子的范围内达到此下界。本文提出的框架，尤其是权重扰动技术，具有独立的研究价值，并为稀疏张量 PCA 等其他问题提供了潜在的基于梯度的解决方案。

## 提交历史

来自：Siyu Chen [查看邮箱 (https://arxiv.org/show-email/6b7b9978/2606.15219)]  
**[v1]** 2026年6月13日星期六 09:34:39 UTC（1,738 KB）