Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate

Nicolas Gast 1
1 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Mean-field approximation is a powerful tool to study large-scale stochastic systems such as data-centers – one example being the famous power of two-choice paradigm. It is shown in the literature that under quite general conditions, the empirical measure of a system of N interacting objects converges at rate O (1/ √ N) to a deterministic dynamical system, called its mean-field approximation. In this paper, we revisit the accuracy of mean-field approximation by focusing on expected values. We show that, under almost the same general conditions, the expectation of any performance functional converges at rate O (1/N) to its mean-field approximation. Our result applies for finite and infinite-dimensional mean-field models. We also develop a new perturbation theory argument that shows that the result holds for the stationary regime if the dynamical system is asymptotically exponentially stable. We provide numerical experiments that demonstrate that this rate of convergence is tight and that illustrate the necessity of our conditions. As an example, we apply our result to the classical two-choice model. By combining our theory with numerical experiments, we claim that, as the load ρ goes to 1, the average queue length of a two-choice system with N servers is log 2 1 1−ρ + 1 2N (1−ρ) + O 1 N 2 .
Type de document :
Communication dans un congrès
ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems SIGMETRICS '17 , Jun 2017, Urbana-Champaign, United States. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1, pp.26, 2017, ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems SIGMETRICS '17 〈https://www.sigmetrics.org/sigmetrics2017/〉. 〈10.1145/2896377.2901463〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01553133
Contributeur : Nicolas Gast <>
Soumis le : mardi 4 juillet 2017 - 10:13:23
Dernière modification le : jeudi 11 octobre 2018 - 08:48:05

Fichier

mf_rate_convergence(1).pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Nicolas Gast. Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate. ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems SIGMETRICS '17 , Jun 2017, Urbana-Champaign, United States. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1, pp.26, 2017, ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems SIGMETRICS '17 〈https://www.sigmetrics.org/sigmetrics2017/〉. 〈10.1145/2896377.2901463〉. 〈hal-01553133〉

Partager

Métriques

Consultations de la notice

328

Téléchargements de fichiers

209