AF: Small: Efficiently Learning Neural Network Architectures with Applications

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

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.