2021 Edition

This course will run between Weeks 5-8 of Hilary Term and Weeks 1-4 of Trinity Term. Some of the text on the website may not make complete sense given the virtual edition of the course. Please make suitable substitutions. If you have enrolled in this course and/or expressed interest in being informed about lectures, then you should have received an email by now. If you have not received an email and wish to take this course formally for credit, please get in touch with the Academic Office in Computer Science. If you simply wish to be informed about the lecture links, then send an email to the course lecturer using your oxford email address.

About

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 concentration inequalities, 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 courses on algorithms and complexity. A formal course on Machine Learning is not required, however, students are more likely to appreciate the contents of the course if they have some familiarity with machine learning.

Pre-requisites

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 are likely to find the course very 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 Mathematics and the Foundations of Computer Science. This course covers fundamental algorithmic, computational and mathematical ideas behind machine learning. Part C students in Mathematics and Computer Science may also be interested in Algorithmic Foundations of Machine Learning and Theories of Deep Learning which will suitably complement material taught in this course. Students interested in practical applications should consider other more applied courses such as Machine Learning or Advanced Topics in Machine Learning.

Note 1: Past student feedback has suggested that this course can be both very challenging and rewarding. If you find yourself struggling after the first two weeks of lectures and the first problem sheet, you should seek advice from your academic superviser and consider other courses instead. While the pre-requisites for this course are set to be as minimal as possible, you will have to take the initiative and do extra reading to catch-up on any holes in your background knowledge.

Note 2: Anybody who holds a University of Oxford Bod Card is welcome to attend lectures and view the materials posted on the website; there is no need to email the course lecturer to confirm. However, problem classes are only for officially registered students. Registration is only allowed for students in programs listed in the official handbook.

Textbooks

The first half of the course will closely follow the following introductory text. However, in order to deepen your understanding you will need to refer to additional texts and primary literature.

  • Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.

Additional Reading

  • 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.
  • Vladimir Vapnik. The nature of Statistical Learning Theory. Springer 1999.
  • Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer 2009.
  • Edwin T. Jaynes. Probability Theory: The logic of science. Cambridge University Press, 2003.
  • David Mackay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003.

Examination

There will be a take-home examination for this course. The exact dates and locations for pick-up and hand-in may differ depending on the programme you are enrolled in. You will be required to typeset your answers, preferably using LaTeX; using LaTeX to typset your solutions to problem sheets will help you practice for the exam. Where necessary, use of scanned pictures drawn by hand will be acceptable, but equations and text must be typed. Page limits on the examination guidelines will be strictly enforced, so you must practice writing succinctly. Questions about logistics of the examination should be addressed to the Academic Administrator of your programme rather than the lecturer.

Contact Information

For very brief questions, you can get in touch with the lecturer right after lectures. For more detailed questions please make use of the office hours announced on the course website.

We have set up a piazza forum. We hope you will make use of this to post questions, answer questions posted by your classmates, and generally make good use of this as a discussion forum. The lecturer will monitor the forum and answer questions as well. The option to post anonymously is enabled, should you wish to remain anonymous. Posting your question on this forum will allow other students to benefit from the answers.

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