可高效计算的函数必有稀疏组合结构，可用浅层网络逼近。
On efficiently computable functions, deep networks and sparse compositionality
- 若函数在固定精度下可高效计算，则存在稀疏有向图表示
- 对应神经网络大小与深度为输入输出精度的多项式量级
- 适用于研究深度学习的表达能力与优化机制
我们证明，在任意固定输入输出精度下，若函数具有高效图灵可计算性，则其存在组合稀疏（有界扇入、多项式规模）的有向无环图表示，并存在相应的神经网络近似器，达到目标精度。具体而言：若函数 $f:[0,1]^d\to\R^m$ 在比特深度上多项式时间内可计算，则对任意精度对 $(n,m_{\mathrm{out}})$，存在有界扇入布尔电路，其大小与深度为 $\poly(n+m_{\mathrm{out}})$，用于计算离散化映射；将每个门替换为常数大小的神经模拟器，即可得到大小与深度为 $\poly(n+m_{\mathrm{out}})$ 的深度网络，实现精度 $\varepsilon=2^{-m_{\mathrm{out}}}$。我们还将这些构造与组合逼近率 \\cite{MhaskarPoggio2016b,poggio_deep_shallow_2017,Poggio2017,Poggio2023HowDS} 及优化视为对稀疏结构的分层搜索联系起来。
原文摘要 · Abstract (English)
We show that \emph{efficient Turing computability} at any fixed input/output precision implies the existence of \emph{compositionally sparse} (bounded-fan-in, polynomial-size) DAG representations and of corresponding neural approximants achieving the target precision. Concretely: if $f:[0,1]^d\to\R^m$ is computable in time polynomial in the bit-depths, then for every pair of precisions $(n,m_{\mathrm{out}})$ there exists a bounded-fan-in Boolean circuit of size and depth $\poly(n+m_{\mathrm{out}})$ computing the discretized map; replacing each gate by a constant-size neural emulator yields a deep network of size/depth $\poly(n+m_{\mathrm{out}})$ that achieves accuracy $\varepsilon=2^{-m_{\mathrm{out}}}$. We also relate these constructions to compositional approximation rates \cite{MhaskarPoggio2016b,poggio_deep_shallow_2017,Poggio2017,Poggio2023HowDS} and to optimization viewed as hierarchical search over sparse structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。