Optimisation - Archived material for the year 2019-2020

2019-2020
Lecturer(s): 
Prof. Raphael Hauser
Course Term: 
Hilary
Course Overview: 

Optimisation problems occur naturally in mathematical models of finance, data analysis and machine learning. This course covers a few of the typical problem formulations in that appear in large scaled modern models and then focuses specifically on gradient based algorithms and their convergence analysis.

Learning Outcomes: 

Course participants learn how to model applied problems as optimisation problems and gain an understanding of the geometric underpinnings of gradient based algorithms for the solution of such problems. Many variants of such algorithms have been published in the modern literature. Although we will not be able to cover the literature comprehensively, the algorithms we do study introduce the basic tools that will enable participants to understand the strengths, weaknesses and limitations of other algorithms when they expand their knowledge through further independent reading.

Course Syllabus: 

Lecture 1: Modelling: least squares, matrix completion, sparse inverse covariance estimation, sparse principal components, sparse plus low rank matrix decomposition, support vector machines.

Lecture 2: Further modelling: logistic regression, deep learning. Mathematical preliminaries: Global and local optimisers, convexity, subgradients, optimality conditions.

Lecture 3: Preliminaries: Proximal operators, convergence rates.

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

Lecture 5: Prox-gradient methods.

Lecture 6: Accelerating gradient methods: heavy ball method, Nesterov acceleration.

Lecture 7: Oracle complexity and the stochastic gradient descent algorithm.

Lecture 8: Variance reduced stochastic gradient descent.

Reading List: 

- S.J.Wright. “Optimization Algorithms for Data Analysis”, http://www.optimization-online.org/DB_FILE/2016/12/5748.pdf

- L. Bottou, F.E. Curtis, and J. Nocedal. “Optimization methods for large-scale machine learning. SIAM Review, 59(1): 65-98, 2017.

- Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1): 8194-8244, 2017.

Please note that e-book versions of many books in the reading lists can be found on SOLO and ORLO.