CRII: AF: Guarantees for Training Neural Networks

Brandeis University, Waltham MA

Investigators

Abstract

The past decade has seen explosive progress in artificial intelligence, with conspicuous improvements in autonomous vehicles, intelligent virtual assistants, and recommendation systems, to name just a few applications. These advances are all powered by a broad family of techniques known as deep learning. Despite its observed successes, many basic questions about deep learning remain unanswered. To ensure predictable artificial-intelligence outcomes, is it possible to give useful formal guarantees for the performance of deep-learning algorithms? In order to deploy artificial intelligence on less powerful hardware (such as smartphones), is there a practical way to compress a massive deep-learning model into a smaller and more efficient model? Can deep-learning models be made provably robust against maliciously-crafted inputs? This project will search for rigorous answers to such questions in order to expand the theoretical foundations of deep learning. Integral to this project's success is the mentoring of graduate students. Innovations in education will furthermore broaden the community of researchers equipped with tools to solve problems at the intersection of computer science and mathematics. This project begins its development of rigorous algorithmic foundations for training neural networks by seeking useful upper bounds on the generalization error and time- and sample-complexity for supervised learning. However, lower bounds can serve as helpful guideposts by suggesting structural assumptions that are necessary for interesting algorithmic guarantees. For example, existing lower bounds rule out efficiently learning many simple concepts over high-dimensional Gaussian inputs. Hence, this project will explore the complexity of learning data labeled by deep neural networks with low-rank weight matrices over low-dimensional inputs. Additionally, this project will seek theoretically rigorous algorithms for compressing trained deep-neural-network models to much shallower approximations. Lower bounds against local or distribution-free approaches to the compression problem will also be developed to guide algorithmic intuition. Furthermore, this project will seek simple hypotheses under which gradient descent provably trains neural-network models that are susceptible to adversarial inputs. Understanding the weaknesses of existing training algorithms will guide the development of algorithms that are robust to adversarial inputs. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.