A1320
Title: FLIPHAT: Joint differential privacy for high dimensional linear bandits
Authors: Saptarshi Roy - UT Austin (United States) [presenting]
Abstract: High dimensional sparse linear bandits serve as an efficient model for sequential decision-making problems (e.g., personalized medicine), where high dimensional features (e.g., genomic data) on users are available, but only a small subset of them are relevant. Motivated by data privacy concerns in these applications, the joint differentially Private high dimensional sparse linear bandits setting is studied, where both rewards and contexts are considered as Private data. First, to quantify the cost of privacy, a lower bound on the regret achievable in this setting is derived. To further address the problem, a computationally efficient bandit algorithm, ForgetfuL Iterative Private Hard Thresholding (FLIPHAT), is designed. Along with doubling of episodes and episodic forgetting, FLIPHAT deploys a variant of Noisy Iterative Hard Thresholding (IHT) algorithm as a sparse linear regression oracle to ensure both privacy and regret-optimality. FLIPHAT achieves optimal regret in terms of privacy parameters, context dimension, and time horizon up to a linear factor in model sparsity in the problem independent case. The regret is analyzed by providing a novel refined analysis of the estimation error of IHT, which is of independent interest.
