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

arXiv cs.LG 论文
neural-networks computational-statistical-tradeoff single-index-model gradient-based-methods sample-complexity theoretical-analysis

摘要

本文证明，使用基于梯度的方法训练的两层神经网络能够实现学习高斯单指数模型的最优计算-统计权衡，对于所有生成指数，匹配SQ下界至多对数因子，并通过一种新颖的权重扰动技术扩展到稀疏设置。

arXiv:2606.15219v1 公告类型：新 摘要：本文研究以下问题：使用基于梯度的方法训练的神经网络能否在学习高斯单指数模型时实现最优计算-统计权衡？先前研究表明，在统计查询（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）的潜在基于梯度的解决方案。
查看原文
查看缓存全文

缓存时间: 2026/06/16 11:38 

# 神经网络能否实现最优的计算-统计权衡？——单指标模型分析
来源：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）

相似文章

草图线性对比学习：近似、优化与统计缩放

arXiv cs.LG

本文推导了在高斯潜变量模型下的草图线性对比学习的缩放定律，分析了风险如何分解为近似项、优化项和统计项，并为对比学习中平衡模型规模、数据和计算提供了理论指导。