SOLACE Team

Research Publications Seminar Links with industry People ☰
Research Publications Seminar Links with industry People

The SOLACE seminar is organized on Thursdays at 2pm at the Laboratory of Analysis and Architecture of Systems (LAAS).

Irrational Agents and the Power Grid

Sean Meyn – July 11, 2024 (Part II) – Slides

Preamble: For decades, power systems academics have proclaimed the need for real time prices to create a more efficient energy grid. The rationale is economics 101: proper price signals will lead to an efficient outcome. The mathematics is elegant — who doesn’t love Lagrange multipliers? However, application of this mathematics to electric power markets cannot be justified. This harsh assessment is based on a casual review of economics 101; in particular, the definition of efficiency. The conclusions of the power economist are correct if the population of rational power consuming agents have a concave utility function that models preference for electric power. However, in the real world, a typical user of electric power knows this is absurd. Look at any of the big power consumers at your own home: is your personal welfare a continuous function of the electric power consumed by each device? The absurdity is most clear for on-off loads such as a water heater, refrigerator, A/C or pool pump. The creation of a realistic economic model requires that we talk to humans. We might learn that a particular agent uses a refrigerator to keep food cold, and a water heater to help keep their family and their dishes clean. It follows that the electrical energy products of interest to this agent are complex functions of time, and only loosely related to electric power – the quantity associated with price signals, and in particular the price surges witnessed at ERCOT this year and in 2011. There is a longer history in the communications sector where surge pricing was promoted, and then dismissed based on similar reasoning.

To realize a reliable energy grid and to promote innovation, we must abandon the dogma of surge pricing.

The lecture consists of two parts:

  1. Realistic models of consumer preferences, and how these can be used to design distributed control strategies to obtain the needed services. This model also makes clear why the popular "prices to devices" paradigm will destabilize the power grid.
  2. A survey of distributed control techniques to obtain grid services from millions of electric loads.

This talk is based on two surveys:

Q-Learning is Now Stable—What About Actor-Critic?

Sean Meyn – July 11, 2024 (Part I) – Slides

This question was prompted by the discussion following my keynote lecture on June 21 at the workshop Reinforcement Learning for Stochastic Networks, held at ENSEEIHT.

Participants pointed out that my conclusions for Q-learning are precisely what would be anticipated by theory for the Actor-Critic method (for which there is a far firmer mathematical foundation than Q-learning). The lecture will review this theory and come to surprising conclusions. For one, I claim that theory for actor-critic as currently implemented is no stronger than theory for Q-learning! In contrast, the approach of Konda and Tsitsiklis, that is largely dismissed, is an instance of unbiased stochastic gradient descent.

My hope is that the new theory presented in my lecture of June 21 will open the doors to justification of popular versions of the actor-critic method.

This talk is based on Chapter 10 "Setting the Stage, Return of the Actors" from the book Control Systems and Reinforcement Learning.

Quasi-Stochastic Approximation: Algorithm Design Principles with Applications to Gradient Free Optimization/Extremum Seeking Control

Sean Meyn – June 27, 2024 – Slides

Many machine learning and optimization algorithms solve hidden root-finding problems through the magic of stochastic approximation (SA). Unfortunately, these algorithms are slow to converge: the optimal convergence rate for the mean squared error (MSE) is of order $O(n^{-1})$ at iteration $n$. Far faster convergence rates are possible by reconsidering the design of exploration signals used in these algorithms. In this lecture the focus is on quasi-stochastic approximation (QSA), in which a multi-dimensional clock process defines exploration. It is found that algorithms can be designed to achieve a MSE convergence rate approaching $O(n^{-4})$. Although the framework is entirely deterministic, this new theory leans heavily on concepts from the theory of Markov processes. Most critical is Poisson’s equation to transform the QSA equations into a mean flow with additive “noise” with attractive properties. Existence of solutions to Poisson’s equation is based on Baker’s Theorem from number theory—to the best of our knowledge, this is the first time this theorem has been applied to any topic in engineering! The theory is illustrated with applications to gradient free optimization in the form of Spall’s SPSA1 algorithm / extremum seeking control. It is found that these algorithms are not necessarily stable since they violate key assumptions in the SA literature. Resolutions are presented, and from this we obtain the astonishingly quick convergence rates. Joint research with Caio Lauand, current graduate student at UF.

