Machine learning studies automatic methods for identifying patterns in complex data and for making 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 compuationally 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 coures on machine learning, algorithms and complexity.


There are no hard pre-requisites for this course. However, if you have not taken a majority of the following courses at Oxford (or their equivalents elsewhere), you will find the course challenging.

Who should take this course?

This course is open to Part C students in Computer Science, Computer Science and Philosophy, Mathematics and Computer Science, and Mathematics and Philosophy, as well as MSc students in Computer Science and MFoCS students. This course covers fundamental algorithmic, computational and mathematical ideas behind machine learning. Students interested in practical applications should consider enrolling in the course on Deep Learning for NLP instead.

Note: Students who completed the Computational Learning Theory course in MT 2015 or 2014 are not permitted to register for this course.

Recommended Textbooks

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


There will be a take-home examination for this course. The exact dates for pick-up and hand-in may differ depending on which programme you are enrolled in, and will be announced during the middle of Hilary term.

Contact Information

Apart from lectures and classes, we have set up a Piazza forum. Please sign up here. You should use this forum to ask questions which could be answered by your classmates, TAs, and the lecturer. Should you so wish, you can also post to this forum anonymously. You may also send private messages to the lecturer and teaching staff, though we recommend that you use this option sparingly.

If your question is personal in nature, you should contact the lecturer and/or your academic superviser/adviser directly via email. Please allow at least 48 hours for an email response.

It can be challenging for the lecturer to guage how smoothly the course is progressing. Your comments, suggestions and feedback are always welcome. If you would like to remain anonymous while doing so, feel free to use an anonymous emailer such as this one. In addition, please do not forget to fill out the official feedback forms at the end of the term.