{"id":163762,"date":"2012-12-01T00:00:00","date_gmt":"2012-12-01T00:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/distributed-non-stochastic-experts\/"},"modified":"2018-11-09T01:25:42","modified_gmt":"2018-11-09T09:25:42","slug":"distributed-non-stochastic-experts","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/distributed-non-stochastic-experts\/","title":{"rendered":"Distributed Non-Stochastic Experts"},"content":{"rendered":"<div class=\"asset-content\">\n<p>We consider the online distributed non-stochastic experts problem, where the distributed system consists of one coordinator node that is connected to <i>k<\/i> sites, and the sites are required to communicate with each other via the coordinator. At each time-step <i>t<\/i>, one of the <i>k<\/i> site nodes has to pick an expert from the set <i>{1, \u2026, n}<\/i>, 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 <i>T<\/i>, while simultaneously keeping communication to a minimum. The two extreme solutions to this problem are:<\/p>\n<ol>\n<li>Full communication: This essentially simulates the non-distributed setting to obtain the optimal <i>O(\u221alog (n)T)<\/i> regret bound at the cost of <i>T<\/i> communication.<\/li>\n<li>No communication: Each site runs an independent copy \u2013 the regret is <i>O(\u221alog (n)kT)<\/i> and the communication is <i>0<\/i>. This paper shows the difficulty of simultaneously achieving regret asymptotically better than <i>\u221akT<\/i> and communication better than <i>T<\/i>. We give a novel algorithm that for an oblivious adversary achieves a non-trivial trade-off: regret <i>O(\u221ak<sup>5(1 + \u03b5)\/6<\/sup>T)<\/i> and communication <i>O(T\/k<sup>\u03b5<\/sup>)<\/i>, for any value of <i>\u03b5 \u2208 (0, 1\/5)<\/i>.<\/li>\n<\/ol>\n<p>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.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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, [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13556,13547],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-163762","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-artificial-intelligence","msr-research-area-systems-and-networking","msr-locale-en_us"],"msr_publishername":"Neural Information Processing Systems Foundation","msr_edition":"","msr_affiliation":"","msr_published_date":"2012-12-1","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"205747","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/long_version.pdf","id":"205747","title":"long_version.pdf","label_id":"243109","label":0},{"type":"file","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/main-31.pdf","id":"205746","title":"main.pdf","label_id":"243109","label":0}],"msr_related_uploader":"","msr_attachments":[{"id":205747,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/long_version.pdf"},{"id":205746,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/main-31.pdf"}],"msr-author-ordering":[{"type":"text","value":"Varun Kanade","user_id":0,"rest_url":false},{"type":"text","value":"Zhenming Liu","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Bozidar Radunovic","user_id":31286,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Bozidar Radunovic"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[171035],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":171035,"post_title":"Big Data Analytics","post_name":"big-data-analytics","post_type":"msr-project","post_date":"2012-10-18 14:31:33","post_modified":"2019-08-19 14:57:01","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/big-data-analytics\/","post_excerpt":"We conduct research in the area of algorithms and systems for processing massive amounts of data. Our work aims at pushing the boundary\u00a0of\u00a0computer science\u00a0in the area of algorithms and systems for large-scale computations. Our mission is to\u00a0achieve\u00a0major technological breakthroughs\u00a0in order to facilitate\u00a0new\u00a0systems and services relying on efficient processing of big data. Research Areas Database queries - How can we efficiently resolve database queries on massive amounts of input data? Here the input data may be&hellip;","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/171035"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163762"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163762\/revisions"}],"predecessor-version":[{"id":404105,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163762\/revisions\/404105"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=163762"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=163762"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=163762"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=163762"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=163762"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=163762"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=163762"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=163762"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=163762"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=163762"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=163762"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=163762"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=163762"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=163762"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=163762"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=163762"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}