Stochastic Approximation and Reinforcement Learning

Vivek Borkar – June 6 and 13, 2024 – Slides about Stochastic approximation – Slides about MDPs – Slides about RL

I shall give a quick overview of the `ODE' (for `Ordinary Differential Equations') approach to the analysis of stochastic approximation algorithms and then using (mostly) infinite horizon discounted cost Markov decision processes as the test case, give its applications to analyzing the convergence of various reinforcement learning algorithms.

Compressibility and Stochastic Stability of Monotone Markov Chain

Sergey Foss – May 30, 2024

For a stochastically monotone Markov chain taking values in a Polish space, we present a number of conditions for existence and for uniqueness of its stationary regime, as well as for closeness of its transient trajectories. In particular, we generalise a basic result by Bhattacharya and Majumdar (2007) where a certain form of mixing, or swap condition was assumed uniformly over the state space. We do not rely on continuity properties of transition probabilities.

This is a joint work with Michael Scheutzow (TU Berlin).

Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models

Sergey Foss – May 23, 2024

This is a short overview on results obtained by a group of researchers within the last 20 years. A survey paper has been placed in Arxiv.org in December 2023.

We consider directed random graphs, the prototype of which being the Barak-Erdős graph $\vec G(Z, p)$, and study the way that long (or heavy, if weights are present) paths grow. This is done by relating the graphs to certain particle systems that we call Infinite Bin Models (IBM). A number of limit theorems are shown. The goal of this paper is to present results along with techniques that have been used in this area. In the case of $\vec G(Z, p)$ the last passage percolation constant $C(p)$ is studied in great detail. It is shown that $C(p)$ is analytic for $p>0$, has an interesting asymptotic expansion at $p=1$ and that $C(p)/p$ converges to $e$ like $1/(\log p)^2$ as $p \to 0$. The paper includes the study of IBMs as models on their own as well as their connections to stochastic models of branching processes in continuous or discrete time with selection. Several proofs herein are new or simplified versions of published ones. Regenerative techniques are used where possible, exhibiting random sets of vertices over which the graphs regenerate. When edges have random weights we show how the last passage percolation constants behave and when central limit theorems exist. When the underlying vertex set is partially ordered, new phenomena occur, e.g., there are relations with last passage Brownian percolation. We also look at weights that may possibly take negative values and study in detail some special cases that require combinatorial/graph theoretic techniques that exhibit some interesting non-differentiability properties of the last passage percolation constant. We also explain how to approach the problem of estimation of last passage percolation constants by means of perfect simulation.

A practical guide to series expansion techniques in queueing theory

Dieter Fiems – April 4, 2024 – Slides

Series expansion techniques for Markov chains aim at expanding the steady-state solution of the Markov chain in terms of one of its parameters. Assuming that the chain is easy to solve for a particular value of this parameter, it is often the case that one can also find the higher order terms of the expansion around this value. This is not unsurprising, as the system of equations for the steady state solution are somewhat related to the equations for the terms in the series expansion. The series expansion technique therefore extends the solution for a single parameter value to solutions in a neighbourhood of this particular parameter value. The quintessential example where expansion techniques apply in queueing theory is the light-traffic approximation: this is a series expansion in the system load. The technique is not limited to light-traffic situations though. By means of some examples, we illustrate the possibilities of series expansion techniques, either as a purely numerical solution technique, or in combination with analytical results. We further discuss the importance of convergence acceleration techniques. Such techniques not only allow for accelerating convergence in the region of convergence of the series expansion, but also allow for extending the region of convergence which vastly widens the scope of the expansion technique.

Rational traffic advice for rush hour commuting

Dieter Fiems – March 28, 2024 – Slides

Most urban areas suffer from traffic congestion, with peaks during the morning and evening commutes. At an individual level, commuters optimise their travel times by opting for the shortest routes in time. Up till recently, these route choices where often confined to a couple of routes per commuter, and the route choice at any day was at most influenced by experience of past commutes at similar times, or by generic reports on the radio on the traffic conditions around major cities. Hence, the chosen routes were frequently suboptimal. In contrast, nowadays, online applications like Waze and Google maps can direct commuters to the routes which offer the least expected travel times, given the present traffic situation, such that commuters can rationally opt for the best route.

