Programme

Emma Horton  -- Genealogies of critical branching processes

Abstract: Branching processes are pertinent to understanding many different real world processes such as cell division, population growth and neutron transport. In particular, understanding their genealogical structures can prove useful for parameter estimation, Monte Carlo simulations and scaling limits. In this talk we discuss a decomposition of the branching process known as the many-to-few formula, which allows one to understand the behaviour of a branching process in terms of a weighted subtree. I will then give two applications of this decomposition to demonstrate its use in understanding the genealogical structure of the branching process. 

Jim Dai - The BAR-approach for continuous-time stochastic systems

Abstract: I will survey the basic adjoint relationship (BAR)-approach
that has been advanced recently by Braverman, Dai, and Miyazawa (2017,
2024) for steady-state analysis of continuous-time stochastic systems.
In such a system, the distributions of stochastic primitives (e.g,
service times) are assumed to be general, not necessarily exponential
or phase-type. I will illustrate that the BAR-approach is an effective
too to prove (1) the state space collapse in a join-shortest-queue
system, (2) asymptotic steady-state independence for multiclass
queueing networks in multi-scale heavy traffic.

Ruth Williams - Stochastic Analysis of Chemical Reaction Networks with Applications to Epigenetic Cell Memory

Abstract: Epigenetic cell memory, the inheritance of gene expression patterns across subsequent cell divisions, is a critical property of multi-cellular organisms. Simulation studies have shown how stochastic dynamics and time-scale differences between establishment and erasure processes in chromatin modifications can have a critical effect on epigenetic cell memory.

In this talk, we describe a mathematical framework to rigorously validate and extend beyond these computational findings. Viewing ourstochasticmodel of a chromatin modification circuit as a singularly perturbed, finite state, continuous time Markov chain, we extend beyond existing theory in order to characterize the leading coefficients in the series expansions of stationary distributions and mean first passage times. In particular, we characterize the limiting stationary distribution in terms of a reduced Markov chain, provide an algorithm to determine the orders of the poles of mean first passage times, and describe a comparison theorem which can be used to explore how changing erasure rates affects system behavior. These theoretical tools not only allow us to set a rigorous mathematical basis for the computational findings of prior work, highlighting the effect of chromatin modification dynamics on epigenetic cell memory, but they can also be applied to other singularly perturbed Markov chains especially those associated with chemical reaction networks.

Based on joint work with Simone Bruno, Felipe Campos, Yi Fu and Domitilla Del Vecchio.

Session organized and chaired by Stefan Stojanovic

Peter Taylor - A strategy for constructing tractable models of malarial superinfection

Abstract: Superinfection, that is the concurrent presentation of separately-acquired infections, is an important feature of several infectious diseases. A particularly pertinent example is malaria. Population-level compartment models allowing for malarial superinfection may take the form of countably infinite systems of ordinary differential equations, which poses complications for simulation and analysis. Here, we present a novel strategy for deriving tractable systems of integrodifferential equations for epidemic models of malarial superinfection. Our approach is predicated on the fact that we can characterise the within-host dynamics using a network of infinite-server queues with a time dependent batch arrival rate that is a function of the intensity of mosquito-to-human transmission. We shall illustrate this approach in the context of the classical model of superinfection for Plasmodium falciparum malaria. By observing that the classical deterministic compartment model has the same form as the Kolmogorov forward differential equations for an infinite server queue, we recover a reduced system of integro-differential equations governing the intensity of mosquito-to-human transmission. The resultant systems of IDEs are amenable to numerical solution, allowing us to explore the transient, population-level dynamics of superinfection without resorting to approximation. We can also derive threshold parameters governing the existence of non-trivial (endemic) equilibria. This approach can be generalised to account for additional biological complexity, in particular the accrual of the hypnozoite reservoir — a bank of dormant liver-stage parasites that can activate to yield repeated relapses of Plasmodium vivax malaria. It can also be used in models that take into account demography, drug treatment and the development of immunity.

