Skip to main content

Advanced Machine Learning:  2016-2017



Schedule C1 (CS&P)Computer Science and Philosophy

Schedule C1Computer Science

Schedule C1Mathematics and Computer Science

Schedule CMSc in Advanced Computer Science

MSc in Mathematics and Foundations of Computer Science




Machine learning studies automatic methods for identifying patterns in complex data and for making accurate predictions based on past observations. In this course, we develop rigorous mathematical foundations of machine learning, in order to provide guarantees about the behaviour of learning algorithms and also to understand the inherent difficulty of learning problems.

The course will begin by providing a statistical and computational toolkit, such as generalisation guarantees, fundamental algorithms, and methods to analyse learning algorithms. We will cover questions such as when can we generalise well from limited amounts of data, how can we develop algorithms that are computationally efficient, and understand statistical and computational trade-offs in learning algorithms. We will also discuss new models designed to address relevant practical questions of the day, such as learning with limited memory, communication, privacy, and labelled and unlabelled data. In addition to core concepts from machine learning, we will make connections to principal ideas from information theory, game theory and optimisation.

This is an advanced course requiring a high level of mathematical maturity. It is expected that students will have taken prior courses on machine learning, algorithms, and complexity.

NB. There is no past paper for the 2016-17 Advanced Machine Learning course. Whilst you may refer to the 2015-16 Computational Theory exam in preparation, please note that the content and scope of the 2016-17 version will be different.


These are not hard pre-requisites. However, if you have not taken a majority of the following courses at Oxford (or equivalent elsewhere), you will find the course challenging.

  • Algorithms and Data Structures
  • Machine Learning
  • At least one of Probability and Computing, Computational Complexity, Foundations of Computer Science

If you have any doubt about your background, you are encouraged to discuss with the instructor before the beginning of term or as soon thereafter as possible. Extra lectures will cover some basic computer science background for mathematics students and basic inequalities from probability that we will encounter frequently.


  • (Background) Probability
  • (Background) Computational Complexity
  • PAC learning, sample complexity, computational complexity
  • Proper vs improper learning
  • Growth function, VC dimension, sample complexity lower bounds
  • Learning with membership queries, Angluin's algorithm
  • Boosting, weak learning, Adaboost, Margin Bounds
  • Learning in the presense of noise, SQ Learning, Agnostic Learning
  • Learning Parities with noise, Learning Juntas
  • Complexity-theoretic and cryptographic hardness of learning
  • Online learning, perceptron and winnow, attribute efficient learning
  • Learning from expert advice, multi-armed bandit problems
  • (Time permitting) Learning discrete distributions
  • (Time permitting) Privacy preserving learning, adaptive data analysis

Reading list

  • Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994
  • Mehryar Mohri, Afshin Rostamizadeh and Amit Talwar. Foundations of Machine Learning. MIT Press, 2012
  • Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.


Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.