By selecting the shortest routes, these online applications hold the promise to better spread traffic over different routes, and thereby reduce congestion. However, if more commuters rely on these applications, there is also a real risk that these applications create congestion by routing too many commuters to a noncongested route as routing decisions only affect congestion levels at a later time. One can argue that the online application should be better at forecasting future congestion levels. However, these congestion problems are not created by a lack of information on the future congestion levels, but by the routing decisions taken by these online applications. As routing decisions are taken by the individual commuters, this is a distributed control problem which can be studied by game-theoretic methods.

In particular, our modelling effort draws upon traffic flow theory to relate traffic density and traffic flow at a macroscopic scale, on queueing theory to relate traffic intensity and density at this scale, and on the concept of the time-dependent Wardrop equilibrium to model the routing choice of individual commuters. As an application, we study how park-and-ride systems can mitigate congestion levels, and how time-dependent pricing can be used to obtain the socially optimal traffic mix.

Portfolio optimization under CV@R constraint with stochastic mirror descent

Manon Costa – March 21, 2024 – Slides

In this talk we consider the problem of optimal portfolio allocation with {CV@R penalty} when dealing with imperfectly simulated financial assets.

We use a Stochastic biased Mirror Descent to find optimal resource allocation for a portfolio whose underlying assets cannot be generated exactly and may only be approximated with a numerical scheme that satisfies suitable error bounds, under a risk management constraint.

We establish almost sure asymptotic properties as well as the rate of convergence for the averaged algorithm. We then focus on the optimal tuning of the overall procedure to obtain an optimized numerical cost. Our results are then illustrated numerically on simulated as well as real data sets.

Maximal displacement of a time-inhomogeneous N(T)-particles branching Brownian motion

Pascal Maillard – March 7, 2024 – Paper – Slides

The N-particles branching Brownian motion (N-BBM) is a branching Markov process which describes the evolution of a population of particles undergoing reproduction and selection. It shares many properties with the $N$-particles branching random walk (N-BRW), which itself is strongly related to physical $p$-spin models, or to Derrida's Continuous Random Energy Model (CREM). The N-BRW can also be seen as the realization of an optimization algorithm over hierarchical data, often called beam search. More precisely, the maximal displacement of the N-BRW (or N-BBM) can be seen as the output of the beam search algorithm, with N the « width » of the beam, that almost matches the computational complexity of the algorithm.

In this paper, we investigate the maximal displacement at time $T$ of an N-BBM, where $N=N(T)$ is picked arbitrarily depending on T and the diffusion of the process is inhomogeneous in time. We prove the existence of a phase transition in the second order of the maximal displacement when log N(T) is of order $T^{1/3}$. This can be interpreted as an "efficiency ceiling" in the output of the beam search algorithm, which extends previous results by Addario-Berry and Maillard regarding an algorithm hardness threshold for optimizing the Hamiltonian of the CREM.

Based on joint work with Alexandre Legrand.

Optimizing Decision-Making in Resource-Constrained Environments: The Lagrange Policy for Continuous Actions (LPCA) Algorithm

Francisco Robledo Relaño – February 29, 2024 – Slides

In this presentation, we introduce the Lagrange Policy for Continuous Actions (LPCA), a new reinforcement learning algorithm developed for restless multi-armed bandit problems with continuous action spaces. LPCA addresses the unique challenge of making decisions in environments where resources are limited and actions are continuous.

We will discuss the structure of LPCA, which combines neural network-based Q-value computation with a Lagrange multiplier approach. This combination allows for effective policy learning by decoupling the arms in multi-armed bandit problems under resource constraints.

The presentation will cover two variations of LPCA: LPCA-DE, which uses differential evolution for global optimization, and LPCA-Greedy, which selects actions incrementally based on the gradients of Q-values. We will present a comparative analysis of LPCA against the DDPG algorithm enhanced with OptLayer, showcasing LPCA's effectiveness in resource allocation and reward maximization.

