Anirbit

"Deep Learning"/"Deep Neural Nets" are a technological marvel and they are being increasingly deployed at the cutting-edge of artificial intelligence tasks. This ongoing revolution can be said to have been ignited by the iconic 2012 paper from the University of Toronto titled ``ImageNet Classification with Deep Convolutional Neural Networks'' by Alex Krizhevsky, Ilya Sutskever and Geoffrey E. Hinton. This showed that deep nets can be used to classify images into meaningful categories with almost human-like accuracies! As of 2019 this approach continues to produce unprecedented performance for an ever widening variety of novel purposes ranging from playing chess to self-driving cars to  experimental astrophysics and high-energy physics. 

As theoreticians we might as well look beyond immediate practical implications and also focus on certain mind-boggling experiments like this one running live on the browser - which for all we know might also have concrete uses in the long run!  In here every time we refresh the page we are being shown a seemingly human photograph (which sometimes might have minor defects), just that this photograph is completely artificially generated by a neural network! :-o  The picture one sees on every refreshing of the page is essentially a sample from a distribution generated by pushing forward the standard normal distribution via a certain neural function. In a sense this person is purely the net's imagination and he/she does not actually exist! So how did the net learn to ``draw" such realistic human faces? This mechanism is still highly ill-understood and the best efforts yet by the community (see section 3.4 here of Sanjeev Arora's talk at the International Congress of Mathematicians) hint towards needing to go into very deep waters than ever before - possibly into entirely uncharted territories in high-dimensional probability.

These plethora of astonishing new successes of deep neural nets in the last few years have turned out to be extremely challenging to be mathematically rigorously explainable. Study of neural networks is a very rapidly evolving field and there is an urgent need for mathematically coherent and yet accessible introductions to it. Thus motivated I wrote this exposition on neural nets aimed at high-school students and beginning undergrads. My essay was picked up by this international consortium of scientists who  have created this translation of my article into Bangla, my mother-tongue

• • In our ICLR 2018 paper ``Understanding Deep Neural Networks with Rectified Linear Units" (with Amitabh Basu, Raman Arora and Poorya Mianjy, all that JHU) we observed that the gauge function of a rare kind of polytopes called ``zonotopes" are exactly representable by ReLU nets. This we used to construct neural functions with some of the highest known number of affine pieces for certain architectural regimes. We have also given constructive proofs of existence of continuum of neural functions which are super-exponentially (in the smaller depth) hard in size to represent for quadratically smaller depths. We also show characterizations like that of every continuous piecewise linear function from R^n -> R being a O(log (n)) depth ReLU net representable. We leverage our architecture specific descriptions of the corresponding neural function space to get complexity theoretic insights into exact empirical risk minimization over them. 

  • In a subsequent paper  (with Amitabh Basu) we have built upon recent developments in the theory of sign-rank of Boolean functions and about random restriction techniques for LTF gates to show various depth-hierarchy theorems for ReLU nets over Boolean functions. 

For the forseeable future this is going to be a predominant part of my research program. One can see here a preliminary experimental study in this theme that my intern Pulkit, from IIT-Kanpur, published at a NeuRIPS workshop. After this, Pulkit, me and Sayar Karmakar (at UFlorida) have done a lot more theoretical work on this theme and details shall be coming in here over the next few months. Keep watching this space :)  

• In this paper with Soham Dan (UPenn) and Phanideep Gampa we have tried to redefine and make mathematically precise an idea originally from Weijie Su and Hangfeng He about they called local elasticity of neural nets. One can read a summary of this work at these slides that I presented at a couple of recent talks like at Google Mountain View and CMStatistics 2020. 

• Most recently with Sayar Karmakar we have done detailed experimental investigations into the emergence of heavy-tailed behaviour in the stochastic learning algorithms for even the simplest of neural nets. This has led to a number of surprising conjectures and we shall soon be making our experiments public. 

(the current draft of the above upcoming paper is available on request) 

• In this work (link), a part of which was presented at the DeepMath 2020 (in collaboration with Jiayao Zhang) we showed how one could choose distributions for the stochastic gradient so as to get RMSProp to converge at sub-linear rates for smooth non-convex functions and while not using any time-varying hyper-parameters and not modifying the standard pseudocode that is implemented in softwares like TensorFlow.  

• • We explore iterative non-gradient algorithms for neural training in this pair of recently released papers, 

Part 1 : https://arxiv.org/abs/2005.01699 

(with Sayar Karmakar and Ramachandran Muthukumar) 

