CaltechAUTHORS
A Caltech Library Service

Iterative maximum likelihood on networks

Mossel, Elchanan and Tamuz, Omer (2010) Iterative maximum likelihood on networks. Advances in Applied Mathematics, 45 (1). pp. 36-49. ISSN 0196-8858. https://resolver.caltech.edu/CaltechAUTHORS:20161109-165317769

 PDF - Submitted Version See Usage Policy. 165Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161109-165317769

Abstract

We consider n agents located on the vertices of a connected graph. Each agent v receives a signal X_v(0)∼N(μ,1) where μ is an unknown quantity. A natural iterative way of estimating μ is to perform the following procedure. At iteration t+1 let X_v(t+1) be the average of X_v(t) and of X_w(t) among all the neighbors w of v. It is well known that this procedure converges to X(∞) = 1/2 |E|^(−1) Σ d_v X_v where dv is the degree of v. In this paper we consider a variant of simple iterative averaging, which models “greedy” behavior of the agents. At iteration t, each agent v declares the value of its estimator X_v(t) to all of its neighbors. Then, it updates X_v(t+1) by taking the maximum likelihood (or minimum variance) estimator of μ, given X_v(t) and X_w(t) for all neighbors w of v, and the structure of the graph. We give an explicit efficient procedure for calculating X_v(t), study the convergence of the process as t→∞ and show that if the limit exists then X_v(∞)=X_w(∞) for all v and w. For graphs that are symmetric under actions of transitive groups, we show that the process is efficient. Finally, we show that the greedy process is in some cases more efficient than simple averaging, while in other cases the converse is true, so that, in this model, “greed” of the individual agents may or may not have an adverse affect on the outcome. The model discussed here may be viewed as the maximum likelihood version of models studied in Bayesian Economics. The ML variant is more accessible and allows in particular to show the significance of symmetry in the efficiency of estimators using networks of agents.

Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/j.aam.2009.11.004DOIArticle
http://www.sciencedirect.com/science/article/pii/S0196885809001237PublisherArticle
https://arxiv.org/abs/0904.4903arXivDiscussion Paper
ORCID:
AuthorORCID
Mossel, Elchanan0000-0001-7812-7886
Tamuz, Omer0000-0002-0111-0418
Additional Information:© 2009 Elsevier. Received 30 April 2009. Accepted 31 August 2009. Available online 3 December 2009. Supported by a Sloan fellowship in Mathematics, by BSF grant 2004105, by NSF Career Award (DMS 054829) by ONR award N00014-07-1-0506 and by ISF grant 1300/08. Supported by ISF grant 1300/08.
Funders:
Funding AgencyGrant Number
Alfred P. Sloan FoundationUNSPECIFIED
Binational Science Foundation (USA-Israel)2004105
NSFDMS 054829
Office of Naval Research (ONR)N00014-07-1-0506
Israel Science Foundation1300/08
Subject Keywords:Maximum likelihood; Sparse sensing; Learning on networks; Algebraic recursion relation; Bayesian Economics
Issue or Number:1
Classification Code:MSC: 62F12; 90B18; 91D30
Record Number:CaltechAUTHORS:20161109-165317769
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161109-165317769
Official Citation:Elchanan Mossel, Omer Tamuz, Iterative maximum likelihood on networks, Advances in Applied Mathematics, Volume 45, Issue 1, 2010, Pages 36-49, ISSN 0196-8858, http://dx.doi.org/10.1016/j.aam.2009.11.004. (http://www.sciencedirect.com/science/article/pii/S0196885809001237)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71904
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:11 Nov 2016 16:08