Scaling Limits of Graph Laplacians

Ernesto Garcia Ciganda – February 1, 2024 – Slides

In this talk, I will present ongoing joint work with Vittorio Puricelli and Matthieu Jonckheere. We aim to characterize the limit of the 'generalized graph Laplacian' operator on graphs, proposed in [1]. Our focus is on random geometric graphs, where nodes are sampled independently from some unknown probability distributions. We aim to understand this limit, under appropriate scaling as the number of nodes increases, for clustering purposes.

[1] Generalized Spectral Clustering for Directed and Undirected Graphs. Harry Sevi, Matthieu Jonckheere, Argyris Kalogeratos. Link to the paper

Learning to Optimize Robotic Behaviors

Ludovic Righetti – December 14, 2023 – Slides

To walk, run, jump or manipulate objects, robots need to constantly interact with objects and the environment. Unfortunately, reasoning about physical interactions is a computationally daunting task. For this reason, robots try to avoid physical interactions at all costs and unexpected physical contacts often lead to failures. In this talk, I will present our recent approach(es) to break down this complexity: the formulation of optimal control problems that leverage machine learning (reinforcement learning) to achieve real-time efficiency and real-robot robustness. I will also demonstrate our algorithms on real manipulation and locomotion examples. Finally, I will discuss current challenges towards real robotic applications.

Introduction to Restless Multi Armed Bandits and Whittle Indices

Urtzi Ayesta – December 7, 2023, and January 11, 2024

We survey the basics of restless multi-armed bandit as introduced by Whittle (1988), and the Lagrangian relaxation approach that leads to the definition of Whittle's Index. We will derive an expression of Whittle's index for the the averaged cost criterion.

Talk based on:

Asymptotic Behavior of Fermat Distances in the Presence of Noise

Sebastian Zaninovich – November 23, 2023

Fermat distances are metrics defined to work with datasets supported on manifolds equipped with densities. These distances function as geodesics in the (complete) graph, penalizing long jumps between points. In this talk, we are going to present some (mathematical) motivation related to first passage percolation, some interesting questions that arise there, the original model, and introduce the noisy case. Our main result states that if the noise converges asymptotically to zero, then the noisy microscopic Fermat distance converges to the non-noisy macroscopic Fermat distance. The presentation is going to be focused on the mathematical aspects of the model, not on the applications.

Learning Optimal Admission Control in Partially Observable Queueing Networks

Bruno Gaujal – November 9, 2023 – Slides – Paper

In this talk, I will present an efficient reinforcement learning algorithm that learns the optimal admission control policy in a partially observable queueing network. Specifically, only the arrival and departure times from the network are observable, and optimality refers to the average holding/rejection cost in infinite horizon.

While reinforcement learning in Partially Observable Markov Decision Processes (POMDP) is prohibitively expensive in general, we show that our algorithm has a regret that only depends sub-linearly on the maximal number of jobs ($S$) in the network. In particular, in contrast with existing regret analyses, our regret bound does not depend on the diameter of the underlying Markov DecisionProcess (MDP), which in most queueing systems is at least exponential in $S$. The novelty of our approach is to leverage Norton’s equivalent theorem for closed product-form queueing networks and an efficient reinforcement learning algorithm for MDPs with the structure of birth-and-death processes.

This is a joined work with Jonatha Anselmi and Louis-Sébastien Rebuffi.

Prediction-based Coflow Scheduling

Olivier Brun – October 12, 2023 – Slides

We explore the problem of minimizing the weighted average coflow completion time of coflows when flow sizes are unknown but unreliable predictions on them are available. We propose to use Sincronia, a 4-approximation algorithm when actual flow sizes are known, directly on the predictions. For this variant of Sincronia, we obtain a finite upper bound on the approximation ratio that combines unreliability on predictions and the weights of the coflows. On several numerical experiments, it is shown that this bound is too conservative, and that in practice Sincronia with predictions has a much better performance on average as well as in the worst-case.

Convergence and Approximation Properties of Dropout in Neural Network Models

Albert Senen-Cerda – September 28, 2023 – Slides – Paper 1 – Paper 2 – Paper 3

