nips nips2013 nips2013-228 nips2013-228-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Shahin Shahrampour, Sasha Rakhlin, Ali Jadbabaie
Abstract: 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. 1
[1] M. H. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.
[2] A. Jadbabaie, P. Molavi, A. Sandroni, and A. Tahbaz-Salehi, “Non-bayesian social learning,” Games and Economic Behavior, vol. 76, no. 1, pp. 210–225, 2012.
[3] E. Mossel and O. Tamuz, “Efficient bayesian learning in social networks with gaussian estimators,” arXiv preprint arXiv:1002.0747, 2010.
[4] O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao, “Optimal distributed online prediction using mini-batches,” The Journal of Machine Learning Research, vol. 13, pp. 165–202, 2012.
[5] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor fusion based on average consensus,” in Fourth International Symposium on Information Processing in Sensor Networks. IEEE, 2005, pp. 63–70.
[6] S. Kar, J. M. Moura, and K. Ramanan, “Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication,” IEEE Transactions on Information Theory, vol. 58, no. 6, pp. 3575–3605, 2012.
[7] S. Shahrampour and A. Jadbabaie, “Exponentially fast parameter estimation in networks using distributed dual averaging,” arXiv preprint arXiv:1309.2350, 2013.
[8] D. Acemoglu, A. Nedic, and A. Ozdaglar, “Convergence of rule-of-thumb learning rules in social networks,” in 47th IEEE Conference on Decision and Control, 2008, pp. 1714–1720.
[9] R. M. Frongillo, G. Schoenebeck, and O. Tamuz, “Social learning in a changing world,” in Internet and Network Economics. Springer, 2011, pp. 146–157.
[10] U. A. Khan, S. Kar, A. Jadbabaie, and J. M. Moura, “On connectivity, observability, and stability in distributed estimation,” in 49th IEEE Conference on Decision and Control, 2010, pp. 6639–6644.
[11] R. Olfati-Saber, “Distributed kalman filtering for sensor networks,” in 46th IEEE Conference on Decision and Control, 2007, pp. 5492–5498.
[12] N. Cesa-Bianchi, Prediction, learning, and games. Cambridge University Press, 2006.
[13] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization: convergence analysis and network scaling,” IEEE Transactions on Automatic Control, vol. 57, no. 3, pp. 592–606, 2012.
[14] R. E. Kalman et al., “A new approach to linear filtering and prediction problems,” Journal of basic Engineering, vol. 82, no. 1, pp. 35–45, 1960.
[15] M. Mesbahi and M. Egerstedt, Graph theoretic methods in multiagent networks. University Press, 2010. Princeton
[16] J. A. Tropp, “User-friendly tail bounds for sums of random matrices,” Foundations of Computational Mathematics, vol. 12, no. 4, pp. 389–434, 2012.
[17] G. Biau, K. Bleakley, L. Gy¨ rfi, and G. Ottucs´ k, “Nonparametric sequential prediction of o a time series,” Journal of Nonparametric Statistics, vol. 22, no. 3, pp. 297–317, 2010.
[18] L. Gyorfi and G. Ottucsak, “Sequential prediction of unbounded stationary time series,” IEEE Transactions on Information Theory, vol. 53, no. 5, pp. 1866–1872, 2007.
[19] L. Gy¨ rfi, G. Lugosi et al., Strategies for sequential prediction of stationary time series. o Springer, 2000. 9