DISCO-Func: Discrete Optimization in Neural Network Function Classes through Submodular Analysis

Driven by advances in deep learning, powerful automated algorithms enable us to hold conversations with virtual assistants running on our mobile phone, cars are autonomously driving on streets in mixed traffic, increasingly sophisticated medical diagnostic software is assisting doctors in making life-saving decisions, and social networks and media libraries are automatically indexed and personalized to individual users. At the core of these advances is a simple mathematical technique, stochastic gradient descent, which enables a network to be trained on potentially millions of training examples. Stochastic gradient descent assumes numbers are continuous, while in practice computers are discrete. If we devote sufficient computational resources to simulating continuous numbers, the precision is high enough in practice to achieve excellent empirical performance, but it does so at a computational cost that imposes a limit on the model size that we can implement in practice, or increases the time required to perform computation on a single image. This results in a less advantageous tradeoff between accuracy and throughput. In this project, we will extend the foundations of neural network training to incorporate submodular analysis for the optimization of discrete neural network parameters. In doing so, we provide a powerful strategy for developing highly-efficient neural networks.