Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits

Youming Tao, Yulian Wu, Peng Zhao, Di Wang

Research output: Contribution to conferencePaperpeer-review

3 Scopus citations

Abstract

In this paper we investigate the problem of stochastic multi-armed bandits (MAB) in the (local) differential privacy (DP/LDP) model. Unlike previous results that assume bounded/sub-Gaussian reward distributions, we focus on the setting where each arm's reward distribution only has (1 + v)-th moment with some v ∈ (0, 1]. In the first part, we study the problem in the central ε-DP model. We first provide a near-optimal result by developing a private and robust Upper Confidence Bound (UCB) algorithm. Then, we improve the result via a private and robust version of the Successive Elimination (SE) algorithm. Finally, we establish the lower bound to show that the instance-dependent regret of our improved algorithm is optimal. In the second part, we study the problem in the ε-LDP model. We propose an algorithm that can be seen as locally private and robust version of SE algorithm, which provably achieves (near) optimal rates for both instance-dependent and instance-independent regret. Our results reveal differences between the problem of private MAB with bounded/sub-Gaussian rewards and heavy-tailed rewards. To achieve these (near) optimal rates, we develop several new hard instances and private robust estimators as byproducts, which might be used to other related problems. Finally, experiments also support our theoretical findings and show the effectiveness of our algorithms.

Original languageEnglish (US)
Pages1546-1574
Number of pages29
StatePublished - 2022
Event25th International Conference on Artificial Intelligence and Statistics, AISTATS 2022 - Virtual, Online, Spain
Duration: Mar 28 2022Mar 30 2022

Conference

Conference25th International Conference on Artificial Intelligence and Statistics, AISTATS 2022
Country/TerritorySpain
CityVirtual, Online
Period03/28/2203/30/22

Bibliographical note

Funding Information:
Di Wang and Yulian Wu were support in part by the baseline funding BAS/1/1689-01-01 and funding from the AI Initiative REI/1/4811-10-01 of King Abdullah University of Science and Technology (KAUST). Peng Zhao was supported by the Baidu Scholarship.

Publisher Copyright:
Copyright © 2022 by the author(s)

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits'. Together they form a unique fingerprint.

Cite this