AF: Small: Efficiently Learning Neural Network Architectures with Applications

AF：小：通过应用程序有效学习神经网络架构

• 批准号: 1717896
• 负责人: Adam Klivans
• 金额: $ 44.99万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717896&HistoricalAwards=false
• 关键词: AF; Small; Efficiently; Learning; Neural

In the last few years there have been several breakthroughs in machine learning and artificial intelligence due to the success of tools for learning "deep neural networks" including the best computer program for playing Go, the best programs for automatically playing Atari games, and the best tools for several fundamental object-recognition tasks. These are considered some of the most exciting new results in all of computer science.From a theoretical perspective, however, the mathematics underlying these neural networks is not as satisfying. We have few rigorous results that explain how and why heuristics for learning deep neural networks perform so well in practice. The primary research goal of this proposal is to develop provably efficient algorithms for learning neural networks that have rigorous performance guarantees and give applications to related problems from machine learning. Given the ubiquity of machine learning algorithms, this research will have direct impact on data science problems from a diverse set of fields including biology (protein interaction networks) and security (differential privacy). The PI is also developing a new data mining course at UT-Austin that will incorporate the latest research from these areas.A central technical question of this work is that of the most expressive class of neural networks that can be provably learned in polynomial time. Furthermore, the algorithm should be robust to noisy data. A neural network can be thought of as a type of directed circuit where the internal nodes compute some activation function of a linear combination of the inputs. The classical example of an activation function is a sigmoid, but the ReLU (rectified linear unit) has become very popular. In a recent work, the PI showed that a neural network consisting of a sum of one layer of sigmoids is learnable in fully-polynomial time, even in the presence of noise. This is the most expressive class known to be efficiently learnable. Can this result be extended to more sophisticated networks? This question has interesting tie-ins to kernel methods and kernel approximations.For the ReLU activiation, the PI has shown that this problem is most likely computationally intractable in the worst case. The intriguing question then becomes that of the minimal assumptions needed to show that these networks are computationally tractable. In a recent work, the PI has shown that there are distributional assumptions that imply fully-polynomial-time algorithms for learning sophisticated networks of ReLUs. Can these assumptions be weakened? This work has to do with proving that certain algorithms do not overfit by using compression schemes. Another type of assumption that the weights of the unknown network are chosen in some random way (as opposed to succeeding in the worst-case). This corresponds to the notion of random initialization from machine learning. Can we prove a type of smoothed analysis for learning neural networks, where we can give fully-polynomial-time learning algorithms for almost all networks?Finally, in this proposal we will explore what other tasks can be reduced to various types of simple neural network learning. For example, the problem of one-bit compressed sensing can be viewed as learning a threshold activation using as few samples as possible. Still, we lack a one-bit compressed sensing algorithm that has optimal tolerance for noise. Another canonical example is matrix or tensor completion, where it is possible to reduce these challenges to learning with respect to polynomial activations. Finding the proper regularization to ensure low sample complexity is an exciting area of research.

在过去的几年里，由于学习“深度神经网络”工具的成功，机器学习和人工智能取得了一些突破，包括下围棋的最佳计算机程序、自动玩 Atari 游戏的最佳程序以及用于几个基本对象识别任务的最佳工具。 这些被认为是所有计算机科学中最令人兴奋的新成果。然而，从理论角度来看，这些神经网络背后的数学并不令人满意。 我们几乎没有严格的结果来解释学习深度神经网络的启发式方法在实践中如何以及为何表现得如此出色。该提案的主要研究目标是开发可证明有效的学习神经网络算法，该算法具有严格的性能保证，并应用于机器学习的相关问题。 鉴于机器学习算法的普遍存在，这项研究将对生物学（蛋白质相互作用网络）和安全（差异隐私）等不同领域的数据科学问题产生直接影响。 PI 还在 UT-Austin 开发了一门新的数据挖掘课程，该课程将纳入这些领域的最新研究。这项工作的一个核心技术问题是可以证明在多项式时间内学习的最具表现力的一类神经网络。 此外，该算法应对噪声数据具有鲁棒性。 神经网络可以被认为是一种有向电路，其中内部节点计算输入线性组合的某个激活函数。 激活函数的经典示例是 sigmoid，但 ReLU（修正线性单元）已变得非常流行。 在最近的一项工作中，PI 表明，即使存在噪声，由一层 sigmoid 之和组成的神经网络也可以在完全多项式时间内学习。 这是已知的最具表现力、可有效学习的课程。 这个结果可以扩展到更复杂的网络吗？ 这个问题与核方法和核近似有有趣的联系。对于 ReLU 激活，PI 表明，在最坏的情况下，这个问题很可能在计算上难以解决。 那么有趣的问题就变成了证明这些网络在计算上易于处理所需的最小假设。 在最近的一项工作中，PI 表明存在分布式假设，这些假设意味着用于学习复杂的 ReLU 网络的完全多项式时间算法。 这些假设是否可以被削弱？ 这项工作与证明某些算法不会通过使用压缩方案而过度拟合。 另一种假设是，未知网络的权重是以某种随机方式选择的（而不是在最坏情况下成功）。 这对应于机器学习中随机初始化的概念。 我们能否证明一种用于学习神经网络的平滑分析，我们可以为几乎所有网络提供完全多项式时间学习算法？最后，在本提案中，我们将探索哪些其他任务可以简化为各种类型的简单神经网络学习。 例如，一位压缩感知问题可以被视为使用尽可能少的样本来学习阈值激活。 尽管如此，我们仍然缺乏一种对噪声具有最佳容忍度的一位压缩感知算法。 另一个典型的例子是矩阵或张量补全，可以减少多项式激活方面的学习挑战。 寻找适当的正则化以确保较低的样本复杂性是一个令人兴奋的研究领域。

项目成果

Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent

• 发表时间: 2020-06
• 作者: Surbhi Goel;Aravind Gollakota;Zhihan Jin;Sushrut Karmalkar;Adam R. Klivans

Learning Ising Models with Independent Failures

学习具有独立故障的 Ising 模型

• 发表时间: 2019
• 期刊: Conference on Learning Theory
• 作者: Goel, Surbhi;Kane, Daniel;Klivans, Adam
• 通讯作者: Klivans, Adam

Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals

• 发表时间: 2019-11
• 期刊: ArXiv
• 作者: Surbhi Goel;Sushrut Karmalkar;Adam R. Klivans

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

• 发表时间: 2017-09
• 作者: Surbhi Goel;Adam R. Klivans

Learning One Convolutional Layer with Overlapping Patches

• 发表时间: 2018-02
• 期刊: ArXiv
• 作者: Surbhi Goel;Adam R. Klivans;Raghu Meka