Workshop Programme
for period 12 - 16 August 2013
Modern probabilistic techniques for design and analysis of stochastic systems and networks
12 - 16 August 2013
Timetable
Monday 12 August | ||
09:00-09:50 | Registration | |
09:50-10:00 | Welcome by John Toland, Director of the Institute | |
10:00-10:45 | Robert, PH (INRIA Paris - Rocquencourt) | |
On the Fluid Limits of a Resource Sharing Algorithm with Logarithmic Weights | Sem 1 | |
The properties of a class of resource allocation algorithms for communication networks are presented in this talk.The algorithm is as follows: if a node of this network has x requests to transmit, then it receives a fraction of the capacity proportional to log(x), the logarithm of its current load. A fluid scaling analysis of such a network is presented. It is shown that several different times scales play an important role in the evolution of such a system. An interesting interaction of time scales phenomenon is exhibited. It is also shown that these algorithms with logarithmics weights have remarkable, unsual, fairness properties. A heavy traffic limit theorem for the invariant distribution is proved. Joint work with Amandine Veber. | ||
10:45-11:00 | Morning Coffee | |
11:00-11:45 | Shah, D (Massachusetts Institute of Technology) | |
Optimal queue-size scaling in switched networks | Sem 1 | |
We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input- queued switches, wireless networks and more recently data-centers. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. Designing a scheduling policy with optimal average queue-size for switched network has been a question of interest for a while now. As the main result, we shall discuss a new class of online scheduling policies that achieve optimal scaling for average queue-size for a class of switched networks including input-queued switches. Talk is based on work with Neil Walton (U of Amsterdam)+ Yuan Zhong (UC Berkeley). | ||
12:30-13:30 | Lunch at Wolfson Court | |
13:30-14:15 | Ward, AR (University of Southern California) | |
Routing and Staffing to Incentivize Servers in Many-Server Systems | Sem 1 | |
Co-authors: S. Doroudi, R. Gopalakrishnan, and A. Wierman
Traditionally, research focusing on the design of scheduling and staffing policies for service systems has modeled servers as having fixed (possibly heterogeneous) service rates. However, service systems are often staffed by people. Then, the rate a server chooses to work may be impacted by the scheduling and staffing policies used by the system. We present a model for such ``strategic servers'' that choose their service rate in order to maximize a trade-off between an ``effort cost'', which captures the idea that servers exert more effort when working at a faster rate, and a ``value of idleness'', which assumes that servers prefer to be idle as much as possible. In this strategic server framework, we re-visit classic scheduling and staffing questions in many-server systems, and, in particular, we investigate the performance of the common square-root safety staffing rule. | ||
14:15-14:30 | Afternoon Tea | |
14:30-15:15 | Rybko, AN (Russian Academy of Sciences) | |
Infinite Networks with Varying Topology - A Mean-Field Approach | Sem 1 | |
We consider a model of a queuing network, containing infinite moving servers (nodes). The customers of different types are getting into the network in corresponding entrance nodes and each of the customer c has an exit node D(c) which it needs to reach. On the way to its destination the customer visits some intermediate nodes, where it stays in queues. Service times distributions depend on the customer and on the node types. After being served at any node v, the customer c is sent to the server v' which is the closest to the destination server D(c). Once it gets to D(c), it leaves the network.
The main feature of the network is that its nodes are moving. So while the customer c is waiting in the queue in some node v, this node and its destination node D(c) can move. In such networks with moving nodes new effects take place, which are encountered in the situation with stationary nodes.
My talk is based on joint paper with Francois Baccelli and Senya Shlosman. Its main result can be described as follows: we start with the definition of the class of the networks with jumping nodes. The network can be finite or infinitely extended. In order to be able to treat them we consider the mean-field version of it, which consists of N copies of the network, interconnected in a mean-field manner. We show that as N increases, the limiting object becomes Non-Linear Markov Process in time. We establish the existence of the NLMP and the convergence to it. | ||
17:00-18:00 | Welcome reception |
Tuesday 13 August | ||
10:00-10:45 | Anandkumar , A (University of California, Irvine) | |
A Tensor Spectral Approach to Learning Mixed Membership Community Models | Sem 1 | |
Co-authors: Rong Ge (Princeton), Daniel Hsu (Microsoft Research), Sham Kakade (Microsoft Research)
Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al. 2008. This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebra operations, e.g. singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model. Related Links: http://newport.eecs.uci.edu/anandkumar/pubs/AnandkumarCommunity.pdf - manuscript | ||
10:45-11:00 | Morning Coffee | |
11:00-11:45 | Borkar, V (Indian Institute of Technology) | |
Miscellaneous gossip | Sem 1 | |
This talk will describe several problems related to gossip and related algorithms implemented on a network. These include: convergence issues for averaging schemes on graphs and a `learning' variant, distributed ranking algorithms on graphs, opinion dynamics on graphs and its optimization and/or control, etc. | ||
12:30-13:30 | Lunch at Wolfson Court | |
13:30-14:15 | Olvera-Cravioto, M (Columbia University) | |
Ranking algorithms on directed random networks | Sem 1 | |
The probabilistic analysis of information ranking algorithms on directed random networks, e.g., Google's PageRank, has recently led to natural approximations based on stochastic fixed-point equations whose explicit solutions can be constructed on weighted branching trees and whose tail behavior can be described in great detail. In this talk we present a model for generating directed random graphs with prescribed degree distributions where we can prove that the rank of a randomly chosen node does indeed converge to the solution of the corresponding fixed-point equation as the number of nodes in the graph grows to infinity. The proof of this result is based on classical random graph coupling techniques combined with the now extensive literature on the behavior of branching recursions on trees. The results we present are applicable to a wide class of linear algorithms on directed graphs, and have the potential to be extended to other max-plus type of recursions. This is joint work with Ningyuan Chen and Nelly Litvak. | ||
14:15-14:30 | Afternoon Tea | |
14:30-15:15 | Prabhakar, B (Stanford University) | |
Models of congestion and human response | Sem 1 | |
15:45-17:00 | Open Problems Session | |
17:00-18:30 | Poster Session |
Wednesday 14 August | ||
10:00-10:45 | Sanghavi, S (University of Texas at Austin) | |
Clustering Sparse Graphs | Sem 1 | |
Graph clustering involves the task of partitioning nodes, so that the edge density is higher within partitions as opposed to across partitions. A natural problem, it represents a first step in a wide array of applications in network analysis, community detection, recommendation systems etc.
A classic and popular statistical setting for evaluating between different solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this talk, we present a new algorithm for this problem, which improves by polynomial factors over the performance of all previous known algorithms. It is based on convex optimization, and draws a connection between this problem and a different field: high-dimensional statistical inference. | ||
10:45-11:00 | Morning Coffee | |
11:00-11:45 | Proutiere, A (KTH) | |
Bandit Optimisation with Large Strategy Sets: Theory and Applications | Sem 1 | |
In this talk, we report recent results on bandit optimisation problems with large strategy (or decision) sets. These problems naturally arise in many contemporary applications found in communication networks, e-commerce, and recommendation systems. We address both stochastic or adversarial settings, depending on the way rewards obtained under various strategies are generated. We provide lower bounds on regret, which provide fundamental performance limits that any online algorithm cannot beat, and develop algorithms that approach these limits. Results are applied to resource allocation in wireless networks, and recommendation systems. | ||
12:30-13:30 | Lunch at Wolfson Court | |
13:30-14:15 | Meyn, S (University of Illinois) | |
Ancillary service to the grid from deferrable loads: the case for intelligent pool pumps in Florida | Sem 1 | |
Renewable energy sources such as wind and solar power have a high degree of unpredictability and time-variation, which makes balancing demand and supply challenging. One possible way to address this challenge is to harness the inherent flexibility in demand of many types of loads. We focus on pool pumps, and how they can be used to provide ancillary service to the grid for maintaining demand-supply balance. The control solution is based on the following steps: 1. A Markov Decision Process (MDP) model is introduced for an individual pool pump. 2. Using the Todorov's formulation, a randomized control architecture is proposed, motivated by the need for decentralized decision making, and the need to avoid synchronization that can lead to large and detrimental spikes in demand. 3. An aggregate model for a large number of pools is obtained from a mean field limit. 4. A linearization of the eigenvector problem in (2) provides an LTI-system approximation of the aggregate nonlinear model, with a scalar signal as the input and a measure of the aggregate demand as the output. The final approximation is convenient for control design at the grid level. Simulations are provided to illustrate the accuracy of the models and effectiveness of the proposed control approach. | ||
14:15-14:30 | Afternoon Tea | |
14:30-15:15 | Reed, J (New York University) | |
High Frequency Asymptotics for the Limit Order Book | Sem 1 | |
We study the one-sided limit order book corresponding to limit sell orders and model it as a measure-valued process. Limit orders arrive to the book according to a Poisson process and are placed on the book according to a distribution which varies depending on the current best price. Market orders to buy periodically arrive to the book according to a second, independent Poisson process and remove from the book the order corresponding to the current best price. We consider the above described limit order book in a high frequency regime in which the rate of incoming limit and market orders is large and traders place their limit sell orders close to the current best price. Our first set of results provide weak limits for the unscaled price process and the properly scaled measure-valued limit order book process in the high frequency regime. In particular, we characterize the limiting measure-valued limit order book process as the solution to a measure-valued stochastic differential equation. We then provide an analysis of both the transient and long-run behavior of the limiting limit order book process. This is joint work with Peter Lakner and Sasha Stoikov. | ||
19:30-22:00 | Conference Dinner at Cambridge Union Society hosted by Cambridge Dining Company |
Thursday 15 August | ||
10:00-10:45 | van der Hofstad, R (TU Eindhoven) | |
Optimal flows on random graphs | Sem 1 | |
We investigate minimal-weight problems on the configuration model, in which flow passes through the network minimizing the total weight along edges. In practice, one is both interested in the actual weight of the minimal weight path, which represents its cost, as well as the number of edges used or hopcount, as this is often a good measure of the delay observed in the network.
We assume that the edge weights are independent continuous random variables, leading to first passage percolation on the configuration model. We then investigate the total weight and hopcount of the minimal weight path. We study how the minimal weight and hopcount depend on the structure of the edge weights as well as on the structure of the graph. Our proofs crucially rely on the connection between first passage percolation and continuous-time branching processes, which is due to the tree-like nature of the configuration model. The above research is inspired by transport in real-world networks, such as the Internet. Measurements have shown fascinating features of the Internet, such as the `small world phenomenon'. The small-world phenomenon states that typical distances in the network under consideration is small. Also, the degrees in the Internet are rather different from the degree structure in classical random graphs. Internet is a key example of a complex network, other examples being the Internet Movie Data Base, social networks, biological networks, the WWW, etc. [This is joint work with Gerard Hooghiemstra, Shankar Bhamidi, Piet Van Mieghem, Henri van den Esker and Dmitri Znamenski.] | ||
10:45-11:00 | Morning Coffee | |
11:00-11:45 | Salez, J (Université Paris 7 - Denis-Diderot) | |
Distances in large random regular networks | Sem 1 | |
We study the array of point-to-point distances in large random regular graphs equipped with exponential edge-lengths. The asymptotic marginal distribution of a single entry is now well-understood, thanks to the work of Bhamidi, van der Hofstad and Hooghiemstra (2010). In this talk, we will show that the whole array, suitably recentered, converges in the weak sense to a rather simple infinite random array. This confirms a prediction of David Aldous. | ||
12:30-13:30 | Lunch at Wolfson Court | |
13:30-14:15 | Holroyd, AE (Microsoft Research) | |
Self-organizing cellular automata | Sem 1 | |
Cellular automata display an extraordinary range of behavior, ranging from the very simple to the apparently chaotic, with many cases in between. Perhaps the most interesting rules are those that yield multiple behavior types from different initial conditions - this is common even for one-dimensional rules started from finitely-supported seeds. If a rule yields chaos from some initial conditions, it is tempting to conclude by analogy with the second law of thermodynamics that chaos should be prevalent from almost all initial conditions. For a certain natural class of rules, we prove that the opposite holds: typical (i.e. random) initial seeds self-organize into predictable (but non-trivial) evolution, while exceptional seeds generate more complicated behavior, including chaos. The key technique is the application of percolation arguments to the highly non-independent setting of space-time configurations of cellular automata.
Joint work with Janko Gravner. | ||
14:15-14:30 | Afternoon Tea | |
14:30-15:15 | Martin, JB (University of Oxford) | |
Forest fires and coagulation-deletion processes | Sem 1 | |
Consider the following extension of the Erdos-Renyi random graph process; in a graph on $n$ vertices, each edge arrives at rate 1, but also each vertex is struck by lightning at rate $\lambda$, in which case all the edges in its connected component are removed. Such a "mean-field forest fire" model was introduced by Rath and Toth. For appropriate ranges of $\lambda$, the model exhibits self-organised criticality. We investigate scaling limits, involving a multiplicative coalescent with an added "deletion" mechanism. I'll mention a few other related models, including epidemic models and "frozen percolation" processes. | ||
15:45-17:00 | Open Problems Session | |
17:00-18:30 | Poster Session |
Friday 16 August | ||
10:00-10:45 | Mandjes, M (Universiteit van Amsterdam) | |
Timescaling results for Markov modulated infinite-server systems and OU processes | Sem 1 | |
Co-authors: J. Blom (CWI), K. de Turck (Ghent), O. Kella (Jerusalem), D. Anderson (Wisconsin), H. Thorsdottir (CWI), G. Huang (Amsterdam), P. Spreij (Amsterdam)
In this talk I'll consider an infinite-server queue whose input is modulated by a Markovian background process, with a focus on the analysis of the number of customers in the system, both in the central-limit and the large deviations regime. In the scaling that we study, the background process is sped up by a factor N^f, while the arrival rate are scaled by N. Interestingly, in the CLT regime crucially different results come out for f > 1 and for f < 1; in the former case the input process essentially behaves as a (normal) Poisson process, while in the latter case the CLT involves deviation matrices. A similar distinction applies in the LD context. In the second part of the talk I'll address similar issues for the Markov modulated Ornstein-Uhlenbeck process. The last part of the presentation is about multiple infinite-servers systems (or multiple OU systems), modulated by a single background process, thus creating correlation between the individual components. A PDE that characterizes the joint distribution of all coordinates is derived, leading to recursive expressions for all moments. Also a multidimensional CLT is established. | ||
10:45-11:00 | Morning Coffee | |
11:00-11:45 | Blanchet, J (Columbia University) | |
Tolerance Enforced Simulation for Stochastic Differential Equations via Rough Path Analysis | Sem 1 | |
Consider a stochastic differential equation (SDE) driven by Brownian Motion which possesses a strong solution in the interval [0,t]. Given any tolerance error, say epsilon, defined in advance, we explain how to simulate a piece-wise linear path which approximates the underlying SDE in uniform norm in [0,t] with an error less than epsilon with probability one. The technique, as we shall explain, takes advantage of continuity estimates, studied in the theory of rough paths, of the Ito-Lyons map defining the underlying the SDE. (This presentation is based on joint work with Xinyun Chen and Jing Dong.) | ||
12:30-13:30 | Lunch at Wolfson Court | |
13:30-14:15 | Ganesh, A (University of Bristol) | |
On the secure connectivity of wireless sensor networks | Sem 1 | |
We consider a model of a wireless sensor network in which nodes are distributed uniformly at random over a unit square, and can communicate other nodes within a ?xed radius. This is the well-known random geometric graph model. In addition, each node is assigned a subset of cryptographic keys chosen uniformly at random from a key pool. Two nodes can communicate only if they are within range of each other, and possess at least one common key. We establish a connectivity threshold for these random graph models. This resolves a conjecture of Osman Yagan. Joint work with Bikash Dey, Santhana Krishnan and D. Manjunath. | ||
14:15-14:30 | Afternoon Tea | |
14:30-15:15 | Thorisson, H (University of Iceland) | |
Unbiased shifts of Brownian Motion | Sem 1 | |
Let $B = (B_t)_{t\in\mathbb{R}}$ be a two-sided standard Brownian motion. Let $T$ be a measurable function of $B$. Call $T$ an \emph{unbiased shift} if $(B_{T+t}-B_T)_{t\in\mathbb{R}}$ is a Brownian motion independent of $B_T$. We characterize unbiased shifts in terms of allocation rules balancing local times of $B$. For any probability distribution $\nu$ on $\mathbb{R}$ we construct a nonnegative stopping time $T$ with the above properties such that $B_T$ has distribution $\nu$. In particular, we show that if we travel in time according to the clock of local time at zero we always see a two-sided Brownian motion. A crucial ingredient of our approach is a new theorem on the existence of allocation rules balancing jointly stationary diffuse random measures on $\mathbb{R}$. We also study moment and minimality properties of unbiased shifts. |