首次证明深网络在算法上优于浅网络，可高效学习分层傅里叶结构函数。
Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks
- 用分层坐标下降法逐层重构分层傅里叶谱，实现对数深度网络的高效学习。
- 对称子类函数中，常数深度网络在超立方体均匀分布下逼近误差恒定。
- 为深层网络的算法优势提供新理论支撑，适合关注深度学习理论的研究者。
尽管深层网络在实践中优于浅层网络，但理论上的深度分离主要集中在近似能力方面，而算法性结果大多局限于两层与三层网络的比较。本文首次证明了常数深度与对数深度神经网络之间的算法分离。具体而言，我们识别出一类具有分层傅里叶谱结构的布尔函数，对数深度网络可通过分层坐标下降法逐层自适应重构谱结构，从而高效学习。同时，我们展示了一个子类，其中任意具有足够规则激活函数和受控谱范数的常数深度、多项式宽度网络，在超立方体上的均匀分布下，必须承受恒定的 $L^2$ 近似误差。
原文摘要 · Abstract (English)
Despite the empirical advantages of deep networks over shallow ones, theoretical depth separations largely concern approximation power, while algorithmic results are mostly limited to comparisons between two- and three-layer networks. In this work, we prove the first algorithmic separation between constant-depth and logarithmic-depth networks. Specifically, we identify a class of Boolean functions with hierarchically structured Fourier spectra that logarithmic-depth networks can learn efficiently using layerwise coordinate descent by reconstructing the spectra hierarchically and adaptively. We also exhibit a subclass for which every constant-depth, polynomial-width network with sufficiently regular activations and controlled spectral norms must incur constant $L^2$ approximation error under the uniform distribution over the hypercube.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。