On the recommendation of a friend, I've ordered a book today:
Understanding Machine Learning: From Theory to Algorithms, 1st Edition, Cambridge University Press
by Shai Shalev-Shwartz and Shai Ben-David
Also, I've ordered this one too...
Foundations of Machine Learning (Adaptive Computation and Machine Learning series, MIT Press)
by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar