Course: B6.2 Optimisation for Data Science (2024-25)

Lecturer: Profile: Coralia Cartis

Course information

General Prerequisites:

Basic linear algebra (such as eigenvalues and eigenvectors of real matrices), multivariate real analysis (such as norms, inner products, continuity, differentiability), multivariable calculus (such as Taylor expansions, multivariate differentiation, gradients), basic probability and statistics. All these notions are covered in Prelims Linear Algebra, Analysis, Calculus (Intro and Multivariate), Probability and Statistics. Part A Numerical Analysis is recommended but not essential.

Course Term: Hilary

Course Lecture Information: 16 lectures

Course Weight: 1

Course Level: H

Assessment Type: Written Examination

Course Overview:

Optimisation problems occur naturally in statistics, data analysis, machine learning, and in signal and information processing. Their efficient solution is, for example, the cornerstone of successfully training machine learning models, principal component analysis, matrix completion, and many more. This course covers a few of the typical problem formulations in that appear in such large scaled modern models and then focuses specifically on gradient-based algorithms (namely, deterministic and stochastic first-order methods) and their convergence and complexity analyses for (mainly) convex problems.

Learning Outcomes:

Course participants learn how to model applied problems as optimisation problems and gain an understanding of the underpinnings of gradient-based algorithms for the solution of such problems. While many variants of such algorithms have been published in the modern literature, this course will cover the key formulations and analyses on which state-of-the-art methods are based. The algorithms we study introduce the basic tools that will enable participants to understand the strengths and limitations of these and other algorithms more generally.

Course Synopsis:

Mathematical preliminaries: Global and local optimisers, convexity, gradients and subgradients, optimality conditions, convergence rates.

Steepest descent method and its convergence analysis in the general case, the convex case and the strongly convex case.

Modelling: least squares, matrix completion, sparse inverse covariance estimation, sparse principal components, sparse plus low rank matrix decomposition, support vector machines, logistic regression, deep learning.

Proximal operators and prox-gradient methods.

Accelerating gradient methods: heavy ball method and Nesterov acceleration.

Oracle complexity and the stochastic gradient descent algorithm.

The variance reduced stochastic gradient descent algorithm.

Dimensionality reduction techniques for large scale optimisation (Johnson-Lindenstrauss Lemma)

Data sketching: linear least squares and sums of functions (batch stochastic gradient)

Parameter sketching: Randomised coordinate descent first order methods and random subspace methods.

Section outline

Select section General

General

Collapse all Expand all
- Select activity Announcements
  
  Announcements Forum
- Select activity Reading List
  
  Reading List URL
- Select activity Discussion Forum
  
  Discussion Forum
- Select activity Additional Reading
  
  Additional Reading File
Select section Problem Sheets

Problem Sheets
- Select activity Problem Sheet 2
  
  Problem Sheet 2 Assignment
  
  Opened: Thursday, 6 February 2025, 12:00 AM
  
  Due: Friday, 7 February 2025, 12:00 AM
- Select activity Problem Sheet 1
  
  Problem Sheet 1 Assignment
  
  Opened: Saturday, 25 January 2025, 12:00 AM
- Select activity Problem Sheet 3
  
  Problem Sheet 3 Assignment
  
  Opened: Friday, 21 February 2025, 12:00 AM
  
  Due: Friday, 28 February 2025, 12:00 AM
- Select activity Problem Sheet 4
  
  Problem Sheet 4 Assignment
  
  Opened: Thursday, 27 February 2025, 12:00 AM
  
  Due: Thursday, 6 March 2025, 12:00 AM
Select section Course Materials

Course Materials
- Select activity Old Lecture Notes
  
  Old Lecture Notes Folder
  
  Old Lecture notes with Latex source code. Disclaimer: these notes provide an overview of all the material in one place, but they may contain typos that we are fixing in the lecture slides, as the course progresses. At the end of the course we will post updated lecture notes with fixed typos, if required. The lecture slides contain all the lecture materials in their most up-to-date form.
- Select activity Lecture Slides
  
  Lecture Slides Folder
- Select activity Lecture Slides - UPDATED/CORRECTED
  
  Lecture Slides - UPDATED/CORRECTED Folder
- Select activity Exam Preparation Materials
  
  Exam Preparation Materials Folder
Select section Videos

Videos
- Select activity Last Year's Panopto Recordings
  
  Last Year's Panopto Recordings Folder
  
  https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3Dd0e45590-75c1-48e1-bfbf-ae1601012ce1%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3D5ee2e5f3-7769-4f4e-bf95-ae1601012d3a%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3D5fc62a2a-6ed4-4fad-a56f-ae1601017362%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3D8e795c1b-c7fe-4bb5-920c-ae1601012d4f%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3D197d00d3-8a58-4077-854a-ae1601017411%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3D19453d24-a26a-4248-9c5a-ae1601012d66%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3Db0f90c1c-f415-4fba-bf35-ae16010173b8%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3Dfa691284-c06e-454d-9d0e-ae1601012d92%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3Dd7905c89-2197-48b5-85a1-ae1601017321%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3De26ae3a2-b0d4-41b8-ab5f-ae160101738e%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3D0b9e6334-80ea-4fbe-b54e-ae16010173f7%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3D712a7ad0-d536-44bc-bba5-ae1601017378%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3Da54d9a71-ca36-4a04-9af0-ae1601012daa%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3Df215947f-a157-4ee3-9302-ae1601012d7b%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3Dd7a94db6-45bd-482b-93dd-ae16010173db%3C%2Fa%3E%3C%2Fspan%3E%3Cbr%3E%3C%2Fp%3E%0A%3Cp%3E%3Cspan%20style%3D"font-size: 0.9375rem;">https://ox.cloud.panopto.eu/Panopto/Pages/Auth/Login.aspx?instance=moodle-maths&support=true&ReturnUrl=https%3A%2F%2Fox.cloud.panopto.eu%2FPanopto%2FPages%2FViewer.aspx%3Fid%3De6931e9e-615f-4c97-9df3-ae1601012dc0%3C%2Fa%3E%3C%2Fspan%3E%3C%2Fp%3E%3Cbr%3E%3Cp%3E%3C%2Fp%3E%3C%2Fdiv%3E

Select section Intercollegiate Classes

Intercollegiate Classes
- Select activity Class Signup
  
  Class Signup Class registration
  
  Registration start: Monday, 13 January 2025, 12:00 PM
  
  Registration end: Friday, 14 February 2025, 12:00 PM
- Select activity Class Tutor's Comments
  
  Class Tutor's Comments Assignment
  
  Class tutors will use this activity to provide overall feedback to students at the end of the course.
  
  Not available unless: You have signed up to a class

Main content blocks

Section outline

General

Problem Sheets

Course Materials

Videos

Intercollegiate Classes