stochapprox

Schedule

For the current schedule

Announcements

13/01/2019: Lecture notes uploaded.

17/01/2019: Assignment 1 is available online. See schedule section.

7/02/2019: Assignment 2 is available online. See schedule section.

10/02/2019: Lecture notes on probability theory updated.

21/02/2019: Lecture notes on probability theory updated.

12/03/2019: Lecture notes on probability theory updated.

14/03/2019: Typo error in Theorem 12. Now fixed.

Syllabus for CMPUT 659

Time and Location

MW, 9:30AM - 10:50PM

GSB 553

Instructor

Martha White (whitem@ualberta.ca, Office: ATH 3-05)

Ajin Joseph (ajoseph@ualberta.ca, Office: ATH 2-05)

Office hours

Martha will always come to class at 9 a.m. before class, for any questions about projects. Additional office hours will be in ATH 3-05 from 1-2 on Wednesday.

Ajin: 3PM-4:30PM Monday-Friday

Course Objective

The course objective is to study the analysis of stochastic approximation algorithms from the viewpoint of dynamical systems.

Prerequisites

Linear Algebra, Probability

We will cover the needed background, from the beginning (real analysis, probability theory, stochastic processes) to make these topics accessible. The goal of the courses is Fundamentals of Stochastic Approximation Theory, rather than Advanced topics.

Textbooks

Stochastic Approximation: A Dynamical Systems Viewpoint, Vivek S. Borkar.

Recommended supplements

Stochastic Approximation and Recursive Algorithms and Applications. George Yin and Harold J. Kushner

Grading

Topics:

Lectures Topics to cover
Lecture 1 Introduction
Lecture 2 Real analysis: properties of real numbers, sequences, series, topology
Lecture 3 Real analysis: compact sets, continuous functions
Lecture 4 Real analysis: differentiation and integration
Lecture 5 Probability theory: probability and expectation
Lecture 6 Probability theory: convergence theorems
Lecture 7 Probability theory: conditional expectation
Lecture 8 Martingales
Lecture 9 Martingales
Lecture 10 Martingales
Lecture 11 Dynamical systems: existence and uniqueness of solutions
Lecture 12 Dynamical systems: stability, linear autonomous systems, gradient flow
Lecture 13 Stochastic approximation algorithms: chapter 2 of Borkar’s text
Lecture 14 Stochastic approximation algorithms: chapter 2 of Borkar’s text (cont)
Lecture 15 Stochastic approximation algorithms: chapter 3 of Borkar’s text
Lecture 16 Stochastic approximation algorithms: chapter 6 of Borkar’s text
Lecture 17 Stochastic approximation algorithms: chapter 4 of Borkar’s text