Online Learning of Dynamic Parameters in Social Networks
This paper addresses the problem of online learning in a dynamic setting. We consider a social network in which each individual observes a private signal about the underlying state of the world and communicates with her neighbors at each time period. Unlike many existing approaches, the underlying state is dynamic, and evolves according to a geometric random walk. We view the scenario as an optimization problem where agents aim to learn the true state while suffering the smallest possible loss. Based on the decomposition of the global loss function, we introduce two update mechanisms, each of which generates an estimate of the true state. We establish a tight bound on the rate of change of the underlying state, under which individuals can track the parameter with a bounded variance. Then, we characterize explicit expressions for the steady state mean-square deviation(MSD) of the estimates from the truth, per individual. We observe that only one of the estimators recovers the optimal MSD, which underscores the impact of the objective function decomposition on the learning quality. Finally, we provide an upper bound on the regret of the proposed methods, measured as an average of errors in estimating the parameter in a finite time.
This paper addresses the problem of distributed 
      estimation of underlying dynamic states (which is a geometric random walk) 
      on a graph. Estimate the underlying state is not hard is all the 
      observations are globally known. The main challenge here is to perform 
      local update based on information available from neighbors only. The 
      authors cast the problem into an online minimization of a separable, 
      time-varying cost function and then provide two methods to perform local 
      update on each node by employing distributed dual averaging methods. The 
      two methods differ in the way they choose the local loss function. Then 
      the necessary conditions for the convergence of beliefs are established. 
      By defining the steady state mean square deviation, the authors 
      provide a regret analysis of the two methods and establish a bound for the 
      regret. This paper is technically sound. The organization of the 
      paper is logical and clear. Main results of the paper seem to be 
      correct. As pointed out by the authors, there is a previous work 
      focusing of distributed estimation of the underlying world given a simple 
      random walk model [9]. [9] solves the special case where the graph is 
      a complete graph. This paper changes the underlying state model to a 
      geometric random walk and the analysis are conducted on a more general 
      graph. However, the problem this paper target at is of limited 
      practical impact. The underlying state is a geometric random walk with 
      a constant rate of change, which is assumed to be known apriori to all 
      agents. This constant rate of change could limit the application of 
      the proposed methods. It is hard to find a real world scenario where 
      the model could be used. Maybe the author could provide more 
      motivating examples.