Mariana Olvera-Cravioto - Local limits and preferential attachment graphs

Abstract: This talk is meant to provide an overview of local weak convergence techniques for a large class of directed random graphs, including static models such as the Erdos-Renyi, Chung-Lu, stochastic block model, and configuration models, as well as dynamic models such as the collapsed branching process and the directed preferential attachment graph. We explain how local limits can be used to study important structural graph properties, including centrality measures such as the PageRank distribution. We further use the insights obtained from our analysis of centrality measures to explain how static models and evolving models differ in how large degree vertices are distributed within the graph and how they shape their neighborhoods. In particular, we show that the empirically accepted “power-law hypothesis” on scale-free graphs, which states that the PageRank distribution follows a power-law with the same tail index as the in-degree distribution, holds in most static models but not in the dynamic models we study.

This is joint work with: Sayan Banerjee and Prabhanka Deka.

Jiaming Xu - Recent advances on random graph matching problems

Abstract: Random graph matching, the problem of recovering vertex correspondences between two random graphs through their correlated edge connections, is a pivotal challenge with extensive applications. This interdisciplinary problem holds great importance in areas such as network privacy, computational biology, computer vision, and natural language processing, while also raising intricate theoretical questions at the intersection of algorithms, computational complexity, and information theory. Remarkable strides have recently been made in the study of matching correlated Erdős–Rényi graphs. In this talk, the speaker will overview these recent developments,

highlight key breakthroughs, and point out important directions for future investigation.

Clara Stegehuis - Optimal structures in random networks

Abstract: Subgraphs contain important information about network structures and their functions. But where can we find these subgraphs in random graphs? And how likely are we to find a much larger amount of them than expected? Interestingly, these question leads to mixed integer optimization problems on random graphs that identify the dominant structure of any given subgraph. The optimizer describes the degrees and the spatial locations of the vertices that together create the most likely subgraph. On the popular hyperbolic random graph model, our optimization problem shows the trade-off between geometry and popularity: some subgraphs are most likely formed by vertices that are close by, whereas others are most likely formed by vertices of high degree. This insight makes it possible to create optimal statistics that detect the presence of an underlying spatial structure.

Adam Wierman - Learning Augmented Algorithms for MDPs

Abstract: Making use of modern black-box AI tools such as deep reinforcement learning is potentially transformational for sustainable systems such as data centers, electric vehicles, and the electricity grid. However, such machine-learned algorithms typically do not have formal guarantees on their worst-case performance, stability, or safety. So, while their performance may improve upon traditional approaches in “typical” cases, they may perform arbitrarily worse in scenarios where the training examples are not representative due to, e.g., distribution shift. Thus, a challenging open question emerges: Is it possible to provide guarantees that allow black-box AI tools to be used in safety-critical applications? In this talk, I will provide an overview of an emerging area studying learning-augmented algorithms that seeks to answer this question in the affirmative. I will survey recent results in the area, focusing on online optimization and MDPs, and then describe applications of these results to the design of sustainable data centers and electric vehicle charging.

Title: Further Adventures of the Compensated Coupling

Abstract: Around five years ago, my collaborators and I introduced the compensated coupling: a simple paradigm for designing sequential decision-making policies based on sample-pathwise comparisons to a hindsight benchmark. Our approach generalized many standard results used in studying MDPs and reinforcement learning, but also gives new policies which are much simpler and more effective than existing heuristics for a large class of widely-studied problems -- including online packing and covering, dynamic pricing, generalized assignment, online bin packing, fair allocation, bandits with knapsacks, and many others. In this talk, I will provide a brief overview of the main technique, and then try to illustrate some newer extensions that illustrate the power of the approach: 1. how to achieve constant regret (i.e., additive loss compared to a hindsight benchmark which is independent of state-space size) for a wide range of problems, and under minimal conditions, 2. how we can use it to derive tradeoff laws between different objectives, and 3. how we can incorporate side information and historical data, and achieve constant regret with as little as a single data trace.

