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).