AI4OPT Seminar Series

Date: Thursday October 19, 2023

Time: Noon – 1:00 pm

Location: Love Manufacturing Building 183 (771 Ferst Dr NW, Atlanta, GA 30332)

Speaker: Neil Walton

Exponential Concentration of Stochastic Approximation with Non-vanishing Gradient

Abstract: We analyze the behavior of stochastic approximation algorithms where iterates, in expectation, make progress towards an objective at each step. When progress is proportional to the step size of the algorithm, we prove exponential concentration bounds. These tail-bounds contrast asymptotic normality results which are more frequently associated with stochastic approximation. The methods that we develop rely on a geometric ergodicity proof. This extends a result on Markov chains due to Hajek (1982) to the area of stochastic approximation algorithms. For Projected Stochastic Gradient Descent with a non-vanishing gradient, our results can be used to prove O(1/t) and linear convergence rates.

This is joint work with Kody Law and Shangda Yang. 

Bio: Neil Walton is a Professor in Operations Management at Durham University Business School. He received his undergraduate ('05), Masters ('06) and PhD ('10) in Mathematics at the University of Cambridge. His research is in applied probability and principally concerns the decentralized minimization of congestion in networks. He was a lecturer at University of Amsterdam where he held an NWO Veni Fellowship. He then moved to the University of Manchester where was a Reader in Mathematics. Neil has conducted research visits at Microsoft Research Cambridge, the Basque Centre for Mathematics and the Automatic Control Laboratory ETH Zurich. From 2017 to 2019 Neil was the head of probability and statistics group at the University of Manchester. Neil was a Fellow of the Alan Turing Institute and a guest lecturer at London Business School. He has an honorary position at the Manchester University NHS Foundation Trust. In Durham, he is Deputy Head of the Department of Management and Marketing. He is an associate editor at the journal Stochastic Systems. He is an area editor for stochastic models at Operations Research. He has won best papers awards at the ACM Sigmetrics conference and he was awarded the 2018 Erlang Prize by the Informs Applied Probability Society. 

To continue receiving all AI4OPT seminar announcements, please sign up to the mailing list at https://lists.isye.gatech.edu/mailman/listinfo/ai4opt-seminars

Videos of the past seminars can be seen on AI4OPT webpage at https://www.ai4opt.org/seminars/past-seminars