Title: Inventing Algorithms via Deep Learning
Abstract: Deep learning is a part of daily life, owing to its successes in computer vision and natural language processing.
In these applications, the success of the model-free deep learning approach can be attributed to a lack of (mathematical)
generative model. In yet other applications, the data is generated by a simple model and performance criterion
mathematically precise and training/test samples infinitely abundant, but the space of algorithmic choices is
enormous (example: chess). Deep learning has recently shown strong promise in these problems too (example: alphazero).
In this talk, we study two canonical problems of great scientific and engineering interest through the lens of deep learning.
The first is reliable communication over noisy media where we successfully revisit classical open problems in
information theory; we show that creatively trained and architected neural networks can beat state of the art
on the AWGN channel with noisy feedback by a 100 fold improvement in bit error rate.
The second is optimization and classification problems on graphs, where the key algorithmic challenge is scalable
performance to arbitrary sized graphs. Representing graphs as randomized nonlinear dynamical systems via
recurrent neural networks, we show that creative adversarial training allows one to train on small size graphs
and test on much larger sized graphs (100~1000x) with approximation ratios that rival state of the art
on a variety of optimization problems across the complexity theoretic hardness spectrum.
Apart from the obvious practical value, this study of mathematically precise problems sheds light on
the mysteries of deep learning methods: training example choices, architectural design decisions and
loss function/learning methodologies. Our (mostly) empirical research is conducted under the backdrop of
a theoretical research program of understanding gated neural networks (eg: attention networks, GRU, LSTM); we show the first provably (globally) consistent algorithms to recover the parameters of a
classical gated neural network architecture: mixture of experts (MoE).