The theoretical foundations of machine learning have a double nature: statistical and game-theoretic. In this course we take advantage of both paradigms to introduce and investigate a number of basic topics, including mistake bounds and risk bounds, empirical risk minimization, online linear optimization, compression bounds, overfitting and regularization. The goal of the course is to provide a sound mathematical framework within which one can investigate basic questions in learning theory, such as the dependence of the predictive performance of a model on the complexity of the model class and on the amount of training information.