Inria
Inria.fr
Inria Channel
Séminaire : RAP
Séminaire RAP (Réseaux Algorithmes et Probabilités)
Séminaires organisés par l'équipe-projet RAP, entrée libre.
- Date : 16/12/2010
- Lieu : Rocquencourt, bâtiment 9
- Intervenants : Nicolas Gast (EPFL) and Florence Bénézit, TREC, Inria Paris-Rocquencourt
- Organisateurs : RAP
A 10 h 00 - Nicolas Gast (EPFL)
Mean field limits for controlled system.
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 analyzing the behavior 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 optimization problem. Then, I will present how to study the limiting behavior 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.
A 14 h 00 - Florence Bénézit, TREC, Inria Paris-Rocquencourt
One-Way Averaging in Networks
Many algorithms were developed in the last 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 was 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 generalization 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 are the challenges in computing the speed of convergence of one-way averaging algorithms.
Mots-clés : Paris - Rocquencourt Séminaire RAP
