Provable Bounds for Learning Some Deep Representations
Sanjeev Arora Princeton University, Computer Science Department and Center for Computational Intractability. Email: This work is supported by the NSF grants CCF-0832797, CCF-1117309, CCF-1302518, DMS-1317308, and Simons Investigator Grant. Aditya Bhaskara Google Research NYC. Email: The work was done while the author was a Postdoc at EPFL, Switzerland. Rong Ge Microsoft Research, New England. Email: Part of this work was done while the author was a graduate student at Princeton University and was supported in part by NSF grants CCF-0832797, CCF-1117309, CCF-1302518, DMS-1317308, and Simons Investigator Grant. Tengyu Ma Princeton University, Computer Science Department and Center for Computational Intractability. Email: This work is supported by the NSF grants CCF-0832797, CCF-1117309, CCF-1302518, DMS-1317308, and Simons Investigator Grant.
Abstract
We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an $n$ node multilayer neural net that has degree at most $n^{\gamma}$ for some $\gamma<1$ and each edge has a random edge weight in $[-1,1]$ . Our algorithm learns almost all networks in this class with polynomial running time. The sample complexity is quadratic or cubic depending upon the details of the model.
中文速览
针对深度神经网络难以用理论保证学习这一核心难题，研究者提出了一类随机生成式深度网络模型：网络每层节点度数不超过 $n^\gamma$（$\gamma<1$），边权随机取自 $[-1,1]$，顶层输入为稀疏 0/1 向量，逐层向下做带阈值的线性计算。基于"同层中频繁共同激活的节点对很可能连接到上层同一节点"这一改进版 Hebb 规则，算法通过统计层内节点的两两（或三元）相关性，再利用图平方根恢复方法重建层间边结构，实现逐层无监督学习。理论分析证明，该算法能以多项式时间、二次或三次多项式样本复杂度学习该类中几乎所有网络，且学到的网络与真实网络生成的分布在统计上不可区分。这项工作不仅为深度生成模型的可证明学习提供了首批严格理论保障，还从理论上验证了"权重绑定"、去噪自编码器等实践中广泛使用的深度学习假设在随机网络上确实成立。
原文 arXiv:1310.6343;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1310.6343v1