Dropout (Hinton et al., 2012) is a well-known method to prevent overfitting in neural networks that temporarily ‘drops out’ nodes of the network at random during each step of the training with stochastic gradient descent.

In the first part of the talk, I will present general convergence guarantees for training neural networks with dropout and investigate its convergence rate using stochastic approximation techniques on simplified models for deep and shallow neural networks. Specifically, we examine theoretically and with simulations the dependence of the convergence rate on the width and depth of the neural network, and more importantly, on the dropout probability. For the considered models, we obtain explicit bounds for the convergence rate that depend on the dropout probability.

In the second part of the talk, we will then go on to analyze random neural networks that have dropout as their source of randomness and show that, despite this randomness, they still satisfy a universal approximation theorem.

Good Practices on Python

Claudia Lilian Ramirez – July 3, 2023 – Slides Part 1 – Instructions Part 2 – HTML Part 2 – Notebook Part 2 – Data Part 2

In this seminar I will be presenting some basic concepts on how to structure/produce a code correctly. This is not merely about “organizing” code, this has to do with making code simpler, efficient, readable, and therefore, “better”. You won't learn how to do anything “new”, but with luck you will learn how to make it faster and efficiently.

The seminar will be divided into 3 parts (a break between each part is considered). You can participate in just the first, or just first and second. But you cannot participate in the second part if you didn’t participate in the first, and so on. The seminar is made of “building blocks”, the latter needs the previous.

Coarsening Phase for the Condensing Zero Range Process

Inés Armendáriz – June 22, 2023

We prove a fluid limit for the coarsening phase of the condensing zero-range process on a finite number of sites. When time and occupation per site are linearly rescaled by the total number of particles, the evolution of the process is described by a piecewise linear trajectory in the simplex indexed by the sites. The linear coefficients are determined by the trace process of the underlying random walk on the subset of non-empty sites, and the trajectory reaches an absorbing configuration in finite time. A boundary of the simplex is called absorbing for the fluid limit if a trajectory started at a configuration in the boundary remains in it for all times. We identify the set of absorbing configurations and characterize the absorbing boundaries.

This talk is based on a joint work with J. Beltrán, D. Cuesta and M. Jara.

Reinforcement Learning in Product-Form Queueing Networks

Céline Comte – June 8, 2023 – Slides

We introduce a reinforcement-learning gradient-based method to optimize performance in product-form queueing networks. More specifically, we consider a queueing network whose equilibrium distribution is given, up to a multiplicative constant, as a product of differentiable functions of a vector of control parameters. Our main contribution is a novel expression of the gradient of the undiscounted return in the form of a covariance vector for which we can build an unbiased estimator. We evaluate this method numerically on several examples and compare its performance to that of classical reinforcement-learning methods. Our result can be generalized to other Markov decision processes, provided that we can build an estimator of the gradient of the logarithm of a stationary measure with respect to the vector of control parameters.

This talk is based on an ongoing work with Matthieu Jonckheere, Jaron Sanders, and Albert Senen Cerda.

Finite-time Convergence Guarantees of Contractive Stochastic Approximation: Mean-Square and Tail Bounds

Siva Theja Maguluri – June 2, 2023 – Slides – Paper 1 – Paper 2 – Paper 3

Motivated by applications in Reinforcement Learning (RL), this talk focuses on the Stochastic Appproximation (SA) method to find fixed points of a contractive operator. First proposed by Robins and Monro, SA is a popular approach for solving fixed point equations when the information is corrupted by noise. We consider the SA algorithm for operators that are contractive under arbitrary norms (especially the l-infinity norm). We present finite sample bounds on the mean square error, which are established using a Lyapunov framework based on infimal convolution and generalized Moreau envelope. We then present our more recent result on concentration of the tail error, even when the iterates are not bounded by a constant. These tail bounds are obtained using exponential supermartingales in conjunction with the Moreau envelop and a novel bootstrapping approach. Our results immediately imply the state-of-the-art sample complexity results for a large class of RL algorithms.

A Framework for Efficient Dynamic Routing under Stochastically Varying Conditions

Nikki Levering – May 30, 2023 – Paper 1 – Paper 2 – Slides

