  "Deep Learning"/"Deep Neural Nets" is a technological marvel that is now
increasingly deployed at the cutting-edge of artificial intelligence tasks.
This dramatic success of deep learning in the last few years has been hinged on
an enormous amount of heuristics and it has turned out to be a serious
mathematical challenge to be able to rigorously explain them. In this thesis,
submitted to the Department of Applied Mathematics and Statistics, Johns
Hopkins University we take several steps towards building strong theoretical
foundations for these new paradigms of deep-learning. In chapter 2 we show new
circuit complexity theorems for deep neural functions and prove classification
theorems about these function spaces which in turn lead to exact algorithms for
empirical risk minimization for depth 2 ReLU nets. We also motivate a measure
of complexity of neural functions to constructively establish the existence of
high-complexity neural functions. In chapter 3 we give the first algorithm
which can train a ReLU gate in the realizable setting in linear time in an
almost distribution free set up. In chapter 4 we give rigorous proofs towards
explaining the phenomenon of autoencoders being able to do sparse-coding. In
chapter 5 we give the first-of-its-kind proofs of convergence for stochastic
and deterministic versions of the widely used adaptive gradient deep-learning
algorithms, RMSProp and ADAM. This chapter also includes a detailed empirical
study on autoencoders of the hyper-parameter values at which modern algorithms
have a significant advantage over classical acceleration based methods. In the
last chapter 6 we give new and improved PAC-Bayesian bounds for the risk of
stochastic neural nets. This chapter also includes an experimental
investigation revealing new geometric properties of the paths in weight space
that are traced out by the net during the training.
