Reference Request: Computational Learning Theory
Another good introductory book is "Foundations of Machine Learning" by Mohri et al.: https://www.amazon.com/Foundations-Machine-Learning-Mehryar-Mohri/dp/0262039400/.  It has a large overlap with the Shai and Shai book, but also quite a bit of content that they don't cover.

There are also good books and surveys on more advanced or specialized topics:


Szepesvári and Lattimore have a nice book on bandits:
https://tor-lattimore.com/downloads/book/book.pdf
Cesa-Bianchi and Lugosi have a difficult but rewarding book on
learning and games: https://www.amazon.com/Prediction-Learning-Games-Nicolo-Cesa-Bianchi/dp/0521841089/
Schapire and Freund have a wonderful book on boosting: https://mitpress.mit.edu/books/boosting


There are more, but I hope this is a good start.