Cynthia Rush - Characterizing Model Selection Performance of Sorted L1 Regularization Using Approximate Message Passing

Abstract: Sorted L1 regularization has been incorporated into many methods for solving high- dimensional statistical estimation problems, including the SLOPE estimator in linear regression. In this talk, we study how this regularization technique improves variable selection by characterizing the optimal SLOPE trade-off between the false discovery proportion (FDP) and true positive proportion (TPP) or, equivalently, between measures of type I and type II error. Additionally, we show that on any problem instance, SLOPE with a certain simplified two-level regularization sequence outperforms the Lasso, in the sense of having an asymptotically smaller FDP, larger TPP and smaller L2 estimation risk simultaneously. We discuss how this simplified version of SLOPE with a two-level regularization sequence, which we refer to as 2-level SLOPE, performs nearly as well as SLOPE in its full generality and has far fewer tuning parameters. Our proofs are based on a novel technique that reduces a variational calculus problem to a class of infinite-dimensional convex optimization problems and a recent results from approximate message passing (AMP) theory. With SLOPE being a particular example, we discuss these results in the context of a general program for systematically deriving exact expressions for the asymptotic risk of estimators that are solutions to a broad class of convex optimization problems via AMP. Collaborators on this work include Zhiqi Bu, Jason Klusowski, and Weijie Su (https://arxiv.org/abs/1907.07502 and https://arxiv.org/abs/2105.13302), Oliver Feng, Ramji Venkataramanan, and Richard Samworth (https://arxiv.org/abs/2105.02180) and Ruijia Wu.

Amy Ward - Integrating Machine Learning and Queueing to Enhance Decision-Making: An Application in Criminal Justice

Joint work with: Bingxuan Li, Pengyi Shi, Zhiqiang Zhang

Abstract: Recidivism, or the repetition of criminal acts after being punished, is a significant problem in the U.S., where over 70% of prisoners reoffend. Incarceration diversion programs are one attempt to combat recidivism, by focusing on societal reintegration rather than incarceration. Machine learning (ML) algorithms play an important role in program admission decisions, by assigning a risk score, that helps to quantify the trade-off between the potential benefit of the program to the individual, and the risk that the individual may reoffend while completing program requirements. Since incarceration diversion programs often have limited capacity, admission decisions are made by prioritizing individuals based on this tradeoff. However, ML classifications are imperfect, resulting in potentially incorrect admission decisions. Furthermore, algorithmic bias in the machine learning model may lead to unfairness with respect to which subpopulations have the opportunity to benefit from the incarceration diversion programs. Errors in decision making and unfairness are especially worrying in this environment, as these decisions affect both the life path of an individual and society’s exposure to offenders.

Motivated by the incarceration diversion program setting, we formulate an admission control problem in a queueing model with heterogeneous classes, in which an underlying ML algorithm estimates each arriving individual’s class. The queueing model is a loss model with reneging from service. The loss feature replicates the fact that individuals admitted to an incarceration diversion program should begin in the program immediately. The reneging from service feature is unique compared to most reneging models in the literature and is motivated by the fact that an individual in the incarceration diversion program may either be successfully served (complete the program) or renege (recidivate while in the program). Our main theoretical results pertain to the performance of a priority score policy under imperfect estimation, and our main computational results focus on calibrating a simulation model to underlying program data.

Maria Deijfen - Mean field stable matching

Abstract: Consider a situation where a number of objects acting to maximize their own satisfaction are to be matched. Each object ranks the other objects and a matching is then said to be stable if there is no pair of objects that would prefer to be matched to each other rather than their current partners. We consider stable matching of the vertices in the complete graph based on i.i.d. exponential edge costs. Our results concern the total cost of the matching, the typical cost and rank of an edge in the matching, and the sensitivity of the matching and the matching cost to small perturbations of the underlying edge costs.