The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
复制标题
神经网络中的近似、深度分离和可学习性之间的联系
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ohad Shamir
中科院分区：
文献类型：
--
作者：
Eran Malach;Gilad Yehudai;Shai Shalev;Ohad Shamir
最近的几项工作显示了深层神经网络和逼近能力较差的假设类之间的分离结果，如浅层网络或核类。另一方面，深度网络可以有效地表达目标函数，并不意味着该目标函数可以通过深度神经网络有效地学习。在这项工作中，我们研究了可学习性和逼近能力之间的复杂联系。我们证明了目标函数的深层网络的可学习性取决于更简单的类逼近目标的能力。具体地说，我们证明了一个函数在深神经网络上可以通过梯度下降学习的必要条件是能够用浅神经网络逼近该函数，至少在弱意义上是这样。我们还证明了一类函数可以通过有效的统计查询算法学习当且仅当它可以被某个核类在弱意义下逼近。我们给出了几个演示深度分离的函数的例子，并得出结论，即使是通过可以有效地逼近它们的假设类，它们也不能有效地学习。
Several recent works have shown separation results between deep neural networks, and hypothesis classes with inferior approximation capacity such as shallow networks or kernel classes. On the other hand, the fact that deep networks can efficiently express a target function does not mean that this target function can be learned efficiently by deep neural networks. In this work we study the intricate connection between learnability and approximation capacity. We show that learnability with deep networks of a target function depends on the ability of simpler classes to approximate the target. Specifically, we show that a necessary condition for a function to be learnable by gradient descent on deep neural networks is to be able to approximate the function, at least in a weak sense, with shallow neural networks. We also show that a class of functions can be learned by an efficient statistical query algorithm if and only if it can be approximated in a weak sense by some kernel class. We give several examples of functions which demonstrate depth separation, and conclude that they cannot be efficiently learned, even by a hypothesis class that can efficiently approximate them.
DOI：
--
发表时间：
2020-06
期刊：
--
影响因子：
--
作者：
Surbhi Goel;Aravind Gollakota;Zhihan Jin;Sushrut Karmalkar;Adam R. Klivans
通讯作者：
Surbhi Goel;Aravind Gollakota;Zhihan Jin;Sushrut Karmalkar;Adam R. Klivans
DOI：
--
发表时间：
2020-05
期刊：
ArXiv
影响因子：
--
作者：
Spencer Frei;Yuan Cao;Quanquan Gu
通讯作者：
Spencer Frei;Yuan Cao;Quanquan Gu
近似就足够了：维度和边际复杂性的概率变体
DOI：
--
发表时间：
2020
期刊：
Proceedings of Thirty Third Conference on Learning Theory
影响因子：
--
作者：
Kamath Pritish;Montasser Omar;Srebro Nathan
通讯作者：
Srebro Nathan