Depth-Width Trade-offs for Neural Networks via Topological Entropy
Kaifeng Bu1 (K.Bu) , Yaobo Zhang2,3 (Y.Zhang) and Qingxian Luo4,5 Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA Zhejiang Institute of Modern Physics, Zhejiang University, Hangzhou, Zhejiang 310027, China Department of Physics, Zhejiang University, Hangzhou Zhejiang 310027, China School of Mathematical Sciences, Zhejiang University, Hangzhou, Zhejiang 310027, China Center for Data Science, Zhejiang University, Hangzhou Zhejiang 310027, China
Abstract
One of the central problems in the study of deep learning theory is to understand how the structure properties, such as depth, width and the number of nodes, affect the expressivity of deep neural networks. In this work, we show a new connection between the expressivity of deep neural networks and topological entropy from dynamical system, which can be used to characterize depth-width trade-offs of neural networks. We provide an upper bound on the topological entropy of neural networks with continuous semi-algebraic units by the structure parameters. Specifically, the topological entropy of ReLU network with $l$ layers and $m$ nodes per layer is upper bounded by $O(l\log m)$ . Besides, if the neural network is a good approximation of some function $f$ , then the size of the neural network has an exponential lower bound with respect to the topological entropy of $f$ . Moreover, we discuss the relationship between topological entropy, the number of oscillations, periods and Lipschitz constant.
中文速览
神经网络的表达能力究竟受深度和宽度怎样的制约，一直是深度学习理论的核心问题；这项工作引入动力系统中的拓扑熵（topological entropy）作为刻画函数复杂度的新工具来回答这一问题。研究者证明，对于使用连续半代数激活函数（continuous semi-algebraic units）的深度神经网络，其拓扑熵由网络结构参数严格上界——例如 $l$ 层、每层 $m$ 个节点的 ReLU 网络，拓扑熵不超过 $O(l\log m)$；反过来，若某神经网络要良好逼近一个具有正有限拓扑熵的函数 $f$，则网络规模必须关于 $f$ 的拓扑熵呈指数级增长，从而给出深度-宽度权衡的指数下界。此外，论文还厘清了拓扑熵与函数振荡次数、周期结构以及 Lipschitz 常数之间的定量关系，将已有的深度分离结果统一到一个更简洁的动力系统框架之下，为理解深层网络为何比浅层网络更高效提供了新的理论支撑。
原文 arXiv:2010.07587;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2010.07587v1