Understanding Deep Learning

Introduction

While extremely successful, deep learning (DL) still lacks a solid theoretical foundation.

Recent Achievements

In the last 5 years, the PI focused almost entirely on DL theory, yielding a strong publication record with:

1. 7 papers at NeurIPS (the leading ML conference), including:
   • 2 spotlights (top 3% of submitted papers)
   • 1 oral (top 1%)
2. 2 papers at ICLR (the leading DL conference)
3. 1 paper at COLT (the leading ML theory conference)

These results are amongst the first that break a 20-year hiatus in NN theory, thereby giving some hope for a solid deep learning theory. This includes:

1. The first poly-time learnability result for a non-trivial function class by SGD on NN.
2. The first such result with near optimal rate.
3. New methodology to bound the sample complexity of NN, establishing the first sample complexity bound that is sublinear in the number of parameters, under norm constraints that are valid in practice.
4. An explanation for the phenomena of adversarial examples.

Future Plans

We plan to go far beyond these and other results, and to build a coherent theory for DL, addressing all three pillars of learning theory:

Optimization

We plan to investigate the success of SGD in finding a good model, arguably the greatest mystery of modern deep learning. Specifically, our goal is to understand what models are learnable by SGD on neural networks. To this end, we plan to develop a new class of models that can potentially lead to new deep learning algorithms, with a solid theory behind them.

Statistical Complexity

We plan to crack the second great mystery of modern deep learning, which is their ability to generalize with fewer examples than parameters. Our plan is to investigate the sample complexity of classes of neural networks that are defined by bounds on the weights’ magnitude.

Representation

We plan to investigate functions that can be realized by NN. This includes classical questions such as the benefits of depth, as well as more modern aspects such as adversarial examples.