Textbook on the *theory* of neural nets/ML algorithms? Every textbook I've seen so far describes ML algorithms and how to implement them.
Is there also a textbook that builds theorems and proofs for the behaviour of those algorithms? e.g. stating that under conditions $x,y,z$, gradient descent will always lead to $A,B,C$?
 A: Machine Learning: a Probabilistic Perspective by Kevin P. Murphy explains a lot of theory from a Bayesian perspective (I've only used it for logistic regression, but I thought it was quite good). The whole book is available online as a PDF by searching on Google. 
A: *

*Deep Learning (Adaptive Computation and Machine Learning series). 
This is written by Ian Goodfellow, Yoshua Bengio, Aaron Courville. As per the agreement of the author with MIT Press, you can read the legally free copy available on the browser in this website. www.deeplearningbook.org This is good for pure mathematics and theory of neural net and its different sub branches.


In addition to this, 


*

*The Elements of Statistical Learning: Data Mining, Inference, and Prediction is also a good book to build theoritical and mathematical foundation in traditional machine learning. This is written by Trevor Hastie, Robert Tibshirani and Jerome Friedman and  available for free by the authors at https://web.stanford.edu/~hastie/ElemStatLearn/
A: Foundations of Machine Learning, by Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar, is a 2012 book on machine learning theory.
Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David, is a similar 2014 book that's fairly well-known and targeted a little more introductory than Mohri/Rostamizadeh/Talwalkar, but still has lots of theory in it. It's freely available online.
Neural Network Learning: Theoretical Foundations, by Martin Anthony and Peter Bartlett, is a 1999 book about ML theory phrased as being about neural networks, but (to my impression not having read it) is mostly about ML theory in general.
These three books mostly take the predominant viewpoint of statistical learning theory. There is also an interesting point of view called computational learning theory, inspired more by computer science theory. I think the standard introductory book in this area is An Introduction to Computational Learning Theory, a 1994 book by Michael Kearns and Umesh Vazirani.
Another excellent and oft-recommended freely available book is Trevor Hastie, Robert Tibshirani, and Jerome Friedman's 2009 second edition of The Elements of Statistical Learning. It's perhaps a little less theoretical than the others, and more from the statistician's point of view than the machine learner's, but still has plenty of interest.
Also, if you care about gradient descent in particular, the standard reference is Convex Optimization by Stephen Boyd and Lieven Vandenberghe. This 2004 book is freely available online.
None of these books contain much on the modern theory of deep networks, if that's what you care about. (For example, most of the optimization theory will be about convex cases, which deep networks decidedly are not.) That's because this theory is very new; most of the results have come only in the last few years, and it's still very much being figured out. But, as an overview of the basic understanding of the field so far, any of them will set you up well to understand the papers in which that work is done (except perhaps Kearns/Vazirani, which focuses on different aspects of analysis that I'm not sure have been successfully applied to deep networks – yet).
A: Neural Network Design (Martin T. Hagan, Howard B. Demuth, Mark Hudson Beale, Orlando De Jesús) has some nice discussion of optimization in the context of neural nets. 
