Dimitar Chakarov

Dimitar Chakarov, Lee Cohen, Nathan Srebro

We extend Incentive Compatible Exploration beyond the Bayesian full-information setting of Kremer et al. [2014]. We consider agents that may possess external information unknown to the principal. We show such settings require new notions of incentivized exploration, as well as going beyond a Bayesian perspective, and we introduce a definition where agents choose any reasonable (undominated) action. Furthermore, our framework provides for a more robust treatment of ties, and extends to settings where agents lack a single common prior and instead only know that reward distributions belong to a collection of potential priors.

Dimitar Chakarov, Nikita Tsoy, Kristian Minchev et al.

Federated learning (FL) is a distributed collaborative learning method, where multiple clients learn together by sharing gradient updates instead of raw data. However, it is well-known that FL is vulnerable to manipulated updates from clients. In this work we study the impact of data heterogeneity on clients' incentives to manipulate their updates. First, we present heterogeneous collaborative learning scenarios where a client can modify their updates to be better off, and show that these manipulations can lead to diminishing model performance. To prevent such modifications, we formulate a game in which clients may misreport their gradient updates in order to "steer" the server model to their advantage. We develop a payment rule that provably disincentivizes sending modified updates under the FedSGD protocol. We derive explicit bounds on the clients' payments and the convergence rate of the global model, which allows us to study the trade-off between heterogeneity, payments and convergence. Finally, we provide an experimental evaluation of the effectiveness of our payment rule in the FedSGD, median-based aggregation FedSGD and FedAvg protocols on three tasks in computer vision and natural language processing. In all cases we find that our scheme successfully disincentivizes modifications.