Despite measures to reduce congestion, both recurrent patterns (e.g., rush hours) and non-recurrent events (e.g., traffic incidents) cause large delays in highway networks with important economic implications. In this talk, we will introduce the Markovian Velocity Model (MVM), a framework capable of incorporating both effects. The model uses a Markov-modulated background process that tracks the random and (semi-)predictable events affecting the vehicle speeds in a highway network. The resulting continuous-time model, which allows for correlation between the velocities on the arcs, is highly flexible. This flexibility can be employed to operationalize the model in real-life traffic networks. The fitted model can then be used to predict travel-time distributions and, as a result, provide departure time and route guidance for travelers in such networks.

Machine Learning Applied to Physics

Claudia Lilian Ramírez – May 11, 2023 – Slides

ML allows us to understand the behavior of a system, without needing to fully understand the equations that describe such a system. Because of this, it is being applied in many problems where the equations are unknown, or even sometimes just too expensive to get the answers that we want.
In this talk I will present my current work, which is applying ML tools to fully explore an ignition process. Currently we are using Gaussian Processes, and we want to implement some reinforcement learning techniques.
I won't go into technical details, because I want to present the problem and discuss the next steps that are still not implemented. And if I did that (explain the physics, and then the different tools of machine learning) it would take me a lot of time. Instead, I will present the basic notions, and the concepts involved*.
* If you want to learn more about the physics or (probably) the math involved, you can find it on the internet, it's all there!

A Tour on Classical Methods for Dimension Reduction

Matthieu Jonckheere – March 30, 2023

We review some classical methods (in particular Spectral clustering and T-SNE) to deal with dimension reduction/low dimensional representation and clustering.

Fleming-Viot Based Optimisation to Tackle Barren Plateaus, with Application to Quantum Circuits

Daniel Mastropietro – March 24, 2023

The Fleming-Viot stochastic process has been proposed by W. Fleming and M. Viot in 1979 to model population genetics [1]. Driven by an underlying stochastic process with absorption, it has been proved useful to estimate the quasi-stationary distribution of such absorbing processes [2]. My recent work with the Fleming-Viot process has been two-fold: to help discover rare events such as queue blocking, and to optimise functions that present large barren areas, i.e. where the gradient is nearly zero. In this talk I will motivate how the Fleming-Viot process could help tackle the barren plateau problem with an application to finding the minimum energy in quantum circuits, where optimisation problems with large barren plateaus are ubiquitous [3].

References:
[1] Fleming W., Viot M. “Some Measure-Valued Markov Processes in Population Genetics Theory” (1979)
http://www.jstor.org/stable/24892583
[2] Asselah, A.; Ferrari, P. A.; Groisman, P. & Jonckheere, M. Fleming–Viot selects the minimal quasi-stationary distribution: The Galton–Watson case
Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Institute of Mathematical Statistics, 2016, 52, 647-668
https://doi.org/10.1214/14-aihp635
[3] McClean, J.R., Boixo, S., Smelyanskiy, V.N. et al. Barren plateaus in quantum neural network training landscapes. Nat Commun 9, 4812 (2018)
https://doi.org/10.1038/s41467-018-07090-4

Fluid Limit for a Multiclass Multiserver Random Order of Service Queue with Reneging

Eva Loeser – March 16, 2023

In this talk, we consider a multiclass multiserver queue with reneging operating under the random order of service discipline. Interarrival times, service times, and patience times are assumed to be generally distributed. We establish a fluid limit for a measure valued process that keeps track of the remaining patience time for each job in queue. We prove uniqueness for fluid model solutions under mild conditions and study the asymptotic behavior of fluid model solutions as time goes to infinity. This model is also of interest in studying the dynamics of enzymatic processing.

This talk is based on joint work with Ruth Williams.

Adversarial Examples: 10 Years of Worst Case

Gilles Tredan – March 9, 2023 – Slides

In machine learning, adversarial examples are inputs designed by an adversary to fool a target classifier.
More precisely, these examples are crafted by adding imperceptible noise to originally well-classified inputs in order to change the resulting classification.
Introduced almost a decade ago (2014), they generated a wide spectrum of research that ranges from very practical questions (can I fool an autonomous vehicle) to more fundamental ones (are there classifiers that resist adversarial inputs, and at which cost ?).
This talk is a humble introduction to these various topics by a non-expert.

