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

• Weekly Progress Report: 10%
• Assignments (2): 20%
• Initial draft for project: 20%
• Final project write-up: 50%

Topics:

• Real Analysis - Real numbers, topology, sequences, compact sets, continuity, differentiability, Riemann integraton.
• Probability Theory - Borel set, probability measure, expectation, convergence theorems, L-p spaces, Radon-Nikodyn theorem
• Stochastic process - Conditional expectation, stochastic processes, Kolmogorov extension theorem, martingales, martingale convergence theorems
• Dynamical systems - ODE local existence and uniqueness theorems, stability, linear dynamical systems.
• Stochastic approximation algorithms - Chapter 2, 3, 6 and 4 of Borkar’s textbook.

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