Seminar by the RAP team (Algorithm and Probability Networks)
Seminars organised by the RAP project-team. Free entry.
- Date : 16/12/2010
- Place : Rocquencourt, building 9
- Guest(s) : Nicolas Gast (EPFL) and Florence Bénézit, TREC, Inria Paris-Rocquencourt
- Organiser(s) : RAP
At 10.00 am - Nicolas Gast (Federal Polytechnic School of Lausanne )
Mean field limits for controlled systems.
The study of complex systems composed of a large number of interacting objects often becomes intractable as the size of the system grows. The mean field approximation provides a efficient framework for analysing the behaviour of such systems.
In this talk, I will explain how to use stochastic approximation methods to study mean field models. This allows one to obtain generic convergence results for the convergence of the macroscopic dynamic to a deterministic one. Using this approach, I will present how to extend classical mean field methods to study the control and the optimal control of large stochastic systems. I will first show that as the number of objects of the system grows, solving an optimal control problem for a stochastic system can be reduced to the solving of a
deterministic optimisation problem. Then, I will present how to study the limiting behaviour of the controlled system using differential inclusions.
In practice, this allows one to easily evaluate the performance of a policy and provide a way to asymptotically solve problems that used to be intractable. Some examples will be provided, illustrating these facts.
2.00 pm - F
lorence Bénézit, TREC, Inria Paris-Rocquencourt
One-Way Averaging in Networks
Many algorithms have been developed in recent years to compute averages in a distributed way. Each node in a connected network holds a value and wants to know the global average of these values based on local message passing only. The most famous algorithms (gossip) iterate local averaging until convergence to the global average. The speed of convergence of a gossip algorithm depends on the topology of the network and on the sequence of the random groups of nodes that are averaged together at each round.
It has been shown that averaging random routes in a lattice or in a random geometric graph is order optimal: it necessitates O(n log n) messages to converge with high probability at a precision of 1/n. Path averaging is very efficient but it is not robust in unreliable networks. Indeed, to average the values of a route of nodes, messages should be sent from the
source of the route to the destination and then from the destination back to the source. In a mobile network or in a network with unreliable links, routing a message back on a given route might be difficult or even impossible.
This talk investigates a broad class of algorithms that allow unidirectional averaging. It is a generalisation of the Push-Sum protocol, which was proven to converge only in the case of synchronous rounds in complete graphs. We will show that the algorithm also works asynchronously in any connected network, which is a key feature for distributed networks. Simulations show that one-way path averaging converges faster than regular path-averaging, and we will explain what the challenges are in computing the speed of convergence of one-way averaging algorithms.