The Critical Parameter of Fermat Distance

Matthieu Jonckheere – February 9, 2023

In statistical learning tasks such as clustering, recommendation, or dimension reduction, a notion of distance or similarity between points is crucial but might not be directly available as an input. In previous work, we proposed a new density-based estimator for weighted geodesic distances that takes into account the underlying density of the data, and that is suitable for nonuniform data lying on a manifold of lower dimension than the ambient space. The consistency of the estimator is proven using tools from first passage percolation. The macroscopic distance obtained depends on a unique parameter and we discuss the choice of this parameter and the properties of the obtained distance for machine learning tasks.

Stochastic Dynamic Matching in Graphs

Céline Comte – January 26 and February 16, 2023 – Paper 1 – Paper 2 – Slides

In this presentation, we will consider a stochastic dynamic matching model, in which items of different classes arrive according to independent Poisson processes, and compatibilities between items are described by an undirected graph on their classes. We will first focus on a specific matching policy called first-come-first-matched. Our main contribution is the observation that, under this policy, the matching model is equivalent to an order-independent (loss) queue, a model that has recently gained momentum in the queueing-theory community. Using this equivalence, we will formulate simpler proofs for several existing results and derive closed-form expressions for performance metrics like the waiting time of a class and the matching rate along an edge. In a second time, we will use results from graph theory and linear algebra to characterize the set of achievable matching rates under any matching policy.

The first part of this presentation is based on the paper “Stochastic non-bipartite matching models and order-independent loss queues” published in the journal Stochastic Models, Taylor & Francis (2022). The second part of this presentation is based on the recent preprint “Stochastic dynamic matching: a mixed graph-theory and linear-algebra approach” published in collaboration with Fabien Mathieu (LINCS) and Ana Bušić (Inria and PSL University).

Migration-Contagion Processes

Seva Shneer – January 12, 2022 – Paper

We consider the following migration process based on a closed network of $N$ queues with $K_N$ customers. Each station is a ./M/infty queue with service (or migration) rate mu. Upon departure, a customer is routed independently and uniformly at random to another station. In addition to migration, these customers are subject to an SIS (Susceptible, Infected, Susceptible) dynamics. That is, customers are in one of two states: I for infected, or S for susceptible. Customers can only swap their state either from I to S or from S to I in stations. More precisely, at any station, each susceptible customer becomes infected with the instantaneous rate $\alpha*Y$ if there are $Y$ infected customers in the station, whereas each infected customer recovers and becomes susceptible with rate $\beta$. We let $N$ tend to infinity and assume that $\lim_{N\to infty} K_N/N= \eta := \lambda/\mu$, where $\eta$ is a positive constant representing the customer density. The main question of interest is about the set of parameters of such a system for which there exists a stationary regime where the epidemic survives in the limiting system. The latter limit will be referred to as the thermodynamic limit. We establish several structural properties (monotonicity and convexity) of the system, which allow us to give the structure of the phase transition diagram of this thermodynamic limit w.r.t. $\eta$. The analysis of this SIS model reduces to that of a wave-type PDE for which we found no explicit solution. This plain SIS model is one among several companion stochastic processes that exhibit both migration and contagion. We discuss two of them as they provide variants to the plain SIS model as well as some bounds. These two variants are the SIS-DOCS (Departure On Change of State) and the SIS-AIR (Averaged Infection Rate), which both admit closed form solutions. The SIS-AIR system is a classical mean-field model where the infection mechanism based on the actual population of infected customers is replaced by a mechanism based on some empirical average of the number of infected customers in all stations. The latter admits a product-form solution. SIS-DOCS features accelerated migration in that each change of SIS state implies an immediate departure. This model leads to another wave-type PDE that admits a closed form solution. Our main focus is on the closed systems and their limits. The open systems consisting of a single station with Poisson input are instrumental in the analysis of the thermodynamic limits and are also of independent interest.

This is a joint work with François Baccelli and Sergey Foss.

Bayesian Limits in Structured PCA, and How to Reach Them

Manuel Saenz and Jean Barbier – December 15, 2022 – Paper

