AF: Small: Efficiently Learning Neural Network Architectures with Applications

University Of Texas At Austin, Austin TX

Investigators

Abstract

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.