权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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表明，由一层sigmoids组成的神经网络即使在存在噪声的情况下也可以在全多项式时间内学习。这是已知的最有表现力的类，可以有效地学习。这一结果能否推广到更复杂的网络？这个问题与内核方法和内核近似有着有趣的联系。对于ReLU活动，PI已经表明，在最坏的情况下，这个问题很可能是计算上难以解决的。那么，有趣的问题就变成了，要证明这些网络在计算上是可处理的，需要做哪些最小的假设。在最近的一项工作中，PI已经表明，存在分布假设，这意味着用于学习复杂的ReLU网络的全多项式时间算法。这些假设可以被削弱吗？这项工作必须证明某些算法不会通过使用压缩方案过拟合。另一种类型的假设，即未知网络的权重是以某种随机方式选择的（而不是在最坏情况下成功）。这对应于机器学习中随机初始化的概念。我们能否证明一种用于学习神经网络的平滑分析，在这种分析中，我们可以为几乎所有的网络给出完全多项式时间的学习算法？最后，在本提案中，我们将探索哪些其他任务可以简化为各种类型的简单神经网络学习。例如，一位压缩感测的问题可以被视为使用尽可能少的样本来学习阈值激活。尽管如此，我们仍然缺乏一个比特压缩感知算法，具有最佳的噪声容忍度。另一个典型的例子是矩阵或张量完成，其中可以减少这些关于多项式激活的学习挑战。寻找适当的正则化以确保低样本复杂度是一个令人兴奋的研究领域。

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

DOI：
发表时间：
2020-06
期刊：
影响因子：
0
作者：
Surbhi Goel;Aravind Gollakota;Zhihan Jin;Sushrut Karmalkar;Adam R. Klivans
通讯作者：
Surbhi Goel;Aravind Gollakota;Zhihan Jin;Sushrut Karmalkar;Adam R. Klivans

Learning Ising Models with Independent Failures

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