Collaborative Top Distribution Identifications with Limited Interaction

February 10, 2023

2023   ·   circuits   complexity     ·   spring-2023  

Speaker

Nikolai Karpov February 10, 2023.

Abstract

We consider the following problem: given a set of n distributions, find the top-m ones with the largest means. This problem is also called top-m arm identifications in the literature of reinforcement learning, and has numerous applications. We study the problem in the collaborative learning model where we have multiple agents who can draw samples from n distributions in parallel. In this talk, we discuss tradeoffs between the running time of learning process and the number of rounds of interaction between agents.

Based on joint work with Qin Zhang and Yuan Zhou



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Redundancy and Resilience in Distributed Optimization
  • Reconstructing Graphs from Random Subgraphs.
  • Derandomization from Time-Space Tradeoffs
  • Are quantum speedups for learning expressive classes possible?
  • Approximating CSPs in the streaming setting