nips nips2012 nips2012-102 nips2012-102-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Varun Kanade, Zhenming Liu, Bozidar Radunovic
Abstract: We consider the online distributed non-stochastic experts problem, where the distributed system consists of one coordinator node that is connected to k sites, and the sites are required to communicate with each other via the coordinator. At each time-step t, one of the k site nodes has to pick an expert from the set {1, . . . , n}, and the same site receives information about payoffs of all experts for that round. The goal of the distributed system is to minimize regret at time horizon T , while simultaneously keeping communication to a minimum. The two extreme solutions to this problem are: (i) Full communication: This essentially simulates the nondistributed setting to obtain the optimal O( log(n)T ) regret bound at the cost of T communication. (ii) No communication: Each site runs an independent copy – the regret is O( log(n)kT ) and the communication is 0. This paper shows the √ difficulty of simultaneously achieving regret asymptotically better than kT and communication better than T . We give a novel algorithm that for an oblivious √ adversary achieves a non-trivial trade-off: regret O( k 5(1+ )/6 T ) and communication O(T /k ), for any value of ∈ (0, 1/5). We also consider a variant of the model, where the coordinator picks the expert. In this model, we show that the label-efficient forecaster of Cesa-Bianchi et al. (2005) already gives us strategy that is near optimal in regret vs communication trade-off. 1
[1] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learnign and an application to boosting. In EuroCOLT, 1995.
[2] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[3] T. Cover. Universal portfolios. Mathematical Finance, 1:1–19, 1991.
[4] E. Hazan and S. Kale. On stochastic and worst-case models for investing. In NIPS, 2009.
[5] E. Hazan. The convex optimization approach to regret minimization. Optimization for Machine Learning, 2012.
[6] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71:291–307, 2005.
[7] V. Kanade, Z. Liu, and B. Radunovi´ . Distributed non-stochastic experts. In arXiv, 2012. c
[8] O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao. Optimal distributed online prediction. In ICML, 2011.
[9] J. Duchi, A. Agarwal, and M. Wainright. Distributed dual averaging in networks. In NIPS, 2010.
[10] A. Agarwal and J. Duchi. Distributed delayed stochastic optimization. In NIPS, 2011.
[11] G. Cormode, S. Muthukrishnan, and K. Yi. Algorithms for distributed functional monitoring. ACM Transactions on Algorithms, 7, 2011.
[12] Z. Huang, K. Yi, and Q. Zhang. Randomized algorithms for tracking distributed count, frequencies and ranks. In PODS, 2012.
[13] Z. Liu, B. Radunovi´ , and M. Vojnovi´ . Continuous distributed counting for non-monotone c c streams. In PODS, 2012.
[14] N. Cesa-Bianchi, G. Lugosi, and G. Stoltz. Minimizing regret with label efficient prediction. In ISIT, 2005.
[15] M-F. Balcan, A. Blum, S. Fine, and Y. Mansour. Distributed learning, communication complexity and privacy. In COLT (to appear), 2012.
[16] H. Daum´ III, J. M. Phillips, A. Saha, and S. Venkatasubramanian. Protocols for learning e classifiers on distributed data. In AISTATS, 2012.
[17] H. Daum´ III, J. M. Phillips, A. Saha, and S. Venkatasubramanian. Efficients protocols for e distributed classification and optimization. In arXiv:1204.3523v1, 2012.
[18] G. Cormode, M. Garofalakis, P. Haas, and C. Jermaine. Synopses for Massive Data - Samples, Histograms, Wavelets, Sketches. Foundations and Trends in Databases, 2012.
[19] K. Clarkson, E. Hazan, and D. Woodruff. Sublinear optimization for machine learning. In FOCS, 2010. 9