(Locally) Differentially Private Combinatorial Semi-Bandits

Jul 12, 2020



In this paper, we study (locally) differentially private Combinatorial Semi-Bandits (CSB). Compared with private Multi-Armed Bandits (MAB), since the server receives more information from the user, it usually leads to additional dependence over the dimension of feedback, which is a notorious problem in private learning. Somewhat surprisingly, we show that it is possible to remove this side-effect caused by privacy protection and nearly match corresponding non-private best results. In detail, for general CSB with B-bounded smooth reward function in the sense of Chen et al. 2016, we propose a novel algorithm that achieves regret bound Õ(mB^2log T / ϵ) over T rounds under ϵ-local differential privacy, where m is the number of base arms. However, for Linear CSB, B equals K, where K is the maximum number of feedback in each round, and above bound has an additional K compared with non-private optimal result. We then propose a different algorithm with nearly optimal regret bound Õ(mKlog T / ϵ) if one cares about ϵ-differential privacy rather than ϵ-local differential privacy. Besides, we also prove some lower bounds in each setting.



About ICML 2020

The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%


Recommended Videos

Presentations on similar topic, category or speaker