Instructor: Anton Braverman (Northwestern University)
Time: 11:30am–1pm US ET
Dates: starts Tue, Jul 29, then each Mon & Thu from Jul 31–Aug 28 (inclusive)
Zoom link: https://cornell.zoom.us/j/97764140425?pwd=IsaobqTCjbrY09X8QTQlgFLIieaods.1
This summer school is now over. The complete playlist of lecture recordings is available on YouTube!
This summer, as a pilot program, SNAPP is running a virtual summer school. This is a virtual lecture series held on Zoom with the aim of teaching an advanced but broadly applicable topic to researchers in applied probability.
For the inaugural summer school, we are delighted to have Anton Braverman (Northwestern University) teach a 10-lecture course about Stein's method for queueing approximations. Lectures will be recorded and posted to the SNAPP YouTube channel.
If you're planning to attend, please fill out the brief interest form. See below (and this spreadsheet) for a schedule and course description, and sign up for the SNAPP mailing list to stay tuned for updates.
Lectures will be held virtually over Zoom at 11:30am–1pm ET, starting Tuesday, July 29 and continuing on Mondays and Thursdays until August 28:
Thursday, July 31 [video] [notes] [supplemental notes]
See also the lecture-by-lecture topic schedule here.
The generator comparison approach of Stein’s method is a framework used to compare the stationary distributions of any two Markov processes and derive bounds on their distance under some integral probability metric. Notably, the approach does not require coupling the two distributions.
Roughly ten years ago, the generator approach was introduced to queueing theory and, specifically, to the area of fluid and diffusion approximations of queueing models. The ability to compare the steady-state distribution of the fluid/diffusion approximation to the original (often intractable) queueing model spurred a variety of interesting research questions. The past ten years have provided answers to many of these questions. Some highlights:
We now have a theory to derive rates of convergence of the original queueing model to its diffusion/fluid approximation
We now know that diffusion/fluid models can perform well universally, across multiple parameter regimes (as opposed to heavy-traffic limit theorems which assume that the model primitives converge to one particular limit; e.g., the Halfin-Whitt regime).
We have learned of higher-order approximations whose approximation error goes to zero an order of magnitude faster than “classical” approximations
The generator approach has been extended to the setting of dynamic control (MDPs) where it quantifies the error of approximating an MDP by the continuous Brownian control problem, resulting in an approximate DP state-space aggregation algorithm.
The generator approach has been extended to “non-Markovian” models; e.g., queueing models with general inter-arrival and service time distributions.
The purpose of this course is to disseminate the developments in the generator approach (with a focus on queueing) over the past ten years. No prior knowledge is assumed. We begin with the basic generator approach for a simple one-dimensional birth-death process, and then add complexity by considering multidimensional CTMCs and, eventually, piecewise-deterministic Markov processes where jumps are driven by general clocks.
At the end of the course students will be familiar with using the generator approach and will be able to apply it to their own research. They will also know the state-of-the-art of the theory, including some open problems.
The target audience is graduate students, postdocs, and faculty working in applied probability, but there are relatively few specific prerequieites. Participants should be familiar with CTMCs (positive recurrence, stationary distributions). Familiarity with Ito’s lemma is a plus, but it will be reviewed at the start of the course.
Preliminaries: Ito’s lemma, generators of CTMCs and diffusion, and the drift method.
A simple one-dimensional example: the M/M/∞ queue.
High-order diffusion approximations.
The prelimit generator comparison approach.
Multi-dimensional examples: state-space collapse and gradient (Stein factor) bounds.
Beyond CTMCs: applications to models with generally-distributed jump clocks.
You can view a lecture-by-lecture topic schedule here. Time permitting, additional topics may include Stein’s method for mean-field approximations and Stein’s method for MDPs/dynamic control.
Anton Braverman is an associate professor who joined the Operations group at Kellogg in 2017. He completed his PhD in Operations Research from Cornell University, and holds a Bachelor’s degree in Mathematics and Statistics from the University of Toronto. Anton’s research is focused on stochastic modelling and applied probability. Some application domains of interest include ridesharing services and revenue management.