I will present recent results concerning the Bayesian estimation of low-rank matrices corrupted by structured noise, namely rotational invariant noise with generic spectrum. Using the replica method we derive the optimal performance limit. This is possible by exploiting the low-rank structure of the matrix signal implying that we can reduce the model to an effective quadratic model of the Ising type. Secondly, we show that the Approximate Message Passing (AMP) algorithm currently proposed in the literature for Bayesian estimation is sub-optimal. Exploiting the theory of Adaptive Thouless-Anderson-Palmer equations by Opper et al. we explain the reason for this sub-optimality and as a consequence we deduce an optimal Bayesian AMP algorithm with a rigorous state evolution matching the replica prediction.

Graph Adjacency Spectral Embeddings: Algorithmic Advances and Applications

Paola Bermolen – December 1, 2022

The random dot product graph (RDPG) is a tractable yet expressive generative graph model for relational data, that subsumes simple Erdős-Rényi and stochastic block model ensembles as particular cases. RDPGs postulate that there exist latent positions for each node and specify the edge formation probabilities via the inner product of the corresponding latent vectors. In this talk, we first focus on the embedding task of estimating these latent positions from observed graphs. The workhorse adjacency spectral embedding (ASE) offers an approximate solution obtained via the eigendecomposition of the adjacency matrix, which enjoys solid statistical guarantees but can be computationally intensive and is formally solving a surrogate problem. To address these challenges, we bring to bear recent non-convex optimization advances and demonstrate their impact to RDPG inference. We show the proposed algorithms are scalable, robust to missing network data, and can track the latent positions over time when the graphs are acquired in a streaming fashion; even for dynamic networks subject to node additions and deletions. We also discuss extensions to the vanilla RDPG to accommodate directed and weighted graphs. Unlike previous proposals, our non-parametric RDPG model for weighted networks does not require a priori specification of the weights’ distribution to perform inference and estimation in a provably consistent fashion. Finally, we discuss the problem of online monitoring and detection of changes in the underlying data distribution of a graph sequence. Our idea is to endow sequential change-point detection (CPD) techniques with a graph representation learning substrate based on the versatile RDPG model. We share an open-source implementation of the proposed node embedding and online CPD algorithms, whose effectiveness is demonstrated via synthetic and real network data experiments.

Population Models, Coalescent Processes, and Genetic Inference

Alejandro Hernandez Wences – November 24 and December 8, 2022

In this talk I will review neutral population models and describe their genealogies in terms of coalescent processes; in particular we will focus on the case where these are best described by Kingman’s coalescent. Then I will present the family of exponential models which incorporate the effect of natural selection, and whose genealogies are best described by the Bolthausen-Sznitman coalescent (although together with Emmanuel Schertzer we have found that this is not always the case). Finally, I will introduce the often used framework (in population genetics) of the site frequency spectrum for the inference of the genealogy of a real population from present-day genetic data. I will present a recent characterization of this statistic for the particular case of the Bolthausen-Sznitman coalescent.

This is a work in collaboration with Arno Siri-Jégousse.

Asymptotically Optimal Matching for the Online Stochastic Block Model

Nahuel Soprano Loto – November 11, 2022

The Online Stochastic Block Model (OSMB) in the dense regime can be informally described as follows. Nodes arrive one-by-one to the system at each time-step. The nodes can be of $K$ different colors. The color of the arriving node is drawn according to a fixed probability distribution. The arriving node, on arrival, tries to connect with any of the present nodes in the system. Each connection actually takes place with a probability that depends only on the colors of the involved nodes. In this way, at each time step, we obtain a random graph. We propose an online algorithm that, at each time-step, gives a matching of this random graph (a matching of a graph is a subset of pairwise disjoint edges). Under certain conditions, we prove that this algorithm is asymptotically optimal in the sense that the ratio between the cardinality of the matching and the total number of nodes converges to 1. The proof uses a non-trivial connection between the OSBM and a modification of the version of the Stochastic Matching model studied in [MM2016], and strongly relies on ideas developed in [JMSLR2022].

This is a work in collaboration with Matthieu Jonckheere and Pascal Moyal.

CIMI           LAAS       LAAS