(A deterministic version of it was presented at DeepMath 2020)   

               Part 2 : https://arxiv.org/abs/2005.04211  (see here for the version that appeared in the Neural Networks journal)

(with Sayar Karmakar)

The question of provable training of neural nets is mathematically extremely challenging and vastly open. During 2020 - 2021 we investigated certain special cases at depth 2 and have given provable guarantees in regimes hitherto unexplored. Or results probe the particularly challenging trifecta of having finitely large nets, while not tying the data to any specific distribution and while having an adversarial attack. 

We give 2 kinds of results, 

• We give a simple stochastic algorithm that can train a ReLU  gate in the realizable setting in linear time with significantly milder conditions on the  data distribution than in previous results. Leveraging some additional distributional assumptions we also show near-optimal guarantees of training  a ReLU gate when an adversary is allowed to corrupt the true labels and we show that our guarantees degrade gracefully with the magnitude and the probability of the attack.  Further all these guarantees that we give above hold while simultaneously keeping track of the effect of mini-batching on the  algorithm - and we give experimental evidence as to how it seems to be tracking the S.G.D. dynamics which isnt yet provable! 

•  We exhibit a non-gradient stochastic iterative algorithm "Neuro-Tron" which shows how far the above ideas can be pushed to multi-gate scenarios. To the best of my knowledge this is probably the only example where for some kind of an adversarial setting - here for a label poisoning attack - a proof has been written for a finitely large neural net.  

• • In collaboration with Soham De (Deepmind, UK) and Enayat Ullah (JHU) have shown the first proofs of convergence of adaptive gradient algorithms like RMSProp and ADAM under any condition. Among other things this gives (a) the first moment based control on the stochastic gradient oracle which can get RMSProp to converge on smooth non-convex objectives at the same speed as SGD on convex objectives and (b) a proof of convergence for deterministic ADAM which naturally reveals a choice of step-size that has strong resemblance to the experimental heuristic called the ``bias correction term"! Thus we are led closer to explaining the mysteries of the most fundamental deep-learning algorithms. 

We have also demonstrated extensive experiments on autoencoders to identify a scheme of tuning of the ADAM's parameters (beyond the conventional ranges) which help it supersede other alternatives in neural training performance. 

Latest copy of this paper can be seen here  A preliminary version (arXiv:1807.06766) ``Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration" appeared in the ICML 2018 Workshop, Modern Trends in Nonconvex Optimization for Machine Learning.

• • In our ISIT 2018 paper ``Sparse Coding and Autoencoders", arXiv:1708.03735, (with  Akshay Rangamani, Amitabh Basu, Tejaswini Ganapathy (Salesforce, San Francisco), Ashish Arora, Trac D.Tran, Sang (Peter) Chin (BU)) we have shown that the landscape of autoencoders under the standard sparse-coding generative model, is asymptotically (in the sparse-code dimension) critical in a neighbourhood of the true dictionary. 

To the best of our knowledge this is among the very few proofs in literature about unsupervised learning using neural nets. 

This is the last chapter of my Ph.D. thesis (work done with Pushpendre Rastogi at JHU (now Amazon), Dan Roy and Jun Yang at the Vector Institute of Artificial Intelligence , Department of Statistics at UToronto). A preliminary version of this work appeared at the ICML 2019 Workshop, ``Understanding and Improving Generalization in Deep Learning" 

In here we have derived a new PAC-Bayesian bound for stochastic risk of neural nets i.e the expected population risk (over the data distribution) of a neural net which is in turn being sampled from a distribution over nets. Natural sources of such distributions are the ones induced by the output of any stochastic algorithm optimizing over the neural function space. This bound of ours is capable of leveraging fine-grained geometric data about the training algorithm. We can empirically show that our bounds supersede existing theoretical PAC-Bayesian neural risk bounds in not just tightness of the numerical value of the derived bound but also in giving better/slower rates of dependencies on the architectural parameters like width and depth of the net. 

These risk bound proofs at their core rely on our new theorems constructing large families of noise distributions to which the nets can be provably resilient to. This question of provable resilience of neural nets to noise distributions is intimately connected to the question of compressibility of nets - and this is a theme that we intend to explore further. 

Also importantly this work includes in its Apppendix a re-derivation of the first neural PAC-Bayes bound by Neyshabur-Bhojanapalli-Srebro. We believe that our careful re-derivation not only better elucidates the use of data-dependent priors than in their proof but also fixes many of the missing details there and thus makes it amenable for direct computational comparison against other contemporary bounds.