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

MW, 9:30AM - 10:50PM

GSB 553

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

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

Martha will always come to class at 9 a.m. before class, for any questions about projects

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

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

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.

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

**Recommended supplements**

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

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

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